Matemáticas universitarias — Grado 3 · Bachelor Year 3

22Probabilidad: fundamentos y la ley de los grandes Números

El año 2 construyó probabilidad en espacios contables; medida teoría ahora elimina todas las restricciones. Un espacio de probabilidad es un medir el espacio de masa total $1$ , variables aleatorias son mensurable mapas, expectativa es la integral de Lebesgue — y a la vez todo el arsenal analítico (Capítulos 9, 10 y 11) se aplica a oportunidad. Este capítulo instala el diccionario, construye secuencias infinitas de independiente variables aleatorias (en $\intcc01$ , de dígitos binarios: la aleatoriedad se esconde en su interior medida de lebesgue), demuestra los lemas de Borel-Cantelli y ley cero uno de Kolmogorov, clasifica los modos de convergencia, y demuestra el ley de grandes números — el teorema que hace que las frecuencias converjan a probabilidades y estadísticas posibles. El problema del fin de semana da la prueba de Etemadi del fuerte ley en su forma definitiva $L^1$ .

22.1 el diccionario

Definición 22.1

Un espacio de probabilidad es un medir el espacio $(\Omega, \mathcal A, \P)$ con $\P(\Omega) = 1$ ; Los elementos de $\mathcal A$ son eventos y una propiedad. tiene casi seguramente (a.s.) si su evento tiene probabilidad $1$ . Un variable aleatoria es una aplicación mensurable $X \colon \Omega \to \R$ (o $\R^d$ : un vector aleatorio); su ley es la probabilidad de avance medida $\P_X = X_*\P$ en $\R$ (Ejercicio 11.9), determinada por el función de distribución $F_X(t) = \P(X \leq t)$ (Ejercicio 9.3). $X$ tiene densidad $f$ si $\P_X = f\,\dd\lambda$ ; es discreto si $\P_X$ es un combinación contable de masas de Dirac. el expectativa es

\E[X] = \int_\Omega X\,\dd\P \qquad (X \geq 0 \text{ or } X \in L^1(\P)),

y el teorema de transferencia (Ejercicio 11.9) lo calcula en la ley: $\E[g(X)] = \int_\R g\,\dd\P_X$ — $= \sum g(x_k)p_k$ en el caso discreto, $= \int g(x)f(x)\dd x$ en el caso densidad: fórmulas del año 2, ahora teoremas de una teoría. El diferencia es $\V(X) = \E[(X - \E X)^2] = \E[X^2] - (\E X)^2$ para $X \in L^2$ .

Ejemplo 22.2

El estándar leyes y sus transformaciones destacadas: Bernoulli $\mathcal B(p)$ , binomial $\mathcal B(n, p)$ , geométrico, Poisson $\mathcal P(\lambda)$ (discreto: tablas del año 2 siguen siendo válidos); uniforme en $\intcc01$ (medida de lebesgue mismo); exponencial $\mathcal E(\lambda)$ (densidad $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$ ); el gaussiano $\mathcal N(m, \sigma^2)$ con densidad $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x - m)^2}{2\sigma^2}\bigr)$ — una probabilidad densidad por Problema 10.1, con media $m$ y varianza $\sigma^2$ (momentos gaussianos, Ejercicio 11.10).

Proposición 22.3 (Markov y Chebyshev)

Para $X \geq 0$ y $a > 0$ : $\P(X \geq a) \leq \frac{\E X}{a}$ ; para $X \in L^2$ : $\P\bigl(\abs{X - \E X} \geq a\bigr) \leq \frac{\V(X)}{a^2}$ .

Demostración. Ejercicio 10.5(a); Chebyshev es el aplicado a Markov $(X - \E X)^2$ . ∎

22.2 Independencia

Definición 22.4

Las sub- $\sigma$ -álgebras $\mathcal A_1, \dots, \mathcal A_n \subseteq \mathcal A$ son independiente si $\P(A_1\cap\dots\cap A_n) = \prod\P(A_i)$ para todos los $A_i \in \mathcal A_i$ ; los eventos son independientes si las álgebras $\sigma$ $\{\varnothing, A_i, A_i^c, \Omega\}$ son; variables aleatorias $X_1, \dots, X_n$ si las $\sigma$ -álgebras $\sigma(X_i) = X_i^{-1}(\mathcal B(\R))$ son. Una familia infinita es independiente si cada subfamilia finita lo es.

Teorema 22.5

$X_1, \dots, X_n$ son independiente si el ley del vector $(X_1, \dots, X_n)$ es el medida del producto $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$ . En ese caso, para $g_i \geq 0$ (o tal que los productos sean integrable):

\E\Bigl[\prod_ig_i(X_i)\Bigr] = \prod_i\E[g_i(X_i)],

en particular $\E[XY] = \E X\,\E Y$ y $\V(X_1 + \dots + X_n) = \sum\V(X_i)$ para las variables independiente $L^2$ .

Demostración. Si $X_i$ es independiente, las dos probabilidades medidas $\P_{(X_1,\dots,X_n)}$ y $\bigotimes\P_{X_i}$ están de acuerdo en todo productos $B_1\times\dots\times B_n$ de conjuntos Borel — a $\pi$ -sistema generando $\mathcal B(\R^n)$ (Proposición 11.2(b)) — por lo tanto en todas partes (Teorema 9.7). Por el contrario, un producto ley factoriza todos los eventos $\bigcap_iX_i^{-1}(B_i)$ : independencia. La fórmula expectativa es entonces Tonelli/Fubini (Teorema 11.5) a través del teorema de transferencia; $\E[XY] = \E X\E Y$ es el caso $g_i = \mathrm{id}$ , y al expandir el cuadrado se obtiene la aditividad de variaciones (términos cruzados $\E[(X_i - \E X_i)(X_j - \E X_j)] = 0$ ). ∎

Teorema 22.6 (Existencia de secuencias independientes.)

En $\bigl(\intcc01, \mathcal L, \lambda\bigr)$ existe un secuencia $(U_n)_{n\geq1}$ de independiente variables aleatorias, cada uniforme en $\intcc01$ . En consecuencia, para cualquier prescripción leyes $(\mu_n)$ en $\R$ existe independiente $(X_n)$ con $\P_{X_n} = \mu_n$ .

Demostración. Dígitos. Para $\omega \in \intcc01$ , sea $(b_k(\omega))$ ser sus dígitos binarios ( $\omega = \sum b_k2^{-k}$ ; elija el la expansión no termina en todos los $1$ — la ambigüedad solo se refiere un conjunto contable, por lo tanto nulo). Cada $b_k$ es un aleatorio variable ( $\{b_k = 1\}$ es una unión finita de diádicos intervalos) y el vector $(b_1, \dots, b_m)$ toma cada valor en $\{0,1\}^m$ en un intervalo diádico de longitud $2^{-m}$ : los $b_k$ son independiente Bernoulli $(\frac12)$ .

Reagrupación. Dividir $\N^*$ en infinitos desunidos conjuntos infinitos $(I_n)$ (por ejemplo, por potencias primas o diagonales); deje que $(k^n_j)_j$ enumere $I_n$ y establezca

U_n = \sum_{j\geq1} b_{k^n_j}\,2^{-j} .

Cada $U_n$ es uniforme: sus dígitos binarios son independiente justos bits, entonces $\P(U_n \in [l2^{-m}, (l+1)2^{-m})) = 2^{-m}$ para cada intervalo diádico, y los intervalos diádicos determinan el ley (Teorema 9.7). Los $U_n$ son independiente: son funciones de bloques disjuntos del independiente familia $(b_k)$ — formalmente, eventos $\{U_n \in D_n\}$ para diádico $D_n$ depende de un número finito de dígitos disjuntos conjuntos y factorizar; el argumento del sistema $\pi$ se actualiza a todos los conjuntos de Borel.

Arbitrary leyes. Dejemos que $G_n(u) = \inf\{t : F_{\mu_n}(t) \geq u\}$ (el función cuantil de la distribución función $F_{\mu_n}$ ); la equivalencia de clave $G_n(u) \leq t \iff u \leq F_{\mu_n}(t)$ (continuidad derecha de $F$ , monotonicidad) muestra $X_n = G_n(U_n)$ es mensurable con $\P(X_n \leq t) = \P(U_n \leq F_{\mu_n}(t)) = F_{\mu_n}(t)$ : ley $\mu_n$ ; independencia se hereda (funciones de variables independiente, Ejercicio 22.3). ∎

Ejemplo 22.7 (El problema del cumpleaños, sinceramente.)

Entre $n$ personas con independiente, cumpleaños uniformes terminados $N = 365$ días, la probabilidad de que todos los cumpleaños difieran es

p_n = \prod_{k=1}^{n-1}\Bigl(1 - \frac kN\Bigr),

por condicionamiento iterado (o directamente: el favorable $N(N-1)\cdots(N - n + 1)$ sobre el total $N^n$ , un conteo argumento que la fórmula del producto independencia hace riguroso). Tomando logaritmos y usando $-\ln(1 - x) = x + O(x^2)$ :

\ln p_n = -\frac{n(n-1)}{2N} + O\Bigl(\frac{n^3}{N^2}\Bigr), \qquad\text{so}\qquad p_n \approx \eu^{-n^2/2N} .

El punto de inflexión $p_n = \frac12$ se sitúa en $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$ : para $N = 365$ , $n = 23$ ( $p_{23} = 0.4927$ ). Dos moralejas. Primero, colisiones entre $n$ Los elementos en los cuadros $N$ aparecen en la escala $n \sim \sqrt N$ , no $n \sim N$ — el escala de cumpleaños que gobierna el hash colisiones y el costo $\sqrt N$ de los ataques de cumpleaños en criptografía. En segundo lugar, el cálculo es una plantilla: el $\binom n2$ los eventos de colisión de pares aún no son independiente la respuesta se comporta como si lo fueran ( $\eu^{-\binom n2/N}$ son exactamente los pares independientes heurística) — una primera instancia de la teoría de Poisson aproximación hecha rigurosa en el fin de semana de Capítulo 23 problema (desigualdad de Le Cam).

22.3 Borel–Cantelli y la ley cero-uno

Teorema 22.8 (Borel–Cantelli)

Sea $(A_n)$ eventos y $\limsup A_n = \bigcap_N \bigcup_{n\geq N}A_n$ (“ $A_n$ ocurre infinitamente a menudo”).

Si $\sum\P(A_n) < \infty$ , entonces $\P(\limsup A_n) = 0$ .
Si $\sum\P(A_n) = \infty$ and the $A_n$ are independiente, entonces $\P(\limsup A_n) = 1$ .

Demostración. (1) es Ejercicio 9.4. (2): para $N \leq M$ , independencia de complementos (Ejercicio 22.3) da

