Exercises

$A \cup B = \{2,3,4,5,6\}$. (Everything that is even OR greater than 2.) $\mathbb{P}(A \cup B) = 5/6$.

$A \cap B = \{4,6\}$. (Even AND greater than 2.) $\mathbb{P}(A \cap B) = 2/6 = 1/3$.

$A^c = \{1,3,5\}$ (odd outcomes). $A^c \cap B = \{3,5\}$. (Odd AND greater than 2.) $\mathbb{P}(A^c \cap B) = 2/6 = 1/3$.

De Morgan: $A^c \cup B^c = (A \cap B)^c = \{4,6\}^c = \{1,2,3,5\}$. $\mathbb{P}(A^c \cup B^c) = 4/6 = 2/3$.

Check via inclusion-exclusion: $\mathbb{P}(A^c) + \mathbb{P}(B^c) - \mathbb{P}(A^c \cap B^c) = 3/6 + 2/6 - 1/6 = 4/6$. $\checkmark$

$(1-p)^k p \geq 0$ for all $k$ since $p \in [0,1]$ implies $1-p \in [0,1]$. So $\mathbb{P}(H^k T) \geq 0$ for all $k$. $\checkmark$

$\mathbb{P}(\Omega) = \sum_{k=0}^{\infty} (1-p)^k p = p \sum_{k=0}^{\infty} (1-p)^k = \frac{p}{1-(1-p)} = \frac{p}{p} = 1.$$(Using the geometric series with ratio$|1-p| < 1$for$p \in (0,1)$.)$\checkmark$

For any event $A = \{H^{k_1}T, H^{k_2}T, \ldots\}$ (a subset of outcomes), countable additivity gives $\mathbb{P}(A) = \sum_{k \in A} (1-p)^k p$. This is consistent with the definition: the probability of any event is the sum of the probabilities of the outcomes it contains. $\checkmark$

Let $D = A \cup B$. By the two-set inclusion-exclusion: $\mathbb{P}(D \cup C) = \mathbb{P}(D) + \mathbb{P}(C) - \mathbb{P}(D \cap C)$. Also: $\mathbb{P}(D) = \mathbb{P}(A) + \mathbb{P}(B) - \mathbb{P}(A \cap B)$.

$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$. By the two-set formula: $\mathbb{P}((A \cap C) \cup (B \cap C)) = \mathbb{P}(A \cap C) + \mathbb{P}(B \cap C) - \mathbb{P}(A \cap B \cap C)$.

Substituting: $\mathbb{P}(A \cup B \cup C) = [\mathbb{P}(A) + \mathbb{P}(B) - \mathbb{P}(A \cap B)] + \mathbb{P}(C) - [\mathbb{P}(A \cap C) + \mathbb{P}(B \cap C) - \mathbb{P}(A \cap B \cap C)]$ which is exactly the stated formula. $\blacksquare$

$\mathbb{P}(A \cup B \cup C) = 0.3 + 0.4 + 0.2 - 0.1 - 0.05 - 0.08 + 0.02 = 0.69$.

For an increasing sequence: $\bigcup_{n=1}^{\infty} A_n = \lim_{n \to \infty} A_n$.

By the continuity of $\mathbb{P}$ for increasing sequences (TContinuity of Probability): $$\mathbb{P}\!\left(\bigcup_{n=1}^{\infty} A_n\right) = \lim_{n \to \infty} \mathbb{P}(A_n) = \lim_{n \to \infty} \left(1 - \frac{1}{n}\right) = 1.$$ $\blacksquare$

Let $E_k$ = "bit $k$ is flipped," $\mathbb{P}(E_k) = \epsilon$ for all $k$. By the union bound: $\mathbb{P}(\text{at least one error}) = \mathbb{P}(\bigcup_{k=1}^n E_k) \leq \sum_{k=1}^n \epsilon = n\epsilon$.

Since bits are flipped independently, $\mathbb{P}(\text{no errors}) = (1-\epsilon)^n$. Therefore: $\mathbb{P}(\text{at least one error}) = 1 - (1-\epsilon)^n$.

