En la teoría de la probabilidad , la desigualdad de Azuma-Hoeffding (llamada así por Kazuoki Azuma y Wassily Hoeffding ) da un resultado de concentración para los valores de martingalas que tienen diferencias acotadas.
Supongamos que { X k : k = 0, 1, 2, 3, ...} es una martingala (o supermartingala ) y
casi seguro . Luego, para todos los enteros positivos N y todos los reales positivos ,
Y simétricamente (cuando X k es una submartingala):
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:
Prueba
La prueba comparte una idea similar de 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 Azuma
Tenga en cuenta que la desigualdad de la vainilla Azuma requiere límites simétricos en incrementos de martingala, es decir . Entonces, si el límite conocido es asimétrico, p. Ej., para usar la desigualdad de Azuma, es necesario elegir lo que podría ser un desperdicio de información sobre la delimitació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.
Declaración
Dejar ser una martingala (o supermartingala) con respecto a la filtración . Suponga que hay procesos predecibles y con respecto a , es decir, para todos , están - medibles y constantes tal que
casi seguro. Entonces para todos,
Dado que una submartingala es una supermartingala con signos invertidos, tenemos si en cambio es una martingala (o submartingala),
Si es una martingala, ya que es a la vez una supermartingala y una submartingala, aplicando el límite de unión a las dos desigualdades anteriores, podríamos obtener el límite de dos lados:
Prueba
Demostraremos el caso de la supermartingala sólo ya que el resto es evidente por sí mismo. Por descomposición de Doob , podríamos descomponer supermartingale como dónde es una martingala y es una secuencia predecible que no aumenta (tenga en cuenta que si en sí mismo es una martingala, entonces ). De, tenemos
Aplicando Chernoff enlazado a, tenemos para ,
Para el término de expectativa interna, ya que (i) como es una martingala; (ii); (iii) y son ambos -medible como es un proceso predecible; y (iv), aplicando el lema de Hoeffding [nota 1] , tenemos
Repitiendo este paso, uno podría obtener
Tenga en cuenta que el mínimo se alcanza en , entonces tenemos
Finalmente, desde y como no aumenta, por lo que event implica , y por lo tanto
Observación
Tenga en cuenta que al establecer , podríamos obtener la desigualdad de Azuma vainilla.
Tenga en cuenta que tanto para la submartingala como para la supermartingala, solo se mantiene un lado de la desigualdad de Azuma. No podemos decir mucho acerca de qué tan rápido sube una submartingala con incrementos acotados (o cae una supermartingala).
Esta forma general de 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 para los lanzamientos de monedas
Sea F i una secuencia de lanzamientos de monedas aleatorios independientes e idénticamente distribuidos (es decir, sea F i igualmente probable que sea -1 o 1 independiente de los otros valores de F i ). Definiendorinde una martingala con | X k - X k −1 | ≤ 1, lo que nos permite aplicar la desigualdad de Azuma. Específicamente, obtenemos
Por ejemplo, si establecemos t proporcional an , entonces esto nos dice que aunque el valor máximo posible de X n escala linealmente con n , la probabilidad de que la suma escala linealmente con n disminuye exponencialmente rápido con n .
Si ponemos obtenemos:
lo que significa que la probabilidad de desviarse más de se aproxima a 0 cuando n va al infinito.
Observación
Una desigualdad similares se probó bajo supuestos más débiles por Sergei Bernstein en 1937.
Hoeffding probó este resultado para las variables independientes en lugar de las diferencias de martingala, y también observó que ligeras modificaciones de su argumento establecen el resultado para las diferencias de martingala (ver página 18 de su artículo de 1963).
Ver también
- Desigualdad de concentración : un resumen de los límites de cola de las variables aleatorias.
Notas
- ^ 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 se aplica al caso en el que la expectativa es una expectativa condicional y los límites son medibles con respecto al campo sigma al que está condicionada la expectativa condicional.
Referencias
- Alon, 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 . London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Prensa. págs. 148-188. Señor 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 . Señor 0144363 .
- Godbole, AP; Hitczenko, P. (1998). Más allá del método de las diferencias acotadas . Serie DIMACS en Matemática Discreta e Informática Teórica . 41 . págs. 43–58. doi : 10.1090 / dimacs / 041/03 . ISBN 9780821808276. Señor 1630408 .