\P\Bigl(\bigcap_{n=N}^{M}A_n^c\Bigr) = \prod_{n=N}^M\bigl(1 - \P(A_n)\bigr) \leq \exp\Bigl(-\sum_{n=N}^M\P(A_n)\Bigr) \xrightarrow[M \to \infty]{} 0

( $1 - x \leq \eu^{-x}$ ; la serie diverge). entonces $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ por cada $N$ , y la intersección decreciente sobre $N$ todavía tiene probabilidad $1$ (continuidad desde arriba, Proposición 9.6). ∎

Teorema 22.9 (Ley cero-uno de Kolmogorov)

Sea $(X_n)$ independiente y $\mathcal T = \bigcap_N\sigma(X_N, X_{N+1}, \dots)$ tail $\sigma$ -algebra (eventos insensible a cualquier número finito del $X_n$ : convergencia de $\sum X_n$ , de $\frac{S_n}n$ , valores de $\limsup$ ’s, …). Entonces cada $T \in \mathcal T$ tiene $\P(T) \in \{0, 1\}$ .

Demostración. Reparar $N$ . Las álgebras $\sigma$ $\sigma(X_1, \dots, X_N)$ y $\sigma(X_{N+1}, \dots)$ son independiente: eventos dependiendo de los bloques disjuntos se factorizan en los sistemas generadores $\pi$ (cilindros $\bigcap_{i\leq N}\{X_i \in B_i\}$ , resp. finito condiciones en variables posteriores), y Dynkin (Teorema 9.4, aplicado dos veces, un lado a la vez tiempo) extiende la factorización. Un evento de cola $T$ se encuentra en $\sigma(X_{N+1}, \dots)$ por cada $N$ : $T$ es independiente de cada $\sigma(X_1, \dots, X_N)$ , por lo tanto del álgebra $\sigma$ generan, $\sigma(X_1, X_2, \dots)$ (Dynkin una vez más: la unión del $\sigma(X_1,\dots,X_N)$ es un sistema $\pi$ generarlo). Pero $T \in \sigma(X_1, X_2, \dots)$ también: $T$ es independiente de si mismo, $\P(T) = \P(T\cap T) = \P(T)^2$ : $\P(T) \in \{0, 1\}$ . ∎

22.4 Modos de convergencia

Definición 22.10

$X_n \to X$ casi seguramente si $\P(X_n \to X) = 1$ ; en probabilidad si $\P(\abs{X_n - X} \geq \varepsilon) \to 0$ por cada $\varepsilon > 0$ ; in $L^p$ si $\E\abs{X_n - X}^p \to 0$ .

Proposición 22.11

(a) la convergencia a.s. implica convergencia en probabilidad; (b) La convergencia $L^p$ implica convergencia en probabilidad; (c) la convergencia en probabilidad implica a.s. convergencia a lo largo de una subsecuencia; (d) ninguna otra implicación es válida en general.

Demostración. (a) $\P(\abs{X_n - X} \geq \varepsilon) \leq \P\bigl(\sup_{m\geq n}\abs{X_m - X} \geq \varepsilon\bigr) \downarrow \P\bigl(\limsup\{\abs{X_m - X} \geq \varepsilon\}\bigr) = 0$ bajo a.s. convergencia (continuidad desde arriba; el evento limsup excluye la convergencia). (b) Markov: $\P(\abs{X_n - X} \geq \varepsilon) \leq \varepsilon^{-p}\,\E\abs{X_n - X}^p$ . (c) Elija $n_k$ con $\P(\abs{X_{n_k} - X} \geq 2^{-k}) \leq 2^{-k}$ ; Borel–Cantelli (1) marca $\abs{X_{n_k} - X} < 2^{-k}$ finalmente, como. (d) La máquina de escribir (Ejercicio 12.3) en $(\intcc01, \lambda)$ converge en $L^1$ y en probabilidad pero en ninguna parte puntualmente; $n\mathbf 1_{\intoo0{1/n}} \to 0$ a.s. pero no en $L^1$ ; detalles y el resto contraejemplos en Ejercicio 22.6. ∎

22.5 La ley de los grandes números.

En todo momento, $(X_n)$ son independiente con el mismo ley. (i.i.d.), $S_n = X_1 + \dots + X_n$ .

Teorema 22.12 (Ley débil de los grandes números)

Si $X_1 \in L^2$ , con $m = \E X_1$ :

\P\Bigl(\Bigl|\frac{S_n}{n} - m\Bigr| \geq \varepsilon\Bigr) \leq \frac{\V(X_1)}{n\,\varepsilon^2} \xrightarrow[n\to\infty]{} 0 :

$\frac{S_n}n \to m$ en probabilidad (y en $L^2$ ).

Demostración. $\E\frac{S_n}n = m$ y $\V\bigl(\frac{S_n}n\bigr) = \frac{n\V(X_1)}{n^2}$ (Teorema 22.5); Chebyshev. ∎

Teorema 22.13 (Ley fuerte de los grandes números.)

Si $X_1 \in L^1$ , entonces

\frac{S_n}{n} \xrightarrow[n\to\infty]{\text{a.s.}} \E[X_1].

Lo demostramos aquí bajo la hipótesis más fuerte $X_1 \in L^4$ ; el caso general ( $L^1$ : prueba de Etemadi) es el problema del fin de semana.

Prueba bajo $\E X_1^4 < \infty$ . Centrado ( $X_i \mapsto X_i - m$ ), suponga $m = 0$ . Ampliar:

\E[S_n^4] = \sum_{i,j,k,l}\E[X_iX_jX_kX_l] = n\,\E[X_1^4] + 3n(n-1)\,\bigl(\E[X_1^2]\bigr)^2 \leq C\,n^2 ,

desde independencia y centrando eliminan todos los términos que contienen un factor aislado ( $\E[X_iX_jX_kX_l] = \E[X_i]\E[\cdots] = 0$ a menos que los índices se emparejen: el único Los supervivientes son los términos $n$ $i=j=k=l$ y $3n(n-1)$ . términos con dos pares distintos). Markov:

\P\Bigl(\Bigl|\frac{S_n}n\Bigr| \geq \varepsilon\Bigr) = \P\bigl(S_n^4 \geq n^4\varepsilon^4\bigr) \leq \frac{Cn^2}{n^4\varepsilon^4} = \frac{C}{\varepsilon^4n^2},

sumable: Borel-Cantelli (1) da, para cada racional $\varepsilon$ , que $\abs{S_n/n} < \varepsilon$ eventualmente, como; intersección sobre $\varepsilon \in \Q_+^*$ (contablemente muchos eventos de probabilidad- $1$ ): $S_n/n \to 0$ a.s. ∎

Ejemplo 22.14 (Lo que compra la ley fuerte)

(a) Frecuencias: para i.i.d. lanzamientos de moneda, el observado frecuencia de cabezas converge a.s. a $p$ — el empírico justificación de la probabilidad misma. (b) Montecarlo: para $g \in L^1(\intcc01)$ y $(U_n)$ i.i.d. uniforme (Teorema 22.6), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ a.s.: integrales por muestreo, en cualquier dimensión, en el independiente de la dimensión tarifa $\sim n^{-1/2}$ precisada en Capítulo 23. (c) Números normales: casi todo número real tiene, en su expansión binaria, frecuencia asintótica $\frac12$ de unos (Aplique el fuerte ley a las variables de dígitos de Teorema 22.6) — Teorema de Borel, a declaración sobre los números de cadaday probados por medida: Problema 22.1 completa en todas las bases.

Método 22.15

El orden de funcionamiento de enunciados asintóticos sobre el azar. secuencias: (1) ¿Es el evento un evento de cola? Entonces es la probabilidad es $0$ o $1$ (Teorema 22.9) y solo hay que decidir cual. (2) To prove a.s. statements: Borel–Cantelli — probabilidades sumables para el Eventos "malos", a través de límites tipo Markov/Chebyshev en cualesquiera momentos que existan; independencia sólo es necesario para el dirección inversa. (3) Subsecuencia + sándwich: probar convergencia a lo largo de una subsecuencia manejable, controlar la oscilación intermedia por monotonicidad o máxima Desigualdades: el esqueleto de la prueba de Etemadi. (4) Para límites de distribución, espere Capítulo 23.

22.6 Ceremonias

Ejercicio 22.1 ★

(a) Sea $X$ tener continuo distribución estrictamente creciente función $F$ . Demuestre que $F(X)$ es uniforme en $\intcc01$ , y que $G(U) \sim F$ para $U$ uniforme, $G = F^{-1}$ : simulación por inversión. (b) Calcule la función de distribución y densidad de $X^2$ para $X$ uniforme en $\intcc{-1}1$ , y de $-\frac1\lambda\ln U$ para $U$ uniforme en $\intoo01$ .

Solución

Solución de Ejercicio 22.1.

(a) Para $u \in \intoo01$ : $\P(F(X) \leq u) = \P(X \leq F^{-1}(u)) = F(F^{-1}(u)) = u$ (continuidad y estricta La monotonicidad hace de $F$ una biyección sobre $\intoo01$ con $\{F(X) \leq u\} = \{X \leq F^{-1}(u)\}$ ): $F(X)$ es uniforme. Por el contrario $\P(G(U) \leq t) = \P(U \leq F(t)) = F(t)$ : a simular un ley, aplicar la función de distribución inversa a un muestra uniforme.

(b) $Y = X^2$ , $X$ uniforme en $\intcc{-1}1$ : para $t \in \intcc01$ , $F_Y(t) = \P(-\sqrt t \leq X \leq \sqrt t) = \sqrt t$ : densidad $\frac1{2\sqrt t}\mathbf 1_{\intoo01}$ . y $\P\bigl(-\frac1\lambda\ln U \leq t\bigr) = \P(U \geq \eu^{-\lambda t}) = 1 - \eu^{-\lambda t}$ : el exponencial $\mathcal E(\lambda)$ — inversión en acción.

Ejercicio 22.2 ★

(a) Calcule la media y la varianza de Poisson $\mathcal P(\lambda)$ y geométrico leyes mediante el teorema de transferencia. (b) Demuestre que un variable aleatoria $T$ positivo con $\P(T > t) > 0$ para todos los $t$ satisface la propiedad sin memoria $\P(T > t + s \mid T > t) = \P(T > s)$ para todos los $s, t \geq 0$ si $T$ es exponencial. (The survival function satisfies Cauchy’s functional equation; monotonicity replaces continuidad.)

Solución

Solución de Ejercicio 22.2.

