Matemática universitária — Graduação 2 · Bachelor Year 2

22Variáveis aleatórias discretas

As variáveis aleatórias organizam os cálculos de probabilidade em torno de funções, e não de eventos. Em espaços enumeráveis a teoria é movida pelas famílias somáveis do Capítulo 7: a esperança é a soma de uma família indexada pelo espaço amostral, e todas as suas propriedades — linearidade, transferência, fórmula do produto para variáveis independentes — são teoremas sobre famílias somáveis. O capítulo demonstra as desigualdades-chave de Markov, Chebyshev, Cauchy–Schwarz e Jensen, e termina com as leis clássicas e a lei fraca dos grandes números, cuja demonstração tem duas linhas uma vez disponível Chebyshev.

22.1 Variáveis aleatórias e suas leis

Definição 22.1 (Variável aleatória discreta; lei)

Seja $(\Omega, \P)$ um espaço de probabilidade enumerável. Uma variável aleatória é uma aplicação $X \colon \Omega \to E$ ( $E$ um conjunto qualquer; variável aleatória real quando $E = \R$ ). Sua lei (ou distribuição) é a medida de probabilidade $\P_X$ no conjunto enumerável $X(\Omega)$ definida por

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

Exemplo 22.2 (As leis clássicas)

Bernoulli $\mathcal{B}(p)$ : $X \in \{0, 1\}$ , $\P(X = 1) = p$ . Indicadora de um evento.
Binomial $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ , $0 \leq k \leq n$ : número de sucessos em $n$ provas de Bernoulli independentes (volume do ensino médio; redemonstrada abaixo via somas de variáveis independentes).
Geométrica $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : posição do primeiro sucesso (Exemplo 21.5).
Poisson $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — uma medida de probabilidade pela série exponencial. A lei dos eventos raros (Capítulo 23).

Observação 22.3 (Qual lei modela o quê)

As quatro leis respondem a quatro perguntas primitivas: Bernoulli, “aconteceu?”; binomial, “quantas vezes em $n$ tentativas?”; geométrica, “quanto tempo até a primeira vez?”; Poisson, “quantos eventos a uma dada taxa, quando as tentativas são muitas e individualmente improváveis?”. Reconhecer a pergunta é nove décimos da modelagem: somas de indicadoras apontam para a binomial, tempos de espera para a geométrica, contagens de eventos raros para a Poisson — com a passagem da binomial à Poisson precisada pela lei dos eventos raros no Capítulo 23.

Proposição 22.4 (Ausência de memória da lei geométrica)

Se $X \sim \mathcal{G}(p)$ , então, para todos $m, n \in \N$ :

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

e as leis geométricas são as únicas leis em $\N^*$ com essa propriedade.

Demonstração. Somando os pesos geométricos, $\P(X > n) = (1-p)^n$ . Portanto

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

Reciprocamente, se $G(n) = \P(X > n)$ satisfaz $G(m + n) = G(m)G(n)$ com $G(0) = 1$ , então $G(n) = G(1)^n$ por indução; $q = G(1) \in \intco{0}{1}$ , e $q = 0$ ou a lei é $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Exemplo 22.5 (Nenhum número está jamais “atrasado”)

Lance um dado esperando um seis: o tempo de espera é $X \sim \mathcal G(1/6)$ . A ausência de memória diz que, após $10$ lançamentos infrutíferos, a espera restante $X - 10$ , dado $X > 10$ , é de novo $\mathcal G(1/6)$ : a espera condicional esperada continua sendo $6$ lançamentos, exatamente como no início. O dado não se lembra, e nenhum seis está jamais “atrasado” — a falácia do apostador é a crença de que a lei condicional deveria ter mudado. Reciprocamente, a metade de unicidade da proposição diz que essa indiferença caracteriza os tempos de espera geométricos: todo tempo de espera cuja previsão nunca se atualiza é geométrico. Filas e tempos de vida reais em geral se atualizam, que é precisamente como se detecta que eles não são geométricos.

22.2 Esperança

Definição 22.6 (Esperança)

Uma variável aleatória real $X$ em $(\Omega, \P)$ tem esperança se a família $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ for somável (Capítulo 7); sua esperança é então

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

Teorema 22.7 (Teorema de transferência)

$X$ tem esperança se e somente se a família $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ é somável, e então

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

Mais geralmente, para $f \colon X(\Omega) \to \R$ , a variável $f(X)$ tem esperança se e somente se $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , e então $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Demonstração. Particione $\Omega$ nos conjuntos de nível $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . Pelo teorema de soma por pacotes para famílias somáveis (Capítulo 7), a família $(X(\omega)\P(\{\omega\}))_\omega$ é somável se e somente se cada pacote o for (automático: $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) e a família das somas dos pacotes $\bigl(x\,\P(X = x)\bigr)_x$ for somável — e então as somas totais coincidem. Para $f(X)$ : aplique o enunciado já demonstrado à variável $Y = f \circ X$ , cujos conjuntos de nível são $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ; uma segunda soma por pacotes converte $\sum_y y\,\P(Y = y)$ em $\sum_x f(x)\,\P(X = x)$ , agrupando agora os pacotes os valores $x$ por sua imagem $f(x)$ , com a somabilidade absoluta de uma família equivalente à da outra. ∎

Teorema 22.8 (Propriedades da esperança)

No conjunto das variáveis aleatórias com esperança:

(Linearidade) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positividade e monotonia) $X \geq 0 \Rightarrow \E(X) \geq 0$ ; $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ; e $\abs{\E(X)} \leq \E(\abs X)$ .
(Dominação) Se $\abs X \leq Z$ e $Z$ tem esperança, então $X$ também tem.

Demonstração. Todas são propriedades de somas de famílias somáveis (Capítulo 7): linearidade da soma, positividade termo a termo e o critério de dominação para a somabilidade. (Note que a linearidade é imediata na definição sobre $\Omega$ , ao passo que seria desajeitada na fórmula de transferência — um benefício de definir $\E$ a montante.) ∎

Exemplo 22.9

$X \sim \mathcal{B}(n, p)$ : escrevendo $X = X_1 + \dots + X_n$ como soma de indicadoras de Bernoulli e usando a linearidade, $\E(X) = np$ — sem precisar de coeficientes binomiais. $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 a série geométrica dentro de seu 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$ .

Exemplo 22.10 (Transferência em ação)

Para $X \sim \mathcal P(\lambda)$ , calcule $\E\bigl(\frac1{1+X}\bigr)$ — a lei do próprio $\frac1{1+X}$ é desajeitada, mas a transferência nunca a pede:

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

Duas lições. Computacional: reconhecer uma série exponencial deslocada é todo o trabalho — a transferência reduz esperanças de $f(X)$ a manipulação de séries. Estrutural: o valor ingênuo por substituição seria $\frac1{1 + \E X} = \frac1{1 + \lambda}$ , e a resposta verdadeira é maior,

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

