Bayesian Modeling of Collatz Stopping Times: A Probabilistic Machine Learning Perspective

Este artigo analisa os tempos de parada da conjectura de Collatz para $n \le 10^7$ através de uma perspectiva de aprendizado de máquina probabilístico, demonstrando que um modelo hierárquico bayesiano de regressão Negativa Binomial supera aproximações geradoras baseadas em decomposição de blocos ímpares, enquanto evidencia que a estrutura modular de baixa ordem é um fator crucial para a heterogeneidade observada nos dados.

O essencial

Imagine que o Problema de Collatz é um jogo de tabuleiro infinito e misterioso. As regras são simples:

1. Se o número for par, você o divide por 2.
2. Se for ímpar, você multiplica por 3 e soma 1.
3. Repita até chegar ao número 1.

A grande pergunta dos matemáticos é: "Será que qualquer número que você começar vai eventualmente chegar ao 1?" Ninguém sabe a resposta definitiva. Mas, neste artigo, os autores não tentam provar a resposta. Em vez disso, eles agem como detetives de dados ou meteorologistas. Eles não querem saber por que o tempo vai chover amanhã (a prova matemática), mas sim prever como vai ser o tempo com base em padrões históricos.

Eles estudaram 10 milhões de números e mediram quanto tempo (quantos passos) cada um levou para chegar ao 1. Esse tempo é chamado de "tempo de parada".

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

1. O Problema: É um caos bagunçado?

Se você olhar para o tempo que cada número leva para chegar ao 1, parece uma bagunça total. Alguns números chegam rápido, outros demoram muito. A distribuição não é uma linha reta nem uma curva suave; é "distorcida" e cheia de valores extremos (como um dia de tempestade que dura 10 horas em vez de 1).

Os autores disseram: "Ok, não podemos prever o caminho exato de cada número (porque é determinístico), mas podemos criar um modelo estatístico que descreva o comportamento médio desses números, como se eles fossem aleatórios."

2. A Primeira Solução: O "Oráculo Estatístico" (Regressão Negativa Binomial)

Imagine que você quer prever o preço de uma casa. Você sabe que casas maiores custam mais (escala) e que casas em bairros específicos têm um preço base diferente (arquitetura do bairro).

Os autores criaram um modelo matemático (chamado NB2-GLM) que funciona como um oráculo esperto:

• Fator 1 (Tamanho): Eles notaram que números maiores tendem a demorar um pouco mais, mas não linearmente. É como dizer que uma casa de 100m² não custa o dobro de uma de 50m², mas sim um pouco mais. Eles usaram o logaritmo do número para medir isso.
• Fator 2 (O "Bairro" do Número): Eles perceberam que o resto da divisão do número por 8 (se o número é "resto 0", "resto 1", etc.) faz uma grande diferença. É como se números que terminam em certos dígitos tivessem um "destino" diferente no jogo.

O Resultado: Esse modelo é como um GPS de alta precisão. Ele não sabe o caminho exato que o carro vai tomar, mas prevê com muita certeza quanto tempo a viagem vai demorar e dá uma margem de erro. Quando testado em números que ele nunca viu antes, esse "GPS" foi o mais preciso de todos.

3. A Segunda Solução: O "Simulador de Mecânica" (Modelo Gerador de Blocos)

A primeira solução é ótima para prever, mas não explica como o jogo funciona por dentro. Então, os autores criaram uma segunda abordagem: um simulador mecânico.

Imagine que o jogo de Collatz é feito de "blocos".

• Quando você tem um número ímpar, ele dá um "salto" (multiplica por 3 e soma 1).
• Depois desse salto, o número fica par e você divide por 2 várias vezes seguidas até ficar ímpar de novo.
• A quantidade de vezes que você divide por 2 é chamada de "comprimento do bloco".

A teoria antiga dizia que esses "comprimentos de bloco" eram como jogar um dado: 50% de chance de dividir uma vez, 25% duas vezes, etc.
Os autores pegaram essa ideia e a refinaram. Eles disseram: "E se o 'dado' não for justo? E se o tipo de dado mudar dependendo do 'bairro' (resto módulo 8) do número?"

