The implementations evaluate a function \(f(a,b)\) for the asymmetric random walk that moves \(+b\) or \(-a\) with probability \(1/2\) at each step. For the two concrete pairs that appear in the implementations, \((1,2)\) for validation and \((89,97)\) for the final answer, the numbers \(a\) and \(b\) are coprime. In that setting, every positive return to the origin happens after a multiple of \(a+b\) steps.
The quantity being computed is not a raw infinite sum for its own sake. That sum is the total return kernel at the origin, and its reciprocal is the probability that the walk never returns to its starting point. The whole problem is therefore about converting return probabilities into a rapidly convergent series that can be evaluated with high-precision arithmetic.
The code reveals a very specific structure: it keeps a running series whose \(n\)-th nontrivial term is the probability of being back at 0 after \((a+b)n\) steps. Once that interpretation is made explicit, the rest of the derivation is standard but elegant.
Let the walk start at 0. After \(R\) jumps of size \(+b\) and \(L\) jumps of size \(-a\), the position is
$$bR-aL.$$
A return to the origin therefore requires
$$bR=aL.$$
For the coprime inputs used here, this forces
$$R=an,\qquad L=bn$$
for some integer \(n\ge 0\). Hence every return time is of the form
$$N=(a+b)n.$$
This is the key invariant of the problem: the walk can only revisit 0 when the numbers of right and left steps occur in the fixed ratio \(a:b\).
Let
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1.$$
To be back at 0 after \((a+b)n\) steps, the walk must contain exactly \(an\) right jumps and \(bn\) left jumps. Every sequence of that type has probability \(2^{-(a+b)n}\), and the number of such sequences is \(\binom{(a+b)n}{an}\). Therefore
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
The implementations do not recompute this from factorials every time. Instead they use the ratio
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
This is exactly the multiplicative update visible in all three language versions.
Let \(r_n\) be the probability that the first return to 0 occurs at time \((a+b)n\). Then every return can be decomposed by the time of the first return:
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
Introduce generating functions
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n.$$
The convolution above gives
$$U(z)=1+R(z)U(z),\qquad\text{so}\qquad U(z)=\frac{1}{1-R(z)}.$$
Setting \(z=1\) yields
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}.$$
Here \(R(1)\) is the total probability of ever coming back to the origin, so the probability of never returning is
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
This reciprocal is exactly what the implementations return.
If \(a=b\), then
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
The series \(\sum u_n\) diverges, which means the walk returns to the origin with probability 1. Consequently
$$f(a,a)=0.$$
When \(a\ne b\), Stirling's formula gives
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}.$$
Weighted AM-GM shows \(\lambda<1\) unless \(a=b\), so the asymmetric case converges exponentially fast. That is why a strict cutoff such as \(10^{-80}\) is more than enough for a 9-decimal final answer.
The first positive return can only happen after 3 steps, with one \(+2\) move and two \(-1\) moves. Hence
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
After 6 steps, the walk must contain two \(+2\) moves and four \(-1\) moves, so
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
Therefore
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots,$$
and the escape probability is
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272.$$
This is the same check value used by the implementations before evaluating the target pair \((89,97)\).
The C++, Python, and Java implementations begin with the trivial symmetric case \(a=b\), where the answer is immediately 0. Otherwise they precompute \(2^{a+b}\) once, initialize the current term to \(u_0=1\), and then update each new \(u_n\) multiplicatively from \(u_{n-1}\) using the ratio above. This avoids repeatedly forming enormous factorials or binomial coefficients.
A running sum starts at 1, corresponding to the walk being at the origin at time 0. Each loop iteration multiplies by the next ratio, adds the new term to the total, and thereby builds
$$U(1)=\sum_{n\ge 0}u_n.$$
At the end, the implementation returns \(1/U(1)\), which is the escape probability derived above.
All three implementations use about 100 decimal digits of working precision. They stop when the newest term drops below \(10^{-80}\), leaving a very comfortable margin before the final 9-digit rounding. The two built-in checks also reflect the mathematics: the symmetric case \((1,1)\) must give 0, and the asymmetric case \((1,2)\) must reproduce the known probability above.
If \(L\) terms are needed before the threshold is reached, each term requires \(O(a+b)\) high-precision multiplications and divisions, because the ratio contains \(a+b\) numerator factors and \(a+b\) denominator factors in total. The running time is therefore
$$O(L(a+b)).$$
The extra memory usage is \(O(1)\): the implementation stores only the current term, the cumulative sum, the fixed power \(2^{a+b}\), and a few scalar temporaries. For the target input the convergence is rapid, so the practical cost is very small.
Die Implementierungen werten eine Funktion \(f(a,b)\) für einen asymmetrischen Random Walk aus, der in jedem Schritt mit Wahrscheinlichkeit \(1/2\) um \(+b\) oder um \(-a\) springt. Für die beiden konkret verwendeten Paare, \((1,2)\) als Validierung und \((89,97)\) für das Endergebnis, sind \(a\) und \(b\) teilerfremd. Dann kann eine positive Rückkehr zum Ursprung nur nach einem Vielfachen von \(a+b\) Schritten auftreten.
Die berechnete Größe ist nicht bloß eine beliebige unendliche Reihe. Diese Reihe ist die gesamte Rückkehrmasse am Ursprung, und ihr Kehrwert ist die Wahrscheinlichkeit, dass der Walk nie wieder zu seinem Startpunkt zurückkehrt. Genau deshalb lohnt es sich, die Rückkehrwahrscheinlichkeiten in eine schnell konvergierende numerische Auswertung umzuschreiben.
Der Code legt eine sehr präzise mathematische Struktur offen: Das \(n\)-te nichttriviale Reihenglied ist die Wahrscheinlichkeit, nach \((a+b)n\) Schritten wieder bei 0 zu stehen. Sobald man das erkennt, lassen sich Invariante, Rekurrenz und Grenzfall sauber herleiten.
Der Walk starte bei 0. Nach \(R\) Sprüngen der Länge \(+b\) und \(L\) Sprüngen der Länge \(-a\) ist die Position
$$bR-aL.$$
Für eine Rückkehr zum Ursprung muss also gelten
$$bR=aL.$$
Bei den hier benutzten teilerfremden Eingaben folgt daraus
$$R=an,\qquad L=bn$$
für ein \(n\ge 0\). Jede Rückkehrzeit hat damit die Form
$$N=(a+b)n.$$
Das ist die entscheidende Invariante des Problems: Nur wenn rechte und linke Schritte im festen Verhältnis \(a:b\) vorkommen, kann die Summe wieder 0 werden.
Definiere
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1.$$
Um nach \((a+b)n\) Schritten wieder 0 zu erreichen, muss die Folge genau \(an\) rechte und \(bn\) linke Sprünge enthalten. Jede solche Folge hat Wahrscheinlichkeit \(2^{-(a+b)n}\), und ihre Anzahl ist \(\binom{(a+b)n}{an}\). Also
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
Die Implementierungen berechnen diese Werte nicht jedes Mal neu aus Fakultäten. Stattdessen verwenden sie die Quotientenformel
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
Genau dieser multiplikative Schritt steht in allen drei Sprachversionen.
Sei \(r_n\) die Wahrscheinlichkeit, dass die erste Rückkehr nach 0 genau zur Zeit \((a+b)n\) stattfindet. Dann zerlegt sich jede Rückkehr nach dem Zeitpunkt der ersten Rückkehr:
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
Mit den erzeugenden Funktionen
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n$$
folgt daraus
$$U(z)=1+R(z)U(z),\qquad\text{also}\qquad U(z)=\frac{1}{1-R(z)}.$$
Setzt man \(z=1\), erhält man
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}.$$
\(R(1)\) ist die Gesamtwahrscheinlichkeit, den Ursprung irgendwann wieder zu treffen. Daher ist die Wahrscheinlichkeit, nie zurückzukehren, gleich
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
Genau diesen Kehrwert liefern die Implementierungen.
Für \(a=b\) gilt
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
Die Reihe \(\sum u_n\) divergiert, also kehrt der Walk mit Wahrscheinlichkeit 1 zurück. Folglich ist
$$f(a,a)=0.$$
Für \(a\ne b\) liefert die Stirling-Approximation
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}.$$
Mit gewichteter AM-GM-Ungleichung folgt \(\lambda<1\), solange \(a\ne b\). Deshalb konvergiert der asymmetrische Fall exponentiell schnell, und ein Abbruch bei \(10^{-80}\) ist weit strenger als für 9 Nachkommastellen nötig.
Die erste positive Rückkehr kann erst nach 3 Schritten erfolgen, nämlich mit einem \(+2\)-Sprung und zwei \(-1\)-Sprüngen. Also
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
Nach 6 Schritten braucht man zwei \(+2\)-Sprünge und vier \(-1\)-Sprünge, also
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
Damit ist
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots,$$
und die Fluchtwahrscheinlichkeit beträgt
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272.$$
Genau dieser Wert dient in den Implementierungen als Kontrollbeispiel, bevor das Zielpaar \((89,97)\) berechnet wird.
Die C++-, Python- und Java-Implementierungen behandeln zuerst den trivialen symmetrischen Fall \(a=b\), in dem die Antwort sofort 0 ist. Andernfalls wird \(2^{a+b}\) einmal vorab berechnet, der aktuelle Term mit \(u_0=1\) initialisiert und jeder neue Wert \(u_n\) multiplikativ aus \(u_{n-1}\) erzeugt. Dadurch vermeidet man das wiederholte Auswerten großer Fakultäten oder Binomialkoeffizienten.
Die laufende Summe startet bei 1, weil der Walk zur Zeit 0 sicher im Ursprung steht. In jeder Iteration wird mit dem nächsten Quotienten multipliziert, der neue Term addiert und so
$$U(1)=\sum_{n\ge 0}u_n$$
aufgebaut. Am Ende wird der Kehrwert \(1/U(1)\) zurückgegeben, also genau die oben hergeleitete Fluchtwahrscheinlichkeit.
Alle drei Implementierungen arbeiten mit ungefähr 100 Dezimalstellen Präzision. Abgebrochen wird, sobald der neueste Term kleiner als \(10^{-80}\) ist; damit bleibt vor der Rundung auf 9 Nachkommastellen ein sehr großer Sicherheitspuffer. Auch die eingebauten Tests spiegeln die Mathematik direkt wider: \((1,1)\) muss 0 liefern, und \((1,2)\) muss die bekannte Wahrscheinlichkeit oben reproduzieren.
Werden bis zur Schranke \(L\) Reihenterme benötigt, so kostet jeder Term \(O(a+b)\) hochpräzise Multiplikationen und Divisionen, weil der Quotient insgesamt \(a+b\) Zählerfaktoren und \(a+b\) Nennerfaktoren enthält. Damit ist die Laufzeit
$$O(L(a+b)).$$
Der zusätzliche Speicherbedarf ist \(O(1)\): gespeichert werden nur der aktuelle Term, die laufende Summe, die feste Potenz \(2^{a+b}\) und einige Skalare. Für die Zielwerte ist die Konvergenz schnell, also bleibt auch der praktische Aufwand klein.
Uygulamalar, her adımda olasılığı \(1/2\) olan iki hamleden birini yapan asimetrik bir rassal yürüyüş için \(f(a,b)\) fonksiyonunu hesaplıyor: ya \(+b\) kadar sağa ya da \(-a\) kadar sola gidiliyor. Kodda görünen iki somut çift, doğrulama için \((1,2)\) ve nihai hesap için \((89,97)\), aralarında asal olduğundan, başlangıç noktasına pozitif zamanda dönüş ancak \(a+b\) adımının katlarında gerçekleşebiliyor.
Hesaplanan büyüklük yalnızca teknik bir sonsuz seri değildir. Bu seri, orijine toplam dönüş kütlesini verir; onun tersi ise yürüyüşün başlangıç noktasına bir daha hiç dönmeme olasılığıdır. Dolayısıyla problem, dönüş olasılıklarını yüksek hassasiyetle ve hızlı yakınsayan bir biçimde toplama problemine indirgenir.
Kodun taşıdığı yapı çok nettir: serinin \(n\). esas terimi, yürüyüşün \((a+b)n\) adım sonra yeniden 0'da olma olasılığıdır. Bu yorum açıkça yazıldığında hem kombinatorik kapalı form hem de yenilenme bağıntısı doğal biçimde ortaya çıkar.
Yürüyüş 0'dan başlasın. \(R\) tane \(+b\) adımı ve \(L\) tane \(-a\) adımı sonrasında konum
$$bR-aL$$
olur. Orijine dönmek için
$$bR=aL$$
gerekir. Burada kullanılan aralarında asal girdiler için bu eşitlik ancak
$$R=an,\qquad L=bn$$
şeklinde sağlanır. Bu yüzden tüm dönüş zamanları
$$N=(a+b)n$$
biçimindedir. Problemdeki temel invariant budur: sağ ve sol adımlar tam olarak \(a:b\) oranında gerçekleşmedikçe toplam yer değiştirme yeniden 0 olamaz.
Şimdi
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1$$
tanımını yapalım. \((a+b)n\) adım sonra 0'da olmak için yürüyüşün tam \(an\) kez sağa, \(bn\) kez sola gitmiş olması gerekir. Böyle her dizi \(2^{-(a+b)n}\) olasılığa sahiptir ve bu dizilerin sayısı \(\binom{(a+b)n}{an}\) olur. Dolayısıyla
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
Uygulamalar bu terimi her seferinde faktöriyellerden üretmez. Bunun yerine şu çarpımsal oranı kullanır:
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
C++, Python ve Java uygulamalarındaki çekirdek güncelleme tam olarak budur.
\(r_n\), ilk kez orijine \((a+b)n\) anında dönme olasılığı olsun. O zaman her dönüş, ilk dönüş zamanına göre ayrıştırılabilir:
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
Üreteç fonksiyonları
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n$$
olarak tanımlanırsa
$$U(z)=1+R(z)U(z),\qquad\text{yani}\qquad U(z)=\frac{1}{1-R(z)}$$
elde edilir. \(z=1\) için
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}$$
olur. Buradaki \(R(1)\), yürüyüşün bir gün orijine geri dönme toplam olasılığıdır. Bu yüzden hiç geri dönmeme olasılığı
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
Kodun sonunda döndürülen değer tam olarak bu ters toplamdır.
\(a=b\) ise
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
Bu durumda \(\sum u_n\) ıraksaktır; yani yürüyüş orijine olasılık 1 ile geri döner. Sonuç olarak
$$f(a,a)=0.$$
\(a\ne b\) için Stirling yaklaşımı
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}$$
verir. Ağırlıklı AM-GM eşitsizliği, \(a\ne b\) iken \(\lambda<1\) olduğunu söyler; bu da asimetrik durumda serinin üstel hızla yakınsadığını gösterir. Bu nedenle \(10^{-80}\) eşiği, 9 ondalık basamak için fazlasıyla güvenlidir.
İlk pozitif dönüş yalnızca 3. adımda olabilir: bir kez \(+2\), iki kez \(-1\). O halde
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
6 adım sonunda ise iki \(+2\) ve dört \(-1\) gerekir, dolayısıyla
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
Böylece
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots$$
olur ve kaçış olasılığı
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272$$
çıkar. Uygulamaların yerleşik doğrulama değeri de budur.
C++, Python ve Java uygulamaları önce \(a=b\) özel durumunu yakalar; bu durumda sonuç doğrudan 0'dır. Aksi halde \(2^{a+b}\) bir kez hesaplanır, mevcut terim \(u_0=1\) ile başlatılır ve her yeni \(u_n\), yukarıdaki oran aracılığıyla \(u_{n-1}\)'den çarpımsal olarak üretilir. Böylece devasa faktöriyel veya binom katsayıları tekrar tekrar kurulmaz.
Toplam 1 ile başlar; bu, zaman 0'da orijinde olmanın kesinliğidir. Her döngüde yeni oranla çarpılır, yeni terim eklenir ve böylece
$$U(1)=\sum_{n\ge 0}u_n$$
toplanır. Son adımda bunun tersi alınır; yani doğrudan kaçış olasılığı elde edilir.
Üç uygulama da yaklaşık 100 ondalık basamaklık çalışma hassasiyeti kullanır. Yeni terim \(10^{-80}\)'in altına düştüğünde döngü sonlanır; bu, 9 basamaklı son yuvarlama için çok rahat bir güvenlik payı bırakır. Yerleşik kontroller de matematikle tam uyumludur: \((1,1)\) durumu 0 vermeli, \((1,2)\) durumu ise yukarıdaki bilinen olasılığı yeniden üretmelidir.
Eşiğe ulaşmak için \(L\) terim gerekiyorsa, her terim \(O(a+b)\) adet yüksek hassasiyetli çarpma ve bölme ister; çünkü oran ifadesinde toplam \(a+b\) pay ve \(a+b\) payda faktörü vardır. Bu nedenle çalışma süresi
$$O(L(a+b)).$$
Ek bellek kullanımı \(O(1)\)'dir: yalnızca güncel terim, biriken toplam, sabit \(2^{a+b}\) değeri ve birkaç skaler tutulur. Hedef girdi için yakınsama hızlı olduğundan pratik maliyet küçüktür.
Las implementaciones evalúan una función \(f(a,b)\) asociada a una caminata aleatoria asimétrica que en cada paso salta \(+b\) o \(-a\) con probabilidad \(1/2\). En los dos pares concretos usados por el código, \((1,2)\) para validar y \((89,97)\) para la respuesta final, \(a\) y \(b\) son coprimos. En ese caso, cualquier regreso positivo al origen sólo puede ocurrir tras un múltiplo de \(a+b\) pasos.
La suma infinita que aparece en el código no es un artificio numérico sin interpretación. Esa suma es la masa total de retorno al origen, y su recíproco es la probabilidad de no volver jamás al punto inicial. Por eso el problema consiste en transformar probabilidades de retorno en una serie que converja muy deprisa y pueda sumarse con gran precisión.
La estructura matemática implícita en el código es muy concreta: el término no trivial número \(n\) es la probabilidad de estar otra vez en 0 después de \((a+b)n\) pasos. A partir de ahí aparecen de forma natural la restricción combinatoria, la recurrencia multiplicativa y la interpretación mediante primer retorno.
Supongamos que la caminata empieza en 0. Después de \(R\) saltos de tamaño \(+b\) y \(L\) saltos de tamaño \(-a\), la posición vale
$$bR-aL.$$
Para volver al origen es necesario que
$$bR=aL.$$
Como en los casos usados aquí \(a\) y \(b\) son coprimos, esto obliga a
$$R=an,\qquad L=bn$$
para algún \(n\ge 0\). Por tanto, todo retorno ocurre en tiempos
$$N=(a+b)n.$$
Éste es el invariante central del problema: el paseo sólo puede compensar su desplazamiento si los pasos hacia la derecha y hacia la izquierda aparecen exactamente en la proporción \(a:b\).
Definimos
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1.$$
Para estar en 0 tras \((a+b)n\) pasos, la secuencia debe contener exactamente \(an\) saltos a la derecha y \(bn\) saltos a la izquierda. Cada secuencia así tiene probabilidad \(2^{-(a+b)n}\), y el número de secuencias posibles es \(\binom{(a+b)n}{an}\). Luego
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
Las implementaciones no recalculan esta expresión desde factoriales en cada iteración. Usan directamente el cociente
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
Ésa es exactamente la actualización multiplicativa visible en C++, Python y Java.
Sea \(r_n\) la probabilidad de que el primer retorno a 0 ocurra en el instante \((a+b)n\). Entonces cualquier retorno se descompone por el momento del primer retorno:
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
Si introducimos las funciones generadoras
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n,$$
obtenemos
$$U(z)=1+R(z)U(z),\qquad\text{y por tanto}\qquad U(z)=\frac{1}{1-R(z)}.$$
Al evaluar en \(z=1\) resulta
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}.$$
\(R(1)\) es la probabilidad total de volver alguna vez al origen, así que la probabilidad de no regresar nunca es
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
Ésta es exactamente la cantidad que devuelve la implementación.
Si \(a=b\), entonces
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
La serie \(\sum u_n\) diverge, lo que significa que la caminata vuelve al origen con probabilidad 1. En consecuencia,
$$f(a,a)=0.$$
Cuando \(a\ne b\), la fórmula de Stirling da
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}.$$
La desigualdad AM-GM ponderada muestra que \(\lambda<1\) salvo en el caso simétrico, así que la serie converge exponencialmente rápido. Por eso un corte en \(10^{-80}\) deja margen de sobra para redondear a 9 decimales.
El primer retorno positivo sólo puede ocurrir tras 3 pasos: un salto \(+2\) y dos saltos \(-1\). Por tanto
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
Tras 6 pasos hacen falta dos saltos \(+2\) y cuatro saltos \(-1\), luego
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
Así,
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots,$$
y la probabilidad de escape es
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272.$$
Ese mismo valor aparece como comprobación numérica antes de calcular el caso objetivo \((89,97)\).
Las versiones en C++, Python y Java empiezan detectando el caso simétrico \(a=b\), donde la respuesta es inmediatamente 0. Si no, precalculan \(2^{a+b}\), fijan el término actual en \(u_0=1\) y generan cada \(u_n\) a partir de \(u_{n-1}\) con el cociente anterior. Así evitan construir factoriales o coeficientes binomiales gigantes en cada paso.
La suma acumulada arranca en 1, que corresponde a estar en el origen en el instante inicial. En cada iteración se multiplica por el siguiente cociente, se añade el nuevo término y se construye
$$U(1)=\sum_{n\ge 0}u_n.$$
Al final se devuelve el recíproco \(1/U(1)\), es decir, la probabilidad de escape.
Las tres implementaciones trabajan con unas 100 cifras decimales de precisión. El bucle se detiene cuando el término recién añadido cae por debajo de \(10^{-80}\), de modo que el error de cola es insignificante comparado con la salida final de 9 decimales. Las comprobaciones internas siguen directamente la teoría: \((1,1)\) debe dar 0 y \((1,2)\) debe reproducir la probabilidad conocida anterior.
Si hacen falta \(L\) términos hasta alcanzar el umbral, cada término cuesta \(O(a+b)\) operaciones de multiplicación y división con precisión alta, porque el cociente contiene \(a+b\) factores en el numerador y \(a+b\) en los denominadores en conjunto. Por ello, el tiempo total es
$$O(L(a+b)).$$
La memoria adicional es \(O(1)\): sólo se guardan el término actual, la suma acumulada, la potencia fija \(2^{a+b}\) y unas pocas variables escalares. En la práctica, el caso objetivo converge deprisa.
这些实现计算的是非对称随机游走对应的函数 \(f(a,b)\)。每一步都以概率 \(1/2\) 向右跳 \(+b\)，或向左跳 \(-a\)。实现里真正出现的两个参数对分别是验证用的 \((1,2)\) 和最终求值用的 \((89,97)\)，它们都是互素的，因此一旦游走在正时间重新回到原点，返回时刻必定是 \(a+b\) 的倍数。
代码中的无穷级数不是随便选出来的数值技巧。它表示原点处的总返回权重，而它的倒数正是“从起点出发后永不再回到起点”的概率。于是题目的核心就变成：先把返回原点的概率写成封闭形式，再把这组概率稳定而高精度地求和。
从实现可以直接看出一个很清楚的结构：第 \(n\) 个非平凡项，就是游走在 \((a+b)n\) 步后回到 0 的概率。只要把这一点说清楚，问题中的状态空间、递推关系和收敛性都会自然地连起来。
设游走从 0 出发。若其中有 \(R\) 次走 \(+b\)，有 \(L\) 次走 \(-a\)，那么当前位置是
$$bR-aL.$$
要回到原点，必须满足
$$bR=aL.$$
对于这里使用的互素输入，这就强制得到
$$R=an,\qquad L=bn$$
其中 \(n\ge 0\)。因此所有返回原点的时刻都只能是
$$N=(a+b)n.$$
这就是本题最重要的不变量：只有当向右和向左的步数严格按 \(a:b\) 的比例出现时，累计位移才可能重新变成 0。
定义
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1.$$
在 \((a+b)n\) 步后回到 0，等价于这段路径里恰好有 \(an\) 次向右跳和 \(bn\) 次向左跳。每一条这样的路径概率都是 \(2^{-(a+b)n}\)，而满足条件的路径总数是 \(\binom{(a+b)n}{an}\)。于是
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
实现并没有在每一步重新计算大阶乘，而是使用相邻两项之间的乘法递推：
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
这正是三种语言实现里循环更新的核心公式。
记 \(r_n\) 为“第一次回到 0 恰好发生在 \((a+b)n\) 步”这一事件的概率。任何一次返回都可以按第一次返回的时刻分解，因此
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
再定义生成函数
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n,$$
则有
$$U(z)=1+R(z)U(z),\qquad\text{所以}\qquad U(z)=\frac{1}{1-R(z)}.$$
把 \(z=1\) 代入得到
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}.$$
这里的 \(R(1)\) 是“最终某时会回到原点”的总概率，因此永不返回的概率就是
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
这说明实现最终返回的不是别的量，而正是这条非对称随机游走的逃逸概率。
当 \(a=b\) 时，
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
因此级数 \(\sum u_n\) 发散，也就是说游走以概率 1 反复回到原点，所以
$$f(a,a)=0.$$
而在 \(a\ne b\) 时，由 Stirling 公式可以得到
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}.$$
加权 AM-GM 不等式说明只要 \(a\ne b\)，就有 \(\lambda<1\)。因此非对称情形的级数按指数速度衰减，代码使用 \(10^{-80}\) 作为截断阈值，对最终保留 9 位小数来说绰绰有余。
第一次正时间返回只能发生在 3 步之后，此时必须有 1 次 \(+2\) 和 2 次 \(-1\)。所以
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
在 6 步之后，要回到 0 就必须有 2 次 \(+2\) 和 4 次 \(-1\)，从而
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
于是
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots,$$
对应的逃逸概率为
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272.$$
这正是实现里用于校验的数值，然后才继续计算目标参数 \((89,97)\)。
C++、Python 和 Java 三个实现都会先处理 \(a=b\) 的特殊情形，此时答案立刻就是 0。否则先预计算 \(2^{a+b}\)，把当前项设为 \(u_0=1\)，再利用上面的相邻项比值从 \(u_{n-1}\) 递推出 \(u_n\)。这样就不需要在循环里反复构造巨大的阶乘或二项式系数。
累计和从 1 开始，因为时刻 0 一定在原点。每次迭代先乘上下一个比值，再把新项加入总和，从而构造出
$$U(1)=\sum_{n\ge 0}u_n.$$
最后返回其倒数 \(1/U(1)\)，也就是上面推导出的逃逸概率。
三个实现都采用大约 100 位十进制工作精度。当最新一项小于 \(10^{-80}\) 时就停止循环，因此尾部误差相对于最终 9 位小数的输出几乎可以忽略。内置检查也直接对应理论：\((1,1)\) 必须得到 0，而 \((1,2)\) 必须重现上面的已知概率。
如果达到截断阈值前需要 \(L\) 项，那么每一项都要做 \(O(a+b)\) 次高精度乘除，因为比值公式一共含有 \(a+b\) 个分子因子以及总计 \(a+b\) 个分母因子。因此总时间复杂度是
$$O(L(a+b)).$$
额外空间复杂度是 \(O(1)\)：只需要保存当前项、累计和、固定的 \(2^{a+b}\) 以及少量标量。对目标输入来说，收敛速度很快，所以实际开销很小。
Реализации вычисляют функцию \(f(a,b)\), связанную с асимметричным случайным блужданием: на каждом шаге процесс с вероятностью \(1/2\) сдвигается либо на \(+b\), либо на \(-a\). Для двух пар, которые действительно используются в вычислениях, \((1,2)\) для проверки и \((89,97)\) для окончательного ответа, числа \(a\) и \(b\) взаимно просты. Поэтому возврат в ноль в положительный момент времени возможен только после числа шагов, кратного \(a+b\).
Бесконечный ряд в коде не является случайной численной конструкцией. Это суммарная масса возвратов в ноль, а её обратная величина есть вероятность никогда больше не вернуться в начальную точку. Значит, задача сводится к точному описанию вероятностей возврата и к устойчивому суммированию быстро убывающего ряда.
Код фактически показывает, что \(n\)-й нетривиальный член ряда равен вероятности оказаться в нуле через \((a+b)n\) шагов. После этого естественно появляются и инвариант, и замкнутая формула, и связь с вероятностью первого возвращения.
Пусть блуждание стартует из 0. После \(R\) прыжков величины \(+b\) и \(L\) прыжков величины \(-a\) положение равно
$$bR-aL.$$
Чтобы снова оказаться в нуле, необходимо
$$bR=aL.$$
Для взаимно простых параметров, используемых здесь, отсюда следует
$$R=an,\qquad L=bn$$
для некоторого \(n\ge 0\). Поэтому каждый момент возврата имеет вид
$$N=(a+b)n.$$
Это и есть главный инвариант задачи: вернуться в 0 можно только тогда, когда числа шагов вправо и влево находятся в фиксированном отношении \(a:b\).
Обозначим
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1.$$
Чтобы быть в нуле после \((a+b)n\) шагов, траектория должна содержать ровно \(an\) шагов вправо и \(bn\) шагов влево. Каждая такая последовательность имеет вероятность \(2^{-(a+b)n}\), а число таких последовательностей равно \(\binom{(a+b)n}{an}\). Следовательно,
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
Реализации не пересчитывают это выражение через факториалы на каждом шаге. Вместо этого используется отношение соседних членов:
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
Именно этот мультипликативный переход присутствует во всех трёх версиях реализации.
Пусть \(r_n\) обозначает вероятность того, что первое возвращение в ноль произойдёт ровно в момент \((a+b)n\). Тогда любой возврат можно разложить по времени первого возврата:
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
Введём производящие функции
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n.$$
Из свёртки следует
$$U(z)=1+R(z)U(z),\qquad\text{то есть}\qquad U(z)=\frac{1}{1-R(z)}.$$
Подстановка \(z=1\) даёт
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}.$$
Величина \(R(1)\) есть полная вероятность когда-нибудь снова попасть в ноль, поэтому вероятность никогда не вернуться равна
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
Именно это число и возвращают реализации.
Если \(a=b\), то
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
Ряд \(\sum u_n\) расходится, а значит, блуждание возвращается в ноль с вероятностью 1. Следовательно,
$$f(a,a)=0.$$
При \(a\ne b\) формула Стирлинга даёт
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}.$$
Взвешенное неравенство AM-GM показывает, что при \(a\ne b\) выполнено \(\lambda<1\). Поэтому асимметричный случай сходится экспоненциально быстро, и отсечение при \(10^{-80}\) более чем достаточно для вывода с 9 десятичными знаками.
Первый положительный возврат может произойти только через 3 шага: нужен один шаг \(+2\) и два шага \(-1\). Поэтому
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
Через 6 шагов для возврата нужны два шага \(+2\) и четыре шага \(-1\), так что
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
Отсюда
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots,$$
а вероятность никогда не вернуться равна
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272.$$
Это ровно то контрольное значение, которое проверяется перед вычислением целевой пары \((89,97)\).
Реализации на C++, Python и Java сначала обрабатывают тривиальный симметричный случай \(a=b\), где ответ сразу равен 0. Иначе один раз вычисляется \(2^{a+b}\), текущий член инициализируется как \(u_0=1\), а каждый следующий \(u_n\) получается из \(u_{n-1}\) умножением на приведённое выше отношение. Это избавляет от постоянного пересчёта гигантских факториалов и биномиальных коэффициентов.
Накопленная сумма начинается с 1, потому что в момент 0 блуждание гарантированно находится в начале. На каждой итерации вычисляется следующий член, он добавляется к сумме, и тем самым строится
$$U(1)=\sum_{n\ge 0}u_n.$$
После завершения цикла берётся обратная величина \(1/U(1)\), то есть искомая вероятность ухода без возврата.
Во всех трёх реализациях используется около 100 десятичных знаков рабочей точности. Цикл останавливается, когда очередной член становится меньше \(10^{-80}\), поэтому вклад хвоста ничтожен по сравнению с окончательным округлением до 9 знаков после запятой. Встроенные проверки тоже напрямую отражают математику: \((1,1)\) должно давать 0, а \((1,2)\) должно воспроизводить указанное выше известное значение.
Если до достижения порога требуется \(L\) членов, то вычисление каждого члена стоит \(O(a+b)\) операций умножения и деления с высокой точностью, потому что в отношении есть \(a+b\) множителей в числителе и в сумме \(a+b\) множителей в знаменателях. Следовательно, общее время работы равно
$$O(L(a+b)).$$
Дополнительная память равна \(O(1)\): хранятся только текущий член, накопленная сумма, фиксированная степень \(2^{a+b}\) и несколько скаляров. Для целевого ввода сходимость быстрая, поэтому практическая стоимость мала.
تحسب التطبيقات الدالة \(f(a,b)\) المرتبطة بمشية عشوائية غير متناظرة: في كل خطوة يتحرك المسار بمقدار \(+b\) أو \(-a\) باحتمال \(1/2\) لكل منهما. الزوجان الظاهران فعليًا في التنفيذ هما \((1,2)\) من أجل التحقق و\((89,97)\) من أجل الناتج النهائي، وهما عددان أوليان نسبيًا في كلتا الحالتين. لذلك فإن أي عودة موجبة إلى الأصل لا يمكن أن تحدث إلا بعد عدد من الخطوات يساوي مضاعفًا لـ \(a+b\).
المتسلسلة اللانهائية في الكود ليست مجرد حيلة عددية. إنها تمثل الكتلة الكلية لاحتمالات العودة إلى الأصل، ومقلوبها يساوي احتمال ألا تعود المشية إلى نقطة البداية أبدًا. ومن ثم فجوهر المسألة هو تحويل احتمالات العودة إلى سلسلة سريعة التقارب يمكن جمعها بدقة عالية.
يكشف الكود عن بنية رياضية دقيقة: الحد غير التافه رقم \(n\) هو احتمال أن تكون المشية عند الصفر بعد \((a+b)n\) خطوة. وبمجرد فهم ذلك تصبح صيغة العد، والعلاقة التراجعية، وتفسير الاحتمال النهائي أمورًا طبيعية.
لنفرض أن المشية تبدأ من 0. بعد \(R\) خطوة من النوع \(+b\) و\(L\) خطوة من النوع \(-a\)، يكون الموضع
$$bR-aL.$$
ولكي تعود المشية إلى الأصل يجب أن يتحقق
$$bR=aL.$$
وبما أن المدخلات المستخدمة هنا أولية نسبيًا، فإن هذا يفرض
$$R=an,\qquad L=bn$$
لبعض \(n\ge 0\). لذلك فإن كل زمن عودة له الصورة
$$N=(a+b)n.$$
وهذا هو الثابت الأساسي في المسألة: لا يمكن أن ينعدم الإزاحة الكلية من جديد إلا إذا ظهرت الخطوات إلى اليمين واليسار بالنسبة الدقيقة \(a:b\).
لنعرّف
$$u_n=\Pr(X_{(a+b)n}=0),\qquad u_0=1.$$
العودة إلى الصفر بعد \((a+b)n\) خطوة تعني أن المسار احتوى بالضبط على \(an\) خطوة إلى اليمين و\(bn\) خطوة إلى اليسار. كل ترتيب من هذا النوع له احتمال \(2^{-(a+b)n}\)، وعدد هذه الترتيبات يساوي \(\binom{(a+b)n}{an}\). ومن ثم
$$u_n=\frac{1}{2^{(a+b)n}}\binom{(a+b)n}{an}.$$
لا تعيد التطبيقات حساب هذه القيمة من الصفر باستخدام المضروبات في كل مرة، بل تستعمل نسبة حدين متتاليين:
$$\frac{u_n}{u_{n-1}}=\frac{\prod_{i=1}^{a+b}\bigl((a+b)(n-1)+i\bigr)}{2^{a+b}\left(\prod_{i=1}^{a}\bigl(a(n-1)+i\bigr)\right)\left(\prod_{i=1}^{b}\bigl(b(n-1)+i\bigr)\right)}.$$
وهذه هي بالضبط القاعدة الضربية الظاهرة في نسخ C++ وPython وJava.
ليكن \(r_n\) احتمال أن تحدث أول عودة إلى الصفر عند الزمن \((a+b)n\). عندئذ يمكن تفكيك كل عودة بحسب زمن العودة الأولى:
$$u_n=\sum_{k=1}^{n} r_k\,u_{n-k}\qquad (n\ge 1).$$
إذا عرّفنا الدالتين المولّدتين
$$U(z)=\sum_{n\ge 0}u_n z^n,\qquad R(z)=\sum_{n\ge 1}r_n z^n,$$
فإن العلاقة السابقة تعطي
$$U(z)=1+R(z)U(z).$$
ومن ثم
$$U(z)=\frac{1}{1-R(z)}.$$
وعند وضع \(z=1\) نحصل على
$$U(1)=\sum_{n\ge 0}u_n,\qquad R(1)=1-\frac{1}{U(1)}.$$
تمثل \(R(1)\) الاحتمال الكلي للعودة إلى الأصل في وقت ما، ولذلك فإن احتمال عدم العودة أبدًا هو
$$f(a,b)=1-R(1)=\frac{1}{\sum_{n\ge 0}u_n}=\frac{1}{\sum_{n\ge 0}\binom{(a+b)n}{an}\,2^{-(a+b)n}}.$$
وهذه هي القيمة التي تعيدها التطبيقات في النهاية.
إذا كان \(a=b\)، فإن
$$u_n=\frac{1}{2^{2an}}\binom{2an}{an}\sim \frac{1}{\sqrt{\pi an}}.$$
ومن ثم فإن السلسلة \(\sum u_n\) متباعدة، أي إن المشية تعود إلى الأصل باحتمال 1، وبالتالي
$$f(a,a)=0.$$
أما إذا كان \(a\ne b\)، فتعطي صيغة ستيرلينغ
$$u_n\sim \frac{C}{\sqrt{n}}\lambda^n,\qquad \lambda=\frac{(a+b)^{a+b}}{2^{a+b}a^a b^b}.$$
وتبين متباينة AM-GM الموزونة أن \(\lambda<1\) ما دام \(a\ne b\). لذا فإن السلسلة في الحالة غير المتناظرة تتناقص أسيًا، ولهذا فإن حدًا مثل \(10^{-80}\) كافٍ جدًا قبل تقريب الناتج إلى 9 منازل عشرية.
أول عودة موجبة لا يمكن أن تقع إلا بعد 3 خطوات: خطوة واحدة \(+2\) وخطوتان \(-1\). إذًا
$$u_1=\frac{\binom{3}{1}}{2^3}=\frac{3}{8}.$$
وبعد 6 خطوات نحتاج إلى خطوتين \(+2\) وأربع خطوات \(-1\)، وبالتالي
$$u_2=\frac{\binom{6}{2}}{2^6}=\frac{15}{64}.$$
ومن ثم
$$U(1)=1+\frac{3}{8}+\frac{15}{64}+\frac{\binom{9}{3}}{2^9}+\cdots,$$
واحتمال الهروب يساوي
$$f(1,2)=\frac{1}{U(1)}\approx 0.427050983124842272.$$
وهذه هي القيمة المستخدمة في التحقق العددي قبل حساب الزوج المستهدف \((89,97)\).
تبدأ تطبيقات C++ وPython وJava بالتعامل مع الحالة الخاصة \(a=b\)، حيث تكون النتيجة فورًا 0. وفي غير ذلك تُحسب \(2^{a+b}\) مرة واحدة، ويُضبط الحد الحالي على \(u_0=1\)، ثم يُولَّد كل حد جديد \(u_n\) من الحد السابق \(u_{n-1}\) باستعمال النسبة المذكورة أعلاه. بهذا نتجنب تكوين معاملات ثنائية أو مضروبات هائلة في كل دورة.
تبدأ القيمة التراكمية من 1 لأنها تمثل وجود المشية في الأصل عند الزمن 0. وفي كل تكرار يُضرب الحد الحالي في النسبة التالية ويُضاف الناتج إلى المجموع، فتُبنى الكمية
$$U(1)=\sum_{n\ge 0}u_n.$$
وفي النهاية يُعاد المقلوب \(1/U(1)\)، أي احتمال الهروب نفسه.
تستخدم التطبيقات الثلاثة نحو 100 رقم عشري من الدقة أثناء العمل. وتتوقف الحلقة عندما يصبح الحد الجديد أصغر من \(10^{-80}\)، ولذلك يكون تأثير الذيل أصغر بكثير من هامش التقريب النهائي إلى 9 منازل عشرية. كما أن اختبارات التحقق تعكس النظرية مباشرة: يجب أن تعطي \((1,1)\) القيمة 0، ويجب أن تعيد \((1,2)\) القيمة المعروفة المذكورة أعلاه.
إذا احتجنا إلى \(L\) حدود قبل الوصول إلى العتبة، فإن كل حد يكلف \(O(a+b)\) من عمليات الضرب والقسمة عالية الدقة، لأن صيغة النسبة تحتوي على \(a+b\) عاملًا في البسط ومجموع \(a+b\) عاملًا في المقامات. لذلك يكون الزمن الكلي
$$O(L(a+b)).$$
أما الذاكرة الإضافية فهي \(O(1)\) فقط: يُخزَّن الحد الحالي، والمجموع التراكمي، والقيمة الثابتة \(2^{a+b}\)، وبعض المتغيرات العددية البسيطة. وبالنسبة إلى الإدخال المستهدف فإن التقارب سريع جدًا عمليًا.