Suppose $Y=\sum_{i=1}^{n} X_{i}$ where each $X_{i}$ is an independently and identically distributed geometric random variable with success parameter $p$, so that $Y$ has a negative binomial distribution.

Are there any good upper bounds on $\mathbb{P}(Y>l)$ other than the standard Markov inequality for general $l$? I'm not necessarily looking for bounds on the concentration around the mean.


You can use a Chernoff bound (which is useful for large $l$), which is an easy consequence of the usual Markov inequality: For any $s>0$, $P(Y>l) = P(e^{sY} > e^{sl}) \leq \frac{E[e^{s Y}]}{e^{sl}} = \frac{(E[e^{sX_1}])^n }{e^{sl}} = \frac{ (\frac{p}{1-(1-p)e^s})^n}{e^{sl}} = e^{n \log \left(\frac{p}{1-(1-p)e^s} \right) -s l}$ (*).

Now, you can minimize the RHS over $s$ (i.e. find $s>0$ such that $n \log \left(\frac{p}{1-(1-p)e^s} \right) -s l$ is minimized), or plug in any $s>0$ to get a valid bound. Note that this function is convex (since its n times a log moment generating function minus something linear).

Differentiating $n \log \left(\frac{p}{1-(1-p)e^s} \right) -s l$ with respect to $s$ and setting it equal to zero gives $n (1-p) e^s=(1-(1-p)e^s)l$. Collecting the $e^s$ terms on one side and solving for $s$ will give you the $s$ which minimizes the RHS of (*).

The CDF is actually a regularized incomplete beta function, but I don't think that has any nice direct upper bounds. Generally, Chernoff bound (and other large deviation bounds) tend to work pretty well (Cramer's theorem tells you that the Chernoff bound applied ot the mean gives a tight exponent in $n$, for example).

| cite | improve this answer | |

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.