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

Cet article propose une modélisation bayésienne des temps d'arrêt de la conjecture de Collatz en comparant une régression hiérarchique binomiale négative et une approximation générative basée sur la décomposition en blocs impairs, démontrant que la structure modulaire de bas ordre (notamment $n \bmod 8$) est un facteur clé de l'hétérogénéité observée.

L'essentiel

Voici une explication simple de ce papier de recherche, imagée comme si nous racontions une histoire sur un jeu de hasard mathématique.

🎲 Le Grand Jeu de la Collatz : Un pari sur le destin des nombres

Imaginez que vous avez une machine à sous mathématique appelée la conjecture de Collatz. Voici comment elle fonctionne :

• Si le nombre est pair, vous le divisez par 2.
• Si le nombre est impair, vous le multipliez par 3 et ajoutez 1.
• Vous répétez l'opération encore et encore jusqu'à tomber sur le nombre 1.

Le "temps d'arrêt" (noté $\tau$), c'est simplement le nombre de coups de manivelle qu'il faut pour atteindre le 1. Par exemple, pour le nombre 27, il faut 111 coups ! Pour d'autres, c'est très court.

Le problème ? Personne ne sait pourquoi certains nombres mettent si longtemps à arriver à 1. C'est un mystère mathématique vieux de plusieurs décennies.

🕵️‍♂️ L'approche des auteurs : "On ne résout pas le mystère, on le prédit"

