Resume
Research
Learning
Blog
Teaching
Jokes
Kernel Papers

# Chernoff Bounds

Let $$X$$ be a random variable. By applying Markov’s Inequality to the moment generating function of $$X$$, we obtain Chernoff bounds i.e. $$\forall t > 0$$:

$\mathbb{P}[X \geq a] = \mathbb{P}[e^{t X} \geq e^{t a}] \leq \frac{\mathbb{E}[e^{t X}]}{e^{t a}}$

## Properties

• If $$X_i$$ is a single Bernoulli with probability $$p_i$$, then using the Bernoulli MGF, $$\mathbb{P}[X_i \geq a] \leq \frac{1 + p_i (e - 1)}{e^a}$$

• If $$X$$ is a sum of independent but not necessarily identically distributed Bernoullis with mean $$\mu$$, then $$\forall \delta > 0$$:

$\mathbb{P}[X \geq (1 + \delta) \mu] \leq \Big( \frac{e^{\delta}}{(1 + \delta)^{1+\delta}} \Big)^{\mu}$

and

$\forall \delta > 0, \mathbb{P}[X \leq (1-\delta) \mu] \leq \Big( \frac{e^{-\delta}}{(1 - \delta)^{1-\delta}} \Big)^{\mu}$
• Corollaries: If $$X$$ is the sum of indep. but not necessarily identical Bernoullis, then:

• $\forall \delta \in (0, 1], \mathbb{P}[X \geq (1+\delta) \mu] \leq e^{-\mu \delta^2/3}$
• $\forall \delta \in (0, 1], \mathbb{P}[X \leq (1-\delta) \mu] \leq e^{-\mu \delta^2/2}$
• $c \geq 6, \mathbb{P}[X \geq c \mu] \leq 2^{-c/\mu}$

## Examples

### Fair Coin Flips

Let $$X$$ be the number of heads after $$n$$ coin flips of a fair coin, and consider the probability that $$X \geq 3n/4$$. Markov’s Inequality tells us that the probability is:

$\mathbb{P}[X \geq 3n/4] \leq \frac{\mathbb{E}[X]}{3n/4} = \frac{n/2}{3n/4} = \frac{2}{3}$

Intuitively, that feels loose, especially if $$n$$ is large. What does [Chebyshev’s Inequality] tell us?

$\mathbb{P}[X \geq 3n/4] \leq \frac{4}{n}$

That’s inversely related to $$n$$, which is Better! But intuitively, we expect that $$\exp(-\Omega(n))$$ should be possible. Using Chernoff’s gives us exponential decay in $$n$$.