Matemáticas universitarias — Grado 2 · Bachelor Year 2

22Variables aleatorias discretas

variables aleatorias organizar cálculos de probabilidad alrededor funciones en lugar de eventos. En los espacios contable la teoría es impulsado por las familias sumable de Capítulo 7: expectativa es la suma de una familia indexada por el espacio muestral, y todas sus propiedades — linealidad, transferencia, fórmula del producto para variables independiente — son teoremas sobre sumable familias. El capítulo demuestra las desigualdades clave de Markov, Chebyshev, Cauchy–Schwarz y Jensen, y termina con el clásico leyes y la ley débil de los grandes números, cuya demostración son dos líneas una vez que Chebyshev esté disponible.

22.1 Variables aleatorias y sus leyes.

Definición 22.1 (Variable aleatoria discreta; ley)

Sea $(\Omega, \P)$ un contable espacio de probabilidad. un variable aleatoria es un mapa $X \colon \Omega \to E$ ( $E$ cualquier conjunto; real variable aleatoria cuando $E = \R$ ). Es ley (o distribución) es el medida de probabilidad $\P_X$ en el conjunto contable $X(\Omega)$ definido por

\P_X(\{x\}) = \P(X = x) = \P\bigl(\{\omega : X(\omega) = x\}\bigr) .

Ejemplo 22.2 (Las leyes clásicas)

bernoulli $\mathcal{B}(p)$ : $X \in \{0, 1\}$ , $\P(X = 1) = p$ . Indicador de un evento.
Binomio $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ , $0 \leq k \leq n$ : número de éxitos en $n$ independiente ensayos de Bernoulli (volumen de escuela secundaria; reprobado a continuación mediante sumas de variables independiente).
Geométrico $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : rango del primer éxito (Ejemplo 21.5).
Poison $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — a probabilidad medida por la serie exponencial. La ley de los eventos raros. (Capítulo 23).

Observación 22.3 (Qué ley modelo qué)

Los cuatro leyes responden a cuatro preguntas primitivas: Bernoulli, “¿sucedió?”; binomial, “cuántas veces en $n$ ¿Intenta?”; geometric, “how long until the first time?”; Poisson, "¿cuántos eventos a un ritmo determinado, cuando se realizan intentos?" ¿Muchos e individualmente improbables?”. Reconociendo la pregunta es nueve décimos del modelo: las sumas de los indicadores apuntan a el binomial, tiempos de espera a lo geométrico, evento raro cuenta con el Poisson — con el paso del binomio al Poisson precisado por la ley de eventos raros en Capítulo 23.

Proposición 22.4 (La falta de memoria de lo geométrico. ley)

Si $X \sim \mathcal{G}(p)$ , entonces para todos $m, n \in \N$ :

\P(X > m + n \mid X > m) = \P(X > n) ,

y el leyes geométrico son los únicos leyes en $\N^*$ con esto propiedad.

Demostración. Sumando los pesos geométricos, $\P(X > n) = (1-p)^n$ . Por lo tanto

\P(X > m + n \mid X > m) = \frac{\P(X > m + n)}{\P(X > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \P(X > n).

Por el contrario, si $G(n) = \P(X > n)$ satisface $G(m + n) = G(m)G(n)$ con $G(0) = 1$ , entonces $G(n) = G(1)^n$ por inducción; $q = G(1) \in \intco{0}{1}$ y $q = 0$ o ley son $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Ejemplo 22.5 (Nunca se vence ningún número)

Tira un dado esperando un seis: el tiempo de espera es $X \sim \mathcal G(1/6)$ . La falta de memoria dice que después de $10$ rollos infructuosos, el restante espera $X - 10$ , dado $X > 10$ , es nuevamente $\mathcal G(1/6)$ : el condicional La espera esperada sigue siendo $6$ rollos, exactamente como al principio. El dado no recuerda, y nunca se "vende" ningún seis — el La falacia del jugador es la creencia de que el condicional ley debería haber cambiado. Por el contrario, la unicidad de la proposición la mitad dice esta indiferencia caracteriza geométrica tiempos de espera: cualquier tiempo de espera cuyo pronóstico nunca se actualiza es geométrico. Las colas y vidas reales generalmente se actualizan, que es precisamente como se detecta que no lo son geométrico.

22.2 Expectativa

Definición 22.6 (expectativa)

Un verdadero variable aleatoria $X$ en $(\Omega, \P)$ tiene un expectativa si la familia $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ es sumable (Capítulo 7); su expectativa es entonces

\E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) .

Teorema 22.7 (Teorema de transferencia)

$X$ tiene un expectativa si y sólo si la familia $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ es sumable, y luego

\E(X) = \sum_{x \in X(\Omega)} x\,\P(X = x) .

De manera más general, para $f \colon X(\Omega) \to \R$ , la variable $f(X)$ tiene un expectativa si $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ y luego $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Demostración. Particione $\Omega$ en los conjuntos de niveles $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . Según el teorema de suma por paquetes para sumable familias (Capítulo 7), la familia $(X(\omega)\P(\{\omega\}))_\omega$ es sumable si cada paquete es (automático: $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) y la familia de sumas de paquetes $\bigl(x\,\P(X = x)\bigr)_x$ es sumable — y luego el total las sumas coinciden. Para $f(X)$ : aplique la declaración probada a la variable $Y = f \circ X$ , cuyos conjuntos de niveles son $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ; una segunda suma por Los paquetes convierten $\sum_y y\,\P(Y = y)$ en $\sum_x f(x)\,\P(X = x)$ , los paquetes ahora agrupan los valores $x$ . por su imagen $f(x)$ , con sumabilidad absoluta de uno familia equivalente a la del otro. ∎

Teorema 22.8 (Propiedades de expectativa)

En el set de variables aleatorias con expectativa:

(Linealidad) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positividad y monotonicidad) $X \geq 0 \Rightarrow \E(X) \geq 0$ ; $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ; y $\abs{\E(X)} \leq \E(\abs X)$ .
(Dominación) Si $\abs X \leq Z$ y $Z$ tienen un expectativa, también lo hace $X$ .

Demostración. Todas son propiedades de sumas de familias sumable. (Capítulo 7): linealidad de la suma, término de positividad por término y el criterio de dominación para sumabilidad. (Tenga en cuenta que la linealidad es inmediata en definición sobre $\Omega$ , aunque sería incómodo con la fórmula de transferencia: un beneficio de definir $\E$ en sentido ascendente.) ∎

Ejemplo 22.9

$X \sim \mathcal{B}(n, p)$ : escribiendo $X = X_1 + \dots + X_n$ como suma de indicadores de Bernoulli y uso de linealidad, $\E(X) = np$ — no se necesitan coeficientes binomiales. $X \sim \mathcal{G}(p)$ : $\E(X) = \sum_{k\geq1}k(1-p)^{k-1}p = p\cdot\frac{1}{(1 - (1-p))^2} = \frac1p$ , diferenciando la serie geométrica dentro de su disco (Capítulo 11). $X \sim \mathcal{P}(\lambda)$ : $\E(X) = \sum_{k\geq1}k e^{-\lambda}\frac{\lambda^k}{k!} = \lambda e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda$ .

Ejemplo 22.10 (Transferencia en acción)

Para $X \sim \mathcal P(\lambda)$ , calcule $\E\bigl(\frac1{1+X}\bigr)$ — el ley de $\frac1{1+X}$ En sí mismo es incómodo, pero la transferencia nunca lo solicita:

\E\Bigl(\frac1{1+X}\Bigr) = \sum_{k\geq0}\frac{1}{k+1}\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \frac{\eu^{-\lambda}}{\lambda}\sum_{k\geq0} \frac{\lambda^{k+1}}{(k+1)!} = \frac{\eu^{-\lambda}}{\lambda}\bigl(\eu^\lambda - 1\bigr) = \frac{1 - \eu^{-\lambda}}{\lambda} .

Dos lecciones. Computacionalmente: reconocer un desplazamiento la serie exponencial es todo el trabajo — la transferencia reduce esperanzas de heredar de $f(X)$ a manipulación en serie. Estructuralmente: el valor ingenuo del complemento sería $\frac1{1 + \E X} = \frac1{1 + \lambda}$ , y la respuesta verdadera es mayor,

\frac{1 - \eu^{-\lambda}}{\lambda} \geq \frac{1}{1 + \lambda},

exactamente como exige la desigualdad de Jensen para la función convexa $t \mapsto \frac1{1+t}$ . Esperanzas de heredar de Las imágenes convexo se ubican por encima del valor ingenuo del complemento y se transfieren además, una verificación de serie concreta la desigualdad abstracta.

