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

22Probabilidade: fundamentos e a lei dos grandes números

O segundo ano construiu a probabilidade em espaços enumeráveis; a teoria da medida agora retira toda restrição. Um espaço de probabilidade é um espaço de medida de massa total $1$ , as variáveis aleatórias são aplicações mensuráveis, a esperança é a integral de Lebesgue — e, de imediato, todo o arsenal analítico (Capítulos 9, 10 e 11) se aplica ao acaso. Este capítulo instala o dicionário, constrói sequências infinitas de variáveis aleatórias independentes (em $\intcc01$ , a partir de dígitos binários: o acaso está escondido dentro da medida de Lebesgue), demonstra os lemas de Borel–Cantelli e a lei zero–um de Kolmogorov, organiza os modos de convergência e demonstra a lei dos grandes números — o teorema que faz as frequências convergirem às probabilidades e torna a estatística possível. O problema de fim de semana dá a demonstração de Etemadi da lei forte em sua forma definitiva $L^1$ .

22.1 O dicionário

Definição 22.1

Um espaço de probabilidade é um espaço de medida $(\Omega, \mathcal A, \P)$ com $\P(\Omega) = 1$ ; os elementos de $\mathcal A$ são eventos, e uma propriedade vale quase certamente (q.c.) se seu evento tem probabilidade $1$ . Uma variável aleatória é uma aplicação mensurável $X \colon \Omega \to \R$ (ou em $\R^d$ : um vetor aleatório); sua lei é a medida de probabilidade imagem $\P_X = X_*\P$ em $\R$ (Exercício 11.9), determinada pela função de distribuição $F_X(t) = \P(X \leq t)$ (Exercício 9.3). $X$ tem densidade $f$ se $\P_X = f\,\dd\lambda$ ; ela é discreta se $\P_X$ é uma combinação enumerável de massas de Dirac. A esperança é

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

e o teorema de transferência (Exercício 11.9) a calcula na lei: $\E[g(X)] = \int_\R g\,\dd\P_X$ — $= \sum g(x_k)p_k$ no caso discreto, $= \int g(x)f(x)\dd x$ no caso com densidade: as fórmulas do segundo ano, agora teoremas de uma única teoria. A variância é $\V(X) = \E[(X - \E X)^2] = \E[X^2] - (\E X)^2$ para $X \in L^2$ .

Exemplo 22.2

As leis padrão e suas transformadas notáveis: Bernoulli $\mathcal B(p)$ , binomial $\mathcal B(n, p)$ , geométrica, Poisson $\mathcal P(\lambda)$ (discretas: as tabelas do segundo ano continuam válidas); uniforme em $\intcc01$ (a própria medida de Lebesgue); exponencial $\mathcal E(\lambda)$ (densidade $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$ ); e a gaussiana $\mathcal N(m, \sigma^2)$ , de densidade $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x - m)^2}{2\sigma^2}\bigr)$ — uma densidade de probabilidade pelo Problema 10.1, de média $m$ e variância $\sigma^2$ (momentos gaussianos, Exercício 11.10).

Proposição 22.3 (Markov e Chebyshev)

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

Demonstração. Exercício 10.5(a); Chebyshev é Markov aplicado a $(X - \E X)^2$ . ∎

22.2 Independência

Definição 22.4

Sub- $\sigma$ -álgebras $\mathcal A_1, \dots, \mathcal A_n \subseteq \mathcal A$ são independentes se $\P(A_1\cap\dots\cap A_n) = \prod\P(A_i)$ para todos $A_i \in \mathcal A_i$ ; eventos são independentes se as $\sigma$ -álgebras $\{\varnothing, A_i, A_i^c, \Omega\}$ o forem; variáveis aleatórias $X_1, \dots, X_n$ , se as $\sigma$ -álgebras $\sigma(X_i) = X_i^{-1}(\mathcal B(\R))$ o forem. Uma família infinita é independente se toda subfamília finita o for.

Teorema 22.5

$X_1, \dots, X_n$ são independentes se, e somente se, a lei do vetor $(X_1, \dots, X_n)$ é a medida produto $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$ . Nesse caso, para $g_i \geq 0$ (ou tais que os produtos sejam integráveis):

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

em particular, $\E[XY] = \E X\,\E Y$ e $\V(X_1 + \dots + X_n) = \sum\V(X_i)$ para variáveis $L^2$ independentes.

Demonstração. Se as $X_i$ são independentes, as duas medidas de probabilidade $\P_{(X_1,\dots,X_n)}$ e $\bigotimes\P_{X_i}$ coincidem em todos os produtos $B_1\times\dots\times B_n$ de borelianos — um $\pi$ -sistema que gera $\mathcal B(\R^n)$ (Proposição 11.2(b)) —, logo em toda parte (Teorema 9.7). Reciprocamente, uma lei produto fatoriza todos os eventos $\bigcap_iX_i^{-1}(B_i)$ : independência. A fórmula da esperança é então Tonelli/Fubini (Teorema 11.5) através do teorema de transferência; $\E[XY] = \E X\E Y$ é o caso $g_i = \mathrm{id}$ , e expandir o quadrado dá a aditividade das variâncias (os termos cruzados $\E[(X_i - \E X_i)(X_j - \E X_j)] = 0$ ). ∎

Teorema 22.6 (Existência de sequências independentes)

Em $\bigl(\intcc01, \mathcal L, \lambda\bigr)$ existe uma sequência $(U_n)_{n\geq1}$ de variáveis aleatórias independentes, cada uma uniforme em $\intcc01$ . Consequentemente, para leis prescritas $(\mu_n)$ em $\R$ quaisquer, existem $(X_n)$ independentes com $\P_{X_n} = \mu_n$ .

Demonstração. Dígitos. Para $\omega \in \intcc01$ , sejam $(b_k(\omega))$ seus dígitos binários ( $\omega = \sum b_k2^{-k}$ ; escolha a expansão que não termina em uma sequência de $1$ — a ambiguidade envolve apenas um conjunto enumerável, logo nulo). Cada $b_k$ é variável aleatória ( $\{b_k = 1\}$ é uma reunião finita de intervalos diádicos), e o vetor $(b_1, \dots, b_m)$ assume cada valor de $\{0,1\}^m$ em um intervalo diádico de comprimento $2^{-m}$ : os $b_k$ são Bernoulli $(\frac12)$ independentes.

Reagrupamento. Separe $\N^*$ em infinitos conjuntos infinitos disjuntos $(I_n)$ (por exemplo, por potências de primos ou por diagonais); seja $(k^n_j)_j$ uma enumeração de $I_n$ e ponha

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

Cada $U_n$ é uniforme: seus dígitos binários são bits independentes e honestos, de modo que $\P(U_n \in [l2^{-m}, (l+1)2^{-m})) = 2^{-m}$ para todo intervalo diádico, e os intervalos diádicos determinam a lei (Teorema 9.7). Os $U_n$ são independentes: são funções de blocos disjuntos da família independente $(b_k)$ — formalmente, os eventos $\{U_n \in D_n\}$ para $D_n$ diádicos dependem de finitos dígitos de conjuntos disjuntos e se fatorizam; o argumento do $\pi$ -sistema eleva isso a todos os borelianos.

Leis arbitrárias. Seja $G_n(u) = \inf\{t : F_{\mu_n}(t) \geq u\}$ (a função quantil da função de distribuição $F_{\mu_n}$ ); a equivalência-chave $G_n(u) \leq t \iff u \leq F_{\mu_n}(t)$ (continuidade à direita de $F$ , monotonicidade) mostra que $X_n = G_n(U_n)$ é mensurável com $\P(X_n \leq t) = \P(U_n \leq F_{\mu_n}(t)) = F_{\mu_n}(t)$ : lei $\mu_n$ ; a independência é herdada (funções de variáveis independentes, Exercício 22.3). ∎

Exemplo 22.7 (O problema dos aniversários, honestamente)

Entre $n$ pessoas com aniversários independentes e uniformes em $N = 365$ dias, a probabilidade de que todos os aniversários difiram é

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

por condicionamentos sucessivos (ou diretamente: os $N(N-1)\cdots(N - n + 1)$ casos favoráveis sobre o total $N^n$ , um argumento de contagem que a fórmula do produto da independência torna rigoroso). Tomando logaritmos e usando $-\ln(1 - x) = x + O(x^2)$ :

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

O ponto de virada $p_n = \frac12$ fica em $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$ : para $N = 365$ , $n = 23$ ( $p_{23} = 0.4927$ ). Duas morais. Primeira: as colisões entre $n$ itens em $N$ caixas aparecem na escala $n \sim \sqrt N$ , e não $n \sim N$ — o escalamento do aniversário, que governa as colisões de hash e o custo $\sqrt N$ dos ataques de aniversário em criptografia. Segunda: o cálculo é um modelo: os $\binom n2$ eventos de colisão de pares não são independentes e, no entanto, a resposta se comporta como se fossem ( $\eu^{-\binom n2/N}$ é exatamente a heurística de pares independentes) — uma primeira instância da aproximação de Poisson, tornada rigorosa no problema de fim de semana do Capítulo 23 (desigualdade de Le Cam).

22.3 Borel–Cantelli e a lei zero–um

Teorema 22.8 (Borel–Cantelli)

