Project Euler Problem 661
Two friends A and B are great fans of Chess.
Solution
Answer: 646231.2177
Let the score difference after $n$ games be
$$S_n = (#\text{wins by A})-(#\text{wins by B}).$$
Then after each game:
- $S\to S+1$ with probability $a=p_A$,
- $S\to S-1$ with probability $b=p_B$,
- $S\to S$ with probability $d=1-a-b$.
Also, after every game the match stops with probability $p$, so it continues with probability
$$q=1-p.$$
We want
$$\mathbb E_A(a,b,p) =\sum_{n\ge1}\Pr(S_n>0,\text{ game }n\text{ is played}).$$
Since game $n$ is played iff the previous $n-1$ continuation tosses were tails,
$$\Pr(\text{game }n\text{ played})=q^{,n-1}.$$
Hence
$$\mathbb E_A(a,b,p) =\sum_{n\ge1} q^{n-1}\Pr(S_n>0).$$
1. Solving the random-walk recurrence
Define $F_i$ to be the expected future number of times A leads, starting from score difference $i$.
For $i\ge2$,
$$F_i =1+q(aF_{i+1}+bF_{i-1}+dF_i),$$
because after one more game A is certainly still leading.
For $i\le -1$,
$$F_i=q(aF_{i+1}+bF_{i-1}+dF_i),$$
since A is not currently leading.
At the boundary:
$$F_1=a(1+qF_2)+b(qF_0)+d(1+qF_1),$$
$$F_0=a(1+qF_1)+b(qF_{-1})+d(qF_0).$$
Homogeneous solution
The characteristic equation is
$$qa r^2-(1-qd)r+qb=0.$$
Let its roots be $\alpha,\beta$ with $\alpha<1<\beta$:
$$\alpha,\beta = \frac{1-qd\mp\sqrt{\Delta}}{2qa},$$
where
$$\Delta=(1-qd)^2-4q^2ab.$$
Using $d=1-a-b$,
$$\Delta = p^2+2pq(a+b)+q^2(a-b)^2.$$
The bounded solutions are
$$F_i= \begin{cases} \dfrac1p + B\alpha^i, & i\ge1,\[1ex] C\beta^i, & i\le -1. \end{cases}$$
Solving the boundary equations gives
$$F_0 = \frac{1-\alpha}{pq(\beta-\alpha)}.$$
Using
$$\beta-\alpha=\frac{\sqrt{\Delta}}{qa},$$
and simplifying,
$$\boxed{ \mathbb E_A(a,b,p) = \frac{\sqrt{\Delta}-p+q(a-b)} {2pq\sqrt{\Delta}} }$$
with
$$\Delta = p^2+2pq(a+b)+q^2(a-b)^2.$$
2. Apply to $H(50)$
We are given
$$a=\frac1{\sqrt{k+3}}, \qquad b=\frac1{\sqrt{k+3}}+\frac1{k^2}, \qquad p=\frac1{k^3}.$$
So
$$H(50) = \sum_{k=3}^{50} \mathbb E_A(a,b,p).$$
3. Python implementation
from math import sqrt
def EA(a, b, p):
q = 1.0 - p
Delta = (
p * p
+ 2.0 * p * q * (a + b)
+ q * q * (a - b) * (a - b)
)
root = sqrt(Delta)
return (root - p + q * (a - b)) / (2.0 * p * q * root)
H = 0.0
for k in range(3, 51):
a = 1.0 / sqrt(k + 3)
b = a + 1.0 / (k * k)
p = 1.0 / (k ** 3)
H += EA(a, b, p)
print("{:.10f}".format(H))
4. Verification against the examples
For
$$(a,b,p)=(0.25,0.25,0.5),$$
the formula gives
$$0.5857864376\ldots$$
matching the statement.
For
$$(a,b,p)=(0.47,0.48,0.001),$$
it gives
$$377.4717357\ldots$$
again matching the statement.
Finally,
$$H(50)=646231.2176705868\ldots$$
which rounds to 4 decimal places as
$$646231.2177.$$
Answer: 646231.2177