---
title: "Probability on Countable Spaces"
book: "University Mathematics — Year 2"
subject: math
language: en
chapter: 21
exercises: 12
source: https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces
---

# Chapter 21 — Probability on Countable Spaces

The final three chapters develop modern probability theory: [probability measures](#def-b2-proba-space) on [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) [sample spaces](#def-b2-proba-space), discrete random variables, and [generating functions](https://one-course.com/books/math/4/en/chapter/11-power-series#ex-b2-powerseries-fibonacci). The finite theory of the High School volume acquires its full infrastructure: $\sigma$-additivity replaces finite additivity, and the summable-family machinery of [Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series) is exactly what makes infinite [sample spaces](#def-b2-proba-space) workable. The centerpiece results here are the [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) of probability along monotone sequences of [events](#def-b2-proba-space) and the Borel–Cantelli lemma.

## 21.1 Probability spaces

**Definition 21.1 (Countable probability space).**

Let $\Omega$ be a nonempty finite or [countable set](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) (the *sample space*). A *probability measure* on $\Omega$ is a map $\P$ from the set $\mathcal{P}(\Omega)$ of all subsets of $\Omega$ (*events*) to $[0, 1]$ such that:

1. $\P(\Omega) = 1$ ;
2. ($\sigma$-additivity) for every sequence $(A_n)_{n\in\N}$ of pairwise disjoint events, $$\P\Bigl(\,\bigcup_{n \in \N} A_n\Bigr) = \sum_{n=0}^{\infty} \P(A_n) .$$

The pair $(\Omega, \P)$ is a ([countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable)) *probability space*.

**Remark 21.2.**

On a [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) $\Omega$ we may take all subsets as [events](#def-b2-proba-space); on uncountable spaces (as needed for [continuous](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) models in Year 3) this is no longer possible, and one restricts $\P$ to a suitable collection of [events](#def-b2-proba-space), a *$\sigma$-algebra*. All the formulas of this chapter survive that generalization verbatim.

**Proposition 21.3 (Elementary rules).**

For [events](#def-b2-proba-space) $A, B$ and a [probability measure](#def-b2-proba-space) $\P$: $\P(\emptyset) = 0$; $\P$ is finitely additive; $\P(A^c) = 1 -
\P(A)$; if $A \subseteq B$ then $\P(A) \leq \P(B)$; and

$$
\P(A \cup B) = \P(A) + \P(B) - \P(A \cap B) .
$$

**Proof.** Applying $\sigma$-additivity to $A_0 = \Omega$, $A_n = \emptyset$ ($n \geq 1$) gives $1 = 1 + \sum_{n\geq1}\P(\emptyset)$, so $\P(\emptyset) = 0$; padding a finite disjoint union with empty sets then gives finite additivity. The rest follows as in the finite case (High School volume): $1 = \P(A) + \P(A^c)$ from $\Omega = A \sqcup A^c$; $\P(B) = \P(A) + \P(B \setminus A)
\geq \P(A)$ when $A \subseteq B$; and decomposing into three disjoint pieces,

$$
\begin{align*}
\P(A \cup B) &= \P(A \setminus B) + \P(B \setminus A) +
\P(A \cap B)\\
&= \bigl(\P(A) - \P(A\cap B)\bigr) + \bigl(\P(B) - \P(A\cap
B)\bigr) + \P(A \cap B),
\end{align*}
$$

which is inclusion–exclusion; the general $n$-set version is [Exercise 21.4](#exo-b2-proba-4). ∎

**Proposition 21.4 (Distributions on a countable space).**

Giving a [probability measure](#def-b2-proba-space) on a [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) $\Omega =
\{\omega_0, \omega_1, \dots\}$ amounts exactly to giving weights $p_i = \P(\{\omega_i\}) \geq 0$ with $\sum_i p_i = 1$; then for every $A \subseteq \Omega$,

$$
\P(A) = \sum_{\omega \in A} \P(\{\omega\}) ,
$$

an ([absolutely](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-def) convergent) sub-sum of the family $(p_i)$.

**Proof.** Given $\P$, the singletons $\{\omega\}$, $\omega \in A$, form a [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) disjoint cover of $A$, so $\sigma$-additivity forces

$$
\P(A) = \sum_{\omega\in A}\P(\{\omega\}),
$$

an unconditional sub-sum of the nonnegative [summable family](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) $(p_i)$ — reordering is harmless precisely because the terms are nonnegative ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)); in particular $\sum_ip_i = \P(\Omega) = 1$. Conversely, given nonnegative weights of total sum $1$, define $\P(A) = \sum_{\omega \in A}p_\omega$: the family is [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable), and $\sigma$-additivity is exactly the theorem on summation by packets of [Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series) applied to the partition of $\bigcup A_n$ into the $A_n$. ∎

**Example 21.5 (Geometric model: waiting for the first head).**

Toss a coin with head probability $p \in \intoo{0}{1}$ repeatedly, and let $\Omega = \N^* \cup \{\infty\}$ record the rank of the first head. The natural weights are

$$
\P(\{k\}) = (1 - p)^{k-1}p
\quad (k \in \N^*),
\qquad
\P(\{\infty\}) = 0 ,
$$

a [probability measure](#def-b2-proba-space) since $\sum_{k\geq1}(1-p)^{k-1}p =
\frac{p}{1 - (1-p)} = 1$: with probability $1$ the game ends — but the [sample space](#def-b2-proba-space) must still contain the possibility that it does not. [Countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) additivity is what lets us assert $\P(\text{the game ends}) = \sum_k \P(\{k\})$.

**Theorem 21.6 (Monotone continuity).**

Let $(A_n)$ be a sequence of [events](#def-b2-proba-space).

1. If $A_n \subseteq A_{n+1}$ for all $n$ ( *increasing* ), then $\P\bigl(\bigcup_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .
2. If $A_n \supseteq A_{n+1}$ for all $n$ ( *decreasing* ), then $\P\bigl(\bigcap_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .

**Proof.** *1.* Disjointify: let $B_0 = A_0$ and $B_n = A_n \setminus
A_{n-1}$. The $B_n$ are pairwise disjoint with $\bigcup_{k \leq n}
B_k = A_n$ and $\bigcup_n B_n = \bigcup_n A_n$. By $\sigma$-additivity and finite additivity,

$$
\P\Bigl(\bigcup_n A_n\Bigr)
= \sum_{n=0}^\infty \P(B_n)
= \lim_{N\to\infty}\sum_{n=0}^N \P(B_n)
= \lim_{N\to\infty}\P(A_N) .
$$

*2.* Pass to complements: $(A_n^c)$ is increasing with union $\bigl(\bigcap A_n\bigr)^c$, and apply part 1: $1 - \P(\bigcap A_n) = \lim (1 - \P(A_n))$. ∎

**Corollary 21.7 (Countable subadditivity).**

For any sequence of [events](#def-b2-proba-space), $\P\bigl(\bigcup_n A_n\bigr) \leq
\sum_{n=0}^\infty \P(A_n)$.

**Proof.** Finite subadditivity $\P(A_0 \cup \dots \cup A_N) \leq
\sum_0^N \P(A_n)$ follows from inclusion–exclusion by induction (or from additivity over the disjointified $B_n \subseteq A_n$). Let $N \to \infty$: the left side converges to $\P(\bigcup_n A_n)$ by monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) applied to the increasing sequence $C_N = A_0 \cup \dots \cup A_N$. ∎

**Example 21.8 (The union bound: crude but indestructible).**

Subadditivity with finitely many [events](#def-b2-proba-space) — the *union bound* — trades precision for universality. For the birthday problem with $23$ people, bounding the collision probability by the sum over pairs gives

$$
\P(\text{collision}) \leq \binom{23}2\cdot\frac1{365}
= \frac{253}{365} \approx 0.693 ,
$$

against the true $0.507$: off by a wide margin, because collisions overlap. Yet the bound needs *no* [independence](#def-b2-proba-independence), no joint law, nothing but the pair probabilities — which is why, in the weekend problem and throughout [Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar), the union bound is the first tool drawn: when it happens to be small, the matter is settled with no further modelling.

**Example 21.9 (A six comes, eventually).**

Roll a fair die forever and let $B_n = {}$“at least one six among the first $n$ rolls”, an increasing sequence of [events](#def-b2-proba-space) with $\P(B_n) = 1 - (5/6)^n$. Monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) gives

$$
\P(\text{a six eventually appears})
= \P\Bigl(\bigcup_nB_n\Bigr)
= \lim_n\bigl(1 - (5/6)^n\bigr) = 1 .
$$

The point is not the (obvious) limit but the logical step: “eventually” is an [event](#def-b2-proba-space) about *infinitely many* rolls, outside the reach of finite additivity, and monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) — that is, $\sigma$-additivity — is precisely the axiom that assigns it a probability. Every almost-sure statement in the rest of this book passes through this same narrow door.

## 21.2 Conditioning and independence

**Definition 21.10 (Conditional probability).**

For [events](#def-b2-proba-space) $A, B$ with $\P(B) > 0$, the *conditional probability* of $A$ given $B$ is

$$
\P(A \mid B) = \frac{\P(A \cap B)}{\P(B)} .
$$

The map $A \mapsto \P(A \mid B)$ is itself a [probability measure](#def-b2-proba-space) on $\Omega$.

**Remark 21.11.**

That $A \mapsto \pcond BA$ is again a [probability measure](#def-b2-proba-space) is worth a moment: $\pcond B\Omega = 1$ and $\sigma$-additivity pass through the quotient because intersection with $B$ respects disjoint unions. The practical consequence: every identity of this chapter — inclusion–exclusion, monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity), Borel–Cantelli — may be applied *after* conditioning, with no new proofs. Probabilists constantly “work under $\pcond B{\cdot}$” for exactly this reason.

**Example 21.12 (Conditioning can create uniformity).**

Roll two fair dice and condition on the sum being $7$: for each $k \in \intint16$,

$$
\pcond{\{S = 7\}}{X = k}
= \frac{\P(X = k,\ Y = 7 - k)}{\P(S = 7)}
= \frac{1/36}{6/36} = \frac16 :
$$

given a sum of $7$, the first die is exactly uniform — $7$ is the only total compatible with every face, so the conditioning erases all information about $X$. Any other total skews the law (given $S = 4$, the first die is uniform on $\{1, 2, 3\}$ only). Computing a conditional law means renormalizing the joint weights along the conditioning [event](#def-b2-proba-space), nothing more.

**Example 21.13 (The second draw is as good as the first).**

An urn holds $3$ white and $2$ black balls; draw two without replacement. Everyone agrees $\P(W_1) = \frac35$; what is $\P(W_2)$? Total probability along the first draw:

$$
\P(W_2) = \pcond{W_1}{W_2}\,\P(W_1) +
\pcond{B_1}{W_2}\,\P(B_1)
= \frac24\cdot\frac35 + \frac34\cdot\frac25
= \frac{12}{20} = \frac35 :
$$

exactly $\P(W_1)$. No computation was needed: by symmetry, every ball is equally likely to be the second one drawn, so the second draw — *unconditionally* — has the same law as the first. Conditioning on the first result changes the odds; not knowing it does not. This exchangeability argument returns in the next chapter for sampling without replacement, where it gives the hypergeometric mean $np$ with no binomial identities at all.

**Theorem 21.14 (Compound probabilities, total probability, Bayes).**

1. (Chain rule) If $\P(A_1 \cap \dots \cap A_{n-1}) > 0$, $$\P(A_1 \cap \dots \cap A_n) = \P(A_1)\,\P(A_2 \mid A_1)\cdots \P(A_n \mid A_1 \cap \dots \cap A_{n-1}) .$$
2. (Total probability) If $(B_i)_{i \in I}$ is a finite or [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) partition of $\Omega$ with $\P(B_i) > 0$, then for every [event](#def-b2-proba-space) $A$: $$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$$
3. (Bayes) Under the same hypotheses, if moreover $\P(A) > 0$: $$\P(B_j \mid A) = \frac{\P(A \mid B_j)\,\P(B_j)}  {\sum_{i \in I} \P(A \mid B_i)\,\P(B_i)} .$$

**Proof.** *1.* Write each [conditional probability](#def-b2-proba-conditional) as a quotient: the right side is

$$
\P(A_1)\cdot\frac{\P(A_1 \cap A_2)}{\P(A_1)}\cdot
\frac{\P(A_1 \cap A_2 \cap A_3)}{\P(A_1 \cap A_2)}\cdots
\frac{\P(A_1 \cap \dots \cap A_n)}{\P(A_1 \cap \dots \cap
A_{n-1})},
$$

a telescoping product: every denominator cancels the preceding numerator, leaving $\P(A_1 \cap \dots \cap A_n)$. All denominators are $\geq \P(A_1 \cap \dots \cap A_{n-1}) >
0$ by monotonicity, so nothing vanishes. (The hypothesis guards exactly this: conditioning on an [event](#def-b2-proba-space) of probability zero is undefined.) *2.* The sets $A \cap B_i$ are pairwise disjoint with union $A$; apply ($\sigma$-)additivity and the definition of conditioning. *3.* Both sides of $\P(B_j \mid A)\P(A) = \P(A \mid
B_j)\P(B_j)$ equal $\P(A \cap B_j)$; divide by $\P(A)$ and expand $\P(A)$ by total probability. ∎

**Example 21.15 (The birthday collision, by the chain rule).**

With $n$ people whose birthdays are [independent](#def-b2-proba-independence) and uniform over $365$ days, let $D_n = {}$“all $n$ birthdays differ”. Conditioning person by person (chain rule):

$$
\P(D_n) = \prod_{k=1}^{n-1}\Bigl(1 - \frac{k}{365}\Bigr),
$$

each new person having to avoid the $k$ days already taken. For $n = 23$: $\P(D_{23}) \approx 0.493$ — a shared birthday is already more likely than not. The heuristic that explains the smallness of $23$: taking logarithms, $-\ln
\P(D_n) \approx \sum_{k<n}\frac k{365} =
\frac{\binom n2}{365}$, and $\binom{23}2 = 253$ gives $253/365 \approx 0.693 \approx \ln 2$. What matters is the number of *pairs*, which grows quadratically: collision problems live on the scale $n \sim \sqrt{365}$, not $n \sim
365$ — the birthday paradox is a square root in disguise.

**Example 21.16 (Monty Hall, by Bayes).**

A prize hides behind one of three doors, uniformly. You pick door $1$; the host, who knows where the prize is, opens one of the other doors, always empty (choosing [uniformly](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def) when he has a choice), say door $3$. Let $B_i = {}$“prize behind door $i$” and $A = {}$“host opens door $3$”. Then $\pcond{B_1}{A} = \frac12$, $\pcond{B_2}{A} = 1$, $\pcond{B_3}{A} = 0$, so by Bayes ([Theorem 21.14](#thm-b2-proba-bayes)),

$$
\P(B_2 \mid A)
= \frac{1\cdot\frac13}
{\frac12\cdot\frac13 + 1\cdot\frac13 + 0\cdot\frac13}
= \frac23 :
$$

switching doors wins two times out of three. The computation locates the popular confusion exactly: the host’s move is *informative* (he could not [open](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-topology) door $2$ if the prize were there), and Bayes’ formula is the bookkeeping device that converts this asymmetry into the $\frac23$. Conditioning on “what was seen” rather than on “what is true” is the whole art of the formula.

**Example 21.17 (The Chevalier de Méré’s two bets).**

Two seventeenth-century wagers, settled by [independence](#def-b2-proba-independence). Bet one: at least one six in $4$ rolls of a die,

$$
\P = 1 - \Bigl(\frac56\Bigr)^{\!4} \approx 0.518 > \frac12 .
$$

Bet two: at least one double-six in $24$ rolls of two dice,

$$
\P = 1 - \Bigl(\frac{35}{36}\Bigr)^{\!24} \approx 0.491 <
\frac12 .
$$

De Méré reasoned that $24$ rolls at chance $\frac1{36}$ should match $4$ rolls at chance $\frac16$ (same ratio $\frac{24}{36} = \frac46$); the failure of this proportionality — probabilities of unions do not scale linearly — is said to have prompted his letter to Pascal, and thereby the birth of probability theory. The correct comparison is through logarithms: $n$ trials at chance $p$ succeed at least once with probability $1 - (1-p)^n \approx
1 - \eu^{-np}$, so the honest invariant is $np$: here $4\cdot\frac16 = \frac23$ versus $24\cdot\frac1{36} =
\frac23$ — equal! The two bets differ only at the second order in $p$, and by just enough to move one across the fifty-percent line: small probabilities are a domain where intuition needs the exponential, not the ruler.

**Remark 21.18 (Common fallacies of conditioning).**

Three recurrent confusions, all visible in the examples above. (i) *Inversion*: $\pcond BA$ and $\pcond AB$ differ by the factor $\P(A)/\P(B)$ — a test that is $99\%$ accurate on the sick may still leave a positive patient almost certainly healthy when the disease is rare ([Exercise 21.3](#exo-b2-proba-3)); quoting $\pcond{\text{sick}}{
\text{positive}}$ where $\pcond{\text{positive}}{
\text{sick}}$ is meant is the base-rate fallacy. (ii) *Conditioning on the wrong [event](#def-b2-proba-space)*: in Monty Hall, the correct conditioning [event](#def-b2-proba-space) is “the host opened door $3$”, not “the prize is not behind door $3$”; the two carry different information, and the whole $\frac23$ hangs on the difference. (iii) *Disjoint versus [independent](#def-b2-proba-independence)*: disjoint [events](#def-b2-proba-space) of positive probability are never [independent](#def-b2-proba-independence) ($\P(A\cap B) = 0 \neq \P(A)\P(B)$) — [independence](#def-b2-proba-independence) is compatibility of information, not absence of overlap.

**Definition 21.19 (Independence).**

[Events](#def-b2-proba-space) $A$ and $B$ are *independent* if $\P(A \cap B) =
\P(A)\P(B)$. A family $(A_i)_{i \in I}$ of [events](#def-b2-proba-space) is *(mutually) independent* if for every finite subset $J
\subseteq I$,

$$
\P\Bigl(\bigcap_{i \in J} A_i\Bigr)
= \prod_{i \in J} \P(A_i) .
$$

**Remark 21.20.**

Mutual [independence](#def-b2-proba-independence) is strictly stronger than pairwise [independence](#def-b2-proba-independence): with two fair coin tosses, the [events](#def-b2-proba-space) “first is a head”, “second is a head”, “both agree” are pairwise [independent](#def-b2-proba-independence) (each pair has intersection probability $\frac14 =
\frac12\cdot\frac12$), yet the triple intersection has probability $\frac14 \neq \frac18$. Note also that if $A, B$ are [independent](#def-b2-proba-independence), so are $A, B^c$ (compute: $\P(A \cap B^c) = \P(A) - \P(A\cap B) =
\P(A)(1 - \P(B))$), hence also $A^c, B^c$.

**Example 21.21 (Independence read off a product structure).**

Roll two fair dice: $\Omega = \intint16^2$ with uniform weights. Let $A = {}$“first die even” and $B = {}$“second die at least $5$”. Counting: $\abs A = 3\cdot6 = 18$, $\abs B = 6\cdot2 = 12$, $\abs{A\cap B} = 3\cdot2 = 6$, so

$$
\P(A\cap B) = \frac6{36} = \frac{18}{36}\cdot\frac{12}{36} =
\P(A)\,\P(B) :
$$

[independent](#def-b2-proba-independence), and the mechanism is visible — $A$ constrains only the first coordinate, $B$ only the second, and the uniform measure on a product set makes coordinate counts multiply. Every claim of the type “[events](#def-b2-proba-space) depending on disjoint groups of tosses are [independent](#def-b2-proba-independence)” (used massively in the weekend problem) is this computation, wearing more indices.

**Example 21.22 (First-step analysis).**

For the geometric model of [Example 21.5](#ex-b2-proba-geometric), what is the probability $u$ that the first head falls at an *even* rank? Condition on toss one: with probability $p$ the rank is $1$ (odd); with probability $q = 1 - p$ the game restarts with all parities flipped, so

$$
u = p\cdot0 + q\,(1 - u)
\qquad\Longrightarrow\qquad
u = \frac{q}{1 + q} .
$$

One line, no series — and it agrees with the direct summation of [Exercise 21.9](#exo-b2-proba-9), which gives $1 - u =
\frac1{1+q}$. This “first-step” technique (condition on the first experiment, recognize a shifted copy of the problem) is the probabilistic form of a recursion, and it is the engine behind the game-duration equations of [Exercise 21.6](#exo-b2-proba-6) and the first-passage computations of the weekend problem.

## 21.3 The Borel–Cantelli lemma

**Definition 21.23 (Limit superior of events).**

For a sequence $(A_n)$ of [events](#def-b2-proba-space), the [event](#def-b2-proba-space)

$$
\limsup_n A_n
= \bigcap_{N=0}^{\infty}\ \bigcup_{n \geq N} A_n
= \{\omega \in \Omega : \omega \in A_n
\text{ for infinitely many } n\}
$$

is the [event](#def-b2-proba-space) “$A_n$ occurs infinitely often”.

**Example 21.24 (Translating “infinitely often” and “eventually”).**

The complement of $\limsup_nA_n$ is, by de Morgan,

$$
\Bigl(\bigcap_N\bigcup_{n\geq N}A_n\Bigr)^{\!c}
= \bigcup_N\bigcap_{n\geq N}A_n^c
= \{\omega : \omega \notin A_n \text{ for all large }n\},
$$

the [event](#def-b2-proba-space) “*eventually*, $A_n$ fails” (written $\liminf_nA_n^c$). So “$A_n$ infinitely often” and “$A_n^c$ eventually” are complementary — keeping this dictionary straight prevents most quantifier accidents. Sample translations for coin tossing: “infinitely many heads” is $\limsup\{X_n = H\}$; “only finitely many runs of $100$ heads” is the complement of a limsup; “the running frequency converges to $\frac12$” is $\bigcap_j\bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n -
\tfrac12} < \tfrac1j\}$ — [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) operations throughout, so all of these are honest [events](#def-b2-proba-space).

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

1. If $\sum_{n} \P(A_n) < \infty$ , then $\P\bigl(\limsup_n A_n\bigr) = 0$ .
2. If the [events](#def-b2-proba-space) $A_n$ are [independent](#def-b2-proba-independence) and $\sum_n \P(A_n) = \infty$ , then $\P\bigl(\limsup_n A_n\bigr) = 1$ .

**Proof.** *1.* Let $C_N = \bigcup_{n \geq N}A_n$; the sequence $(C_N)$ is decreasing with intersection $\limsup A_n$, and by [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) subadditivity ([Corollary 21.7](#cor-b2-proba-subadd))

$$
\P(C_N) \leq \sum_{n \geq N}\P(A_n)
\xrightarrow[N\to\infty]{} 0
$$

(tail of a convergent series). Monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ([Theorem 21.6](#thm-b2-proba-continuity)) concludes: $\P(\limsup A_n) =
\lim_N \P(C_N) = 0$.

*2.* It suffices to show $\P\bigl(\bigcup_{n\geq N}A_n\bigr)
= 1$ for every $N$: indeed, if [events](#def-b2-proba-space) $B_N$ all have probability $1$, then

$$
\P\Bigl(\Bigl(\bigcap_NB_N\Bigr)^{\!c}\Bigr)
= \P\Bigl(\bigcup_NB_N^c\Bigr)
\leq \sum_N\P(B_N^c) = 0
$$

by [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) subadditivity ([Corollary 21.7](#cor-b2-proba-subadd)), so the [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) intersection $\limsup A_n = \bigcap_N\bigcup_{n\geq N}A_n$ still has probability $1$. Fix $N$, and consider for $M > N$ the complement:

$$
\P\Bigl(\bigcap_{n=N}^{M} A_n^c\Bigr)
= \prod_{n=N}^{M}\bigl(1 - \P(A_n)\bigr)
\leq \prod_{n=N}^{M} e^{-\P(A_n)}
= \exp\Bigl(-\sum_{n=N}^M \P(A_n)\Bigr) ,
$$

using [independence](#def-b2-proba-independence) of the complements and the convexity bound $1 -
x \leq e^{-x}$. As $M \to \infty$ the exponent tends to $-\infty$ by divergence of the series, so by monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) (decreasing sequence) $\P\bigl(\bigcap_{n \geq N}A_n^c\bigr) = 0$, i.e. $\P\bigl(\bigcup_{n \geq N}A_n\bigr) = 1$. ∎

**Example 21.26 (Infinite runs of heads).**

Toss a fair coin forever, and let $A_n$ be the [event](#def-b2-proba-space) “tosses $n,
n+1, \dots, n + k - 1$ are all heads” (a run of $k$ heads starting at time $n$), for fixed $k$. The [events](#def-b2-proba-space) $A_{jk}$ ($j =
1, 2, \dots$), depending on disjoint blocks of tosses, are [independent](#def-b2-proba-independence), each of probability $2^{-k}$, and $\sum_j 2^{-k} =
\infty$: by Borel–Cantelli 2, with probability $1$ infinitely many blocks are all-heads — *every* fixed pattern recurs infinitely often, almost surely. Conversely, if we let the run length grow, $B_n = {}$“a run of $2\log_2 n$ heads starts at $n$” has $\P(B_n) = n^{-2}$ [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable), so almost surely only finitely many such long runs start: Borel–Cantelli calibrates precisely *how long* the longest runs are.

**Example 21.27 (The infinite monkey, quantified).**

A monkey types [independent](#def-b2-proba-independence) uniform letters from a $26$-letter alphabet. Cut the typescript into disjoint blocks of four letters; the [events](#def-b2-proba-space) $A_j = {}$“block $j$ spells MATH” are [independent](#def-b2-proba-independence) with $\P(A_j) = 26^{-4}$, and $\sum_j\P(A_j) = \infty$: by Borel–Cantelli 2 the monkey types MATH infinitely often, almost surely — and the same holds for any fixed text of any length, blocks adjusted. The quantitative footnote deflates the miracle: $26^4 =
456\,976$, so the first MATH takes about half a million keystrokes on average, and a Shakespeare play of $10^5$ characters waits of order $26^{10^5}$ blocks — almost sure is a statement about the horizon $\infty$, not about any horizon a monkey will meet. Borel–Cantelli certifies the limit; the summands’ size tells the story at human scales.

**Remark 21.28.**

In [Example 21.26](#ex-b2-proba-runs) the underlying [sample space](#def-b2-proba-space) (infinite sequences of tosses) is uncountable, so strictly speaking the example lives in the measure-theoretic framework of Year 3; the *computations*, though, use only the rules proved in this chapter, applied to [events](#def-b2-proba-space) determined by finitely many tosses and their [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) combinations. This is the standard convention at this level: the theory is stated on [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) spaces, and infinite-game examples are treated with the same toolkit.

**Remark 21.29 (Perspectives within this volume).**

This chapter’s machinery is consumed wholesale by the next two. Indicators turn [events](#def-b2-proba-space) into random variables, and $\sigma$-additivity becomes the [summability](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) that defines expectation ([Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar)); Borel–Cantelli plus a [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) tail bound is exactly how the strong law of large numbers for coins is proved there. In [Chapter 23](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun), monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) reappears at the decisive moment: the extinction probability of a branching process is *defined* as the monotone limit $\lim\P(Z_n = 0)$, and the fixed-point equation it satisfies is obtained by passing to the limit in that increasing sequence — the final theorem of the book stands on this chapter’s first theorem.

**Remark 21.30 (Method: three ways to probability one).**

Almost-sure statements are proved with three levers, in increasing order of strength. *Monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity)*: exhibit the [event](#def-b2-proba-space) as an increasing union (or decreasing intersection) of finite-horizon [events](#def-b2-proba-space) with computable probabilities ([Example 21.9](#ex-b2-proba-sixeventually)). *Null unions*: a [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) union of probability-zero [events](#def-b2-proba-space) is null ([countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) subadditivity), so it suffices to kill each bad [event](#def-b2-proba-space) separately — this is how “for every $j$, eventually $\abs{\widehat p_n - p} < 1/j$” assembles into convergence. *Borel–Cantelli*: when the [event](#def-b2-proba-space) is a limsup, sum the probabilities; convergence kills it (no [independence](#def-b2-proba-independence) needed), and divergence plus [independence](#def-b2-proba-independence) certifies it. Choosing the right lever is usually the whole proof; the weekend problem runs all three in a single argument.

**Remark 21.31 (Where this is used).**

Monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) and Borel–Cantelli are the two levers of every “almost sure” statement: they drive the recurrence of the [random walk](#pb-b2-proba-1) in this chapter’s weekend problem, the almost-sure side of the law of large numbers ([Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar)), and the extinction analysis of branching processes ([Chapter 23](https://one-course.com/books/math/4/en/chapter/23-probability-generating-functions#ch-b2-genfun)). The Year 3 volume rebuilds the theory on $\sigma$-algebras and Lebesgue integration, where the uncountable [sample spaces](#def-b2-proba-space) used informally here become fully rigorous.

## 21.4 Exercises

**Exercise 21.1 ★.**

An urn contains $n$ numbered balls. Balls are drawn one by one without replacement. Compute the probability that ball number $1$ is drawn before ball number $2$. Generalize: the probability that ball $1$ is drawn first among balls $1, \dots, k$.

**Solution of Exercise 21.1.**

By symmetry: the drawing order induces a uniformly random relative order on balls $1$ and $2$, so $\P(1 \text{ before } 2) =
\frac12$. Formally: exchanging the positions of balls $1$ and $2$ in a drawing sequence is a bijection of the (equiprobable) outcomes that swaps the [event](#def-b2-proba-space) with its complement. Among balls $1, \dots, k$: the relative order of these $k$ balls is uniform among the $k!$ orderings, and ball $1$ is first in $(k-1)!$ of them: probability $\frac{(k-1)!}{k!} = \frac1k$.

**Exercise 21.2 ★.**

Show that on $\Omega = \N^*$ the weights $p_k = \frac{1}{k(k+1)}$ define a [probability measure](#def-b2-proba-space), and compute $\P(2\N^*)$ (even outcomes) as a series; show that it equals $1 - \ln 2$. *(Telescope $\frac{1}{2j(2j+1)} = \frac{1}{2j} -
\frac{1}{2j+1}$ and use the alternating harmonic series, [Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series).)*

**Solution of Exercise 21.2.**

$\frac{1}{k(k+1)} = \frac1k - \frac1{k+1}$, so $\sum_{k\geq1} p_k$ telescopes to $1$: a [probability measure](#def-b2-proba-space). Even outcomes:

$$
\P(2\N^*) = \sum_{j=1}^{\infty}\frac{1}{2j(2j+1)}
= \sum_{j=1}^{\infty}\Bigl(\frac{1}{2j} - \frac{1}{2j+1}\Bigr)
= \frac12 - \frac13 + \frac14 - \frac15 + \cdots
$$

This is the alternating harmonic series with its first term removed and signs flipped: since $\ln 2 = 1 - \frac12 + \frac13 -
\frac14 + \cdots$ ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series)),

$$
\P(2\N^*) = -\bigl(\ln 2 - 1\bigr) = 1 - \ln 2 \approx 0.307 .
$$

**Exercise 21.3 ★.**

(False positives) A disease affects one person in $10\,000$. A test detects it with probability $0.99$ on the sick, and gives a false positive with probability $0.01$ on the healthy. Compute the probability of being sick given a positive test, and comment.

**Solution of Exercise 21.3.**

Let $S$ = sick, $+$ = positive test. Bayes ([Theorem 21.14](#thm-b2-proba-bayes)) with the partition $\{S, S^c\}$:

$$
\P(S \mid +)
= \frac{0.99 \times 10^{-4}}
       {0.99 \times 10^{-4} + 0.01 \times 0.9999}
= \frac{0.000099}{0.000099 + 0.009999}
\approx 0.0098 ,
$$

below $1\%$. Although the test is “99% accurate”, a positive result leaves you about $99\%$ likely to be healthy: the false positives among the vast healthy majority swamp the true positives from the tiny sick minority. Screening tests for rare conditions must always be read through this base-rate computation.

**Exercise 21.4 ★★.**

Let $A_1, \dots, A_n$ be [events](#def-b2-proba-space). Prove the inclusion–exclusion formula

$$
\P\Bigl(\bigcup_{i=1}^n A_i\Bigr)
= \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}}
(-1)^{\abs J + 1}\,\P\Bigl(\bigcap_{i \in J}A_i\Bigr)
$$

by integrating the identity $1 - \prod_{i=1}^n(1 -
\mathbf{1}_{A_i}) = \mathbf{1}_{\bigcup A_i}$ over $\Omega$ (i.e. summing weighted by $\P(\{\omega\})$).

**Solution of Exercise 21.4.**

[Pointwise](https://one-course.com/books/math/4/en/chapter/10-sequences-and-series-of-functions#def-b2-funcseq-def) on $\Omega$: $\omega \in \bigcup A_i$ iff some factor $1 - \mathbf{1}_{A_i}(\omega)$ vanishes, so

$$
\mathbf{1}_{\bigcup A_i}
= 1 - \prod_{i=1}^n\bigl(1 - \mathbf{1}_{A_i}\bigr)
= \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}}
(-1)^{\abs J + 1}\prod_{i \in J}\mathbf{1}_{A_i} ,
$$

expanding the product and moving the $1$ across. Now $\prod_{i\in J}\mathbf{1}_{A_i} = \mathbf{1}_{\bigcap_{i \in J}
A_i}$, and summing against the weights $\P(\{\omega\})$ — legitimate: finitely many bounded terms, each family [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) — turns each indicator into the probability of its [event](#def-b2-proba-space), giving the formula.

**Exercise 21.5 ★★.**

(Matching problem, via inclusion–exclusion) $n$ letters are put uniformly at random into $n$ envelopes, one each. Using [Exercise 21.4](#exo-b2-proba-4), show that the probability of *no* correct match is $\sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}$, and deduce the probability of exactly one match.

**Solution of Exercise 21.5.**

Let $A_i$ = “letter $i$ is in the right envelope”. For $J$ of size $k$, $\P\bigl(\bigcap_{i\in J}A_i\bigr) =
\frac{(n-k)!}{n!}$ (fix $k$ letters, permute the rest). By inclusion–exclusion,

$$
\P\Bigl(\bigcup A_i\Bigr)
= \sum_{k=1}^n (-1)^{k+1}\binom nk \frac{(n-k)!}{n!}
= \sum_{k=1}^n \frac{(-1)^{k+1}}{k!} ,
$$

so

$$
\P(\text{no match})
= 1 - \P\Bigl(\bigcup A_i\Bigr)
= \sum_{k=0}^{n}\frac{(-1)^k}{k!}
\xrightarrow[n\to\infty]{} e^{-1} \approx 0.368 .
$$

Exactly one match: a permutation with exactly one fixed point is determined by the choice of the fixed letter ($n$ ways) and a *derangement* (no-match arrangement) of the other $n - 1$; writing $D_{n-1} = (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$ for the number of derangements (the first part, scaled by $(n-1)!$),

$$
\P(\text{exactly one match})
= \frac{n\,D_{n-1}}{n!}
= \frac{D_{n-1}}{(n-1)!}
= \sum_{k=0}^{n-1}\frac{(-1)^k}{k!}
\xrightarrow[n\to\infty]{} e^{-1} :
$$

in the limit, “no match” and “exactly one match” are equally likely, each with probability $e^{-1}$.

**Exercise 21.6 ★★.**

A biased coin (head probability $p \in \intoo{0}{1}$) is tossed until two consecutive heads appear. Let $q_n$ be the probability that the game lasts more than $n$ tosses. Show, conditioning on the first toss(es), that $q_n = (1-p)\,q_{n-1} + p(1-p)\,q_{n-2}$ for $n \geq 2$, and deduce that the game ends with probability $1$. *(Show $q_n \to 0$ by comparing with a geometric sequence: both roots of the characteristic equation lie in $\intoo{0}{1}$ in absolute value.)*

**Solution of Exercise 21.6.**

Condition on the start (chain rule / [Theorem 21.14](#thm-b2-proba-bayes)):

- first toss T (probability $1 - p$ ): the game restarts afresh; lasting more than $n$ means lasting more than $n - 1$ from there: contribution $(1-p)\,q_{n-1}$ ;
- first tosses HT (probability $p(1-p)$ ): restart after two tosses: contribution $p(1-p)\,q_{n-2}$ ;
- first tosses HH: the game has ended (within $n$ tosses, $n \geq 2$ ): contributes $0$ .

Hence $q_n = (1-p)q_{n-1} + p(1-p)q_{n-2}$. The characteristic equation $r^2 = (1-p)r + p(1-p)$ has roots

$$
r_\pm = \frac{(1-p) \pm \sqrt{(1-p)^2 + 4p(1-p)}}{2},
$$

with $\abs{r_\pm} < 1$: indeed the polynomial $\chi(r) = r^2 -
(1-p)r - p(1-p)$ satisfies $\chi(1) = 1 - (1-p) - p(1-p) = p^2 >
0$ and $\chi(-1) = 1 + (1-p) - p(1-p) > 0$, while $\chi(0) =
-p(1-p) < 0$: one root in $\intoo{-1}{0}$, one in $\intoo{0}{1}$. So $q_n = \alpha r_+^n + \beta r_-^n \to 0$. The [events](#def-b2-proba-space) “game lasts more than $n$” decrease to “game never ends”; monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ([Theorem 21.6](#thm-b2-proba-continuity)) gives $\P(\text{never ends}) = \lim q_n = 0$: the game ends almost surely.

**Exercise 21.7 ★★★.**

(Records) Draw an infinite sequence of [independent](#def-b2-proba-independence) uniform rankings, in the following combinatorial sense: for each $n$, the relative order of the first $n$ draws is uniform among the $n!$ possibilities, and $R_n = {}$“the $n$-th draw is a record (larger than all previous ones)”. Admitting that the [events](#def-b2-proba-space) $R_n$ are [independent](#def-b2-proba-independence) with $\P(R_n) = 1/n$ (prove at least this last equality by symmetry), show using Borel–Cantelli that infinitely many records occur almost surely, but that records at *consecutive* times $n, n+1$ occur infinitely often with probability — compute $\sum_n \P(R_n \cap R_{n+1})$ and conclude what Borel–Cantelli 1 gives.

**Solution of Exercise 21.7.**

*$\P(R_n) = 1/n$:* among the first $n$ draws, each of the $n$ relative positions of the last draw is equally likely (uniformity of the relative order), and $R_n$ is the [event](#def-b2-proba-space) that it is the largest: probability $1/n$.

*Infinitely many records:* $\sum_n \P(R_n) = \sum 1/n =
\infty$ and the $R_n$ are [independent](#def-b2-proba-independence) (admitted), so Borel–Cantelli 2 ([Theorem 21.25](#thm-b2-proba-borelcantelli)) gives $\P(\limsup R_n) = 1$: records never stop, almost surely — but they thin out logarithmically.

*Consecutive records:* by [independence](#def-b2-proba-independence),

$$
\sum_n \P(R_n \cap R_{n+1})
= \sum_n \frac{1}{n(n+1)} < \infty ,
$$

so Borel–Cantelli 1 applies: almost surely, only finitely many times is a record immediately followed by another record. The two halves of the lemma work in tandem: infinitely many records, but (a.s.) eventually never two in a row.

**Exercise 21.8 ★★★.**

(Kochen–Stone flavour, easier version) Let $(A_n)$ be [independent events](#def-b2-proba-independence) with $\P(A_n) = \frac{1}{n+1}$. Show that $\P(\limsup A_n) = 1$, although $\P(A_n) \to 0$: “individually rare, collectively certain”. Conversely, exhibit a sequence of (dependent) [events](#def-b2-proba-space) with $\sum\P(A_n) = \infty$ and $\P(\limsup A_n) = 0$, showing [independence](#def-b2-proba-independence) cannot be dropped in Borel–Cantelli 2.

**Solution of Exercise 21.8.**

*First part:* $\sum \P(A_n) = \sum\frac{1}{n+1} = \infty$ with [independence](#def-b2-proba-independence): Borel–Cantelli 2 gives $\P(\limsup A_n) = 1$. Each individual $A_n$ is increasingly unlikely, yet almost every $\omega$ belongs to infinitely many of them.

*Counterexample without [independence](#def-b2-proba-independence):* take $\Omega = \N^*$ with the weights $p_k = \frac{1}{k(k+1)}$ of [Exercise 21.2](#exo-b2-proba-2), and $A_n = \{k \in \N^* : k \geq n\}$. Then

$$
\P(A_n) = \sum_{k \geq n}\Bigl(\frac1k - \frac1{k+1}\Bigr)
= \frac1n ,
\qquad
\sum_n \P(A_n) = \infty ,
$$

but the $A_n$ are decreasing, so $\limsup_n A_n = \bigcap_n A_n =
\emptyset$: $\P(\limsup A_n) = 0$. Divergence of $\sum\P(A_n)$ alone guarantees nothing when the [events](#def-b2-proba-space) pile up on a shrinking part of the space — [independence](#def-b2-proba-independence) is what forbids that conspiracy.

**Exercise 21.9 ★.**

A coin with head probability $p \in \intoo01$ is tossed until the first head. Compute the probability that this happens at an odd rank, and evaluate it for a fair coin.

**Solution of Exercise 21.9.**

With $q = 1 - p$, the first head falls at rank $2j + 1$ with probability $q^{2j}p$, so

$$
\P(\text{odd rank}) = \sum_{j\geq0}q^{2j}p
= \frac{p}{1 - q^2} = \frac{1}{1 + q} .
$$

For a fair coin: $\frac1{1 + 1/2} = \frac23$. (Sanity check: odd ranks should be likelier, since rank $1$ comes first — and indeed $\frac1{1+q} > \frac12$ always.)

**Exercise 21.10 ★★.**

Let $(A_n)_{n\geq1}$ be [independent events](#def-b2-proba-independence) with $\P(A_n) =
p_n < 1$. Show that

$$
\P\Bigl(\bigcap_{n\geq1}A_n^c\Bigr)
= \prod_{n\geq1}(1 - p_n)
:= \lim_{N\to\infty}\prod_{n=1}^N(1 - p_n),
$$

and that this limit is $> 0$ if and only if $\sum p_n <
\infty$. Reconcile with Borel–Cantelli: when $\sum p_n =
\infty$, not only does some $A_n$ occur almost surely — infinitely many do.

**Solution of Exercise 21.10.**

The [events](#def-b2-proba-space) $B_N = \bigcap_{n=1}^N A_n^c$ decrease to $\bigcap_nA_n^c$, and by [independence](#def-b2-proba-independence) of the complements $\P(B_N) = \prod_{n=1}^N(1 - p_n)$; monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ([Theorem 21.6](#thm-b2-proba-continuity)) gives the displayed limit. Taking logarithms, $\prod(1 - p_n) > 0$ iff $\sum-\ln(1 -
p_n) < \infty$. If $\sum p_n < \infty$ then $p_n \to 0$ and $-\ln(1 - p_n) \sim p_n$: the log-series converges. If $\sum p_n = \infty$, then $-\ln(1 - p_n) \geq p_n$ forces divergence, so the product is $0$. This matches Borel–Cantelli 2: for $\sum p_n = \infty$, not only is $\P(\text{no }A_n\text{ occurs}) = 0$, but almost surely infinitely many $A_n$ occur.

**Exercise 21.11 ★★.**

(Banach’s matchbox) A smoker keeps one box of $n$ matches in each pocket and reaches into a uniformly random pocket each time. When he first finds a box empty, what is the probability that the other box contains exactly $k$ matches? Show the answer is $\binom{2n-k}{n}2^{-(2n-k)}$ and check that these probabilities sum to $1$ for $n = 1$.

**Solution of Exercise 21.11.**

Say box $A$ is the one first discovered empty, with the other box holding $k$. This means: among the first $2n - k$ reaches, exactly $n$ went to $A$ and $n - k$ to $B$ (in some order), and reach number $2n - k + 1$ went to $A$ again, finding it empty. The reaches are [independent](#def-b2-proba-independence) fair choices, so this [event](#def-b2-proba-space) has probability $\binom{2n-k}{n}2^{-(2n-k)}\cdot\frac12$; doubling (the empty box can be either one) gives

$$
\P(\text{other box has }k) = \binom{2n-k}{n}\,2^{-(2n-k)} .
$$

For $n = 1$: $k = 1$ gives $\binom11 2^{-1} = \frac12$ and $k
= 0$ gives $\binom21 2^{-2} = \frac12$: total $1$, as it must be.

**Exercise 21.12 ★★★.**

($\sigma$-additivity is a real axiom) (a) Show that there is no [probability measure](#def-b2-proba-space) on $(\N,
\mathcal P(\N))$ giving all singletons the same weight. (b) For $A \subseteq \N^*$, let $d(A) =
\lim_n\frac{\abs{A\cap\intint1n}}{n}$ when the limit exists (the *natural density*). Show $d$ is finitely additive on pairs where all three densities exist, gives every singleton density $0$ and $\N^*$ density $1$ — and conclude that $d$ is not $\sigma$-additive. (c) Exhibit a set with no density. *(Alternate blocks $\intint{2^{2k}}{2^{2k+1}-1}$ in and out.)*

**Solution of Exercise 21.12.**

(a) If $\P(\{n\}) = c$ for all $n$, $\sigma$-additivity forces $1 = \sum_nc$: impossible, whether $c = 0$ (sum $0$) or $c > 0$ (sum infinite). There is no uniform probability on $\N$.

(b) If $A \cap B = \emptyset$ and $d(A)$, $d(B)$ exist, then $\abs{(A \sqcup B)\cap\intint1n} = \abs{A\cap\intint1n} +
\abs{B\cap\intint1n}$, so $d(A \sqcup B) = d(A) + d(B)$: finite additivity on such pairs. Each singleton has counting function eventually constant, so density $0$, while $d(\N^*) = 1$. Were $d$ $\sigma$-additive, $\N^* =
\bigsqcup_k\{k\}$ would give $1 = \sum_k 0 = 0$: density is finitely additive but not $\sigma$-additive — the axiom has content.

(c) Let $A = \bigcup_{k\geq0}\intint{4^k}{2\cdot4^k - 1}$ (blocks from $4^k$ to $2\cdot4^k - 1$). At $n = 2\cdot4^K -
1$ the count is $\sum_{k\leq K}4^k \sim \frac43 4^K$, giving ratio $\to \frac23$; at $n = 4^{K+1} - 1$ the count is unchanged, giving ratio $\to \frac13$. The ratio oscillates between limits $\frac13$ and $\frac23$: no density.

## 21.5 Problem: the simple random walk on $\Z$ is recurrent

![Twenty-four steps of a simple random walk; the red dots mark the returns to the origin. The problem shows that, with probability 1, these dots never stop appearing — yet the waiting time between them has divergent mean.](https://one-course.com/images/onecourse/chapters/math-4/b2-proba/fig-1c561d473a2b.svg)

*Twenty-four steps of a [simple random walk](#pb-b2-proba-1); the red dots mark the returns to the origin. The problem shows that, with probability $1$, these dots never stop appearing — yet the waiting time between them has divergent mean.*

**Problem 21.1.**

Weekend problem — Pólya’s recurrence theorem on $\Z$, with the ballot problem and the arcsine flavor on the way

Toss a fair coin forever; let $X_i = \pm1$ be the $i$-th step and $S_n = X_1 + \dots + X_n$ the *simple random walk* on $\Z$, $S_0 = 0$. As in [Example 21.26](#ex-b2-proba-runs), all [events](#def-b2-proba-space) below are determined by finitely many tosses or are [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) combinations of such [events](#def-b2-proba-space), and [independence](#def-b2-proba-independence) of [events](#def-b2-proba-space) depending on disjoint blocks of tosses is part of the model. We write $u_n =
\P(S_{2n} = 0)$ and $N_n(k)$ for the number of $\pm1$-paths of length $n$ from $0$ to $k$.

**Part I — Counting paths.**

1. Show that $N_n(k) = \binom{n}{(n+k)/2}$ when $n + k$ is even and $\abs k \leq n$ , and $0$ otherwise; deduce $\P(S_n = k) = N_n(k)\,2^{-n}$ . Why is every individual path of length $n$ equally likely?
2. Show $S_{2n+1} \neq 0$ , $u_n =  \binom{2n}{n}4^{-n}$ , and compute $u_1, u_2, u_3$ .
3. Prove $u_n = \frac{2n-1}{2n}\,u_{n-1}$; deduce that $(u_n)$ decreases to $0$, and from [Example 6.14](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ex-b2-comparison-centralbinomial) that $$u_n \sim \frac{1}{\sqrt{\pi n}},  \qquad\text{so}\qquad  \sum_n u_n = \infty .$$
4. (Reflection principle) For $k \geq 1$ , show that the paths of length $n$ from $1$ to $k$ that touch $0$ are in bijection with the paths from $-1$ to $k$ ; deduce that the number of paths from $0$ to $k$ that stay $> 0$ after time $0$ is $N_{n-1}(k-1) -  N_{n-1}(k+1)$ .
5. (Ballot theorem) Deduce that $$\P\bigl(S_1 > 0, \dots, S_{n-1} > 0 \bigm| S_n =  k\bigr) = \frac kn \qquad (k \geq 1) :$$ in a count where the winner leads by $k$ out of $n$ ballots, the probability the winner led throughout the count is $k/n$. Verify by hand for $n = 3$, $k =  1$.

**Part II — Return to the origin.**

6. Prove the key identity $$\P(S_1 \neq 0,\ S_2 \neq 0,\ \dots,\ S_{2n} \neq 0) =  u_n$$ *(condition on the first step, sum the counts of question 4 over the endpoint, and telescope; finish with $2\binom{2n-1}{n} = \binom{2n}{n}$)*.
7. Deduce from monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ([Theorem 21.6](#thm-b2-proba-continuity)) that the walk returns to $0$ at least once with probability $1$, and that $f_n := \P(\text{first return at time }2n)$ satisfies $$f_n = u_{n-1} - u_n = \frac{u_n}{2n-1},  \qquad \sum_{n\geq1}f_n = 1 .$$
8. Show that $\sum_n 2n\,f_n = \infty$ : the return is certain, but the series that would compute the mean waiting time diverges (in the vocabulary of [Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar) , the return time has infinite expectation).
9. Prove that for every $k \geq 1$, $\P(\text{at least }  k\text{ returns to }0) = 1$ *(decompose over the times of the first $k$ returns: the corresponding toss blocks are disjoint, so the probabilities multiply and sum to $(\sum_nf_n)^k$)*; conclude with monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity): $$\P(S_n = 0 \text{ for infinitely many } n) = 1 :$$ the [simple random walk](#pb-b2-proba-1) on $\Z$ is *recurrent*.
10. Show that the walk visits every site $k \in \Z$ almost surely, hence (by recurrence, restarted at the first visit) infinitely often. *(The signs of the successive excursions from $0$ are [independent](#def-b2-proba-independence) fair coins; a positive excursion visits $1$.)*

**Part III — Borel–Cantelli and the biased walk.**

11. The [events](#def-b2-proba-space) $A_n = \{S_{2n} = 0\}$ satisfy $\sum\P(A_n)  = \infty$ ; explain why Borel–Cantelli 2 does *not* apply to them, and what Borel–Cantelli 1 would give if the series converged. (This is the strategy of the whole Part.)
12. Now let the coin have bias $p \neq \frac12$ , $q = 1 -  p$ . Show $\P(S_{2n} = 0) = \binom{2n}n(pq)^n =  u_n\,(4pq)^n$ with $4pq < 1$ , deduce $\sum_n\P(S_{2n} = 0) < \infty$ , and conclude by Borel–Cantelli 1 that the biased walk returns to $0$ only finitely many times, almost surely.
13. Still for $p \neq \frac12$ : show $\P(S_n = k) \leq  \binom{n}{\floor{n/2}}\,(pq)^{n/2}\,(p/q)^{k/2}$ for each fixed $k$ , deduce that every site is visited finitely often almost surely, and conclude $\abs{S_n} \to \infty$ almost surely: the biased walk is *transient* .
14. Back to the fair coin: using question 6, compute the probability that $200$ tosses produce *no* tie ( $S_n \neq 0$ for $1 \leq n \leq 200$ ), numerically $u_{100} \approx 0.056$ . Comment on the slow $1/\sqrt{\pi n}$ decay: ties are certain in the long run but rarer than intuition suggests.
15. (First passage) Let $T_1$ be the first time the walk hits $1$ . Using the reflection principle for the maximum $M_n = \max_{i\leq n}S_i$ (proved in question 16, which does not depend on this one), or directly from question 7 by conditioning on the first step, show $\P(T_1 = 2n - 1) = f_n$ ; deduce $\P(T_1 <  \infty) = 1$ while the mean-time series $\sum(2n-1)f_n$ diverges.

**Part IV — Maxima, last zero, long leads.**

16. (Reflection for the maximum) For $k \geq 1$, prove $$\P(M_n \geq k) = 2\,\P(S_n > k) + \P(S_n = k)$$ by reflecting the path after its first visit to level $k$.
17. Deduce $\P(M_{2n} \geq 1) = 1 - u_n$ , i.e. $\P(S_i \leq 0 \text{ for all } i \leq 2n) = u_n$ : the probability of never being ahead equals the probability of never being at zero (question 6) — two different [events](#def-b2-proba-space) , one probability.
18. (Last zero) Let $L_{2n} = \max\{k \leq 2n : S_k =  0\}$ (even). Combining question 6 with [independence](#def-b2-proba-independence) of disjoint toss blocks, show $$\P(L_{2n} = 2k) = u_k\,u_{n-k}  \qquad (0 \leq k \leq n),$$ and deduce, with no further computation, the binomial identity $\sum_{k=0}^n u_ku_{n-k} = 1$.
19. Show that the law of $L_{2n}$ is [symmetric](https://one-course.com/books/math/4/en/chapter/12-quadratic-forms#def-b2-quadratic-adjoint) ( $\P(L =  2k) = \P(L = 2n - 2k)$ ) and, using $u_j \sim  1/\sqrt{\pi j}$ , that its extremes are its most likely values. Tabulate for $n = 5$ : $\P(L_{10} = 0)  = u_5 \approx 0.246$ versus $\P(L_{10} = 4) = u_2u_3  \approx 0.117$ . Interpret: in a long fair game, the last tie tends to be very early or very late — long leads are the rule, not the exception.
20. Assemble questions 16–19 into a paragraph on the fluctuation picture of the fair walk: the diffusive scale suggested by question 3, the certainty of return against the divergent mean waiting time, and the arcsine-flavored persistence of leads.

**Part V — The renewal identity and Pólya’s theorem.**

21. Prove, by partitioning $\{S_{2n} = 0\}$ over the time of the first return, the *renewal identity* $$u_n = \sum_{k=1}^n f_k\,u_{n-k} \quad (n \geq 1),  \qquad\text{hence}\qquad  U(x)\bigl(1 - F(x)\bigr) = 1 \quad (0 \leq x < 1),$$ where $U(x) = \sum_{n\geq0}u_nx^n$ and $F(x) =  \sum_{n\geq1}f_nx^n$ (justify the radii and the product of series with [Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)).
22. Deduce the *recurrence dichotomy*: letting $x  \to 1^-$ (monotone limits of series with nonnegative coefficients), $$\sum_n u_n = \infty \iff \sum_n f_n = 1 ,$$ and check it against questions 3, 7 (fair walk) and 12 (biased walk).
23. (Dimension $2$) The simple walk on $\Z^2$ takes steps $(\pm1, 0)$, $(0, \pm1)$ uniformly. Show that the rotated coordinates $U_n = X_n + Y_n$ and $V_n = X_n  - Y_n$ perform *[independent](#def-b2-proba-independence)* fair walks on $\Z$, deduce $$\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim  \frac1{\pi n},  \qquad \sum_n u_n^2 = \infty ,$$ and conclude with questions 21–22 (whose proofs transfer verbatim) that the walk on $\Z^2$ is recurrent.
24. (Dimension $3$ ) For the simple walk on $\Z^3$ , admit the local estimate $\P(S^{(3)}_{2n} = 0) \leq  C\,n^{-3/2}$ (proved with the local limit theorem in the Year 3 volume). Deduce from Borel–Cantelli 1 that the walk on $\Z^3$ is transient, and state the full result: *Pólya’s theorem* — the [simple random walk](#pb-b2-proba-1) is recurrent in dimensions $1$ and $2$ , transient in dimension $3$ and higher.
25. Synthesis. List the exact role played by: path counting and reflection; monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) ; [independence](#def-b2-proba-independence) of disjoint toss blocks; Borel–Cantelli 1; the renewal identity. Which single [analytic](https://one-course.com/books/math/4/en/chapter/11-power-series#def-b2-powerseries-analytic) fact ( $u_n \sim 1/\sqrt{\pi n}$ , hence $\sum u_n = \infty$ but $\sum u_n^2 = \infty$ and $\sum n^{-3/2} < \infty$ ) decides between recurrence and transience in each dimension?

**Solution of Problem 21.1.**

**1.** A path of length $n$ is determined by the set of its up-steps; ending at $k$ means $u$ up-steps and $n - u$ down-steps with $u - (n - u) = k$, i.e. $u = \frac{n+k}2$: possible iff $n + k$ is even and $\abs k \leq n$, in $\binom{n}{(n+k)/2}$ ways. Each specific path is one point of the fair product measure on $n$ tosses: probability $2^{-n}$. Hence $\P(S_n = k) = N_n(k)2^{-n}$.

**2.** $S_n$ has the parity of $n$, so $S_{2n+1} \neq
0$; and $u_n = N_{2n}(0)4^{-n} = \binom{2n}n4^{-n}$. Values: $u_1 = \frac12$, $u_2 = \frac6{16} = \frac38$, $u_3 =
\frac{20}{64} = \frac5{16}$.

**3.** $\dfrac{u_n}{u_{n-1}} =
\dfrac{\binom{2n}n}{4\binom{2n-2}{n-1}} =
\dfrac{(2n)(2n-1)}{4n^2} = \dfrac{2n-1}{2n} < 1$: decreasing. By [Example 6.14](https://one-course.com/books/math/4/en/chapter/6-comparison-of-functions#ex-b2-comparison-centralbinomial), $\binom{2n}n \sim
\frac{4^n}{\sqrt{\pi n}}$, so $u_n \sim \frac1{\sqrt{\pi n}}
\to 0$, and $\sum u_n$ diverges by comparison with $\sum
n^{-1/2}$.

**4.** Given a path from $1$ to $k$ touching $0$, reflect its initial segment (up to the *first* visit to $0$) through the horizontal axis: the result is a path from $-1$ to $k$, and the operation is an involution — every path from $-1$ to $k \geq 1$ must cross $0$, and reflecting its initial segment back recovers the original. Hence the touching paths number $N_{n-1}(k + 1)$ (from $-1$ to $k$ the displacement is $k + 1$). A path from $0$ to $k$ staying $>
0$ after time $0$ starts with an up-step and then goes from $1$ to $k$ in $n - 1$ steps without touching $0$: there are $N_{n-1}(k-1) - N_{n-1}(k+1)$ of them.

**5.** With $m = \frac{n+k}2$, using $\binom{n-1}{m-1} = \frac mn\binom nm$ and $\binom{n-1}{m} =
\frac{n-m}n\binom nm$:

$$
\frac{N_{n-1}(k-1) - N_{n-1}(k+1)}{N_n(k)}
= \frac{\binom{n-1}{m-1} - \binom{n-1}{m}}{\binom nm}
= \frac{m - (n - m)}{n} = \frac kn .
$$

For $n = 3$, $k = 1$: $N_3(1) = 3$ paths ($++-$, $+-+$, $-++$), of which only $++-$ stays positive ($+-+$ returns to $0$ at time $2$): one out of three, and $\frac kn = \frac13$.

**6.** By symmetry the probability is $2\P(S_i > 0\ \forall
i \leq 2n)$. Summing over the endpoint $2k$ and using question 4 (with $n$ replaced by $2n$):

$$
\P(S_i > 0\ \forall i) = 2^{-2n}\sum_{k\geq1}
\bigl(N_{2n-1}(2k-1) - N_{2n-1}(2k+1)\bigr)
= 2^{-2n}\,N_{2n-1}(1),
$$

a telescoping sum. Now $N_{2n-1}(1) = \binom{2n-1}{n}$ and $2\binom{2n-1}n = \binom{2n}n$ (Pascal), so the displayed probability is $2\cdot2^{-2n}\binom{2n-1}n =
\binom{2n}n4^{-n} = u_n$.

**7.** The [events](#def-b2-proba-space) $D_n = \{S_i \neq 0,\ i \leq 2n\}$ decrease, with intersection “no return ever”; by monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) and question 6, $\P(\text{no return}) = \lim u_n =
0$: the walk returns almost surely. Moreover $f_n = \P(D_{n-1})
- \P(D_n) = u_{n-1} - u_n$, and by question 3

$$
u_{n-1} - u_n = u_n\Bigl(\frac{2n}{2n-1} - 1\Bigr) =
\frac{u_n}{2n-1};
\qquad
\sum_{n\geq1}f_n = u_0 - \lim u_n = 1 .
$$

**8.** $2n\,f_n = \frac{2n}{2n-1}u_n \geq u_n$, and $\sum u_n = \infty$ (question 3): the series $\sum 2nf_n$ diverges. The first return is certain but has no finite mean waiting time — the walk is *null recurrent*, in the vocabulary that [Chapter 22](https://one-course.com/books/math/4/en/chapter/22-discrete-random-variables#ch-b2-randomvar) will provide.

**9.** The [event](#def-b2-proba-space) “at least $k$ returns” is the disjoint [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) union, over $0 < n_1 < \dots < n_k$, of the [events](#def-b2-proba-space) “the first $k$ returns happen exactly at times $2n_1, \dots, 2n_k$”. Such an [event](#def-b2-proba-space) is the intersection of $k$ [events](#def-b2-proba-space) depending on the disjoint toss blocks $\intint1{2n_1}$, $\intint{2n_1+1}{2n_2}$, …, each block requiring a fresh walk to make its first return after exactly the allotted number of steps; by [independence](#def-b2-proba-independence) of the blocks its probability is $f_{n_1}f_{n_2-n_1}\cdots
f_{n_k-n_{k-1}}$. Summing by packets ([Chapter 7](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#ch-b2-series), all terms nonnegative):

$$
\P(\text{at least }k\text{ returns})
= \Bigl(\sum_{n\geq1}f_n\Bigr)^{\!k} = 1^k = 1 .
$$

The [events](#def-b2-proba-space) decrease in $k$, so by monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) $\P(\text{infinitely many returns}) = 1$: recurrence.

**10.** By question 9 the walk makes infinitely many excursions away from $0$. The first step of each excursion is a fresh coin, [independent](#def-b2-proba-independence) of everything before: the probability that the first $m$ excursions all start downward is $2^{-m}$. To reach $1$ the walk only needs one upward excursion start (from $<0$ it must pass through $0$ before reaching $1$, steps being $\pm1$), so $\P(\text{never hit }1)
\leq 2^{-m}$ for every $m$: the walk hits $1$ almost surely. Decomposing over the (almost surely finite) hitting time, the walk restarted there is a fresh walk started at $1$: by induction it hits every $k \geq 1$ almost surely, and by symmetry every $k \leq -1$. Finally, restarting at the first visit to $k$, question 9 applies to the fresh walk: every site is visited infinitely often, almost surely.

**11.** The [events](#def-b2-proba-space) $A_n = \{S_{2n} = 0\}$ are far from [independent](#def-b2-proba-independence) (being at $0$ at time $2n$ makes being at $0$ at time $2n + 2$ far likelier than $u_{n+1}$), so Borel–Cantelli 2 is unavailable, and indeed the whole work of Part II was to replace it. The other direction needs no [independence](#def-b2-proba-independence): *if* $\sum\P(A_n)$ converges, Borel–Cantelli 1 yields finitely many returns almost surely. That implication is the engine of every transience proof below.

**12.** A return at time $2n$ requires $n$ up- and $n$ down-steps: $\P(S_{2n} = 0) = \binom{2n}np^nq^n =
u_n(4pq)^n$, and $4pq = 1 - (p - q)^2 < 1$ for $p \neq
\frac12$. Since $u_n \leq 1$, the series $\sum\P(S_{2n} = 0)$ is dominated by the geometric $\sum(4pq)^n$: convergent. By Borel–Cantelli 1, $\P(S_{2n} = 0 \text{ infinitely often}) =
0$: finitely many returns, almost surely.

**13.** For $n + k$ even, $\P(S_n = k) =
\binom{n}{\frac{n+k}2}p^{\frac{n+k}2}q^{\frac{n-k}2}$; the binomial coefficient is at most the central one, and $p^{\frac{n+k}2}q^{\frac{n-k}2} = (pq)^{n/2}(p/q)^{k/2}$, giving the stated bound $\leq
2^n(pq)^{n/2}(p/q)^{k/2} = (4pq)^{n/2}(p/q)^{k/2}$, [summable](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#def-b2-series-summable) in $n$ since $\sqrt{4pq} < 1$. Borel–Cantelli 1: site $k$ is visited finitely often almost surely; the union over $k \in
\Z$ of the exceptional null [events](#def-b2-proba-space) is still null ([countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) subadditivity). Almost surely every site is visited finitely often, so the integer sequence $(S_n)$ leaves every bounded window for good: $\abs{S_n} \to \infty$.

**14.** $\P(S_n \neq 0,\ 1 \leq n \leq 200) = u_{100} =
\binom{200}{100}4^{-100} \approx \frac1{\sqrt{100\pi}}
\approx 0.056$: more than a one-in-twenty chance that $200$ fair tosses never tie. The decay $1/\sqrt{\pi n}$ is excruciatingly slow: certainty of a tie (question 7) is compatible with very long tie-free stretches — a first taste of the arcsine phenomena of Part IV.

**15.** Condition on the first step. If $X_1 = +1$ then $T_1 = 1$, and $f_1 = \frac12$ matches. If $X_1 = -1$, the walk must climb from $-1$ to $1$; by the block decomposition, returning to $0$ for the first time at time $2n$ splits as: one step down, then a fresh walk started at $-1$ first reaching $0$ — equivalently a fresh walk first reaching $+1$ — in $2n - 1$ steps, or the symmetric event upward. Both signs contribute equally:

$$
f_n = 2\cdot\tfrac12\,\P(T_1 = 2n - 1) = \P(T_1 = 2n-1) .
$$

Hence $\P(T_1 < \infty) = \sum f_n = 1$, while $\sum_n(2n -
1)f_n = \sum_n u_n = \infty$ by question 7: the walk reaches $1$ almost surely, in infinite mean time.

**16.** Partition $\{M_n \geq k\}$ by the terminal value $S_n = m$. For $m \geq k$ the condition $M_n \geq k$ is automatic. For $m < k$, reflect the path after its *first* visit to level $k$: this is a bijection between $\{M_n \geq k, S_n = m\}$ and $\{S_n = 2k - m\}$ (every path ending at $2k - m > k$ visits $k$; reflecting back is the inverse). Hence

$$
\P(M_n \geq k)
= \sum_{m > k}\P(S_n = m) + \P(S_n = k)
+ \sum_{m < k}\P(S_n = 2k - m)
= 2\P(S_n > k) + \P(S_n = k).
$$

**17.** At even time $2n$ with $k = 1$: $\P(S_{2n} = 1)
= 0$ and $\P(S_{2n} > 1) = \P(S_{2n} \geq 2)$, so

$$
\P(M_{2n} \geq 1) = 2\P(S_{2n} \geq 2)
= \P(S_{2n} \geq 2) + \P(S_{2n} \leq -2)
= 1 - u_n .
$$

Thus $\P(S_i \leq 0\ \forall i \leq 2n) = u_n$: the walk never leads in the first $2n$ steps exactly as often as it never ties (question 6) — two quite different [events](#def-b2-proba-space), carried by the same $u_n$.

**18.** $\{L_{2n} = 2k\} = \{S_{2k} = 0\} \cap
\{\text{the walk of the tosses } 2k+1, \dots, 2n \text{ has
no zero}\}$. The two [events](#def-b2-proba-space) depend on disjoint toss blocks, so they are [independent](#def-b2-proba-independence); the first has probability $u_k$, the second $u_{n-k}$ by question 6 applied to the fresh $(2n-2k)$-step walk. Hence $\P(L_{2n} = 2k) = u_ku_{n-k}$. Since $L_{2n}$ takes exactly the values $0, 2, \dots, 2n$, these probabilities sum to $1$: $\sum_{k=0}^nu_ku_{n-k} = 1$, a binomial identity delivered by a probabilistic partition.

**19.** Symmetry is immediate: $u_ku_{n-k} =
u_{n-k}u_k$. As $u_j$ decreases in $j$, the product $u_ku_{n-k}$ is smallest for central $k$ and largest at the extremes $k \in \{0, n\}$, where it equals $u_n$; quantitatively $u_ku_{n-k} \approx \frac1{\pi\sqrt{k(n-k)}}$ in the bulk, against $u_n \approx \frac1{\sqrt{\pi n}}$ at the edges. For $n = 5$: $\P(L_{10} = 0) = \P(L_{10} = 10) =
u_5 = \frac{63}{256} \approx 0.246$, while $\P(L_{10} = 4) =
u_2u_3 = \frac38\cdot\frac5{16} = \frac{15}{128} \approx
0.117$. In a long fair game the last equalization is most likely near the very beginning or the very end: one player typically leads for enormous stretches, with no bias in the coin.

**20.** The picture: at time $n$ the walk lives at scale $\sqrt n$ (the binomial spread of question 3 — $u_n \sim
1/\sqrt{\pi n}$ is the height of the central peak); it returns to $0$ infinitely often with probability $1$ (Part II), yet the waiting time between returns has divergent mean (question 8), which is why single excursions can occupy a positive fraction of any horizon; correspondingly the last tie of a $2n$-step game is spread out with extreme values most likely (questions 18–19), and never-leading has the same slowly decaying probability $u_n$ as never-tying (question 17). Certainty in the limit, persistence at every finite horizon: that is the fair walk.

**21.** Partition $\{S_{2n} = 0\}$ ($n \geq 1$) by the first return time $2k$, $1 \leq k \leq n$: the first block of $2k$ tosses realizes a first return, the remaining $2n - 2k$ tosses realize a return of a fresh walk, and the blocks are [independent](#def-b2-proba-independence): $u_n = \sum_{k=1}^nf_ku_{n-k}$. Both series $U(x) = \sum u_nx^n$, $F(x) = \sum f_nx^n$ have radius $\geq
1$ (coefficients in $\intcc01$), and the [Cauchy product](https://one-course.com/books/math/4/en/chapter/7-sequences-and-series#thm-b2-series-fubini) ([Chapter 11](https://one-course.com/books/math/4/en/chapter/11-power-series#ch-b2-powerseries)) gives, for $0 \leq x < 1$,

$$
U(x) - 1 = \sum_{n\geq1}\Bigl(\sum_{k=1}^n
f_ku_{n-k}\Bigr)x^n = F(x)\,U(x),
\qquad\text{i.e.}\qquad
U(x)\bigl(1 - F(x)\bigr) = 1 .
$$

**22.** As $x \uparrow 1$, $U(x)$ and $F(x)$ increase (nonnegative coefficients); every partial sum $\sum_{n\leq
N}u_n$ is a limit of $\sum_{n\leq N}u_nx^n \leq U(x)$, so $U(x) \uparrow \sum u_n \in \intoc0{+\infty}$, and likewise $F(x) \uparrow f = \sum f_n$. If $\sum u_n = \infty$: $1 -
F(x) = 1/U(x) \to 0$, so $f = 1$. If $\sum u_n = S < \infty$: $1 - f = 1/S > 0$, so $f < 1$. Checks: fair walk, $\sum u_n =
\infty$ and $f = 1$ (questions 3, 7); biased walk, $\sum
u_n(4pq)^n < \infty$ and correspondingly $f = 1 -
1/\sum_{n\geq0}u_n(4pq)^n < 1$, consistent with the almost-sure finiteness of the number of returns (question 12).

**23.** For the four steps $(\pm1, 0), (0, \pm1)$ of the $\Z^2$ walk, the increments of $U = X + Y$ and $V = X - Y$ are: $(+,+)$ for $(1,0)$, $(+,-)$ for $(0,1)$, $(-,+)$ for $(0,-1)$, $(-,-)$ for $(-1,0)$ — each pair of signs with probability $\frac14 = \frac12\cdot\frac12$: the two coordinate walks $(U_n)$ and $(V_n)$ are [independent](#def-b2-proba-independence) fair walks on $\Z$. Since $S^{(2)}_{2n} = (0,0)$ iff $U_{2n} = 0$ and $V_{2n} = 0$,

$$
\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi
n}, \qquad \sum_nu_n^2 = \infty .
$$

The renewal identity of question 21 and the dichotomy of question 22 used nothing one-dimensional (only the decomposition over the first return and disjoint-block [independence](#def-b2-proba-independence)), so $\sum u_n^{(2)} = \infty$ gives $f^{(2)} =
1$, and the argument of question 9 upgrades it: the walk on $\Z^2$ returns to the origin infinitely often almost surely.

**24.** With the admitted bound $\P(S^{(3)}_{2n} = 0)
\leq Cn^{-3/2}$, the series converges, and Borel–Cantelli 1 gives finitely many returns almost surely: the walk on $\Z^3$ is transient (and the same bound with exponent $-d/2$ handles every $d \geq 3$). Altogether: *Pólya’s theorem* — the [simple random walk](#pb-b2-proba-1) is recurrent on $\Z$ and $\Z^2$, transient on $\Z^d$ for $d \geq 3$. A drunk man finds his way home; a drunk bird may not.

**25.** Path counting and reflection produced the exact laws ($u_n$, the ballot theorem, $f_n$, the maximum, the last zero); monotone [continuity](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#def-b2-metric-continuity) converted every limiting statement (“returns at least once”, “infinitely often”) into a limit of finite-horizon probabilities; disjoint-block [independence](#def-b2-proba-independence) powered the renewal decompositions (questions 9, 18, 21) — it is the [countable](https://one-course.com/books/math/4/en/chapter/1-sets-and-structures#def-b2-structures-countable) skeleton of the Markov property; Borel–Cantelli 1 was the transience weapon (questions 12–13, 24), needing no [independence](#def-b2-proba-independence); the renewal identity organized everything into the dichotomy $\sum u_n = \infty \iff$ recurrence. The single [analytic](https://one-course.com/books/math/4/en/chapter/11-power-series#def-b2-powerseries-analytic) input is the local estimate $u_n \sim 1/\sqrt{\pi
n}$: its square $1/(\pi n)$ still diverges (dimension $2$, recurrent), while $n^{-3/2}$ converges (dimension $3$, transient) — Pólya’s theorem is, in the end, a statement about the divergence of $\sum n^{-d/2}$.