Eles criaram um gerador que simula o jogo jogando esses dados personalizados.

• Versão Simples: Usa um dado padrão para todos. (Funciona mal).
• Versão Refinada: Usa dados diferentes para cada tipo de resto (módulo 8). (Funciona melhor, mas ainda não é perfeito).

4. Quem venceu?

Quando compararam os dois modelos em um teste de "quem acerta mais":

• O Oráculo Estatístico (Modelo 1) venceu de longe. Ele previu os tempos de parada com muito mais precisão. É como um meteorologista que olha para o histórico de 10 anos e diz "vai chover".
• O Simulador Mecânico (Modelo 2) foi menos preciso em prever o número exato, mas foi mais honesto sobre a física do jogo. Ele mostrou que a estrutura matemática (o resto da divisão por 8) é a chave para entender por que alguns números se comportam de forma diferente.

A Lição Principal (A Metáfora Final)

Pense no Problema de Collatz como uma floresta densa:

• O Modelo Estatístico é como um mapa de satélite que diz: "Se você entrar na floresta por aqui, a chance de sair em 10 minutos é de 80%". É útil para quem quer chegar ao destino.
• O Modelo Mecânico é como um guia que explica: "A floresta tem caminhos que se curvam mais à esquerda dependendo da cor da sua mochila". É útil para entender a natureza da floresta.

Conclusão do Artigo:
Os autores mostram que, mesmo sem resolver o mistério matemático de por que o jogo funciona, podemos usar a inteligência artificial e a estatística para entender o comportamento desses números. Eles descobriram que a "aritmética simples" (o resto da divisão por 8) é o segredo que explica por que alguns números demoram tanto mais que outros.

É uma prova de que, às vezes, para entender o caos, não precisamos de uma fórmula mágica, mas sim de um bom modelo estatístico que respeite as pequenas regras do jogo.

Resumo técnico

Resumo Técnico: Modelagem Bayesiana dos Tempos de Parada de Collatz

1. O Problema e o Objetivo

O artigo aborda o problema de parada total da conjectura de Collatz, definido como $\tau(n) = \min\{t \ge 0 : T^t(n) = 1\}$, onde $T(n)$ é o mapa de Collatz ($n/2$ se par, $3n+1$se ímpar). Embora a conjectura de que$\tau(n) < \infty$para todo$n$ permaneça aberta, os autores não buscam uma prova matemática.

Em vez disso, o objetivo é preditivo e explicativo:

• Analisar a lei empírica de $\tau(n)$ para $n \le 10^7$.
• Desenvolver modelos probabilísticos que expliquem a forma da distribuição (que é enviesada e superdispersa) e sua heterogeneidade aritmética (variação baseada na estrutura modular dos números).
• Quantificar a incerteza nas previsões sem assumir ruído físico no sistema determinístico, tratando $n$ como uma variável aleatória amostrada uniformemente.

2. Metodologia e Modelos Propostos

Os autores desenvolveram dois modelos complementares para analisar os dados:

A. Regressão Hierárquica Binomial Negativa (NB2-GLM)

• Abordagem: Trata $\tau(n)$ como uma variável de contagem superdispersa.
• Estrutura: Um modelo de regressão logística (link log) onde a média $\mu_n$ depende de:
  1. $\log(n)$: Para capturar o crescimento lento da escala.
  2. $n \pmod 8$: Incluído como um efeito aleatório hierárquico (random intercept) para capturar a heterogeneidade aritmética (bandas visíveis nos dados).
• Distribuição: Binomial Negativa (NB2), onde a variância é $\text{Var}(Y) = \mu + \alpha\mu^2$. Isso permite modelar a superdispersão observada (razão variância/média $\approx 24.56$), algo que um modelo Poisson não conseguiria.
• Inferência: Utilização de amostragem NUTS (No-U-Turn Sampler) via PyMC para obter distribuições posteriores.

B. Modelo Gerador Mecanístico (Odd-Block)