(a) Poisson: $\E X = \sum_{k\geq0}k\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \lambda$ , $\E[X(X-1)] = \lambda^2$ , entonces $\V = \lambda^2 + \lambda - \lambda^2 = \lambda$ . Geométrico ( $\P(X = k) = p(1-p)^{k-1}$ ): $\E X = \frac1p$ , $\V = \frac{1-p}{p^2}$ (diferenciar la serie geométrica dos veces).

(b) $G(t) = \P(T > t)$ no aumenta con $G(0^+)\dots$ $G \colon \intco0\infty \to \intoc01$ ; la falta de memoria lee $G(t + s) = G(t)G(s)$ . Entonces $G(n t) = G(t)^n$ y $G(t/n) = G(t)^{1/n}$ : $G(q) = G(1)^q$ para $q \geq 0$ racional; escribiendo $G(1) = \eu^{-\lambda}$ ( $\in \intoo01$ : $G(1) = 1$ sería fuerza $G \equiv 1$ , imposible para un variable aleatoria finito; $G(1) = 0$ está excluido por hipótesis) y apretando un $t$ arbitrario entre racionales (monotonicidad): $G(t) = \eu^{-\lambda t}$ — el exponencial ley. Lo contrario es un cálculo.

Ejercicio 22.3 ★★

(a) Demuestre que si $X_1, \dots, X_n$ son independiente y $f_i$ son funciones de Borel, las $f_i(X_i)$ son independiente. (b) Demuestre que los eventos $A_1, \dots, A_n$ son independiente si y así sus complementos son, si los indicadores $\mathbf 1_{A_i}$ son independiente variables aleatorias. (c) (Por parejas es más débil) Dos monedas justas: $A =$ la primera es cara, $B =$ el segundo es cara, $C =$ los dos están de acuerdo. Mostrar $A, B, C$ son independiente en pares pero no independiente.

Solución

Solución de Ejercicio 22.3.

(a) $\sigma(f_i(X_i)) = f_i(X_i)^{-1}(\mathcal B) \subseteq X_i^{-1}(\mathcal B) = \sigma(X_i)$ ( $f_i$ Borel), y sub- $\sigma$ -álgebras de independiente $\sigma$ -álgebras son independiente (la identidad definitoria es válida a fortiori).

(b) $\sigma(A_i) = \{\varnothing, A_i, A_i^c, \Omega\} = \sigma(A_i^c) = \sigma(\mathbf 1_{A_i})$ : los tres declaraciones afirman independencia del mismo $\sigma$ -álgebras. (Esa factorización sobre el $A_i$ se propaga a complementos es el argumento del sistema $\lambda$ dentro de la equivalencia de Definición 22.4 — o inclusión-exclusión directa.)

(c) $\P(A) = \P(B) = \P(C) = \frac12$ ; $A\cap B = A\cap C = B\cap C$ en pares: cada intersección es “ambas caras” o análogo, de probabilidad $\frac14$ : por pares independiente. Pero $\P(A\cap B\cap C) = \P(\text{HH}) = \frac14 \neq \frac18$ : no independiente — $C$ está determinado por $A$ y $B$ .

Ejercicio 22.4 ★★

(a) (Mono infinito) Una secuencia i.i.d. de uniforme pulsaciones de teclas en un alfabeto finito como contiene cada finito texto infinitamente a menudo: pruébalo con Borel–Cantelli (2) en bloques disjuntos. (b) (Ejecuciones) Para i.i.d. bits justos, sea $R_n$ la longitud de la serie de unos que comienzan en la posición $n$ . Muestra ese culo $R_n \geq (1+\varepsilon)\log_2n$ con frecuencia finita y $R_n \geq \log_2 n$ con frecuencia infinita (both halves of Borel–Cantelli; for the second, pass to disjoint blocks to gain independencia): la ejecución más larga en los primeros dígitos $n$ crece como $\log_2n$ .

Solución

Solución de Ejercicio 22.4.

