Matemáticas universitarias — Grado 2 · Bachelor Year 2

22Variables aleatorias discretas

Las variables aleatorias organizan los cálculos de probabilidad en torno a funciones y no a sucesos. Sobre espacios numerables, la teoría se apoya en las familias sumables del Capítulo 7: la esperanza es la suma de una familia indexada por el espacio muestral, y todas sus propiedades —linealidad, transferencia, fórmula del producto para variables independientes— son teoremas sobre familias sumables. El capítulo demuestra las desigualdades clave de Markov, Chebyshev, Cauchy–Schwarz y Jensen, y termina con las leyes clásicas y la ley débil de los grandes números, cuya demostración ocupa dos líneas en cuanto se dispone de Chebyshev.

22.1 Variables aleatorias y sus leyes

Definición 22.1 (Variable aleatoria discreta; ley)

Sea $(\Omega, \P)$ un espacio de probabilidad numerable. Una variable aleatoria es una aplicación $X \colon \Omega \to E$ ( $E$ un conjunto cualquiera; variable aleatoria real cuando $E = \R$ ). Su ley (o distribución) es la medida de probabilidad $\P_X$ sobre el conjunto numerable $X(\Omega)$ definida 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$ . La indicatriz de un suceso.
Binomial $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ , $0 \leq k \leq n$ : el número de éxitos en $n$ ensayos de Bernoulli independientes (volumen de secundaria; se vuelve a demostrar más abajo mediante sumas de variables independientes).
Geométrica $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : el rango del primer éxito (Ejemplo 21.5).
Poisson $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ ; una medida de probabilidad por la serie exponencial. La ley de los sucesos raros (Capítulo 23).

Observación 22.3 (Qué modela cada ley)

Las cuatro leyes responden a cuatro preguntas primitivas: la de Bernoulli, “¿ocurrió?”; la binomial, “¿cuántas veces en $n$ intentos?”; la geométrica, “¿cuánto hasta la primera vez?”; y la de Poisson, “¿cuántos sucesos a una tasa dada, cuando los intentos son muchos e individualmente improbables?”. Reconocer la pregunta es nueve décimas partes de la modelización: las sumas de indicatrices apuntan a la binomial, los tiempos de espera a la geométrica y los recuentos de sucesos raros a la de Poisson, con el paso de la binomial a la de Poisson precisado por la ley de los sucesos raros en el Capítulo 23.

Proposición 22.4 (Ausencia de memoria de la ley geométrica)

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

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

y las leyes geométricas son las únicas leyes sobre $\N^*$ con esta propiedad.

Demostración. Sumando los pesos geométricos, $\P(X > n) = (1-p)^n$ . De ahí,

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

Recíprocamente, si $G(n) = \P(X > n)$ cumple $G(m + n) = G(m)G(n)$ con $G(0) = 1$ , entonces $G(n) = G(1)^n$ por inducción; con $q = G(1) \in \intco{0}{1}$ , o bien $q = 0$ , o bien la ley es $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Ejemplo 22.5 (Ningún número está nunca “a punto de salir”)

Lánzase un dado esperando un seis: el tiempo de espera es $X \sim \mathcal G(1/6)$ . La ausencia de memoria dice que, tras $10$ tiradas infructuosas, la espera restante $X - 10$ , dado $X > 10$ , es de nuevo $\mathcal G(1/6)$ : la espera esperada condicionada sigue siendo de $6$ tiradas, exactamente como al principio. El dado no recuerda, y ningún seis está nunca “a punto de salir”; la falacia del jugador es la creencia de que la ley condicionada debería haberse desplazado. Recíprocamente, la mitad de unicidad de la proposición dice que esa indiferencia caracteriza los tiempos de espera geométricos: todo tiempo de espera cuya previsión nunca se actualiza es geométrico. Las colas y los tiempos de vida reales sí suelen actualizarse, que es precisamente cómo se detecta que no son geométricos.

22.2 Esperanza

Definición 22.6 (Esperanza)

Una variable aleatoria real $X$ sobre $(\Omega, \P)$ tiene esperanza si la familia $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ es sumable (Capítulo 7); y su esperanza es entonces

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

Teorema 22.7 (Teorema de transferencia)

$X$ tiene esperanza si y solo si la familia $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ es sumable, y entonces

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

Más en general, para $f \colon X(\Omega) \to \R$ , la variable $f(X)$ tiene esperanza si y solo si $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , y entonces $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Demostración. Pártase $\Omega$ en los conjuntos de nivel $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . Por el teorema de sumación por paquetes para familias sumables (Capítulo 7), la familia $(X(\omega)\P(\{\omega\}))_\omega$ es sumable si y solo si lo es cada paquete (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 entonces las sumas totales coinciden. Para $f(X)$ : aplíquese el enunciado ya demostrado a la variable $Y = f \circ X$ , cuyos conjuntos de nivel son $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ; una segunda sumación por paquetes convierte $\sum_y y\,\P(Y = y)$ en $\sum_x f(x)\,\P(X = x)$ , agrupando ahora los paquetes los valores $x$ según su imagen $f(x)$ , con la sumabilidad absoluta de una familia equivalente a la de la otra. ∎

Teorema 22.8 (Propiedades de la esperanza)

Sobre el conjunto de las variables aleatorias con esperanza:

(Linealidad) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positividad y monotonía) $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$ tiene esperanza, entonces $X$ también.

Demostración. Todas son propiedades de las sumas de familias sumables (Capítulo 7): la linealidad de la suma, la positividad término a término y el criterio de dominación para la sumabilidad. (Nótese que la linealidad es inmediata sobre la definición como suma sobre $\Omega$ , mientras que resultaría incómoda sobre la fórmula de transferencia; una ventaja de definir $\E$ aguas arriba.) ∎

Ejemplo 22.9

$X \sim \mathcal{B}(n, p)$ : escribiendo $X = X_1 + \dots + X_n$ como suma de indicatrices de Bernoulli y usando la linealidad, $\E(X) = np$ ; sin necesidad de 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$ , derivando 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 (La transferencia en acción)

