Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:11:07Z http://mathoverflow.net/feeds/question/45050 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45050/probability-theory-chernoff-bounds-sum-of-independent-but-not-identically-dist Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. Michael 2010-11-06T09:40:43Z 2013-02-17T21:08:44Z <p>Dear friends,</p> <p>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).</p> <p>Formally, if $X_i$ ~ Geom($p_i$), and $X = \sum_{i=1}^n X_i$, and it is known that $E[X]=\Theta(n)$,</p> <p>Is it possible to show that $\Pr(X &lt; 2E[X]) > 1 - \delta ^n$, where $\delta &lt; 1$?</p> <p>Thank you in advance, Michael.</p> http://mathoverflow.net/questions/45050/probability-theory-chernoff-bounds-sum-of-independent-but-not-identically-dist/45078#45078 Answer by Warren Schudy for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. Warren Schudy 2010-11-06T15:55:42Z 2010-11-06T15:55:42Z <p>Yes, see e.g. <a href="http://en.wikipedia.org/wiki/Bernstein_inequalities_%28probability_theory%29" rel="nofollow">http://en.wikipedia.org/wiki/Bernstein_inequalities_%28probability_theory%29</a></p> http://mathoverflow.net/questions/45050/probability-theory-chernoff-bounds-sum-of-independent-but-not-identically-dist/45085#45085 Answer by Anand Sarwate for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. Anand Sarwate 2010-11-06T18:15:00Z 2010-11-06T18:15:00Z <p>You want the multiplicative form of Chernoff's bound.</p> <p><a href="http://en.wikipedia.org/wiki/Chernoff_bound" rel="nofollow">http://en.wikipedia.org/wiki/Chernoff_bound</a></p> http://mathoverflow.net/questions/45050/probability-theory-chernoff-bounds-sum-of-independent-but-not-identically-dist/45146#45146 Answer by Ori Gurel-Gurevich for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. Ori Gurel-Gurevich 2010-11-07T07:39:13Z 2010-11-07T07:39:13Z <p>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)$.</p> http://mathoverflow.net/questions/45050/probability-theory-chernoff-bounds-sum-of-independent-but-not-identically-dist/122098#122098 Answer by tipanverella for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v. tipanverella 2013-02-17T21:08:44Z 2013-02-17T21:08:44Z <p>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}$.</p>