Sejam $(A_n)$ eventos e $\limsup A_n = \bigcap_N \bigcup_{n\geq N}A_n$ (“ $A_n$ ocorre infinitas vezes”).

Se $\sum\P(A_n) < \infty$ , então $\P(\limsup A_n) = 0$ .
Se $\sum\P(A_n) = \infty$ e os $A_n$ são independentes, então $\P(\limsup A_n) = 1$ .

Demonstração. (1) é o Exercício 9.4. (2): para $N \leq M$ , a independência dos complementares (Exercício 22.3) dá

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

( $1 - x \leq \eu^{-x}$ ; a série diverge). Logo $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ para todo $N$ , e a interseção decrescente em $N$ continua tendo probabilidade $1$ (continuidade por cima, Proposição 9.6). ∎

Teorema 22.9 (Lei zero–um de Kolmogorov)

Sejam $(X_n)$ independentes e $\mathcal T = \bigcap_N\sigma(X_N, X_{N+1}, \dots)$ a $\sigma$ -álgebra caudal (eventos insensíveis a qualquer número finito dos $X_n$ : convergência de $\sum X_n$ , de $\frac{S_n}n$ , valores de $\limsup$ , …). Então todo $T \in \mathcal T$ tem $\P(T) \in \{0, 1\}$ .

Demonstração. Fixe $N$ . As $\sigma$ -álgebras $\sigma(X_1, \dots, X_N)$ e $\sigma(X_{N+1}, \dots)$ são independentes: eventos que dependem de blocos disjuntos se fatorizam nos $\pi$ -sistemas geradores (cilindros $\bigcap_{i\leq N}\{X_i \in B_i\}$ e condições finitas sobre as variáveis posteriores, respectivamente), e Dynkin (Teorema 9.4, aplicado duas vezes, um lado de cada vez) estende a fatoração. Um evento caudal $T$ está em $\sigma(X_{N+1}, \dots)$ para todo $N$ : $T$ é independente de todo $\sigma(X_1, \dots, X_N)$ , logo da $\sigma$ -álgebra que eles geram, $\sigma(X_1, X_2, \dots)$ (Dynkin mais uma vez: a reunião dos $\sigma(X_1,\dots,X_N)$ é um $\pi$ -sistema que a gera). Mas $T \in \sigma(X_1, X_2, \dots)$ também: $T$ é independente de si mesmo, $\P(T) = \P(T\cap T) = \P(T)^2$ : $\P(T) \in \{0, 1\}$ . ∎

22.4 Modos de convergência

Definição 22.10

$X_n \to X$ quase certamente se $\P(X_n \to X) = 1$ ; em probabilidade se $\P(\abs{X_n - X} \geq \varepsilon) \to 0$ para todo $\varepsilon > 0$ ; em $L^p$ se $\E\abs{X_n - X}^p \to 0$ .

Proposição 22.11

(a) a convergência q.c. implica a convergência em probabilidade; (b) a convergência $L^p$ implica a convergência em probabilidade; (c) a convergência em probabilidade implica a convergência q.c. ao longo de uma subsequência; (d) nenhuma outra implicação vale em geral.

Demonstração. (a) $\P(\abs{X_n - X} \geq \varepsilon) \leq \P\bigl(\sup_{m\geq n}\abs{X_m - X} \geq \varepsilon\bigr) \downarrow \P\bigl(\limsup\{\abs{X_m - X} \geq \varepsilon\}\bigr) = 0$ sob convergência q.c. (continuidade por cima; o evento limsup exclui a convergência). (b) Markov: $\P(\abs{X_n - X} \geq \varepsilon) \leq \varepsilon^{-p}\,\E\abs{X_n - X}^p$ . (c) Tome $n_k$ com $\P(\abs{X_{n_k} - X} \geq 2^{-k}) \leq 2^{-k}$ ; Borel–Cantelli (1) faz $\abs{X_{n_k} - X} < 2^{-k}$ a partir de certo índice, q.c. (d) A máquina de escrever (Exercício 12.3) em $(\intcc01, \lambda)$ converge em $L^1$ e em probabilidade, mas em ponto algum; $n\mathbf 1_{\intoo0{1/n}} \to 0$ q.c. mas não em $L^1$ ; os detalhes e os demais contraexemplos estão no Exercício 22.6. ∎

22.5 A lei dos grandes números

Ao longo de toda esta seção, $(X_n)$ são independentes de mesma lei (i.i.d.), com $S_n = X_1 + \dots + X_n$ .

Teorema 22.12 (Lei fraca dos grandes números)

Se $X_1 \in L^2$ , com $m = \E X_1$ :

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

$\frac{S_n}n \to m$ em probabilidade (e em $L^2$ ).

Demonstração. $\E\frac{S_n}n = m$ e $\V\bigl(\frac{S_n}n\bigr) = \frac{n\V(X_1)}{n^2}$ (Teorema 22.5); Chebyshev. ∎

Teorema 22.13 (Lei forte dos grandes números)

Se $X_1 \in L^1$ , então

\frac{S_n}{n} \xrightarrow[n\to\infty]{\text{q.c.}} \E[X_1].

Demonstramo-la aqui sob a hipótese mais forte $X_1 \in L^4$ ; o caso geral ( $L^1$ : a demonstração de Etemadi) é o problema de fim de semana.

Demonstração sob $\E X_1^4 < \infty$ . Centrando ( $X_i \mapsto X_i - m$ ), suponha $m = 0$ . Expanda:

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

pois a independência e a centragem matam todo termo que contenha um fator isolado ( $\E[X_iX_jX_kX_l] = \E[X_i]\E[\cdots] = 0$ , a menos que os índices se emparelhem: os únicos sobreviventes são os $n$ termos $i=j=k=l$ e os $3n(n-1)$ termos com dois pares distintos). Markov:

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

somável: Borel–Cantelli (1) dá, para cada racional $\varepsilon$ , que $\abs{S_n/n} < \varepsilon$ a partir de certo índice, q.c.; intersectando em $\varepsilon \in \Q_+^*$ (uma quantidade enumerável de eventos de probabilidade $1$ ): $S_n/n \to 0$ q.c. ∎

Exemplo 22.14 (O que a lei forte compra)

(a) Frequências: para lançamentos de moeda i.i.d., a frequência observada de caras converge q.c. a $p$ — a justificativa empírica da própria probabilidade. (b) Monte Carlo: para $g \in L^1(\intcc01)$ e $(U_n)$ i.i.d. uniformes (Teorema 22.6), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ q.c.: integrais por amostragem, em qualquer dimensão, à taxa $\sim n^{-1/2}$ independente da dimensão, tornada precisa no Capítulo 23. (c) Números normais: quase todo número real tem, em sua expansão binária, frequência assintótica $\frac12$ de uns (aplique a lei forte às variáveis dígito do Teorema 22.6) — o teorema de Borel, uma afirmação sobre os números de todo dia demonstrada por medida; o Problema 22.1 a completa em todas as bases.

Método 22.15

A ordem de trabalho para enunciados assintóticos sobre sequências aleatórias: (1) o evento é caudal? Então sua probabilidade é $0$ ou $1$ (Teorema 22.9), e resta apenas decidir qual. (2) Para demonstrar enunciados q.c.: Borel–Cantelli — somabilidade das probabilidades dos eventos “ruins”, via cotas do tipo Markov/Chebyshev sobre os momentos que existirem; a independência só é necessária na direção recíproca. (3) Subsequência + sanduíche: demonstre a convergência ao longo de uma subsequência tratável e controle a oscilação intermediária por monotonicidade ou desigualdades maximais — o esqueleto da demonstração de Etemadi. (4) Para limites em distribuição, espere o Capítulo 23.

22.6 Exercícios

Exercício 22.1 ★

(a) Seja $X$ com função de distribuição $F$ contínua e estritamente crescente. Mostre que $F(X)$ é uniforme em $\intcc01$ e que $G(U) \sim F$ para $U$ uniforme, $G = F^{-1}$ : simulação por inversão. (b) Calcule a função de distribuição e a densidade de $X^2$ para $X$ uniforme em $\intcc{-1}1$ , e de $-\frac1\lambda\ln U$ para $U$ uniforme em $\intoo01$ .

Solução

Solução de Exercício 22.1.

(a) Para $u \in \intoo01$ : $\P(F(X) \leq u) = \P(X \leq F^{-1}(u)) = F(F^{-1}(u)) = u$ (a continuidade e a monotonicidade estrita fazem de $F$ uma bijeção sobre $\intoo01$ com $\{F(X) \leq u\} = \{X \leq F^{-1}(u)\}$ ): $F(X)$ é uniforme. Reciprocamente, $\P(G(U) \leq t) = \P(U \leq F(t)) = F(t)$ : para simular uma lei, aplique a inversa da função de distribuição a uma amostra uniforme.

(b) $Y = X^2$ , $X$ uniforme em $\intcc{-1}1$ : para $t \in \intcc01$ , $F_Y(t) = \P(-\sqrt t \leq X \leq \sqrt t) = \sqrt t$ : densidade $\frac1{2\sqrt t}\mathbf 1_{\intoo01}$ . E $\P\bigl(-\frac1\lambda\ln U \leq t\bigr) = \P(U \geq \eu^{-\lambda t}) = 1 - \eu^{-\lambda t}$ : a exponencial $\mathcal E(\lambda)$ — a inversão em ação.