Teorema 22.11 (independencia y productos)

variables aleatorias $X, Y$ son independiente si $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ para todos $x, y$ — equivalentemente, el eventos $\{X \in A\}$ y $\{Y \in B\}$ son independiente para todos los $A, B$ . Si $X$ y $Y$ son variables reales independiente con esperanzas de heredar, entonces $XY$ tiene un expectativa y

\E(XY) = \E(X)\,\E(Y) .

Demostración. La equivalencia de las dos formulaciones se obtiene sumando las puntualmente identidad sobre $(x, y) \in A \times B$ ( $\sigma$ -aditividad dos veces). Para el producto: la doble familia $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ es sumable, ya que por Fubini para familias (Capítulo 7)

\sum_{x, y}\abs x \abs y\,\P(X{=}x)\P(Y{=}y) = \Bigl(\sum_x \abs x \P(X{=}x)\Bigr) \Bigl(\sum_y \abs y \P(Y{=}y)\Bigr) < \infty ;

por independencia esta familia es exactamente $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , cuya suma es $\E(XY)$ por transferencia aplicada al variable $(X, Y) \mapsto xy$ ; Fubini vuelve a evaluar a los no fichados suma como el producto $\E(X)\E(Y)$ . ∎

Ejemplo 22.12 (Productos, con y sin independencia)

Tira dos dados justos. Si $Y$ es el segundo dado (independiente de el primero), $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . si en cambio $Y = X$ (el "producto" de un dado consigo mismo),

\E(X^2) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17 \neq 12.25 :

mismo marginal leyes en ambos escenarios, distinto conjunto leyes, producto diferente esperanzas de heredar. La moraleja, digna de grabarse: $\E(XY)$ es un funcional del par, no de los dos marginales — y la brecha $\E(X^2) - \E(X)^2 \approx 2.92$ es, por König–Huygens, precisamente el diferencia $\frac{35}{12}$ del dado.

22.3 Varianza, covarianza y desigualdades clásicas.

Definición 22.13 (Momentos, variación)

$X$ tiene un momento de orden 2 si $X^2$ tiene un expectativa (luego también lo hace $X$ , por dominación: $\abs X \leq \frac{1 + X^2}{2}$ ). Sus diferencia y estándar desviación son entonces

V(X) = \E\bigl((X - \E(X))^2\bigr) = \E(X^2) - \E(X)^2 , \qquad \sigma(X) = \sqrt{V(X)} ,

(la segunda forma — la fórmula König–Huygens — por expandiendo el cuadrado y usando linealidad:

\E\bigl((X - \E X)^2\bigr) = \E\bigl(X^2 - 2X\,\E X + \E(X)^2\bigr) = \E(X^2) - 2\,\E(X)^2 + \E(X)^2 ,

el término medio usando que $\E X$ es una constante). Para $X, Y$ con segundos momentos, el covarianza es

\operatorname{Cov}(X, Y) = \E\bigl((X - \E X)(Y - \E Y)\bigr) = \E(XY) - \E(X)\E(Y) .

Teorema 22.14 (Kit de herramientas de variación.)

Para variables con segundos momentos:

$V(aX + b) = a^2\,V(X)$ ;
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ , y más generalmente

$V\Bigl(\sum_{i=1}^n X_i\Bigr) = \sum_{i=1}^n V(X_i) + 2\sum_{i < j}\operatorname{Cov}(X_i, X_j) ;$
si $X, Y$ son independiente, $\operatorname{Cov}(X, Y) = 0$ (lo contrario es falso), entonces variaciones de las variables independiente agregar.

Demostración. 1 y 2 son expansiones de cuadrados más linealidad; los productos $X_iX_j$ tienen esperanzas de heredar de Cauchy–Schwarz a continuación (o por $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 es Teorema 22.11 aplicado al centrado variables. Un contraejemplo estándar de lo contrario: $X$ uniforme en $\{-1, 0, 1\}$ y $Y = X^2$ no están correlacionados ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) pero claramente dependiente. ∎

Teorema 22.15 (Markov y Chebyshev desigualdades)

(Markov) Si $X \geq 0$ tiene un expectativa, entonces para cada $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Chebyshev) Si $X$ tiene un segundo momento, entonces por cada $\varepsilon > 0$ :

$\P\bigl(\abs{X - \E(X)} \geq \varepsilon\bigr) \leq \frac{V(X)}{\varepsilon^2} .$

Demostración. 1. Puntualmente, $a\,\mathbf{1}_{X \geq a} \leq X$ (en el evento el lado izquierdo es $a \leq X$ ; fuera de él, $0 \leq X$ ). tomar esperanzas de heredar: $a\,\P(X \geq a) \leq \E(X)$ por monotonicidad y $\E(\mathbf{1}_A) = \P(A)$ . 2. Aplique Markov a la variable no negativa $(X - \E X)^2$ en el nivel $a = \varepsilon^2$ : el evento $\{(X - \E X)^2 \geq \varepsilon^2\}$ es exactamente $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Ejemplo 22.16 (Sin correlacionar pero pegado juntos)

Tira dos dados justos, $X$ y $Y$ independiente, y establece $S = X + Y$ , $D = X - Y$ . Por bilinealidad del covarianza,

\operatorname{Cov}(S, D) = V(X) - V(Y) + \operatorname{Cov}(Y, X) - \operatorname{Cov}(X, Y) = V(X) - V(Y) = 0 :

la suma y la diferencia no están correlacionadas. Independiente? Ciertamente no: $S = 12$ obliga a $D = 0$ , mientras que $\P(D = 0) = \frac16$ incondicionalmente. La correlación sólo prueba la lineal parte de una dependencia; aquí la dependencia es llevado por la restricción de que $S$ y $D$ tienen el mismo paridad, invisible para covarianza. (Para este par, cero covarianza necesario $V(X) = V(Y)$ : idéntico distribuciones, no independencia, hizo el trabajo.)

Ejemplo 22.17 (Cuando Markov es exacto)

La desigualdad de Markov es una igualdad precisamente cuando no hay nada. desperdiciado en el cota $a\,\mathbf 1_{X\geq a} \leq X$ : el La variable debe tomar solo los valores $0$ y $a$ . Concretamente, si $\P(X = a) = \pi$ y $\P(X = 0) = 1 - \pi$ , entonces $\E(X) = a\pi$ y

\P(X \geq a) = \pi = \frac{\E(X)}{a} .

Una lectura realista: en una población donde la riqueza promedio es $100$ y la riqueza es $0$ o $10^6$ , la proporción de millonarios es exactamente $10^{-4}$ — Markov está atado, golpeado exactamente por desigualdad máxima. Siempre que $X$ se extienda En los valores intermedios, el límite es estricto, a menudo excesivamente; pero como muestra el caso extremo, no se puede encontrar una mejor desigualdad. extraído únicamente de la media.

Ejemplo 22.18 (Chebyshev es agudo — sin más hipótesis)

Arregla $\varepsilon > 0$ , $q \in \intoc01$ y deja que $X$ tome el control. valores $\pm\varepsilon$ con probabilidad $\frac q2$ cada uno y $0$ con probabilidad $1 - q$ . Luego $\E(X) = 0$ , $V(X) = q\varepsilon^2$ y

\P\bigl(\abs{X - \E X} \geq \varepsilon\bigr) = q = \frac{V(X)}{\varepsilon^2} :

igualdad en Chebyshev. Entonces la desigualdad no se puede mejorar. usando solo el diferencia — la caída $1/\varepsilon^2$ es el precio exacto de la información del segundo momento. Decaimiento más rápido requiere hipótesis más sólidas: acotación de la variable compra concentración exponencial, como Ejercicio 22.7 avances y fin de semana de este capítulo El problema se desarrolla sistemáticamente.

Teorema 22.19 (Cauchy–Schwarz y Jensen)

(Cauchy–Schwarz) Si $X, Y$ tiene segundos momentos, $XY$ tiene un expectativa y $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; en consecuencia $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(Jensen) Si $\varphi \colon I \to \R$ es convexo en un intervalo que contiene $X(\Omega)$ y $X$ , $\varphi(X)$ tienen esperanzas de heredar, entonces

$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$

Demostración. 1. Sumabilidad de $XY$ : $\abs{XY} \leq \frac{X^2 + Y^2}2$ . El mapa $(X, Y) \mapsto \E(XY)$ es un bilineal simétrico forma positivo en el espacio de variables con segundos momentos, por lo que el resumen Se aplica la desigualdad de Cauchy-Schwarz de Capítulo 12 (semi-definido positivo es suficiente para la desigualdad). Aplicándolo a las variables centradas se obtiene el límite covarianza.