The union bound $n\epsilon$ is an upper bound: $1 - (1-\epsilon)^n \leq n\epsilon$ (from Bernoulli's inequality: $(1-\epsilon)^n \geq 1 - n\epsilon$).

The bound is tight when $\epsilon \ll 1/n$: in this regime, $1 - (1-\epsilon)^n \approx n\epsilon - \binom{n}{2}\epsilon^2 + \cdots \approx n\epsilon$. The union bound is loose when $\epsilon n \approx 1$ or larger, because pairwise overlaps $\mathbb{P}(E_i \cap E_j) = \epsilon^2$ become non-negligible.

$\sum_{n=1}^{\infty} 1/\sqrt{n} = \sum_{n=1}^{\infty} n^{-1/2}$. This is a $p$-series with $p = 1/2 < 1$, so it diverges. The first Borel-Cantelli lemma does NOT apply.

The second Borel-Cantelli lemma (not proved until Chapter 2) requires: (a) independence of the $A_n$, AND (b) $\sum \mathbb{P}(A_n) = \infty$. Condition (b) is satisfied. If the $A_n$ are also independent, the second lemma gives $\mathbb{P}(A_n \text{ i.o.}) = 1$.

Without independence, the divergence of $\sum \mathbb{P}(A_n)$ is insufficient: there exist dependent event sequences with $\sum \mathbb{P}(A_n) = \infty$ and $\mathbb{P}(A_n \text{ i.o.}) = 0$ (e.g., all $A_n = A$ for a fixed event $A$ with $\mathbb{P}(A) = 1/2$). So, with divergent sum but no independence: $\mathbb{P}(A_n \text{ i.o.})$ is unknown without additional information.

4 Aces in 52 cards. $\mathbb{P}(A_1) = 4/52 = 1/13$.

$\mathbb{P}(\text{both Aces}) = \frac{4}{52} \cdot \frac{3}{51} = \frac{12}{2652} = \frac{1}{221} \approx 0.00452$. Using the counting formula: $\frac{4 \cdot 3}{52 \cdot 51}$ (ordered selection of 2 Aces from 4, over all ordered pairs from 52).

$\mathbb{P}(\text{no Ace in first 5}) = \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48} = \frac{\binom{48}{5}}{\binom{52}{5}}$. $\binom{52}{5} = 2{,}598{,}960$, $\binom{48}{5} = 1{,}712{,}304$. $\mathbb{P}(\text{no Ace}) = 1{,}712{,}304/2{,}598{,}960 \approx 0.6588$. $\mathbb{P}(\text{at least one Ace}) = 1 - 0.6588 \approx 0.3412$.

Each position takes a value in an alphabet of size $q$, and there are $n$ positions: total = $q^n$ sequences.

A code with minimum distance $d$ can correct $t = \lfloor(d-1)/2\rfloor$ errors: if at most $t$ symbols are corrupted, the corrupted codeword is closer to the transmitted codeword than to any other.

The Hamming ball $B(\mathbf{c}, t)$ around codeword $\mathbf{c}$ contains all sequences at Hamming distance at most $t$ from $\mathbf{c}$. Its size is: $|B(\mathbf{c}, t)| = V_q(n, t) = \sum_{k=0}^{t}\binom{n}{k}(q-1)^k$. (Choose $k$ positions to change: $\binom{n}{k}$ ways; each changed position has $q-1$ possible non-original values: $(q-1)^k$ ways.)

The $M$ Hamming balls around the $M$ codewords are disjoint (by the minimum-distance assumption). Since all balls are subsets of $\{0,\ldots,q-1\}^n$: $M \cdot V_q(n,t) \leq q^n$, giving $M \leq q^n / V_q(n,t)$. $\blacksquare$

