Desigualdades de Bernstein (teoría de la probabilidad)

Desigualdades en la teoría de la probabilidad

En teoría de la probabilidad , las desigualdades de Bernstein dan límites a la probabilidad de que la suma de variables aleatorias se desvíe de su media. En el caso más simple, sean X ₁ , ...,  X _n variables aleatorias independientes de Bernoulli que toman valores +1 y −1 con probabilidad 1/2 (esta distribución también se conoce como distribución de Rademacher ), entonces para cada positivo , ${\displaystyle \varepsilon }$

${\displaystyle \mathbb {P} \left(\left|{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\right|>\varepsilon \right)\leq 2\exp \left(-{\frac {n\varepsilon ^{2}}{2(1+{\frac {\varepsilon }{3}})}}\right).}$

Las desigualdades de Bernstein fueron demostradas y publicadas por Sergei Bernstein en las décadas de 1920 y 1930. ^{[1] [2] [3] [4]} Más tarde, estas desigualdades fueron redescubiertas varias veces en diversas formas. Así, los casos especiales de las desigualdades de Bernstein también se conocen como el límite de Chernoff , la desigualdad de Hoeffding y la desigualdad de Azuma . El caso martingala de la desigualdad de Bernstein se conoce como la desigualdad de Freedman ^[5] y su refinamiento se conoce como la desigualdad de Hoeffding. ^[6]

Algunas de las desigualdades

1. Sean variables aleatorias independientes de media cero. Supóngase que casi con seguridad, para todos Entonces, para todos los positivos , ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle |X_{i}|\leq M}$ ${\displaystyle i.}$ ${\displaystyle t}$

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq t\right)\leq \exp \left(-{\frac {{\tfrac {1}{2}}t^{2}}{\sum _{i=1}^{n}\mathbb {E} \left[X_{i}^{2}\right]+{\tfrac {1}{3}}Mt}}\right).}$

2. Sean variables aleatorias independientes de media cero. Supóngase que para algún número real positivo y cada entero , ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle L}$ ${\displaystyle k\geq 2}$

${\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {1}{2}}\mathbb {E} \left[X_{i}^{2}\right]L^{k-2}k!}$

Entonces

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum \mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0\leq t\leq {\frac {1}{2L}}{\sqrt {\sum \mathbb {E} \left[X_{j}^{2}\right]}}.}$

3. Sean variables aleatorias independientes de media cero. Supóngase que ${\displaystyle X_{1},\ldots ,X_{n}}$

${\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {k!}{4!}}\left({\frac {L}{5}}\right)^{k-4}}$

para todo entero Denotar ${\displaystyle k\geq 4.}$

${\displaystyle A_{k}=\sum \mathbb {E} \left[X_{i}^{k}\right].}$

Entonces,

${\displaystyle \mathbb {P} \left(\left|\sum _{j=1}^{n}X_{j}-{\frac {A_{3}t^{2}}{3A_{2}}}\right|\geq {\sqrt {2A_{2}}}\,t\left[1+{\frac {A_{4}t^{2}}{6A_{2}^{2}}}\right]\right)<2\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {5{\sqrt {2A_{2}}}}{4L}}.}$

4. Bernstein también demostró generalizaciones de las desigualdades anteriores a variables aleatorias débilmente dependientes. Por ejemplo, la desigualdad (2) se puede extender de la siguiente manera. Sean variables aleatorias posiblemente no independientes. Supóngase que para todos los números enteros , ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle i>0}$

${\displaystyle {\begin{aligned}\mathbb {E} \left.\left[X_{i}\right|X_{1},\ldots ,X_{i-1}\right]&=0,\\\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]&\leq R_{i}\mathbb {E} \left[X_{i}^{2}\right],\\\mathbb {E} \left.\left[X_{i}^{k}\right|X_{1},\ldots ,X_{i-1}\right]&\leq {\tfrac {1}{2}}\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]L^{k-2}k!\end{aligned}}}$

Entonces

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {1}{2L}}{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}.}$

Se pueden encontrar resultados más generales para martingalas en Fan et al. (2015). ^[7]

Pruebas

Las pruebas se basan en una aplicación de la desigualdad de Markov a la variable aleatoria

${\displaystyle \exp \left(\lambda \sum _{j=1}^{n}X_{j}\right),}$

para una adecuada elección del parámetro . ${\displaystyle \lambda >0}$

Generalizaciones

La desigualdad de Bernstein se puede generalizar a matrices aleatorias gaussianas. Sea un escalar donde es una matriz hermítica compleja y es un vector complejo de tamaño . El vector es un vector gaussiano de tamaño . Entonces, para cualquier , tenemos ${\displaystyle G=g^{H}Ag+2\operatorname {Re} (g^{H}a)}$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle g\sim {\mathcal {CN}}(0,I)}$ ${\displaystyle N}$ ${\displaystyle \sigma \geq 0}$

${\displaystyle \mathbb {P} \left(G\leq \operatorname {tr} (A)-{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}-\sigma s^{-}(A)\right)<\exp(-\sigma ),}$

donde es la operación de vectorización y donde es el valor propio más grande de . La prueba se detalla aquí. ^[8] Otra desigualdad similar se formula como ${\displaystyle \operatorname {vec} }$ ${\displaystyle s^{-}(A)=\max(-\lambda _{\max }(A),0)}$ ${\displaystyle \lambda _{\max }(A)}$ ${\displaystyle A}$

${\displaystyle \mathbb {P} \left(G\geq \operatorname {tr} (A)+{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}+\sigma s^{+}(A)\right)<\exp(-\sigma ),}$

dónde . ${\displaystyle s^{+}(A)=\max(\lambda _{\max }(A),0)}$

Véase también

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

Referencias

1. SNBernstein, "Sobre una modificación de la desigualdad de Chebyshev y de la fórmula del error de Laplace", vol. 4, n.° 5 (publicación original: Ann. Sci. Inst. Sav. Ucrania, Sect. Math. 1, 1924)
2. Bernstein, SN (1937). "Об определенных модификациях неравенства Чебышева" [Sobre ciertas modificaciones de la desigualdad de Chebyshev]. Doklady Akademii Nauk SSSR . 17 (6): 275–277.
3. SNBernstein, "Teoría de la probabilidad" (en ruso), Moscú, 1927
4. JVUspensky, "Introducción a la probabilidad matemática", McGraw-Hill Book Company, 1937
5. Freedman, DA (1975). "Sobre las probabilidades de cola para martingalas". Ana. Probablemente . 3 : 100–118.
6. Fan, X.; Grama, I.; Liu, Q. (2012). "Desigualdad de Hoeffding para supermartingalas". Proceso estocástico. Appl . 122 : 3545–3559.
7. Fan, X.; Grama, I.; Liu, Q. (2015). "Desigualdades exponenciales para martingalas con aplicaciones". Revista electrónica de probabilidad . 20 . Electron. J. Probab. 20: 1–22. arXiv : 1311.6273 . doi :10.1214/EJP.v20-3496. S2CID  119713171.
8. Ikhlef, Bechar (2009). "Una desigualdad de tipo Bernstein para procesos estocásticos de formas cuadráticas de variables gaussianas". arXiv : 0909.3595 [math.ST].

(según: SNBernstein, Obras completas, Nauka, 1964)

También se puede encontrar una traducción moderna de algunos de estos resultados en Prokhorov, AV; Korneichuk, NP; Motornyi, VP (2001) [1994], "Desigualdad de Bernstein", Enciclopedia de Matemáticas , EMS Press