Para $X \sim \mathcal P(\lambda)$ , calculemos $\E\bigl(\frac1{1+X}\bigr)$ ; la ley de $\frac1{1+X}$ es incómoda, pero la transferencia no la pide nunca:

\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. En lo computacional: reconocer una serie exponencial desplazada es todo el trabajo; la transferencia reduce las esperanzas de $f(X)$ a manipulación de series. En lo estructural: el valor ingenuo de sustituir 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}$ . Las esperanzas de imágenes convexas quedan por encima del valor ingenuo de sustituir, y la transferencia más una comprobación con series hace concreta la desigualdad abstracta.

Teorema 22.11 (Independencia y productos)

Dos variables aleatorias $X, Y$ son independientes si $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ para todos $x, y$ ; equivalentemente, si los sucesos $\{X \in A\}$ y $\{Y \in B\}$ son independientes para todos $A, B$ . Si $X$ e $Y$ son variables reales independientes con esperanza, entonces $XY$ tiene esperanza y

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

Demostración. La equivalencia de las dos formulaciones se sigue sumando la identidad puntual sobre $(x, y) \in A \times B$ ( $\sigma$ -aditividad dos veces). Para el producto: la familia doble $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ es sumable, pues 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 ;

y por la independencia, esta familia es exactamente $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , cuya suma es $\E(XY)$ por transferencia aplicada a la variable $(X, Y) \mapsto xy$ ; Fubini evalúa de nuevo la suma sin signos como el producto $\E(X)\E(Y)$ . ∎

Ejemplo 22.12 (Productos, con y sin independencia)

Lánzense dos dados equilibrados. Si $Y$ es el segundo dado (independiente del 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 :

las mismas leyes marginales en ambos escenarios, leyes conjuntas distintas y esperanzas del producto distintas. La moraleja, digna de grabarse: $\E(XY)$ es un funcional del par, no de las dos marginales; y la diferencia $\E(X^2) - \E(X)^2 \approx 2.92$ es, por König–Huygens, precisamente la varianza $\frac{35}{12}$ del dado.

22.3 Varianza, covarianza y las desigualdades clásicas

Definición 22.13 (Momentos, varianza)

$X$ tiene momento de orden 2 si $X^2$ tiene esperanza (entonces $X$ también, por dominación: $\abs X \leq \frac{1 + X^2}{2}$ ). Su varianza y su desviación típica 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 de König–Huygens— desarrollando el cuadrado y usando la 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 ,

donde el término central usa que $\E X$ es una constante). Para $X, Y$ con momentos de orden dos, la covarianza es

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

Teorema 22.14 (Caja de herramientas de la varianza)

Para variables con momentos de orden dos:

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

$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 independientes, $\operatorname{Cov}(X, Y) = 0$ (el recíproco es falso), de modo que las varianzas de variables independientes se suman.

Demostración. 1 y 2 son desarrollos de cuadrados más linealidad; los productos $X_iX_j$ tienen esperanza por Cauchy–Schwarz más abajo (o por $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 es el Teorema 22.11 aplicado a las variables centradas. Un contraejemplo estándar del recíproco: $X$ uniforme sobre $\{-1, 0, 1\}$ e $Y = X^2$ están incorreladas ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ), pero son claramente dependientes. ∎

Teorema 22.15 (Desigualdades de Markov y de Chebyshev)

(Markov) Si $X \geq 0$ tiene esperanza, entonces, para todo $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Chebyshev) Si $X$ tiene momento de orden dos, entonces, para todo $\varepsilon > 0$ :

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

Demostración. 1. Punto a punto, $a\,\mathbf{1}_{X \geq a} \leq X$ (sobre el suceso, el miembro izquierdo es $a \leq X$ ; fuera de él, $0 \leq X$ ). Tómense esperanzas: $a\,\P(X \geq a) \leq \E(X)$ por monotonía y $\E(\mathbf{1}_A) = \P(A)$ . 2. Aplíquese Markov a la variable no negativa $(X - \E X)^2$ al nivel $a = \varepsilon^2$ : el suceso $\{(X - \E X)^2 \geq \varepsilon^2\}$ es exactamente $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Ejemplo 22.16 (Incorreladas pero pegadas la una a la otra)

Lánzense dos dados equilibrados, $X$ e $Y$ independientes, y póngase $S = X + Y$ , $D = X - Y$ . Por la bilinealidad de la 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 están incorreladas. ¿Independientes? Desde luego que no: $S = 12$ fuerza $D = 0$ , mientras que $\P(D = 0) = \frac16$ incondicionalmente. La correlación solo pone a prueba la parte lineal de una dependencia; aquí, la dependencia la lleva la restricción de que $S$ y $D$ tengan la misma paridad, invisible para la covarianza. (Para este par, la covarianza nula necesitaba $V(X) = V(Y)$ : fueron las distribuciones idénticas, y no la independencia, las que hicieron el trabajo.)

Ejemplo 22.17 (Cuándo es exacta la de Markov)

La desigualdad de Markov es una igualdad precisamente cuando no se desperdicia nada en la cota $a\,\mathbf 1_{X\geq a} \leq X$ : la variable ha de tomar solo los valores $0$ y $a$ . En concreto, 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 cuya riqueza media es $100$ y donde la riqueza es $0$ o $10^6$ , la proporción de millonarios es exactamente $10^{-4}$ ; la cota de Markov, alcanzada exactamente por una desigualdad maximal. Siempre que $X$ se reparta por valores intermedios, la cota es estricta, a menudo desaforadamente; pero, como muestra el caso extremo, de la sola media no puede extraerse ninguna desigualdad mejor.

Ejemplo 22.18 (Chebyshev es óptima, sin hipótesis adicionales)

Fíjense $\varepsilon > 0$ y $q \in \intoc01$ , y sea $X$ la variable que toma los valores $\pm\varepsilon$ con probabilidad $\frac q2$ cada uno y $0$ con probabilidad $1 - q$ . Entonces $\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. Así pues, la desigualdad no puede mejorarse usando solo la varianza; el decaimiento $1/\varepsilon^2$ es el precio exacto de la información de segundo momento. Un decaimiento más rápido exige hipótesis más fuertes: la acotación de la variable compra concentración exponencial, como anticipa el Ejercicio 22.7 y desarrolla sistemáticamente el problema de fin de semana de este capítulo.

