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?

  • $\begingroup$ It would make more sense with $o(\epsilon)$. $O(\epsilon)$ is surely not what he meant. $\endgroup$ – Matt Samuel Oct 4 '17 at 2:40
  • $\begingroup$ Either that or he means it is bounded by $\epsilon$. $\endgroup$ – Matt Samuel Oct 4 '17 at 2:41
  • $\begingroup$ 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)$). $\endgroup$ – Dap Oct 4 '17 at 5:49
  • $\begingroup$ @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. $\endgroup$ – Question Asker Oct 4 '17 at 9:34
  • $\begingroup$ 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$}\}$" $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Question Asker Oct 4 '17 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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