Error tipográfico en la entrada de Wikipedia sobre Hoeffding la desigualdad?

Question

En la entrada de Wikipedia sobre Hoeffding la desigualdad, afirman que si $\overline{X} := \frac 1 n \sum_{i=1}^n X_i$, luego $$ P(\overline{X}-E[\overline{X}] \ge t) \le \exp (-2n^2 t^2)$$ si suponemos por simplicidad que $a_i=0$ $b_i=1$ todos los $i$.

Este es mi primer encuentro con Hoeffding la desigualdad, por lo que estoy familiarizado con todas las diferentes manifestaciones de este teorema, pero independientemente de ello, todas las otras fuentes que he visto tienen algo a lo largo de las líneas de $\exp (-2nt^2)$ lugar. Es la entrada de Wikipedia de un error tipográfico?

Comentario: creo que la versión de la desigualdad en los que consideramos que $Y := \sum_{i=1}^n X_i$, en lugar del promedio de $\overline{X}$ ha enlazado $\exp(-2t^2)$. Pero, en ningún otro lugar he visto a $\exp(-2n^2 t^2)$ además de la entrada de la Wikipedia.

Gracias!

Answer 1

Es sólo una cuestión de cómo definir las variables aleatorias: la suma de ($Y := \sum_{i=1}^n X_i$) o el promedio ($\overline{X} := \frac 1 n \sum_{i=1}^n X_i = \frac 1 n Y$), de lo contrario los dos límites son equivalentes:

$$\Pr(Y - \mathrm{E}[Y] \geq t) \leq \exp \left( - \frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!$$

con $t = t'\,n$ tenemos:

$$\Pr(Y - \mathrm{E}[Y] \geq t'n) \leq \exp \left( - \frac{2n^2 t'^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!$$

Tenga en cuenta que $\Pr(Y - \mathrm{E}[Y] \geq t'n) = \Pr(\frac{1}{n}(Y - \mathrm{E}[Y]) \geq t') = \Pr(\overline{X} - \mathrm{E}[\overline{X}] \geq t')$, por lo que la desigualdad anterior es equivalente a $$\Pr(\overline{X} - \mathrm{E}[\overline{X}] \geq t') \leq \exp \left( - \frac{2n^2 t'^2}{\sum_{i=1}^n (b_i - a_i)^2} \right).$$

Answer 2

La forma en que copió la ecuación no está muy bien. Si $a_i=0$ $b_i=1$ todos los $i$, entonces el límite es:

$$\exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)=\exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n 1} \right)=\exp \left( - \frac{2n^2t^2}{n} \right)=\exp \left(-2nt^2\right).$$

El formulario de la izquierda es de la Wikipedia, lo cual es correcto; es la misma que la ecuación (2.6) en la fuente. El formulario de la derecha es lo que estabas esperando.