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

Diese Arbeit untersucht die Kollatz-Stop-Zeit über $n \le 10^7$ mittels eines bayesschen hierarchischen Negativ-Binomial-Modells und einer mechanistischen Generatormethode, wobei die Ergebnisse zeigen, dass die Berücksichtigung modularer Restklassen die Verteilungsanpassung erheblich verbessert und das NB2-GLM die höchste Vorhersagegüte erzielt.

Das Wesentliche

Stell dir vor, das Collatz-Problem ist ein riesiges, chaotisches Labyrinth, in dem jede Zahl einen eigenen Weg zum Ausgang (der Zahl 1) hat. Die Regeln sind einfach: Ist die Zahl gerade, teile sie durch 2. Ist sie ungerade, multipliziere sie mit 3 und addiere 1. Wiederhole das, bis du bei 1 ankommst.

Die große Frage ist: Kommt jede Zahl irgendwann bei 1 an? Niemand weiß es sicher. Aber in diesem Papier schauen sich die Autoren nicht den Weg einer einzelnen Zahl an, sondern sie fragen: „Wie sieht der durchschnittliche Weg für Millionen von Zahlen aus?"

Sie haben sich 10 Millionen Zahlen vorgenommen und gemessen, wie viele Schritte jede braucht, um bei 1 anzukommen. Das Ergebnis war ein riesiger, unordentlicher Haufen Daten. Hier ist, wie sie versucht haben, dieses Chaos zu verstehen – erklärt mit einfachen Bildern:

1. Das Problem: Ein unordentlicher Haufen

Stell dir vor, du wirfst 10 Millionen Bälle in einen Korb und zählst, wie oft sie aufspringen, bevor sie liegen bleiben.

• Die meisten Bälle springen ein paar Mal.
• Einige springen sehr oft.
• Ein paar springen extrem oft und landen weit weg.

In der Statistik nennt man das „überdispersiert". Es ist nicht vorhersehbar wie ein Würfelwurf (wo die Wahrscheinlichkeiten klar sind). Es ist wie ein Sturm: Man weiß, dass es regnet, aber nicht genau, wo die größten Pfützen entstehen. Die Autoren haben festgestellt, dass die Anzahl der Schritte (die „Stoppzeit") nicht einfach einer normalen Glockenkurve folgt, sondern einen langen, wilden Schweif hat.

2. Modell A: Der Wettervorhersager (Die statistische Regression)

Der erste Ansatz der Autoren ist wie ein sehr cleverer Wettervorhersager.
Er sagt nicht: „Ich verstehe die Physik des Sturms." Er sagt: „Ich habe die letzten 10 Millionen Tage geschaut, und wenn es heute so aussieht (große Zahl) und die Farbe des Himmels so ist (Rest der Zahl bei Division durch 8), dann wird es wahrscheinlich regnen."

