Capítulo 4

Cadeias de Markov enumeráveis

Em uma cadeia finita, toda classe fechada irredutível é recorrente. Quando o espaço é infinito, a cadeia pode caminhar para longe e nunca retornar.

Em um espaço infinito, uma cadeia irredutível pode ser transiente. Mesmo quando é recorrente, o tempo médio de retorno pode ser infinito; nesse caso, não há distribuição estacionária. Os critérios de retorno, as equações de primeiro passo e o teorema ergódico continuam disponíveis, sob as hipóteses estabelecidas nos capítulos anteriores.

Os passeios aleatórios revelam a influência da dimensão sobre a recorrência. O protocolo Aloha descreve um sistema de comunicação com infinitos estados; nos processos de ramificação, o estado é o tamanho de uma população. Os problemas de síntese reúnem esses modelos no estudo da ruína, do crescimento de filas e da extinção. Por fim, a percolação em árvores e os grafos aleatórios mostram como a ideia de ramificação também ajuda a estudar a formação de grandes componentes em uma rede.

4.1 Passeios aleatórios em \(\mathbb Z^d\)

O critério de recorrência do Teorema 2.16 ganha uma interpretação concreta para passeios aleatórios: basta estimar a probabilidade de o passeio estar novamente na origem após \(n\) passos.

Definição 4.1

Passeio aleatório simples e simétrico em \(\mathbb Z^d\) Fixe \(x\in \mathbb Z^d\), com \(d\geq 1\). Sejam \(\xi _1,\xi _2,\ldots \) vetores aleatórios independentes e identicamente distribuídos tais que

\[ \mathbb {P}(\xi _n=e_j)=\mathbb {P}(\xi _n=-e_j)=\frac{1}{2d}, \qquad j=1,\ldots ,d, \]

onde \(e_1,\ldots ,e_d\) é a base canônica. O processo

\[ S_0=x,\qquad S_n=x+\xi _1+\cdots +\xi _n,\quad n\geq 1, \]

é o passeio aleatório simples e simétrico em \(\mathbb Z^d\).

Sob \(\mathbb P_x\), o passeio parte de \(x\). Como a lei dos incrementos não depende da posição, começar em outro estado apenas desloca a trajetória: \(\mathbb P_x(S_n=x)=\mathbb P_0(S_n=0)\). Por isso, estudaremos os retornos à origem. A Figura 4.1 mostra uma realização em dimensão um.

Figura 4.1 Passeio aleatório simples e simétrico em Z. — Figura 4.1 Passeio aleatório simples e simétrico em \(\mathbb {Z}\).

Exemplo 4.1 (Quantos caminhos retornam em dois e quatro passos?)

As probabilidades de estar novamente na origem após poucos passos podem ser calculadas por contagem de caminhos. Aqui admitimos visitas anteriores à origem: não estamos calculando probabilidades de primeiro retorno. Partindo da origem em \(\mathbb Z^d\), o primeiro passo pode ocorrer em qualquer uma das \(2d\) direções. Para retornar no segundo passo, deve-se escolher a direção oposta. Portanto,

\[ \mathbb P_0(S_2=0)=\frac{2d}{(2d)^2}=\frac1{2d}. \]

Em quatro passos há dois tipos de caminho fechado. No primeiro, todos os passos são paralelos a um mesmo eixo: há \(d\) escolhas do eixo e \(\binom 42=6\) maneiras de ordenar os dois passos positivos e os dois negativos. No segundo, são usados dois eixos distintos, com um passo positivo e um negativo em cada eixo: há \(\binom d2\) escolhas dos eixos e \(4!=24\) ordenações. Para \(d=1\), esse segundo tipo não ocorre, de acordo com \(\binom 12=0\). Assim,

\[ \begin{aligned} \mathbb P_0(S_4=0) & =\frac{6d+24\binom d2}{(2d)^4}\\ & =\frac{3(2d-1)}{8d^3}. \end{aligned} \]

Em particular,

\[ \begin{array}{c|cc} d& \mathbb P_0(S_2=0)& \mathbb P_0(S_4=0)\\ \hline 1& 1/2& 3/8\\ 2& 1/4& 9/64\\ 3& 1/6& 5/72 \end{array} \]

Essas contas mostram que a dimensão altera as probabilidades de retorno já nos primeiros passos. A classificação em recorrente ou transiente depende, porém, da soma sobre todos os instantes.

Os vértices de \(\mathbb Z^d\) se dividem em duas classes: aqueles cuja soma das coordenadas é par e aqueles cuja soma é ímpar. Cada passo liga vértices de classes diferentes; assim, o grafo é bipartido. Como a soma vale zero na origem, o passeio só pode retornar a ela em instantes pares.

Para estimar as probabilidades de retorno, usaremos a fórmula de Stirling,

\[ n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n. \]

Teorema 4.1

Recorrência em \(\mathbb Z\) O passeio simples e simétrico em \(\mathbb Z\) é recorrente. Mais geralmente, se um passo vale \(+1\) com probabilidade \(p\) e \(-1\) com probabilidade \(q=1-p\), o passeio é recorrente se e somente se \(p=q=1/2\).

Demonstração ▼

Se \(p=0\) ou \(p=1\), o passeio se move sempre no mesmo sentido e nunca retorna à origem. Suponha, portanto, \(0\lt p\lt 1\). Para retornar à origem no instante \(2n\), são necessários exatamente \(n\) passos para a direita e \(n\) para a esquerda. Logo,

\[ \mathbb {P}_0(S_{2n}=0)=\binom {2n}{n}p^nq^n. \]

Pela fórmula de Stirling,

\begin{equation} \label{eq:cap1-binomial-central-stirling} \binom {2n}{n} =\frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{4\pi n}\, (2n/e)^{2n}}{2\pi n\, (n/e)^{2n}} =\frac{4^n}{\sqrt{\pi n}}. \tag{4.1} \end{equation}

Consequentemente,

\[ \mathbb {P}_0(S_{2n}=0) =\binom {2n}{n}p^nq^n \sim \frac{(4pq)^n}{\sqrt{\pi n}}. \]

Como não há retornos em instantes ímpares, basta examinar \(\sum _{n\geq 1}\mathbb {P}_0(S_{2n}=0)\). Se \(p=q=1/2\), temos \(4pq=1\) e os termos dessa série são assintoticamente equivalentes a \(1/\sqrt{\pi n}\). Ela diverge, pois \(\sum _{n\geq 1}n^{-1/2}\) diverge. Se \(p\neq q\), então \(4pq=1-(p-q)^2\lt 1\). Como \(\binom {2n}{n}\leq \sum _{j=0}^{2n}\binom {2n}{j}=4^n\), temos \(\mathbb {P}_0(S_{2n}=0)\leq (4pq)^n\) para todo \(n\geq 1\). A série converge por comparação com a série geométrica \(\sum _{n\geq 1}(4pq)^n\). Pelo Teorema 2.16, a origem é recorrente no primeiro caso e transiente no segundo. Por invariância por translação, a mesma classificação vale para todos os estados.

Lema 4.2

Identidade de Vandermonde Para todo \(n\geq 0\),

\[ \sum _{k=0}^{n}\binom nk^2=\binom {2n}{n}. \]

Demonstração ▼

Expandindo os dois fatores pelo binômio de Newton, temos

\[ (1+x)^n(1+x)^n =\left(\sum _{k=0}^{n}\binom nkx^k\right) \left(\sum _{\ell =0}^{n}\binom n\ell x^\ell \right). \]

Um termo de grau \(n\) é obtido escolhendo \(x^k\) no primeiro fator e \(x^{n-k}\) no segundo. Assim, o coeficiente de \(x^n\) no produto é \(\sum _{k=0}^n\binom nk\binom n{n-k}\). Como \(\binom n{n-k}=\binom nk\), essa soma é o lado esquerdo da identidade. Por outro lado, o produto é \((1+x)^{2n}\), cujo coeficiente de \(x^n\) é \(\binom {2n}{n}\). Igualar os coeficientes prova a afirmação, inclusive para \(n=0\).

Teorema 4.3

Recorrência em \(\mathbb Z^2\) O passeio aleatório simples e simétrico em \(\mathbb Z^2\) é recorrente.

Demonstração ▼

Em um caminho fechado com \(2n\) passos, suponha que haja \(k\) passos para a direita e \(k\) para a esquerda. Restam \(n-k\) passos para cima e \(n-k\) para baixo. Para cada \(k\), observamos que

\[ \frac{(2n)!}{k!^2(n-k)!^2} =\frac{(2n)!}{(n!)^2} \left(\frac{n!}{k!(n-k)!}\right)^2 =\binom {2n}{n}\binom nk^2. \]

Portanto, somando sobre \(k\) e usando a identidade de Vandermonde demonstrada acima, o número de caminhos fechados é

\[ \sum _{k=0}^{n}\frac{(2n)!}{k!^2(n-k)!^2} =\binom {2n}{n}\sum _{k=0}^{n}\binom nk^2 =\binom {2n}{n}^{\! 2}. \]

Cada sequência específica de \(2n\) passos tem probabilidade \(4^{-2n}\), pois em cada instante há quatro direções equiprováveis. Consequentemente,

\[ \mathbb P_0(S_{2n}=0) =\binom {2n}{n}^{\! 2}4^{-2n} =\left(\frac{\binom {2n}{n}}{4^n}\right)^2. \]

Pela estimativa (4.1), \(\binom {2n}{n}/4^n\sim 1/\sqrt{\pi n}\). Elevando ao quadrado, obtemos

\[ \boxed {\mathbb P_0(S_{2n}=0)\sim \frac1{\pi n}.} \]

Como a série \(\sum _{n\ge 1}1/n\) diverge, a série das probabilidades de retorno também diverge. Pelo Teorema 2.16, a origem é recorrente; por translação, todos os estados são recorrentes.

A recorrência garante que o passeio volta à origem, mas não que o tempo médio até esse retorno seja finito. As estimativas que acabamos de obter permitem responder também a essa segunda pergunta.

Corolário 4.4

Recorrência nula em dimensões um e dois O passeio aleatório simples e simétrico em \(\mathbb Z^d\) é recorrente nulo para \(d=1\) e \(d=2\).

Demonstração ▼

Em ambos os casos, o passeio é recorrente e \(P^n(0,0)=\mathbb P_0(S_n=0)\to 0\): nos instantes pares, isso decorre das equivalências assintóticas obtidas; nos ímpares, a probabilidade é zero. Denote por

\[ N_n(0)=\sum _{m=1}^n\mathbf1_{\{ S_m=0\} } \]

o número de visitas à origem entre os instantes \(1\) e \(n\). Então

\[ E_0\left[\frac{N_n(0)}n\right] =\frac1n\sum _{m=1}^nP^m(0,0)\longrightarrow 0. \]

Para justificar esse limite, fixe \(\varepsilon \gt 0\) e escolha \(m_0\) tal que \(P^m(0,0)\lt \varepsilon \) para \(m\geq m_0\). Os termos anteriores a \(m_0\) são finitos e, divididos por \(n\), tendem a zero; os restantes contribuem no máximo \(\varepsilon \) à média. Mais explicitamente, para \(n\geq m_0\),

\[ 0\leq \frac1n\sum _{m=1}^{n}P^m(0,0) \leq \frac{m_0-1}{n}+\varepsilon . \]

Primeiro fazemos \(n\) crescer e depois tomamos \(\varepsilon \) arbitrariamente pequeno, obtendo o limite anunciado.

Por outro lado, o Teorema 3.4 dá \(N_n(0)/n\to 1/E_0(T_0^+)\) quase certamente. Como essas variáveis ficam entre zero e um, o Lema 3.5 mostra que suas esperanças convergem para a mesma constante. Logo, \(1/E_0(T_0^+)=0\), isto é, \(E_0(T_0^+)=\infty \). Por translação, a conclusão vale para todos os estados.

A Figura 4.2 mostra uma trajetória no plano e sua distância à origem. Os zeros no segundo painel identificam os retornos da trajetória desenhada no primeiro.

Figura 4.2 Uma realização do passeio simples em Z^2. No painel A, a origem e o ponto final S_(48) estão destacados. No painel B, os zeros de lVert S_nrVert _1 nos instantes 8, 22 e 34 correspondem aos retornos à origem da mesma trajetória. — Figura 4.2 Uma realização do passeio simples em \(\mathbb Z^2\). No painel A, a origem e o ponto final \(S_{48}\) estão destacados. No painel B, os zeros de \(\lVert S_n\rVert _1\) nos instantes \(8\), \(22\) e \(34\) correspondem aos retornos à origem da mesma trajetória.

Teorema 4.5

Transiência em \(\mathbb Z^3\) O passeio aleatório simples e simétrico em \(\mathbb Z^3\) é transiente.

Demonstração ▼

Em dimensão três, a contagem dos caminhos fechados produz uma soma mais difícil de calcular exatamente. Para provar a transiência, basta obter uma cota para a probabilidade de retorno cuja série seja convergente. Combinaremos a estimativa do coeficiente binomial central com uma cota para o maior termo de uma distribuição multinomial.

Um retorno à origem só pode ocorrer após um número par de passos. Consideremos, portanto, \(2n\) passos, com \(n\ge 1\). Denote por \(i,j,k\) as quantidades de passos nas direções positivas dos três eixos. Para que o deslocamento final seja zero, precisamos ter também \(i,j,k\) passos nas respectivas direções negativas. Assim,