Teorema 22.19 (Cauchy–Schwarz y Jensen)

(Cauchy–Schwarz) Si $X, Y$ tienen momentos de orden dos, $XY$ tiene esperanza 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 convexa sobre un intervalo que contiene $X(\Omega)$ , y $X$ y $\varphi(X)$ tienen esperanza, 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$ . La aplicación $(X, Y) \mapsto \E(XY)$ es una forma bilineal simétrica positiva sobre el espacio de las variables con momento de orden dos, así que se aplica la desigualdad de Cauchy–Schwarz abstracta del Capítulo 12 (para la desigualdad basta con que sea semidefinida positiva). Aplicándola a las variables centradas se obtiene la cota de la covarianza.

2. Primero, $m = \E(X)$ está en $I$ : $I$ es un intervalo que contiene todos los valores de $X$ , y la esperanza es monótona, de modo que $m$ está entre $\inf X(\Omega)$ y $\sup X(\Omega)$ . Por el teorema de la recta de apoyo para funciones convexas (Capítulo 8), hay $\alpha, \beta$ con $\varphi(t) \geq \alpha t + \beta$ para todo $t \in I$ y $\varphi(m) = \alpha m + \beta$ . Entonces, punto a punto sobre $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; tomando esperanzas,

\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)$ : la positividad de la varianza; y con $\varphi(t) = 1/t$ sobre $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ ; la media armónica está por debajo de la aritmética, ahora en forma aleatoria.

Observación 22.21 (Errores frecuentes)

(i) $\E(XY) = \E(X)\E(Y)$ exige independencia (o, al menos, covarianza nula): tomando $Y = X$ resulta $\E(X^2) \neq \E(X)^2$ siempre que $V(X) > 0$ . (ii) Igualmente, $V(X + X) = 4V(X)$ , y no $2V(X)$ : las varianzas solo se suman entre sumandos independientes (o incorrelados). (iii) $\E(f(X))$ no es $f(\E(X))$ ; para $f$ convexa, Jensen dice incluso en qué dirección va el error, como en el Ejemplo 22.10. (iv) La existencia es una hipótesis real: para la variable de 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 finita casi seguramente y, sin embargo, no tiene esperanza, y no existe ningún precio de entrada justo para el juego. La sumabilidad en la definición de $\E$ no es pedantería contable: es donde se detectan las colas pesadas. (v) Por último, el teorema de transferencia necesita la sumabilidad absoluta antes de que sea legítimo reordenar la suma sobre los valores (Capítulo 7).

Ejemplo 22.22 (Chebyshev sobre cien lanzamientos)

Para $X \sim \mathcal B(100, \frac12)$ : $\E X = 50$ y $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 $31\,\%$ garantizado queda lejos de la verdad, pero solo necesitó la media y la varianza; el mismo certificado se aplica palabra por palabra a cualquier variable con $\E = 50$ y $V = 25$ , por exótica que sea, y el Ejemplo 22.18 muestra que alguna variable así lo satura. La universalidad tiene un precio; cuando la distribución es genuinamente binomial, las herramientas exponenciales del problema de fin de semana cierran casi toda la brecha.

Ejemplo 22.23 (La correlación de una parte con su todo)

Para $X, Y$ independientes e idénticamente distribuidas con varianza $\sigma^2 > 0$ , ¿cuán correlacionado está un sumando con la suma $S = X + Y$ ? Calculemos

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

de modo que 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 ,

sea cual sea la ley común: dados, monedas, recuentos de Poisson. Con $n$ sumandos, el mismo cálculo da $\rho(X_1, S_n) = 1/\sqrt n$ : la influencia de cada término individual sobre el total se diluye como una raíz cuadrada, que es la sombra correlacional de la escala $\sqrt n$ de las fluctuaciones. Cauchy–Schwarz garantiza $\abs\rho \leq 1$ siempre; aquí la cota se alcanza exactamente en el caso degenerado $n = 1$ y decae de manera previsible después.

Ejemplo 22.24 (La desigualdad de las medias ponderada, desde Jensen)

Sea $Y$ la variable que toma los valores positivos $a_1, \dots, a_k$ con probabilidades $\lambda_1, \dots, \lambda_k$ . La función $-\ln$ es convexa sobre $\intoo0\infty$ , de modo 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 desigualdad aritmético-geométrica ponderada, con igualdad si y solo si $Y$ es constante. Con pesos iguales $\lambda_i = \frac1k$ se recupera la desigualdad de las medias clásica. La probabilidad ha demostrado calladamente un teorema puramente algebraico: elegir una ley de probabilidad no es más que un instrumento contable para combinaciones convexas; el punto de vista baricéntrico del Capítulo 17 una vez más, ahora con Jensen de motor.

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

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

Sean $(X_k)_{k \geq 1}$ variables aleatorias independientes dos a dos con la misma ley y con momento de orden dos; escríbanse $m = \E(X_1)$ y $S_n = X_1 + \dots + X_n$ . Entonces, para todo $\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 el Teorema 22.14 (la independencia dos a dos mata las covarianzas), $V(S_n) = n\,V(X_1)$ , de modo que $V(S_n/n) = V(X_1)/n$ . La desigualdad de Chebyshev aplicada a $S_n/n$ da la cota. ∎

Observación 22.26

Este es el teorema que conecta la probabilidad con la frecuencia: para $X_k$ la indicatriz de un suceso $A$ en repeticiones independientes, $S_n/n$ es la frecuencia observada de $A$ , y la ley de los grandes números dice que se concentra en torno a $\P(A)$ a un ritmo $\frac{p(1-p)}{n\varepsilon^2}$ . La ley fuerte ( $S_n/n \to m$ casi seguramente) es un teorema del tercer año; su demostración con momentos de orden cuatro sí está al alcance, no obstante: véase el Ejercicio 22.9, que ejecuta Borel–Cantelli sobre la cota de tipo Chebyshev. La misma estimación de Chebyshev impulsó la demostración con polinomios de Bernstein del teorema de aproximación de Weierstrass del Capítulo 10: el lema de conteo de allí era la ley débil de los grandes números disfrazada.

