University Mathematics — Year 2 · Bachelor Year 2

22Discrete Random Variables

Random variables organize probability computations around functions rather than events. On countable spaces the theory is powered by the summable families of Chapter 7: expectation is the sum of a family indexed by the sample space, and all its properties — linearity, transfer, product formula for independent variables — are theorems about summable families. The chapter proves the key inequalities of Markov, Chebyshev, Cauchy–Schwarz and Jensen, and ends with the classical laws and the weak law of large numbers, whose proof is two lines once Chebyshev is available.

22.1 Random variables and their laws

Definition 22.1 (Discrete random variable; law)

Let $(\Omega, \P)$ be a countable probability space. A random variable is a map $X \colon \Omega \to E$ ( $E$ any set; real random variable when $E = \R$ ). Its law (or distribution) is the probability measure $\P_X$ on the countable set $X(\Omega)$ defined by

\P_X(\{x\}) = \P(X = x) = \P\bigl(\{\omega : X(\omega) = x\}\bigr) .

Example 22.2 (The classical laws)

Bernoulli $\mathcal{B}(p)$ : $X \in \{0, 1\}$ , $\P(X = 1) = p$ . Indicator of an event.
Binomial $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ , $0 \leq k \leq n$ : number of successes in $n$ independent Bernoulli trials (High School volume; re-proved below via sums of independent variables).
Geometric $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : rank of the first success (Example 21.5).
Poisson $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — a probability measure by the exponential series. The law of rare events (Chapter 23).

Remark 22.3 (Which law models what)

The four laws answer four primitive questions: Bernoulli, “did it happen?”; binomial, “how many times in $n$ tries?”; geometric, “how long until the first time?”; Poisson, “how many events at a given rate, when tries are many and individually unlikely?”. Recognizing the question is nine tenths of the modelling: sums of indicators point to the binomial, waiting times to the geometric, rare-event counts to the Poisson — with the passage from binomial to Poisson made precise by the law of rare events in Chapter 23.

Proposition 22.4 (Memorylessness of the geometric law)

If $X \sim \mathcal{G}(p)$ , then for all $m, n \in \N$ :

\P(X > m + n \mid X > m) = \P(X > n) ,

and the geometric laws are the only laws on $\N^*$ with this property.

Proof. Summing the geometric weights, $\P(X > n) = (1-p)^n$ . Hence

\P(X > m + n \mid X > m) = \frac{\P(X > m + n)}{\P(X > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \P(X > n).

Conversely, if $G(n) = \P(X > n)$ satisfies $G(m + n) = G(m)G(n)$ with $G(0) = 1$ , then $G(n) = G(1)^n$ by induction; $q = G(1) \in \intco{0}{1}$ , and $q = 0$ or the law is $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Example 22.5 (No number is ever “due”)

Roll a die, waiting for a six: the waiting time is $X \sim \mathcal G(1/6)$ . Memorylessness says that after $10$ fruitless rolls, the remaining wait $X - 10$ , given $X > 10$ , is again $\mathcal G(1/6)$ : the conditional expected wait is still $6$ rolls, exactly as at the start. The die does not remember, and no six is ever “due” — the gambler’s fallacy is the belief that the conditional law should have shifted. Conversely, the proposition’s uniqueness half says this indifference characterizes geometric waiting times: any waiting time whose forecast never updates is geometric. Real queues and lifetimes usually do update, which is precisely how one detects that they are not geometric.

22.2 Expectation

Definition 22.6 (Expectation)

A real random variable $X$ on $(\Omega, \P)$ has an expectation if the family $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ is summable (Chapter 7); its expectation is then

\E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) .

Theorem 22.7 (Transfer theorem)

$X$ has an expectation if and only if the family $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ is summable, and then

\E(X) = \sum_{x \in X(\Omega)} x\,\P(X = x) .

More generally, for $f \colon X(\Omega) \to \R$ , the variable $f(X)$ has an expectation iff $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , and then $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Proof. Partition $\Omega$ into the level sets $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . By the summation-by-packets theorem for summable families (Chapter 7), the family $(X(\omega)\P(\{\omega\}))_\omega$ is summable iff each packet is (automatic: $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) and the family of packet sums $\bigl(x\,\P(X = x)\bigr)_x$ is summable — and then the total sums agree. For $f(X)$ : apply the proven statement to the variable $Y = f \circ X$ , whose level sets are $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ; a second summation by packets converts $\sum_y y\,\P(Y = y)$ into $\sum_x f(x)\,\P(X = x)$ , the packets now grouping the values $x$ by their image $f(x)$ , with absolute summability of one family equivalent to that of the other. ∎

Theorem 22.8 (Properties of expectation)

On the set of random variables with expectation:

(Linearity) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positivity and monotonicity) $X \geq 0 \Rightarrow \E(X) \geq 0$ ; $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ; and $\abs{\E(X)} \leq \E(\abs X)$ .
(Domination) If $\abs X \leq Z$ and $Z$ has an expectation, so does $X$ .

Proof. All are properties of sums of summable families (Chapter 7): linearity of the sum, positivity term by term, and the domination criterion for summability. (Note that linearity is immediate on the definition over $\Omega$ , while it would be awkward on the transfer formula — one benefit of defining $\E$ upstream.) ∎

Example 22.9

$X \sim \mathcal{B}(n, p)$ : writing $X = X_1 + \dots + X_n$ as a sum of Bernoulli indicators and using linearity, $\E(X) = np$ — no binomial coefficients needed. $X \sim \mathcal{G}(p)$ : $\E(X) = \sum_{k\geq1}k(1-p)^{k-1}p = p\cdot\frac{1}{(1 - (1-p))^2} = \frac1p$ , by differentiating the geometric series inside its disk (Chapter 11). $X \sim \mathcal{P}(\lambda)$ : $\E(X) = \sum_{k\geq1}k e^{-\lambda}\frac{\lambda^k}{k!} = \lambda e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda$ .

Example 22.10 (Transfer in action)

For $X \sim \mathcal P(\lambda)$ , compute $\E\bigl(\frac1{1+X}\bigr)$ — the law of $\frac1{1+X}$ itself is awkward, but transfer never asks for it:

\E\Bigl(\frac1{1+X}\Bigr) = \sum_{k\geq0}\frac{1}{k+1}\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \frac{\eu^{-\lambda}}{\lambda}\sum_{k\geq0} \frac{\lambda^{k+1}}{(k+1)!} = \frac{\eu^{-\lambda}}{\lambda}\bigl(\eu^\lambda - 1\bigr) = \frac{1 - \eu^{-\lambda}}{\lambda} .

Two lessons. Computationally: recognizing a shifted exponential series is the whole work — transfer reduces expectations of $f(X)$ to series manipulation. Structurally: the naive plug-in value would be $\frac1{1 + \E X} = \frac1{1 + \lambda}$ , and the true answer is larger,

\frac{1 - \eu^{-\lambda}}{\lambda} \geq \frac{1}{1 + \lambda},

exactly as Jensen’s inequality for the convex function $t \mapsto \frac1{1+t}$ demands. Expectations of convex images sit above the naive plug-in value, and transfer plus a series check makes the abstract inequality concrete.

Theorem 22.11 (Independence and products)

Random variables $X, Y$ are independent if $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ for all $x, y$ — equivalently, the events $\{X \in A\}$ and $\{Y \in B\}$ are independent for all $A, B$ . If $X$ and $Y$ are independent real variables with expectations, then $XY$ has an expectation and

