Timeline for Estimator for sum of independent and identically distributed (iid) variables
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2012 at 23:57 | comment | added | Suresh Venkat | There's a variant of McDiarmid's inequality called Bernstein's inequality if you have formal bounds on the variance. In general, you should look at the Dubhashi-Panconesi book on concentration of measure. | |
| Nov 7, 2012 at 14:58 | comment | added | Jesko Hüttenhain | Using the variable $Z=\sum_i X_i=nX$ as well as $X_i\in[-1,1]$ and $E(X_i)=0$, we have $\sum(b_i-a_i)^2=4n$ and your formula basically says $$\Pr(|Z|\ge\lambda)=\Pr(|X|\ge n^{-1}\lambda)\le 2e^{-\lambda^2/2n}.$$ However, Chernoff says $$\Pr(|Z|\ge\lambda)\le 2e^{-\lambda^2/4\sigma^2}.$$ Even with the trivial observation $\sigma\le 1$, I would achieve a bound of $2e^{-\lambda^2/4}$ (which is better than $2e^{-\lambda^2/2n}$ for $n>2$) and even that one is, by far, not good enough. Do I have any other option? | |
| Nov 7, 2012 at 8:53 | history | answered | Suresh Venkat | CC BY-SA 3.0 |