(a) Deje que el texto $T$ tenga una longitud $L$ y $q = a^{-L}$ ( $a$ el tamaño del alfabeto). Los eventos $E_k = \{$ posiciones $kL+1, \dots, (k+1)L$ hechizo $T\}$ son independiente (bloques disjuntos de letras i.i.d., cada una de probabilidad $q > 0$ : $\sum\P(E_k) = \infty$ , y Borel–Cantelli (2) da infinitas ocurrencias como

(b) Superior: $\P\bigl(R_n \geq (1+\varepsilon)\log_2n\bigr) \leq 2^{-(1+\varepsilon)\log_2n} = n^{-(1+\varepsilon)}$ , sumable: por Borel–Cantelli (1), a.s. sólo un número finito tal $n$ . Inferior: empaquetar bloques separados — el $j$ -ésimo de longitud $\ell_j = \lceil\log_2s_j\rceil$ a partir de $s_j = \sum_{i<j}\ell_i$ ; los eventos “el bloque $j$ son todos unos” son independiente con probabilidad $2^{-\ell_j} \asymp \frac1{s_j} \asymp \frac1{j\log_2 j}$ , cuya suma diverge: Borel–Cantelli (2) da infinitos bloques todos unos, es decir, $R_{s_j} \geq \log_2 s_j$ infinitamente frecuente. Juntos: la longitud máxima de ejecución en los primeros dígitos $n$ es $(1 + o(1))\log_2n$ como

Ejercicio 22.5 ★★

Sea $(X_n)$ independiente. (a) Demuestre que el radio de convergencia de $\sum X_n z^n$ es una constante a.s. (posiblemente $0$ o $\infty$ ). (b) Demuestre que $\P(\sum X_n \text{ converges}) \in \{0, 1\}$ y $\P(S_n/n \to m) \in \{0,1\}$ . (c) Darle una cola a un evento sobre $(X_n)$ que sea no evento y verifique que el ley cero uno pueda fallar.

Solución

Solución de Ejercicio 22.5.

(a) $R = \bigl(\limsup\abs{X_n}^{1/n}\bigr)^{-1}$ es sin cambios si se modifican un número finito de $X_n$ : por cada $N$ , $R$ es medible $\sigma(X_N, X_{N+1}, \dots)$ , es decir, cola medible. Entonces cada evento $\{R \leq c\}$ tiene probabilidad $0$ o $1$ (Teorema 22.9), entonces la función de distribución de $R$ toma solo los valores $0, 1$ : salta en un solo punto $c_0 \in \intcc0{+\infty}$ , y $R = c_0$ a.s.

(b) La convergencia de $\sum X_n$ y de $\frac{S_n}n$ son insensible a cambiar un número finito de términos (para el segundo: los términos modificados contribuyen $O(1/n) \to 0$ ): eventos de cola; ley cero uno.

(c) $\{X_1 > 0\}$ depende de $X_1$ : para signos i.i.d. ( $\P(X_1 = \pm1) = \frac12$ ), su probabilidad es $\frac12 \notin \{0,1\}$ — no hay contradicción, no es cola evento.

Ejercicio 22.6 ★★

En $(\intcc01, \lambda)$ , presente — con pruebas — aleatorio variables tal que: (a) $X_n \to 0$ en probabilidad y en cada $L^p$ , pero en ninguna parte como; (b) $X_n \to 0$ a.s. pero en el número $L^p$ ; (c) $X_n \to 0$ en $L^1$ pero no en $L^2$ ; (d) y muestre: si $X_n \to X$ en probabilidad y $\abs{X_n} \leq Y \in L^1$ , entonces $X_n \to X$ en $L^1$ (subsecuencias + convergencia dominada + el truco de la subsecuencia).

Solución

Solución de Ejercicio 22.6.

Trabajar en $(\intcc01, \lambda)$ . (a) La máquina de escribir $\mathbf 1_{I_n}$ (Ejercicio 12.3): $\norm{X_n}_p^p = \lambda(I_n) \to 0$ (todos $p < \infty$ ), por lo tanto también en probabilidad; en cada $\omega$ los valores $0$ y $1$ se repiten: no puntualmente convergencia en cualquier lugar. (b) $X_n = n\mathbf 1_{\intoo0{1/n}} \to 0$ de $0$ , pero $\norm{X_n}_p \geq n^{1 - 1/p} \geq 1$ . (c) $X_n = \sqrt n\,\mathbf 1_{\intoo0{1/n}}$ : $\E\abs{X_n} = n^{-1/2} \to 0$ , $\E X_n^2 = 1$ . (d) De cualquier extracto de subsecuencia (convergencia en probabilidad) otra subsecuencia convergente a.s. (Proposición 22.11(c)); convergencia dominada da convergencia $L^1$ a lo largo de él, con el límite mismo $X$ . Así, cada subsecuencia de la secuencia numérica $\E\abs{X_n - X}$ tiene una subsecuencia que tiende a $0$ : la toda la secuencia tiende a $0$ .

Ejercicio 22.7 ★★

Una encuesta de opinión estima una proporción desconocida $p$ según el Frecuencia empírica $\hat p_n$ de sorteos $n$ independiente. (a) Chebyshev: muestre $\P(\abs{\hat p_n - p} \geq \varepsilon) \leq \frac1{4n\varepsilon^2}$ (use $p(1-p) \leq \frac14$ ). (b) ¿Cuántos sorteos garantizan un error $\leq 3\%$ con probabilidad $\geq 95\%$ por este límite? (La verdadera respuesta, vía Capítulo 23, se trata de $1070$ : Chebyshev es honesto pero crudo.)

Solución

Solución de Ejercicio 22.7.

(a) $\hat p_n = \frac{S_n}n$ con el binomio $S_n$ : $\V(\hat p_n) = \frac{p(1-p)}n \leq \frac1{4n}$ y Chebyshev (Proposición 22.3) da el límite. (b) Resuelva $\frac1{4n(0.03)^2} \leq 0.05$ : $n \geq \frac{1}{4\cdot0.0009\cdot0.05} \approx 5556$ . el central El teorema del límite justificará $n \approx 1070$ para el mismo garantía: Chebyshev paga su generalidad con un factor $\approx 5$ .

Ejercicio 22.8 ★★★

(Bernstein) Para $f \in \mathcal C(\intcc01)$ defina el Polinomio de Bernstein $B_nf(x) = \sum_{k=0}^n\binom nkx^k(1-x)^{n-k}f\bigl(\frac kn\bigr)$ . (a) Reconozca $B_nf(x) = \E\bigl[f\bigl(\frac {S_n}n\bigr)\bigr]$ para el binomio $S_n$ $\mathcal B(n, x)$ . (b) Demostrar $B_nf \to f$ uniformemente en $\intcc01$ : división en $\{\abs{\frac{S_n}n - x} \leq \delta\}$ y su complemento, utilizando el uniforme continuidad y Chebyshev con el cota uniformemente $\V(\frac{S_n}n) \leq \frac1{4n}$ . (c) Concluir: una segunda prueba probabilística de la Teorema de aproximación de Weierstrass (Corolario 7.16), con la tarifa explícita $\norm{B_nf - f}_\infty \leq \frac32\,\omega_f(n^{-1/2})$ para el módulo de continuidad $\omega_f$ — demostrar al menos el formulario $O(\omega_f(n^{-1/2}))$ .

Solución

Solución de Ejercicio 22.8.

(a) Si $S_n \sim \mathcal B(n, x)$ , el teorema de transferencia da $\E\bigl[f(\frac{S_n}n)\bigr] = \sum_k\binom nkx^k(1-x)^{n-k}f(\frac kn) = B_nf(x)$ .

(b)–(c) Sea $\omega = \omega_f$ el módulo de continuidad ( $\abs{f(u) - f(v)} \leq \omega(\abs{u - v})$ y $\omega(c \delta) \leq (1 + c)\,\omega(\delta)$ encadenando pasos). Luego, para cualquier $\delta > 0$ ,

\abs{f(u) - f(x)} \leq \Bigl(1 + \frac{(u - x)^2}{\delta^2}\Bigr)\omega(\delta)

(si $\abs{u - x} \leq \delta$ , claro; en caso contrario $\omega(\abs{u-x}) \leq (1 + \frac{\abs{u-x}}\delta) \omega(\delta) \leq (1 + \frac{(u-x)^2}{\delta^2}) \omega(\delta)$ ). Tome esperanzas de heredar en $u = \frac{S_n}n$ :

\abs{B_nf(x) - f(x)} \leq \Bigl(1 + \frac{\V(S_n/n)}{\delta^2}\Bigr)\omega(\delta) \leq \Bigl(1 + \frac{1}{4n\delta^2}\Bigr)\omega(\delta) ;

con $\delta = n^{-1/2}$ : $\norm{B_nf - f}_\infty \leq \frac54\,\omega\bigl(n^{-1/2}\bigr) \leq \frac32\,\omega\bigl(n^{-1/2}\bigr) \to 0$ (uniforme continuidad en compacto): un Weierstrass probabilístico teorema, con una tasa explícita y uniforme.

Ejercicio 22.9 ★★★

(Coleccionista de cupones) Las tarjetas del tipo $n$ se extraen de manera uniforme con reemplazo; sea $T_n$ el número de sorteos hasta que todos Se ven tipos. (a) Escriba $T_n = \sum_{k=1}^{n}\tau_k$ con $\tau_k$ geométrico del parámetro $\frac{n - k + 1}n$ , el $\tau_k$ independiente, y deducir $\E T_n = n\,H_n \sim n\ln n$ ( $H_n$ el número de armónico) y $\V(T_n) \leq \frac{\pi^2}6n^2$ . (b) Chebyshev: $\frac{T_n}{n\ln n} \to 1$ en probabilidad. (c) Refinar con Borel–Cantelli: mostrar directamente $\P(T_n > \beta n\ln n) \leq n^{1 - \beta}$ para $\beta > 1$ (union bound on the event that some type is missed after $\beta n\ln n$ draws, using $1 - x \leq \eu^{-x}$ ), y deducir eso a lo largo de $n = 2^m$ , a.s. $T_n \leq \beta n\ln n$ eventualmente, por cada $\beta > 2$ .

Solución

Solución de Ejercicio 22.9.

(a) Después de recopilar los tipos $k - 1$ , cada sorteo es nuevo con probabilidad $p_k = \frac{n-k+1}n$ : $\tau_k$ es geométrica $(p_k)$ y $\tau_k$ son independiente (los sorteos son). Sumas: $\E T_n = \sum_k\frac n{n-k+1} = nH_n \sim n\ln n$ ; $\V(T_n) = \sum\frac{1 - p_k}{p_k^2} \leq n^2\sum_{j=1}^n\frac1{j^2} \leq \frac{\pi^2}6n^2$ .

(b) Chebyshev: $\P\bigl(\abs{T_n - nH_n} \geq \varepsilon n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2n} \to 0$ y $\frac{nH_n}{n\ln n} \to 1$ : $\frac{T_n}{n\ln n} \to 1$ en probabilidad.

(c) Con destino a la unión: $T_n > t$ significa que algún tipo no se ve después $\lceil t\rceil$ empata, por lo que $\P(T_n > t) \leq n(1 - \frac1n)^{t} \leq n\,\eu^{-t/n}$ ; en $t = \beta n\ln n$ : $\leq n^{1 - \beta}$ . Para $\beta > 1$ , $\sum_m 2^{m(1-\beta)} < \infty$ : Borel–Cantelli da, junto con $n = 2^m$ , a.s. $T_n \leq \beta n\ln n$ eventualmente — en particular para cada $\beta > 2$ como se indica (cualquier $\beta > 1$ funciona a lo largo de la subsecuencia).

Ejercicio 22.10 ★★

Usando la construcción de dígitos (Teorema 22.6): (a) verificar mediante cálculo directo que $U = \sum b_{2k}2^{-k}$ (dígitos pares indexados de un $\omega$ uniforme) es uniforme y independiente de $V = \sum b_{2k-1}2^{-k}$ ; (b) deducir una biyección mensurable hasta conjuntos nulos entre $\intcc01$ y $\intcc01^2$ conservando medida y comenta: un número aleatorio uniforme contiene dos (y muchos contables) independiente unos — comparar con la curva de Peano (Problema 6.1), que logró sobreyectividad pero no preservación de la medida o inyectividad.

Solución

Solución de Ejercicio 22.10.

(a) Los dígitos pares $(b_{2k})_k$ son i.i.d. justos bits (una subfamilia de la familia de dígitos independiente), por lo que $U = \sum_kb_{2k}2^{-k}$ le da a cada intervalo diádico su valor correcto probabilidad (como en Teorema 22.6): uniforme; igualmente $V$ ; y $(U, V)$ dependen de bloques de dígitos separados: independiente (factorización en rectángulos diádicos, luego Dynkin).

(b) $\Phi(\omega) = (U(\omega), V(\omega))$ es mensurable con $\Phi_*\lambda = \lambda\otimes\lambda = \lambda_2$ (acuerdo sobre rectángulos diádicos + unicidad). Intercalado dígitos define un inverso definido a partir del conjunto (nulo) de racionales diádicos en cualquier factor: una medida que preserva biyección entre medida completa subconjuntos de $\intcc01$ y $\intcc01^2$ . Contraste con Peano (Problema 6.1): continuidad sobreyectividad forzada sin inyectividad; dejando caer continuidad por mera mensurabilidad compra un isomorfismo de medida — la dimensión es invisible para la teoría medida, visible para topología.

Ejercicio 22.11 ★★

(Registros) Sea $(X_n)_{n\geq1}$ i.i.d. con continuo función de distribución, y digamos que ocurre un registro en tiempo $n$ si $X_n > \max(X_1, \dots, X_{n-1})$ (el tiempo $1$ es un registro). Sea $R_n$ el indicador de registro. (a) Mostrar $\P(R_n = 1) = \frac1n$ (by symmetry, each of the $n!$ orderings of $X_1, \dots, X_n$ is equally likely and ties have probability $0$ ). (b) Demuestre que los $R_n$ son independiente (count orderings compatible with prescribed record positions, or argue that the relative order of $X_1, \dots, X_{n-1}$ is independiente of the rank of $X_n$ among them). (c) Deducir de Borel–Cantelli (Teorema 22.8, ambas mitades) que infinitos registros ocurren como, pero los registros en veces consecutivas $n, n+1$ ocurren infinitamente con probabilidad — ¡decide cuál! — y calcular $\sum_n\P(R_n = 1, R_{n+1} = 1)$ .

Solución

Solución de Ejercicio 22.11.

(a) Continuidad de la distribución hace que los empates sean eventos nulos (como en los argumentos de las estadísticas de orden del capítulo), y el Los pedidos relativos de $n!$ de $(X_1, \dots, X_n)$ son intercambiables y, por tanto, igualmente probables. $R_n = 1$ significa el el máximo se sitúa en la última posición: probabilidad $\frac{(n-1)!}{n!} = \frac1n$ .

(b) Corrija $n$ y condición sobre el orden relativo de $X_1, \dots, X_{n-1}$ : insertar $X_n$ en el rango posible $n$ las ranuras son uniformes y independiente de ese orden (intercambiabilidad de la tupla $n$ ). Por lo tanto $R_n$ (el evento “ $X_n$ ocupa el primer lugar”) es independiente del total registrar el historial $(R_1, \dots, R_{n-1})$ , que es una función del orden relativo de las primeras variables $n - 1$ . La inducción proporciona independencia completo con $\P(R_n = 1) = \frac1n$ .

(c) $\sum\P(R_n = 1) = \sum\frac1n = \infty$ con independencia: la segunda parte Borel–Cantelli da récords infinitamente a menudo a.s. (los registros nunca se detienen — pero adelgazar logarítmicamente: $\E[\#\text{records} \leq n] = H_n \approx \ln n$ ). Registros consecutivos: $\P(R_n = R_{n+1} = 1) = \frac1{n(n+1)}$ (independencia), y

\sum_n\frac1{n(n+1)} = \sum_n\Bigl(\frac1n - \frac1{n+1}\Bigr) = 1 < \infty :

la primera mitad Borel-Cantelli se aplica — sólo de forma limitada Se producen muchos pares de registros consecutivos, como.

Ejercicio 22.12 ★★

(Carrera más larga) Lanza una moneda justa infinitas veces y sea $L_n$ la longitud de la ejecución más larga de secuencias consecutivas cabezas dentro de los primeros giros $n$ . (a) Demuestre que para cada $\varepsilon > 0$ , a.s. $L_n \leq (1 + \varepsilon)\log_2n$ eventualmente (the probability that some run of length $\ell$ starts among the first $n$ flips is at most $n2^{-\ell}$ ; Borel–Cantelli along $n = 2^k$ ). (b) Demuestre que a.s. $L_n \geq (1 - \varepsilon)\log_2n$ eventualmente (chop the first $n$ flips into $\lfloor n/\ell\rfloor$ disjoint blocks of length $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ ; the blocks are independiente, each all-heads with probability $2^{-\ell}$ , and the probability that none is all-heads is at most $\exp(-n2^{-\ell}/\ell)$ ; sum along $n = 2^k$ again). (c) Concluir $\frac{L_n}{\log_2n} \to 1$ a.s.: en un millón En los lanzamientos justos se debe esperar una serie de aproximadamente $20$ cabezas — y probablemente se haya fabricado un conjunto de datos sin uno.

Solución

Solución de Ejercicio 22.12.

(a) Un tramo de longitud $\ell$ que comienza en la posición $i \leq n$ tiene probabilidad $2^{-\ell}$ ; vinculado a la unión: $\P(L_n \geq \ell) \leq n2^{-\ell}$ . Con $\ell_n = (1 + \varepsilon)\log_2n$ : $\P(L_n \geq \ell_n) \leq n^{-\varepsilon}$ . A lo largo de $n = 2^k$ : $\sum_k2^{-k\varepsilon} < \infty$ , entonces a.s. $L_{2^k} < (1+\varepsilon)k$ eventualmente (Borel–Cantelli); para generales $n$ elige $2^{k-1} < n \leq 2^k$ y usa la monotonicidad de $L_n$ más $\log_22^{k-1} \leq \log_2n$ : $L_n \leq L_{2^k} < (1 + \varepsilon)k \leq (1 + \varepsilon)\frac{k}{k-1} \log_2n$ , y el factor extra se absorbe ampliando $\varepsilon$ ligeramente.

(b) Con $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ y $m = \lfloor n/\ell\rfloor$ bloques disjuntos: los bloques son independiente, cada cara con probabilidad $2^{-\ell} \geq n^{-(1-\varepsilon)}/2$ , por lo que

\P(L_n < \ell) \leq \bigl(1 - 2^{-\ell}\bigr)^{m} \leq \exp\bigl(-m2^{-\ell}\bigr) \leq \exp\Bigl(-c\,\frac{n^{\varepsilon}}{\log_2n}\Bigr)

para una constante $c > 0$ y $n$ grande. Estas probabilidades son sumables a lo largo de $n = 2^k$ (de hecho, a lo largo de todo $n$ ): Borel–Cantelli finalmente da a.s. $L_n \geq (1 - \varepsilon)\log_2n$ (la monotonicidad completa entre el $2^k$ como en (a), sin causar daño).

(c) Ambos límites a lo largo de una secuencia $\varepsilon = \frac1j$ , intersectando contablemente muchos eventos medida completa: $\frac{L_n}{\log_2n} \to 1$ como Para $n = 10^6$ : $\log_2n \approx 19.9$ — una serie de cabezales $\approx 20$ no es un anomalía sospechosa sino una certeza matemática, y su La ausencia es evidencia de un ser humano fingiendo "aleatoriedad" (los humanos rara vez se atreve a escribir más de $5$ o $6$ cabezas seguidas).

22.7 Problema: la prueba de la ley fuerte de Etemadi

Problema 22.1

Problema del fin de semana — la ley fuerte de los grandes números para i.i.d. variables integrables

El fuerte ley de Kolmogorov — $\frac{S_n}n \to \E X_1$ a.s. para i.i.d. $X_n \in L^1$ — durante mucho tiempo sólo tuvo pruebas intrincadas; en 1981 N. Etemadi encontró uno de sorprendente economía, utilizando nada más allá de este capítulo (e incluso debilitando independencia a pares independencia). Lo seguimos. Sea $(X_n)$ independiente por pares, distribuido idénticamente, integrable; $m = \E X_1$ , $S_n = X_1 + \dots + X_n$ .

Parte I — Reductions.

Demostrar que es suficiente tratar $X_n \geq 0$ (split $X_n = X_n^+ - X_n^-$ : check the two halves are again pairwise independiente i.i.d. integrable). Supongamos en adelante $X_n \geq 0$ .
(truncamiento) Deje $Y_n = X_n\,\mathbf 1_{X_n \leq n}$ y $S_n^* = Y_1 + \dots + Y_n$ . Mostrar

$\sum_{n\geq1}\P(X_n \neq Y_n) = \sum_{n\geq1}\P(X_1 > n) \leq \E[X_1] < \infty$

(Ejercicio 11.3), y deducir vía Borel–Cantelli que $\frac{S_n - S_n^*}{n} \to 0$ a.s.: basta con probar $\frac{S^*_n}n \to m$ como
Mostrar $\E Y_n = \E\bigl[X_1\mathbf 1_{X_1\leq n}\bigr] \to m$ (convergencia monótona), por lo tanto $\frac1n\sum_{k\leq n}\E Y_k \to m$ (Cesàro): es basta con probar $\frac{S_n^* - \E S_n^*}{n} \to 0$ como

Parte II — The variance estimate.

Mostrar

$\V(Y_n) \leq \E[Y_n^2] = \E\bigl[X_1^2\,\mathbf 1_{X_1 \leq n}\bigr]$

y, usando el pastel de capas (Proposición 11.8), la llave encuadernada

$\sum_{n\geq1}\frac{\V(Y_n)}{n^2} \leq \sum_{n\geq1}\frac1{n^2}\, \E\bigl[X_1^2\mathbf 1_{X_1\leq n}\bigr] \leq C\,\E[X_1] < \infty$

(exchange the sum and the expectativa — Tonelli for series — and bound $\sum_{n \geq x}\frac1{n^2} \leq \frac2{\max(x,1)}$ for the inner estimate $x^2\sum_{n\geq x}n^{-2} \leq 2x$ ).

Parte III — Convergence along geometric subsequences. Repare $\alpha > 1$ y deje que $k_j = \lfloor\alpha^j\rfloor$ .

Usando independencia por pares (las variaciones se suman, Teorema 22.5 — comprueba que la aditividad de las varianzas solo necesita por pares independencia) y Chebyshev, espectáculo para todos $\varepsilon > 0$ :

$\sum_{j\geq1}\P\Bigl(\Bigl| \frac{S^*_{k_j} - \E S^*_{k_j}}{k_j}\Bigr| \geq \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j\geq1}\frac1{k_j^2} \sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_{n\geq1}\V(Y_n) \sum_{j\,:\,k_j\geq n}\frac1{k_j^2} .$
Mostrar $\sum_{j : k_j \geq n}k_j^{-2} \leq \frac{C_\alpha}{n^2}$ (geometric series; beware the floor: $k_j \geq \frac{\alpha^j}2$ for $\alpha^j \geq 2$ -type care) y concluir con pregunta 4 y Borel–Cantelli:

$\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \xrightarrow[j\to\infty]{\text{a.s.}} 0, \qquad\text{hence}\qquad \frac{S^*_{k_j}}{k_j} \to m \ \text{a.s.}$

Parte IV — Sandwich and conclusion.

Para $k_j \leq n \leq k_{j+1}$ , use la monotonicidad de $S^*_n$ (¡resúmenes no negativos!) para mostrar

$\frac{k_j}{k_{j+1}}\,\frac{S^*_{k_j}}{k_j} \;\leq\; \frac{S^*_n}{n} \;\leq\; \frac{k_{j+1}}{k_j}\,\frac{S^*_{k_{j+1}}}{k_{j+1}},$

y deducir, como:

$\frac m\alpha \leq \liminf\frac{S^*_n}n \leq \limsup\frac{S^*_n}n \leq \alpha\,m .$
Deje que $\alpha \downarrow 1$ siga una secuencia y concluir $\frac{S_n^*}n \to m$ a.s., por lo tanto (Parte I) el strong ley of large numbers:

$\boxed{\ \frac{S_n}{n} \xrightarrow[n\to\infty]{\text{a.s.}} \E[X_1].\ }$
¿Dónde estaba exactamente independencia por pares (en lugar de completo independencia) ¿suficiente? Enumera los tres lugares donde se invocaron hipótesis de tipo independentista.

Part V — Dividends.

(Números normales de Borel) Demuestre que $\lambda$ : casi todos los $x \in \intcc01$ son normal en cada base $b \geq 2$ : cada dígito $0, \dots, b-1$ aparece con frecuencia asintótica $\frac1b$ (fix $b$ and a digit, apply the strong ley to the indicator variables — justify that base- $b$ digits of a uniform variable are i.i.d. uniform on $\{0,\dots,b-1\}$ as in Teorema 22.6 — then intersect the countably many probability-one events). Exhibe un número explícito no normal, y reflexione: el teorema afirma la normalidad de casi todos los números, pero demostrando la normalidad de $\sqrt2$ o $\pi$ permanece abierto.
(Montecarlo, garantizado) Justificar completamente el método de Ejemplo 22.14(b) para $g \in L^1(\intcc01^d)$ : construir el i.i.d. muestra uniforme en $\intcc01^d$ de Teorema 22.6 y Ejercicio 22.10, e indique cuál es el fuerte ley cumple.

Part VI — What full independencia buys: maximal inequalities and random series. Etemadi gasta sólo por pares independencia; las partes restantes explotan el versión completa (mutua). Sea $(Z_n)$ independiente centrado variables de $L^2$ y $S_k = Z_1 + \dots + Z_k$ (una nueva notación, no relacionada con el $X_n$ anterior).

(desigualdad máxima de Kolmogorov) Para $\varepsilon > 0$ demuestre

$\P\Bigl(\max_{1\leq k\leq n}\abs{S_k} \geq \varepsilon\Bigr) \;\leq\; \frac1{\varepsilon^2}\sum_{k=1}^n\V(Z_k) :$

El precio de Chebyshev compra el máximo (partition the event according to the first index $k$ with $\abs{S_k} \geq \varepsilon$ ; on that piece write $S_n^2 \geq S_k^2 + 2S_k(S_n - S_k)$ and use the independencia of the coalitions $(Z_1, \dots, Z_k)$ and $(Z_{k+1}, \dots, Z_n)$ , Teorema 22.5). señalar el paso donde independencia en pares no lo haría ya es suficiente.
(Teorema de una serie de Khhinchin-Kolmogorov) Deducir: si $\sum_n\V(Z_n) < \infty$ , entonces $\sum_nZ_n$ converge casi con seguridad (show that a.s. the partial sums form a Cauchy sequence: let $m \to \infty$ in the maximal inequality applied to $Z_{N+1}, \dots, Z_{N+m}$ , then let $N \to \infty$ ).
(serie Rademacher) Sea $(\varepsilon_n)$ signos i.i.d. $\P(\varepsilon_n = \pm1) = \frac12$ (Teorema 22.6), y sean $(x_n)$ números reales. mostrar eso $\sum_nx_n\varepsilon_n$ converge a.s. tan pronto como $\sum_nx_n^2 < \infty$ ; mostrar también que, sea lo que sea $(x_n)$ , la probabilidad de que $\sum_nx_n\varepsilon_n$ converge es $0$ o $1$ (Teorema 22.9).
Lo contrario, elementalmente. Configure $T_n = \sum_{k\leq n}x_k\varepsilon_k$ y $s_n^2 = \sum_{k\leq n}x_k^2$ y supongamos $s_n \to \infty$ . (a) Demostrar el Paley–desigualdad de Zygmund: para $Z \geq 0$ con $\E Z^2 < \infty$ y $0 < \theta < 1$ ,

$\P\bigl(Z > \theta\,\E Z\bigr) \;\geq\; (1 - \theta)^2\,\frac{(\E Z)^2}{\E Z^2}$

(split $\E Z$ at the level $\theta\E Z$ and apply Cauchy–Schwarz to the upper piece). (b) Mostrar $\E T_n^4 \leq 3s_n^4$ . (c) Deduzca $\P\bigl(\abs{T_n} > \frac{s_n}2\bigr) \geq \frac3{16}$ y concluya que $\sum_nx_n\varepsilon_n$ diverge a.s.; de ahí el dicotomía

$\sum_nx_n\varepsilon_n\ \text{converges a.s.} \iff \sum_nx_n^2 < \infty .$
(Serie armónica aleatoria) Concluimos que $\sum_n\frac{\varepsilon_n}{n^s}$ converge como si y sólo si $s > \frac12$ . Para $\frac12 < s \leq 1$ la serie converge a.s. mientras $\sum_nn^{-s} = \infty$ : se producen signos aleatorios cancelación de fuerza de raíz cuadrada — comparar con la serie alterna $\sum_n\frac{(-1)^n}{n^s}$ , que converge para cada $s > 0$ .

Part VII — Concentration: Hoeffding’s inequality. El fuerte ley dice $\frac{S_n}n \to m$ ; Las desigualdades de concentración dicen qué tan improbable es una desviación. en cada $n$ fijo.

(lema de Hoeffding) (a) Mostrar $\cosh\lambda \leq \eu^{\lambda^2/2}$ para todos $\lambda \in \R$ , comparando las dos series término a término. (b) Sea $Z$ centrado con $a \leq Z \leq b$ , $a < b$ . Mostrar

$\E\,\eu^{\lambda Z} \leq \exp\Bigl(\frac{\lambda^2(b - a)^2}8\Bigr)$

(bound $\eu^{\lambda z}$ on $\intcc ab$ by its chord, take esperanzas de heredar, and study $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ with $p = \frac{-a}{b-a}$ and $t = \lambda(b - a)$ : show $\varphi(0) = \varphi'(0) = 0$ and $\varphi'' \leq \frac14$ ).
(desigualdad de Hoeffding) Sea $X_1, \dots, X_n$ independiente con $a_i \leq X_i \leq b_i$ y $S_n = X_1 + \dots + X_n$ . Demuestre, para $t > 0$ ,

$\P\bigl(S_n - \E S_n \geq t\bigr) \leq \exp\Bigl(\frac{-2t^2}{\sum_{i=1}^n(b_i - a_i)^2}\Bigr),$

y lo mismo para la cola inferior (exponential Chebyshev: bound $\E\,\eu^{\lambda(S_n - \E S_n)}$ using independencia and question 17, then optimize over $\lambda > 0$ ).
(El ley fuerte, caso acotado, con una tasa) Dejemos que $X_i$ sea i.i.d. con valores en $\intcc ab$ y $m = \E X_1$ . Mostrar

$\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr) \leq 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b - a)^2}\Bigr)$