exatamente como exige a desigualdade de Jensen para a função convexa $t \mapsto \frac1{1+t}$ . As esperanças de imagens convexas ficam acima do valor ingênuo por substituição, e a transferência mais uma verificação de séries torna concreta a desigualdade abstrata.

Teorema 22.11 (Independência e produtos)

As variáveis aleatórias $X, Y$ são independentes se $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ para todos $x, y$ — equivalentemente, os eventos $\{X \in A\}$ e $\{Y \in B\}$ são independentes para todos $A, B$ . Se $X$ e $Y$ são variáveis reais independentes com esperanças, então $XY$ tem esperança e

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

Demonstração. A equivalência das duas formulações segue somando a identidade pontual sobre $(x, y) \in A \times B$ ( $\sigma$ -aditividade duas vezes). Para o produto: a família dupla $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ é somável, pois, por Fubini para famílias (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 ;

pela independência essa família é exatamente $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , cuja soma vale $\E(XY)$ pela transferência aplicada à variável $(X, Y) \mapsto xy$ ; Fubini de novo avalia a soma sem sinais como o produto $\E(X)\E(Y)$ . ∎

Exemplo 22.12 (Produtos, com e sem independência)

Lance dois dados honestos. Se $Y$ é o segundo dado (independente do primeiro), $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . Se, em vez disso, $Y = X$ (o “produto” de um dado consigo mesmo),

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

mesmas leis marginais nos dois cenários, leis conjuntas diferentes, esperanças de produto diferentes. A moral, digna de ser gravada: $\E(XY)$ é um funcional do par, não das duas marginais — e a diferença $\E(X^2) - \E(X)^2 \approx 2.92$ é, por König–Huygens, precisamente a variância $\frac{35}{12}$ do dado.

22.3 Variância, covariância e as desigualdades clássicas

Definição 22.13 (Momentos, variância)

$X$ tem momento de ordem 2 se $X^2$ tiver esperança (e então $X$ também tem, por dominação: $\abs X \leq \frac{1 + X^2}{2}$ ). Sua variância e seu desvio padrão são então

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

(a segunda forma — a fórmula de König–Huygens — vem de desenvolver o quadrado e usar a linearidade:

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

o termo do meio usando que $\E X$ é uma constante). Para $X, Y$ com momentos de segunda ordem, a covariância é

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

Teorema 22.14 (Ferramentas da variância)

Para variáveis com momentos de segunda ordem:

$V(aX + b) = a^2\,V(X)$ ;
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ e, mais geralmente,

$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) ;$
se $X, Y$ são independentes, $\operatorname{Cov}(X, Y) = 0$ (a recíproca é falsa), de modo que as variâncias de variáveis independentes se somam.

Demonstração. 1 e 2 são desenvolvimentos de quadrados mais linearidade; os produtos $X_iX_j$ têm esperança por Cauchy–Schwarz abaixo (ou por $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 é o Teorema 22.11 aplicado às variáveis centradas. Um contraexemplo padrão para a recíproca: $X$ uniforme em $\{-1, 0, 1\}$ e $Y = X^2$ são não correlacionadas ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) mas claramente dependentes. ∎

Teorema 22.15 (Desigualdades de Markov e de Chebyshev)

(Markov) Se $X \geq 0$ tem esperança, então, para todo $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Chebyshev) Se $X$ tem momento de segunda ordem, então, para todo $\varepsilon > 0$ :

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

Demonstração. 1. Pontualmente, $a\,\mathbf{1}_{X \geq a} \leq X$ (no evento o membro da esquerda vale $a \leq X$ ; fora dele, $0 \leq X$ ). Tome esperanças: $a\,\P(X \geq a) \leq \E(X)$ por monotonia e $\E(\mathbf{1}_A) = \P(A)$ . 2. Aplique Markov à variável não negativa $(X - \E X)^2$ no nível $a = \varepsilon^2$ : o evento $\{(X - \E X)^2 \geq \varepsilon^2\}$ é exatamente $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Exemplo 22.16 (Não correlacionadas mas grudadas uma na outra)

Lance dois dados honestos, $X$ e $Y$ independentes, e ponha $S = X + Y$ , $D = X - Y$ . Pela bilinearidade da covariância,

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

soma e diferença são não correlacionadas. Independentes? Certamente não: $S = 12$ força $D = 0$ , enquanto $\P(D = 0) = \frac16$ incondicionalmente. A correlação só testa a parte linear de uma dependência; aqui a dependência é carregada pela restrição de que $S$ e $D$ tenham a mesma paridade, invisível à covariância. (Para esse par, a covariância nula precisou de $V(X) = V(Y)$ : distribuições idênticas, e não independência, é que fizeram o trabalho.)

Exemplo 22.17 (Quando Markov é exata)

A desigualdade de Markov é uma igualdade precisamente quando nada se desperdiça na majoração $a\,\mathbf 1_{X\geq a} \leq X$ : a variável deve assumir apenas os valores $0$ e $a$ . Concretamente, se $\P(X = a) = \pi$ e $\P(X = 0) = 1 - \pi$ , então $\E(X) = a\pi$ e

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

Uma leitura realista: numa população em que a riqueza média é $100$ e a riqueza é $0$ ou $10^6$ , a proporção de milionários é exatamente $10^{-4}$ — a cota de Markov, atingida exatamente por desigualdade maximal. Sempre que $X$ se espalha por valores intermediários a cota é estrita, muitas vezes escandalosamente; mas, como mostra o caso extremo, nenhuma desigualdade melhor pode ser extraída apenas da média.

Exemplo 22.18 (Chebyshev é ótima — sem hipóteses adicionais)

Fixe $\varepsilon > 0$ , $q \in \intoc01$ , e deixe $X$ assumir os valores $\pm\varepsilon$ com probabilidade $\frac q2$ cada e $0$ com probabilidade $1 - q$ . Então $\E(X) = 0$ , $V(X) = q\varepsilon^2$ , e

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

igualdade em Chebyshev. Assim, a desigualdade não pode ser melhorada usando apenas a variância — o decaimento em $1/\varepsilon^2$ é o preço exato da informação de segundo momento. Um decaimento mais rápido exige hipóteses mais fortes: a limitação da variável compra concentração exponencial, como o Exercício 22.7 antecipa e o problema de fim de semana deste capítulo desenvolve sistematicamente.

Teorema 22.19 (Cauchy–Schwarz e Jensen)

(Cauchy–Schwarz) Se $X, Y$ têm momentos de segunda ordem, $XY$ tem esperança e $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; consequentemente, $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(Jensen) Se $\varphi \colon I \to \R$ é convexa num intervalo contendo $X(\Omega)$ e $X$ , $\varphi(X)$ têm esperança, então

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