Ejemplo 22.27 (Coleccionar cincuenta cromos)

El coleccionista de cromos del Ejercicio 22.3 con $n = 50$ juguetes distintos: el total esperado es

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

cajas; cuatro veces y media la conjetura ingenua $50$ . El crecimiento armónico es toda la historia: los primeros $25$ juguetes llegan en unas $50\ln2 \approx 35$ cajas, mientras que el último juguete cuesta él solo $50$ cajas de media (una espera geométrica de parámetro $\frac1{50}$ ). Los problemas de compleción están dominados por su final de partida, y por eso el Ejercicio 22.12 encuentra fluctuaciones de orden $n$ —el tamaño de esa última espera geométrica— en torno a la media $n\ln n$ .

Ejemplo 22.28 (¿Cuán grande ha de ser $n$ ?)

Para fijar la frecuencia observada a menos de $\varepsilon = 0.01$ de $\P(A)$ con una confianza del $95\,\%$ , la cota de Chebyshev exige

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

La dependencia es brutal en $\varepsilon$ (cuadrática) y suave en la confianza (lineal en $1/\alpha$ ). Ambos rasgos son propiedades de la cota, no de la verdad: las desigualdades exponenciales del problema de fin de semana rebajan el precio de la confianza de $1/\alpha$ a $\ln(1/\alpha)$ —la misma especificación costará allí unas $18\,500$ muestras—, mientras que la escala $1/\varepsilon^2$ es genuina e inmejorable. Saber qué parte de una cota está floja es tan útil como la cota misma.

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

Observación 22.29 (Perspectivas dentro de este volumen)

Hacia delante, todo lo de aquí alimenta el Capítulo 23: la esperanza $\E(t^X)$ de una astuta función de $X$ empaqueta toda la ley en una serie de potencias, los momentos se convierten en derivadas en $1$ , y las identidades de tipo Wald para sumas aleatorias sostienen la teoría de los procesos de ramificación; el teorema del producto para variables independientes se convierte en la multiplicatividad de las funciones generatrices. Hacia atrás, la esperanza es un baricentro con pesos de probabilidad (Capítulo 17), la desigualdad de Jensen es la geometría de las rectas de apoyo de las funciones convexas (Capítulo 8), y el método de los momentos exponenciales del problema de fin de semana de este capítulo es Markov aplicado a $\eu^{tX}$ : una desigualdad, mejorada por un buen cambio de variable, abarcando tres capítulos.

22.5 Ejercicios

Ejercicio 22.1 ★

Calcula $\E(X)$ y $V(X)$ para $X \sim \mathcal{B}(n, p)$ (mediante indicatrices), para $X \sim \mathcal{P}(\lambda)$ (prueba que $V(X) = \lambda$ ) y para $X \sim \mathcal{G}(p)$ (prueba que $V(X) = \frac{1-p}{p^2}$ ; usa $\E(X(X-1))$ y la derivada segunda de la serie geométrica).

Solución

Solución de Ejercicio 22.1.

Binomial: $X = \sum_{i=1}^n X_i$ con $X_i$ de Bernoulli independientes; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , y las varianzas de variables independientes se suman (Teorema 22.14):

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

Poisson: $\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$ , luego

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

Geométrica ( $q = 1 - p$ ): derivando $\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}$ , de modo que

\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)$ e $Y \sim \mathcal{P}(\mu)$ independientes. Prueba que $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolución de los pesos; teorema del binomio), y que la ley condicionada de $X$ dado $X + Y = n$ es la binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

Solución

Solución de Ejercicio 22.2.

Suma: para $n \in \N$ , por disjunción e 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)$ . Ley condicionada: 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} ,

la ley binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : dado el recuento total, cada suceso “elige” de manera independiente la primera fuente con probabilidad proporcional a su tasa.

Ejercicio 22.3 ★

(Coleccionista de cromos, esperanza) Una marca de cereales esconde uno de $n$ juguetes distintos, uniformemente, en cada caja. Sea $T_n$ el número de cajas necesarias para reunir los $n$ juguetes. Escribiendo $T_n$ como suma de variables geométricas independientes (el tiempo hasta ver un juguete nuevo cuando aún faltan $k$ ), prueba que

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

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

Solución

Solución de Ejercicio 22.3.

Cuando aún faltan $k$ juguetes, cada caja nueva trae uno nuevo con probabilidad $\frac kn$ , independientemente del pasado: el tiempo de espera $W_k$ hasta el siguiente 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$ (la primera caja siempre da un juguete nuevo: $W_n = 1$ , coherente 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). Lo caro es reunir los últimos juguetes: la mitad de las cajas se va en el puñado final.

Ejercicio 22.4 ★★

Sea $X \geq 0$ con valores enteros. Demuestra la fórmula de la cola

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

(cuando alguno de los dos miembros es finito), escribiendo $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ e intercambiando las sumaciones (Fubini para familias no negativas). Recupera $\E(X) = \frac1p$ para la ley geométrica.

Solución

Solución de Ejercicio 22.4.

Punto a punto, $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . La familia doble $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ es no negativa, así que Fubini para familias (Capítulo 7) se aplica incondicionalmente: sumando primero en $n$ se obtiene $\E(X)$ , y sumando primero en $\omega$ , $\sum_n \P(X \geq n)$ ; ambas son simultáneamente finitas e iguales. Para $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), luego $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Ejercicio 22.5 ★★

(El muestreo sin reemplazamiento está más concentrado) Una urna contiene $N$ bolas, $M$ de ellas blancas. Extráiganse $n \leq N$ sin reemplazamiento y sea $X$ el número de blancas (ley hipergeométrica). Usando indicatrices $X = \sum_{i=1}^n Y_i$ con $Y_i$ la $i$ -ésima extracción: prueba que cada $Y_i$ es de Bernoulli de parámetro $p = M/N$ (¡simetría!), concluye que $\E(X) = np$ exactamente igual que con reemplazamiento, y prueba que $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ para $i \neq j$ , de donde $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 de la urna elegida uniformemente al azar (cualquiera de las $N$ bolas tiene la misma probabilidad de caer en la posición $i$ del orden de extracción), de modo que $\P(Y_i = 1) = \frac MN = p$ y $\E(X) = np$ por linealidad; sin necesitar independencia.

