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

21Probabilidade em espaços enumeráveis

Os três últimos capítulos desenvolvem a teoria moderna da probabilidade: medidas de probabilidade em espaços amostrais enumeráveis, variáveis aleatórias discretas e funções geradoras. A teoria finita do volume do ensino médio adquire sua infraestrutura completa: a $\sigma$ -aditividade substitui a aditividade finita, e a maquinaria das famílias somáveis do Capítulo 7 é exatamente o que torna manejáveis os espaços amostrais infinitos. Os resultados centrais aqui são a continuidade da probabilidade ao longo de sequências monótonas de eventos e o lema de Borel–Cantelli.

21.1 Espaços de probabilidade

Definição 21.1 (Espaço de probabilidade enumerável)

Seja $\Omega$ um conjunto não vazio, finito ou enumerável (o espaço amostral). Uma medida de probabilidade em $\Omega$ é uma aplicação $\P$ do conjunto $\mathcal{P}(\Omega)$ de todos os subconjuntos de $\Omega$ (os eventos) em $[0, 1]$ tal que:

$\P(\Omega) = 1$ ;
( $\sigma$ -aditividade) para toda sequência $(A_n)_{n\in\N}$ de eventos dois a dois disjuntos,

$\P\Bigl(\,\bigcup_{n \in \N} A_n\Bigr) = \sum_{n=0}^{\infty} \P(A_n) .$

O par $(\Omega, \P)$ é um espaço de probabilidade (enumerável).

Observação 21.2

Num $\Omega$ enumerável podemos tomar todos os subconjuntos como eventos; em espaços não enumeráveis (como é preciso para os modelos contínuos do terceiro ano) isso já não é possível, e restringe-se $\P$ a uma coleção adequada de eventos, uma $\sigma$ -álgebra. Todas as fórmulas deste capítulo sobrevivem literalmente a essa generalização.

Proposição 21.3 (Regras elementares)

Para eventos $A, B$ e uma medida de probabilidade $\P$ : $\P(\emptyset) = 0$ ; $\P$ é finitamente aditiva; $\P(A^c) = 1 - \P(A)$ ; se $A \subseteq B$ então $\P(A) \leq \P(B)$ ; e

\P(A \cup B) = \P(A) + \P(B) - \P(A \cap B) .

Demonstração. Aplicar a $\sigma$ -aditividade a $A_0 = \Omega$ , $A_n = \emptyset$ ( $n \geq 1$ ) dá $1 = 1 + \sum_{n\geq1}\P(\emptyset)$ , logo $\P(\emptyset) = 0$ ; completar uma união disjunta finita com conjuntos vazios dá então a aditividade finita. O resto segue como no caso finito (volume do ensino médio): $1 = \P(A) + \P(A^c)$ a partir de $\Omega = A \sqcup A^c$ ; $\P(B) = \P(A) + \P(B \setminus A) \geq \P(A)$ quando $A \subseteq B$ ; e, decompondo em três pedaços disjuntos,

\begin{align*} \P(A \cup B) &= \P(A \setminus B) + \P(B \setminus A) + \P(A \cap B)\\ &= \bigl(\P(A) - \P(A\cap B)\bigr) + \bigl(\P(B) - \P(A\cap B)\bigr) + \P(A \cap B), \end{align*}

que é a inclusão–exclusão; a versão geral para $n$ conjuntos é o Exercício 21.4. ∎

Proposição 21.4 (Distribuições num espaço enumerável)

Dar uma medida de probabilidade num $\Omega = \{\omega_0, \omega_1, \dots\}$ enumerável equivale exatamente a dar pesos $p_i = \P(\{\omega_i\}) \geq 0$ com $\sum_i p_i = 1$ ; então, para todo $A \subseteq \Omega$ ,

\P(A) = \sum_{\omega \in A} \P(\{\omega\}) ,

uma subsoma (absolutamente convergente) da família $(p_i)$ .

Demonstração. Dada $\P$ , os conjuntos unitários $\{\omega\}$ , $\omega \in A$ , formam uma cobertura disjunta enumerável de $A$ , de modo que a $\sigma$ -aditividade força

\P(A) = \sum_{\omega\in A}\P(\{\omega\}),

uma subsoma incondicional da família somável não negativa $(p_i)$ — reordenar é inofensivo precisamente porque os termos são não negativos (Capítulo 7); em particular, $\sum_ip_i = \P(\Omega) = 1$ . Reciprocamente, dados pesos não negativos de soma total $1$ , defina $\P(A) = \sum_{\omega \in A}p_\omega$ : a família é somável, e a $\sigma$ -aditividade é exatamente o teorema de soma por pacotes do Capítulo 7 aplicado à partição de $\bigcup A_n$ nos $A_n$ . ∎

Exemplo 21.5 (Modelo geométrico: esperando a primeira cara)

Lance repetidamente uma moeda com probabilidade de cara $p \in \intoo{0}{1}$ e seja $\Omega = \N^* \cup \{\infty\}$ o registro da posição da primeira cara. Os pesos naturais são

\P(\{k\}) = (1 - p)^{k-1}p \quad (k \in \N^*), \qquad \P(\{\infty\}) = 0 ,

uma medida de probabilidade, pois $\sum_{k\geq1}(1-p)^{k-1}p = \frac{p}{1 - (1-p)} = 1$ : com probabilidade $1$ o jogo termina — mas o espaço amostral deve ainda conter a possibilidade de que ele não termine. A aditividade enumerável é o que nos permite afirmar $\P(\text{o jogo termina}) = \sum_k \P(\{k\})$ .

Teorema 21.6 (Continuidade monótona)

Seja $(A_n)$ uma sequência de eventos.