Demonstração. 1. Somabilidade de $XY$ : $\abs{XY} \leq \frac{X^2 + Y^2}2$ . A aplicação $(X, Y) \mapsto \E(XY)$ é uma forma bilinear simétrica positiva no espaço das variáveis com momentos de segunda ordem, de modo que a desigualdade abstrata de Cauchy–Schwarz do Capítulo 12 se aplica (a positividade semidefinida basta para a desigualdade). Aplicá-la às variáveis centradas dá a cota da covariância.

2. Primeiro, $m = \E(X)$ está em $I$ : $I$ é um intervalo contendo todos os valores de $X$ , e a esperança é monótona, de modo que $m$ está entre $\inf X(\Omega)$ e $\sup X(\Omega)$ . Pelo teorema da reta de apoio para funções convexas (Capítulo 8), existem $\alpha, \beta$ com $\varphi(t) \geq \alpha t + \beta$ para todo $t \in I$ e $\varphi(m) = \alpha m + \beta$ . Então, pontualmente em $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; tomando esperanças,

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

∎

Exemplo 22.20

Jensen com $\varphi(t) = t^2$ dá $\E(X)^2 \leq \E(X^2)$ — a positividade da variância; com $\varphi(t) = 1/t$ em $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — a média harmônica está abaixo da média aritmética, agora em forma aleatória.

Observação 22.21 (Armadilhas comuns)

(i) $\E(XY) = \E(X)\E(Y)$ exige independência (ou ao menos covariância nula): tomar $Y = X$ dá $\E(X^2) \neq \E(X)^2$ sempre que $V(X) > 0$ . (ii) Do mesmo modo, $V(X + X) = 4V(X)$ , e não $2V(X)$ : as variâncias só se somam sobre parcelas independentes (ou não correlacionadas). (iii) $\E(f(X))$ não é $f(\E(X))$ ; para $f$ convexa, Jensen até informa a direção do erro, como no Exemplo 22.10. (iv) A existência é uma hipótese de verdade: para a variável de São Petersburgo $X = 2^K$ com $\P(K = k) = 2^{-k}$ ( $k \geq 1$ ),

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

$X$ é finita quase certamente e no entanto não tem esperança, e não existe preço justo de entrada para o jogo. A somabilidade na definição de $\E$ não é pedantismo contábil — é onde as caudas pesadas são detectadas. (v) Por fim, o teorema de transferência precisa da somabilidade absoluta antes que qualquer rearranjo da soma sobre os valores seja legítimo (Capítulo 7).

Exemplo 22.22 (Chebyshev em cem lançamentos)

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

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

ao passo que a soma binomial exata dá $\approx 0.73$ . Os $31\%$ garantidos estão longe da verdade, mas exigiram apenas a média e a variância — o mesmo certificado se aplica literalmente a qualquer variável com $\E = 50$ , $V = 25$ , por mais exótica que seja, e o Exemplo 22.18 mostra que alguma tal variável o satura. A universalidade tem um preço; quando a distribuição é genuinamente binomial, as ferramentas exponenciais do problema de fim de semana fecham a maior parte da lacuna.

Exemplo 22.23 (A correlação de uma parte com seu todo)

Para $X, Y$ independentes e identicamente distribuídas com variância $\sigma^2 > 0$ , quão correlacionada é uma parcela com a soma $S = X + Y$ ? Calcule

\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 o coeficiente de correlação é

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

qualquer que seja a lei comum — dados, moedas, contagens de Poisson. Com $n$ parcelas, o mesmo cálculo dá $\rho(X_1, S_n) = 1/\sqrt n$ : a influência de cada termo individual sobre o total se dilui como uma raiz quadrada, que é a sombra correlacional da escala $\sqrt n$ das flutuações. Cauchy–Schwarz garante $\abs\rho \leq 1$ sempre; aqui a cota é atingida exatamente no caso degenerado $n = 1$ e decai previsivelmente depois.

Exemplo 22.24 (MA–MG ponderada a partir de Jensen)

Seja $Y$ assumindo os valores positivos $a_1, \dots, a_k$ com probabilidades $\lambda_1, \dots, \lambda_k$ . A função $-\ln$ é convexa em $\intoo0\infty$ , de modo que Jensen dá $-\ln\E(Y) \leq \E(-\ln Y)$ , isto é,

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

a desigualdade aritmético–geométrica ponderada, com igualdade se e somente se $Y$ é constante. Pesos iguais $\lambda_i = \frac1k$ recuperam a MA–MG clássica. A probabilidade demonstrou discretamente um teorema puramente algébrico: escolher uma lei de probabilidade é apenas um dispositivo de contabilidade para combinações convexas — o ponto de vista baricêntrico do Capítulo 17 mais uma vez, agora com Jensen como motor.

22.4 A lei fraca dos grandes números

Teorema 22.25 (Lei fraca dos grandes números)

Sejam $(X_k)_{k \geq 1}$ variáveis aleatórias independentes duas a duas com a mesma lei, admitindo momento de segunda ordem; escreva $m = \E(X_1)$ e $S_n = X_1 + \dots + X_n$ . Então, 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 .

Demonstração. Por linearidade, $\E(S_n/n) = m$ ; pelo Teorema 22.14 (a independência dois a dois mata as covariâncias), $V(S_n) = n\,V(X_1)$ , logo $V(S_n/n) = V(X_1)/n$ . A desigualdade de Chebyshev aplicada a $S_n/n$ dá a cota. ∎

Observação 22.26

Esse é o teorema que conecta probabilidade a frequência: para $X_k$ a indicadora de um evento $A$ em repetições independentes, $S_n/n$ é a frequência observada de $A$ , e a lei dos grandes números diz que ela se concentra em torno de $\P(A)$ à taxa $\frac{p(1-p)}{n\varepsilon^2}$ . A lei forte ( $S_n/n \to m$ quase certamente) é um teorema do terceiro ano — sua demonstração para momentos de quarta ordem está ao alcance, no entanto: veja o Exercício 22.9, que roda Borel–Cantelli sobre a cota do tipo Chebyshev. A mesma estimativa de Chebyshev moveu a demonstração por polinômios de Bernstein do teorema de aproximação de Weierstrass no Capítulo 10 — o lema de contagem de lá era a lei fraca dos grandes números disfarçada.

Exemplo 22.27 (Colecionando cinquenta cupons)

O colecionador de cupons do Exercício 22.3 com $n = 50$ brindes distintos: o total esperado vale

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

caixas — quatro vezes e meia o palpite ingênuo $50$ . O crescimento harmônico é toda a história: os primeiros $25$ brindes chegam em cerca de $50\ln2 \approx 35$ caixas, ao passo que o último brinde sozinho custa $50$ caixas em média (uma espera geométrica de parâmetro $\frac1{50}$ ). Os problemas de completude são dominados por seu final de partida, e é por isso que o Exercício 22.12 encontra flutuações da ordem de $n$ — o tamanho daquela espera geométrica final — em torno da média $n\ln n$ .

