--- title: "Probabilidade em espaços enumeráveis" book: "Matemática universitária — Graduação 2" subject: math language: pt chapter: 21 exercises: 12 source: https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis --- # Capítulo 21 — Probabilidade em espaços enumeráveis Os três últimos capítulos desenvolvem a teoria moderna da probabilidade: [medidas de probabilidade](#def-b2-proba-space) em [espaços amostrais](#def-b2-proba-space) [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable), variáveis aleatórias discretas e [funções geradoras](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#ex-b2-powerseries-fibonacci). A teoria finita do volume do ensino médio adquire sua infraestrutura [completa](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-complete): a $\sigma$-aditividade substitui a aditividade finita, e a maquinaria das [famílias somáveis](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) do [Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series) é exatamente o que torna manejáveis os [espaços amostrais](#def-b2-proba-space) infinitos. Os resultados centrais aqui são a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) da probabilidade ao longo de sequências monótonas de [eventos](#def-b2-proba-space) 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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) (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: 1. $\P(\Omega) = 1$ ; 2. ($\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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable)). **Observação 21.2.** Num $\Omega$ [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) podemos tomar todos os subconjuntos como [eventos](#def-b2-proba-space); em espaços não [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) (como é preciso para os modelos [contínuos](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) do terceiro ano) isso já não é possível, e restringe-se $\P$ a uma coleção adequada de [eventos](#def-b2-proba-space), uma *$\sigma$-álgebra*. Todas as fórmulas deste capítulo sobrevivem literalmente a essa generalização. **Proposição 21.3 (Regras elementares).** Para [eventos](#def-b2-proba-space) $A, B$ e uma [medida de probabilidade](#def-b2-proba-space) $\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](#exo-b2-proba-4). ∎ **Proposição 21.4 (Distribuições num espaço enumerável).** Dar uma [medida de probabilidade](#def-b2-proba-space) num $\Omega = \{\omega_0, \omega_1, \dots\}$ [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-def) convergente) da família $(p_i)$. **Demonstração.** Dada $\P$, os conjuntos unitários $\{\omega\}$, $\omega \in A$, formam uma cobertura disjunta [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) não negativa $(p_i)$ — reordenar é inofensivo precisamente porque os termos são não negativos ([Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)); 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable), e a $\sigma$-aditividade é exatamente o teorema de soma por pacotes do [Capítulo 7](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series) 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](#def-b2-proba-space), 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](#def-b2-proba-space) deve ainda conter a possibilidade de que ele não termine. A aditividade [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) é 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](#def-b2-proba-space). 1. 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)$ . 2. 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](#def-b2-proba-space), $\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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#def-b2-proba-space) — 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](#def-b2-proba-independence), 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](https://one-course.com/books/math/4/pt/chapter/22-variaveis-aleatorias-discretas#ch-b2-randomvar), 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](#def-b2-proba-space) com $\P(B_n) = 1 - (5/6)^n$. A [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#def-b2-proba-space) sobre *infinitos* lançamentos, fora do alcance da aditividade finita, e a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#def-b2-proba-space) $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](#def-b2-proba-space) em $\Omega$. **Observação 21.11.** Que $A \mapsto \pcond BA$ seja de novo uma [medida de probabilidade](#def-b2-proba-space) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#def-b2-proba-space) 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).** 1. (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}) .$$ 2. (Probabilidade total) Se $(B_i)_{i \in I}$ é uma partição finita ou [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) de $\Omega$ com $\P(B_i) > 0$, então, para todo [evento](#def-b2-proba-space) $A$: $$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$$ 3. (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](#def-b2-proba-conditional) 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](#def-b2-proba-space) 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](#def-b2-proba-independence) 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 \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](#exo-b2-proba-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](#def-b2-proba-space) errado*: em Monty Hall, o [evento](#def-b2-proba-space) 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](#def-b2-proba-independence)*: [eventos](#def-b2-proba-space) disjuntos de probabilidade positiva nunca são [independentes](#def-b2-proba-independence) ($\P(A\cap B) = 0 \neq \P(A)\P(B)$) — [independência](#def-b2-proba-independence) é compatibilidade de informação, não ausência de sobreposição. **Definição 21.19 (Independência).** Os [eventos](#def-b2-proba-space) $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](#def-b2-proba-space) é *(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](#def-b2-proba-independence) mútua é estritamente mais forte que a [independência](#def-b2-proba-independence) dois a dois: com dois lançamentos de moeda honesta, os [eventos](#def-b2-proba-space) “o primeiro é cara”, “o segundo é cara”, “os dois coincidem” são dois a dois [independentes](#def-b2-proba-independence) (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](#def-b2-proba-independence), 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](#def-b2-proba-independence), 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](#def-b2-proba-space) que dependem de grupos disjuntos de lançamentos são [independentes](#def-b2-proba-independence)” (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](#ex-b2-proba-geometric), 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](#exo-b2-proba-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](#exo-b2-proba-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](#def-b2-proba-space), o [evento](#def-b2-proba-space) $$ \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](#def-b2-proba-space) “$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](#def-b2-proba-space) “*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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) em toda parte, de modo que todos esses são [eventos](#def-b2-proba-space) honestos. **Teorema 21.25 (Borel–Cantelli).** 1. Se $\sum_{n} \P(A_n) < \infty$ , então $\P\bigl(\limsup_n A_n\bigr) = 0$ . 2. Se os [eventos](#def-b2-proba-space) $A_n$ são [independentes](#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) ([Corolário 21.7](#cor-b2-proba-subadd)), $$ \P(C_N) \leq \sum_{n \geq N}\P(A_n) \xrightarrow[N\to\infty]{} 0 $$ (cauda de uma série convergente). A [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona ([Teorema 21.6](#thm-b2-proba-continuity)) 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](#def-b2-proba-space) $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](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) ([Corolário 21.7](#cor-b2-proba-subadd)), de modo que a interseção [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) $\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](#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#def-b2-proba-space) “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](#def-b2-proba-space) $A_{jk}$ ($j = 1, 2, \dots$), dependendo de blocos disjuntos de lançamentos, são [independentes](#def-b2-proba-independence), 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable), 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](#def-b2-proba-independence) de um alfabeto de $26$ letras. Corte o texto datilografado em blocos disjuntos de quatro letras; os [eventos](#def-b2-proba-space) $A_j = {}$“o bloco $j$ soletra MATH” são [independentes](#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/18-curvas#def-b2-curves-length), 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](#ex-b2-proba-runs) o [espaço amostral](#def-b2-proba-space) subjacente (sequências infinitas de lançamentos) é não [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable), 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](#def-b2-proba-space) determinados por finitos lançamentos e suas combinações [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable). Essa é a convenção padrão nesse nível: a teoria é enunciada em espaços [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable), 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](#def-b2-proba-space) em variáveis aleatórias, e a $\sigma$-aditividade se torna a [somabilidade](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) que define a esperança ([Capítulo 22](https://one-course.com/books/math/4/pt/chapter/22-variaveis-aleatorias-discretas#ch-b2-randomvar)); Borel–Cantelli mais uma cota de cauda [somável](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) é exatamente como a lei forte dos grandes números para moedas é demonstrada lá. No [Capítulo 23](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun), a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona*: exiba o [evento](#def-b2-proba-space) como uma união crescente (ou interseção decrescente) de [eventos](#def-b2-proba-space) de horizonte finito com probabilidades calculáveis ([Exemplo 21.9](#ex-b2-proba-sixeventually)). *Uniões nulas*: uma união [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) de [eventos](#def-b2-proba-space) de probabilidade zero é nula (subaditividade [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable)), de modo que basta matar cada [evento](#def-b2-proba-space) 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](#def-b2-proba-space) é um limsup, some as probabilidades; a convergência o mata (sem precisar de [independência](#def-b2-proba-independence)), e a divergência mais a [independência](#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#pb-b2-proba-1) no problema de fim de semana deste capítulo, o lado quase certo da lei dos grandes números ([Capítulo 22](https://one-course.com/books/math/4/pt/chapter/22-variaveis-aleatorias-discretas#ch-b2-randomvar)) e a análise de extinção dos processos de ramificação ([Capítulo 23](https://one-course.com/books/math/4/pt/chapter/23-funcoes-geradoras-de-probabilidade#ch-b2-genfun)). 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](#def-b2-proba-space) não [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) 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 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](#def-b2-proba-space) 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](#def-b2-proba-space) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series).)* **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](#def-b2-proba-space). 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series)), $$ \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 de Exercício 21.3.** Sejam $S$ = doente e $+$ = teste positivo. Bayes ([Teorema 21.14](#thm-b2-proba-bayes)) 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](#def-b2-proba-space). 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 de Exercício 21.4.** [Pontualmente](https://one-course.com/books/math/4/pt/chapter/10-sequencias-e-series-de-funcoes#def-b2-funcseq-def) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) — cada indicadora se torna a probabilidade de seu [evento](#def-b2-proba-space), 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](#exo-b2-proba-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 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 de Exercício 21.6.** Condicione ao início (regra da cadeia / [Teorema 21.14](#thm-b2-proba-bayes)): - 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](#def-b2-proba-space) “o jogo dura mais de $n$” decrescem para “o jogo nunca termina”; a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona ([Teorema 21.6](#thm-b2-proba-continuity)) 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](#def-b2-proba-independence), 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](#def-b2-proba-space) $R_n$ são [independentes](#def-b2-proba-independence) 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 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](#def-b2-proba-space) 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](#def-b2-proba-independence) (admitido), de modo que Borel–Cantelli 2 ([Teorema 21.25](#thm-b2-proba-borelcantelli)) dá $\P(\limsup R_n) = 1$: os recordes nunca param, quase certamente — mas eles rareiam logaritmicamente. *Recordes consecutivos:* pela [independência](#def-b2-proba-independence), $$ \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](#def-b2-proba-independence) 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](#def-b2-proba-space) (dependentes) com $\sum\P(A_n) = \infty$ e $\P(\limsup A_n) = 0$, mostrando que a [independência](#def-b2-proba-independence) não pode ser dispensada em Borel–Cantelli 2. **Solução de Exercício 21.8.** *Primeira parte:* $\sum \P(A_n) = \sum\frac{1}{n+1} = \infty$ com [independência](#def-b2-proba-independence): 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](#def-b2-proba-independence):* tome $\Omega = \N^*$ com os pesos $p_k = \frac{1}{k(k+1)}$ do [Exercício 21.2](#exo-b2-proba-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](#def-b2-proba-space) se empilham numa parte encolhente do espaço — a [independência](#def-b2-proba-independence) é 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 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](#def-b2-proba-independence) 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 de Exercício 21.10.** Os [eventos](#def-b2-proba-space) $B_N = \bigcap_{n=1}^N A_n^c$ decrescem para $\bigcap_nA_n^c$ e, pela [independência](#def-b2-proba-independence) dos complementares, $\P(B_N) = \prod_{n=1}^N(1 - p_n)$; a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona ([Teorema 21.6](#thm-b2-proba-continuity)) 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 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](#def-b2-proba-independence), de modo que esse [evento](#def-b2-proba-space) 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](#def-b2-proba-space) 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 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.](https://one-course.com/images/onecourse/chapters/math-4/b2-proba/fig-1c561d473a2b.svg) *Vinte e quatro passos de um [passeio aleatório simples](#pb-b2-proba-1); 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](#ex-b2-proba-runs), todos os [eventos](#def-b2-proba-space) abaixo são determinados por finitos lançamentos ou são combinações [enumeráveis](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) de tais [eventos](#def-b2-proba-space), e a [independência](#def-b2-proba-independence) de [eventos](#def-b2-proba-space) 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](https://one-course.com/books/math/4/pt/chapter/18-curvas#def-b2-curves-length) $n$ de $0$ a $k$. **Parte I — Contando caminhos.** 1. 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](https://one-course.com/books/math/4/pt/chapter/18-curvas#def-b2-curves-length) $n$ é igualmente provável? 2. Mostre que $S_{2n+1} \neq 0$ , $u_n = \binom{2n}{n}4^{-n}$ , e calcule $u_1, u_2, u_3$ . 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](https://one-course.com/books/math/4/pt/chapter/6-comparacao-de-funcoes#ex-b2-comparison-centralbinomial), que $$u_n \sim \frac{1}{\sqrt{\pi n}}, \qquad\text{logo}\qquad \sum_n u_n = \infty .$$ 4. (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)$ . 5. (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.** 6. 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}$)*. 7. Deduza da [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona ([Teorema 21.6](#thm-b2-proba-continuity)) 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 .$$ 8. 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](https://one-course.com/books/math/4/pt/chapter/22-variaveis-aleatorias-discretas#ch-b2-randomvar) , o tempo de retorno tem esperança infinita). 9. 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona: $$\P(S_n = 0 \text{ para infinitos } n) = 1 :$$ o [passeio aleatório simples](#pb-b2-proba-1) em $\Z$ é *recorrente*. 10. 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](#def-b2-proba-independence); uma excursão positiva visita $1$.)* **Parte III — Borel–Cantelli e o passeio viciado.** 11. Os [eventos](#def-b2-proba-space) $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.) 12. 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. 13. 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* . 14. 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. 15. (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.** 16. (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$. 17. 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](#def-b2-proba-space) diferentes, uma só probabilidade. 18. (Último zero) Seja $L_{2n} = \max\{k \leq 2n : S_k = 0\}$ (par). Combinando a questão 6 com a [independência](#def-b2-proba-independence) 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$. 19. Mostre que a lei de $L_{2n}$ é [simétrica](https://one-course.com/books/math/4/pt/chapter/12-formas-quadraticas#def-b2-quadratic-adjoint) ( $\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. 20. 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.** 21. 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](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#ch-b2-powerseries)). 22. 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). 23. (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](#def-b2-proba-independence)* 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. 24. (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](#pb-b2-proba-1) é recorrente nas dimensões $1$ e $2$ , e transiente na dimensão $3$ e acima. 25. Síntese. Liste o papel exato desempenhado por: a contagem de caminhos e a reflexão; a [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona; a [independência](#def-b2-proba-independence) de blocos disjuntos de lançamentos; Borel–Cantelli 1; a identidade de renovação. Qual único fato [analítico](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#def-b2-powerseries-analytic) ( $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 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](https://one-course.com/books/math/4/pt/chapter/6-comparacao-de-funcoes#ex-b2-comparison-centralbinomial), $\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](#def-b2-proba-space) $D_n = \{S_i \neq 0,\ i \leq 2n\}$ decrescem, com interseção “nenhum retorno jamais”; pela [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](https://one-course.com/books/math/4/pt/chapter/22-variaveis-aleatorias-discretas#ch-b2-randomvar) fornecerá. **9.** O [evento](#def-b2-proba-space) “ao menos $k$ retornos” é a união [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) disjunta, sobre $0 < n_1 < \dots < n_k$, dos [eventos](#def-b2-proba-space) “os $k$ primeiros retornos ocorrem exatamente nos instantes $2n_1, \dots, 2n_k$”. Um tal [evento](#def-b2-proba-space) é a interseção de $k$ [eventos](#def-b2-proba-space) 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](#def-b2-proba-independence) 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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#ch-b2-series), 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](#def-b2-proba-space) decrescem em $k$, de modo que, pela [continuidade](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) 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](#def-b2-proba-independence) 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](#def-b2-proba-space) $A_n = \{S_{2n} = 0\}$ estão longe de ser [independentes](#def-b2-proba-independence) (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](#def-b2-proba-independence): *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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#def-b2-series-summable) 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](#def-b2-proba-space) excepcionais nulos ainda é nula (subaditividade [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable)). 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](#def-b2-proba-space) 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](#def-b2-proba-space) dependem de blocos disjuntos de lançamentos, logo são [independentes](#def-b2-proba-independence); 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](#def-b2-proba-independence): $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](https://one-course.com/books/math/4/pt/chapter/7-sequencias-e-series#thm-b2-series-fubini) ([Capítulo 11](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#ch-b2-powerseries)) 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](#def-b2-proba-independence) 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](#def-b2-proba-independence) 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](#pb-b2-proba-1) é 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](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#def-b2-metric-continuity) monótona converteu toda afirmação limite (“retorna ao menos uma vez”, “infinitas vezes”) num limite de probabilidades de horizonte finito; a [independência](#def-b2-proba-independence) de blocos disjuntos moveu as decomposições de renovação (questões 9, 18, 21) — ela é o esqueleto [enumerável](https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas#def-b2-structures-countable) da propriedade de Markov; Borel–Cantelli 1 foi a arma da transiência (questões 12–13, 24), sem precisar de [independência](#def-b2-proba-independence); a identidade de renovação organizou tudo na dicotomia $\sum u_n = \infty \iff$ recorrência. O único insumo [analítico](https://one-course.com/books/math/4/pt/chapter/11-series-de-potencias#def-b2-powerseries-analytic) é 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}$.