Exercício 22.2 ★

(a) Calcule a média e a variância das leis de Poisson $\mathcal P(\lambda)$ e geométrica via o teorema de transferência. (b) Mostre que uma variável aleatória positiva $T$ com $\P(T > t) > 0$ para todo $t$ satisfaz a propriedade de falta de memória $\P(T > t + s \mid T > t) = \P(T > s)$ para todos $s, t \geq 0$ se, e somente se, $T$ é exponencial. (A função de sobrevivência satisfaz a equação funcional de Cauchy; a monotonicidade substitui a continuidade.)

Solução

Solução de Exercício 22.2.

(a) Poisson: $\E X = \sum_{k\geq0}k\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \lambda$ , $\E[X(X-1)] = \lambda^2$ , de modo que $\V = \lambda^2 + \lambda - \lambda^2 = \lambda$ . Geométrica ( $\P(X = k) = p(1-p)^{k-1}$ ): $\E X = \frac1p$ , $\V = \frac{1-p}{p^2}$ (derive duas vezes a série geométrica).

(b) $G(t) = \P(T > t)$ é não crescente com $G(0^+)\dots$ $G \colon \intco0\infty \to \intoc01$ ; a ausência de memória se lê $G(t + s) = G(t)G(s)$ . Então $G(n t) = G(t)^n$ e $G(t/n) = G(t)^{1/n}$ : $G(q) = G(1)^q$ para $q \geq 0$ racionais; escrevendo $G(1) = \eu^{-\lambda}$ ( $\in \intoo01$ : $G(1) = 1$ forçaria $G \equiv 1$ , impossível para uma variável aleatória finita; $G(1) = 0$ está excluído por hipótese) e espremendo um $t$ arbitrário entre racionais (monotonicidade): $G(t) = \eu^{-\lambda t}$ — a lei exponencial. A recíproca é um cálculo.

Exercício 22.3 ★★

(a) Mostre que, se $X_1, \dots, X_n$ são independentes e as $f_i$ são funções borelianas, então as $f_i(X_i)$ são independentes. (b) Mostre que eventos $A_1, \dots, A_n$ são independentes se, e somente se, seus complementares o são, e se, e somente se, as indicadoras $\mathbf 1_{A_i}$ são variáveis aleatórias independentes. (c) (Duas a duas é mais fraco) Duas moedas honestas: $A =$ a primeira dá cara, $B =$ a segunda dá cara, $C =$ as duas coincidem. Mostre que $A, B, C$ são independentes duas a duas, mas não são independentes.

Solução

Solução de Exercício 22.3.

(a) $\sigma(f_i(X_i)) = f_i(X_i)^{-1}(\mathcal B) \subseteq X_i^{-1}(\mathcal B) = \sigma(X_i)$ ( $f_i$ borelianas), e sub- $\sigma$ -álgebras de $\sigma$ -álgebras independentes são independentes (a identidade que as define vale a fortiori).

(b) $\sigma(A_i) = \{\varnothing, A_i, A_i^c, \Omega\} = \sigma(A_i^c) = \sigma(\mathbf 1_{A_i})$ : as três afirmações asseguram a independência das mesmas $\sigma$ -álgebras. (Que a fatoração sobre os $A_i$ se propague aos complementares é o argumento de $\lambda$ -sistemas dentro da equivalência da Definição 22.4 — ou inclusão-exclusão direta.)

(c) $\P(A) = \P(B) = \P(C) = \frac12$ ; $A\cap B = A\cap C = B\cap C$ nos pares: cada interseção é “duas caras” ou análoga, de probabilidade $\frac14$ : independentes dois a dois. Mas $\P(A\cap B\cap C) = \P(\text{HH}) = \frac14 \neq \frac18$ : não independentes — $C$ é determinado por $A$ e $B$ .

Exercício 22.4 ★★

(a) (O macaco infinito) Uma sequência i.i.d. de teclas uniformes em um alfabeto finito contém q.c. todo texto finito infinitas vezes: demonstre-o com Borel–Cantelli (2) em blocos disjuntos. (b) (Corridas) Para bits honestos i.i.d., seja $R_n$ o comprimento da corrida de uns que começa na posição $n$ . Mostre que, q.c., $R_n \geq (1+\varepsilon)\log_2n$ apenas um número finito de vezes, e $R_n \geq \log_2 n$ infinitas vezes (as duas metades de Borel–Cantelli; para a segunda, passe a blocos disjuntos para ganhar independência): a corrida mais longa nos primeiros $n$ dígitos cresce como $\log_2n$ .

Solução

Solução de Exercício 22.4.

(a) Seja o texto $T$ de comprimento $L$ e $q = a^{-L}$ ( $a$ o tamanho do alfabeto). Os eventos $E_k = \{$ as posições $kL+1, \dots, (k+1)L$ soletram $T\}$ são independentes (blocos disjuntos de letras i.i.d.), cada um de probabilidade $q > 0$ : $\sum\P(E_k) = \infty$ , e Borel–Cantelli (2) dá uma infinidade de ocorrências q.c.

(b) Superior: $\P\bigl(R_n \geq (1+\varepsilon)\log_2n\bigr) \leq 2^{-(1+\varepsilon)\log_2n} = n^{-(1+\varepsilon)}$ , somável: por Borel–Cantelli (1), q.c. só finitos $n$ desses. Inferior: empacote blocos disjuntos — o $j$ -ésimo de comprimento $\ell_j = \lceil\log_2s_j\rceil$ começando em $s_j = \sum_{i<j}\ell_i$ ; os eventos “o bloco $j$ é só de uns” são independentes, de probabilidade $2^{-\ell_j} \asymp \frac1{s_j} \asymp \frac1{j\log_2 j}$ , cuja soma diverge: Borel–Cantelli (2) dá uma infinidade de blocos só de uns, isto é, $R_{s_j} \geq \log_2 s_j$ uma infinidade de vezes. Juntos: o comprimento máximo de uma sequência de uns nos $n$ primeiros dígitos é $(1 + o(1))\log_2n$ q.c.

Exercício 22.5 ★★

Sejam $(X_n)$ independentes. (a) Mostre que o raio de convergência de $\sum X_n z^n$ é uma constante q.c. (possivelmente $0$ ou $\infty$ ). (b) Mostre que $\P(\sum X_n \text{ converge}) \in \{0, 1\}$ e $\P(S_n/n \to m) \in \{0,1\}$ . (c) Dê um evento sobre $(X_n)$ que não seja caudal e verifique que a lei zero–um pode falhar para ele.

Solução

Solução de Exercício 22.5.

(a) $R = \bigl(\limsup\abs{X_n}^{1/n}\bigr)^{-1}$ não muda se finitos $X_n$ forem modificados: para todo $N$ , $R$ é $\sigma(X_N, X_{N+1}, \dots)$ -mensurável, isto é, mensurável na cauda. Então cada evento $\{R \leq c\}$ tem probabilidade $0$ ou $1$ (Teorema 22.9), de modo que a função de distribuição de $R$ assume apenas os valores $0, 1$ : ela salta num único ponto $c_0 \in \intcc0{+\infty}$ , e $R = c_0$ q.c.

(b) A convergência de $\sum X_n$ e a de $\frac{S_n}n$ são insensíveis à alteração de finitos termos (para a segunda: os termos modificados contribuem com $O(1/n) \to 0$ ): eventos de cauda; lei zero–um.

(c) $\{X_1 > 0\}$ depende de $X_1$ : para sinais i.i.d. ( $\P(X_1 = \pm1) = \frac12$ ), sua probabilidade vale $\frac12 \notin \{0,1\}$ — nenhuma contradição: não é evento de cauda.

Exercício 22.6 ★★

Em $(\intcc01, \lambda)$ , exiba — com demonstrações — variáveis aleatórias tais que: (a) $X_n \to 0$ em probabilidade e em todo $L^p$ , mas em ponto algum q.c.; (b) $X_n \to 0$ q.c. mas em nenhum $L^p$ ; (c) $X_n \to 0$ em $L^1$ mas não em $L^2$ ; (d) e mostre: se $X_n \to X$ em probabilidade e $\abs{X_n} \leq Y \in L^1$ , então $X_n \to X$ em $L^1$ (subsequências + convergência dominada + o truque da subsubsequência).

Solução

Solução de Exercício 22.6.

Trabalhe em $(\intcc01, \lambda)$ . (a) A máquina de escrever $\mathbf 1_{I_n}$ (Exercício 12.3): $\norm{X_n}_p^p = \lambda(I_n) \to 0$ (todo $p < \infty$ ), logo também em probabilidade; em todo $\omega$ os valores $0$ e $1$ recorrem ambos: nenhuma convergência pontual em parte alguma. (b) $X_n = n\mathbf 1_{\intoo0{1/n}} \to 0$ fora de $0$ , mas $\norm{X_n}_p \geq n^{1 - 1/p} \geq 1$ . (c) $X_n = \sqrt n\,\mathbf 1_{\intoo0{1/n}}$ : $\E\abs{X_n} = n^{-1/2} \to 0$ , $\E X_n^2 = 1$ . (d) De qualquer subsequência extraia (convergência em probabilidade) uma subsequência ulterior convergindo q.c. (Proposição 22.11(c)); a convergência dominada dá a convergência $L^1$ ao longo dela, com o mesmo limite $X$ . Assim, toda subsequência da sequência numérica $\E\abs{X_n - X}$ tem uma sub-subsequência tendendo a $0$ : a sequência inteira tende a $0$ .

