Katkat
Back

Expected Winnings in a Random-Walk Money Collection Game on 45 Stones

DRWQuantitative Researcher · Onsite
HardQuantitative ResearcherOnsiteStatistics & Math

Last updated

Calculates a player's expected winnings in a random-walk money collection game on an odd-sized circle of stones using Gambler's Ruin and parity arguments.

Problem Description

A game is played on a circle of 45 stones, indexed 0 through 44 in clockwise order. A marker begins at stone 0. Stone 0 contains no money, while each of the remaining 44 stones (stones 1 through 44) contains a $100 prize.

You and an opponent play a turn-based game, with the opponent taking the first turn:

  • On turn t = 1, the opponent flips a fair coin and moves the marker 1 stone clockwise (Heads) or 1 stone counterclockwise (Tails).
  • On turn t = 2, you flip a fair coin and move the marker 1 stone clockwise or counterclockwise from its current position.
  • The players continue to alternate turns indefinitely (t = 3 opponent, t = 4 you, etc.).
  • Whenever the marker lands on a stone for the very first time in the game, the player who made that move collects the $100 prize from that stone.
  • The game ends once all 44 prizes have been collected.

Tasks

  1. For any given stone x in {1, 2, ..., 44}, determine the probability that you collect the prize on stone x.
  2. Calculate your total expected winnings in dollars. Provide the exact rational value as well as its decimal equivalent rounded to the nearest cent.

Hints

Hint 1

Notice that prior to the marker reaching stone x for the first time, the walk is restricted to a simple path (which is a bipartite graph), meaning the parity of the arrival time depends strictly on whether stone x is reached from the clockwise or counterclockwise neighbor.

Hint 2

Formulate the direction of first arrival at stone x as a Gambler's Ruin problem on the unrolled interval [-(45 - x), x] starting from 0.

Hint 3

Apply linearity of expectation and pair the probabilities for stones 2k - 1 and 2k to simplify the sum.

Follow-up questions

  • What would the expected winnings be if the circle had an even number of stones, for instance 44 stones total with stone 0 empty and 43 prizes?
  • If the coin were biased, landing Heads with probability p != 1/2, how would you set up the first-passage probabilities to find the new expected winnings?
  • What is the expected total number of steps until all 44 prizes are collected (the cover time of the cycle graph)?