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

23Funções geradoras de probabilidade

As séries de potências do Capítulo 11 voltam com uma missão probabilística: a uma variável aleatória com valores em $\N$ associamos a série de potências de coeficientes $\P(X = n)$ . Essa função geradora converte somas de variáveis independentes em produtos, momentos em derivadas em $1$ e identidades combinatórias difíceis em multiplicações de uma linha. O capítulo fecha o livro com duas peças de exibição: a aproximação de Poisson de eventos raros e o critério de extinção para processos de ramificação — um cálculo probabilístico genuinamente infinito resolvido inteiramente pela geometria de uma curva convexa.

23.1 Definição e propriedades básicas

Definição 23.1 (Função geradora de probabilidade)

Seja $X$ uma variável aleatória com valores em $\N$ , $p_n = \P(X = n)$ . A função geradora de probabilidade de $X$ é a soma da série de potências

G_X(t) = \E\bigl(t^X\bigr) = \sum_{n=0}^{\infty} p_n\,t^n .

Exemplo 23.2 (Primeiros reflexos)

Uma variável constante $X = c$ tem $G_X(t) = t^c$ ; um deslocamento obedece a $G_{X+c}(t) = t^c\,G_X(t)$ ; e avaliar em pontos especiais extrai informação sem desenvolvimento algum: $G_X(0) = \P(X = 0)$ , $G_X(1) = 1$ e $G_X(-1) = \P(X\text{ par}) - \P(X\text{ ímpar})$ , o balanço de paridades explorado no Exercício 23.10. Essas frases de uma linha são usadas silenciosamente em toda parte abaixo — e a avaliação $G_X(0)$ é exatamente como as probabilidades de extinção serão extraídas de funções geradoras iteradas no fim do capítulo.

Proposição 23.3 (Raio e primeiras propriedades)

A série que define $G_X$ tem raio de convergência $\geq 1$ ; $G_X$ está definida e é contínua em $\intcc{-1}{1}$ , $\mathcal{C}^\infty$ em $\intoo{-1}{1}$ , com $G_X(1) = 1$ e $\abs{G_X(t)} \leq 1$ ali. Além disso, $G_X$ determina a lei de $X$ :

p_n = \frac{G_X^{(n)}(0)}{n!} .

Demonstração. Como $\sum p_n = 1$ converge, os termos $p_n\,1^n$ são limitados, de modo que o raio é $\geq 1$ (lema de Abel, Capítulo 11); em $t = \pm1$ a série converge absolutamente ( $\sum p_n = 1$ a domina); melhor, em todo o intervalo $\intcc{-1}1$ ,

\sup_{\abs t\leq1}\,\abs{p_nt^n} = p_n \quad\text{com}\quad \sum_np_n < \infty :

a série converge normalmente em $\intcc{-1}1$ , de modo que sua soma é contínua ali (Teoremas 10.16 e 10.4). A suavidade no interior e a fórmula dos coeficientes são a teoria geral das séries de potências; sendo os coeficientes recuperáveis, duas variáveis com a mesma função geradora têm a mesma lei. ∎

Exemplo 23.4 (As leis clássicas)

Bernoulli $\mathcal{B}(p)$ : $G(t) = 1 - p + pt$ .
Binomial $\mathcal{B}(n, p)$ : $G(t) = \sum_k \binom nk (pt)^k(1-p)^{n-k} = (1 - p + pt)^n$ (teorema binomial).
Geométrica $\mathcal{G}(p)$ : $G(t) = \sum_{k\geq1}(1-p)^{k-1}p\,t^k = \dfrac{pt}{1 - (1-p)t}$ (raio $\frac{1}{1-p} > 1$ ).
Poisson $\mathcal{P}(\lambda)$ : $G(t) = \sum_k e^{-\lambda}\frac{(\lambda t)^k}{k!} = e^{\lambda(t - 1)}$ (raio $\infty$ ).

Exemplo 23.5 (Integrando a função geradora)

As derivadas de $G_X$ em $1$ dão momentos positivos; a integral dá um momento negativo. De $\int_0^1t^k\dd t = \frac1{k+1}$ e da integração termo a termo (convergência normal em $\intcc01$ ):

\int_0^1G_X(t)\,\dd t = \sum_{k\geq0}\frac{\P(X = k)}{k+1} = \E\Bigl(\frac1{1+X}\Bigr).

Para $X \sim \mathcal P(\lambda)$ :

\E\Bigl(\frac1{1+X}\Bigr) = \int_0^1\eu^{\lambda(t-1)}\,\dd t = \frac{1 - \eu^{-\lambda}}{\lambda},

recuperando numa linha o cálculo em séries do Exemplo 22.10. A função geradora é um instrumento de mão dupla: derive em $1$ para os momentos $\E(X)$ , $\E(X(X-1))$ , integre em $\intcc01$ para $\E\bigl(\frac1{1+X}\bigr)$ — um só objeto analítico, consultado na direção de que o problema precisa.

Exemplo 23.6 (Uma lei de raio exatamente um)

Seja $\P(X = k) = \dfrac{6}{\pi^2k^2}$ para $k \geq 1$ — uma lei de probabilidade pela identidade de Basileia (Exemplo 14.12). Sua função geradora $G(t) = \frac6{\pi^2}\sum_{k\geq1}\frac{t^k}{k^2}$ tem raio de convergência exatamente $1$ : a cota geral “raio $\geq 1$ ” da Proposição 23.3 não pode ser melhorada. E a média vale

\sum_{k\geq1}k\,\P(X = k) = \frac6{\pi^2}\sum_{k\geq1}\frac1k = \infty :

$G$ é contínua em $\intcc{-1}1$ , suave no interior, mas sua derivada explode em $1^-$ — o gráfico chega ao ponto $(1, 1)$ com tangente vertical. As caudas pesadas são visíveis geometricamente na função geradora, no único ponto $t = 1$ ; o teorema dos momentos abaixo torna essa correspondência exata.

Teorema 23.7 (Momentos a partir da função geradora)

$X$ tem esperança se e somente se $G_X$ é diferenciável em $1^-$ (derivada à esquerda, finita), e então $\E(X) = G_X'(1)$ . Do mesmo modo, $X$ tem momento de segunda ordem se e somente se $G_X$ é duas vezes diferenciável em $1^-$ , e então

\E\bigl(X(X - 1)\bigr) = G_X''(1), \qquad V(X) = G_X''(1) + G_X'(1) - G_X'(1)^2 .

Demonstração. Para $t \in \intoo{0}{1}$ , a derivação termo a termo dentro do disco dá $G_X'(t) = \sum_{n\geq1} np_n t^{n-1}$ , uma série com coeficientes não negativos: $t \mapsto G_X'(t)$ é não decrescente em $\intoo{0}{1}$ e, por convergência monótona das somas parciais (ou pelo teorema de Abel para coeficientes não negativos, Capítulo 11),

\lim_{t \to 1^-} G_X'(t) = \sum_{n\geq1} n\,p_n \in \intcc{0}{+\infty} ,

cada membro finito exatamente quando o outro o é. Quando finito, o teorema do valor médio espreme os quocientes de diferenças $\frac{G_X(1) - G_X(t)}{1 - t}$ entre valores de $G_X'$ , de modo que $G_X$ é diferenciável em $1^-$ com $G_X'(1) = \sum np_n = \E(X)$ (por transferência). O enunciado de segunda ordem repete o argumento um nível acima: $G''_X(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ é não decrescente em $\intoo01$ com limite monótono $\sum_nn(n-1)p_n = \E(X(X-1))$ , finito exatamente quando $X$ tem momento de segunda ordem. A fórmula da variância segue então de König–Huygens:

V(X) = \E(X^2) - \E(X)^2 = \E\bigl(X(X-1)\bigr) + \E(X) - \E(X)^2 = G''_X(1) + G'_X(1) - G'_X(1)^2 .

∎

Exemplo 23.8

Poisson: $G'(t) = \lambda e^{\lambda(t-1)}$ , logo $\E(X) = \lambda$ ; $G''(1) = \lambda^2$ , logo $V(X) = \lambda^2 + \lambda - \lambda^2 = \lambda$ — os cálculos do Capítulo 22 em uma linha cada.

Exemplo 23.9 (A moda de uma lei de Poisson)

Onde $\P(X = k)$ é maior para $X \sim \mathcal P(\lambda)$ ? Pesos consecutivos se comparam pela razão

\frac{\P(X = k+1)}{\P(X = k)} = \frac{\lambda}{k + 1} ,

que excede $1$ enquanto $k < \lambda - 1$ e cai abaixo de $1$ assim que $k > \lambda - 1$ : os pesos sobem e depois descem, com moda $\floor\lambda$ (e um empate entre $\lambda - 1$ e $\lambda$ quando $\lambda$ é inteiro: para $\lambda = 3$ , $\P(X = 2) = \P(X = 3) = \frac92\eu^{-3} \approx 0.224$ ). Testes de razão sobre os coeficientes são muitas vezes a via mais rápida para fatos qualitativos sobre uma lei discreta — sem precisar de função geradora, mas os coeficientes são a função geradora, lida termo a termo.

23.2 Somas de variáveis independentes

Teorema 23.10 (Multiplicatividade)

Se $X$ e $Y$ são variáveis aleatórias independentes com valores em $\N$ , então

G_{X + Y}(t) = G_X(t)\,G_Y(t) \qquad (\abs t \leq 1),

e, por indução, $G_{X_1 + \dots + X_n} = \prod_i G_{X_i}$ para $X_1, \dots, X_n$ independentes.

Demonstração. Duas demonstrações, ambas instrutivas. Via esperanças: $t^X$ e $t^Y$ são variáveis limitadas independentes, de modo que (Teorema 22.11)

G_{X+Y}(t) = \E\bigl(t^{X+Y}\bigr) = \E\bigl(t^X t^Y\bigr) = \E\bigl(t^X\bigr)\E\bigl(t^Y\bigr) .

Via produtos de Cauchy: a lei de $X + Y$ é a convolução $\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k)$ , e o teorema do produto de Cauchy para séries absolutamente convergentes (Capítulo 7) multiplica as duas séries de potências exatamente ao longo dessa convolução. ∎

Exemplo 23.11 (Estabilidade das leis clássicas)

