Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. - MathOverflow

Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v.

2010-11-06T09:40:43Z

Dear friends,

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$?

Thank you in advance, Michael.

Answer by Warren Schudy for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v.

2010-11-06T15:55:42Z

Yes, see e.g. http://en.wikipedia.org/wiki/Bernstein_inequalities_%28probability_theory%29

Answer by Anand Sarwate for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v.

2010-11-06T18:15:00Z

You want the multiplicative form of Chernoff's bound.

http://en.wikipedia.org/wiki/Chernoff_bound

Answer by Ori Gurel-Gurevich for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v.

2010-11-07T07:39:13Z

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)$.

Answer by tipanverella for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v.

2013-02-17T21:08:44Z

Lookup the Gartner-Ellis. My name intuition is that you can bound the probability you are interested in, using the Fenchel-Legendre transform of a log-moment-generating-function of a random variable and that is essentially a Geometric random variable with parameter $p := \displaystyle \lim_{n\to \infty} \left(\prod_{i=1}^n p_i\right)^{1/n}$.