Bounds & Inequalities - Probability & Statistics

1 Union Bound (Boole's Inequality)

The probability of a union of events is at most the sum of their individual probabilities. This holds regardless of independence.

$$ P\left( \bigcup_{i=1}^n A_i \right) \leq \sum_{i=1}^n P(A_i) $$

Bonferroni Inequalities: Including more terms from the Inclusion-Exclusion Principle gives alternating upper and lower bounds.

2 Markov & Chebyshev Inequalities

Markov's Inequality

For a non-negative RV $ X $ and $ a > 0 $:

$$ P(X \geq a) \leq \frac{E[X]}{a} $$

Chebyshev's Inequality

For any RV $ X $ with finite mean and variance, and $ k > 0 $:

$$ P(|X - \mu| \geq k) \leq \frac{\text{Var}(X)}{k^2} $$

3 Chernoff Bound

Chernoff bounds provide exponentially decaying estimates for tail probabilities using the Moment Generating Function $ M_X(s) $.

$$ P(X \geq a) \leq \min_{s>0} e^{-sa} M_X(s) $$

Interactive Bounds Explorer

Compare the true tail probability $ P(X \geq a) $ with Markov and Chebyshev bounds for an Exponential($ \lambda=1 $) distribution.
Note: Chebyshev applies to $ |X-\mu| $, so we plot the one-sided equivalent for comparison where applicable.

Threshold $ a $: 2

4 Solved Example: Bounds on Binomial Distribution

Let $ X \sim \text{Binomial}(n, p) $. We want to bound the probability of deviating from the mean $ \mu = np $. Consider $ P(X \ge \alpha n) $ where $ \alpha > p $.

Markov Bound

Using $ E[X] = np $:

$$ P(X \ge \alpha n) \le \frac{np}{\alpha n} = \frac{p}{\alpha} $$

Weakest bound. Constant (doesn't decay with $ n $).

Chebyshev Bound

Using $ \text{Var}(X) = np(1-p) $:

$$ P(X \ge \alpha n) \le \frac{p(1-p)}{n(\alpha-p)^2} $$

Better. Decays as $ 1/n $.

Chernoff Bound

Using MGF:

$$ P(X \ge \alpha n) \le e^{-n D(\alpha || p)} $$

Strongest. Decays exponentially with $ n $.

5 Other Important Inequalities

Cauchy-Schwarz Inequality

Relates expectations of products to products of expectations.

$$ |E[XY]| \leq \sqrt{E[X^2]E[Y^2]} $$

Implies $ |\rho(X,Y)| \leq 1 $

Jensen's Inequality

For a convex function $ g(x) $ (like $ x^2 $ or $ e^x $):

$$ E[g(X)] \geq g(E[X]) $$

Check Your Understanding

1. Markov Application

If $ E[X] = 10 $ and $ X \geq 0 $, what is the upper bound for $ P(X \geq 50) $?

2. Convexity

Is $ E[X^2] \geq (E[X])^2 $?