---
title: "Discrete Random Variables"
book: "University Mathematics — Year 2"
subject: math
language: en
chapter: 22
exercises: 12
source: https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables
---

# Chapter 22 — Discrete Random Variables

[Random variables](#def-b2-randomvar-law) organize probability computations around functions rather than [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space). On [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) spaces the theory is powered by the [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) families of [Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series): [expectation](#def-b2-randomvar-expectation) is the sum of a family indexed by the [sample space](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space), and all its properties — linearity, transfer, product formula for [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) variables — are theorems about [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) families. The chapter proves the key inequalities of Markov, Chebyshev, Cauchy–Schwarz and Jensen, and ends with the classical [laws](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) [probability space](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\P_X$ on the [countable set](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) $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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) .
- *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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) Bernoulli trials (High School volume; re-proved below via sums of [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) variables).
- *Geometric* $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : rank of the first success ( [Example 21.5](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#ex-b2-proba-geometric) ).
- *Poisson* $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — a [probability measure](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) by the exponential series. The law of rare events ( [Chapter 23](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun) ).

**Remark 22.3 (Which law models what).**

The four [laws](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) counts to the Poisson — with the passage from binomial to Poisson made precise by the law of rare events in [Chapter 23](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun).

**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](#def-b2-randomvar-law) are the only [laws](#def-b2-randomvar-law) 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](#def-b2-randomvar-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](#def-b2-randomvar-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](#def-b2-randomvar-law) $X$ on $(\Omega, \P)$ *has an expectation* if the family $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ is [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)); its *expectation* is then

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

**Theorem 22.7 (Transfer theorem).**

$X$ has an [expectation](#def-b2-randomvar-expectation) if and only if the family $\bigl(x\,\P(X =
x)\bigr)_{x \in X(\Omega)}$ is [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-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](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) families ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)), the family $(X(\omega)\P(\{\omega\}))_\omega$ is [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-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](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-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](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) of one family equivalent to that of the other. ∎

**Theorem 22.8 (Properties of expectation).**

On the set of [random variables](#def-b2-randomvar-law) with [expectation](#def-b2-randomvar-expectation):

1. (Linearity) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
2. (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)$ .
3. (Domination) If $\abs X \leq Z$ and $Z$ has an [expectation](#def-b2-randomvar-expectation) , so does $X$ .

**Proof.** All are properties of sums of [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) families ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)): linearity of the sum, positivity term by term, and the domination criterion for [summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable). (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](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)). $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](#def-b2-randomvar-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](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-expectation) of [convex](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-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](#def-b2-randomvar-law) $X, Y$ are *[independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence)* if $\P(X = x, Y =
y) = \P(X = x)\P(Y = y)$ for all $x, y$ — equivalently, the [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\{X \in A\}$ and $\{Y \in B\}$ are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) for all $A,
B$. If $X$ and $Y$ are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) real variables with [expectations](#def-b2-randomvar-expectation), then $XY$ has an [expectation](#def-b2-randomvar-expectation) and

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

**Proof.** The equivalence of the two formulations follows by summing the [pointwise](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def) 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](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable), since by Fubini for families ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series))