Covarianza: para $i \neq j$ , $\E(Y_iY_j) = \P(\text{las extracciones } i, j \text{ son ambas blancas}) = \frac{M(M-1)}{N(N-1)}$ (a pares ordenados de posiciones distintas les corresponde un par ordenado de bolas distintas, uniformemente). De ahí,

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

extraer una bola blanca hace las blancas más escasas para las demás extracciones. Por el 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 reemplazamiento tiene la misma media pero menor varianza que con reemplazamiento (con igualdad solo para $n = 1$ ), actuando las correlaciones negativas como estabilizador. Para $n = N$ la varianza se anula: el recuento es entonces determinista.

Ejercicio 22.6 ★★

Sea $X$ con momento de orden dos. Prueba que $c \mapsto \E\bigl((X - c)^2\bigr)$ es mínima exactamente en $c = \E(X)$ , con mínimo $V(X)$ . Prueba después que $\P(X = \E(X)) = 1$ si y solo si $V(X) = 0$ . (Para el segundo punto: si $V(X) = 0$ , usa Chebyshev con $\varepsilon = 1/n$ y la continuidad monótona, Teorema 21.6.)

Solución

Solución de Ejercicio 22.6.

Desarrollando en torno a $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ínima exactamente en $c = m$ y con valor $V(X)$ ; la esperanza es el mejor predictor constante en media cuadrática.

Si $\P(X = m) = 1$ , entonces $(X - m)^2$ se anula con probabilidad $1$ , luego $V(X) = 0$ (la familia que la define tiene términos nulos salvo sobre un conjunto nulo). Recíprocamente, si $V(X) = 0$ , Chebyshev (Teorema 22.15) da $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ para todo $n$ ; los sucesos $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ crecen hacia $\{X \neq m\}$ , de modo que la continuidad monótona (Teorema 21.6) da $\P(X \neq m) = 0$ .

Ejercicio 22.7 ★★★

(La concentración gana a Markov) Sea $S_n \sim \mathcal{B}(n, \frac12)$ (número de caras en $n$ lanzamientos equilibrados). Compara las cotas que dan Markov (para $\P(S_n \geq \frac{3n}{4})$ ), Chebyshev y el método exponencial (de 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 optimiza en $t$ para obtener una cota exponencialmente pequeña. (En $t = \ln 3$ : cota $\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$ : una cota constante, inútil para $n$ grande. Chebyshev: el suceso implica $\abs{S_n - \frac n2} \geq \frac n4$ , luego la probabilidad es $\leq \frac{n/4}{(n/4)^2} = \frac4n$ : decae, pero solo polinómicamente. 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, para todo $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).

Minimícese 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$ , lo que da

\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 Markov a una función de la variable que crece más deprisa.

Ejercicio 22.8 ★★★

(Weierstrass otra vez, probabilísticamente) Sean $f \colon [0,1] \to \R$ continua y $S_n \sim \mathcal{B}(n, x)$ . Prueba 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}$ vale $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ , y vuelve a deducir la estimación $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ del Capítulo 10 en este lenguaje probabilista (pártase según $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ y úsese Chebyshev).

Solución

Solución de Ejercicio 22.8.

Por el teorema de 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) .

Fíjese $\delta > 0$ y pártase $\abs{f(S_n/n) - f(x)}$ según el suceso $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : fuera de $D$ , la diferencia es a lo sumo el módulo de continuidad $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; y sobre $D$ , a lo sumo $2\norm f_\infty$ . Tomando esperanzas 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} .

La continuidad uniforme de $f$ sobre $[0, 1]$ hace $\omega_f(\delta) \to 0$ : elíjase $\delta$ y después $n$ , y $B_nf \to f$ uniformemente; el teorema de aproximación de Weierstrass del Capítulo 10, cuyo “lema de conteo” es ahora reconocible como la desigualdad de Chebyshev para la ley binomial.

Ejercicio 22.9 ★★★

(Ley fuerte con momentos de orden cuatro) Sean $(X_k)$ independientes, idénticamente distribuidas y centradas ( $\E X_1 = 0$ ), con $\E(X_1^4) < \infty$ . Desarrollando $\E(S_n^4)$ y contando los términos que sobreviven (solo los de $\E(X_i^4)$ y $\E(X_i^2X_j^2)$ , con $i \neq j$ ), prueba que $\E(S_n^4) \leq C n^2$ para una constante $C$ . Deduce que $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ para cada $\varepsilon > 0$ (Markov de orden 4) y concluye con Borel–Cantelli (Teorema 21.25) que $S_n/n \to 0$ casi seguramente, en la formulación adecuada: el suceso $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ tiene probabilidad $1$ .

Solución

Solución de Ejercicio 22.9.

Desarróllese $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ y tómense esperanzas. Por la independencia y el centrado, todo término que contenga un índice que aparezca exactamente una vez se anula ( $\E(X_i) = 0$ sale factor). Términos supervivientes: los $n$ diagonales $\E(X_i^4)$ y los que emparejan dos parejas de índices iguales, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ para $i \neq j$ , que aparecen $3n(n-1)$ veces: elíjase la pareja no ordenada de valores ( $\binom n2$ maneras) y después las $\frac{4!}{2!\,2!} = 6$ maneras de colocarlos en las cuatro ranuras: $6\binom n2 = 3n(n-1)$ . Por 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 de 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), para cada $j$ el suceso $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ tiene probabilidad $0$ , luego $\P\bigl(\bigcup_j B_j\bigr) = 0$ por subaditividad numerable. Sobre el complementario —de probabilidad $1$ — para todo $j$ hay un $N$ con $\abs{S_n/n} < \frac1j$ para todo $n \geq N$ : precisamente $S_n/n \to 0$ . La ley fuerte de los grandes números vale con momento de orden cuatro; suprimir esa hipótesis (el teorema de Kolmogórov) es tarea del tercer año.

Ejercicio 22.10 ★

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

