MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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

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

-
 You should proofread your post and use $\LaTeX$ formating -- in particular, your question is unclear (misses a parenthesis and a comparison sign I guess). – BenoĆ®t Kloeckner Nov 6 2010 at 12:55 Fixed. Thank you for the comment. – Michael Nov 6 2010 at 17:52

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

-
This is what I wrote in the last comment of the previous answer. So, in general, if the variables are not identical, the sum is not strongly concentrated around the $E[X]$ if $E[X]=\Theta(n)$. Thanks a lot! – Michael Nov 7 2010 at 10:27
Maybe I should add that it's enough if all the $p_i$ are bounded from below by some constant (using the standard proof). – Ori Gurel-Gurevich Nov 7 2010 at 16:41
-
 But is seems that Bernstein inequality (for geometric r.v. we can use ineq. #2 from the link) can't give exponential tail in the case t=constant. If t is not constant, then we don't get $\Pr(X > \alpha\cdot E[X])$, where $\alpha=const$. – Michael Nov 6 2010 at 18:02 Can't you pick $t=\Theta(\sqrt{n})$? Do you know that $E[X] = \Omega(n)$? If $E[X]$ can be arbitrarily small then you can't get better than Markov. – Warren Schudy Nov 6 2010 at 21:07 Maybe I should write this in the question: Yes, my $E[X]=\Theta(n)$. As I commented in the another answer, I think there is no such bound for this case (linear expectation and exponential bound). – Michael Nov 6 2010 at 21:19

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

-

You want the multiplicative form of Chernoff's bound.

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

-
Chernoff gives the result in the case of Bernoulli random variables. In the case of identical geometric variables, we can use the relation between the geometric and Bernoulli variable ($\Pr(\sum_{i=1}^n G_i \le k)=\Pr(\sum_{i=1}^k B_i > n)$), and use the known bound for Bernoulli. In the case of not identical geometric random variables we can't use this trick... So, the question still remains... – Michael Nov 6 2010 at 18:40
So the issue is the unbounded support for the geometric random variables? You should be able to handle that using other methods. Perhaps skim through econ.upf.edu/~lugosi/anu.pdf – Anand Sarwate Nov 6 2010 at 20:07
I think now that there is no such a bound. For example, if $X_1,...,X_{n-1}$ are distributed Geom(p=1), and $X_n$ is distributed $X_n$. Then, $E[X]=(n-1)\cdot 1 + n\approx 2n$. But X now is not much concentrated around $E[X]$. To obtain an exponential high probability, we have to repeat the experience $\Omega(n)$ times. If we want only $\tfrac{1}{n}$ high probability, we need to repeat it $log n$ times. So, the sum of $n$ indepemdent but not identical geometric r.v. is not concentrated around $\alpha\cdot E[x]$, where $\alpha=const$. – Michael Nov 6 2010 at 20:50
I mean, $X_n$ is distributed Geom($p=\tfrac{1}{n}$) – Michael Nov 6 2010 at 20:51