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


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.

  • $\begingroup$ 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. $\endgroup$ – Clement C. Nov 6 '17 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.