2. Primero, $m = \E(X)$ se encuentra en $I$ : $I$ es un intervalo contiene todos los valores de $X$ y expectativa es monótono, por lo que $m$ está entre $\inf X(\Omega)$ y $\sup X(\Omega)$ . por el teorema de la línea de soporte para funciones convexas (Capítulo 8), hay $\alpha, \beta$ con $\varphi(t) \geq \alpha t + \beta$ para todos $t \in I$ y $\varphi(m) = \alpha m + \beta$ . Luego, puntualmente en $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; tomando esperanzas de heredar,

\E\bigl(\varphi(X)\bigr) \geq \alpha\,\E(X) + \beta = \varphi\bigl(\E(X)\bigr). \qedhere

∎

Ejemplo 22.20

Jensen con $\varphi(t) = t^2$ da $\E(X)^2 \leq \E(X^2)$ — positividad del diferencia; con $\varphi(t) = 1/t$ encendido $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — la media armónica está por debajo de la media aritmética, ahora en forma aleatoria forma.

Observación 22.21 (Errores comunes)

(i) $\E(XY) = \E(X)\E(Y)$ requiere independencia (o en mínimo cero covarianza): tomar $Y = X$ da $\E(X^2) \neq \E(X)^2$ siempre que $V(X) > 0$ . (ii) Del mismo modo, $V(X + X) = 4V(X)$ , no $2V(X)$ : variaciones agrega solo en independiente (o no correlacionados) sumandos. (iii) $\E(f(X))$ no es $f(\E(X))$ ; para convexo $f$ Jensen incluso te dice el dirección del error, como en Ejemplo 22.10. (iv) La existencia es real. Hipótesis: para la variable San Petersburgo $X = 2^K$ con $\P(K = k) = 2^{-k}$ ( $k \geq 1$ ),

\sum_{k\geq1}2^k\cdot2^{-k} = \sum_{k\geq1}1 = \infty :

$X$ es casi seguro que es finito, pero no tiene expectativa ni Existe un precio de entrada justo para el juego. Sumabilidad en el La definición de $\E$ no es pedantería contable — es donde se detectan colas pesadas. (v) Finalmente, la transferencia El teorema necesita absoluto sumabilidad antes de cualquier la reordenación de la suma de los valores es legítima (Capítulo 7).

Ejemplo 22.22 (Chebyshev y cien lanzamientos)

Para $X \sim \mathcal B(100, \frac12)$ : $\E X = 50$ , $V(X) = 25$ . Chebyshev con $\varepsilon = 6$ :

\P(45 \leq X \leq 55) = \P(\abs{X - 50} < 6) \geq 1 - \frac{25}{36} \approx 0.31 ,

mientras que la suma binomial exacta da $\approx 0.73$ . el garantizado $31\%$ está lejos de la verdad, pero requiere solo la media y diferencia — el mismo certificado se aplica palabra por palabra a cualquier variable con $\E = 50$ , $V = 25$ , por exótico que sea, y Ejemplo 22.18 muestra alguna de esas variables lo satura. La universalidad tiene un precio; cuando el distribución es genuinamente binomial, el exponencial Las herramientas del problema del fin de semana cierran la mayor parte de la brecha.

Ejemplo 22.23 (La compensación de una pieza con su entero)

Para independiente $X, Y$ distribuido idénticamente con diferencia $\sigma^2 > 0$ , ¿qué correlación tiene un sumando con la suma? $S = X + Y$ ? calcular

\operatorname{Cov}(X, S) = \operatorname{Cov}(X, X) + \operatorname{Cov}(X, Y) = \sigma^2 + 0 = \sigma^2, \qquad V(S) = 2\sigma^2,

entonces el coeficiente de correlación es

\rho(X, S) = \frac{\operatorname{Cov}(X, S)}{\sigma(X)\,\sigma(S)} = \frac{\sigma^2}{\sigma\cdot\sigma\sqrt2} = \frac{1}{\sqrt2} \approx 0.707 ,

cualquiera que sea el ley común — dados, monedas, recuentos de Poisson. con $n$ suma el mismo cálculo que da $\rho(X_1, S_n) = 1/\sqrt n$ : la influencia de cada término individual en el total se diluye como una raíz cuadrada, que es la sombra correlacional de la escala de fluctuaciones $\sqrt n$ . Cauchy–Negro garantiza $\abs\rho \leq 1$ siempre; aquí se cumple el límite exactamente en el caso degenerado $n = 1$ y decae de forma predecible después.

Ejemplo 22.24 (AM ponderado–GM de Jensen)

Dejemos que $Y$ tome los valores positivos $a_1, \dots, a_k$ con probabilidades $\lambda_1, \dots, \lambda_k$ . la funcion $-\ln$ es convexo en $\intoo0\infty$ , por lo que Jensen da $-\ln\E(Y) \leq \E(-\ln Y)$ , es decir

a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_k^{\lambda_k} \;\leq\; \lambda_1a_1 + \lambda_2a_2 + \dots + \lambda_ka_k :

la aritmética ponderada: desigualdad geométrica, con igualdad si $Y$ es constante. Pesos iguales $\lambda_i = \frac1k$ recuperar el clásico AM–GM. La probabilidad ha demostrado silenciosamente un teorema puramente algebraico: elegir una probabilidad ley es sólo un dispositivo de contabilidad para combinaciones convexo — el punto de vista baricéntrico de Capítulo 17 una vez más, ahora con Jensen como motor.

22.4 La ley débil de los grandes números.

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

Sea $(X_k)_{k \geq 1}$ por pares independiente variables aleatorias con el mismo ley, admitiéndose un segundo momento; escribe $m = \E(X_1)$ y $S_n = X_1 + \dots + X_n$ . Luego para cada $\varepsilon > 0$ :

\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 .

Demostración. Por linealidad $\E(S_n/n) = m$ ; por Teorema 22.14 (por pares independencia mata el covarianzas) $V(S_n) = n\,V(X_1)$ , entonces $V(S_n/n) = V(X_1)/n$ . La desigualdad de Chebyshev aplicada a $S_n/n$ da la atado. ∎

Observación 22.26

Este es el teorema que conecta la probabilidad con la frecuencia: por $X_k$ el indicador de un evento $A$ en independiente repeticiones, $S_n/n$ es la frecuencia observada de $A$ y la ley de los grandes Los números dicen que se concentra alrededor de $\P(A)$ a un ritmo $\frac{p(1-p)}{n\varepsilon^2}$ . La ley fuerte ( $S_n/n \to m$ casi con seguridad) es un teorema del año 3 — su prueba para el cuarto Sin embargo, los momentos están a nuestro alcance: consulte Ejercicio 22.9, que corre Borel-Cantelli en el sentido Chebyshev. lo mismo La estimación de Chebyshev impulsó la prueba del polinomio de Bernstein de la Teorema de aproximación de Weierstrass en Capítulo 10 — el contando el lema allí era la ley débil de los grandes números en disfrazarse.

Ejemplo 22.27 (Recogiendo cincuenta cupones)

El recolector de cupones de Ejercicio 22.3 con juguetes distintos $n = 50$ : el total esperado es

\E(T_{50}) = 50\,H_{50} = 50\sum_{k=1}^{50}\frac1k \approx 50 \times 4.499 \approx 225

casillas — cuatro veces y media la ingenua suposición $50$ . el El crecimiento armónico lo es todo: los primeros juguetes $25$ llegan en aproximadamente $50\ln2 \approx 35$ cajas, mientras que el El juguete último por sí solo cuesta $50$ cajas en promedio (un espera geométrica del parámetro $\frac1{50}$ ). Finalización Los problemas están dominados por su final, razón por la cual Ejercicio 22.12 encuentra fluctuaciones de orden $n$ — el tamaño de esa espera geométrica final — alrededor del significa $n\ln n$ .

Ejemplo 22.28 (¿Qué tamaño debe tener $n$ ?)

Para fijar la frecuencia observada dentro de $\varepsilon = 0.01$ de $\P(A)$ con confianza $95\%$ , las exigencias obligadas de Chebyshev

\frac{p(1-p)}{n\varepsilon^2} \leq \frac{1}{4n\varepsilon^2} \leq 0.05, \qquad\text{i.e.}\qquad n \geq \frac{1}{4\cdot0.05\cdot(0.01)^2} = 50\,000 .

La dependencia es brutal en $\varepsilon$ (cuadrática) y leve en la confianza (lineal en $1/\alpha$ ). Ambas características son propiedades del atado, no de la verdad: el Las desigualdades exponenciales del problema del fin de semana reducen el precio de confianza de $1/\alpha$ a $\ln(1/\alpha)$ — lo mismo La especificación costará alrededor de muestras $18\,500$ allí — mientras que la báscula $1/\varepsilon^2$ es genuina y inmejorable. Saber qué parte de un salto está suelta es tan tan útil como el cota mismo.

