Chernoff bound

cosmos 16th May 2019 at 5:18pm
Probability theory

See here

Let X1,...,XnX_1,...,X_n be independent random variables, where Xi=1X_i=1 with probability pip_i and Xi=0X_i=0 with probability 1pi1-p_i. Let X=i=1nXiX= \sum_{i=1}^n X_i and μ=E[X]=i=1npi\mu = E[X] = \sum_{i=1}^n p_i. Then for α[0,1]\alpha \in [0,1],

P[Xμαμ]2exp(μα22)\mathcal{P}[|X-\mu| \geq \alpha \mu] \leq 2\exp{\left(-\frac{\mu \alpha^2}{2}\right)}

Relative entropy Chernoff bound

A tighter version of the standard Chernoff bound, which uses the Relative entropy