# Law of large numbers for non-identically distributed Bernoulli random variables

Let $(X_n)$ be a succession of independent r.v., such that $X_n$ ~ $Bern(p_n)$. I know then that $\lim_{n \to \infty}p_n=p$ and $p_n>p>0$ for each $n \in \mathbb{N}$. I have to prove that

$\dfrac{X_1 + \dots + X_n}{n} \rightarrow p$

almost surely.

Intuitively, by the strong law of large numbers, I would say it is true. The problem is that the succession $p_n$ is not constant, so I do not know how to conclude in a formal way.

Thanks to who will solve my doubt.

• If you know Kolmogorov's strong law, then the assertion is a straight-forward consequence of this result. – saz Sep 5 '17 at 6:15
• Don't we need to assume that both $p_n$ and $p$ must be bounded away from 1 as well? – Konstantinos I. Stouras Apr 21 at 0:39

This answer is based on a coupling argument, which makes rigorous the comment by LJG in the answer by Davide Giraudo. We will assume the (usual) strong law of large numbers for i.i.d. sequences, but nothing else.

Namely, let $X_n$ be independent random variables with $X_n \sim Bern(p_n)$ where $p_n \downarrow p$. Define a sequence $Y_n$ of i.i.d. Bernoulli($p$) random variables as follows. If $X_n=0$, let $Y_n=0$. If $X_n=1$, flip an (independent, unfair) coin, whose probability of heads is $1-p/p_n$. If heads, let $Y_n=0$. If tails let $Y_n=1$. Clearly $Y_n \leq X_n$ for all $n$, and the $Y_n$ are i.i.d. Bern($p$). By the strong law of large numbers $$\liminf_{n \to \infty}\frac{1}{n} \sum_1^n X_k \geq \liminf_{n \to \infty}\frac{1}{n} \sum_1^n Y_k =p, \;\;\;\;\;\;\;a.s.$$

Now let $q>p$. For large enough $n$ we have that $p_n<q$. Since the limit of Cesaro means does not depend on the omission of some finite number of terms, we may assume wlog that $p_n<q$ for all $n$. We now define a sequence $Z_n$ of i.i.d. Bernoulli($q$) random variables as follows. If $X_n=1$, let $Z_n=1$. If $X_n=0$, flip an (independent, unfair) coin, whose probability of heads is $(q-p_n)/(1-p_n)$. If heads, let $Z_n=1$. If tails let $Z_n=0$. Clearly $Z_n \geq X_n$ for all $n$, and the $Z_n$ are i.i.d. Bern($q$). By the strong law of large numbers, $$\limsup_{n \to \infty}\frac{1}{n} \sum_1^n X_k \leq \limsup_{n \to \infty}\frac{1}{n} \sum_1^n Z_k =q, \;\;\;\;\;\;\;a.s.$$ But since $q>p$ was arbitrary, we conclude (after taking the intersection over countably many $q$'s converging down to $p$) that $$\limsup_{n \to \infty}\frac{1}{n} \sum_1^n X_k \leq p, \;\;\;\;a.s.$$ which gives the result.

• Very nice! This is what I meant by my comment to Davide Giraudo's answer. Though I would prefer to write that wlog $X_n = \mathbf1_{U_n<p_n}$, where $U_1,U_2,\dots$ are independent uniform $U[0,1]$ random variables. And then define $Y_n = \mathbf1_{U_n<p}$, $Z_n = \mathbf1_{U_n<q}$. Essentially this is the same as you wrote, but this way one does not have to flip additional coin and compute those probabilities. Anyway, +1 from me. – zhoraster Sep 6 '17 at 5:35
• You are right... that would have been nicer to read! – Shalop Sep 6 '17 at 13:50
• What happens if the sequence ${p_n}$ does not converge to $p$? That is, each $X_n$ is drawn from a different distribution. It seems to me that in this case the LLN does not hold. Is this correct? – Confounded Mar 23 '18 at 9:51

This answer uses the following statement

Let $(Y_i)_{i \in \mathbb{N}}$ be a sequence of independent random variables. If $\sum_{i=0}^n Y_i$ converges in probability, then $\sum_{i=0}^n Y_i$ converges almost surely.

Hints:

1. Set $T_n := \sum_{i=1}^n (X_i-p_i)/i$. Use the independence of the random variables $X_i$ to show that $$\mathbb{E}((T_n-T_m)^2) \leq 4 \sum_{i=m+1}^n \frac{1}{i^2}$$ for all $n \geq m$. Conclude that the limit $$\sum_{i=1}^{\infty} \frac{X_i-p_i}{i} := \lim_{n \to \infty} T_n$$ exists in $L^2$ and, hence, in probability.
2. Deduce from Step 1 that $\sum_{i=1}^{n} (X_i-p_i)/i$ converges almost surely as $n \to \infty$.
3. Apply the Kronecker lemma to conclude that $$\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n (X_i-p_i)=0$$ almost surely.

Remark: Using the above reasoning it is actually possible to show the following more general result which is known as "Kolmogorov's strong law"

Let $(X_i)_{i \in \mathbb{N}} \subseteq L^2(\mathbb{P})$ be a sequence of independent random variables. If $$\sum_{i \geq 1} \frac{\text{var} \, (X_i)}{i^2} < \infty$$ then $$\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n (X_i-\mathbb{E}(X_i))=0 \quad \text{almost surely.}$$

• You are applying a version of the law of large numbers for non identically distributed random variables. My guess is that specifying the details of this result would be useful to the OP. – Did Sep 4 '17 at 18:48
• @Did Well, yes, you are right ... I've rewritten my answer. – saz Sep 5 '17 at 6:16
• It is worth to mention that you prove a stronger result assuming only the Cesaro convergence $(p_1+\dots+p_n)/n\to p, n\to\infty$. – zhoraster Sep 5 '17 at 19:48

Let $S_n:=\sum_{i=1}^n\left(X_i-p_i\right)$. Use Kolmogorov's inequality to get a good bound for $$\mathbb P\left\{\max_{1\leqslant n\leqslant 2^N}\left\lvert S_n\right\rvert \gt 2^N\varepsilon \right\}.$$ Then use the Borel-Cantelli lemma to get that $S_n/n\to 0$ almost surely.

• We have never studied Kolmogorov's inequality. However, I have tried to develop your idea but I do not understand how you can conclude using the Borel-Cantelli lemma. – LJG Sep 4 '17 at 20:18
• The sum over $N$ of the expression in the display expression is finite. – Davide Giraudo Sep 4 '17 at 20:30
• @LJG Since you didn't provide us any information on your background, it's pretty hard to write an answer which does not use results which you haven't studied. How are we supposed to know what you have already studied? – saz Sep 5 '17 at 6:11
• I thought this solution, could it be correct? Define $S_n = X_1 + \dots + X_n$ and let $\bar{p} = p+\epsilon$ ($\epsilon > 0$). Because $p_n \rightarrow p$ then exists $N \in \mathbb{N}$ such that $p \le p_n \le \bar{p}$ for each $n \ge N$. So we have $p+\epsilon = \bar{p} \ge \limsup_{n \to \infty}\frac{S_n}{n} \ge \liminf_{n \to \infty}\frac{S_n}{n} \ge p$. It ends with $\epsilon \rightarrow 0$. – LJG Sep 5 '17 at 12:05
• @LJG, nice idea. Yes, one can make a rigorous proof out of that. – zhoraster Sep 5 '17 at 19:51