We consider a Markov chain on a subset of positive integers S = {0, 1, 2, 3, .......N}, with transition probabilities defined as follows:
The chain jumps only one unit to the left or right.
p(i, j) = 0 if I i - j I > 1
p(i, i + 1) = (N - i) /N , for i in {1, 2, 3, ....., N-1}.
p(i, i - 1) = i/N , for i in {1, 2, 3, ....., N-1}.
We assume that we have absorbing barriers at 0 and N, so we have p(0, 0) = p(N, N) = 1.
What is the expected time it takes for the chain to be absorbed at 0 or N, starting at i in {0, 1, 2, 3, .......N}? If T_i is the time it takes for the chain to be absorbed at 0 or N, when starting at i, what is E(T_i)?
This Markov chain can be seen as a particular case of a birth and death chain, or as a one dimensional random walk with 2 absorbing barriers and probabilities varying from place to place.
I would call this the problem of the drunken man in a valley. The closer he gets to the absorbing barriers (the top of the hill), less likely it is that he will continue towards them. Then what is the expected time of the drunkard to reach the top of the hills surrounding him?
Note that this problem is related to a class of problems of practical interest.