Exemplo 22.28 (Quão grande deve ser $n$ ?)

Para fixar a frequência observada a menos de $\varepsilon = 0.01$ de $\P(A)$ com confiança $95\%$ , a cota de Chebyshev exige

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

A dependência é brutal em $\varepsilon$ (quadrática) e suave na confiança (linear em $1/\alpha$ ). Ambas as características são propriedades da cota, não da verdade: as desigualdades exponenciais do problema de fim de semana baixam o preço da confiança de $1/\alpha$ para $\ln(1/\alpha)$ — a mesma especificação custará ali cerca de $18\,500$ amostras — enquanto a escala $1/\varepsilon^2$ é genuína e inaperfeiçoável. Saber qual parte de uma cota é frouxa é tão útil quanto a própria cota.

A lei dos grandes números em imagem: a lei de S_n/n (desenhada esquematicamente) mantém seu centro m mas se estreita à medida que n cresce, de modo que a probabilidade fora da faixa [m- , m+ ] — as duas caudas — encolhe a zero. Chebyshev majora as caudas por V(X_1)/(n 2); o problema de fim de semana mostra que elas são de fato exponencialmente pequenas. — A lei dos grandes números em imagem: a lei de $S_n/n$ (desenhada esquematicamente) mantém seu centro $m$ mas se estreita à medida que $n$ cresce, de modo que a probabilidade fora da faixa $\intcc{m-\varepsilon}{m+\varepsilon}$ — as duas caudas — encolhe a zero. Chebyshev majora as caudas por $V(X_1)/(n\varepsilon^2)$ ; o problema de fim de semana mostra que elas são de fato exponencialmente pequenas.

Observação 22.29 (Perspectivas dentro deste volume)

Para a frente, tudo aqui alimenta o Capítulo 23: a esperança $\E(t^X)$ de uma função astuciosa de $X$ empacota a lei inteira numa série de potências, os momentos se tornam derivadas em $1$ , e identidades do tipo Wald para somas aleatórias carregam a teoria dos processos de ramificação; o teorema do produto para variáveis independentes se torna a multiplicatividade das funções geradoras. Para trás, a esperança é um baricentro com pesos de probabilidade (Capítulo 17), a desigualdade de Jensen é a geometria da reta de apoio das funções convexas (Capítulo 8) e o método dos momentos exponenciais do problema de fim de semana deste capítulo é Markov aplicado a $\eu^{tX}$ — uma desigualdade, aprimorada por uma boa mudança de variável, atravessando três capítulos.

22.5 Exercícios

Exercício 22.1 ★

Calcule $\E(X)$ e $V(X)$ para $X \sim \mathcal{B}(n, p)$ (via indicadoras), $X \sim \mathcal{P}(\lambda)$ (mostre que $V(X) = \lambda$ ) e $X \sim \mathcal{G}(p)$ (mostre que $V(X) = \frac{1-p}{p^2}$ ; use $\E(X(X-1))$ e a segunda derivada da série geométrica).

Solução

Solução de Exercício 22.1.

Binomial: $X = \sum_{i=1}^n X_i$ com variáveis de Bernoulli independentes $X_i$ ; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , e as variâncias de variáveis independentes se somam (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$ , logo

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}$ duas vezes dentro do disco (Capítulo 11), $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ , logo

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

Exercício 22.2 ★

Sejam $X \sim \mathcal{P}(\lambda)$ e $Y \sim \mathcal{P}(\mu)$ independentes. Mostre que $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolução dos pesos; teorema binomial) e que a lei condicional de $X$ dado $X + Y = n$ é binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

Solução

Solução de Exercício 22.2.

Soma: para $n \in \N$ , por disjunção e independência,

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

pelo teorema binomial: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Lei condicional: 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} ,

a lei binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : dada a contagem total, cada evento “escolhe” independentemente a primeira fonte com probabilidade proporcional à sua taxa.

Exercício 22.3 ★

(Colecionador de cupons, esperança) Uma marca de cereal esconde um de $n$ brindes distintos, uniformemente, em cada caixa. Seja $T_n$ o número de caixas necessárias para coletar todos os $n$ brindes. Escrevendo $T_n$ como soma de variáveis geométricas independentes (tempo até ver um brinde novo quando $k$ ainda faltam), mostre que

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

(equivalente pela comparação série–integral do Capítulo 6).

Solução

Solução de Exercício 22.3.

Quando ainda faltam $k$ brindes, cada caixa nova traz um brinde novo com probabilidade $\frac kn$ , independentemente do passado: o tempo de espera $W_k$ pelo próximo brinde novo é geométrico $\mathcal{G}\bigl(\frac kn\bigr)$ , com $\E(W_k) = \frac nk$ , e $T_n = W_n + W_{n-1} + \dots + W_1$ (a primeira caixa sempre dá um brinde novo: $W_n = 1$ , coerente com $\E = n/n$ ). Por linearidade,

\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). Coletar os últimos brindes é o que custa: metade das caixas vai para o punhado final.

Exercício 22.4 ★★

Seja $X \geq 0$ com valores inteiros. Demonstre a fórmula das caudas

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

(quando um dos membros é finito), escrevendo $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ e trocando as somas (Fubini para famílias não negativas). Recupere $\E(X) = \frac1p$ para a lei geométrica.

Solução

Solução de Exercício 22.4.

Pontualmente, $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . A família dupla $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ é não negativa, de modo que Fubini para famílias (Capítulo 7) se aplica sem condições: somar primeiro em $n$ dá $\E(X)$ , somar primeiro em $\omega$ dá $\sum_n \P(X \geq n)$ ; as duas são simultaneamente finitas e iguais. Para $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), logo $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Exercício 22.5 ★★

(A amostragem sem reposição é mais concentrada) Uma urna tem $N$ bolas, $M$ delas brancas. Sorteie $n \leq N$ sem reposição e seja $X$ a contagem de brancas (lei hipergeométrica). Usando indicadoras $X = \sum_{i=1}^n Y_i$ com $Y_i$ o $i$ -ésimo sorteio: mostre que cada $Y_i$ é Bernoulli de parâmetro $p = M/N$ (simetria!), conclua que $\E(X) = np$ exatamente como com reposição e mostre que $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ para $i \neq j$ , logo $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

Solução

Solução de Exercício 22.5.

Simetria: a $i$ -ésima bola sorteada é uma bola uniformemente aleatória da urna (qualquer uma das $N$ bolas tem a mesma chance de cair na posição $i$ da ordem de sorteio), logo $\P(Y_i = 1) = \frac MN = p$ e $\E(X) = np$ por linearidade — sem precisar de independência.

