in

Entendiendo la prueba de la desigualdad de McDiarmid

Estoy trabajando con el conjunto 2 de notas de clase de Wasserman y no puedo completar los pasos que faltan en la derivación de la desigualdad de McDiarmid (p.5). Al igual que mi pregunta anterior en el foro, estoy reproduciendo la prueba en las notas a continuación y después de la prueba señalaré los pasos que no puedo deducir.

Desigualdad de McDiarmid

Sean $X_{1}, \ldots, X_{n}$ variables aleatorias independientes. Suponer que

\begin{align*} \sup_{x_{1}, \ldots, x_{n}, x_{i}^{\prime}} \left| g(x_{1}, \ldots, x_{i-1}, x_{i}, x_{i+1}, \ldots, x_{n}) – g(x_{1}, \ldots, x_{ i-1}, x_{i}^{\prime} , x_{i+1}, \ldots, x_{n}) \right| &\le c_{i} \end{align*}

para $i = 1, \ldots, n$. Después

\begin{align*} \mathbb{P} \left( g(X_{1}, \ldots, X_{n}) – \mathbb{E}(g(X_{1}, \ldots, X_{n} )) \ge \epsilon \right) & \le \exp \left( -\frac{2\epsilon^{2}}{\sum_{i=1}^{n} c_{i}^{2}} \derecha) \end{alinear*}

Prueba

Sea $V_{i} = \mathbb{E}(g | X_{1}, \ldots, X_{i}) – \mathbb{E}(g | X_{1}, \ldots, X_{i-1 ps Entonces \begin{align*} g(X_{1}, \ldots, X_{n}) – \mathbb{E}(g(X_{1}, \ldots, X_{n})) &= \sum_{ i=1}^{n} V_{i} \end{align*} y $\mathbb{E}(V_{i} | X_{1}, \ldots, X_{i-1}) = 0$

Usando un argumento similar al de la prueba del Lema de Hoeffding tenemos, \begin{align*} \mathbb{E}(e^{t V_{i} } | X_{1}, \ldots, X_{i-1} ) &\le e^{t^2c_{i}^{2}/8} \end{align*}

Ahora, para cualquier $t > 0$, \begin{align*} \mathbb{P} \left( g(X_{1}, \ldots, X_{n}) – \mathbb{E}(g(X_{ 1}, \ldots, X_{n})) \ge \epsilon \right) &= \mathbb{P} \left( \sum_{i=1}^{n} V_{i} \ge \epsilon \right ) \\\\ &=\mathbb{P} \left( e^{t \sum_{i=1}^{n} V_{i}} \ge e^{t \epsilon} \right) \le e ^{- t \epsilon} \mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} \right) \\\\ &= e^{- t \ épsilon} \mathbb{E} \left ( e^{t \sum_{i=1}^{n-1} V_{i}} \mathbb{E} \left( e^{tV_{n}} | X_ {1}, \ldots, X_{n-1} \right) \right ) \\\\ &\le e^{- t \epsilon} e^{t^2c_{n}^{2}/8} \mathbb{E} \left ( e^{t \sum_{i=1}^{n-1} V_{i}} \right ) \\\\ & \ldots \\\\ &\le e^{ – t \epsilon} e^{t^2 \sum_{i=1}^{n} c_{i}^{2}/8} \end{align*}

El resultado sigue tomando $t = 4 \epsilon / \sum_{i=1}^{n} c_{i}^{2}$.

Preguntas

como probar

  1. $\mathbb{E}(V_{i} | X_{1}, \ldots, X_{i-1}) = 0$
  2. $\mathbb{E}(e^{t V_{i} } | X_{1}, \ldots, X_{i-1}) \le e^{t^2c_{i}^{2}/8} ps
  3. $\mathbb{E} \left( e^{t \sum_{i=1}^{n} V_{i}} \right) = \mathbb{E} \left( e^{t \sum_{i= 1}^{n-1} V_{i}} \mathbb{E} \left( e^{tV_{n}} | X_{1}, \ldots, X_{n-1} \right) \right) ps

Aunque esto involucra detalles técnicos, cualquier intuición sobre los detalles será útil.

1 respuesta
1

Introduzcamos alguna notación, $X_{1:i} = X_{1}, \ldots, X_{i}$.

¿Te ayudó la respuesta?

Subscribirse
Notificar por
guest
0 Comentarios
Inline Feedbacks
Ver todas las Respuestas

Temporización de acordes arpegiados

¿Un cifrado indescifrable de Hill?