Chebyshev Inequality

Let $X$ be a real valued random variable. $\forall \alpha > 0$,

$$\mathbb{P}[(X - \mathbb{E}[X])^2 \geq \alpha] \leq \frac{\mathbb{V}[X]}{\alpha}$$

Alternatively, $\forall c > 0$

$$\mathbb{P}[(X - \mathbb{E}[X])^2 \geq c\mathbb{V}[X]] \leq \frac{1}{c}$$

Proof: Apply Markov’s inequality to the standard deviation $$

X - \mathbb{E}[X]

$$:

$$\mathbb{P}[X - \mathbb{E}[X] \geq \alpha] \leq \mathbb{P}[(X - \mathbb{E}[X])^2 \geq \alpha^2] \leq \frac{\mathbb{E}[|X - \mathbb{E}[X]|]}{\alpha}$$

Comparison with other inequalities

Chebyshev’s is great when you have a sum of pairwise independent things because then $\mathbb{V}[\sum_n X_n] = \sum_n \mathbb{V}[X_n]$

Examples

Pairwise Independent Hashing

Let $p$ be prime and consider a hash family $H = \{ h_{ab} : a \in \mathbb{Z}_p^k, b \in \mathbb{Z}_p \}$ where $h_{ab}: \mathbb{Z}_p^k \rightarrow \mathbb{Z}_p$ given by $h_{a, b} = a \cdot x + b \mod p$. Fix $x_1, ..., x_N \in \mathbb{Z}_p^k$ and pick $y \in \mathbb{Z}_p$. What is the probability, over $h \in H$ drawn uniformly at random, that $h(x_i) = y$ for more than $(1/p + \epsilon)N$ values of $i$? In other words, assuming we choose elements from the hash family uniformly at random, what’s the probability that multiple elements map to the same value $y$?

Define $X_i = \mathbb{I}\{h(x_i) = y\}$ and $X = \sum X_i$. Note that $\mathbb{E}[X] = \frac{N}{P}$. Then:

$$\mathbb{P}[X \geq (1/p + \epsilon)N] \leq \frac{\mathbb{V}[X]}{\epsilon^2 n^2} = \frac{\sum (1/p)(1 - 1/p)}{\epsilon^2 n^2}$$