# 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 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 ,

$\Pr [A\text { or } B] ~ \le ~ \Pr [A] + \Pr [B].$

For any random events ,

$\Pr [\text {some } A_ i \text { occurs}] ~ \le ~ \sum _ i \Pr [A_ i].$
Theorem 3 (linearity of expectation).

For any numeric random variables and real constant ,

$\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 and constant ,

$\Pr [X\ge {}c] ~ \le ~ \textrm{E}[X]/c$

and, if , then1

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

# Related

## Footnotes

1. Here is a proof of the second claim in the Markov bound.
If , we’re done, so assume .
Then so .