\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 a lo sumo $k$ , independientemente), de modo 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 ,

holgadamente por encima de la media $3.5$ de un solo dado, como debe ser en un máximo.

Ejercicio 22.11 ★★

Sea $F_n$ el número de puntos fijos de una permutación uniformemente aleatoria 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 concluye que $V(F_n) = 1$ : de media queda una letra fija, con varianza exactamente $1$ , sea cual 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$ , luego $\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)}$ , de donde

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

Por la caja de herramientas de la varianza (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$ , varianza $1$ , independientes de $n$ ; coherente con el límite de Poisson del problema de los emparejamientos (Ejercicio 21.5).

Ejercicio 22.12 ★★★

(Coleccionista de cromos, concentración) En el marco del Ejercicio 22.3, prueba que

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,

usando la 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 el Ejemplo 14.12). Deduce con Chebyshev que $\dfrac{T_n}{n\ln n} \to 1$ en probabilidad: el tiempo total del coleccionista es $n\ln n$ salvo 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 tiempo hasta ver un juguete nuevo cuando faltan $k$ , siendo las etapas independientes. De ahí,

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 el Ejemplo 14.12. Con $\E(T_n) = nH_n$ y $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 .

Como $H_n \sim \ln n$ , dividiendo entre $n\ln n$ se ve que $T_n/(n\ln n) \to 1$ en probabilidad: las fluctuaciones de $T_n$ son de orden $n$ , despreciables frente a la media $n\ln n$ .

22.6 Problema: la caja de herramientas de la concentración, de Markov a Hoeffding

Problema 22.1

Problema de fin de semana — concentración exponencial a mano, y a cuánta gente ha de preguntar una encuesta

La desigualdad de Markov cuesta un momento y compra un decaimiento $1/a$ ; Chebyshev cuesta dos momentos y compra $1/\varepsilon^2$ ; y el Ejemplo 22.18 muestra que eso es todo lo que esos momentos pueden comprar. Este problema sube el resto de la escalera: el método exponencial (de Chernoff) con su ritmo exacto para lanzamientos de moneda, la desigualdad de Hoeffding para todas las variables acotadas, y la recompensa: tamaños de muestra explícitos y honestos para encuestas, adjudicaciones electorales y contraste de monedas. En todo el problema, $S_n \sim \mathcal B(n, p)$ es una suma de $n$ variables de Bernoulli independientes y $\widehat p_n = S_n/n$ la frecuencia empírica.

Parte I — Calibración sobre la moneda equilibrada. Aquí $p = \frac12$ y $a \in \intoo{\frac12}{1}$ .

Markov al nivel $an$ : prueba que $\P(S_n \geq an) \leq \frac1{2a}$ , una cota que ni siquiera tiende a $0$ . ¿Dónde pierde tanto Markov?
Chebyshev: usando la simetría de la binomial equilibrada respecto de $n/2$ , prueba que

$\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$ : por fin, decaimiento polinómico.
(Chernoff, nivel general) Calcula $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ y optimiza $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ en $t > 0$ : prueba que el $t$ óptimo es $\ln\frac{a}{1-a}$ y que

$\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 la cota $\bigl(2\cdot3^{-3/4}\bigr)^n$ del Ejercicio 22.7.
(El exponente es exacto) Sea $k = an$ un entero. A partir de que $\binom nk a^k(1-a)^{n-k}$ es el mayor de los $n + 1$ términos de una distribución de probabilidad, demuestra que $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ con $H(a) = -a\ln a - (1-a)\ln(1-a)$ , y deduce la cota inferior correspondiente

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Tabula las tres cotas en $n = 100$ , $a = \frac34$ : Markov $\frac23$ , Chebyshev $0.02$ , Chernoff $\approx 2.1\cdot10^{-6}$ (el valor verdadero es $\approx 2.8\cdot10^{-7}$ ). ¿La moraleja, en una frase?

Parte II — La desigualdad de Hoeffding.

(Caso de Rademacher) Para $\varepsilon = \pm1$ con probabilidad $\frac12$ cada uno, demuestra que

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

