Louise and Julie draw independent \(U(0,1)\) numbers and keep a common running total. Louise stops when the total first exceeds \(1\) and records her final draw \(x\). Julie then continues from that same total, stops when the total first exceeds \(2\), and records her final draw \(y\). The goal is to compute
$$\Pr(y \gt x).$$
The implementations evaluate this probability exactly and obtain
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
So Julie is favored, but only slightly.
The solution has three clean pieces: first derive the distribution of the final draw for crossing a threshold in \([0,1]\), then derive the joint density of Louise's last draw and overshoot above \(1\), and finally integrate the conditional probability that Julie's last draw is larger.
For \(0 \le t \le 1\) and \(0 \le z \le 1\), define
$$G(t,z)=\Pr(L_t \le z).$$
Condition on the first new draw \(u \sim U(0,1)\).
If \(u \gt t\), then the threshold is crossed immediately and the last draw is exactly \(u\). This contributes
$$\Pr(t \lt u \le z)=\max(0,z-t).$$
If \(u \le t\), then after subtracting \(u\) from the remaining distance, the problem restarts with threshold \(t-u\). Averaging over \(u\) gives the renewal equation
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
With the substitution \(v=t-u\), this becomes
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t).$$
Differentiate with respect to \(t\).
For \(0 \le t \lt z\), the boundary term is \(z-t\), so
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
The solution is
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1).$$
For \(0 \le z \le t \le 1\), the boundary term is \(0\), so
$$\frac{\partial G}{\partial t}=G.$$
Using continuity at \(t=z\), we obtain
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1).$$
Thus the last-draw CDF is
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1. \end{cases}$$
It also satisfies the expected boundary values \(G(0,z)=z\), \(G(t,0)=0\), and \(G(t,1)=1\).
Let \(s\) be the running total immediately before Louise's last draw. Then \(0 \lt s \lt 1\). If this state is reached after exactly \(n\) previous draws, the density of the sum of \(n\) independent \(U(0,1)\) variables on the interval \([0,1]\) is the first branch of the Irwin-Hall distribution:
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
Summing over all possible numbers of previous draws gives the density of the pre-crossing state:
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1).$$
Now let \(x\) be Louise's last draw and let \(w\) be the overshoot above \(1\). Then
$$s+x=1+w,\qquad s=1+w-x.$$
Because \(0 \le s \le 1\) and \(0 \le x \le 1\), the admissible region is
$$0 \le w \le x \le 1.$$
Given \(s\), the last draw is uniform on the interval \((1-s,1)\), so its density is simply \(1\) there. Therefore the joint density of \((x,w)\) is
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1).$$
A quick normalization check confirms that this is correct:
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1.$$
After Louise stops, the common running total is \(1+w\). Julie therefore needs only an additional amount
$$t=1-w$$
to exceed \(2\). Conditioned on \((x,w)\), Julie's phase is a fresh threshold-crossing problem with threshold \(1-w\). Hence
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x).$$
Integrating over Louise's terminal state gives
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw.$$
The formula for \(G\) depends on whether \(1-w\) is smaller or larger than \(x\).
If \(x+w \gt 1\), then \(1-w \lt x\), so the first branch applies:
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
Multiplying by the joint density gives
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}.$$
If \(x+w \le 1\), then \(1-w \ge x\), so the second branch applies:
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
After multiplication by \(e^{1+w-x}\), the integrand becomes
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}.$$
Therefore we split the integral along the line \(x=1-w\).
For \(0 \le w \le \tfrac12\), the line \(x=1-w\) lies inside the interval \([w,1]\). For \(w \ge \tfrac12\), the whole interval satisfies \(x+w \gt 1\). Thus
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
The inner integrals simplify to
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right).$$
So we only need two one-dimensional integrals:
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
The \(e^{3/2}\) terms cancel, leaving
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}.$$
Numerically,
$$\Pr(y \gt x)\approx 0.5276662759.$$
The C++, Python, and Java implementations all use the exact closed form \(\frac{1+14e-5e^2}{4}\) as the final result. The C++ implementation additionally performs independent checks: it verifies the boundary behavior of the last-draw distribution, tests the renewal identity numerically at several sample points, and compares the exact closed form against a separate two-dimensional Simpson integration of the probability integral. The Python and Java implementations simply evaluate the closed form and format the answer to 10 decimal places.
The exact computation is \(O(1)\) time and \(O(1)\) memory because it reduces to a fixed closed-form expression. The numerical verification in the C++ implementation uses Simpson quadrature on a grid of \(N_w\) overshoot slices and \(N_x\) inner points, so that validation path costs \(O(N_wN_x)\) time. Its outer slices are independent, so that validation can be parallelized. Memory usage remains \(O(N_w)\) for the stored inner values.
Louise und Julie ziehen unabhängige Zahlen aus \(U(0,1)\) und führen dieselbe laufende Summe fort. Louise stoppt, sobald die Summe erstmals größer als \(1\) wird, und notiert ihren letzten Zug \(x\). Julie setzt von genau diesem Zwischenstand aus fort, stoppt beim ersten Überschreiten von \(2\) und notiert ihren letzten Zug \(y\). Gesucht ist
$$\Pr(y \gt x).$$
Die Implementierungen berechnen diese Wahrscheinlichkeit exakt und erhalten
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
Julie ist also leicht im Vorteil.
Die Herleitung zerfällt in drei Teile: Zuerst bestimmen wir die Verteilung des letzten Zugs beim Überschreiten einer Schwelle in \([0,1]\). Danach bestimmen wir die gemeinsame Dichte von Louises letztem Zug und ihrem Überschuss über \(1\). Schließlich integrieren wir die bedingte Wahrscheinlichkeit, dass Julies letzter Zug größer ist.
Für \(0 \le t \le 1\) und \(0 \le z \le 1\) definieren wir
$$G(t,z)=\Pr(L_t \le z).$$
Wir konditionieren auf den ersten neuen Zug \(u \sim U(0,1)\).
Falls \(u \gt t\), wird die Schwelle sofort überschritten und der letzte Zug ist genau \(u\). Dieser Beitrag ist
$$\Pr(t \lt u \le z)=\max(0,z-t).$$
Falls \(u \le t\), bleibt danach dieselbe Aufgabe mit Restschwelle \(t-u\). Durch Mittelung über \(u\) erhält man die Erneuerungsgleichung
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
Mit der Substitution \(v=t-u\) folgt
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t).$$
Nun differenzieren wir nach \(t\).
Für \(0 \le t \lt z\) ist der Randterm \(z-t\), also
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
Daraus folgt
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1).$$
Für \(0 \le z \le t \le 1\) verschwindet der Randterm und es gilt
$$\frac{\partial G}{\partial t}=G.$$
Mit Stetigkeit bei \(t=z\) erhalten wir
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1).$$
Somit ist die Verteilungsfunktion des letzten Zugs
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1. \end{cases}$$
Sie erfüllt außerdem die Randwerte \(G(0,z)=z\), \(G(t,0)=0\) und \(G(t,1)=1\).
Sei \(s\) die laufende Summe unmittelbar vor Louises letztem Zug. Dann gilt \(0 \lt s \lt 1\). Wird dieser Zustand nach genau \(n\) vorherigen Zügen erreicht, so hat die Summe von \(n\) unabhängigen \(U(0,1)\)-Zufallsvariablen auf \([0,1]\) die erste Verzweigung der Irwin-Hall-Verteilung:
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
Summiert man über alle möglichen Anzahlen vorheriger Züge, so erhält man die Dichte des Zustands direkt vor dem Überschreiten:
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1).$$
Nun sei \(x\) Louises letzter Zug und \(w\) der Überschuss über \(1\). Dann gilt
$$s+x=1+w,\qquad s=1+w-x.$$
Wegen \(0 \le s \le 1\) und \(0 \le x \le 1\) ist der zulässige Bereich
$$0 \le w \le x \le 1.$$
Für festes \(s\) ist der letzte Zug auf \((1-s,1)\) gleichverteilt, also mit Dichte \(1\). Daher lautet die gemeinsame Dichte von \((x,w)\)
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1).$$
Die Normierung stimmt:
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1.$$
Nach Louises Stopp ist die gemeinsame Summe gleich \(1+w\). Julie muss also nur noch den Restbetrag
$$t=1-w$$
übertreffen, um \(2\) zu überschreiten. Bedingt auf \((x,w)\) ist Julies Phase damit ein neuer Schwellenüberschreitungsprozess mit Schwelle \(1-w\). Also
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x).$$
Durch Integration über Louises Endzustand erhalten wir
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw.$$
Welche Formel für \(G\) gilt, hängt davon ab, ob \(1-w\) kleiner oder größer als \(x\) ist.
Für \(x+w \gt 1\) gilt \(1-w \lt x\), also verwendet man den ersten Zweig:
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
Mit der gemeinsamen Dichte vereinfacht sich der Integrand zu
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}.$$
Für \(x+w \le 1\) gilt \(1-w \ge x\), also verwendet man den zweiten Zweig:
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
Nach Multiplikation mit \(e^{1+w-x}\) erhält man
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}.$$
Daher zerlegen wir das Integral entlang der Geraden \(x=1-w\).
Für \(0 \le w \le \tfrac12\) liegt die Gerade \(x=1-w\) innerhalb des Intervalls \([w,1]\). Für \(w \ge \tfrac12\) gilt auf dem ganzen Intervall bereits \(x+w \gt 1\). Also
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
Die inneren Integrale vereinfachen sich zu
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right).$$
Damit bleiben nur noch zwei eindimensionale Integrale:
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
Die Terme mit \(e^{3/2}\) heben sich weg, und es bleibt
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}.$$
Numerisch ergibt das
$$\Pr(y \gt x)\approx 0.5276662759.$$
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe exakte geschlossene Form \(\frac{1+14e-5e^2}{4}\). Die C++-Implementierung führt zusätzlich unabhängige Kontrollen aus: Sie überprüft das Randverhalten der Verteilung des letzten Zugs, testet die Erneuerungsgleichung numerisch an mehreren Beispielpunkten und vergleicht die exakte geschlossene Form mit einer separaten zweidimensionalen Simpson-Integration des Wahrscheinlichkeitsintegrals. Die Python- und Java-Implementierungen werten nur die geschlossene Form aus und formatieren das Ergebnis mit 10 Nachkommastellen.
Die exakte Berechnung selbst hat \(O(1)\) Laufzeit und \(O(1)\) Speicherbedarf, weil sie auf einen festen geschlossenen Ausdruck reduziert ist. Die numerische Verifikation in der C++-Implementierung benutzt Simpson-Quadratur auf einem Gitter mit \(N_w\) Overshoot-Schnitten und \(N_x\) inneren Punkten und kostet daher \(O(N_wN_x)\) Zeit. Die äußeren Schnitte sind unabhängig und können parallel verarbeitet werden. Der Speicherbedarf bleibt \(O(N_w)\) für die gespeicherten inneren Werte.
Louise ve Julie bağımsız \(U(0,1)\) sayıları çekiyor ve aynı kümülatif toplamı sürdürüyor. Louise toplam ilk kez \(1\)'i geçtiğinde durup son çekilişini \(x\) olarak kaydediyor. Julie aynı toplamdan devam ediyor, toplam ilk kez \(2\)'yi geçtiğinde duruyor ve son çekilişini \(y\) olarak kaydediyor. Aranan olasılık
$$\Pr(y \gt x).$$
Uygulamalar bu olasılığı tam olarak hesaplayıp şu sonucu veriyor:
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
Yani Julie'nin avantajı var, ancak fark küçüktür.
Çözüm üç adımdan oluşur: önce \([0,1]\) içindeki bir eşiği aşarken son çekilişin dağılımını çıkarırız, sonra Louise'in son çekilişi ile \(1\) üzerindeki taşma miktarının ortak yoğunluğunu buluruz, en sonunda da Julie'nin son çekilişinin daha büyük olma olasılığını integre ederiz.
\(0 \le t \le 1\) ve \(0 \le z \le 1\) için
$$G(t,z)=\Pr(L_t \le z)$$
tanımını yapalım. İlk yeni çekilişi \(u \sim U(0,1)\) ile koşullandıralım.
Eğer \(u \gt t\) ise eşik hemen aşılır ve son çekiliş doğrudan \(u\) olur. Bu katkı
$$\Pr(t \lt u \le z)=\max(0,z-t)$$
şeklindedir. Eğer \(u \le t\) ise geriye \(t-u\) kadar mesafe kalır ve problem aynı biçimde yeniden başlar. \(u\) üzerinde ortalama alınca yenilenme denklemi elde edilir:
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
\(v=t-u\) dönüşümü ile
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t)$$
olur. Şimdi \(t\)'ye göre türev alalım.
\(0 \le t \lt z\) için sınır terimi \(z-t\) olduğundan
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
Buradan
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1)$$
çıkar. \(0 \le z \le t \le 1\) için sınır terimi yok olur ve
$$\frac{\partial G}{\partial t}=G$$
elde edilir. \(t=z\) noktasındaki süreklilikten
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1)$$
sonucuna ulaşırız. Böylece son çekiliş dağılımı
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1 \end{cases}$$
olur. Ayrıca \(G(0,z)=z\), \(G(t,0)=0\) ve \(G(t,1)=1\) sınır değerlerini de sağlar.
\(s\), Louise'in son çekilişinden hemen önceki toplam olsun. O halde \(0 \lt s \lt 1\). Bu durum tam olarak \(n\) önceki çekilişten sonra oluşmuşsa, \(n\) bağımsız \(U(0,1)\) değişkeninin toplamı \([0,1]\) aralığında Irwin-Hall dağılımının ilk parçasına sahiptir:
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
Tüm olası önceki çekiliş sayıları üzerinden toplarsak, eşiğe gelmeden hemen önceki durumun yoğunluğu
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1)$$
olur. Şimdi \(x\) Louise'in son çekilişi, \(w\) ise \(1\) üzerindeki taşması olsun. O zaman
$$s+x=1+w,\qquad s=1+w-x.$$
\(0 \le s \le 1\) ve \(0 \le x \le 1\) koşullarından izinli bölge
$$0 \le w \le x \le 1$$
şeklindedir. Sabit \(s\) için son çekiliş \((1-s,1)\) aralığında uniform olduğundan yoğunluğu \(1\)'dir. Dolayısıyla \((x,w)\) ortak yoğunluğu
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1)$$
olur. Gerçekten de
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1$$
eşitliği normlamayı doğrular.
Louise durduğunda ortak toplam \(1+w\) olur. Julie'nin \(2\)'yi geçmek için ihtiyaç duyduğu ek miktar
$$t=1-w$$
olur. \((x,w)\) verildiğinde Julie'nin aşaması, eşiği \(1-w\) olan yeni bir ilk-geçiş problemidir. Bu yüzden
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x)$$
yazarız. Louise'in son durumu üzerinde integral alınca
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw$$
elde edilir.
\(G\) için hangi kapalı formun kullanılacağı, \(1-w\) ile \(x\)'in karşılaştırılmasına bağlıdır.
Eğer \(x+w \gt 1\) ise \(1-w \lt x\) olur ve ilk dal geçerlidir:
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
Bunu ortak yoğunlukla çarparsak integrand
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}$$
şeklinde sadeleşir. Eğer \(x+w \le 1\) ise \(1-w \ge x\) olur ve ikinci dal kullanılır:
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
\(e^{1+w-x}\) ile çarpınca integrand
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}$$
olur. Bu yüzden integrali \(x=1-w\) doğrusu boyunca ayırırız.
\(0 \le w \le \tfrac12\) için \(x=1-w\) doğrusu \([w,1]\) aralığının içindedir. \(w \ge \tfrac12\) için ise tüm aralıkta zaten \(x+w \gt 1\) geçerlidir. Dolayısıyla
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
İç integraller
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right)$$
şekline iner. Böylece iki tek boyutlu integral kalır:
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
\(e^{3/2}\) terimleri birbirini götürür ve sonuç
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}$$
olur. Sayısal değer
$$\Pr(y \gt x)\approx 0.5276662759$$
şeklindedir.
C++, Python ve Java implementasyonlarının hepsi nihai sonuç olarak aynı kapalı formu, yani \(\frac{1+14e-5e^2}{4}\) ifadesini kullanır. C++ implementasyonu buna ek olarak bağımsız doğrulamalar içerir: son çekiliş dağılımının sınır davranışını kontrol eder, yenilenme özdeşliğini birkaç örnek noktada sayısal olarak test eder ve kapalı form sonucu olasılık integralinin ayrı bir iki boyutlu Simpson integrasyonu ile karşılaştırır. Python ve Java implementasyonları ise kapalı formu doğrudan değerlendirip sonucu 10 ondalık basamakla yazar.
Asıl hesap sabit sayıda aritmetik işlem içerdiği için \(O(1)\) zaman ve \(O(1)\) bellek kullanır. C++ implementasyonundaki sayısal doğrulama, \(N_w\) taşma dilimi ve \(N_x\) iç nokta kullanan Simpson integrasyonuna dayandığından \(O(N_wN_x)\) zaman maliyetine sahiptir. Dış dilimler birbirinden bağımsız olduğu için bu doğrulama paralelleştirilebilir. Saklanan iç değerler nedeniyle bellek kullanımı \(O(N_w)\) düzeyinde kalır.
Louise y Julie extraen números independientes con distribución \(U(0,1)\) y comparten la misma suma acumulada. Louise se detiene cuando la suma supera por primera vez \(1\) y registra su última extracción \(x\). Julie continúa desde ese mismo total, se detiene cuando la suma supera por primera vez \(2\) y registra su última extracción \(y\). Debemos calcular
$$\Pr(y \gt x).$$
Las implementaciones evalúan esta probabilidad de forma exacta y obtienen
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
Por lo tanto Julie tiene una ventaja ligera.
La derivación tiene tres partes. Primero se obtiene la distribución de la última extracción al cruzar un umbral en \([0,1]\). Después se deduce la densidad conjunta de la última extracción de Louise y del exceso sobre \(1\). Finalmente se integra la probabilidad condicional de que la última extracción de Julie sea mayor.
Para \(0 \le t \le 1\) y \(0 \le z \le 1\), definimos
$$G(t,z)=\Pr(L_t \le z).$$
Condicionamos sobre la primera nueva extracción \(u \sim U(0,1)\).
Si \(u \gt t\), el umbral se supera inmediatamente y la última extracción es exactamente \(u\). Esa contribución es
$$\Pr(t \lt u \le z)=\max(0,z-t).$$
Si \(u \le t\), el problema se reinicia con umbral restante \(t-u\). Promediando sobre \(u\), obtenemos la ecuación de renovación
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
Con el cambio \(v=t-u\), queda
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t).$$
Ahora diferenciamos respecto de \(t\).
Para \(0 \le t \lt z\), el término de borde es \(z-t\), así que
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
De aquí sale
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1).$$
Para \(0 \le z \le t \le 1\), el término de borde vale \(0\), y entonces
$$\frac{\partial G}{\partial t}=G.$$
Usando continuidad en \(t=z\), obtenemos
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1).$$
Por tanto, la CDF de la última extracción es
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1. \end{cases}$$
Además cumple los valores de borde \(G(0,z)=z\), \(G(t,0)=0\) y \(G(t,1)=1\).
Sea \(s\) la suma acumulada justo antes de la última extracción de Louise. Entonces \(0 \lt s \lt 1\). Si ese estado se alcanza tras exactamente \(n\) extracciones previas, la densidad de la suma de \(n\) variables \(U(0,1)\) en \([0,1]\) coincide con la primera rama de la distribución de Irwin-Hall:
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
Sumando sobre todos los posibles números de extracciones previas, obtenemos la densidad del estado justo antes del cruce:
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1).$$
Ahora \(x\) será la última extracción de Louise y \(w\) el exceso por encima de \(1\). Entonces
$$s+x=1+w,\qquad s=1+w-x.$$
Como \(0 \le s \le 1\) y \(0 \le x \le 1\), la región admisible es
$$0 \le w \le x \le 1.$$
Fijado \(s\), la última extracción es uniforme en \((1-s,1)\), así que su densidad allí es \(1\). Por ello, la densidad conjunta de \((x,w)\) es
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1).$$
Se comprueba fácilmente que está normalizada:
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1.$$
Cuando Louise se detiene, la suma común vale \(1+w\). Julie necesita entonces una cantidad adicional
$$t=1-w$$
para superar \(2\). Condicionado \((x,w)\), el problema de Julie es un nuevo problema de primer cruce con umbral \(1-w\). Por tanto,
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x).$$
Integrando sobre el estado final de Louise, resulta
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw.$$
La fórmula aplicable para \(G\) depende de si \(1-w\) es menor o mayor que \(x\).
Si \(x+w \gt 1\), entonces \(1-w \lt x\), y usamos la primera rama:
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
Multiplicando por la densidad conjunta, el integrando se simplifica a
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}.$$
Si \(x+w \le 1\), entonces \(1-w \ge x\), y usamos la segunda rama:
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
Tras multiplicar por \(e^{1+w-x}\), el integrando queda
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}.$$
Así, partimos la integral sobre la recta \(x=1-w\).
Para \(0 \le w \le \tfrac12\), la recta \(x=1-w\) cae dentro del intervalo \([w,1]\). Para \(w \ge \tfrac12\), todo el intervalo satisface ya \(x+w \gt 1\). En consecuencia,
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
Las integrales internas se reducen a
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right).$$
Por tanto, sólo quedan dos integrales unidimensionales:
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
Los términos con \(e^{3/2}\) se cancelan y queda
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}.$$
Numéricamente,
$$\Pr(y \gt x)\approx 0.5276662759.$$
Las implementaciones en C++, Python y Java usan todas la misma forma cerrada exacta \(\frac{1+14e-5e^2}{4}\). La implementación en C++ además incorpora verificaciones independientes: comprueba el comportamiento de borde de la distribución de la última extracción, verifica numéricamente la identidad de renovación en varios puntos de muestra y compara la forma cerrada exacta con una integración bidimensional de Simpson aplicada por separado a la integral de probabilidad. Las implementaciones en Python y Java evalúan directamente la forma cerrada y muestran el resultado con 10 decimales.
El cálculo exacto final requiere sólo un número fijo de operaciones aritméticas, por lo que cuesta \(O(1)\) tiempo y \(O(1)\) memoria. La validación numérica de la implementación en C++ usa cuadratura de Simpson sobre una malla con \(N_w\) cortes de exceso y \(N_x\) puntos interiores, de modo que esa ruta de validación cuesta \(O(N_wN_x)\) tiempo. Los cortes externos son independientes, así que la validación puede paralelizarse. La memoria se mantiene en \(O(N_w)\) para almacenar los valores interiores.
Louise 和 Julie 依次抽取独立的 \(U(0,1)\) 随机数，并共享同一个累加和。Louise 在总和第一次超过 \(1\) 时停止，并记下最后一次抽样 \(x\)。Julie 从这个总和继续，直到总和第一次超过 \(2\) 时停止，并记下最后一次抽样 \(y\)。要求计算
$$\Pr(y \gt x).$$
实现使用精确公式，结果为
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
因此 Julie 略占优势。
推导分成三步：先求“越过阈值时最后一次抽样”的分布，再求 Louise 的最后一次抽样与超过 \(1\) 的超量之间的联合密度，最后把 Julie 获胜的条件概率积分掉。
对 \(0 \le t \le 1\) 与 \(0 \le z \le 1\)，定义
$$G(t,z)=\Pr(L_t \le z).$$
对第一步新抽样 \(u \sim U(0,1)\) 分情况讨论。
如果 \(u \gt t\)，那么立刻越过阈值，最后一次抽样就是 \(u\)。这一部分贡献为
$$\Pr(t \lt u \le z)=\max(0,z-t).$$
如果 \(u \le t\)，那么剩余距离变成 \(t-u\)，问题以同样形式重新开始。对 \(u\) 取平均，得到更新方程
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
令 \(v=t-u\)，可写成
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t).$$
接着对 \(t\) 求导。
当 \(0 \le t \lt z\) 时，边界项为 \(z-t\)，因此
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
解得
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1).$$
当 \(0 \le z \le t \le 1\) 时，边界项为 \(0\)，于是
$$\frac{\partial G}{\partial t}=G.$$
再利用 \(t=z\) 处的连续性，得到
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1).$$
所以最后一次抽样的分布函数为
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1. \end{cases}$$
它还满足边界条件 \(G(0,z)=z\)、\(G(t,0)=0\)、\(G(t,1)=1\)。
记 \(s\) 为 Louise 最后一次抽样之前的累加和，则 \(0 \lt s \lt 1\)。如果这个状态是在恰好 \(n\) 次先前抽样后到达的，那么 \(n\) 个独立 \(U(0,1)\) 变量之和在 \([0,1]\) 上的密度就是 Irwin-Hall 分布的第一段：
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
把所有可能的先前步数加总，可得越界前状态的密度
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1).$$
现在令 \(x\) 表示 Louise 的最后一次抽样，\(w\) 表示超过 \(1\) 的超量，则
$$s+x=1+w,\qquad s=1+w-x.$$
由 \(0 \le s \le 1\) 与 \(0 \le x \le 1\) 可知允许区域为
$$0 \le w \le x \le 1.$$
在给定 \(s\) 的条件下，最后一次抽样在区间 \((1-s,1)\) 上均匀分布，因此密度为 \(1\)。于是 \((x,w)\) 的联合密度为
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1).$$
简单检查可知它确实归一化：
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1.$$
当 Louise 停止时，共同总和是 \(1+w\)。因此 Julie 还需要额外增加
$$t=1-w$$
才能超过 \(2\)。在给定 \((x,w)\) 的条件下，Julie 的部分就是一个阈值为 \(1-w\) 的全新首达问题。所以
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x).$$
对 Louise 的末状态积分后得到
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw.$$
\(G\) 的具体表达式取决于 \(1-w\) 与 \(x\) 的大小关系。
若 \(x+w \gt 1\)，则 \(1-w \lt x\)，此时使用第一段公式：
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
乘上联合密度后，积分核化简为
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}.$$
若 \(x+w \le 1\)，则 \(1-w \ge x\)，此时使用第二段公式：
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
与 \(e^{1+w-x}\) 相乘后得到
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}.$$
因此需要沿直线 \(x=1-w\) 把积分拆开。
当 \(0 \le w \le \tfrac12\) 时，直线 \(x=1-w\) 位于区间 \([w,1]\) 内部；当 \(w \ge \tfrac12\) 时，整个区间都满足 \(x+w \gt 1\)。因此
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
内部积分可化为
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right).$$
于是只剩两个一维积分：
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
\(e^{3/2}\) 项恰好相消，因此
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}.$$
数值上为
$$\Pr(y \gt x)\approx 0.5276662759.$$
C++、Python 和 Java 实现都直接使用同一个精确闭式 \(\frac{1+14e-5e^2}{4}\)。其中 C++ 实现还加入了独立校验：它检查最后一次抽样分布的边界值，在多个采样点上数值验证更新方程，并用独立的二维 Simpson 积分去核对这个闭式结果。Python 和 Java 实现则直接计算闭式并把答案格式化到小数点后 10 位。
最终精确答案只需要固定次数的算术运算，因此主计算的时间复杂度为 \(O(1)\)，空间复杂度为 \(O(1)\)。C++ 实现中的数值校验采用 \(N_w\) 个超量切片和 \(N_x\) 个内层积分点的 Simpson 求积，因此这条验证路径的时间复杂度为 \(O(N_wN_x)\)。外层切片彼此独立，所以可以并行化。保存内层结果所需的内存为 \(O(N_w)\)。
Луиза и Жюли тянут независимые числа из \(U(0,1)\) и продолжают одну и ту же накопленную сумму. Луиза останавливается, когда сумма впервые превышает \(1\), и записывает свой последний ход \(x\). Затем Жюли продолжает с того же значения суммы, останавливается при первом превышении \(2\) и записывает свой последний ход \(y\). Требуется найти
$$\Pr(y \gt x).$$
Реализации вычисляют эту вероятность точно и получают
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
Значит, преимущество у Жюли, но оно невелико.
Решение удобно разбить на три части: сначала вывести распределение последнего хода при переходе через порог из \([0,1]\), затем получить совместную плотность последнего хода Луизы и её перелёта через \(1\), и наконец проинтегрировать условную вероятность события \(y \gt x\).
Для \(0 \le t \le 1\) и \(0 \le z \le 1\) введём
$$G(t,z)=\Pr(L_t \le z).$$
Условимся по первому новому ходу \(u \sim U(0,1)\).
Если \(u \gt t\), то порог пересекается сразу, и последний ход равен \(u\). Этот вклад равен
$$\Pr(t \lt u \le z)=\max(0,z-t).$$
Если \(u \le t\), то после вычитания \(u\) остаётся точно такая же задача с порогом \(t-u\). Усреднение по \(u\) даёт уравнение восстановления
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
После замены \(v=t-u\) получаем
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t).$$
Теперь дифференцируем по \(t\).
При \(0 \le t \lt z\) граничный член равен \(z-t\), поэтому
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
Отсюда следует
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1).$$
При \(0 \le z \le t \le 1\) граничный член равен нулю, и тогда
$$\frac{\partial G}{\partial t}=G.$$
Используя непрерывность в точке \(t=z\), получаем
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1).$$
Итак, функция распределения последнего хода имеет вид
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1. \end{cases}$$
Она также удовлетворяет естественным граничным условиям \(G(0,z)=z\), \(G(t,0)=0\) и \(G(t,1)=1\).
Обозначим через \(s\) накопленную сумму непосредственно перед последним ходом Луизы. Тогда \(0 \lt s \lt 1\). Если этот уровень достигается ровно после \(n\) предыдущих ходов, то плотность суммы \(n\) независимых величин \(U(0,1)\) на отрезке \([0,1]\) совпадает с первой ветвью распределения Ирвина-Холла:
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
Суммируя по всем возможным значениям \(n\), получаем плотность состояния непосредственно перед пересечением порога:
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1).$$
Теперь пусть \(x\) — последний ход Луизы, а \(w\) — перелёт через \(1\). Тогда
$$s+x=1+w,\qquad s=1+w-x.$$
Из условий \(0 \le s \le 1\) и \(0 \le x \le 1\) следует допустимая область
$$0 \le w \le x \le 1.$$
При фиксированном \(s\) последний ход равномерно распределён на интервале \((1-s,1)\), значит его плотность там равна \(1\). Следовательно, совместная плотность \((x,w)\) равна
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1).$$
Нормировка проверяется напрямую:
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1.$$
После остановки Луизы общая сумма равна \(1+w\). Значит, Жюли требуется добрать лишь
$$t=1-w$$
чтобы превысить \(2\). При фиксированных \((x,w)\) её часть игры является новым процессом первого прохода с порогом \(1-w\). Поэтому
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x).$$
Интегрируя по конечному состоянию Луизы, получаем
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw.$$
Нужная формула для \(G\) зависит от того, меньше или больше число \(1-w\), чем \(x\).
Если \(x+w \gt 1\), то \(1-w \lt x\), и используется первая ветвь:
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
После умножения на совместную плотность интегранд упрощается до
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}.$$
Если \(x+w \le 1\), то \(1-w \ge x\), и используется вторая ветвь:
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
После умножения на \(e^{1+w-x}\) получаем
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}.$$
Значит, интеграл нужно разрезать по прямой \(x=1-w\).
При \(0 \le w \le \tfrac12\) прямая \(x=1-w\) проходит внутри отрезка \([w,1]\). При \(w \ge \tfrac12\) весь отрезок уже удовлетворяет условию \(x+w \gt 1\). Поэтому
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
Внутренние интегралы сводятся к формулам
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right).$$
Остаются две одномерные интеграции:
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
Члены с \(e^{3/2}\) сокращаются, и остаётся
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}.$$
Численно это равно
$$\Pr(y \gt x)\approx 0.5276662759.$$
Реализации на C++, Python и Java используют одну и ту же точную формулу \(\frac{1+14e-5e^2}{4}\). Реализация на C++ дополнительно выполняет независимые проверки: контролирует граничные значения распределения последнего хода, численно проверяет уравнение восстановления в нескольких точках и сравнивает точную формулу с отдельным двумерным интегрированием по правилу Симпсона. Реализации на Python и Java напрямую вычисляют закрытую формулу и выводят ответ с точностью до 10 знаков после запятой.
Само точное вычисление требует лишь фиксированного числа арифметических операций, поэтому занимает \(O(1)\) времени и \(O(1)\) памяти. Численная проверка в реализации на C++ использует квадратурную схему Симпсона на сетке из \(N_w\) срезов по перелёту и \(N_x\) внутренних точек, так что эта проверочная ветка стоит \(O(N_wN_x)\) по времени. Внешние срезы независимы, поэтому проверка естественно распараллеливается. Память остаётся \(O(N_w)\) за счёт хранения внутренних значений.
تسحب لويز وجولي أعدادًا مستقلة من التوزيع \(U(0,1)\) وتتابعان المجموع التراكمي نفسه. تتوقف لويز عندما يتجاوز المجموع \(1\) لأول مرة وتسجل السحبة الأخيرة \(x\). ثم تكمل جولي من ذلك المجموع نفسه، وتتوقف عندما يتجاوز المجموع \(2\) لأول مرة وتسجل السحبة الأخيرة \(y\). المطلوب حساب
$$\Pr(y \gt x).$$
تعطي التنفيذات قيمة دقيقة لهذه الاحتمالية:
$$\boxed{\Pr(y \gt x)=\frac{1+14e-5e^2}{4}\approx 0.5276662759.}$$
إذًا جولي مفضلة قليلًا.
يمكن تقسيم الاشتقاق إلى ثلاث مراحل: أولًا نحسب توزيع السحبة الأخيرة عند عبور عتبة ضمن \([0,1]\)، ثم نستخرج الكثافة المشتركة بين آخر سحبة للويز ومقدار التجاوز فوق \(1\)، وأخيرًا نكامل الاحتمال الشرطي بأن تكون سحبة جولي الأخيرة أكبر.
لـ \(0 \le t \le 1\) و \(0 \le z \le 1\)، نعرّف
$$G(t,z)=\Pr(L_t \le z).$$
نشرط على السحبة الجديدة الأولى \(u \sim U(0,1)\).
إذا كان \(u \gt t\)، فإن العتبة تُتجاوز مباشرة وتكون السحبة الأخيرة هي \(u\) نفسها. وهذا يساهم بالمقدار
$$\Pr(t \lt u \le z)=\max(0,z-t).$$
أما إذا كان \(u \le t\)، فيبقى مقدار \(t-u\) للوصول إلى العتبة، وتبدأ المسألة نفسها من جديد. بأخذ المتوسط على \(u\) نحصل على معادلة التجديد:
$$G(t,z)=\int_0^t G(t-u,z)\,du+\max(0,z-t).$$
وبالتبديل \(v=t-u\) تصبح
$$G(t,z)=\int_0^t G(v,z)\,dv+\max(0,z-t).$$
الآن نشتق بالنسبة إلى \(t\).
عندما \(0 \le t \lt z\)، يكون حد الحافة هو \(z-t\)، ولذلك
$$\frac{\partial G}{\partial t}=G-1,\qquad G(0,z)=z.$$
ومن ثم
$$G(t,z)=1-(1-z)e^t \qquad (0 \le t \lt z \le 1).$$
وعندما \(0 \le z \le t \le 1\)، يختفي حد الحافة فنحصل على
$$\frac{\partial G}{\partial t}=G.$$
وباستخدام الاستمرارية عند \(t=z\)، نجد
$$G(t,z)=e^t\bigl(e^{-z}-1+z\bigr)\qquad (0 \le z \le t \le 1).$$
إذًا دالة التوزيع التراكمي للسحبة الأخيرة هي
$$G(t,z)= \begin{cases} 1-(1-z)e^t, & 0 \le t \lt z \le 1,\\[4pt] e^t\bigl(e^{-z}-1+z\bigr), & 0 \le z \le t \le 1. \end{cases}$$
كما أنها تحقق القيم الحدية الطبيعية \(G(0,z)=z\) و\(G(t,0)=0\) و\(G(t,1)=1\).
لنرمز بـ \(s\) إلى المجموع مباشرة قبل آخر سحبة للويز. عندئذ \(0 \lt s \lt 1\). إذا وصلنا إلى هذه الحالة بعد \(n\) سحبات سابقة بالضبط، فإن كثافة مجموع \(n\) متغيرات مستقلة من \(U(0,1)\) على الفترة \([0,1]\) هي الفرع الأول من توزيع Irwin-Hall:
$$f_n(s)=\frac{s^{n-1}}{(n-1)!}\qquad (0 \le s \le 1,\ n \ge 1).$$
وبجمع جميع القيم الممكنة لـ \(n\)، نحصل على كثافة الحالة السابقة للعبور:
$$r(s)=\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}=e^s \qquad (0 \le s \le 1).$$
الآن لتكن \(x\) آخر سحبة للويز، و\(w\) مقدار التجاوز فوق \(1\). عندئذ
$$s+x=1+w,\qquad s=1+w-x.$$
ومن الشرطين \(0 \le s \le 1\) و\(0 \le x \le 1\) نحصل على المجال المسموح
$$0 \le w \le x \le 1.$$
ومع تثبيت \(s\)، تكون السحبة الأخيرة موزعة بانتظام على المجال \((1-s,1)\)، لذا كثافتها هناك هي \(1\). وبالتالي فإن الكثافة المشتركة لـ \((x,w)\) تساوي
$$f(x,w)=e^{1+w-x}\qquad (0 \le w \le x \le 1).$$
وفعلًا تحقق التطبيع:
$$\int_0^1\int_w^1 e^{1+w-x}\,dx\,dw=1.$$
بعد توقف لويز، يصبح المجموع المشترك \(1+w\). لذا تحتاج جولي فقط إلى مقدار إضافي
$$t=1-w$$
لكي تتجاوز \(2\). بشرط \((x,w)\)، تصبح مرحلة جولي مسألة عبور أول جديدة بعتبة \(1-w\). لذلك
$$\Pr(y \gt x \mid x,w)=1-G(1-w,x).$$
وبالتكامل على حالات نهاية لويز نحصل على
$$\Pr(y \gt x)=\int_0^1\int_w^1 e^{1+w-x}\bigl(1-G(1-w,x)\bigr)\,dx\,dw.$$
الصيغة المناسبة لـ \(G\) تعتمد على مقارنة \(1-w\) مع \(x\).
إذا كان \(x+w \gt 1\)، فلدينا \(1-w \lt x\)، وعندها نستخدم الفرع الأول:
$$1-G(1-w,x)=(1-x)e^{1-w}.$$
وبعد الضرب في الكثافة المشتركة يتبسط التكامل إلى
$$e^{1+w-x}\bigl(1-G(1-w,x)\bigr)=(1-x)e^{2-x}.$$
أما إذا كان \(x+w \le 1\)، فلدينا \(1-w \ge x\)، فنستخدم الفرع الثاني:
$$1-G(1-w,x)=1-e^{1-w}\bigl(e^{-x}-1+x\bigr).$$
وبالضرب في \(e^{1+w-x}\) يصبح التكامل
$$e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}.$$
إذًا يجب تقسيم التكامل على الخط \(x=1-w\).
عندما \(0 \le w \le \tfrac12\)، يقع الخط \(x=1-w\) داخل الفترة \([w,1]\). وعندما \(w \ge \tfrac12\)، فإن كامل الفترة يحقق أصلًا \(x+w \gt 1\). ومن ثم
$$\begin{aligned} \Pr(y \gt x)=&\int_0^{1/2}\left[\int_w^{1-w}\left(e^{1+w-x}-e^{2-2x}+(1-x)e^{2-x}\right)\,dx\right]dw\\ &+\int_0^{1/2}\left[\int_{1-w}^{1}(1-x)e^{2-x}\,dx\right]dw\\ &+\int_{1/2}^{1}\left[\int_w^{1}(1-x)e^{2-x}\,dx\right]dw. \end{aligned}$$
تتبسط التكاملات الداخلية إلى
$$I_1(w)=2e-we^{2-w}-\frac{e^{2w}}{2}-\frac{e^{2-2w}}{2}\qquad \left(0 \le w \le \frac12\right),$$
$$I_2(w)=e-we^{2-w}\qquad \left(\frac12 \le w \le 1\right).$$
إذًا يتبقى تكاملان أحاديّا البعد:
$$A=\int_0^{1/2} I_1(w)\,dw=\frac14+e-\frac{5e^2}{4}+\frac{3e^{3/2}}{2},$$
$$B=\int_{1/2}^{1} I_2(w)\,dw=\frac{5e}{2}-\frac{3e^{3/2}}{2}.$$
وتتلاشى حدود \(e^{3/2}\) عند الجمع، فنحصل على
$$\Pr(y \gt x)=A+B=\boxed{\frac{1+14e-5e^2}{4}}.$$
وقيمتها العددية
$$\Pr(y \gt x)\approx 0.5276662759.$$
تستخدم تنفيذات C++ وPython وJava الصيغة المغلقة نفسها \(\frac{1+14e-5e^2}{4}\) باعتبارها الجواب النهائي. ويضيف تنفيذ C++ طبقة تحقق مستقلة: فهو يفحص السلوك الحدّي لتوزيع السحبة الأخيرة، ويتحقق عدديًا من هوية التجديد عند عدة نقاط، ثم يقارن الصيغة المغلقة الدقيقة مع تكامل Simpson ثنائي الأبعاد محسوب بصورة مستقلة. أما تنفيذا Python وJava فيقيّمان الصيغة المغلقة مباشرة ويعرضان النتيجة حتى 10 منازل عشرية.
الحساب الدقيق النهائي يحتاج إلى عدد ثابت فقط من العمليات الحسابية، لذا فإن زمنه \(O(1)\) وذاكرته \(O(1)\). أمّا التحقق العددي في تنفيذ C++ فيستخدم تكامل Simpson على شبكة مكوّنة من \(N_w\) شرائح تجاوز و\(N_x\) نقاط داخلية، ولذلك تكلفته الزمنية \(O(N_wN_x)\). الشرائح الخارجية مستقلة عن بعضها، ولذلك يمكن تنفيذ هذا التحقق على التوازي. وتبقى الذاكرة عند \(O(N_w)\) بسبب تخزين القيم الداخلية.