Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '10 at 12:55
    
Fixed. Thank you for the comment. –  Michael Nov 6 '10 at 17:52

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer
1  
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 '10 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 '10 at 16:41

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

share|improve this answer
    
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 '10 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 '10 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 '10 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}$.

share|improve this answer

You want the multiplicative form of Chernoff's bound.

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

share|improve this answer
1  
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 '10 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 '10 at 20:07
1  
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 '10 at 20:50
    
I mean, $X_n$ is distributed Geom($p=\tfrac{1}{n}$) –  Michael Nov 6 '10 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.