Percolação em árvores
4.1 Processo de Galton–Watson
O processo de Galton–Watson surgiu do problema da sobrevivência de sobrenomes ao longo das gerações, estudado por Francis Galton e Henry William Watson no século XIX. Nesse modelo, cada indivíduo produz, independentemente dos demais, um número aleatório de descendentes segundo uma distribuição fixa.
Partimos de um único indivíduo, que constitui a geração inicial. Seus filhos formam a primeira geração; os filhos destes, a segunda, e assim sucessivamente. A repetição da mesma regra de descendência produz uma árvore genealógica aleatória.
Em vez de acompanhar toda a árvore, consideramos o tamanho da população em cada geração. Isso permite estudar a probabilidade de extinção: sob a hipótese não degenerada usual, a população se extingue quase certamente quando o número médio de descendentes por indivíduo é menor ou igual a 1; quando essa média é maior que 1, a sobrevivência tem probabilidade positiva.
Na percolação em árvores, a exploração da componente aberta pode ser descrita por esse processo de ramificação. O critério de extinção fornecerá, assim, o parâmetro crítico.
Seja \( \mu \) uma distribuição em \( \mathbb {N} \), ou seja, \( \mu : \mathbb {N} \to [0,1] \) tal que \( \sum _{n} \mu (n) = 1 \). O processo de Galton–Watson com distribuição de descendência \( \mu \), também denotado por \( \mathrm{GW}_{\mu } \), é a seguinte cadeia de Markov \( (Z_{n})_{n} \) sobre \( \mathbb {N} \):
Seja \( (X_{j,k})_{j,k\in \mathbb {N}} \) uma família de variáveis aleatórias i.i.d. com distribuição \(\mu \).
Na geração \(n=0\), definimos \(Z_0=1\), isto é, iniciamos com um único indivíduo.
Dado \( Z_{n} \), definimos:
\[ Z_{n+1} := \sum _{k=1}^{Z_{n}} X_{n+1, k} \]onde \( X_{n+1, k} \) representa o número de descendentes do \( k \)-ésimo indivíduo na geração \( n \).
Escrevemos ainda \(p_k=\mu (k)\), \(k\geq 0\), para a probabilidade de um indivíduo ter exatamente \(k\) descendentes.
Critério de extinção
Seja \(m\) o número médio de descendentes por indivíduo,
e seja \(q\) a probabilidade de extinção. O comportamento do processo depende de \(m\) e do caso degenerado \(p_1=1\):
Se \( m \lt 1 \), então \( q = 1 \), ou seja, a extinção ocorre quase certamente.
Se \( m \gt 1 \), então \( q \lt 1\).
Se \(m=1\) e \(p_1\neq 1\), então \(q=1\).
Considere a função geradora da distribuição de descendência,
Seja
Como o estado \(0\) é absorvente, \(q_n\) é também a probabilidade de o processo ter se extinguido até a geração \(n\). Condicionando no número \(k\) de descendentes do indivíduo inicial, a extinção até a geração \(n+1\) ocorre exatamente quando cada uma das \(k\) linhagens se extingue até a geração \(n\). Pela independência das linhagens,
Assim, \((q_n)_n\) é crescente e converge para a probabilidade de extinção \(q\). Pela continuidade de \(f\),
Além disso, se \(s\in [0,1]\) satisfaz \(f(s)=s\), então
Por indução, \(q_n\le s\) para todo \(n\); logo \(q\le s\). Portanto, \(q\) é o menor ponto fixo de \(f\) em \([0,1]\).
A função \(f\) é convexa, satisfaz \(f(1)=1\) e
(com o valor \(+\infty \) permitido). Se \(m\lt 1\), a convexidade fornece, para \(0\le s\lt 1\),
Como \(s-1\lt 0\) e \(m\lt 1\),
Logo \(f(s)\gt s\) para todo \(s\lt 1\), o único ponto fixo é \(1\) e \(q=1\).
Se \(m=1\), a convexidade fornece \(f(s)\ge s\) em \([0,1]\). Se houvesse igualdade em algum \(s\lt 1\), a convexidade e a igualdade também em \(1\) forçariam \(f\) a coincidir com a reta identidade em todo o intervalo \([s,1]\) e, por analiticidade em \((0,1)\), em todo \((0,1)\); isso equivale ao caso degenerado \(p_1=1\). Portanto, quando \(p_1\neq 1\), temos novamente \(f(s)\gt s\) para todo \(s\lt 1\) e, assim, \(q=1\).
Finalmente, suponha \(m\gt 1\). Então, para \(s\lt 1\) suficientemente próximo de \(1\),
Como \(f(0)=p_0\ge 0\), a continuidade fornece um ponto fixo em \([0,1)\); se \(p_0=0\), o próprio \(0\) já é ponto fixo. Como \(q\) é o menor ponto fixo, segue que \(q\lt 1\).
O processo de Galton–Watson também é usado em biologia populacional e epidemiologia. Para a percolação, o exemplo binomial permite descrever a componente aberta em árvores regulares.
4.2 Percolação em árvores regulares
Considere \(d\ge 3\) e seja \(\mathbb T_d\) a árvore infinita \(d\)-regular: todo vértice possui exatamente \(d\) vizinhos. Fixe uma raiz \(o\). A escolha da raiz não altera o grafo; ela serve apenas para orientar as arestas em direção ao infinito.
Se \(x_1,\dots ,x_d\) são os vizinhos de \(o\), a remoção de \(o\) decompõe \(\mathbb T_d\) em \(d\) subárvores disjuntas \(T_1,\dots ,T_d\), onde \(T_j\) contém \(x_j\). Vista como árvore enraizada em \(x_j\), cada \(T_j\) possui exatamente \(d-1\) filhos por vértice.
É preciso distinguir a raiz dos demais vértices: a componente de \(o\) na árvore \(d\)-regular não é, desde a geração inicial, um processo de Galton–Watson homogêneo com distribuição \(\operatorname {Bin}(d-1,p)\), pois a raiz possui \(d\) vizinhos. Em cada ramo \(T_j\), porém, o processo de descendência é Galton–Watson com essa distribuição.
Cada vértice de \(T_j\) possui \(d-1\) vizinhos mais distantes de \(o\). As arestas que ligam um vértice a esses descendentes são independentes e abertas com probabilidade \(p\). Assim, o número de descendentes abertos de cada indivíduo tem distribuição \(\operatorname {Bin}(d-1,p)\), independentemente dos demais. Ramos distintos usam conjuntos disjuntos de arestas, o que fornece a independência.
Em cada ramo \(T_j\), a sobrevivência além de \(x_j\) é governada por um processo de Galton–Watson com média
Se \(p\le 1/(d-1)\), esse processo se extingue quase certamente. Como há apenas \(d\) ramos,
Logo
Se \(p\gt 1/(d-1)\), o processo de Galton–Watson em cada ramo sobrevive com probabilidade positiva. A aresta \(\{ o,x_j\} \) está aberta com probabilidade \(p\gt 0\), independentemente da configuração no restante de \(T_j\). Portanto, para qualquer \(j\),
o que implica \(\theta _{\mathbb T_d,o}(p)\gt 0\). Assim
No ponto crítico \(p=1/(d-1)\), a média do processo é \(1\) e a distribuição \(\operatorname {Bin}(d-1,p)\) não é degenerada em \(1\) para \(d\ge 3\). Pelo critério de extinção de Galton–Watson, todos os ramos se extinguem quase certamente; portanto \(\theta _{\mathbb T_d,o}(p_c)=0\).
Por transitividade de \(\mathbb T_d\), todo vértice tem a mesma probabilidade de pertencer a uma componente infinita; no ponto crítico essa probabilidade é zero. Como \(\mathbb T_d\) é enumerável, a probabilidade de existir alguma componente infinita é no máximo a soma, sobre os vértices, dessas probabilidades, e portanto é zero.