La ley de los grandes números en imagen: el ley de S_n/n (dibujado esquemáticamente) mantiene su centro m pero se estrecha a medida que n crece, por lo que la probabilidad fuera de la banda [m- , m+ ] — las dos colas — se reduce a cero. Chebyshev ata las colas por V(X_1)/(n 2); el problema del fin de semana muestra que lo son de hecho, exponencialmente pequeño. — La ley de los grandes números en imagen: el ley de $S_n/n$ (dibujado esquemáticamente) mantiene su centro $m$ pero se estrecha a medida que $n$ crece, por lo que la probabilidad fuera de la banda $\intcc{m-\varepsilon}{m+\varepsilon}$ — las dos colas — se reduce a cero. Chebyshev ata las colas por $V(X_1)/(n\varepsilon^2)$ ; el problema del fin de semana muestra que lo son de hecho, exponencialmente pequeño.

Observación 22.29 (Perspectivas dentro de este volumen)

Adelante, todo aquí alimenta a Capítulo 23: el expectativa $\E(t^X)$ de una astuta función de paquetes $X$ todo el ley en una serie de potencias, los momentos se convierten derivados en $1$ e identidades tipo Wald para sumas aleatorias llevar la teoría del proceso de ramificación; el teorema del producto para Las variables independiente se convierten en multiplicatividad de generando funciones. Al revés, expectativa es un baricentro con ponderaciones de probabilidad (Capítulo 17), de Jensen la desigualdad es la geometría de la línea de soporte de funciones convexas (Capítulo 8), y el método del momento exponencial de El problema del fin de semana de este capítulo se aplica a Markov. $\eu^{tX}$ — una desigualdad, mejorada por un buen cambio de variable, que abarca tres capítulos.

22.5 Ceremonias

Ejercicio 22.1 ★

Calcule $\E(X)$ y $V(X)$ para $X \sim \mathcal{B}(n, p)$ (a través de indicadores), $X \sim \mathcal{P}(\lambda)$ (mostrar $V(X) = \lambda$ ) y $X \sim \mathcal{G}(p)$ (mostrar $V(X) = \frac{1-p}{p^2}$ ; use $\E(X(X-1))$ y la segunda derivada de la serie geométrica).

Solución

Solución de Ejercicio 22.1.

Binomio: $X = \sum_{i=1}^n X_i$ con independiente Bernoulli $X_i$ ; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ y variaciones de variables independiente agregar (Teorema 22.14):

\E(X) = np, \qquad V(X) = np(1-p) .

veneno: $\E\bigl(X(X-1)\bigr) = \sum_{k\geq2}k(k-1)e^{-\lambda}\frac{\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda^2$ , entonces

V(X) = \E(X^2) - \E(X)^2 = \lambda^2 + \lambda - \lambda^2 = \lambda .

Geométrico ( $q = 1 - p$ ): diferenciando $\sum_{k\geq0}q^k = \frac{1}{1-q}$ dos veces dentro del disco (Capítulo 11), $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ , entonces

\E\bigl(X(X-1)\bigr) = pq\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2q}{p^2}, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{q}{p^2} = \frac{1-p}{p^2} .

Ejercicio 22.2 ★

Sean $X \sim \mathcal{P}(\lambda)$ y $Y \sim \mathcal{P}(\mu)$ independiente. Muestra que $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolución de los pesos; teorema del binomio), y que el ley condicional de $X$ dado $X + Y = n$ es binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

Solución

Solución de Ejercicio 22.2.

Suma: por $n \in \N$ , por desunión y independencia,

\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k) = e^{-(\lambda + \mu)}\frac{1}{n!} \sum_{k=0}^n \binom nk \lambda^k\mu^{n-k} = e^{-(\lambda+\mu)}\frac{(\lambda + \mu)^n}{n!}

por el teorema del binomio: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Conditional ley: para $0 \leq k \leq n$ ,

\P(X = k \mid X + Y = n) = \frac{\P(X = k)\P(Y = n - k)}{\P(X + Y = n)} = \binom nk \Bigl(\frac{\lambda}{\lambda+\mu}\Bigr)^{k} \Bigl(\frac{\mu}{\lambda+\mu}\Bigr)^{n-k} ,

el binomio ley $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : dado el conteo total, cada evento "elige" independientemente la primera fuente con probabilidad proporcional a su tasa.

Ejercicio 22.3 ★

(Coleccionista de cupones, expectativa) Una marca de cereal esconde uno de $n$ juguetes distintos, uniformemente, en cada caja. Sea $T_n$ el número de Cajas necesarias para recoger todos los juguetes $n$ . Escribiendo $T_n$ como una suma de independiente variables geométricas (es hora de ver un juguete nuevo cuando $k$ todavía faltan), mostrar

\E(T_n) = n\sum_{k=1}^{n}\frac{1}{k} \sim n\ln n

(equivalente por la serie-comparación integral de Capítulo 6).

Solución

Solución de Ejercicio 22.3.

Cuando aún faltan juguetes $k$ , cada caja nueva trae un juguete nuevo con probabilidad $\frac kn$ , independientemente del pasado: el El tiempo de espera $W_k$ para el próximo juguete nuevo es geométrico. $\mathcal{G}\bigl(\frac kn\bigr)$ , con $\E(W_k) = \frac nk$ , y $T_n = W_n + W_{n-1} + \dots + W_1$ (el primer cuadro siempre proporciona una nueva juguete: $W_n = 1$ , compatible con $\E = n/n$ ). Por linealidad,

\E(T_n) = \sum_{k=1}^n \frac nk = n\sum_{k=1}^n\frac1k \sim n\ln n ,

usando $\sum_{k\leq n}\frac1k = \ln n + \gamma + o(1)$ (Capítulo 6). Recoger los últimos juguetes es lo que costos: la mitad de las cajas van al último puñado.

Ejercicio 22.4 ★★

Sea $X \geq 0$ un valor entero. Prueba el fórmula de la cola

\E(X) = \sum_{n=1}^{\infty} \P(X \geq n)

(cuando cualquiera de los lados es finito), escribiendo $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ e intercambiando sumatorias (Fubini para familias no negativas). Recuperar $\E(X) = \frac1p$ para el geométrico ley.

Solución

Solución de Ejercicio 22.4.

Puntualmente, $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . la doble familia $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ no es negativo, por lo que Fubini para familias (Capítulo 7) se aplica incondicionalmente: sumando primero en $n$ da $\E(X)$ , sumando primero en $\omega$ da $\sum_n \P(X \geq n)$ ; los dos son simultáneamente finitos e iguales. Para $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), entonces $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Ejercicio 22.5 ★★

(El muestreo sin reposición es más concentrado) Una urna tiene $N$ bolas, $M$ de ellas blancas. Sorteo $n \leq N$ sin reemplazo y dejemos que $X$ cuente los blancos (hipergeométrico ley). Usando Indicadores $X = \sum_{i=1}^n Y_i$ con $Y_i$ del sorteo $i$ : muestre que cada $Y_i$ es Bernoulli del parámetro $p = M/N$ (¡simetría!), Concluya $\E(X) = np$ exactamente como con el reemplazo y muestre $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ para $i \neq j$ , por lo tanto $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

Solución

Solución de Ejercicio 22.5.

Simetría: la $i$ -ésima bola extraída es una bola uniformemente aleatoria de la urna (cualquiera de las bolas $N$ tiene la misma probabilidad de aterrizar en posición $i$ del orden de dibujo), por lo que $\P(Y_i = 1) = \frac MN = p$ y $\E(X) = np$ por linealidad — no se necesita independencia.

Covarianza: para $i \neq j$ , $\E(Y_iY_j) = \P(\text{draws } i, j \text{ both white}) = \frac{M(M-1)}{N(N-1)}$ (pares ordenados de posiciones distintas obtienen un par ordenado de bolas distintas, uniformemente). Por lo tanto

\operatorname{Cov}(Y_i, Y_j) = \frac{M(M-1)}{N(N-1)} - \frac{M^2}{N^2} = \frac{M(N - M)}{N^2}\cdot\frac{-1}{N-1} = -\frac{p(1-p)}{N-1} < 0 :

Sacar una bola blanca hace que las blancas sean más escasas para los otros sorteos. Por Teorema 22.14,

V(X) = np(1-p) + n(n-1)\Bigl(-\frac{p(1-p)}{N-1}\Bigr) = np(1-p)\,\frac{N - n}{N - 1} \leq np(1-p) :

