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?



1 Answer 1


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.)

  • 1
    $\begingroup$ Actually, I think this is the right answer (+1), and as such, it's fine that it isn't a comment. $\endgroup$
    – jbowman
    Commented Mar 28, 2014 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.