\[ i+j+k=n. \]

Para valores fixados de \(i,j,k\), estamos ordenando seis tipos de passos, com multiplicidades \(i,i,j,j,k,k\). O número dessas sequências é

\[ \frac{(2n)!}{i!^2j!^2k!^2}. \]

Cada sequência tem probabilidade \(6^{-2n}\), porque há seis direções equiprováveis. Somando sobre todas as possibilidades, chegamos a

\[ \mathbb P_0(S_{2n}=0) =\frac1{6^{2n}} \sum _{\substack {i,j,k\ge 0\\ i+j+k=n}} \frac{(2n)!}{i!^2j!^2k!^2}. \]

Primeiro passo: reconhecer uma distribuição de probabilidade. Defina

\[ a_{i,j,k}=\frac{n!}{i!j!k!}\, 3^{-n}, \qquad i+j+k=n. \]

Esse é o valor da probabilidade de obter \(i,j,k\) resultados em três categorias equiprováveis, em \(n\) ensaios independentes. Pela fórmula multinomial,

\[ \sum _{i+j+k=n}a_{i,j,k} =\left(\frac13+\frac13+\frac13\right)^n=1. \]

Com esses números, a expressão admite a fatoração

\[ \frac{(2n)!}{i!^2j!^2k!^2} =\binom {2n}{n} \left(\frac{n!}{i!j!k!}\right)^2. \]

Como \(6^{2n}=2^{2n}3^{2n}\), a probabilidade de retorno fica

\[ \mathbb P_0(S_{2n}=0) =\frac{\binom {2n}{n}}{2^{2n}} \sum _{i+j+k=n}a_{i,j,k}^{\, 2}. \]

Não precisaremos calcular a soma dos quadrados: como todos os termos são não negativos e somam um,

\[ \sum _{i+j+k=n}a_{i,j,k}^{\, 2} \leq \left(\max _{i+j+k=n}a_{i,j,k}\right) \sum _{i+j+k=n}a_{i,j,k} =\max _{i+j+k=n}a_{i,j,k}. \]

Logo,

\[ \mathbb P_0(S_{2n}=0) \leq \frac{\binom {2n}{n}}{2^{2n}}\, M_n, \qquad M_n:=\max _{i+j+k=n}a_{i,j,k}. \]

Segundo passo: estimar o maior termo multinomial. O máximo ocorre quando \(i,j,k\) diferem entre si por no máximo uma unidade. Para ver isso, suponha, por exemplo, que \(i\ge j+2\). Ao trocar \((i,j,k)\) por \((i-1,j+1,k)\), a razão entre o novo termo e o anterior é

\[ \frac{a_{i-1,j+1,k}}{a_{i,j,k}} =\frac{i}{j+1}\gt 1. \]

Assim, enquanto duas coordenadas diferirem por duas ou mais unidades, podemos aumentar o termo aproximando-as. No máximo, as três coordenadas estão tão equilibradas quanto possível.

Comecemos pelo caso \(n=3m\). Então o maior termo é \(M_{3m}=a_{m,m,m}\). Pela fórmula de Stirling, \(k!\sim \sqrt{2\pi k}(k/e)^k\), obtemos

\[ \begin{aligned} M_{3m} & =\frac{(3m)!}{(m!)^3}\, 3^{-3m}\\ & \sim \frac{\sqrt{6\pi m}(3m/e)^{3m}}{(2\pi m)^{3/2}(m/e)^{3m}\, 3^{3m}}\\ & =\frac{\sqrt3}{2\pi m} =\frac{3\sqrt3}{2\pi n}. \end{aligned} \]

Em particular, \(M_{3m}\) é da ordem de \(1/m\).

Para os demais valores de \(n\), se \(n=3m+1\), os índices maximais são \((m+1,m,m)\) e suas permutações. Se \(n=3m+2\), são \((m+1,m+1,m)\) e suas permutações. Comparando diretamente os fatoriais com os do caso \(3m\),

\[ \begin{aligned} M_{3m+1} & =\frac{3m+1}{3(m+1)}\, M_{3m},\\ M_{3m+2} & =\frac{(3m+2)(3m+1)}{9(m+1)^2}\, M_{3m}. \end{aligned} \]

Ambos os fatores são no máximo um. Como \(n=3m\), \(3m+1\) ou \(3m+2\) tem a mesma ordem de grandeza que \(m\) para \(m\ge 1\), existe uma constante \(C_2\) tal que

\[ M_n\leq \frac{C_2}{n}\qquad (n\ge 1). \]

Os casos \(n=1,2\) são incluídos aumentando \(C_2\), se necessário.

Terceiro passo: reunir as duas estimativas. A estimativa (4.1) fornece

\[ \frac{\binom {2n}{n}}{2^{2n}}\sim \frac1{\sqrt{\pi n}}. \]

Assim, existe uma constante \(C_1\) tal que \(\binom {2n}{n}/2^{2n}\leq C_1/\sqrt n\) para \(n\) suficientemente grande. Aumentando \(C_1\), incluímos também os primeiros valores de \(n\). Portanto,

\[ \boxed {\mathbb P_0(S_{2n}=0) \leq \frac{C_1}{\sqrt n}\frac{C_2}{n} =\frac{C}{n^{3/2}}.} \]

Não há retornos em instantes ímpares. Como \(\sum _{n\ge 1}n^{-3/2}\) converge, também converge \(\sum _{k\ge 1}\mathbb P_0(S_k=0)\). Pelo critério de recorrência, a origem é transiente. A invariância por translação estende essa conclusão a todos os estados.

Corolário 4.6

Transiência em dimensões maiores O passeio aleatório simples e simétrico em \(\mathbb Z^d\) é transiente para todo \(d\geq 3\).

Demonstração ▼

Para \(d\gt 3\), projete o passeio nas três primeiras coordenadas. A projeção fica parada quando o passo ocorre numa das demais coordenadas. Se a observarmos apenas nos instantes em que ela se move, obtemos o passeio simples em \(\mathbb Z^3\); esse processo é a cadeia de saltos da projeção. De fato, cada passo move uma dessas três coordenadas com probabilidade \(6/(2d)=3/d\). Condicionadas à ocorrência de um movimento, as seis direções projetadas têm probabilidade \((1/(2d))/(3/d)=1/6\) cada uma. Como os incrementos originais são independentes, essas direções sucessivas também são independentes.

O tempo de espera até cada movimento tem distribuição geométrica com parâmetro \(3/d\gt 0\) e é finito quase certamente: a probabilidade de esperar mais de \(r\) passos é \((1-3/d)^r\), que tende a zero. Os tempos de espera formam uma sequência enumerável; portanto, com probabilidade um, todos são finitos. Pela transiência em dimensão três, a cadeia de saltos visita a origem apenas um número finito de vezes e todas as suas permanências têm duração finita. Nesse mesmo evento, a projeção está na origem em apenas um número finito de instantes. Toda visita do passeio original à origem exige que a projeção esteja na origem. Portanto, o passeio em \(\mathbb Z^d\) é transiente.

Os resultados anteriores compõem o teorema de Pólya: o passeio simples e simétrico é recorrente nas dimensões \(1\) e \(2\) e transiente em todas as dimensões maiores.

Heurística

A fronteira dimensional Mais geralmente, as probabilidades de retorno em tempos pares têm ordem \(n^{-d/2}\). Esse é um resultado adicional: demonstramos a equivalência assintótica nas dimensões \(1\) e \(2\), uma cota superior suficiente na dimensão \(3\) e a transiência por projeção nas dimensões maiores. A ordem exata para todas as dimensões requer estimativas mais precisas das probabilidades de transição; veja Lawler 2006. A série correspondente diverge em dimensões \(1\) e \(2\), mas converge a partir da dimensão \(3\). Essa é a mudança de regime por trás do teorema de Pólya.

4.2 Um sistema com infinitos estados: o protocolo Aloha

Nos passeios, perguntamos se a trajetória retorna a um estado. Em um sistema de comunicação, os estados podem registrar o número de mensagens pendentes. O exemplo a seguir mostra como as colisões podem impedir o escoamento dessas mensagens e fazer a fila crescer.

Exemplo 4.2 (Protocolo Aloha: colisões que bloqueiam o canal)

Em uma versão simplificada do protocolo Aloha, mensagens novas tentam transmitir assim que chegam; cada mensagem que já sofreu uma colisão tenta novamente, independentemente das outras, com probabilidade \(r=1/2\) por intervalo. Se exatamente uma mensagem transmitir, ela sai do sistema. Se duas ou mais transmitirem, ocorre uma colisão e nenhuma sai.

Suponha que, em cada intervalo \(n\), cheguem \(A_n=1\) mensagem com probabilidade \(3/4\) ou \(A_n=2\) mensagens com probabilidade \(1/4\), independentemente entre intervalos. As decisões de retransmissão são renovadas a cada intervalo, independentemente das novas chegadas e de todos os sorteios anteriores. Seja \(X_n\) o número de mensagens pendentes antes das novas chegadas no intervalo \(n\), com \(X_0=0\). A Figura 4.3 resume as possibilidades de transmissão.

Figura não resolvida: figuras/aloha-colisoes.tikz

Figura 4.3 As tentativas simultâneas competem pelo mesmo canal. Apenas quando há exatamente uma transmissão ocorre uma saída.

Escreva \(I_n=1\) quando há uma transmissão bem-sucedida no intervalo \(n\) e \(I_n=0\) caso contrário. Então

\[ X_{n+1}=X_n+A_n-I_n. \]

Se chegam duas mensagens, elas colidem entre si e \(X_n\) aumenta em duas unidades. Se chega uma, o número de mensagens pendentes fica igual ou aumenta em uma unidade. Portanto, \(X_n\) nunca diminui.

Há uma particularidade importante nesta versão do modelo: sempre chega pelo menos uma mensagem nova, e ela tenta transmitir imediatamente. Por isso, uma mensagem pendente nunca consegue sair: qualquer tentativa sua colide com uma nova transmissão. O único sucesso possível ocorre quando chega uma única mensagem e todas as pendentes ficam em silêncio; nesse caso, quem sai é a mensagem recém-chegada.

Dado \(X_n=k\), as probabilidades do próximo estado dependem apenas de \(k\), pois os novos sorteios são independentes do passado. Assim, \((X_n)\) é uma cadeia de Markov em \(\mathbb N_0\), com transições

\[ \begin{aligned} p(k,k)& =\frac34\, 2^{-k},\\ p(k,k+1)& =\frac34(1-2^{-k}),\\ p(k,k+2)& =\frac14, \end{aligned} \]

e todas as demais probabilidades são zero. Cada estado é transiente: partindo de \(k\), a probabilidade de permanecer nele durante os próximos \(r\) intervalos é \(p(k,k)^r\), que tende a zero porque \(p(k,k)\lt 1\). Portanto, a cadeia o deixa em tempo finito quase certamente; como nunca diminui, não pode retornar depois de sair.

Além do crescimento da fila, ocorre um bloqueio persistente do canal: ao longo de infinitos intervalos, ocorrem somente finitas transmissões bem-sucedidas, quase certamente. Para demonstrá-lo, observamos que a condição de sucesso descrita acima dá

\[ \mathbb P(I_n=1\mid X_n=k)=\frac34\, 2^{-k}. \]

Se \(M_n\) é o número de intervalos entre \(0\) e \(n-1\) em que chegaram duas mensagens, então \(X_n\geq 2M_n\) e \(M_n\) tem distribuição binomial com parâmetros \(n\) e \(1/4\). Cada intervalo com duas chegadas acrescenta duas mensagens à fila, e os demais nunca a fazem diminuir; isso explica a desigualdade \(X_n\geq 2M_n\). Além disso, escrevendo \(M_n\) como soma dos indicadores independentes desses intervalos, obtemos

\[ E(4^{-M_n}) =\prod _{k=0}^{n-1}E\bigl(4^{-\mathbf1_{\{ A_k=2\} }}\bigr) =\left(\frac34+\frac14\cdot \frac14\right)^n. \]

Consequentemente,

\[ \begin{aligned} \mathbb P(I_n=1) & =\frac34 E(2^{-X_n}) \leq \frac34 E(4^{-M_n})\\ & =\frac34\left(\frac34+\frac14\cdot \frac14\right)^n =\frac34\left(\frac{13}{16}\right)^n. \end{aligned} \]

Para contar todos os sucessos, somamos primeiro até um instante finito e depois fazemos esse instante crescer. Pela linearidade da esperança e pela passagem ao limite para contagens crescentes, justificada no Lema 2.15, obtemos

\[ E\left(\sum _{n=0}^{\infty }I_n\right) =\sum _{n=0}^{\infty }\mathbb P(I_n=1) \leq \frac34\sum _{n=0}^{\infty }\left(\frac{13}{16}\right)^n =\boxed {4}. \]

Uma variável não negativa com esperança finita não pode ser infinita com probabilidade positiva. Para ver isso aqui, se \(S=\sum _{n\geq 0}I_n\), a desigualdade de Markov dá \(\mathbb P(S\geq r)\leq 4/r\) para todo \(r\geq 1\); como \(\{ S=\infty \} \subseteq \{ S\geq r\} \), sua probabilidade é zero. Logo, o número total de sucessos é finito quase certamente, embora mensagens continuem chegando. As tentativas simultâneas impedem o escoamento das mensagens.