Covariância: para $i \neq j$ , $\E(Y_iY_j) = \P(\text{sorteios } i, j \text{ ambas brancas}) = \frac{M(M-1)}{N(N-1)}$ (pares ordenados de posições distintas recebem um par ordenado de bolas distintas, uniformemente). Portanto

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

sortear uma bola branca torna as brancas mais escassas para os demais sorteios. Pelo 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) :

a amostragem sem reposição tem a mesma média mas menor variância que a amostragem com reposição (igualdade só para $n = 1$ ), agindo as correlações negativas como estabilizador. Para $n = N$ a variância se anula: a contagem é então determinística.

Exercício 22.6 ★★

Seja $X$ com momento de segunda ordem. Mostre que $c \mapsto \E\bigl((X - c)^2\bigr)$ é mínima exatamente em $c = \E(X)$ , com mínimo $V(X)$ . Mostre então que $\P(X = \E(X)) = 1$ se e somente se $V(X) = 0$ . (Para o segundo ponto: se $V(X) = 0$ , use Chebyshev com $\varepsilon = 1/n$ e a continuidade monótona, Teorema 21.6.)

Solução

Solução de Exercício 22.6.

Desenvolvendo em torno 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ínima exatamente em $c = m$ com valor $V(X)$ — a esperança é o melhor preditor constante em média quadrática.

Se $\P(X = m) = 1$ , então $(X - m)^2$ se anula com probabilidade $1$ , logo $V(X) = 0$ (a família que a define tem termos nulos salvo num conjunto nulo). Reciprocamente, se $V(X) = 0$ , Chebyshev (Teorema 22.15) dá $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ para todo $n$ ; os eventos $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ crescem para $\{X \neq m\}$ , de modo que a continuidade monótona (Teorema 21.6) dá $\P(X \neq m) = 0$ .

Exercício 22.7 ★★★

(A concentração bate Markov) Seja $S_n \sim \mathcal{B}(n, \frac12)$ (número de caras em $n$ lançamentos honestos). Compare as cotas dadas por Markov ( $\P(S_n \geq \frac{3n}{4})$ ), por Chebyshev e pelo 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),

e otimize $t$ para obter uma cota exponencialmente pequena. (Em $t = \ln 3$ : majore $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

Solução

Solução de Exercício 22.7.

$\E(S_n) = \frac n2$ e $V(S_n) = \frac n4$ . Markov: $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — uma cota constante, inútil para $n$ grande. Chebyshev: o evento implica $\abs{S_n - \frac n2} \geq \frac n4$ , de modo que a probabilidade é $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — decai, mas apenas polinomialmente. Chernoff: pela independência, $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ , e Markov aplicado a $e^{tS_n} \geq e^{3nt/4}$ dá, 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).

Minimize o expoente: $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ em $e^t = 3$ , isto é, $t = \ln 3$ , o que dá

\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 pequeno. A hierarquia Markov $\to$ Chebyshev $\to$ Chernoff é a escada padrão: cada degrau aplica Markov a uma função de crescimento mais rápido da variável.

Exercício 22.8 ★★★

(Weierstrass de novo, probabilisticamente) Seja $f \colon [0,1] \to \R$ contínua e $S_n \sim \mathcal{B}(n, x)$ . Mostre que o polinômio 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]$ e redemonstre a estimativa $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ do Capítulo 10 nessa linguagem probabilística (separe em $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ e use Chebyshev).

Solução

Solução de Exercício 22.8.

Pelo teorema de transferência (Teorema 22.7) aplicado a $f\bigl(\frac{S_n}{n}\bigr)$ com $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) .

Fixe $\delta > 0$ e separe $\abs{f(S_n/n) - f(x)}$ no evento $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : fora de $D$ , a diferença é no máximo o módulo de continuidade $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; em $D$ , no máximo $2\norm f_\infty$ . Tomando esperanças e usando Chebyshev com $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} .

A continuidade uniforme de $f$ em $[0, 1]$ faz $\omega_f(\delta) \to 0$ : escolha $\delta$ e depois $n$ , e $B_nf \to f$ uniformemente — o teorema de aproximação de Weierstrass do Capítulo 10, cujo “lema de contagem” é agora reconhecível como a desigualdade de Chebyshev para a lei binomial.

Exercício 22.9 ★★★

(Lei forte sob momentos de quarta ordem) Sejam $(X_k)$ independentes, identicamente distribuídas, centradas ( $\E X_1 = 0$ ), com $\E(X_1^4) < \infty$ . Desenvolvendo $\E(S_n^4)$ e contando os termos sobreviventes (apenas termos em $\E(X_i^4)$ e em $\E(X_i^2X_j^2)$ , $i \neq j$ ), mostre que $\E(S_n^4) \leq C n^2$ para uma constante $C$ . Deduza $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ para cada $\varepsilon > 0$ (Markov na ordem 4) e conclua com Borel–Cantelli (Teorema 21.25) que $S_n/n \to 0$ quase certamente, numa formulação adequada: o evento $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ tem probabilidade $1$ .

Solução

Solução de Exercício 22.9.

Desenvolva $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ e tome esperanças. Por independência e centragem, todo termo que contenha um índice que apareça exatamente uma vez se anula ( $\E(X_i) = 0$ se fatora para fora). Termos sobreviventes: os $n$ termos diagonais $\E(X_i^4)$ e os termos que emparelham dois pares de índices iguais, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ para $i \neq j$ , aparecendo $3n(n-1)$ vezes: escolha o par não ordenado de valores ( $\binom n2$ modos) e depois os $\frac{4!}{2!\,2!} = 6$ modos de dispô-los nas quatro posições — $6\binom n2 = 3n(n-1)$ . Portanto, com $\E(X_1^2)^2 \leq \E(X_1^4)$ (Jensen ou 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 na ordem 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} ,

uma série somável. Por Borel–Cantelli 1 (Teorema 21.25), para cada $j$ o evento $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ tem probabilidade $0$ , logo $\P\bigl(\bigcup_j B_j\bigr) = 0$ por subaditividade enumerável. No complementar — de probabilidade $1$ — para todo $j$ existe $N$ com $\abs{S_n/n} < \frac1j$ para todo $n \geq N$ : precisamente $S_n/n \to 0$ . A lei forte dos grandes números vale sob momento de quarta ordem; remover essa hipótese (teorema de Kolmogorov) é trabalho do terceiro ano.

Exercício 22.10 ★

Lançam-se dois dados honestos; seja $M$ o maior dos dois resultados. Usando a fórmula das caudas do Exercício 22.4 (versão finita), mostre 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 .

Solução

Solução de Exercício 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (os dois dados no máximo $k$ , independentemente), logo $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ e

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

confortavelmente acima da média $3.5$ de um único dado, como um máximo deve ficar.

