Consider independent Bernoulli trials with success probability \(p\) and failure probability \(q=1-p\). The process stops as soon as either successes or failures has appeared \(n\) times. If \(T\) denotes that stopping time, then the quantity evaluated by the implementation is
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}.$$
So the problem is to compute a normalized expected remaining score in a first-to-\(n\) race between two complementary outcomes. For small or moderate inputs the value can be summed exactly, while for huge \(n\) with a strong bias one can replace the full stopping-time distribution by a drift-dominant approximation.
The exact formula comes from the distribution of the stopping time \(T\). Because one side reaches count \(n\) first, we always have \(n \le T \le 2n-1\).
Write \(T=n+m\) with \(0\le m\le n-1\). There are two mutually exclusive ways to stop on trial \(n+m\): the last trial can be a failure, or the last trial can be a success.
If the process ends with a failure on trial \(n+m\), then the first \(n+m-1\) trials must contain exactly \(n-1\) failures and \(m\) successes, followed by one more failure. Therefore
$$A_m=\Pr(T=n+m\text{ and stop by a failure})=\binom{n+m-1}{m}p^m q^n.$$
By symmetry, ending with a success has probability
$$B_m=\Pr(T=n+m\text{ and stop by a success})=\binom{n+m-1}{m}q^m p^n.$$
The two branches are disjoint, so
$$\Pr(T=n+m)=A_m+B_m.$$
Since \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\), the quantity being computed can be written either as a normalized expectation
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
or directly as the exact finite sum
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
Because \(2n+1-(n+m)=n+1-m\), this becomes
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right).$$
Computing binomial coefficients from scratch at every step is unnecessary. The two branch terms satisfy
$$A_0=q^n,\qquad B_0=p^n,$$
and for \(m\ge 0\)
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q.$$
This follows from
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}.$$
So the exact mode needs only constant memory: accumulate the current contribution, then advance both terminal probabilities by one recurrence step.
When \(p\) is far from \(\frac12\), one outcome is dominant. Let
$$d=\max(p,q).$$
In that case the process usually ends when the dominant outcome collects its \(n\)-th occurrence, and the stopping time is close to the negative-binomial expectation
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
Substituting this into the normalized form gives the approximation used by the implementation:
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
This is effective when \(n\) is huge and the bias is strong enough that the losing branch contributes negligibly.
The implementation measures the strength of the bias with
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}.$$
The factor \(|1-2p|\) is the drift per trial, while \(\sqrt{npq}\) is the natural fluctuation scale after about \(n\) trials. So \(\delta\) compares deterministic drift against random noise. The exact summation is used when \(n\le 2000\) or \(\delta \lt 15\); otherwise the large-drift approximation is used.
Here \(q=\frac12\). The exact branch terms are
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}.$$
Therefore
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
The normalized value is
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857.$$
This example shows exactly how the weights \(n+1-m\) are paired with the stopping-time probabilities.
The C++, Python, and Java implementations all follow the same hybrid plan. They first compute \(q=1-p\) and the drift score \(\delta\). If the input lies in the exact regime, the program initializes the two terminal-branch probabilities at \(q^n\) and \(p^n\), loops over \(m=0,1,\dots,n-1\), adds the weighted contribution \(\frac{n+1-m}{2n+1}(A_m+B_m)\), and updates both terms by the recurrence above.
If the input lies in the drift-dominant regime, the implementation skips the loop and returns \(\frac{2n+1-n/\max(p,q)}{2n+1}\) directly. All three versions print the final decimal value to ten digits, and the C++ implementation also checks a few smaller benchmark cases before evaluating the huge target input.
The exact regime performs one pass over \(m=0,\dots,n-1\), so it runs in \(O(n)\) time and \(O(1)\) memory. The drift-dominant approximation is \(O(1)\) time and \(O(1)\) memory. The hybrid switch keeps the exact method where cancellation matters and avoids an impossible \(O(n)\) loop when \(n\) is extremely large.
Betrachtet werden unabhängige Bernoulli-Versuche mit Erfolgswahrscheinlichkeit \(p\) und Misserfolgswahrscheinlichkeit \(q=1-p\). Der Prozess endet, sobald entweder die Erfolge oder die Misserfolge zum \(n\)-ten Mal aufgetreten sind. Bezeichnet \(T\) diese Stoppzeit, dann berechnet die Implementierung die Größe
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}.$$
Gesucht ist also ein normierter Erwartungswert für ein First-to-\(n\)-Rennen zwischen zwei komplementären Ausgängen. Für kleine und mittlere Eingaben kann man die Verteilung exakt aufsummieren; für riesige \(n\) mit starkem Bias genügt eine Drift-Näherung.
Die exakte Formel ergibt sich direkt aus der Verteilung der Stoppzeit \(T\). Da eine der beiden Seiten zuerst den Zähler \(n\) erreicht, gilt immer \(n \le T \le 2n-1\).
Schreibe \(T=n+m\) mit \(0\le m\le n-1\). Dann gibt es genau zwei disjunkte Möglichkeiten, auf dem Versuch \(n+m\) zu stoppen: Der letzte Versuch ist ein Misserfolg oder der letzte Versuch ist ein Erfolg.
Endet der Prozess durch einen Misserfolg auf Versuch \(n+m\), dann müssen unter den ersten \(n+m-1\) Versuchen genau \(n-1\) Misserfolge und \(m\) Erfolge liegen, gefolgt von einem weiteren Misserfolg. Daher
$$A_m=\Pr(T=n+m\text{ und Stopp durch Misserfolg})=\binom{n+m-1}{m}p^m q^n.$$
Symmetrisch dazu ist die Erfolgswahrscheinlichkeit
$$B_m=\Pr(T=n+m\text{ und Stopp durch Erfolg})=\binom{n+m-1}{m}q^m p^n.$$
Die beiden Zweige schließen einander aus, also
$$\Pr(T=n+m)=A_m+B_m.$$
Weil \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\), kann die gesuchte Größe entweder als normierter Erwartungswert
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
oder unmittelbar als exakte endliche Summe geschrieben werden:
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
Da \(2n+1-(n+m)=n+1-m\), folgt
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right).$$
Es ist unnötig, in jedem Schritt Binomialkoeffizienten neu zu berechnen. Die beiden Zweigterme erfüllen
$$A_0=q^n,\qquad B_0=p^n,$$
und für \(m\ge 0\)
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q.$$
Das folgt aus
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}.$$
Im exakten Modus reichen also konstanter Speicher und eine lineare Schleife: Beitrag aufsummieren, dann beide Wahrscheinlichkeiten rekursiv fortschreiben.
Liegt \(p\) deutlich von \(\frac12\) entfernt, ist eine Seite dominant. Setze
$$d=\max(p,q).$$
Dann endet der Prozess typischerweise, wenn die dominante Seite ihr \(n\)-tes Auftreten erreicht, und die Stoppzeit liegt nahe beim negativ-binomialen Erwartungswert
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
In die normierte Form eingesetzt ergibt das genau die verwendete Näherung:
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
Diese Näherung ist besonders gut, wenn \(n\) riesig ist und der unterlegene Zweig nur noch einen vernachlässigbaren Beitrag leistet.
Die Implementierung misst die Stärke des Bias durch
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}.$$
Der Faktor \(|1-2p|\) ist die Drift pro Versuch, während \(\sqrt{npq}\) die natürliche Fluktuationsskala nach ungefähr \(n\) Versuchen beschreibt. Damit vergleicht \(\delta\) deterministische Drift mit zufälligem Rauschen. Exakt summiert wird für \(n\le 2000\) oder \(\delta \lt 15\); andernfalls wird die Großdrift-Näherung verwendet.
Hier ist \(q=\frac12\). Die exakten Zweigterme sind
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}.$$
Also gilt
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
Der normierte Wert ist damit
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857.$$
An diesem Beispiel sieht man direkt, wie die Gewichte \(n+1-m\) mit den Stoppwahrscheinlichkeiten gekoppelt werden.
Die C++-, Python- und Java-Implementierungen folgen demselben hybriden Schema. Zuerst werden \(q=1-p\) und der Driftwert \(\delta\) berechnet. Liegt die Eingabe im exakten Bereich, initialisiert das Programm die beiden Endzweig-Wahrscheinlichkeiten mit \(q^n\) und \(p^n\), iteriert über \(m=0,1,\dots,n-1\), addiert den gewichteten Beitrag \(\frac{n+1-m}{2n+1}(A_m+B_m)\) und aktualisiert anschließend beide Terme über die obige Rekurrenz.
Liegt die Eingabe im Drift-Regime, wird die Schleife komplett übersprungen und direkt \(\frac{2n+1-n/\max(p,q)}{2n+1}\) zurückgegeben. Alle drei Versionen formatieren das Ergebnis mit zehn Nachkommastellen; die C++-Variante prüft zusätzlich einige kleinere Vergleichswerte, bevor die große Zieleingabe berechnet wird.
Der exakte Modus durchläuft \(m=0,\dots,n-1\) genau einmal und benötigt deshalb \(O(n)\) Zeit sowie \(O(1)\) Speicher. Die Drift-Näherung kostet \(O(1)\) Zeit und \(O(1)\) Speicher. Der hybride Umschalter bewahrt die exakte Methode dort, wo numerische Auslöschung relevant ist, und vermeidet gleichzeitig eine unpraktikable \(O(n)\)-Schleife bei extrem großem \(n\).
Bağımsız Bernoulli denemeleri düşünelim. Başarı olasılığı \(p\), başarısızlık olasılığı ise \(q=1-p\) olsun. Süreç, başarıların veya başarısızlıkların herhangi biri \(n\) sayısına ulaştığı anda durur. Bu durma zamanını \(T\) ile gösterirsek, uygulamanın hesapladığı nicelik
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}$$
olur. Yani problem, birbirini tamamlayan iki sonucun first-to-\(n\) yarışındaki normalize edilmiş beklenen kalan skorunu bulmaktır. Küçük ve orta boyutlu girdilerde değer tam olarak toplanabilir; çok büyük \(n\) ve güçlü bir yanlılık olduğunda ise drift baskın bir yaklaşım yeterlidir.
Tam formül, durma zamanı \(T\)'nin dağılımından gelir. Taraflardan biri ilk kez \(n\)'e ulaştığı için her zaman \(n \le T \le 2n-1\) vardır.
\(T=n+m\) yazalım; burada \(0\le m\le n-1\). \(n+m\). denemede durmanın birbirini dışlayan iki yolu vardır: son deneme başarısızlıktır ya da son deneme başarıdır.
Süreç \(n+m\). denemede bir başarısızlıkla bitiyorsa, ilk \(n+m-1\) denemede tam olarak \(n-1\) başarısızlık ve \(m\) başarı bulunmalı, ardından bir başarısızlık daha gelmelidir. Bu yüzden
$$A_m=\Pr(T=n+m\text{ ve durma nedeni başarısızlık})=\binom{n+m-1}{m}p^m q^n.$$
Simetrik olarak başarıyla bitme olasılığı
$$B_m=\Pr(T=n+m\text{ ve durma nedeni başarı})=\binom{n+m-1}{m}q^m p^n$$
olur.
Bu iki dal ayrık olduğundan
$$\Pr(T=n+m)=A_m+B_m$$
elde edilir. Ayrıca \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\) olduğu için aranan nicelik ya normalize edilmiş beklenti biçiminde
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
ya da doğrudan sonlu toplam olarak yazılabilir:
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
\(2n+1-(n+m)=n+1-m\) olduğundan
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right)$$
şeklini alır.
Her adımda binom katsayısını baştan hesaplamak gerekmez. İki dal terimi
$$A_0=q^n,\qquad B_0=p^n,$$
ile başlar ve \(m\ge 0\) için
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q$$
yinelemesini sağlar. Bunun nedeni
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}$$
özdeşliğidir. Böylece tam modda sabit bellek yeterlidir: o anki katkıyı toplar, sonra iki uç olasılığı bir sonraki adıma ilerletirsiniz.
\(p\) değeri \(\frac12\)'den belirgin biçimde uzaktaysa bir sonuç baskın hale gelir. Şunu tanımlayalım:
$$d=\max(p,q).$$
Bu durumda süreç çoğunlukla baskın sonucun \(n\). kez görülmesiyle biter ve durma zamanı negatif binom beklentisine yaklaşır:
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
Bunu normalize forma koyunca uygulamadaki yaklaşım elde edilir:
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
Bu yaklaşım, \(n\) çok büyük olduğunda ve kaybeden dalın katkısı ihmal edilebilir hale geldiğinde oldukça etkilidir.
Uygulama yanlılığın gücünü
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}$$
ile ölçer. \(|1-2p|\) deneme başına drift miktarıdır; \(\sqrt{npq}\) ise yaklaşık \(n\) denemedeki doğal dalgalanma ölçeğidir. Yani \(\delta\), deterministik yönelimi rastgele gürültüyle karşılaştırır. \(n\le 2000\) veya \(\delta \lt 15\) ise tam toplam kullanılır; aksi halde büyük-drift yaklaşımına geçilir.
Burada \(q=\frac12\) olur. Tam dal terimleri
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}$$
şeklindedir. Dolayısıyla
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
Normalize edilmiş değer
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857$$
olur. Bu örnek, \(n+1-m\) ağırlıklarının durma-zamanı olasılıklarıyla nasıl eşleştirildiğini açıkça gösterir.
C++, Python ve Java implementasyonlarının üçü de aynı hibrit planı izler. Önce \(q=1-p\) ve drift skoru \(\delta\) hesaplanır. Girdi tam rejimdeyse program iki uç dal olasılığını \(q^n\) ve \(p^n\) ile başlatır, \(m=0,1,\dots,n-1\) boyunca döner, ağırlıklı katkı \(\frac{n+1-m}{2n+1}(A_m+B_m)\) terimini toplar ve ardından iki olasılığı yukarıdaki yineleme ile günceller.
Girdi drift baskın bölgedeyse döngü tamamen atlanır ve doğrudan \(\frac{2n+1-n/\max(p,q)}{2n+1}\) döndürülür. Üç sürüm de sonucu ondalık olarak on basamakla yazar; C++ implementasyonu ayrıca büyük hedef girdiye geçmeden önce birkaç küçük doğrulama değeri de kontrol eder.
Tam rejim \(m=0,\dots,n-1\) üzerinde tek geçiş yaptığı için \(O(n)\) zaman ve \(O(1)\) bellek kullanır. Drift baskın yaklaşım \(O(1)\) zaman ve \(O(1)\) bellek gerektirir. Bu hibrit seçim, iptallerin önemli olduğu bölgelerde tam hesabı korur ve \(n\) aşırı büyüdüğünde pratik olmayan \(O(n)\) döngüden kaçınır.
Consideramos ensayos de Bernoulli independientes con probabilidad de éxito \(p\) y probabilidad de fallo \(q=1-p\). El proceso termina tan pronto como los éxitos o los fallos hayan aparecido \(n\) veces. Si \(T\) denota ese tiempo de parada, entonces la cantidad calculada por la implementación es
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}.$$
En otras palabras, el problema pide un valor esperado normalizado en una carrera first-to-\(n\) entre dos resultados complementarios. Para entradas pequeñas o medianas puede sumarse la distribución exacta; para valores enormes de \(n\) con sesgo fuerte basta una aproximación dominada por la deriva.
La fórmula exacta nace de la distribución del tiempo de parada \(T\). Como uno de los dos lados alcanza antes el conteo \(n\), siempre se cumple \(n \le T \le 2n-1\).
Escribimos \(T=n+m\) con \(0\le m\le n-1\). Hay dos maneras mutuamente excluyentes de parar en el ensayo \(n+m\): que el último ensayo sea un fallo o que el último ensayo sea un éxito.
Si el proceso termina con un fallo en el ensayo \(n+m\), entonces en los primeros \(n+m-1\) ensayos debe haber exactamente \(n-1\) fallos y \(m\) éxitos, seguidos por un fallo más. Por tanto,
$$A_m=\Pr(T=n+m\text{ y parada por fallo})=\binom{n+m-1}{m}p^m q^n.$$
Por simetría, la probabilidad de terminar con un éxito es
$$B_m=\Pr(T=n+m\text{ y parada por éxito})=\binom{n+m-1}{m}q^m p^n.$$
Las dos ramas son disjuntas, así que
$$\Pr(T=n+m)=A_m+B_m.$$
Como \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\), la magnitud buscada puede escribirse como esperanza normalizada
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
o directamente como suma finita exacta:
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
Como \(2n+1-(n+m)=n+1-m\), resulta
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right).$$
No hace falta recalcular coeficientes binomiales desde cero en cada iteración. Los dos términos terminales satisfacen
$$A_0=q^n,\qquad B_0=p^n,$$
y para \(m\ge 0\)
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q.$$
Esto se deduce de
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}.$$
Así, el modo exacto necesita memoria constante: se acumula la contribución actual y luego se avanzan las dos probabilidades terminales un paso en la recurrencia.
Cuando \(p\) está lejos de \(\frac12\), uno de los dos resultados domina. Definimos
$$d=\max(p,q).$$
En esa situación, el proceso suele terminar cuando el resultado dominante alcanza su aparición número \(n\), y el tiempo de parada se aproxima por la esperanza binomial negativa
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
Al sustituirlo en la forma normalizada obtenemos la aproximación usada por la implementación:
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
Esta aproximación es muy útil cuando \(n\) es enorme y la rama perdedora aporta una masa despreciable.
La implementación mide la fuerza del sesgo con
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}.$$
El factor \(|1-2p|\) representa la deriva por ensayo, mientras que \(\sqrt{npq}\) es la escala natural de fluctuación tras alrededor de \(n\) ensayos. Por eso \(\delta\) compara deriva determinista contra ruido aleatorio. Se usa la suma exacta cuando \(n\le 2000\) o \(\delta \lt 15\); en caso contrario se adopta la aproximación de gran deriva.
Aquí \(q=\frac12\). Los términos exactos de cada rama son
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}.$$
Por tanto,
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
El valor normalizado es
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857.$$
Este ejemplo muestra con claridad cómo los pesos \(n+1-m\) se combinan con las probabilidades del tiempo de parada.
Las implementaciones en C++, Python y Java siguen el mismo plan híbrido. Primero calculan \(q=1-p\) y la puntuación de deriva \(\delta\). Si la entrada cae en el régimen exacto, el programa inicializa las dos probabilidades terminales en \(q^n\) y \(p^n\), recorre \(m=0,1,\dots,n-1\), añade la contribución ponderada \(\frac{n+1-m}{2n+1}(A_m+B_m)\) y actualiza ambos términos con la recurrencia anterior.
Si la entrada pertenece al régimen dominado por la deriva, la implementación omite el bucle y devuelve directamente \(\frac{2n+1-n/\max(p,q)}{2n+1}\). Las tres versiones imprimen el valor final con diez cifras decimales, y la implementación en C++ además comprueba algunos casos de referencia más pequeños antes de evaluar la entrada gigantesca.
El régimen exacto realiza una sola pasada sobre \(m=0,\dots,n-1\), así que cuesta \(O(n)\) tiempo y \(O(1)\) memoria. La aproximación de gran deriva cuesta \(O(1)\) tiempo y \(O(1)\) memoria. El cambio híbrido conserva el método exacto donde la cancelación importa y evita un bucle \(O(n)\) inviable cuando \(n\) es extremadamente grande.
考虑一串相互独立的 Bernoulli 试验，成功概率为 \(p\)，失败概率为 \(q=1-p\)。一旦成功次数或失败次数中的任意一方先达到 \(n\)，过程就立刻停止。若用 \(T\) 表示这个停止时刻，那么实现实际计算的量是
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}.$$
因此，这道题本质上是在求一个“先到 \(n\)”双分支过程中的归一化剩余期望值。对于小规模或中等规模输入，可以把完整的停止时间分布精确求和；而当 \(n\) 极大且偏置足够明显时，可以用由漂移主导的近似式替代完整分布。
精确公式来自停止时间 \(T\) 的分布。由于总有一方先达到第 \(n\) 次出现，所以必然有 \(n \le T \le 2n-1\)。
把停止时间写成 \(T=n+m\)，其中 \(0\le m\le n-1\)。在第 \(n+m\) 次试验停止有且仅有两种互斥情形：最后一次试验是失败，或者最后一次试验是成功。
如果过程在第 \(n+m\) 次试验以失败结束，那么前 \(n+m-1\) 次试验中必须恰好出现 \(n-1\) 次失败和 \(m\) 次成功，然后再跟着一次失败。因此
$$A_m=\Pr(T=n+m\text{ 且以失败停止})=\binom{n+m-1}{m}p^m q^n.$$
由完全对称性可得，以成功停止的概率为
$$B_m=\Pr(T=n+m\text{ 且以成功停止})=\binom{n+m-1}{m}q^m p^n.$$
这两种停止方式互不重叠，所以
$$\Pr(T=n+m)=A_m+B_m.$$
又因为 \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\)，所以要求的量既可以写成归一化期望
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
也可以直接写成一个精确有限和：
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
由于 \(2n+1-(n+m)=n+1-m\)，可化为
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right).$$
这正是实现中逐项累加的数学依据。
如果每一步都重新计算组合数，会做很多重复工作。实际上，两条终止分支满足非常简单的递推关系：
$$A_0=q^n,\qquad B_0=p^n,$$
并且对所有 \(m\ge 0\)，都有
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q.$$
这来自恒等式
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}.$$
于是精确模式只需要常数级额外空间：保存当前两项的值，累加当前贡献，再递推到下一项即可。
当 \(p\) 明显偏离 \(\frac12\) 时，成功或失败中必有一方明显占优。记
$$d=\max(p,q).$$
在这种情况下，过程通常会在占优一方收集到第 \(n\) 次出现时结束，因此停止时间接近一个负二项型期望值
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
把它代回归一化表达式，就得到实现采用的近似公式：
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
当 \(n\) 极大而偏置又足够强时，落败分支的尾部质量几乎可以忽略，这个近似尤其有效。
实现用下面的量来衡量偏置强度：
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}.$$
其中 \(|1-2p|\) 可以看成每一步的平均漂移，而 \(\sqrt{npq}\) 对应大约 \(n\) 步之后的自然波动尺度。因此 \(\delta\) 本质上是在比较“确定性偏移”与“随机波动”谁更强。实现中的规则是：当 \(n\le 2000\) 或 \(\delta \lt 15\) 时使用精确求和；否则切换到大漂移近似。
此时 \(q=\frac12\)。两条分支的精确项为
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}.$$
因此
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
归一化结果为
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857.$$
这个例子完整展示了实现中的权重 \(n+1-m\) 如何与停止时间分布逐项配对。
C++、Python 和 Java 的实现都采用同一套混合策略。程序先计算 \(q=1-p\) 和漂移评分 \(\delta\)。如果输入落在精确模式内，就把两条终止分支的初值设为 \(q^n\) 与 \(p^n\)，然后对 \(m=0,1,\dots,n-1\) 依次累加权重贡献 \(\frac{n+1-m}{2n+1}(A_m+B_m)\)，并用上面的递推式把两项推进到下一步。
如果输入已经进入漂移主导区域，实现就直接跳过线性循环，返回 \(\frac{2n+1-n/\max(p,q)}{2n+1}\)。三个版本都会把最终结果格式化为 10 位小数，其中 C++ 版本还会在处理巨大目标输入之前验证几个较小的基准数值。
精确模式只做一次长度为 \(n\) 的线性扫描，因此时间复杂度是 \(O(n)\)，额外空间复杂度是 \(O(1)\)。大漂移近似只需要常数次运算，因此时间和空间都是 \(O(1)\)。这种混合切换策略在需要精确求和的区域保留了完整公式，同时避免了对超大 \(n\) 执行不可接受的 \(O(n)\) 循环。
Рассматривается последовательность независимых испытаний Бернулли с вероятностью успеха \(p\) и вероятностью неуспеха \(q=1-p\). Процесс останавливается в тот момент, когда либо успехи, либо неуспехи встретились \(n\) раз. Если \(T\) обозначает это время остановки, то реализуемая программой величина равна
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}.$$
То есть нужно вычислить нормированное ожидаемое остаточное значение в гонке до \(n\) между двумя взаимодополняющими исходами. Для малых и средних входов распределение можно суммировать точно, а для огромных \(n\) при сильном смещении достаточно приближения, в котором доминирует дрейф.
Точная формула получается из распределения времени остановки \(T\). Поскольку одна из сторон впервые достигает значения \(n\), всегда выполнено \(n \le T \le 2n-1\).
Запишем \(T=n+m\), где \(0\le m\le n-1\). Остановиться на испытании \(n+m\) можно двумя взаимоисключающими способами: последнее испытание оказывается неуспехом или успехом.
Если процесс заканчивается неуспехом на шаге \(n+m\), то среди первых \(n+m-1\) испытаний должно быть ровно \(n-1\) неуспехов и \(m\) успехов, после чего следует еще один неуспех. Поэтому
$$A_m=\Pr(T=n+m\text{ и остановка по неуспеху})=\binom{n+m-1}{m}p^m q^n.$$
По симметрии вероятность остановки по успеху равна
$$B_m=\Pr(T=n+m\text{ и остановка по успеху})=\binom{n+m-1}{m}q^m p^n.$$
Эти две ветви не пересекаются, значит
$$\Pr(T=n+m)=A_m+B_m.$$
Так как \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\), искомую величину можно записать либо как нормированное математическое ожидание
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
либо напрямую как точную конечную сумму:
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
Поскольку \(2n+1-(n+m)=n+1-m\), получаем
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right).$$
Пересчитывать биномиальные коэффициенты с нуля на каждом шаге не нужно. Два терминальных слагаемых удовлетворяют соотношениям
$$A_0=q^n,\qquad B_0=p^n,$$
и при \(m\ge 0\)
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q.$$
Это следует из тождества
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}.$$
Следовательно, в точном режиме достаточно постоянной памяти: добавляем текущий вклад и рекуррентно переходим к следующей паре вероятностей.
Когда \(p\) заметно отличается от \(\frac12\), один из исходов становится доминирующим. Обозначим
$$d=\max(p,q).$$
Тогда процесс обычно заканчивается в тот момент, когда доминирующий исход встречается в \(n\)-й раз, а время остановки близко к отрицательно-биномиальному ожиданию
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
Подставляя это в нормированную форму, получаем используемое приближение:
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
Оно особенно хорошо работает при огромном \(n\), когда вклад проигрывающей ветви становится пренебрежимо малым.
Сила смещения измеряется выражением
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}.$$
Множитель \(|1-2p|\) отражает средний дрейф за одно испытание, а \(\sqrt{npq}\) задает естественный масштаб флуктуаций после примерно \(n\) испытаний. Поэтому \(\delta\) сравнивает детерминированный сдвиг со случайным шумом. Точная сумма используется при \(n\le 2000\) или \(\delta \lt 15\); иначе выбирается приближение большого дрейфа.
Здесь \(q=\frac12\). Точные слагаемые двух ветвей таковы:
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}.$$
Следовательно,
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
Нормированное значение равно
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857.$$
На этом примере видно, как веса \(n+1-m\) сочетаются с вероятностями различных времен остановки.
Реализации на C++, Python и Java используют один и тот же гибридный план. Сначала вычисляются \(q=1-p\) и показатель дрейфа \(\delta\). Если вход относится к точному режиму, программа инициализирует две терминальные вероятности значениями \(q^n\) и \(p^n\), затем проходит по \(m=0,1,\dots,n-1\), добавляет взвешенный вклад \(\frac{n+1-m}{2n+1}(A_m+B_m)\) и обновляет оба слагаемых по приведенной выше рекурсии.
Если вход уже лежит в режиме доминирующего дрейфа, линейный цикл пропускается и сразу возвращается \(\frac{2n+1-n/\max(p,q)}{2n+1}\). Все три версии выводят итоговое число с десятью знаками после запятой, а версия на C++ дополнительно проверяет несколько меньших контрольных примеров перед вычислением огромного целевого входа.
Точный режим делает один линейный проход по \(m=0,\dots,n-1\), поэтому требует \(O(n)\) времени и \(O(1)\) памяти. Приближение большого дрейфа работает за \(O(1)\) времени и \(O(1)\) памяти. Гибридное переключение сохраняет точный метод там, где важны тонкие компенсации, и одновременно избегает непрактичного цикла длины \(O(n)\) при чрезвычайно больших \(n\).
ننظر إلى سلسلة من تجارب برنولي المستقلة، حيث احتمال النجاح هو \(p\) واحتمال الإخفاق هو \(q=1-p\). تتوقف العملية فورًا عندما يصل عدد النجاحات أو عدد الإخفاقات إلى \(n\). وإذا رمزنا لزمن التوقف بالرمز \(T\)، فإن الكمية التي تحسبها الخوارزمية هي
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1}.$$
إذن المطلوب هو إيجاد قيمة متوقعة مطبّعة تمثل ما يتبقى في سباق من نوع first-to-\(n\) بين نتيجتين متكاملتين. عندما تكون المدخلات صغيرة أو متوسطة يمكن جمع التوزيع كاملًا بدقة، أما عندما يكون \(n\) هائلًا والانحياز قويًا فيكفي تقريب تهيمن عليه جهة الانجراف.
الصيغة الدقيقة تأتي من توزيع زمن التوقف \(T\). وبما أن إحدى الجهتين تصل أولًا إلى العدد \(n\)، فلدينا دائمًا
$$n \le T \le 2n-1.$$
لنكتب \(T=n+m\)، حيث \(0\le m\le n-1\). يوجد طريقان متنافيان للتوقف عند التجربة \(n+m\): إما أن تكون التجربة الأخيرة إخفاقًا، أو تكون نجاحًا.
إذا انتهت العملية بإخفاق عند التجربة \(n+m\)، فلا بد أن تحتوي أول \(n+m-1\) تجربة على \(n-1\) إخفاقات بالضبط و\(m\) نجاحات، ثم يأتي إخفاق إضافي في النهاية. لذلك يكون
$$A_m=\binom{n+m-1}{m}p^m q^n.$$
وبالتماثل تكون احتمالية التوقف بسبب نجاح مساوية لـ
$$B_m=\binom{n+m-1}{m}q^m p^n.$$
بما أن الفرعين منفصلان، فإن
$$\Pr(T=n+m)=A_m+B_m.$$
ومع حقيقة أن \(\sum_{m=0}^{n-1}\Pr(T=n+m)=1\)، يمكن كتابة المقدار المطلوب إما كقيمة متوقعة مطبعة
$$f(n,p)=\frac{2n+1-\mathbb{E}[T]}{2n+1},$$
أو مباشرة كمجموع منتهٍ دقيق:
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(2n+1-(n+m))(A_m+B_m).$$
ولأن \(2n+1-(n+m)=n+1-m\)، نحصل على
$$f(n,p)=\frac{1}{2n+1}\sum_{m=0}^{n-1}(n+1-m)\left(\binom{n+m-1}{m}p^m q^n+\binom{n+m-1}{m}q^m p^n\right).$$
لا حاجة إلى إعادة حساب معاملات ذي الحدين من الصفر في كل خطوة. فحدا الفرعين النهائيين يحققان
$$A_0=q^n,\qquad B_0=p^n,$$
ولكل \(m\ge 0\)
$$A_{m+1}=A_m\cdot \frac{n+m}{m+1}\,p,\qquad B_{m+1}=B_m\cdot \frac{n+m}{m+1}\,q.$$
وهذا ينتج من الهوية
$$\binom{n+m}{m+1}=\binom{n+m-1}{m}\frac{n+m}{m+1}.$$
لذلك يكفي في النمط الدقيق استخدام ذاكرة ثابتة: نجمع المساهمة الحالية ثم ننقل الاحتمالين إلى الخطوة التالية عبر العودية.
عندما يكون \(p\) بعيدًا بوضوح عن \(\frac12\)، تصبح إحدى النتيجتين مهيمنة. لنعرّف
$$d=\max(p,q).$$
في هذه الحالة تنتهي العملية غالبًا عندما تصل النتيجة المهيمنة إلى ظهورها رقم \(n\)، ويكون زمن التوقف قريبًا من توقع سلبي ثنائي الحدين
$$\mathbb{E}[T]\approx \frac{n}{d}.$$
وبالتعويض في الصيغة المطبعة نحصل على التقريب المستخدم فعليًا:
$$f(n,p)\approx \frac{2n+1-\frac{n}{d}}{2n+1}.$$
ويصبح هذا التقريب شديد الفاعلية عندما يكون \(n\) ضخمًا وتكون مساهمة الفرع الخاسر ضئيلة جدًا.
تقيس الخوارزمية شدة الانحياز بواسطة
$$\delta=|1-2p|\sqrt{\frac{n}{pq}}.$$
فالحد \(|1-2p|\) يمثل مقدار الانجراف في كل تجربة، بينما تمثل \(\sqrt{npq}\) مقياس التذبذب الطبيعي بعد نحو \(n\) تجربة. لذا فإن \(\delta\) يقارن بين التأثير الحتمي للانحياز وبين الضجيج العشوائي. يستخدم الجمع الدقيق عندما \(n\le 2000\) أو \(\delta \lt 15\)، وإلا ينتقل التنفيذ إلى تقريب الانجراف الكبير.
هنا يكون \(q=\frac12\). وتصبح حدود الفرعين الدقيقة
$$A_0=B_0=\left(\frac12\right)^3=\frac18,$$
$$A_1=B_1=\binom{3}{1}\left(\frac12\right)^4=\frac{3}{16},$$
$$A_2=B_2=\binom{4}{2}\left(\frac12\right)^5=\frac{3}{16}.$$
ومن ثم
$$\Pr(T=3)=\frac14,\qquad \Pr(T=4)=\frac38,\qquad \Pr(T=5)=\frac38.$$
فتكون القيمة المطبعة
$$f\left(3,\frac12\right)=\frac{4\cdot \frac14+3\cdot \frac38+2\cdot \frac38}{7}=\frac{23}{56}\approx 0.4107142857.$$
ويبين هذا المثال بوضوح كيف تقترن الأوزان \(n+1-m\) باحتمالات أزمنة التوقف المختلفة.
تتبع تطبيقات C++ وPython وJava الخطة الهجينة نفسها. يبدأ التنفيذ بحساب \(q=1-p\) ودرجة الانجراف \(\delta\). إذا كانت المدخلة تقع في النظام الدقيق، يهيئ البرنامج احتمالي الفرعين النهائيين بالقيمتين \(q^n\) و\(p^n\)، ثم يمر على \(m=0,1,\dots,n-1\)، ويضيف المساهمة الموزونة \(\frac{n+1-m}{2n+1}(A_m+B_m)\)، ثم يحدّث الحدين بالعلاقة العودية السابقة.
أما إذا كانت المدخلة في منطقة يهيمن عليها الانجراف، فيتجاوز التنفيذ الحلقة الخطية ويعيد مباشرة \(\frac{2n+1-n/\max(p,q)}{2n+1}\). وتطبع النسخ الثلاث النتيجة النهائية بدقة عشر منازل عشرية، كما أن تنفيذ C++ يتحقق أيضًا من عدة حالات مرجعية أصغر قبل معالجة المدخلة الضخمة المستهدفة.
ينفذ النظام الدقيق مرورًا واحدًا على \(m=0,\dots,n-1\)، لذا يحتاج إلى زمن \(O(n)\) وذاكرة \(O(1)\). أما تقريب الانجراف الكبير فيعمل بزمن \(O(1)\) وذاكرة \(O(1)\). هذه الآلية الهجينة تحفظ الدقة عندما تكون الفروق الدقيقة مهمة، وتتفادى في الوقت نفسه حلقة \(O(n)\) غير عملية عندما يصبح \(n\) هائلًا للغاية.