We have a simple random walk S on a finite set of $\mathbb{N}: {0,...,N}$.

Let $m_x$ be the expected number of steps, starting at $x$, required to reach $0$ or $N$ for the first time. Show that $m_x$ satisfies the conditions:

(a) $m_0 = 0$

(b) $m_N = 0$

(c) $m_x = \frac{1}{2}m_{x-1}+\frac{1}{2}m_{x+1}+1$.

For (a) and (b) my reasoning goes as follows. Substitute either $0$ or $N$ for $x$ in $m_x$. Then we are looking for the expected numbers of steps before reaching either $0$ or $N$ starting in either $0$ or $N$. This is $0$ since we are already there.

How do we show that the difference equation applies though?


migrated from mathoverflow.net Oct 17 '16 at 16:11

This question came from our site for professional mathematicians.

  • $\begingroup$ See "help" above to discover what sort of questions to ask here. $\endgroup$ – GEdgar Oct 17 '16 at 15:51
  • $\begingroup$ The difference equation follows from the total expectation formula and the Markov property of the random walk. $\endgroup$ – Ian Oct 17 '16 at 16:16
  • $\begingroup$ Do you mean the total expectation of the stopping time? We have that $m_x = \mathbb{E}_x(\tau_{0,N})$ with $\tau_{0,N}$ the minimum of the number of steps it takes to reach either $0$ or $N$ from the starting point $x$. I can't seem to figure out how to calculate this expectation. $\endgroup$ – Vydai Oct 17 '16 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.