La desigualdad de Azuma

Teorema en la teoría de la probabilidad.

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

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

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

casi seguramente . Entonces, para todos los números enteros positivos N y todos los reales positivos , ${\displaystyle \epsilon }$

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

Y simétricamente (cuando X _k es una submartingala):

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

Si X es una martingala, usar las dos desigualdades anteriores y aplicar el límite de unión permite obtener un límite de dos lados:

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

Prueba

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

Una forma general de la desigualdad de Azuma.

Limitación de la desigualdad de vainilla de Azuma.

Tenga en cuenta que la desigualdad básica de Azuma requiere límites simétricos en incrementos de martingala, es decir . Entonces, si el límite conocido es asimétrico, por ejemplo , para usar la desigualdad de Azuma, es necesario elegir cuál podría ser un desperdicio de información sobre el límite de . Sin embargo, este problema se puede resolver y se puede obtener una probabilidad más estricta ligada a 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}|)}$ ${\displaystyle X_{t}-X_{t-1}}$

Declaración

Sea una martingala (o supermartingala) con respecto a la filtración . Supongamos que hay procesos predecibles y con respecto a , es decir, para todos , son mensurables 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},\dots \right\}}$ ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$ ${\displaystyle t}$ ${\displaystyle 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{and}}\quad B_{t}-A_{t}\leq c_{t}}$

casi con seguridad. 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).}$

Dado que una submartingala es una supermartingala con signos invertidos, tenemos if en cambio es una martingala (o submartingala), ${\displaystyle \left\{X_{0},X_{1},\dots \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, dado que es a la vez una supermartingala y una submartingala, aplicando la unión ligada a las dos desigualdades anteriores, podríamos obtener la ligada de dos lados: ${\displaystyle \left\{X_{0},X_{1},\dots \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).}$

Prueba

Demostraremos el caso de la supermartingala sólo porque el resto es evidente. Mediante la descomposición de Doob , podríamos descomponer la supermartingala como donde es una martingala y es una secuencia predecible no creciente (tenga en cuenta que si en sí misma 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 Chernoff ligado 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 lo 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 son 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).}$

Tenga en cuenta que el mínimo se logra 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, 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 }$

Observación

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

Tenga en cuenta que tanto para la submartingala como para la supermartingala, solo se cumple un lado de la desigualdad de Azuma. No podemos decir mucho sobre qué tan rápido sube una submartingala con incrementos acotados (o cae una supermartingala).

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

Ejemplo simple de la desigualdad de Azuma al lanzar una moneda

Sea F _i una secuencia de lanzamientos de moneda aleatorios independientes e idénticamente distribuidos (es decir, sea igualmente probable que F _i sea −1 o 1 independiente de los otros valores de F _i ). La definición produce 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 proporcional a n , entonces esto nos dice que aunque el valor máximo posible de X _n aumenta linealmente con n , la probabilidad de que la suma aumente linealmente con n disminuye exponencialmente rápido con  n .

Si configuramos 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 de se acerca a 0 cuando n tiende a infinito. ${\displaystyle {\sqrt {2n\ln n}}}$

Observació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 (consulte la página 9 de su artículo de 1963).

Ver también

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

Notas

1. Sin embargo, no es una aplicación directa del lema de Hoeffding. El enunciado del lema de Hoeffding maneja la expectativa total, pero también es válido para el caso en que la expectativa es una expectativa condicional y los límites son mensurables con respecto al campo sigma al que está condicionada la expectativa condicional. La prueba es la misma que para el lema de Hoeffding clásico.

Referencias

• Alón, N.; Spencer, J. (1992). El método probabilístico . Nueva York: Wiley.
• Azuma, K. (1967). "Sumas ponderadas de determinadas variables aleatorias dependientes" (PDF) . Revista Matemática Tôhoku . 19 (3): 357–367. doi : 10.2748/tmj/1178243286 . SEÑOR  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). "En el método de las diferencias acotadas". Encuestas en Combinatoria . Matemáticas de Londres. Soc. Notas de conferencias 141. Cambridge: Cambridge Univ. Prensa. págs. 148–188. SEÑOR  1036755.
• Hoeffding, W. (1963). "Las desigualdades de probabilidad para sumas de variables aleatorias delimitadas". Revista de la Asociación Estadounidense de Estadística . 58 (301): 13–30. doi :10.2307/2282952. JSTOR  2282952. SEÑOR  0144363.
• Godbole, AP; Hitczenko, P. (1998). "Más allá del método de las diferencias acotadas". Microencuestas en probabilidad discreta . Serie DIMACS en Matemática Discreta e Informática Teórica. vol. 41. págs. 43–58. doi :10.1090/dimacs/041/03. ISBN 9780821808276. SEÑOR  1630408.