Se $A_n \subseteq A_{n+1}$ para todo $n$ (crescente), então $\P\bigl(\bigcup_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .
Se $A_n \supseteq A_{n+1}$ para todo $n$ (decrescente), então $\P\bigl(\bigcap_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .

Demonstração. 1. Disjuntifique: ponha $B_0 = A_0$ e $B_n = A_n \setminus A_{n-1}$ . Os $B_n$ são dois a dois disjuntos com $\bigcup_{k \leq n} B_k = A_n$ e $\bigcup_n B_n = \bigcup_n A_n$ . Pela $\sigma$ -aditividade e pela aditividade finita,

\P\Bigl(\bigcup_n A_n\Bigr) = \sum_{n=0}^\infty \P(B_n) = \lim_{N\to\infty}\sum_{n=0}^N \P(B_n) = \lim_{N\to\infty}\P(A_N) .

2. Passe aos complementares: $(A_n^c)$ é crescente com união $\bigl(\bigcap A_n\bigr)^c$ , e aplique a parte 1: $1 - \P(\bigcap A_n) = \lim (1 - \P(A_n))$ . ∎

Corolário 21.7 (Subaditividade enumerável)

Para qualquer sequência de eventos, $\P\bigl(\bigcup_n A_n\bigr) \leq \sum_{n=0}^\infty \P(A_n)$ .

Demonstração. A subaditividade finita $\P(A_0 \cup \dots \cup A_N) \leq \sum_0^N \P(A_n)$ decorre da inclusão–exclusão por indução (ou da aditividade sobre os $B_n \subseteq A_n$ disjuntificados). Faça $N \to \infty$ : o membro da esquerda converge para $\P(\bigcup_n A_n)$ pela continuidade monótona aplicada à sequência crescente $C_N = A_0 \cup \dots \cup A_N$ . ∎

Exemplo 21.8 (A cota da união: grosseira mas indestrutível)

A subaditividade com finitos eventos — a cota da união — troca precisão por universalidade. Para o problema dos aniversários com $23$ pessoas, majorar a probabilidade de colisão pela soma sobre os pares dá

\P(\text{colisão}) \leq \binom{23}2\cdot\frac1{365} = \frac{253}{365} \approx 0.693 ,

contra o verdadeiro $0.507$ : errado por larga margem, porque as colisões se sobrepõem. Ainda assim, a cota não precisa de independência, de lei conjunta, de nada além das probabilidades de pares — e é por isso que, no problema de fim de semana e ao longo de todo o Capítulo 22, a cota da união é a primeira ferramenta sacada: quando ela por acaso é pequena, a questão está resolvida sem modelagem adicional.

Exemplo 21.9 (Um seis vem, mais cedo ou mais tarde)

Lance um dado honesto indefinidamente e seja $B_n = {}$ “ao menos um seis entre os $n$ primeiros lançamentos”, uma sequência crescente de eventos com $\P(B_n) = 1 - (5/6)^n$ . A continuidade monótona dá

\P(\text{um seis acaba aparecendo}) = \P\Bigl(\bigcup_nB_n\Bigr) = \lim_n\bigl(1 - (5/6)^n\bigr) = 1 .

O ponto não é o limite (óbvio), mas o passo lógico: “mais cedo ou mais tarde” é um evento sobre infinitos lançamentos, fora do alcance da aditividade finita, e a continuidade monótona — isto é, a $\sigma$ -aditividade — é precisamente o axioma que lhe atribui uma probabilidade. Toda afirmação quase certa no resto deste livro passa por essa mesma porta estreita.

21.2 Condicionamento e independência

Definição 21.10 (Probabilidade condicional)

Para eventos $A, B$ com $\P(B) > 0$ , a probabilidade condicional de $A$ dado $B$ é

\P(A \mid B) = \frac{\P(A \cap B)}{\P(B)} .

A aplicação $A \mapsto \P(A \mid B)$ é ela própria uma medida de probabilidade em $\Omega$ .

Observação 21.11

Que $A \mapsto \pcond BA$ seja de novo uma medida de probabilidade merece um instante: $\pcond B\Omega = 1$ e a $\sigma$ -aditividade passam pelo quociente porque a interseção com $B$ respeita uniões disjuntas. A consequência prática: toda identidade deste capítulo — inclusão–exclusão, continuidade monótona, Borel–Cantelli — pode ser aplicada depois do condicionamento, sem demonstrações novas. Os probabilistas constantemente “trabalham sob $\pcond B{\cdot}$ ” exatamente por essa razão.

Exemplo 21.12 (O condicionamento pode criar uniformidade)

Lance dois dados honestos e condicione a soma valer $7$ : para cada $k \in \intint16$ ,

\pcond{\{S = 7\}}{X = k} = \frac{\P(X = k,\ Y = 7 - k)}{\P(S = 7)} = \frac{1/36}{6/36} = \frac16 :

dada uma soma de $7$ , o primeiro dado é exatamente uniforme — $7$ é o único total compatível com todas as faces, de modo que o condicionamento apaga toda informação sobre $X$ . Qualquer outro total enviesa a lei (dado $S = 4$ , o primeiro dado é uniforme apenas em $\{1, 2, 3\}$ ). Calcular uma lei condicional significa renormalizar os pesos conjuntos ao longo do evento condicionante, nada mais.

Exemplo 21.13 (O segundo sorteio vale tanto quanto o primeiro)

Uma urna contém $3$ bolas brancas e $2$ pretas; sorteiam-se duas sem reposição. Todos concordam que $\P(W_1) = \frac35$ ; quanto vale $\P(W_2)$ ? Probabilidade total ao longo do primeiro sorteio:

\P(W_2) = \pcond{W_1}{W_2}\,\P(W_1) + \pcond{B_1}{W_2}\,\P(B_1) = \frac24\cdot\frac35 + \frac34\cdot\frac25 = \frac{12}{20} = \frac35 :

exatamente $\P(W_1)$ . Nenhum cálculo era necessário: por simetria, toda bola tem a mesma chance de ser a segunda sorteada, de modo que o segundo sorteio — incondicionalmente — tem a mesma lei que o primeiro. Condicionar ao primeiro resultado muda as chances; não conhecê-lo, não. Esse argumento de permutabilidade volta no próximo capítulo para a amostragem sem reposição, em que dá a média hipergeométrica $np$ sem identidade binomial alguma.

Teorema 21.14 (Probabilidades compostas, probabilidade total, Bayes)

(Regra da cadeia) Se $\P(A_1 \cap \dots \cap A_{n-1}) > 0$ ,

$\P(A_1 \cap \dots \cap A_n) = \P(A_1)\,\P(A_2 \mid A_1)\cdots \P(A_n \mid A_1 \cap \dots \cap A_{n-1}) .$
(Probabilidade total) Se $(B_i)_{i \in I}$ é uma partição finita ou enumerável de $\Omega$ com $\P(B_i) > 0$ , então, para todo evento $A$ :

$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$
(Bayes) Sob as mesmas hipóteses, se além disso $\P(A) > 0$ :

$\P(B_j \mid A) = \frac{\P(A \mid B_j)\,\P(B_j)} {\sum_{i \in I} \P(A \mid B_i)\,\P(B_i)} .$

Demonstração. 1. Escreva cada probabilidade condicional como um quociente: o membro da direita é

\P(A_1)\cdot\frac{\P(A_1 \cap A_2)}{\P(A_1)}\cdot \frac{\P(A_1 \cap A_2 \cap A_3)}{\P(A_1 \cap A_2)}\cdots \frac{\P(A_1 \cap \dots \cap A_n)}{\P(A_1 \cap \dots \cap A_{n-1})},

um produto telescópico: cada denominador cancela o numerador precedente, deixando $\P(A_1 \cap \dots \cap A_n)$ . Todos os denominadores são $\geq \P(A_1 \cap \dots \cap A_{n-1}) > 0$ por monotonia, de modo que nada se anula. (A hipótese protege exatamente isso: condicionar a um evento de probabilidade zero é indefinido.) 2. Os conjuntos $A \cap B_i$ são dois a dois disjuntos com união $A$ ; aplique a ( $\sigma$ -)aditividade e a definição de condicionamento. 3. Ambos os membros de $\P(B_j \mid A)\P(A) = \P(A \mid B_j)\P(B_j)$ valem $\P(A \cap B_j)$ ; divida por $\P(A)$ e desenvolva $\P(A)$ pela probabilidade total. ∎

Exemplo 21.15 (A colisão de aniversários, pela regra da cadeia)

Com $n$ pessoas cujos aniversários são independentes e uniformes em $365$ dias, seja $D_n = {}$ “todos os $n$ aniversários diferem”. Condicionando pessoa a pessoa (regra da cadeia):

\P(D_n) = \prod_{k=1}^{n-1}\Bigl(1 - \frac{k}{365}\Bigr),

cada nova pessoa tendo de evitar os $k$ dias já ocupados. Para $n = 23$ : $\P(D_{23}) \approx 0.493$ — um aniversário compartilhado já é mais provável do que não. A heurística que explica a pequenez de $23$ : tomando logaritmos, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$ , e $\binom{23}2 = 253$ dá $253/365 \approx 0.693 \approx \ln 2$ . O que importa é o número de pares, que cresce quadraticamente: os problemas de colisão vivem na escala $n \sim \sqrt{365}$ , e não $n \sim 365$ — o paradoxo dos aniversários é uma raiz quadrada disfarçada.

Exemplo 21.16 (Monty Hall, por Bayes)

Um prêmio se esconde atrás de uma de três portas, uniformemente. Você escolhe a porta $1$ ; o apresentador, que sabe onde está o prêmio, abre uma das outras portas, sempre vazia (escolhendo uniformemente quando tem escolha), digamos a porta $3$ . Sejam $B_i = {}$ “prêmio atrás da porta $i$ ” e $A = {}$ “o apresentador abre a porta $3$ ”. Então $\pcond{B_1}{A} = \frac12$ , $\pcond{B_2}{A} = 1$ , $\pcond{B_3}{A} = 0$ , de modo que, por Bayes (Teorema 21.14),

\P(B_2 \mid A) = \frac{1\cdot\frac13} {\frac12\cdot\frac13 + 1\cdot\frac13 + 0\cdot\frac13} = \frac23 :

trocar de porta ganha duas vezes em três. O cálculo localiza exatamente a confusão popular: o gesto do apresentador é informativo (ele não poderia abrir a porta $2$ se o prêmio estivesse ali), e a fórmula de Bayes é o dispositivo de contabilidade que converte essa assimetria no $\frac23$ . Condicionar ao “que foi visto” e não ao “que é verdadeiro” é toda a arte da fórmula.

Exemplo 21.17 (As duas apostas do Cavaleiro de Méré)

Duas apostas do século XVII, resolvidas pela independência. Aposta um: ao menos um seis em $4$ lançamentos de um dado,

\P = 1 - \Bigl(\frac56\Bigr)^{\!4} \approx 0.518 > \frac12 .

Aposta dois: ao menos um duplo seis em $24$ lançamentos de dois dados,

\P = 1 - \Bigl(\frac{35}{36}\Bigr)^{\!24} \approx 0.491 < \frac12 .

Méré raciocinou que $24$ lançamentos com chance $\frac1{36}$ deveriam equivaler a $4$ lançamentos com chance $\frac16$ (mesma razão $\frac{24}{36} = \frac46$ ); a falha dessa proporcionalidade — probabilidades de uniões não escalam linearmente — teria motivado sua carta a Pascal e, com ela, o nascimento da teoria da probabilidade. A comparação correta é por logaritmos: $n$ tentativas com chance $p$ têm sucesso ao menos uma vez com probabilidade $1 - (1-p)^n \approx 1 - \eu^{-np}$ , de modo que o invariante honesto é $np$ : aqui $4\cdot\frac16 = \frac23$ contra $24\cdot\frac1{36} = \frac23$ — iguais! As duas apostas diferem apenas na segunda ordem em $p$ , e por pouco o bastante para levar uma delas ao outro lado da linha dos cinquenta por cento: probabilidades pequenas são um domínio em que a intuição precisa da exponencial, não da régua.

Observação 21.18 (Falácias comuns do condicionamento)

Três confusões recorrentes, todas visíveis nos exemplos acima. (i) Inversão: $\pcond BA$ e $\pcond AB$ diferem pelo fator $\P(A)/\P(B)$ — um teste que acerta $99\%$ nos doentes pode ainda deixar um paciente positivo quase certamente saudável quando a doença é rara (Exercício 21.3); citar $\pcond{\text{doente}}{ \text{positivo}}$ onde se quer dizer $\pcond{\text{positivo}}{ \text{doente}}$ é a falácia da taxa base. (ii) Condicionar ao evento errado: em Monty Hall, o evento condicionante correto é “o apresentador abriu a porta $3$ ”, e não “o prêmio não está atrás da porta $3$ ”; os dois carregam informações diferentes, e todo o $\frac23$ depende dessa diferença. (iii) Disjunto contra independente: eventos disjuntos de probabilidade positiva nunca são independentes ( $\P(A\cap B) = 0 \neq \P(A)\P(B)$ ) — independência é compatibilidade de informação, não ausência de sobreposição.

Definição 21.19 (Independência)

Os eventos $A$ e $B$ são independentes se $\P(A \cap B) = \P(A)\P(B)$ . Uma família $(A_i)_{i \in I}$ de eventos é (mutuamente) independente se, para todo subconjunto finito $J \subseteq I$ ,

\P\Bigl(\bigcap_{i \in J} A_i\Bigr) = \prod_{i \in J} \P(A_i) .

Observação 21.20

A independência mútua é estritamente mais forte que a independência dois a dois: com dois lançamentos de moeda honesta, os eventos “o primeiro é cara”, “o segundo é cara”, “os dois coincidem” são dois a dois independentes (cada par tem probabilidade de interseção $\frac14 = \frac12\cdot\frac12$ ), e no entanto a interseção tripla tem probabilidade $\frac14 \neq \frac18$ . Note também que, se $A, B$ são independentes, também o são $A, B^c$ (calcule: $\P(A \cap B^c) = \P(A) - \P(A\cap B) = \P(A)(1 - \P(B))$ ), logo também $A^c, B^c$ .

Exemplo 21.21 (Independência lida numa estrutura de produto)

Lance dois dados honestos: $\Omega = \intint16^2$ com pesos uniformes. Sejam $A = {}$ “primeiro dado par” e $B = {}$ “segundo dado ao menos $5$ ”. Contando: $\abs A = 3\cdot6 = 18$ , $\abs B = 6\cdot2 = 12$ , $\abs{A\cap B} = 3\cdot2 = 6$ , logo

\P(A\cap B) = \frac6{36} = \frac{18}{36}\cdot\frac{12}{36} = \P(A)\,\P(B) :

independentes, e o mecanismo é visível — $A$ restringe apenas a primeira coordenada, $B$ apenas a segunda, e a medida uniforme num conjunto produto faz as contagens de coordenadas se multiplicarem. Toda afirmação do tipo “eventos que dependem de grupos disjuntos de lançamentos são independentes” (usada massivamente no problema de fim de semana) é esse cálculo, vestindo mais índices.

Exemplo 21.22 (Análise do primeiro passo)

Para o modelo geométrico do Exemplo 21.5, qual é a probabilidade $u$ de que a primeira cara caia numa posição par? Condicione ao primeiro lançamento: com probabilidade $p$ a posição é $1$ (ímpar); com probabilidade $q = 1 - p$ o jogo recomeça com todas as paridades invertidas, de modo que

u = p\cdot0 + q\,(1 - u) \qquad\Longrightarrow\qquad u = \frac{q}{1 + q} .

Uma linha, sem série alguma — e concorda com a soma direta de Exercício 21.9, que dá $1 - u = \frac1{1+q}$ . Essa técnica do “primeiro passo” (condicionar ao primeiro experimento, reconhecer uma cópia deslocada do problema) é a forma probabilística de uma recursão, e é o motor por trás das equações de duração de jogo do Exercício 21.6 e dos cálculos de primeira passagem do problema de fim de semana.

21.3 O lema de Borel–Cantelli

Definição 21.23 (Limite superior de eventos)

Para uma sequência $(A_n)$ de eventos, o evento

\limsup_n A_n = \bigcap_{N=0}^{\infty}\ \bigcup_{n \geq N} A_n = \{\omega \in \Omega : \omega \in A_n \text{ para infinitos } n\}

é o evento “ $A_n$ ocorre infinitas vezes”.

Exemplo 21.24 (Traduzindo “infinitas vezes” e “a partir de certa ordem”)

O complementar de $\limsup_nA_n$ é, por de Morgan,

\Bigl(\bigcap_N\bigcup_{n\geq N}A_n\Bigr)^{\!c} = \bigcup_N\bigcap_{n\geq N}A_n^c = \{\omega : \omega \notin A_n \text{ para todo grande }n\},

o evento “a partir de certa ordem, $A_n$ falha” (escrito $\liminf_nA_n^c$ ). Assim, “ $A_n$ infinitas vezes” e “ $A_n^c$ a partir de certa ordem” são complementares — manter esse dicionário em ordem previne a maioria dos acidentes com quantificadores. Traduções de amostra para o lançamento de moedas: “infinitas caras” é $\limsup\{X_n = H\}$ ; “apenas finitas sequências de $100$ caras” é o complementar de um limsup; “a frequência corrente converge para $\frac12$ ” é $\bigcap_j\bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - \tfrac12} < \tfrac1j\}$ — operações enumeráveis em toda parte, de modo que todos esses são eventos honestos.

