Timeline for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2010 at 20:52 | vote | accept | Michael | ||
| Nov 6, 2010 at 21:22 | |||||
| Nov 6, 2010 at 20:51 | comment | added | Michael | I mean, $X_n$ is distributed Geom($p=\tfrac{1}{n}$) | |
| Nov 6, 2010 at 20:50 | comment | added | Michael | 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$. | |
| Nov 6, 2010 at 20:40 | vote | accept | Michael | ||
| Nov 6, 2010 at 20:52 | |||||
| Nov 6, 2010 at 20:07 | comment | added | Anand Sarwate | 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 | |
| Nov 6, 2010 at 18:41 | vote | accept | Michael | ||
| Nov 6, 2010 at 18:41 | |||||
| Nov 6, 2010 at 18:40 | comment | added | Michael | 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... | |
| Nov 6, 2010 at 18:15 | history | answered | Anand Sarwate | CC BY-SA 2.5 |