\E(XY) = \E(X)\,\E(Y) .

Proof. The equivalence of the two formulations follows by summing the pointwise identity over $(x, y) \in A \times B$ ( $\sigma$ -additivity twice). For the product: the double family $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ is summable, since by Fubini for families (Chapter 7)

\sum_{x, y}\abs x \abs y\,\P(X{=}x)\P(Y{=}y) = \Bigl(\sum_x \abs x \P(X{=}x)\Bigr) \Bigl(\sum_y \abs y \P(Y{=}y)\Bigr) < \infty ;

by independence this family is exactly $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , whose sum is $\E(XY)$ by transfer applied to the variable $(X, Y) \mapsto xy$ ; Fubini again evaluates the unsigned sum as the product $\E(X)\E(Y)$ . ∎

Example 22.12 (Products, with and without independence)

Roll two fair dice. If $Y$ is the second die (independent of the first), $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . If instead $Y = X$ (the “product” of a die with itself),

\E(X^2) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17 \neq 12.25 :

same marginal laws in both scenarios, different joint laws, different product expectations. The moral, worth engraving: $\E(XY)$ is a functional of the pair, not of the two marginals — and the gap $\E(X^2) - \E(X)^2 \approx 2.92$ is, by König–Huygens, precisely the variance $\frac{35}{12}$ of the die.

22.3 Variance, covariance, and the classical inequalities

Definition 22.13 (Moments, variance)

$X$ has a moment of order 2 if $X^2$ has an expectation (then so does $X$ , by domination: $\abs X \leq \frac{1 + X^2}{2}$ ). Its variance and standard deviation are then

V(X) = \E\bigl((X - \E(X))^2\bigr) = \E(X^2) - \E(X)^2 , \qquad \sigma(X) = \sqrt{V(X)} ,

(the second form — the König–Huygens formula — by expanding the square and using linearity:

\E\bigl((X - \E X)^2\bigr) = \E\bigl(X^2 - 2X\,\E X + \E(X)^2\bigr) = \E(X^2) - 2\,\E(X)^2 + \E(X)^2 ,

the middle term using that $\E X$ is a constant). For $X, Y$ with second moments, the covariance is

\operatorname{Cov}(X, Y) = \E\bigl((X - \E X)(Y - \E Y)\bigr) = \E(XY) - \E(X)\E(Y) .

Theorem 22.14 (Variance toolkit)

For variables with second moments:

$V(aX + b) = a^2\,V(X)$ ;
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ , and more generally

$V\Bigl(\sum_{i=1}^n X_i\Bigr) = \sum_{i=1}^n V(X_i) + 2\sum_{i < j}\operatorname{Cov}(X_i, X_j) ;$
if $X, Y$ are independent, $\operatorname{Cov}(X, Y) = 0$ (the converse is false), so variances of independent variables add.

Proof. 1 and 2 are expansions of squares plus linearity; the products $X_iX_j$ have expectations by Cauchy–Schwarz below (or by $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 is Theorem 22.11 applied to the centered variables. A standard counterexample to the converse: $X$ uniform on $\{-1, 0, 1\}$ and $Y = X^2$ are uncorrelated ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) but clearly dependent. ∎

Theorem 22.15 (Markov and Chebyshev inequalities)

(Markov) If $X \geq 0$ has an expectation, then for every $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Chebyshev) If $X$ has a second moment, then for every $\varepsilon > 0$ :

$\P\bigl(\abs{X - \E(X)} \geq \varepsilon\bigr) \leq \frac{V(X)}{\varepsilon^2} .$

Proof. 1. Pointwise, $a\,\mathbf{1}_{X \geq a} \leq X$ (on the event the left side is $a \leq X$ ; off it, $0 \leq X$ ). Take expectations: $a\,\P(X \geq a) \leq \E(X)$ by monotonicity and $\E(\mathbf{1}_A) = \P(A)$ . 2. Apply Markov to the nonnegative variable $(X - \E X)^2$ at level $a = \varepsilon^2$ : the event $\{(X - \E X)^2 \geq \varepsilon^2\}$ is exactly $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Example 22.16 (Uncorrelated but glued together)

Roll two fair dice, $X$ and $Y$ independent, and set $S = X + Y$ , $D = X - Y$ . By bilinearity of the covariance,

\operatorname{Cov}(S, D) = V(X) - V(Y) + \operatorname{Cov}(Y, X) - \operatorname{Cov}(X, Y) = V(X) - V(Y) = 0 :

sum and difference are uncorrelated. Independent? Certainly not: $S = 12$ forces $D = 0$ , while $\P(D = 0) = \frac16$ unconditionally. Correlation only tests the linear part of a dependence; here the dependence is carried by the constraint that $S$ and $D$ have the same parity, invisible to covariance. (For this pair, zero covariance needed $V(X) = V(Y)$ : identical distributions, not independence, did the work.)

Example 22.17 (When Markov is exact)

Markov’s inequality is an equality precisely when nothing is wasted in the bound $a\,\mathbf 1_{X\geq a} \leq X$ : the variable must take only the values $0$ and $a$ . Concretely, if $\P(X = a) = \pi$ and $\P(X = 0) = 1 - \pi$ , then $\E(X) = a\pi$ and

\P(X \geq a) = \pi = \frac{\E(X)}{a} .

A realistic reading: in a population where average wealth is $100$ and wealth is either $0$ or $10^6$ , the proportion of millionaires is exactly $10^{-4}$ — Markov’s bound, hit exactly by maximal inequality. Whenever $X$ spreads over intermediate values the bound is strict, often wildly so; but as the extreme case shows, no better inequality can be extracted from the mean alone.

Example 22.18 (Chebyshev is sharp — without further hypotheses)

Fix $\varepsilon > 0$ , $q \in \intoc01$ , and let $X$ take the values $\pm\varepsilon$ with probability $\frac q2$ each and $0$ with probability $1 - q$ . Then $\E(X) = 0$ , $V(X) = q\varepsilon^2$ , and

\P\bigl(\abs{X - \E X} \geq \varepsilon\bigr) = q = \frac{V(X)}{\varepsilon^2} :

equality in Chebyshev. So the inequality cannot be improved using only the variance — the $1/\varepsilon^2$ decay is the exact price of second-moment information. Faster decay requires stronger hypotheses: boundedness of the variable buys exponential concentration, as Exercise 22.7 previews and this chapter’s weekend problem develops systematically.

Theorem 22.19 (Cauchy–Schwarz and Jensen)

(Cauchy–Schwarz) If $X, Y$ have second moments, $XY$ has an expectation and $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; consequently $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(Jensen) If $\varphi \colon I \to \R$ is convex on an interval containing $X(\Omega)$ , and $X$ , $\varphi(X)$ have expectations, then

$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$

Proof. 1. Summability of $XY$ : $\abs{XY} \leq \frac{X^2 + Y^2}2$ . The map $(X, Y) \mapsto \E(XY)$ is a positive symmetric bilinear form on the space of variables with second moments, so the abstract Cauchy–Schwarz inequality of Chapter 12 applies (positive semi-definite suffices for the inequality). Applying it to the centered variables gives the covariance bound.

2. First, $m = \E(X)$ lies in $I$ : $I$ is an interval containing all values of $X$ , and expectation is monotone, so $m$ is between $\inf X(\Omega)$ and $\sup X(\Omega)$ . By the support-line theorem for convex functions (Chapter 8), there are $\alpha, \beta$ with $\varphi(t) \geq \alpha t + \beta$ for all $t \in I$ and $\varphi(m) = \alpha m + \beta$ . Then, pointwise on $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; taking expectations,