Teorema 21.25 (Borel–Cantelli)

Se $\sum_{n} \P(A_n) < \infty$ , então $\P\bigl(\limsup_n A_n\bigr) = 0$ .
Se os eventos $A_n$ são independentes e $\sum_n \P(A_n) = \infty$ , então $\P\bigl(\limsup_n A_n\bigr) = 1$ .

Demonstração. 1. Ponha $C_N = \bigcup_{n \geq N}A_n$ ; a sequência $(C_N)$ é decrescente com interseção $\limsup A_n$ e, pela subaditividade enumerável (Corolário 21.7),

\P(C_N) \leq \sum_{n \geq N}\P(A_n) \xrightarrow[N\to\infty]{} 0

(cauda de uma série convergente). A continuidade monótona (Teorema 21.6) conclui: $\P(\limsup A_n) = \lim_N \P(C_N) = 0$ .

2. Basta mostrar que $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ para todo $N$ : com efeito, se os eventos $B_N$ têm todos probabilidade $1$ , então

\P\Bigl(\Bigl(\bigcap_NB_N\Bigr)^{\!c}\Bigr) = \P\Bigl(\bigcup_NB_N^c\Bigr) \leq \sum_N\P(B_N^c) = 0

pela subaditividade enumerável (Corolário 21.7), de modo que a interseção enumerável $\limsup A_n = \bigcap_N\bigcup_{n\geq N}A_n$ ainda tem probabilidade $1$ . Fixe $N$ e considere, para $M > N$ , o complementar:

\P\Bigl(\bigcap_{n=N}^{M} A_n^c\Bigr) = \prod_{n=N}^{M}\bigl(1 - \P(A_n)\bigr) \leq \prod_{n=N}^{M} e^{-\P(A_n)} = \exp\Bigl(-\sum_{n=N}^M \P(A_n)\Bigr) ,

usando a independência dos complementares e a majoração de convexidade $1 - x \leq e^{-x}$ . Quando $M \to \infty$ , o expoente tende a $-\infty$ pela divergência da série, de modo que, pela continuidade monótona (sequência decrescente), $\P\bigl(\bigcap_{n \geq N}A_n^c\bigr) = 0$ , isto é, $\P\bigl(\bigcup_{n \geq N}A_n\bigr) = 1$ . ∎

Exemplo 21.26 (Sequências infinitas de caras)

Lance uma moeda honesta indefinidamente e seja $A_n$ o evento “os lançamentos $n, n+1, \dots, n + k - 1$ são todos cara” (uma sequência de $k$ caras começando no instante $n$ ), para $k$ fixo. Os eventos $A_{jk}$ ( $j = 1, 2, \dots$ ), dependendo de blocos disjuntos de lançamentos, são independentes, cada um de probabilidade $2^{-k}$ , e $\sum_j 2^{-k} = \infty$ : por Borel–Cantelli 2, com probabilidade $1$ infinitos blocos são todos-cara — todo padrão fixo recorre infinitas vezes, quase certamente. Reciprocamente, se deixarmos o comprimento da sequência crescer, $B_n = {}$ “uma sequência de $2\log_2 n$ caras começa em $n$ ” tem $\P(B_n) = n^{-2}$ somável, de modo que, quase certamente, apenas finitas dessas longas sequências começam: Borel–Cantelli calibra precisamente quão longas são as sequências mais longas.

Exemplo 21.27 (O macaco infinito, quantificado)

Um macaco digita letras uniformes independentes de um alfabeto de $26$ letras. Corte o texto datilografado em blocos disjuntos de quatro letras; os eventos $A_j = {}$ “o bloco $j$ soletra MATH” são independentes com $\P(A_j) = 26^{-4}$ , e $\sum_j\P(A_j) = \infty$ : por Borel–Cantelli 2 o macaco digita MATH infinitas vezes, quase certamente — e o mesmo vale para qualquer texto fixo de qualquer comprimento, ajustados os blocos. A nota de rodapé quantitativa esvazia o milagre: $26^4 = 456\,976$ , de modo que o primeiro MATH leva cerca de meio milhão de toques em média, e uma peça de Shakespeare de $10^5$ caracteres espera da ordem de $26^{10^5}$ blocos — quase certo é uma afirmação sobre o horizonte $\infty$ , não sobre algum horizonte que um macaco venha a encontrar. Borel–Cantelli certifica o limite; o tamanho das parcelas conta a história nas escalas humanas.

Observação 21.28

No Exemplo 21.26 o espaço amostral subjacente (sequências infinitas de lançamentos) é não enumerável, de modo que, a rigor, o exemplo vive no quadro da teoria da medida do terceiro ano; os cálculos, porém, usam apenas as regras demonstradas neste capítulo, aplicadas a eventos determinados por finitos lançamentos e suas combinações enumeráveis. Essa é a convenção padrão nesse nível: a teoria é enunciada em espaços enumeráveis, e os exemplos de jogos infinitos são tratados com o mesmo instrumental.

Observação 21.29 (Perspectivas dentro deste volume)

A maquinaria deste capítulo é consumida por atacado pelos dois seguintes. As indicadoras transformam eventos em variáveis aleatórias, e a $\sigma$ -aditividade se torna a somabilidade que define a esperança (Capítulo 22); Borel–Cantelli mais uma cota de cauda somável é exatamente como a lei forte dos grandes números para moedas é demonstrada lá. No Capítulo 23, a continuidade monótona reaparece no momento decisivo: a probabilidade de extinção de um processo de ramificação é definida como o limite monótono $\lim\P(Z_n = 0)$ , e a equação de ponto fixo que ela satisfaz é obtida passando ao limite nessa sequência crescente — o teorema final do livro se apoia no primeiro teorema deste capítulo.

Observação 21.30 (Método: três caminhos para a probabilidade um)

Afirmações quase certas se demonstram com três alavancas, em ordem crescente de força. Continuidade monótona: exiba o evento como uma união crescente (ou interseção decrescente) de eventos de horizonte finito com probabilidades calculáveis (Exemplo 21.9). Uniões nulas: uma união enumerável de eventos de probabilidade zero é nula (subaditividade enumerável), de modo que basta matar cada evento ruim separadamente — é assim que “para todo $j$ , a partir de certa ordem $\abs{\widehat p_n - p} < 1/j$ ” se monta em convergência. Borel–Cantelli: quando o evento é um limsup, some as probabilidades; a convergência o mata (sem precisar de independência), e a divergência mais a independência o certificam. Escolher a alavanca certa costuma ser toda a demonstração; o problema de fim de semana roda as três num único argumento.

Observação 21.31 (Onde isso é usado)

