Is there any known bound on sum of independent but not identically
distributed geometric random variables?
I have to show that the tail of the sum drops exponentially (like in
the Chernoff bounds for the sum of iid geom. variables).
Formally, if $X_i$ ~ Geom($p_i$), and $X = \sum_{i=1}^n X_i$, and it is known that $E[X]=\Theta(n)$,
Is it possible to show that $\Pr(X < 2E[X]) > 1 – \delta ^n$, where $\delta < 1$?
Best Answer
This isn't true, in general. If you take $p_0=1/n$ and the other $p_i=1$ then you get a constant probability for $X>2\mathbb{E}(X)$.