el muestreo sin reemplazo tiene la misma media pero menor diferencia que con reemplazo (igualdad solo para $n = 1$ ), el correlaciones negativas que actúan como estabilizador. Para $n = N$ el diferencia desaparece: el recuento es entonces determinista.

Ejercicio 22.6 ★★

Dejemos que $X$ tenga un segundo momento. Demuestre que $c \mapsto \E\bigl((X - c)^2\bigr)$ es mínimo exactamente en $c = \E(X)$ , con mínimo $V(X)$ . Luego muestre que $\P(X = \E(X)) = 1$ si y solo si $V(X) = 0$ . (For the second point: if $V(X) = 0$ , use Chebyshev with $\varepsilon = 1/n$ and monotone continuidad, Teorema 21.6.)

Solución

Solución de Ejercicio 22.6.

Ampliando alrededor de $m = \E(X)$ :

\E\bigl((X - c)^2\bigr) = \E\bigl((X - m)^2\bigr) + 2(m - c)\,\E(X - m) + (m - c)^2 = V(X) + (m - c)^2 ,

mínimo exactamente en $c = m$ con valor $V(X)$ — expectativa es el mejor predictor constante en cuadrado medio.

Si $\P(X = m) = 1$ entonces $(X - m)^2$ desaparece con probabilidad $1$ , por lo que $V(X) = 0$ (la familia definitoria tiene términos nulos excepto en un conjunto nulo). Por el contrario, si $V(X) = 0$ , Chebyshev (Teorema 22.15) da $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ por cada $n$ ; el eventos $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ aumenta a $\{X \neq m\}$ , por lo que es monótono continuidad (Teorema 21.6) produce $\P(X \neq m) = 0$ .

Ejercicio 22.7 ★★★

(La concentración supera a Markov) Sea $S_n \sim \mathcal{B}(n, \frac12)$ (número de caras en $n$ lanzamientos justos). comparar el límites dados por Markov ( $\P(S_n \geq \frac{3n}{4})$ ), por Chebyshev, y por el método exponencial (Chernoff):

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \E\bigl(e^{tS_n}\bigr)e^{-3nt/4} = \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} \quad (t > 0),

y optimice $t$ para obtener un límite exponencialmente pequeño. (At $t = \ln 3$ : bound $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

Solución

Solución de Ejercicio 22.7.

$\E(S_n) = \frac n2$ y $V(S_n) = \frac n4$ . Markov: $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — un límite constante, inútil para grande $n$ . Chebyshev: el evento implica $\abs{S_n - \frac n2} \geq \frac n4$ , por lo que la probabilidad es $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — decae, pero solo polinomialmente. Chernoff: por independencia, $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ y Markov aplicado a $e^{tS_n} \geq e^{3nt/4}$ da, por cada $t > 0$ ,

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} = \exp\Bigl(n\bigl(\ln\tfrac{1 + e^t}{2} - \tfrac{3t}4\bigr)\Bigr).

Minimiza el exponente: $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ en $e^t = 3$ , es decir $t = \ln 3$ , dando

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{4}{2}\Bigr)^n 3^{-3n/4} = \bigl(2 \cdot 3^{-3/4}\bigr)^n \approx (0.877)^n ,

exponencialmente pequeño. La jerarquía Markov $\to$ Chebyshev $\to$ Chernoff es la escalera estándar: cada peldaño aplica a Markov a un función de la variable que crece más rápidamente.

Ejercicio 22.8 ★★★

(Weierstrass de nuevo, probabilísticamente) Sea $f \colon [0,1] \to \R$ ser continuo y $S_n \sim \mathcal{B}(n, x)$ . Demuestre que el Polinomio de Bernstein $B_nf(x) = \sum_{k=0}^n f\bigl(\frac kn\bigr)\binom nk x^k(1-x)^{n-k}$ es igual $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ y volver a derivar el estimación $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ de Capítulo 10 en este lenguaje probabilístico (dividido en $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ y uso Chebyshev).

Solución

Solución de Ejercicio 22.8.

Por el teorema de la transferencia (Teorema 22.7) aplicado a $f\bigl(\frac{S_n}{n}\bigr)$ con $S_n \sim \mathcal{B}(n, x)$ :

\E\Bigl[f\Bigl(\frac{S_n}{n}\Bigr)\Bigr] = \sum_{k=0}^n f\Bigl(\frac kn\Bigr)\binom nk x^k(1-x)^{n-k} = B_nf(x) .

Repare $\delta > 0$ y divida $\abs{f(S_n/n) - f(x)}$ en evento $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : apagado $D$ , la diferencia es como máximo el módulo de continuidad $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; en $D$ , como máximo $2\norm f_\infty$ . Tomando esperanzas de heredar y usando Chebyshev con $V\bigl(\frac{S_n}{n}\bigr) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$ :

\abs{B_nf(x) - f(x)} \leq \E\,\abs{f(S_n/n) - f(x)} \leq \omega_f(\delta) + 2\norm f_\infty\,\P(D) \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2} .

El uniforme continuidad de $f$ en $[0, 1]$ hace $\omega_f(\delta) \to 0$ : elija $\delta$ , luego $n$ y $B_nf \to f$ uniformemente — el Teorema de aproximación de Weierstrass de Capítulo 10, cuyo El "lema de conteo" ahora es reconocible como la desigualdad de Chebyshev para el binomio ley.

Ejercicio 22.9 ★★★

(Fuerte ley en el cuarto momento) Sea $(X_k)$ independiente, idénticamente distribuido, centrado ( $\E X_1 = 0$ ), con $\E(X_1^4) < \infty$ . Expandiendo $\E(S_n^4)$ y contando el Los términos supervivientes (solo términos $\E(X_i^4)$ y $\E(X_i^2X_j^2)$ , $i \neq j$ ), muestran $\E(S_n^4) \leq C n^2$ para una constante $C$ . deducir $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ para cada $\varepsilon > 0$ (Markov en el orden 4) y concluir con Borel–Cantelli (Teorema 21.25) que $S_n/n \to 0$ casi seguramente siguiendo una formulación adecuada: el evento $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ tiene probabilidad $1$ .

Solución

Solución de Ejercicio 22.9.

Expanda $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ y tome esperanzas de heredar. Por independencia y centrado, cualquier término que contenga un índice que aparece exactamente una vez desaparece (factores $\E(X_i) = 0$ fuera). Términos supervivientes: los términos diagonales $n$ $\E(X_i^4)$ y los términos que emparejan dos pares de índices iguales, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ para $i \neq j$ , que aparecen $3n(n-1)$ veces: elija el par desordenado de valores (formas $\binom n2$ ), luego el $\frac{4!}{2!\,2!} = 6$ formas de colocarlos en las cuatro ranuras — $6\binom n2 = 3n(n-1)$ . Por lo tanto, con $\E(X_1^2)^2 \leq \E(X_1^4)$ (Jensen o Cauchy–Schwarz),

\E(S_n^4) = n\,\E(X_1^4) + 3n(n-1)\,\E(X_1^2)^2 \leq C n^2, \qquad C = 4\,\E(X_1^4) .

Markov en el orden 4:

\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}{n^2\varepsilon^4} ,

una serie sumable. Por Borel–Cantelli 1 (Teorema 21.25), por cada $j$ el evento $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ tiene probabilidad $0$ , entonces $\P\bigl(\bigcup_j B_j\bigr) = 0$ por contable subaditividad. Sobre el complemento — de probabilidad $1$ — por cada $j$ hay $N$ con $\abs{S_n/n} < \frac1j$ para todos $n \geq N$ : precisamente $S_n/n \to 0$ . La fuerte ley de las grandes los números se mantienen bajo un cuarto momento; eliminando esa hipótesis (Teorema de Kolmogorov) es el trabajo del año 3.

Ejercicio 22.10 ★

Se lanzan dos dados justos; sea $M$ el mayor de los dos resultados. Usando la fórmula de cola de Ejercicio 22.4 (versión finita), mostrar

\E(M) = \sum_{k=1}^{6}\P(M \geq k) = 6 - \sum_{j=0}^5\Bigl(\frac j6\Bigr)^2 = \frac{161}{36} \approx 4.47 .

Solución

Solución de Ejercicio 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (ambos dados como máximo $k$ , de forma independiente), por lo que $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ y

\E(M) = \sum_{k=1}^6\P(M \geq k) = 6 - \frac{0 + 1 + 4 + 9 + 16 + 25}{36} = 6 - \frac{55}{36} = \frac{161}{36} \approx 4.47 ,