\E\bigl(\varphi(X)\bigr) \geq \alpha\,\E(X) + \beta = \varphi\bigl(\E(X)\bigr). \qedhere

∎

Example 22.20

Jensen with $\varphi(t) = t^2$ gives $\E(X)^2 \leq \E(X^2)$ — positivity of the variance; with $\varphi(t) = 1/t$ on $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — the harmonic mean is below the arithmetic mean, now in random form.

Remark 22.21 (Common pitfalls)

(i) $\E(XY) = \E(X)\E(Y)$ requires independence (or at least zero covariance): taking $Y = X$ gives $\E(X^2) \neq \E(X)^2$ whenever $V(X) > 0$ . (ii) Likewise $V(X + X) = 4V(X)$ , not $2V(X)$ : variances add only across independent (or uncorrelated) summands. (iii) $\E(f(X))$ is not $f(\E(X))$ ; for convex $f$ Jensen even tells you the direction of the error, as in Example 22.10. (iv) Existence is a real hypothesis: for the St Petersburg variable $X = 2^K$ with $\P(K = k) = 2^{-k}$ ( $k \geq 1$ ),

\sum_{k\geq1}2^k\cdot2^{-k} = \sum_{k\geq1}1 = \infty :

$X$ is finite almost surely yet has no expectation, and no fair entry price for the game exists. Summability in the definition of $\E$ is not bookkeeping pedantry — it is where heavy tails are detected. (v) Finally, the transfer theorem needs absolute summability before any rearrangement of the sum over values is legitimate (Chapter 7).

Example 22.22 (Chebyshev on one hundred tosses)

For $X \sim \mathcal B(100, \frac12)$ : $\E X = 50$ , $V(X) = 25$ . Chebyshev with $\varepsilon = 6$ :

\P(45 \leq X \leq 55) = \P(\abs{X - 50} < 6) \geq 1 - \frac{25}{36} \approx 0.31 ,

while the exact binomial sum gives $\approx 0.73$ . The guaranteed $31\%$ is far from the truth, but it required only the mean and variance — the same certificate applies verbatim to any variable with $\E = 50$ , $V = 25$ , however exotic, and Example 22.18 shows some such variable saturates it. Universality has a price; when the distribution is genuinely binomial, the exponential tools of the weekend problem close most of the gap.

Example 22.23 (The correlation of a part with its whole)

For independent identically distributed $X, Y$ with variance $\sigma^2 > 0$ , how correlated is one summand with the sum $S = X + Y$ ? Compute

\operatorname{Cov}(X, S) = \operatorname{Cov}(X, X) + \operatorname{Cov}(X, Y) = \sigma^2 + 0 = \sigma^2, \qquad V(S) = 2\sigma^2,

so the correlation coefficient is

\rho(X, S) = \frac{\operatorname{Cov}(X, S)}{\sigma(X)\,\sigma(S)} = \frac{\sigma^2}{\sigma\cdot\sigma\sqrt2} = \frac{1}{\sqrt2} \approx 0.707 ,

whatever the common law — dice, coins, Poisson counts. With $n$ summands the same computation gives $\rho(X_1, S_n) = 1/\sqrt n$ : each individual term’s influence on the total dilutes like a square root, which is the correlational shadow of the $\sqrt n$ scale of fluctuations. Cauchy–Schwarz guarantees $\abs\rho \leq 1$ always; here the bound is met exactly in the degenerate case $n = 1$ and decays predictably after.

Example 22.24 (Weighted AM–GM from Jensen)

Let $Y$ take the positive values $a_1, \dots, a_k$ with probabilities $\lambda_1, \dots, \lambda_k$ . The function $-\ln$ is convex on $\intoo0\infty$ , so Jensen gives $-\ln\E(Y) \leq \E(-\ln Y)$ , i.e.

a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_k^{\lambda_k} \;\leq\; \lambda_1a_1 + \lambda_2a_2 + \dots + \lambda_ka_k :

the weighted arithmetic–geometric inequality, with equality iff $Y$ is constant. Equal weights $\lambda_i = \frac1k$ recover the classical AM–GM. Probability has quietly proved a purely algebraic theorem: choosing a probability law is just a bookkeeping device for convex combinations — the barycentric viewpoint of Chapter 17 once more, now with Jensen as the engine.

22.4 The weak law of large numbers

Theorem 22.25 (Weak law of large numbers)

Let $(X_k)_{k \geq 1}$ be pairwise independent random variables with the same law, admitting a second moment; write $m = \E(X_1)$ and $S_n = X_1 + \dots + X_n$ . Then for every $\varepsilon > 0$ :

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

Proof. By linearity $\E(S_n/n) = m$ ; by Theorem 22.14 (pairwise independence kills the covariances) $V(S_n) = n\,V(X_1)$ , so $V(S_n/n) = V(X_1)/n$ . Chebyshev’s inequality applied to $S_n/n$ gives the bound. ∎

Remark 22.26

This is the theorem that connects probability to frequency: for $X_k$ the indicator of an event $A$ in independent repetitions, $S_n/n$ is the observed frequency of $A$ , and the law of large numbers says it concentrates around $\P(A)$ at rate $\frac{p(1-p)}{n\varepsilon^2}$ . The strong law ( $S_n/n \to m$ almost surely) is a Year 3 theorem — its proof for fourth moments is within reach, though: see Exercise 22.9, which runs Borel–Cantelli on the Chebyshev-type bound. The same Chebyshev estimate powered the Bernstein-polynomial proof of the Weierstrass approximation theorem in Chapter 10 — the counting lemma there was the weak law of large numbers in disguise.

Example 22.27 (Collecting fifty coupons)

The coupon collector of Exercise 22.3 with $n = 50$ distinct toys: the expected total is

\E(T_{50}) = 50\,H_{50} = 50\sum_{k=1}^{50}\frac1k \approx 50 \times 4.499 \approx 225

boxes — four and a half times the naive guess $50$ . The harmonic growth is the whole story: the first $25$ toys arrive in about $50\ln2 \approx 35$ boxes, while the last toy alone costs $50$ boxes on average (a geometric wait of parameter $\frac1{50}$ ). Completion problems are dominated by their endgame, which is why Exercise 22.12 finds fluctuations of order $n$ — the size of that final geometric wait — around the mean $n\ln n$ .

Example 22.28 (How large must $n$ be?)

To pin the observed frequency within $\varepsilon = 0.01$ of $\P(A)$ with confidence $95\%$ , Chebyshev’s bound demands

\frac{p(1-p)}{n\varepsilon^2} \leq \frac{1}{4n\varepsilon^2} \leq 0.05, \qquad\text{i.e.}\qquad n \geq \frac{1}{4\cdot0.05\cdot(0.01)^2} = 50\,000 .

The dependence is brutal in $\varepsilon$ (quadratic) and mild in the confidence (linear in $1/\alpha$ ). Both features are properties of the bound, not of the truth: the weekend problem’s exponential inequalities lower the price of confidence from $1/\alpha$ to $\ln(1/\alpha)$ — the same specification will cost about $18\,500$ samples there — while the $1/\varepsilon^2$ scale is genuine and unimprovable. Knowing which part of a bound is loose is as useful as the bound itself.