Binomiais independentes com o mesmo $p$ se somam: $(1 - p + pt)^m(1 - p + pt)^n = (1 - p + pt)^{m+n}$ , logo $\mathcal{B}(m, p) + \mathcal{B}(n, p) = \mathcal{B}(m + n, p)$ — em particular, uma soma de $n$ variáveis de Bernoulli independentes é binomial, redemonstrando a lei do número de sucessos. Poissons independentes se somam: $e^{\lambda(t-1)}e^{\mu(t-1)} = e^{(\lambda + \mu)(t-1)}$ , logo $\mathcal{P}(\lambda) + \mathcal{P}(\mu) = \mathcal{P}(\lambda + \mu)$ — o cálculo de convolução do Exercício 22.2, agora sem cálculo algum.

Exemplo 23.12 (Dois dados, um polinômio ao quadrado)

Para um dado honesto, $G(t) = \frac{t + t^2 + \dots + t^6}{6}$ ; para a soma de dois,

G(t)^2 = \frac{1}{36}\bigl(t^2 + 2t^3 + 3t^4 + 4t^5 + 5t^6 + 6t^7 + 5t^8 + 4t^9 + 3t^{10} + 2t^{11} + t^{12}\bigr) :

a lei triangular das somas de dados ( $7$ é a moda, com probabilidade $\frac6{36} = \frac16$ ), lida num quadrado de polinômio que se multiplica uma vez na vida. A fórmula de convolução teria exigido onze argumentos de contagem separados; a função geradora os faz todos simultaneamente, porque multiplicar polinômios é convoluir coeficientes. Essa tradução mecânica — leis em coeficientes, somas em produtos — é todo o modelo de negócios do capítulo, e o Exercício 23.11 o leva até os surpreendentes dados de Sicherman.

Exemplo 23.13 (Três dados e uma extração de coeficiente)

Para a soma $S$ de três dados honestos, $\P(S = 10)$ é o coeficiente de $t^{10}$ em $\bigl(\frac{t + \dots + t^6}6\bigr)^3$ . Fatore e desenvolva com as séries binomial e geométrica:

\Bigl(\frac{t(1 - t^6)}{6(1 - t)}\Bigr)^{\!3} = \frac{t^3}{216}\,\bigl(1 - 3t^6 + 3t^{12} - t^{18}\bigr)\sum_{j\geq0}\binom{j+2}2t^j .

O coeficiente de $t^{10}$ exige $t^7$ do produto: $j = 7$ com o termo $1$ , e $j = 1$ com o termo $-3t^6$ :

\P(S = 10) = \frac{1}{216}\Bigl(\binom92 - 3\binom32\Bigr) = \frac{36 - 9}{216} = \frac{27}{216} = \frac18 .

A enumeração direta das $27$ triplas é propensa a erros; a álgebra é mecânica e escala para qualquer número de dados — a inclusão–exclusão visível em $(1 - t^6)^3$ faz a análise de casos automaticamente.

Exemplo 23.14 (Lendo uma lei em sua função geradora)

Que lei tem $G(t) = \dfrac1{2 - t}$ ? Desenvolva em série de potências:

\frac{1}{2 - t} = \frac12\cdot\frac1{1 - t/2} = \sum_{k\geq0}\frac{t^k}{2^{k+1}} :

coeficientes não negativos de soma $G(1) = 1$ , de modo que essa é uma lei genuína, $\P(X = k) = 2^{-(k+1)}$ em $\N$ — uma lei geométrica começando em $0$ . Por unicidade (Proposição 23.3), nenhuma outra lei compartilha essa $G$ . Reconhecer leis a partir de suas funções geradoras é uma habilidade que vale treinar: é assim que o iterado crítico de ramificação $G_n(t) = \frac{n - (n-1)t}{n+1 - nt}$ do problema de fim de semana é desmascarado como uma lei geométrica condicionada à sobrevivência.

Observação 23.15

