betaFeedback

WorksMathematics

On shared responsibility, fish, and the strong law of large numbers

Abstract

We give a new, short, and intuitive proof of the strong law of large numbers for i.i.d. random variables.

While probability theory is largely abstract, many of its fundamental results are easy to observe in real life, even without writing abstract formulas. A prominent example is the law of large numbers (LLN). While one draw of a random variable, or a result of one experiment may be arbitrarily far from the expected value, it is natural to expect that the empirical average of many draws converges to the expected value. The strong variant of LLN specifies the mode of this convergence, using one of the strongest notions of convergence in probability theory — convergence almost surely.

Theorem 1. Let X1,X2,…X_1, X_2, \ldots be i.i.d. real valued random variables with E[∣X1∣]<∞\mathbb{E}[|X_1|] < \infty. Let μ:=E[X1]\mu:= \mathbb{E}[X_1], and for every n≥1n \ge1, let Yn=(X1+⋯+Xn)/nY_n = (X_1 + \cdots+ X_n)/n. Then, Yn→μY_n \to\mu almost surely as n→∞n \to\infty.

The statement’s intuition can be easily grasped without an extensive mathematical training, and at the same time this law is one of the fundamental results in probability theory. This naturally led to several approaches to prove it: some of the classical treatments include Kolmogorov’s truncation argument [3 Chapter 7], backwards martingales [2 Chapter 4], and the duality of the random walk [1]. Here, we give an intuitive proof connecting foundational concepts that are usually already taught in a basic probability course. In fact, we claim that putting rigour aside for a moment, the proof idea is natural for this result.

To say that YnY_n converges to μ\mu almost surely is equivalent to saying that the event that YnY_n does not converge to μ\mu has zero measure. Let us look closely at this region AA, where Yn↛μY_n \not\to\mu (see Figure 1a). On one hand, an individual experiment X1X_1 has nothing to do with the limit value of YnY_n behaving out of place, which mathematically corresponds to X1X_1 being independent of AA. Hence, on AA, it still behaves

(a) The orange region AA is the event {Yn↛μ}\{Y_n \not\to\mu\}.

(b) The orange slices indexed by kk are the events A∩{Yk>μ+ε}A \cap\{Y_k > \mu+ \varepsilon\}. If Yn↛μY_n \not\to\mu, there are infinitely many indices kk such that Yk>μ+εY_k > \mu+ \varepsilon for a fixed ε>0\varepsilon> 0.

Figure 1.

typically and its expected value remains at μ\mu — in other words, X1X_1 is innocent. However, at the finite scale2 things change. If YnY_n does not converge to μ\mu, it means that there are infinitely many indices kk such that the finite average YkY_k is above or below μ\mu. Equivalently, in AA, there are infinitely many non-empty slices with, say, Yk>μ+εY_k > \mu+ \varepsilon for a fixed ε>0\varepsilon> 0, see Figure 1b (these slices may in fact overlap; we will address this slight inconvenience in the formal proof). On each such a slice, since all the experiments are identical and independent, we anticipate the typical value of each one of them — including X1X_1 — to be higher than μ\mu. In other words, they are exchangeable with each other and so when they all look the same, they all share the blame. The only way to consolidate this contradiction is if this region AA has zero measure, or equivalently, YnY_n were to converge almost surely to μ\mu. Below, we give a proof formalising this intuition.

Proof of Theorem 1. Without loss of generality, let μ=0\mu= 0. For any ε>0\varepsilon> 0, define events

Aε:={lim sup⁡n→∞Yn>ε},Bε:={lim inf⁡n→∞Yn<−ε}.A_{\varepsilon} := \left\{\limsup_{n \to\infty} Y_n > \varepsilon\right\}, \quad B_{\varepsilon} := \left\{\liminf_{n \to\infty} Y_n < -\varepsilon\right\}.

