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

Improve this question
$\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$
    – Benoît Kloeckner
    Commented Nov 6, 2010 at 12:55

4 Answers 4

Reset to default
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)$.

Improve this answer
$\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
    Commented 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$
    – Ori Gurel-Gurevich
    Commented Nov 7, 2010 at 16:41
1
$\begingroup$

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

Improve this answer
$\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
    Commented 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$
    – Warren Schudy
    Commented 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
    Commented 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}$.

Improve this answer
$\endgroup$
0
$\begingroup$

You want the multiplicative form of Chernoff's bound.

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

Improve this answer
$\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
    Commented 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$
    – Anand Sarwate
    Commented 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
    Commented Nov 6, 2010 at 20:50
  • $\begingroup$ I mean, $X_n$ is distributed Geom($p=\tfrac{1}{n}$) $\endgroup$
    – Michael
    Commented Nov 6, 2010 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .