Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Distribution of the Last Draw for a Residual Threshold

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\).

Step 2: Joint Density of Louise's Last Draw and Overshoot

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.$

Step 3: Condition Julie's Phase on Louise's Terminal State

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.$

Step 4: Split the Domain Along \(x+w=1\)

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\).

Step 5: Evaluate the Integral Exactly

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.$

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=436
2. Renewal theory: Wikipedia — Renewal theory
3. Irwin-Hall distribution: Wikipedia — Irwin-Hall distribution
4. Simpson's rule: Wikipedia — Simpson's rule