So, I promise this blog isn’t going to only feature puzzles and Excel challenges (next ‘real’ post on Friday, if all goes according to plan), but I enjoyed this week’s Riddler enough that I thought I should write something on it.
Consider a hot new bar game. … A marker is placed at zero on [a] number line. Then [a] coin is repeatedly flipped. Every time the coin lands heads, the marker is moved one integer in a positive direction. Every time the coin lands tails, the marker moves one integer in a negative direction. You win if the coin reaches -X first, while your friend wins if the coin reaches +Y first. (Winner keeps the coin.)
How long can you expect to sit, flipping a coin, at the bar?
Here are a few ways you can tackle it (if you’re just an Excel nerd and not a general nerd, you can skip to the last one…):
1. Recurrence relations
Let n = X + Y, and let E(i) be the expected number of flips before the game ends starting i positions to the right of -X. Then E(X) is the answer we’re looking for, and E(0) = E(n) = 0, since the game ends in either of those positions.
Now, starting from position i, there will be one flip, followed by a 50% (assuming a fair coin) chance of starting over in position i-1 and a 50% chance of starting over in position i+1. So, we get 
To use the boundary condition, set i = 2 to get 
You can probably spot the pattern that 
The Riddler has a tradition of the Riddler extension – think of a way to make the puzzle more interesting / difficult, and then solve that too. The obvious extension here is to be able to deal with a biased coin that doesn’t come up heads and tails with the same odds, and I turned to a different method to crack that version.
2. Generating functions
Generating functions are an almost-magical way of approaching recurrence relations (and lots of other things) in maths and computer science. Even a shallow explanation is WAY too big a detour for this little blog post, but see the wikipedia article in the link, and if you feel like you’re ready for more, I recommend reading Flajolet & Sedegwick. For the rest of this section, I assume you know about generating functions.
Let GF(x,n) be the generating function for the expected number of moves starting from each position for X + Y = n. So, in the notation above, we have 
Solving for GF, and with a little tidying up, we get
![GF(x,n)=\left.x\left[(1-p)E(n-1)x^n - \sum_{i=1}^{n-1} x^i + pE(1)\right]\right/\left[\left((1-p)x-p\right)(x-1)\right].](https://s0.wp.com/latex.php?latex=GF%28x%2Cn%29%3D%5Cleft.x%5Cleft%5B%281-p%29E%28n-1%29x%5En+-+%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D+x%5Ei+%2B+pE%281%29%5Cright%5D%5Cright%2F%5Cleft%5B%5Cleft%28%281-p%29x-p%5Cright%29%28x-1%29%5Cright%5D.&bg=ffffff&fg=000000&s=0&c=20201002)
Now, since GF is a polynomial, the two terms in the denominator have to divide evenly into the numerator. Equivalently, the two roots of the bottom, 
![E(1) = \frac{1}{2p-1}\left[n\frac{1-\left(\frac{1-p}{p}\right)}{1-\left(\frac{1-p}{p}\right)^n}-1\right].](https://s0.wp.com/latex.php?latex=E%281%29+%3D+%5Cfrac%7B1%7D%7B2p-1%7D%5Cleft%5Bn%5Cfrac%7B1-%5Cleft%28%5Cfrac%7B1-p%7D%7Bp%7D%5Cright%29%7D%7B1-%5Cleft%28%5Cfrac%7B1-p%7D%7Bp%7D%5Cright%29%5En%7D-1%5Cright%5D.&bg=ffffff&fg=000000&s=0&c=20201002)
Combining this with the recurrence equation for E(i+1) in terms of E(i) and E(i-1) and using the fact that E(0) = 0, we get
![E(2) = \frac{1}{2p-1}\left[n\frac{1-\left(\frac{1-p}{p}\right)^2}{1-\left(\frac{1-p}{p}\right)^n}-2\right].](https://s0.wp.com/latex.php?latex=E%282%29+%3D+%5Cfrac%7B1%7D%7B2p-1%7D%5Cleft%5Bn%5Cfrac%7B1-%5Cleft%28%5Cfrac%7B1-p%7D%7Bp%7D%5Cright%29%5E2%7D%7B1-%5Cleft%28%5Cfrac%7B1-p%7D%7Bp%7D%5Cright%29%5En%7D-2%5Cright%5D.&bg=ffffff&fg=000000&s=0&c=20201002)
Continuing in the same way, we get a general term that looks like this:
![E(i) = \frac{1}{2p-1}\left[n\frac{1-\left(\frac{1-p}{p}\right)^i}{1-\left(\frac{1-p}{p}\right)^n}-i\right].](https://s0.wp.com/latex.php?latex=E%28i%29+%3D+%5Cfrac%7B1%7D%7B2p-1%7D%5Cleft%5Bn%5Cfrac%7B1-%5Cleft%28%5Cfrac%7B1-p%7D%7Bp%7D%5Cright%29%5Ei%7D%7B1-%5Cleft%28%5Cfrac%7B1-p%7D%7Bp%7D%5Cright%29%5En%7D-i%5Cright%5D.&bg=ffffff&fg=000000&s=0&c=20201002)
Full disclosure: I worked out E(1) and E(n-1) by myself, but I hadn’t cracked the general term before I read a fellow blogger’s write-up here which led me to these notes that solve the problem very neatly directly from the recurrence relation, and obviously made it a lot easier for me to finish off.
3. Use Excel
So, having done things the hard way, let’s round out with doing it the easy way. You might be tempted to simulate the whole game with random numbers, then run it hundreds or thousands of times and get some summary stats (a.k.a. a Monte Carlo simulation) – but you can get a more precise answer more easily, and with a much smaller file size, by putting the recurrence relations above into Excel and letting it work them out.
Pick a cell to store your value of p (and, to keep your formulas simple, name the cell p). Then pick a range of n+1 cells in a row (say B2:B[n+2]) to store your values of E(i). Enter 0 in the first and last, then in B3 enter
= 1 + ( 1 – p ) * B2 + p * B4
and copy that formula down to B[n+1]. You can adjust the iterative calculation settings (allow more calculations and higher precision) to make your answer more accurate. If you enter the formula for the general term in the next column, you’ll see that the two come out essentially identical.
Now that we have the data in Excel, we can also play around with it a little more, and add one more Riddler extension: Let’s say you really like the person you’re playing this hypothetical bar game with – if you could pick the bias of the coin, p, how much longer could you make the game last compared to using a fair coin?
The shortest game is easy – just pick a coin that always comes up heads or always comes up tails (whichever endpoint is closer). But longer is tricky: you want the coin to bias towards the end that’s further away, but only a little or it will get to the far end quickly. It’s not obvious how much better you can do, and looking at the general term for E(i) above might not make it seem super-obvious either. But if you put that general formula into Excel, and divide by the ‘base case’ of XY, or i(n-i), you can easily graph the result for various values of X, Y, and p. The GIF below shows examples for X = 1 and X = 25 with a wide range of Y values.
[Note: The horizontal axis actually shows the probability of tails, or 1 – p instead of the probability of heads, or p as it says. So the value at 0.4 corresponds to the case when p = 0.6, and there’s a 40% chance of going left on any turn, and a 60% chance of going right. Apparently I switched my naming convention between making the graph and writing the rest of this post…]
As you can see, if Y is much bigger than X, you can almost (but not quite) make the game last twice as long with a coin that’s more likely to take you towards Y. For X = 1, any bias in favor of moving towards Y will help the game last longer – but for X > 1, even slightly too much bias and the game will end up finishing much sooner… so you might find the safest way to keep your friend at the bar a bit longer is just to buy them another drink…
The Excelements 