It suffices to show $\mathbb{P}(A_n \text{ i.o.})^c = \mathbb{P}(\bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k^c) = 0$. Let $C_n = \bigcap_{k=n}^{\infty} A_k^c$ (finitely many $A_k$ occur, starting from $n$). $\{C_n\}$ is an increasing sequence with $\bigcup C_n = \{A_n \text{ i.o.}\}^c$. By continuity: $\mathbb{P}(\{A_n \text{ i.o.}\}^c) = \lim_n \mathbb{P}(C_n)$.

$C_n = \bigcap_{k=n}^{\infty} A_k^c = \lim_{N \to \infty} \bigcap_{k=n}^{N} A_k^c$ (decreasing intersection). By continuity: $\mathbb{P}(C_n) = \lim_{N \to \infty} \mathbb{P}(\bigcap_{k=n}^{N} A_k^c)$.

By independence of $\{A_k^c\}$ (which follows from independence of $\{A_k\}$): $$\mathbb{P}\!\left(\bigcap_{k=n}^{N} A_k^c\right) = \prod_{k=n}^{N}(1-\mathbb{P}(A_k)) \leq \prod_{k=n}^{N} e^{-\mathbb{P}(A_k)} = \exp\!\left(-\sum_{k=n}^{N}\mathbb{P}(A_k)\right).$$ Since $\sum_{k=1}^{\infty} \mathbb{P}(A_k) = \infty$, the partial sum $\sum_{k=n}^{N} \mathbb{P}(A_k) \to \infty$ as $N \to \infty$. Hence $\mathbb{P}(C_n) = 0$ for all $n$, so $\mathbb{P}(\{A_n \text{ i.o.}\}^c) = 0$, giving $\mathbb{P}(A_n \text{ i.o.}) = 1$. $\blacksquare$

$\Omega = \{1, 2, 3\}$ (the door hiding the car). Under equal likelihood: $\mathbb{P}(\text{car at door } i) = 1/3$ for $i = 1,2,3$. You pick door 1; host opens door 3.

Staying with door 1 wins if and only if the car is behind door 1. $\mathbb{P}(\text{win} \mid \text{stay}) = \mathbb{P}(\text{car at 1}) = 1/3$.

Switching to door 2 wins if the car is NOT behind door 1, i.e., behind door 2 or 3. But the host opened door 3 (no car there), so switching wins exactly when the car is behind door 2. $\mathbb{P}(\text{win} \mid \text{switch}) = \mathbb{P}(\text{car at 2}) = 2/3$.

(More carefully: if car is at 2, host must open 3; if car is at 1, host can open 2 or 3 equally — but the problem conditions on door 3 being opened.)

Always switch. The switching strategy wins with probability $2/3$, double the staying strategy's $1/3$. The key insight: the host's action (opening a specific door with a goat) carries information about where the car is. When you picked door 1, the probability that the car is behind one of the OTHER doors was $2/3$; the host's action concentrates that $2/3$ probability onto door 2 alone.

$\mathbb{P}(\text{all distinct}) = \frac{365 \cdot 364 \cdots 336}{365^{30}} = \prod_{k=0}^{29}\left(1 - \frac{k}{365}\right) \approx 0.294$.

$\mathbb{P}(\text{at least one collision}) = 1 - 0.294 = 0.706$. With 30 people, there is about a 70.6% chance of a shared birthday.

This is a harder calculation (requires summing over which pair matches); the key result is that $\mathbb{P}(\text{at least one collision}) \approx 0.706$, which is dominated by the probability of exactly one collision for moderate $n$. The reader should verify using the exact formula from the Poisson approximation: $\mathbb{P}(\text{at least one collision}) \approx 1 - e^{-\binom{n}{2}/365}$. For $n=30$: $\binom{30}{2}/365 \approx 1.23$, giving $1 - e^{-1.23} \approx 0.708$, consistent with the exact answer.

By TGeneral Inclusion-Exclusion Formula: $\mathbb{P}(\bigcup_i A_i) = S_1 - S_2 + S_3 - S_4 + \cdots$ where $S_k = \sum_{i_1 < \cdots < i_k} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k})$.