Au lieu de tenter de prouver que tout le monde finit par 1 (ce que personne n'a encore réussi), les auteurs ont décidé de jouer les statisticiens. Ils ont pris 10 millions de nombres, calculé combien de coups il fallait pour chacun, et se sont demandé : "Peut-on deviner la durée du voyage d'un nombre en regardant juste ses caractéristiques de base ?"

Ils ont construit deux modèles différents pour répondre à cette question, comme deux détectives avec des méthodes différentes.

---

🔍 Modèle 1 : Le Détective Statisticien (La Régression Bayésienne)

Imaginez un détective très pragmatique qui dit : "Je ne m'intéresse pas à la mécanique interne de la machine, je regarde juste les tendances."

• Son outil : Il utilise une règle mathématique flexible appelée régression Negative Binomial. C'est comme un modèle météo pour les nombres.
• Ce qu'il regarde : Il ne regarde que deux choses simples :
  1. La taille du nombre (plus le nombre est grand, plus le voyage est long, mais pas linéairement).
  2. Le reste de la division par 8 (c'est-à-dire la "famille" du nombre). Par exemple, un nombre qui donne 1 en le divisant par 8 se comporte différemment d'un nombre qui donne 7.
• Le résultat : Ce détective est très précis. Il prédit très bien la durée moyenne du voyage et sait même dire : "Il y a 95 % de chances que ce voyage dure entre X et Y coups." C'est le modèle le plus performant pour faire des prédictions pures.

Analogie : C'est comme un agent immobilier qui prédit le prix d'une maison juste en regardant sa surface et son quartier, sans avoir besoin de connaître l'histoire de la famille qui y a vécu.

---

⚙️ Modèle 2 : L'Ingénieur Mécanicien (Le Modèle Génératif)

Le deuxième détective est un ingénieur. Il dit : "Non, il faut comprendre comment la machine tourne !"

• Son idée : Il observe que le processus de Collatz fonctionne par "blocs". Quand on a un nombre impair, on fait l'opération $3n+1$, ce qui donne un nombre pair. Ensuite, on divise par 2 plusieurs fois de suite jusqu'à retomber sur un impair.
• Son hypothèse : Il suppose que le nombre de divisions par 2 (la longueur du bloc) est un peu aléatoire, comme lancer un dé.
  • Version A : Il lance un dé standard (théorie classique).
  • Version B : Il lance un dé spécial qui change selon la "famille" du nombre (le reste modulo 8), un peu comme si la machine avait des biais cachés.
• Le résultat : Ce modèle est plus joli et plus logique. Il explique pourquoi il y a des voyages très longs (des "queues" dans la distribution). Cependant, il est moins précis que le détective statistique pour prédire exactement combien de temps durera un voyage spécifique.

Analogie : C'est comme un mécanicien de voiture. Il ne prédit pas juste la vitesse, il explique que la voiture va plus vite parce que le moteur a un certain nombre de cylindres et que l'essence brûle d'une certaine façon. C'est plus "vrai" physiquement, mais moins précis pour deviner l'heure d'arrivée exacte.

---

🏆 Le Verdict : Qui gagne ?

Les auteurs ont mis les deux modèles en compétition sur un jeu de données qu'ils n'avaient jamais vu (un test caché).

1. Le gagnant de la précision : Le Détective Statisticien (Modèle 1). Il a gagné haut la main. Il sait mieux prédire la durée réelle du voyage.
2. Le gagnant de la compréhension : L'Ingénieur Mécanicien (Modèle 2). Bien qu'il soit moins précis, il nous apprend quelque chose d'important : la structure mathématique (le reste modulo 8) est la clé. Quand l'ingénieur a ajusté son modèle pour tenir compte de cette structure, il s'est beaucoup rapproché du détective.

💡 La leçon principale

Ce papier nous dit deux choses fascinantes :

1. Même si la machine Collatz semble chaotique, elle suit des règles statistiques très claires que l'on peut modéliser avec des outils simples (taille du nombre + reste modulo 8).
2. Pour comprendre le chaos, il ne suffit pas de regarder les nombres en gros. Il faut regarder les petites structures cachées (comme le reste de la division par 8) qui agissent comme des "feux tricolores" régulant la vitesse de la machine.

En résumé : On ne peut pas encore prouver que la machine s'arrête toujours, mais on peut maintenant prédire avec une grande précision combien de temps elle va tourner, et comprendre pourquoi certains nombres prennent des chemins de traverse.

Résumé technique

Voici un résumé technique détaillé de l'article "Bayesian Modeling of Collatz Stopping Times: A Probabilistic Machine Learning Perspective" de Nicolò Bonacorsi et Matteo Bordoni.

1. Problématique et Contexte

L'article aborde le problème de la conjecture de Collatz non pas sous l'angle de la preuve mathématique (qui reste ouverte), mais sous un angle probabiliste et d'apprentissage automatique.

• Objectif : Étudier la loi empirique du temps d'arrêt total $\tau(n)$ (le nombre d'itérations pour atteindre 1) pour $n \le 10^7$.
• Observations préliminaires : La distribution de $\tau(n)$ est fortement asymétrique, sur-dispersée (la variance est bien supérieure à la moyenne) et présente une hétérogénéité arithmétique marquée (des structures en bandes visibles en fonction de la valeur de $n$).
• Approche : Les auteurs traitent $n$ comme une variable aléatoire (échantillonnée uniformément) et modélisent la variabilité induite de $\tau(n)$ via des familles stochastiques paramétriques, sans supposer de bruit physique dans la dynamique déterministe de Collatz.

2. Méthodologie

Les auteurs développent deux modèles complémentaires pour prédire et expliquer la distribution de $\tau(n)$ :

A. Modèle Régressif Hiérarchique (NB2-GLM Bayésien)

Ce modèle vise la prédiction pure et la quantification de l'incertitude.

• Distribution : Utilisation d'une loi Binomiale Négative (NB2) pour gérer la sur-dispersion des données de comptage ($\text{Var} \approx \mu + \alpha\mu^2$).
• Covariables :
  • $\log(n)$ : Pour capturer la tendance de croissance lente de la moyenne.
  • $n \pmod 8$ : Pour capturer la structure arithmétique (hétérogénéité).
• Structure Hiérarchique : Les effets de la classe de résidus modulo 8 sont modélisés comme des effets aléatoires ($u_r \sim \mathcal{N}(0, \sigma_u^2)$) avec un "partial pooling" pour éviter le surajustement et stabiliser les estimations pour chaque classe.
• Inférence : Utilisation de l'échantillonnage NUTS (No-U-Turn Sampler) dans le cadre PyMC sur un sous-ensemble d'entraînement de 50 000 points.

B. Modèle Génératif Mécaniste (Odd-Block)

Ce modèle tente de reproduire la dynamique sous-jacente de manière stochastique.

• Décomposition : Basée sur la décomposition des blocs impairs. Pour un entier impair $m$, on écrit $3m+1 = 2^{K(m)}m'$, où$K(m) = v_2(3m+1)$ est la longueur du bloc de divisions par 2.
• Approximation Stochastique : Au lieu de calculer $K(m)$ de manière déterministe, on le remplace par une variable aléatoire $K_j$ tirée d'une distribution de probabilité $p_k$.
• Calibration :
  • G2 : Distribution $p_k$ globale estimée via un prior Dirichlet sur les longueurs de blocs observées.
  • G3 : Distribution $p_k$ conditionnée à la classe de résidus $m \pmod 8$, intégrant ainsi la dépendance arithmétique observée.
• Validation : Comparaison des distributions générées avec les données réelles via des vérifications prédictives a posteriori (PPC).

3. Résultats Clés

Performance Prédictive

Les modèles ont été évalués sur un ensemble de test disjoint ($N_{test} = 50\,000$) en utilisant le score de vraisemblance prédictive (Log Score) et la distance de Wasserstein ($W_1$).

Modèle	Log Score (plus élevé = mieux)	Distance $W_1$ (plus faible = mieux)
NB2-GLM (M3)	-272 911	3.20
Génératif G3 (Conditionnel)	-1 079 086	5.43
Génératif G2 (Global)	-1 165 983	17.59

• Conclusion : Le modèle de régression hiérarchique (NB2-GLM) surpasse largement les modèles génératifs en termes de vraisemblance prédictive. Il attribue une probabilité beaucoup plus élevée aux temps d'arrêt observés.
• Amélioration du modèle génératif : Le modèle G3 (conditionné par $m \pmod 8$) améliore considérablement l'ajustement par rapport au modèle G2 global, prouvant que la structure modulaire de bas ordre est un moteur clé de l'hétérogénéité.

Analyse de la Distribution

• La distribution empirique de $\tau(n)$ confirme une sur-dispersion massive ($\text{Var}/\text{Moy} \approx 24.56$), invalidant un modèle de Poisson simple.
• L'hypothèse classique selon laquelle la longueur de bloc $K$ suit une loi géométrique ($P(K=k) \approx 2^{-k}$) est rejetée par les données : la distribution empirique dévie significativement de la référence géométrique, surtout lorsqu'on la conditionne par $m \pmod 8$.

4. Contributions Principales

1. Modélisation Probabiliste Rigoureuse : Application d'une régression hiérarchique bayésienne (NB2-GLM) pour quantifier l'incertitude et prédire les temps d'arrêt de Collatz avec une grande précision sur un large jeu de données ($10^7$).
2. Générateur Mécaniste Calibré : Développement d'une approximation générative basée sur la décomposition "odd-block", calibrée par inférence bayésienne (Dirichlet-Multinomiale) plutôt que par des heuristiques purement théoriques.
3. Preuve de l'Importance Modulaire : Démonstration empirique que la classe de résidus modulo 8 est une variable explicative cruciale, tant pour la régression (effet aléatoire) que pour la génération (conditionnement), reliant ainsi les structures arithmétiques aux propriétés statistiques globales.
4. Comparaison Méthodologique : Mise en évidence de la complémentarité entre les modèles prédictifs (excellents pour la prévision) et les modèles mécanistes (excellents pour l'interprétation structurelle, même si moins performants en score pur).

5. Signification et Perspectives

Cet article démontre que les propriétés statistiques complexes de la conjecture de Collatz peuvent être capturées et prédites par des modèles d'apprentissage automatique modernes, sans résoudre la conjecture elle-même.

• Signification : Il fournit une "vraisemblance de travail" (working likelihood) solide pour étudier la dynamique de Collatz comme un processus stochastique induit par la structure arithmétique des entiers.
• Travaux futurs : Les auteurs suggèrent d'étendre la structure conditionnelle à des puissances de deux plus élevées, d'incorporer une dépendance explicite de l'état dans les longueurs de blocs, et d'aligner davantage les scores de vraisemblance avec l'interprétabilité mécaniste.

En résumé, l'article propose un cadre hybride où la statistique bayésienne sert à la fois d'outil de prédiction robuste et de moyen de valider des hypothèses mécanistes sur la dynamique de Collatz.