6

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.

Rohit Pandey
  • 6,803
  • 2
    My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can. – Sam Benner Jan 02 '19 at 18:24
  • 2
    Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter. – Jeremy Dover Jan 02 '19 at 19:55
  • Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern. – Rohit Pandey Jan 02 '19 at 20:02
  • A037964 Briefly offered hope. – Rohit Pandey Jan 02 '19 at 20:08
  • 1
    I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way. – Alex Ravsky Jan 03 '19 at 19:09
  • 1
    Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $\pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3. – Rohit Pandey Jan 03 '19 at 19:40
  • I looked more closely at the sequences mentioned above. Some of them look relevant, especially A086116 with a reference from MathWorld to “Random Walk--1-Dimensional” by Eric W. Weisstein. – Alex Ravsky Jan 03 '19 at 20:26
  • Those 21's are really thorns in the sides. I wish there were a way to calculate the expression for 13. – Rohit Pandey Jan 04 '19 at 07:15
  • 1
    Although Mathematica can’t reduce (d[13] + g[13])Pi to a rational number, it will give you a very conspicuous result for ContinuedFraction[(d[13] + g[13])Pi + N[10^-100, 100]], which you can truncate at the stupidly large element to get very strong numerical evidence that $\frac{E_{13}}{F_{13}}$ is FromContinuedFraction[{1819512525, 1, 4, 2, 1, 1, 1, 1, 1, 2, 3}] = $\frac{1821332038340}{1001}$. The next few starting at $\frac{E_{14}}{F_{14}}$ appear to be $\frac{10242265213328}{1001}, \frac{2598075674762068}{45045}, \frac{14675811920024576}{45045}, \frac{282378678293341060}{153153}$. – Anders Kaseorg Jan 13 '19 at 12:53
  • Thanks, this is great! Can you share a screenshot of your Mathematica code with these commands? I'm still new with it and don't even know how to put the d's and g's into arrays. Also, what's the role of the N[10^-100,100]? – Rohit Pandey Jan 13 '19 at 19:12
  • 1
    @RohitPandey This isn’t the best space to teach Mathematica, but I just did d[k_] = Sum[(k/(k + t) Binomial[2t + k - 1, t]/2^(2t + k))^2, {t, 0, Infinity}]; g[k_] = Sum[Binomial[k, l + 1] Binomial[k + l, l], {l, 0, k - 1}] (single brackets are for functions, not arrays). I added $10^{-100}$ to avoid forcing Mathematica to compare an expression it doesn’t know is rational to the exact fraction; otherwise it’s not willing to commit to the last element we need from the continued fraction expansion. N[…, 100] evaluates numerically with 100 digits of precision. – Anders Kaseorg Jan 14 '19 at 03:00
  • Ok, thanks again. I didn't think I'd ever know a recurrence for this problem. Might even be possible to solve it now :) – Rohit Pandey Jan 15 '19 at 00:20

1 Answers1

2

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.

Anders Kaseorg
  • 8,377