basic bounds

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. \]


  1. 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].

MathJax is loading, equations are not yet displayed...