y recuperar $\frac{S_n}n \to m$ a.s. por Borel–Cantelli: una segunda prueba de la fuerza ley para variables acotadas — sin truncamiento, un tasa exponencial en cada $n$ finito, pero acotado demandas y independencia completo. comparar el hipótesis con la de Etemadi.
(Montecarlo, garantizado en $n$ fijo) Sea $g \colon \intcc01^d \to \intcc01$ mensurable y $(U_k)$ la muestra uniforme i.i.d. de la pregunta 11. Dado $\varepsilon, \delta > 0$ , mostrar

$n \geq \frac{\log(2/\delta)}{2\varepsilon^2} \implies \P\Bigl(\Bigl|\frac1n\sum_{k=1}^ng(U_k) - \int g\,\dd\lambda_d\Bigr| \geq \varepsilon\Bigr) \leq \delta,$

y evaluar el umbral para $\varepsilon = \delta = 10^{-2}$ . El límite no involucra a $d$ : comparar con la pregunta 11 y con determinista rejillas.

Part VIII — How big is a random walk? Toward the iterated logarithm. Sea $S_n = \varepsilon_1 + \dots + \varepsilon_n$ el paseo aleatorio simple construido a partir de i.i.d. signos justos.

(colas subgaussianas) Mostrar $\E\,\eu^{\lambda S_n} = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ y deducir, para $x > 0$ ,

