--- title: "Variáveis aleatórias discretas" book: "Matemática universitária — Graduação 2" subject: math language: pt chapter: 22 exercises: 12 source: https://one-course.com/books/math/4/pt/chapter/22-variaveis-aleatorias-discretas --- # Capítulo 22 — Variáveis aleatórias discretas As [variáveis aleatórias](#def-b2-randomvar-law) organizam os cálculos de probabilidade em torno de funções, e não de [eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space). Em espaços [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) a teoria é movida pelas [famílias somáveis](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) do [Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series): a [esperança](#def-b2-randomvar-expectation) é a soma de uma família indexada pelo [espaço amostral](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space), e todas as suas propriedades — linearidade, transferência, fórmula do produto para variáveis [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) — são teoremas sobre [famílias somáveis](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable). O capítulo demonstra as desigualdades-chave de Markov, Chebyshev, Cauchy–Schwarz e Jensen, e termina com as [leis](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable). 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $\P_X$ no [conjunto enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) $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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) . - *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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) (volume do ensino médio; redemonstrada abaixo via somas de variáveis [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) ). - *Geométrica* $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : posição do primeiro sucesso ( [Exemplo 21.5](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#ex-b2-proba-geometric) ). - *Poisson* $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — uma [medida de probabilidade](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) pela série exponencial. A lei dos eventos raros ( [Capítulo 23](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun) ). **Observação 22.3 (Qual lei modela o quê).** As quatro [leis](#def-b2-randomvar-law) respondem a quatro perguntas primitivas: Bernoulli, “aconteceu?”; binomial, “quantas vezes em $n$ tentativas?”; geométrica, “quanto tempo até a primeira vez?”; Poisson, “quantos [eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) raros para a Poisson — com a passagem da binomial à Poisson precisada pela lei dos eventos raros no [Capítulo 23](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun). **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](#def-b2-randomvar-law) geométricas são as únicas [leis](#def-b2-randomvar-law) 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](#def-b2-randomvar-law) é $\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](#def-b2-randomvar-law) 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](#def-b2-randomvar-law) real $X$ em $(\Omega, \P)$ *tem esperança* se a família $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ for [somável](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) ([Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)); 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](#def-b2-randomvar-expectation) se e somente se a família $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ é [somável](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable), 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](#def-b2-randomvar-expectation) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) ([Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)), a família $(X(\omega)\P(\{\omega\}))_\omega$ é [somável](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) — 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) absoluta de uma família equivalente à da outra. ∎ **Teorema 22.8 (Propriedades da esperança).** No conjunto das [variáveis aleatórias](#def-b2-randomvar-law) com [esperança](#def-b2-randomvar-expectation): 1. (Linearidade) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ . 2. (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)$ . 3. (Dominação) Se $\abs X \leq Z$ e $Z$ tem [esperança](#def-b2-randomvar-expectation) , então $X$ também tem. **Demonstração.** Todas são propriedades de somas de [famílias somáveis](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) ([Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)): linearidade da soma, positividade termo a termo e o critério de dominação para a [somabilidade](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable). (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](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#ch-b2-powerseries)). $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](#def-b2-randomvar-law) 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](#def-b2-randomvar-expectation) 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](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) $t \mapsto \frac1{1+t}$. As [esperanças](#def-b2-randomvar-expectation) de imagens [convexas](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) 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](#def-b2-randomvar-law) $X, Y$ são *[independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence)* se $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ para todos $x, y$ — equivalentemente, os [eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $\{X \in A\}$ e $\{Y \in B\}$ são [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) para todos $A, B$. Se $X$ e $Y$ são variáveis reais [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) com [esperanças](#def-b2-randomvar-expectation), então $XY$ tem [esperança](#def-b2-randomvar-expectation) e $$ \E(XY) = \E(X)\,\E(Y) . $$ **Demonstração.** A equivalência das duas formulações segue somando a identidade [pontual](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable), pois, por Fubini para famílias ([Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)), $$ \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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) 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](#def-b2-randomvar-law) marginais nos dois cenários, [leis](#def-b2-randomvar-law) conjuntas diferentes, [esperanças](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-variance) $\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](#def-b2-randomvar-expectation) (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: 1. $V(aX + b) = a^2\,V(X)$ ; 2. $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) ;$$ 3. se $X, Y$ são [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) , $\operatorname{Cov}(X, Y) = 0$ (a recíproca é falsa), de modo que as [variâncias](#def-b2-randomvar-variance) de variáveis [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) se somam. **Demonstração.** *1* e *2* são desenvolvimentos de quadrados mais linearidade; os produtos $X_iX_j$ têm [esperança](#def-b2-randomvar-expectation) por Cauchy–Schwarz abaixo (ou por $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$). *3* é o [Teorema 22.11](#thm-b2-randomvar-product) 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).** 1. (Markov) Se $X \geq 0$ tem [esperança](#def-b2-randomvar-expectation), então, para todo $a > 0$: $$\P(X \geq a) \leq \frac{\E(X)}{a} .$$ 2. (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](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def), $a\,\mathbf{1}_{X \geq a} \leq X$ (no [evento](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) o membro da esquerda vale $a \leq X$; fora dele, $0 \leq X$). Tome [esperanças](#def-b2-randomvar-expectation): $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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $\{(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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), e ponha $S = X + Y$, $D = X - Y$. Pela bilinearidade da [covariância](#def-b2-randomvar-variance), $$ \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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence)? 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](#def-b2-randomvar-variance). (Para esse par, a [covariância](#def-b2-randomvar-variance) nula precisou de $V(X) = V(Y)$: [distribuições](#def-b2-randomvar-law) idênticas, e não [independência](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), é 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](#def-b2-randomvar-variance) — 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](#exo-b2-randomvar-7) antecipa e o problema de fim de semana deste capítulo desenvolve sistematicamente. **Teorema 22.19 (Cauchy–Schwarz e Jensen).** 1. (Cauchy–Schwarz) Se $X, Y$ têm momentos de segunda ordem, $XY$ tem [esperança](#def-b2-randomvar-expectation) e $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; consequentemente, $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ . 2. (Jensen) Se $\varphi \colon I \to \R$ é [convexa](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) num intervalo contendo $X(\Omega)$ e $X$, $\varphi(X)$ têm [esperança](#def-b2-randomvar-expectation), então $$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$$ **Demonstração.** *1.* [Somabilidade](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) de $XY$: $\abs{XY} \leq \frac{X^2 + Y^2}2$. A aplicação $(X, Y) \mapsto \E(XY)$ é uma [forma bilinear simétrica](https://one-course.com/books/math/4/pt/chapter/12-formas-quadraticas#def-b2-quadratic-def) 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](https://one-course.com/books/math/4/pt/chapter/12-formas-quadraticas#ch-b2-quadratic) se aplica (a positividade *semi*definida basta para a desigualdade). Aplicá-la às variáveis centradas dá a cota da [covariância](#def-b2-randomvar-variance). *2.* Primeiro, $m = \E(X)$ está em $I$: $I$ é um intervalo contendo todos os valores de $X$, e a [esperança](#def-b2-randomvar-expectation) é 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](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) ([Capítulo 8](https://one-course.com/books/math/4/pt/chapter/8-funcoes-de-uma-variavel-real#ch-b2-realfun)), existem $\alpha, \beta$ com $\varphi(t) \geq \alpha t + \beta$ para todo $t \in I$ e $\varphi(m) = \alpha m + \beta$. Então, [pontualmente](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def) em $\Omega$, $\varphi(X) \geq \alpha X + \beta$; tomando [esperanças](#def-b2-randomvar-expectation), $$ \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](#def-b2-randomvar-variance); 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) (ou ao menos [covariância](#def-b2-randomvar-variance) 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](#def-b2-randomvar-variance) só se somam sobre parcelas [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) (ou não correlacionadas). (iii) $\E(f(X))$ não é $f(\E(X))$; para $f$ [convexa](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex), Jensen até informa a direção do erro, como no [Exemplo 22.10](#ex-b2-randomvar-transferex). (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](#def-b2-randomvar-expectation), e não existe preço justo de entrada para o jogo. A [somabilidade](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) *absoluta* antes que qualquer rearranjo da soma sobre os valores seja legítimo ([Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)). **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](#def-b2-randomvar-variance) — 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](#ex-b2-randomvar-chebsharp) mostra que alguma tal variável o satura. A universalidade tem um preço; quando a [distribuição](#def-b2-randomvar-law) é 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) e identicamente distribuídas com [variância](#def-b2-randomvar-variance) $\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](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) 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](#def-b2-randomvar-law) de probabilidade é apenas um dispositivo de contabilidade para combinações [convexas](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) — o ponto de vista baricêntrico do [Capítulo 17](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#ch-b2-affine) 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](#def-b2-randomvar-law) [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) duas a duas com a mesma [lei](#def-b2-randomvar-law), 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](#thm-b2-randomvar-variancerules) (a [independência](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) dois a dois mata as [covariâncias](#def-b2-randomvar-variance)), $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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $A$ em repetições [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), $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](#def-b2-randomvar-law) *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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#thm-b2-funcseq-weierstrass) do teorema de aproximação de Weierstrass no [Capítulo 10](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#ch-b2-funcseq) — 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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-complete) são dominados por seu final de partida, e é por isso que o [Exercício 22.12](#exo-b2-randomvar-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 nnn?).** 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.](https://one-course.com/images/onecourse/chapters/math-4/b2-randomvar/fig-8fed2e7f1bf4.svg) *A lei dos grandes números em imagem: a [lei](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun): a [esperança](#def-b2-randomvar-expectation) $\E(t^X)$ de uma função astuciosa de $X$ empacota a [lei](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) se torna a multiplicatividade das [funções geradoras](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#ex-b2-powerseries-fibonacci). Para trás, a [esperança](#def-b2-randomvar-expectation) é um [baricentro](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-barycenter) com pesos de probabilidade ([Capítulo 17](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#ch-b2-affine)), a desigualdade de Jensen é a geometria da reta de apoio das funções [convexas](https://one-course.com/books/math/4/pt/chapter/17-espacos-afins#def-b2-affine-convex) ([Capítulo 8](https://one-course.com/books/math/4/pt/chapter/8-funcoes-de-uma-variavel-real#ch-b2-realfun)) 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 de Exercício 22.1.** *Binomial:* $X = \sum_{i=1}^n X_i$ com variáveis de Bernoulli [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) $X_i$; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$, e as [variâncias](#def-b2-randomvar-variance) de variáveis [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) se somam ([Teorema 22.14](#thm-b2-randomvar-variancerules)): $$ \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](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#ch-b2-powerseries)), $\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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence). Mostre que $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolução dos pesos; teorema binomial) e que a [lei](#def-b2-randomvar-law) condicional de $X$ dado $X + Y = n$ é binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$. **Solução de Exercício 22.2.** *Soma:* para $n \in \N$, por disjunção e [independência](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), $$ \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](#def-b2-randomvar-law) 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](#def-b2-randomvar-law) binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$: dada a contagem total, cada [evento](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) “escolhe” independentemente a primeira fonte com probabilidade proporcional à sua taxa. **Exercício 22.3 ★.** (Colecionador de cupons, [esperança](#def-b2-randomvar-expectation)) Uma marca de cereal esconde um de $n$ brindes distintos, [uniformemente](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def), 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) (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](https://one-course.com/books/math/4/pt/chapter/6-comparacao-de-funcoes#ch-b2-comparison)). **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](https://one-course.com/books/math/4/pt/chapter/6-comparacao-de-funcoes#ch-b2-comparison)). 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](#def-b2-randomvar-law) geométrica. **Solução de Exercício 22.4.** [Pontualmente](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def), $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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)) 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](#def-b2-randomvar-law) *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 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence). *[Covariância](#def-b2-randomvar-variance):* 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](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def)). 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](#thm-b2-randomvar-variancerules), $$ 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](#def-b2-randomvar-variance) que a amostragem com reposição (igualdade só para $n = 1$), agindo as correlações negativas como estabilizador. Para $n = N$ a [variância](#def-b2-randomvar-variance) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona, [Teorema 21.6](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#thm-b2-proba-continuity).)* **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](#def-b2-randomvar-expectation) é 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](#thm-b2-randomvar-markov)) dá $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ para todo $n$; os [eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ crescem para $\{X \neq m\}$, de modo que a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona ([Teorema 21.6](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#thm-b2-proba-continuity)) 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 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), $\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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) e $S_n \sim \mathcal{B}(n, x)$. Mostre que o [polinômio de Bernstein](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#thm-b2-funcseq-weierstrass) $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](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#ch-b2-funcseq) nessa linguagem probabilística (separe em $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ e use Chebyshev). **Solução de Exercício 22.8.** Pelo teorema de transferência ([Teorema 22.7](#thm-b2-randomvar-transfer)) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) $\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](#def-b2-randomvar-expectation) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) uniforme de $f$ em $[0, 1]$ faz $\omega_f(\delta) \to 0$: escolha $\delta$ e depois $n$, e $B_nf \to f$ [uniformemente](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def) — o teorema de aproximação de Weierstrass do [Capítulo 10](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#ch-b2-funcseq), cujo “lema de contagem” é agora reconhecível como a desigualdade de Chebyshev para a [lei](#def-b2-randomvar-law) binomial. **Exercício 22.9 ★★★.** ([Lei](#def-b2-randomvar-law) forte sob momentos de quarta ordem) Sejam $(X_k)$ [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#thm-b2-proba-borelcantelli)) que $S_n/n \to 0$ quase certamente, numa formulação adequada: o [evento](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ tem probabilidade $1$. **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](#def-b2-randomvar-expectation). Por [independência](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable). Por Borel–Cantelli 1 ([Teorema 21.25](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#thm-b2-proba-borelcantelli)), para cada $j$ o [evento](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable). 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](#exo-b2-randomvar-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 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](#def-b2-randomvar-variance) exatamente $1$, qualquer que seja $n$. **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](#def-b2-randomvar-variance) ([Teorema 22.14](#thm-b2-randomvar-variancerules)), $$ 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](#def-b2-randomvar-variance) $1$, independentemente de $n$ — coerente com o limite de Poisson do problema dos encontros ([Exercício 21.5](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#exo-b2-proba-5)). **Exercício 22.12 ★★★.** (Colecionador de cupons, concentração) No contexto do [Exercício 22.3](#exo-b2-randomvar-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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) das etapas geométricas e $V(\mathcal G(p)) = \frac{1-p}{p^2}$ ([Exercício 22.1](#exo-b2-randomvar-1); o valor $\pi^2/6$ é [Exemplo 14.12](https://one-course.com/books/math/4/pt/chapter/14-series-de-fourier#ex-b2-fourier-basel)). 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 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence). 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](https://one-course.com/books/math/4/pt/chapter/14-series-de-fourier#ex-b2-fourier-basel). Com $\E(T_n) = nH_n$, $H_n = \sum_1^n\frac1k$ ([Exercício 22.3](#exo-b2-randomvar-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](#ex-b2-randomvar-chebsharp) 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) 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}$. 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? 2. 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. 3. (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](#exo-b2-randomvar-7). 4. (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](#def-b2-randomvar-law) 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} .$$ 5. 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.** 6. (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!$). 7. Deduza, para variáveis de Rademacher [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) $\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)} .$$ 8. 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$ . 9. (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](https://one-course.com/books/math/4/pt/chapter/15-calculo-diferencial#def-b2-diffcalc-differential) 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](#def-b2-randomvar-variance)* de uma variável reponderada que ainda assume valores em $\intcc01$; majore-a por $\frac14$ (o argumento de minimalidade do [Exercício 22.6](#exo-b2-randomvar-6)) e conclua por Taylor: $$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$$ 10. (Desigualdade de Hoeffding) Para $X_i \in \intcc01$ [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) 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).$$ 11. 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) e uniformemente escolhidos; cada um responde honestamente; $p$ é a intenção verdadeira e $\widehat p_n$ é o número da pesquisa. 12. 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} .$$ 13. 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. 14. 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](#exo-b2-randomvar-5) : a [variância](#def-b2-randomvar-variance) encolhe por $\frac{N-n}{N-1}$ ). 15. (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. 16. O que a matemática *não* cobre: liste as hipóteses de modelagem usadas (amostragem uniforme [independente](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) , 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.** 17. (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](#def-b2-randomvar-variance). 18. (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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) a acontecer. 19. (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. 20. 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. 21. Monte a tabela da caixa de ferramentas: para Markov, Chebyshev, a cota de quarto momento do [Exercício 22.9](#exo-b2-randomvar-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.** 22. (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\%$ . 23. ( [Eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) raros pedem uma cota atenta à [variância](#def-b2-randomvar-variance) ) 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](#def-b2-randomvar-variance) verdadeira $p(1-p)$ ( $n \approx 7920$ ): a cota exponencial cega à [variância](#def-b2-randomvar-variance) 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](#def-b2-randomvar-variance) ; a aproximação de Poisson do [Capítulo 23](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun) ). 24. ( [Lei](#def-b2-randomvar-law) forte para moedas) A partir do $\sum_n 2\eu^{-2n\delta^2} < \infty$ e de Borel–Cantelli ( [Teorema 21.25](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#thm-b2-proba-borelcantelli) ), demonstre que $\widehat p_n \to p$ quase certamente para lançamentos de moeda [independentes](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) : formule o [evento](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) quase certo como $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ , como no [Exercício 22.9](#exo-b2-randomvar-9) , e conclua. (A limitação substitui o momento de quarta ordem usado lá.) 25. 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 de Problema 22.1.** **1.** $\E(S_n) = \frac n2$ e Markov ([Teorema 22.15](#thm-b2-randomvar-markov)) 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](https://one-course.com/books/math/4/pt/chapter/12-formas-quadraticas#def-b2-quadratic-adjoint) em torno de $n/2$ ($S_n$ e $n - S_n$ têm a mesma [lei](#def-b2-randomvar-law)), de modo que, com $x = n(a - \frac12) > 0$, os dois [eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $\{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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence) 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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), $\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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-compact) de $t$, por $\eu^{\abs t}\P(X = x)$ (pois $0 \leq x \leq 1$): pelo teorema de derivação para séries [normalmente](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-series) convergentes ([Teorema 10.7](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#thm-b2-funcseq-differentiation)) ela é duas vezes [diferenciável](https://one-course.com/books/math/4/pt/chapter/15-calculo-diferencial#def-b2-diffcalc-differential), 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](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-variance) de uma variável com valores em $\intcc01$ vale no máximo $\frac14$: pelo [Exercício 22.6](#exo-b2-randomvar-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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence), $\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](#def-b2-randomvar-variance) de uma moeda, não o tamanho do país. Reduzir a margem à metade custa quatro vezes a amostra — a [lei](#def-b2-randomvar-law) $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](#def-b2-randomvar-variance) é multiplicada por $\frac{N - n}{N-1} < 1$ ([Exercício 22.5](#exo-b2-randomvar-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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-topology) $\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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-independence). 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](#def-b2-randomvar-variance) — útil precisamente quando as parcelas são ilimitadas e Hoeffding não está disponível. **18.** Cauchy–Schwarz ([Teorema 22.19](#thm-b2-randomvar-jensen)): $$ \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](https://one-course.com/books/math/4/pt/chapter/12-formas-quadraticas#def-b2-quadratic-adjoint) 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](#ex-b2-randomvar-chebsharp)), e a melhor ferramenta na questão 23. Quarto momento ([Exercício 22.9](#exo-b2-randomvar-9)): decaimento $C/n^2$, [somabilidade](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-complete), 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](#def-b2-randomvar-variance) 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](#def-b2-randomvar-variance) 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](#def-b2-randomvar-variance) (desigualdade de Bernstein, terceiro ano) — ou, para [eventos](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) raros, a aproximação de Poisson demonstrada no [Capítulo 23](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun), 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](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#thm-b2-proba-borelcantelli)) dá $\P(\abs{\widehat p_n - p} \geq \delta \text{ infinitas vezes}) = 0$, isto é, o [evento](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#def-b2-proba-space) $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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) $\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](#exo-b2-randomvar-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](#def-b2-randomvar-law) quase certa; a limitação compra $\eu^{-2n\delta^2}$; e o momento exponencial [completo](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-complete) 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](#def-b2-randomvar-variance) 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](#def-b2-randomvar-law) limite exata com constantes explícitas — transformando toda cota deste problema numa igualdade assintótica.