• Abordagem: Uma aproximação generativa baseada na decomposição de "blocos ímpares".
• Mecanismo: Para um número ímpar $m$, escreve-se $3m+1 = 2^{K(m)}m'$, onde$K(m) = v_2(3m+1)$ é o número de divisões por 2 até retornar a um número ímpar.
• Estocastificação: Substitui-se a dependência determinística de $K(m)$ por uma distribuição estocástica de comprimentos de bloco ($K_j$).
• Calibração:
  • G1 (Heurística Clássica): Assume $K$ segue uma distribuição geométrica $P(K=k) \approx 2^{-k}$.
  • G2 (Calibrado Global): Estima os parâmetros da distribuição de $K$ a partir dos dados observados usando uma atualização Dirichlet-Multinomial.
  • G3 (Condicionado): Refina o modelo G2 condicionando a distribuição de $K$ à classe de resíduo $m \pmod 8$.

3. Resultados Principais

Os modelos foram avaliados em um conjunto de teste de 50.000 pontos não vistos, utilizando Log-Score Preditivo (uma regra de pontuação estritamente adequada) e a Distância Wasserstein (W1) para medir o ajuste da forma da distribuição.

• Desempenho Preditivo:
  • O modelo NB2-GLM (M3) obteve o melhor desempenho, com um log-score de -272.911 (média de -5.46 por observação).
  • O gerador global (G2) teve um desempenho significativamente pior (-1.165.983).
  • O gerador condicionado (G3) melhorou substancialmente sobre o global (-1.079.086), mas ainda ficou atrás da regressão.
• Ajuste Distribucional (W1):
  • O NB2-GLM apresentou a menor distância W1 (3.20), indicando o melhor ajuste global à forma da distribuição empírica.
  • O modelo G3 reduziu a distância W1 para 5.43 (contra 17.59 do G2), demonstrando que a estrutura modular é crucial para capturar a heterogeneidade.
• Descobertas sobre Heterogeneidade:
  • A análise confirmou que a classe de resíduo $n \pmod 8$ é um driver chave da heterogeneidade.
  • O modelo G3 mostrou que a distribuição de comprimentos de bloco $K$ varia sistematicamente dependendo do resíduo módulo 8, refutando a hipótese de que $K$ é puramente geométrico e independente do contexto aritmético.

4. Contribuições Chave

1. Modelagem Probabilística Rigorosa: Demonstra que uma abordagem de aprendizado de máquina bayesiano pode capturar a estrutura complexa de sistemas determinísticos caóticos como o de Collatz, fornecendo intervalos de confiança e quantificação de incerteza.
2. Validação de Heurísticas: Valida empiricamente que a heurística clássica de "número de divisões por 2 é geométrica" é uma aproximação grosseira. A calibração baseada em dados e o condicionamento modular são necessários para um ajuste preciso.
3. Ponte entre Fenomenologia e Mecanismo: O estudo conecta dois pontos de vista:
   • O modelo de regressão (fenomenológico) captura a tendência macro e a heterogeneidade via efeitos aleatórios.
   • O modelo gerador (mecanístico) explica por que essa heterogeneidade existe (dependência aritmética de $K(m)$).
4. Eficiência Computacional: Uso de programação dinâmica e compilação JIT (Numba) para calcular tempos de parada para $10^7$ inteiros de forma eficiente.

5. Significado e Conclusão

O artigo conclui que, embora o modelo de regressão hierárquica seja superior para previsão pura (maior verossimilhança), o modelo gerador condicional oferece uma interpretabilidade mecânica valiosa.

A principal lição é que a estrutura modular de baixa ordem (como $n \pmod 8$) é fundamental para entender a dinâmica de Collatz. Ignorar essa estrutura (como no modelo G2) leva a erros significativos na modelagem da cauda e da variância. O trabalho sugere que futuras pesquisas devem focar em estender essa estrutura condicional para potências maiores de dois e incorporar dependência de estado explícita nos geradores estocásticos para alinhar melhor a pontuação preditiva com a interpretabilidade mecânica.

Em suma, o papel não prova a conjectura de Collatz, mas fornece uma ferramenta estatística robusta para entender o comportamento "típico" e as anomalias aritméticas das trajetórias de Collatz em grandes escalas.