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.
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)$$
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?
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.