Asymptotic normality for general subtree counts in conditioned Galton--Watson trees

O artigo demonstra que, sob uma condição de momento moderada, o número de ocorrências de uma árvore enraizada fixa como subárvore geral em árvores de Galton-Watson condicionadas a ter $n$ nós converge para uma distribuição normal assintótica com média e variância lineares em $n$, confirmando uma conjectura de Janson e estabelecendo que a violação dessa condição de momento pode invalidar o resultado.

O essencial

Imagine que você tem um árvore genealógica gigante, mas em vez de pessoas, ela é feita de "nós" (pontos) e "ramos". Essa árvore cresce de uma maneira muito específica e aleatória, como se fosse um jogo de dados onde cada nó decide quantos filhos terá.

Os autores deste artigo, Fameno e Dimbinaina, estão interessados em uma pergunta específica: Se pegarmos uma dessas árvores gigantes que tem exatamente $n$ nós, quantas vezes um pequeno desenho de árvore específico (vamos chamar de "padrão") aparece dentro dela?

Aqui está uma explicação simples do que eles descobriram, usando analogias do dia a dia:

1. O Cenário: A Árvore que Cresce Sozinha

Pense em uma árvore que cresce seguindo regras aleatórias. A regra principal é que, em média, cada "nó" tem exatamente 1 filho. Isso significa que a árvore não cresce para o infinito nem morre imediatamente; ela fica em um equilíbrio delicado.

Os autores olham para uma versão "condicionada" dessa árvore: eles só olham para as árvores que, por sorte, pararam de crescer exatamente quando atingiram um tamanho gigante ($n$ nós).

2. O Problema: Contando Padrões Escondidos

Dentro dessa grande árvore, você pode procurar por um pequeno desenho específico.

• Exemplo: Imagine que o seu "padrão" é um pequeno galho com 3 folhas.
• A pergunta: Quantas vezes esse galho de 3 folhas aparece espalhado por toda a árvore gigante?

O artigo prova que, se a árvore for grande o suficiente, o número de vezes que esse padrão aparece segue uma curva de sino perfeita (o que os matemáticos chamam de "distribuição normal").

3. A Analogia da "Sopa de Pedras"

Imagine que você está cozinhando uma sopa gigante (a árvore $T_n$). Você quer saber quantas batatas (o padrão $t$) existem na sopa.

• A Média: Se você fizer essa sopa muitas vezes, o número de batatas será sempre proporcional ao tamanho da panela. Se a panela dobra de tamanho, o número de batatas também dobra. Isso é o que eles chamam de "média linear".
• A Variação (O "Barulho"): Nem sempre o número será exatamente o dobro. Às vezes sai um pouco mais, às vezes um pouco menos. O artigo prova que essas pequenas variações, quando você olha para panelas gigantes, se organizam de forma previsível e suave (a curva de sino).

4. A Regra de Ouro: O "Limite de Peso"

Para que essa "curva de sino" funcione perfeitamente, existe uma condição importante sobre como a árvore cresce.

• A Regra: A árvore não pode ter "nós" que geram muitos filhos de uma vez de forma muito extrema e rara.
• A Analogia: Pense em uma festa. Se a maioria das pessoas traz apenas 1 ou 2 amigos, a festa é equilibrada. Mas, se de repente uma pessoa traz 1.000 amigos, isso distorce tudo.
• O que os autores dizem: Eles mostram que, desde que a probabilidade de alguém trazer uma quantidade enorme de amigos não seja tão alta (uma condição matemática chamada "momento"), a contagem dos padrões será estável e previsível. Se essa regra for quebrada (se houver "gigantes" muito raros), a contagem fica caótica e a curva de sino desaparece.

5. Quando a Regra Quebra? (Os Casos Especiais)

O artigo também investiga quando essa previsibilidade falha.

