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

Dit artikel presenteert een Bayesiaanse machine learning-analyse van de Collatz-stoptijden voor $n \le 10^7$, waarbij een hiërarchisch Negatief Binomiaal regressiemodel en een mechanistische generatieve benadering worden vergeleken om aan te tonen dat modulaire structuur (met name modulo 8) cruciaal is voor het verklaren van de heterogeniteit in deze tijden.

De kern

Stel je voor dat je een enorme, ingewikkelde labyrint hebt, waar elke deur een getal is. Je begint bij een willekeurig getal en volgt een heel simpel, maar raar spoor:

• Als het getal even is, deel je het door 2.
• Als het getal oneven is, vermenigvuldig je het met 3 en tel je er 1 bij op.

Je doet dit steeds opnieuw. De grote vraag (de "Collatz-vermoeden") is: Kom je uiteindelijk altijd bij het getal 1 uit? Niemand weet het zeker, maar voor bijna alle getallen die we hebben gecontroleerd, is het antwoord ja.

Dit artikel van Bonacorsi en Bordoni probeert niet om dat labyrint te oplossen. In plaats daarvan kijken ze naar een heel specifiek aspect: Hoeveel stappen kost het om bij 1 te komen? Dit noemen ze de "stop-tijd".

Hier is wat ze hebben gedaan, vertaald naar simpele taal met een paar creatieve vergelijkingen:

1. Het Probleem: Een chaotische massa

Als je naar de stop-tijden van miljoenen getallen kijkt, zie je geen nette lijn. Het is een enorme chaos.

• Sommige getallen stoppen heel snel.
• Andere getallen rennen heel lang rond voordat ze stoppen.
• Het is alsof je een regenwolk van punten ziet: de meeste zijn laag, maar er zijn een paar die tot in de stratosfeer vliegen.

De auteurs zeggen: "Dit is te chaotisch om exact te voorspellen, maar we kunnen wel een statistisch model bouwen dat het gedrag beschrijft." Ze behandelen het getal $n$ alsof het een willekeurig geloot nummer is in een loterij.

2. Model 1: De "Slimme Gokker" (Bayesiaanse Regressie)

De eerste methode is als een slimme gokker die patronen zoekt zonder te weten hoe de machine van binnen werkt.

• De observatie: Ze zien twee dingen die belangrijk zijn:
  1. Hoe groter het getal, hoe langer het meestal duurt (maar niet lineair, meer als een logaritmische kromme).
  2. Er is een vreemd patroon: getallen die op dezelfde manier "klinken" als je ze door 8 deelt (bijvoorbeeld 1, 9, 17, 25), gedragen zich vaak hetzelfde.
• De oplossing: Ze bouwen een wiskundig model (een "Negative Binomial" model) dat deze twee factoren combineert.
• Het resultaat: Dit model is als een uitstekende voorspeller. Als je een nieuw getal geeft, kan het model heel nauwkeurig zeggen: "Dit getal duurt waarschijnlijk tussen de 150 en 200 stappen." Het is niet perfect, maar het is de beste voorspeller die ze hebben.

3. Model 2: De "Mechanische Poppenkast" (Generatief Model)

De tweede methode is interessanter. In plaats van alleen te gokken, proberen ze de motor van het labyrint na te bouwen.

• De mechaniek: Ze kijken naar wat er gebeurt als je een oneven getal hebt. Je doet $3n+1$, en het resultaat is altijd even. Dan moet je het een paar keer door 2 delen totdat je weer bij een oneven getal bent.
  • Vergelijking: Stel je voor dat je een bal op een helling gooit. Soms rolt hij 1 meter, soms 5 meter, soms 10 meter voordat hij weer een nieuwe sprong maakt. De "spronglengte" is willekeurig.
• De simulatie: Ze maken een computerprogramma dat deze sprongen niet exact berekent, maar willekeurig genereert op basis van de gemiddelde lengte die ze in de data hebben gezien.
• Het inzicht: Eerst dachten ze dat deze spronglengtes volledig willekeurig waren (zoals het gooien van een munt). Maar toen ze keken naar de "mod 8" (het patroon van de laatste cijfers), zagen ze dat de lengte van de sprong afhangt van dat patroon.
  • Analogie: Het is alsof je merkt dat de bal op de helling altijd langer rolt als hij op een rood tapijt begint, en korter op een blauw tapijt.

