Existence proofs, the naive union bound, linearity of expectation, Markov bound.
Basic bounds
Here is the basic principle underlying the probabilistic method:
Theorem 1 (existence).
Fix any random experiment. Let be any random variable and let . Then there exists at least one outcome where (and at least one where ).
Here are three simple but fundamental bounds:
Theorem 2 (naive union bound).
For any two random events and ,
For any random events ,
Theorem 3 (linearity of expectation).
For any numeric random variables and real constant ,
Theorem 4 (Markov bound).
For any non-negative random variable and constant ,
and, if , then1
Related
Introductory textbooks on basic probability, available online
-
Notes on Discrete Probability — by Trevisan
-
Introduction to Probability — by Grinstead and Snell (see Chapters 1, 4, 6)
-
Lecture Notes on Probability Theory and Random Processes — by Walrand (see Chapters 1–6)
Footnotes
- Here is a proof of the second claim in the Markov bound.
If , we’re done, so assume .
Then so .