---
title: "Probability: Foundations and the Law of Large Numbers"
book: "University Mathematics — Year 3"
subject: math
language: en
chapter: 22
exercises: 12
source: https://one-course.com/books/math/5/en/chapter/22-probability-foundations-and-the-law-of-large-numbers
---

# Chapter 22 — Probability: Foundations and the Law of Large Numbers

Year 2 built probability on countable spaces; [measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) theory now removes every restriction. A [probability space](#def-b3-probability-space) is a [measure space](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) of total mass $1$, [random variables](#def-b3-probability-space) are [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) maps, [expectation](#def-b3-probability-space) is the Lebesgue integral — and at once the whole analytic arsenal (Chapters [9](https://one-course.com/books/math/5/en/chapter/9-measure-theory#ch-b3-measure), [10](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ch-b3-lebesgue) and [11](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#ch-b3-product)) applies to chance. This chapter installs the dictionary, constructs infinite sequences of [independent](#def-b3-probability-independence) [random variables](#def-b3-probability-space) (on $\intcc01$, from binary digits: randomness is hiding inside [Lebesgue measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-lebesgueouter)), proves the Borel–Cantelli lemmas and Kolmogorov’s [zero–one law](#thm-b3-probability-zeroone), sorts out the modes of convergence, and proves the [law](#def-b3-probability-space) of large numbers — the theorem that makes frequencies converge to probabilities and statistics possible. The weekend problem gives Etemadi’s proof of the strong [law](#def-b3-probability-space) in its definitive $L^1$ form.

## 22.1 The dictionary

**Definition 22.1.**

A *probability space* is a [measure space](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) $(\Omega, \mathcal A, \P)$ with $\P(\Omega) =
1$; elements of $\mathcal A$ are *events*, and a property holds *almost surely* (a.s.) if its event has probability $1$. A *random variable* is a [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) map $X \colon \Omega \to \R$ (or $\R^d$: a random vector); its *law* is the pushforward probability [measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) $\P_X =
X_*\P$ on $\R$ ([Exercise 11.9](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#exo-b3-product-9)), determined by the *distribution function* $F_X(t) = \P(X \leq t)$ ([Exercise 9.3](https://one-course.com/books/math/5/en/chapter/9-measure-theory#exo-b3-measure-3)). $X$ has *[density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma)* $f$ if $\P_X = f\,\dd\lambda$; it is *discrete* if $\P_X$ is a countable combination of Dirac masses. The *expectation* is

$$
\E[X] = \int_\Omega X\,\dd\P
\qquad (X \geq 0 \text{ or } X \in L^1(\P)),
$$

and the *transfer theorem* ([Exercise 11.9](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#exo-b3-product-9)) computes it in the law: $\E[g(X)] = \int_\R g\,\dd\P_X$ — $= \sum g(x_k)p_k$ in the discrete case, $= \int
g(x)f(x)\dd x$ in the [density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma) case: Year 2’s formulas, now theorems of one theory. The *variance* is $\V(X) =
\E[(X - \E X)^2] = \E[X^2] - (\E X)^2$ for $X \in L^2$.

**Example 22.2.**

The standard [laws](#def-b3-probability-space) and their transforms of note: Bernoulli $\mathcal B(p)$, binomial $\mathcal B(n, p)$, geometric, Poisson $\mathcal P(\lambda)$ (discrete: Year 2’s tables remain valid); uniform on $\intcc01$ ([Lebesgue measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-lebesgueouter) itself); exponential $\mathcal E(\lambda)$ ([density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma) $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$); the *Gaussian* $\mathcal N(m, \sigma^2)$ with [density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma) $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x -
m)^2}{2\sigma^2}\bigr)$ — a probability [density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma) by [Problem 10.1](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#pb-b3-lebesgue-1), with mean $m$ and variance $\sigma^2$ (Gaussian moments, [Exercise 11.10](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#exo-b3-product-10)).

**Proposition 22.3 (Markov and Chebyshev).**

For $X \geq 0$ and $a > 0$: $\P(X \geq a) \leq \frac{\E
X}{a}$; for $X \in L^2$: $\P\bigl(\abs{X - \E X} \geq
a\bigr) \leq \frac{\V(X)}{a^2}$.

**Proof.** [Exercise 10.5](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#exo-b3-lebesgue-5)(a); Chebyshev is Markov applied to $(X - \E X)^2$. ∎

## 22.2 Independence

**Definition 22.4.**

Sub-$\sigma$-algebras $\mathcal A_1, \dots, \mathcal A_n
\subseteq \mathcal A$ are *independent* if $\P(A_1\cap\dots\cap A_n) = \prod\P(A_i)$ for all $A_i \in
\mathcal A_i$; events are independent if the $\sigma$-algebras $\{\varnothing, A_i, A_i^c, \Omega\}$ are; [random variables](#def-b3-probability-space) $X_1, \dots, X_n$ if the $\sigma$-algebras $\sigma(X_i) =
X_i^{-1}(\mathcal B(\R))$ are. An infinite family is independent if every finite subfamily is.

**Theorem 22.5.**

$X_1, \dots, X_n$ are [independent](#def-b3-probability-independence) iff the [law](#def-b3-probability-space) of the vector $(X_1, \dots, X_n)$ is the [product measure](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#thm-b3-product-existence) $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$. In that case, for $g_i \geq 0$ (or such that the products are [integrable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-l1)):

$$
\E\Bigl[\prod_ig_i(X_i)\Bigr] = \prod_i\E[g_i(X_i)],
$$

in particular $\E[XY] = \E X\,\E Y$ and $\V(X_1 + \dots +
X_n) = \sum\V(X_i)$ for [independent](#def-b3-probability-independence) $L^2$ variables.

**Proof.** If the $X_i$ are [independent](#def-b3-probability-independence), the two probability [measures](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) $\P_{(X_1,\dots,X_n)}$ and $\bigotimes\P_{X_i}$ agree on all products $B_1\times\dots\times B_n$ of Borel sets — a $\pi$-system generating $\mathcal B(\R^n)$ ([Proposition 11.2](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#prop-b3-product-sections)(b)) — hence everywhere ([Theorem 9.7](https://one-course.com/books/math/5/en/chapter/9-measure-theory#thm-b3-measure-uniqueness)). Conversely, a product [law](#def-b3-probability-space) factorizes all events $\bigcap_iX_i^{-1}(B_i)$: [independence](#def-b3-probability-independence). The [expectation](#def-b3-probability-space) formula is then Tonelli/Fubini ([Theorem 11.5](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#thm-b3-product-tonelli)) through the transfer theorem; $\E[XY] = \E X\E Y$ is the case $g_i =
\mathrm{id}$, and expanding the square gives the additivity of variances (cross terms $\E[(X_i - \E X_i)(X_j - \E X_j)]
= 0$). ∎

**Theorem 22.6 (Existence of independent sequences).**

On $\bigl(\intcc01, \mathcal L, \lambda\bigr)$ there exists a sequence $(U_n)_{n\geq1}$ of [independent](#def-b3-probability-independence) [random variables](#def-b3-probability-space), each uniform on $\intcc01$. Consequently, for any prescribed [laws](#def-b3-probability-space) $(\mu_n)$ on $\R$ there exist [independent](#def-b3-probability-independence) $(X_n)$ with $\P_{X_n} = \mu_n$.

**Proof.** *Digits.* For $\omega \in \intcc01$, let $(b_k(\omega))$ be its binary digits ($\omega = \sum b_k2^{-k}$; choose the expansion not ending in all $1$’s — ambiguity concerns only a countable, hence null, set). Each $b_k$ is a [random variable](#def-b3-probability-space) ($\{b_k = 1\}$ is a finite union of dyadic intervals) and the vector $(b_1, \dots, b_m)$ takes each value in $\{0,1\}^m$ on a dyadic interval of length $2^{-m}$: the $b_k$ are [independent](#def-b3-probability-independence) Bernoulli$(\frac12)$.

*Regrouping.* Split $\N^*$ into infinitely many disjoint infinite sets $(I_n)$ (e.g. by prime powers, or diagonals); let $(k^n_j)_j$ enumerate $I_n$ and set

$$
U_n = \sum_{j\geq1} b_{k^n_j}\,2^{-j} .
$$

Each $U_n$ is uniform: its binary digits are [independent](#def-b3-probability-independence) fair bits, so $\P(U_n \in [l2^{-m}, (l+1)2^{-m})) = 2^{-m}$ for every dyadic interval, and dyadic intervals determine the [law](#def-b3-probability-space) ([Theorem 9.7](https://one-course.com/books/math/5/en/chapter/9-measure-theory#thm-b3-measure-uniqueness)). The $U_n$ are [independent](#def-b3-probability-independence): they are functions of disjoint blocks of the [independent](#def-b3-probability-independence) family $(b_k)$ — formally, events $\{U_n \in D_n\}$ for dyadic $D_n$ depend on finitely many digits from disjoint sets, and factorize; the $\pi$-system argument upgrades to all Borel sets.

*Arbitrary [laws](#def-b3-probability-space).* Let $G_n(u) = \inf\{t : F_{\mu_n}(t)
\geq u\}$ (the *quantile function* of the distribution function $F_{\mu_n}$); the key equivalence $G_n(u) \leq t
\iff u \leq F_{\mu_n}(t)$ ([right-continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) of $F$, monotonicity) shows $X_n = G_n(U_n)$ is [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) with $\P(X_n \leq t) = \P(U_n \leq F_{\mu_n}(t)) =
F_{\mu_n}(t)$: [law](#def-b3-probability-space) $\mu_n$; [independence](#def-b3-probability-independence) is inherited (functions of [independent](#def-b3-probability-independence) variables, [Exercise 22.3](#exo-b3-probability-3)). ∎

**Example 22.7 (The birthday problem, honestly).**

Among $n$ people with [independent](#def-b3-probability-independence), uniform birthdays over $N = 365$ days, the probability that all birthdays differ is

$$
p_n = \prod_{k=1}^{n-1}\Bigl(1 - \frac kN\Bigr),
$$

by iterated conditioning (or directly: the favorable $N(N-1)\cdots(N - n + 1)$ over the total $N^n$, a counting argument the product formula of [independence](#def-b3-probability-independence) makes rigorous). Taking logarithms and using $-\ln(1 - x) = x +
O(x^2)$:

$$
\ln p_n = -\frac{n(n-1)}{2N} +
O\Bigl(\frac{n^3}{N^2}\Bigr),
\qquad\text{so}\qquad
p_n \approx \eu^{-n^2/2N} .
$$

The tipping point $p_n = \frac12$ sits at $n \approx
\sqrt{2N\ln2} \approx 1.18\sqrt N$: for $N = 365$, $n = 23$ ($p_{23} = 0.4927$). Two morals. First, collisions among $n$ items in $N$ boxes appear at the scale $n \sim \sqrt N$, not $n \sim N$ — the *birthday scaling* that governs hash collisions and the $\sqrt N$ cost of birthday attacks in cryptography. Second, the computation is a template: the $\binom n2$ pair-collision events are not [independent](#def-b3-probability-independence), yet the answer behaves as if they were ($\eu^{-\binom n2/N}$ is exactly the independent-pairs heuristic) — a first instance of the Poisson approximation made rigorous in [Chapter 23](https://one-course.com/books/math/5/en/chapter/23-characteristic-functions-and-the-central-limit-theorem#ch-b3-clt)’s weekend problem (Le Cam’s inequality).

## 22.3 Borel–Cantelli and the zero–one law

**Theorem 22.8 (Borel–Cantelli).**

Let $(A_n)$ be events and $\limsup A_n = \bigcap_N
\bigcup_{n\geq N}A_n$ (“$A_n$ occurs infinitely often”).

1. If $\sum\P(A_n) < \infty$ , then $\P(\limsup A_n) =  0$ .
2. If $\sum\P(A_n) = \infty$ *and the $A_n$ are [independent](#def-b3-probability-independence)* , then $\P(\limsup A_n) = 1$ .

**Proof.** (1) is [Exercise 9.4](https://one-course.com/books/math/5/en/chapter/9-measure-theory#exo-b3-measure-4). (2): for $N \leq M$, [independence](#def-b3-probability-independence) of complements ([Exercise 22.3](#exo-b3-probability-3)) gives

$$
\P\Bigl(\bigcap_{n=N}^{M}A_n^c\Bigr) = \prod_{n=N}^M\bigl(1
- \P(A_n)\bigr) \leq
\exp\Bigl(-\sum_{n=N}^M\P(A_n)\Bigr) \xrightarrow[M \to
\infty]{} 0
$$

($1 - x \leq \eu^{-x}$; the series diverges). So $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ for every $N$, and the decreasing intersection over $N$ still has probability $1$ ([continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) from above, [Proposition 9.6](https://one-course.com/books/math/5/en/chapter/9-measure-theory#prop-b3-measure-basics)). ∎

**Theorem 22.9 (Kolmogorov’s zero–one law).**

Let $(X_n)$ be [independent](#def-b3-probability-independence) and $\mathcal T =
\bigcap_N\sigma(X_N, X_{N+1}, \dots)$ the *tail $\sigma$-algebra* (events insensitive to any finite number of the $X_n$: convergence of $\sum X_n$, of $\frac{S_n}n$, values of $\limsup$’s, …). Then every $T \in \mathcal T$ has $\P(T) \in \{0,
1\}$.

**Proof.** Fix $N$. The $\sigma$-algebras $\sigma(X_1, \dots, X_N)$ and $\sigma(X_{N+1}, \dots)$ are [independent](#def-b3-probability-independence): events depending on disjoint blocks factorize on the generating $\pi$-systems (cylinders $\bigcap_{i\leq N}\{X_i \in B_i\}$, resp. finite conditions on later variables), and Dynkin ([Theorem 9.4](https://one-course.com/books/math/5/en/chapter/9-measure-theory#thm-b3-measure-dynkin), applied twice, one side at a time) extends the factorization. A tail event $T$ lies in $\sigma(X_{N+1}, \dots)$ for every $N$: $T$ is [independent](#def-b3-probability-independence) of every $\sigma(X_1, \dots, X_N)$, hence of the $\sigma$-algebra they generate, $\sigma(X_1, X_2, \dots)$ (Dynkin once more: the union of the $\sigma(X_1,\dots,X_N)$ is a $\pi$-system generating it). But $T \in \sigma(X_1, X_2, \dots)$ too: $T$ is [independent](#def-b3-probability-independence) *of itself*, $\P(T) = \P(T\cap T) =
\P(T)^2$: $\P(T) \in \{0, 1\}$. ∎

## 22.4 Modes of convergence

**Definition 22.10.**

$X_n \to X$ *almost surely* if $\P(X_n \to X) = 1$; *in probability* if $\P(\abs{X_n - X} \geq \varepsilon)
\to 0$ for every $\varepsilon > 0$; *in $L^p$* if $\E\abs{X_n - X}^p \to 0$.

**Proposition 22.11.**

(a) a.s. convergence implies convergence in probability; (b) $L^p$ convergence implies convergence in probability; (c) convergence in probability implies a.s. convergence *along a subsequence*; (d) no other implication holds in general.

**Proof.** (a) $\P(\abs{X_n - X} \geq \varepsilon) \leq
\P\bigl(\sup_{m\geq n}\abs{X_m - X} \geq \varepsilon\bigr)
\downarrow \P\bigl(\limsup\{\abs{X_m - X} \geq
\varepsilon\}\bigr) = 0$ under a.s. convergence ([continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) from above; the limsup event excludes convergence). (b) Markov: $\P(\abs{X_n - X} \geq \varepsilon) \leq
\varepsilon^{-p}\,\E\abs{X_n - X}^p$. (c) Pick $n_k$ with $\P(\abs{X_{n_k} - X} \geq 2^{-k}) \leq 2^{-k}$; Borel–Cantelli (1) makes $\abs{X_{n_k} - X} < 2^{-k}$ eventually, a.s. (d) The typewriter ([Exercise 12.3](https://one-course.com/books/math/5/en/chapter/12-the-lp-spaces#exo-b3-lp-3)) on $(\intcc01, \lambda)$ converges in $L^1$ and in probability but nowhere pointwise; $n\mathbf 1_{\intoo0{1/n}} \to 0$ a.s. but not in $L^1$; details and the remaining counterexamples in [Exercise 22.6](#exo-b3-probability-6). ∎

## 22.5 The law of large numbers

Throughout, $(X_n)$ are [independent](#def-b3-probability-independence) with the same [law](#def-b3-probability-space) (*i.i.d.*), $S_n = X_1 + \dots + X_n$.

**Theorem 22.12 (Weak law of large numbers).**

If $X_1 \in L^2$, with $m = \E X_1$:

$$
\P\Bigl(\Bigl|\frac{S_n}{n} - m\Bigr| \geq
\varepsilon\Bigr) \leq
\frac{\V(X_1)}{n\,\varepsilon^2}
\xrightarrow[n\to\infty]{} 0 :
$$

$\frac{S_n}n \to m$ in probability (and in $L^2$).

**Proof.** $\E\frac{S_n}n = m$ and $\V\bigl(\frac{S_n}n\bigr) =
\frac{n\V(X_1)}{n^2}$ ([Theorem 22.5](#thm-b3-probability-independence)); Chebyshev. ∎

**Theorem 22.13 (Strong law of large numbers).**

If $X_1 \in L^1$, then

$$
\frac{S_n}{n} \xrightarrow[n\to\infty]{\text{a.s.}} \E[X_1].
$$

We prove it here under the stronger hypothesis $X_1 \in
L^4$; the general case ($L^1$: Etemadi’s proof) is the weekend problem.

**Proof under $\E X_1^4 < \infty$.** Centering ($X_i \mapsto X_i - m$), assume $m = 0$. Expand:

$$
\E[S_n^4] = \sum_{i,j,k,l}\E[X_iX_jX_kX_l]
= n\,\E[X_1^4] + 3n(n-1)\,\bigl(\E[X_1^2]\bigr)^2 \leq
C\,n^2 ,
$$

since [independence](#def-b3-probability-independence) and centering kill every term containing an isolated factor ($\E[X_iX_jX_kX_l] =
\E[X_i]\E[\cdots] = 0$ unless the indices pair up: the only survivors are the $n$ terms $i=j=k=l$ and the $3n(n-1)$ terms with two distinct pairs). Markov:

$$
\P\Bigl(\Bigl|\frac{S_n}n\Bigr| \geq \varepsilon\Bigr)
= \P\bigl(S_n^4 \geq n^4\varepsilon^4\bigr)
\leq \frac{Cn^2}{n^4\varepsilon^4} =
\frac{C}{\varepsilon^4n^2},
$$

summable: Borel–Cantelli (1) gives, for each rational $\varepsilon$, that $\abs{S_n/n} < \varepsilon$ eventually, a.s.; intersecting over $\varepsilon \in \Q_+^*$ (countably many probability-$1$ events): $S_n/n \to 0$ a.s. ∎

**Example 22.14 (What the strong law buys).**

(a) *Frequencies*: for i.i.d. coin flips, the observed frequency of heads converges a.s. to $p$ — the empirical justification of probability itself. (b) *Monte Carlo*: for $g \in
L^1(\intcc01)$ and $(U_n)$ i.i.d. uniform ([Theorem 22.6](#thm-b3-probability-existence)), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ a.s.: integrals by sampling, in any dimension, at the [dimension-independent](#def-b3-probability-independence) rate $\sim n^{-1/2}$ made precise in [Chapter 23](https://one-course.com/books/math/5/en/chapter/23-characteristic-functions-and-the-central-limit-theorem#ch-b3-clt). (c) *Normal numbers*: almost every real number has, in its binary expansion, asymptotic frequency $\frac12$ of ones (apply the strong [law](#def-b3-probability-space) to the digit variables of [Theorem 22.6](#thm-b3-probability-existence)) — Borel’s theorem, a statement about *every*day numbers proved by [measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure): [Problem 22.1](#pb-b3-probability-1) [completes](https://one-course.com/books/math/5/en/chapter/7-complete-spaces-baire-ascoli-stoneweierstrass#def-b3-complete-complete) it in all bases.

**Method 22.15.**

The working order for asymptotic statements about random sequences: (1) *Is the event a tail event?* Then its probability is $0$ or $1$ ([Theorem 22.9](#thm-b3-probability-zeroone)) and one only has to decide which. (2) *To prove a.s. statements*: Borel–Cantelli — summable probabilities for the “bad” events, via Markov/Chebyshev-type bounds on whatever moments exist; [independence](#def-b3-probability-independence) only needed for the converse direction. (3) *Subsequence + sandwich*: prove convergence along a manageable subsequence, control the oscillation in between by monotonicity or maximal inequalities — the skeleton of Etemadi’s proof. (4) For distributional limits, wait for [Chapter 23](https://one-course.com/books/math/5/en/chapter/23-characteristic-functions-and-the-central-limit-theorem#ch-b3-clt).

## 22.6 Exercises

**Exercise 22.1 ★.**

(a) Let $X$ have [continuous](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) strictly increasing distribution function $F$. Show that $F(X)$ is uniform on $\intcc01$, and that $G(U) \sim F$ for $U$ uniform, $G = F^{-1}$: simulation by inversion. (b) Compute the distribution function and [density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma) of $X^2$ for $X$ uniform on $\intcc{-1}1$, and of $-\frac1\lambda\ln
U$ for $U$ uniform on $\intoo01$.

**Solution of Exercise 22.1.**

(a) For $u \in \intoo01$: $\P(F(X) \leq u) = \P(X \leq
F^{-1}(u)) = F(F^{-1}(u)) = u$ ([continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) and strict monotonicity make $F$ a bijection onto $\intoo01$ with $\{F(X) \leq u\} = \{X \leq F^{-1}(u)\}$): $F(X)$ is uniform. Conversely $\P(G(U) \leq t) = \P(U \leq F(t)) = F(t)$: to simulate a [law](#def-b3-probability-space), apply the inverse distribution function to a uniform sample.

(b) $Y = X^2$, $X$ uniform on $\intcc{-1}1$: for $t \in
\intcc01$, $F_Y(t) = \P(-\sqrt t \leq X \leq \sqrt t) = \sqrt
t$: [density](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#ex-b3-lebesgue-gamma) $\frac1{2\sqrt t}\mathbf 1_{\intoo01}$. And $\P\bigl(-\frac1\lambda\ln U \leq t\bigr) = \P(U \geq
\eu^{-\lambda t}) = 1 - \eu^{-\lambda t}$: the exponential $\mathcal E(\lambda)$ — inversion in action.

**Exercise 22.2 ★.**

(a) Compute mean and variance of the Poisson $\mathcal
P(\lambda)$ and geometric [laws](#def-b3-probability-space) via the transfer theorem. (b) Show that a positive [random variable](#def-b3-probability-space) $T$ with $\P(T > t)
> 0$ for all $t$ satisfies the *memoryless* property $\P(T > t + s \mid
T > t) = \P(T > s)$ for all $s, t \geq 0$ iff $T$ is exponential. *(The survival function satisfies Cauchy’s functional equation; monotonicity replaces [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity).)*

**Solution of Exercise 22.2.**

(a) Poisson: $\E X = \sum_{k\geq0}k\,\eu^{-\lambda}
\frac{\lambda^k}{k!} = \lambda$, $\E[X(X-1)] = \lambda^2$, so $\V = \lambda^2 + \lambda - \lambda^2 = \lambda$. Geometric ($\P(X = k) = p(1-p)^{k-1}$): $\E X = \frac1p$, $\V =
\frac{1-p}{p^2}$ (differentiate the geometric series twice).

(b) $G(t) = \P(T > t)$ is nonincreasing with $G(0^+)\dots$ $G \colon \intco0\infty \to \intoc01$; memorylessness reads $G(t + s) = G(t)G(s)$. Then $G(n t) = G(t)^n$ and $G(t/n) =
G(t)^{1/n}$: $G(q) = G(1)^q$ for rational $q \geq 0$; writing $G(1) = \eu^{-\lambda}$ ($\in \intoo01$: $G(1) = 1$ would force $G \equiv 1$, impossible for a finite [random variable](#def-b3-probability-space); $G(1) = 0$ is excluded by hypothesis) and squeezing an arbitrary $t$ between rationals (monotonicity): $G(t) =
\eu^{-\lambda t}$ — the exponential [law](#def-b3-probability-space). The converse is a computation.

**Exercise 22.3 ★★.**

(a) Show that if $X_1, \dots, X_n$ are [independent](#def-b3-probability-independence) and $f_i$ are Borel functions, the $f_i(X_i)$ are [independent](#def-b3-probability-independence). (b) Show that events $A_1, \dots, A_n$ are [independent](#def-b3-probability-independence) iff their complements are, iff the indicators $\mathbf 1_{A_i}$ are [independent](#def-b3-probability-independence) [random variables](#def-b3-probability-space). (c) (Pairwise is weaker) Two fair coins: $A =$ first is heads, $B =$ second is heads, $C =$ the two agree. Show $A, B, C$ are pairwise [independent](#def-b3-probability-independence) but not [independent](#def-b3-probability-independence).

**Solution of Exercise 22.3.**

(a) $\sigma(f_i(X_i)) = f_i(X_i)^{-1}(\mathcal B) \subseteq
X_i^{-1}(\mathcal B) = \sigma(X_i)$ ($f_i$ Borel), and sub-$\sigma$-algebras of [independent](#def-b3-probability-independence) $\sigma$-algebras are [independent](#def-b3-probability-independence) (the defining identity holds a fortiori).

(b) $\sigma(A_i) = \{\varnothing, A_i, A_i^c, \Omega\} =
\sigma(A_i^c) = \sigma(\mathbf 1_{A_i})$: all three statements assert [independence](#def-b3-probability-independence) of the same $\sigma$-algebras. (That factorization over the $A_i$ propagates to complements is the $\lambda$-system argument inside [Definition 22.4](#def-b3-probability-independence)’s equivalence — or direct inclusion-exclusion.)

(c) $\P(A) = \P(B) = \P(C) = \frac12$; $A\cap B = A\cap C =
B\cap C$ on pairs: each intersection is “both heads” or analogous, of probability $\frac14$: pairwise [independent](#def-b3-probability-independence). But $\P(A\cap B\cap C) = \P(\text{HH}) = \frac14 \neq
\frac18$: not [independent](#def-b3-probability-independence) — $C$ is determined by $A$ and $B$.

**Exercise 22.4 ★★.**

(a) (Infinite monkey) An i.i.d. sequence of uniform keystrokes on a finite alphabet a.s. contains every finite text infinitely often: prove it with Borel–Cantelli (2) on disjoint blocks. (b) (Runs) For i.i.d. fair bits, let $R_n$ be the length of the run of ones starting at position $n$. Show that a.s. $R_n \geq (1+\varepsilon)\log_2n$ finitely often, and $R_n
\geq \log_2 n$ infinitely often *(both halves of Borel–Cantelli; for the second, pass to disjoint blocks to gain [independence](#def-b3-probability-independence))*: the longest run in the first $n$ digits grows like $\log_2n$.

**Solution of Exercise 22.4.**

(a) Let the text $T$ have length $L$ and $q = a^{-L}$ ($a$ the alphabet size). The events $E_k = \{$positions $kL+1,
\dots, (k+1)L$ spell $T\}$ are [independent](#def-b3-probability-independence) (disjoint blocks of i.i.d. letters), each of probability $q > 0$: $\sum\P(E_k)
= \infty$, and Borel–Cantelli (2) gives infinitely many occurrences a.s.

(b) Upper: $\P\bigl(R_n \geq (1+\varepsilon)\log_2n\bigr)
\leq 2^{-(1+\varepsilon)\log_2n} = n^{-(1+\varepsilon)}$, summable: by Borel–Cantelli (1), a.s. only finitely many such $n$. Lower: pack disjoint blocks — the $j$-th of length $\ell_j = \lceil\log_2s_j\rceil$ starting at $s_j =
\sum_{i<j}\ell_i$; the events “block $j$ is all ones” are [independent](#def-b3-probability-independence) with probability $2^{-\ell_j} \asymp
\frac1{s_j} \asymp \frac1{j\log_2 j}$, whose sum diverges: Borel–Cantelli (2) gives infinitely many all-ones blocks, i.e. $R_{s_j} \geq \log_2 s_j$ infinitely often. Together: the maximal run length in the first $n$ digits is $(1 + o(1))\log_2n$ a.s.

**Exercise 22.5 ★★.**

Let $(X_n)$ be [independent](#def-b3-probability-independence). (a) Show that the radius of convergence of $\sum X_n z^n$ is an a.s. constant (possibly $0$ or $\infty$). (b) Show that $\P(\sum X_n \text{ converges}) \in \{0, 1\}$ and $\P(S_n/n \to m) \in \{0,1\}$. (c) Give an event about $(X_n)$ that is *not* a tail event, and check that the [zero–one law](#thm-b3-probability-zeroone) can fail for it.

**Solution of Exercise 22.5.**

(a) $R = \bigl(\limsup\abs{X_n}^{1/n}\bigr)^{-1}$ is unchanged if finitely many $X_n$ are modified: for every $N$, $R$ is $\sigma(X_N, X_{N+1}, \dots)$-measurable, i.e. [tail-measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable). Then each event $\{R \leq c\}$ has probability $0$ or $1$ ([Theorem 22.9](#thm-b3-probability-zeroone)), so the distribution function of $R$ takes only the values $0, 1$: it jumps at a single point $c_0 \in
\intcc0{+\infty}$, and $R = c_0$ a.s.

(b) Convergence of $\sum X_n$ and of $\frac{S_n}n$ are insensitive to changing finitely many terms (for the second: the modified terms contribute $O(1/n) \to 0$): tail events; [zero–one law](#thm-b3-probability-zeroone).

(c) $\{X_1 > 0\}$ depends on $X_1$: for i.i.d. signs ($\P(X_1 = \pm1) = \frac12$), its probability is $\frac12
\notin \{0,1\}$ — no contradiction, it is not a tail event.

**Exercise 22.6 ★★.**

On $(\intcc01, \lambda)$, exhibit — with proofs — [random variables](#def-b3-probability-space) such that: (a) $X_n \to 0$ in probability and in every $L^p$, but nowhere a.s.; (b) $X_n \to 0$ a.s. but in no $L^p$; (c) $X_n \to 0$ in $L^1$ but not in $L^2$; (d) and show: if $X_n \to X$ in probability and $\abs{X_n}
\leq Y \in L^1$, then $X_n \to X$ in $L^1$ *(subsequences + dominated convergence + the subsubsequence trick)*.

**Solution of Exercise 22.6.**

Work on $(\intcc01, \lambda)$. (a) The typewriter $\mathbf 1_{I_n}$ ([Exercise 12.3](https://one-course.com/books/math/5/en/chapter/12-the-lp-spaces#exo-b3-lp-3)): $\norm{X_n}_p^p = \lambda(I_n) \to 0$ (all $p < \infty$), hence also in probability; at every $\omega$ the values $0$ and $1$ both recur: no pointwise convergence anywhere. (b) $X_n = n\mathbf 1_{\intoo0{1/n}} \to 0$ off $0$, but $\norm{X_n}_p \geq n^{1 - 1/p} \geq 1$. (c) $X_n = \sqrt n\,\mathbf 1_{\intoo0{1/n}}$: $\E\abs{X_n} =
n^{-1/2} \to 0$, $\E X_n^2 = 1$. (d) From any subsequence extract (convergence in probability) a further subsequence converging a.s. ([Proposition 22.11](#prop-b3-probability-modes)(c)); dominated convergence gives $L^1$ convergence along it, with the *same* limit $X$. Thus every subsequence of the numerical sequence $\E\abs{X_n - X}$ has a subsubsequence tending to $0$: the whole sequence tends to $0$.

**Exercise 22.7 ★★.**

An opinion poll estimates an unknown proportion $p$ by the empirical frequency $\hat p_n$ of $n$ [independent](#def-b3-probability-independence) draws. (a) Chebyshev: show $\P(\abs{\hat p_n - p} \geq \varepsilon)
\leq \frac1{4n\varepsilon^2}$ (use $p(1-p) \leq \frac14$). (b) How many draws guarantee an error $\leq 3\%$ with probability $\geq 95\%$ by this bound? (The true answer, via [Chapter 23](https://one-course.com/books/math/5/en/chapter/23-characteristic-functions-and-the-central-limit-theorem#ch-b3-clt), is about $1070$: Chebyshev is honest but crude.)

**Solution of Exercise 22.7.**

(a) $\hat p_n = \frac{S_n}n$ with $S_n$ binomial: $\V(\hat
p_n) = \frac{p(1-p)}n \leq \frac1{4n}$, and Chebyshev ([Proposition 22.3](#prop-b3-probability-markov)) gives the bound. (b) Solve $\frac1{4n(0.03)^2} \leq 0.05$: $n \geq
\frac{1}{4\cdot0.0009\cdot0.05} \approx 5556$. The central limit theorem will justify $n \approx 1070$ for the same guarantee: Chebyshev pays for its generality with a factor $\approx 5$.

**Exercise 22.8 ★★★.**

(Bernstein) For $f \in \mathcal C(\intcc01)$ define the Bernstein polynomial $B_nf(x) =
\sum_{k=0}^n\binom nkx^k(1-x)^{n-k}f\bigl(\frac kn\bigr)$. (a) Recognize $B_nf(x) = \E\bigl[f\bigl(\frac
{S_n}n\bigr)\bigr]$ for $S_n$ binomial $\mathcal B(n, x)$. (b) Prove $B_nf \to f$ *uniformly* on $\intcc01$: split on $\{\abs{\frac{S_n}n - x} \leq \delta\}$ and its complement, using uniform [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) and Chebyshev with the uniform bound $\V(\frac{S_n}n) \leq \frac1{4n}$. (c) Conclude: a second, probabilistic proof of the Weierstrass approximation theorem ([Corollary 7.16](https://one-course.com/books/math/5/en/chapter/7-complete-spaces-baire-ascoli-stoneweierstrass#cor-b3-complete-weierstrass)), with the explicit rate $\norm{B_nf - f}_\infty \leq \frac32\,\omega_f(n^{-1/2})$ for the modulus of [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) $\omega_f$ — prove at least the $O(\omega_f(n^{-1/2}))$ form.

**Solution of Exercise 22.8.**

(a) If $S_n \sim \mathcal B(n, x)$, the transfer theorem gives $\E\bigl[f(\frac{S_n}n)\bigr] =
\sum_k\binom nkx^k(1-x)^{n-k}f(\frac kn) = B_nf(x)$.

(b)–(c) Let $\omega = \omega_f$ be the modulus of [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) ($\abs{f(u) - f(v)} \leq \omega(\abs{u - v})$, and $\omega(c
\delta) \leq (1 + c)\,\omega(\delta)$ by chaining steps). Then, for any $\delta > 0$,

$$
\abs{f(u) - f(x)} \leq \Bigl(1 + \frac{(u -
x)^2}{\delta^2}\Bigr)\omega(\delta)
$$

(if $\abs{u - x} \leq \delta$, clear; otherwise $\omega(\abs{u-x}) \leq (1 + \frac{\abs{u-x}}\delta)
\omega(\delta) \leq (1 + \frac{(u-x)^2}{\delta^2})
\omega(\delta)$). Take [expectations](#def-b3-probability-space) at $u = \frac{S_n}n$:

$$
\abs{B_nf(x) - f(x)} \leq
\Bigl(1 + \frac{\V(S_n/n)}{\delta^2}\Bigr)\omega(\delta)
\leq \Bigl(1 + \frac{1}{4n\delta^2}\Bigr)\omega(\delta) ;
$$

with $\delta = n^{-1/2}$: $\norm{B_nf - f}_\infty \leq
\frac54\,\omega\bigl(n^{-1/2}\bigr) \leq
\frac32\,\omega\bigl(n^{-1/2}\bigr) \to 0$ (uniform [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) on the [compact](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-compact)): a probabilistic Weierstrass theorem, with an explicit and uniform rate.

**Exercise 22.9 ★★★.**

(Coupon collector) Cards of $n$ types are drawn uniformly with replacement; let $T_n$ be the number of draws until all types are seen. (a) Write $T_n = \sum_{k=1}^{n}\tau_k$ with $\tau_k$ geometric of parameter $\frac{n - k + 1}n$, the $\tau_k$ [independent](#def-b3-probability-independence), and deduce $\E T_n = n\,H_n \sim n\ln n$ ($H_n$ the harmonic number) and $\V(T_n) \leq
\frac{\pi^2}6n^2$. (b) Chebyshev: $\frac{T_n}{n\ln n} \to 1$ in probability. (c) Refine with Borel–Cantelli: show directly $\P(T_n >
\beta n\ln n) \leq n^{1 - \beta}$ for $\beta > 1$ *(union bound on the event that some type is missed after $\beta n\ln n$ draws, using $1 - x \leq \eu^{-x}$)*, and deduce that along $n = 2^m$, a.s. $T_n \leq \beta n\ln
n$ eventually, for every $\beta > 2$.

**Solution of Exercise 22.9.**

(a) After $k - 1$ types are collected, each draw is new with probability $p_k = \frac{n-k+1}n$: $\tau_k$ is geometric $(p_k)$, and the $\tau_k$ are [independent](#def-b3-probability-independence) (the draws are). Sums: $\E T_n = \sum_k\frac n{n-k+1} = nH_n \sim n\ln n$; $\V(T_n) = \sum\frac{1 - p_k}{p_k^2} \leq
n^2\sum_{j=1}^n\frac1{j^2} \leq \frac{\pi^2}6n^2$.

(b) Chebyshev: $\P\bigl(\abs{T_n - nH_n} \geq \varepsilon
n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2n}
\to 0$, and $\frac{nH_n}{n\ln n} \to 1$: $\frac{T_n}{n\ln n}
\to 1$ in probability.

(c) Union bound: $T_n > t$ means some type is unseen after $\lceil t\rceil$ draws, so $\P(T_n > t) \leq n(1 -
\frac1n)^{t} \leq n\,\eu^{-t/n}$; at $t = \beta n\ln n$: $\leq n^{1 - \beta}$. For $\beta > 1$, $\sum_m
2^{m(1-\beta)} < \infty$: Borel–Cantelli gives, along $n =
2^m$, a.s. $T_n \leq \beta n\ln n$ eventually — in particular for every $\beta > 2$ as stated (any $\beta > 1$ works along the subsequence).

**Exercise 22.10 ★★.**

Using the digit construction ([Theorem 22.6](#thm-b3-probability-existence)): (a) verify by direct computation that $U = \sum b_{2k}2^{-k}$ (even-indexed digits of a uniform $\omega$) is uniform and [independent](#def-b3-probability-independence) of $V = \sum b_{2k-1}2^{-k}$; (b) deduce a [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) bijection-up-to-null-sets between $\intcc01$ and $\intcc01^2$ preserving [measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure), and comment: one uniform random number contains two (and countably many) [independent](#def-b3-probability-independence) ones — compare with the Peano curve ([Problem 6.1](https://one-course.com/books/math/5/en/chapter/6-general-topology#pb-b3-topology-1)), which achieved surjectivity but not measure-preservation or injectivity.

**Solution of Exercise 22.10.**

(a) The even-indexed digits $(b_{2k})_k$ are i.i.d. fair bits (a subfamily of the [independent](#def-b3-probability-independence) digit family), so $U =
\sum_kb_{2k}2^{-k}$ gives every dyadic interval its correct probability (as in [Theorem 22.6](#thm-b3-probability-existence)): uniform; likewise $V$; and $(U, V)$ depend on disjoint digit blocks: [independent](#def-b3-probability-independence) (factorization on dyadic rectangles, then Dynkin).

(b) $\Phi(\omega) = (U(\omega), V(\omega))$ is [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) with $\Phi_*\lambda = \lambda\otimes\lambda = \lambda_2$ (agreement on dyadic rectangles + uniqueness). Interleaving digits defines an inverse defined off the (null) set of dyadic rationals in either factor: a measure-preserving bijection between [full-measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) subsets of $\intcc01$ and $\intcc01^2$. Contrast with Peano ([Problem 6.1](https://one-course.com/books/math/5/en/chapter/6-general-topology#pb-b3-topology-1)): [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) forced surjectivity without injectivity; dropping [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) for mere [measurability](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) buys a measure-isomorphism — dimension is invisible to [measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) theory, visible to [topology](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-topology).

**Exercise 22.11 ★★.**

(Records) Let $(X_n)_{n\geq1}$ be i.i.d. with [continuous](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) distribution function, and say a *record* occurs at time $n$ if $X_n > \max(X_1, \dots, X_{n-1})$ (time $1$ is a record). Let $R_n$ be the record indicator. (a) Show $\P(R_n = 1) = \frac1n$ *(by symmetry, each of the $n!$ orderings of $X_1, \dots, X_n$ is equally likely and ties have probability $0$)*. (b) Show that the $R_n$ are *[independent](#def-b3-probability-independence)* *(count orderings compatible with prescribed record positions, or argue that the relative order of $X_1, \dots, X_{n-1}$ is [independent](#def-b3-probability-independence) of the rank of $X_n$ among them)*. (c) Deduce from Borel–Cantelli ([Theorem 22.8](#thm-b3-probability-borelcantelli), both halves) that infinitely many records occur a.s., but records at consecutive times $n, n+1$ occur infinitely often with probability — decide which! — and compute $\sum_n\P(R_n = 1, R_{n+1} = 1)$.

**Solution of Exercise 22.11.**

(a) [Continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) of the distribution makes ties null events (as in the chapter’s order-statistics arguments), and the $n!$ relative orderings of $(X_1, \dots, X_n)$ are exchangeable, hence equally likely. $R_n = 1$ means the maximum sits in the last position: probability $\frac{(n-1)!}{n!} = \frac1n$.

(b) Fix $n$ and condition on the relative ordering of $X_1,
\dots, X_{n-1}$: inserting $X_n$ into the $n$ possible rank slots is uniform and [independent](#def-b3-probability-independence) of that ordering (exchangeability of the $n$-tuple). Hence $R_n$ (the event “$X_n$ takes the top slot”) is [independent](#def-b3-probability-independence) of the whole record history $(R_1, \dots, R_{n-1})$, which is a function of the relative ordering of the first $n - 1$ variables. Induction gives full [independence](#def-b3-probability-independence) with $\P(R_n = 1) =
\frac1n$.

(c) $\sum\P(R_n = 1) = \sum\frac1n = \infty$ with [independence](#def-b3-probability-independence): the second Borel–Cantelli half gives records infinitely often a.s. (records never stop — but they thin out logarithmically: $\E[\#\text{records} \leq n] =
H_n \approx \ln n$). Consecutive records: $\P(R_n = R_{n+1}
= 1) = \frac1{n(n+1)}$ ([independence](#def-b3-probability-independence)), and

$$
\sum_n\frac1{n(n+1)} = \sum_n\Bigl(\frac1n -
\frac1{n+1}\Bigr) = 1 < \infty :
$$

the first Borel–Cantelli half applies — only finitely many consecutive-record pairs occur, a.s.

**Exercise 22.12 ★★.**

(Longest head run) Flip a fair coin infinitely often, and let $L_n$ be the length of the longest run of consecutive heads within the first $n$ flips. (a) Show that for every $\varepsilon > 0$, a.s. $L_n \leq
(1 + \varepsilon)\log_2n$ eventually *(the probability that some run of length $\ell$ starts among the first $n$ flips is at most $n2^{-\ell}$; Borel–Cantelli along $n =
2^k$)*. (b) Show that a.s. $L_n \geq (1 - \varepsilon)\log_2n$ eventually *(chop the first $n$ flips into $\lfloor n/\ell\rfloor$ disjoint blocks of length $\ell =
\lceil(1 - \varepsilon)\log_2n\rceil$; the blocks are [independent](#def-b3-probability-independence), each all-heads with probability $2^{-\ell}$, and the probability that none is all-heads is at most $\exp(-n2^{-\ell}/\ell)$; sum along $n = 2^k$ again)*. (c) Conclude $\frac{L_n}{\log_2n} \to 1$ a.s.: in a million fair flips one should expect a run of about $20$ heads — and a dataset without one is probably fabricated.

**Solution of Exercise 22.12.**

(a) A run of length $\ell$ starting at position $i \leq n$ has probability $2^{-\ell}$; union bound: $\P(L_n \geq \ell)
\leq n2^{-\ell}$. With $\ell_n = (1 +
\varepsilon)\log_2n$: $\P(L_n \geq \ell_n) \leq
n^{-\varepsilon}$. Along $n = 2^k$: $\sum_k2^{-k\varepsilon} < \infty$, so a.s. $L_{2^k} <
(1+\varepsilon)k$ eventually (Borel–Cantelli); for general $n$ pick $2^{k-1} < n \leq 2^k$ and use monotonicity of $L_n$ plus $\log_22^{k-1} \leq \log_2n$: $L_n \leq L_{2^k}
< (1 + \varepsilon)k \leq (1 + \varepsilon)\frac{k}{k-1}
\log_2n$, and the extra factor is absorbed by enlarging $\varepsilon$ slightly.

(b) With $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ and $m = \lfloor n/\ell\rfloor$ disjoint blocks: the blocks are [independent](#def-b3-probability-independence), each all-heads with probability $2^{-\ell}
\geq n^{-(1-\varepsilon)}/2$, so

$$
\P(L_n < \ell) \leq \bigl(1 - 2^{-\ell}\bigr)^{m}
\leq \exp\bigl(-m2^{-\ell}\bigr)
\leq \exp\Bigl(-c\,\frac{n^{\varepsilon}}{\log_2n}\Bigr)
$$

for a constant $c > 0$ and $n$ large. These probabilities are summable along $n = 2^k$ (indeed along all $n$): Borel–Cantelli gives a.s. $L_n \geq (1 -
\varepsilon)\log_2n$ eventually (monotonicity fills in between the $2^k$ as in (a), harmlessly).

(c) Both bounds along a sequence $\varepsilon = \frac1j$, intersecting countably many [full-measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) events: $\frac{L_n}{\log_2n} \to 1$ a.s. For $n = 10^6$: $\log_2n
\approx 19.9$ — a run of $\approx 20$ heads is not a suspicious anomaly but a mathematical certainty, and its absence is evidence of a human faking “randomness” (humans rarely dare write more than $5$ or $6$ heads in a row).

## 22.7 Problem: Etemadi’s proof of the strong law

**Problem 22.1.**

Weekend problem — the strong law of large numbers for i.i.d. integrable variables

Kolmogorov’s strong [law](#def-b3-probability-space) — $\frac{S_n}n \to \E X_1$ a.s. for i.i.d. $X_n \in L^1$ — long had only intricate proofs; in 1981 N. Etemadi found one of striking economy, using nothing beyond this chapter (and even weakening [independence](#def-b3-probability-independence) to pairwise [independence](#def-b3-probability-independence)). We follow it. Let $(X_n)$ be pairwise [independent](#def-b3-probability-independence), identically distributed, [integrable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-l1); $m = \E X_1$, $S_n = X_1 + \dots + X_n$.

**Part I — Reductions.**

1. Show that it suffices to treat $X_n \geq 0$ *(split $X_n = X_n^+ - X_n^-$: check the two halves are again pairwise [independent](#def-b3-probability-independence) i.i.d. [integrable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-l1))* . Assume henceforth $X_n \geq 0$ .
2. (Truncation) Let $Y_n = X_n\,\mathbf 1_{X_n \leq n}$ and $S_n^* = Y_1 + \dots + Y_n$. Show $$\sum_{n\geq1}\P(X_n \neq Y_n) =  \sum_{n\geq1}\P(X_1 > n) \leq \E[X_1] < \infty$$ ([Exercise 11.3](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#exo-b3-product-3)), and deduce via Borel–Cantelli that $\frac{S_n - S_n^*}{n} \to 0$ a.s.: it suffices to prove $\frac{S^*_n}n \to m$ a.s.
3. Show $\E Y_n = \E\bigl[X_1\mathbf 1_{X_1\leq  n}\bigr] \to m$ (monotone convergence), hence $\frac1n\sum_{k\leq n}\E Y_k \to m$ (Cesàro): it suffices to prove $\frac{S_n^* - \E S_n^*}{n} \to 0$ a.s.

**Part II — The variance estimate.**

4. Show $$\V(Y_n) \leq \E[Y_n^2] = \E\bigl[X_1^2\,\mathbf  1_{X_1 \leq n}\bigr]$$ and, using the layer cake ([Proposition 11.8](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#prop-b3-product-layercake)), the key bound $$\sum_{n\geq1}\frac{\V(Y_n)}{n^2}  \leq \sum_{n\geq1}\frac1{n^2}\,  \E\bigl[X_1^2\mathbf 1_{X_1\leq n}\bigr]  \leq C\,\E[X_1] < \infty$$ *(exchange the sum and the [expectation](#def-b3-probability-space) — Tonelli for series — and bound $\sum_{n \geq  x}\frac1{n^2} \leq \frac2{\max(x,1)}$ for the inner estimate $x^2\sum_{n\geq x}n^{-2} \leq 2x$)*.

**Part III — Convergence along geometric subsequences.** Fix $\alpha > 1$ and let $k_j =
\lfloor\alpha^j\rfloor$.

5. Using pairwise [independence](#def-b3-probability-independence) (variances add, [Theorem 22.5](#thm-b3-probability-independence) — check that additivity of variances needs only pairwise [independence](#def-b3-probability-independence)) and Chebyshev, show for every $\varepsilon > 0$: $$\sum_{j\geq1}\P\Bigl(\Bigl|  \frac{S^*_{k_j} - \E S^*_{k_j}}{k_j}\Bigr| \geq  \varepsilon\Bigr)  \leq  \frac1{\varepsilon^2}\sum_{j\geq1}\frac1{k_j^2}  \sum_{n\leq k_j}\V(Y_n)  = \frac1{\varepsilon^2}\sum_{n\geq1}\V(Y_n)  \sum_{j\,:\,k_j\geq n}\frac1{k_j^2} .$$
6. Show $\sum_{j : k_j \geq n}k_j^{-2} \leq  \frac{C_\alpha}{n^2}$ *(geometric series; beware the floor: $k_j \geq \frac{\alpha^j}2$ for $\alpha^j \geq 2$-type care)*, and conclude with question 4 and Borel–Cantelli: $$\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j}  \xrightarrow[j\to\infty]{\text{a.s.}} 0,  \qquad\text{hence}\qquad  \frac{S^*_{k_j}}{k_j} \to m \ \text{a.s.}$$

**Part IV — Sandwich and conclusion.**

7. For $k_j \leq n \leq k_{j+1}$, use the monotonicity of $S^*_n$ (nonnegative summands!) to show $$\frac{k_j}{k_{j+1}}\,\frac{S^*_{k_j}}{k_j}  \;\leq\; \frac{S^*_n}{n} \;\leq\;  \frac{k_{j+1}}{k_j}\,\frac{S^*_{k_{j+1}}}{k_{j+1}},$$ and deduce, a.s.: $$\frac m\alpha \leq \liminf\frac{S^*_n}n \leq  \limsup\frac{S^*_n}n \leq \alpha\,m .$$
8. Let $\alpha \downarrow 1$ along a sequence and conclude $\frac{S_n^*}n \to m$ a.s., hence (Part I) the *strong [law](#def-b3-probability-space) of large numbers*: $$\boxed{\ \frac{S_n}{n}  \xrightarrow[n\to\infty]{\text{a.s.}} \E[X_1].\ }$$
9. Where exactly was pairwise [independence](#def-b3-probability-independence) (rather than full [independence](#def-b3-probability-independence) ) sufficient? List the three places where independence-type hypotheses were invoked.

**Part V — Dividends.**

10. (Borel’s normal numbers) Show that $\lambda$ -almost every $x \in \intcc01$ is *normal in every base* $b \geq 2$ : each digit $0, \dots, b-1$ appears with asymptotic frequency $\frac1b$ *(fix $b$ and a digit, apply the strong [law](#def-b3-probability-space) to the indicator variables — justify that base-$b$ digits of a uniform variable are i.i.d. uniform on $\{0,\dots,b-1\}$ as in [Theorem 22.6](#thm-b3-probability-existence) — then intersect the countably many probability-one events)* . Exhibit one explicit non-normal number, and reflect: the theorem asserts normality of almost all numbers, yet proving normality of $\sqrt2$ or $\pi$ remains open.
11. ( [Monte Carlo](#ex-b3-probability-sllnapps) , guaranteed) Justify completely the method of [Example 22.14](#ex-b3-probability-sllnapps) (b) for $g \in L^1(\intcc01^d)$ : construct the i.i.d. uniform sample on $\intcc01^d$ from [Theorem 22.6](#thm-b3-probability-existence) and [Exercise 22.10](#exo-b3-probability-10) , and state what the strong [law](#def-b3-probability-space) delivers.

**Part VI — What full [independence](#def-b3-probability-independence) buys: maximal inequalities and random series.** Etemadi spends only pairwise [independence](#def-b3-probability-independence); the remaining parts exploit the full (mutual) version. Let $(Z_n)$ be [independent](#def-b3-probability-independence) centered variables of $L^2$ and $S_k = Z_1 + \dots + Z_k$ (a fresh notation, unrelated to the $X_n$ above).

12. (Kolmogorov’s maximal inequality) For $\varepsilon  > 0$ prove $$\P\Bigl(\max_{1\leq k\leq n}\abs{S_k} \geq  \varepsilon\Bigr) \;\leq\;  \frac1{\varepsilon^2}\sum_{k=1}^n\V(Z_k) :$$ Chebyshev’s price buys the maximum *(partition the event according to the first index $k$ with $\abs{S_k} \geq \varepsilon$; on that piece write $S_n^2 \geq S_k^2 + 2S_k(S_n - S_k)$ and use the [independence](#def-b3-probability-independence) of the coalitions $(Z_1, \dots, Z_k)$ and $(Z_{k+1}, \dots, Z_n)$, [Theorem 22.5](#thm-b3-probability-independence))*. Point out the step where pairwise [independence](#def-b3-probability-independence) would no longer suffice.
13. (Khinchin–Kolmogorov one-series theorem) Deduce: if $\sum_n\V(Z_n) < \infty$ , then $\sum_nZ_n$ converges almost surely *(show that a.s. the partial sums form a Cauchy sequence: let $m \to  \infty$ in the maximal inequality applied to $Z_{N+1}, \dots, Z_{N+m}$, then let $N \to  \infty$)* .
14. (Rademacher series) Let $(\varepsilon_n)$ be i.i.d. signs, $\P(\varepsilon_n = \pm1) =  \frac12$ ( [Theorem 22.6](#thm-b3-probability-existence) ), and let $(x_n)$ be real numbers. Show that $\sum_nx_n\varepsilon_n$ converges a.s. as soon as $\sum_nx_n^2 < \infty$ ; show also that, whatever $(x_n)$ , the probability that $\sum_nx_n\varepsilon_n$ converges is $0$ or $1$ ( [Theorem 22.9](#thm-b3-probability-zeroone) ).
15. The converse, elementarily. Set $T_n = \sum_{k\leq  n}x_k\varepsilon_k$ and $s_n^2 = \sum_{k\leq  n}x_k^2$, and suppose $s_n \to \infty$. (a) Prove the *Paley–Zygmund inequality*: for $Z \geq 0$ with $\E Z^2 < \infty$ and $0 < \theta <  1$, $$\P\bigl(Z > \theta\,\E Z\bigr) \;\geq\; (1 -  \theta)^2\,\frac{(\E Z)^2}{\E Z^2}$$ *(split $\E Z$ at the level $\theta\E Z$ and apply Cauchy–Schwarz to the upper piece)*. (b) Show $\E T_n^4 \leq 3s_n^4$. (c) Deduce $\P\bigl(\abs{T_n} > \frac{s_n}2\bigr)  \geq \frac3{16}$ and conclude that $\sum_nx_n\varepsilon_n$ diverges a.s.; hence the dichotomy $$\sum_nx_n\varepsilon_n\ \text{converges a.s.}  \iff \sum_nx_n^2 < \infty .$$
16. (Random harmonic series) Conclude that $\sum_n\frac{\varepsilon_n}{n^s}$ converges a.s. if and only if $s > \frac12$ . For $\frac12 < s \leq  1$ the series converges a.s. while $\sum_nn^{-s} = \infty$ : random signs produce square-root-strength cancellation — compare with the alternating series $\sum_n\frac{(-1)^n}{n^s}$ , which converges for *every* $s > 0$ .

**Part VII — Concentration: Hoeffding’s inequality.** The strong [law](#def-b3-probability-space) says $\frac{S_n}n \to m$; concentration inequalities say how unlikely a deviation is *at each fixed $n$*.

17. (Hoeffding’s lemma) (a) Show $\cosh\lambda \leq \eu^{\lambda^2/2}$ for all $\lambda \in \R$, by comparing the two series termwise. (b) Let $Z$ be centered with $a \leq Z \leq b$, $a < b$. Show $$\E\,\eu^{\lambda Z} \leq  \exp\Bigl(\frac{\lambda^2(b - a)^2}8\Bigr)$$ *(bound $\eu^{\lambda z}$ on $\intcc ab$ by its chord, take [expectations](#def-b3-probability-space), and study $\varphi(t)  = -pt + \log(1 - p + p\eu^t)$ with $p =  \frac{-a}{b-a}$ and $t = \lambda(b - a)$: show $\varphi(0) = \varphi'(0) = 0$ and $\varphi''  \leq \frac14$)*.
18. (Hoeffding’s inequality) Let $X_1, \dots, X_n$ be [independent](#def-b3-probability-independence) with $a_i \leq X_i \leq b_i$ and $S_n =  X_1 + \dots + X_n$. Prove, for $t > 0$, $$\P\bigl(S_n - \E S_n \geq t\bigr) \leq  \exp\Bigl(\frac{-2t^2}{\sum_{i=1}^n(b_i -  a_i)^2}\Bigr),$$ and the same bound for the lower tail *(exponential Chebyshev: bound $\E\,\eu^{\lambda(S_n - \E S_n)}$ using [independence](#def-b3-probability-independence) and question 17, then optimize over $\lambda > 0$)*.
19. (The strong [law](#def-b3-probability-space), bounded case, with a rate) Let the $X_i$ be i.i.d. with values in $\intcc ab$ and $m  = \E X_1$. Show $$\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq  \varepsilon\Bigr) \leq  2\exp\Bigl(\frac{-2n\varepsilon^2}{(b - a)^2}\Bigr)$$ and recover $\frac{S_n}n \to m$ a.s. by Borel–Cantelli: a second proof of the strong [law](#def-b3-probability-space) for bounded variables — no truncation, an exponential rate at every finite $n$, but bounded summands and full [independence](#def-b3-probability-independence). Compare the hypotheses with Etemadi’s.
20. ([Monte Carlo](#ex-b3-probability-sllnapps), guaranteed at fixed $n$) Let $g  \colon \intcc01^d \to \intcc01$ be [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) and $(U_k)$ the i.i.d. uniform sample of question 11. Given $\varepsilon, \delta > 0$, show $$n \geq \frac{\log(2/\delta)}{2\varepsilon^2}  \implies  \P\Bigl(\Bigl|\frac1n\sum_{k=1}^ng(U_k) -  \int g\,\dd\lambda_d\Bigr| \geq \varepsilon\Bigr)  \leq \delta,$$ and evaluate the threshold for $\varepsilon =  \delta = 10^{-2}$. The bound does not involve $d$: compare with question 11 and with deterministic grids.

**Part VIII — How big is a random walk? Toward the iterated logarithm.** Let $S_n = \varepsilon_1 +
\dots + \varepsilon_n$ be the simple random walk built from i.i.d. fair signs.

21. (Sub-Gaussian tails) Show $\E\,\eu^{\lambda S_n} =  (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ and deduce, for $x > 0$, $$\P(S_n \geq x) \leq \eu^{-x^2/(2n)},  \qquad  \P(\abs{S_n} \geq x) \leq 2\,\eu^{-x^2/(2n)} .$$
22. Deduce, via Borel–Cantelli, $$\limsup_{n\to\infty}\frac{\abs{S_n}}  {\sqrt{2n\log n}} \leq 1 \quad\text{a.s.}$$ *(for $\eta > 0$, sum the tail bounds at $x =  (1 + \eta)\sqrt{2n\log n}$, then intersect over $\eta = \frac1p$)*. In particular the walk lives on the CLT scale $\sqrt n$ up to a logarithmic factor — far below the crude bound $\abs{S_n} \leq n$.
23. Along the doubling subsequence $n_j = 2^j$, show $$\limsup_{j\to\infty}\frac{S_{n_j}}  {\sqrt{2n_j\log\log n_j}} \leq 1 \quad\text{a.s.},$$ and reflect: the *[law](#def-b3-probability-space) of the iterated logarithm* (Khinchin; Hartman–Wintner for general centered $L^2$ summands) states that $$\limsup_{n\to\infty}\frac{S_n}  {\sqrt{2n\log\log n}} = 1 \quad\text{a.s.}$$ Explain precisely what separates the subsequence estimate just proved from the upper half of this statement (one must control $\max_{n_j \leq n \leq  n_{j+1}}S_n$ inside each block, which requires a maximal inequality at the *exponential* scale) and check quantitatively that question 12’s inequality is too weak for that purpose. The lower half rests on the second Borel–Cantelli lemma applied to [independent](#def-b3-probability-independence) blocks; both halves are honest Year 3 material for a dedicated probability course.
24. (Uniform deviation over a finite class) Let $A_1,  \dots, A_N$ be events in a repeatable experiment, and estimate each probability by its empirical frequency $\hat p_i$ over $n$ i.i.d. repetitions. Combining Hoeffding’s inequality with a union bound, show $$\P\Bigl(\max_{i\leq N}\,\abs{\hat p_i - \P(A_i)} >  \varepsilon\Bigr) \;\leq\; 2N\,\eu^{-2n\varepsilon^2},$$ and deduce the sample-size rule: $n \geq  \frac{\ln(2N/\delta)}{2\varepsilon^2}$ guarantees all $N$ estimates simultaneously $\varepsilon$-accurate with probability $\geq 1 -  \delta$. Compute $n$ for $N = 10^6$, $\varepsilon =  0.01$, $\delta = 0.05$: the logarithmic price of uniformity.
25. (The random harmonic window) Combining the two halves of the random series theory, show that for i.i.d. signs $(\varepsilon_n)$ the series $\sum_n\frac{\varepsilon_n}{n^\alpha}$ converges a.s. if $\alpha > \frac12$ and diverges a.s. if $\alpha \leq \frac12$ ; contrast with absolute convergence (which requires $\alpha > 1$ ): on the window $\alpha \in \intoc{\frac12}1$ , convergence is a genuinely probabilistic phenomenon — cancellation, not size.

**Solution of Problem 22.1.**

**1.** $X_n^{\pm}$ are Borel functions of $X_n$: they remain pairwise [independent](#def-b3-probability-independence) ([Exercise 22.3](#exo-b3-probability-3)(a)) and identically distributed, [integrable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-l1), with $\E X_1 = \E X_1^+ - \E
X_1^-$. If the theorem holds for nonnegative variables, apply it to both halves and subtract: $\frac{S_n}n = \frac{S_n^+}n - \frac{S_n^-}n \to \E X_1^+ -
\E X_1^- = m$ a.s.

**2.** $\P(X_n \neq Y_n) = \P(X_n > n) = \P(X_1 > n)$ (identical [laws](#def-b3-probability-space)), and $\sum_n\P(X_1 > n) \leq \sum_n\P(X_1
\geq n) \leq \E X_1 < \infty$ ([Exercise 11.3](https://one-course.com/books/math/5/en/chapter/11-product-measures-fubini-change-of-variables#exo-b3-product-3)(a)). Borel–Cantelli (1): a.s. $X_n = Y_n$ for all large $n$, so $S_n - S_n^*$ is eventually constant in $n$: $\frac{S_n - S_n^*}n \to 0$ a.s., and the two normalized sums share their asymptotic behavior.

**3.** $X_1\mathbf 1_{X_1 \leq n} \nearrow X_1$: MCT gives $\E Y_n \to m$; Cesàro means of a convergent sequence converge to the same limit: $\frac{\E S_n^*}n =
\frac1n\sum_{k\leq n}\E Y_k \to m$. Hence it suffices to prove $\frac{S^*_n - \E S^*_n}{n} \to 0$ a.s.

**4.** $\V(Y_n) \leq \E Y_n^2 = \E[X_1^2\mathbf
1_{X_1\leq n}]$. By Tonelli for series,

$$
\sum_n\frac{\E[X_1^2\mathbf 1_{X_1\leq n}]}{n^2}
= \E\Bigl[X_1^2\!\!\sum_{n \geq \max(X_1, 1)}\!\frac1{n^2}
\Bigr]
\leq \E\Bigl[X_1^2\cdot\frac{4}{\max(X_1,1)}\Bigr]
\leq 4\,\E[X_1] < \infty,
$$

using $\sum_{n\geq x}n^{-2} \leq \frac4x$ for $x \geq 1$ (for $x \geq 2$: $\leq \frac1{x-1} \leq \frac2x$; for $1
\leq x < 2$: $\leq \frac{\pi^2}6 \leq \frac4x$ since $\frac4x > 2$), and $X_1^2/\max(X_1, 1) \leq X_1$ in both cases $X_1 \gtrless 1$.

**5.** Pairwise [independence](#def-b3-probability-independence) gives $\E[(Y_i - \E
Y_i)(Y_j - \E Y_j)] = 0$ for $i \neq j$ (the product formula for two variables), so variances add: $\V(S^*_k) =
\sum_{n\leq k}\V(Y_n)$. Chebyshev on each $k_j$ and summing:

$$
\sum_j\P\Bigl(\abs{S^*_{k_j} - \E S^*_{k_j}} \geq
\varepsilon k_j\Bigr)
\leq \frac1{\varepsilon^2}\sum_j\frac1{k_j^2}\sum_{n\leq
k_j}\V(Y_n)
= \frac1{\varepsilon^2}\sum_n\V(Y_n)\!\!\sum_{j : k_j\geq
n}\!\frac1{k_j^2}
$$

(Tonelli for the nonnegative double series).

**6.** $k_j = \lfloor\alpha^j\rfloor \geq
\frac{\alpha^j}2$ (valid once $\alpha^j \geq 1$, i.e. all $j \geq 0$: $\lfloor x\rfloor \geq \frac x2$ for $x \geq
1$). Hence

$$
\sum_{j : k_j \geq n}\frac1{k_j^2}
\leq 4\sum_{j : \alpha^j \geq n}\alpha^{-2j}
\leq \frac{4}{1 - \alpha^{-2}}\cdot\frac1{n^2}
= \frac{C_\alpha}{n^2},
$$

(geometric series from the first $j$ with $\alpha^j \geq
n$). Combining with questions 4–5, the double sum is finite; Borel–Cantelli (1), applied for each rational $\varepsilon$ and intersected, gives $\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \to 0$ a.s., and with question 3: $\frac{S^*_{k_j}}{k_j} \to m$ a.s.

**7.** $Y_n \geq 0$ makes $n \mapsto S^*_n$ nondecreasing: for $k_j \leq n \leq k_{j+1}$,

$$
\frac{S^*_{k_j}}{k_{j+1}} \leq \frac{S^*_n}{n} \leq
\frac{S^*_{k_{j+1}}}{k_j},
$$

which is the displayed sandwich after inserting $\frac{k_j}{k_{j+1}}$ and $\frac{k_{j+1}}{k_j}$. Since $\frac{k_{j+1}}{k_j} \to \alpha$, question 6 gives a.s.

$$
\frac m\alpha \leq \liminf_n\frac{S^*_n}n \leq
\limsup_n\frac{S^*_n}n \leq \alpha m .
$$

**8.** Apply question 7 for $\alpha = 1 + \frac1p$, $p
\in \N^*$: countably many a.s. events; on their intersection, letting $p \to \infty$: $\lim\frac{S^*_n}n =
m$ a.s. With questions 1–3, $\frac{S_n}n \to \E X_1$ a.s.: the strong [law](#def-b3-probability-space) of large numbers, under pairwise [independence](#def-b3-probability-independence).

**9.** Independence-type hypotheses appeared three times: (i) additivity of variances (question 5) — pairwise suffices; (ii) identical distribution, in the truncation sums (question 2) and the mean computation (question 3) — no [independence](#def-b3-probability-independence) at all; (iii) Borel–Cantelli (1) (questions 2 and 6) — valid without any [independence](#def-b3-probability-independence). Full mutual [independence](#def-b3-probability-independence) was never invoked: Etemadi’s observation.

**10.** Fix a base $b$ and a digit $r$. The base-$b$ digits $(d_k)$ of a uniform $\omega$ are i.i.d. uniform on $\{0, \dots, b-1\}$ (each digit vector value occupies an interval of length $b^{-m}$: the argument of [Theorem 22.6](#thm-b3-probability-existence) verbatim). The strong [law](#def-b3-probability-space) applied to the i.i.d. bounded variables $\mathbf
1_{d_k = r}$ gives: a.s., the frequency of the digit $r$ tends to $\frac1b$. Intersecting over the countably many pairs $(b, r)$: almost every number is *simply normal in every base*. An explicit non-normal number: $x = 0.100100100\ldots_2$ (frequency of ones $\frac13 \neq \frac12$). The contrast is humbling: almost all numbers are normal, yet for $\sqrt2$, $\eu$, or $\pi$ normality remains unproved — [measure](https://one-course.com/books/math/5/en/chapter/9-measure-theory#def-b3-measure-measure) theory counts without exhibiting.

**11.** By [Exercise 22.10](#exo-b3-probability-10) iterated, a single uniform variable yields a sequence of i.i.d. uniform *vectors* $U_k$ on $\intcc01^d$ (split the digit set of each $U_n$ of [Theorem 22.6](#thm-b3-probability-existence) into $d$ subfamilies). For $g \in L^1(\intcc01^d)$, the variables $g(U_k)$ are i.i.d. [integrable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-l1) with mean $\int g\,\dd\lambda_d$ (transfer): the strong [law](#def-b3-probability-space) gives

$$
\frac1n\sum_{k=1}^ng(U_k)
\xrightarrow[n\to\infty]{\text{a.s.}}
\int_{\intcc01^d}g\,\dd\lambda_d :
$$

[Monte Carlo](#ex-b3-probability-sllnapps) integration converges almost surely, in every dimension — the error size is the business of the central limit theorem ([Chapter 23](https://one-course.com/books/math/5/en/chapter/23-characteristic-functions-and-the-central-limit-theorem#ch-b3-clt)).

**12.** Let $A_k = \{\abs{S_k} \geq \varepsilon\} \cap
\bigcap_{j<k}\{\abs{S_j} < \varepsilon\}$: the $A_k$ are disjoint with union $A = \{\max_{k\leq n}\abs{S_k} \geq
\varepsilon\}$. Then

$$
\E S_n^2 \geq \sum_{k=1}^n\E\bigl[S_n^2\mathbf 1_{A_k}\bigr]
= \sum_{k=1}^n\E\Bigl[\bigl(S_k^2 + 2S_k(S_n - S_k) + (S_n
- S_k)^2\bigr)\mathbf 1_{A_k}\Bigr]
\geq \sum_{k=1}^n\E\bigl[S_k^2\mathbf 1_{A_k}\bigr],
$$

because the cross term vanishes: $S_k\mathbf 1_{A_k}$ is a Borel function of the coalition $(Z_1, \dots, Z_k)$, which is [independent](#def-b3-probability-independence) of $S_n - S_k$, a function of $(Z_{k+1},
\dots, Z_n)$ ([Theorem 22.5](#thm-b3-probability-independence)), so $\E[S_k\mathbf 1_{A_k}(S_n - S_k)] = \E[S_k\mathbf
1_{A_k}]\,\E[S_n - S_k] = 0$. On $A_k$, $S_k^2 \geq
\varepsilon^2$, whence $\E S_n^2 \geq
\varepsilon^2\sum_k\P(A_k) = \varepsilon^2\P(A)$; and $\E
S_n^2 = \sum_{k\leq n}\V(Z_k)$ (variances add). The decisive step is the factorization: $S_k\mathbf 1_{A_k}$ is a *nonlinear* function of the whole first block, and its [independence](#def-b3-probability-independence) from the second block is coalition [independence](#def-b3-probability-independence) — pairwise [independence](#def-b3-probability-independence) of the $Z_i$ only decorrelates pairs and would not justify it.

**13.** Fix $N$ and apply question 12 to $Z_{N+1},
\dots, Z_{N+m}$:

$$
\P\Bigl(\max_{N < k \leq N+m}\abs{S_k - S_N} >
\varepsilon\Bigr) \leq
\frac1{\varepsilon^2}\sum_{j=N+1}^{N+m}\V(Z_j) \leq
\frac{r_N}{\varepsilon^2},
\qquad r_N = \sum_{j>N}\V(Z_j) .
$$

The events increase with $m$; [continuity](https://one-course.com/books/math/5/en/chapter/6-general-topology#def-b3-topology-continuity) from below gives $\P(\sup_{k>N}\abs{S_k - S_N} > \varepsilon) \leq
r_N/\varepsilon^2$, and $r_N \to 0$ by hypothesis. Hence for each $p \in \N^*$, $\P\bigl(\bigcap_N\{\sup_{k>N}
\abs{S_k - S_N} > \frac1p\}\bigr) \leq \inf_Np^2r_N = 0$: almost surely, for every $p$ there is $N$ with $\sup_{k>N}\abs{S_k - S_N} \leq \frac1p$ (intersect the countably many a.s. events over $p$), so that $\abs{S_k -
S_l} \leq \frac2p$ for all $k, l > N$: the partial sums are a.s. Cauchy, hence a.s. convergent.

**14.** The variables $Z_n = x_n\varepsilon_n$ are [independent](#def-b3-probability-independence) (Borel functions of [independent](#def-b3-probability-independence) variables, [Exercise 22.3](#exo-b3-probability-3)(a)), centered, with $\V(Z_n) =
x_n^2$: question 13 applies when $\sum_nx_n^2 < \infty$ and gives a.s. convergence. In general, for each $N$ the convergence of $\sum_nx_n\varepsilon_n$ is unaffected by the values of $\varepsilon_1, \dots, \varepsilon_N$: the convergence event lies in the tail $\sigma$-algebra of the [independent](#def-b3-probability-independence) sequence $(\varepsilon_n)$, so Kolmogorov’s [zero–one law](#thm-b3-probability-zeroone) ([Theorem 22.9](#thm-b3-probability-zeroone)) forces its probability to be $0$ or $1$.

**15.** (a) Splitting at the level $\theta\E Z$ and using Cauchy–Schwarz on the upper piece,

$$
\E Z = \E\bigl[Z\mathbf 1_{Z \leq \theta\E Z}\bigr] +
\E\bigl[Z\mathbf 1_{Z > \theta\E Z}\bigr]
\leq \theta\,\E Z + \sqrt{\E Z^2}\,
\sqrt{\P(Z > \theta\E Z)} ,
$$

so $(1 - \theta)\E Z \leq \sqrt{\E Z^2\,\P(Z > \theta\E
Z)}$; square. (b) Expand $T_n^4 =
\sum_{i,j,k,l}x_ix_jx_kx_l\,
\E[\varepsilon_i\varepsilon_j\varepsilon_k\varepsilon_l]$: the [expectation](#def-b3-probability-space) is $1$ when the indices pair off (all four equal, or two distinct pairs, the latter in $3$ arrangements) and $0$ otherwise (an unpaired sign has zero mean and factors out by [independence](#def-b3-probability-independence)). Hence

$$
\E T_n^4 = \sum_kx_k^4 + 3\sum_{i\neq j}x_i^2x_j^2 =
3s_n^4 - 2\sum_kx_k^4 \leq 3s_n^4 .
$$

(c) Paley–Zygmund with $Z = T_n^2$, $\E Z = s_n^2$, $\theta = \frac14$:

$$
\P\Bigl(\abs{T_n} > \frac{s_n}2\Bigr) = \P\Bigl(T_n^2 >
\frac{s_n^2}4\Bigr) \geq \Bigl(\frac34\Bigr)^2
\frac{s_n^4}{3s_n^4} = \frac3{16} .
$$

If the series converged with positive probability, it would converge a.s. (question 14), so $\sup_n\abs{T_n} <
\infty$ a.s., and some $M$ would satisfy $\P(\sup_n\abs{T_n} > M) < \frac3{16}$; but as soon as $s_n
> 2M$, $\P(\abs{T_n} > M) \geq \P(\abs{T_n} > \frac{s_n}2)
\geq \frac3{16}$: contradiction. So divergence is almost sure, and with question 14 the dichotomy is [complete](https://one-course.com/books/math/5/en/chapter/7-complete-spaces-baire-ascoli-stoneweierstrass#def-b3-complete-complete).

**16.** Here $x_n = n^{-s}$ and $\sum_nn^{-2s} <
\infty$ exactly when $s > \frac12$: by questions 14–15, $\sum_n\frac{\varepsilon_n}{n^s}$ converges a.s. if and only if $s > \frac12$ (for $s \leq \frac12$, a.s. divergence). For $\frac12 < s \leq 1$ the convergence is never absolute. The comparison is instructive: perfectly alternating signs cancel at strength $n^{-s}$ for every $s
> 0$, while typical random signs cancel only at square-root strength — the random walk of question 21 grows like $\sqrt n$, and Abel summation converts exactly that growth into convergence of $\sum\varepsilon_nn^{-s}$ for $s > \frac12$.

**17.** (a) $\cosh\lambda =
\sum_k\frac{\lambda^{2k}}{(2k)!}$ and $\eu^{\lambda^2/2} =
\sum_k\frac{\lambda^{2k}}{2^kk!}$; and $(2k)! \geq 2^kk!$ holds termwise, because $\frac{(2k)!}{k!} =
\prod_{i=1}^k(k + i) \geq \prod_{i=1}^k(2i) = 2^kk!$ (each factor satisfies $k + i \geq 2i$ for $i \leq k$), so that in fact $(2k)! \geq 2^k(k!)^2 \geq 2^kk!$. (b) Note $a \leq 0 \leq b$ ($Z$ is centered), and by convexity of $z \mapsto \eu^{\lambda z}$, for $z \in \intcc ab$:

$$
\eu^{\lambda z} \leq \frac{b - z}{b - a}\,\eu^{\lambda a} +
\frac{z - a}{b - a}\,\eu^{\lambda b},
\qquad\text{so}\qquad
\E\,\eu^{\lambda Z} \leq \frac{b\,\eu^{\lambda a} -
a\,\eu^{\lambda b}}{b - a}
= (1 - p)\eu^{-pt} + p\,\eu^{(1-p)t} = \eu^{\varphi(t)}
$$

with $p = \frac{-a}{b-a} \in \intcc01$, $t = \lambda(b -
a)$, $\varphi(t) = -pt + \log(1 - p + p\eu^t)$. Then $\varphi(0) = 0$, $\varphi'(t) = -p + \frac{p\eu^t}{1 - p +
p\eu^t}$ vanishes at $0$, and $\varphi''(t) = \rho(1 -
\rho) \leq \frac14$ for $\rho = \frac{p\eu^t}{1 - p +
p\eu^t} \in \intcc01$: Taylor at order $2$ gives $\varphi(t) \leq \frac{t^2}8 = \frac{\lambda^2(b-a)^2}8$.

**18.** For $\lambda > 0$, Markov applied to the positive variable $\eu^{\lambda(S_n - \E S_n)}$ ([Proposition 22.3](#prop-b3-probability-markov)) and the product formula for [independent](#def-b3-probability-independence) variables give

$$
\P(S_n - \E S_n \geq t) \leq \eu^{-\lambda
t}\prod_{i=1}^n\E\,\eu^{\lambda(X_i - \E X_i)}
\leq \exp\Bigl(-\lambda t +
\frac{\lambda^2}8\sum_i(b_i - a_i)^2\Bigr),
$$

by question 17(b) applied to each centered $X_i - \E X_i
\in \intcc{a_i - \E X_i}{b_i - \E X_i}$ (same width). Minimizing the exponent at $\lambda = \frac{4t}{D}$, $D =
\sum_i(b_i - a_i)^2$, yields $-\frac{2t^2}D$. The lower tail follows by applying the result to $(-X_i)$.

**19.** Take $t = n\varepsilon$ and $D = n(b - a)^2$:

$$
\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr)
\leq 2\exp\Bigl(\frac{-2n^2\varepsilon^2}{n(b-a)^2}\Bigr)
= 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b-a)^2}\Bigr),
$$

which is summable in $n$ (a geometric-type series): Borel–Cantelli ([Theorem 22.8](#thm-b3-probability-borelcantelli)) gives that a.s. $\abs{\frac{S_n}n - m} < \varepsilon$ eventually; intersecting over $\varepsilon = \frac1p$ yields $\frac{S_n}n \to m$ a.s. Comparison: Etemadi asks only $X_1 \in L^1$ and pairwise [independence](#def-b3-probability-independence), and delivers no rate; Hoeffding asks boundedness and full [independence](#def-b3-probability-independence), and delivers an explicit exponential guarantee at every finite $n$ — the two theorems answer different questions about the same limit.

**20.** The $g(U_k)$ are i.i.d. with values in $\intcc01$ and mean $\int g\,\dd\lambda_d$ (transfer), so question 18 with $b_i - a_i = 1$, $t = n\varepsilon$ gives the two-sided bound $2\eu^{-2n\varepsilon^2} \leq \delta$ as soon as $\eu^{2n\varepsilon^2} \geq \frac2\delta$, i.e. $n \geq \frac{\log(2/\delta)}{2\varepsilon^2}$. For $\varepsilon = \delta = 10^{-2}$:

$$
n \geq \frac{\log 200}{2\cdot10^{-4}} =
\frac{5.2983\ldots}{0.0002} \approx 26\,492 :
$$

about $26\,500$ samples guarantee a $1\%$ accuracy with $99\%$ confidence — in every dimension $d$, for every [measurable](https://one-course.com/books/math/5/en/chapter/10-the-lebesgue-integral#def-b3-lebesgue-measurable) integrand with values in $\intcc01$. Question 11’s strong [law](#def-b3-probability-space) promised convergence with no finite-$n$ guarantee; a deterministic grid with $k$ points per axis costs $k^d$ evaluations, exponential in $d$. Concentration is what makes [Monte Carlo](#ex-b3-probability-sllnapps) a *method* rather than a hope.

**21.** [Independence](#def-b3-probability-independence) and the product formula: $\E\,\eu^{\lambda S_n} = (\E\,\eu^{\lambda\varepsilon_1})^n
= (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ by question 17(a). Markov on $\eu^{\lambda S_n}$:

$$
\P(S_n \geq x) \leq \eu^{-\lambda x + n\lambda^2/2}
= \eu^{-x^2/(2n)}
\qquad\text{at the optimum } \lambda = \frac xn,
$$

and the symmetric bound for $-S_n$ (same [law](#def-b3-probability-space)) doubles the constant for $\abs{S_n}$.

**22.** Fix $\eta > 0$ and set $x_n = (1 +
\eta)\sqrt{2n\log n}$ for $n \geq 2$:

$$
\P(\abs{S_n} \geq x_n) \leq 2\exp\bigl(-(1 +
\eta)^2\log n\bigr) = \frac{2}{n^{(1+\eta)^2}},
$$

summable since $(1 + \eta)^2 > 1$. Borel–Cantelli: a.s. $\abs{S_n} < (1 + \eta)\sqrt{2n\log n}$ for all large $n$, so $\limsup_n\frac{\abs{S_n}}{\sqrt{2n\log n}} \leq 1 +
\eta$ a.s.; intersecting the a.s. events for $\eta =
\frac1p$, $p \in \N^*$, gives the claim. The walk of size $n$ has typical amplitude $\sqrt n$ (its variance), and even its worst excursions exceed that scale by at most $\sqrt{2\log n}$.

**23.** With $n_j = 2^j$ and $x = (1 +
\eta)\sqrt{2n_j\log\log n_j}$ (defined for $j \geq 2$), question 21 gives

$$
\P\bigl(S_{n_j} \geq x\bigr) \leq \exp\bigl(-(1 +
\eta)^2\log\log n_j\bigr) = (j\log 2)^{-(1+\eta)^2},
$$

summable in $j$ since $(1 + \eta)^2 > 1$: Borel–Cantelli and $\eta = \frac1p$ give $\limsup_jS_{n_j}/\sqrt{2n_j
\log\log n_j} \leq 1$ a.s. What is missing for the full upper half is the bridge between checkpoints: one must show $\max_{n_j\leq n\leq n_{j+1}}S_n$ exceeds $(1+\eta)\sqrt{2n_j\log\log n_j}$ only finitely often, which demands a maximal inequality with *Gaussian* tails (Lévy’s reflection inequality or Ottaviani’s inequality, not proved here). Question 12 is quantitatively too weak: it bounds the probability by

$$
\frac{n_j}{(1+\eta)^2\,2n_j\log\log n_j}
= \frac{1}{2(1+\eta)^2\log(j\log2)},
$$

which tends to $0$ but is *not summable* in $j$: Borel–Cantelli cannot conclude. The lower half of the [law](#def-b3-probability-space) of the iterated logarithm applies the second Borel–Cantelli lemma to the [independent](#def-b3-probability-independence) increments $S_{n_{j+1}} - S_{n_j}$, using matching lower bounds for Gaussian-type tails. Both refinements are genuine Year 3 probability, one course further along; what this problem delivers unaided is the exact iterated-logarithm scale along geometric times.

**24.** Each $\hat p_i$ is an average of $n$ i.i.d. indicator variables with values in $\intcc01$ and mean $\P(A_i)$: Hoeffding gives $\P(\abs{\hat p_i - \P(A_i)} >
\varepsilon) \leq 2\eu^{-2n\varepsilon^2}$. The union bound multiplies by $N$. Solving $2N\eu^{-2n\varepsilon^2} \leq
\delta$: $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$. Numerically: $\ln\frac{2\cdot10^6}{0.05} =
\ln(4\cdot10^7) \approx 17.5$, so $n \geq
\frac{17.5}{2\cdot10^{-4}} \approx 87\,600$: estimating *one* probability to $\pm1\%$ takes about $18\,500$ samples ($\ln(2/\delta)/2\varepsilon^2$), and a *million* probabilities only $\approx 4.7$ times more — uniformity costs $\ln N$, not $N$: the observation that makes empirical risk minimization, and with it machine learning, statistically possible.

**25.** The variables $X_n = \frac{\varepsilon_n}
{n^\alpha}$ are [independent](#def-b3-probability-independence), centered, bounded, with $\sum_n\V(X_n) = \sum_nn^{-2\alpha}$. If $\alpha >
\frac12$: the variance series converges, and the one-series theorem (Part VI) gives a.s. convergence of $\sum X_n$. If $\alpha \leq \frac12$: the variance series diverges, and the converse half (Part VI’s Paley–Zygmund argument, applicable since the summands are bounded by $1$) gives a.s. divergence. Absolute convergence asks $\sum n^{-\alpha} < \infty$: $\alpha > 1$. On $\intoc{\frac12}1$, the series converges a.s. although $\sum\abs{X_n} = \infty$ surely: the signs conspire to cancel, with probability one — convergence by cancellation, invisible to any absolute test, and (by the [zero–one law](#thm-b3-probability-zeroone)) with a deterministic verdict all the same.