another riddle

A riddle from The Riddler, a few weeks ago, to ponder while waiting for Godot another plane:

Consider a game played with a coin, between you and a friend, on the integer line. You are assigned a negative integer -X, and your friend is assigned a positive integer, +Y. A marker is placed at zero on the number line. Then the 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.

What is the expected number of coin flips in a complete game?

Not much to say there since this is the classical Feller’s gambler ruin problem that I used to analyse in my practical classes at Polytechnique. The winning probability is X/(X+Y). Assuming the coin is fair. And the distribution of the hitting times (win or loose) is easily analysed by the reflection principle. But a simpler recursion shows that the expected number of steps till hitting one boundary is XY, which is rather surprising as a multiplicative formula.

One Response to “another riddle”

  1. The multiplicative formula perhaps could be guessed, if you take either X or Y or infinity. Since in this case, one must have the expected time to be infinity, due to the recurrence of the random walk.

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