A conclusão vale para a versão de carga elevada considerada aqui. Outras leis de chegada exigem uma análise própria.

Nos passeios e no protocolo Aloha, acompanhamos deslocamentos ou o acúmulo de mensagens. No próximo modelo, a população de uma geração produz a seguinte: o tamanho atual continua sendo toda a informação necessária para descrever o próximo passo, mas cada indivíduo contribui com uma quantidade aleatória de novos indivíduos.

4.3 Processos de ramificação

Uma população pode crescer em média e, ainda assim, desaparecer. O tamanho esperado, por si só, não determina a probabilidade de extinção.

A ideia de acompanhar sucessivas gerações não se limita a populações de seres vivos. Ela aparece também em sistemas físicos e em processos de transmissão, como mostram os exemplos a seguir.

Linhagens familiares. A partir de um indivíduo, acompanhamos seus filhos, netos, bisnetos e assim por diante. O número de filhos pode variar de uma pessoa para outra, e cada filho pode dar continuidade à linhagem por meio de seus próprios descendentes. Quantos membros haverá em uma geração futura? Qual é a probabilidade de que a linhagem deixe de ter descendentes?

Multiplicadores de elétrons. Um elétron que atinge uma superfície pode provocar a emissão de vários outros elétrons. Estes são conduzidos a uma segunda superfície, onde podem produzir novas emissões. Em uma sequência de etapas, um pequeno número inicial de elétrons pode dar origem a um sinal muito maior. Cada etapa corresponde a uma geração, e o número de elétrons emitidos por impacto faz o papel do número de filhos.

Reações em cadeia. Um nêutron pode provocar a fissão de um núcleo atômico, liberando novos nêutrons, que podem provocar outras fissões. Nem todo nêutron dá continuidade à reação: ele pode escapar do material ou ser absorvido sem produzir uma fissão. Em uma aproximação por gerações, podemos perguntar se a sequência de fissões se interrompe ou continua.

Início de uma epidemia. Uma pessoa infectada pode transmitir a doença a um número aleatório de outras pessoas. Estas podem produzir novas infecções, formando sucessivas gerações de transmissão. Quando ainda há muitas pessoas suscetíveis e diferentes cadeias de transmissão raramente alcançam a mesma pessoa, um processo de ramificação pode aproximar essa fase inicial. As gerações indicam quem infectou quem, não intervalos de tempo de igual duração.

Nesses exemplos, cada elemento pode produzir um número aleatório de novos elementos. Para construir um modelo comum, chamaremos esses elementos de indivíduos e acompanharemos o total em cada geração.

O tamanho de cada geração será o estado de uma cadeia de Markov. Condicionando no tamanho da geração anterior, calcularemos a média e a variância da população; com as funções geradoras, estudaremos a probabilidade de extinção. Ao final, discutiremos o que se pode estimar a partir de dados de cascatas de compartilhamentos, em uma aplicação que também pode ser lida separadamente.

4.3.1 Indivíduos, gerações e crescimento médio

Considere uma população que evolui em gerações. Cada indivíduo produz um número aleatório de filhos, independentemente dos demais e sempre segundo a mesma distribuição. Esses filhos formam a geração seguinte, na qual o mecanismo se repete. Assim, o tamanho de cada geração é determinado pela soma dos números de filhos dos indivíduos da geração anterior.

Definição 4.2

Processo de Galton–Watson Seja \(Y\) uma variável com valores em \(\mathbb N_0=\{ 0,1,2,\ldots \} \) e lei \(p_j=\mathbb {P}(Y=j)\). Considere cópias independentes \((Y_{n,r})_{n\geq 0,r\geq 1}\) de \(Y\). Para \(Z_0=k\in \mathbb N_0\), defina

\[ Z_{n+1}=\sum _{r=1}^{Z_n}Y_{n,r}. \]

A soma vazia vale zero. O processo \((Z_n)\) é um processo de Galton–Watson, e \((p_j)\) é sua distribuição de descendentes.

O índice \(n\) identifica a geração e \(r\) distingue os indivíduos que a compõem. A fórmula conta os filhos de todos eles. Se dois indivíduos produzem, respectivamente, três e nenhum filho, a geração seguinte terá tamanho três. A família \((Y_{n,r})\) registra quantos filhos cada indivíduo tem, enquanto a sequência \((Z_n)\) conserva apenas os totais por geração. Assim, árvores genealógicas diferentes podem produzir a mesma sequência de tamanhos.

A. Árvore genealógica

Ilustração: Indivíduos, gerações e crescimento médio

B. Evolução dos tamanhos

Figura não resolvida: figuras/ramificacao-tamanhos.tikz

Figura 4.4 A árvore acompanha os indivíduos e os seus filhos; o gráfico registra apenas os totais por geração, aqui \(Z_0=1\), \(Z_1=3\) e \(Z_2=3\). O indivíduo central da geração 1 não deixa descendentes.

Se sabemos que \(Z_n=i\), há exatamente \(i\) indivíduos para se reproduzir. As gerações até \(n\) foram determinadas pelos sorteios \(Y_{\ell ,r}\) com \(\ell \lt n\). Os números de filhos \(Y_{n,1},\ldots ,Y_{n,i}\) são independentes desses sorteios e têm todos a lei de \(Y\). Por isso, conhecer as gerações anteriores não altera a distribuição da próxima: basta saber \(Z_n\). Essa é a propriedade de Markov, e as probabilidades de transição são

\[ p(i,j)=\mathbb {P}(Y_1+\cdots +Y_i=j),\qquad p(0,0)=1, \]

onde \(Y_1,\ldots ,Y_i\) são cópias independentes de \(Y\). O estado zero é absorvente: se uma geração não tem indivíduos, a seguinte também estará vazia.

A independência das reproduções, o uso da mesma lei por todos os indivíduos e a separação em gerações são hipóteses do modelo, não propriedades automáticas de uma população real.

Exemplo 4.3 (Uma linha da matriz de transição)

Suponha que cada indivíduo não tenha filhos com probabilidade \(1/3\) e tenha dois filhos com probabilidade \(2/3\). Se \(Z_n=2\), então

\[ Z_{n+1}=Y_1+Y_2, \]

com \(Y_1,Y_2\) independentes e valores em \(\{ 0,2\} \). Portanto,

\[ p(2,0)=\left(\frac13\right)^2=\frac19, \qquad p(2,2)=2\frac13\frac23=\frac49, \qquad p(2,4)=\left(\frac23\right)^2=\frac49. \]

Para obter dois filhos ao todo, exatamente um dos dois indivíduos deve reproduzir-se; as duas escolhas possíveis explicam o fator \(2\) em \(p(2,2)\). Essas são todas as possibilidades, e suas probabilidades somam um.

O mesmo raciocínio vale para qualquer tamanho inicial. Se \(Z_n=i\), o número \(B\) de indivíduos que produzem dois filhos tem distribuição binomial com parâmetros \(i\) e \(2/3\), e \(Z_{n+1}=2B\). Assim, para \(0\leq k\leq i\),

\[ p(i,2k)=\binom {i}{k} \left(\frac23\right)^k \left(\frac13\right)^{i-k}, \]

enquanto \(p(i,j)=0\) nos demais casos.

Teorema 4.7

Tamanho esperado da geração Se \(m=E(Y)\lt \infty \) e \(Z_0=k\), então \(E(Z_n)=km^n\) para todo \(n\geq 0\), com \(m^0=1\).

O fator \(m\) tem uma interpretação simples: cada indivíduo deixa, em média, \(m\) filhos, de modo que a esperança do tamanho da população é multiplicada por \(m\) de uma geração para a seguinte. Isso se refere à média entre possíveis evoluções, não ao crescimento de cada trajetória. Algumas populações podem desaparecer, enquanto outras crescem o suficiente para sustentar a esperança.

Demonstração ▼

Se \(Z_n=i\), os \(i\) indivíduos produzem filhos, cada um com esperança \(m\). Pela linearidade da esperança,

\[ E(Z_{n+1}\mid Z_n=i)=im. \]

Retiramos o condicionamento somando sobre os possíveis tamanhos da geração atual. Pela esperança total,

\[ \begin{aligned} E(Z_{n+1}) & =\sum _{i=0}^{\infty }E(Z_{n+1}\mid Z_n=i)\, \mathbb P(Z_n=i)\\ & =\sum _{i=0}^{\infty }im\, \mathbb P(Z_n=i) =mE(Z_n). \end{aligned} \]

Na soma, os valores de \(i\) com probabilidade zero não contribuem. Como \(Z_0=k\) é constante, \(E(Z_0)=k\). Se \(E(Z_n)=km^n\lt \infty \), a igualdade anterior dá \(E(Z_{n+1})=km^{n+1}\lt \infty \). Isso estabelece simultaneamente a fórmula e a finitude das esperanças por indução, incluindo \(n=0\).

A média não informa quanto os tamanhos das gerações podem variar entre uma realização e outra. Para estudar essa variação, suponha que a distribuição de filhos tenha variância finita \(\sigma ^2=\operatorname {Var}(Y)\).

Proposição 4.8

Variância do tamanho da geração Se \(\sigma ^2\lt \infty \) e \(Z_0=k\), então \(v_n=\operatorname {Var}(Z_n)\) satisfaz

\[ v_0=0,\qquad v_{n+1}=\sigma ^2km^n+m^2v_n. \]

Em particular, se \(m=1\), então \(v_n=kn\sigma ^2\) para todo \(n\geq 0\).

Demonstração ▼

Escreva \(v_n=\operatorname {Var}(Z_n)\). Dado \(Z_n=i\), a geração seguinte é formada pelos filhos desses \(i\) indivíduos. Como os números de filhos são independentes, cada um com média \(m\) e variância \(\sigma ^2\), temos

\[ E(Z_{n+1}\mid Z_n=i)=im,\qquad \operatorname {Var}(Z_{n+1}\mid Z_n=i)=i\sigma ^2. \]

O segundo momento é a soma da variância com o quadrado da média. Aplicando essa identidade à distribuição condicionada, obtemos

\[ E(Z_{n+1}^2\mid Z_n=i)=i\sigma ^2+i^2m^2. \]

Para calcular o segundo momento de \(Z_{n+1}\), tomamos agora a esperança sobre os possíveis valores de \(Z_n\). Como

\[ E(Z_{n+1}^2\mid Z_n=i)=i\sigma ^2+i^2m^2, \]

a fórmula da esperança total fornece

\[ \begin{aligned} E(Z_{n+1}^2) & =E\bigl[E(Z_{n+1}^2\mid Z_n)\bigr]\\ & =E\bigl[\sigma ^2 Z_n+m^2Z_n^2\bigr]\\ & =\sigma ^2E(Z_n)+m^2E(Z_n^2). \end{aligned} \]

Essa igualdade também permite verificar que os segundos momentos são finitos. De fato, como \(Z_0=k\), temos \(E(Z_0^2)=k^2\lt \infty \). Suponha agora que \(E(Z_n^2)\lt \infty \). Como já sabemos que \(E(Z_n)=km^n\) é finita, a igualdade anterior mostra que \(E(Z_{n+1}^2)\lt \infty \). Portanto, por indução, todos os segundos momentos são finitos.

Podemos, então, calcular a variância subtraindo o quadrado da média. Usando \(E(Z_{n+1})=mE(Z_n)\), encontramos

\[ \begin{aligned} v_{n+1} & =E(Z_{n+1}^2)-[E(Z_{n+1})]^2\\ & =\sigma ^2E(Z_n) +m^2\bigl(E(Z_n^2)-[E(Z_n)]^2\bigr)\\ & =\sigma ^2km^n+m^2v_n. \end{aligned} \]

Na última igualdade, usamos \(E(Z_n)=km^n\) e reconhecemos, entre parênteses, a variância de \(Z_n\).

Se \(m=1\), a recorrência se reduz a

\[ v_{n+1}=k\sigma ^2+v_n. \]

Assim, a variância aumenta \(k\sigma ^2\) a cada geração. Como \(Z_0=k\) é constante, temos \(v_0=0\) e, portanto,

\[ v_n=nk\sigma ^2. \]

Os dois termos da recorrência têm origens diferentes. O primeiro mede a variabilidade produzida pela reprodução na geração atual; o segundo vem da variação no número de indivíduos que chegaram a essa geração.

Com um indivíduo inicial e média de um filho, temos

\[ E(Z_n)=1,\qquad \operatorname {Var}(Z_n)=n\sigma ^2. \]

Se \(\sigma ^2\gt 0\), a média permanece constante, mas a variância cresce linearmente. Isso não significa que a população se mantenha perto de um indivíduo. Veremos que, nesse caso, ela acaba se extinguindo com probabilidade um.

Exemplo 4.4 (Dois multiplicadores de elétrons)

Retomemos os multiplicadores de elétrons mencionados na abertura. Em cada etapa, um elétron pode provocar a emissão de novos elétrons, que seguem para a etapa seguinte. Considere dois modelos, nos quais os números de elétrons emitidos por impactos diferentes são independentes e seguem, em todas as etapas, as distribuições:

\[ \begin{array}{c|cc} \text{Elétrons emitidos} & \text{Modelo A} & \text{Modelo B}\\ \hline 0 & 1/4 & 1/2\\ 2 & 1/2 & 0\\ 4 & 1/4 & 1/2 \end{array} \]

Os dois equipamentos começam com dois elétrons e possuem três etapas de amplificação. Qual deles produz, em média, mais elétrons na saída? Em qual o sinal final é menos variável?

