# Big O Notation and Weak Law of Large Numbers

The following is from Terrance Tao's notes on the laws of large numbers here: https://terrytao.wordpress.com/2008/06/18/the-strong-law-of-large-numbers/. We are in the process of proving a form of the weak law of large numbers, the conclusion of which is that $\lim_{n\rightarrow \infty}\mathbb{P}(|\overline{X_n} - \mathbb{E}(X)|\ge \varepsilon) = 0$ for every $\varepsilon > 0$, where $\overline{X_n} = \frac{1}{n}(X_1 + ... + X_n)$. Here is the first line of the proof:

"Let $\varepsilon > 0$. It suffices to show that whenever $n$ is sufficiently large depending on $\varepsilon$, that $\overline{X_n} = \mathbb{E}(X) + O(\varepsilon)$ with probability $1 - O(\varepsilon)$"

I do not understand how to parse this line. One side of the equality is a random variable for each $n\in\mathbb{N}$, and the other side is a real number and an element of the class of functions $O(\varepsilon)= \{g : |g(x)|\le \varepsilon M\text{ for some M and all sufficiently large$x$}\}$, which appears to just be the bounded functions (on $\Omega$?). This is based on the definition here: https://en.wikipedia.org/wiki/Big_O_notation. In addition to not understanding precisely what $O(\varepsilon)$ means here, I am also unsure whether we are choosing a different element of $O(\varepsilon)$ for each $n$.

Could anyone give a way to rigorously interpret this line, preferably so that is clear why it suffices to prove this statement?

• It would make more sense with $o(\epsilon)$. $O(\epsilon)$ is surely not what he meant. – Matt Samuel Oct 4 '17 at 2:40
• Either that or he means it is bounded by $\epsilon$. – Matt Samuel Oct 4 '17 at 2:41
• I think the "class of functions" interpretation is just wrong. $a_n=O(b_n)$ means $|a_n|\leq C|b_n|$ for sufficiently large $n$, for an unspecified $C$ that is fixed for each different $O$ symbol written down (it may depend on other bound variables, though this should ideally be written explicitly like $O_{x,t}(a_n)$). – Dap Oct 4 '17 at 5:49
• @Dap I liked your answer, but I do think that we have to think of $O$ as being a class of functions. If $\overline{X_n}(\omega) = \mathbb{E}(X) + O(\varepsilon)$, then the LHS needs to depend on $\omega$ too. Also, since the LHS is a different function of $\omega$ for each $n$, the RHS will need to be different for every $n$. But if $C_1,C_2$ are fixed at the start, this is all fine. – Question Asker Oct 4 '17 at 9:34
• Yeah, I guess it is still some class of functions, but it is "$\{g:|g(x)|\leq \varepsilon M\text{ for all sufficiently large$x$}\}$ for some absolute constant $M$" rather than "$\{g : |g(x)|\le \varepsilon M\text{ for some M and all sufficiently large$x$}\}$" – Dap Oct 4 '17 at 9:43

An explicit way to interpret this would be

There exists $C_1,C_2$ such that for all $\varepsilon>0$ there exists $N$ such that for all $n\geq N,$ $$\mathbb P[|\overline{X_n}-\mathbb E(X)|\leq C_1\varepsilon] \geq 1 - C_2\varepsilon.$$

It might help to just rid of the implicit constants. Let $\pm E$ mean any number in the range $[-E,E]$. Here is the same proof, but with $O(\dots)$ replaced by $\pm \dots$, and some extra factors:

Let $\varepsilon > 0$. It suffices to show that whenever $n$ is sufficiently large depending on $\varepsilon$, that $\overline{X}_n = {\Bbb E} X \pm 3\varepsilon$ with probability $1\pm 3\varepsilon$.

From (7), (8), we can find a threshold $N$ (depending on $\varepsilon$) such that ${\Bbb E} |X_{\geq N}| = \pm\varepsilon^2$ and ${\Bbb E} X_{<N} = {\Bbb E} X \pm \varepsilon$. Now we use (5) to split

$$\displaystyle \overline{X}_n = (\overline{X_{\geq N}})_n +(\overline{X_{< N}})_n.$$

From the first moment tail bound (Lemma 1), we know that $(\overline{X_{\geq N}})_n = \pm\varepsilon$ with probability $1 \pm \varepsilon$. From the second moment tail bound (Lemma 2) and (6), we know that $(\overline{X_{< N}})_n = {\Bbb E} X_{<N} \pm \varepsilon = {\Bbb E} X \pm 2\varepsilon$ with probability $1\pm 2\varepsilon$ if $n$ is sufficiently large depending on $N$ and $\varepsilon$. The claim follows.

• I think that this works. I am supposed to fix the constants $C_1,C_2$ at the beginning of the proof so that they do not depend on $n$ or $\varepsilon$. Thanks. – Question Asker Oct 4 '17 at 9:27