Probability bound on sum of geometric random variables

Question

Suppose each $X_i$ is a geometric distribution with probability $p = 1/2$. That is $X_i$ measures the number of coin flips it takes until you get a heads. Let $X = X_1 + X_2 + ... + X_n$. Clearly $E[X] = 2n$. Is there a good way to bound, say, $P(X > 10 n)$? I think it should be exponentially unlikely in $n$ but can't figure out how to prove that.

Answer 1

$E(e^{sX_1})=\frac{e^s}{2-e^s}$ for $s<\log 2.$ Thus for $0<s<\log 2$ and Markov inequality $\Pr(Y>y)\leq \frac{1}{y}E(Y)$ we have

$$\Pr(X>10n)=\Pr(e^{sX}>e^{s10n})\leq e^{-s10n}\left(\frac{e^s}{2-e^s}\right)^n$$ The minimum is obtained by choosing $s=19/10$ and you get the following majorization $$\Pr(X>10n)\leq\left(\frac{10^{10}}{19^9}\right)^n.$$

Answer 2

If your geometric random variables are independent then I believe this note should be useful, the main theorem on page 3 looks to be such a bound: https://cs.uwaterloo.ca/~browndg/negbin.pdf