Exercício 22.7 ★★

Uma pesquisa de opinião estima uma proporção desconhecida $p$ pela frequência empírica $\hat p_n$ de $n$ sorteios independentes. (a) Chebyshev: mostre que $\P(\abs{\hat p_n - p} \geq \varepsilon) \leq \frac1{4n\varepsilon^2}$ (use $p(1-p) \leq \frac14$ ). (b) Quantos sorteios garantem um erro $\leq 3\%$ com probabilidade $\geq 95\%$ por essa cota? (A resposta verdadeira, via o Capítulo 23, é cerca de $1070$ : Chebyshev é honesto, mas grosseiro.)

Solução

Solução de Exercício 22.7.

(a) $\hat p_n = \frac{S_n}n$ com $S_n$ binomial: $\V(\hat p_n) = \frac{p(1-p)}n \leq \frac1{4n}$ , e Chebyshev (Proposição 22.3) dá a cota. (b) Resolva $\frac1{4n(0.03)^2} \leq 0.05$ : $n \geq \frac{1}{4\cdot0.0009\cdot0.05} \approx 5556$ . O teorema central do limite justificará $n \approx 1070$ para a mesma garantia: Chebyshev paga sua generalidade com um fator $\approx 5$ .

Exercício 22.8 ★★★

(Bernstein) Para $f \in \mathcal C(\intcc01)$ , defina o polinômio de Bernstein $B_nf(x) = \sum_{k=0}^n\binom nkx^k(1-x)^{n-k}f\bigl(\frac kn\bigr)$ . (a) Reconheça $B_nf(x) = \E\bigl[f\bigl(\frac {S_n}n\bigr)\bigr]$ para $S_n$ binomial $\mathcal B(n, x)$ . (b) Demonstre $B_nf \to f$ uniformemente em $\intcc01$ : separe em $\{\abs{\frac{S_n}n - x} \leq \delta\}$ e seu complementar, usando a continuidade uniforme e Chebyshev com a cota uniforme $\V(\frac{S_n}n) \leq \frac1{4n}$ . (c) Conclua: uma segunda demonstração, probabilística, do teorema de aproximação de Weierstrass (Corolário 7.16), com a taxa explícita $\norm{B_nf - f}_\infty \leq \frac32\,\omega_f(n^{-1/2})$ para o módulo de continuidade $\omega_f$ — demonstre ao menos a forma $O(\omega_f(n^{-1/2}))$ .

Solução

Solução de Exercício 22.8.

(a) Se $S_n \sim \mathcal B(n, x)$ , o teorema de transferência dá $\E\bigl[f(\frac{S_n}n)\bigr] = \sum_k\binom nkx^k(1-x)^{n-k}f(\frac kn) = B_nf(x)$ .

(b)–(c) Seja $\omega = \omega_f$ o módulo de continuidade ( $\abs{f(u) - f(v)} \leq \omega(\abs{u - v})$ , e $\omega(c \delta) \leq (1 + c)\,\omega(\delta)$ encadeando passos). Então, para qualquer $\delta > 0$ ,

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

(se $\abs{u - x} \leq \delta$ , claro; caso contrário, $\omega(\abs{u-x}) \leq (1 + \frac{\abs{u-x}}\delta) \omega(\delta) \leq (1 + \frac{(u-x)^2}{\delta^2}) \omega(\delta)$ ). Tome esperanças em $u = \frac{S_n}n$ :

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

com $\delta = n^{-1/2}$ : $\norm{B_nf - f}_\infty \leq \frac54\,\omega\bigl(n^{-1/2}\bigr) \leq \frac32\,\omega\bigl(n^{-1/2}\bigr) \to 0$ (continuidade uniforme no compacto): um teorema de Weierstrass probabilístico, com taxa explícita e uniforme.

Exercício 22.9 ★★★

(Colecionador de figurinhas) Figurinhas de $n$ tipos são sorteadas uniformemente com reposição; seja $T_n$ o número de sorteios até que todos os tipos apareçam. (a) Escreva $T_n = \sum_{k=1}^{n}\tau_k$ com $\tau_k$ geométricas de parâmetro $\frac{n - k + 1}n$ , os $\tau_k$ independentes, e deduza $\E T_n = n\,H_n \sim n\ln n$ (com $H_n$ o número harmônico) e $\V(T_n) \leq \frac{\pi^2}6n^2$ . (b) Chebyshev: $\frac{T_n}{n\ln n} \to 1$ em probabilidade. (c) Refine com Borel–Cantelli: mostre diretamente que $\P(T_n > \beta n\ln n) \leq n^{1 - \beta}$ para $\beta > 1$ (cota da união sobre o evento de algum tipo faltar após $\beta n\ln n$ sorteios, usando $1 - x \leq \eu^{-x}$ ) e deduza que, ao longo de $n = 2^m$ , q.c. $T_n \leq \beta n\ln n$ a partir de certo índice, para todo $\beta > 2$ .

Solução

Solução de Exercício 22.9.

(a) Depois de $k - 1$ tipos coletados, cada sorteio é novo com probabilidade $p_k = \frac{n-k+1}n$ : $\tau_k$ é geométrica $(p_k)$ , e os $\tau_k$ são independentes (os sorteios o são). Somas: $\E T_n = \sum_k\frac n{n-k+1} = nH_n \sim n\ln n$ ; $\V(T_n) = \sum\frac{1 - p_k}{p_k^2} \leq n^2\sum_{j=1}^n\frac1{j^2} \leq \frac{\pi^2}6n^2$ .

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

(c) Cota da união: $T_n > t$ significa que algum tipo não foi visto após $\lceil t\rceil$ sorteios, de modo que $\P(T_n > t) \leq n(1 - \frac1n)^{t} \leq n\,\eu^{-t/n}$ ; em $t = \beta n\ln n$ : $\leq n^{1 - \beta}$ . Para $\beta > 1$ , $\sum_m 2^{m(1-\beta)} < \infty$ : Borel–Cantelli dá, ao longo de $n = 2^m$ , q.c. $T_n \leq \beta n\ln n$ a partir de certa ordem — em particular, para todo $\beta > 2$ como enunciado (qualquer $\beta > 1$ serve ao longo da subsequência).

Exercício 22.10 ★★

Usando a construção por dígitos (Teorema 22.6): (a) verifique por cálculo direto que $U = \sum b_{2k}2^{-k}$ (os dígitos de índice par de um $\omega$ uniforme) é uniforme e independente de $V = \sum b_{2k-1}2^{-k}$ ; (b) deduza uma bijeção mensurável a menos de conjuntos nulos entre $\intcc01$ e $\intcc01^2$ que preserva a medida, e comente: um único número aleatório uniforme contém dois (e enumeráveis) independentes — compare com a curva de Peano (Problema 6.1), que obteve sobrejetividade, mas não preservação de medida nem injetividade.

Solução

Solução de Exercício 22.10.

(a) Os dígitos de índice par $(b_{2k})_k$ são bits honestos i.i.d. (uma subfamília da família independente de dígitos), de modo que $U = \sum_kb_{2k}2^{-k}$ dá a todo intervalo diádico sua probabilidade correta (como no Teorema 22.6): uniforme; do mesmo modo $V$ ; e $(U, V)$ dependem de blocos de dígitos disjuntos: independentes (fatoração em retângulos diádicos, depois Dynkin).

(b) $\Phi(\omega) = (U(\omega), V(\omega))$ é mensurável com $\Phi_*\lambda = \lambda\otimes\lambda = \lambda_2$ (coincidência em retângulos diádicos + unicidade). Intercalar dígitos define uma inversa definida fora do conjunto (nulo) dos racionais diádicos em qualquer dos fatores: uma bijeção que preserva a medida entre subconjuntos de medida total de $\intcc01$ e $\intcc01^2$ . Contraste com Peano (Problema 6.1): a continuidade forçava a sobrejetividade sem a injetividade; trocar a continuidade pela mera mensurabilidade compra um isomorfismo de medida — a dimensão é invisível à teoria da medida e visível à topologia.

Exercício 22.11 ★★

(Recordes) Sejam $(X_n)_{n\geq1}$ i.i.d. com função de distribuição contínua, e diga que ocorre um recorde no instante $n$ se $X_n > \max(X_1, \dots, X_{n-1})$ (o instante $1$ é recorde). Seja $R_n$ a indicadora de recorde. (a) Mostre que $\P(R_n = 1) = \frac1n$ (por simetria, cada uma das $n!$ ordenações de $X_1, \dots, X_n$ é igualmente provável, e os empates têm probabilidade $0$ ). (b) Mostre que os $R_n$ são independentes (conte as ordenações compatíveis com posições de recorde prescritas, ou argumente que a ordem relativa de $X_1, \dots, X_{n-1}$ é independente do posto de $X_n$ entre eles). (c) Deduza de Borel–Cantelli (Teorema 22.8, as duas metades) que ocorrem infinitos recordes q.c., mas que recordes em instantes consecutivos $n, n+1$ ocorrem infinitas vezes com probabilidade — decida qual! — e calcule $\sum_n\P(R_n = 1, R_{n+1} = 1)$ .

