Chernoff Bounds For Rademacher Random Variable

01 Mar 2018

Prologue To The Chernoff Bounds For Rademacher Random Variable

The Chernoff bounds is a convenient way to build the shaper bounds in exponential form for the Rademacher random variable. It could efficiently relate the sample size to the error bias fits within the desired probability.

The Rademacher Random Variable

It is also called the random sign variable. Let S be a Rademacher random variable, its events are given $\{1,-1\}$, each with probability $\frac {1}{2}$.

Then, it has the basic property that $E\lbrack S^{k}\rbrack$=$0$, for $k$ is odd, while $E\lbrack S^{k}\rbrack$=$1$, for $k$ is even.
➀$E\lbrack S^{1}\rbrack$=$\frac {1}{2}\cdot 1$+$\frac {1}{2}\cdot (-1)$=$0$
➁$E\lbrack S^{3}\rbrack$=$\frac {1}{2}\cdot 1^{3}$+$\frac {1}{2}\cdot (-1)^{3}$=$0$
➂$E\lbrack S^{2}\rbrack$=$\frac {1}{2}\cdot 1^{2}$+$\frac {1}{2}\cdot (-1)^{2}$=$1$
➃$E\lbrack S^{4}\rbrack$=$\frac {1}{2}\cdot 1^{4}$+$\frac {1}{2}\cdot (-1)^{4}$=$1$

Chernoff Bounds For Rademacher Random Variable

Given $S$ is a Rademacher random variable, then
$\;\;P(Z\ge t)\le exp(\frac {n\cdot\lambda^{2}}{2})\cdot e^{-\lambda\cdot t}$
, where $Z$=$\sum_{i=1}^{n}S_{i}$
Proof:
➀begin by Taylor series of exponential function.
$E\lbrack e^{\lambda\cdot S}\rbrack$
=$E\lbrack\sum_{k=0}^{\infty}\frac {(\lambda\cdot S)^{k}}{k!}\rbrack$
=$\sum_{k=0}^{\infty}\frac {\lambda^{k}\cdot E\lbrack S^{k}\rbrack}{k!}$
=$\sum_{k=0,2,4,…}^{\infty}\frac {\lambda^{k}}{k!}$
=$\sum_{k=0}^{\infty}\frac {\lambda^{2\cdot k}}{2\cdot k!}$
➁next to find the closest upper bound, specifically, in exponential form.
since $2\cdot k!\ge 2^{k}\cdot k!$, we have
$E\lbrack e^{\lambda\cdot S}\rbrack$
=$\sum_{k=0}^{\infty}\frac {\lambda^{2\cdot k}}{2\cdot k!}$
$\le \sum_{k=0}^{\infty}\frac {\lambda^{2\cdot k}}{2^{k}\cdot k!}$
=$\sum_{k=0}^{\infty}(\frac {\lambda^{2}}{2})^{k}/k!$
=$e^{(\frac {\lambda^{2}}{2})}$
➂by given $Z$=$\sum_{i=1}^{n}S_{i}$, we have
$P(Z\ge t)$
$\le \frac {E\lbrack Z\rbrack}{t}$…Markov inequality
=$\frac {E\lbrack\sum_{i=1}^{n}S_{i}\rbrack}{t}$
=$\frac {E\lbrack e^{\lambda\cdot\sum_{i=1}^{n}S_{i}}\rbrack}{e^{\lambda\cdot t}}$……Chernoff bounds
=$\frac {E^{n}\lbrack e^{\lambda\cdot S_{1}}\rbrack}{e^{\lambda\cdot t}}$
$\le (e^{(\frac {\lambda^{2}}{2})})^{n}\cdot e^{-\lambda\cdot t}$
$\Rightarrow P(Z\ge t)\le e^{(\frac {n\cdot\lambda^{2}}{2})}\cdot e^{-\lambda\cdot t}$

Chernoff Bounds Extension

In this section, we’d like to inspect probability, sample size and the desired bias.
$P(Z\ge t)\le e^{(\frac {n\cdot\lambda^{2}}{2})}\cdot e^{-\lambda\cdot t}$
$\Rightarrow P(Z\ge t)\le e^{(\frac {n\cdot\lambda^{2}}{2})-\lambda\cdot t}$

We can get the minimum upper bound by finding some $\lambda$, which is equivalent to finding $\underset{\lambda\ge 0}{min}\{\frac{n\cdot\lambda^2}2-\lambda\cdot t\}$
➀taking derivatives with respect to $\lambda$, and set it to $0$, we get $\lambda$=$\frac {t}{n}$.
➁replace $\lambda$ with $\frac {t}{n}$ in inequality, we have
$P(Z\ge t)\le e^{-\frac {t^{2}}{2\cdot n}}$
➂suppose you’d like to constraint the testing result, the quantity from random variable $Z$, bigger than the bias, denote it $t$, with the error probability as a whole, limited within $\delta$, we can express it below: $P(Z\ge t)\le\delta$, where $\delta$=$e^{-\frac {t^{2}}{2\cdot n}}$
Then, $t$=$\sqrt {2\cdot n\cdot ln\frac {1}{\delta}}$
Finally, we can get the appropriate data size in terms of bias, $t$ and the error probability, say it $\delta$.

Cautions must be made that such extension holds only on event containing true and false. Other articles in my dev blog would inspect the form with respect to events of multiple results(more than 2 results).