A gambler with $1$ dollar intends to make repeated bets of $1$ dollar until he wins $20$ dollars or is ruined. Probabilities of win/loss are $p$ and $(1-p)$, and each bet brings a gain/loss of $1$ dollar.
Unfortunately, the devil is active, and ensures that every time he reaches $19, he loses! Obviously, the poor guy will get ruined sooner or later!
The question is, what is the expected number of bets he makes until he is ruined?
Best Answer
I drew your transition matrix for you, to better visualize the situation:
Notice, of course, that there's no way to get to 20 dollars. It might as well be removed, but I wanted to put it there anyway.
I'll just explain what Tim did and how he did it, using the transition matrix.
First of all, let's define $\mu_i$ such that it is the expected number of "steps" to reach 0 dollars. Each "step" is simply a transition from 1 state (a circle) into another state (another circle).
So at $\mu_0$, we have $\mu_0 = 0$ because we're already there. The gambler is already ruined.
With just 1 dollar, we need to take 1 step either to state 0 or state 2. So whatever happens, our expected number of steps is always at least 1.
We therefore have $\mu_1 = p\mu_2 + (1-p)\mu_0 + 1$ because there is a $1-p$ chance to get to state 0, and a $p$ chance to get to state 2.
Generally, $\mu_n = p\mu_{n+1} + (1-p)\mu_{n-1} + 1$ which is exactly what Tim did. You can verify this on your diagram.
So with your $i$ ranging from 0 to 19 (we don't need to consider 20 since there is no way to get to it), you have 20 equations to define all your $\mu_i$ as well as 20 unknowns.
From here, it's only a matter of solving systems of equations. Tim showed a good shortcut though, so you probably want to do that instead.