University Mathematics — Year 3 · Bachelor Year 3

22Probability: Foundations and the Law of Large Numbers

Year 2 built probability on countable spaces; measure theory now removes every restriction. A probability space is a measure space of total mass $1$ , random variables are measurable maps, expectation is the Lebesgue integral — and at once the whole analytic arsenal (Chapters 9, 10 and 11) applies to chance. This chapter installs the dictionary, constructs infinite sequences of independent random variables (on $\intcc01$ , from binary digits: randomness is hiding inside Lebesgue measure), proves the Borel–Cantelli lemmas and Kolmogorov’s zero–one law, sorts out the modes of convergence, and proves the law 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 in its definitive $L^1$ form.

22.1 The dictionary

Definition 22.1

A probability space is a measure space $(\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 map $X \colon \Omega \to \R$ (or $\R^d$ : a random vector); its law is the pushforward probability measure $\P_X = X_*\P$ on $\R$ (Exercise 11.9), determined by the distribution function $F_X(t) = \P(X \leq t)$ (Exercise 9.3). $X$ has density $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) 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 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 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 itself); exponential $\mathcal E(\lambda)$ (density $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$ ); the Gaussian $\mathcal N(m, \sigma^2)$ with density $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x - m)^2}{2\sigma^2}\bigr)$ — a probability density by Problem 10.1, with mean $m$ and variance $\sigma^2$ (Gaussian moments, Exercise 11.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(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 $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 iff the law of the vector $(X_1, \dots, X_n)$ is the product measure $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$ . In that case, for $g_i \geq 0$ (or such that the products are integrable):

\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 $L^2$ variables.

Proof. If the $X_i$ are independent, the two probability measures $\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(b)) — hence everywhere (Theorem 9.7). Conversely, a product law factorizes all events $\bigcap_iX_i^{-1}(B_i)$ : independence. The expectation formula is then Tonelli/Fubini (Theorem 11.5) 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 random variables, each uniform on $\intcc01$ . Consequently, for any prescribed laws $(\mu_n)$ on $\R$ there exist independent $(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 ( $\{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 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 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 (Theorem 9.7). The $U_n$ are independent: they are functions of disjoint blocks of the independent 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. 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 of $F$ , monotonicity) shows $X_n = G_n(U_n)$ is measurable with $\P(X_n \leq t) = \P(U_n \leq F_{\mu_n}(t)) = F_{\mu_n}(t)$ : law $\mu_n$ ; independence is inherited (functions of independent variables, Exercise 22.3). ∎

Example 22.7 (The birthday problem, honestly)

Among $n$ people with independent, 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 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, 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’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”).

If $\sum\P(A_n) < \infty$ , then $\P(\limsup A_n) = 0$ .
If $\sum\P(A_n) = \infty$ and the $A_n$ are independent, then $\P(\limsup A_n) = 1$ .

Proof. (1) is Exercise 9.4. (2): for $N \leq M$ , independence of complements (Exercise 22.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 from above, Proposition 9.6). ∎

Theorem 22.9 (Kolmogorov’s zero–one law)

Let $(X_n)$ be independent 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: 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, 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 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 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 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) 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. ∎

22.5 The law of large numbers

Throughout, $(X_n)$ are independent with the same law (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); 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 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), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ a.s.: integrals by sampling, in any dimension, at the dimension-independent rate $\sim n^{-1/2}$ made precise in Chapter 23. (c) Normal numbers: almost every real number has, in its binary expansion, asymptotic frequency $\frac12$ of ones (apply the strong law to the digit variables of Theorem 22.6) — Borel’s theorem, a statement about everyday numbers proved by measure: Problem 22.1 completes 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) 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 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.

22.6 Exercises

Exercise 22.1 ★

(a) Let $X$ have continuous 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 of $X^2$ for $X$ uniform on $\intcc{-1}1$ , and of $-\frac1\lambda\ln U$ for $U$ uniform on $\intoo01$ .

Solution

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 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, 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 $\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 via the transfer theorem. (b) Show that a positive random variable $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.)

Solution

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; $G(1) = 0$ is excluded by hypothesis) and squeezing an arbitrary $t$ between rationals (monotonicity): $G(t) = \eu^{-\lambda t}$ — the exponential law. The converse is a computation.

Exercise 22.3 ★★

