# Is the sum of low-probability dependent Bernoulli variables close to zero with high probability?

Assume $$X_1,\dots,X_n$$, $$X_i\sim \mathrm{Ber}(\epsilon)$$ are (possibly) dependent Bernoulli random variables with $$P(X_i=1) = 1-P(X_i=0) = \epsilon$$ for all $$1\leq i\leq n$$ and denote $$Y_n = \sum_{i=1}^n X_i$$.

Question. Is it true that for any $$\epsilon>0$$, there exists $$n_0 \in \mathbb{N}$$ such that for all $$n \geq n_0$$ and for all random variables $$X_1,\dots,X_n$$ with marginal distributions $$X_i \sim \mathrm{Ber}(\epsilon)$$, we have $$P\left(Y_n\leq 2 \epsilon n\right) \geq 1-\epsilon?$$

If the above question is answered with "no", can we choose a different (larger) constant $$c$$ instead of $$2$$ to make this statement correct?

Here is my thought process: For independent variables this statement is directly correct due to, e.g., the weak law of large numbers. Also, for very dependent variables, i.e., $$X_1=\dots=X_n$$ this statement is correct, since $$P\left(Y_n\leq 2\epsilon n\right) = 1-\epsilon$$ (the probability that all $$X_1=\dots=X_n=0$$ is $$1-\epsilon$$). I am unsure however about other possible dependencies.

I will be glad about any hints or references to the literature.

• Consider making the quantifiers on your $n$ and $\epsilon$ clearer. What does it exactly mean when you say "for large enough $n$ and any $\epsilon>0$? Does it mean it holds for all $n,\epsilon>0$? Or that for any $n$, one might choose a suitable $\epsilon$? Or vice versa? The answer might depend crucially on such mundane details as quantifier order. Commented Sep 4, 2021 at 21:28
• Thanks for pointing this out. I was wondering if for any fixed $\epsilon$, there exists a $n_0$ such that the statement is true for all $n\geq n_0$. I edited the question accordingly. Commented Sep 4, 2021 at 21:34
• A related paper on the strong law of large numbers for dependent Bernoulli variables: arxiv.org/abs/2008.00318 Commented Sep 5, 2021 at 6:21

I am still confused about the intended quantifier order, but let me rewrite the question as I think it is meant.

Question. Is the following claim true? For all $$\epsilon>0$$, there exists $$n_0$$ such that for all $$n>n_0$$ and for all $$\text{Bernoulli}(\epsilon)$$ random variables $$X_1,\ldots,X_n$$ we have $$P(\sum_i X_i \le 2\epsilon n) \ge 1-\epsilon$$.

Assuming this is the meaning, the answer is no. One counterexample suffices to prove the claim false, but you can also modify its parameters for other similar claims (e.g. if the 2 is replaced with some other constant).

Let $$\epsilon=0.01$$ and $$n=100k$$, where $$k$$ is any positive integer. Let $$X_i$$ be dependent in this way: With $$1/4$$ probability, a randomly chosen subset of $$4k$$ of them are ones, and the other $$96k$$ are zeros. With $$3/4$$ probability, all $$X_i$$ are zeros. Clearly for any $$i$$ we have $$P(X_i=1) = (1/4)(4k/100k) = 0.01 = \epsilon$$ as required.

But we have $$1/4$$ probability that $$Y_n = \sum_i X_i = 4k$$. So $$P(Y_n \le 2\epsilon n) = P(Y_n \le 2k) = 3/4$$, much less than $$1-\epsilon=0.99$$.

## Weaker claim (This time it is true)

But the title of the question asks for something much weaker: is the sum close to zero with high probability? Yes, this we can prove, but we just cannot be too greedy with those two things, "close" and "high", at the same time. Let's be more moderate, and then we can do it.

Claim. Let $$\epsilon>0$$ and $$n \in \mathbb{Z}_+$$ be arbitrary. Let $$X_1,\ldots,X_n$$ be $$\text{Bernoulli}(\epsilon)$$ variables and $$Y_n=\sum_{i=1}^n X_i$$. Then for any $$c>0$$ we have $$P(Y_n \le cn\epsilon) \ge 1-1/c.$$

Proof. $$Y_n$$ is a nonnegative random variable with $$\mathbb{E}Y = n\epsilon$$. The claim follows from Markov's inequality.

For example, if we take $$c=1/\sqrt{n\epsilon}$$, then we have something reminiscent of the original question: $$P(Y_n \le \sqrt{n \epsilon}) \ge 1-\sqrt{n\epsilon}.$$

So you will have $$Y_n$$ "close to zero with high probability" after all. Just don't be too greedy about it.

• I honestly don't quite get the reason for your confusion, but this answer solves my issue. Thanks a lot for coming up with a counterexample and figuring the weaker statement using Markov's inequality. I'll edit my question to avoid confusion for future readers. Commented Sep 6, 2021 at 12:07
• I guess I was reading your question too literally: First you had some $n$ Bernoulli variables, then the question was if for all $\epsilon$ and large enough $n$ something happens. But $n$ was already fixed when you chose your $n$ Bernoulli variables... Commented Sep 6, 2021 at 12:21