A continuidade monótona e Borel–Cantelli são as duas alavancas de toda afirmação “quase certa”: elas movem a recorrência do passeio aleatório no problema de fim de semana deste capítulo, o lado quase certo da lei dos grandes números (Capítulo 22) e a análise de extinção dos processos de ramificação (Capítulo 23). O volume do terceiro ano de graduação reconstrói a teoria sobre $\sigma$ -álgebras e a integração de Lebesgue, em que os espaços amostrais não enumeráveis usados informalmente aqui se tornam plenamente rigorosos.

21.4 Exercícios

Exercício 21.1 ★

Uma urna contém $n$ bolas numeradas. As bolas são sorteadas uma a uma sem reposição. Calcule a probabilidade de a bola número $1$ ser sorteada antes da bola número $2$ . Generalize: a probabilidade de a bola $1$ ser sorteada primeiro entre as bolas $1, \dots, k$ .

Solução

Solução de Exercício 21.1.

Por simetria: a ordem de sorteio induz uma ordem relativa uniformemente aleatória sobre as bolas $1$ e $2$ , logo $\P(1 \text{ antes de } 2) = \frac12$ . Formalmente: trocar as posições das bolas $1$ e $2$ numa sequência de sorteios é uma bijeção dos resultados (equiprováveis) que troca o evento por seu complementar. Entre as bolas $1, \dots, k$ : a ordem relativa dessas $k$ bolas é uniforme entre as $k!$ ordenações, e a bola $1$ é a primeira em $(k-1)!$ delas: probabilidade $\frac{(k-1)!}{k!} = \frac1k$ .

Exercício 21.2 ★

Mostre que em $\Omega = \N^*$ os pesos $p_k = \frac{1}{k(k+1)}$ definem uma medida de probabilidade e calcule $\P(2\N^*)$ (resultados pares) como uma série; mostre que ela vale $1 - \ln 2$ . (Telescope $\frac{1}{2j(2j+1)} = \frac{1}{2j} - \frac{1}{2j+1}$ e use a série harmônica alternada, Capítulo 7.)

Solução

Solução de Exercício 21.2.

$\frac{1}{k(k+1)} = \frac1k - \frac1{k+1}$ , de modo que $\sum_{k\geq1} p_k$ telescopa a $1$ : uma medida de probabilidade. Resultados pares:

\P(2\N^*) = \sum_{j=1}^{\infty}\frac{1}{2j(2j+1)} = \sum_{j=1}^{\infty}\Bigl(\frac{1}{2j} - \frac{1}{2j+1}\Bigr) = \frac12 - \frac13 + \frac14 - \frac15 + \cdots

Essa é a série harmônica alternada com seu primeiro termo removido e os sinais invertidos: como $\ln 2 = 1 - \frac12 + \frac13 - \frac14 + \cdots$ (Capítulo 7),

\P(2\N^*) = -\bigl(\ln 2 - 1\bigr) = 1 - \ln 2 \approx 0.307 .

Exercício 21.3 ★

(Falsos positivos) Uma doença afeta uma pessoa em $10\,000$ . Um teste a detecta com probabilidade $0.99$ nos doentes e dá um falso positivo com probabilidade $0.01$ nos saudáveis. Calcule a probabilidade de estar doente dado um teste positivo e comente.

Solução

Solução de Exercício 21.3.

Sejam $S$ = doente e $+$ = teste positivo. Bayes (Teorema 21.14) com a partição $\{S, S^c\}$ :

\P(S \mid +) = \frac{0.99 \times 10^{-4}} {0.99 \times 10^{-4} + 0.01 \times 0.9999} = \frac{0.000099}{0.000099 + 0.009999} \approx 0.0098 ,

abaixo de $1\%$ . Embora o teste seja “99% preciso”, um resultado positivo deixa você com cerca de $99\%$ de chance de estar saudável: os falsos positivos entre a vasta maioria saudável afogam os verdadeiros positivos da minúscula minoria doente. Testes de rastreamento para condições raras devem sempre ser lidos através desse cálculo de taxa base.

Exercício 21.4 ★★

Sejam $A_1, \dots, A_n$ eventos. Demonstre a fórmula de inclusão–exclusão

\P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}} (-1)^{\abs J + 1}\,\P\Bigl(\bigcap_{i \in J}A_i\Bigr)

integrando a identidade $1 - \prod_{i=1}^n(1 - \mathbf{1}_{A_i}) = \mathbf{1}_{\bigcup A_i}$ em $\Omega$ (isto é, somando com peso $\P(\{\omega\})$ ).

Solução

Solução de Exercício 21.4.

Pontualmente em $\Omega$ : $\omega \in \bigcup A_i$ se e somente se algum fator $1 - \mathbf{1}_{A_i}(\omega)$ se anula, logo

\mathbf{1}_{\bigcup A_i} = 1 - \prod_{i=1}^n\bigl(1 - \mathbf{1}_{A_i}\bigr) = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}} (-1)^{\abs J + 1}\prod_{i \in J}\mathbf{1}_{A_i} ,

desenvolvendo o produto e passando o $1$ para o outro lado. Ora, $\prod_{i\in J}\mathbf{1}_{A_i} = \mathbf{1}_{\bigcap_{i \in J} A_i}$ e, somando contra os pesos $\P(\{\omega\})$ — legítimo: finitos termos limitados, cada família somável — cada indicadora se torna a probabilidade de seu evento, o que dá a fórmula.

Exercício 21.5 ★★

(Problema dos encontros, via inclusão–exclusão) $n$ cartas são postas uniformemente ao acaso em $n$ envelopes, uma em cada. Usando o Exercício 21.4, mostre que a probabilidade de nenhum acerto vale $\sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}$ e deduza a probabilidade de exatamente um acerto.

Solução

Solução de Exercício 21.5.

Seja $A_i$ = “a carta $i$ está no envelope certo”. Para $J$ de cardinal $k$ , $\P\bigl(\bigcap_{i\in J}A_i\bigr) = \frac{(n-k)!}{n!}$ (fixe $k$ cartas, permute o resto). Por inclusão–exclusão,

\P\Bigl(\bigcup A_i\Bigr) = \sum_{k=1}^n (-1)^{k+1}\binom nk \frac{(n-k)!}{n!} = \sum_{k=1}^n \frac{(-1)^{k+1}}{k!} ,

logo

\P(\text{nenhum acerto}) = 1 - \P\Bigl(\bigcup A_i\Bigr) = \sum_{k=0}^{n}\frac{(-1)^k}{k!} \xrightarrow[n\to\infty]{} e^{-1} \approx 0.368 .

