Gambler's Ruin
A simple random walk models a gambler’s fortune starting at , winning with probability and losing with probability each step, until the fortune reaches or . With reaches before reaching , the ruin-avoidance probabilities solve
giving for the symmetric walk and
otherwise.
Consider as a simple random walk, which is the fortune of a gambler who starts with at time and at every time step, he wins with probability and loses with probability .The game ends if he reaches or if he reaches , whichever comes first.
Let . Then and .
Then,
So we can solve the following system of equations to find for all :
-
For , we get a simple symmetric random walk (SSRW), in which case we have
This leads to
Hence,
Considering boundary conditions, gives . Hence, for a SSRW, we have
-
For , we need to try a solution of the form for some . Then
The general solution is of the form for some constants . Using the boundary conditions, we get
Time to absorption
Let be the time to absorption and write . Conditioning on the first step by the law of total expectation,
with boundary conditions .
For the symmetric walk , trying forces , so the general solution is and the boundary conditions give
For , trying gives , and the full solution is
Related
Stated in
- Example 3.54 (Gambler's Ruin)§3.5.1 Simple Random Walk