# tight bound of bernoulli sums with unknown dependency

Consider n random variables $X_1, \ldots, X_n$ all follow same bernoulli distribution of mean $p$. But the dependency of these variables are unknown (i.e., cannot assume that they are independent).

Define $Y=\sum_1^n X_i$, then can I get a lower bound of $\Pr[Y \leq t\cdot n]$ (e.g., I want to get $p_\tau$ such that $\Pr[Y \leq t\cdot n] > p_\tau$) which is tighter than applying the Markov inequality?

Thanks.

Sorry if this is not a useful insight, but the first thing that came to my mind was that for all we know, it could be that $X_1=\ldots=X_n$, so that $Y=nX_1$ and $\{Y\leq nt\}=\{X_1\leq t\}$. This (in a sense most extreme case of being dependent) reduces your question to the study of the CDF of a Bernoulli random variable. (I wanted to post this as a comment but could not, perhaps because I lack the reputation. Surely there are results for your problem that use some model for the dependency and give more useful results.)