Solução

Solução de Exercício 22.11.

(a) A continuidade da distribuição torna nulos os eventos de empate (como nos argumentos de estatísticas de ordem do capítulo), e as $n!$ ordenações relativas de $(X_1, \dots, X_n)$ são permutáveis, logo equiprováveis. $R_n = 1$ significa que o máximo ocupa a última posição: probabilidade $\frac{(n-1)!}{n!} = \frac1n$ .

(b) Fixe $n$ e condicione à ordenação relativa de $X_1, \dots, X_{n-1}$ : inserir $X_n$ nas $n$ posições de posto possíveis é uniforme e independente dessa ordenação (permutabilidade da $n$ -upla). Logo $R_n$ (o evento “ $X_n$ ocupa a primeira posição”) é independente de todo o histórico de recordes $(R_1, \dots, R_{n-1})$ , que é função da ordenação relativa das $n - 1$ primeiras variáveis. A indução dá a independência plena, com $\P(R_n = 1) = \frac1n$ .

(c) $\sum\P(R_n = 1) = \sum\frac1n = \infty$ com independência: a segunda metade de Borel–Cantelli dá recordes uma infinidade de vezes q.c. (os recordes nunca cessam — mas rareiam logaritmicamente: $\E[\#\text{recordes} \leq n] = H_n \approx \ln n$ ). Recordes consecutivos: $\P(R_n = R_{n+1} = 1) = \frac1{n(n+1)}$ (independência), e

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

a primeira metade de Borel–Cantelli se aplica — só finitos pares de recordes consecutivos ocorrem, q.c.

Exercício 22.12 ★★

(A corrida de caras mais longa) Lance uma moeda honesta infinitas vezes e seja $L_n$ o comprimento da maior corrida de caras consecutivas entre os primeiros $n$ lançamentos. (a) Mostre que, para todo $\varepsilon > 0$ , q.c. $L_n \leq (1 + \varepsilon)\log_2n$ a partir de certo índice (a probabilidade de alguma corrida de comprimento $\ell$ começar entre os primeiros $n$ lançamentos é no máximo $n2^{-\ell}$ ; Borel–Cantelli ao longo de $n = 2^k$ ). (b) Mostre que q.c. $L_n \geq (1 - \varepsilon)\log_2n$ a partir de certo índice (reparta os primeiros $n$ lançamentos em $\lfloor n/\ell\rfloor$ blocos disjuntos de comprimento $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ ; os blocos são independentes, cada um todo de caras com probabilidade $2^{-\ell}$ , e a probabilidade de nenhum ser todo de caras é no máximo $\exp(-n2^{-\ell}/\ell)$ ; some ao longo de $n = 2^k$ , de novo). (c) Conclua que $\frac{L_n}{\log_2n} \to 1$ q.c.: em um milhão de lançamentos honestos deve-se esperar uma corrida de cerca de $20$ caras — e um conjunto de dados sem ela provavelmente foi fabricado.

Solução

Solução de Exercício 22.12.

(a) Uma sequência de comprimento $\ell$ começando na posição $i \leq n$ tem probabilidade $2^{-\ell}$ ; cota da união: $\P(L_n \geq \ell) \leq n2^{-\ell}$ . Com $\ell_n = (1 + \varepsilon)\log_2n$ : $\P(L_n \geq \ell_n) \leq n^{-\varepsilon}$ . Ao longo de $n = 2^k$ : $\sum_k2^{-k\varepsilon} < \infty$ , de modo que q.c. $L_{2^k} < (1+\varepsilon)k$ a partir de certa ordem (Borel–Cantelli); para $n$ geral, tome $2^{k-1} < n \leq 2^k$ e use a monotonicidade de $L_n$ mais $\log_22^{k-1} \leq \log_2n$ : $L_n \leq L_{2^k} < (1 + \varepsilon)k \leq (1 + \varepsilon)\frac{k}{k-1} \log_2n$ , e o fator extra é absorvido aumentando ligeiramente $\varepsilon$ .

(b) Com $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ e $m = \lfloor n/\ell\rfloor$ blocos disjuntos: os blocos são independentes, cada um só de caras com probabilidade $2^{-\ell} \geq n^{-(1-\varepsilon)}/2$ , de modo que

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

para uma constante $c > 0$ e $n$ grande. Essas probabilidades são somáveis ao longo de $n = 2^k$ (de fato, ao longo de todos os $n$ ): Borel–Cantelli dá q.c. $L_n \geq (1 - \varepsilon)\log_2n$ a partir de certa ordem (a monotonicidade preenche entre os $2^k$ como em (a), inofensivamente).

(c) Ambas as cotas ao longo de uma sequência $\varepsilon = \frac1j$ , intersectando uma infinidade enumerável de eventos de medida total: $\frac{L_n}{\log_2n} \to 1$ q.c. Para $n = 10^6$ : $\log_2n \approx 19.9$ — uma sequência de $\approx 20$ caras não é uma anomalia suspeita, e sim uma certeza matemática, e sua ausência é indício de um humano forjando “aleatoriedade” (humanos raramente ousam escrever mais de $5$ ou $6$ caras seguidas).

22.7 Problema: a demonstração de Etemadi da lei forte

Problema 22.1

Problema de fim de semana — a lei forte dos grandes números para variáveis i.i.d. integráveis

A lei forte de Kolmogorov — $\frac{S_n}n \to \E X_1$ q.c. para $X_n \in L^1$ i.i.d. — teve por muito tempo apenas demonstrações intrincadas; em 1981, N. Etemadi encontrou uma de economia notável, que não usa nada além deste capítulo (e chega a enfraquecer a independência para independência duas a duas). Vamos segui-la. Sejam $(X_n)$ independentes duas a duas, de mesma lei, integráveis; $m = \E X_1$ , $S_n = X_1 + \dots + X_n$ .

Parte I — Reduções.

Mostre que basta tratar $X_n \geq 0$ (separe $X_n = X_n^+ - X_n^-$ : verifique que as duas metades são de novo i.i.d. integráveis e independentes duas a duas). Suponha daqui em diante $X_n \geq 0$ .
(Truncamento) Sejam $Y_n = X_n\,\mathbf 1_{X_n \leq n}$ e $S_n^* = Y_1 + \dots + Y_n$ . Mostre que

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

(Exercício 11.3) e deduza, via Borel–Cantelli, que $\frac{S_n - S_n^*}{n} \to 0$ q.c.: basta demonstrar $\frac{S^*_n}n \to m$ q.c.
Mostre que $\E Y_n = \E\bigl[X_1\mathbf 1_{X_1\leq n}\bigr] \to m$ (convergência monótona), logo $\frac1n\sum_{k\leq n}\E Y_k \to m$ (Cesàro): basta demonstrar $\frac{S_n^* - \E S_n^*}{n} \to 0$ q.c.

Parte II — A estimativa de variância.

Mostre que

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

e, usando o bolo de camadas (Proposição 11.8), a cota-chave

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

(troque a soma com a esperança — Tonelli para séries — e limite $\sum_{n \geq x}\frac1{n^2} \leq \frac2{\max(x,1)}$ para a estimativa interna $x^2\sum_{n\geq x}n^{-2} \leq 2x$ ).

Parte III — Convergência ao longo de subsequências geométricas. Fixe $\alpha > 1$ e ponha $k_j = \lfloor\alpha^j\rfloor$ .

Usando a independência duas a duas (as variâncias se somam, Teorema 22.5 — verifique que a aditividade das variâncias só precisa da independência duas a duas) e Chebyshev, mostre que, para todo $\varepsilon > 0$ :

$\sum_{j\geq1}\P\Bigl(\Bigl| \frac{S^*_{k_j} - \E S^*_{k_j}}{k_j}\Bigr| \geq \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j\geq1}\frac1{k_j^2} \sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_{n\geq1}\V(Y_n) \sum_{j\,:\,k_j\geq n}\frac1{k_j^2} .$
Mostre que $\sum_{j : k_j \geq n}k_j^{-2} \leq \frac{C_\alpha}{n^2}$ (série geométrica; cuidado com a parte inteira: $k_j \geq \frac{\alpha^j}2$ para o cuidado do tipo $\alpha^j \geq 2$ ) e conclua, com a questão 4 e Borel–Cantelli:

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

Parte IV — Sanduíche e conclusão.

Para $k_j \leq n \leq k_{j+1}$ , use a monotonicidade de $S^*_n$ (as parcelas são não negativas!) para mostrar

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

e deduza, q.c.:

$\frac m\alpha \leq \liminf\frac{S^*_n}n \leq \limsup\frac{S^*_n}n \leq \alpha\,m .$
Faça $\alpha \downarrow 1$ ao longo de uma sequência e conclua $\frac{S_n^*}n \to m$ q.c., logo (Parte I) a lei forte dos grandes números:

$\boxed{\ \frac{S_n}{n} \xrightarrow[n\to\infty]{\text{q.c.}} \E[X_1].\ }$
Onde exatamente a independência duas a duas (em vez da independência plena) foi suficiente? Liste os três pontos em que hipóteses do tipo independência foram invocadas.

Parte V — Dividendos.

(Números normais de Borel) Mostre que $\lambda$ -quase todo $x \in \intcc01$ é normal em toda base $b \geq 2$ : cada dígito $0, \dots, b-1$ aparece com frequência assintótica $\frac1b$ (fixe $b$ e um dígito, aplique a lei forte às variáveis indicadoras — justifique que os dígitos na base $b$ de uma variável uniforme são i.i.d. uniformes em $\{0,\dots,b-1\}$ , como no Teorema 22.6 — e intersecte os enumeráveis eventos de probabilidade um). Exiba um número explicitamente não normal e reflita: o teorema afirma a normalidade de quase todos os números e, no entanto, demonstrar a normalidade de $\sqrt2$ ou de $\pi$ continua em aberto.
(Monte Carlo, com garantia) Justifique por completo o método do Exemplo 22.14(b) para $g \in L^1(\intcc01^d)$ : construa a amostra uniforme i.i.d. em $\intcc01^d$ a partir do Teorema 22.6 e do Exercício 22.10, e enuncie o que a lei forte entrega.

Parte VI — O que a independência plena compra: desigualdades maximais e séries aleatórias. Etemadi gasta apenas a independência duas a duas; as partes restantes exploram a versão plena (mútua). Sejam $(Z_n)$ variáveis independentes centradas de $L^2$ e $S_k = Z_1 + \dots + Z_k$ (notação nova, sem relação com os $X_n$ acima).

(Desigualdade maximal de Kolmogorov) Para $\varepsilon > 0$ , demonstre

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

o preço de Chebyshev compra o máximo (reparta o evento segundo o primeiro índice $k$ com $\abs{S_k} \geq \varepsilon$ ; nessa peça, escreva $S_n^2 \geq S_k^2 + 2S_k(S_n - S_k)$ e use a independência das coalizões $(Z_1, \dots, Z_k)$ e $(Z_{k+1}, \dots, Z_n)$ , Teorema 22.5). Aponte o passo em que a independência duas a duas já não bastaria.
(Teorema de uma série de Khinchin–Kolmogorov) Deduza: se $\sum_n\V(Z_n) < \infty$ , então $\sum_nZ_n$ converge quase certamente (mostre que, q.c., as somas parciais formam uma sequência de Cauchy: faça $m \to \infty$ na desigualdade maximal aplicada a $Z_{N+1}, \dots, Z_{N+m}$ e, depois, faça $N \to \infty$ ).
(Séries de Rademacher) Sejam $(\varepsilon_n)$ sinais i.i.d., $\P(\varepsilon_n = \pm1) = \frac12$ (Teorema 22.6), e sejam $(x_n)$ números reais. Mostre que $\sum_nx_n\varepsilon_n$ converge q.c. assim que $\sum_nx_n^2 < \infty$ ; mostre também que, quaisquer que sejam os $(x_n)$ , a probabilidade de $\sum_nx_n\varepsilon_n$ convergir é $0$ ou $1$ (Teorema 22.9).
A recíproca, de maneira elementar. Ponha $T_n = \sum_{k\leq n}x_k\varepsilon_k$ e $s_n^2 = \sum_{k\leq n}x_k^2$ , e suponha $s_n \to \infty$ . (a) Demonstre a desigualdade de Paley–Zygmund: para $Z \geq 0$ com $\E Z^2 < \infty$ e $0 < \theta < 1$ ,

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

(separe $\E Z$ no nível $\theta\E Z$ e aplique Cauchy–Schwarz à peça superior). (b) Mostre que $\E T_n^4 \leq 3s_n^4$ . (c) Deduza $\P\bigl(\abs{T_n} > \frac{s_n}2\bigr) \geq \frac3{16}$ e conclua que $\sum_nx_n\varepsilon_n$ diverge q.c.; donde a dicotomia

$\sum_nx_n\varepsilon_n\ \text{converge q.c.} \iff \sum_nx_n^2 < \infty .$
(Série harmônica aleatória) Conclua que $\sum_n\frac{\varepsilon_n}{n^s}$ converge q.c. se, e somente se, $s > \frac12$ . Para $\frac12 < s \leq 1$ , a série converge q.c. enquanto $\sum_nn^{-s} = \infty$ : sinais aleatórios produzem cancelamento de intensidade raiz quadrada — compare com a série alternada $\sum_n\frac{(-1)^n}{n^s}$ , que converge para todo $s > 0$ .

Parte VII — Concentração: a desigualdade de Hoeffding. A lei forte diz que $\frac{S_n}n \to m$ ; as desigualdades de concentração dizem quão improvável é um desvio em cada $n$ fixado.

(Lema de Hoeffding) (a) Mostre que $\cosh\lambda \leq \eu^{\lambda^2/2}$ para todo $\lambda \in \R$ , comparando as duas séries termo a termo. (b) Seja $Z$ centrada com $a \leq Z \leq b$ , $a < b$ . Mostre que

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

(limite $\eu^{\lambda z}$ em $\intcc ab$ por sua corda, tome esperanças e estude $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ com $p = \frac{-a}{b-a}$ e $t = \lambda(b - a)$ : mostre que $\varphi(0) = \varphi'(0) = 0$ e $\varphi'' \leq \frac14$ ).
(Desigualdade de Hoeffding) Sejam $X_1, \dots, X_n$ independentes com $a_i \leq X_i \leq b_i$ e $S_n = X_1 + \dots + X_n$ . Demonstre, para $t > 0$ ,

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

e a mesma cota para a cauda inferior (Chebyshev exponencial: limite $\E\,\eu^{\lambda(S_n - \E S_n)}$ usando a independência e a questão 17 e, depois, otimize em $\lambda > 0$ ).
(A lei forte, caso limitado, com taxa) Sejam as $X_i$ i.i.d. com valores em $\intcc ab$ e $m = \E X_1$ . Mostre que

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

e recupere $\frac{S_n}n \to m$ q.c. por Borel–Cantelli: uma segunda demonstração da lei forte para variáveis limitadas — sem truncamento, com taxa exponencial em cada $n$ finito, mas com parcelas limitadas e independência plena. Compare as hipóteses com as de Etemadi.
(Monte Carlo, com garantia em $n$ fixado) Sejam $g \colon \intcc01^d \to \intcc01$ mensurável e $(U_k)$ a amostra uniforme i.i.d. da questão 11. Dado $\varepsilon, \delta > 0$ , mostre que

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

e avalie o limiar para $\varepsilon = \delta = 10^{-2}$ . A cota não envolve $d$ : compare com a questão 11 e com as grades determinísticas.

Parte VIII — Qual é o tamanho de um passeio aleatório? Rumo ao logaritmo iterado. Seja $S_n = \varepsilon_1 + \dots + \varepsilon_n$ o passeio aleatório simples construído a partir de sinais honestos i.i.d.

(Caudas sub-gaussianas) Mostre que $\E\,\eu^{\lambda S_n} = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ e deduza, para $x > 0$ ,

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

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

(para $\eta > 0$ , some as cotas de cauda em $x = (1 + \eta)\sqrt{2n\log n}$ e, depois, intersecte em $\eta = \frac1p$ ). Em particular, o passeio vive na escala do teorema central do limite, $\sqrt n$ , a menos de um fator logarítmico — muito abaixo da cota grosseira $\abs{S_n} \leq n$ .
Ao longo da subsequência de dobramento $n_j = 2^j$ , mostre que

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

e reflita: a lei do logaritmo iterado (Khinchin; Hartman–Wintner para parcelas $L^2$ centradas gerais) afirma que

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

Explique com precisão o que separa a estimativa em subsequência que acabamos de demonstrar da metade superior desse enunciado (é preciso controlar $\max_{n_j \leq n \leq n_{j+1}}S_n$ dentro de cada bloco, o que exige uma desigualdade maximal em escala exponencial) e verifique quantitativamente que a desigualdade da questão 12 é fraca demais para esse fim. A metade inferior repousa sobre o segundo lema de Borel–Cantelli aplicado a blocos independentes; as duas metades são material honesto de terceiro ano para um curso dedicado de probabilidade.
(Desvio uniforme sobre uma classe finita) Sejam $A_1, \dots, A_N$ eventos de um experimento repetível, e estime cada probabilidade por sua frequência empírica $\hat p_i$ em $n$ repetições i.i.d. Combinando a desigualdade de Hoeffding com uma cota da união, mostre que

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

e deduza a regra de tamanho de amostra: $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ garante que as $N$ estimativas sejam simultaneamente $\varepsilon$ -precisas com probabilidade $\geq 1 - \delta$ . Calcule $n$ para $N = 10^6$ , $\varepsilon = 0.01$ , $\delta = 0.05$ : o preço logarítmico da uniformidade.
(A janela harmônica aleatória) Combinando as duas metades da teoria de séries aleatórias, mostre que, para sinais i.i.d. $(\varepsilon_n)$ , a série $\sum_n\frac{\varepsilon_n}{n^\alpha}$ converge q.c. se $\alpha > \frac12$ e diverge q.c. se $\alpha \leq \frac12$ ; contraste com a convergência absoluta (que exige $\alpha > 1$ ): na janela $\alpha \in \intoc{\frac12}1$ , a convergência é um fenômeno genuinamente probabilístico — cancelamento, não tamanho.

Solução

Solução de Problema 22.1.

1. $X_n^{\pm}$ são funções borelianas de $X_n$ : elas permanecem independentes dois a dois (Exercício 22.3(a)) e identicamente distribuídas, integráveis, com $\E X_1 = \E X_1^+ - \E X_1^-$ . Se o teorema vale para variáveis não negativas, aplique-o às duas metades e subtraia: $\frac{S_n}n = \frac{S_n^+}n - \frac{S_n^-}n \to \E X_1^+ - \E X_1^- = m$ q.c.

2. $\P(X_n \neq Y_n) = \P(X_n > n) = \P(X_1 > n)$ (leis idênticas), e $\sum_n\P(X_1 > n) \leq \sum_n\P(X_1 \geq n) \leq \E X_1 < \infty$ (Exercício 11.3(a)). Borel–Cantelli (1): q.c. $X_n = Y_n$ para todo $n$ grande, de modo que $S_n - S_n^*$ é constante em $n$ a partir de certa ordem: $\frac{S_n - S_n^*}n \to 0$ q.c., e as duas somas normalizadas partilham o comportamento assintótico.

3. $X_1\mathbf 1_{X_1 \leq n} \nearrow X_1$ : o TCM dá $\E Y_n \to m$ ; as médias de Cesàro de uma sequência convergente convergem ao mesmo limite: $\frac{\E S_n^*}n = \frac1n\sum_{k\leq n}\E Y_k \to m$ . Logo basta demonstrar $\frac{S^*_n - \E S^*_n}{n} \to 0$ q.c.

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

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

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

5. A independência dois a dois dá $\E[(Y_i - \E Y_i)(Y_j - \E Y_j)] = 0$ para $i \neq j$ (a fórmula do produto para duas variáveis), de modo que as variâncias se somam: $\V(S^*_k) = \sum_{n\leq k}\V(Y_n)$ . Chebyshev em cada $k_j$ e somando:

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

(Tonelli para a série dupla não negativa).

6. $k_j = \lfloor\alpha^j\rfloor \geq \frac{\alpha^j}2$ (válido assim que $\alpha^j \geq 1$ , isto é, para todo $j \geq 0$ : $\lfloor x\rfloor \geq \frac x2$ para $x \geq 1$ ). Logo

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

(série geométrica a partir do primeiro $j$ com $\alpha^j \geq n$ ). Combinando com as questões 4–5, a soma dupla é finita; Borel–Cantelli (1), aplicado para cada $\varepsilon$ racional e intersectado, dá $\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \to 0$ q.c. e, com a questão 3: $\frac{S^*_{k_j}}{k_j} \to m$ q.c.

7. $Y_n \geq 0$ torna $n \mapsto S^*_n$ não decrescente: para $k_j \leq n \leq k_{j+1}$ ,

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

que é o sanduíche em destaque após inserir $\frac{k_j}{k_{j+1}}$ e $\frac{k_{j+1}}{k_j}$ . Como $\frac{k_{j+1}}{k_j} \to \alpha$ , a questão 6 dá q.c.

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

8. Aplique a questão 7 para $\alpha = 1 + \frac1p$ , $p \in \N^*$ : uma infinidade enumerável de eventos q.c.; em sua interseção, fazendo $p \to \infty$ : $\lim\frac{S^*_n}n = m$ q.c. Com as questões 1–3, $\frac{S_n}n \to \E X_1$ q.c.: a lei forte dos grandes números, sob independência dois a dois.

9. As hipóteses do tipo independência apareceram três vezes: (i) a aditividade das variâncias (questão 5) — a independência dois a dois basta; (ii) a distribuição idêntica, nas somas truncadas (questão 2) e no cálculo da média (questão 3) — nenhuma independência; (iii) Borel–Cantelli (1) (questões 2 e 6) — válido sem independência alguma. A independência mútua plena nunca foi invocada: a observação de Etemadi.

10. Fixe uma base $b$ e um dígito $r$ . Os dígitos na base $b$ $(d_k)$ de um $\omega$ uniforme são i.i.d. uniformes em $\{0, \dots, b-1\}$ (cada valor do vetor de dígitos ocupa um intervalo de comprimento $b^{-m}$ : o argumento do Teorema 22.6 literalmente). A lei forte aplicada às variáveis i.i.d. limitadas $\mathbf 1_{d_k = r}$ dá: q.c., a frequência do dígito $r$ tende a $\frac1b$ . Intersectando sobre a infinidade enumerável de pares $(b, r)$ : quase todo número é simplesmente normal em toda base. Um número não normal explícito: $x = 0.100100100\ldots_2$ (frequência de uns $\frac13 \neq \frac12$ ). O contraste é humilhante: quase todos os números são normais e, no entanto, para $\sqrt2$ , $\eu$ ou $\pi$ a normalidade permanece indemonstrada — a teoria da medida conta sem exibir.

11. Pelo Exercício 22.10 iterado, uma única variável uniforme fornece uma sequência de vetores uniformes i.i.d. $U_k$ em $\intcc01^d$ (reparta o conjunto de dígitos de cada $U_n$ do Teorema 22.6 em $d$ subfamílias). Para $g \in L^1(\intcc01^d)$ , as variáveis $g(U_k)$ são i.i.d. integráveis de média $\int g\,\dd\lambda_d$ (transferência): a lei forte dá

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

A integração de Monte Carlo converge quase certamente, em toda dimensão — o tamanho do erro é assunto do teorema central do limite (Capítulo 23).

12. Seja $A_k = \{\abs{S_k} \geq \varepsilon\} \cap \bigcap_{j<k}\{\abs{S_j} < \varepsilon\}$ : os $A_k$ são disjuntos, de união $A = \{\max_{k\leq n}\abs{S_k} \geq \varepsilon\}$ . Então

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

porque o termo cruzado se anula: $S_k\mathbf 1_{A_k}$ é função boreliana da coalizão $(Z_1, \dots, Z_k)$ , que é independente de $S_n - S_k$ , função de $(Z_{k+1}, \dots, Z_n)$ (Teorema 22.5), de modo que $\E[S_k\mathbf 1_{A_k}(S_n - S_k)] = \E[S_k\mathbf 1_{A_k}]\,\E[S_n - S_k] = 0$ . Em $A_k$ , $S_k^2 \geq \varepsilon^2$ , donde $\E S_n^2 \geq \varepsilon^2\sum_k\P(A_k) = \varepsilon^2\P(A)$ ; e $\E S_n^2 = \sum_{k\leq n}\V(Z_k)$ (as variâncias se somam). O passo decisivo é a fatoração: $S_k\mathbf 1_{A_k}$ é função não linear de todo o primeiro bloco, e sua independência do segundo bloco é a independência por coalizões — a independência dois a dois dos $Z_i$ apenas descorrelaciona pares e não a justificaria.

13. Fixe $N$ e aplique a questão 12 a $Z_{N+1}, \dots, Z_{N+m}$ :

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

Os eventos crescem com $m$ ; a continuidade por baixo dá $\P(\sup_{k>N}\abs{S_k - S_N} > \varepsilon) \leq r_N/\varepsilon^2$ , e $r_N \to 0$ por hipótese. Logo, para cada $p \in \N^*$ , $\P\bigl(\bigcap_N\{\sup_{k>N} \abs{S_k - S_N} > \frac1p\}\bigr) \leq \inf_Np^2r_N = 0$ : quase certamente, para todo $p$ existe $N$ com $\sup_{k>N}\abs{S_k - S_N} \leq \frac1p$ (intersecte a infinidade enumerável de eventos q.c. sobre $p$ ), de modo que $\abs{S_k - S_l} \leq \frac2p$ para todo $k, l > N$ : as somas parciais são q.c. de Cauchy, logo q.c. convergentes.

14. As variáveis $Z_n = x_n\varepsilon_n$ são independentes (funções borelianas de variáveis independentes, Exercício 22.3(a)), centradas, com $\V(Z_n) = x_n^2$ : a questão 13 se aplica quando $\sum_nx_n^2 < \infty$ e dá a convergência q.c. Em geral, para cada $N$ a convergência de $\sum_nx_n\varepsilon_n$ não é afetada pelos valores de $\varepsilon_1, \dots, \varepsilon_N$ : o evento de convergência está na $\sigma$ -álgebra de cauda da sequência independente $(\varepsilon_n)$ , de modo que a lei zero–um de Kolmogorov (Teorema 22.9) força sua probabilidade a ser $0$ ou $1$ .

15. (a) Separando no nível $\theta\E Z$ e usando Cauchy–Schwarz na peça superior,

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

de modo que $(1 - \theta)\E Z \leq \sqrt{\E Z^2\,\P(Z > \theta\E Z)}$ ; eleve ao quadrado. (b) Expanda $T_n^4 = \sum_{i,j,k,l}x_ix_jx_kx_l\, \E[\varepsilon_i\varepsilon_j\varepsilon_k\varepsilon_l]$ : a esperança vale $1$ quando os índices se emparelham (todos os quatro iguais, ou dois pares distintos, este último em $3$ arranjos) e $0$ nos demais casos (um sinal desemparelhado tem média nula e se fatora por independência). Logo

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

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

Se a série convergisse com probabilidade positiva, ela convergiria q.c. (questão 14), de modo que $\sup_n\abs{T_n} < \infty$ q.c., e algum $M$ satisfaria $\P(\sup_n\abs{T_n} > M) < \frac3{16}$ ; mas, assim que $s_n > 2M$ , $\P(\abs{T_n} > M) \geq \P(\abs{T_n} > \frac{s_n}2) \geq \frac3{16}$ : contradição. Logo a divergência é quase certa e, com a questão 14, a dicotomia está completa.

16. Aqui $x_n = n^{-s}$ e $\sum_nn^{-2s} < \infty$ exatamente quando $s > \frac12$ : pelas questões 14–15, $\sum_n\frac{\varepsilon_n}{n^s}$ converge q.c. se, e somente se, $s > \frac12$ (para $s \leq \frac12$ , divergência q.c.). Para $\frac12 < s \leq 1$ a convergência nunca é absoluta. A comparação é instrutiva: sinais perfeitamente alternados se cancelam na força $n^{-s}$ para todo $s > 0$ , ao passo que sinais aleatórios típicos se cancelam apenas na força da raiz quadrada — o passeio aleatório da questão 21 cresce como $\sqrt n$ , e a soma de Abel converte exatamente esse crescimento em convergência de $\sum\varepsilon_nn^{-s}$ para $s > \frac12$ .

17. (a) $\cosh\lambda = \sum_k\frac{\lambda^{2k}}{(2k)!}$ e $\eu^{\lambda^2/2} = \sum_k\frac{\lambda^{2k}}{2^kk!}$ ; e $(2k)! \geq 2^kk!$ vale termo a termo, pois $\frac{(2k)!}{k!} = \prod_{i=1}^k(k + i) \geq \prod_{i=1}^k(2i) = 2^kk!$ (cada fator satisfaz $k + i \geq 2i$ para $i \leq k$ ), de modo que, de fato, $(2k)! \geq 2^k(k!)^2 \geq 2^kk!$ . (b) Note $a \leq 0 \leq b$ ( $Z$ é centrada) e, pela convexidade de $z \mapsto \eu^{\lambda z}$ , para $z \in \intcc ab$ :

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

com $p = \frac{-a}{b-a} \in \intcc01$ , $t = \lambda(b - a)$ , $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ . Então $\varphi(0) = 0$ , $\varphi'(t) = -p + \frac{p\eu^t}{1 - p + p\eu^t}$ se anula em $0$ e $\varphi''(t) = \rho(1 - \rho) \leq \frac14$ para $\rho = \frac{p\eu^t}{1 - p + p\eu^t} \in \intcc01$ : Taylor de ordem $2$ dá $\varphi(t) \leq \frac{t^2}8 = \frac{\lambda^2(b-a)^2}8$ .

18. Para $\lambda > 0$ , Markov aplicado à variável positiva $\eu^{\lambda(S_n - \E S_n)}$ (Proposição 22.3) e a fórmula do produto para variáveis independentes dão

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

pela questão 17(b) aplicada a cada $X_i - \E X_i \in \intcc{a_i - \E X_i}{b_i - \E X_i}$ centrada (mesma largura). Minimizando o expoente em $\lambda = \frac{4t}{D}$ , $D = \sum_i(b_i - a_i)^2$ , obtém-se $-\frac{2t^2}D$ . A cauda inferior segue aplicando o resultado a $(-X_i)$ .

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

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

que é somável em $n$ (uma série do tipo geométrico): Borel–Cantelli (Teorema 22.8) dá que q.c. $\abs{\frac{S_n}n - m} < \varepsilon$ a partir de certa ordem; intersectando sobre $\varepsilon = \frac1p$ , obtém-se $\frac{S_n}n \to m$ q.c. Comparação: Etemadi pede apenas $X_1 \in L^1$ e independência dois a dois, e não fornece taxa; Hoeffding pede limitação e independência plena, e fornece uma garantia exponencial explícita em todo $n$ finito — os dois teoremas respondem a perguntas diferentes sobre o mesmo limite.

20. As $g(U_k)$ são i.i.d. com valores em $\intcc01$ e média $\int g\,\dd\lambda_d$ (transferência), de modo que a questão 18 com $b_i - a_i = 1$ , $t = n\varepsilon$ dá a cota bilateral $2\eu^{-2n\varepsilon^2} \leq \delta$ assim que $\eu^{2n\varepsilon^2} \geq \frac2\delta$ , isto é, $n \geq \frac{\log(2/\delta)}{2\varepsilon^2}$ . Para $\varepsilon = \delta = 10^{-2}$ :

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

cerca de $26\,500$ amostras garantem $1\%$ de precisão com $99\%$ de confiança — em toda dimensão $d$ , para todo integrando mensurável com valores em $\intcc01$ . A lei forte da questão 11 prometia convergência sem garantia alguma em $n$ finito; uma malha determinística com $k$ pontos por eixo custa $k^d$ avaliações, exponencial em $d$ . A concentração é o que faz de Monte Carlo um método e não uma esperança.

21. Independência e a fórmula do produto: $\E\,\eu^{\lambda S_n} = (\E\,\eu^{\lambda\varepsilon_1})^n = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ pela questão 17(a). Markov em $\eu^{\lambda S_n}$ :

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

e a cota simétrica para $-S_n$ (mesma lei) duplica a constante para $\abs{S_n}$ .

22. Fixe $\eta > 0$ e ponha $x_n = (1 + \eta)\sqrt{2n\log n}$ para $n \geq 2$ :

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

somável, já que $(1 + \eta)^2 > 1$ . Borel–Cantelli: q.c. $\abs{S_n} < (1 + \eta)\sqrt{2n\log n}$ para todo $n$ grande, de modo que $\limsup_n\frac{\abs{S_n}}{\sqrt{2n\log n}} \leq 1 + \eta$ q.c.; intersectar os eventos q.c. para $\eta = \frac1p$ , $p \in \N^*$ , dá o afirmado. O passeio de tamanho $n$ tem amplitude típica $\sqrt n$ (sua variância), e mesmo suas piores excursões excedem essa escala em, no máximo, $\sqrt{2\log n}$ .

23. Com $n_j = 2^j$ e $x = (1 + \eta)\sqrt{2n_j\log\log n_j}$ (definido para $j \geq 2$ ), a questão 21 dá

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

somável em $j$ , pois $(1 + \eta)^2 > 1$ : Borel–Cantelli e $\eta = \frac1p$ dão $\limsup_jS_{n_j}/\sqrt{2n_j \log\log n_j} \leq 1$ q.c. O que falta para a metade superior completa é a ponte entre os pontos de controle: é preciso mostrar que $\max_{n_j\leq n\leq n_{j+1}}S_n$ excede $(1+\eta)\sqrt{2n_j\log\log n_j}$ apenas finitas vezes, o que exige uma desigualdade maximal com caudas gaussianas (a desigualdade de reflexão de Lévy ou a desigualdade de Ottaviani, não demonstradas aqui). A questão 12 é quantitativamente fraca demais: ela limita a probabilidade por

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

que tende a $0$ , mas não é somável em $j$ : Borel–Cantelli não consegue concluir. A metade inferior da lei do logaritmo iterado aplica o segundo lema de Borel–Cantelli aos incrementos independentes $S_{n_{j+1}} - S_{n_j}$ , usando cotas inferiores correspondentes para caudas de tipo gaussiano. Ambos os refinamentos são probabilidade genuína do terceiro ano, um curso adiante; o que este problema entrega sem auxílio é a escala exata do logaritmo iterado ao longo de tempos geométricos.

24. Cada $\hat p_i$ é uma média de $n$ variáveis indicadoras i.i.d. com valores em $\intcc01$ e média $\P(A_i)$ : Hoeffding dá $\P(\abs{\hat p_i - \P(A_i)} > \varepsilon) \leq 2\eu^{-2n\varepsilon^2}$ . A cota da união multiplica por $N$ . Resolvendo $2N\eu^{-2n\varepsilon^2} \leq \delta$ : $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ . Numericamente: $\ln\frac{2\cdot10^6}{0.05} = \ln(4\cdot10^7) \approx 17.5$ , de modo que $n \geq \frac{17.5}{2\cdot10^{-4}} \approx 87\,600$ : estimar uma probabilidade com $\pm1\%$ exige cerca de $18\,500$ amostras ( $\ln(2/\delta)/2\varepsilon^2$ ), e um milhão de probabilidades apenas $\approx 4.7$ vezes mais — a uniformidade custa $\ln N$ , não $N$ : a observação que torna a minimização do risco empírico, e com ela o aprendizado de máquina, estatisticamente possível.

25. As variáveis $X_n = \frac{\varepsilon_n} {n^\alpha}$ são independentes, centradas, limitadas, com $\sum_n\V(X_n) = \sum_nn^{-2\alpha}$ . Se $\alpha > \frac12$ : a série das variâncias converge, e o teorema de uma série (Parte VI) dá a convergência q.c. de $\sum X_n$ . Se $\alpha \leq \frac12$ : a série das variâncias diverge, e a metade recíproca (o argumento de Paley–Zygmund da Parte VI, aplicável já que as parcelas são limitadas por $1$ ) dá a divergência q.c. A convergência absoluta pede $\sum n^{-\alpha} < \infty$ : $\alpha > 1$ . Em $\intoc{\frac12}1$ , a série converge q.c. embora $\sum\abs{X_n} = \infty$ com certeza: os sinais conspiram para se cancelar, com probabilidade um — convergência por cancelamento, invisível a qualquer teste absoluto e, pela lei zero–um, com um veredicto determinístico ainda assim.