(a) Show that if $X_1, \dots, X_n$ are independent and $f_i$ are Borel functions, the $f_i(X_i)$ are independent. (b) Show that events $A_1, \dots, A_n$ are independent iff their complements are, iff the indicators $\mathbf 1_{A_i}$ are independent random variables. (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 but not independent.

Solution

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 $\sigma$ -algebras are independent (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 of the same $\sigma$ -algebras. (That factorization over the $A_i$ propagates to complements is the $\lambda$ -system argument inside Definition 22.4’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. But $\P(A\cap B\cap C) = \P(\text{HH}) = \frac14 \neq \frac18$ : not independent — $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): the longest run in the first $n$ digits grows like $\log_2n$ .

Solution

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 (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 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. (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 can fail for it.

Solution

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. Then each event $\{R \leq c\}$ has probability $0$ or $1$ (Theorem 22.9), 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.

(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 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

Solution of Exercise 22.6.

Work on $(\intcc01, \lambda)$ . (a) The typewriter $\mathbf 1_{I_n}$ (Exercise 12.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(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 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, is about $1070$ : Chebyshev is honest but crude.)

Solution

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) 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 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), with the explicit rate $\norm{B_nf - f}_\infty \leq \frac32\,\omega_f(n^{-1/2})$ for the modulus of continuity $\omega_f$ — prove at least the $O(\omega_f(n^{-1/2}))$ form.

Solution

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 ( $\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 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 on the 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, 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

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 (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): (a) verify by direct computation that $U = \sum b_{2k}2^{-k}$ (even-indexed digits of a uniform $\omega$ ) is uniform and independent of $V = \sum b_{2k-1}2^{-k}$ ; (b) deduce a measurable bijection-up-to-null-sets between $\intcc01$ and $\intcc01^2$ preserving measure, and comment: one uniform random number contains two (and countably many) independent ones — compare with the Peano curve (Problem 6.1), which achieved surjectivity but not measure-preservation or injectivity.

Solution

Solution of Exercise 22.10.

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

(b) $\Phi(\omega) = (U(\omega), V(\omega))$ is 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 subsets of $\intcc01$ and $\intcc01^2$ . Contrast with Peano (Problem 6.1): continuity forced surjectivity without injectivity; dropping continuity for mere measurability buys a measure-isomorphism — dimension is invisible to measure theory, visible to topology.

Exercise 22.11 ★★

(Records) Let $(X_n)_{n\geq1}$ be i.i.d. with continuous 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 (count orderings compatible with prescribed record positions, or argue that the relative order of $X_1, \dots, X_{n-1}$ is independent of the rank of $X_n$ among them). (c) Deduce from Borel–Cantelli (Theorem 22.8, 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

Solution of Exercise 22.11.

(a) 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 of that ordering (exchangeability of the $n$ -tuple). Hence $R_n$ (the event “ $X_n$ takes the top slot”) is independent 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 with $\P(R_n = 1) = \frac1n$ .

(c) $\sum\P(R_n = 1) = \sum\frac1n = \infty$ with 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), 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, 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

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, 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 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 — $\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 to pairwise independence). We follow it. Let $(X_n)$ be pairwise independent, identically distributed, integrable; $m = \E X_1$ , $S_n = X_1 + \dots + X_n$ .

Part I — Reductions.

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 i.i.d. integrable). Assume henceforth $X_n \geq 0$ .
(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), 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.
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.

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), 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 — 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$ .

Using pairwise independence (variances add, Theorem 22.5 — check that additivity of variances needs only pairwise 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} .$
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.

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 .$
Let $\alpha \downarrow 1$ along a sequence and conclude $\frac{S_n^*}n \to m$ a.s., hence (Part I) the strong law of large numbers:

$\boxed{\ \frac{S_n}{n} \xrightarrow[n\to\infty]{\text{a.s.}} \E[X_1].\ }$
Where exactly was pairwise independence (rather than full independence) sufficient? List the three places where independence-type hypotheses were invoked.

Part V — Dividends.

(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 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 — 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.
(Monte Carlo, guaranteed) Justify completely the method of Example 22.14(b) for $g \in L^1(\intcc01^d)$ : construct the i.i.d. uniform sample on $\intcc01^d$ from Theorem 22.6 and Exercise 22.10, and state what the strong law delivers.

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

(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 of the coalitions $(Z_1, \dots, Z_k)$ and $(Z_{k+1}, \dots, Z_n)$ , Theorem 22.5). Point out the step where pairwise independence would no longer suffice.
(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$ ).
(Rademacher series) Let $(\varepsilon_n)$ be i.i.d. signs, $\P(\varepsilon_n = \pm1) = \frac12$ (Theorem 22.6), 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).
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 .$
(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 says $\frac{S_n}n \to m$ ; concentration inequalities say how unlikely a deviation is at each fixed $n$ .

(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, 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$ ).
(Hoeffding’s inequality) Let $X_1, \dots, X_n$ be independent 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 and question 17, then optimize over $\lambda > 0$ ).
(The strong law, 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 for bounded variables — no truncation, an exponential rate at every finite $n$ , but bounded summands and full independence. Compare the hypotheses with Etemadi’s.
(Monte Carlo, guaranteed at fixed $n$ ) Let $g \colon \intcc01^d \to \intcc01$ be 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.

(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)} .$
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$ .
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 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 blocks; both halves are honest Year 3 material for a dedicated probability course.
(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.
(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

Solution of Problem 22.1.

1. $X_n^{\pm}$ are Borel functions of $X_n$ : they remain pairwise independent (Exercise 22.3(a)) and identically distributed, integrable, 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), and $\sum_n\P(X_1 > n) \leq \sum_n\P(X_1 \geq n) \leq \E X_1 < \infty$ (Exercise 11.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 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 of large numbers, under pairwise 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 at all; (iii) Borel–Cantelli (1) (questions 2 and 6) — valid without any independence. Full mutual 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 verbatim). The strong law 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 theory counts without exhibiting.

11. By Exercise 22.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 into $d$ subfamilies). For $g \in L^1(\intcc01^d)$ , the variables $g(U_k)$ are i.i.d. integrable with mean $\int g\,\dd\lambda_d$ (transfer): the strong law gives

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

Monte Carlo integration converges almost surely, in every dimension — the error size is the business of the central limit theorem (Chapter 23).

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 of $S_n - S_k$ , a function of $(Z_{k+1}, \dots, Z_n)$ (Theorem 22.5), 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 from the second block is coalition independence — pairwise 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 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 (Borel functions of independent variables, Exercise 22.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 sequence $(\varepsilon_n)$ , so Kolmogorov’s zero–one law (Theorem 22.9) 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 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). 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 .

\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.

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) and the product formula for independent 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) 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, and delivers no rate; Hoeffding asks boundedness and full 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 integrand with values in $\intcc01$ . Question 11’s strong law 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 a method rather than a hope.

21. 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) 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 of the iterated logarithm applies the second Borel–Cantelli lemma to the independent 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, 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) with a deterministic verdict all the same.