12 votos

De desigualdades concentración medida de entendimiento

En el espíritu de esta pregunta la Comprensión de prueba de un lema utilizado en la desigualdad de Hoeffding , estoy tratando de entender los pasos que conducen a Hoeffding la desigualdad.

Lo que sostiene la mayoría de misterio para mí en la prueba es la parte donde exponencial momentos se calcula por la suma de (i).yo.d variables, después de que la desigualdad de Markov se aplica.

Mi objetivo es comprender: ¿por Qué esta técnica de dar un ajustado a la desigualdad, y no es de las más completas que podemos lograr? Una típica explicación se refiere al momento de generar las propiedades de los exponentes. Sin embargo, esto me parece demasiado vago.

Un post en el Tao del blog, http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/#hoeff, puede contener algunas respuestas.

Con este objetivo en mente, mi pregunta es acerca de tres puntos en el Tao del post en el que estoy atrapado en el y que espero que podrían dar pistas explicó una vez.

  1. Tao se deriva la siguiente desigualdad utilizando el k-ésimo momento$$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$$ Si esto es cierto para cualquier k, concluye una exponencial obligado. Esto es donde estoy perdido. $$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$$

  2. Hoeffding del lema se presenta: Lema 1 (Hoeffding del lema) Deje ${X}$ ser un escalar de variable toma valores en un intervalo de ${[a,b]}$. Entonces para cualquier ${t>0}$, $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$$ En particular $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$$ La prueba del Lema 1 comienza por tomar la expectativa sobre la expansión de taylor $\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$ .¿Por qué la expansión estar delimitado por que el término cuadrático? y ¿cómo ecuación 10 seguir?

  3. Por último, un ejercicio:
    Ejercicio 1 Muestran que la ${O(t^2(b-a)^2)}$ factor en (10) puede ser reemplazado con ${t^2 (b-a)^2/8}$, y que este es nítida. Esto proporcionaría un período mucho más corto de la prueba que en la Comprensión de la prueba de un lema utilizado en la desigualdad de Hoeffding , pero no sé cómo resolver esto.

Cualquier intuiciones\explicaciones acerca de la prueba de la desigualdad o la razón por la que no se puede derivar de una manera más rigurosa obligado definitivamente son bienvenidos.

8voto

Mark Cohen Puntos 566

El uso de exponenciales momentos es un paso común en el proceso de la prueba de concentración de medir las desigualdades. Mi entendimiento es como sigue 1) mediante el uso de $\mathbb{E}e^X$ en lugar de $\mathbb{E} X$, una captura todos los momentos de $X$, en lugar de simplemente el primer momento. Por lo tanto, es siempre ventajoso enlazado $\mathbb{E} e^X$, en lugar de obligada $\mathbb{E}X$, ya que hay más información en $\mathbb{E} e^X$. ¿Por qué $\mathbb{E} e^X$ tiene más información? Informal, la explicación está dada por el hecho de que una expansión de Taylor de $e^{X}=1+X+\frac{X^2}{2}+\frac{X^3}{6}+\ldots$. Como usted puede ver todas las facultades de $X$ están involucrados. Por lo tanto, cuando usted tome $\mathbb{E}X$, básicamente terminan delimitador todos los momentos de la $X$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X