$\P(S_n \geq x) \leq \eu^{-x^2/(2n)}, \qquad \P(\abs{S_n} \geq x) \leq 2\,\eu^{-x^2/(2n)} .$
Deducir, vía Borel–Cantelli,

$\limsup_{n\to\infty}\frac{\abs{S_n}} {\sqrt{2n\log n}} \leq 1 \quad\text{a.s.}$

(for $\eta > 0$ , sum the tail bounds at $x = (1 + \eta)\sqrt{2n\log n}$ , then intersect over $\eta = \frac1p$ ). En particular, el paseo sigue vivo. la escala CLT $\sqrt n$ hasta un factor logarítmico — muy por debajo del límite del crudo $\abs{S_n} \leq n$ .
A lo largo de la subsecuencia de duplicación $n_j = 2^j$ , muestre

$\limsup_{j\to\infty}\frac{S_{n_j}} {\sqrt{2n_j\log\log n_j}} \leq 1 \quad\text{a.s.},$

y reflejar: el ley of the iterated logarithm (Khinchin; Hartman–Wintner para general centrados $L^2$ ) establece que

$\limsup_{n\to\infty}\frac{S_n} {\sqrt{2n\log\log n}} = 1 \quad\text{a.s.}$

Explique con precisión qué separa la subsecuencia estimación recién demostrada de la mitad superior de este declaración (se debe controlar $\max_{n_j \leq n \leq n_{j+1}}S_n$ dentro de cada bloque, lo que requiere una desigualdad máxima en la escala exponencial) y comprobar cuantitativamente que la pregunta 12 la desigualdad es demasiado débil para ese propósito. el inferior la mitad se basa en el segundo lema de Borel-Cantelli aplicado a bloques independiente; ambas mitades son Material honesto del tercer año para una probabilidad dedicada. curso.
(Desviación uniforme sobre una clase finita) Sean $A_1, \dots, A_N$ eventos en un experimento repetible, y estimar cada probabilidad por su valor empírico frecuencia $\hat p_i$ sobre $n$ i.i.d. repeticiones. Combinando la desigualdad de Hoeffding con un límite sindical, mostrar

$\P\Bigl(\max_{i\leq N}\,\abs{\hat p_i - \P(A_i)} > \varepsilon\Bigr) \;\leq\; 2N\,\eu^{-2n\varepsilon^2},$

y deducir la regla del tamaño de la muestra: $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ garantiza todas las estimaciones $N$ simultáneamente $\varepsilon$ : exacto con probabilidad $\geq 1 - \delta$ . Calcule $n$ para $N = 10^6$ , $\varepsilon = 0.01$ , $\delta = 0.05$ : el precio logarítmico de uniformidad.
(La ventana armónica aleatoria) Combinando los dos mitades de la teoría de series aleatorias, muestran que para i.i.d. firma $(\varepsilon_n)$ la serie $\sum_n\frac{\varepsilon_n}{n^\alpha}$ converge a.s. si $\alpha > \frac12$ y diverge a.s. si $\alpha \leq \frac12$ ; contraste con absoluto convergencia (que requiere $\alpha > 1$ ): en el ventana $\alpha \in \intoc{\frac12}1$ , convergencia es un fenómeno genuinamente probabilístico — cancelación, no tamaño.

Solución

Solución de Problema 22.1.

1. $X_n^{\pm}$ son funciones Borel de $X_n$ : permanecer en pares independiente (Ejercicio 22.3(a)) e idénticamente distribuido, integrable, con $\E X_1 = \E X_1^+ - \E X_1^-$ . Si el teorema se cumple para variables no negativas, aplícalo a ambas mitades y resta: $\frac{S_n}n = \frac{S_n^+}n - \frac{S_n^-}n \to \E X_1^+ - \E X_1^- = m$ a.s.

2. $\P(X_n \neq Y_n) = \P(X_n > n) = \P(X_1 > n)$ (idéntico leyes) y $\sum_n\P(X_1 > n) \leq \sum_n\P(X_1 \geq n) \leq \E X_1 < \infty$ (Ejercicio 11.3(a)). Borel–Cantelli (1): a.s. $X_n = Y_n$ para todos los $n$ grandes, por lo que $S_n - S_n^*$ es eventualmente constante en $n$ : $\frac{S_n - S_n^*}n \to 0$ a.s., y las dos sumas normalizadas comparten su asintótica comportamiento.

3. $X_1\mathbf 1_{X_1 \leq n} \nearrow X_1$ : MCT da $\E Y_n \to m$ ; Cesàro significa un convergente La secuencia converge al mismo límite: $\frac{\E S_n^*}n = \frac1n\sum_{k\leq n}\E Y_k \to m$ . Por lo tanto basta con probar $\frac{S^*_n - \E S^*_n}{n} \to 0$ a.s.

4. $\V(Y_n) \leq \E Y_n^2 = \E[X_1^2\mathbf 1_{X_1\leq n}]$ . Por Tonelli para serie,

\sum_n\frac{\E[X_1^2\mathbf 1_{X_1\leq n}]}{n^2} = \E\Bigl[X_1^2\!\!\sum_{n \geq \max(X_1, 1)}\!\frac1{n^2} \Bigr] \leq \E\Bigl[X_1^2\cdot\frac{4}{\max(X_1,1)}\Bigr] \leq 4\,\E[X_1] < \infty,

usando $\sum_{n\geq x}n^{-2} \leq \frac4x$ para $x \geq 1$ (para $x \geq 2$ : $\leq \frac1{x-1} \leq \frac2x$ ; para $1 \leq x < 2$ : $\leq \frac{\pi^2}6 \leq \frac4x$ desde $\frac4x > 2$ ) y $X_1^2/\max(X_1, 1) \leq X_1$ en ambos casos $X_1 \gtrless 1$ .

5. Por pares independencia da $\E[(Y_i - \E Y_i)(Y_j - \E Y_j)] = 0$ por $i \neq j$ (el producto fórmula para dos variables), por lo que las variaciones suman: $\V(S^*_k) = \sum_{n\leq k}\V(Y_n)$ . Chebyshev en cada $k_j$ y sumando:

\sum_j\P\Bigl(\abs{S^*_{k_j} - \E S^*_{k_j}} \geq \varepsilon k_j\Bigr) \leq \frac1{\varepsilon^2}\sum_j\frac1{k_j^2}\sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_n\V(Y_n)\!\!\sum_{j : k_j\geq n}\!\frac1{k_j^2}