The law of large numbers as a picture: the law of S_n/n (schematically drawn) keeps its center m but narrows as n grows, so the probability outside the band [m- , m+ ] — the two tails — shrinks to zero. Chebyshev bounds the tails by V(X_1)/(n 2); the weekend problem shows they are in fact exponentially small. — The law of large numbers as a picture: the law of $S_n/n$ (schematically drawn) keeps its center $m$ but narrows as $n$ grows, so the probability outside the band $\intcc{m-\varepsilon}{m+\varepsilon}$ — the two tails — shrinks to zero. Chebyshev bounds the tails by $V(X_1)/(n\varepsilon^2)$ ; the weekend problem shows they are in fact exponentially small.

Remark 22.29 (Perspectives within this volume)

Forward, everything here feeds Chapter 23: the expectation $\E(t^X)$ of one cunning function of $X$ packs the whole law into a power series, moments become derivatives at $1$ , and Wald-type identities for random sums carry the branching-process theory; the product theorem for independent variables becomes multiplicativity of generating functions. Backward, expectation is a barycenter with probability weights (Chapter 17), Jensen’s inequality is the support-line geometry of convex functions (Chapter 8), and the exponential-moment method of this chapter’s weekend problem is Markov applied to $\eu^{tX}$ — one inequality, upgraded by one good change of variable, spanning three chapters.

22.5 Exercises

Exercise 22.1 ★

Compute $\E(X)$ and $V(X)$ for $X \sim \mathcal{B}(n, p)$ (via indicators), $X \sim \mathcal{P}(\lambda)$ (show $V(X) = \lambda$ ), and $X \sim \mathcal{G}(p)$ (show $V(X) = \frac{1-p}{p^2}$ ; use $\E(X(X-1))$ and the second derivative of the geometric series).

Solution

Solution of Exercise 22.1.

Binomial: $X = \sum_{i=1}^n X_i$ with independent Bernoulli $X_i$ ; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , and variances of independent variables add (Theorem 22.14):

\E(X) = np, \qquad V(X) = np(1-p) .

Poisson: $\E\bigl(X(X-1)\bigr) = \sum_{k\geq2}k(k-1)e^{-\lambda}\frac{\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda^2$ , so

V(X) = \E(X^2) - \E(X)^2 = \lambda^2 + \lambda - \lambda^2 = \lambda .

Geometric ( $q = 1 - p$ ): differentiating $\sum_{k\geq0}q^k = \frac{1}{1-q}$ twice inside the disk (Chapter 11), $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ , so

\E\bigl(X(X-1)\bigr) = pq\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2q}{p^2}, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{q}{p^2} = \frac{1-p}{p^2} .

Exercise 22.2 ★

Let $X \sim \mathcal{P}(\lambda)$ and $Y \sim \mathcal{P}(\mu)$ be independent. Show that $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolution of the weights; binomial theorem), and that the conditional law of $X$ given $X + Y = n$ is binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

Solution

Solution of Exercise 22.2.

Sum: for $n \in \N$ , by disjointness and independence,

\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k) = e^{-(\lambda + \mu)}\frac{1}{n!} \sum_{k=0}^n \binom nk \lambda^k\mu^{n-k} = e^{-(\lambda+\mu)}\frac{(\lambda + \mu)^n}{n!}

by the binomial theorem: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Conditional law: for $0 \leq k \leq n$ ,

\P(X = k \mid X + Y = n) = \frac{\P(X = k)\P(Y = n - k)}{\P(X + Y = n)} = \binom nk \Bigl(\frac{\lambda}{\lambda+\mu}\Bigr)^{k} \Bigl(\frac{\mu}{\lambda+\mu}\Bigr)^{n-k} ,

the binomial law $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : given the total count, each event independently “chooses” the first source with probability proportional to its rate.

Exercise 22.3 ★

(Coupon collector, expectation) A cereal brand hides one of $n$ distinct toys, uniformly, in each box. Let $T_n$ be the number of boxes needed to collect all $n$ toys. Writing $T_n$ as a sum of independent geometric variables (time to see a new toy when $k$ are still missing), show

\E(T_n) = n\sum_{k=1}^{n}\frac{1}{k} \sim n\ln n

(equivalent by the series–integral comparison of Chapter 6).

Solution

Solution of Exercise 22.3.

When $k$ toys are still missing, each new box brings a new toy with probability $\frac kn$ , independently of the past: the waiting time $W_k$ for the next new toy is geometric $\mathcal{G}\bigl(\frac kn\bigr)$ , with $\E(W_k) = \frac nk$ , and $T_n = W_n + W_{n-1} + \dots + W_1$ (first box always gives a new toy: $W_n = 1$ , consistent with $\E = n/n$ ). By linearity,

\E(T_n) = \sum_{k=1}^n \frac nk = n\sum_{k=1}^n\frac1k \sim n\ln n ,

using $\sum_{k\leq n}\frac1k = \ln n + \gamma + o(1)$ (Chapter 6). Collecting the last few toys is what costs: half the boxes go to the final handful.

Exercise 22.4 ★★

Let $X \geq 0$ be integer-valued. Prove the tail formula

\E(X) = \sum_{n=1}^{\infty} \P(X \geq n)

(when either side is finite), by writing $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ and exchanging summations (Fubini for nonnegative families). Recover $\E(X) = \frac1p$ for the geometric law.

Solution

Solution of Exercise 22.4.

Pointwise, $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . The double family $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ is nonnegative, so Fubini for families (Chapter 7) applies unconditionally: summing first in $n$ gives $\E(X)$ , summing first in $\omega$ gives $\sum_n \P(X \geq n)$ ; the two are simultaneously finite and equal. For $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), so $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Exercise 22.5 ★★

(Sampling without replacement is more concentrated) An urn has $N$ balls, $M$ of them white. Draw $n \leq N$ without replacement and let $X$ count the whites (hypergeometric law). Using indicators $X = \sum_{i=1}^n Y_i$ with $Y_i$ the $i$ -th draw: show each $Y_i$ is Bernoulli of parameter $p = M/N$ (symmetry!), conclude $\E(X) = np$ exactly as with replacement, and show $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ for $i \neq j$ , hence $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

Solution

Solution of Exercise 22.5.

Symmetry: the $i$ -th ball drawn is a uniformly random ball of the urn (any of the $N$ balls is equally likely to land in position $i$ of the drawing order), so $\P(Y_i = 1) = \frac MN = p$ and $\E(X) = np$ by linearity — no independence needed.

Covariance: for $i \neq j$ , $\E(Y_iY_j) = \P(\text{draws } i, j \text{ both white}) = \frac{M(M-1)}{N(N-1)}$ (ordered pairs of distinct positions get an ordered pair of distinct balls, uniformly). Hence

\operatorname{Cov}(Y_i, Y_j) = \frac{M(M-1)}{N(N-1)} - \frac{M^2}{N^2} = \frac{M(N - M)}{N^2}\cdot\frac{-1}{N-1} = -\frac{p(1-p)}{N-1} < 0 :

drawing a white ball makes whites scarcer for the other draws. By Theorem 22.14,

V(X) = np(1-p) + n(n-1)\Bigl(-\frac{p(1-p)}{N-1}\Bigr) = np(1-p)\,\frac{N - n}{N - 1} \leq np(1-p) :

sampling without replacement has the same mean but smaller variance than with replacement (equality only for $n = 1$ ), the negative correlations acting as a stabilizer. For $n = N$ the variance vanishes: the count is then deterministic.

Exercise 22.6 ★★