Exercício 22.11 ★★

Seja $F_n$ o número de pontos fixos de uma permutação uniformemente aleatória de $\{1, \dots, n\}$ ( $n \geq 2$ ). Escrevendo $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ , calcule $\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$ , e conclua que $V(F_n) = 1$ : em média uma carta fica fixa, com variância exatamente $1$ , qualquer que seja $n$ .

Solução

Solução de Exercício 22.11.

Com $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ , logo $\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)}$ , portanto

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

Pelas ferramentas da variância (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 .

Média $1$ , variância $1$ , independentemente de $n$ — coerente com o limite de Poisson do problema dos encontros (Exercício 21.5).

Exercício 22.12 ★★★

(Colecionador de cupons, concentração) No contexto do Exercício 22.3, mostre 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 a independência das etapas geométricas e $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (Exercício 22.1; o valor $\pi^2/6$ é Exemplo 14.12). Deduza com Chebyshev que $\dfrac{T_n}{n\ln n} \to 1$ em probabilidade: o tempo total do colecionador é $n\ln n$ a menos de flutuações da ordem de $n$ .

Solução

Solução de Exercício 22.12.

$T_n = \sum_{k=1}^nG_k$ , em que $G_k \sim \mathcal G(k/n)$ é o tempo até ver um brinde novo quando faltam $k$ , sendo as etapas independentes. Portanto

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 ,

pelo Exemplo 14.12. Com $\E(T_n) = nH_n$ , $H_n = \sum_1^n\frac1k$ (Exercício 22.3), Chebyshev dá, 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$ , dividir por $n\ln n$ mostra que $T_n/(n\ln n) \to 1$ em probabilidade: as flutuações de $T_n$ são da ordem de $n$ , desprezíveis contra a média $n\ln n$ .

22.6 Problema: a caixa de ferramentas da concentração, de Markov a Hoeffding

Problema 22.1

Problema de fim de semana — concentração exponencial na mão, e quantas pessoas uma pesquisa deve ouvir

A desigualdade de Markov custa um momento e compra um decaimento em $1/a$ ; Chebyshev custa dois momentos e compra $1/\varepsilon^2$ — e o Exemplo 22.18 mostra que isso é tudo o que esses momentos podem comprar. Este problema sobe o resto da escada: o método exponencial (Chernoff) com sua taxa exata para lançamentos de moeda, a desigualdade de Hoeffding para todas as variáveis limitadas e a recompensa — tamanhos de amostra explícitos e honestos para pesquisas eleitorais, previsões de eleição e teste de moedas. Em todo o problema, $S_n \sim \mathcal B(n, p)$ é uma soma de $n$ variáveis de Bernoulli independentes e $\widehat p_n = S_n/n$ é a frequência empírica.

Parte I — Calibração na moeda honesta. Aqui $p = \frac12$ e $a \in \intoo{\frac12}{1}$ .

Markov no nível $an$ : mostre que $\P(S_n \geq an) \leq \frac1{2a}$ , uma cota que não tende sequer a $0$ . Onde Markov perde tanto?
Chebyshev: usando a simetria da binomial honesta em torno de $n/2$ , mostre 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},$

isto é, $\frac2n$ em $a = \frac34$ : decaimento polinomial, enfim.
(Chernoff, nível geral) Calcule $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ e otimize $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ em $t > 0$ : mostre que o $t$ ótimo é $\ln\frac{a}{1-a}$ e 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 .$

Verifique que $a = \frac34$ recupera a cota $\bigl(2\cdot3^{-3/4}\bigr)^n$ do Exercício 22.7.
(O expoente é exato) Seja $k = an$ um inteiro. A partir do fato de que $\binom nk a^k(1-a)^{n-k}$ é o maior dos $n + 1$ termos de uma distribuição de probabilidade, demonstre que $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ com $H(a) = -a\ln a - (1-a)\ln(1-a)$ , e deduza a cota inferior correspondente

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Tabule as três cotas em $n = 100$ , $a = \frac34$ : Markov $\frac23$ , Chebyshev $0.02$ , Chernoff $\approx 2.1\cdot10^{-6}$ (o valor verdadeiro é $\approx 2.8\cdot10^{-7}$ ). Moral, numa frase?

Parte II — A desigualdade de Hoeffding.

(Caso Rademacher) Para $\varepsilon = \pm1$ com probabilidade $\frac12$ cada, demonstre que

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

comparando as duas séries termo a termo ( $(2k)! \geq 2^kk!$ ).
Deduza, para variáveis de Rademacher independentes $\varepsilon_1, \dots, \varepsilon_n$ e todo $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Traduza para moedas honestas ( $X_i = \frac{1+\varepsilon_i}2$ ): $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ , e a versão bilateral com um fator $2$ .
(Lema de Hoeffding) Seja $X \in \intcc01$ com $\E X = p$ e $\psi(t) = \ln\E(\eu^{tX})$ . Justifique que $\psi$ é duas vezes diferenciável com

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

uma variância de uma variável reponderada que ainda assume valores em $\intcc01$ ; majore-a por $\frac14$ (o argumento de minimalidade do Exercício 22.6) e conclua por Taylor:

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(Desigualdade de Hoeffding) Para $X_i \in \intcc01$ independentes com média comum $p$ , deduza

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Compare a taxa de Chebyshev $\frac{p(1-p)}{n\delta^2}$ com a de Hoeffding $2\eu^{-2n\delta^2}$ : que hipótese cada uma exige, e a partir de qual $n$ (grosseiramente) a cota exponencial ganha em $\delta = 0.03$ , $p = \frac12$ ?

Parte III — Quantas pessoas uma pesquisa deve ouvir? Uma pesquisa consulta $n$ eleitores independentes e uniformemente escolhidos; cada um responde honestamente; $p$ é a intenção verdadeira e $\widehat p_n$ é o número da pesquisa.

Mostre que a pesquisa é precisa a menos de $\pm\delta$ com confiança $1 - \alpha$ (isto é, $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) assim que

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Calcule o $n$ necessário para a especificação padrão “três pontos, noventa e cinco por cento” ( $\delta = 0.03$ , $\alpha = 0.05$ ): $n \geq 2050$ ; e para um ponto: $n \geq 18\,445$ . Observe — e explique — o fato notável de que a resposta não envolve o tamanho da população.
Refaça a questão 13 com Chebyshev ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ para três pontos. Note que a amostragem sem reposição só ajuda (Exercício 22.5: a variância encolhe por $\frac{N-n}{N-1}$ ).
(Prever uma eleição) A intenção verdadeira de um candidato é $p = 0.52$ . Quantos eleitores devem ser consultados para que $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Mostre que $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — prever uma disputa apertada custa muito mais que estimar uma intenção de voto.
O que a matemática não cobre: liste as hipóteses de modelagem usadas (amostragem uniforme independente, respostas honestas, $p$ fixo) e explique num parágrafo curto por que os erros reais de pesquisa são dominados pelo viés (amostragem não uniforme, não resposta), que aumento algum de $n$ reduz.