cómodamente por encima de la media $3.5$ de un solo dado, como máximo debería ser.

Ejercicio 22.11 ★★

Sea $F_n$ el número de puntos fijos de un sistema uniformemente aleatorio. permutación de $\{1, \dots, n\}$ ( $n \geq 2$ ). Escribiendo $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ , calcula $\E(F_n) = 1$ , $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ para $i \neq j$ , y concluir $V(F_n) = 1$ : en promedio una letra es fija, con diferencia exactamente $1$ , lo que sea $n$ .

Solución

Solución de Ejercicio 22.11.

Con $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ , entonces $\E(F_n) = n\cdot\frac1n = 1$ . Para $i \neq j$ : $\P(\sigma(i) = i, \sigma(j) = j) = \frac{(n-2)!}{n!} = \frac1{n(n-1)}$ , por lo tanto

\operatorname{Cov}(I_i, I_j) = \frac1{n(n-1)} - \frac1{n^2} = \frac{1}{n^2(n-1)} .

Por el kit de herramientas diferencia (Teorema 22.14),

V(F_n) = n\cdot\frac1n\Bigl(1 - \frac1n\Bigr) + n(n-1)\cdot\frac1{n^2(n-1)} = 1 - \frac1n + \frac1n = 1 .

Media $1$ , diferencia $1$ , independiente de $n$ — consistente con el límite de Poisson del problema de emparejamiento (Ejercicio 21.5).

Ejercicio 22.12 ★★★

(Coleccionista de cupones, concentración) En el marco de Ejercicio 22.3, mostrar

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq n^2\sum_{k=1}^n\frac{1}{k^2} \leq \frac{\pi^2}{6}n^2,

utilizando independencia de las etapas geométricas y $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (Ejercicio 22.1; el valor $\pi^2/6$ es Ejemplo 14.12). deducir con Chebyshev que $\dfrac{T_n}{n\ln n} \to 1$ en probabilidad: el tiempo total del coleccionista es $n\ln n$ hasta fluctuaciones de orden $n$ .

Solución

Solución de Ejercicio 22.12.

$T_n = \sum_{k=1}^nG_k$ donde $G_k \sim \mathcal G(k/n)$ es el momento de ver un juguete nuevo cuando falta $k$ , las etapas siendo independiente. Por lo tanto

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq \sum_{k=1}^n\frac{n^2}{k^2} \leq \frac{\pi^2}6\,n^2 ,

por Ejemplo 14.12. Con $\E(T_n) = nH_n$ , $H_n = \sum_1^n\frac1k$ (Ejercicio 22.3), Chebyshev da, para $\varepsilon > 0$ ,

\P\bigl(\abs{T_n - nH_n} \geq \varepsilon\,n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2 n} = \frac{\pi^2}{6\,\varepsilon^2\ln^2n} \xrightarrow[n\to\infty]{} 0 .

Desde $H_n \sim \ln n$ , al dividir por $n\ln n$ se muestra $T_n/(n\ln n) \to 1$ en probabilidad: las fluctuaciones de $T_n$ son del orden $n$ , insignificantes frente a la media $n\ln n$ .

22.6 Problema: la caja de herramientas de la concentración, desde Markov hasta Höffding

Problema 22.1

Problema de fin de semana — concentración exponencial a mano, y a cuantas personas debe preguntar una encuesta

La desigualdad de Markov cuesta un momento y compra una decadencia $1/a$ ; Chebyshev cuesta dos momentos y compra $1/\varepsilon^2$ — y Ejemplo 22.18 muestra que son todos esos Los momentos pueden comprar. Este problema sube el resto de la escalera: el método exponencial (Chernoff) con su tasa exacto para lanzamientos de moneda, la desigualdad de Hoeffding para todos los límites variables y el beneficio: tamaños de muestra explícitos y honestos para encuestas, convocatorias electorales y pruebas de monedas. En todo momento, $S_n \sim \mathcal B(n, p)$ es una suma de $n$ independiente Bernoulli variables y $\widehat p_n = S_n/n$ la frecuencia empírica.

Parte I — Calibration on the fair coin. Aquí $p = \frac12$ y $a \in \intoo{\frac12}{1}$ .

Markov en el nivel $an$ : muestra $\P(S_n \geq an) \leq \frac1{2a}$ , un límite que ni siquiera tiende a $0$ . ¿Dónde pierde tanto Markov?
Chebyshev: utilizando la simetría del binomio justo sobre $n/2$ , mostrar

$\P(S_n \geq an) = \tfrac12\, \P\bigl(\abs{S_n - \tfrac n2} \geq n(a - \tfrac12)\bigr) \leq \frac{1}{8n(a - 1/2)^2},$

es decir, $\frac2n$ en $a = \frac34$ : decaimiento polinómico en último.
(Chernoff, nivel general) Computar $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ y optimizar $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ sobre $t > 0$ : mostrar el $t$ óptimo es $\ln\frac{a}{1-a}$ y

$\P(S_n \geq an) \leq \eu^{-n\,I(a)}, \qquad I(a) = \ln 2 + a\ln a + (1-a)\ln(1-a) > 0 .$

Comprueba que $a = \frac34$ recupera el cota. $\bigl(2\cdot3^{-3/4}\bigr)^n$ de Ejercicio 22.7.
(El exponente es exacto) Sea $k = an$ un número entero. Del hecho de que $\binom nk a^k(1-a)^{n-k}$ es el mayor de los términos $n + 1$ de una probabilidad distribución, pruebe $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ con $H(a) = -a\ln a - (1-a)\ln(1-a)$ y deduzca el límite inferior coincidente

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Tabule los tres límites en $n = 100$ , $a = \frac34$ : Markov $\frac23$ , Chebyshev $0.02$ , Chernoff $\approx 2.1\cdot10^{-6}$ (el valor real es $\approx 2.8\cdot10^{-7}$ ). ¿Moral, en una frase?

Parte II — Hoeffding’s inequality.

(caso Rademacher) Para $\varepsilon = \pm1$ con probabilidad $\frac12$ cada uno, probar

$\E(\eu^{t\varepsilon}) = \cosh t \leq \eu^{t^2/2} \qquad (t \in \R)$

comparando las dos series término por término ( $(2k)! \geq 2^kk!$ ).
Deducir, para independiente variables Rademacher $\varepsilon_1, \dots, \varepsilon_n$ y cada $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Traducir a monedas justas ( $X_i = \frac{1+\varepsilon_i}2$ ): $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ , y la versión de dos caras con un factor $2$ .
(lema de Hoeffding) Sea $X \in \intcc01$ con $\E X = p$ y $\psi(t) = \ln\E(\eu^{tX})$ . justifica eso $\psi$ es el doble de diferenciable con

$\psi''(t) = \E_t(X^2) - \E_t(X)^2, \qquad \E_t(Y) := \frac{\E(Y\eu^{tX})}{\E(\eu^{tX})},$

a diferencia de una variable reponderada todavía tomando valores en $\intcc01$ ; atado por $\frac14$ (Argumento de minimalidad de Ejercicio 22.6) y Concluye por Taylor:

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(desigualdad de Hoeffding) Para independiente $X_i \in \intcc01$ con media común $p$ , deduzca

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Comparar el tipo de cambio Chebyshev $\frac{p(1-p)}{n\delta^2}$ con Hoeffding $2\eu^{-2n\delta^2}$ : ¿qué hipótesis tiene cada una? requieren, y desde el cual $n$ (aproximadamente) hace el ¿Ganar límite exponencial en $\delta = 0.03$ , $p = \frac12$ ?

Parte III — How many people must a poll ask? Una encuesta pregunta $n$ independiente, votantes elegidos uniformemente; cada uno responde honestamente; $p$ es la puntuación real, $\widehat p_n$ la cifra de la encuesta.

Demuestre que la encuesta es precisa para $\pm\delta$ con confianza $1 - \alpha$ (es decir, $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) tan pronto como

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Calcule el $n$ requerido para el estándar "tres puntos, noventa y cinco por ciento” especificación ( $\delta = 0.03$ , $\alpha = 0.05$ ): $n \geq 2050$ ; y por uno punto: $n \geq 18\,445$ . Observa — y explica — el hecho sorprendente de que la respuesta no implica el tamaño de la población.
Rehacer la pregunta 13 con Chebyshev ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ en tres puntos. Tenga en cuenta que el muestreo El reemplazo sin solo ayuda (Ejercicio 22.5: el diferencia se encoge $\frac{N-n}{N-1}$ ).
(Convocatoria de elecciones) La verdadera puntuación de un candidato es $p = 0.52$ . ¿Cuántos votantes deben ser encuestados para que $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Mostrar $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — llamar a una carrera reñida cuesta mucho más que estimar una puntuación.
Qué cubren las matemáticas no: enumere las supuestos de modelado utilizados (independiente uniforme muestreo, respuestas honestas, arreglado $p$ ), y explique en Un breve párrafo de por qué se producen errores reales en las encuestas. dominado por inclinación (muestreo no uniforme, falta de respuesta), que ningún aumento de $n$ reduce.