comparando las dos series término a término ( $(2k)! \geq 2^kk!$ ).
Deduce, para variables de Rademacher independientes $\varepsilon_1, \dots, \varepsilon_n$ y todo $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Tradúcelo a monedas equilibradas ( $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 bilateral con un factor $2$ .
(Lema de Hoeffding) Sea $X \in \intcc01$ con $\E X = p$ , y $\psi(t) = \ln\E(\eu^{tX})$ . Justifica que $\psi$ es dos veces diferenciable con

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

una varianza de una variable reponderada que sigue tomando valores en $\intcc01$ ; acótala por $\frac14$ (el argumento de minimalidad del Ejercicio 22.6) y concluye por Taylor:

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

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Compara el ritmo de Chebyshev $\frac{p(1-p)}{n\delta^2}$ con el $2\eu^{-2n\delta^2}$ de Hoeffding: ¿qué hipótesis exige cada uno, y a partir de qué $n$ (aproximadamente) gana la cota exponencial en $\delta = 0.03$ , $p = \frac12$ ?

Parte III — ¿A cuánta gente ha de preguntar una encuesta? Una encuesta pregunta a $n$ votantes elegidos uniformemente y de manera independiente; cada uno responde con sinceridad; $p$ es el resultado verdadero y $\widehat p_n$ la cifra de la encuesta.

Prueba que la encuesta es precisa hasta $\pm\delta$ con confianza $1 - \alpha$ (es decir, $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) en cuanto

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Calcula el $n$ necesario para la especificación estándar de “tres puntos, noventa y cinco por ciento” ( $\delta = 0.03$ , $\alpha = 0.05$ ): $n \geq 2050$ ; y para un punto: $n \geq 18\,445$ . Obsérvese —y explíquese— el hecho llamativo de que la respuesta no involucra el tamaño de la población.
Rehaz la pregunta 13 con Chebyshev ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ con tres puntos. Nótese que muestrear sin reemplazamiento solo ayuda (Ejercicio 22.5: la varianza se encoge en $\frac{N-n}{N-1}$ ).
(Adjudicar una elección) El resultado verdadero de un candidato es $p = 0.52$ . ¿A cuántos votantes hay que encuestar para que $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Prueba que $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ : adjudicar una carrera reñida cuesta mucho más que estimar un resultado.
Lo que la matemática no cubre: enumera las hipótesis de modelización usadas (muestreo uniforme independiente, respuestas sinceras, $p$ fijo) y explica en un párrafo breve por qué los errores reales de las encuestas están dominados por el sesgo (muestreo no uniforme, falta de respuesta), que ningún aumento de $n$ reduce.

Parte IV — Más afiladas y más baratas.

(Mediana de medias: decaimiento exponencial a partir de dos momentos) Repártase un presupuesto de $km$ muestras en $k$ grupos independientes de $m$ ; sean $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ las medias de los grupos y $M$ su mediana. Elíjase $m$ de modo que cada grupo cumpla $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (Chebyshev: basta $m \geq \frac2{\delta^2}$ ). Prueba que si $\abs{M - p} \geq \delta$ , entonces al menos $k/2$ grupos yerran, y deduce que

$\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 usando nada más allá de las varianzas.
(Paley–Zygmund) Para $X \geq 0$ con momento de orden dos, demuestra que $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz sobre $X\mathbf 1_{X>0}$ ): la herramienta en sentido inverso; los momentos también pueden forzar a los sucesos a ocurrir.
(Pinsker en versión ligera) Prueba que $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ sobre $\intoo{\frac12}1$ (la diferencia se anula hasta el segundo orden en $\frac12$ y su derivada segunda es $\frac1{a(1-a)} - 4 \geq 0$ ): el exponente exacto de Chernoff siempre gana al cuadrático de Hoeffding.
Desarrolla $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ y combínalo con la pregunta 4: para desviaciones pequeñas, el exponente $2n\delta^2$ de Hoeffding es asintóticamente exacto; ningún método puede mejorarlo en más que factores polinómicos.
Redacta la tabla de la caja de herramientas: para Markov, Chebyshev, la cota de cuarto momento del Ejercicio 22.9, Hoeffding y Chernoff con exponente $I$ , indica en una línea cada uno: hipótesis requerida, decaimiento obtenido y la pregunta de este problema donde resultó más afilado.

Parte V — Dividendos.

(Contrastar una moneda) Una moneda es equilibrada o está sesgada con $p = 0.55$ . Se lanza $n$ veces y se declara “sesgada” cuando $\widehat p_n > 0.525$ . Prueba que ambas probabilidades de error son a lo sumo $\eu^{-2n(0.025)^2}$ , y que $n \geq 3685$ lanzamientos garantizan que ambas queden por debajo del $1\,\%$ .
(Los sucesos raros necesitan una cota consciente de la varianza) Sea $p = 0.01$ y tómese la especificación relativa $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . Compara los tamaños de muestra que exigen Hoeffding ( $n \approx 74\,000$ ) y Chebyshev con la varianza verdadera $p(1-p)$ ( $n \approx 7920$ ): la cota exponencial, ciega a la varianza, pierde frente al humilde momento de orden dos. Enuncia la moraleja y di de dónde vendrá la herramienta que falta (una cota exponencial consciente de la varianza; la aproximación de Poisson del Capítulo 23).
(Ley fuerte para monedas) A partir de $\sum_n 2\eu^{-2n\delta^2} < \infty$ y de Borel–Cantelli (Teorema 21.25), demuestra que $\widehat p_n \to p$ casi seguramente para lanzamientos de moneda independientes: formula el suceso casi seguro como $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ , como en el Ejercicio 22.9, y concluye. (La acotación sustituye al cuarto momento usado allí.)
Síntesis. En cinco frases: qué cuesta y qué compra cada peldaño de la escalera (momentos uno, dos y cuatro; exponencial acotada; exponente exacto); por qué encuestar a $2050$ personas basta para un país de cualquier tamaño; y cuál de estas cotas afilará el volumen del tercer año hasta las constantes exactas del teorema central del límite.

Solución

Solución de Problema 22.1.

1. $\E(S_n) = \frac n2$ y Markov (Teorema 22.15) dan $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov solo conoce la media: no puede distinguir una variable concentrada en $n/2$ de otra repartida entre $0$ y $n$ , así que tarifa la cola como si toda la masa pudiera estar allí.

2. La binomial equilibrada es simétrica respecto de $n/2$ ( $S_n$ y $n - S_n$ tienen la misma ley), de modo que, con $x = n(a - \frac12) > 0$ , los dos sucesos $\{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 vale $\frac2n$ en $a = \frac34$ .

3. Por la 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 aplicado 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$ , que se anula en $\eu^t = \frac a{1-a}$ , es decir, $t^* = \ln\frac a{1-a} > 0$ ; allí, $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ y el exponente vale

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$ e $I'(a) = \ln\frac a{1-a} > 0$ sobre $\intoo{\frac12}1$ : $I(a) > 0$ . En $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , la cota del Ejercicio 22.7.

4. Los $n + 1$ números $\binom nja^j(1-a)^{n-j}$ suman $1$ , y el mayor es el de $j = k = an$ (la moda de $\mathcal B(n, a)$ es $\floor{(n+1)a} = k$ aquí). Un máximo de $n + 1$ números 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}.

De ahí, $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : salvo 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}$ , frente al valor exacto $2.8\cdot10^{-7}$ . Moraleja: cada momento de información divide la cota polinómicamente; 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!}$ ; la afirmación se sigue término a término de $(2k)! \geq 2^kk!$ , que vale 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 la independencia, $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , de modo que Markov da $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; minimizando en $t = s/n$ resulta $\eu^{-s^2/(2n)}$ .

8. Con $X_i = \frac{1 + \varepsilon_i}2$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , luego $\{\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 suceso simétrico tiene la misma cota, 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 una serie de funciones regulares de $t$ cuyas derivadas término a término están dominadas, sobre todo intervalo compacto de $t$ , por $\eu^{\abs t}\P(X = x)$ (pues $0 \leq x \leq 1$ ): por el teorema de derivación para series normalmente convergentes (Teorema 10.7) es dos veces 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 la esperanza para los pesos reponderados $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ : no negativos, de suma $1$ y llevados por los mismos valores $x \in \intcc01$ . Una varianza de una variable con valores en $\intcc01$ es a lo sumo $\frac14$ : por el Ejercicio 22.6, vale $\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$ y $\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 todo $t$ real.

10. Por la 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};