Se \(Y_A\) e \(Y_B\) representam o número de elétrons emitidos por um impacto, as médias são iguais:

\[ E(Y_A)=2\cdot \frac12+4\cdot \frac14=2, \qquad E(Y_B)=4\cdot \frac12=2. \]

As variâncias, porém, são diferentes. Calculando os segundos momentos, obtemos

\[ \begin{aligned} \operatorname {Var}(Y_A) & =\left(2^2\cdot \frac12+4^2\cdot \frac14\right)-2^2=2,\\ \operatorname {Var}(Y_B) & =4^2\cdot \frac12-2^2=4. \end{aligned} \]

Denote por \(Z_n\) o número de elétrons após a etapa \(n\), com \(Z_0=2\). Como \(m=2\) nos dois modelos, o tamanho esperado da terceira geração é o mesmo:

\[ E(Z_3)=2\cdot 2^3=16. \]

Para calcular a variância, usamos a recorrência da Proposição 4.8. Com \(k=m=2\) e \(v_0=0\), ela fornece

\[ v_1=2\sigma ^2,\qquad v_2=12\sigma ^2,\qquad v_3=56\sigma ^2. \]

Portanto,

\[ \operatorname {Var}(Z_3)= \begin{cases} 112,& \text{no modelo A},\\ 224,& \text{no modelo B}. \end{cases} \]

Embora os dois equipamentos produzam o mesmo sinal médio, o modelo A apresenta menor variabilidade.

Há ainda outra diferença. Para que não reste nenhum elétron após a primeira etapa, os dois elétrons iniciais precisam deixar zero descendentes. Pela independência, essa probabilidade é

\[ \mathbb P(Z_1=0)= \begin{cases} (1/4)^2=1/16,& \text{no modelo A},\\ (1/2)^2=1/4,& \text{no modelo B}. \end{cases} \]

Assim, a mesma média de reprodução pode acompanhar comportamentos bastante distintos, tanto na variabilidade do sinal quanto na chance de ele desaparecer. Para estudar a extinção em um número qualquer de gerações, precisaremos considerar toda a distribuição de descendentes.

4.3.2 Geradoras e extinção

Para calcular a probabilidade de extinção, precisamos ir além do crescimento médio. Compare duas regras: na primeira, cada indivíduo tem exatamente um filho; na segunda, ele tem zero ou dois filhos, cada possibilidade com probabilidade \(1/2\). Ambas têm média um, mas, na primeira, a população permanece sempre com o mesmo tamanho, enquanto, na segunda, veremos que a extinção é certa. Para entender essa diferença, precisamos levar em conta toda a distribuição de filhos.

Definição 4.3

Função geradora de probabilidades A função geradora de \(Y\) é

\[ f(s)=E(s^Y)=\sum _{j=0}^{\infty }p_js^j,\qquad 0\leq s\leq 1, \]

com a convenção \(0^0=1\).

Da definição, vemos que \(f(0)=p_0\) e \(f(1)=1\). Cada coeficiente \(p_j\) registra a probabilidade de um indivíduo ter exatamente \(j\) filhos.

A principal vantagem da função geradora aparece quando somamos os números de filhos de indivíduos diferentes. Se \(Y_1\) e \(Y_2\) são independentes e têm a mesma distribuição de \(Y\), então

\[ \begin{aligned} E(s^{Y_1+Y_2}) & =E(s^{Y_1}s^{Y_2})\\ & =E(s^{Y_1})E(s^{Y_2})\\ & =f(s)^2. \end{aligned} \]

A segunda igualdade decorre da independência. Assim, a soma dos números de filhos corresponde ao produto das funções geradoras. Para \(i\) indivíduos que se reproduzem independentemente, o mesmo argumento mostra que a geradora do número total de filhos é \(f(s)^i\).

Para estudar a extinção, usaremos também a continuidade e a convexidade de \(f\), além de uma relação entre sua derivada e o número médio de filhos.

Proposição 4.9

Propriedades elementares da geradora A função \(f\) é contínua, não decrescente e convexa em \([0,1]\). Se \(\mathbb {P}(Y\geq 2)\gt 0\), a convexidade é estrita. Quando \(m=E(Y)\lt \infty \),