• Wie es funktioniert: Sie nutzen ein mathematisches Werkzeug (eine „Negative Binomial-Regression"), das zwei Dinge beachtet:
  1. Die Größe der Zahl: Je größer die Zahl, desto länger dauert es im Durchschnitt (wie ein längerer Weg).
  2. Die „Farbe" der Zahl: Wenn man die Zahl durch 8 teilt, bleibt ein Rest (z. B. 1, 3, 5...). Dieser Rest ist wie ein versteckter Code. Zahlen mit demselben Rest verhalten sich oft ähnlich.
• Das Ergebnis: Dieser Vorhersager ist extrem gut darin, zu sagen, wie viele Schritte wahrscheinlich nötig sind. Er ist wie ein erfahrener Kapitän, der die Wellen kennt, ohne zu wissen, wie der Wind physikalisch entsteht. Er gewinnt den Wettbewerb, wenn es nur darum geht, die richtige Vorhersage zu treffen.

3. Modell B: Der Mechaniker (Der generative Prozess)

Der zweite Ansatz ist wie ein Mechaniker, der versucht, den Motor des Labyrinths nachzubauen.
Statt nur zu schauen, wo die Bälle landen, versuchen sie, den Motor zu verstehen, der die Bälle wirft.

• Die Idee: Wenn eine ungerade Zahl „3n+1" macht, wird sie gerade. Dann wird sie durch 2 geteilt, bis sie wieder ungerade ist. Dieser Zyklus (ungerade → 3n+1 → viele Halbierungen → wieder ungerade) ist wie ein Baustein.
• Der Zufall: Die Autoren sagen: „Statt die exakte Mathematik für jede Zahl zu berechnen, bauen wir einen Zufallsgenerator." Sie nehmen an, dass die Anzahl der Halbierungsschritte (der Baustein) zufällig ist, aber nach bestimmten Regeln.
• Die Entdeckung: Anfangs dachten sie, diese Bausteine wären völlig zufällig (wie ein Würfelwurf). Aber als sie genauer hinschauten, merkten sie: Nein! Die Art und Weise, wie viele Halbierungsschritte nötig sind, hängt stark davon ab, welchen Rest die Zahl bei 8 lässt.
  • Analogie: Stell dir vor, du hast 8 verschiedene Arten von Schrauben. Du dachtest, sie wären alle gleich. Aber wenn du genauer hinschaust, merkst du: Schrauben mit Rest 1 brauchen immer 2 Drehungen, Schrauben mit Rest 3 brauchen 4. Das ist der „arithmetische Code".

4. Der Showdown: Wer gewinnt?

Am Ende haben sie beide Modelle gegeneinander antreten lassen, um zu sehen, wer die 10 Millionen Zahlen besser vorhersagen kann.

• Der Wettervorhersager (Modell A) hat gewonnen. Er war viel genauer darin, die tatsächlichen Ergebnisse vorherzusagen. Er ist pragmatisch und nutzt die Muster, die er sieht, ohne sich um die tiefe Physik zu kümmern.
• Der Mechaniker (Modell B) war etwas ungenauer, aber er hat etwas Wichtigeres gelernt: Er hat entdeckt, dass das „Zufallsspiel" gar nicht zufällig ist. Es folgt einer versteckten Struktur (dem Rest bei 8).

Fazit für den Alltag

Das Papier sagt uns zwei Dinge:

1. Pragmatismus siegt: Wenn du nur wissen willst, wie lange ein Weg dauert, reicht es oft, einfache Muster (Größe der Zahl + Rest bei 8) zu nutzen. Du musst den ganzen Motor nicht verstehen.
2. Versteckte Ordnung: Selbst in einem chaotischen System wie dem Collatz-Problem gibt es tiefe, versteckte Regeln. Wenn man den Mechanismus (den Motor) baut, muss man diese versteckten Regeln (die Reste bei 8) einbauen, sonst funktioniert das Modell nicht richtig.

Es ist wie beim Kochen:

• Der Statistiker sagt: „Wenn du 100 Eier hast und den Ofen auf 200 Grad stellst, brennen sie zu 90% an." (Er hat die Daten).
• Der Mechaniker sagt: „Ah, ich verstehe jetzt, warum sie brennen! Es liegt an der Hitzeverteilung im Ofen, die von der Form des Blechs abhängt." (Er hat das Prinzip verstanden).

Beide haben recht, aber der Statistiker liefert die bessere Vorhersage für das nächste Gericht, während der Mechaniker uns hilft, den Ofen zu reparieren.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Bayesian Modeling of Collatz Stopping Times: A Probabilistic Machine Learning Perspective" auf Deutsch.

1. Problemstellung und Zielsetzung

Das Paper untersucht das Collatz-Problem (auch $3x+1$-Problem) aus einer probabilistischen Machine-Learning-Perspektive. Das Ziel ist nicht, die Vermutung zu beweisen, dass die Collatz-Folge für jede natürliche Zahl$n$gegen 1 konvergiert, sondern das Verhalten der **Gesamtschrittzeit** (total stopping time)$\tau(n)$ zu modellieren und zu verstehen.

• Definition: Die Collatz-Abbildung $T(n)$ ist definiert als $n/2$ für gerade $n$ und $3n+1$für ungerade$n$. Die Gesamtschrittzeit$\tau(n)$ist die minimale Anzahl von Schritten$t$, bis$T^t(n) = 1$ gilt.
• Datenbasis: Die Autoren analysieren den Datensatz $D_N = \{(n, \tau(n))\}$ für alle $1 \le n \le N$mit$N = 10^7$.
• Herausforderung: Die Verteilung von $\tau(n)$ ist stark schief (skewed), überdispersiert (overdispersed) und weist eine ausgeprägte arithmetische Heterogenität auf (z. B. Bandstrukturen in Abhängigkeit von $n$). Das Paper fragt, welche einfachen probabilistischen Modelle diese Verteilungsform und die arithmetischen Strukturen vorhersagen und erklären können.

2. Methodik

Die Autoren entwickeln zwei komplementäre Modelle, um $\tau(n)$ zu modellieren:

A. Modell 1: Bayessche hierarchische Negative-Binomial-Regression (NB2-GLM)

Dies ist ein phänomenologisches, prädiktives Modell.

• Likelihood: Da $\tau(n)$ eine überdispersierte Zählvariable ist (Varianz $\gg$ Mittelwert), wird eine Negative-Binomial-Verteilung (NB2-Parametrisierung) gewählt:
  $$Y_n | \mu_n, \alpha \sim \text{NB}(\mu_n, \alpha), \quad \text{Var}(Y_n) = \mu_n + \alpha \mu_n^2$$
• Kovariaten: Der Logarithmus des Mittelwerts $\log \mu_n$ wird als Funktion von zwei einfachen Kovariaten modelliert:
  1. $\log n$: Erfasst den langsamen Skaleneffekt.
  2. $n \pmod 8$: Erfasst die arithmetische Heterogenität (Restklassen).
• Hierarchie: Die Effekte der Restklassen $r \in \{0, \dots, 7\}$ werden als zufällige Effekte ($u_r \sim \mathcal{N}(0, \sigma_u^2)$) modelliert. Dies ermöglicht ein „partial pooling", das Überanpassung verhindert und stabile Schätzungen auch für Klassen mit weniger Daten liefert.
• Inferenz: Die Parameter werden mittels NUTS (No-U-Turn Sampler) in PyMC geschätzt, basierend auf einem Trainingsdatensatz von 50.000 Stichproben.

B. Modell 2: Mechanistischer generativer Odd-Block-Ansatz

Dies ist ein strukturelles Modell, das auf der Dynamik der Collatz-Folge basiert.

• Odd-Block-Zerlegung: Für eine ungerade Zahl $m$ gilt $3m+1 = 2^{K(m)} \cdot m'$, wobei$m'$wieder ungerade ist und$K(m) = v_2(3m+1)$ die Anzahl der Teilungen durch 2 angibt.
• Stochastische Approximation: Anstatt die deterministische Abhängigkeit von $K(m)$ exakt zu berechnen, wird $K(m)$ durch eine stochastische Variable $K$ ersetzt, die einer Wahrscheinlichkeitsverteilung $p_k$ folgt.
• Generativer Prozess: Die Dynamik wird als Zufallsprozess modelliert, bei dem die Blocklängen $K_j$ zufällig gezogen werden.
• Kalibrierung:
  • G1 (Basis): Annahme einer geometrischen Verteilung $P(K=k) \approx 2^{-k}$.
  • G2 (Global): Die Verteilung $p_k$ wird empirisch aus den Daten geschätzt (Dirichlet-Multinomial-Update).
  • G3 (Konditional): Die Verteilung $p_k$ wird zusätzlich auf die Restklasse $m \pmod 8$ konditioniert, um die arithmetische Struktur explizit zu berücksichtigen.

3. Wichtige Ergebnisse

Die Modelle wurden auf einem zurückgehaltenen Testdatensatz ($N_{test} = 50.000$) verglichen, unter Verwendung des logarithmischen Vorhersagescores (Log Predictive Score) und der Wasserstein-Distanz (W1) zur Bewertung der Verteilungsgüte.

Modell	Log Score (höher besser)	W1-Distanz (niedriger besser)	Interpretation
NB2-GLM (M3)	-272.912	3,20	Beste Vorhersagegenauigkeit. Das Modell erfasst die Verteilungsform und die Heterogenität am besten.
Odd-Block G3 (konditional)	-1.079.087	5,43	Deutlich besser als G2, aber schlechter als Regression. Zeigt, dass $m \pmod 8$ entscheidend ist.
Odd-Block G2 (global)	-1.165.983	17,59	Schlechte Anpassung, da die arithmetische Heterogenität ignoriert wird.

Schlüsselerkenntnisse:

1. Überdispersion: Die Varianz von $\tau(n)$ ist etwa das 24,5-fache des Mittelwerts, was eine Poisson-Verteilung ausschließt und die Wahl der Negative-Binomial-Verteilung bestätigt.
2. Arithmetische Struktur: Die Restklasse modulo 8 ist ein starker Prädiktor. Sowohl im Regressionsmodell (als zufälliger Effekt) als auch im generativen Modell (als Konditionierung) führt die Berücksichtigung von $n \pmod 8$ zu einer drastischen Verbesserung der Modellgüte.
3. Vorhersage vs. Mechanismus: Das NB2-GLM ist rein prädiktiv überlegen. Der generative Odd-Block-Ansatz ist jedoch mechanistisch wertvoll, da er erklärt, warum die Heterogenität existiert (durch die Abhängigkeit der Blocklängen $K$ von der Restklasse).

4. Technische Details und Implementierung

• Datenerstellung: Die Berechnung von $\tau(n)$ für $10^7$ Zahlen erfolgte effizient durch dynamische Programmierung (Wiederverwendung bereits berechneter Werte bei Kollisionen von Trajektorien) und JIT-Kompilierung mit Numba.
• Inferenz: Für das NB2-GLM wurden schwach informative Priors verwendet und 2 MCMC-Ketten mit je 1000 Tuning-Schritten und 1000 Ziehungen gefahren.
• Generative Evaluation: Der Log-Score für die generativen Modelle wurde über Monte-Carlo-Simulationen ($S_{MC} = 40$ Replikationen pro Testpunkt) approximiert, da die geschlossene Form der Verteilung nicht verfügbar ist.

5. Bedeutung und Fazit

Das Paper demonstriert erfolgreich, wie probabilistische Machine-Learning-Methoden verwendet werden können, um die statistischen Eigenschaften eines klassischen mathematischen offenen Problems zu analysieren.

• Beitrag zur Statistik: Es zeigt, dass selbst bei deterministischen Systemen (wie der Collatz-Folge) „Working Likelihoods" (Arbeits-Likelihoods) nützlich sind, um Unsicherheit zu quantifizieren und Muster in großen Datensätzen zu erklären.
• Erkenntnisgewinn: Die Studie bestätigt, dass die scheinbar chaotische Natur der Collatz-Folge starke, niedrigdimensionale arithmetische Strukturen ($n \pmod 8$) aufweist, die durch einfache probabilistische Modelle erfasst werden können.
• Zukunftsausblick: Die Autoren schlagen vor, die Konditionierung auf höhere Potenzen von 2 zu erweitern und die Abhängigkeit der Blocklängen explizit vom Zustand $m$ zu modellieren, um die Lücke zwischen rein prädiktiver Genauigkeit und mechanistischer Interpretierbarkeit weiter zu schließen.

Zusammenfassend liefert das Paper einen robusten Beweis dafür, dass die Heterogenität der Collatz-Stoppzeiten primär durch eine Kombination aus logarithmischem Skaleneffekt und modularer Arithmetik (insbesondere modulo 8) getrieben wird, und bietet einen Rahmen für die quantitative Bewertung solcher heuristischer Modelle.