Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1\$ on heads and losing 1\$ on tails. Both start at 0\$ and have infinite bank balances. Both of them want to get to k\$. What is the probability that they will both reach their targets on the same toss?
Based on this question we see that the answers to all such questions take the form $A+\frac{B}{\pi}$. Here, we're strictly focusing on draws. First, we know that the stopping time (probability he'll reach his target first time on toss $2t+k$) for any one gambler is given by:
$$a_k(t) = \frac{k}{k+t}\frac{{2t+k-1 \choose t}}{2^{2t+k}}$$
Now, the probability of an overall draw is simply the probability both will reach their target on toss $2t+k$, summed over all possible values of $t$.
$$D_k = \sum\limits_{t=0}^{\infty} \left(\frac{k}{k+t}\frac{{2t+k-1 \choose t}}{2^{2t+k}}\right)^2$$
Mathematica can't find a nice closed form expression for the summation above (if you can, I'll be very impressed indeed). However, plugging various values of $k$ in we find that the answer always takes the form:
$$D_k = \frac{E_k}{F_k \pi} – G_k$$
Where $E_k$, $F_k$ and $G_k$ are all integers. Plugging the first few values of $G_k$ (calculated using Mathematica) into OEIS, I got the sequence A002002. This means that:
$$G_k = \sum\limits_{l=0}^{k-1} {k \choose l+1} {k+l \choose l}$$
However, I haven't been able to find corresponding expressions for $E_k$ and $F_k$. Can anyone help with this? We can use it to get an expression for $\pi$ since $D_{\infty} = 0$
Here are the first few expressions for $D_k$.
$$D_1 = \frac{4}{\pi}-1$$
$$D_2 = \frac{16}{\pi}-5$$
$$D_3 = \frac{236}{3 \pi}-25$$
$$D_4 = \frac{1216}{3 \pi} – 129$$
$$D_5 = \frac{32092}{15 \pi} – 681$$
$$D_6 = \frac{172144}{15 \pi} – 3653$$
$$D_7 = \frac{1307924}{21 \pi} – 19825$$
$$D_8 = \frac{7161088}{21 \pi} – 108545$$
$$D_9 = \frac{592194476}{315 \pi} – 598417$$
$$D_{10} = \frac{3282949168}{315 \pi} – 3317445$$
$$D_{11} = \frac{40221561524}{693 \pi} – 18474633$$
$$D_{12} = \frac{224841634624}{693 \pi} – 103274625$$
Unfortunately, Mathematica gives up providing nice expressions in terms of $\pi$, $D_{13}$ onwards.
The idea is courtesy /u/boyobo on this reddit thread.
Best Answer
The OEIS entry for A002002 gives the recurrence
$$2(6k^2-12k+5)G_{k-1}-(k-2)(2k-1)G_{k-2}-k(2k-3)G_k = 0.$$
On a random hunch, I tried $D_n$ with the same operator and found that
$$2(6k^2-12k+5)D_{k-1}-(k-2)(2k-1)D_{k-2}-k(2k-3)D_k = \frac{8}{\pi}$$
holds for all the values Mathematica can reduce to closed form ($2 \le k \le 12$), and continues to hold numerically to hundreds of significant digits for thousands of terms, so this is almost certainly the right recurrence.