Perelman hat Zeit.

Wie kriegst du da den Münzwurf rein?

Hallo Tommy,



im Prinzip ist "vollständige Induktion" bzw etwas allgemeiner
ein rekursiver Ansatz eine gute Idee - auch für Systeme mit
Zufall.

Hier ist mal ein Beispiel aus einem etwas anderen Bereich:
Betrachtet wird ein Partikel, was auf den natürlichen Zahlen
einen Random Walk mit Drift nach links aufführt.

Bei 0 wird das Partikel absorbiert.
Steht es bei i > 0, so geht es im nächsten Schritt mit Wahrscheinlichkeit
2/3 nach i-1, und mit W-keit 1/3 nach i+1.

Es ist lange bekannt (und auch intuitiv), dass das Partikel, wenn es bei
einem n > 0 startet, mit W-keit 1 in endlich vielen Schritten bei 0 absorbiert wird.

Und jetzt kommt der rekursive Ansatz ins Spiel: Man kann sogar ziemlich
leicht die erwartete Schrittzahl bis zur Absorption berechnen, über das
Gleichungssystem

a(0) = 0.
a(i) = 1 + 2/3 * a(i-1) + 1/3 * a(i+1)  für alle i > 0.

Dieses lineare Gleichungssystem hat unendlich viele Variablen,
aber nur eine Lösung, in der die a(i) "vernünftig" anwachsen.
Nämlich a(i) = 3*i für alle i > 0.

Das sieht man so: Ist außer a(0) auch a(1) festgelegt, sind auch
alle a(i) für i > 1 festgelegt.

Das sieht man ein, wenn man die Gleichungen oben für i umstellt:
1/3 * a(i+1) = a(i) - 1 - 2/3 * a(i-1).

Wenn man jetzt verschiedene Werte für a(1) probiert, macht
nur a(1) = 3 Sinn.

*********************

Für das Collatz-Problem mit zufälliger Anwendung von 3n+1 und 3n-1
lässt sich auch ein unendliches lineares Gleichungssystem aufstellen,
mit einer Gleichung für jedes i.
Leider ist es nicht so einfach strukturiert wie das für den Random Walk
mit Drift.

Viele Grüße, Ingo.