Expected Winnings in a Random-Walk Money Collection Game on 45 Stones
Company: DRW
Role: Quantitative Researcher
Category: Statistics & Math
Difficulty: hard
Interview Round: Onsite
Forty-five stones are arranged in a circle, and each stone holds \$100. You place a token on a stone chosen uniformly at random and collect that stone's money. You and an opponent then take alternating turns, with the opponent moving first. On each turn, the player tosses a fair coin and moves the token one stone clockwise for heads or one stone counterclockwise for tails, collecting any money remaining on the destination stone. All tosses are independent, and play ends when all the money has been collected.
What is the expected total amount you collect, including the initial \$100?
```hint Look at one stone at a time
By linearity of expectation, it is enough to find, for each of the other 44 stones, the probability that the move that first reaches it is one of yours.
```
```hint Unwrap the circle
Consider following the token's net displacement on the integers rather than its position on the circle. What does the number of moves made so far tell you about that displacement?
```
### Constraints and Clarifications
- A stone's money is collected once, by whichever player first moves the token onto it; landing on an emptied stone collects nothing.
- The starting stone's \$100 is yours.
- The opponent makes moves 1, 3, 5, and so on; you make moves 2, 4, 6, and so on.
- Give an exact value and a dollar approximation.
### What a Strong Answer Covers
- Reducing the expected total to a sum of per-stone probabilities.
- A first-passage argument for when, and from which direction, the token first reaches each stone.
- The link between who collects a stone and the parity of the move that first reaches it, including the effect of the circle having an odd number of stones.
- An exact total with sanity checks, such as consistency with the total money available and a small circle worked by hand.
### Follow-up Questions
1. How would the answer change if the circle had an even number of stones?
2. Would you rather make the first move, and by how much would your expected total change?
3. What is the probability that a particular stone is the last one collected?
Overview: Random-walk puzzle in which a token moves one step either way around a circle of 45 stones holding 100 dollars each, while two players alternate coin-toss moves and collect money from stones they reach first. Asks for your expected winnings when the opponent moves first, testing linearity of expectation and first-passage arguments.
Read the full DRW Quantitative Researcher interview experience this question came from