4. De Vergelijking: Wie wint er?

Ze hebben beide modellen getest op een nieuwe set getallen (die ze niet eerder hadden gezien).

• De "Slimme Gokker" (Model 1): Wint met gemak. Hij voorspelt de resultaten het meest nauwkeurig. Hij is als een ervaren meteoroloog die de weersvoorspelling perfect heeft.
• De "Mechanische Poppenkast" (Model 2): Wint op het gebied van begrip. Hij vertelt je waarom het gebeurt. Als je de "rode tapijten" (de mod 8 patronen) meeneemt in de simulatie, wordt hij veel beter.

De Grote Les

Het artikel leert ons twee dingen:

1. Je kunt het gedrag van dit wiskundige mysterie heel goed voorspellen met een simpel statistisch model, zelfs zonder de onderliggende regels volledig te doorgronden.
2. Maar als je echt wilt begrijpen waarom het zo werkt, moet je kijken naar de kleine, verborgen patronen (zoals de rest bij deling door 8). Zelfs in een chaotisch systeem als dit, zit er een strakke, wiskundige orde in die je kunt "luisteren" als je goed genoeg kijkt.

Kortom: Ze hebben geen oplossing gevonden voor het raadsel van het getal 1, maar ze hebben wel een heel goede kaart getekend van het landschap, en ze hebben ontdekt dat de "grondsoort" (het getal modulo 8) bepaalt hoe snel je door dat landschap beweegt.

Technische samenvatting

Hieronder volgt een gedetailleerde technische samenvatting van het artikel "Bayesian Modeling of Collatz Stopping Times: A Probabilistic Machine Learning Perspective" in het Nederlands.

Probleemstelling

Het artikel onderzoekt het Collatz-probleem (ook wel de $3x+1$-conjecture genoemd) niet vanuit het perspectief van een wiskundig bewijs, maar als een statistisch voorspellingsprobleem. De auteurs analyseren de **totale stoptijd**$\tau(n)$, gedefinieerd als het aantal stappen dat nodig is om van een geheel getal$n$naar 1 te komen via de Collatz-afbeelding$T(n)$.

De centrale uitdaging is het modelleren van de empirische verdeling van $\tau(n)$ voor $n \leq 10^7$. De data vertoont kenmerken die moeilijk te modelleren zijn met standaard methoden:

• Sterke scheefheid en overdispersie: De verdeling heeft een zware rechterstaart en de variantie is veel groter dan het gemiddelde (dispensieratio $\approx 24,56$), wat een Poisson-model uitsluit.
• Arithmetische heterogeniteit: Er is een duidelijke "bandvorming" in de data afhankelijk van de restklasse van $n$ modulo kleine machten van 2 (bijv. $n \pmod 8$).
• Determinisme vs. Probabiliteit: Hoewel de Collatz-dynamiek deterministisch is, behandelen de auteurs $n$ als een stochastische variabele (uniform verdeeld) om een werkende waarschijnlijkheidsfunctie (working likelihood) te bouwen voor voorspelling en onzekerheidskwantificering.

Methodologie

De auteurs ontwikkelen twee complementaire modellen om de stoptijden te verklaren en te voorspellen:

1. Bayesiaanse Hiërarchische Negatief-Binomiale Regressie (NB2-GLM)

Dit is een fenomenologisch model dat $\tau(n)$ behandelt als een overdispersed tellingsvariabele.

• Likelihood: Gebruik van een Negatief-Binomiale verdeling (NB2-parameterisatie) waarbij de variantie $\text{Var}(Y) = \mu + \alpha\mu^2$. Dit lost het probleem van overdispersie op.
• Covariaten:
  • $\log(n)$: Om de langzame groei van de gemiddelde stoptijd te vangen.
  • $n \pmod 8$: Als een categorische variabele om de arithmetische structuur te modelleren.
• Hiërarchische structuur: De intercepts voor de verschillende restklassen ($r = 0, \dots, 7$) worden gemodelleerd als willekeurige effecten ($u_r \sim \mathcal{N}(0, \sigma_u^2)$). Dit zorgt voor "partial pooling", wat overfitting voorkomt en stabiele schattingen oplevert voor klassen met minder data.
• Inferentie: Uitgevoerd met NUTS (No-U-Turn Sampler) in PyMC op een trainingsset van 50.000 punten.

2. Mechanistische Generatief Model (Odd-Block Decompositie)