\[ \lim _{s\uparrow 1}\frac{1-f(s)}{1-s}=f'(1-)=m, \qquad f(s)\geq 1+m(s-1)\quad (0\leq s\leq 1). \]

Se \(\mathbb {P}(Y\geq 2)\gt 0\), a última desigualdade é estrita para \(s\lt 1\).

A notação \(f'(1-)\) indica a derivada em \(1\) tomada pela esquerda. A identidade \(f'(1-)=m\) mostra como a geradora recupera a média dos filhos; a última desigualdade compara seu gráfico com a reta tangente em \(1\).

Demonstração ▼

Continuidade. Separamos a série que define \(f\) em uma soma finita e uma cauda. Como \(|s^j-t^j|\leq 1\) para \(s,t\in [0,1]\), para qualquer inteiro \(J\geq 0\) temos

\[ |f(s)-f(t)| \leq \sum _{j=0}^{J}p_j|s^j-t^j|+\sum _{j\gt J}p_j. \]

Dado \(\varepsilon \gt 0\), escolha primeiro \(J\) para que a segunda soma seja menor que \(\varepsilon /2\). Isso é possível porque \(\sum _jp_j=1\). A primeira soma é finita e tende a zero quando \(s\) se aproxima de \(t\). Assim, com \(s\) suficientemente próximo de \(t\), ela também é menor que \(\varepsilon /2\). Esse argumento vale inclusive nos extremos \(0\) e \(1\).

Monotonicidade e convexidade. Cada função \(s^j\) é não decrescente e convexa em \([0,1]\). Para \(0\lt \theta \lt 1\),

\[ (\theta s+(1-\theta )t)^j \leq \theta s^j+(1-\theta )t^j. \]

Multiplicar por \(p_j\) e somar primeiro até \(J\) produz a mesma desigualdade para as somas parciais de \(f\). Fazer \(J\) crescer preserva a desigualdade e dá a convexidade de \(f\); a monotonicidade segue do mesmo argumento termo a termo. Se algum \(p_j\gt 0\) com \(j\geq 2\), esse termo satisfaz a desigualdade estrita sempre que \(s\ne t\), e os demais termos não a desfazem.

Derivada em \(1\) e reta tangente. Para encontrar a inclinação da geradora em \(1\), usaremos o quociente de diferenças, sem pressupor que podemos derivar a série termo a termo. Para \(0\leq s\lt 1\), a identidade da soma geométrica fornece

\[ \frac{1-f(s)}{1-s} =\sum _{j=1}^{\infty }p_j(1+s+\cdots +s^{j-1}). \]

A igualdade pode ser obtida somando \(p_j(1-s^j)\) até \(J\) e fazendo \(J\) crescer, com \(s\) fixo. Cada parêntese é no máximo \(j\), de modo que o quociente não excede \(m\). Para obter uma cota inferior, fixamos \(J\) e conservamos apenas os primeiros termos:

\[ \frac{1-f(s)}{1-s} \geq \sum _{j=1}^{J}p_j(1+s+\cdots +s^{j-1}). \]

Quando \(s\) se aproxima de \(1\), a soma à direita se aproxima de \(\sum _{j=1}^{J}jp_j\). Escolhendo primeiro \(J\) suficientemente grande e depois \(s\) suficientemente próximo de \(1\), tornamos essa cota tão próxima de \(m\) quanto desejarmos. Como o quociente nunca excede \(m\), seu limite é \(m\).

A cota superior também dá \(1-f(s)\leq m(1-s)\), que é a desigualdade da reta tangente. Se algum \(p_j\gt 0\) com \(j\geq 2\) e \(s\lt 1\), então \(1+s+\cdots +s^{j-1}\lt j\) nesse termo; a cota superior é estrita, como afirmado.

Para acompanhar várias gerações, escreva

\[ F_n(s)=E_1(s^{Z_n}) =\sum _{j=0}^{\infty }\mathbb {P}_1(Z_n=j)s^j, \qquad s\in [0,1], \]

com \(\mathbb P_k\) e \(E_k\) na convenção do Capítulo 2 para a cadeia iniciada em \(k\).

Enquanto o coeficiente \(p_j\) de \(f\) representa a probabilidade de um indivíduo ter exatamente \(j\) filhos, o coeficiente de \(s^j\) em \(F_n\) representa a probabilidade de a geração \(n\) conter exatamente \(j\) indivíduos, partindo de um único ancestral. Assim, \(f\) descreve a reprodução individual, enquanto \(F_n\) descreve a distribuição do tamanho da geração \(n\). O resultado a seguir relaciona essas geradoras por meio da composição de funções.

Proposição 4.10

Iteração da função geradora Para o processo de Galton–Watson iniciado com \(Z_0=1\), as funções geradoras das sucessivas gerações satisfazem, para \(s\in [0,1]\),

\[ F_0(s)=s,\qquad F_{n+1}(s)=F_n(f(s)),\quad n\geq 0. \]

Consequentemente,

\[ F_n=f^{\circ n},\qquad n\geq 0, \]

onde \(f^{\circ n}\) denota a composição de \(f\) consigo mesma \(n\) vezes, com \(f^{\circ 0}(s)=s\). Em particular, também vale

\[ F_{n+1}(s)=f(F_n(s)). \]

Demonstração ▼

Como \(Z_0=1\), temos \(F_0(s)=E_1(s^{Z_0})=s\).

Para relacionar duas gerações consecutivas, condicionamos ao tamanho da geração \(n\). Se \(Z_n=i\), os números de filhos dos \(i\) indivíduos são independentes e têm a mesma distribuição de \(Y\). Portanto,

\[ \begin{aligned} E_1(s^{Z_{n+1}}\mid Z_n=i) & =E\left(s^{Y_{n,1}+\cdots +Y_{n,i}}\right)\\ & =E\left(\prod _{r=1}^{i}s^{Y_{n,r}}\right)\\ & =\prod _{r=1}^{i}E(s^{Y_{n,r}})=f(s)^i. \end{aligned} \]

A igualdade vale também para \(i=0\): nesse caso, a geração seguinte é vazia, e o produto vazio vale um, inclusive quando \(s=0\), pela convenção \(0^0=1\).

Retirando o condicionamento pela esperança total, obtemos

\[ F_{n+1}(s)=E_1\bigl(f(s)^{Z_n}\bigr)=F_n(f(s)), \]

onde a última igualdade usa a definição de \(F_n\), pois \(f(s)\in [0,1]\).

Partindo de \(F_0(s)=s\), a recorrência fornece, por indução, \(F_n=f^{\circ n}\). Por fim, como \(f^{\circ (n+1)}=f\circ f^{\circ n}\), também obtemos \(F_{n+1}=f\circ F_n\).

Por exemplo, \(F_1(s)=f(s)\) e \(F_2(s)=f(f(s))\). A cada nova geração, aplicamos \(f\) mais uma vez: trata-se de composição, não da potência \(f(s)^n\).

Se a população começa com \(k\) indivíduos, a geradora inicial é \(s^k\). O mesmo condicionamento e uma indução em \(n\) fornecem

\[ E_k(s^{Z_n})=F_n(s)^k. \]

Essa potência expressa a propriedade de ramificação: o tamanho da geração \(n\), partindo de \(k\) indivíduos, tem a mesma distribuição que a soma dos tamanhos de \(k\) populações independentes, cada uma iniciada com um indivíduo.

Voltemos agora à probabilidade de extinção. Considere o tempo

\[ H_0=\inf \{ n\geq 0:Z_n=0\} \]

e escreva

\[ q_n=\mathbb {P}_1(H_0\leq n) \]

para a probabilidade de a população se extinguir até a geração \(n\).

Como zero é absorvente, a extinção até a geração \(n\) equivale a termos \(Z_n=0\). Portanto,

\[ q_n=\mathbb {P}_1(Z_n=0)=F_n(0). \]

Como \(Z_0=1\), temos \(q_0=0\). Além disso, pela Proposição 4.10,

\[ q_{n+1}=F_{n+1}(0)=f(F_n(0))=f(q_n). \]

A recorrência tem uma leitura genealógica. Para a população se extinguir até a geração \(n+1\), cada família fundada por um filho da primeira geração precisa desaparecer em no máximo \(n\) gerações adicionais. Se há \(i\) filhos, a probabilidade é \(q_n^i\). Retirando o condicionamento sobre o número de filhos, obtemos \(\sum _i p_iq_n^i=f(q_n)\). Além disso, \(q_n\) não diminui quando damos à população mais uma geração para se extinguir.

Teorema 4.11

Extinção como menor ponto fixo A probabilidade \(q=\mathbb {P}_1(H_0\lt \infty )\) é a menor solução da equação \(f(s)=s\) em \([0,1]\). Partindo de \(k\geq 1\) indivíduos, \(\mathbb {P}_k(H_0\lt \infty )=q^k\).

Como \(f(1)=1\), a equação de ponto fixo sempre admite a solução \(1\). Isso não significa que a extinção seja certa: quando há outras soluções, precisamos identificar qual delas representa essa probabilidade. A sequência que começa em \(q_0=0\) faz exatamente essa seleção, pois considera horizontes finitos cada vez maiores. A fórmula \(q^k\), por sua vez, decorre da independência entre as \(k\) famílias iniciais.

Demonstração ▼

Os eventos \(\{ H_0\leq n\} \) aumentam para \(\{ H_0\lt \infty \} \). Pela continuidade das probabilidades de eventos crescentes, recordada na Proposição 2.9, temos \(q_n\uparrow q\). A continuidade de \(f\), provada na Proposição 4.9, permite passar ao limite em \(q_{n+1}=f(q_n)\) e concluir que \(q=f(q)\).

Se \(r\in [0,1]\) satisfaz \(f(r)=r\), então \(q_0=0\leq r\). Suponha \(q_n\leq r\). Como \(f\) é não decrescente,

\[ q_{n+1}=f(q_n)\leq f(r)=r. \]

A indução mostra que \(q_n\leq r\) para todo \(n\); tomando o limite, obtemos \(q\leq r\). Assim, nenhum outro ponto fixo em \([0,1]\) pode ser menor que a probabilidade de extinção.

Por fim, para uma população iniciada com \(k\) indivíduos, a fórmula da geradora e o fato de zero ser absorvente dão

\[ \mathbb P_k(H_0\leq n)=\mathbb P_k(Z_n=0)=F_n(0)^k=q_n^k. \]

Fazendo \(n\to \infty \), a mesma continuidade das probabilidades e a continuidade da potência \(s\mapsto s^k\) fornecem \(\mathbb P_k(H_0\lt \infty )=q^k\). Equivalentemente, cada uma das \(k\) famílias iniciais precisa se extinguir; a independência dessas famílias produz o mesmo fator \(q^k\).

Teorema 4.12

Regimes subcrítico, crítico e supercrítico Suponha \(m\lt \infty \) e \(Z_0=1\). Se \(m\lt 1\), então \(q=1\). Se \(m=1\) e \(\mathbb {P}(Y=1)\lt 1\), também \(q=1\). Se \(m\gt 1\), então \(q\lt 1\). No caso degenerado \(Y=1\) quase certamente, \(Z_n=1\) para todo \(n\) e \(q=0\).

A média de um filho por indivíduo separa os regimes. No caso crítico não degenerado, a esperança do tamanho da população permanece constante e, ainda assim, a extinção é certa. Quando \(m\gt 1\), há uma probabilidade positiva de sobrevivência; essa probabilidade só é igual a um se nenhum indivíduo puder ter zero filhos.

Ideia (Leitura geométrica dos três regimes)

A equação \(f(s)=s\) pede os pontos em que o gráfico de \(y=f(s)\) encontra a diagonal \(y=s\). Um encontro sempre ocorre em \(s=1\). Nesse ponto, a inclinação da geradora é \(f'(1-)=m\); junto com a convexidade, ela determina o que pode acontecer à esquerda.

Se \(m\lt 1\), a tangente em \(1\) tem inclinação menor que a diagonal e fica acima dela à esquerda de \(1\). Pela convexidade, o gráfico de \(f\) fica sobre a tangente ou acima dela e, portanto, estritamente acima da diagonal para \(s\lt 1\). Não há outro ponto fixo.

Se \(m=1\) e a reprodução não é degenerada, a curva tem a mesma inclinação que a diagonal em \(1\), mas é estritamente convexa. Ela continua acima da diagonal para \(s\lt 1\), e a extinção também é certa.

Se \(m\gt 1\), a inclinação em \(1\) supera a da diagonal. Imediatamente à esquerda, temos \(f(s)\lt s\). Já em \(s=0\) vale \(f(0)=p_0\geq 0\); pela continuidade, há um ponto fixo abaixo de \(1\): ele é \(0\) quando \(p_0=0\) e pertence a \((0,1)\) quando \(p_0\gt 0\). Esse menor ponto fixo é a probabilidade de extinção.

Demonstração ▼

Para \(m\lt 1\) e \(s\lt 1\), a desigualdade da reta tangente, justificada na Proposição 4.9, fornece

\[ f(s)\geq 1+m(s-1)\gt s. \]

A desigualdade estrita vale porque \(1+m(s-1)-s=(1-m)(1-s)\gt 0\). Logo o único ponto fixo é \(1\), e o Teorema 4.11 dá \(q=1\). Se \(m=1\) e \(Y\) não é identicamente um, necessariamente \(\mathbb {P}(Y\geq 2)\gt 0\): caso contrário, \(Y\) só assumiria os valores \(0\) e \(1\), e a média um forçaria \(\mathbb {P}(Y=1)=1\). A desigualdade da reta tangente é então estrita para \(s\lt 1\): \(f(s)\gt 1+(s-1)=s\). Novamente, o único ponto fixo é \(1\), e \(q=1\).

Se \(m\gt 1\), o quociente \((1-f(s))/(1-s)\) é maior que um para \(s\lt 1\) suficientemente próximo de \(1\), pois seu limite é \(m\). Isso equivale a \(f(s)\lt s\) nessa região. Por outro lado, \(f(0)-0=p_0\geq 0\). Se \(p_0\gt 0\), a função contínua \(f(s)-s\) muda de sinal entre \(0\) e um ponto próximo de \(1\), logo se anula em \((0,1)\). Se \(p_0=0\), o próprio zero é ponto fixo. Em ambos os casos, o menor ponto fixo é menor que um. Quando \(Y=1\) quase certamente, cada indivíduo é substituído por exatamente um filho. A recursão dá \(Z_{n+1}=Z_n\) em todas as gerações; como \(Z_0=1\), nunca se atinge zero e \(q=0\).

A mesma distinção pode ser vista tomando a probabilidade de sobrevivência, em vez da de extinção, como incógnita. Para isso, definimos

\[ \lambda (s)=1-f(1-s),\qquad 0\leq s\leq 1. \]

Se \(q\) é a probabilidade de extinção, então \(\rho =1-q\) é a probabilidade de sobrevivência. Como \(f(q)=q\), temos \(\lambda (\rho )=\rho \). Como \(q\) é o menor ponto fixo de \(f\), \(\rho \) é o maior ponto fixo de \(\lambda \) em \([0,1]\).

Além disso, \(\lambda (0)=0\) e \(\lambda '(0+)=f'(1-)=m\): a inclinação que antes observávamos em \(1\) passa a ser vista na origem.

A Figura 4.5 compara os três regimes para uma distribuição que atribui probabilidade \(1-p\) a nenhum filho e probabilidade \(p\) a três filhos.

Ilustração: Geradoras e extinção

Figura 4.5 Os três regimes para \(\lambda (s)=p[1-(1-s)^3]\). O zero é sempre um ponto fixo. Nos casos subcrítico e crítico, é o único; no supercrítico, aparece também o ponto fixo positivo \(\rho \), que representa a probabilidade de sobrevivência.

No último painel, com \(p=3/5\), obtemos \(\rho =(9-\sqrt{33})/6\approx 0{,}543\). A possibilidade de sobrevivência aparece, portanto, como um novo ponto de encontro entre a curva e a diagonal.

Podemos agora retomar as aplicações da abertura. Nas linhagens, a extinção significa não haver mais descendentes; nas reações em cadeia, significa que a sequência de fissões se encerrou. O critério se refere ao número médio de descendentes por indivíduo, contando também os que não deixam nenhum, e depende das hipóteses de reprodução independente e de uma mesma lei ao longo das gerações.

Nem toda aplicação, porém, acompanha um número ilimitado de gerações. Em um multiplicador com \(n\) etapas, iniciado por um elétron, a probabilidade de não haver elétrons na saída é \(q_n\), não \(q\). A quantidade \(q\) descreve a extinção eventual na idealização em que o mecanismo pode se repetir indefinidamente.

Exemplo 4.5 (Zero ou dois filhos)

Suponha \(p_0=1/4\) e \(p_2=3/4\). Então \(m=3/2\) e \(f(s)=1/4+3s^2/4\). A equação de ponto fixo equivale a

\[ 3s^2-4s+1=(3s-1)(s-1)=0. \]

Portanto, pelo Teorema 4.11, \(q=1/3\), apesar de \(E_1(Z_n)=(3/2)^n\). Com três indivíduos iniciais, a extinção tem probabilidade \(1/27\), e a sobrevivência, \(26/27\).

Figura 4.6 A geradora \(f(s)=1/4+3s^2/4\) e a diagonal no recorte \(0\leq s\leq 1/2\). As setas mostram a iteração \(q_{n+1}=f(q_n)\), iniciada em \(q_0=0\), aproximando-se do menor ponto fixo, \(q=1/3\). A outra solução, \(s=1\), está fora do recorte.

Na Figura 4.6, cada degrau parte de \((q_n,q_n)\), na diagonal, e sobe até \((q_n,q_{n+1})\), no gráfico de \(f\). O trecho horizontal leva então a \((q_{n+1},q_{n+1})\), de volta à diagonal. A iteração iniciada em zero se aproxima do menor ponto fixo sem ultrapassá-lo. Essa construção também permite visualizar o procedimento numérico usado no próximo exemplo.

Exemplo 4.6 (Descendência Poisson)

Para \(Y\) com lei de Poisson de média \(2\), isto é, \(\mathbb {P}(Y=j)=e^{-2}2^j/j!\), temos

\[ f(s)=e^{-2}\sum _{j=0}^{\infty }\frac{(2s)^j}{j!} =e^{-2}e^{2s}=e^{2(s-1)}. \]

Usamos, na segunda igualdade, a série da função exponencial. Aqui a equação de ponto fixo não é polinomial, mas podemos aproximar sua menor solução pela mesma iteração usada no Teorema 4.11. Começando em \(q_0=0\) e calculando \(q_{n+1}=e^{2(q_n-1)}\), obtemos \(q\approx 0{,}203188\). Assim, a extinção tem probabilidade de cerca de \(20{,}3\% \) a partir de um indivíduo. Com dois indivíduos iniciais, essa probabilidade cai para \(q^2\approx 0{,}041285\).

Os exemplos anteriores mostram como calcular a probabilidade de extinção a partir de uma lei de descendentes. A próxima comparação mostra por que duas leis com a mesma média podem levar a respostas diferentes mesmo quando ambas são supercríticas.

Exemplo 4.7 (Mesma média, diferentes probabilidades de extinção)

Cada indivíduo produz dois descendentes, mas apenas os que sobrevivem até a idade de reprodução são contados na geração seguinte. Cada descendente tem probabilidade \(3/5\) de sobreviver. Compare duas regras para essa sobrevivência. Em ambas, famílias diferentes e gerações diferentes usam sorteios independentes.

Mortalidade independente. Os dois descendentes sobrevivem independentemente. O número \(Y_A\) dos que chegam à geração seguinte tem distribuição binomial com parâmetros \(2\) e \(3/5\), de modo que

\[ f_A(s)=\left(\frac25+\frac35s\right)^2 =\frac4{25}+\frac{12}{25}s+\frac9{25}s^2. \]

Pode não sobreviver nenhum, apenas um ou ambos.

Mortalidade conjunta. Os dois descendentes sobrevivem juntos, com probabilidade \(3/5\), ou ambos morrem, com probabilidade \(2/5\). O número \(Y_B\) dos sobreviventes é, portanto, zero ou dois, e

\[ f_B(s)=\frac25+\frac35s^2. \]

Aqui a dependência está dentro de cada família: o resultado de uma família não determina o de outra.

As duas regras têm a mesma média,

\[ E(Y_A)=E(Y_B)=2\cdot \frac35=\frac65. \]

Assim, começando com um indivíduo, ambas produzem o mesmo tamanho esperado \((6/5)^n\) na geração \(n\). Para comparar as probabilidades de extinção, procuramos os menores pontos fixos das geradoras. No primeiro caso,

\[ f_A(s)=s \quad \Longleftrightarrow \quad 9s^2-13s+4=(9s-4)(s-1)=0, \]

logo \(q_A=4/9\). No segundo,

\[ f_B(s)=s \quad \Longleftrightarrow \quad 3s^2-5s+2=(3s-2)(s-1)=0, \]

logo \(q_B=2/3\). A extinção é, portanto, mais provável sob a mortalidade conjunta, embora cada descendente tenha a mesma probabilidade individual de sobrevivência nos dois modelos.

As variâncias também diferem:

\[ \operatorname {Var}(Y_A)=2\cdot \frac35\cdot \frac25=\frac{12}{25}, \qquad \operatorname {Var}(Y_B)=4\cdot \frac35\cdot \frac25=\frac{24}{25}. \]

Na segunda regra, uma família inteira pode ser perdida de uma só vez; na primeira, um dos descendentes pode sobreviver mesmo quando o outro morre. A média de reprodução não distingue essas situações, mas a lei de descendentes e sua função geradora distinguem.

Até aqui, supusemos conhecida a distribuição de descendentes. Em uma aplicação, ela precisa ser estimada a partir das observações.

4.3.3 Cascatas: o que os dados permitem estimar

Em uma cascata de compartilhamentos, chamamos de filho uma transmissão direta. Se uma pessoa alcança outra e esta, por sua vez, alcança dez novas pessoas, a primeira teve um filho, não onze. Contar filhos não é o mesmo que contar todos os indivíduos atingidos: a primeira quantidade descreve a reprodução de cada participante; a segunda, o alcance acumulado da cascata.

Suponha que \(Y_1,\ldots ,Y_N\) sejam observações independentes, completamente acompanhadas, da mesma distribuição de filhos. Escreva \(N_j=\# \{ r:Y_r=j\} \), com \(N\gt 0\). A distribuição empírica e sua geradora são

\[ \widehat p_j=\frac{N_j}{N},\qquad \widehat m=\frac1N\sum _{r=1}^NY_r,\qquad \widehat f(s)=\sum _j\widehat p_js^j. \]

Definimos \(\widehat q\) como a probabilidade de extinção do processo cuja distribuição de descendentes é \(\widehat p\). Pelo Teorema 4.11, ela é o menor ponto fixo de \(\widehat f\). Esses números descrevem o modelo ajustado; não quantificam a incerteza amostral, que não trataremos aqui.

A distribuição empírica também pode ser obtida procurando a lei que torna os resultados observados mais prováveis. Pela independência, a probabilidade desses resultados, sob uma lei \(p=(p_j)\), é

\[ L(p)=\prod _{r=1}^{N}p_{Y_r} =\prod _{j:N_j\gt 0}p_j^{N_j}. \]

Vista como função da lei desconhecida \(p\), essa expressão é chamada de verossimilhança.

Proposição 4.13

Estimador de máxima verossimilhança Entre todas as distribuições de probabilidade em \(\mathbb N_0\), a verossimilhança \(L(p)\) é maximizada por \(\widehat p_j=N_j/N\), inclusive quando algumas contagens são zero.

Uma categoria não observada recebe probabilidade zero no estimador, mas isso não prova que seja impossível na população. Se todas as categorias observadas têm probabilidade positiva, redistribuir entre elas, proporcionalmente, qualquer massa atribuída às demais aumenta a verossimilhança.

Demonstração ▼

Seja \(J=\{ j:N_j\gt 0\} \) o conjunto das categorias observadas. Esse conjunto é finito, pois foram acompanhados apenas \(N\) indivíduos; assim, todas as somas de logaritmos a seguir são finitas. Se \(p_j=0\) para algum \(j\in J\), a verossimilhança se anula, enquanto \(\widehat p\) fornece um valor positivo. Basta, portanto, considerar distribuições com \(p_j\gt 0\) para todo \(j\in J\).

Escreva

\[ \ell (p)=\sum _{j\in J}N_j\log p_j \]

para o logaritmo da verossimilhança. Como o logaritmo é crescente, maximizar \(\ell \) equivale a maximizar a verossimilhança. A desigualdade \(\log u\leq u-1\), para \(u\gt 0\), segue de que \(u-1-\log u\) decresce até \(u=1\) e cresce depois, atingindo ali o mínimo zero. Aplicando-a a cada razão positiva \(p_j/\widehat p_j\), obtemos

\[ \begin{aligned} \ell (p)-\ell (\widehat p) & =N\sum _{j\in J}\widehat p_j\log \frac{p_j}{\widehat p_j}\\ & \leq N\sum _{j\in J}(p_j-\widehat p_j)\\ & =N\left(\sum _{j\in J}p_j-1\right)\leq 0. \end{aligned} \]

A última desigualdade usa apenas que a massa total de uma distribuição é um. A igualdade exige \(p_j=\widehat p_j\) para todo \(j\in J\), pois \(\log u=u-1\) apenas quando \(u=1\). Nesse caso, a massa em \(J\) já soma um, de modo que \(p_j=0\) fora de \(J\). Logo, \(p=\widehat p\), o que prova também a unicidade do maximizador.

Exemplo 4.8 (Uma amostra de transmissores)

Uma amostra didática de \(80\) pessoas, selecionadas antes de conhecer seus resultados e acompanhadas durante toda a janela de reprodução, fornece as seguintes contagens:

\[ \begin{array}{c|ccc} j& 0& 1& 2\\ \hline N_j& 24& 12& 44 \end{array} \]

A média estimada é \(\widehat m=(12+2\cdot 44)/80=1{,}25\), e a função geradora empírica é

\[ \widehat f(s)=0{,}30+0{,}15s+0{,}55s^2. \]

Pelo Teorema 4.11, a equação \(11s^2-17s+6=(11s-6)(s-1)=0\) dá \(\widehat q=6/11\). Com quatro sementes independentes, a probabilidade ajustada de extinção é \((6/11)^4\approx 0{,}08852\).

Essa amostra não seria equivalente a reunir todos os indivíduos de uma única árvore que já terminou. Em uma árvore finita com \(N\) vértices, cada indivíduo, exceto a raiz, está ligado a seu pai por uma aresta. Há, portanto, \(N-1\) arestas, que correspondem aos \(N-1\) filhos contados na árvore inteira. A média observada seria forçosamente \((N-1)/N\lt 1\), independentemente da lei de reprodução subjacente. Selecionar apenas cascatas que terminaram pode, assim, esconder um mecanismo supercrítico; selecionar apenas cascatas grandes introduz outro viés.

Mesmo com uma amostra bem escolhida, precisamos examinar como os indivíduos foram acompanhados. Se a coleta termina antes de alguém ter oportunidade de produzir todos os seus filhos, há censura: um zero registrado pode ser apenas temporário. Em uma rede de contatos, duas linhagens também podem alcançar a mesma pessoa. Essas colisões rompem a estrutura de árvore do modelo.

Outras dificuldades dizem respeito à reprodução. Pessoas expostas ao mesmo contexto podem não se comportar de forma independente, e grupos ou gerações diferentes podem seguir leis distintas. Nesses casos, a dependência e a heterogeneidade limitam a descrição por uma única função geradora.

A interpretação de \(\widehat m\) e \(\widehat q\) depende, portanto, de como a amostra foi obtida. É preciso distinguir uma característica da reprodução de um efeito da seleção dos indivíduos ou da interrupção do acompanhamento.

Em uma rede finita, a sobrevivência eterna é uma idealização: o processo de Galton–Watson funciona sobretudo como uma aproximação inicial, antes que a saturação e as colisões passem a dominar a dinâmica. Depois dos problemas de síntese, a Seção 4.5 retoma essa limitação ao explorar grafos aleatórios. Para aprofundar a teoria clássica de ramificação e seus exercícios, veja Schinazi (1999, seção I.9).

4.4 Problemas de síntese

Os modelos deste capítulo levantam perguntas que não se resolvem olhando apenas uma transição. Na ruína sem barreira superior, precisamos escolher a solução correta de uma equação harmônica; no protocolo Aloha, determinar o crescimento de uma fila; na ramificação, distinguir tamanho esperado e probabilidade de extinção. Os três problemas a seguir retomam essas perguntas com as ferramentas já desenvolvidas.

Exemplo 4.9 (Ruína sem uma barreira superior: qual solução escolher?)

Um jogador começa com \(i\geq 1\) unidades e, a cada rodada, ganha uma unidade com probabilidade \(p\in (0,1)\) ou perde uma unidade com probabilidade \(q=1-p\). O jogo termina ao atingir zero, mas não há limite superior para a fortuna.

Figura não resolvida: figuras/ruina-infinita.tikz

Figura 4.7 Passeio nos inteiros não negativos: zero é absorvente, mas não existe barreira à direita.

Queremos \(h(i)=\mathbb P_i(H_0\lt \infty )\). Aqui \(h(i)\) representa a probabilidade de ruína sem uma barreira superior. Em contraste, \(u_i\) no Exemplo 2.33 representa a probabilidade de atingir a meta antes de zero no jogo com duas barreiras. Condicionando pelo primeiro passo,

\[ h(0)=1,\qquad h(i)=ph(i+1)+qh(i-1),\quad i\geq 1. \]

No espaço infinito, essas equações não identificam sozinhas a probabilidade procurada: a função constante \(h(i)=1\) sempre as satisfaz. Precisamos de uma condição que selecione a solução correta.

Para isso, introduzimos provisoriamente uma barreira \(N\gt i\). A probabilidade \(h_N(i)=\mathbb P_i(H_0\lt H_N)\) já foi obtida na ruína finita:

\[ h_N(i)= \begin{cases} \dfrac {(q/p)^i-(q/p)^N}{1-(q/p)^N},& p\ne q,\\[2mm] 1-\dfrac iN,& p=q. \end{cases} \]

Os eventos \(\{ H_0\lt H_N\} \) crescem com \(N\) e sua união é \(\{ H_0\lt \infty \} \): toda trajetória que chega a zero percorreu apenas um número finito de estados antes dessa chegada. A monotonicidade também pode ser vista diretamente: para atingir uma barreira mais distante antes de zero, o passeio precisa atravessar cada barreira mais próxima. Por outro lado, se \(H_0\lt \infty \), o máximo das posições até \(H_0\) é finito; qualquer \(N\) acima desse máximo satisfaz \(H_0\lt H_N\). Pela continuidade das probabilidades de eventos crescentes, basta, portanto, tomar \(N\to \infty \). Se \(p\lt q\), dividimos numerador e denominador de \(h_N(i)\) por \((q/p)^N\) e obtemos o limite um; se \(p\gt q\), usamos \((q/p)^N\to 0\). No caso \(p=q\), temos \(i/N\to 0\). Assim,

\[ \boxed { h(i)= \begin{cases} 1,& p\leq q,\\[1mm] (q/p)^i,& p\gt q. \end{cases}} \]

Por exemplo, se \(p=3/5\) e o jogador começa com duas unidades, a probabilidade de ruína é \((2/3)^2=4/9\). Logo, ele tem probabilidade \(5/9\) de nunca ficar sem dinheiro.

A resposta também é a menor solução não negativa das equações de primeiro passo com \(h(0)=1\). De fato, se \(u\geq 0\) é outra solução, seu valor no estado \(N\) é não negativo. Em \(\{ 0,\ldots ,N\} \), a função \(u\) é harmônica no interior. A chegada a uma das barreiras ocorre quase certamente: em qualquer bloco de \(N\) rodadas, uma sequência de \(N\) perdas, de probabilidade \(q^N\gt 0\), garante a chegada a zero se a chegada ainda não ocorreu. A probabilidade de permanecer no interior durante \(r\) blocos é, portanto, no máximo \((1-q^N)^r\), que tende a zero.

As probabilidades de atingir cada barreira são harmônicas no interior, por condicionamento no primeiro passo. A combinação dessas probabilidades com os valores de fronteira \(u(0)=1\) e \(u(N)\) tem os mesmos valores de \(u\) nas duas barreiras. Ela é a única função harmônica com esses dados: se a diferença entre duas soluções tivesse máximo positivo no interior, a equação de média ponderada, com \(p,q\gt 0\), obrigaria os dois vizinhos a terem o mesmo máximo. Repetindo o argumento, chegaríamos a uma barreira, onde a diferença é zero, uma contradição. Aplicar o mesmo raciocínio ao mínimo exclui uma diferença negativa. Logo, decompor segundo a primeira barreira atingida dá

\[ u(i)=\mathbb P_i(H_0\lt H_N) +u(N)\mathbb P_i(H_N\lt H_0)\geq h_N(i). \]

Deixando \(N\to \infty \), obtemos \(u(i)\geq h(i)\). A condição de minimalidade seleciona, entre as soluções não negativas da equação harmônica, aquela que representa a probabilidade procurada.

Exemplo 4.10 (Aloha revisitado: como cresce a fila quando os sucessos cessam?)

O protocolo Aloha do Exemplo 4.2 tem chegadas independentes de uma mensagem com probabilidade \(3/4\) e de duas mensagens com probabilidade \(1/4\). Como vimos, o número total de transmissões bem-sucedidas é finito quase certamente, e a demonstração fornece

\[ \mathbb P(I_n=1)\leq \frac34\left(\frac{13}{16}\right)^n. \]

O diagrama da Figura 4.3 explica o mecanismo: quanto maior a fila de mensagens pendentes, mais provável é uma colisão.

A desigualdade da união e a série geométrica dão uma cota para os sucessos futuros:

\[ \begin{aligned} \mathbb P(\text{algum sucesso a partir do instante }n) & \leq \sum _{k=n}^{\infty }\mathbb P(I_k=1)\\ & \leq 4\left(\frac{13}{16}\right)^n. \end{aligned} \]

Por exemplo, para \(n=22\) a cota é menor que \(0{,}05\). Portanto, com probabilidade superior a \(95\% \), não ocorre mais nenhuma transmissão bem-sucedida a partir desse instante, embora continuem chegando mensagens.

Para calcular o crescimento da fila, retomemos sua identidade:

\[ X_n=X_0+\sum _{k=0}^{n-1}A_k -\sum _{k=0}^{n-1}I_k. \]

A lei forte dos grandes números, aplicada às chegadas, dá

\[ \frac1n\sum _{k=0}^{n-1}A_k \longrightarrow E(A_0)= \frac34\cdot 1+\frac14\cdot 2=\frac54 \quad \text{quase certamente}. \]

A soma de todos os \(I_k\) é finita quase certamente, logo sua contribuição dividida por \(n\) tende a zero. Concluímos que

\[ \boxed {\frac{X_n}{n}\longrightarrow \frac54 \quad \text{quase certamente}.} \]

Como o sistema realiza somente um número finito de transmissões bem-sucedidas, a fila cresce à taxa assintótica das próprias chegadas.

Exemplo 4.11 (Duas populações com o mesmo crescimento médio)

Duas populações começam com um único indivíduo. Em cada geração, seus descendentes reproduzem-se independentemente, segundo o modelo de Galton–Watson. Compare as seguintes leis para o número \(Y\) de filhos:

\[ \begin{array}{ll} \text{População A:}& \mathbb P(Y=2)=1,\\[2pt] \text{População B:}& \mathbb P(Y=0)=\dfrac 13,\quad \mathbb P(Y=3)=\dfrac 23. \end{array} \]

Nas duas populações a média de filhos é exatamente \(m=E(Y)=2\); portanto, o teorema do tamanho esperado da geração fornece

\[ \boxed {E_1(Z_n)=2^n\quad \text{nos dois modelos}.} \]

Figura não resolvida: figuras/sintese-ramificacao-media.tikz

Figura 4.8 À esquerda, toda geração duplica; à direita, uma trajetória possível se extingue após uma geração com três indivíduos. A média de filhos nos dois modelos é a mesma.

A igualdade das médias não implica igualdade das chances de sobrevivência. Na população A, todo indivíduo tem dois filhos. Começando com um indivíduo, \(Z_n=2^n\) em todas as trajetórias e a extinção é impossível.

Na população B, a função geradora é

\[ f(s)=\frac13+\frac23s^3. \]

Pelo teorema da extinção, a probabilidade \(q\) de desaparecimento é o menor ponto fixo de \(f\). A equação \(f(q)=q\) equivale a

\[ 2q^3-3q+1 =(q-1)(2q^2+2q-1)=0. \]

As raízes são \(1\), \((-1+\sqrt3)/2\) e \((-1-\sqrt3)/2\). A última é negativa e, entre os dois pontos fixos de \([0,1]\), devemos escolher o menor:

\[ \boxed {q=\frac{\sqrt3-1}{2}\approx 0{,}366.} \]

Embora seu tamanho esperado cresça como \(2^n\), essa população desaparece com probabilidade superior a \(36\% \).

As probabilidades de extinção em horizontes finitos permitem acompanhar essa aproximação. Na primeira geração, a extinção tem probabilidade \(q_1=1/3\). Até a segunda geração,

\[ q_2=f(q_1) =\frac13+\frac23\left(\frac13\right)^3 =\frac{29}{81}, \]

e as iterações seguintes aumentam até \(q\). Com três indivíduos iniciais, cujas famílias são independentes, a extinção eventual tem probabilidade \(q^3\approx 0{,}049\).

A média \(m\) determina o crescimento esperado de cada geração e separa regimes de reprodução. Ela não determina, sozinha, a chance de extinção: essa probabilidade depende da distribuição completa de descendentes, resumida pela função geradora.

Nos três problemas, uma conta local só ganha sentido quando a relacionamos ao comportamento de longo prazo. Na ruína, a minimalidade seleciona a probabilidade correta; no Aloha, a soma dos sucessos determina a taxa de crescimento da fila; na ramificação, a distribuição dos filhos distingue crescimento esperado e chance de sobrevivência.

4.5 Percolação em árvores e grafos aleatórios^*

Até aqui, usamos processos de ramificação para acompanhar o número de indivíduos de cada geração. Podemos fazer uma pergunta semelhante em uma rede: se cada ligação estiver disponível apenas com certa probabilidade, quantos vértices poderão ser alcançados a partir de um vértice inicial?

A resposta é particularmente simples quando a rede tem a forma de uma árvore. Nesse caso, os vértices alcançados se organizam em gerações, como em uma árvore genealógica, e a relação com Galton–Watson é exata. Em um grafo aleatório com ciclos, essa relação deixa de ser exata, mas ainda ajuda a explicar quando surge uma componente que reúne uma fração considerável dos vértices.

Definição 4.4

Percolação por arestas Considere um grafo não orientado \(G=(V,E)\), finito ou enumerável, e um número \(p\in [0,1]\). Cada aresta é declarada aberta com probabilidade \(p\) e fechada com probabilidade \(1-p\), independentemente das demais. O grafo formado pelos mesmos vértices e apenas pelas arestas abertas é chamado de percolação por arestas em \(G\).

Denotaremos por \(C(v)\) a componente aberta de \(v\): o conjunto de vértices que podem ser alcançados a partir de \(v\) por caminhos de arestas abertas, incluindo o próprio \(v\). Se o grafo for infinito, uma questão natural será saber quando \(C(v)\) também pode ser infinita.

4.5.1 Percolação em uma árvore infinita

Considere uma árvore infinita enraizada em \(o\), na qual cada vértice tem exatamente \(b\geq 2\) filhos. Como se trata de uma árvore, cada vértice diferente da raiz tem um único pai. A raiz forma a geração zero, seus filhos formam a geração um, e assim por diante. Suponha que cada aresta seja aberta, independentemente das demais, com probabilidade \(p\).

Seja \(Z_n\) o número de vértices da geração \(n\) que podem ser alcançados a partir da raiz usando somente arestas abertas. Em particular, \(Z_0=1\). Um vértice alcançado pode dar acesso a alguns de seus \(b\) filhos: somente aqueles ligados a ele por uma aresta aberta.

Proposição 4.14

Percolação e ramificação em árvores O processo \((Z_n)\) é um processo de Galton–Watson com distribuição de descendentes

\[ Y\sim \operatorname {Binomial}(b,p). \]

Sua função geradora e seu número médio de descendentes são

\[ f(s)=(1-p+ps)^b,\qquad m=bp. \]

A distribuição binomial aparece porque cada vértice possui \(b\) possibilidades de alcançar um filho, e cada uma delas ocorre com probabilidade \(p\). A independência das arestas garante a independência das reproduções.

Demonstração ▼

Suponha conhecidos os vértices alcançados até a geração \(n\). Para cada um dos \(Z_n\) vértices alcançados nessa geração, examinamos as \(b\) arestas que o ligam aos filhos. Essas arestas ainda não foram examinadas e são independentes das utilizadas nas gerações anteriores.

Assim, o número \(Y_{n,r}\) de filhos alcançados a partir do \(r\)-ésimo vértice tem distribuição binomial de parâmetros \(b\) e \(p\). Dois vértices distintos têm conjuntos disjuntos de arestas para seus filhos. Além disso, em uma árvore, um filho só pode ser alcançado por meio de seu próprio pai: não há caminhos alternativos que levem a contá-lo duas vezes. A independência das arestas permite, portanto, associar a cada vértice uma reprodução independente, sempre com a mesma lei binomial. Assim, essas variáveis são independentes entre si e entre gerações, e

\[ Z_{n+1}=\sum _{r=1}^{Z_n}Y_{n,r}. \]

Esta é exatamente a construção da Definição 4.2. Por fim, a fórmula binomial fornece

\[ \begin{aligned} f(s) & =\sum _{j=0}^{b}\binom {b}{j}p^j(1-p)^{b-j}s^j\\ & =(1-p+ps)^b. \end{aligned} \]

Para calcular a média, escreva \(Y\) como a soma dos \(b\) indicadores de abertura das arestas que ligam um vértice a seus filhos. Cada indicador tem esperança \(p\); pela linearidade da esperança, \(m=E(Y)=bp\).

Como as gerações são disjuntas e cada uma contém no máximo \(b^n\) vértices, o tamanho da componente da raiz é

\[ |C(o)|=\sum _{n=0}^{\infty }Z_n. \]

Essa componente é infinita precisamente quando \((Z_n)\) nunca se extingue. Se alguma geração está vazia, todas as seguintes também estarão, e a soma terá apenas um número finito de termos não nulos. Por outro lado, se \(Z_n\geq 1\) para todo \(n\), a soma é infinita.

Teorema 4.15

Limiar de percolação na árvore Seja

\[ \theta (p)=\mathbb {P}(|C(o)|=\infty ). \]

Para a árvore com \(b\geq 2\) filhos por vértice,

\[ \theta (p)=0\quad \text{se }p\leq \frac1b, \qquad \theta (p)\gt 0\quad \text{se }p\gt \frac1b. \]

Além disso, \(q=1-\theta (p)\) é a menor solução em \([0,1]\) de

\[ q=(1-p+pq)^b. \]

A probabilidade crítica é o limiar

\[ p_c=\inf \{ p\in [0,1]:\theta (p)\gt 0\} . \]

O teorema mostra que \(p_c=1/b\). Até esse valor, inclusive no ponto crítico, a componente da raiz é finita quase certamente. Acima dele, surge uma probabilidade positiva de ela ser infinita, embora a extinção continue possível enquanto \(p\lt 1\).

Demonstração ▼

Pela Proposição 4.14, a média de descendentes é \(m=bp\). Se \(p\lt 1/b\), então \(m\lt 1\) e o processo se extingue quase certamente. No ponto \(p=1/b\), temos \(m=1\). Como \(b\geq 2\), a binomial correspondente não é a distribuição degenerada \(Y=1\): em particular, \(\mathbb P(Y=0)=(1-1/b)^b\gt 0\). Também nesse caso a extinção é certa.

Se \(p\gt 1/b\), então \(m\gt 1\) e a sobrevivência tem probabilidade positiva. Essas são exatamente as conclusões do Teorema 4.12. A equivalência entre sobrevivência e componente infinita dá as afirmações sobre \(\theta (p)\).

Pelo Teorema 4.11, a probabilidade de extinção é a menor solução de \(f(q)=q\). Como \(\theta (p)\) é a probabilidade do evento complementar à extinção, temos \(q=1-\theta (p)\). Substituir \(f(s)=(1-p+ps)^b\) fornece a equação indicada.

Também podemos escrever a equação em termos da probabilidade de percolação. Substituindo \(q=1-\theta (p)\), obtemos

\[ \theta (p)=1-(1-p\theta (p))^b. \]

Quando \(p\leq p_c\), a única solução em \([0,1]\) é zero. Quando \(p\gt p_c\), existe também uma solução positiva, e é ela que corresponde à probabilidade de percolação: trata-se da maior solução em \([0,1]\). Isso decorre da mudança de variável \(\theta =1-q\), que inverte a ordem das soluções: o menor ponto fixo na variável \(q\) corresponde à maior solução na variável \(\theta \).

Exemplo 4.12 (Uma árvore binária)

Suponha que cada vértice tenha dois filhos e que cada aresta esteja aberta com probabilidade \(3/4\). Nesse caso,

\[ m=2\cdot \frac34=\frac32, \qquad f(s)=\left(\frac14+\frac34s\right)^2. \]

A equação de extinção é

\[ q=\left(\frac14+\frac34q\right)^2, \]

ou, equivalentemente,

\[ 9q^2-10q+1=(9q-1)(q-1)=0. \]

Como a probabilidade de extinção é o menor ponto fixo, \(q=1/9\). Portanto,

\[ \theta (3/4)=1-\frac19=\frac89. \]

Compare com o Exemplo 4.5, em que cada indivíduo tinha zero ou dois filhos, com probabilidades \(1/4\) e \(3/4\). A média de descendentes também era \(3/2\), mas a probabilidade de extinção era \(1/3\), não \(1/9\). A chance de alcançar infinitos vértices depende da distribuição dos descendentes, não apenas de sua média.

Há ainda uma distinção entre a extinção e o tamanho esperado da componente. Para calcular \(E(|C(o)|)\) a partir da soma das gerações, começamos pela contagem até uma geração finita:

\[ B_N=\sum _{n=0}^{N}Z_n, \qquad E(B_N)=\sum _{n=0}^{N}(bp)^n. \]

A última igualdade usa o Teorema 4.7 e a linearidade da esperança. Como \(B_N\) cresce para \(|C(o)|\), a passagem ao limite para contagens crescentes, justificada no Lema 2.15, fornece

\[ E\bigl(|C(o)|\bigr) =\sum _{n=0}^{\infty }(bp)^n =\begin{cases} \displaystyle \frac{1}{1-bp},& p\lt 1/b,\\[6pt] +\infty ,& p\geq 1/b. \end{cases} \]

No ponto crítico \(p=1/b\), a componente da raiz é finita quase certamente, mas seu tamanho esperado é infinito. Não há contradição: o fato de uma variável aleatória ser finita quase certamente não obriga sua esperança a ser finita.

4.5.2 Erdős–Rényi: da exploração local à componente gigante

Uma árvore não tem ciclos: cada vértice distinto da raiz está ligado a ela por um único caminho simples, isto é, sem repetir vértices. Em uma rede geral, podemos encontrar um mesmo vértice por caminhos diferentes. Essas colisões impedem que a exploração da componente seja, exatamente, um processo de Galton–Watson.

Ainda assim, a ramificação descreve bem o início da exploração de certos grafos aleatórios. O exemplo mais conhecido é o modelo de Erdős–Rényi.

Definição 4.5

Grafo aleatório de Erdős–Rényi Fixe \(n\geq 2\) e \(p\in [0,1]\). O grafo \(G(n,p)\) tem vértices \(\{ 1,\ldots ,n\} \). Para cada par de vértices distintos, a aresta que os liga está presente com probabilidade \(p\), independentemente das demais.

Trata-se da percolação por arestas no grafo completo com \(n\) vértices: começamos com todas as arestas possíveis e conservamos cada uma delas com probabilidade \(p\). A Figura 4.9 mostra uma realização com seis vértices.

Ilustração: Erdős–Rényi: da exploração local à componente gigante

Figura 4.9 Uma realização de \(G(6,p)\). As cinco arestas presentes aparecem em verde-petróleo, e as dez ausentes, em cinza pontilhado. As componentes conexas são \(\{ 1,2,3,4\} \) e \(\{ 5,6\} \).

Para estudar grafos grandes, escolheremos

\[ p=\frac cn,\qquad c\gt 0\text{ fixo}, \]

com \(n\) suficientemente grande para que \(c/n\leq 1\). Essa escolha mantém o número médio de vizinhos por vértice próximo de \(c\). De fato, se \(D_v\) é o número de vizinhos, ou grau, de um vértice \(v\), então

\[ D_v\sim \operatorname {Binomial}\left(n-1,\frac cn\right), \qquad E(D_v)=(n-1)\frac cn\longrightarrow c. \]

Quando \(n\) cresce, temos muitas possibilidades de ligação, cada uma com probabilidade pequena. Para cada \(j\) fixo,

\[ \mathbb {P}(D_v=j) =\binom {n-1}{j}\left(\frac cn\right)^j \left(1-\frac cn\right)^{n-1-j} \longrightarrow e^{-c}\frac{c^j}{j!}. \]

Para verificar esse limite, observe que

\[ \binom {n-1}{j}\left(\frac cn\right)^j =\frac{c^j}{j!}\prod _{\ell =1}^{j}\left(1-\frac\ell n\right) \longrightarrow \frac{c^j}{j!}, \]

com produto vazio igual a um quando \(j=0\), enquanto \((1-c/n)^{n-1-j}\to e^{-c}\). Assim, o número de vizinhos de um vértice fixado tem, no limite, distribuição de Poisson de média \(c\).

Mas conhecer a distribuição do grau não basta para entender o tamanho de uma componente. Precisamos acompanhar sua exploração. Começamos por um vértice e o colocamos em uma fila. Ao examinar o primeiro vértice da fila, revelamos suas arestas para os vértices ainda não descobertos. Os novos vizinhos entram no fim da fila, e o vértice examinado sai dela. Repetimos esse procedimento até a fila ficar vazia; nesse momento, toda a componente inicial foi descoberta.

Suponha que a fila ainda não esteja vazia e que, até essa etapa, tenham sido descobertos \(r\) vértices: o inicial e todos os novos vizinhos encontrados nos passos anteriores. Esse total inclui os já examinados e os que ainda aguardam na fila. Restam \(n-r\) vértices não descobertos, e as arestas entre eles e o próximo vértice a ser examinado ainda não foram reveladas. Condicionalmente ao histórico da exploração, o número de novos vizinhos tem, portanto, distribuição

\[ \operatorname {Binomial}\left(n-r,\frac cn\right). \]

Ao contrário de uma ramificação com descendentes independentes, a distribuição dessas contagens muda ao longo da exploração: \(r\) depende dos resultados dos passos anteriores. Mas, enquanto \(r\) for pequeno em comparação com \(n\), a distribuição acima se aproxima de uma Poisson de média \(c\). Para um número fixo de etapas, essa aproximação pode ser tornada rigorosa quando \(n\to \infty \): a exploração é descrita, no limite, por uma ramificação com descendências independentes de lei Poisson de média \(c\), encerrada se não houver mais vértices por examinar.

Essa descrição é local. Em um grafo com ciclos, podem existir arestas entre vértices já descobertos, mas essas ligações não acrescentam novos elementos à fila. Na exploração, só podem ser novos vizinhos os \(n-r\) vértices ainda não descobertos. Quando \(r\) deixa de ser pequeno diante de \(n\), a média condicional \((n-r)c/n\) já não está próxima de \(c\), e a aproximação por Galton–Watson não descreve sozinha a exploração de uma componente grande.

Para a distribuição de Poisson de média \(c\), a função geradora é

\[ f(s)=e^{c(s-1)},\qquad m=c. \]

O Teorema 4.12 sugere, portanto, uma mudança de comportamento em \(c=1\): abaixo desse valor a ramificação se extingue quase certamente; acima dele há probabilidade positiva de sobrevivência. O resultado para o grafo finito é mais forte e exige argumentos adicionais.

Teorema 4.16

Componente gigante em Erdős–Rényi Considere \(G(n,c/n)\), com \(c\gt 0\) fixo, e denote por \(L_1(n)\geq L_2(n)\) os tamanhos das duas maiores componentes conexas, com \(L_2(n)=0\) se houver apenas uma componente.

Se \(0\lt c\lt 1\), existe uma constante \(A=A(c)\) tal que

\[ \mathbb {P}\bigl(L_1(n)\leq A\log n\bigr)\longrightarrow 1. \]
Se \(c\gt 1\), então

\[ \frac{L_1(n)}n\longrightarrow \rho (c) \quad \text{em probabilidade}, \]

onde \(\rho (c)\in (0,1)\) é a única solução positiva de

\[ \rho =1-e^{-c\rho }. \]

Além disso, existe uma constante \(B=B(c)\) tal que

\[ \mathbb {P}\bigl(L_2(n)\leq B\log n\bigr)\longrightarrow 1. \]

A convergência em probabilidade no segundo item significa que, para todo \(\varepsilon \gt 0\),

\[ \mathbb P\left(\left|\frac{L_1(n)}n-\rho (c)\right|\gt \varepsilon \right) \longrightarrow 0. \]

Portanto, a fração de vértices na maior componente se concentra perto de \(\rho (c)\) quando o grafo cresce.

Uma componente que reúne uma proporção positiva dos vértices é chamada de componente gigante. O teorema afirma que ela não aparece no regime subcrítico e que, no supercrítico, existe uma única componente desse tipo: todas as demais têm tamanho muito menor que \(n\). No ponto crítico \(c=1\), não há componente gigante; o tamanho das maiores componentes está na escala \(n^{2/3}\), um comportamento mais delicado que não estudaremos aqui.

Não demonstraremos esse resultado; uma apresentação com demonstrações dos três regimes está em Frieze e Karoński (2016, capítulo 2). A aproximação local por Galton–Watson explica a origem da equação para \(\rho (c)\), mas não é suficiente para justificar a existência e a unicidade de uma componente gigante. Para isso, é necessário controlar a exploração também quando o número de vértices descobertos já é grande.

A equação do teorema é precisamente a equação de sobrevivência para um processo de Galton–Watson de descendência Poisson de média \(c\). Com efeito, se \(q\) é sua probabilidade de extinção,

\[ q=e^{c(q-1)}. \]

Escrevendo \(\rho (c)=1-q\), encontramos

\[ \rho (c)=1-e^{-c\rho (c)}. \]

Essa coincidência tem uma interpretação probabilística. Depois de realizado o grafo, escolha um de seus \(n\) vértices uniformemente. A probabilidade de ele pertencer à maior componente, condicionada ao grafo, é \(L_1(n)/n\), que pelo teorema fica próxima de \(\rho (c)\) com alta probabilidade. Por outro lado, a exploração iniciada nesse vértice se aproxima, nas primeiras etapas, de uma ramificação Poisson: a chance de essa ramificação sobreviver sugere a proporção de vértices que pertencem à componente gigante. Essa interpretação não substitui os argumentos globais necessários à prova do teorema.

Exemplo 4.13 (Uma componente com quase oitenta por cento dos vértices)

Considere \(G(n,2/n)\). No Exemplo 4.6, vimos que a probabilidade de extinção de uma ramificação com descendência Poisson de média \(2\) é aproximadamente \(q=0{,}203188\). Portanto,

\[ \rho (2)=1-q\approx 0{,}796812. \]

Em um grafo suficientemente grande desse modelo, a maior componente ocupa uma proporção próxima de \(79{,}7\% \) dos vértices, com alta probabilidade.

Isso não significa que o grafo inteiro seja conexo. Um vértice específico é isolado quando nenhuma de suas \(n-1\) arestas possíveis está presente, o que ocorre com probabilidade

\[ \left(1-\frac2n\right)^{n-1}\longrightarrow e^{-2} \approx 0{,}1353. \]

Pela linearidade da esperança, a proporção esperada de vértices isolados também se aproxima de \(13{,}5\% \). A existência de uma componente gigante não é o mesmo que a conectividade de todo o grafo.

Nos dois modelos, a média de descendentes igual a um marca a transição. Na árvore, alcançar novos vértices é exatamente um processo de ramificação. Em Erdős–Rényi, essa descrição vale aproximadamente no início da exploração, mas antecipa uma propriedade global do grafo. O que começou como uma pergunta sobre extinção torna-se uma pergunta sobre o aparecimento de grandes estruturas em uma rede.

4.6 Exercícios

4.6.1 Passeios e outras cadeias enumeráveis

Exercício 4.1

Retornar sempre não significa retornar depressa Compare os passeios em \(\mathbb Z\) com \(p=1/2\) e com \(p=7/10\). Use as probabilidades de retorno em tempos pares para classificá-los. No caso simétrico, explique por que recorrência não implica tempo médio de retorno finito.

Exercício 4.2

Uma recompensa sem média estacionária finita Em \(\mathbb N_0\), faça \(p(i,0)=1/3\) e \(p(i,i+1)=2/3\) para todo \(i\geq 0\). Encontre a distribuição estacionária, o tempo médio de retorno a zero e a média temporal de \(X_n\). Para \(f(i)=2^i\), verifique que a hipótese de integrabilidade do teorema ergódico falha. Use as funções limitadas \(f\wedge b\) para mostrar que a média temporal de \(f(X_n)\) tende a \(+\infty \).

4.6.2 Processos de ramificação

Exercício 4.3

Transições e duas gerações Para \(p_0=1/4\) e \(p_2=3/4\), calcule \(p(2,0)\), \(p(2,2)\), \(p(2,4)\) e \(E_2(Z_3)\). Partindo de uma semente, calcule a probabilidade de extinção até a segunda geração e compare-a com a probabilidade de extinção eventual.

Exercício 4.4

Quando a extinção é impossível? Lembre que \(q=\mathbb {P}_1(H_0\lt \infty )\) se refere a uma semente. Mostre que \(q=0\) se e somente se \(p_0=0\), e conclua que, para toda população inicial de \(k\geq 1\) indivíduos, a extinção é impossível exatamente quando \(p_0=0\). Use a relação \(\mathbb {P}_k(H_0\lt \infty )=q^k\). Explique por que o caso \(Y\equiv 1\) precisa ser separado no critério pela média.

Exercício 4.5

Descendência geométrica Suponha \(\mathbb {P}(Y=j)=(1-r)r^j\), \(j\geq 0\), com \(0\lt r\lt 1\). Calcule \(m\), \(f\) e \(q\) em função de \(r\). Depois, determine a probabilidade de sobrevivência com três sementes quando \(r=2/3\).

Exercício 4.6

Tamanho total no regime subcrítico Se \(m\lt 1\) e \(Z_0=k\), seja \(B=\sum _{n\geq 0}Z_n\) o número total de indivíduos, incluindo os iniciais. Prove que \(E(B)=k/(1-m)\). Justifique a troca entre soma e esperança a partir das somas finitas \(B_M=\sum _{n=0}^{M}Z_n\) e de suas probabilidades de cauda, admitindo inicialmente a possibilidade \(B=\infty \). Explique por que a finitude da média obtida implica \(B\lt \infty \) quase certamente.

Exercício 4.7

Amostragem e fronteira Uma amostra completa de \(60\) indivíduos contém \(18\) sem filhos, \(6\) com um filho e \(36\) com dois filhos. Calcule \(\widehat m\), \(\widehat f\), \(\widehat q\) e a probabilidade estimada de extinção com duas sementes. Explique o que \(\widehat p_3=0\) permite afirmar e por que uma árvore encerrada com \(60\) vértices não poderia produzir essas contagens.

4.7 Exercícios complementares^*

Exercício 4.8

Uma árvore ternária^* Cada vértice de uma árvore infinita possui três filhos, e cada aresta é aberta independentemente com probabilidade \(p\). Determine o valor crítico de \(p\). Para \(p=1/4\), calcule o tamanho esperado da componente da raiz. Explique o que acontece com a probabilidade de uma componente infinita e com o tamanho esperado quando \(p=1/3\).

Exercício 4.9

Árvore regular e a escolha da raiz^* Em uma árvore infinita em que todos os vértices têm exatamente \(d\geq 3\) vizinhos, escolha um deles como raiz. Abra cada aresta, independentemente, com probabilidade \(p\). A raiz tem \(d\) vizinhos, mas cada um dos demais vértices tem apenas \(d-1\) filhos, pois um vizinho é seu pai. Determine a probabilidade crítica de percolação por arestas. Explique por que a diferença na primeira geração não altera esse limiar.

Exercício 4.10

Vértices isolados em Erdős–Rényi^* Considere \(G(n,c/n)\) e denote por \(I_n\) o número de vértices isolados. Calcule \(E(I_n)\) e mostre que \(E(I_n)/n\to e^{-c}\). Por que a presença de uma componente gigante, quando \(c\gt 1\), não implica que o grafo seja conexo?

Cadeias de Markov enumeráveis

4.1 Passeios aleatórios em \(\mathbb Z^d\)

4.2 Um sistema com infinitos estados: o protocolo Aloha

4.3 Processos de ramificação

4.3.1 Indivíduos, gerações e crescimento médio

4.3.2 Geradoras e extinção

4.3.3 Cascatas: o que os dados permitem estimar

4.4 Problemas de síntese

4.5 Percolação em árvores e grafos aleatórios*

4.5.1 Percolação em uma árvore infinita

4.5.2 Erdős–Rényi: da exploração local à componente gigante

4.6 Exercícios

4.6.1 Passeios e outras cadeias enumeráveis

4.6.2 Processos de ramificação

4.7 Exercícios complementares*

4.5 Percolação em árvores e grafos aleatórios^*

4.7 Exercícios complementares^*