Exercises

$R_s = R_1 \cdot R_2 = 0.95 \times 0.90 = 0.855.$

After upgrade: $R_s' = 0.95 \times 0.99 = 0.9405.$ Improvement: $R_s' - R_s = 0.9405 - 0.855 = 0.0855$, a relative increase of $10\%$. The upgrade to the weaker stage has a large effect because the second stage is the bottleneck.

$R_s = 1 - (1-0.8)^3 = 1 - 0.2^3 = 1 - 0.008 = 0.992.$

Solve $0.2^n \leq 10^{-4}$: $n \geq \log(10^{-4})/\log(0.2) = 4/\log_2(5) \approx 4/2.322 \approx 1.72$. Since $0.2^2 = 0.04 > 10^{-4}$ and $0.2^3 = 0.008 < 10^{-4}$... check: $0.2^3 = 8 \times 10^{-3} > 10^{-4}$, $0.2^4 = 1.6\times 10^{-3} > 10^{-4}$, $0.2^5 = 3.2 \times 10^{-4} > 10^{-4}$, $0.2^6 = 6.4 \times 10^{-5} < 10^{-4}$. So $n = 6$ transponders yield $R_s = 1 - 0.2^6 = 1 - 6.4 \times 10^{-5} \approx 0.99994.$

$P(\text{no collision}) = \frac{50}{50} \cdot \frac{49}{50} \cdot \frac{48}{50} \cdot \frac{47}{50} \cdot \frac{46}{50} \cdot \frac{45}{50} \cdot \frac{44}{50} = \frac{50!/(50-7)!}{50^7} = \frac{50 \cdot 49 \cdots 44}{50^7}.$$Numerically:$0.98 \times 0.96 \times 0.94 \times 0.92 \times 0.90 \times 0.88 \approx 0.605.$

$P(\text{collision}) = 1 - 0.605 = 0.395 \approx 39.5\%.$ Even with only 7 people and 50 possible birthdays ($n/7 \approx 7$), a collision is almost 40% likely.

Each player plays $n-1$ matches. In a uniformly random tournament (each match decided by a fair coin), $\mathbb{E}[W_i] = (n-1)/2$ for every player $i$ (each match is a 50-50 coin flip for $W_i$).

The total wins sum to $\binom{n}{2}$ (one per match), so the average wins per player is $\binom{n}{2}/n = (n-1)/2$. Some player must have wins $\geq \lceil(n-1)/2\rceil$ (the ceiling of the average). This player is the answer. $\blacksquare$

$H_6 = 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 = 60/60 + 30/60 + 20/60 + 15/60 + 12/60 + 10/60 = 147/60 = 2.45.$

$\mathbb{E}[T_6] = 6 \times 2.45 = 14.7$ rolls on average. Intuitively, the first new face comes on the first roll, the last new face takes $6/1 = 6$ rolls on average — the last few faces are hard to get.

Let $S \sim \text{Bin}(n,p)$ be the number of working components. $$R_s = P(S \geq k) = \sum_{j=k}^n \binom{n}{j} p^j (1-p)^{n-j}.$$

$k=1$ (at least 1 works): $R_s = 1 - 0.1^5 = 0.99999$. $k=3$ (majority): $R_s = \binom{5}{3}0.9^3\cdot 0.1^2 + \binom{5}{4} 0.9^4 \cdot 0.1 + 0.9^5 = 10(0.729)(0.01) + 5(0.6561)(0.1) + 0.59049$ $= 0.0729 + 0.32805 + 0.59049 = 0.99144$. $k=5$ (all work): $R_s = 0.9^5 = 0.59049$.

$k=n$: $R_s = \binom{n}{n}p^n(1-p)^0 = p^n$ — series formula. $k=1$: $R_s = 1 - \binom{n}{0}p^0(1-p)^n = 1-(1-p)^n$ — parallel formula. $\blacksquare$

The events $(A_1 \cup A_2)$ and $(A_3 \cup A_4)$ are independent because the four components are independent. Therefore $$R_s = P(A_1 \cup A_2) \cdot P(A_3 \cup A_4).$$

$P(A_1 \cup A_2) = 1 - (1-p)^2 = 2p - p^2$ (same for pair 2).

$R_s = (2p-p^2)^2 = 4p^2 - 4p^3 + p^4.$ At $p = 0.9$: $R_s = 4(0.81) - 4(0.729) + 0.6561 = 3.24 - 2.916 + 0.6561 = 0.9801.$

For each pair $(i,j)$ with $i < j$, let $X_{ij} = \mathbf{1}\{d_i = d_j\}$ where $d_i$ is the $i$-th draw. Since draws are i.i.d.\ uniform over $\{1,\ldots,n\}$: $\mathbb{E}[X_{ij}] = 1/n$.