Assume there is an ω\omega such that Yn(ω)↛μY_n(\omega) \not\to\mu. Then there exists ε>0\varepsilon> 0 such that for infinitely many indices nn, either Yn(ω)>εY_n(\omega) > \varepsilon or Yn(ω)<−εY_n(\omega) < -\varepsilon. Therefore, ω∈Aε∪Bε\omega\in A_{\varepsilon} \cup B_{\varepsilon}, and the statement follows if we show P(Aε)=P(Bε)=0\mathbb{P}(A_{\varepsilon}) = \mathbb{P}(B_{\varepsilon}) = 0. Since the two cases are analogous, we show it for AεA_{\varepsilon}. Fix such ε\varepsilon, and abbreviate A:=AεA := A_{\varepsilon}.

X1X_1 is innocent. Define A′={lim sup⁡n→∞(X2+⋯+Xn)/n>ε}A' = \{\limsup_{n \to\infty}(X_2 + \cdots+ X_n)/n > \varepsilon\}. Since X1/n→0X_1/n \to0 as n→∞n \to\infty, we have that 1A=1A′\mathbf{1}_A = \mathbf{1}_{A'} almost surely. Thus,

E[X11A]=E[X11A′]=0⋅P(A′)=0,(1)\mathbb{E}[X_1\mathbf{1}_A] = \mathbb{E}[X_1\mathbf{1}_{A'}] = 0 \cdot\mathbb{P}(A') = 0, \tag*{(1)}

where the penultimate equality follows since X1X_1 is independent of A′A'.

When they all look the same, X1X_1 shares the blame. In what remains, we show that E[X11A]≥ε⋅P(A)\mathbb{E}[X_1\mathbf{1}_A] \ge\varepsilon\cdot\mathbb{P}(A). Together with (1), this will imply that P(A)=0\mathbb{P}(A) = 0. Note that A⊆⋃n≥1{Yn>ε}A \subseteq\bigcup_{n \ge1}\{Y_n > \varepsilon\}, and thus A∩⋃k=1N{Yk>ε}A \cap\bigcup_{k=1}^{N}\{Y_k > \varepsilon\} increases to AA with NN. Since ∣X11A∩⋃k=1N{Yk>ε}∣≤∣X1∣\left|X_1\mathbf{1}_{A \cap\bigcup_{k=1}^{N}\{Y_k > \varepsilon\}}\right| \le|X_1| for every NN, and E[∣X1∣]<∞\mathbb{E}[|X_1|] < \infty, by the dominated convergence theorem,

E[X11A]=E[lim⁡N→∞X11A∩⋃k=1N{Yk>ε}]=lim⁡N→∞E[X11A∩⋃k=1N{Yk>ε}].(2)\mathbb{E}[X_1\mathbf{1}_A] = \mathbb{E}\left[\lim_{N \to\infty} X_1\mathbf{1}_{A \cap\bigcup_{k=1}^{N}\{Y_k > \varepsilon\}}\right] = \lim_{N \to\infty}\mathbb{E}\left[X_1\mathbf{1}_{A \cap\bigcup_{k=1}^{N}\{Y_k > \varepsilon\}}\right]. \tag*{(2)}

For every 1≤k≤N1 \le k \le N, define Dk,N={Yk>ε}∩{Yk+1,…,YN≤ε}D_{k,N} = \{Y_k > \varepsilon\} \cap\{Y_{k+1}, \ldots, Y_N \le\varepsilon\}. Considering these disjoint events allows us to decompose ⋃k=1N{Yk>ε}\bigcup_{k=1}^{N}\{Y_k > \varepsilon\} into ⨆k=1NDk,N\bigsqcup_{k=1}^{N} D_{k,N}. This, in turn, gives

E[X11A∩⋃k=1N{Yk>ε}]=∑k=1NE[X11A∩Dk,N].(3)\mathbb{E}\left[X_1\mathbf{1}_{A \cap\bigcup_{k=1}^{N}\{Y_k > \varepsilon\}}\right] = \sum_{k=1}^{N}\mathbb{E}\left[X_1\mathbf{1}_{A \cap D_{k,N}}\right]. \tag*{(3)}

We will now bound separately each summand on the right hand side. (The motivation to decompose into the disjoint events is that we will bound each summand separately, however even if the expectation is bounded on two events, it is not necessarily that the same bound holds on the union of these events unless they are disjoint3.

Since X1,X2,…X_1, X_2, \ldots are i.i.d. and since 1A∩Dk,N\mathbf{1}_{A\cap D_{k,N}} is symmetric with respect to X1,…,XkX_1,\ldots,X_k, we have that for every 1≤i≤k1\le i\le k,

E[X11A∩Dk,N]=∫x11A∩Dk,N dP(x1,…,xi,…)=∫x11A∩Dk,N dP(x1)⋯dP(xi)dP(xi+1,…)=∫xi1A∩Dk,N dP(xi)⋯dP(x1)dP(xi+1,…)=E[Xi1A∩Dk,N].\begin{aligned} \mathbb{E}\left[X_1\mathbf{1}_{A\cap D_{k,N}}\right] = \int x_1\mathbf{1}_{A\cap D_{k,N}}\,\mathrm{d}\mathbb{P}(x_1,\ldots,x_i,\ldots) = \int x_1\mathbf{1}_{A\cap D_{k,N}}\,\mathrm{d}\mathbb{P}(x_1)\cdots\mathrm{d}\mathbb{P}(x_i)\mathrm{d}\mathbb{P}(x_{i+1},\ldots) \\ &= \int x_i\mathbf{1}_{A\cap D_{k,N}}\,\mathrm{d}\mathbb{P}(x_i)\cdots\mathrm{d}\mathbb{P}(x_1)\mathrm{d}\mathbb{P}(x_{i+1},\ldots) = \mathbb{E}\left[X_i\mathbf{1}_{A\cap D_{k,N}}\right]. \end{aligned}

Summing over indices 1,…,k1,\ldots,k and dividing by kk gives us

E[X11A∩Dk,N]=E[Yk1A∩Dk,N]≥ε⋅P(A∩Dk,N).\mathbb{E}\left[X_1\mathbf{1}_{A\cap D_{k,N}}\right] = \mathbb{E}\left[Y_k\mathbf{1}_{A\cap D_{k,N}}\right] \ge\varepsilon\cdot\mathbb{P}(A\cap D_{k,N}).

Substituting the above in (3), we obtain E[X11A∩⋃k=1N{Yk>ε}]≥ε⋅P(A∩⋃k=1N{Yk>ε})\mathbb{E}\left[X_1\mathbf{1}_{A\cap\bigcup_{k=1}^{N}\{Y_k>\varepsilon\}}\right]\ge\varepsilon\cdot\mathbb{P}\left(A\cap\bigcup_{k=1}^{N}\{Y_k>\varepsilon\}\right). Therefore, taking N→∞N\to\infty, by (2) we obtain E[X11A]≥ε⋅P(A)\mathbb{E}[X_1\mathbf{1}_A]\ge\varepsilon\cdot\mathbb{P}(A), as required.

Considering that X1X_1 is innocent as E[X11A]=0\mathbb{E}[X_1\mathbf{1}_A]=0, this can only hold if P(A)=0\mathbb{P}(A)=0, as in Figure 2.

Figure 2. No fish (of non-zero measure) in the pond.

Acknowledgements

The authors would like to thank Afonso S. Bandeira, Ron Peled, Benny Sudakov, Vincent Tassion, and Maksim Zhukovskii for valuable comments and suggestions.

Use of AI

AI tools were used to assist with transforming hand-drawn sketches into the tikz code for the figures; no real fish were hurt during the process of human generation of the rest.

References

  1. [1][Cur22] Nicolas Curien. “Yet another proof of the strong law of large numbers”. In: Amer. Math. Monthly 129.10 (2022), pp. 972–974. DOI: 10.1080/00029890.2022.2115820.DOI
  2. [2][Dur19] Rick Durrett. Probability—theory and examples. Fifth. Vol. 49. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge: Cambridge University Press, 2019. DOI: 10.1017/9781108591034.
  3. [3][Fel71] William Feller. An introduction to probability theory and its applications. Vol. II. Second. New York–London–Sydney: John Wiley & Sons, Inc., 1971.

Paper details

vlnc:W_s84sue55
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…
Contents