Parte IV — Mais fino e mais barato.

(Mediana das médias: decaimento exponencial a partir de dois momentos) Divida um orçamento de $km$ amostras em $k$ grupos independentes de $m$ ; sejam $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ as médias dos grupos e $M$ a mediana delas. Escolha $m$ de modo que cada grupo satisfaça $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (Chebyshev: $m \geq \frac2{\delta^2}$ basta). Mostre que, se $\abs{M - p} \geq \delta$ , então ao menos $k/2$ grupos erram, e deduza

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

concentração exponencial sem usar nada além de variâncias.
(Paley–Zygmund) Para $X \geq 0$ com momento de segunda ordem, demonstre que $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz em $X\mathbf 1_{X>0}$ ): a ferramenta na direção inversa — os momentos também podem forçar eventos a acontecer.
(Pinsker leve) Mostre que $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ em $\intoo{\frac12}1$ (a diferença se anula até a segunda ordem em $\frac12$ e sua segunda derivada é $\frac1{a(1-a)} - 4 \geq 0$ ): o expoente exato de Chernoff sempre bate o quadrático de Hoeffding.
Desenvolva $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ e combine com a questão 4: para desvios pequenos, o expoente de Hoeffding $2n\delta^2$ é assintoticamente exato — método algum pode batê-lo por mais que fatores polinomiais.
Monte a tabela da caixa de ferramentas: para Markov, Chebyshev, a cota de quarto momento do Exercício 22.9, Hoeffding e Chernoff com expoente $I$ , enuncie em uma linha cada: hipótese exigida, decaimento obtido e a questão deste problema em que ela foi mais fina.

Parte V — Dividendos.

(Testando uma moeda) Uma moeda é honesta ou é viciada com $p = 0.55$ . Você a lança $n$ vezes e declara “viciada” quando $\widehat p_n > 0.525$ . Mostre que ambas as probabilidades de erro são no máximo $\eu^{-2n(0.025)^2}$ e que $n \geq 3685$ lançamentos garantem as duas abaixo de $1\%$ .
(Eventos raros pedem uma cota atenta à variância) Seja $p = 0.01$ e tome a especificação relativa $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . Compare os tamanhos de amostra exigidos por Hoeffding ( $n \approx 74\,000$ ) e por Chebyshev com a variância verdadeira $p(1-p)$ ( $n \approx 7920$ ): a cota exponencial cega à variância perde para o humilde momento de segunda ordem. Enuncie a moral e diga de onde virá a ferramenta que falta (uma cota exponencial atenta à variância; a aproximação de Poisson do Capítulo 23).
(Lei forte para moedas) A partir do $\sum_n 2\eu^{-2n\delta^2} < \infty$ e de Borel–Cantelli (Teorema 21.25), demonstre que $\widehat p_n \to p$ quase certamente para lançamentos de moeda independentes: formule o evento quase certo como $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ , como no Exercício 22.9, e conclua. (A limitação substitui o momento de quarta ordem usado lá.)
Síntese. Em cinco frases: o que cada degrau da escada (momentos um, dois, quatro; exponencial limitado; expoente exato) custa e compra; por que consultar $2050$ pessoas basta para um país de qualquer tamanho; e qual dessas cotas o volume do terceiro ano de graduação afinará nas constantes exatas do teorema central do limite.

Solução

Solução de Problema 22.1.

1. $\E(S_n) = \frac n2$ e Markov (Teorema 22.15) dão $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov só conhece a média: ele não consegue distinguir uma variável concentrada em $n/2$ de uma espalhada entre $0$ e $n$ , de modo que precifica a cauda como se toda a massa pudesse estar ali.

2. A binomial honesta é simétrica em torno de $n/2$ ( $S_n$ e $n - S_n$ têm a mesma lei), de modo que, com $x = n(a - \frac12) > 0$ , os dois eventos $\{S_n - \frac n2 \geq x\}$ e $\{S_n - \frac n2 \leq -x\}$ são disjuntos e equiprováveis: $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . Chebyshev com $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$ em $a = \frac34$ .

3. Pela independência e pelo teorema do produto, $\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).

A derivada do expoente em $t$ é $\frac{\eu^t}{1 + \eu^t} - a$ , que se anula em $\eu^t = \frac a{1-a}$ , isto é, $t^* = \ln\frac a{1-a} > 0$ ; ali $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ e o expoente 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),

com $I(\frac12) = 0$ e $I'(a) = \ln\frac a{1-a} > 0$ em $\intoo{\frac12}1$ : $I(a) > 0$ . Em $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , a cota do Exercício 22.7.

4. Os $n + 1$ números $\binom nja^j(1-a)^{n-j}$ somam $1$ , e o maior é o que está em $j = k = an$ (a moda de $\mathcal B(n, a)$ é $\floor{(n+1)a} = k$ aqui). Um máximo de $n + 1$ números que somam $1$ é ao 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}.

Portanto $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : a menos do fator polinomial $n + 1$ , o expoente de Chernoff é a verdade.

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 o exato $2.8\cdot10^{-7}$ . Moral: cada momento de informação divide a cota polinomialmente; o momento exponencial muda sua natureza.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ e $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ; a afirmação segue termo a termo de $(2k)! \geq 2^kk!$ , que vale por indução: $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. Pela independência, $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , de modo que Markov dá $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; minimizar em $t = s/n$ dá $\eu^{-s^2/(2n)}$ .

8. Com $X_i = \frac{1 + \varepsilon_i}2$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , logo $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ e a questão 7 dá a cota $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . O evento simétrico tem a mesma cota, donde o fator $2$ para $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ é uma série de funções suaves de $t$ cujas derivadas termo a termo são dominadas, em todo intervalo compacto de $t$ , por $\eu^{\abs t}\P(X = x)$ (pois $0 \leq x \leq 1$ ): pelo teorema de derivação para séries normalmente convergentes (Teorema 10.7) ela é duas vezes diferenciável, e a regra do quociente dá $\psi' = \E_t(X)$ e $\psi'' = \E_t(X^2) - \E_t(X)^2$ , em que $\E_t$ é a esperança para os pesos reponderados $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — não negativos, de soma $1$ , carregados pelos mesmos valores $x \in \intcc01$ . Uma variância de uma variável com valores em $\intcc01$ vale no máximo $\frac14$ : pelo Exercício 22.6, ela é $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . Taylor com 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,

isto é, $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ para todo $t$ real.

10. Pela independência, $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ; Markov e a otimização $t = 4\delta$ dão

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

