A player starts with wealth \(1\) and may bet through \(N=1000\) independent rounds. Each round is won with probability \(p=0.6\), and the goal is to finish with wealth at least \(T=10^{12}\). Because the bets are priced fairly at each step, the right way to analyze the problem is not to enumerate betting rules directly, but to study which terminal states are worth buying under a fixed pricing budget.
The implementations therefore reduce the gambling problem to an optimization problem between two probability measures: the true measure \(P\), where wins occur with probability \(0.6\), and a fair reference measure \(Q\), where each branch has probability \(1/2\). The answer is the largest \(P\)-probability of a success set whose \(Q\)-cost does not exceed \(1/T\).
Let \(\omega\) denote a complete win-loss path of length \(N\), and let \(X(\omega)\) be the terminal wealth delivered on that path. The complete binomial tree lets us price terminal payoffs path by path, so the whole problem becomes a measure-theoretic budget allocation problem.
Under fair even-money pricing, each one-step branch has price \(1/2\). Therefore every full path \(\omega\) has fair price
$$Q(\{\omega\}) = 2^{-N}.$$
By linearity, any nonnegative terminal payoff \(X\) has initial cost
$$\text{cost}(X) = E_Q[X].$$
Since the player starts with capital \(1\), every feasible strategy must satisfy
$$E_Q[X] \le 1.$$
This is the key structural simplification: the space of adaptive betting strategies can be replaced by the space of terminal payoffs with a single linear budget constraint.
Let
$$A = \{\omega : X(\omega) \ge T\}$$
be the success event. On that event we have \(X(\omega) \ge T\), so
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$$
Hence every feasible strategy obeys
$$Q(A) \le \frac{1}{T}.$$
Conversely, if an event \(A\) satisfies \(Q(A) \le 1/T\), then the digital payoff
$$X(\omega) = T \cdot 1_A(\omega)$$
has cost \(TQ(A) \le 1\), so it is feasible and succeeds exactly on \(A\). Therefore the original problem is exactly equivalent to
$$\max_A P(A) \quad \text{subject to} \quad Q(A) \le \frac{1}{T}.$$
This is a Neyman-Pearson type optimization problem.
Let \(W\) be the number of wins along the path. Under the fair measure \(Q\),
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$$
Under the true measure \(P\),
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$$
All paths with the same \(w\) have the same price under \(Q\) and the same probability under \(P\). So instead of choosing individual paths, we only need to choose how much of each win-count layer \(w\) to include.
The relevant ranking statistic is the likelihood ratio
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
For this problem \(p=0.6\), so \(p/(1-p)=1.5>1\). As \(w\) increases by \(1\), the ratio is multiplied by
$$\frac{p}{1-p} > 1.$$
Therefore \(\frac{p_w}{q_w}\) is strictly increasing in \(w\). The optimal success set must thus take the largest \(w\)-layers first: all states with \(W=N\), then \(W=N-1\), and so on, because those layers give the most true probability per unit of fair-cost budget.
Let
$$B = \frac{1}{T}.$$
We accumulate \(Q\)-mass from \(w=N\) downward until the next full layer would exceed \(B\). Suppose \(w_*\) is the boundary layer. Then every layer with \(w > w_*\) is taken completely, and only a fraction
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
of layer \(w_*\) is needed, with \(0 \le \eta \le 1\). The optimal success probability is therefore
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$$
This is exactly the form implemented by the program.
Here the budget is \(B=1/2\). Under the fair measure \(Q\),
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$$
Under the true measure \(P\),
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$$
We take the \(w=2\) layer completely, using \(Q\)-mass \(1/4\). The remaining budget is \(1/4\), so we take
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}$$
of the \(w=1\) layer. Hence the optimal success probability is
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60.$$
This matches the small validation case embedded in the implementations.
The implementations first handle the trivial case \(T \le 1\), where success is guaranteed. Otherwise they set the fair-cost budget to \(1/T\) and build the entire fair layer distribution \((q_0,\dots,q_N)\) using the stable binomial recurrence
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
Next they recover the true distribution \((p_0,\dots,p_N)\) from the same layers via
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w,$$
which avoids direct factorials and keeps the arithmetic numerically stable. Finally they scan from \(w=N\) down to \(0\), add whole layers while the \(Q\)-budget allows it, identify the first layer that would overflow the budget, and then add the needed boundary fraction from that layer. The C++, Python, and Java implementations all follow this same logic, differing only in their numeric types.
Building the two arrays of layer masses takes \(O(N)\) time, and the final downward scan also takes \(O(N)\) time. Because the implementations store the \(Q\)-distribution and the \(P\)-distribution explicitly for all \(N+1\) win counts, the memory usage is \(O(N)\). For the actual instance \(N=1000\), this is easily manageable.
Ein Spieler startet mit Vermögen \(1\) und darf über \(N=1000\) unabhängige Runden wetten. Jede Runde wird mit Wahrscheinlichkeit \(p=0.6\) gewonnen, und das Ziel ist ein Endvermögen von mindestens \(T=10^{12}\). Wegen der fairen Preisstruktur der einzelnen Einsätze ist eine direkte Suche über Wettregeln unpraktisch; stattdessen betrachtet man, welche Endzustände sich innerhalb eines festen Bewertungsbudgets kaufen lassen.
Die Implementierungen formulieren das Problem daher als Optimierung zwischen zwei Wahrscheinlichkeitsmaßen: dem echten Maß \(P\) mit Gewinnwahrscheinlichkeit \(0.6\) und einem fairen Referenzmaß \(Q\), bei dem jeder Ast Wahrscheinlichkeit \(1/2\) hat. Gesucht ist die größte \(P\)-Wahrscheinlichkeit einer Erfolgsmenge, deren \(Q\)-Kosten höchstens \(1/T\) betragen.
Sei \(\omega\) ein vollständiger Gewinn-Verlust-Pfad der Länge \(N\), und sei \(X(\omega)\) das Endvermögen auf diesem Pfad. Im vollständigen binomialen Baum lassen sich Endauszahlungen pfadweise bepreisen, also wird das Wettproblem zu einer Budgetoptimierung über terminale Zustände.
Unter fairer Even-Money-Bepreisung kostet jeder Einzelschritt \(1/2\). Daher hat jeder vollständige Pfad \(\omega\) den fairen Preis
$$Q(\{\omega\}) = 2^{-N}.$$
Wegen der Linearität hat jede nichtnegative Endauszahlung \(X\) Anfangskosten
$$\text{cost}(X) = E_Q[X].$$
Da das Anfangskapital \(1\) beträgt, muss für jede zulässige Strategie gelten:
$$E_Q[X] \le 1.$$
Damit kann man die Menge adaptiver Wettstrategien durch die Menge terminaler Auszahlungen mit einer einzigen linearen Nebenbedingung ersetzen.
Sei
$$A = \{\omega : X(\omega) \ge T\}$$
das Erfolgsereignis. Auf \(A\) gilt \(X(\omega) \ge T\), also
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$$
Somit erfüllt jede zulässige Strategie
$$Q(A) \le \frac{1}{T}.$$
Umgekehrt ist für jedes Ereignis \(A\) mit \(Q(A) \le 1/T\) die digitale Auszahlung
$$X(\omega) = T \cdot 1_A(\omega)$$
mit Kosten \(TQ(A) \le 1\) finanzierbar und erzielt Erfolg genau auf \(A\). Daher ist das ursprüngliche Problem exakt äquivalent zu
$$\max_A P(A) \quad \text{unter der Bedingung} \quad Q(A) \le \frac{1}{T}.$$
Das ist genau die Struktur des Neyman-Pearson-Lemmas.
Sei \(W\) die Zahl der Gewinne auf dem Pfad. Unter dem fairen Maß \(Q\) gilt
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$$
Unter dem echten Maß \(P\) gilt
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$$
Alle Pfade mit demselben \(w\) sind unter \(Q\) gleich teuer und unter \(P\) gleich wahrscheinlich. Deshalb muss man nicht einzelne Pfade auswählen, sondern nur entscheiden, wie viel von jeder Gewinnschicht \(w\) aufgenommen wird.
Die relevante Rangzahl ist das Likelihood-Verhältnis
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
Hier ist \(p=0.6\), also \(p/(1-p)=1.5>1\). Wenn \(w\) um \(1\) steigt, wird dieses Verhältnis mit
$$\frac{p}{1-p} > 1$$
multipliziert. Also wächst \(\frac{p_w}{q_w}\) streng mit \(w\). Optimal ist daher, die größten Gewinnschichten zuerst zu kaufen: zuerst \(W=N\), dann \(W=N-1\) und so weiter.
Setze
$$B = \frac{1}{T}.$$
Man akkumuliert \(Q\)-Masse von \(w=N\) abwärts, bis die nächste volle Schicht das Budget überschreiten würde. Sei \(w_*\) die Grenzschicht. Dann werden alle Schichten mit \(w > w_*\) vollständig genommen, und aus der Schicht \(w_*\) nur der Anteil
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
mit \(0 \le \eta \le 1\). Die optimale Erfolgswahrscheinlichkeit lautet damit
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$$
Genau diese Formel setzt das Programm um.
Hier ist das Budget \(B=1/2\). Unter \(Q\) gilt
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$$
Unter \(P\) gilt
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$$
Die Schicht \(w=2\) wird vollständig genommen und verbraucht \(Q\)-Masse \(1/4\). Es bleibt \(1/4\) Budget, also nimmt man aus der Schicht \(w=1\) den Anteil
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}.$$
Die optimale Erfolgswahrscheinlichkeit ist somit
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60,$$
genau der kleine Kontrollfall aus den Implementierungen.
Die Implementierungen behandeln zuerst den trivialen Fall \(T \le 1\); dann ist Erfolg sicher. Andernfalls setzen sie das faire Budget auf \(1/T\) und erzeugen die komplette faire Schichtverteilung \((q_0,\dots,q_N)\) über die stabile Binomialrekursion
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
Anschließend wird die echte Verteilung \((p_0,\dots,p_N)\) aus denselben Schichten über
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w$$
rekonstruiert. So vermeidet man direkte Fakultäten und große Binomialkoeffizienten. Zum Schluss wird von \(w=N\) nach \(0\) abwärts gescannt: ganze Schichten werden addiert, solange das \(Q\)-Budget reicht; die erste Schicht, die zu groß wäre, liefert den Grenzindex, und von ihr wird nur der nötige Anteil genommen. Die C++-, Python- und Java-Implementierungen unterscheiden sich dabei nur in den verwendeten Zahlentypen.
Der Aufbau der beiden Schichtarrays kostet \(O(N)\) Zeit, und der abschließende Abwärtsscan kostet ebenfalls \(O(N)\) Zeit. Da die Implementierungen die \(Q\)- und \(P\)-Verteilung für alle \(N+1\) Gewinnzahlen explizit speichern, liegt der Speicherverbrauch bei \(O(N)\). Für \(N=1000\) ist das problemlos handhabbar.
Bir oyuncu \(1\) birim servetle başlıyor ve \(N=1000\) bağımsız tur boyunca bahis yapabiliyor. Her tur kazanma olasılığı \(p=0.6\), hedef ise sonunda serveti en az \(T=10^{12}\) seviyesine çıkarmak. Bahisler her adımda adil fiyatlandığı için çözüm, hangi bahis kuralının denenmesi gerektiğini tek tek aramak yerine, sınırlı bir fiyatlama bütçesiyle hangi terminal durumların satın alınmasının en avantajlı olduğunu inceliyor.
Bu yüzden uygulamalar problemi iki olasılık ölçüsü arasındaki bir optimizasyona dönüştürüyor: gerçek ölçü \(P\), burada kazanma olasılığı \(0.6\); ve her dalın olasılığı \(1/2\) olan adil referans ölçüsü \(Q\). Amaç, \(Q\)-maliyeti en fazla \(1/T\) olan bir başarı kümesinin \(P\) altındaki olasılığını en büyük yapmaktır.
\(\omega\), uzunluğu \(N\) olan tam bir kazanma-kaybetme yolunu göstersin. \(X(\omega)\) da bu yol sonundaki servet olsun. Tam binom ağacında terminal ödemeler yol bazında fiyatlanabildiği için, tüm problem son durumlar üzerinde bir bütçe tahsisine dönüşür.
Adil even-money fiyatlamada her tek adımın fiyatı \(1/2\)'dir. Bu nedenle her tam yol \(\omega\) için adil fiyat
$$Q(\{\omega\}) = 2^{-N}$$
olur. Doğrusallık sayesinde herhangi bir negatif olmayan terminal ödeme \(X\) için başlangıç maliyeti
$$\text{cost}(X) = E_Q[X]$$
şeklindedir. Oyuncu \(1\) birim sermaye ile başladığından her uygulanabilir strateji
$$E_Q[X] \le 1$$
koşulunu sağlamalıdır. Böylece adaptif bahis stratejileri uzayı, tek bir lineer bütçe kısıtı altındaki terminal ödeme uzayına indirgenir.
Başarı olayını
$$A = \{\omega : X(\omega) \ge T\}$$
olarak tanımlayalım. \(A\) üzerinde \(X(\omega) \ge T\) olduğundan
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A)$$
elde edilir. Dolayısıyla her uygulanabilir strateji için
$$Q(A) \le \frac{1}{T}$$
zorunludur. Ters yönde, \(Q(A) \le 1/T\) sağlayan herhangi bir olay için
$$X(\omega) = T \cdot 1_A(\omega)$$
dijital ödemesi tam olarak \(TQ(A)\) maliyetine sahiptir ve başarıyı yalnızca \(A\) üzerinde verir. Bu nedenle özgün problem tam olarak
$$\max_A P(A) \quad \text{koşuluyla} \quad Q(A) \le \frac{1}{T}$$
problemine eşdeğerdir. Bu da doğrudan Neyman-Pearson tipindeki yapıdır.
\(W\) toplam kazanılan tur sayısı olsun. Adil ölçü \(Q\) altında
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}$$
olur. Gerçek ölçü \(P\) altında ise
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}$$
elde edilir. Aynı \(w\) değerine sahip tüm yolların \(Q\) maliyeti de \(P\) olasılığı da aynıdır. O yüzden tek tek yollar yerine, her kazanma katmanından ne kadar alınacağına karar vermek yeterlidir.
Sıralamayı belirleyen büyüklük olabilirlik oranıdır:
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
Bu problemde \(p=0.6\) olduğu için \(p/(1-p)=1.5>1\). \(w\) bir arttığında oran
$$\frac{p}{1-p} > 1$$
ile çarpılır. Yani \(\frac{p_w}{q_w}\) değeri \(w\) ile sıkı biçimde artar. Sonuç olarak en iyi seçim, en büyük kazanma sayılı katmanları önce almaktır: önce \(W=N\), sonra \(W=N-1\) ve böyle devam eder.
Şimdi
$$B = \frac{1}{T}$$
olsun. \(Q\)-kütlesini \(w=N\)'den aşağı doğru toplarız; bir sonraki tam katman bütçeyi aşacaksa sınır katmanına gelmişiz demektir. Bu sınır katmanına \(w_*\) diyelim. O zaman \(w > w_*\) olan bütün katmanlar tamamen alınır ve \(w_*\) katmanından yalnızca
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
oranı gerekir; burada \(0 \le \eta \le 1\). Böylece en büyük başarı olasılığı
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}$$
olur. Kodun uyguladığı kapalı biçim tam budur.
Burada bütçe \(B=1/2\)'dir. Adil ölçü altında
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}$$
ve gerçek ölçü altında
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16$$
elde edilir. \(w=2\) katmanını tamamen alırsak \(Q\)-bütçeden \(1/4\) kullanırız. Kalan bütçe yine \(1/4\) olduğundan \(w=1\) katmanının
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}$$
kadarlık kısmını alırız. Toplam başarı olasılığı
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60$$
olur. Bu, uygulamalardaki küçük doğrulama örneğiyle aynıdır.
Uygulamalar önce \(T \le 1\) durumunu ele alır; bu halde başarı zaten kesindir. Aksi halde adil bütçe \(1/T\) olarak belirlenir ve tüm adil katman dağılımı \((q_0,\dots,q_N)\) kararlı binom özyinelemesiyle üretilir:
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
Daha sonra gerçek dağılım \((p_0,\dots,p_N)\), aynı katmanlar üzerinden
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w$$
eşitliğiyle elde edilir. Böylece doğrudan faktöriyel veya dev binom katsayıları hesaplanmaz. Son aşamada kod \(w=N\)'den \(0\)'a doğru tarama yapar, bütçe izin verdiği sürece tam katmanları ekler, taşmaya neden olacak ilk katmanı sınır katmanı olarak işaretler ve oradan gereken kesirli kısmı ekler. C++, Python ve Java uygulamaları aynı matematiksel akışı izler; fark yalnızca kullandıkları sayı türleridir.
İki katman dizisini kurmak \(O(N)\) zaman alır; aşağı doğru yapılan son tarama da \(O(N)\) zamandadır. Uygulamalar \(N+1\) adet \(Q\)-katmanı ve \(P\)-katmanını açıkça sakladığı için bellek kullanımı \(O(N)\)'dir. Gerçek örnekte \(N=1000\) olduğundan bu maliyet oldukça küçüktür.
Un jugador empieza con riqueza \(1\) y puede apostar durante \(N=1000\) rondas independientes. Cada ronda se gana con probabilidad \(p=0.6\), y el objetivo es terminar con riqueza al menos \(T=10^{12}\). Como las apuestas están valoradas de forma justa en cada paso, la solución no intenta enumerar reglas de apuesta; en su lugar estudia qué estados finales conviene comprar dentro de un presupuesto de valoración fijo.
Por eso las implementaciones reformulan el problema como una optimización entre dos medidas de probabilidad: la medida real \(P\), donde la probabilidad de ganar es \(0.6\), y una medida de referencia justa \(Q\), donde cada rama tiene probabilidad \(1/2\). La cantidad buscada es la mayor probabilidad \(P\) de un conjunto de éxito cuyo coste bajo \(Q\) no supere \(1/T\).
Sea \(\omega\) una trayectoria completa de victorias y derrotas de longitud \(N\), y sea \(X(\omega)\) la riqueza final en esa trayectoria. En el árbol binomial completo, los pagos terminales se pueden valorar hoja por hoja, de modo que el problema entero se convierte en una asignación de presupuesto sobre estados terminales.
Bajo una valoración justa a par, cada paso elemental cuesta \(1/2\). Por lo tanto, toda trayectoria completa \(\omega\) tiene precio justo
$$Q(\{\omega\}) = 2^{-N}.$$
Por linealidad, cualquier pago terminal no negativo \(X\) tiene coste inicial
$$\text{cost}(X) = E_Q[X].$$
Como el jugador empieza con capital \(1\), toda estrategia factible debe satisfacer
$$E_Q[X] \le 1.$$
Ésta es la reducción clave: en vez de pensar en apuestas adaptativas paso a paso, basta estudiar pagos finales sujetos a una única restricción lineal de presupuesto.
Definamos el evento de éxito
$$A = \{\omega : X(\omega) \ge T\}.$$
En ese evento se cumple \(X(\omega) \ge T\), así que
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$$
Por consiguiente, cualquier estrategia factible cumple
$$Q(A) \le \frac{1}{T}.$$
Recíprocamente, si un evento \(A\) verifica \(Q(A) \le 1/T\), entonces el pago digital
$$X(\omega) = T \cdot 1_A(\omega)$$
tiene coste \(TQ(A) \le 1\), luego es factible y tiene éxito exactamente sobre \(A\). Así, el problema original es equivalente a
$$\max_A P(A) \quad \text{sujeto a} \quad Q(A) \le \frac{1}{T}.$$
Ésta es precisamente la forma del principio de Neyman-Pearson.
Sea \(W\) el número total de victorias. Bajo la medida justa \(Q\),
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$$
Bajo la medida real \(P\),
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$$
Todas las trayectorias con el mismo valor de \(w\) tienen el mismo coste bajo \(Q\) y la misma probabilidad bajo \(P\). Por eso no hace falta decidir hoja por hoja: sólo importa cuánto tomar de cada capa con \(w\) victorias.
La estadística relevante es
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
Aquí \(p=0.6\), de modo que \(p/(1-p)=1.5>1\). Cuando \(w\) aumenta en \(1\), este cociente se multiplica por
$$\frac{p}{1-p} > 1.$$
Así, \(\frac{p_w}{q_w}\) crece estrictamente con \(w\). La política óptima consiste entonces en tomar primero las capas con más victorias: \(W=N\), luego \(W=N-1\), y así sucesivamente.
Sea
$$B = \frac{1}{T}.$$
Acumulamos masa \(Q\) desde \(w=N\) hacia abajo hasta que la siguiente capa completa exceda \(B\). Si \(w_*\) es la capa frontera, entonces todas las capas con \(w > w_*\) se toman completas, y de la capa \(w_*\) sólo se necesita la fracción
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
con \(0 \le \eta \le 1\). La probabilidad óptima de éxito es por tanto
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$$
Ésta es exactamente la expresión que implementa el programa.
En este caso el presupuesto es \(B=1/2\). Bajo \(Q\),
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$$
Bajo \(P\),
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$$
Tomamos por completo la capa \(w=2\), que consume masa \(Q\) igual a \(1/4\). Queda un presupuesto de \(1/4\), así que tomamos
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}$$
de la capa \(w=1\). La probabilidad máxima de éxito es entonces
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60.$$
Esto coincide con el caso pequeño de validación usado por las implementaciones.
Las implementaciones empiezan resolviendo el caso trivial \(T \le 1\), donde el éxito está garantizado. En caso contrario fijan el presupuesto justo en \(1/T\) y construyen toda la distribución justa \((q_0,\dots,q_N)\) mediante la recurrencia binomial estable
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
Después recuperan la distribución real \((p_0,\dots,p_N)\) a partir de esas mismas capas usando
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w,$$
lo que evita calcular factoriales o coeficientes binomiales enormes. Finalmente recorren las capas desde \(w=N\) hasta \(0\), agregan capas completas mientras el presupuesto \(Q\) lo permita, detectan la primera capa que desborda el presupuesto y añaden sólo la fracción necesaria de esa capa frontera. Las versiones en C++, Python y Java siguen exactamente esta lógica.
Construir los dos arreglos de masas por capas cuesta \(O(N)\) tiempo, y el recorrido final descendente también cuesta \(O(N)\). Como las implementaciones almacenan explícitamente las distribuciones \(Q\) y \(P\) para los \(N+1\) valores posibles de \(W\), el uso de memoria es \(O(N)\). Para \(N=1000\), este coste es muy pequeño.
玩家以初始财富 \(1\) 开始，可以进行 \(N=1000\) 轮独立下注。每一轮获胜概率为 \(p=0.6\)，目标是在最后让财富达到至少 \(T=10^{12}\)。由于每一步的下注都按公平价格计价，正确的分析方式不是暴力枚举所有投注策略，而是研究在固定的定价预算之下，哪些终局状态最值得“购买”。
因此，程序把问题改写成两个概率测度之间的优化问题：真实测度 \(P\)，其中单轮胜率为 \(0.6\)；以及公平参考测度 \(Q\)，其中每条分支的概率都是 \(1/2\)。我们要求的是：在 \(Q\)-成本不超过 \(1/T\) 的前提下，成功集合在 \(P\) 下的概率最大可以是多少。
记 \(\omega\) 为长度为 \(N\) 的一条完整胜负路径，\(X(\omega)\) 为该路径对应的终局财富。因为完整的二叉树是完备的，所以终局支付可以按叶子逐个定价，整个问题就变成了在终局状态上分配预算的问题。
在公平的 even-money 定价下，每一步分支的价格都是 \(1/2\)。因此，每一条完整路径 \(\omega\) 的公平价格都是
$$Q(\{\omega\}) = 2^{-N}.$$
由线性性可知，任意非负终局支付 \(X\) 的初始成本为
$$\text{cost}(X) = E_Q[X].$$
玩家初始资本只有 \(1\)，所以任何可行策略都必须满足
$$E_Q[X] \le 1.$$
这一步非常关键。它说明我们不必显式地追踪每一轮该押多少，而可以直接研究所有满足单一线性预算约束的终局支付。
设成功事件为
$$A = \{\omega : X(\omega) \ge T\}.$$
在这个事件上有 \(X(\omega) \ge T\)，于是
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$$
所以任何可行策略都必须满足
$$Q(A) \le \frac{1}{T}.$$
反过来，如果某个事件 \(A\) 满足 \(Q(A) \le 1/T\)，那么数字支付
$$X(\omega) = T \cdot 1_A(\omega)$$
的成本恰好是 \(TQ(A)\le 1\)，因此它是可行的，并且只在 \(A\) 上达到成功。于是原问题与下面的优化完全等价：
$$\max_A P(A) \quad \text{subject to} \quad Q(A) \le \frac{1}{T}.$$
这正是一个 Neyman-Pearson 型的最优选择问题。
记 \(W\) 为整条路径中的获胜轮数。在公平测度 \(Q\) 下，
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$$
在真实测度 \(P\) 下，
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$$
只要获胜次数相同，所有路径在 \(Q\) 下的总成本和在 \(P\) 下的总概率都相同。因此我们不需要区分同一层中的具体叶子，只需决定每个获胜层 \(w\) 取多少即可。
最关键的排序指标是似然比
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
本题中 \(p=0.6\)，因此 \(p/(1-p)=1.5>1\)。当 \(w\) 增加 \(1\) 时，上式会额外乘上
$$\frac{p}{1-p} > 1.$$
这意味着 \(\frac{p_w}{q_w}\) 随 \(w\) 严格递增。也就是说，单位 \(Q\)-成本能够换来的 \(P\)-概率，在高胜场层里更划算。因此最优策略一定是先拿 \(W=N\) 这一层，再拿 \(W=N-1\)，然后继续向下。
设
$$B = \frac{1}{T}.$$
从 \(w=N\) 开始向下累加 \(Q\)-质量，直到再完整加入下一层就会超过 \(B\)。设这个边界层为 \(w_*\)。那么所有满足 \(w > w_*\) 的层都整层取走，而边界层只需取其中的比例
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
其中 \(0 \le \eta \le 1\)。于是最优成功概率为
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$$
这正是程序实现的核心公式。
此时预算 \(B=1/2\)。在公平测度 \(Q\) 下，
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$$
在真实测度 \(P\) 下，
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$$
先把 \(w=2\) 这一层全部取走，会消耗 \(Q\)-质量 \(1/4\)。还剩下 \(1/4\) 的预算，所以从 \(w=1\) 这一层中再取
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}$$
即可。于是最大成功概率为
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60.$$
这和程序中的小规模校验案例完全一致。
实现首先处理平凡情况 \(T \le 1\)，这时成功概率就是 \(1\)。否则，程序把公平预算设为 \(1/T\)，并通过稳定的二项分布递推构造完整的公平分层分布 \((q_0,\dots,q_N)\)：
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
接着再利用
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w$$
从同一组层质量恢复真实分布 \((p_0,\dots,p_N)\)。这样就避免了直接计算阶乘和巨大的二项系数，也使数值更稳定。最后，程序从 \(w=N\) 向 \(0\) 递减扫描：预算允许时整层加入，一旦下一层会超预算，就把该层记作边界层，并加入恰好足够的那一部分。C++、Python 和 Java 三份实现都遵循这一逻辑，只是所用的高精度数值类型不同。
构造两组层概率数组需要 \(O(N)\) 时间，最后的逆序扫描也需要 \(O(N)\) 时间。因为实现把 \(Q\) 分布和 \(P\) 分布的全部 \(N+1\) 个层值都显式存储下来，所以空间复杂度是 \(O(N)\)。对实际参数 \(N=1000\) 而言，这个成本非常小。
Игрок начинает с капиталом \(1\) и может делать ставки в течение \(N=1000\) независимых раундов. Вероятность выигрыша в каждом раунде равна \(p=0.6\), а цель состоит в том, чтобы к концу получить капитал не меньше \(T=10^{12}\). Поскольку ставки на каждом шаге оцениваются справедливо, решение не перебирает стратегии напрямую, а ищет, какие конечные состояния выгоднее всего «купить» в рамках заданного ценового бюджета.
Поэтому реализации сводят задачу к оптимизации между двумя вероятностными мерами: истинной мерой \(P\), где вероятность выигрыша равна \(0.6\), и справедливой опорной мерой \(Q\), где каждая ветвь имеет вероятность \(1/2\). Нужно максимизировать вероятность успеха по \(P\) при условии, что стоимость множества успеха по \(Q\) не превосходит \(1/T\).
Пусть \(\omega\) обозначает полный путь из выигрышей и проигрышей длины \(N\), а \(X(\omega)\) — конечное богатство на этом пути. В полном биномиальном дереве конечные выплаты можно оценивать по листьям, так что вся задача превращается в распределение бюджета по терминальным состояниям.
При справедливой even-money цене каждый одношаговый переход стоит \(1/2\). Следовательно, каждый полный путь \(\omega\) имеет справедливую цену
$$Q(\{\omega\}) = 2^{-N}.$$
По линейности любая неотрицательная конечная выплата \(X\) имеет начальную стоимость
$$\text{cost}(X) = E_Q[X].$$
Так как стартовый капитал равен \(1\), любая допустимая стратегия обязана удовлетворять условию
$$E_Q[X] \le 1.$$
Это и есть главное упрощение: вместо пошагового описания ставок можно сразу работать с конечными выплатами, подчинёнными одному линейному бюджетному ограничению.
Обозначим событие успеха через
$$A = \{\omega : X(\omega) \ge T\}.$$
На событии \(A\) выполнено \(X(\omega) \ge T\), поэтому
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$$
Значит, любая допустимая стратегия должна удовлетворять
$$Q(A) \le \frac{1}{T}.$$
Обратно, если событие \(A\) удовлетворяет \(Q(A) \le 1/T\), то цифровая выплата
$$X(\omega) = T \cdot 1_A(\omega)$$
имеет стоимость \(TQ(A) \le 1\), то есть допустима и приводит к успеху ровно на \(A\). Поэтому исходная задача в точности эквивалентна задаче
$$\max_A P(A) \quad \text{при условии} \quad Q(A) \le \frac{1}{T}.$$
Это стандартная структура леммы Неймана-Пирсона.
Пусть \(W\) — число выигранных раундов. При справедливой мере \(Q\)
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$$
При истинной мере \(P\)
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$$
Все пути с одним и тем же \(w\) имеют одинаковую стоимость по \(Q\) и одинаковую вероятность по \(P\). Значит, нужно выбирать не отдельные листья, а долю каждого слоя с фиксированным числом выигрышей.
Ключевая величина — отношение
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
В этой задаче \(p=0.6\), значит \(p/(1-p)=1.5>1\). При увеличении \(w\) на единицу это отношение умножается на
$$\frac{p}{1-p} > 1.$$
Следовательно, \(\frac{p_w}{q_w}\) строго возрастает по \(w\). Поэтому оптимально брать сначала самые верхние слои: сначала \(W=N\), затем \(W=N-1\), и так далее.
Положим
$$B = \frac{1}{T}.$$
Будем накапливать \(Q\)-массу от \(w=N\) вниз, пока следующий полный слой не переполнит бюджет \(B\). Пусть \(w_*\) — пограничный слой. Тогда все слои с \(w > w_*\) берутся полностью, а из слоя \(w_*\) нужна только доля
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
при \(0 \le \eta \le 1\). Оптимальная вероятность успеха равна
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$$
Именно эту формулу реализует программа.
Здесь бюджет равен \(B=1/2\). При мере \(Q\)
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$$
При мере \(P\)
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$$
Слой \(w=2\) берётся целиком и расходует \(Q\)-массу \(1/4\). Остаётся ещё \(1/4\), поэтому из слоя \(w=1\) нужно взять долю
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}.$$
Отсюда максимальная вероятность успеха равна
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60.$$
Это совпадает с небольшим проверочным примером, использованным в реализациях.
Сначала реализации обрабатывают тривиальный случай \(T \le 1\), когда успех гарантирован. Иначе они задают справедливый бюджет \(1/T\) и строят полное распределение \((q_0,\dots,q_N)\) по справедливой мере с помощью устойчивой биномиальной рекурсии
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
Затем настоящее распределение \((p_0,\dots,p_N)\) восстанавливается по формуле
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w,$$
что позволяет не вычислять факториалы и огромные биномиальные коэффициенты напрямую. После этого код идёт по слоям от \(w=N\) к \(0\), добавляет целые слои, пока хватает \(Q\)-бюджета, отмечает первый слой, который переполняет бюджет, и добавляет только нужную долю этого пограничного слоя. Реализации на C++, Python и Java следуют одной и той же схеме.
Построение двух массивов слоёв занимает \(O(N)\) времени, а финальный проход сверху вниз также требует \(O(N)\) времени. Поскольку реализации явно хранят распределения \(Q\) и \(P\) для всех \(N+1\) возможных значений числа выигрышей, память составляет \(O(N)\). Для \(N=1000\) это очень небольшой объём.
يبدأ اللاعب بثروة مقدارها \(1\)، ويستطيع المراهنة خلال \(N=1000\) جولة مستقلة. احتمال الفوز في كل جولة هو \(p=0.6\)، والهدف هو الوصول في النهاية إلى ثروة لا تقل عن \(T=10^{12}\). وبما أن التسعير في كل خطوة عادل، فإن التحليل الصحيح لا يعتمد على تعداد قواعد المراهنة واحدةً واحدة، بل على تحديد أي الحالات النهائية ينبغي شراؤها ضمن ميزانية تسعير ثابتة.
لهذا تعيد التطبيقات صياغة المسألة كمسألة تحسين بين قياسين احتماليين: القياس الحقيقي \(P\) حيث احتمال الفوز هو \(0.6\)، وقياس مرجعي عادل \(Q\) حيث لكل فرع احتمال \(1/2\). المطلوب هو أكبر احتمال نجاح تحت \(P\) لمجموعة نجاح لا تتجاوز كلفتها تحت \(Q\) القيمة \(1/T\).
لنرمز بالرمز \(\omega\) إلى مسار كامل من الربح والخسارة بطول \(N\)، ولتكن \(X(\omega)\) هي الثروة النهائية على ذلك المسار. بما أن الشجرة الثنائية الكاملة تسمح بتسعير الدفعات النهائية ورقةً بورقة، فإن المسألة كلها تتحول إلى توزيع ميزانية على الحالات النهائية.
في التسعير العادل من نوع even-money تكون كلفة كل خطوة مفردة مساويةً لـ \(1/2\). لذلك فإن السعر العادل لأي مسار كامل \(\omega\) هو
$$Q(\{\omega\}) = 2^{-N}.$$
وبالخطية فإن أي دفعة نهائية غير سالبة \(X\) تكون كلفتها الابتدائية
$$\text{cost}(X) = E_Q[X].$$
ولأن رأس المال الابتدائي يساوي \(1\)، فلا بد لأي استراتيجية ممكنة أن تحقق
$$E_Q[X] \le 1.$$
وهذه هي الخطوة الجوهرية: بدلاً من متابعة المراهنات التكيفية جولة بعد جولة، نعمل مباشرةً مع جميع الدفعات النهائية التي تحقق قيد ميزانية خطيًا واحدًا.
لنعرّف حدث النجاح بأنه
$$A = \{\omega : X(\omega) \ge T\}.$$
على هذا الحدث لدينا \(X(\omega) \ge T\)، ومن ثم
$$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$$
إذن كل استراتيجية ممكنة لا بد أن تحقق
$$Q(A) \le \frac{1}{T}.$$
وبالعكس، إذا كان حدث ما \(A\) يحقق \(Q(A) \le 1/T\)، فإن الدفعة الرقمية
$$X(\omega) = T \cdot 1_A(\omega)$$
تكلف \(TQ(A) \le 1\)، وبالتالي فهي ممكنة وتحقق النجاح بالضبط على \(A\). لذلك تصبح المسألة الأصلية مكافئة تمامًا للمسألة
$$\max_A P(A) \quad \text{subject to} \quad Q(A) \le \frac{1}{T}.$$
وهذا هو الشكل القياسي لمسألة من نوع Neyman-Pearson.
لتكن \(W\) عدد الجولات الرابحة. تحت القياس العادل \(Q\) نحصل على
$$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$$
أما تحت القياس الحقيقي \(P\) فنحصل على
$$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$$
كل المسارات التي تمتلك العدد نفسه من الانتصارات لها الكلفة نفسها تحت \(Q\) والاحتمال نفسه تحت \(P\). لذلك لا حاجة لاختيار الأوراق واحدةً واحدة؛ يكفي تحديد المقدار المأخوذ من كل طبقة ذات \(w\) انتصارات.
الكمية الحاسمة للترتيب هي نسبة الترجيح
$$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$$
في هذه المسألة لدينا \(p=0.6\)، وبالتالي \(p/(1-p)=1.5>1\). عندما يزداد \(w\) بمقدار \(1\)، فإن هذه النسبة تُضرب في
$$\frac{p}{1-p} > 1.$$
إذن \(\frac{p_w}{q_w}\) تزداد ازديادًا صارمًا مع \(w\). وهذا يعني أن الطبقات ذات عدد الانتصارات الأكبر تعطي احتمالًا حقيقيًا أكبر لكل وحدة من كلفة \(Q\)، ولذلك فهي تُؤخذ أولاً.
لنضع
$$B = \frac{1}{T}.$$
نبدأ بتجميع كتلة \(Q\) من \(w=N\) نزولاً، إلى أن تصبح الطبقة التالية الكاملة أكبر من الميزانية \(B\). ولتكن \(w_*\) هي الطبقة الحدية. عندئذ تؤخذ جميع الطبقات التي تحقق \(w > w_*\) بالكامل، ومن الطبقة \(w_*\) نأخذ فقط الكسر
$$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$$
حيث \(0 \le \eta \le 1\). وعليه يكون احتمال النجاح الأمثل
$$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$$
وهذه هي الصيغة التي تطبقها الشيفرة مباشرةً.
في هذا المثال تكون الميزانية \(B=1/2\). تحت القياس \(Q\) نحصل على
$$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$$
وتحت القياس \(P\) نحصل على
$$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$$
إذا أخذنا طبقة \(w=2\) بالكامل فإننا نستهلك كتلة \(Q\) مقدارها \(1/4\). يتبقى إذن \(1/4\) من الميزانية، ولذلك نأخذ من طبقة \(w=1\) النسبة
$$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}.$$
ومن ثم يكون احتمال النجاح الأعظمي
$$0.36 + \frac{1}{2}\cdot 0.48 = 0.60.$$
وهذا يطابق تمامًا حالة التحقق الصغيرة الموجودة في التطبيقات.
تبدأ التطبيقات بمعالجة الحالة البديهية \(T \le 1\)، حيث يكون النجاح مضمونًا. وإلا فإنها تضبط ميزانية \(Q\) على \(1/T\)، ثم تبني التوزيع الطبقي الكامل \((q_0,\dots,q_N)\) تحت القياس العادل بواسطة العلاقة التكرارية المستقرة
$$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$$
بعد ذلك تُستعاد القيم \((p_0,\dots,p_N)\) من الطبقات نفسها باستخدام
$$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w,$$
وهو ما يتجنب الحساب المباشر للمضروبات والمعاملات الثنائية الضخمة ويحافظ على الاستقرار العددي. في المرحلة الأخيرة يجري مسح الطبقات من \(w=N\) إلى \(0\)، وتُضاف الطبقات الكاملة ما دامت الميزانية تسمح بذلك، ثم تُحدد أول طبقة تتسبب في تجاوز الميزانية، ويؤخذ منها فقط الجزء اللازم. تطبيقات C++ وPython وJava تتبع جميعها المنهج نفسه مع اختلاف نوع الأعداد فقط.
بناء مصفوفتَي الكتل الطبقية يحتاج إلى زمن \(O(N)\)، كما أن المسح النهائي التنازلي يحتاج أيضًا إلى زمن \(O(N)\). وبما أن التطبيقات تخزن توزيعي \(Q\) و\(P\) صراحةً لكل القيم الممكنة وعددها \(N+1\)، فإن استهلاك الذاكرة هو \(O(N)\). وبالنسبة إلى \(N=1000\) فإن هذا الاستهلاك صغير جدًا.