Dit model probeert de onderliggende dynamiek te benaderen door de deterministische stappen te randomiseren.

• Odd-Block Decompositie: Voor een oneven getal $m$ wordt $3m+1$geschreven als$2^{K(m)}m'$, waarbij$K(m) = v_2(3m+1)$het aantal delingen door 2 is. De dynamica wordt gezien als een reeks "blokken" van lengte$K$.
• Stochastische benadering: In plaats van de exacte waarde van $K(m)$ te berekenen, wordt deze vervangen door een stochastische variabele $K_j$ met een kansverdeling $p_k$.
• Calibratie: De verdeling $p_k$ wordt geschat uit de data via een Dirichlet-multinomiaal update.
• Varianten:
  • G1: Een klassieke heuristiek waarbij $K$ geometrisch verdeeld is ($P(K=k) \approx 2^{-k}$).
  • G2: Een globaal gekalibreerd model (gebaseerd op de empirische verdeling van $K$).
  • G3: Een conditioneel model waarbij de verdeling van $K$ afhangt van de restklasse $m \pmod 8$.

Belangrijkste Resultaten

Voorspellende Prestaties

De modellen werden geëvalueerd op een gehouden testset ($N_{test} = 50.000$) met behulp van de log-predictieve score (een proper scoring rule) en de 1-Wasserstein afstand (W1) voor verdelingsvorm.

Model	Log Score (hoger is beter)	W1 Afstand (lager is beter)
NB2-GLM (M3)	-272.912	3,20
Odd-Block G3 (Conditioneel)	-1.079.087	5,43
Odd-Block G2 (Globaal)	-1.165.983	17,59

• De NB2-GLM presteert veruit het best qua voorspellende waarschijnlijkheid. Het model kent de waargenomen stoptijden aanzienlijk hogere kansen toe dan de generatieve modellen.
• De Odd-Block generator G3 (conditioneel op $m \pmod 8$) presteert aanzienlijk beter dan het globale model G2, wat aantoont dat de lage-orde modulaire structuur een sleutelfactor is in de heterogeniteit van de stoptijden.
• Desondanks blijft de regressie (M3) superieur in pure voorspellende nauwkeurigheid.

Verdelingsanalyse

• De NB2-GLM past de bulk van de verdeling goed aan, maar overschat licht de massa in de uiterste rechterstaart (consistent met de kwadratische variantie van NB2).
• Het generatieve model G3 verbetert de fit in de bulk ten opzichte van G2, maar kan de zware staart van de empirische data niet volledig reproduceren zonder de complexe deterministische afhankelijkheden te modelleren.

Bijdragen en Significantie

1. Probabilistische Kaderstelling: Het artikel biedt een nieuw perspectief op het Collatz-probleem door het te behandelen als een machine learning-taak voor voorspelling en onzekerheidskwantificering, zonder te proberen de conjectuur te bewijzen.
2. Kwantificering van Heterogeniteit: Het bewijst empirisch dat eenvoudige covariaten ($\log n$ en $n \pmod 8$) een groot deel van de variatie in stoptijden kunnen verklaren. De hiërarchische regressie toont aan dat de "bandvorming" in de data statistisch significant is.
3. Brug tussen Mechanisme en Statistiek: Het onderzoek verbindt een mechanistische benadering (odd-block decompositie) met statistische modellering. Het toont aan dat het randomiseren van de blok-lengten $K$ een bruikbare generatieve benadering is, mits deze correct wordt gekalibreerd en conditioneel wordt gemaakt op arithmetische eigenschappen.
4. Praktische Implementatie: De auteurs demonstreren hoe schaalbare berekeningen ($N=10^7$) mogelijk zijn door gebruik te maken van dynamisch programmeren en JIT-compilatie (Numba), en hoe Bayesiaanse methoden (PyMC) effectief kunnen worden ingezet voor complexe, niet-lineaire getaltheoretische data.

Conclusie:
Hoewel de hiërarchische Negatief-Binomiale regressie het meest accurate voorspellende model is, biedt het mechanistische odd-block model (vooral de conditionele variant G3) diepere inzichten in waarom de data zo gedraagt. De studie suggereert dat de arithmetische structuur (mod 8) een fundamentele drijvende kracht is achter de heterogeniteit van Collatz-stoptijden, en dat probabilistische modellen een krachtig hulpmiddel zijn om deze structuren te kwantificeren.