Iterative Poohsticks

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 n-th time before the other player’s stick has emerged n-1 times.

Let’s make this more precise by modeling the game as a discrete event simulation with positive integer parameters (a, b, c).  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 a and b (inclusive).  The river is random, but the players are otherwise evenly matched: each player then takes a constant c 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 (a,b,c)=(10,30,5).  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 t(a,b,c) 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 n-th time, at exactly the same time that the trailing player’s stick emerges for the n-1-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.)

This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Iterative Poohsticks

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s