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

boundary value problemprobability theory

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}}
$$

Best Answer

Using the Chernoff bound (as stated here as (2) for reference):

$$ \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.

Related Question