Let $X$ have a second moment. Show that $c \mapsto \E\bigl((X - c)^2\bigr)$ is minimal exactly at $c = \E(X)$ , with minimum $V(X)$ . Then show that $\P(X = \E(X)) = 1$ if and only if $V(X) = 0$ . (For the second point: if $V(X) = 0$ , use Chebyshev with $\varepsilon = 1/n$ and monotone continuity, Theorem 21.6.)

Solution

Solution of Exercise 22.6.

Expanding around $m = \E(X)$ :

\E\bigl((X - c)^2\bigr) = \E\bigl((X - m)^2\bigr) + 2(m - c)\,\E(X - m) + (m - c)^2 = V(X) + (m - c)^2 ,

minimal exactly at $c = m$ with value $V(X)$ — expectation is the best constant predictor in mean square.

If $\P(X = m) = 1$ then $(X - m)^2$ vanishes with probability $1$ , so $V(X) = 0$ (the defining family has null terms except on a null set). Conversely, if $V(X) = 0$ , Chebyshev (Theorem 22.15) gives $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ for every $n$ ; the events $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ increase to $\{X \neq m\}$ , so monotone continuity (Theorem 21.6) yields $\P(X \neq m) = 0$ .

Exercise 22.7 ★★★

(Concentration beats Markov) Let $S_n \sim \mathcal{B}(n, \frac12)$ (number of heads in $n$ fair tosses). Compare the bounds given by Markov ( $\P(S_n \geq \frac{3n}{4})$ ), by Chebyshev, and by the exponential (Chernoff) method:

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \E\bigl(e^{tS_n}\bigr)e^{-3nt/4} = \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} \quad (t > 0),

and optimize $t$ to obtain an exponentially small bound. (At $t = \ln 3$ : bound $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

Solution

Solution of Exercise 22.7.

$\E(S_n) = \frac n2$ and $V(S_n) = \frac n4$ . Markov: $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — a constant bound, useless for large $n$ . Chebyshev: the event implies $\abs{S_n - \frac n2} \geq \frac n4$ , so the probability is $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — decays, but only polynomially. Chernoff: by independence, $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ , and Markov applied to $e^{tS_n} \geq e^{3nt/4}$ gives, for every $t > 0$ ,

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} = \exp\Bigl(n\bigl(\ln\tfrac{1 + e^t}{2} - \tfrac{3t}4\bigr)\Bigr).

Minimize the exponent: $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ at $e^t = 3$ , i.e. $t = \ln 3$ , giving

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{4}{2}\Bigr)^n 3^{-3n/4} = \bigl(2 \cdot 3^{-3/4}\bigr)^n \approx (0.877)^n ,

exponentially small. The hierarchy Markov $\to$ Chebyshev $\to$ Chernoff is the standard ladder: each rung applies Markov to a faster-growing function of the variable.

Exercise 22.8 ★★★

(Weierstrass again, probabilistically) Let $f \colon [0,1] \to \R$ be continuous and $S_n \sim \mathcal{B}(n, x)$ . Show that the Bernstein polynomial $B_nf(x) = \sum_{k=0}^n f\bigl(\frac kn\bigr)\binom nk x^k(1-x)^{n-k}$ equals $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ , and re-derive the estimate $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ of Chapter 10 in this probabilistic language (split on $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ and use Chebyshev).

Solution

Solution of Exercise 22.8.

By the transfer theorem (Theorem 22.7) applied to $f\bigl(\frac{S_n}{n}\bigr)$ with $S_n \sim \mathcal{B}(n, x)$ :

\E\Bigl[f\Bigl(\frac{S_n}{n}\Bigr)\Bigr] = \sum_{k=0}^n f\Bigl(\frac kn\Bigr)\binom nk x^k(1-x)^{n-k} = B_nf(x) .

Fix $\delta > 0$ and split $\abs{f(S_n/n) - f(x)}$ on the event $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : off $D$ , the difference is at most the modulus of continuity $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; on $D$ , at most $2\norm f_\infty$ . Taking expectations and using Chebyshev with $V\bigl(\frac{S_n}{n}\bigr) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$ :

\abs{B_nf(x) - f(x)} \leq \E\,\abs{f(S_n/n) - f(x)} \leq \omega_f(\delta) + 2\norm f_\infty\,\P(D) \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2} .

Uniform continuity of $f$ on $[0, 1]$ makes $\omega_f(\delta) \to 0$ : choose $\delta$ then $n$ , and $B_nf \to f$ uniformly — the Weierstrass approximation theorem of Chapter 10, whose “counting lemma” is now recognizable as Chebyshev’s inequality for the binomial law.

Exercise 22.9 ★★★

(Strong law under fourth moments) Let $(X_k)$ be independent, identically distributed, centered ( $\E X_1 = 0$ ), with $\E(X_1^4) < \infty$ . Expanding $\E(S_n^4)$ and counting the surviving terms (only $\E(X_i^4)$ and $\E(X_i^2X_j^2)$ terms, $i \neq j$ ), show $\E(S_n^4) \leq C n^2$ for a constant $C$ . Deduce $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ for each $\varepsilon > 0$ (Markov at order 4) and conclude with Borel–Cantelli (Theorem 21.25) that $S_n/n \to 0$ almost surely along a suitable formulation: the event $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ has probability $1$ .

Solution

Solution of Exercise 22.9.

Expand $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ and take expectations. By independence and centering, any term containing an index appearing exactly once vanishes ( $\E(X_i) = 0$ factors out). Surviving terms: the $n$ diagonal terms $\E(X_i^4)$ , and the terms pairing two pairs of equal indices, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ for $i \neq j$ , appearing $3n(n-1)$ times: choose the unordered pair of values ( $\binom n2$ ways), then the $\frac{4!}{2!\,2!} = 6$ ways to place them in the four slots — $6\binom n2 = 3n(n-1)$ . Hence, with $\E(X_1^2)^2 \leq \E(X_1^4)$ (Jensen or Cauchy–Schwarz),

\E(S_n^4) = n\,\E(X_1^4) + 3n(n-1)\,\E(X_1^2)^2 \leq C n^2, \qquad C = 4\,\E(X_1^4) .

Markov at order 4:

\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}{n^2\varepsilon^4} ,

a summable series. By Borel–Cantelli 1 (Theorem 21.25), for each $j$ the event $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ has probability $0$ , so $\P\bigl(\bigcup_j B_j\bigr) = 0$ by countable subadditivity. On the complement — of probability $1$ — for every $j$ there is $N$ with $\abs{S_n/n} < \frac1j$ for all $n \geq N$ : precisely $S_n/n \to 0$ . The strong law of large numbers holds under a fourth moment; removing that hypothesis (Kolmogorov’s theorem) is Year 3 work.

Exercise 22.10 ★

Two fair dice are thrown; let $M$ be the larger of the two results. Using the tail formula of Exercise 22.4 (finite version), show

\E(M) = \sum_{k=1}^{6}\P(M \geq k) = 6 - \sum_{j=0}^5\Bigl(\frac j6\Bigr)^2 = \frac{161}{36} \approx 4.47 .

Solution

Solution of Exercise 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (both dice at most $k$ , independently), so $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ and

\E(M) = \sum_{k=1}^6\P(M \geq k) = 6 - \frac{0 + 1 + 4 + 9 + 16 + 25}{36} = 6 - \frac{55}{36} = \frac{161}{36} \approx 4.47 ,

comfortably above the mean $3.5$ of a single die, as a maximum should be.

Exercise 22.11 ★★