A estabilidade vale num sentido só: somas de Poissons independentes são Poisson, mas diferenças não são — $X - Y$ assume valores negativos, de modo que não tem função geradora alguma, e sua lei (a distribuição de Skellam) fica fora do instrumental deste capítulo. Do mesmo modo, $\mathcal B(m, p) + \mathcal B(n, p')$ com $p \neq p'$ não é binomial: o produto $(1 - p + pt)^m(1 - p' + p't)^n$ tem duas localizações de raiz distintas, ao passo que toda função geradora binomial tem uma única raiz repetida. Ler a estabilidade nos padrões de raízes é uma pequena antevisão de quanta estrutura o polinômio codifica.

Observação 23.16 (O filtro das raízes da unidade)

Avaliar em $-1$ separa pares de ímpares; avaliar em todas as raízes $m$ -ésimas da unidade separa cada classe de resto: com $\omega = \eu^{2\iu\pi/m}$ ,

\P(X \equiv r \bmod m) = \frac1m\sum_{j=0}^{m-1}\omega^{-jr}\,G_X(\omega^j),

pois a média de $\omega^{j(k-r)}$ sobre $j$ dá $1$ se $k \equiv r$ e $0$ caso contrário. Dividendo de amostra: para a soma $S$ de dois dados honestos, cada $G(\omega^j) = \frac16\sum_{k=1}^6 \omega^{jk} = -\frac16$ para $j \neq 0$ (as sete raízes sétimas da unidade somam zero), logo

\P(7 \mid S) = \frac17\Bigl(1 + 6\cdot\frac1{36}\Bigr) = \frac16 ,

confirmando a contagem do Exemplo 23.12 — e o método escala para questões em que a contagem direta não escala.

Teorema 23.17 (Somas aleatórias: identidade de Wald para funções geradoras)

Sejam $(X_k)_{k\geq1}$ variáveis independentes com valores em $\N$ , de mesma lei e função geradora $G_X$ , e seja $N$ uma variável com valores em $\N$ independente das $X_k$ , de função geradora $G_N$ . Então a soma aleatória $S = X_1 + \dots + X_N$ (com $S = 0$ quando $N = 0$ ) tem função geradora

G_S = G_N \circ G_X .

Em particular, se $N$ e $X_1$ têm esperança, $\E(S) = \E(N)\,\E(X_1)$ .

Demonstração. Condicione a $N$ (probabilidade total, Teorema 21.14): para $\abs t \leq 1$ ,

G_S(t) = \sum_{n=0}^\infty \P(N = n)\, \E\bigl(t^{X_1 + \dots + X_n}\bigr) = \sum_{n=0}^\infty \P(N = n)\,G_X(t)^n = G_N\bigl(G_X(t)\bigr),

usando a multiplicatividade para cada $n$ fixo e a somabilidade de toda a família dupla ( $\abs{G_X(t)} \leq 1$ ). A troca de somas é Fubini para famílias somáveis (Capítulo 7). Derivando em $1^-$ pela regra da cadeia e Teorema 23.7: $\E(S) = G_N'(G_X(1))\,G_X'(1) = G_N'(1)G_X'(1) = \E(N)\E(X_1)$ . ∎

Exemplo 23.18 (Poisson composta: perdas anuais de seguro)

Uma seguradora recebe $N \sim \mathcal P(\lambda)$ sinistros num ano, custando cada sinistro $X_k$ (unidades inteiras, i.i.d., com função geradora $G_X$ , média $\mu$ , independentes de $N$ ). Pelo Teorema 23.17, a perda total $S$ tem

G_S(t) = \eu^{\lambda(G_X(t) - 1)}, \qquad \E(S) = \lambda\mu ,

e, derivando duas vezes em $1^-$ :

V(S) = \lambda\,G_X''(1) + \lambda^2\mu^2 + \lambda\mu - (\lambda\mu)^2 = \lambda\,\E(X^2) .

A variância envolve o segundo momento de um único sinistro, não sua variância: uma soma de Poisson composta sente o sinistro grande ocasional duas vezes — uma pelo quantos, outra pelo quão grande. Para $\lambda = 10$ sinistros de lei geométrica de média $2$ ( $\E X^2 = 6$ ): $\E S = 20$ , $V(S) = 60$ , e Chebyshev (Capítulo 22) já fornece margens de solvência utilizáveis. Esse padrão de “soma parada aleatoriamente” é o mesmo que moverá a recursão de ramificação do Proposição 23.23: a composição de funções geradoras é a álgebra das populações aleatórias.

Observação 23.19

A independência de $N$ em relação às parcelas não é decorativa. Tome $X_k \in \{0, 2\}$ com probabilidades iguais e ponha $N = X_1$ (flagrantemente dependente): então $S = X_1 + \dots + X_N$ vale $0$ quando $X_1 = 0$ , e $2 + X_2$ quando $X_1 = 2$ , de modo que $\E(S) = \frac12(2 + 1) = \frac32$ , enquanto $\E(N)\E(X_1) = 1\cdot1 = 1$ : a identidade de Wald falha. Quando o número de parcelas pode reagir às próprias parcelas, a estrutura limpa de produto desmorona — a teoria completa dessas regras de “parada” é o capítulo de martingais do volume do terceiro ano de graduação.

23.3 Aproximação de Poisson

Teorema 23.20 (Lei dos eventos raros)

Seja $X_n \sim \mathcal{B}(n, p_n)$ com $n\,p_n \to \lambda > 0$ . Então, para todo $k \in \N$ :

\P(X_n = k) \xrightarrow[n\to\infty]{} e^{-\lambda}\frac{\lambda^k}{k!} :

a lei binomial de muitos eventos independentes raros converge à lei de Poisson de parâmetro $\lambda$ .

Demonstração. Cálculo direto com $p_n = \frac{\lambda_n}{n}$ , $\lambda_n \to \lambda$ :

\P(X_n = k) = \binom nk p_n^k(1 - p_n)^{n-k} = \frac{n(n-1)\cdots(n-k+1)}{n^k}\cdot \frac{\lambda_n^k}{k!}\, \bigl(1 - \tfrac{\lambda_n}{n}\bigr)^{n-k} .

Quando $n \to \infty$ com $k$ fixo: o primeiro fator tende a $1$ (produto de $k$ fatores $\to 1$ ); $\lambda_n^k \to \lambda^k$ ; e $\bigl(1 - \frac{\lambda_n}{n}\bigr)^{n-k} = \exp\bigl((n-k)\ln(1 - \frac{\lambda_n}{n})\bigr) \to e^{-\lambda}$ pois $(n - k)\ln\bigl(1 - \frac{\lambda_n}{n}\bigr) \sim -\lambda_n \to -\lambda$ (Capítulo 6). Alternativamente, no nível das funções geradoras: $G_{X_n}(t) = \bigl(1 + \frac{\lambda_n(t-1)}{n}\bigr)^n \to e^{\lambda(t - 1)} = G_{\mathcal{P}(\lambda)}(t)$ para cada $t \in [0, 1]$ fixo — convergência de funções geradoras que (para variáveis com valores em $\N$ ) é equivalente à convergência de cada $\P(X_n = k)$ ; veja o Exercício 23.9. ∎

Observação 23.21

É por isso que as leis de Poisson modelam contagens de eventos raros — erros de digitação por página, decaimentos radioativos por segundo, acidentes por dia num cruzamento: cada oportunidade é quase desprezível, as oportunidades são muitas, e só a taxa média $\lambda$ sobrevive no limite.

Exemplo 23.22 (Vendo o limite de Poisson convergir)

Fixe $\lambda = 2$ e faça $X_n \sim \mathcal B(n, 2/n)$ . A probabilidade de nenhum evento é exatamente $\P(X_n = 0) = (1 - 2/n)^n$ :

n = 10:\ 0.107, \qquad n = 20:\ 0.122, \qquad n = 50:\ 0.130, \qquad n = 100:\ 0.133,

contra o limite $\eu^{-2} \approx 0.135$ . A convergência é monótona e de velocidade $O(1/n)$ — desenvolvendo, $(1 - 2/n)^n = \eu^{-2}\bigl(1 - \tfrac2n + O(n^{-2})\bigr)$ — de modo que, para $n$ na casa das centenas, o modelo de Poisson já é preciso até o terceiro dígito. Esse é o conteúdo prático da lei dos eventos raros: quem modela nunca conhece $n$ e $p$ separadamente (quantas micro-oportunidades de erro de digitação uma página contém?), mas apenas seu produto $\lambda$ , e a lei limite misericordiosamente não depende de mais nada.

23.4 Processos de ramificação

Considere uma população que parte de um único ancestral; cada indivíduo, independentemente, tem um número aleatório de filhos com lei $(p_k)_{k \in \N}$ e função geradora $G$ (a distribuição de descendência). Seja $Z_n$ o tamanho da geração $n$ ( $Z_0 = 1$ ), e seja $m = G'(1) = \E(Z_1)$ o número médio de filhos.

Proposição 23.23

A função geradora de $Z_n$ é o $n$ -ésimo iterado $G_{Z_n} = G \circ G \circ \dots \circ G$ ( $n$ vezes), e as probabilidades de extinção $q_n = \P(Z_n = 0)$ satisfazem

q_0 = 0, \qquad q_{n+1} = G(q_n),

e crescem para a probabilidade $q$ de extinção eventual, que é um ponto fixo de $G$ .

Demonstração. A geração $n + 1$ é a soma aleatória da descendência dos $Z_n$ membros da geração $n$ , com contagens independentes entre si e de $Z_n$ : o Teorema 23.17 dá $G_{Z_{n+1}} = G_{Z_n} \circ G$ , e a indução a partir de $G_{Z_0}(t) = t$ dá o iterado $n$ vezes — que, pela associatividade da composição, pode igualmente ser lido como $G_{Z_{n+1}} = G \circ G_{Z_n}$ . Avaliando essa segunda forma em $0$ : $q_{n+1} = G_{Z_{n+1}}(0) = G\bigl(G_{Z_n}(0)\bigr) = G(q_n)$ . Os eventos $\{Z_n = 0\}$ crescem (populações extintas permanecem extintas), de modo que $q_n \uparrow q = \P\bigl(\bigcup_n\{Z_n = 0\}\bigr)$ pela continuidade monótona (Teorema 21.6), e a continuidade de $G$ em $[0, 1]$ transforma $q_{n+1} = G(q_n)$ em $q = G(q)$ no limite. ∎

Exemplo 23.24 (Vendo a extinção convergir)

Para a lei de descendência $(p_0, p_1, p_2) = (\tfrac14, \tfrac14, \tfrac12)$ de Exemplo 23.27, $G(t) = \tfrac14 + \tfrac14t + \tfrac12t^2$ e a iteração $q_{n+1} = G(q_n)$ dá

q_1 = 0.25, \quad q_2 = 0.34375, \quad q_3 \approx 0.39502, \quad q_4 \approx 0.42678, \quad q_5 \approx 0.44776,

subindo rumo à probabilidade de extinção $q = \tfrac12$ . As diferenças $q - q_n$ valem $0.25$ , $0.156$ , $0.105$ , $0.073$ , $0.052$ : cada uma é aproximadamente $\tfrac34$ da anterior e, de fato, o teorema do valor médio dá $q - q_{n+1} = G'(c_n)(q - q_n)$ com $G'(q) = \tfrac14 + q = \tfrac34$ . Duas morais: uma linhagem ainda viva na geração $n$ tem, embutida no mesmo cálculo, probabilidade $q - q_n$ de estar condenada mais tarde; e a taxa de convergência da escada da figura abaixo é a derivada no ponto fixo — o problema de fim de semana transforma ambas as observações em teoremas.

Teorema 23.25 (Critério de extinção)

Suponha $p_1 \neq 1$ . A probabilidade de extinção $q$ é o menor ponto fixo de $G$ em $\intcc{0}{1}$ , e:

se $m \leq 1$ (subcrítico ou crítico), $q = 1$ : a extinção é certa;
se $m > 1$ (supercrítico), $q < 1$ : a população sobrevive para sempre com probabilidade positiva $1 - q$ .

Demonstração. $G$ é convexa em $\intcc{0}{1}$ (série de potências com coeficientes não negativos: $G'' \geq 0$ ), não decrescente, com $G(1) = 1$ .

Menor ponto fixo: seja $r \in \intcc{0}{1}$ um ponto fixo qualquer. Então $q_0 = 0 \leq r$ e, indutivamente, $q_{n+1} = G(q_n) \leq G(r) = r$ (monotonia): logo $q = \lim q_n \leq r$ .

Caso $m \leq 1$ : suponha que $r < 1$ seja um ponto fixo. Pelo teorema do valor médio em $[r, 1]$ , existe $c \in \intoo{r}{1}$ com $G'(c) = \frac{G(1) - G(r)}{1 - r} = \frac{1 - r}{1 - r} = 1$ . Mas $G'$ é não decrescente (convexidade) com $\lim_{t\to1^-}G'(t) = m \leq 1$ , logo $G' \leq 1$ em $\intoo{0}{1}$ ; a igualdade $G'(c) = 1$ força então $G'$ a ser constante igual a $1$ em $\intco{c}{1}$ , portanto $G'' = \sum n(n-1)p_nt^{n-2} \equiv 0$ ali. Uma série de potências com coeficientes não negativos que se anula num intervalo tem todos esses coeficientes nulos: $p_n = 0$ para $n \geq 2$ , de modo que $G(t) = p_0 + p_1t$ e $1 = G'(c) = p_1$ — contradizendo a hipótese $p_1 \neq 1$ . Assim, $1$ é o único ponto fixo: $q = 1$ .

Caso $m > 1$ : perto de $1$ , $G(t) - t$ tem derivada $G'(t) - 1 \to m - 1 > 0$ quando $t \to 1^-$ , logo $G(t) - t < G(1) - 1 = 0$ em algum intervalo $\intoo{1 - \delta}{1}$ : a função contínua $G(t) - t$ vale $\geq 0$ em $t = 0$ ( $G(0) = p_0 \geq 0$ ) e é $< 0$ logo abaixo de $1$ , de modo que ela se anula em algum $r < 1$ (teorema do valor intermediário). O menor ponto fixo é então $q \leq r < 1$ . ∎

Probabilidades de extinção como iteração de ponto fixo q_n+1 = G(q_n) começando em q_0 = 0 (escada vermelha). À esquerda: uma lei de descendência subcrítica — a curva convexa fica acima da diagonal, e a iteração sobe até o ponto fixo único 1. À direita: uma lei supercrítica — a curva cruza a diagonal em q < 1, onde a iteração para: a sobrevivência tem probabilidade 1 - q > 0. — **Figura 23.1.** Probabilidades de extinção como iteração de ponto fixo $q_{n+1} = G(q_n)$ começando em $q_0 = 0$ (escada vermelha). À esquerda: uma lei de descendência subcrítica — a curva convexa fica acima da diagonal, e a iteração sobe até o ponto fixo único $1$ . À direita: uma lei supercrítica — a curva cruza a diagonal em $q < 1$ , onde a iteração para: a sobrevivência tem probabilidade $1 - q > 0$ .

Observação 23.26 (Como ler o diagrama de teia)

Na figura, um movimento vertical aplica $G$ (de $(q_n, q_n)$ até $(q_n, G(q_n))$ ), e um movimento horizontal até a diagonal converte saída em entrada: a escada é a recursão $q_{n+1} = G(q_n)$ . A convexidade de $G$ e $G(1) = 1$ deixam apenas duas geometrias. Ou a curva fica acima da diagonal em $\intco01$ (média $m \leq 1$ ): a escada não tem onde parar antes de $1$ . Ou a curva cruza em algum $q < 1$ ( $m > 1$ ): a escada fica presa abaixo do cruzamento e converge para ele, à taxa geométrica $G'(q) < 1$ quantificada no Exemplo 23.24. Toda a análise do teorema de extinção é visível nessa única imagem — e é por isso que vale a pena desenhá-la antes de calcular.

Exemplo 23.27

Lei de descendência: nenhum filho, um filho, dois filhos com probabilidades $\frac14, \frac14, \frac12$ . Então $m = \frac14 + 1 = \frac54 > 1$ e $G(t) = \frac14 + \frac14 t + \frac12 t^2$ . Pontos fixos: $\frac12 t^2 - \frac34 t + \frac14 = 0$ , isto é, $2t^2 - 3t + 1 = (2t - 1)(t - 1) = 0$ : $q = \frac12$ . A linhagem se extingue com probabilidade $\frac12$ — e com probabilidade $\frac12$ ela vive para sempre.

Observação 23.28 (Perspectivas dentro deste volume)

O capítulo é o entroncamento do livro, e cada ingrediente chegou de um lugar com nome: a álgebra de séries do Capítulo 7 e do Capítulo 11, a probabilidade do Capítulo 21 (a continuidade monótona demonstra $q_n \uparrow q$ ) e do Capítulo 22 ( $G_X = \E(t^X)$ é uma esperança, a multiplicatividade é o teorema do produto), a convexidade do Capítulo 8 via o Capítulo 17. Até as patologias de cauda pesada se conectam: a variável de São Petersburgo do capítulo anterior tem $G(t) = \sum_k2^{-k}t^{2^k}$ , uma série perfeitamente convergente em $\intcc01$ cuja derivada em $1^-$ diverge — média infinita, visível num relance. Um só objeto, todas as ferramentas do ano: um último capítulo à altura.

Observação 23.29 (Armadilhas comuns)

(i) As funções geradoras se aplicam apenas a variáveis com valores em $\N$ : para variáveis com sinal ou não inteiras, o objeto $\E(t^X)$ perde sua estrutura de série de potências (o terceiro ano o substitui por transformadas adaptadas a $\R$ ). (ii) A primeira verificação de bom senso de qualquer $G$ calculada é $G(1) = 1$ ; a segunda é que os coeficientes sejam não negativos — um coeficiente negativo significa um deslize algébrico, não uma lei nova. (iii) Em somas aleatórias, a ordem da composição importa: $G_S = G_N \circ G_X$ , sendo a função externa a que conta as parcelas; compor na outra ordem não faz sentido ( $G_X \circ G_N$ contaria itens de itens). (iv) A multiplicatividade exige independência e fontes distintas de aleatoriedade: $G_{2X}(t) = G_X(t^2)$ , e não $G_X(t)^2$ . (v) Derivar em $1$ é uma operação de bordo: quando o raio é exatamente $1$ , como no Exemplo 23.6, $G'(1^-)$ pode ser infinita, e a formulação por limite monótono do teorema dos momentos não é um preciosismo pedante, mas o enunciado honesto.

Encerrando o volume

A função geradora é um objeto final à altura deste livro: ela é simultaneamente uma série de potências (Capítulo 11), uma ferramenta de famílias somáveis (Capítulo 7), uma esperança (Capítulo 22), uma função convexa cuja geometria decide a extinção (Capítulo 8) e uma iteração de ponto fixo (Capítulo 4). A matemática do segundo ano é um só assunto. O volume do terceiro ano de graduação abrirá as portas deliberadamente deixadas fechadas aqui: a integração de Lebesgue (quitando o teorema da convergência dominada do Capítulo 9), a probabilidade em espaços não enumeráveis à luz da teoria da medida e a demonstração completa do teorema da função inversa (Capítulo 15) no contexto da geometria diferencial.

23.5 Exercícios

Exercício 23.1 ★

Calcule a função geradora da lei uniforme em $\{1, 2, \dots, 6\}$ (um dado honesto). Mostre que a soma de dois dados honestos não pode ser uniforme em $\{2, \dots, 12\}$ : fatore $G_{X+Y}$ e conte raízes. (Uma soma uniforme forçaria $G_X(t)G_Y(t) = \frac{t^2}{11}\sum_{k=0}^{10}t^k$ , cujas raízes não nulas são as raízes $11$ -ésimas da unidade distintas de $1$ — nenhuma delas real — enquanto $G_X/t$ e $G_Y/t$ são polinômios reais de grau $5$ , cada um com ao menos uma raiz real.)

Solução

Solução de Exercício 23.1.

Dado honesto: $G(t) = \frac16(t + t^2 + \dots + t^6) = \frac t6(1 + t + \dots + t^5)$ . Se a soma de dois dados honestos fosse uniforme em $\{2, \dots, 12\}$ , então

G(t)^2 = \frac{t^2}{36}\,h(t)^2 = \frac{t^2}{11}\sum_{k=0}^{10}t^k , \qquad h(t) = 1 + t + \dots + t^5 .

Ora, $h$ é um polinômio real de grau ímpar $5$ , de modo que tem raiz real (teorema do valor intermediário; concretamente $h(-1) = 0$ ), donde $h^2$ tem uma raiz real. Mas $\sum_{k=0}^{10}t^k$ não tem nenhuma: ele é positivo para $t \geq 0$ e, para $t < 0$ , vale $\frac{t^{11} - 1}{t - 1}$ , um quociente de dois números negativos. Contradição — a soma de dois dados honestos nunca é uniforme (como confirma a familiar distribuição triangular das somas de dados).

Exercício 23.2 ★

Usando funções geradoras, recupere $\E$ e $V$ para as leis binomial e geométrica (Teorema 23.7).

Solução

Solução de Exercício 23.2.

Binomial: $G(t) = (1 - p + pt)^n$ , $G'(t) = np(1 - p + pt)^{n-1}$ , $G''(t) = n(n-1)p^2(1 - p + pt)^{n-2}$ , logo

\E(X) = G'(1) = np, \qquad V(X) = G''(1) + G'(1) - G'(1)^2 = n(n-1)p^2 + np - n^2p^2 = np(1-p).

Geométrica ( $q = 1 - p$ ): $G(t) = \frac{pt}{1 - qt}$ , logo $G'(t) = \frac{p}{(1 - qt)^2}$ e $G''(t) = \frac{2pq}{(1 - qt)^3}$ ; em $t = 1$ (usando $1 - q = p$ ):

\E(X) = \frac{p}{p^2} = \frac1p, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{2q + p - 1}{p^2} = \frac{q}{p^2} ,

coincidindo com o Exercício 22.1 com menos trabalho.

Exercício 23.3 ★

Dois dados viciados: é possível viciar dois dados (independentemente, de modo idêntico ou não) para que sua soma seja uniforme em $\{2, \dots, 12\}$ ? (A mesma obstrução por fatoração do Exercício 23.1: a resposta é não mesmo com viciamentos diferentes, pois cada fator $G_X(t)/t$ tem grau ímpar $5$ , logo uma raiz real, enquanto o alvo não tem nenhuma.)

Solução

Solução de Exercício 23.3.

Não, nem mesmo com viciamentos diferentes. Suponha que $X, Y$ sejam leis em $\{1, \dots, 6\}$ de soma uniforme. Então $G_X(t) = t\,a(t)$ e $G_Y(t) = t\,b(t)$ com $a, b$ polinômios reais de grau no máximo $5$ — e seus graus devem somar $10$ (a soma atinge $12$ com probabilidade positiva), logo $\deg a = \deg b = 5$ , ambos ímpares. Como no Exercício 23.1,

a(t)\,b(t) = \frac{1}{11}\sum_{k=0}^{10}t^k

forçaria uma raiz real à esquerda (todo polinômio real de grau ímpar tem uma) e nenhuma à direita. Assim, nenhum viciamento de dois dados independentes — iguais ou não — produz soma uniforme.

Exercício 23.4 ★★

Sejam $X_1, X_2, \dots$ variáveis de Bernoulli $\mathcal{B}(p)$ independentes e $N \sim \mathcal{P}(\lambda)$ independente delas. Mostre, via o Teorema 23.17, que $S = X_1 + \dots + X_N \sim \mathcal{P}(\lambda p)$ : um número de Poisson de itens, cada um mantido com probabilidade $p$ , deixa um número de Poisson — o afinamento. Calcule também a lei da contagem descartada e admire: ela é $\mathcal{P}(\lambda(1-p))$ , e pode-se mostrar que é independente de $S$ .

Solução

Solução de Exercício 23.4.

Pelo Teorema 23.17 com $G_N(s) = e^{\lambda(s-1)}$ e $G_X(t) = 1 - p + pt$ :

G_S(t) = e^{\lambda(1 - p + pt - 1)} = e^{\lambda p(t - 1)} :

$S \sim \mathcal{P}(\lambda p)$ . A contagem descartada $D = N - S$ conta os mesmos itens mantidos com probabilidade $1 - p$ , de modo que, pelo mesmo cálculo, $D \sim \mathcal{P}(\lambda(1 - p))$ . Independência, diretamente: para $j, k \in \N$ ,

\begin{align*} \P(S = j,\ D = k) &= \P(N = j + k)\,\binom{j+k}{j}p^jq^k = e^{-\lambda}\frac{\lambda^{j+k}}{(j+k)!}\, \frac{(j+k)!}{j!\,k!}\,p^jq^k\\ &= \Bigl(e^{-\lambda p}\frac{(\lambda p)^j}{j!}\Bigr) \Bigl(e^{-\lambda q}\frac{(\lambda q)^k}{k!}\Bigr) \end{align*}

com $q = 1 - p$ : a lei conjunta se fatora como $\mathcal{P}(\lambda p) \otimes \mathcal{P}(\lambda q)$ . Um fluxo de Poisson dividido ao acaso dá fluxos de Poisson independentes — um pequeno milagre constantemente usado na teoria das filas.

Exercício 23.5 ★★

(Binomial negativa) Seja $T_r$ o número de lançamentos para obter $r$ caras (probabilidade de cara $p$ ). Escreva $T_r$ como soma de $r$ variáveis geométricas independentes, deduza

G_{T_r}(t) = \Bigl(\frac{pt}{1 - (1-p)t}\Bigr)^{r}, \qquad \E(T_r) = \frac rp, \qquad V(T_r) = \frac{r(1-p)}{p^2},

e desenvolva $G_{T_r}$ para achar $\P(T_r = n) = \binom{n-1}{r-1} p^r(1-p)^{n-r}$ .

Solução

Solução de Exercício 23.5.

Os tempos de espera entre caras consecutivas são variáveis geométricas $\mathcal{G}(p)$ independentes (ausência de memória: após cada cara o jogo recomeça), de modo que $T_r = W_1 + \dots + W_r$ e a multiplicatividade (Teorema 23.10) dá

G_{T_r}(t) = \Bigl(\frac{pt}{1 - qt}\Bigr)^{r}, \qquad \E(T_r) = r\,\E(W_1) = \frac rp, \qquad V(T_r) = r\,V(W_1) = \frac{rq}{p^2}

( $q = 1 - p$ ; as variâncias se somam por independência). Desenvolvimento: pela série binomial generalizada (Capítulo 11), $(1 - qt)^{-r} = \sum_{m\geq0} \binom{m + r - 1}{r - 1}q^mt^m$ , de modo que o coeficiente de $t^n$ em $p^rt^r(1 - qt)^{-r}$ é (com $m = n - r$ )

\P(T_r = n) = \binom{n-1}{r-1}p^r(1-p)^{n-r}, \qquad n \geq r ,

a lei binomial negativa — combinatoriamente: a $r$ -ésima cara cai no lançamento $n$ se e somente se as $r - 1$ caras anteriores escolhem seus lugares entre os $n - 1$ primeiros lançamentos.

Exercício 23.6 ★★

Para a lei de descendência $p_0 = \frac18$ , $p_1 = \frac38$ , $p_2 = \frac38$ , $p_3 = \frac18$ : calcule $m$ , decida a supercriticalidade e calcule exatamente a probabilidade de extinção $q$ . (Fatore a raiz $t = 1$ de $G(t) - t$ .)

Solução

Solução de Exercício 23.6.

$m = 1\cdot\frac38 + 2\cdot\frac38 + 3\cdot\frac18 = \frac{3 + 6 + 3}{8} = \frac32 > 1$ : supercrítico. A função geradora é

G(t) = \frac{1 + 3t + 3t^2 + t^3}{8} = \frac{(1 + t)^3}{8} ,

de modo que os pontos fixos resolvem $(1 + t)^3 = 8t$ , isto é, $t^3 + 3t^2 - 5t + 1 = 0$ . Fatorando a raiz garantida $t = 1$ :

t^3 + 3t^2 - 5t + 1 = (t - 1)\bigl(t^2 + 4t - 1\bigr),

e $t^2 + 4t - 1 = 0$ dá $t = -2 \pm \sqrt5$ . A raiz em $\intco{0}{1}$ é $\sqrt5 - 2 \approx 0.236$ : pelo Teorema 23.25,

q = \sqrt 5 - 2 .

(Uma verificação agradável: a lei de descendência é a de $3$ moedas honestas independentes, $Z_1 \sim \mathcal{B}(3, \frac12)$ .)

Exercício 23.7 ★★★

(Prole total) Num processo de ramificação subcrítico ( $m < 1$ ), seja $Y = \sum_{n\geq0} Z_n$ o número total de indivíduos jamais nascidos. Mostre que $\E(Y) = \sum_n m^n = \frac{1}{1 - m}$ (justifique a troca de somas) e demonstre que a função geradora $H = G_Y$ satisfaz a equação funcional $H(t) = t\,G(H(t))$ . (O ancestral, mais as proles totais de cada um de seus filhos, que são cópias independentes de $Y$ .)

Solução

Solução de Exercício 23.7.

Esperança. Primeiro $\E(Z_n) = m^n$ : pelo Teorema 23.17, $\E(Z_{n+1}) = \E(Z_n)\,m$ , e $\E(Z_0) = 1$ . A família $\bigl(Z_n(\omega)\P(\{\omega\}) \bigr)_{n, \omega}$ é não negativa, de modo que Fubini para famílias se aplica sem condições:

\E(Y) = \sum_{n=0}^{\infty}\E(Z_n) = \sum_{n=0}^\infty m^n = \frac{1}{1 - m} < \infty

(em particular, $Y$ é quase certamente finita: coerente com a extinção certa no caso subcrítico).

Equação funcional. Decomponha a população pelos filhos do ancestral: se o ancestral tem $Z_1 = k$ filhos, a prole total é $Y = 1 + Y_1 + \dots + Y_k$ , em que $Y_i$ é a prole total da linhagem do $i$ -ésimo filho — e as $Y_i$ são cópias independentes de $Y$ , independentes de $Z_1$ (linhagens distintas usam eventos de reprodução disjuntos e independentes). Condicionando a $Z_1$ como no Teorema 23.17:

H(t) = \E\bigl(t^Y\bigr) = t\sum_{k=0}^\infty \P(Z_1 = k)\,H(t)^k = t\,G\bigl(H(t)\bigr),

com o fator $t$ contabilizando o próprio ancestral. (Para a lei $p_0 = 1 - p$ , $p_2 = p$ da ramificação binária, essa equação quadrática em $H$ pode ser resolvida explicitamente e desenvolvida — os números de Catalan do Capítulo 11 contam as árvores genealógicas.)

Exercício 23.8 ★★★

Seja $X$ com função geradora $G$ de raio de convergência $> 1$ . Demonstre a cota exponencial de cauda: existem $C > 0$ e $\rho \in \intoo{0}{1}$ com $\P(X \geq n) \leq C\rho^n$ . (Markov aplicado a $t^X$ para um $t > 1$ fixo dentro do disco.) Reciprocamente, mostre que, se $\P(X \geq n) \leq C\rho^n$ com $\rho < 1$ , o raio de $G$ é $\geq 1/\rho > 1$ .

Solução

Solução de Exercício 23.8.

Seja $R > 1$ o raio e fixe $t \in \intoo{1}{R}$ . Então $\E(t^X) = G(t) < \infty$ , e a desigualdade de Markov (Teorema 22.15) aplicada à variável não negativa $t^X$ no nível $t^n$ :

\P(X \geq n) = \P\bigl(t^X \geq t^n\bigr) \leq \frac{G(t)}{t^n} = C\rho^n, \qquad C = G(t),\quad \rho = \frac1t \in \intoo{0}{1}.

Recíproca: se $\P(X \geq n) \leq C\rho^n$ , então $p_n \leq \P(X \geq n) \leq C\rho^n$ , de modo que, para $\abs t < \frac1\rho$ , a série $\sum p_n\abs t^n$ é dominada pela série geométrica convergente $C\sum(\rho\abs t)^n$ : o raio é ao menos $\frac1\rho > 1$ . O raio da função geradora e o decaimento geométrico da cauda são duas faces da mesma propriedade.

Exercício 23.9 ★★★

(Teorema de continuidade, caso elementar) Sejam $X, X_1, X_2, \dots$ variáveis com valores em $\N$ tais que $G_{X_n}(t) \to G_X(t)$ para todo $t \in \intco{0}{1}$ . Mostre que $\P(X_n = k) \to \P(X = k)$ para todo $k$ . (Indução em $k$ : para $k = 0$ tome $t \to 0$ — com cuidado: fixe $t$ pequeno, use $\abs{\P(X_n = 0) - G_{X_n}(t)} \leq \frac{t}{1-t}$ , válido pois a cauda $\sum_{j \geq 1}p_jt^j \leq \frac{t}{1 - t}$ ; depois diagonalize. Para o passo de indução, considere $\frac{G(t) - \P(X = 0)}{t}$ , a função geradora de uma lei deslocada.)

Solução

Solução de Exercício 23.9.

Escreva $p_k^{(n)} = \P(X_n = k)$ , $p_k = \P(X = k)$ .

Caso $k = 0$ . Para $t \in \intoo{0}{1}$ e qualquer lei $(q_j)$ com $\sum_j q_j \leq 1$ :

\Bigl|\,q_0 - \sum_j q_jt^j\Bigr| = \sum_{j \geq 1} q_j t^j \leq \sum_{j\geq1}t^j = \frac{t}{1 - t} .

Portanto

\abs{p_0^{(n)} - p_0} \leq \frac{2t}{1 - t} + \abs{G_{X_n}(t) - G_X(t)} .

Dado $\varepsilon > 0$ , escolha $t$ com $\frac{2t}{1-t} < \frac\varepsilon2$ e depois $n_0$ tal que o último termo seja $< \frac\varepsilon2$ para $n \geq n_0$ : logo $p_0^{(n)} \to p_0$ .

Passo de indução. Suponha $p_j^{(n)} \to p_j$ para $j < k$ . Considere as funções deslocadas

g_n(t) = \frac{G_{X_n}(t) - p^{(n)}_0}{t} = \sum_{j\geq0} p^{(n)}_{j+1}t^j, \qquad g(t) = \frac{G_X(t) - p_0}{t} ,

funções geradoras das sequências de subprobabilidade $(p^{(n)}_{j+1})_j$ (massa total $\leq 1$ , que é tudo o que o argumento de $k = 0$ usou). Para $t \in \intoo{0}{1}$ fixo, $g_n(t) \to g(t)$ por hipótese e pelo caso $k = 0$ . Aplicar o argumento de $k = 0$ a $g_n$ dá $p_1^{(n)} \to p_1$ ; iterar o deslocamento $k$ vezes dá $p_k^{(n)} \to p_k$ para todo $k$ . (Essa é a instância discreta e elementar do teorema da continuidade de Lévy, cuja forma geral — para funções características — é um marco do terceiro ano.)

Exercício 23.10 ★

(Truque da paridade) Mostre que, para uma variável $X$ com valores em $\N$ ,

\P(X \text{ par}) = \frac{1 + G_X(-1)}{2} ,

e calcule essa probabilidade para $X \sim \mathcal P(\lambda)$ e $X \sim \mathcal B(n, p)$ . O que significa $G_X(-1) \to 0$ probabilisticamente?

Solução

Solução de Exercício 23.10.

Pontualmente, $\frac{1 + (-1)^X}{2}$ vale $1$ quando $X$ é par e $0$ quando é ímpar, de modo que, tomando esperanças (transferência),

\P(X \text{ par}) = \frac{1 + \E\bigl((-1)^X\bigr)}2 = \frac{1 + G_X(-1)}2 .

Poisson: $\frac{1 + \eu^{-2\lambda}}2 \to \frac12$ quando $\lambda$ cresce. Binomial: $\frac{1 + (1 - 2p)^n}2$ . Nos dois casos, $G_X(-1) \to 0$ diz que a paridade de $X$ se torna uma moeda honesta: a lei se espalha por muitos inteiros e esquece sua paridade.

Exercício 23.11 ★★

(Dados de Sicherman) Verifique a fatoração da função geradora do dado honesto

\frac{t + t^2 + \dots + t^6}{6} = \frac{t\,(1 + t)(1 + t + t^2)(1 - t + t^2)}{6},

e mostre que os dois dados de faces $\{1, 2, 2, 3, 3, 4\}$ e $\{1, 3, 4, 5, 6, 8\}$ têm funções geradoras $\frac{t(1+t)(1+t+t^2)}6$ e $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6$ , cujo produto é o de dois dados padrão: esses dados exóticos produzem todo total $2, \dots, 12$ com exatamente as probabilidades padrão.

Solução

Solução de Exercício 23.11.

$t + \dots + t^6 = t\,\frac{1 - t^6}{1 - t}$ e $1 - t^6 = (1 - t)(1 + t)(1 + t + t^2)(1 - t + t^2)$ , o que dá a fatoração anunciada. Para o primeiro dado, $(1 + t)(1 + t + t^2) = 1 + 2t + 2t^2 + t^3$ , logo $\frac{t(1+t)(1+t+t^2)}6 = \frac{t + 2t^2 + 2t^3 + t^4}6$ : faces $\{1, 2, 2, 3, 3, 4\}$ . Para o segundo, desenvolvendo

(1 + 2t + 2t^2 + t^3)(1 - t + t^2)^2 = 1 + t^2 + t^3 + t^4 + t^5 + t^7,

logo $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6 = \frac{t + t^3 + t^4 + t^5 + t^6 + t^8}6$ : faces $\{1, 3, 4, 5, 6, 8\}$ . O produto das duas funções geradoras reagrupa os seis fatores em $\bigl(\frac{t(1+t)(1+t+t^2)(1-t+t^2)}6 \bigr)^2$ , o quadrado da função do dado padrão: o par de Sicherman tem exatamente a lei padrão para o total — as funções geradoras classificam todos esses reagrupamentos.

Exercício 23.12 ★★★

(Esperando duas caras seguidas) Uma moeda com probabilidade de cara $p$ é lançada até aparecerem duas caras consecutivas; seja $T$ o número de lançamentos (o jogo do Exercício 21.6). Condicionando aos primeiros lançamentos, deduza um sistema linear para as funções geradoras a partir dos estados “nenhuma cara corrente” e “uma cara corrente”, e conclua que

G_T(t) = \frac{p^2t^2}{1 - qt - pqt^2} \qquad (q = 1 - p);

verifique $G_T(1) = 1$ e $\E(T) = \dfrac{1 + p}{p^2}$ ( $= 6$ para uma moeda honesta).

Solução

Solução de Exercício 23.12.

Sejam $A$ e $B$ as funções geradoras da duração restante a partir de “nenhuma cara corrente” e de “uma cara corrente”. Gasta-se um lançamento e então: do estado $0$ , coroa retorna ao estado $0$ e cara move ao estado $1$ ; do estado $1$ , cara encerra o jogo e coroa retorna ao estado $0$ :

A(t) = t\bigl(q\,A(t) + p\,B(t)\bigr), \qquad B(t) = t\bigl(p + q\,A(t)\bigr).

Substituindo: $A(1 - qt) = pt\,B = pt(pt + qtA)$ , logo

G_T(t) = A(t) = \frac{p^2t^2}{1 - qt - pq\,t^2} .

Em $t = 1$ o denominador vale $1 - q - pq = p(1 - q) = p^2$ : $G_T(1) = 1$ , o jogo termina quase certamente (como o Exercício 21.6 mostrou por recursão). Derivação logarítmica em $1$ : $\E(T) = 2 - \frac{D'(1)}{D(1)}$ com $D(t) = 1 - qt - pqt^2$ , $D'(1) = -q - 2pq$ :

\E(T) = 2 + \frac{q + 2pq}{p^2} = \frac{2p^2 + q + 2pq}{p^2} = \frac{1 + p}{p^2},

que vale $6$ para $p = \frac12$ .

23.6 Problema: o processo de Galton–Watson, resolvido

Problema 23.1

Problema de fim de semana — taxas de crescimento, soluções exatas, prole total e a estimativa crítica de Kolmogorov

O critério de extinção (Teorema 23.25) separa os processos de ramificação em subcríticos, críticos e supercríticos — mas nada diz sobre taxas: quão rápido morre uma linhagem condenada, quão grande cresce uma sobrevivente. Este problema as calcula. Mantemos a notação do capítulo: lei de descendência $(p_k)$ com função geradora $G$ , média $m = G'(1)$ , tamanhos de geração $Z_n$ ( $Z_0 = 1$ ), iterados $G_n = G_{Z_n}$ , probabilidades de extinção $q_n = \P(Z_n = 0) \uparrow q$ ; supomos sempre $p_1 \neq 1$ e, onde aparecem momentos de segunda ordem, $G''(1) < \infty$ , e escrevemos $\sigma^2 = V(Z_1)$ .

Parte I — Momentos das gerações.

Mostre que $\E(Z_n) = m^n$ (regra da cadeia em $G_n = G \circ G_{n-1}$ em $1^-$ , usando $G_{n-1}(1) = 1$ e Teorema 23.7).
Estabeleça a recursão $G_n''(1) = G''(1)\,m^{2(n-1)} + m\,G_{n-1}''(1)$ e resolva-a: $G_n''(1) = G''(1)\,m^{n-1}\dfrac{m^n - 1}{m - 1}$ para $m \neq 1$ , e $G_n''(1) = n\,G''(1)$ para $m = 1$ .
Deduza

$V(Z_n) = \sigma^2m^{n-1}\,\frac{m^n - 1}{m - 1} \quad (m \neq 1), \qquad V(Z_n) = n\,\sigma^2 \quad (m = 1).$
(Taxa subcrítica, cota superior) Para $m < 1$ , mostre que $\P(Z_n > 0) \leq m^n$ (Markov na variável $Z_n$ com valores inteiros): a extinção é certa com uma taxa geométrica — um refinamento quantitativo do critério do capítulo.
(Taxa subcrítica, cota inferior) Usando Cauchy–Schwarz em $Z_n\mathbf 1_{Z_n > 0}$ , mostre que

$\P(Z_n > 0) \geq \frac{\E(Z_n)^2}{\E(Z_n^2)} \geq c\,m^{n} \quad\text{com}\quad c = \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1} :$

a taxa geométrica $m^n$ é exata a menos de constantes.

Parte II — A família geométrica, resolvida exatamente. Seja a lei de descendência geométrica em $\N$ : $p_k = qp^k$ ( $k \geq 0$ ), com $0 < p < 1$ , $q = 1 - p$ .

Calcule $G(t) = \dfrac{q}{1 - pt}$ e $m = \dfrac pq$ ; localize os três regimes em termos de $p$ .
Resolva $G(t) = t$ : mostre que os pontos fixos são $1$ e $q/p = 1/m$ , e recupere a probabilidade de extinção $q_{\mathrm{ext}} = \min(1, 1/m)$ .
Demonstre por indução as formas fechadas

$q_n = \frac{m^n - 1}{m^{n+1} - 1} \quad (m \neq 1), \qquad q_n = \frac{n}{n+1} \quad (m = 1).$
Deduza as taxas exatas: $1 - q_n \sim (1 - m)\,m^n$ no caso subcrítico, e $q_{\mathrm{ext}} - q_n \sim \dfrac{m - 1}{m^{2}}\cdot m^{-n}$ no caso supercrítico; verifique que a razão de contração supercrítica é $G'(q_{\mathrm{ext}}) = 1/m$ .
Caso crítico ( $p = \tfrac12$ ): calcule $\sigma^2 = 2$ e note que $1 - q_n = \frac1{n+1}$ : a sobrevivência decai como $\frac1n$ — nem geométrica nem somável.
Ainda no caso crítico: demonstre por indução o iterado completo

$G_n(t) = \frac{n - (n-1)t}{n + 1 - nt},$

e deduza que, condicionado à sobrevivência, $Z_n$ é geométrico em $\N^*$ de parâmetro $\frac1{n+1}$ :

$\P(Z_n = k \mid Z_n > 0) = \frac1{n+1} \Bigl(\frac{n}{n+1}\Bigr)^{k-1}, \qquad \E(Z_n \mid Z_n > 0) = n + 1 .$

A linhagem média morre, mas as linhagens sobreviventes têm tamanho da ordem de $n$ .

Parte III — Prole total. Seja $Y = \sum_{n\geq0}Z_n \in \N^* \cup \{\infty\}$ o número total de indivíduos jamais nascidos, e $H(t) = \sum_{k\geq1}\P(Y = k)t^k$ .

Justifique $\P(Y < \infty) = q_{\mathrm{ext}}$ e recorde do Exercício 23.7 a equação funcional $H(t) = t\,G(H(t))$ (cuja dedução não usou $m < 1$ ).
(Ramificação binária) Para $p_0 = p_2 = \frac12$ (crítico), resolva a equação funcional:

$H(t) = \frac{1 - \sqrt{1 - t^2}}{t},$

e desenvolva com Exemplo 11.21 para obter

$\P(Y = 2k + 1) = \frac{C_k}{2^{2k+1}}, \qquad C_k = \frac1{k+1}\binom{2k}k ;$

confira os valores $\P(Y = 1) = \frac12$ e $\P(Y = 3) = \frac18$ por contagem direta.
Derivando a equação funcional em $1^-$ , mostre que $\E(Y) = \frac{1}{1-m}$ para $m < 1$ , enquanto a criticalidade força $\E(Y) = \infty$ : a prole total crítica é finita quase certamente com média infinita.
Com a assintótica do binomial central (Exemplo 6.14), mostre que

$\P(Y = 2k+1) \sim \frac{1}{2\sqrt\pi\,k^{3/2}},$

uma cauda pesada em $k^{-3/2}$ , e deduza $\P(Y > n) \asymp n^{-1/2}$ (cotas superior e inferior dessa ordem bastam).
Compare com o passeio aleatório honesto (o problema de fim de semana do Capítulo 21): lá tempos de retorno certos mas de média infinita, aqui prole total certa mas de média infinita, ambos com leis locais em $n^{-3/2}$ . Um parágrafo sobre por que a criticalidade produz essa assinatura.

Parte IV — A estimativa de Kolmogorov na criticalidade. Suponha $m = 1$ , $0 < \sigma^2 = G''(1) < \infty$ .

Mostre que $G''$ se estende continuamente a $\intcc01$ (não negativa, crescente e com limite finito) e deduza o desenvolvimento de Taylor em $1$ :

$G(t) = t + b\,(1-t)^2 + o\bigl((1-t)^2\bigr), \qquad b = \frac{G''(1)}2 = \frac{\sigma^2}2 .$
Para $t \in \intco01$ , ponha $h(t) = \dfrac1{1 - G(t)} - \dfrac1{1 - t}$ . Mostre que

$h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)} \xrightarrow[t\to1^-]{} b .$
Telescope ao longo da iteração $q_{j+1} = G(q_j)$ :

