# Question about Strong Law of Large Numbers in Breiman

I was reading through Breiman's Probability on Strong Large Numbers and got stuck on a part of its proof. It goes:

Let $\Omega$={0,1}$^\mathbb N$ and $S_n$=$\sum_{k=1}^n\omega_k$.

If $C$={$\omega\in\Omega$ : $\lim_{n\to \infty}$$S_n(\omega)/n={1\over 2}}, and \hat C={\omega\in\Omega : \lim_{m\to \infty}$$S_{m^2}$($\omega$)/$n$=${1\over 2}$}, then $C=\hat C$.

I tried to prove this on my own, but cannot seem to make any progress, or find where to start. Any help on how to start this proof or the proof itself would be greatly appreciated. Thank you.

Edit: Grammar, formatting

• Why $m^2$? What is the relationship (if any) between $m$ and $n$? – herb steinberg Sep 14 '18 at 23:54
• He shows that $P(\hat C)=1$ and then extends that to $P(C)=1$ in the text. There is a proof in the text for this issue, but I cannot seem to fathom the logic behind it. – Mog Sep 14 '18 at 23:57
• Typo? I think the condition in $\hat C$ should be $\lim_{m\to\infty} S_{m^2}(\omega)/m^2=\frac12$ – grand_chat Sep 15 '18 at 0:00
• You're right. That's a typo on my part. Edited now, thanks! – Mog Sep 15 '18 at 0:01
• Correcting the typo gets $\hat{C}=C$. $P(C)=1$ is not apparent. – herb steinberg Sep 15 '18 at 0:06

I have Breiman's proof in front of me, so I can attempt to explain it more clearly.

The assertion that $C=\hat C$ is an assertion about sequences of zeros and ones, so we can suppress the $\omega$ by focusing on just one sequence.

The inclusion $C\subset \hat C$ is trivial: if a sequence $x_n$ converges to zero as $n\to\infty$, then it also converges along the sequence $n_k:=k^2$. So the hard direction is proving that if $S_{m^2}/m^2\to\frac12$, then so does $S_n/n$.

Suppose $S_{m^2}/m^2\to\frac12$. Let $\epsilon>0$. To show $S_n/n\to\frac12$, the obvious first step is to write, using the triangle inequality, $$\left|\frac{S_n}n-\frac12\right|\le\left|\frac{S_n}n-\frac{S_{m^2}}{m^2}\right|+ \left|\frac{S_{m^2}}{m^2}-\frac12\right|.\tag1$$ But the second term on the RHS of (1) tends to $0$ as $m\to\infty$. So for all large $m$, say $m\ge M$, we have $$\left|\frac{S_{m^2}}{m^2}-\frac12\right|<\epsilon.\tag2$$ Now pick $n\ge M^2$. For this $n$, find an $m\ge M$ such that $m^2\le n<(m+1)^2$. Confirm that this implies that $|n-m^2|\le 2m$. By the triangle inequality, we can bound the first term on the RHS of (1): $$\left|\frac{S_n}n-\frac{S_{m^2}}{m^2}\right|\le \left|\frac{S_n}n-\frac{S_n}{m^2}\right|+ \left|\frac{S_n}{m^2}-\frac{S_{m^2}}{m^2}\right|.\tag3$$ Since $|S_n|\le n$, bound the first term on the RHS of (3) by $n\left|\frac 1n-\frac1{m^2}\right|\le\frac2m$. Bound the second term by $\frac1{m^2}|n-m^2|$, since the distance between $S_n$ and $S_{m^2}$ is at most the number of steps from time $m^2$ to time $n$. Adding these, it follows that the RHS of (3) is at most $\frac4m\le\frac4M$. Putting (2) and (3) together, we have $$\left|\frac{S_n}n-\frac12\right|\le\frac4M+\epsilon$$ whenever $n\ge M^2$. This implies that (1) is less than $2\epsilon$ for all large $n$, and we're done.

• What exactly do you mean by "suppressing the $\omega$ by focusing on just one sequence"? Sorry if it is something elementary, I'm a fairly new student of analysis :/. – Mog Sep 15 '18 at 0:42
• @pilotmath To eliminate clutter I'm dropping all the occurrences of $\omega$ in the proof, so instead of writing $S_n(\omega)$ I write $S_n$. So now $S_n$ now looks like a sequence of real numbers. – grand_chat Sep 15 '18 at 0:46
• $S_n$ as a sequence of real numbers as in all the possible sums of 0's and 1's right? Also, is there a reason why we pick a specific $n\geq M^2$, and an $m$ accordingly? – Mog Sep 15 '18 at 0:53
• @pilotmath $S_n$ is the partial sum of a specific sequence of 0's and 1's. Each $\omega$ gives rise to one sequence. We are picking $n\ge M^2$ to set up the standard epsilon-N proof for convergence of a sequence: For each $\epsilon$ you have to find an $N$ such that $|x_n-a|<\epsilon$ whenever $n>N$. Here $N$ is chosen to be $M^2$. – grand_chat Sep 15 '18 at 2:22
• thank you so much! It all makes sense now! – Mog Sep 15 '18 at 2:59

If $m^{2} \leq n \leq (m+1)^{2}$ then $\frac {S_m^{2}} {m^{2}} \frac {m^{2}} n \leq \frac {S_n} n \leq \frac {S_{m+1}^{2}} {(m+1)^{2}} \frac {(m+1)^{2}} n$. Just verify that $\frac {m^{2}} n$ and $\frac {(m+1)^{2}} n$ tend to $1$ as $n\to \infty$. [$\frac {m^{2}} {(m+1)^{2}} \leq\frac {m^{2}} n\leq 1$ and $\frac {m^{2}} {(m+1)^{2}} \to 1$ because $m \to \infty$ as $n \to \infty$. Similar argument for $\frac {(m+1)^{2}} n$.