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.
August 9, 2016 at 12:58 am
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.