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 X be any random variable and let \mu =\textrm{E}[X]. Then there exists at least one outcome where X \ge \mu (and at least one where X \le \mu ).
Here are three simple but fundamental bounds:
Theorem 2 (naive union bound).
For any two random events A and B,
\[ \Pr [A\text { or } B] ~ \le ~ \Pr [A] + \Pr [B]. \]
For any n random events A_1,A_2,\ldots ,A_ n,
\[ \Pr [\text {some } A_ i \text { occurs}] ~ \le ~ \sum _ i \Pr [A_ i]. \]
Theorem 3 (linearity of expectation).
For any numeric random variables X,Y and real constant c,
\[ \textrm{E}[X+Y] ~ =~ \textrm{E}[X]+\textrm{E}[Y] ~ \text { and }~ \textrm{E}[c X] ~ =~ c\, \textrm{E}[X]. \]
Theorem 4 (Markov bound).
For any non-negative random variable X and constant c\gt 0,
\[ \Pr [X\ge {}c] ~ \le ~ \textrm{E}[X]/c \]
and, if E[X]\gt 0, then1
\[ \Pr [X\gt c] ~ \lt ~ \textrm{E}[X]/c. \]
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 \Pr [X\gt c]=0, we’re done, so assume \Pr [X\gt c]\gt 0.
Then \textrm{E}[X] \ge \Pr [X \gt c] \textrm{E}[X \, |\, X \gt c] \gt \Pr [X \gt c]\, c so \textrm{E}[x]/c \gt \Pr [X \gt c].