y aplicar esto a las variables $1 - X_i$ (también en $\intcc01$ ) acota la otra cola, de donde el $2\eu^{-2n\delta^2}$ bilateral.

11. Chebyshev solo necesita un momento de orden dos y da $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding necesita la acotación y da $2\eu^{-2n\delta^2}$ . En $p = \frac12$ , $\delta = 0.03$ : las cotas son $\frac{278}{n}$ (aproximadamente) frente a $2\eu^{-0.0018n}$ ; se cruzan cerca de $n \approx 1200$ , a partir de donde gana la cota exponencial, y con creces ( $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$ en cuanto $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 no aparece nunca porque cada votante muestreado se modela como una extracción de Bernoulli $(p)$ nueva: la dificultad de la encuesta es la varianza de una moneda, no el tamaño del 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$ con tres puntos: unas $2.7$ veces lo que exige Hoeffding. Sin reemplazamiento, la varianza queda multiplicada por $\frac{N - n}{N-1} < 1$ (Ejercicio 22.5), de modo que el mismo $n$ solo puede hacerlo mejor: el cálculo con reemplazamiento es el conservador.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , así que, por la cota unilateral de Hoeffding, $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ en cuanto $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ votantes. El coste escala como el inverso del cuadrado de la ventaja, no de la precisión deseada: las carreras reñidas son caras.

16. Se usó: que la muestra se extrae uniformemente y de manera independiente del electorado; que toda persona muestreada responde, y con sinceridad; y que $p$ no se mueve durante el trabajo de campo. Las encuestas reales violan las tres: las personas localizables y dispuestas no son una muestra uniforme (sesgo de selección y de no respuesta), y las respuestas pueden ser insinceras o inestables. Son errores de sesgo: desplazan $\E(\widehat p_n)$ respecto de $p$ en una cantidad independiente de $n$ , de modo que ningún tamaño de muestra los reduce; la matemática de esta parte controla únicamente 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 yerran menos de $k/2$ grupos, entonces más de $k/2$ de los valores $\widehat p^{(i)}$ están en el intervalo abierto $\intoo{p - \delta}{p + \delta}$ , y su mediana también; de modo que $\{\abs{M - p} \geq \delta\}$ fuerza al menos $\lceil k/2\rceil$ errores entre $k$ grupos independientes. La cota de la unión sobre los $\binom k{\lceil k/2\rceil}$ conjuntos posibles de grupos que yerran da

\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} :

decaimiento exponencial en el número de grupos, comprado con nada más que varianzas; útil precisamente cuando los sumandos no están acotados y Hoeffding no está disponible.

18. Cauchy–Schwarz (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)} ;

elévese al cuadrado y divídase.

19. Sea $h(a) = I(a) - 2(a - \tfrac12)^2$ . Entonces $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ se anula en $\tfrac12$ , y

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

puesto que $a(1-a) \leq \frac14$ . Así pues, $h'$ crece desde $0$ sobre $\intco{\frac12}1$ , luego $h' \geq 0$ y $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ y $I''(a) = \frac1{a(1-a)}$ dan $I''(\tfrac12) = 4$ , y $I'''(\tfrac12) = 0$ (la función es simétrica respecto de $\tfrac12$ ), de modo que $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . La pregunta 4 acota entonces la cola verdadera por debajo mediante $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : para $\delta$ pequeño, el exponente $2n\delta^2$ de Hoeffding es asintóticamente exacto; solo son posibles mejoras polinómicas en $n$ .

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

22. Si la moneda es equilibrada: $\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 quedan por debajo de $0.01$ cuando $2n(0.025)^2 \geq \ln 100$ , es decir, $n \geq 3684.2$ : $3685$ lanzamientos. (Distinguir hipótesis separadas $2.5$ puntos cuesta lo mismo que estimar con $\pm2.5$ puntos.)

23. Hoeffding: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Chebyshev con la varianza verdadera $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ : nueve veces más barato. El exponente $2n\delta^2$ de Hoeffding tarifa la varianza en su peor caso $\frac14$ , absurdamente pesimista cuando $p = 0.01$ ; el humilde momento de orden dos sabe más. La herramienta que falta es una cota exponencial consciente de la varianza (la desigualdad de Bernstein, tercer año) o, para sucesos raros, la aproximación de Poisson demostrada en el Capítulo 23, que trabaja en la escala relativa natural.

24. Fíjese $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (una serie de tipo geométrico), de modo que Borel–Cantelli 1 (Teorema 21.25) da $\P(\abs{\widehat p_n - p} \geq \delta \text{ infinitas veces}) = 0$ ; es decir, el suceso $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ tiene probabilidad $1$ para cada $j$ . La intersección numerable $\bigcap_jE_j$ sigue teniendo probabilidad $1$ (subaditividad sobre los complementarios), y sobre ella $\widehat p_n \to p$ : la ley fuerte de los grandes números para lanzamientos de moneda, con la acotación desempeñando el papel que allí desempeñaba el cuarto momento (Ejercicio 22.9).

25. Un momento compra una cota plana; dos compran $1/(n\delta^2)$ , y no más (el ejemplo de optimalidad); cuatro compran $1/n^2$ , suficiente para telescopar en una ley casi segura; la acotación compra $\eu^{-2n\delta^2}$ ; y el momento exponencial completo compra el ritmo exacto $I$ , que ningún método supera. Encuestar a $2050$ personas basta para cualquier país porque la fluctuación de la muestra la gobierna la varianza de la moneda, no el tamaño de la población; las etiquetas de precio $1/\delta^2$ y $\ln(1/\alpha)$ son universales. El teorema central del límite del volumen del tercer año sustituye estas desigualdades, en la escala $\sqrt n$ , por una ley límite exacta con constantes explícitas, convirtiendo toda cota de este problema en una igualdad asintótica.

Términos definidos en este capítulo

Ver los 395 términos del glosario