$\frac1{1 - q_n} = 1 + \sum_{j=0}^{n-1}h(q_j),$

e conclua, com um argumento de Cesàro, que

$\P(Z_n > 0) = 1 - q_n \sim \frac{2}{\sigma^2\,n}$

— a estimativa de Kolmogorov: todo processo de ramificação crítico morre à taxa universal $1/n$ , com apenas a constante lembrando a lei de descendência.
Confira a estimativa contra o caso geométrico crítico da questão 10.
Deduza $\E(Z_n \mid Z_n > 0) = \dfrac{1}{1 - q_n} \sim \dfrac{\sigma^2 n}{2}$ (note que $\E(Z_n \mathbf 1_{Z_n>0}) = \E(Z_n) = 1$ ) e confira-a contra a questão 11: condicionada à sobrevivência, a população cresce linearmente — a corda bamba crítica entre a morte e a explosão.

Parte V — Aplicações e síntese.

(Epidemias, reações em cadeia) Para uma lei de descendência de Poisson $\mathcal P(\lambda)$ — cada caso infecta $\mathcal P(\lambda)$ novos casos — escreva a equação de extinção $q = \eu^{\lambda(q-1)}$ e resolva-a numericamente para $\lambda = 1.5$ ( $q \approx 0.417$ ) e $\lambda = 2$ ( $q \approx 0.203$ ): partindo de um único caso, um surto grande não é certo nem mesmo quando $\lambda > 1$ . Explique por que a iteração $q_{n+1} = \eu^{\lambda(q_n - 1)}$ a partir de $q_0 = 0$ converge para a raiz certa.
Partindo de $k$ ancestrais em vez de um, mostre que a probabilidade de extinção é $q^k$ . Aplicação: com $\lambda = 1.5$ , quantos casos iniciais tornam um surto ao menos $99\%$ provável?
(Condicionando um processo supercrítico à extinção) Para $m > 1$ com probabilidade de extinção $q \in \intoo01$ : demonstre primeiro, por convexidade, que $G'(q) < 1$ no menor ponto fixo, e deduza $q_{\mathrm{ext}} - q_n = O\bigl(G'(q)^n\bigr)$ (convergência geométrica, como exemplificou a questão 9). Mostre então que $\widehat G(t) = G(qt)/q$ é a função geradora de uma lei de descendência legítima, de média $\widehat m = G'(q) < 1$ : um processo companheiro subcrítico. Verifique na família geométrica: condicionar o processo supercrítico em $(p, q)$ à extinção troca $p$ e $q$ . (O enunciado completo — o processo condicionado é o processo companheiro — é demonstrado no volume do terceiro ano de graduação; aqui você verificou sua sombra em funções geradoras.)
Síntese: monte a tabela da tricotomia — para $m < 1$ , $m = 1$ , $m > 1$ : valor de $q$ ; taxa de $\P(Z_n > 0)$ ou de $q - q_n$ ; $\E(Y)$ ; tamanho de uma geração sobrevivente. Enuncie, em uma frase por ferramenta, como a composição de funções geradoras, a convexidade, Taylor em $1^-$ e a média de Cesàro carregaram todo o problema, e o que o volume do terceiro ano de graduação acrescenta (o martingal $Z_n/m^n$ e a lei limite exponencial de Yaglom).

