The game of Poohsticks was invented by Milne and appears in one of his books, where Pooh and Christopher Robin each simultaneously drop a stick into a river from the upstream side of a bridge.  The winner is the one whose stick emerges first from the downstream side.  Sounds like fun, right?

Right.  Now consider the following iterative version of the game: as each player’s stick emerges from under the bridge, he retrieves it, then runs back to the upstream side of the bridge and drops the stick again.  Both players continue in this way, until one player’s stick “laps” the other, having emerged from under the bridge for the -th time before the other player’s stick has emerged times.

Let’s make this more precise by modeling the game as a discrete event simulation with positive integer parameters .  Both players start at time 0 by simultaneously dropping their sticks, each of which emerges from under the bridge an integer number of seconds later, independently and uniformly distributed between and (inclusive).  The river is random, but the players are otherwise evenly matched: each player then takes a constant seconds to recover his stick from the water, run back to the upstream side of the bridge, and drop the stick again.

Suppose, for example, that .  If the game ends at the instant the winner’s stick emerges from under the bridge having first lapped the other player’s stick, then what is the expected time to complete a game of Iterative Poohsticks?

I think this is a great problem.  As is often the case here, it’s not only an interesting mathematical problem to calculate the exact expected number of seconds to complete the game, but in addition, this game can even be tricky to simulate correctly, as a means of approximating the solution.  The potential trickiness stems from an ambiguity in the description of how the game ends: what happens if the leading player’s stick emerges from under the bridge for the -th time, at exactly the same time that the trailing player’s stick emerges for the -st time?

There are two possibilities.  Under version A of the rules, the game continues, so that the leading player’s stick must emerge strictly before the trailing player’s stick.  Under version B of the rules, the game ends there, so that the leading player’s stick need only emerge as or before the trailing player’s stick emerges in order to win.

(It’s interesting to consider which of these versions of the game is easier to simulate and/or analyze.  I think version B admits a slightly cleaner exact solution, although my simulation of the game switches more easily between the two versions.  For reference, the expected time to complete the game with the above parameters is about 309.911 seconds for version A, and about 290.014 seconds for version B.)