Since all probabilities are non-negative, $S_3 \geq 0$. Therefore: $\mathbb{P}(\bigcup_i A_i) = S_1 - S_2 + S_3 - S_4 + \cdots \geq S_1 - S_2$ (dropping $S_3 - S_4 + \cdots \geq 0$, which requires showing this alternating tail is non-negative — proved by the full Bonferroni inequalities theorem). The simpler argument: $S_1 - S_2 + S_3 \geq S_1 - S_2$ because $S_3 \geq 0$, and by the upper bound $\mathbb{P}(\bigcup A_i) \leq S_1 - S_2 + S_3$. Combined, $S_1 - S_2 \leq \mathbb{P}(\bigcup A_i) \leq S_1 - S_2 + S_3$. $\blacksquare$

Unordered selection without replacement: $\binom{6}{2} = 15$ pairs.

$\mathbb{P}(\{1,3\}) = 1/\binom{6}{2} = 1/15 \approx 0.067$.

$(\bigcap_{n=1}^{\infty} A_n)^c = \bigcup_{n=1}^{\infty} A_n^c$. By complementation: $\mathbb{P}(\bigcap A_n) = 1 - \mathbb{P}(\bigcup A_n^c)$.

$\mathbb{P}(\bigcup A_n^c) \leq \sum \mathbb{P}(A_n^c)$. Therefore: $\mathbb{P}(\bigcap A_n) = 1 - \mathbb{P}(\bigcup A_n^c) \geq 1 - \sum \mathbb{P}(A_n^c)$. $\blacksquare$

Application: If each $A_n$ holds with probability at least $1 - \epsilon_n$, and $\sum \epsilon_n < 1$, then all events hold simultaneously with positive probability. This is used in coding theory to show the existence of codes achieving both rate and reliability simultaneously.

A path of length $2n$ from 0 back to 0 takes $n$ steps of $+1$ and $n$ steps of $-1$. Total such paths: $\binom{2n}{n}$. Of these, the "first return at step $2n$" paths are those that do NOT touch 0 at any intermediate even step. By the cycle lemma, the number of paths from $+1$ to $+1$ in $2n-2$ steps that remain positive is $\frac{1}{n-1}\binom{2n-2}{n-1}$ (the $(n-1)$-th Catalan number). Combined with the first step being $+1$ or $-1$: $C_n = \frac{1}{n}\binom{2(n-1)}{n-1}$.

$\binom{2(n-1)}{n-1} = \frac{(2n-2)!}{((n-1)!)^2}$. By Stirling: $(2n-2)! \approx \sqrt{4\pi(n-1)}((2n-2)/e)^{2n-2}$ and $(n-1)! \approx \sqrt{2\pi(n-1)}((n-1)/e)^{n-1}$. So $\binom{2(n-1)}{n-1} \approx \frac{4^{n-1}}{\sqrt{\pi(n-1)}}$. Hence $C_n \approx \frac{4^{n-1}}{n\sqrt{\pi(n-1)}} \approx \frac{4^{n-1}}{\sqrt{\pi}n^{3/2}}$.

$\mathbb{P}(\text{first return at step } 2n) = C_n \cdot (1/2)^{2n}$. Summing over all $n$: $\mathbb{P}(\text{ever return}) = \sum_{n=1}^{\infty} \frac{C_n}{4^n}$. From (a): $C_n = \frac{1}{n}\binom{2(n-1)}{n-1}$. Substituting and using the generating function of Catalan numbers: $\sum_{n=1}^{\infty} \frac{1}{n}\binom{2(n-1)}{n-1} 4^{-n} = 1/2$.

So the 1D symmetric random walk returns to 0 with probability $\sum C_n/4^n = 1/2$, meaning it is NOT recurrent in the strict sense (probability 1 of return). Actually, the full analysis shows that the walk IS recurrent (probability 1 of eventual return), since the sum over ALL returns $\sum_{n=1}^{\infty} \binom{2n}{n}/4^n$ diverges — this is the Pólya recurrence theorem (Chapter 17).