Exatamente um acerto: uma permutação com exatamente um ponto fixo é determinada pela escolha da carta fixada ( $n$ modos) e por um desarranjo (arranjo sem acertos) das outras $n - 1$ ; escrevendo $D_{n-1} = (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$ para o número de desarranjos (a primeira parte, multiplicada por $(n-1)!$ ),

\P(\text{exatamente um acerto}) = \frac{n\,D_{n-1}}{n!} = \frac{D_{n-1}}{(n-1)!} = \sum_{k=0}^{n-1}\frac{(-1)^k}{k!} \xrightarrow[n\to\infty]{} e^{-1} :

no limite, “nenhum acerto” e “exatamente um acerto” são igualmente prováveis, cada um com probabilidade $e^{-1}$ .

Exercício 21.6 ★★

Uma moeda viciada (probabilidade de cara $p \in \intoo{0}{1}$ ) é lançada até aparecerem duas caras consecutivas. Seja $q_n$ a probabilidade de o jogo durar mais de $n$ lançamentos. Mostre, condicionando ao primeiro (ou aos primeiros) lançamento(s), que $q_n = (1-p)\,q_{n-1} + p(1-p)\,q_{n-2}$ para $n \geq 2$ , e deduza que o jogo termina com probabilidade $1$ . (Mostre que $q_n \to 0$ comparando com uma sequência geométrica: ambas as raízes da equação característica têm valor absoluto em $\intoo{0}{1}$ .)

Solução

Solução de Exercício 21.6.

Condicione ao início (regra da cadeia / Teorema 21.14):

primeiro lançamento coroa (probabilidade $1 - p$ ): o jogo recomeça do zero; durar mais de $n$ significa durar mais de $n - 1$ a partir dali: contribuição $(1-p)\,q_{n-1}$ ;
primeiros lançamentos cara-coroa (probabilidade $p(1-p)$ ): recomeço após dois lançamentos: contribuição $p(1-p)\,q_{n-2}$ ;
primeiros lançamentos cara-cara: o jogo terminou (em até $n$ lançamentos, $n \geq 2$ ): contribui com $0$ .

Portanto $q_n = (1-p)q_{n-1} + p(1-p)q_{n-2}$ . A equação característica $r^2 = (1-p)r + p(1-p)$ tem raízes

r_\pm = \frac{(1-p) \pm \sqrt{(1-p)^2 + 4p(1-p)}}{2},

com $\abs{r_\pm} < 1$ : de fato, o polinômio $\chi(r) = r^2 - (1-p)r - p(1-p)$ satisfaz $\chi(1) = 1 - (1-p) - p(1-p) = p^2 > 0$ e $\chi(-1) = 1 + (1-p) - p(1-p) > 0$ , enquanto $\chi(0) = -p(1-p) < 0$ : uma raiz em $\intoo{-1}{0}$ , outra em $\intoo{0}{1}$ . Logo $q_n = \alpha r_+^n + \beta r_-^n \to 0$ . Os eventos “o jogo dura mais de $n$ ” decrescem para “o jogo nunca termina”; a continuidade monótona (Teorema 21.6) dá $\P(\text{nunca termina}) = \lim q_n = 0$ : o jogo termina quase certamente.

Exercício 21.7 ★★★

(Recordes) Sorteie uma sequência infinita de ordenações uniformes independentes, no seguinte sentido combinatório: para cada $n$ , a ordem relativa dos $n$ primeiros sorteios é uniforme entre as $n!$ possibilidades, e $R_n = {}$ “o $n$ -ésimo sorteio é um recorde (maior que todos os anteriores)”. Admitindo que os eventos $R_n$ são independentes com $\P(R_n) = 1/n$ (demonstre ao menos essa última igualdade por simetria), mostre, usando Borel–Cantelli, que infinitos recordes ocorrem quase certamente, mas que recordes em instantes consecutivos $n, n+1$ ocorrem infinitas vezes com probabilidade — calcule $\sum_n \P(R_n \cap R_{n+1})$ e conclua o que dá Borel–Cantelli 1.

Solução

Solução de Exercício 21.7.

$\P(R_n) = 1/n$ : entre os $n$ primeiros sorteios, cada uma das $n$ posições relativas do último sorteio é igualmente provável (uniformidade da ordem relativa), e $R_n$ é o evento de ele ser o maior: probabilidade $1/n$ .

Infinitos recordes: $\sum_n \P(R_n) = \sum 1/n = \infty$ e os $R_n$ são independentes (admitido), de modo que Borel–Cantelli 2 (Teorema 21.25) dá $\P(\limsup R_n) = 1$ : os recordes nunca param, quase certamente — mas eles rareiam logaritmicamente.

Recordes consecutivos: pela independência,

\sum_n \P(R_n \cap R_{n+1}) = \sum_n \frac{1}{n(n+1)} < \infty ,

de modo que Borel–Cantelli 1 se aplica: quase certamente, apenas finitas vezes um recorde é imediatamente seguido de outro recorde. As duas metades do lema trabalham em conjunto: infinitos recordes, mas (q.c.) a partir de certa ordem nunca dois seguidos.

Exercício 21.8 ★★★

(Sabor Kochen–Stone, versão mais fácil) Sejam $(A_n)$ eventos independentes com $\P(A_n) = \frac{1}{n+1}$ . Mostre que $\P(\limsup A_n) = 1$ , embora $\P(A_n) \to 0$ : “individualmente raros, coletivamente certos”. Reciprocamente, exiba uma sequência de eventos (dependentes) com $\sum\P(A_n) = \infty$ e $\P(\limsup A_n) = 0$ , mostrando que a independência não pode ser dispensada em Borel–Cantelli 2.

Solução

Solução de Exercício 21.8.

Primeira parte: $\sum \P(A_n) = \sum\frac{1}{n+1} = \infty$ com independência: Borel–Cantelli 2 dá $\P(\limsup A_n) = 1$ . Cada $A_n$ individual é cada vez mais improvável e, no entanto, quase todo $\omega$ pertence a infinitos deles.

Contraexemplo sem independência: tome $\Omega = \N^*$ com os pesos $p_k = \frac{1}{k(k+1)}$ do Exercício 21.2, e $A_n = \{k \in \N^* : k \geq n\}$ . Então

\P(A_n) = \sum_{k \geq n}\Bigl(\frac1k - \frac1{k+1}\Bigr) = \frac1n , \qquad \sum_n \P(A_n) = \infty ,

mas os $A_n$ são decrescentes, logo $\limsup_n A_n = \bigcap_n A_n = \emptyset$ : $\P(\limsup A_n) = 0$ . A divergência de $\sum\P(A_n)$ sozinha não garante nada quando os eventos se empilham numa parte encolhente do espaço — a independência é o que proíbe essa conspiração.

Exercício 21.9 ★

Uma moeda com probabilidade de cara $p \in \intoo01$ é lançada até a primeira cara. Calcule a probabilidade de isso acontecer numa posição ímpar e avalie-a para uma moeda honesta.

Solução

Solução de Exercício 21.9.

Com $q = 1 - p$ , a primeira cara cai na posição $2j + 1$ com probabilidade $q^{2j}p$ , logo

\P(\text{posição ímpar}) = \sum_{j\geq0}q^{2j}p = \frac{p}{1 - q^2} = \frac{1}{1 + q} .

Para uma moeda honesta: $\frac1{1 + 1/2} = \frac23$ . (Verificação de bom senso: as posições ímpares devem ser mais prováveis, pois a posição $1$ vem primeiro — e, de fato, $\frac1{1+q} > \frac12$ sempre.)

Exercício 21.10 ★★

Sejam $(A_n)_{n\geq1}$ eventos independentes com $\P(A_n) = p_n < 1$ . Mostre que

\P\Bigl(\bigcap_{n\geq1}A_n^c\Bigr) = \prod_{n\geq1}(1 - p_n) := \lim_{N\to\infty}\prod_{n=1}^N(1 - p_n),

e que esse limite vale $> 0$ se e somente se $\sum p_n < \infty$ . Concilie com Borel–Cantelli: quando $\sum p_n = \infty$ , não apenas algum $A_n$ ocorre quase certamente — infinitos ocorrem.

Solução

Solução de Exercício 21.10.

Os eventos $B_N = \bigcap_{n=1}^N A_n^c$ decrescem para $\bigcap_nA_n^c$ e, pela independência dos complementares, $\P(B_N) = \prod_{n=1}^N(1 - p_n)$ ; a continuidade monótona (Teorema 21.6) dá o limite exibido. Tomando logaritmos, $\prod(1 - p_n) > 0$ se e somente se $\sum-\ln(1 - p_n) < \infty$ . Se $\sum p_n < \infty$ , então $p_n \to 0$ e $-\ln(1 - p_n) \sim p_n$ : a série dos logaritmos converge. Se $\sum p_n = \infty$ , então $-\ln(1 - p_n) \geq p_n$ força a divergência, logo o produto vale $0$ . Isso coincide com Borel–Cantelli 2: para $\sum p_n = \infty$ , não apenas $\P(\text{nenhum }A_n\text{ ocorre}) = 0$ , mas quase certamente infinitos $A_n$ ocorrem.

Exercício 21.11 ★★

(Caixa de fósforos de Banach) Um fumante mantém uma caixa de $n$ fósforos em cada bolso e enfia a mão num bolso uniformemente ao acaso a cada vez. Quando ele encontra pela primeira vez uma caixa vazia, qual é a probabilidade de a outra caixa conter exatamente $k$ fósforos? Mostre que a resposta é $\binom{2n-k}{n}2^{-(2n-k)}$ e verifique que essas probabilidades somam $1$ para $n = 1$ .

Solução

Solução de Exercício 21.11.

Digamos que a caixa $A$ seja a primeira encontrada vazia, com a outra caixa contendo $k$ . Isso significa: entre as primeiras $2n - k$ enfiadas de mão, exatamente $n$ foram para $A$ e $n - k$ para $B$ (em alguma ordem), e a enfiada número $2n - k + 1$ foi de novo para $A$ , encontrando-a vazia. As enfiadas são escolhas honestas independentes, de modo que esse evento tem probabilidade $\binom{2n-k}{n}2^{-(2n-k)}\cdot\frac12$ ; dobrando (a caixa vazia pode ser qualquer uma das duas) obtém-se

\P(\text{a outra caixa tem }k) = \binom{2n-k}{n}\,2^{-(2n-k)} .

Para $n = 1$ : $k = 1$ dá $\binom11 2^{-1} = \frac12$ e $k = 0$ dá $\binom21 2^{-2} = \frac12$ : total $1$ , como deve ser.

Exercício 21.12 ★★★

(A $\sigma$ -aditividade é um axioma de verdade) (a) Mostre que não há medida de probabilidade em $(\N, \mathcal P(\N))$ que dê a todos os conjuntos unitários o mesmo peso. (b) Para $A \subseteq \N^*$ , ponha $d(A) = \lim_n\frac{\abs{A\cap\intint1n}}{n}$ quando o limite existe (a densidade natural). Mostre que $d$ é finitamente aditiva nos pares em que as três densidades existem, dá a todo conjunto unitário densidade $0$ e a $\N^*$ densidade $1$ — e conclua que $d$ não é $\sigma$ -aditiva. (c) Exiba um conjunto sem densidade. (Alterne blocos $\intint{2^{2k}}{2^{2k+1}-1}$ dentro e fora.)

Solução

Solução de Exercício 21.12.

(a) Se $\P(\{n\}) = c$ para todo $n$ , a $\sigma$ -aditividade força $1 = \sum_nc$ : impossível, seja $c = 0$ (soma $0$ ) ou $c > 0$ (soma infinita). Não há probabilidade uniforme em $\N$ .

(b) Se $A \cap B = \emptyset$ e $d(A)$ , $d(B)$ existem, então $\abs{(A \sqcup B)\cap\intint1n} = \abs{A\cap\intint1n} + \abs{B\cap\intint1n}$ , logo $d(A \sqcup B) = d(A) + d(B)$ : aditividade finita em tais pares. Cada conjunto unitário tem função de contagem constante a partir de certa ordem, logo densidade $0$ , enquanto $d(\N^*) = 1$ . Se $d$ fosse $\sigma$ -aditiva, $\N^* = \bigsqcup_k\{k\}$ daria $1 = \sum_k 0 = 0$ : a densidade é finitamente aditiva, mas não $\sigma$ -aditiva — o axioma tem conteúdo.

(c) Seja $A = \bigcup_{k\geq0}\intint{4^k}{2\cdot4^k - 1}$ (blocos de $4^k$ a $2\cdot4^k - 1$ ). Em $n = 2\cdot4^K - 1$ a contagem vale $\sum_{k\leq K}4^k \sim \frac43 4^K$ , o que dá razão $\to \frac23$ ; em $n = 4^{K+1} - 1$ a contagem fica inalterada, o que dá razão $\to \frac13$ . A razão oscila entre os limites $\frac13$ e $\frac23$ : sem densidade.

21.5 Problema: o passeio aleatório simples em $\Z$ é recorrente

Vinte e quatro passos de um passeio aleatório simples; os pontos vermelhos marcam os retornos à origem. O problema mostra que, com probabilidade 1, esses pontos nunca deixam de aparecer — e no entanto o tempo de espera entre eles tem média divergente. — Vinte e quatro passos de um passeio aleatório simples; os pontos vermelhos marcam os retornos à origem. O problema mostra que, com probabilidade $1$ , esses pontos nunca deixam de aparecer — e no entanto o tempo de espera entre eles tem média divergente.

Problema 21.1

Problema de fim de semana — o teorema de recorrência de Pólya em $\Z$ , com o problema das cédulas e o sabor do arco seno pelo caminho

Lance uma moeda honesta indefinidamente; seja $X_i = \pm1$ o $i$ -ésimo passo e $S_n = X_1 + \dots + X_n$ o passeio aleatório simples em $\Z$ , $S_0 = 0$ . Como no Exemplo 21.26, todos os eventos abaixo são determinados por finitos lançamentos ou são combinações enumeráveis de tais eventos, e a independência de eventos que dependem de blocos disjuntos de lançamentos faz parte do modelo. Escrevemos $u_n = \P(S_{2n} = 0)$ e $N_n(k)$ para o número de caminhos de $\pm1$ de comprimento $n$ de $0$ a $k$ .

Parte I — Contando caminhos.

Mostre que $N_n(k) = \binom{n}{(n+k)/2}$ quando $n + k$ é par e $\abs k \leq n$ , e $0$ caso contrário; deduza $\P(S_n = k) = N_n(k)\,2^{-n}$ . Por que todo caminho individual de comprimento $n$ é igualmente provável?
Mostre que $S_{2n+1} \neq 0$ , $u_n = \binom{2n}{n}4^{-n}$ , e calcule $u_1, u_2, u_3$ .
Demonstre que $u_n = \frac{2n-1}{2n}\,u_{n-1}$ ; deduza que $(u_n)$ decresce para $0$ e, a partir do Exemplo 6.14, que

$u_n \sim \frac{1}{\sqrt{\pi n}}, \qquad\text{logo}\qquad \sum_n u_n = \infty .$
(Princípio da reflexão) Para $k \geq 1$ , mostre que os caminhos de comprimento $n$ de $1$ a $k$ que tocam $0$ estão em bijeção com os caminhos de $-1$ a $k$ ; deduza que o número de caminhos de $0$ a $k$ que permanecem $> 0$ depois do instante $0$ é $N_{n-1}(k-1) - N_{n-1}(k+1)$ .
(Teorema das cédulas) Deduza que

$\P\bigl(S_1 > 0, \dots, S_{n-1} > 0 \bigm| S_n = k\bigr) = \frac kn \qquad (k \geq 1) :$

numa apuração em que o vencedor lidera por $k$ de $n$ cédulas, a probabilidade de o vencedor ter liderado durante toda a apuração é $k/n$ . Verifique à mão para $n = 3$ , $k = 1$ .

Parte II — Retorno à origem.

Demonstre a identidade-chave

$\P(S_1 \neq 0,\ S_2 \neq 0,\ \dots,\ S_{2n} \neq 0) = u_n$

(condicione ao primeiro passo, some as contagens da questão 4 sobre o ponto final e telescope; conclua com $2\binom{2n-1}{n} = \binom{2n}{n}$ ).
Deduza da continuidade monótona (Teorema 21.6) que o passeio retorna a $0$ ao menos uma vez com probabilidade $1$ , e que $f_n := \P(\text{primeiro retorno no instante }2n)$ satisfaz

$f_n = u_{n-1} - u_n = \frac{u_n}{2n-1}, \qquad \sum_{n\geq1}f_n = 1 .$
Mostre que $\sum_n 2n\,f_n = \infty$ : o retorno é certo, mas a série que calcularia o tempo médio de espera diverge (no vocabulário do Capítulo 22, o tempo de retorno tem esperança infinita).
Demonstre que, para todo $k \geq 1$ , $\P(\text{ao menos } k\text{ retornos a }0) = 1$ (decomponha sobre os instantes dos $k$ primeiros retornos: os blocos de lançamentos correspondentes são disjuntos, de modo que as probabilidades se multiplicam e somam $(\sum_nf_n)^k$ ); conclua com a continuidade monótona:

$\P(S_n = 0 \text{ para infinitos } n) = 1 :$

o passeio aleatório simples em $\Z$ é recorrente.
Mostre que o passeio visita todo sítio $k \in \Z$ quase certamente e, portanto (por recorrência, reiniciado na primeira visita), infinitas vezes. (Os sinais das excursões sucessivas a partir de $0$ são moedas honestas independentes; uma excursão positiva visita $1$ .)

Parte III — Borel–Cantelli e o passeio viciado.

Os eventos $A_n = \{S_{2n} = 0\}$ satisfazem $\sum\P(A_n) = \infty$ ; explique por que Borel–Cantelli 2 não se aplica a eles, e o que Borel–Cantelli 1 daria se a série convergisse. (Essa é a estratégia de toda a Parte.)
Deixe agora a moeda ter viés $p \neq \frac12$ , $q = 1 - p$ . Mostre que $\P(S_{2n} = 0) = \binom{2n}n(pq)^n = u_n\,(4pq)^n$ com $4pq < 1$ , deduza $\sum_n\P(S_{2n} = 0) < \infty$ e conclua, por Borel–Cantelli 1, que o passeio viciado retorna a $0$ apenas finitas vezes, quase certamente.
Ainda para $p \neq \frac12$ : mostre que $\P(S_n = k) \leq \binom{n}{\floor{n/2}}\,(pq)^{n/2}\,(p/q)^{k/2}$ para cada $k$ fixo, deduza que todo sítio é visitado finitas vezes quase certamente e conclua que $\abs{S_n} \to \infty$ quase certamente: o passeio viciado é transiente.
De volta à moeda honesta: usando a questão 6, calcule a probabilidade de $200$ lançamentos não produzirem nenhum empate ( $S_n \neq 0$ para $1 \leq n \leq 200$ ), numericamente $u_{100} \approx 0.056$ . Comente o lento decaimento em $1/\sqrt{\pi n}$ : os empates são certos no longo prazo, mas mais raros do que a intuição sugere.
(Primeira passagem) Seja $T_1$ o primeiro instante em que o passeio atinge $1$ . Usando o princípio da reflexão para o máximo $M_n = \max_{i\leq n}S_i$ (demonstrado na questão 16, que não depende desta), ou diretamente da questão 7 condicionando ao primeiro passo, mostre que $\P(T_1 = 2n - 1) = f_n$ ; deduza $\P(T_1 < \infty) = 1$ enquanto a série do tempo médio $\sum(2n-1)f_n$ diverge.

Parte IV — Máximos, último zero, liderança longa.

(Reflexão para o máximo) Para $k \geq 1$ , demonstre que

$\P(M_n \geq k) = 2\,\P(S_n > k) + \P(S_n = k)$

refletindo o caminho após sua primeira visita ao nível $k$ .
Deduza que $\P(M_{2n} \geq 1) = 1 - u_n$ , isto é, $\P(S_i \leq 0 \text{ para todo } i \leq 2n) = u_n$ : a probabilidade de nunca estar à frente é igual à probabilidade de nunca estar em zero (questão 6) — dois eventos diferentes, uma só probabilidade.
(Último zero) Seja $L_{2n} = \max\{k \leq 2n : S_k = 0\}$ (par). Combinando a questão 6 com a independência de blocos disjuntos de lançamentos, mostre que

$\P(L_{2n} = 2k) = u_k\,u_{n-k} \qquad (0 \leq k \leq n),$

e deduza, sem cálculo adicional algum, a identidade binomial $\sum_{k=0}^n u_ku_{n-k} = 1$ .
Mostre que a lei de $L_{2n}$ é simétrica ( $\P(L = 2k) = \P(L = 2n - 2k)$ ) e, usando o $u_j \sim 1/\sqrt{\pi j}$ , que seus extremos são seus valores mais prováveis. Tabule para $n = 5$ : $\P(L_{10} = 0) = u_5 \approx 0.246$ contra $\P(L_{10} = 4) = u_2u_3 \approx 0.117$ . Interprete: num jogo honesto longo, o último empate tende a ser muito cedo ou muito tarde — as lideranças longas são a regra, não a exceção.
Reúna as questões 16–19 num parágrafo sobre o retrato de flutuação do passeio honesto: a escala difusiva sugerida pela questão 3, a certeza do retorno contra o tempo médio de espera divergente, e a persistência com sabor de arco seno das lideranças.

Parte V — A identidade de renovação e o teorema de Pólya.

Demonstre, particionando $\{S_{2n} = 0\}$ sobre o instante do primeiro retorno, a identidade de renovação

$u_n = \sum_{k=1}^n f_k\,u_{n-k} \quad (n \geq 1), \qquad\text{logo}\qquad U(x)\bigl(1 - F(x)\bigr) = 1 \quad (0 \leq x < 1),$

em que $U(x) = \sum_{n\geq0}u_nx^n$ e $F(x) = \sum_{n\geq1}f_nx^n$ (justifique os raios e o produto de séries com o Capítulo 11).
Deduza a dicotomia de recorrência: fazendo $x \to 1^-$ (limites monótonos de séries com coeficientes não negativos),

$\sum_n u_n = \infty \iff \sum_n f_n = 1 ,$

e confira-a contra as questões 3, 7 (passeio honesto) e 12 (passeio viciado).
(Dimensão $2$ ) O passeio simples em $\Z^2$ dá passos $(\pm1, 0)$ , $(0, \pm1)$ uniformemente. Mostre que as coordenadas rodadas $U_n = X_n + Y_n$ e $V_n = X_n - Y_n$ realizam passeios honestos independentes em $\Z$ , deduza

$\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi n}, \qquad \sum_n u_n^2 = \infty ,$