Solução

Solução de Problema 23.1.

1. Para $t \in \intoo01$ , a regra da cadeia em $G_n = G \circ G_{n-1}$ dá $G_n'(t) = G'\bigl(G_{n-1}(t)\bigr)G_{n-1}'(t)$ . Quando $t \to 1^-$ , $G_{n-1}(t) \uparrow 1$ , e $G'$ é não decrescente com limite à esquerda $m$ em $1$ , de modo que o primeiro fator tende a $m$ ; por indução o segundo tende a $m^{n-1}$ . Pelo Teorema 23.7, $\E(Z_n) = G_n'(1^-) = m^n$ .

2. Derivando mais uma vez,

G_n'' = G''(G_{n-1})\,(G_{n-1}')^2 + G'(G_{n-1})\,G_{n-1}'',

e fazendo $t \to 1^-$ : $a_n = G''(1)m^{2(n-1)} + m\, a_{n-1}$ com $a_n = G_n''(1)$ , $a_1 = G''(1)$ . Para $m \neq 1$ verifica-se por indução que $a_n = G''(1)\,m^{n-1} \frac{m^n - 1}{m - 1}$ (a recursão acrescenta $G''(1)m^{2n-2}$ a $m\cdot G''(1)m^{n-2}\frac{m^{n-1}-1}{m-1}$ , e $m^{n-1} + \frac{m^{n-1}-1}{m-1} = \frac{m^n - 1}{m-1}$ ); para $m = 1$ , $a_n = a_{n-1} + G''(1) = n\,G''(1)$ .

3. $V(Z_n) = a_n + m^n - m^{2n}$ e $G''(1) = \sigma^2 + m^2 - m$ . Para $m \neq 1$ , a parcela $(m^2 - m)m^{n-1}\frac{m^n-1}{m-1} = m^n(m^n - 1)$ cancela $m^n - m^{2n}$ exatamente, deixando $V(Z_n) = \sigma^2m^{n-1}\frac{m^n-1}{m-1}$ . Para $m = 1$ : $V(Z_n) = nG''(1) = n\sigma^2$ .

4. $Z_n$ é uma variável inteira não negativa, de modo que $\P(Z_n > 0) = \P(Z_n \geq 1) \leq \E(Z_n) = m^n$ por Markov (Teorema 22.15). Para $m < 1$ isso decai geometricamente — e de modo somável, de sorte que Borel–Cantelli dá até que apenas finitas gerações são não vazias, o que é de novo a extinção.

5. Cauchy–Schwarz: $\E(Z_n)^2 = \E(Z_n\mathbf 1_{Z_n>0})^2 \leq \E(Z_n^2)\,\P(Z_n > 0)$ . Com a questão 3 e $m < 1$ :

\E(Z_n^2) = V(Z_n) + m^{2n} \leq \frac{\sigma^2m^{n-1}}{1-m} + m^{2n},

de modo que, dividindo $m^{2n}$ por essa cota e simplificando por $m^n$ ,

\P(Z_n > 0) \geq \frac{m^n}{\frac{\sigma^2}{m(1-m)} + m^n} \geq \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1}m^n ,