Parte IV — Sharper and cheaper.

(Mediana de medias: decaimiento exponencial de dos momentos) Divida un presupuesto de muestras $km$ en $k$ independiente grupos de $m$ ; sea $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ la media del grupo y $M$ su mediana. Elija $m$ para que cada grupo satisfaga $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (Chebyshev: $m \geq \frac2{\delta^2}$ basta). Mostrar que si $\abs{M - p} \geq \delta$ entonces al menos $k/2$ grupos se equivocan y deducen

$\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil}\Bigl(\frac18 \Bigr)^{k/2} \leq 2^k\cdot 8^{-k/2} = 2^{-k/2} :$

concentración exponencial sin usar nada más allá variaciones.
(Paley–Zygmund) Para $X \geq 0$ con un segundo momento, probar $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz on $X\mathbf 1_{X>0}$ ): el herramienta de dirección inversa — los momentos también pueden forzar eventos suceda.
(Pinsker-lite) Mostrar $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ en $\intoo{\frac12}1$ (the difference vanishes to second order at $\frac12$ and its second derivative is $\frac1{a(1-a)} - 4 \geq 0$ ): El exponente exacto de Chernoff siempre supera La cuadrática de Hoeffding.
Expanda $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ y combine con la pregunta 4: para pequeños desviaciones el exponente de Hoeffding $2n\delta^2$ es asintóticamente exacto — ningún método puede superarlo por más que factores polinomiales.
Elabora la tabla de la caja de herramientas: para Markov, Chebyshev, el límite de cuarto momento de Ejercicio 22.9, Hoeffding y Chernoff con exponente $I$ , indican en una línea cada uno: hipótesis requerida, decaimiento obtenido, y la pregunta en este problema donde estaba más agudo.

Part V — Dividends.

(Probando una moneda) Una moneda es justa o está sesgada con $p = 0.55$ . Le das la vuelta $n$ veces y declaras “sesgado” cuando $\widehat p_n > 0.525$ . mostrar eso ambas probabilidades de error son como máximo $\eu^{-2n(0.025)^2}$ , y que $n \geq 3685$ voltea Garantizar ambos por debajo de $1\%$ .
(raro eventos necesita un límite que tenga en cuenta la variación) Dejemos que sea $p = 0.01$ y tome la especificación relativa $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . comparar la muestra tamaños exigidos por Hoeffding ( $n \approx 74\,000$ ) y por Chebyshev con el verdadero diferencia $p(1-p)$ ( $n \approx 7920$ ): el límite exponencial ciego a la varianza Pierde al humilde segundo momento. Indique la moraleja, y donde la herramienta que falta (una herramienta consciente de la variación) límite exponencial; la aproximación de Poisson de Capítulo 23) provendrá.
(Fuerte ley para monedas) De $\sum_n 2\eu^{-2n\delta^2} < \infty$ y Borel–Cantelli (Teorema 21.25), demostrar que $\widehat p_n \to p$ casi seguramente para independiente lanzamientos de moneda: formule el casi seguro evento como $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ como en Ejercicio 22.9 y concluir. (limitación reemplaza el cuarto momento usado allí.)
Síntesis. En cinco frases: lo que cada peldaño del escalera (momentos uno, dos, cuatro; exponencial acotado; exponente exacto) costos y compras; ¿Por qué encuestar $2050$ ? personas son suficientes para un país de cualquier tamaño; y cual de estos límites el volumen del Año 3 se afinará en las constantes exactas del teorema del límite central.

Solución

Solución de Problema 22.1.

1. $\E(S_n) = \frac n2$ y Markov (Teorema 22.15) dé $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov sólo conoce el medio: no se puede distinguir una variable concentrada en $n/2$ de una repartido entre $0$ y $n$ , por lo que fija el precio de la cola como si todos la masa podría sentarse allí.

2. El binomio justo es simétrico sobre $n/2$ ( $S_n$ y $n - S_n$ tienen el mismo ley), por lo que con $x = n(a - \frac12) > 0$ los dos eventos $\{S_n - \frac n2 \geq x\}$ y $\{S_n - \frac n2 \leq -x\}$ son disjuntos y equiprobables: $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . Chebyshev con $V(S_n) = \frac n4$ :

\P(S_n \geq an) \leq \frac12\cdot\frac{n/4}{n^2(a - 1/2)^2} = \frac1{8n(a - 1/2)^2},

que es $\frac2n$ en $a = \frac34$ .

3. Por independencia y el teorema del producto, $\E(\eu^{tS_n}) = \bigl(\E \eu^{tX_1}\bigr)^n = \bigl(\frac{1 + \eu^t}2\bigr)^n$ . Markov aplicó a $\eu^{tS_n}$ :

\P(S_n \geq an) \leq \eu^{-tan}\Bigl(\frac{1 + \eu^t}2\Bigr)^{\!n} = \exp\Bigl(n\bigl(\ln\tfrac{1 + \eu^t}2 - ta\bigr)\Bigr).

La derivada del exponente en $t$ es $\frac{\eu^t}{1 + \eu^t} - a$ y desaparece en $\eu^t = \frac a{1-a}$ , es decir, $t^* = \ln\frac a{1-a} > 0$ ; ahí $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ y el exponente es igual

n\Bigl(-\ln 2 - \ln(1-a) - a\ln\frac a{1-a}\Bigr) = -n\bigl(\ln2 + a\ln a + (1-a)\ln(1-a)\bigr) = -n\,I(a),

con $I(\frac12) = 0$ y $I'(a) = \ln\frac a{1-a} > 0$ encendidos $\intoo{\frac12}1$ : $I(a) > 0$ . En $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , el límite de Ejercicio 22.7.

4. La suma de los números $n + 1$ $\binom nja^j(1-a)^{n-j}$ a $1$ , y el más grande es el de $j = k = an$ (el modo de $\mathcal B(n, a)$ es $\floor{(n+1)a} = k$ aquí). un máximo de números $n + 1$ que suman $1$ es al menos $\frac1{n+1}$ :

\binom nk a^k(1-a)^{n-k} \geq \frac1{n+1} \quad\Longrightarrow\quad \binom nk \geq \frac{a^{-an}(1-a)^{-n(1-a)}}{n+1} = \frac{\eu^{nH(a)}}{n+1}.

Por lo tanto $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : hasta el factor polinómico $n + 1$ , el exponente de Chernoff es la verdad.

5. $n = 100$ , $a = \frac34$ : Markov $\frac23$ ; Chebyshev $\frac2{100} = 0.02$ ; Chernoff $(2\cdot3^{-3/4})^{100} = \eu^{-100\,I(3/4)} \approx 2.1\cdot10^{-6}$ , contra el $2.8\cdot10^{-7}$ exacto. Moraleja: cada momento de información divide polinomialmente el límite; el momento exponencial cambia su naturaleza.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ y $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ; el reclamo sigue término por término de $(2k)! \geq 2^kk!$ , que se mantiene por inducción: $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. Por independencia, $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , entonces Markov da $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; minimizar en $t = s/n$ produce $\eu^{-s^2/(2n)}$ .

8. Con $X_i = \frac{1 + \varepsilon_i}2$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , entonces $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ y la pregunta 7 da la cota $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . el evento simétrico tiene el mismo límite, de donde el factor $2$ para $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ es un serie de funciones suaves de $t$ cuyo término por término Los derivados están dominados, en cada intervalo compacto $t$ , por $\eu^{\abs t}\P(X = x)$ (como $0 \leq x \leq 1$ ): por el teorema de diferenciación para series convergentes normalmente (Teorema 10.7) es el doble diferenciable, y la regla del cociente da $\psi' = \E_t(X)$ y $\psi'' = \E_t(X^2) - \E_t(X)^2$ , donde $\E_t$ es el expectativa para los pesos reponderados $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — no negativo, sumando a $1$ , llevado por los mismos valores $x \in \intcc01$ . Adiferencia de una variable con valor $\intcc01$ es como máximo $\frac14$ : por Ejercicio 22.6, es $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . taylor con resto integral, usando $\psi(0) = 0$ , $\psi'(0) = p$ :

\psi(t) = tp + \int_0^t(t - s)\,\psi''(s)\,\dd s \leq tp + \frac{t^2}2\cdot\frac14,