e conclua com as questões 21–22 (cujas demonstrações se transferem literalmente) que o passeio em $\Z^2$ é recorrente.
(Dimensão $3$ ) Para o passeio simples em $\Z^3$ , admita a estimativa local $\P(S^{(3)}_{2n} = 0) \leq C\,n^{-3/2}$ (demonstrada com o teorema limite local no volume do terceiro ano de graduação). Deduza de Borel–Cantelli 1 que o passeio em $\Z^3$ é transiente e enuncie o resultado completo: o teorema de Pólya — o passeio aleatório simples é recorrente nas dimensões $1$ e $2$ , e transiente na dimensão $3$ e acima.
Síntese. Liste o papel exato desempenhado por: a contagem de caminhos e a reflexão; a continuidade monótona; a independência de blocos disjuntos de lançamentos; Borel–Cantelli 1; a identidade de renovação. Qual único fato analítico ( $u_n \sim 1/\sqrt{\pi n}$ , logo $\sum u_n = \infty$ mas $\sum u_n^2 = \infty$ e $\sum n^{-3/2} < \infty$ ) decide entre recorrência e transiência em cada dimensão?

Solução

Solução de Problema 21.1.

1. Um caminho de comprimento $n$ é determinado pelo conjunto de seus passos para cima; terminar em $k$ significa $u$ passos para cima e $n - u$ passos para baixo com $u - (n - u) = k$ , isto é, $u = \frac{n+k}2$ : possível se e somente se $n + k$ é par e $\abs k \leq n$ , de $\binom{n}{(n+k)/2}$ modos. Cada caminho específico é um ponto da medida produto honesta em $n$ lançamentos: probabilidade $2^{-n}$ . Portanto $\P(S_n = k) = N_n(k)2^{-n}$ .