Let $F_n$ be the number of fixed points of a uniformly random permutation of $\{1, \dots, n\}$ ( $n \geq 2$ ). Writing $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ , compute $\E(F_n) = 1$ , $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ for $i \neq j$ , and conclude $V(F_n) = 1$ : on average one letter is fixed, with variance exactly $1$ , whatever $n$ .

Solution

Solution of Exercise 22.11.

With $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ , so $\E(F_n) = n\cdot\frac1n = 1$ . For $i \neq j$ : $\P(\sigma(i) = i, \sigma(j) = j) = \frac{(n-2)!}{n!} = \frac1{n(n-1)}$ , hence

\operatorname{Cov}(I_i, I_j) = \frac1{n(n-1)} - \frac1{n^2} = \frac{1}{n^2(n-1)} .

By the variance toolkit (Theorem 22.14),

V(F_n) = n\cdot\frac1n\Bigl(1 - \frac1n\Bigr) + n(n-1)\cdot\frac1{n^2(n-1)} = 1 - \frac1n + \frac1n = 1 .

Mean $1$ , variance $1$ , independent of $n$ — consistent with the Poisson limit of the matching problem (Exercise 21.5).

Exercise 22.12 ★★★

(Coupon collector, concentration) In the setting of Exercise 22.3, show

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq n^2\sum_{k=1}^n\frac{1}{k^2} \leq \frac{\pi^2}{6}n^2,

using independence of the geometric stages and $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (Exercise 22.1; the value $\pi^2/6$ is Example 14.12). Deduce with Chebyshev that $\dfrac{T_n}{n\ln n} \to 1$ in probability: the collector’s total time is $n\ln n$ up to fluctuations of order $n$ .

Solution

Solution of Exercise 22.12.

$T_n = \sum_{k=1}^nG_k$ where $G_k \sim \mathcal G(k/n)$ is the time to see a new toy when $k$ are missing, the stages being independent. Hence

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq \sum_{k=1}^n\frac{n^2}{k^2} \leq \frac{\pi^2}6\,n^2 ,

by Example 14.12. With $\E(T_n) = nH_n$ , $H_n = \sum_1^n\frac1k$ (Exercise 22.3), Chebyshev gives, for $\varepsilon > 0$ ,

\P\bigl(\abs{T_n - nH_n} \geq \varepsilon\,n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2 n} = \frac{\pi^2}{6\,\varepsilon^2\ln^2n} \xrightarrow[n\to\infty]{} 0 .

Since $H_n \sim \ln n$ , dividing by $n\ln n$ shows $T_n/(n\ln n) \to 1$ in probability: the fluctuations of $T_n$ are of order $n$ , negligible against the mean $n\ln n$ .

22.6 Problem: the concentration toolbox, from Markov to Hoeffding

Problem 22.1

Weekend problem — exponential concentration by hand, and how many people a poll must ask

Markov’s inequality costs one moment and buys a $1/a$ decay; Chebyshev costs two moments and buys $1/\varepsilon^2$ — and Example 22.18 shows that is all those moments can buy. This problem climbs the rest of the ladder: the exponential (Chernoff) method with its exact rate for coin flips, Hoeffding’s inequality for all bounded variables, and the payoff — explicit, honest sample sizes for polls, election calls and coin testing. Throughout, $S_n \sim \mathcal B(n, p)$ is a sum of $n$ independent Bernoulli variables and $\widehat p_n = S_n/n$ the empirical frequency.

Part I — Calibration on the fair coin. Here $p = \frac12$ and $a \in \intoo{\frac12}{1}$ .

Markov at level $an$ : show $\P(S_n \geq an) \leq \frac1{2a}$ , a bound that does not even tend to $0$ . Where does Markov lose so much?
Chebyshev: using the symmetry of the fair binomial about $n/2$ , show

$\P(S_n \geq an) = \tfrac12\, \P\bigl(\abs{S_n - \tfrac n2} \geq n(a - \tfrac12)\bigr) \leq \frac{1}{8n(a - 1/2)^2},$

i.e. $\frac2n$ at $a = \frac34$ : polynomial decay at last.
(Chernoff, general level) Compute $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ and optimize $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ over $t > 0$ : show the optimal $t$ is $\ln\frac{a}{1-a}$ and

$\P(S_n \geq an) \leq \eu^{-n\,I(a)}, \qquad I(a) = \ln 2 + a\ln a + (1-a)\ln(1-a) > 0 .$

Check that $a = \frac34$ recovers the bound $\bigl(2\cdot3^{-3/4}\bigr)^n$ of Exercise 22.7.
(The exponent is exact) Let $k = an$ be an integer. From the fact that $\binom nk a^k(1-a)^{n-k}$ is the largest of the $n + 1$ terms of a probability distribution, prove $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ with $H(a) = -a\ln a - (1-a)\ln(1-a)$ , and deduce the matching lower bound

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Tabulate the three bounds at $n = 100$ , $a = \frac34$ : Markov $\frac23$ , Chebyshev $0.02$ , Chernoff $\approx 2.1\cdot10^{-6}$ (the true value is $\approx 2.8\cdot10^{-7}$ ). Moral, in one sentence?

Part II — Hoeffding’s inequality.

(Rademacher case) For $\varepsilon = \pm1$ with probability $\frac12$ each, prove

$\E(\eu^{t\varepsilon}) = \cosh t \leq \eu^{t^2/2} \qquad (t \in \R)$

by comparing the two series term by term ( $(2k)! \geq 2^kk!$ ).
Deduce, for independent Rademacher variables $\varepsilon_1, \dots, \varepsilon_n$ and every $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Translate to fair coins ( $X_i = \frac{1+\varepsilon_i}2$ ): $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ , and the two-sided version with a factor $2$ .
(Hoeffding’s lemma) Let $X \in \intcc01$ with $\E X = p$ , and $\psi(t) = \ln\E(\eu^{tX})$ . Justify that $\psi$ is twice differentiable with

$\psi''(t) = \E_t(X^2) - \E_t(X)^2, \qquad \E_t(Y) := \frac{\E(Y\eu^{tX})}{\E(\eu^{tX})},$

a variance of a reweighted variable still taking values in $\intcc01$ ; bound it by $\frac14$ (Exercise 22.6’s minimality argument) and conclude by Taylor:

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(Hoeffding’s inequality) For independent $X_i \in \intcc01$ with common mean $p$ , deduce

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Compare the Chebyshev rate $\frac{p(1-p)}{n\delta^2}$ with Hoeffding’s $2\eu^{-2n\delta^2}$ : which hypothesis does each require, and from which $n$ (roughly) does the exponential bound win at $\delta = 0.03$ , $p = \frac12$ ?

Part III — How many people must a poll ask? A poll asks $n$ independent, uniformly chosen voters; each answers honestly; $p$ is the true score, $\widehat p_n$ the poll’s figure.

Show that the poll is accurate to $\pm\delta$ with confidence $1 - \alpha$ (i.e. $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) as soon as

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Compute the required $n$ for the standard “three points, ninety-five percent” specification ( $\delta = 0.03$ , $\alpha = 0.05$ ): $n \geq 2050$ ; and for one point: $n \geq 18\,445$ . Observe — and explain — the striking fact that the answer does not involve the population size.
Redo question 13 with Chebyshev ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ at three points. Note that sampling without replacement only helps (Exercise 22.5: the variance shrinks by $\frac{N-n}{N-1}$ ).
(Calling an election) A candidate’s true score is $p = 0.52$ . How many voters must be polled so that $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Show $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — calling a close race costs far more than estimating a score.
What the mathematics does not cover: list the modelling assumptions used (independent uniform sampling, honest answers, fixed $p$ ), and explain in a short paragraph why real polling errors are dominated by bias (non-uniform sampling, non-response), which no increase of $n$ reduces.

