La desigualdad de Azuma

En teoría de probabilidad , la desigualdad de Azuma-Hoeffding (llamada así en honor a Kazuoki Azuma y Wassily Hoeffding ) arroja un resultado de concentración para los valores de las martingalas que tienen diferencias acotadas.

Supongamos que es una martingala (o supermartingala ) y${\displaystyle \{X_{k}:k=0,1,2,3,\puntos \}}$

${\displaystyle |X_{k}-X_{k-1}|\leq c_{k},\,}$

casi con seguridad . Entonces, para todos los enteros positivos N y todos los reales positivos ,${\displaystyle \épsilon}$

${\displaystyle {\text{P}}(X_{N}-X_{0}\geq \epsilon )\leq \exp \left({-\epsilon ^{2} \sobre 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

Y simétricamente (cuando X _k es una sub-martingala):

${\displaystyle {\text{P}}(X_{N}-X_{0}\leq -\epsilon )\leq \exp \left({-\epsilon ^{2} \sobre 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

Si X es una martingala, al utilizar ambas desigualdades anteriores y aplicar el límite de unión se puede obtener un límite bilateral:

${\displaystyle {\text{P}}(|X_{N}-X_{0}|\geq \epsilon )\leq 2\exp \left({-\epsilon ^{2} \sobre 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

La prueba comparte una idea similar a la prueba de la forma general de la desigualdad de Azuma que se muestra a continuación. En realidad, esto puede considerarse como un corolario directo de la forma general de la desigualdad de Azuma.

Nótese que la desigualdad de Azuma básica requiere límites simétricos en los incrementos de martingala, es decir , . Por lo tanto, si el límite conocido es asimétrico, por ejemplo , para utilizar la desigualdad de Azuma, se debe elegir, lo que podría ser un desperdicio de información sobre la acotación de . Sin embargo, este problema se puede resolver y se puede obtener un límite de probabilidad más estricto con la siguiente forma general de la desigualdad de Azuma.${\displaystyle -c_{t}\leq X_{t}-X_{t-1}\leq c_{t}}$${\displaystyle a_{t}\leq X_{t}-X_{t-1}\leq b_{t}}$${\displaystyle c_{t}=\max(|a_{t}|,|b_{t}|)}$$Estilo de visualización X_{t}-X_{t-1}}$

Sea una martingala (o supermartingala) con respecto a la filtración . Supongamos que hay procesos predecibles y con respecto a , es decir, para todos los , son - medibles y constantes tales que${\displaystyle \left\{X_{0},X_{1},\cdots \right\}}$ ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$ ${\displaystyle \left\{A_{0},A_{1},\cdots \right\}}$${\displaystyle \left\{B_{0},B_{1},\puntos \right\}}$${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$${\estilo de visualización t}$$Estilo de visualización A_{t}, B_{t}}$${\displaystyle {\mathcal {F}}_{t-1}}$${\displaystyle 0<c_{1},c_{2},\cdots <\infty }$

${\displaystyle A_{t}\leq X_{t}-X_{t-1}\leq B_{t}\quad {\text{y}}\quad B_{t}-A_{t}\leq c_{t}}$

Casi seguro. Entonces para todos ,${\displaystyle \epsilon >0}$

${\displaystyle {\text{P}}(X_{n}-X_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Como una submartingala es una supermartingala con signos invertidos, tenemos que si en cambio es una martingala (o submartingala),${\displaystyle \left\{X_{0},X_{1},\puntos \right\}}$

${\displaystyle {\text{P}}(X_{n}-X_{0}\leq -\epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Si es una martingala, ya que es a la vez supermartingala y submartingala, al aplicar el límite de unión a las dos desigualdades anteriores, podríamos obtener el límite bilateral:${\displaystyle \left\{X_{0},X_{1},\puntos \right\}}$

${\displaystyle {\text{P}}(|X_{n}-X_{0}|\geq \epsilon )\leq 2\exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Probaremos el caso de la supermartingala solo porque el resto es evidente. Por descomposición de Doob , podríamos descomponer la supermartingala como donde es una martingala y es una secuencia predecible no creciente (nótese que si en sí es una martingala, entonces ). De , tenemos${\displaystyle \left\{X_{t}\right\}}$${\displaystyle X_{t}=Y_{t}+Z_{t}}$${\displaystyle \left\{Y_{t},{\mathcal {F}}_{t}\right\}}$${\displaystyle \left\{Z_{t},{\mathcal {F}}_{t}\right\}}$${\displaystyle \left\{X_{t}\right\}}$${\displaystyle Z_{t}=0}$${\displaystyle A_{t}\leq X_{t}-X_{t-1}\leq B_{t}}$

${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$

Aplicando el límite de Chernoff a , tenemos para ,${\displaystyle Y_{n}-Y_{0}}$${\displaystyle \epsilon >0}$

${\displaystyle {\begin{aligned}{\text{P}}(Y_{n}-Y_{0}\geq \epsilon )&\leq {\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} [e^{s(Y_{n}-Y_{0})}]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n}(Y_{t}-Y_{t-1})\right)\right]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n-1}(Y_{t}-Y_{t-1})\right)\mathbb {E} \left[\exp \left(s(Y_{n}-Y_{n-1})\right)\mid {\mathcal {F}}_{n-1}\right]\right]\end{aligned}}}$

Para el término de expectativa interna, ya que

(i) como es una martingala; ${\displaystyle \mathbb {E} [Y_{t}-Y_{t-1}\mid {\mathcal {F}}_{t-1}]=0}$${\displaystyle \left\{Y_{t}\right\}}$

(ii) ;${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$

(iii) y son ambos -mensurables ya que es un proceso predecible; ${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}}$${\displaystyle -(Z_{t}-Z_{t-1})+B_{t}}$${\displaystyle {\mathcal {F}}_{t-1}}$${\displaystyle \left\{Z_{t}\right\}}$

(iv) ;${\displaystyle B_{t}-A_{t}\leq c_{t}}$

Aplicando el lema de Hoeffding ^{[nota 1]} , tenemos

${\displaystyle \mathbb {E} \left[\exp \left(s(Y_{t}-Y_{t-1})\right)\mid {\mathcal {F}}_{t-1}\right]\leq \exp \left({\frac {s^{2}(B_{t}-A_{t})^{2}}{8}}\right)\leq \exp \left({\frac {s^{2}c_{t}^{2}}{8}}\right).}$

Repitiendo este paso, se podría obtener

${\displaystyle {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq {\underset {s>0}{\min }}\ e^{-s\epsilon }\exp \left({\frac {s^{2}\sum _{t=1}^{n}c_{t}^{2}}{8}}\right).}$

Nótese que el mínimo se alcanza en , por lo que tenemos${\displaystyle s={\frac {4\epsilon }{\sum _{t=1}^{n}c_{t}^{2}}}}$

${\displaystyle {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Finalmente, dado que y como no es creciente, entonces el evento implica , y por lo tanto${\displaystyle X_{n}-X_{0}=(Y_{n}-Y_{0})+(Z_{n}-Z_{0})}$${\displaystyle Z_{n}-Z_{0}\leq 0}$${\displaystyle \left\{Z_{n}\right\}}$${\displaystyle \left\{X_{n}-X_{0}\geq \epsilon \right\}}$${\displaystyle \left\{Y_{n}-Y_{0}\geq \epsilon \right\}}$

${\displaystyle {\text{P}}(X_{n}-X_{0}\geq \epsilon )\leq {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).\square }$

Tenga en cuenta que al establecer , podríamos obtener la desigualdad de Azuma original.${\displaystyle A_{t}=-c_{t},B_{t}=c_{t}}$

Tenga en cuenta que, tanto en el caso de la submartingala como en el de la supermartingala, solo se cumple un lado de la desigualdad de Azuma. No podemos decir mucho sobre la velocidad a la que aumenta una submartingala con incrementos acotados (o a la velocidad a la que disminuye una supermartingala).

Esta forma general de la desigualdad de Azuma aplicada a la martingala de Doob da como resultado la desigualdad de McDiarmid, que es común en el análisis de algoritmos aleatorios .

Sea F _i una secuencia de lanzamientos de moneda aleatorios independientes e idénticamente distribuidos (es decir, sea F _i igualmente probable que sea −1 o 1 independientemente de los otros valores de F _i ). Definiendo se obtiene una martingala con | X _k  −  X _{k −1} | ≤ 1, lo que nos permite aplicar la desigualdad de Azuma. Específicamente, obtenemos${\displaystyle X_{i}=\sum _{j=1}^{i}F_{j}}$

${\displaystyle \operatorname {P} (X_{n}>t)\leq \exp \left({\frac {-t^{2}}{2n}}\right).}$

Por ejemplo, si establecemos t como proporcional a n , esto nos dice que, aunque el valor máximo posible de X _n escala linealmente con n , la probabilidad de que la suma escale linealmente con n disminuye exponencialmente rápido con  n .

Si establecemos obtenemos:${\displaystyle t={\sqrt {2n\ln n}}}$

${\displaystyle \operatorname {P} \left(X_{n}>{\sqrt {2n\ln n}}\right)\leq {\frac {1}{n}},}$

lo que significa que la probabilidad de desviarse más se acerca a 0 cuando n tiende a infinito.${\displaystyle {\sqrt {2n\ln n}}}$

Sergei Bernstein demostró una desigualdad similar bajo supuestos más débiles en 1937.

Hoeffding demostró este resultado para variables independientes en lugar de diferencias de martingala, y también observó que ligeras modificaciones de su argumento establecen el resultado para diferencias de martingala (véase la página 9 de su artículo de 1963).

• Desigualdad de concentración : un resumen de los límites de cola en variables aleatorias.

• Alon, N.; Spencer, J. (1992). El método probabilístico . Nueva York: Wiley.
• Azuma, K. (1967). "Sumas ponderadas de ciertas variables aleatorias dependientes" (PDF) . Tôhoku Mathematical Journal . 19 (3): 357–367. doi : 10.2748/tmj/1178243286 . MR  0221571.
• Bernstein, Sergei N. (1937). О некоторых модификациях неравенства Чебышёва[Sobre ciertas modificaciones de la desigualdad de Chebyshev]. Doklady Akademii Nauk SSSR (en ruso). 17 (6): 275–277.(vol. 4, ítem 22 de las obras completas)
• McDiarmid, C. (1989). "Sobre el método de diferencias acotadas". Surveys in Combinatorics . London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. págs. 148–188. MR  1036755.
• Hoeffding, W. (1963). "Desigualdades de probabilidad para sumas de variables aleatorias acotadas". Revista de la Asociación Estadounidense de Estadística . 58 (301): 13–30. doi :10.2307/2282952. JSTOR  2282952. MR  0144363.
• Godbole, AP; Hitczenko, P. (1998). "Más allá del método de diferencias acotadas". Microencuestas en probabilidad discreta . Serie DIMACS en matemáticas discretas y ciencias de la computación teórica. Vol. 41. págs. 43–58. doi :10.1090/dimacs/041/03. ISBN 9780821808276.Señor 1630408  .