2. $S_n$ tem a paridade de $n$ , logo $S_{2n+1} \neq 0$ ; e $u_n = N_{2n}(0)4^{-n} = \binom{2n}n4^{-n}$ . Valores: $u_1 = \frac12$ , $u_2 = \frac6{16} = \frac38$ , $u_3 = \frac{20}{64} = \frac5{16}$ .

3. $\dfrac{u_n}{u_{n-1}} = \dfrac{\binom{2n}n}{4\binom{2n-2}{n-1}} = \dfrac{(2n)(2n-1)}{4n^2} = \dfrac{2n-1}{2n} < 1$ : decrescente. Pelo Exemplo 6.14, $\binom{2n}n \sim \frac{4^n}{\sqrt{\pi n}}$ , logo $u_n \sim \frac1{\sqrt{\pi n}} \to 0$ , e $\sum u_n$ diverge por comparação com $\sum n^{-1/2}$ .

4. Dado um caminho de $1$ a $k$ que toca $0$ , reflita seu segmento inicial (até a primeira visita a $0$ ) em relação ao eixo horizontal: o resultado é um caminho de $-1$ a $k$ , e a operação é uma involução — todo caminho de $-1$ a $k \geq 1$ tem de cruzar $0$ , e refletir seu segmento inicial de volta recupera o original. Portanto os caminhos que tocam são em número de $N_{n-1}(k + 1)$ (de $-1$ a $k$ o deslocamento é $k + 1$ ). Um caminho de $0$ a $k$ que permanece $> 0$ depois do instante $0$ começa com um passo para cima e vai então de $1$ a $k$ em $n - 1$ passos sem tocar $0$ : há $N_{n-1}(k-1) - N_{n-1}(k+1)$ deles.

5. Com $m = \frac{n+k}2$ , usando $\binom{n-1}{m-1} = \frac mn\binom nm$ e $\binom{n-1}{m} = \frac{n-m}n\binom nm$ :

\frac{N_{n-1}(k-1) - N_{n-1}(k+1)}{N_n(k)} = \frac{\binom{n-1}{m-1} - \binom{n-1}{m}}{\binom nm} = \frac{m - (n - m)}{n} = \frac kn .

Para $n = 3$ , $k = 1$ : $N_3(1) = 3$ caminhos ( $++-$ , $+-+$ , $-++$ ), dos quais apenas $++-$ permanece positivo ( $+-+$ retorna a $0$ no instante $2$ ): um em três, e $\frac kn = \frac13$ .

6. Por simetria, a probabilidade vale $2\P(S_i > 0\ \forall i \leq 2n)$ . Somando sobre o ponto final $2k$ e usando a questão 4 (com $n$ substituído por $2n$ ):

\P(S_i > 0\ \forall i) = 2^{-2n}\sum_{k\geq1} \bigl(N_{2n-1}(2k-1) - N_{2n-1}(2k+1)\bigr) = 2^{-2n}\,N_{2n-1}(1),

uma soma telescópica. Ora, $N_{2n-1}(1) = \binom{2n-1}{n}$ e $2\binom{2n-1}n = \binom{2n}n$ (Pascal), de modo que a probabilidade exibida vale $2\cdot2^{-2n}\binom{2n-1}n = \binom{2n}n4^{-n} = u_n$ .

7. Os eventos $D_n = \{S_i \neq 0,\ i \leq 2n\}$ decrescem, com interseção “nenhum retorno jamais”; pela continuidade monótona e pela questão 6, $\P(\text{nenhum retorno}) = \lim u_n = 0$ : o passeio retorna quase certamente. Além disso, $f_n = \P(D_{n-1}) - \P(D_n) = u_{n-1} - u_n$ e, pela questão 3,

u_{n-1} - u_n = u_n\Bigl(\frac{2n}{2n-1} - 1\Bigr) = \frac{u_n}{2n-1}; \qquad \sum_{n\geq1}f_n = u_0 - \lim u_n = 1 .

8. $2n\,f_n = \frac{2n}{2n-1}u_n \geq u_n$ , e $\sum u_n = \infty$ (questão 3): a série $\sum 2nf_n$ diverge. O primeiro retorno é certo, mas não tem tempo médio de espera finito — o passeio é recorrente nulo, no vocabulário que o Capítulo 22 fornecerá.

9. O evento “ao menos $k$ retornos” é a união enumerável disjunta, sobre $0 < n_1 < \dots < n_k$ , dos eventos “os $k$ primeiros retornos ocorrem exatamente nos instantes $2n_1, \dots, 2n_k$ ”. Um tal evento é a interseção de $k$ eventos que dependem dos blocos disjuntos de lançamentos $\intint1{2n_1}$ , $\intint{2n_1+1}{2n_2}$ , …, exigindo cada bloco que um passeio novo faça seu primeiro retorno após exatamente o número de passos alocado; pela independência dos blocos, sua probabilidade vale $f_{n_1}f_{n_2-n_1}\cdots f_{n_k-n_{k-1}}$ . Somando por pacotes (Capítulo 7, todos os termos não negativos):

\P(\text{ao menos }k\text{ retornos}) = \Bigl(\sum_{n\geq1}f_n\Bigr)^{\!k} = 1^k = 1 .

Os eventos decrescem em $k$ , de modo que, pela continuidade monótona, $\P(\text{infinitos retornos}) = 1$ : recorrência.

10. Pela questão 9, o passeio faz infinitas excursões para fora de $0$ . O primeiro passo de cada excursão é uma moeda nova, independente de tudo o que veio antes: a probabilidade de as $m$ primeiras excursões começarem todas para baixo vale $2^{-m}$ . Para atingir $1$ o passeio só precisa do início de uma excursão para cima (a partir de $<0$ ele tem de passar por $0$ antes de atingir $1$ , sendo os passos $\pm1$ ), logo $\P(\text{nunca atinge }1) \leq 2^{-m}$ para todo $m$ : o passeio atinge $1$ quase certamente. Decompondo sobre o instante de atingimento (quase certamente finito), o passeio reiniciado ali é um passeio novo começado em $1$ : por indução ele atinge todo $k \geq 1$ quase certamente e, por simetria, todo $k \leq -1$ . Enfim, reiniciando na primeira visita a $k$ , a questão 9 se aplica ao passeio novo: todo sítio é visitado infinitas vezes, quase certamente.

11. Os eventos $A_n = \{S_{2n} = 0\}$ estão longe de ser independentes (estar em $0$ no instante $2n$ torna estar em $0$ no instante $2n + 2$ muito mais provável que $u_{n+1}$ ), de modo que Borel–Cantelli 2 não está disponível e, de fato, todo o trabalho da Parte II foi substituí-lo. A outra direção não precisa de independência: se $\sum\P(A_n)$ converge, Borel–Cantelli 1 dá finitos retornos quase certamente. Essa implicação é o motor de toda demonstração de transiência abaixo.

12. Um retorno no instante $2n$ exige $n$ passos para cima e $n$ para baixo: $\P(S_{2n} = 0) = \binom{2n}np^nq^n = u_n(4pq)^n$ e $4pq = 1 - (p - q)^2 < 1$ para $p \neq \frac12$ . Como $u_n \leq 1$ , a série $\sum\P(S_{2n} = 0)$ é dominada pela geométrica $\sum(4pq)^n$ : convergente. Por Borel–Cantelli 1, $\P(S_{2n} = 0 \text{ infinitas vezes}) = 0$ : finitos retornos, quase certamente.

13. Para $n + k$ par, $\P(S_n = k) = \binom{n}{\frac{n+k}2}p^{\frac{n+k}2}q^{\frac{n-k}2}$ ; o coeficiente binomial é no máximo o central, e $p^{\frac{n+k}2}q^{\frac{n-k}2} = (pq)^{n/2}(p/q)^{k/2}$ , o que dá a cota anunciada $\leq 2^n(pq)^{n/2}(p/q)^{k/2} = (4pq)^{n/2}(p/q)^{k/2}$ , somável em $n$ pois $\sqrt{4pq} < 1$ . Borel–Cantelli 1: o sítio $k$ é visitado finitas vezes quase certamente; a união sobre $k \in \Z$ dos eventos excepcionais nulos ainda é nula (subaditividade enumerável). Quase certamente todo sítio é visitado finitas vezes, de modo que a sequência de inteiros $(S_n)$ deixa toda janela limitada de vez: $\abs{S_n} \to \infty$ .

14. $\P(S_n \neq 0,\ 1 \leq n \leq 200) = u_{100} = \binom{200}{100}4^{-100} \approx \frac1{\sqrt{100\pi}} \approx 0.056$ : mais de uma chance em vinte de que $200$ lançamentos honestos nunca empatem. O decaimento $1/\sqrt{\pi n}$ é excruciantemente lento: a certeza de um empate (questão 7) é compatível com trechos sem empate muito longos — um primeiro gosto dos fenômenos do arco seno da Parte IV.

