Show that probability of a biased coin returning heads more than half the time is less than a certain number

Question

Let X be the number of successes of a biased coin returning head $\frac{1}{4}$ of the time within $k$ tosses. Show that $P(X\geq\frac{k}{2})\leq\frac{1}{2^{k/5}}$.

So I know that $X$ is $B(k,\frac{1}{4})$. And I was thinking about re-expressing $P(X\geq\frac{k}{2})$ as $\sum_{r=\lceil k/2\rceil}^k \binom{k}{r}(\frac{1}{4})^r(\frac{3}{4})^{k-r} =\sum_{r=\lceil k/2\rceil}^k \binom{k}{r}(\frac{3^{k-r}}{4^k})$ but I don't really know what to do afterwards.

I was told I can use $\binom{2r}{r}\leq\frac{4^r}{2}$ but the only way I can think of is to let $\binom{k}{r}\leq\binom{k}{\frac{k}{2}}\leq2^{k-1}$ for all $r$ and after that I get a very high upper bound much larger than required.

Would appreciate any help towards solving the question. Thank you.

Edit: Made a typo should have been $P(X\geq\frac{k}{2})$ instead of $P(X>\frac{k}{2}).$

Edit 2: Fixed more typos

Answer 1

That is quite a tight upper bound: for example $\frac{1}{2^{k/4}}$ would not work for large $k$ such as $k= 68$.

A possible approach with some gaps for you to fill:

• Show the probability is higher for $k=2m$ than for $k=2m-1$, so can concentrate on even $k$
• For even $k$, show the probability is less than $2 P\left(X = \frac k2\right)$
• Use your $\binom{k}{k/2}\leq \frac{4^{k/2}}{2}$ to say $2 P\left(X = \frac k2\right) = 2{k \choose k/2} \frac{3^{k/2}}{4^k} \le 2\frac{4^{k/2}}{2} \frac{3^{k/2}}{4^k} =\left(\sqrt{\frac{3}{4}}\right)^k$
• $\sqrt{\frac{3}{4}}\approx 0.866 < 0.871\approx \frac{1}{2^{1/5}}$