usando $m^n \leq 1$ no denominador. Com a questão 4: $\P(Z_n > 0) \asymp m^n$ .

6. $G(t) = q\sum_k(pt)^k = \frac{q}{1 - pt}$ , e $m = G'(1) = \frac{pq}{(1-p)^2} = \frac pq$ . Subcrítico para $p < \frac12$ , crítico para $p = \frac12$ , supercrítico para $p > \frac12$ .

7. $G(t) = t$ se lê $pt^2 - t + q = 0$ , com raízes $\frac{1 \pm \abs{p - q}}{2p}$ , isto é, $1$ e $\frac qp = \frac1m$ . A probabilidade de extinção é o menor ponto fixo em $\intcc01$ (Teorema 23.25): $q_{\mathrm{ext}} = 1$ se $m \leq 1$ , e $\frac1m$ se $m > 1$ .

8. Para $m \neq 1$ , com $p = \frac m{m+1}$ , $q = \frac1{m+1}$ : se $q_n = \frac{m^n - 1}{m^{n+1} - 1}$ , então

1 - p\,q_n = \frac{(m+1)(m^{n+1} - 1) - m(m^n - 1)} {(m+1)(m^{n+1} - 1)} = \frac{m^{n+2} - 1}{(m+1)(m^{n+1} - 1)},