Part IV — Sharper and cheaper.

(Median of means: exponential decay from two moments) Split a budget of $km$ samples into $k$ independent groups of $m$ ; let $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ be the group means and $M$ their median. Choose $m$ so that each group satisfies $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (Chebyshev: $m \geq \frac2{\delta^2}$ suffices). Show that if $\abs{M - p} \geq \delta$ then at least $k/2$ groups err, and deduce

$\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil}\Bigl(\frac18 \Bigr)^{k/2} \leq 2^k\cdot 8^{-k/2} = 2^{-k/2} :$

exponential concentration using nothing beyond variances.
(Paley–Zygmund) For $X \geq 0$ with a second moment, prove $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz on $X\mathbf 1_{X>0}$ ): the reverse-direction tool — moments can also force events to happen.
(Pinsker-lite) Show $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ on $\intoo{\frac12}1$ (the difference vanishes to second order at $\frac12$ and its second derivative is $\frac1{a(1-a)} - 4 \geq 0$ ): Chernoff’s exact exponent always beats Hoeffding’s quadratic one.
Expand $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ and combine with question 4: for small deviations the Hoeffding exponent $2n\delta^2$ is asymptotically exact — no method can beat it by more than polynomial factors.
Draw up the toolbox table: for Markov, Chebyshev, the fourth-moment bound of Exercise 22.9, Hoeffding, and Chernoff with exponent $I$ , state in one line each: hypothesis required, decay obtained, and the question in this problem where it was sharpest.

Part V — Dividends.

(Testing a coin) A coin is either fair or biased with $p = 0.55$ . You flip it $n$ times and declare “biased” when $\widehat p_n > 0.525$ . Show that both error probabilities are at most $\eu^{-2n(0.025)^2}$ , and that $n \geq 3685$ flips guarantee both below $1\%$ .
(Rare events need a variance-aware bound) Let $p = 0.01$ and take the relative specification $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . Compare the sample sizes demanded by Hoeffding ( $n \approx 74\,000$ ) and by Chebyshev with the true variance $p(1-p)$ ( $n \approx 7920$ ): the variance-blind exponential bound loses to the humble second moment. State the moral, and where the missing tool (a variance-aware exponential bound; the Poisson approximation of Chapter 23) will come from.
(Strong law for coins) From $\sum_n 2\eu^{-2n\delta^2} < \infty$ and Borel–Cantelli (Theorem 21.25), prove that $\widehat p_n \to p$ almost surely for independent coin flips: formulate the almost-sure event as $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ as in Exercise 22.9, and conclude. (Boundedness replaces the fourth moment used there.)
Synthesis. In five sentences: what each rung of the ladder (moments one, two, four; bounded exponential; exact exponent) costs and buys; why polling $2050$ people suffices for a country of any size; and which of these bounds the Year 3 volume will sharpen into the central limit theorem’s exact constants.

Solution

Solution of Problem 22.1.

1. $\E(S_n) = \frac n2$ and Markov (Theorem 22.15) give $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov only knows the mean: it cannot distinguish a variable concentrated at $n/2$ from one spread between $0$ and $n$ , so it prices the tail as if all the mass could sit there.

2. The fair binomial is symmetric about $n/2$ ( $S_n$ and $n - S_n$ have the same law), so with $x = n(a - \frac12) > 0$ the two events $\{S_n - \frac n2 \geq x\}$ and $\{S_n - \frac n2 \leq -x\}$ are disjoint and equiprobable: $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . Chebyshev with $V(S_n) = \frac n4$ :

\P(S_n \geq an) \leq \frac12\cdot\frac{n/4}{n^2(a - 1/2)^2} = \frac1{8n(a - 1/2)^2},

which is $\frac2n$ at $a = \frac34$ .

3. By independence and the product theorem, $\E(\eu^{tS_n}) = \bigl(\E \eu^{tX_1}\bigr)^n = \bigl(\frac{1 + \eu^t}2\bigr)^n$ . Markov applied to $\eu^{tS_n}$ :

\P(S_n \geq an) \leq \eu^{-tan}\Bigl(\frac{1 + \eu^t}2\Bigr)^{\!n} = \exp\Bigl(n\bigl(\ln\tfrac{1 + \eu^t}2 - ta\bigr)\Bigr).

The exponent’s derivative in $t$ is $\frac{\eu^t}{1 + \eu^t} - a$ , vanishing at $\eu^t = \frac a{1-a}$ , i.e. $t^* = \ln\frac a{1-a} > 0$ ; there $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ and the exponent equals

n\Bigl(-\ln 2 - \ln(1-a) - a\ln\frac a{1-a}\Bigr) = -n\bigl(\ln2 + a\ln a + (1-a)\ln(1-a)\bigr) = -n\,I(a),

with $I(\frac12) = 0$ and $I'(a) = \ln\frac a{1-a} > 0$ on $\intoo{\frac12}1$ : $I(a) > 0$ . At $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , the bound of Exercise 22.7.

4. The $n + 1$ numbers $\binom nja^j(1-a)^{n-j}$ sum to $1$ , and the largest is the one at $j = k = an$ (the mode of $\mathcal B(n, a)$ is $\floor{(n+1)a} = k$ here). A maximum of $n + 1$ numbers summing to $1$ is at least $\frac1{n+1}$ :

\binom nk a^k(1-a)^{n-k} \geq \frac1{n+1} \quad\Longrightarrow\quad \binom nk \geq \frac{a^{-an}(1-a)^{-n(1-a)}}{n+1} = \frac{\eu^{nH(a)}}{n+1}.

Hence $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : up to the polynomial factor $n + 1$ , Chernoff’s exponent is the truth.

5. $n = 100$ , $a = \frac34$ : Markov $\frac23$ ; Chebyshev $\frac2{100} = 0.02$ ; Chernoff $(2\cdot3^{-3/4})^{100} = \eu^{-100\,I(3/4)} \approx 2.1\cdot10^{-6}$ , against the exact $2.8\cdot10^{-7}$ . Moral: each moment of information divides the bound polynomially; the exponential moment changes its nature.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ and $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ; the claim follows term by term from $(2k)! \geq 2^kk!$ , which holds by induction: $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. By independence, $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , so Markov gives $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; minimizing at $t = s/n$ yields $\eu^{-s^2/(2n)}$ .

8. With $X_i = \frac{1 + \varepsilon_i}2$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , so $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ and question 7 gives the bound $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . The symmetric event has the same bound, whence the factor $2$ for $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ is a series of smooth functions of $t$ whose term-by-term derivatives are dominated, on every compact $t$ -interval, by $\eu^{\abs t}\P(X = x)$ (as $0 \leq x \leq 1$ ): by the differentiation theorem for normally convergent series (Theorem 10.7) it is twice differentiable, and the quotient rule gives $\psi' = \E_t(X)$ and $\psi'' = \E_t(X^2) - \E_t(X)^2$ , where $\E_t$ is the expectation for the reweighted weights $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — nonnegative, summing to $1$ , carried by the same values $x \in \intcc01$ . A variance of a $\intcc01$ -valued variable is at most $\frac14$ : by Exercise 22.6, it is $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . Taylor with integral remainder, using $\psi(0) = 0$ , $\psi'(0) = p$ :

