# Chernoff bound probability: value of $n$ so that with probability $.999$ at least half of the coin flips come out heads

Problem 3: Consider a biased coin with probability $p = \frac{1}{3}$ of landing heads and probability $\frac{2}{3}$ of landing tails. Suppose the coin is flipped some number $n$ of times, and let $X_i$ be a random variable denoting the $i$'th flip, where $X_i = 1$ means heads, and $X_i = 0$ means tails (i.e., $X_i$ is the indicator random variable of the $i$'th flip being heads). Use the Chernoff bound to determine a value for $n$ so that the probability that more than half of the coin flips come out heads is less than $0.001$.

I have tried using the formula and got $n=147$, where did I go wrong? What I have tried to do is $$\mathbb{P}\left\{ X > \frac{n}{2} \right\}<0.001=\frac{\mathbb{E}[e^{sx}]}{e^{sn/2}}$$

$$\forall\gamma\in(0,1],\qquad \mathbb{P}\!\left\{\sum_{i=1}^n X_i > (1+\gamma)np \right\} \leq e^{-\gamma^2 \frac{np}{3}}\,.\tag{\dagger}$$
We want $(1+\gamma)np = \frac{n}{2}$, and since $p=\frac{1}{3}$ this leads to setting $\gamma\stackrel{\rm def}{=} \frac{1}{2}$ in $(\dagger)$. Thus, we have an upper bound on the probability of $$e^{-\gamma^2 \frac{np}{3}} = e^{-\left(\frac{1}{2}\right)^2 \frac{n}{9}} = e^{-\frac{n}{36}}\,.$$ To make sure the probability is at most $\frac{1}{1000}$, it suffices to choose $n$ such that our upper bound on the probability is less than $\frac{1}{1000}$, i.e. $e^{-\frac{n}{36}} < \frac{1}{1000}$, or equivalently $$n > 36\ln 1000 \simeq 248.7\,.$$ Therefore, choosing $\boxed{n = 249}$ is sufficient.
• Also, note that the Hoeffding bound ((1) in the link in my answer) would lead to a tighter result: here, $n> 18 \ln 1000$, so $\boxed{n=125}$ would be enough. – Clement C. Nov 6 '17 at 18:50