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.)

Version A seems like the way most people would interpret the rules. In my own simulation (which matches your numbers), I started with Version A. Version B was two more lines of code to test an additional condition. Version B seems like its the version the mathematician prefers in order to get an elegant formula or proof.

Interesting– I would be curious to see your solution, since I had sort of the opposite experience: my simulation approach was effectively the same code for both versions, but for the exact analytic solution, version *A* required the additional work.

Here is the discrete event simulation; with events in the queue ordered first by time, then by priority… but with no other assumption about “stability” (i.e., extraction in insertion order, etc.), the idea is to use the priority to indicate the number of laps completed. This realizes version A (if lesser priority is extracted first); for version B, just negate the priorities.

Using priority like that is really clever. In my version I resolve event ties simultaneously, and Version B needs an extra check when the tie occurs: https://gist.github.com/skeeto/aaf7033c3b84d19ca8ad11efb69aa995