what is The problem of the drunkard in a valley?

The problem of the drunkard in a valley.

• 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 - j|>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? Main question. Is the expected time to absorption polynomial or exponential (in $N$)? Note that this problem is related to a class of problems of practical interest.

• Answer:

  If we make the boundaries at $0$ and $N$ reflecting, rather than absorbing, then your random walk is the http://www.math.uah.edu/stat/markov/Ehrenfest.html. It is well-known that this Markov chain has invariant distribution $\pi_i={N\choose i}/2^N$ for $0\leq i\leq N$. In particular, the expected time to return to the origin, starting there, is $\mathbb{E}_0(T_0)=1/\pi_0=2^N$. This implies that the expected time to hit zero, starting at one, is $\mathbb{E}_1(T_0)=2^N-1$. This is already exponential in $N$, even when the starting point is right beside the boundary. Granted, starting at one, we might hit the boundary point $N$ first. But I'm willing to bet that this is so unlikely that $\mathbb{E}_1(T_{\{0,N\}})$ is exponential in $N$. Update: I think I've found a way to make this rigorous. Create a new random walk on a circle by combining the states $0$ and $N$, call this combined state $b$ (for boundary). The transition probabilities are all the same except from $b$ you jump to either $1$ or $N-1$ with probability $1/2$. This chain has invariant distribution $\pi_j={N\choose j}/2^N$ for $j=1,\dots, N-1$ and $\pi_b=2/2^N$. The expected number of steps to hit the boundary, when you start there, is $$\mathbb{E}_b(T_b)=1/\pi_b=2^{N-1}.$$ On the other hand, first step analysis gives $$\mathbb{E}_b(T_b)=1+\mathbb{E}_1(T_b)/2+\mathbb{E}_{N-1}(T_b)/2=1+\mathbb{E}_1(T_b),$$ where the last equation is by symmetry. Therefore, $\mathbb{E}_1(T_b)=2^{N-1}-1$, which implies for the original model that $\mathbb{E}_1(T_{\{0,N\}})=2^{N-1}-1.$