Probability you win 5$ before going bankrupt in 11 steps?

Question

Here's the game: You start with 1\$ at time 0. Every minute you win 1\$ with probability 0.5 and lose 1\$ with probability 0.5. You win the game if at any time you reach 5\$. You lose the game if at any time you have 0\$. What is the probability you have won by the 11th step (including the possibility of winning at earlier steps)? Can we generalize to non-symmetric walks or different number of steps?

It seems this should be easy but it confuses me. I know how to find the probability you win eventually. But the recurrence relation used for that would lead to a double recurrence here which I am unsure how to solve.

Answer 1

I like to draw a diagram for this kind of question. In the figure below, the number of dollars is indicated by vertical lines with zero on the left (red) and 5 on the right (green). The steps, starting at zero go down the figure. Paths through the game are obtained by traversing the diagonal black lines. At each junction, the number of routes to reach it is indicated in italics.

With this, I make the probability of a win by 11 steps equal to the sum of probabilities of winning in 4, 6, 8 and 10 steps. I.e.

$\qquad \frac{1}{2^4} + \frac{3}{2^6} + \frac{8}{2^8} + \frac{21}{2^{10}} = \frac{165}{1024} $

The probability of a loss by 11 steps can similarly be found using the numbers to the left of the red line. The probability of the game still continuing at 11 steps should be $\frac{89+55}{2^{11}}$.

It is nice that the Fibonacci numbers turn up in the number of routes for the junctions.

Answer 2

Another way to solve this problem is to consider it as a Markov process. We can represent the state of the system by a vector of length 6 where each component represents the probability of having $0, 1, \ldots, 5$ dollars respectively.

This means that at the start of the game, the state can be represented by the vector

$$ x_0 = \begin{pmatrix} 0, & 1, & 0, & 0, & 0, & 0 \\ \end{pmatrix}^T $$

We can model the game as a sequence of state vectors $x_0, x_1, x_2, \ldots$ where transition from from one state to the next is given by $x_{k+1} = M x_{k}$ with the transition matrix $M$ given by

$$ M = \begin{pmatrix} 1 & 0.5& 0 & 0 & 0 & 0 \\ 0 & 0 & 0.5& 0 & 0 & 0 \\ 0 & 0.5& 0 & 0.5& 0 & 0 \\ 0 & 0 & 0.5& 0 & 0.5& 0 \\ 0 & 0 & 0 & 0.5& 0 & 0 \\ 0 & 0 & 0 & 0 & 0.5& 1 \end{pmatrix} $$

Carrying out the recursive calculations required to find $x_{11}$, we obtain

$$ x_{11} = \begin{pmatrix} \frac{787}{2^{10}} , & 0, & \frac{89}{2^{11}} , & 0 , & \frac{55}{2^{11}} , & \frac{165}{2^{10}} \end{pmatrix}^T $$

I.e. the probability of having 5\$ after 11 steps is $\frac{165}{2^{10}}$.

---

If we want to to avoid the repeated multiplications by the transition matrix $M$, then we can calculate its powers more directly. We can get a closed form solution solution by using the fact that the transition matrix $M$ is diagonalisable.

First decompose $M$ as $M = V \Lambda V^T$, where $\Lambda$ is a diagonal matrix containing the eigenvalues of $M$. Then we can use the fact that $M^n = V \Lambda^n V^T$ to get a solution directly. Finding the powers of the diagonal matrix $\Lambda$ is straightforward, we just calculate the powers separately for the diagonal entries. In particular, $x_{11}$ can be calculated as follows:

$$ x_{11} = M^{11} x_0 = V \Lambda^{11} V^T x_0 $$