(Tonelli para la serie doble no negativa).

6. $k_j = \lfloor\alpha^j\rfloor \geq \frac{\alpha^j}2$ (válido una vez $\alpha^j \geq 1$ , es decir todos $j \geq 0$ : $\lfloor x\rfloor \geq \frac x2$ para $x \geq 1$ ). Por lo tanto

\sum_{j : k_j \geq n}\frac1{k_j^2} \leq 4\sum_{j : \alpha^j \geq n}\alpha^{-2j} \leq \frac{4}{1 - \alpha^{-2}}\cdot\frac1{n^2} = \frac{C_\alpha}{n^2},

(serie geométrica del primer $j$ con $\alpha^j \geq n$ ). Combinando con las preguntas 4 a 5, la suma doble es finito; Borel–Cantelli (1), aplicado para cada racional $\varepsilon$ y se cruza, da $\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \to 0$ a.s., y con pregunta 3: $\frac{S^*_{k_j}}{k_j} \to m$ a.s.

7. $Y_n \geq 0$ hace $n \mapsto S^*_n$ no decreciente: para $k_j \leq n \leq k_{j+1}$ ,

\frac{S^*_{k_j}}{k_{j+1}} \leq \frac{S^*_n}{n} \leq \frac{S^*_{k_{j+1}}}{k_j},

cuál es el sándwich que se muestra después de insertar $\frac{k_j}{k_{j+1}}$ y $\frac{k_{j+1}}{k_j}$ . desde $\frac{k_{j+1}}{k_j} \to \alpha$ , la pregunta 6 da a.s.

\frac m\alpha \leq \liminf_n\frac{S^*_n}n \leq \limsup_n\frac{S^*_n}n \leq \alpha m .

8. Aplique la pregunta 7 para $\alpha = 1 + \frac1p$ , $p \in \N^*$ : contablemente muchos eventos a.s. en su intersección, dejando $p \to \infty$ : $\lim\frac{S^*_n}n = m$ a.s. Con preguntas 1–3, $\frac{S_n}n \to \E X_1$ a.s.: el fuerte ley de grandes números, bajo pares independencia.

9. Aparecieron tres hipótesis de tipo independencia veces: (i) aditividad de varianzas (pregunta 5) — por pares es suficiente; (ii) distribución idéntica, en el sumas de truncamiento (pregunta 2) y el cálculo de la media (pregunta 3) — no independencia en absoluto; (iii) Borel–Cantelli (1) (preguntas 2 y 6) — válido sin cualquier independencia. independencia mutuo completo nunca fue invocado: observación de Etemadi.

10. Fija una base $b$ y un dígito $r$ . La base- $b$ Los dígitos $(d_k)$ de un uniforme $\omega$ son i.i.d. uniforme en $\{0, \dots, b-1\}$ (cada valor de vector de dígito ocupa un intervalo de longitud $b^{-m}$ : el argumento de Teorema 22.6 textualmente). el fuerte ley aplicado a las variables acotadas i.i.d. $\mathbf 1_{d_k = r}$ da: a.s., la frecuencia del dígito $r$ tiende a $\frac1b$ . Intersección sobre los contablemente muchos pares $(b, r)$ : casi todos los números son simplemente normal en cada base. Una anormalidad explícita número: $x = 0.100100100\ldots_2$ (frecuencia de unos $\frac13 \neq \frac12$ ). El contraste es humillante: casi todos los números son normales, pero para $\sqrt2$ , $\eu$ o $\pi$ la normalidad sigue sin demostrarse — medida la teoría cuenta sin exponer.

11. Por Ejercicio 22.10 iterado, un una sola variable uniforme produce una secuencia de i.i.d. uniforme vectores $U_k$ en $\intcc01^d$ (dividir el conjunto de dígitos de cada $U_n$ de Teorema 22.6 en subfamilias $d$ ). Para $g \in L^1(\intcc01^d)$ , las variables $g(U_k)$ son i.i.d. integrable con media $\int g\,\dd\lambda_d$ (transferencia): el fuerte ley da

\frac1n\sum_{k=1}^ng(U_k) \xrightarrow[n\to\infty]{\text{a.s.}} \int_{\intcc01^d}g\,\dd\lambda_d :

La integración Montecarlo converge casi con seguridad, en cada dimensión — el tamaño del error es asunto de la central teorema del límite (Capítulo 23).

12. Vamos $A_k = \{\abs{S_k} \geq \varepsilon\} \cap \bigcap_{j<k}\{\abs{S_j} < \varepsilon\}$ : los $A_k$ son disjunto con la unión $A = \{\max_{k\leq n}\abs{S_k} \geq \varepsilon\}$ . entonces

\E S_n^2 \geq \sum_{k=1}^n\E\bigl[S_n^2\mathbf 1_{A_k}\bigr] = \sum_{k=1}^n\E\Bigl[\bigl(S_k^2 + 2S_k(S_n - S_k) + (S_n - S_k)^2\bigr)\mathbf 1_{A_k}\Bigr] \geq \sum_{k=1}^n\E\bigl[S_k^2\mathbf 1_{A_k}\bigr],

porque el término cruzado desaparece: $S_k\mathbf 1_{A_k}$ es un Función Borel de la coalición $(Z_1, \dots, Z_k)$ , que es independiente de $S_n - S_k$ , una función de $(Z_{k+1}, \dots, Z_n)$ (Teorema 22.5), por lo que $\E[S_k\mathbf 1_{A_k}(S_n - S_k)] = \E[S_k\mathbf 1_{A_k}]\,\E[S_n - S_k] = 0$ . En $A_k$ , $S_k^2 \geq \varepsilon^2$ , de donde $\E S_n^2 \geq \varepsilon^2\sum_k\P(A_k) = \varepsilon^2\P(A)$ ; y $\E S_n^2 = \sum_{k\leq n}\V(Z_k)$ (se agregan variaciones). el El paso decisivo es la factorización: $S_k\mathbf 1_{A_k}$ es una función no lineal de todo el primer bloque, y su independencia del segundo bloque es coalición independencia — independencia por pares del $Z_i$ únicamente descorrelaciona pares y no lo justificaría.

13. Corrija $N$ y aplique la pregunta 12 a $Z_{N+1}, \dots, Z_{N+m}$ :

\P\Bigl(\max_{N < k \leq N+m}\abs{S_k - S_N} > \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j=N+1}^{N+m}\V(Z_j) \leq \frac{r_N}{\varepsilon^2}, \qquad r_N = \sum_{j>N}\V(Z_j) .

Los eventos aumentan con $m$ ; continuidad desde abajo da $\P(\sup_{k>N}\abs{S_k - S_N} > \varepsilon) \leq r_N/\varepsilon^2$ y $r_N \to 0$ por hipótesis. Por lo tanto para cada $p \in \N^*$ , $\P\bigl(\bigcap_N\{\sup_{k>N} \abs{S_k - S_N} > \frac1p\}\bigr) \leq \inf_Np^2r_N = 0$ : casi seguramente, por cada $p$ hay $N$ con $\sup_{k>N}\abs{S_k - S_N} \leq \frac1p$ (cruza el contablemente muchos eventos a.s. sobre $p$ ), de modo que $\abs{S_k - S_l} \leq \frac2p$ para todos los $k, l > N$ : las sumas parciales son a.s. Cauchy, por lo tanto a.s. convergentes.

14. Las variables $Z_n = x_n\varepsilon_n$ son independiente (Funciones Borel de variables independiente, Ejercicio 22.3(a)), centrado, con $\V(Z_n) = x_n^2$ : la pregunta 13 aplica cuando $\sum_nx_n^2 < \infty$ y da a.s. convergencia. En general, para cada $N$ el La convergencia de $\sum_nx_n\varepsilon_n$ no se ve afectada por los valores de $\varepsilon_1, \dots, \varepsilon_N$ : el evento de convergencia se encuentra en el álgebra $\sigma$ de cola del independiente secuencia $(\varepsilon_n)$ , por lo que Kolmogorov Fuerzas ley cero uno (Teorema 22.9) su probabilidad es $0$ o $1$ .

15. (a) División en el nivel $\theta\E Z$ y usando Cauchy–Schwarz en la pieza superior,

\E Z = \E\bigl[Z\mathbf 1_{Z \leq \theta\E Z}\bigr] + \E\bigl[Z\mathbf 1_{Z > \theta\E Z}\bigr] \leq \theta\,\E Z + \sqrt{\E Z^2}\, \sqrt{\P(Z > \theta\E Z)} ,

entonces $(1 - \theta)\E Z \leq \sqrt{\E Z^2\,\P(Z > \theta\E Z)}$ ; cuadrado. (b) Ampliar $T_n^4 = \sum_{i,j,k,l}x_ix_jx_kx_l\, \E[\varepsilon_i\varepsilon_j\varepsilon_k\varepsilon_l]$ : el expectativa es $1$ cuando los índices se emparejan (los cuatro iguales, o dos pares distintos, este último en $3$ arreglos) y $0$ en caso contrario (un signo no apareado tiene cero media y factorizado por independencia). Por lo tanto

\E T_n^4 = \sum_kx_k^4 + 3\sum_{i\neq j}x_i^2x_j^2 = 3s_n^4 - 2\sum_kx_k^4 \leq 3s_n^4 .

\P\Bigl(\abs{T_n} > \frac{s_n}2\Bigr) = \P\Bigl(T_n^2 > \frac{s_n^2}4\Bigr) \geq \Bigl(\frac34\Bigr)^2 \frac{s_n^4}{3s_n^4} = \frac3{16} .

Si la serie convergiera con probabilidad positiva, convergería a.s. (pregunta 14), por lo $\sup_n\abs{T_n} < \infty$ a.s., y algo de $M$ satisfaría $\P(\sup_n\abs{T_n} > M) < \frac3{16}$ ; pero en cuanto $s_n > 2M$ , $\P(\abs{T_n} > M) \geq \P(\abs{T_n} > \frac{s_n}2) \geq \frac3{16}$ : contradicción. Entonces la divergencia es casi claro, y con la pregunta 14 la dicotomía es completo.

