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 1 , ..., 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 ), luego, para cada positivo ,![{\displaystyle \varepsilon }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Las desigualdades de Bernstein fueron probadas y publicadas por Sergei Bernstein en las décadas de 1920 y 1930. [1] [2] [3] [4] Posteriormente, estas desigualdades fueron redescubiertas varias veces en diversas formas. Así, los casos especiales de las desigualdades de Bernstein también se conocen como límite de Chernoff , desigualdad de Hoeffding y desigualdad de Azuma . El caso martingala de la desigualdad de Bernstein se conoce como desigualdad de Freedman [5] y su refinamiento se conoce como desigualdad de Hoeffding. [6]
Algunas de las desigualdades
1. Sean variables aleatorias independientes de media cero. Supongamos que casi con seguridad, para todos Entonces, para todos los positivos ,![{\displaystyle X_{1},\ldots,X_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle |X_{i}|\leq M}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle i.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle t}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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}}Monte}}\derecha).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
2. Sean variables aleatorias independientes de media cero. Supongamos que para algún real positivo y cada número entero ,![{\displaystyle X_{1},\ldots,X_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle L}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k\geq 2}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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!}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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]}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
3. Sean variables aleatorias independientes de media cero. Suponer que![{\displaystyle X_{1},\ldots,X_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {k!}{4!}}\left({\frac {L }{5}}\derecha)^{k-4}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
para todo número entero Denotar![{\displaystyle k\geq 4.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A_{k}=\sum \mathbb {E} \left[X_{i}^{k}\right].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
4. Bernstein también demostró generalizaciones de las desigualdades anteriores a variables aleatorias débilmente dependientes. Por ejemplo, la desigualdad (2) se puede ampliar de la siguiente manera. Sean posiblemente variables aleatorias no independientes. Supongamos que para todos los números enteros ,![{\displaystyle X_{1},\ldots,X_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle i>0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 ]}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
para una elección adecuada del parámetro .![{\displaystyle \lambda >0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Generalizaciones
La desigualdad de Bernstein se puede generalizar a matrices aleatorias gaussianas. Sea un escalar donde es una matriz hermitiana compleja y es un vector complejo de tamaño . El vector es un vector gaussiano de tamaño . Entonces para cualquiera , tenemos![{\displaystyle G=g^{H}Ag+2\operatorname {Re} (g^{H}a)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle N}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g\sim {\mathcal {CN}}(0,I)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle N}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \sigma \geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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 ),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
¿Dónde está la operación de vectorización y dónde está el valor propio más grande de ? La prueba se detalla aquí. [8] Otra desigualdad similar se formula como![{\displaystyle \operatorname {vec} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle s^{-}(A)=\max(-\lambda _ {\max }(A),0)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \lambda _ {\max }(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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 ),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
dónde .![{\displaystyle s^{+}(A)=\max(\lambda _ {\max }(A),0)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ver también
Referencias
- ^ SNBernstein, "Sobre una modificación de la desigualdad de Chebyshev y de la fórmula del error de Laplace" vol. 4, #5 (publicación original: Ann. Sci. Inst. Sav. Ucrania, Sect. Math. 1, 1924)
- ^ Bernstein, SN (1937). "Об определенных модификациях неравенства Чебышева" [Sobre ciertas modificaciones de la desigualdad de Chebyshev]. Doklady Akademii Nauk SSSR . 17 (6): 275–277.
- ^ SNBernstein, "Teoría de la probabilidad" (ruso), Moscú, 1927
- ^ JVUspensky, "Introducción a la probabilidad matemática", McGraw-Hill Book Company, 1937
- ^ Freedman, DA (1975). "Sobre las probabilidades de cola para martingalas". Ana. Probablemente . 3 : 100–118.
- ^ Ventilador, X.; Grama, I.; Liu, Q. (2012). "La desigualdad de Hoeffding para las supermartingalas". Proceso estocástico. Aplica . 122 : 3545–3559.
- ^ Ventilador, X.; Grama, I.; Liu, Q. (2015). "Desigualdades exponenciales para martingalas con aplicaciones". Revista Electrónica de Probabilidad . 20 . Electrón. J. Probab. 20: 1–22. arXiv : 1311.6273 . doi :10.1214/EJP.v20-3496. S2CID 119713171.
- ^ Ikhlef, Bechar (2009). "Una desigualdad de tipo Bernstein para procesos estocásticos de formas cuadráticas de variables gaussianas". arXiv : 0909.3595 [matemáticas.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