References & Further Reading

References

1. J. A. Gubner, Probability and Random Processes for Electrical and Computer Engineers, Cambridge University Press, 2006

   The primary course textbook for FSP. Chapter 2 covers the probability axioms, inclusion-exclusion, and the reliability applications in Section 3.1. Notation and definitions follow Gubner throughout.

2. S. M. Ross, Introduction to Probability Models, Academic Press, 10th ed., 2010

   Chapter 3 gives an excellent treatment of reliability theory (series/parallel systems, coherent systems, minimal path sets) with many engineering examples. The bridge network calculation in Example 3.5 is the source for our Section 3.1 example.

3. R. E. Barlow and F. Proschan, Mathematical Theory of Reliability, Wiley, 1965

   The foundational mathematical reference for reliability theory. Introduces the structure function, coherent systems, and importance measures. Chapter 2 is the source for the Bonferroni bounds and the definition of coherent systems used in this chapter.

4. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, Wiley, 3rd ed., 1968

   The classic reference for occupancy problems, birthday problem, and coupon collector (Chapter IV). Feller's treatment of the harmonic number asymptotics and the geometric decomposition of coupon collection time remains definitive.

5. N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 4th ed., 2016

   The standard reference for the probabilistic method. Chapter 1 introduces the basic method and early Erdős results; later chapters cover Lovász Local Lemma, second moment method, and coding theory applications. The tournament Hamiltonian path example is from Chapter 1.

6. C. E. Shannon, A Mathematical Theory of Communication, 1948

   Shannon's original paper introducing the channel coding theorem, channel capacity, and the random coding argument. Section 11 gives the existence proof (probabilistic method) for capacity-achieving codes. This is the paper that started information theory.

7. T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley-Interscience, 2nd ed., 2006

   The standard graduate textbook for information theory. Chapter 7 proves the channel coding theorem rigorously, including the random coding argument previewed in Section 3.2. The BSC capacity formula and random coding exponent are from here.

8. M. Mitzenmacher and E. Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, Cambridge University Press, 2nd ed., 2017

   Excellent graduate-level treatment of probabilistic analysis of algorithms. Chapter 5 covers the balls-into-bins model, birthday problem, and coupon collector with applications to hash tables and load balancing. Very readable and engineering-oriented.

9. T. J. Richardson and R. L. Urbanke, Modern Coding Theory, Cambridge University Press, 2008

   Chapter 1 contextualizes Shannon's random coding argument within the broader history of coding theory, explaining why constructive capacity-achieving codes (LDPC, polar) took decades to discover.

10. N. Abramson, The ALOHA system: Another alternative for computer communications, 1970

    Original ALOHA paper introducing random access protocols. The birthday collision analysis and the $1/e$ throughput bound for slotted ALOHA stem from this work. The wireless connection in Section 3.3 is grounded in Abramson's analysis.

11. D. Tse and P. Viswanath, Fundamentals of Wireless Communication, Cambridge University Press, 2005

    Chapter 3 covers fading and diversity — the wireless connection between series/parallel reliability and spatial diversity in MIMO systems. Section 3.4 analyzes diversity order and the connection to outage probability.

12. A. Birolini, Reliability Engineering: Theory and Practice, Springer, 8th ed., 2017

    Comprehensive engineering reference for reliability theory. Chapter 4 covers redundancy design (active vs. passive standby) and the cost trade-offs discussed in the engineering note of Section 3.1.

13. P. Flajolet and P. Sedgewick, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996

    Section 3.5 gives a thorough asymptotic analysis of the coupon collector problem using generating functions, establishing the $n\ln n + 0.5772 n + O(1)$ correction term.

Further Reading

• Coherent systems and importance measures in reliability

  R. E. Barlow and F. Proschan, *Mathematical Theory of Reliability*, Wiley 1965, Chapters 2–3.

  Chapters 2–3 develop the structure function formalism, minimal path sets, and Birnbaum's importance measure — essential tools for designing large-scale redundant systems beyond series/parallel.

• The probabilistic method in combinatorics and coding

  N. Alon and J. H. Spencer, *The Probabilistic Method*, 4th ed., Wiley 2016, Chapters 1–3.

  Chapters 1–3 cover the Lovász Local Lemma (a powerful generalization of the basic probabilistic method) and the second moment method — the two tools needed to analyze random LDPC code ensembles in Book ITA.

• Polar codes: constructive capacity achievement

  E. Arıkan, 'Channel polarization: A method for constructing capacity-achieving codes,' IEEE Trans. Inf. Theory, vol. 55, no. 7, 2009.

  The original polar codes paper shows how to go beyond Shannon's random coding existence proof to a concrete capacity-achieving construction, completing the quest that Shannon's 1948 argument initiated.

• Balls into bins and load balancing in distributed systems

  M. Mitzenmacher and E. Upfal, *Probability and Computing*, 2nd ed., Cambridge 2017, Chapters 5–6.

  Chapters 5–6 extend the birthday and coupon collector analysis to the 'two choices' paradigm — throwing each ball into the less loaded of two random bins dramatically reduces the maximum load from $O(\log n/\log\log n)$ to $O(\log\log n)$.

• 5G random access and massive machine-type communications

  L. Liu et al., 'Sparse signal processing for grant-free massive connectivity,' IEEE Signal Process. Mag., 2018.

  Connects the coupon collector and birthday-bound analysis to the design of grant-free random access schemes for IoT networks with millions of devices, where the engineering note constraints on 3GPP TS 22.261 become critical.