3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ You should proofread your post and use $\LaTeX$ formating -- in particular, your question is unclear (misses a parenthesis and a comparison sign I guess). $\endgroup$ Nov 6, 2010 at 12:55

4 Answers 4

2
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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! $\endgroup$
    – Michael
    Nov 7, 2010 at 10:27
  • 1
    $\begingroup$ Maybe I should add that it's enough if all the $p_i$ are bounded from below by some constant (using the standard proof). $\endgroup$ Nov 7, 2010 at 16:41
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Michael
    Nov 6, 2010 at 18:02
  • $\begingroup$ 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. $\endgroup$ Nov 6, 2010 at 21:07
  • $\begingroup$ 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). $\endgroup$
    – Michael
    Nov 6, 2010 at 21:19
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

You want the multiplicative form of Chernoff's bound.

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

$\endgroup$
4
  • 1
    $\begingroup$ 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... $\endgroup$
    – Michael
    Nov 6, 2010 at 18:40
  • $\begingroup$ 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 $\endgroup$ Nov 6, 2010 at 20:07
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Michael
    Nov 6, 2010 at 20:50
  • $\begingroup$ I mean, $X_n$ is distributed Geom($p=\tfrac{1}{n}$) $\endgroup$
    – Michael
    Nov 6, 2010 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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