16. Aquí $x_n = n^{-s}$ y $\sum_nn^{-2s} < \infty$ exactamente cuando $s > \frac12$ : mediante las preguntas 14–15, $\sum_n\frac{\varepsilon_n}{n^s}$ converge a.s. si y sólo si $s > \frac12$ (para $s \leq \frac12$ , a.s. divergencia). Para $\frac12 < s \leq 1$ la convergencia es nunca absoluto. La comparación es instructiva: perfectamente Los signos alternos se cancelan con la fuerza $n^{-s}$ por cada $s > 0$ , mientras que los signos aleatorios típicos se cancelan solo con la fuerza $n^{-s}$ . fuerza de la raíz cuadrada — el paseo aleatorio de la pregunta 21 crece como $\sqrt n$ , y la suma de Abel convierte exactamente ese crecimiento hacia la convergencia de $\sum\varepsilon_nn^{-s}$ para $s > \frac12$ .

17. (a) $\cosh\lambda = \sum_k\frac{\lambda^{2k}}{(2k)!}$ y $\eu^{\lambda^2/2} = \sum_k\frac{\lambda^{2k}}{2^kk!}$ ; y $(2k)! \geq 2^kk!$ se mantiene a lo largo de los términos, porque $\frac{(2k)!}{k!} = \prod_{i=1}^k(k + i) \geq \prod_{i=1}^k(2i) = 2^kk!$ (cada factor satisface $k + i \geq 2i$ para $i \leq k$ ), de modo que de hecho $(2k)! \geq 2^k(k!)^2 \geq 2^kk!$ . (b) Nota $a \leq 0 \leq b$ ( $Z$ es centrado), y por la convexidad de $z \mapsto \eu^{\lambda z}$ , para $z \in \intcc ab$ :

\eu^{\lambda z} \leq \frac{b - z}{b - a}\,\eu^{\lambda a} + \frac{z - a}{b - a}\,\eu^{\lambda b}, \qquad\text{so}\qquad \E\,\eu^{\lambda Z} \leq \frac{b\,\eu^{\lambda a} - a\,\eu^{\lambda b}}{b - a} = (1 - p)\eu^{-pt} + p\,\eu^{(1-p)t} = \eu^{\varphi(t)}

con $p = \frac{-a}{b-a} \in \intcc01$ , $t = \lambda(b - a)$ , $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ . entonces $\varphi(0) = 0$ , $\varphi'(t) = -p + \frac{p\eu^t}{1 - p + p\eu^t}$ desaparece en $0$ y $\varphi''(t) = \rho(1 - \rho) \leq \frac14$ para $\rho = \frac{p\eu^t}{1 - p + p\eu^t} \in \intcc01$ : Taylor en la orden $2$ da $\varphi(t) \leq \frac{t^2}8 = \frac{\lambda^2(b-a)^2}8$ .

18. Para $\lambda > 0$ , Markov solicitó al variable positiva $\eu^{\lambda(S_n - \E S_n)}$ (Proposición 22.3) y el producto la fórmula para las variables independiente da

\P(S_n - \E S_n \geq t) \leq \eu^{-\lambda t}\prod_{i=1}^n\E\,\eu^{\lambda(X_i - \E X_i)} \leq \exp\Bigl(-\lambda t + \frac{\lambda^2}8\sum_i(b_i - a_i)^2\Bigr),

por la pregunta 17(b) aplicada a cada $X_i - \E X_i \in \intcc{a_i - \E X_i}{b_i - \E X_i}$ centrado (mismo ancho). Minimizar el exponente en $\lambda = \frac{4t}{D}$ , $D = \sum_i(b_i - a_i)^2$ produce $-\frac{2t^2}D$ . el inferior tail sigue aplicando el resultado a $(-X_i)$ .

19. Tome $t = n\varepsilon$ y $D = n(b - a)^2$ :

\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr) \leq 2\exp\Bigl(\frac{-2n^2\varepsilon^2}{n(b-a)^2}\Bigr) = 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b-a)^2}\Bigr),

que es sumable en $n$ (una serie de tipo geométrico): Borel–Cantelli (Teorema 22.8) da ese culo $\abs{\frac{S_n}n - m} < \varepsilon$ eventualmente; intersección sobre $\varepsilon = \frac1p$ produce $\frac{S_n}n \to m$ a.s. Comparación: Etemadi pregunta solo $X_1 \in L^1$ y independencia por pares, y entrega sin tarifa; Hoeffding pide limitación y completa independencia, y ofrece una garantía exponencial explícita en cada finito $n$ — los dos teoremas responden preguntas diferentes aproximadamente el mismo límite.

20. Los $g(U_k)$ son i.i.d. con valores en $\intcc01$ y significa $\int g\,\dd\lambda_d$ (transferencia), entonces pregunta 18 con $b_i - a_i = 1$ , $t = n\varepsilon$ da el cota de dos caras $2\eu^{-2n\varepsilon^2} \leq \delta$ tan pronto como $\eu^{2n\varepsilon^2} \geq \frac2\delta$ , es decir $n \geq \frac{\log(2/\delta)}{2\varepsilon^2}$ . Para $\varepsilon = \delta = 10^{-2}$ :

n \geq \frac{\log 200}{2\cdot10^{-4}} = \frac{5.2983\ldots}{0.0002} \approx 26\,492 :

Aproximadamente las muestras $26\,500$ garantizan una precisión $1\%$ con $99\%$ confianza — en todas las dimensiones $d$ , para cada mensurable integrando con valores en $\intcc01$ . Pregunta El fuerte ley de 11 prometió convergencia sin finito- $n$ garantía; una cuadrícula determinista con puntos $k$ por eje cuesta evaluaciones $k^d$ , exponencial en $d$ . Concentración es lo que hace que Montecarlo sea un método en lugar de un esperanza.

21. Independencia y la fórmula del producto: $\E\,\eu^{\lambda S_n} = (\E\,\eu^{\lambda\varepsilon_1})^n = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ por pregunta 17(a). Markov en $\eu^{\lambda S_n}$ :

\P(S_n \geq x) \leq \eu^{-\lambda x + n\lambda^2/2} = \eu^{-x^2/(2n)} \qquad\text{at the optimum } \lambda = \frac xn,

y el límite simétrico para $-S_n$ (mismo ley) duplica el constante para $\abs{S_n}$ .

22. Repare $\eta > 0$ y configure $x_n = (1 + \eta)\sqrt{2n\log n}$ para $n \geq 2$ :

\P(\abs{S_n} \geq x_n) \leq 2\exp\bigl(-(1 + \eta)^2\log n\bigr) = \frac{2}{n^{(1+\eta)^2}},

sumable desde $(1 + \eta)^2 > 1$ . Borel–Cantelli: a.s. $\abs{S_n} < (1 + \eta)\sqrt{2n\log n}$ para todos los grandes $n$ , entonces $\limsup_n\frac{\abs{S_n}}{\sqrt{2n\log n}} \leq 1 + \eta$ a.s.; al cruzar los eventos a.s. para $\eta = \frac1p$ , $p \in \N^*$ , se obtiene el reclamo. El paseo del tamaño $n$ tiene la amplitud típica $\sqrt n$ (su varianza), y incluso sus peores excursiones superan esa escala como máximo $\sqrt{2\log n}$ .

23. Con $n_j = 2^j$ y $x = (1 + \eta)\sqrt{2n_j\log\log n_j}$ (definido para $j \geq 2$ ), la pregunta 21 da

\P\bigl(S_{n_j} \geq x\bigr) \leq \exp\bigl(-(1 + \eta)^2\log\log n_j\bigr) = (j\log 2)^{-(1+\eta)^2},

sumable en $j$ desde $(1 + \eta)^2 > 1$ : Borel–Cantelli y $\eta = \frac1p$ le dan a $\limsup_jS_{n_j}/\sqrt{2n_j \log\log n_j} \leq 1$ un.s. Lo que falta para el completo La mitad superior es el puente entre los puntos de control: hay que mostrar $\max_{n_j\leq n\leq n_{j+1}}S_n$ excede $(1+\eta)\sqrt{2n_j\log\log n_j}$ sólo un número limitado de veces, lo que exige una desigualdad máxima con gaussiano colas (reflejo de la desigualdad de Lévy o Ottaviani) desigualdad, no demostrada aquí). La pregunta 12 es cuantitativa demasiado débil: limita la probabilidad por

\frac{n_j}{(1+\eta)^2\,2n_j\log\log n_j} = \frac{1}{2(1+\eta)^2\log(j\log2)},

que tiende a $0$ pero es no sumable en $j$ : Borel-Cantelli no puede concluir. La mitad inferior del ley del logaritmo iterado se aplica el segundo Borel–Lema de Cantelli a los incrementos independiente $S_{n_{j+1}} - S_{n_j}$ , utilizando límites inferiores coincidentes para Colas de tipo gaussiano. Ambos refinamientos son genuinos del Año 3. probabilidad, un curso más adelante; que problema este entrega sin ayuda es la escala exacta de logaritmo iterado a lo largo de tiempos geométricos.

24. Cada $\hat p_i$ es un promedio de $n$ i.i.d. variables indicadoras con valores en $\intcc01$ y media $\P(A_i)$ : Hoeffding da $\P(\abs{\hat p_i - \P(A_i)} > \varepsilon) \leq 2\eu^{-2n\varepsilon^2}$ . El sindicato obligado se multiplica por $N$ . Resolviendo $2N\eu^{-2n\varepsilon^2} \leq \delta$ : $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ . Numéricamente: $\ln\frac{2\cdot10^6}{0.05} = \ln(4\cdot10^7) \approx 17.5$ , entonces $n \geq \frac{17.5}{2\cdot10^{-4}} \approx 87\,600$ : estimación uno probabilidad de $\pm1\%$ toma aproximadamente $18\,500$ muestras ( $\ln(2/\delta)/2\varepsilon^2$ ), y un millón probabilidades solamente $\approx 4.7$ veces más — la uniformidad cuesta $\ln N$ , no $N$ : la observación de que hace la minimización empírica del riesgo, y con ello la máquina aprendizaje, estadísticamente posible.

25. Las variables $X_n = \frac{\varepsilon_n} {n^\alpha}$ son independiente, centradas, acotadas, con $\sum_n\V(X_n) = \sum_nn^{-2\alpha}$ . Si $\alpha > \frac12$ : la serie de varianzas converge y la El teorema de una serie (Parte VI) da la convergencia a.s. de $\sum X_n$ . Si $\alpha \leq \frac12$ : la serie de varianza diverge, y la mitad inversa (Parte VI Argumento Paley-Zygmund, aplicable ya que las demandas son delimitado por $1$ ) da una divergencia. absoluto convergencia pregunta $\sum n^{-\alpha} < \infty$ : $\alpha > 1$ . En $\intoc{\frac12}1$ , la serie converge a.s. aunque $\sum\abs{X_n} = \infty$ seguramente: los signos conspiran para cancelar, con probabilidad uno — convergencia por cancelación, invisible a cualquier prueba absoluta, y (por el ley cero uno) con un veredicto determinista de todos modos.