# Probability of getting $n$ heads after $cn$ tosses?

If $X_n$ is the number of coin tosses to get $n$ heads, then how can one show that there exists a constant $c>1$ such that $P(X_n \geq cn) \leq 1/n$? I am looking for a direct elementary proof.

Assume the coin tosses are fair and independent.

-

## 1 Answer

Since $X_n$ is the sum of $n$ i.i.d. geometric random variables with parameter $\frac12$, $E[X_n]=2n$ and $\mathrm{var}(X_n)=2n$. Bienaymé-Chebychev inequality implies that, for every nonnegative $x$, $$P[X_n\geqslant E[X_n]+x]\leqslant\mathrm{var}(X_n)/x^2.$$ If $x^2=2n^2$, the RHS is $1/n$ and $E[X_n]+x=(2+\sqrt2)n$ hence $c=2+\sqrt2$ answers the question. Or, $$P[X_n\gt 4n]\leqslant1/(2n).$$

-
Thank you. This would be a great answer but I was hoping, perhaps in vain, that there might be a proof that was elementary and entirely self contained. –  felix Oct 6 '13 at 16:43
I suppose I could just incorporate a direct proof of en.wikipedia.org/wiki/… . –  felix Oct 6 '13 at 17:36