logo $q_{n+1} = \frac{q}{1 - pq_n} = \frac{m^{n+1} - 1}{m^{n+2} - 1}$ ; o caso base $q_0 = 0$ vale. Para $m = 1$ : $G(t) = \frac1{2 - t}$ e $q_{n+1} = \frac1{2 - \frac{n}{n+1}} = \frac{n+1}{n+2}$ , com $q_0 = 0$ .

9. $1 - q_n = \frac{m^n(m - 1)}{m^{n+1} - 1}$ . Para $m < 1$ o denominador tende a $-1$ : $1 - q_n \sim (1 - m)\,m^n$ . Para $m > 1$ :

q_{\mathrm{ext}} - q_n = \frac1m - \frac{m^n - 1}{m^{n+1} - 1} = \frac{m - 1}{m\,(m^{n+1} - 1)} \sim \frac{m - 1}{m^{2}}\;m^{-n} .

E $G'(t) = \frac{pq}{(1 - pt)^2}$ avaliada em $t = \frac qp$ (em que $1 - pt = 1 - q = p$ ) dá $G'(q_{\mathrm{ext}}) = \frac qp = \frac1m$ : a razão observada $m^{-1}$ é exatamente a derivada no ponto fixo atrator.

10. Para $p = \frac12$ : $G''(t) = \frac{1/4}{(1 - t/2)^3}$ , logo $G''(1) = 2$ e $\sigma^2 = G''(1) + m - m^2 = 2$ . A forma fechada dá $1 - q_n = \frac1{n+1}$ : a probabilidade de sobrevivência decai como $1/n$ — lentamente demais para ser somável, ao contrário de qualquer taxa subcrítica.

11. Indução: $G_1(t) = \frac1{2-t}$ coincide com a fórmula para $n = 1$ , e

G(G_n(t)) = \cfrac{1}{2 - \cfrac{n - (n-1)t}{n+1 - nt}} = \frac{n + 1 - nt}{2(n+1) - 2nt - n + (n-1)t} = \frac{n+1 - nt}{n + 2 - (n+1)t} .

Então

\frac{G_n(t) - q_n}{1 - q_n} = (n+1)\,\Bigl(\frac{n - (n-1)t}{n+1 - nt} - \frac{n}{n+1}\Bigr) = \frac{t}{n + 1 - nt} = \frac{\frac{t}{n+1}}{1 - \frac{n}{n+1}t} ,

a função geradora da lei geométrica $\mathcal G\bigl(\frac1{n+1} \bigr)$ em $\N^*$ (Exemplo 23.4): dada a sobrevivência, $\P(Z_n = k \mid Z_n > 0) = \frac1{n+1}\bigl(\frac n{n+1}\bigr)^{k-1}$ , com média condicional $n + 1$ . A média incondicional $1 = \E(Z_n)$ é o produto de uma probabilidade de sobrevivência que se anula por um tamanho condicional que cresce linearmente.

