Límite de Chernoff para la suma de variables subgaussianas mediante el método de truncamiento

Question

Estoy tratando de seguir la prueba aquí para la Proposición 6 en https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/ pero no sé cómo calcular la parte final:

Cada ${X_{i,m}}$ está claramente limitada en magnitud por ${2^m}$ ; a partir de la hipótesis subgaussiana también se puede verificar que la media y la varianza de ${X_{i,m}}$ son como máximo ${C' \exp( - c' 2^{2m} )}$ para algunos ${C', c' > 0}$ . Si ${A}$ es suficientemente grande, una aplicación del límite de Chernoff (11) (o más precisamente, el refinamiento en el Ejercicio 3) da entonces (después de algún cálculo) $$\displaystyle {\bf P}( |S_{n,m}| \geq 2^{-m-1} A n ) \leq C' 2^{-m} \exp( - c' A n )$$ (digamos) para algunos ${C', c' > 0}$ y se cumple la afirmación.

Lo que he probado: Cada $X_{n,m}$ está limitada por $K=2^m$ . También disponemos de $\sigma=$ raíz cuadrada de la varianza de $S_{n,m} \leq \sqrt{nC'}\exp(-c'2^{2m}/2)$ . Por último, defina $\lambda := 2^{-m-1} A n /\sigma$ . Aplicamos el límite de Chernoff mejorado como se sugiere: \begin{align*} {\bf P}( |S_{n,m}| \geq 2^{-m-1} A n ) &= {\bf P}( |S_{n,m}| \geq \lambda\sigma)\\ &\leq C \max( \exp( - c \lambda^2 ), {(\lambda K/\sigma)^{-c \lambda \sigma / K}} )\\ &\leq C \max\left(\exp(-c\cdot 2^{-2m-2}A^2n\exp(c'2^{2m})/C''),(A\exp(c'2^{2m})/2C')^{-2^{-2m-1}cAn} \right)\\ &\leq C'' \exp(-c''An)(A/2C')^{-2^{-2m-1}cAn}. \end{align*} $(A/2C')^{-2^{-2m-1}cAn}$ tiende a $1$ como $m$ es grande. No puedo conseguir el $2^{-m}$ para que aparezca en el último paso.

Answer 1

Mi suposición es que $P(|S_{n,m}| \ge 2^{-m-1}An)$ es un error tipográfico. La primera prueba que apoya mi suposición es que justo arriba en la prueba, se encuentra $P(|S_{n,m}| \ge \frac{A}{100(m+1)^2}n)$ . La segunda prueba es que, como has demostrado correctamente, la prueba no funciona con $P(|S_{n,m}| \ge 2^{-m-1}An)$ en su lugar.

Sea $\lambda = \frac{1}{100(m+1)^2}\frac{An}{\sigma}$ . Entonces $P(|S_{n,m}| \ge \frac{An}{100(m+1)^2}) = P(|S_{n,m}| \ge \lambda \sigma) \le C\max(\exp(-c\lambda^2),(\lambda K/\sigma)^{-c\lambda \sigma K})$ . Nota $\exp(-c\lambda^2) = \exp\left(-c\frac{1}{m^4}A^2n\exp(c'2^{2m})\right)$ es obviamente como máximo $C'2^{-m}\exp(-c'An)$ . Y el término que era problemático para usted, es decir. $(\lambda K/\sigma)^{-c\lambda \sigma/K}$ , es ahora de $(\frac{2^m}{m^2}A\exp(c'2^{2m}))^{-c\frac{An}{m^2}2^{-m}} \approx \exp(-c\frac{An}{m^2}c'2^m)$ que también es claramente lo suficientemente pequeño.