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, then^{1}

\[ \Pr [X\gt c] ~ \lt ~ \textrm{E}[X]/c. \]

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

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