\psi(t) = tp + \int_0^t(t - s)\,\psi''(s)\,\dd s \leq tp + \frac{t^2}2\cdot\frac14,

i.e. $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ for all real $t$ .

10. By independence, $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ; Markov and the optimization $t = 4\delta$ give

\P(\widehat p_n - p \geq \delta) \leq \eu^{nt^2/8 - tn\delta}\Big|_{t = 4\delta} = \eu^{-2n\delta^2};

applying this to the variables $1 - X_i$ (also in $\intcc01$ ) bounds the other tail, whence the two-sided $2\eu^{-2n\delta^2}$ .

11. Chebyshev needs only a second moment and gives $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding needs boundedness and gives $2\eu^{-2n\delta^2}$ . At $p = \frac12$ , $\delta = 0.03$ : the bounds are $\frac{278}{n}$ (approximately) versus $2\eu^{-0.0018n}$ ; they cross near $n \approx 1200$ , after which the exponential bound wins, and wildly so ( $n = 5000$ : $0.056$ versus $2.5\cdot10^{-4}$ ).

12. By Hoeffding (question 10), $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ as soon as $2n\delta^2 \geq \ln\frac2\alpha$ , i.e. $n \geq \frac{\ln(2/\alpha)}{2\delta^2}$ .

13. $\delta = 0.03$ , $\alpha = 0.05$ : $n \geq \frac{\ln 40}{2\cdot0.0009} \approx 2049.4$ : $2050$ people. For $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . The population size never appears because each sampled voter is modelled as a fresh Bernoulli $(p)$ draw: the poll’s difficulty is the variance of a coin, not the size of the country. Halving the margin costs four times the sample — the $1/\delta^2$ law.

14. Chebyshev: $\P(\abs{\widehat p_n - p} \geq \delta) \leq \frac{p(1-p)}{n\delta^2} \leq \frac1{4n\delta^2} \leq \alpha$ for $n \geq \frac1{4\alpha\delta^2}$ , i.e. $5556$ at three points — about $2.7$ times the Hoeffding requirement. Without replacement, the variance is multiplied by $\frac{N - n}{N-1} < 1$ (Exercise 22.5), so the same $n$ can only do better: the with-replacement computation is the conservative one.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , so by the one-sided Hoeffding bound $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ as soon as $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ voters. The cost scales like the inverse square of the lead, not of the desired precision: close races are expensive.

16. Used: the sample is drawn uniformly and independently from the electorate; every sampled person answers, honestly, and $p$ does not move during polling. Real polls violate all three: reachable and willing respondents are not a uniform sample (selection and non-response bias), and answers can be untruthful or unstable. These are bias errors: they shift $\E(\widehat p_n)$ away from $p$ by an amount independent of $n$ , so no sample size reduces them — the mathematics of this Part controls only the fluctuation term.

17. Chebyshev for one group of size $m$ : $\P(\abs{ \widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ for $m \geq \frac2{\delta^2}$ . If fewer than $k/2$ groups err, then more than $k/2$ of the values $\widehat p^{(i)}$ lie in the open interval $\intoo{p - \delta}{p + \delta}$ , and so does their median; hence $\{\abs{M - p} \geq \delta\}$ forces at least $\lceil k/2\rceil$ errors among $k$ independent groups. The union bound over the $\binom k{\lceil k/2\rceil}$ possible sets of erring groups gives

\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil} \Bigl(\frac18\Bigr)^{k/2} \leq 2^k\,8^{-k/2} = 2^{-k/2} :

exponential decay in the number of groups, bought with nothing but variances — useful precisely when the summands are unbounded and Hoeffding is unavailable.

18. Cauchy–Schwarz (Theorem 22.19):

\E(X) = \E(X\,\mathbf 1_{X>0}) \leq \sqrt{\E(X^2)}\sqrt{\E(\mathbf 1_{X>0}^2)} = \sqrt{\E(X^2)\,\P(X > 0)} ;

square and divide.

19. Let $h(a) = I(a) - 2(a - \tfrac12)^2$ . Then $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ vanishes at $\tfrac12$ , and

h''(a) = \frac1a + \frac1{1-a} - 4 = \frac{1}{a(1-a)} - 4 \geq 0

since $a(1-a) \leq \frac14$ . So $h'$ increases from $0$ on $\intco{\frac12}1$ , hence $h' \geq 0$ and $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ , $I''(a) = \frac1{a(1-a)}$ gives $I''(\tfrac12) = 4$ , and $I'''(\tfrac12) = 0$ (the function is symmetric about $\tfrac12$ ), so $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . Question 4 then bounds the true tail below by $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : for small $\delta$ the Hoeffding exponent $2n\delta^2$ is asymptotically exact — only polynomial-in- $n$ improvements are possible.

21. Markov: one moment, decay $1/a$ , useful only as the engine behind the others (question 1 shows it flat). Chebyshev: two moments, decay $\frac{V}{n\delta^2}$ , sharp without further hypotheses (Example 22.18), and the best tool at question 23. Fourth moment (Exercise 22.9): decay $C/n^2$ , just enough summability for a strong law. Hoeffding: bounded variables, decay $2\eu^{-2n\delta^2}$ , the workhorse of Part III. Chernoff with the exact rate $I(a)$ : full exponential moments, unbeatable exponent (questions 4, 20), the reference point for everything else.

22. If the coin is fair: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . If $p = 0.55$ : $\P(\widehat p_n \leq 0.525) \leq \P(\widehat p_n - 0.55 \leq -0.025) \leq \eu^{-2n(0.025)^2}$ . Both errors are below $0.01$ when $2n(0.025)^2 \geq \ln 100$ , i.e. $n \geq 3684.2$ : $3685$ flips. (Distinguishing hypotheses $2.5$ points apart costs what estimating to $\pm2.5$ points costs.)

23. Hoeffding: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Chebyshev with the true variance $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — nine times cheaper. Hoeffding’s exponent $2n\delta^2$ prices the variance at its worst case $\frac14$ , absurdly pessimistic when $p = 0.01$ ; the humble second moment knows better. The missing tool is a variance-aware exponential bound (Bernstein’s inequality, Year 3) — or, for rare events, the Poisson approximation proved in Chapter 23, which works on the natural relative scale.

24. Fix $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (geometric-type series), so Borel–Cantelli 1 (Theorem 21.25) gives $\P(\abs{\widehat p_n - p} \geq \delta \text{ infinitely often}) = 0$ , i.e. the event $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ has probability $1$ for each $j$ . The countable intersection $\bigcap_jE_j$ still has probability $1$ (subadditivity on the complements), and on it $\widehat p_n \to p$ : the strong law of large numbers for coin flips, with boundedness playing the role that the fourth moment played in Exercise 22.9.

25. One moment buys a flat bound; two buy $1/(n\delta^2)$ , and no more (the sharpness example); four buy $1/n^2$ , enough to telescope into an almost-sure law; boundedness buys $\eu^{-2n\delta^2}$ ; and the full exponential moment buys the exact rate $I$ , which no method beats. Polling $2050$ people suffices for any country because the sample’s fluctuation is governed by the coin’s variance, not the population’s size — the $1/\delta^2$ and $\ln(1/\alpha)$ price tags are universal. The Year 3 volume’s central limit theorem replaces these inequalities, on the $\sqrt n$ scale, by an exact limit law with explicit constants — turning every bound of this problem into an asymptotic equality.