Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

closed as off-topic by Anthony Quas, Andrey Rekalo, Noah S, Stefan Kohl, David White Nov 30 '13 at 18:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Anthony Quas, Andrey Rekalo, Noah S, Stefan Kohl, David White
If this question can be reworded to fit the rules in the help center, please edit the question.

    
See mathoverflow.net/questions/130513/…. Consider a random walk on the vertices of an $n$-dimensional hypercube $\lbrace0,1 \rbrace^n$. Project this to the sum of the coordinates. –  Douglas Zare Nov 30 '13 at 16:14
    
What "class of problems of practical interest"? I think your question would be better suited for math.stackexchange.com. –  UwF Dec 1 '13 at 11:02
add comment