12. Se a linhagem se extingue na geração $n$ , então $Y = Z_0 + \dots + Z_{n-1}$ é finita; se ela nunca se extingue, $Y \geq \sum_n 1 = \infty$ . Assim, $\{Y < \infty\}$ é o evento de extinção e $\P(Y < \infty) = q_{\mathrm{ext}}$ . A dedução de $H(t) = tG(H(t))$ no Exercício 23.7 — o ancestral contribui com o fator $t$ , seus filhos fundam cópias independentes de $Y$ contadas por $G$ — usou apenas Teorema 23.17, válido em todo regime.

13. Com $G(s) = \frac{1 + s^2}2$ a equação se lê $tH^2 - 2H + t = 0$ , logo $H = \frac{1 - \sqrt{1 - t^2}}{t}$ (a raiz com $H(0) = 0$ ). Comparando com a série de Catalan $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ (Exemplo 11.21): $H(t) = \frac t2\,C\bigl(\frac{t^2}4\bigr) = \sum_{k\geq0}C_k\,\frac{t^{2k+1}}{2^{2k+1}}$ , isto é, $\P(Y = 2k+1) = C_k2^{-2k-1}$ . Verificações: $\P(Y = 1) = C_0/2 = \frac12$ (o ancestral não tem filho); $\P(Y = 3) = C_1/8 = \frac18$ (dois filhos, ambos sem filhos: $\frac12\cdot\frac12\cdot \frac12$ ).

14. Derivando $H = tG(H)$ em $\intoo01$ e fazendo $t \to 1^-$ (limites monótonos como no Teorema 23.7): $H'(1)\bigl(1 - G'(H(1))\bigr) = G(H(1))$ . No caso subcrítico, $H(1) = 1$ e $\E(Y) = H'(1) = \frac1{1 - m}$ . No caso crítico, $G'(1) = 1$ faz o fator da esquerda se anular enquanto o membro da direita é $1$ : nenhum $H'(1)$ finito pode existir, logo $\E(Y) = \infty$ — e no entanto $\P(Y < \infty) = q = 1$ .

15. $C_k = \frac1{k+1}\binom{2k}k \sim \frac{4^k}{\sqrt\pi\,k^{3/2}}$ pelo Exemplo 6.14, logo

\P(Y = 2k+1) = \frac{C_k}{2\cdot4^{k}} \sim \frac1{2\sqrt\pi\,k^{3/2}} .

Somando a cauda (comparação com $\int_K^\infty k^{-3/2}\dd k = 2K^{-1/2}$ , por cima e por baixo): $\P(Y > 2K) \asymp K^{-1/2}$ , isto é, $\P(Y > n) \asymp n^{-1/2}$ — uma cauda pesada de média infinita, quantificando a questão 14.

16. Ambos os objetos críticos — o tempo de retorno do passeio honesto (o problema de fim de semana do Capítulo 21) e a prole total crítica — são quase certamente finitos com média infinita, com leis locais de expoente $-3/2$ e caudas de expoente $-1/2$ . Isso não é coincidência: explorar uma árvore genealógica filho a filho produz um caminho $\pm1$ (um passo para cima por nascimento, um para baixo por morte) que é exatamente um passeio honesto, e $Y$ se torna um tempo de primeira passagem. Criticalidade significa deriva nula: o processo está sempre à beira tanto da extinção quanto da explosão, e as flutuações na escala $\sqrt{}$ da aleatoriedade sem deriva produzem precisamente esses expoentes.

17. $G''(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ tem termos não negativos, de modo que é não decrescente em $\intco01$ com limite finito $G''(1) = \sigma^2$ (a criticalidade faz $\E Z_1(Z_1 - 1) = \sigma^2$ ); uma função não decrescente com limite igual ao valor de bordo é contínua em $1$ . Taylor com resto integral no ponto $1$ :

G(t) = 1 + (t - 1) + \int_1^t(t - s)G''(s)\,\dd s = t + \frac{G''(1)}2(1-t)^2 + o\bigl((1-t)^2\bigr),

pois $G''(s) = G''(1) + o(1)$ quando $s \to 1^-$ .

18. Reduzindo ao denominador comum, $h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)}$ . Pela questão 17, o numerador vale $b(1-t)^2 + o((1-t)^2)$ e $1 - G(t) = (1 - t)\bigl(1 - b(1-t) + o(1-t)\bigr)$ , logo $h(t) \to b$ .

19. Pela definição de $h$ em $t = q_j$ e $G(q_j) = q_{j+1}$ : $\frac1{1 - q_{j+1}} - \frac1{1-q_j} = h(q_j)$ ; somar a partir de $j = 0$ ( $q_0 = 0$ ) dá o resultado exibido. Como o processo crítico se extingue, $q_j \uparrow 1$ , logo $h(q_j) \to b$ e a média de Cesàro $\frac1n\sum_{j<n}h(q_j) \to b$ : $\frac1{1-q_n} \sim bn$ , isto é,

\P(Z_n > 0) \sim \frac1{bn} = \frac{2}{\sigma^2 n} .

20. Caso geométrico crítico: $\sigma^2 = 2$ (questão 10), de modo que Kolmogorov prevê $1 - q_n \sim \frac1n$ — e o valor exato é $\frac1{n+1}$ .

21. Como $Z_n\mathbf 1_{Z_n > 0} = Z_n$ , $\E(Z_n \mid Z_n > 0) = \frac{\E(Z_n)}{\P(Z_n > 0)} = \frac1{1 - q_n} \sim \frac{\sigma^2n}2$ . No caso geométrico isso vale $n + 1$ , coincidindo exatamente com a questão 11 ( $\sigma^2 = 2$ ). O retrato crítico: a extinção é certa, o tamanho médio fica congelado em $1$ , e as raras linhagens sobreviventes têm tamanho crescendo linearmente — cada fator equilibrando o outro.

22. Para descendência $\mathcal P(\lambda)$ , $G(t) = \eu^{\lambda(t-1)}$ e a probabilidade de extinção é a menor raiz de $q = \eu^{\lambda(q-1)}$ . Numericamente: $\lambda = 1.5$ dá $q \approx 0.417$ (itere $q \mapsto \eu^{1.5(q-1)}$ : $0, 0.223, 0.312, 0.356, \dots \to 0.4172$ ); $\lambda = 2$ dá $q \approx 0.203$ . Assim, um caso índice desencadeia um surto grande com probabilidade $58\%$ ( $\lambda = 1.5$ ) ou $80\%$ ( $\lambda = 2$ ) — provável, não certo. A iteração a partir de $q_0 = 0$ converge à menor raiz porque $G$ é não decrescente: por indução $q_n \leq r$ para qualquer ponto fixo $r$ , e $(q_n)$ cresce (ela é $\P(Z_n = 0)$ ), de modo que seu limite é um ponto fixo abaixo de todos os outros.

23. Os $k$ ancestrais fundam árvores genealógicas independentes, e a extinção total é a interseção de $k$ eventos de extinção independentes: probabilidade $q^k$ . Para $\lambda = 1.5$ : uma probabilidade de surto $1 - q^k \geq 0.99$ exige $q^k \leq 0.01$ , isto é, $k \geq \frac{\ln 0.01}{\ln 0.417} \approx 5.3$ : seis casos iniciais tornam o surto $99\%$ certo.

24. $G'(q) < 1$ : $G - \mathrm{id}$ é convexa e se anula em $q$ e $1$ , de modo que é $\leq 0$ em $\intcc q1$ ; se $G'(q) = 1$ , a tangente em $q$ (que a convexidade coloca abaixo de $G$ ) forçaria $G(t) \geq t$ em $\intcc q1$ , portanto $G \equiv \mathrm{id}$ ali, matando todos os coeficientes $p_n$ ( $n \geq 2$ ) e contradizendo $m > 1$ . Convergência geométrica: $q_n < q$ para todo $n$ (indução, $G$ crescente), e o teorema do valor médio dá $q - q_{n+1} = G'(c_n)(q - q_n)$ com $c_n \in \intoo{q_n}q$ , de modo que $G'(c_n) \leq G'(q) < 1$ e $q - q_n \leq q\,G'(q)^n$ . Processo companheiro: $\widehat G(t) = G(qt)/q = \sum_kp_kq^{k-1}t^k$ tem coeficientes não negativos e $\widehat G(1) = G(q)/q = 1$ : uma função geradora; sua média é $\widehat G'(1) = G'(q) < 1$ : subcrítica. Família geométrica: $G(t) = \frac{q}{1-pt}$ , $q_{\mathrm{ext}} = \frac qp$ , e

\widehat G(t) = \frac pq\cdot\frac{q}{1 - p\frac qp t} = \frac{p}{1 - qt} :

a lei de descendência geométrica com $p$ e $q$ trocados — o processo supercrítico visto sobre seu evento de extinção é o subcrítico espelhado.

25. A tabela: $m < 1$ : $q = 1$ , $\P(Z_n > 0) \asymp m^n$ (questões 4–5), $\E(Y) = \frac1{1-m}$ , gerações sobreviventes de média condicional limitada. $m = 1$ : $q = 1$ , $\P(Z_n > 0) \sim \frac2{\sigma^2n}$ (Kolmogorov), $\E(Y) = \infty$ com $\P(Y > n) \asymp n^{-1/2}$ , sobreviventes de tamanho $\sim \frac{\sigma^2n}2$ . $m > 1$ : $q < 1$ é o menor ponto fixo, $q - q_n = O(G'(q)^n)$ , crescimento $\E(Z_n) = m^n$ e, condicionado a morrer, o processo é o companheiro subcrítico (questão 24). As ferramentas: a composição de funções geradoras transformou a recursão populacional em iteração de funções; a convexidade fixou a geometria dos pontos fixos; Taylor em $1^-$ converteu hipóteses de momentos em desenvolvimentos locais; e a média de Cesàro extraiu o $1/n$ de Kolmogorov de uma soma telescópica. O volume do terceiro ano de graduação acrescenta o martingal $Z_n/ m^n$ — cujo limite quase certo refina $\E(Z_n) = m^n$ numa taxa de crescimento trajetória a trajetória — e o teorema de Yaglom, a lei limite por trás da geometria condicional observada na questão 11.

Termos definidos neste capítulo

Função geradora de probabilidade

Ver todos os 395 termos do glossário