$\mathbb{E}[Z] = \sum_{1 \leq i < j \leq m} 1/n = \binom{m}{2}/n = m(m-1)/(2n).$ For $m = 23$, $n = 365$: $\mathbb{E}[Z] = 253/365 \approx 0.693.$

By the first Bonferroni inequality, $P(\text{collision}) = P(Z \geq 1) \geq \mathbb{E}[Z]/(1 + \mathbb{E}[Z])$ (using $P(Z \geq 1) \geq \mathbb{E}[Z]^2/\mathbb{E}[Z^2]$ with the second moment method). The simpler first-moment bound: $$P(\text{no collision}) \leq 1 - \mathbb{E}[Z] + \ldots$$ is not directly Markov, but the exact result shows the Poisson approximation: $P(\text{no collision}) \approx e^{-\mathbb{E}[Z]}$.

The probability that a specific coupon $j$ is missed in $t$ draws (each i.i.d.\ uniform over $n$ types): $P(j \text{ not seen after } t \text{ draws}) = (1-1/n)^t \leq e^{-t/n}.$

$P(T_n > t) = P(\exists j: j \text{ not seen after } t \text{ draws}) \leq \sum_{j=1}^n e^{-t/n} = n \cdot e^{-t/n}.$

$P(T_n > n\ln n + cn) \leq n \cdot e^{-(n\ln n + cn)/n} = n \cdot e^{-\ln n} \cdot e^{-c} = n \cdot (1/n) \cdot e^{-c} = e^{-c}. \quad \blacksquare$

Each slot is a draw of one user uniformly from 20. We need all 20 users to appear at least once. Treating each slot as one draw (there are $20$ slots per frame, i.e., $20$ draws per frame): $\mathbb{E}[T_{20}] = 20 H_{20} \approx 20 \times 3.598 = 71.95$ total slot draws. With 20 slots per frame, this is $\lceil 71.95/20 \rceil = 4$ frames expected.

50 frames $\times$ 20 slots = 1000 total slot draws. Probability user 7 is never chosen: $(1 - 1/20)^{1000} = 0.95^{1000} = e^{1000 \ln 0.95} \approx e^{-51.3} \approx 10^{-22}.$ After 50 frames, it is virtually certain every user has been scheduled.

$R_s = 3p^2(1-p) + p^3 = 3p^2 - 3p^3 + p^3 = 3p^2 - 2p^3.$

$3p^2 - 2p^3 > p \iff 3p^2 - 2p^3 - p > 0 \iff p(3p - 2p^2 - 1) > 0.$ Factoring $3p - 2p^2 - 1 = -(2p^2 - 3p + 1) = -(2p-1)(p-1)$. So the inequality is $p \cdot (-(2p-1)(p-1)) > 0$, i.e., $-(2p-1)(p-1) > 0$ for $p > 0$, which holds when $(2p-1)(p-1) < 0$, i.e., $1/2 < p < 1$. Majority vote beats a single unit whenever $p > 1/2$.

Single unit: $0.7$. Majority ($k=2$): $3(0.49) - 2(0.343) = 1.47 - 0.686 = 0.784$. Series ($k=3$): $0.343$. Majority provides a substantial improvement over a single unit when components are better than chance.

$P(\text{bin } j \text{ empty}) = (1-1/n)^m$ since each of the $m$ balls independently avoids bin $j$ with probability $(n-1)/n$.

By symmetry and linearity: $\mathbb{E}[\text{empty bins}] = n \cdot (1-1/n)^m.$

$n(1-1/n)^n \to n/e \approx 0.368\,n$ for large $n$. So when the number of balls equals the number of bins, about 37% of bins are empty on average. Equivalently, 63% of bins are occupied — far from full coverage.

From the worked example, $R_s(p) = 2p^2 + 2p^3 - 5p^4 + 2p^5$.

$R_s(0) = 0$ (all terms vanish). $R_s(1) = 2+2-5+2 = 1$. $\checkmark$

$R_s(0.9) = 2(0.81)+2(0.729)-5(0.6561)+2(0.59049)$ $= 1.62 + 1.458 - 3.2805 + 1.18098 = 0.97848$. $R_\text{series}(0.9) = 0.9^5 = 0.59049$. $R_\text{parallel}(0.9) = 1-0.1^5 = 0.99999$. Here $R_\text{parallel} > R_\text{bridge} > R_\text{series}$. The bridge network is intermediate: the cross-link adds robustness over a pure series chain but is less redundant than a full parallel system.

Fix a set $S$ of $k$ vertices. There are $\binom{k}{2}$ edges among them. $P(\text{all red}) = 2^{-\binom{k}{2}}$ and $P(\text{all blue}) = 2^{-\binom{k}{2}}$, so $P(\text{monochromatic}) = 2 \cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}.$

$P(\exists \text{ monochromatic } K_k) \leq \binom{n}{k} \cdot 2^{1-\binom{k}{2}}.$

