1
$\begingroup$

According to the current version of the Wikipedia article entitled "Chernoff bound", the probability of simultaneous occurrence of more than $\frac{n}{2}$ successes in $n$ independent Bernoulli trials each with a probability of success $p>\frac{1}{2}$ is bounded from below by $1-e^{-2n\left(p-\frac{1}{2}\right)^2}$

How is this result derived from the Chernoff bound?

1 Answers 1

1

The following lower bound can be readily established $1-e^{-\frac{1}{2p}n\left(p-\frac{1}{2}\right)^2}$ Indeed, let $n\in\left\{1,2,\dots\right\}$ be fixed and let $X_0, X_1, \dots, X_n$ be i.i.d. $\mathrm{Bernouli}(p)$, $p\in\left(\frac{1}{2},1\right)$. Set $S:=\sum_{i=0}^n X_i$, $\mu:=E[S]$. Denote by $q$ the probability of simultaneous occurrence of more than $\frac{n}{2}$ successes, where success in the $i$th trial is the event $\left\{X_i=1\right\}$. Then $q=1-P\left(S\leq\frac{n}{2}\right)$ and, noticing that $\mu=np$, we have by the multiplicative form of the Chernoff bound $P\left(S\leq\frac{n}{2}\right)=P\left(S\leq\left(1-\left(1-\frac{1}{2p}\right)\right)\mu\right)\leq e^{-\frac{\mu}{2}\left(1-\frac{1}{2p}\right)^2}=e^{-\frac{1}{2p}n\left(p-\frac{1}{2}\right)^2}$

Now, since Wikipedia can be edited by anyone, simply replace the lower bound in the entry with the one derived above and you're all set.