• O Caso "Caminho": Imagine que o seu padrão é apenas uma linha reta de nós (um "caminho"). Se a árvore tiver alguns nós que geram muitos filhos, o número de "caminhos" pode variar de forma estranha, sem seguir a curva de sino.
• O Caso "Estrela": Se o seu padrão é uma estrela (um centro com muitos raios), e a árvore permite que alguns nós tenham um número absurdo de filhos, a variação no número de estrelas pode explodir, tornando impossível prever o resultado com uma curva de sino.

6. A Conclusão Principal

Os autores confirmaram uma aposta (conjectura) feita por outro matemático famoso, Svante Janson.

• O Veredito: Em quase todos os casos normais, se você contar quantas vezes um desenho pequeno aparece em uma árvore aleatória gigante, o resultado será previsível e segue uma curva de sino.
• A Exceção: Isso só não acontece se a árvore permitir "monstros" (nós com muitos filhos) que são tão raros que, quando aparecem, bagunçam toda a estatística.

Resumo em uma frase

O artigo diz que, desde que a árvore não tenha "nós" que geram filhos de forma extremamente caótica, contar quantas vezes um pequeno desenho aparece dentro dela é como contar grãos de areia numa praia: o número total é previsível e segue uma regra matemática elegante, mesmo que a árvore tenha crescido de forma aleatória.

Resumo técnico

Resumo Técnico: Normalidade Assintótica para Contagens de Subárvores Gerais em Árvores Galton-Watson Condicionadas

1. O Problema e o Contexto

O artigo investiga o comportamento assintótico da contagem de ocorrências de uma árvore enraizada e ordenada fixa $t$ (denotada por $N_t(T_n)$) dentro de uma árvore Galton-Watson condicionada $T_n$ que possui exatamente $n$ nós.

• Definição de Subárvore Geral: Diferente das "subárvores de borda" (fringe subtrees), que são induzidas por um nó e todos os seus descendentes, uma "subárvore geral" é definida por uma incorporação (embedding) onde a raiz de $t$ mapeia para o nó mais alto de sua imagem em $T_n$, e o grau de cada nó na imagem é maior ou igual ao grau correspondente em $t$.
• Modelo Probabilístico: $T_n$ é derivada de um processo Galton-Watson com distribuição de descendência $\xi$ crítica ($E[\xi]=1$), que pode extinguir-se ($P(\xi=0)>0$) e satisfaz condições de aperiodicidade.
• Objetivo: Estabelecer se a variável aleatória $N_t(T_n)$ segue uma distribuição normal assintótica quando $n \to \infty$, e determinar as condições de momento sobre $\xi$ necessárias para que isso ocorra.

2. Metodologia

Os autores empregam uma combinação de técnicas de análise combinatória de árvores, teoria de probabilidade e estimativas de momentos. A abordagem principal baseia-se em:

• Propriedade Aditiva: O funcional $N_t(T)$ satisfaz uma propriedade aditiva: $N_t(T) = \sum N_t(T_k) + n_t(T)$, onde $T_k$ são as subárvores filhas da raiz e $n_t(T)$ é a função de "pedágio" (toll function) que conta as ocorrências ancoradas na raiz.
• Argumento de Truncamento (Truncation Argument): A prova do Teorema Central do Limite (TCL) utiliza um método clássico baseado na convergência em $L^2$. A ideia é aproximar o funcional original $N_t$ por funcionais truncados $F_{1,p}$ (que consideram apenas subárvores de tamanho limitado) e mostrar que o erro de aproximação tem variância que tende a zero.
• Árvore de Kesten (Size-Biased Tree): Utiliza-se a árvore infinita $\hat{T}$ (árvore de Kesten) para analisar o comportamento local das árvores condicionadas. A distribuição de $\hat{T}$ é definida localmente por $P(\hat{T}^{(M)} = T) = w_M(T)P(T^{(M)} = T)$, onde $w_M(T)$ é o número de nós na distância $M$ da raiz.
• Lemas de Estimativa de Momentos: O coração da prova técnica reside na demonstração de lemas que garantem a finitude de certos momentos condicionados. Especificamente, provam-se limites para $E(n_t(T_n) \mid |T_n|)$ e $E(n_t(T_n)n_{t'}(T_n))$ sob condições de momento específicas de $\xi$.

3. Contribuições Principais e Resultados

A. Teorema Principal (Teorema 1): Normalidade Assintótica
O resultado central estabelece que, sob a condição de momento $E[\xi^{2\Delta(t)+1}] < \infty$ (onde $\Delta(t)$ é o grau máximo de saída em $t$):

1. Comportamento Linear: A média e a variância de $N_t(T_n)$ são lineares em $n$:
   • $E[N_t(T_n)] = \mu n + o(\sqrt{n})$
   • $Var(N_t(T_n)) = \gamma^2 n + o(n)$
2. Convergência Normal: Se a variância não for limitada (ou seja, $\gamma > 0$), então:
   $$\frac{N_t(T_n) - \mu n}{\gamma \sqrt{n}} \xrightarrow{d} N(0, 1)$$
   Isso confirma uma conjectura feita por Janson em trabalho anterior.

B. Condições de Não-Degenerescência (Seção 4)
O artigo caracteriza quando a variância assintótica $\gamma^2$ é estritamente positiva.

• Proposição 8: Fornece condições suficientes para $\gamma > 0$. Se existirem duas árvores $\tau_1$ e $\tau_2$ com o mesmo tamanho e mesma estrutura até a altura de $t-1$, mas com contagens diferentes de $t$ ($N_t(\tau_1) \neq N_t(\tau_2)$), então a distribuição é não degenerada.
• Proposição 9 e Corolário 10: Descrevem os casos degenerados onde $\gamma = 0$. Nestes casos, a variância permanece limitada ($O(1)$) e a distribuição não converge para uma normal não degenerada. Isso ocorre, por exemplo, quando a contagem de subárvores é essencialmente uma função determinística do tamanho da árvore.

C. Otimidade da Condição de Momento (Seção 5)
Os autores investigam se a condição $E[\xi^{2\Delta+1}] < \infty$ é necessária.

• Exemplo 11 (Caminho de comprimento 2): Mostram que se $E[\xi^3] = \infty$ (mas momentos ligeiramente menores são finitos), a variância de $N_t(T_n)$ cresce superlinearmente, violando a normalidade.
• Exemplo 12 (Estrela): Para uma estrela com $\Delta$ folhas, se $E[\xi^{2\Delta}] = \infty$, a variância também cresce superlinearmente.
• Conclusão: A condição de momento proposta está muito próxima do ótimo; violá-la pode levar ao colapso da estrutura de variância linear e da normalidade.

4. Significância e Impacto

• Generalização de Resultados Existentes: O trabalho estende resultados conhecidos sobre contagens de subárvores de borda (fringe subtrees) para o caso mais geral de subárvores definidas por incorporação, que é um problema mais complexo devido à dependência não-local das contagens.
• Resolução de Conjecturas: Confirma a conjectura de Janson sobre a existência de um Teorema Central do Limite para essas contagens em árvores Galton-Watson condicionadas, fornecendo a condição exata de momento necessária.
• Aplicabilidade: As condições de momento cobrem a maioria das famílias clássicas de árvores aleatórias, incluindo árvores rotuladas enraizadas e árvores planas.
• Rigor Técnico: O artigo fornece uma análise detalhada dos casos degenerados e demonstra, através de contra-exemplos, a importância crítica da condição de momento para a validade do TCL, evitando generalizações incorretas para distribuições de descendência com caudas pesadas.

Em suma, o artigo estabelece um quadro rigoroso para a estatística de padrões de subárvores em árvores aleatórias condicionadas, provando que, sob condições de momento adequadas, essas contagens exibem comportamento gaussiano, com uma caracterização precisa das exceções degeneradas.