aplicar isso às variáveis $1 - X_i$ (também em $\intcc01$ ) majora a outra cauda, donde a versão bilateral $2\eu^{-2n\delta^2}$ .

11. Chebyshev precisa apenas de momento de segunda ordem e dá $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding precisa da limitação e dá $2\eu^{-2n\delta^2}$ . Em $p = \frac12$ , $\delta = 0.03$ : as cotas valem $\frac{278}{n}$ (aproximadamente) contra $2\eu^{-0.0018n}$ ; elas se cruzam perto de $n \approx 1200$ , depois do que a cota exponencial ganha, e escandalosamente ( $n = 5000$ : $0.056$ contra $2.5\cdot10^{-4}$ ).

12. Por Hoeffding (questão 10), $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ assim que $2n\delta^2 \geq \ln\frac2\alpha$ , isto é, $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$ pessoas. Para $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . O tamanho da população nunca aparece porque cada eleitor amostrado é modelado como um sorteio novo de Bernoulli $(p)$ : a dificuldade da pesquisa é a variância de uma moeda, não o tamanho do país. Reduzir a margem à metade custa quatro vezes a amostra — a lei $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}$ , isto é, $5556$ para três pontos — cerca de $2.7$ vezes a exigência de Hoeffding. Sem reposição, a variância é multiplicada por $\frac{N - n}{N-1} < 1$ (Exercício 22.5), de modo que o mesmo $n$ só pode fazer melhor: o cálculo com reposição é o conservador.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , de modo que, pela cota unilateral de Hoeffding, $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ assim que $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ eleitores. O custo escala como o inverso do quadrado da vantagem, e não da precisão desejada: disputas apertadas são caras.

16. Usadas: a amostra é sorteada uniforme e independentemente do eleitorado; toda pessoa amostrada responde, honestamente, e $p$ não se move durante a pesquisa. As pesquisas reais violam as três: os respondentes alcançáveis e dispostos não são uma amostra uniforme (viés de seleção e de não resposta), e as respostas podem ser mentirosas ou instáveis. Esses são erros de viés: eles afastam $\E(\widehat p_n)$ de $p$ por uma quantidade independente de $n$ , de modo que tamanho de amostra algum os reduz — a matemática desta Parte controla apenas o termo de flutuação.

17. Chebyshev para um grupo de tamanho $m$ : $\P(\abs{ \widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ para $m \geq \frac2{\delta^2}$ . Se menos de $k/2$ grupos erram, então mais de $k/2$ dos valores $\widehat p^{(i)}$ estão no intervalo aberto $\intoo{p - \delta}{p + \delta}$ , e sua mediana também; portanto $\{\abs{M - p} \geq \delta\}$ força ao menos $\lceil k/2\rceil$ erros entre $k$ grupos independentes. A cota da união sobre os $\binom k{\lceil k/2\rceil}$ conjuntos possíveis de grupos que erram dá

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

decaimento exponencial no número de grupos, comprado com nada além de variâncias — útil precisamente quando as parcelas são ilimitadas e Hoeffding não está disponível.

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)} ;

eleve ao quadrado e divida.

19. Seja $h(a) = I(a) - 2(a - \tfrac12)^2$ . Então $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ se anula em $\tfrac12$ , e

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

pois $a(1-a) \leq \frac14$ . Assim, $h'$ cresce a partir de $0$ em $\intco{\frac12}1$ , logo $h' \geq 0$ e $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ , $I''(a) = \frac1{a(1-a)}$ dá $I''(\tfrac12) = 4$ , e $I'''(\tfrac12) = 0$ (a função é simétrica em torno de $\tfrac12$ ), de modo que $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . A questão 4 então minora a cauda verdadeira por $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : para $\delta$ pequeno o expoente de Hoeffding $2n\delta^2$ é assintoticamente exato — só são possíveis melhorias polinomiais em $n$ .

21. Markov: um momento, decaimento $1/a$ , útil apenas como motor por trás dos demais (a questão 1 o mostra plano). Chebyshev: dois momentos, decaimento $\frac{V}{n\delta^2}$ , ótimo sem hipóteses adicionais (Exemplo 22.18), e a melhor ferramenta na questão 23. Quarto momento (Exercício 22.9): decaimento $C/n^2$ , somabilidade suficiente para uma lei forte. Hoeffding: variáveis limitadas, decaimento $2\eu^{-2n\delta^2}$ , o cavalo de batalha da Parte III. Chernoff com a taxa exata $I(a)$ : momentos exponenciais completos, expoente imbatível (questões 4, 20), o ponto de referência para todo o resto.

22. Se a moeda é honesta: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . Se $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 os erros ficam abaixo de $0.01$ quando $2n(0.025)^2 \geq \ln 100$ , isto é, $n \geq 3684.2$ : $3685$ lançamentos. (Distinguir hipóteses a $2.5$ pontos de distância custa o que custa estimar com $\pm2.5$ pontos de precisão.)

23. Hoeffding: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Chebyshev com a variância verdadeira $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — nove vezes mais barato. O expoente de Hoeffding $2n\delta^2$ precifica a variância em seu pior caso $\frac14$ , absurdamente pessimista quando $p = 0.01$ ; o humilde momento de segunda ordem sabe melhor. A ferramenta que falta é uma cota exponencial atenta à variância (desigualdade de Bernstein, terceiro ano) — ou, para eventos raros, a aproximação de Poisson demonstrada no Capítulo 23, que trabalha na escala relativa natural.

24. Fixe $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (série do tipo geométrico), de modo que Borel–Cantelli 1 (Teorema 21.25) dá $\P(\abs{\widehat p_n - p} \geq \delta \text{ infinitas vezes}) = 0$ , isto é, o evento $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ tem probabilidade $1$ para cada $j$ . A interseção enumerável $\bigcap_jE_j$ ainda tem probabilidade $1$ (subaditividade nos complementares), e nela $\widehat p_n \to p$ : a lei forte dos grandes números para lançamentos de moeda, com a limitação desempenhando o papel que o momento de quarta ordem desempenhou no Exercício 22.9.

25. Um momento compra uma cota plana; dois compram $1/(n\delta^2)$ , e nada mais (o exemplo de otimalidade); quatro compram $1/n^2$ , o bastante para telescopar numa lei quase certa; a limitação compra $\eu^{-2n\delta^2}$ ; e o momento exponencial completo compra a taxa exata $I$ , que método algum bate. Consultar $2050$ pessoas basta para qualquer país porque a flutuação da amostra é governada pela variância da moeda, não pelo tamanho da população — as etiquetas de preço $1/\delta^2$ e $\ln(1/\alpha)$ são universais. O teorema central do limite do volume do terceiro ano de graduação substitui essas desigualdades, na escala $\sqrt n$ , por uma lei limite exata com constantes explícitas — transformando toda cota deste problema numa igualdade assintótica.