15. Condicione ao primeiro passo. Se $X_1 = +1$ , então $T_1 = 1$ , e $f_1 = \frac12$ confere. Se $X_1 = -1$ , o passeio deve subir de $-1$ a $1$ ; pela decomposição em blocos, retornar a $0$ pela primeira vez no instante $2n$ se decompõe assim: um passo para baixo e depois um passeio novo começado em $-1$ atingindo $0$ pela primeira vez — equivalentemente, um passeio novo atingindo $+1$ pela primeira vez — em $2n - 1$ passos, ou o evento simétrico para cima. Ambos os sinais contribuem igualmente:

f_n = 2\cdot\tfrac12\,\P(T_1 = 2n - 1) = \P(T_1 = 2n-1) .

Portanto $\P(T_1 < \infty) = \sum f_n = 1$ , enquanto $\sum_n(2n - 1)f_n = \sum_n u_n = \infty$ pela questão 7: o passeio atinge $1$ quase certamente, em tempo médio infinito.

16. Particione $\{M_n \geq k\}$ pelo valor terminal $S_n = m$ . Para $m \geq k$ a condição $M_n \geq k$ é automática. Para $m < k$ , reflita o caminho após sua primeira visita ao nível $k$ : isso é uma bijeção entre $\{M_n \geq k, S_n = m\}$ e $\{S_n = 2k - m\}$ (todo caminho que termina em $2k - m > k$ visita $k$ ; refletir de volta é a inversa). Portanto

\P(M_n \geq k) = \sum_{m > k}\P(S_n = m) + \P(S_n = k) + \sum_{m < k}\P(S_n = 2k - m) = 2\P(S_n > k) + \P(S_n = k).

17. No instante par $2n$ com $k = 1$ : $\P(S_{2n} = 1) = 0$ e $\P(S_{2n} > 1) = \P(S_{2n} \geq 2)$ , logo

\P(M_{2n} \geq 1) = 2\P(S_{2n} \geq 2) = \P(S_{2n} \geq 2) + \P(S_{2n} \leq -2) = 1 - u_n .

Assim, $\P(S_i \leq 0\ \forall i \leq 2n) = u_n$ : o passeio nunca lidera nos $2n$ primeiros passos exatamente tão frequentemente quanto nunca empata (questão 6) — dois eventos bem diferentes, carregados pelo mesmo $u_n$ .

18. $\{L_{2n} = 2k\} = \{S_{2k} = 0\} \cap \{\text{o passeio dos lançamentos } 2k+1, \dots, 2n \text{ não tem zero}\}$ . Os dois eventos dependem de blocos disjuntos de lançamentos, logo são independentes; o primeiro tem probabilidade $u_k$ , o segundo $u_{n-k}$ pela questão 6 aplicada ao passeio novo de $(2n-2k)$ passos. Portanto $\P(L_{2n} = 2k) = u_ku_{n-k}$ . Como $L_{2n}$ assume exatamente os valores $0, 2, \dots, 2n$ , essas probabilidades somam $1$ : $\sum_{k=0}^nu_ku_{n-k} = 1$ , uma identidade binomial entregue por uma partição probabilística.

19. A simetria é imediata: $u_ku_{n-k} = u_{n-k}u_k$ . Como $u_j$ decresce em $j$ , o produto $u_ku_{n-k}$ é menor para $k$ central e maior nos extremos $k \in \{0, n\}$ , em que vale $u_n$ ; quantitativamente, $u_ku_{n-k} \approx \frac1{\pi\sqrt{k(n-k)}}$ no miolo, contra $u_n \approx \frac1{\sqrt{\pi n}}$ nas bordas. Para $n = 5$ : $\P(L_{10} = 0) = \P(L_{10} = 10) = u_5 = \frac{63}{256} \approx 0.246$ , enquanto $\P(L_{10} = 4) = u_2u_3 = \frac38\cdot\frac5{16} = \frac{15}{128} \approx 0.117$ . Num jogo honesto longo, a última igualação é mais provavelmente muito perto do começo ou muito perto do fim: um jogador tipicamente lidera por trechos enormes, sem viés algum na moeda.

20. O retrato: no instante $n$ o passeio vive na escala $\sqrt n$ (a dispersão binomial da questão 3 — $u_n \sim 1/\sqrt{\pi n}$ é a altura do pico central); ele retorna a $0$ infinitas vezes com probabilidade $1$ (Parte II) e, no entanto, o tempo de espera entre retornos tem média divergente (questão 8), razão pela qual excursões isoladas podem ocupar uma fração positiva de qualquer horizonte; correspondentemente, o último empate de um jogo de $2n$ passos se espalha com os valores extremos mais prováveis (questões 18–19), e nunca liderar tem a mesma probabilidade lentamente decrescente $u_n$ que nunca empatar (questão 17). Certeza no limite, persistência em todo horizonte finito: eis o passeio honesto.

21. Particione $\{S_{2n} = 0\}$ ( $n \geq 1$ ) pelo instante do primeiro retorno $2k$ , $1 \leq k \leq n$ : o primeiro bloco de $2k$ lançamentos realiza um primeiro retorno, os $2n - 2k$ lançamentos restantes realizam um retorno de um passeio novo, e os blocos são independentes: $u_n = \sum_{k=1}^nf_ku_{n-k}$ . Ambas as séries $U(x) = \sum u_nx^n$ , $F(x) = \sum f_nx^n$ têm raio $\geq 1$ (coeficientes em $\intcc01$ ), e o produto de Cauchy (Capítulo 11) dá, para $0 \leq x < 1$ ,

U(x) - 1 = \sum_{n\geq1}\Bigl(\sum_{k=1}^n f_ku_{n-k}\Bigr)x^n = F(x)\,U(x), \qquad\text{i.e.}\qquad U(x)\bigl(1 - F(x)\bigr) = 1 .

22. Quando $x \uparrow 1$ , $U(x)$ e $F(x)$ crescem (coeficientes não negativos); toda soma parcial de $\sum_{n\leq N}u_n$ é limite de $\sum_{n\leq N}u_nx^n \leq U(x)$ , logo $U(x) \uparrow \sum u_n \in \intoc0{+\infty}$ e, do mesmo modo, $F(x) \uparrow f = \sum f_n$ . Se $\sum u_n = \infty$ : $1 - F(x) = 1/U(x) \to 0$ , logo $f = 1$ . Se $\sum u_n = S < \infty$ : $1 - f = 1/S > 0$ , logo $f < 1$ . Verificações: passeio honesto, $\sum u_n = \infty$ e $f = 1$ (questões 3, 7); passeio viciado, $\sum u_n(4pq)^n < \infty$ e, correspondentemente, $f = 1 - 1/\sum_{n\geq0}u_n(4pq)^n < 1$ , coerente com a finitude quase certa do número de retornos (questão 12).

23. Para os quatro passos $(\pm1, 0), (0, \pm1)$ do passeio em $\Z^2$ , os incrementos de $U = X + Y$ e de $V = X - Y$ são: $(+,+)$ para $(1,0)$ , $(+,-)$ para $(0,1)$ , $(-,+)$ para $(0,-1)$ , $(-,-)$ para $(-1,0)$ — cada par de sinais com probabilidade $\frac14 = \frac12\cdot\frac12$ : os dois passeios coordenados $(U_n)$ e $(V_n)$ são passeios honestos independentes em $\Z$ . Como $S^{(2)}_{2n} = (0,0)$ se e somente se $U_{2n} = 0$ e $V_{2n} = 0$ ,

\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi n}, \qquad \sum_nu_n^2 = \infty .

A identidade de renovação da questão 21 e a dicotomia da questão 22 não usaram nada unidimensional (apenas a decomposição sobre o primeiro retorno e a independência de blocos disjuntos), de modo que $\sum u_n^{(2)} = \infty$ dá $f^{(2)} = 1$ , e o argumento da questão 9 o reforça: o passeio em $\Z^2$ retorna à origem infinitas vezes quase certamente.

24. Com a cota admitida $\P(S^{(3)}_{2n} = 0) \leq Cn^{-3/2}$ , a série converge, e Borel–Cantelli 1 dá finitos retornos quase certamente: o passeio em $\Z^3$ é transiente (e a mesma cota com expoente $-d/2$ trata todo $d \geq 3$ ). Ao todo: o teorema de Pólya — o passeio aleatório simples é recorrente em $\Z$ e $\Z^2$ , transiente em $\Z^d$ para $d \geq 3$ . Um bêbado encontra o caminho de casa; um pássaro bêbado talvez não.

25. A contagem de caminhos e a reflexão produziram as leis exatas ( $u_n$ , o teorema das cédulas, $f_n$ , o máximo, o último zero); a continuidade monótona converteu toda afirmação limite (“retorna ao menos uma vez”, “infinitas vezes”) num limite de probabilidades de horizonte finito; a independência de blocos disjuntos moveu as decomposições de renovação (questões 9, 18, 21) — ela é o esqueleto enumerável da propriedade de Markov; Borel–Cantelli 1 foi a arma da transiência (questões 12–13, 24), sem precisar de independência; a identidade de renovação organizou tudo na dicotomia $\sum u_n = \infty \iff$ recorrência. O único insumo analítico é a estimativa local $u_n \sim 1/\sqrt{\pi n}$ : seu quadrado $1/(\pi n)$ ainda diverge (dimensão $2$ , recorrente), enquanto $n^{-3/2}$ converge (dimensão $3$ , transiente) — o teorema de Pólya é, no fim das contas, uma afirmação sobre a divergência de $\sum n^{-d/2}$ .

21.1 Espaços de probabilidade

21.2 Condicionamento e independência

21.3 O lema de Borel–Cantelli

21.4 Exercícios

21.5 Problema: o passeio aleatório simples em Z\ZZ é recorrente

21.5 Problema: o passeio aleatório simples em $\Z$ é recorrente