If $\binom{n}{k} \cdot 2^{1-\binom{k}{2}} < 1$, the union bound gives $P < 1$, so there exists a coloring with NO monochromatic $K_k$. This means $n < R(k,k)$. Using $\binom{n}{k} \leq n^k/k!$ and $\binom{k}{2} = k(k-1)/2$: $$\frac{n^k}{k!} \cdot 2^{1-k(k-1)/2} < 1 \implies n < k! \cdot 2^{k(k-1)/2-1}.$$ For large $k$, $R(k,k) > 2^{k/2}$ follows (since $k! \cdot 2^{-1} \geq 1$ for $k \geq 2$, and more careful analysis gives the $2^{k/2}$ bound). $\blacksquare$

Let $N = \sum_{i=1}^n \mathbf{1}_{A_i}$ count the number of events that occur. We want $P(N = k) = \mathbb{E}[\mathbf{1}_{N=k}]$. The key identity is: $$\mathbf{1}_{N=k} = \sum_{j=k}^{n} (-1)^{j-k}\binom{j}{k} \sum_{|J|=j}\mathbf{1}_{\bigcap_{j \in J} A_j}.$$

Taking expectations: $$P(N=k) = \sum_{j=k}^{n} (-1)^{j-k}\binom{j}{k} S_j,$$ where $S_j = \sum_{|J|=j} P(\bigcap_{i \in J} A_i)$.

$P(N=0) = \sum_{j=0}^{n}(-1)^j S_j$ — this is the inclusion-exclusion formula for $P(\text{none of } A_1, \ldots, A_n)$. $\blacksquare$

By Chebyshev's inequality with $\mu = \mathbb{E}[T_n]$: $$P(|T_n - \mu| \geq t) \leq \frac{\text{Var}(T_n)}{t^2} \leq \frac{\pi^2 n^2/6}{t^2}.$$

$P(|T_{100} - \mu| \geq 100) \leq \pi^2/6 \approx 1.645.$ This bound exceeds 1 — it is vacuous! Chebyshev's inequality provides no information in this case.

The Chebyshev bound is only useful when $t \gg n$ (e.g., $t > n\pi/\sqrt{6} \approx 1.28n$). For tight concentration, one needs the sharper tail bound from Exercise 3.9 (union bound gives $P(T_n > n\ln n + cn) \leq e^{-c}$), which shows $T_n$ is concentrated within $O(n)$ of its mean with high probability.

Given codeword $\mathbf{c}_m$ and erasure pattern $\mathbf{e}$ (with $K \approx n(1-\epsilon)$ unerased positions), a wrong codeword $\mathbf{c}_{m'}$ is confusable if it agrees with $\mathbf{c}_m$ on all $K$ unerased positions. The probability (over random codebook) that a fixed wrong codeword $\mathbf{c}_{m'}$ is confusable is $(1/2)^K = 2^{-K}$. With $M-1 \approx 2^{nR}$ wrong codewords: $\mathbb{E}[\text{confusable}] \approx 2^{nR} \cdot 2^{-n(1-\epsilon)} = 2^{n(R-C)}.$

Let $Z$ = number of confusable wrong codewords. An error occurs iff $Z \geq 1$. By Markov: $P(Z \geq 1) \leq \mathbb{E}[Z] = 2^{n(R-C)}$. For $R < C$, $R-C < 0$, so $\mathbb{E}[Z] \to 0$ exponentially in $n$.

Since $\mathbb{E}_{\mathcal{C}}[P_e] \leq 2^{n(R-C)} < \epsilon$ for large enough $n$, there exists a codebook $\mathcal{C}^*$ with $P_e(\mathcal{C}^*) < \epsilon$. As $\epsilon$ and $R < C$ are arbitrary, codes of every rate below capacity achieve arbitrarily small error probability — establishing that $C = 1-\epsilon$ is the capacity. $\blacksquare$

Node $i$ has expected $\lambda = \pi r^2 (n-1) \approx \pi r^2 n$ neighbors in a disk. Each connection fails with probability $q$. $P(\text{node } i \text{ isolated}) \approx \sum_{k=0}^{\infty} e^{-\lambda}\lambda^k/k! \cdot q^k = e^{-\lambda} e^{\lambda q} = e^{-\lambda(1-q)} = e^{-\pi r^2 n (1-q)}.$

By linearity, $\mathbb{E}[\text{isolated}] \approx n \cdot e^{-\pi r^2 n(1-q)}$.

For connectivity, we need $\mathbb{E}[\text{isolated}] \to 0$, i.e., $n e^{-\pi r^2 n(1-q)} \to 0$, i.e., $\pi r^2 n(1-q) > \ln n$. Thus $r^2 > \ln n / (\pi n (1-q))$. With $q=0$: $r^2 > \ln n/(\pi n)$ (standard connectivity threshold for random geometric graphs). With $q > 0$, the required radius is scaled up by $1/(1-q)$ — link failures require denser deployment to maintain connectivity. $\blacksquare$