Chapter Summary

Chapter Summary

Key Points

• 1.

  System reliability combines component-level probabilities using product rules for series systems ($R_s = \prod R_i$) and parallel systems ($R_s = 1 - \prod(1-R_i)$). Inclusion-exclusion generalizes both to arbitrary network topologies, and the Bonferroni bounds provide efficient two-sided approximations.

• 2.

  The probabilistic method proves existence by randomization: if $\mathbb{E}[f(X)] < t$, then some outcome achieves $f < t$. This non-constructive technique underpins Shannon's 1948 random coding argument — the proof that communication at rates below capacity is possible without specifying which codebook to use.

• 3.

  The birthday bound states that among $m \approx \sqrt{n}$ i.i.d.
  uniform draws from a universe of size $n$, the probability of collision exceeds $1/2$. The precise formula is $P(\text{collision}) \approx 1 - e^{-m^2/(2n)}$. This determines hash function security, slotted ALOHA collision rates, and the capacity of random access protocols.

• 4.

  The coupon collector requires $\mathbb{E}[T_n] = nH_n \approx n\ln n$ draws to see all $n$ types at least once. The proof decomposes $T_n$ into $n$ independent geometric waiting times and applies linearity of expectation. This governs channel sounding protocols, random scheduling, and any "coverage" problem requiring complete sampling of a finite set.

• 5.

  All three combinatorial applications — reliability, random coding, and occupancy — reduce to asking how probability concentrates over structured random objects. The axioms of Chapter 1 and the independence framework of Chapter 2 are the only tools required.