Project Euler Problem 959
A frog is placed on the number line.
Solution
Answer: 0.857162085
Let $R_n$ be the number of distinct integers visited in the first $n$ steps.
For a transient random walk on $\mathbb Z$,
$$\lim_{n\to\infty}\frac{\mathbb E[R_n]}{n} = \frac1{G(0)},$$
where
$$G(0)=\sum_{m=0}^\infty \Pr(S_m=0)$$
is the Green function (expected total number of visits to $0$).
For this walk, each step is either $-a$ or $+b$ with probability $1/2$.
A return to $0$ after $n$ steps is only possible if the number of right jumps is $ak$ and the number of left jumps is $bk$, so
$$n=(a+b)k.$$
Hence
$$\Pr(S_{(a+b)k}=0) = \frac{\binom{(a+b)k}{ak}}{2^{(a+b)k}}.$$
Therefore
$$G(0) = \sum_{k=0}^{\infty} \frac{\binom{(a+b)k}{ak}}{2^{(a+b)k}}.$$
For $(a,b)=(89,97)$,
$$G(0)= \sum_{k=0}^{\infty} \frac{\binom{186k}{89k}}{2^{186k}} \approx 1.1666404958760500068.$$
Thus
$$f(89,97)=\frac1{G(0)} \approx 0.8571620850938173.$$
Rounded to nine digits after the decimal point:
Answer: 0.857162085