Random Walks, Gambler's Ruin and Queueing Systems
We consider a person who performs a random walk on the real line with the non-negative
integers
{ 0, 1, 2, ..., N }
see Figure 1 for instance. There are N + 1 possible states (positions) for the walker.
Each time the walker in State i (i can be 1, 2, ..., N) can move one step forward (+1)
or one step backward (-1) with probabilities p (0 < p < 1) and (1 - p) respectively.
Figure. 1. The Random Walk.
At the end points 0 and N, there are two typical behaviors for the walker.
The first one is that the walker stays there forever. In this case, the states 1 and N are
called absorbing states (absorbing boundary).
The second possible case is that the walker can go back to the previous state with positive.
In this case, the states 0 and N are called non-absorbing states (non-absorbing
boundary).
For the case of absorbing boundary, what happen in the long run?
It is not difficult to imagine that eventually the walker will end up in State 0 or State
1. An interesting question is the following: beginning at State i, i ¹ 0,
N, what is the probability that eventually the walker ends up in State 0?
For the case of non-absorbing boundary, the walker will keep on walking forever. Another
interesting question is the following: In the long run, what is the probability that you can
the walker in the position i ?
In the followings, we will demonstrate the above cases by two practical examples: gambler's
ruin and one-serve queueing system. Detailed analysis of the examples is also given.
| 