$$
\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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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](#def-b2-randomvar-law) in both scenarios, different joint [laws](#def-b2-randomvar-law), different product [expectations](#def-b2-randomvar-expectation). 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](#def-b2-randomvar-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](#def-b2-randomvar-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:

1. $V(aX + b) = a^2\,V(X)$ ;
2. $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) ;$$
3. if $X, Y$ are [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) , $\operatorname{Cov}(X, Y) = 0$ (the converse is false), so [variances](#def-b2-randomvar-variance) of [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) variables add.

**Proof.** *1* and *2* are expansions of squares plus linearity; the products $X_iX_j$ have [expectations](#def-b2-randomvar-expectation) by Cauchy–Schwarz below (or by $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$). *3* is [Theorem 22.11](#thm-b2-randomvar-product) 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).**

1. (Markov) If $X \geq 0$ has an [expectation](#def-b2-randomvar-expectation), then for every $a > 0$: $$\P(X \geq a) \leq \frac{\E(X)}{a} .$$
2. (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](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def), $a\,\mathbf{1}_{X \geq a} \leq X$ (on the [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) the left side is $a \leq X$; off it, $0 \leq X$). Take [expectations](#def-b2-randomvar-expectation): $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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\{(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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence), and set $S = X +
Y$, $D = X - Y$. By bilinearity of the [covariance](#def-b2-randomvar-variance),

$$
\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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence)? 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](#def-b2-randomvar-variance). (For this pair, zero [covariance](#def-b2-randomvar-variance) needed $V(X) = V(Y)$: identical [distributions](#def-b2-randomvar-law), not [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](#def-b2-randomvar-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](#exo-b2-randomvar-7) previews and this chapter’s weekend problem develops systematically.

**Theorem 22.19 (Cauchy–Schwarz and Jensen).**

1. (Cauchy–Schwarz) If $X, Y$ have second moments, $XY$ has an [expectation](#def-b2-randomvar-expectation) and $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; consequently $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
2. (Jensen) If $\varphi \colon I \to \R$ is [convex](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-convex) on an interval containing $X(\Omega)$, and $X$, $\varphi(X)$ have [expectations](#def-b2-randomvar-expectation), then $$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$$

**Proof.** *1.* [Summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) of $XY$: $\abs{XY} \leq \frac{X^2 + Y^2}2$. The map $(X, Y) \mapsto \E(XY)$ is a positive [symmetric bilinear form](https://one-course.com/books/math/4/en/chapter/12-quadratic-forms#def-b2-quadratic-def) on the space of variables with second moments, so the abstract Cauchy–Schwarz inequality of [Chapter 12](https://one-course.com/books/math/4/en/chapter/12-quadratic-forms#ch-b2-quadratic) applies (positive *semi*-definite suffices for the inequality). Applying it to the centered variables gives the [covariance](#def-b2-randomvar-variance) bound.

*2.* First, $m = \E(X)$ lies in $I$: $I$ is an interval containing all values of $X$, and [expectation](#def-b2-randomvar-expectation) is monotone, so $m$ is between $\inf X(\Omega)$ and $\sup X(\Omega)$. By the support-line theorem for convex functions ([Chapter 8](https://one-course.com/books/math/4/en/chapter/8-functions-of-a-real-variable#ch-b2-realfun)), there are $\alpha, \beta$ with $\varphi(t) \geq \alpha t + \beta$ for all $t \in I$ and $\varphi(m) = \alpha m + \beta$. Then, [pointwise](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def) on $\Omega$, $\varphi(X) \geq \alpha X + \beta$; taking [expectations](#def-b2-randomvar-expectation),

$$
\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](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) (or at least zero [covariance](#def-b2-randomvar-variance)): 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](#def-b2-randomvar-variance) add only across [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) (or uncorrelated) summands. (iii) $\E(f(X))$ is not $f(\E(X))$; for [convex](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-convex) $f$ Jensen even tells you the direction of the error, as in [Example 22.10](#ex-b2-randomvar-transferex). (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](#def-b2-randomvar-expectation), and no fair entry price for the game exists. [Summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) in the definition of $\E$ is not bookkeeping pedantry — it is where heavy tails are detected. (v) Finally, the transfer theorem needs *absolute* [summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) before any rearrangement of the sum over values is legitimate ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)).

**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](#def-b2-randomvar-variance) — the same certificate applies verbatim to any variable with $\E = 50$, $V = 25$, however exotic, and [Example 22.18](#ex-b2-randomvar-chebsharp) shows some such variable saturates it. Universality has a price; when the [distribution](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) identically distributed $X, Y$ with [variance](#def-b2-randomvar-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](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-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](#def-b2-randomvar-law) is just a bookkeeping device for [convex](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-convex) combinations — the barycentric viewpoint of [Chapter 17](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#ch-b2-affine) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) [random variables](#def-b2-randomvar-law) with the same [law](#def-b2-randomvar-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](#thm-b2-randomvar-variancerules) (pairwise [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) kills the [covariances](#def-b2-randomvar-variance)) $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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $A$ in [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#ch-b2-funcseq) — 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](#exo-b2-randomvar-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](#exo-b2-randomvar-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 nnn 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.](https://one-course.com/images/onecourse/chapters/math-4/b2-randomvar/fig-6370cfd6ec28.svg)

*The law of large numbers as a picture: the [law](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun): the [expectation](#def-b2-randomvar-expectation) $\E(t^X)$ of one cunning function of $X$ packs the whole [law](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) variables becomes multiplicativity of [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci). Backward, [expectation](#def-b2-randomvar-expectation) is a [barycenter](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#def-b2-affine-barycenter) with probability weights ([Chapter 17](https://one-course.com/books/math/4/en/chapter/17-affine-spaces#ch-b2-affine)), Jensen’s inequality is the support-line geometry of convex functions ([Chapter 8](https://one-course.com/books/math/4/en/chapter/8-functions-of-a-real-variable#ch-b2-realfun)), 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 of Exercise 22.1.**

*Binomial:* $X = \sum_{i=1}^n X_i$ with [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) Bernoulli $X_i$; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$, and [variances](#def-b2-randomvar-variance) of [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) variables add ([Theorem 22.14](#thm-b2-randomvar-variancerules)):

$$
\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](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)), $\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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence). Show that $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolution of the weights; binomial theorem), and that the conditional [law](#def-b2-randomvar-law) of $X$ given $X + Y = n$ is binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$.

**Solution of Exercise 22.2.**

*Sum:* for $n \in \N$, by disjointness and [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](#def-b2-randomvar-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](#def-b2-randomvar-law) $\mathcal{B}\bigl(n,
\frac{\lambda}{\lambda+\mu}\bigr)$: given the total count, each [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) independently “chooses” the first source with probability proportional to its rate.

**Exercise 22.3 ★.**

(Coupon collector, [expectation](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ch-b2-comparison)).

**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](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ch-b2-comparison)). 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](#def-b2-randomvar-law).

**Solution of Exercise 22.4.**

[Pointwise](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def), $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](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)) 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](#def-b2-randomvar-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 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) needed.

*[Covariance](#def-b2-randomvar-variance):* 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](#thm-b2-randomvar-variancerules),

$$
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](#def-b2-randomvar-variance) than with replacement (equality only for $n = 1$), the negative correlations acting as a stabilizer. For $n = N$ the [variance](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity), [Theorem 21.6](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-continuity).)*

**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](#def-b2-randomvar-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](#thm-b2-randomvar-markov)) gives $\P\bigl(\abs{X - m} \geq
\frac1n\bigr) \leq n^2\,V(X) = 0$ for every $n$; the [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ increase to $\{X \neq
m\}$, so monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ([Theorem 21.6](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-continuity)) 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 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) 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](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#ch-b2-funcseq) in this probabilistic language (split on $\bigl|\frac{S_n}{n} -
x\bigr| \geq \delta$ and use Chebyshev).

**Solution of Exercise 22.8.**

By the transfer theorem ([Theorem 22.7](#thm-b2-randomvar-transfer)) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $D
= \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$: off $D$, the difference is at most the modulus of [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-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](#def-b2-randomvar-expectation) 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](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) of $f$ on $[0, 1]$ makes $\omega_f(\delta) \to
0$: choose $\delta$ then $n$, and $B_nf \to f$ [uniformly](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def) — the Weierstrass approximation theorem of [Chapter 10](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#ch-b2-funcseq), whose “counting lemma” is now recognizable as Chebyshev’s inequality for the binomial [law](#def-b2-randomvar-law).

**Exercise 22.9 ★★★.**

(Strong [law](#def-b2-randomvar-law) under fourth moments) Let $(X_k)$ be [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence), 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-borelcantelli)) that $S_n/n \to 0$ almost surely along a suitable formulation: the [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} <
\frac1j\}$ has probability $1$.

**Solution of Exercise 22.9.**

Expand $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ and take [expectations](#def-b2-randomvar-expectation). By [independence](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) series. By Borel–Cantelli 1 ([Theorem 21.25](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-borelcantelli)), for each $j$ the [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $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](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-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](#exo-b2-randomvar-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 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](#def-b2-randomvar-variance) exactly $1$, whatever $n$.

**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](#def-b2-randomvar-variance) toolkit ([Theorem 22.14](#thm-b2-randomvar-variancerules)),

$$
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](#def-b2-randomvar-variance) $1$, independent of $n$ — consistent with the Poisson limit of the matching problem ([Exercise 21.5](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#exo-b2-proba-5)).

**Exercise 22.12 ★★★.**

(Coupon collector, concentration) In the setting of [Exercise 22.3](#exo-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) of the geometric stages and $V(\mathcal
G(p)) = \frac{1-p}{p^2}$ ([Exercise 22.1](#exo-b2-randomvar-1); the value $\pi^2/6$ is [Example 14.12](https://one-course.com/books/math/4/en/chapter/14-fourier-series#ex-b2-fourier-basel)). 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 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence). 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](https://one-course.com/books/math/4/en/chapter/14-fourier-series#ex-b2-fourier-basel). With $\E(T_n) = nH_n$, $H_n =
\sum_1^n\frac1k$ ([Exercise 22.3](#exo-b2-randomvar-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](#ex-b2-randomvar-chebsharp) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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}$.

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?
2. 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.
3. (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](#exo-b2-randomvar-7).
4. (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](#def-b2-randomvar-law), 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} .$$
5. 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.**

6. (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!$).
7. Deduce, for [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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)} .$$
8. 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$ .
9. (Hoeffding’s lemma) Let $X \in \intcc01$ with $\E X =  p$, and $\psi(t) = \ln\E(\eu^{tX})$. Justify that $\psi$ is twice [differentiable](https://one-course.com/books/math/4/en/chapter/15-differential-calculus#def-b2-diffcalc-differential) 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](#def-b2-randomvar-variance)* of a reweighted variable still taking values in $\intcc01$; bound it by $\frac14$ ([Exercise 22.6](#exo-b2-randomvar-6)’s minimality argument) and conclude by Taylor: $$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$$
10. (Hoeffding’s inequality) For [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) $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).$$
11. 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence), uniformly chosen voters; each answers honestly; $p$ is the true score, $\widehat p_n$ the poll’s figure.

12. 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} .$$
13. 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.
14. 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](#exo-b2-randomvar-5) : the [variance](#def-b2-randomvar-variance) shrinks by $\frac{N-n}{N-1}$ ).
15. (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.
16. What the mathematics does *not* cover: list the modelling assumptions used ( [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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.**

17. (Median of means: exponential decay from two moments) Split a budget of $km$ samples into $k$ [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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](#def-b2-randomvar-variance).
18. (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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) to happen.
19. (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.
20. 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.
21. Draw up the toolbox table: for Markov, Chebyshev, the fourth-moment bound of [Exercise 22.9](#exo-b2-randomvar-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.**

22. (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\%$ .
23. (Rare [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) 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](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun) ) will come from.
24. (Strong [law](#def-b2-randomvar-law) for coins) From $\sum_n  2\eu^{-2n\delta^2} < \infty$ and Borel–Cantelli ( [Theorem 21.25](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-borelcantelli) ), prove that $\widehat p_n \to p$ almost surely for [independent](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) coin flips: formulate the almost-sure [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) as $\bigcap_j\bigcup_N\bigcap_{n\geq N}  \{\abs{\widehat p_n - p} < \tfrac1j\}$ as in [Exercise 22.9](#exo-b2-randomvar-9) , and conclude. (Boundedness replaces the fourth moment used there.)
25. 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 of Problem 22.1.**

**1.** $\E(S_n) = \frac n2$ and Markov ([Theorem 22.15](#thm-b2-randomvar-markov)) 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](https://one-course.com/books/math/4/en/chapter/12-quadratic-forms#def-b2-quadratic-adjoint) about $n/2$ ($S_n$ and $n - S_n$ have the same [law](#def-b2-randomvar-law)), so with $x = n(a -
\frac12) > 0$ the two [events](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $\{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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-compact) $t$-interval, by $\eu^{\abs t}\P(X = x)$ (as $0 \leq x \leq 1$): by the differentiation theorem for [normally](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-series) convergent series ([Theorem 10.7](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#thm-b2-funcseq-differentiation)) it is twice [differentiable](https://one-course.com/books/math/4/en/chapter/15-differential-calculus#def-b2-diffcalc-differential), 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](#def-b2-randomvar-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](#def-b2-randomvar-variance) of a $\intcc01$-valued variable is at most $\frac14$: by [Exercise 22.6](#exo-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-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](#def-b2-randomvar-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](#def-b2-randomvar-variance) is multiplied by $\frac{N -
n}{N-1} < 1$ ([Exercise 22.5](#exo-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-topology) 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-independence) 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](#def-b2-randomvar-variance) — useful precisely when the summands are unbounded and Hoeffding is unavailable.

**18.** Cauchy–Schwarz ([Theorem 22.19](#thm-b2-randomvar-jensen)):

$$
\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](https://one-course.com/books/math/4/en/chapter/12-quadratic-forms#def-b2-quadratic-adjoint) 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](#ex-b2-randomvar-chebsharp)), and the best tool at question 23. Fourth moment ([Exercise 22.9](#exo-b2-randomvar-9)): decay $C/n^2$, just enough [summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) 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](#def-b2-randomvar-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](#def-b2-randomvar-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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space), the Poisson approximation proved in [Chapter 23](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun), 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](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#thm-b2-proba-borelcantelli)) gives $\P(\abs{\widehat p_n - p} \geq \delta \text{ infinitely
often}) = 0$, i.e. the [event](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#def-b2-proba-space) $E_j =
\bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} <
\tfrac1j\}$ has probability $1$ for each $j$. The [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-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](#exo-b2-randomvar-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](#def-b2-randomvar-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](#def-b2-randomvar-law) with explicit constants — turning every bound of this problem into an asymptotic equality.