# Chernoff bound for Geometric RVs compared to exact tail bound

I keep getting a result I can't interpret.

X is a Geometric RV with distribution ($0<\rho<1$) $$\pi_k = \rho^k(1- \rho)$$ so directly applying Geometric series the tail bound is $$B_1 = P(X>\theta) = \sum_{k = \theta+1}^{\infty} \pi_k =\rho^{\theta+1}$$ Obviously this is an exact result. My confusion comes from the result I get using Chernoff bound and MGF of Geometric RV: $$P(X> \theta) = P(e^{t X} > e^{t \theta})<\frac{\mathbf{E}e^{tX}}{e^{t (\theta+1)}} = \frac{e^{\log (1-\rho) - t(\theta+1)}}{1-e^t \rho} \ = h(t)$$
Optimizing this for $t$, the optimal value is ($b=\theta+1, \ c= \rho$) $$t^{\ast} = \log \frac{b}{c(b+1)}$$ Plugging this result into the inequality above, I get Chernoff bound: $$B_2 = P(X> \theta) < (\theta+2)(1-\rho)\rho^{\theta+1}\bigg(\frac{b+1}{b}\bigg)^b \approx e (\theta+2)(1-\rho)\rho^{\theta+1}$$ Comparing $B_2$ to $B_1$it turns out that $B_2 < B_1$ for $$\rho>1-\frac{1}{e(\theta+2)}$$ That is, asymptotically in $\theta$ they are the the same, since $\rho<1$, but, e.g. if $\theta=10$, then for $\rho > 0.965 \ B_2$ is sharper.

Bar algebraic typos, where is the mistake in my logic?

-

## 1 Answer

If $\rho>{\theta+1\over \theta+2}$, then $t^*<0$ and the equation $P(X> \theta) = P(e^{t^* X} > e^{t^* \theta})$ fails.

-
great, thanks, I missed this point – Alex Sep 22 '12 at 2:01