es decir, $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ para todos los $t$ reales.

10. Por independencia, $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ; Markov y la optimización $t = 4\delta$ dan

\P(\widehat p_n - p \geq \delta) \leq \eu^{nt^2/8 - tn\delta}\Big|_{t = 4\delta} = \eu^{-2n\delta^2};

aplicando esto a las variables $1 - X_i$ (también en $\intcc01$ ) limita la otra cola, de donde los dos lados $2\eu^{-2n\delta^2}$ .

11. Chebyshev sólo necesita un segundo momento y da $\frac{p(1-p)}{n\delta^2}$ ; Necesidades de Hoefding limitación y da $2\eu^{-2n\delta^2}$ . En $p = \frac12$ , $\delta = 0.03$ : los límites son $\frac{278}{n}$ (aproximadamente) versus $2\eu^{-0.0018n}$ ; cruzan cerca de $n \approx 1200$ , luego en el que gana el límite exponencial, y mucho ( $n = 5000$ : $0.056$ frente a $2.5\cdot10^{-4}$ ).

12. Por Hoeffding (pregunta 10), $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ como tan pronto como $2n\delta^2 \geq \ln\frac2\alpha$ , es decir, $n \geq \frac{\ln(2/\alpha)}{2\delta^2}$ .

13. $\delta = 0.03$ , $\alpha = 0.05$ : $n \geq \frac{\ln 40}{2\cdot0.0009} \approx 2049.4$ : $2050$ personas. Para $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . El tamaño de la población nunca aparece porque cada El votante de la muestra se modela como un nuevo sorteo de Bernoulli $(p)$ : el La dificultad de la encuesta es el diferencia de una moneda, no el tamaño de el país. Reducir a la mitad el margen cuesta cuatro veces la muestra — la ley $1/\delta^2$ .

14. Chebyshev: $\P(\abs{\widehat p_n - p} \geq \delta) \leq \frac{p(1-p)}{n\delta^2} \leq \frac1{4n\delta^2} \leq \alpha$ para $n \geq \frac1{4\alpha\delta^2}$ , es decir $5556$ en tres puntos — aproximadamente $2.7$ veces el requisito de Hoeffding. sin reemplazo, el diferencia se multiplica por $\frac{N - n}{N-1} < 1$ (Ejercicio 22.5), por lo que el mismo $n$ puede sólo hacerlo mejor: el cálculo con reemplazo es el uno conservador.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , por lo unilateral Hoeffding se unió a $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ tan pronto como $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ votantes. El costo escalas como el cuadrado inverso del dirigir, no del Precisión deseada: las carreras reñidas son caras.

16. Usado: la muestra se extrae uniformemente y independientemente del electorado; cada persona muestreada responde, honestamente, y $p$ no se mueve durante la encuesta. reales Las encuestas violan los tres: encuestados accesibles y dispuestos. no son una muestra uniforme (sesgo de selección y falta de respuesta), y las respuestas pueden ser falsas o inestables. Estos son Errores inclinación: alejan $\E(\widehat p_n)$ de $p$ por una cantidad independiente de $n$ , por lo que no hay tamaño de muestra los reduce — las matemáticas de esta Parte controlan sólo el término de fluctuación.

17. Chebyshev para un grupo de tamaño $m$ : $\P(\abs{ \widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ para $m \geq \frac2{\delta^2}$ . Si menos de Los grupos $k/2$ se equivocan, entonces más de $k/2$ de los valores $\widehat p^{(i)}$ se encuentran en el intervalo abierto $\intoo{p - \delta}{p + \delta}$ , al igual que su mediana; por lo tanto $\{\abs{M - p} \geq \delta\}$ fuerza al menos errores $\lceil k/2\rceil$ entre los grupos $k$ independiente. la unión enlazado sobre los $\binom k{\lceil k/2\rceil}$ posibles conjuntos de grupos errantes dan

\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil} \Bigl(\frac18\Bigr)^{k/2} \leq 2^k\,8^{-k/2} = 2^{-k/2} :

caída exponencial en el número de grupos, comprado con nada más que variaciones — útil precisamente cuando los comandos son ilimitados y Hoeffding no está disponible.

18. Cauchy–Negro (Teorema 22.19):

\E(X) = \E(X\,\mathbf 1_{X>0}) \leq \sqrt{\E(X^2)}\sqrt{\E(\mathbf 1_{X>0}^2)} = \sqrt{\E(X^2)\,\P(X > 0)} ;

cuadrar y dividir.

19. Vamos $h(a) = I(a) - 2(a - \tfrac12)^2$ . entonces $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ desaparece en $\tfrac12$ , y

h''(a) = \frac1a + \frac1{1-a} - 4 = \frac{1}{a(1-a)} - 4 \geq 0

desde $a(1-a) \leq \frac14$ . Entonces $h'$ aumenta desde $0$ en adelante $\intco{\frac12}1$ , por lo tanto $h' \geq 0$ y $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ , $I''(a) = \frac1{a(1-a)}$ dan $I''(\tfrac12) = 4$ y $I'''(\tfrac12) = 0$ (la función es simétrico sobre $\tfrac12$ ), entonces $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . Pregunta 4 luego limita la cola verdadera abajo por $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : para pequeños $\delta$ el exponente de Hoeffding $2n\delta^2$ es asintóticamente exacto — sólo son posibles mejoras de polinomio en $n$ .

21. Markov: un momento, decaimiento $1/a$ , útil sólo como el motor detrás de los demás (la pregunta 1 lo muestra plano). Chebyshev: dos momentos, decadencia $\frac{V}{n\delta^2}$ , agudo sin más hipótesis (Ejemplo 22.18), y la mejor herramienta en pregunta 23. Cuarto momento (Ejercicio 22.9): decaimiento $C/n^2$ , suficiente sumabilidad para una ley fuerte. Hoeffding: variables acotadas, decaimiento $2\eu^{-2n\delta^2}$ , el caballo de batalla de la Parte III. Chernoff con la tasa exacta $I(a)$ : momentos exponenciales plenos, exponente inmejorable (preguntas 4, 20), el punto de referencia para todo lo demás.

22. Si la moneda es justa: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . Si $p = 0.55$ : $\P(\widehat p_n \leq 0.525) \leq \P(\widehat p_n - 0.55 \leq -0.025) \leq \eu^{-2n(0.025)^2}$ . Ambos errores están por debajo de $0.01$ cuando $2n(0.025)^2 \geq \ln 100$ , es decir $n \geq 3684.2$ : $3685$ voltea. (Las hipótesis distintivas $2.5$ separan los costos lo que cuesta estimar $\pm2.5$ puntos.)

23. Hoeffding: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Chebyshev con el verdadero diferencia $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — nueve veces más barato. exponente de Hoeffding $2n\delta^2$ valora el diferencia en su peor caso $\frac14$ , absurdamente pesimista cuando $p = 0.01$ ; el humilde segundo momento lo sabe mejor. La herramienta que falta es consciente de la variación límite exponencial (desigualdad de Bernstein, año 3) — o, para el raro eventos, la aproximación de Poisson demostró en Capítulo 23, que trabaja sobre el pariente natural. escala.

24. Corrección $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (serie de tipo geométrico), entonces Borel–Cantelli 1 (Teorema 21.25) da $\P(\abs{\widehat p_n - p} \geq \delta \text{ infinitely often}) = 0$ , es decir el evento $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ tiene probabilidad $1$ para cada $j$ . El contable la intersección $\bigcap_jE_j$ todavía tiene probabilidad $1$ (subaditividad en los complementos), y en él $\widehat p_n \to p$ : la ley fuerte de los grandes números para el lanzamiento de una moneda, con limitación desempeñando el papel que desempeñó el cuarto momento en Ejercicio 22.9.

25. Un momento compra una encuadernación plana; dos compran $1/(n\delta^2)$ , y nada más (el ejemplo de nitidez); cuatro compre $1/n^2$ , suficiente para convertirlo en una ley casi segura; la limitación compra $\eu^{-2n\delta^2}$ ; y el completo momento exponencial compra la tasa exacta $I$ , que ningún método latidos. Encuestar a $2050$ personas es suficiente para cualquier país porque la fluctuación de la muestra se rige por el diferencia de la moneda, no el tamaño de la población — el $1/\delta^2$ y Las etiquetas de precio $\ln(1/\alpha)$ son universales. El volumen del año 3. El teorema del límite central reemplaza estas desigualdades, en el Escala $\sqrt n$ , por un límite exacto ley con explícito constantes — convirtiendo cada límite de este problema en un igualdad asintótica.