Learn / Library / Expected value

Bankroll random walk

Expected valueHard

You start with a bankroll of $3$ . Each round a fair coin is flipped independently: heads wins $1$ , tails loses $1$ . You stop as soon as the bankroll reaches $0$ or $7$ . What is the expected number of rounds played?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Look for a function of the bankroll that drops by exactly $1$ on average each round and vanishes at both boundaries.

Solution

Let $T (k)$ be the expected remaining rounds from bankroll $k$ , with $T (0) = T (7) = 0$ .
For $0 < k < 7$ , $T (k) = 1 + \frac{T ( k - 1 ) + T ( k + 1 )}{2}$ .
Try $T (k) = k \times (7 - k)$ . The average of neighbours is $T (k) - 1$ , which fits the recurrence, and it vanishes at both ends.
So $T (3) = 3 \times 4$ .
The expected number of rounds is $12$ .

Answer: $12$

Next question Back to the library