Hitting time of simple random walk

Question

Consider a random walk on $\mathbb{N}_0$, starting in $0$ with transition probabilities $$p(0,1)=1 \ \text{ and }\ p(n,n-1)=p(n,n+1)=0.5 \ \text{ for }\ n>0.$$

What is the expected time $\mathbb{E}[T_{100}]$ before hitting the value $100$?

I have trouble solving this question. Other questions on this website cover e.g. the hitting times of hitting either boundary when starting in a point in the middle.. But the hard part here is that the left boundary bounces off but does not absorb. How to solve this problem?

Answer 1

Here's a nice method that doesn't require setting up $100$ equations.

Let $\mu_i$ be the mean number of steps to reach state $i+1$ after reaching state $i$ for the first time, so we want $\sum_{i=0}^{99}\mu_i$. By the Markov property, $$\mu_i=1+\frac{1}{2}(\mu_{i-1}+\mu_i)\implies\mu_i=2+\mu_{i-1}.$$ Now $\mu_0=1$, so $\mu_i=2i+1$, hence the expected time to reach $100$ is $$\sum_{i=0}^{99}(2i+1)=100^2.$$

Answer 2

Let $c_i$ be the expected hitting time when starting in state $i$. We have \begin{align} c_{100} &= 0 \\ c_i &= \frac{1}{2} (c_{i-1} + c_{i+1}) + 1 & 0 < i < 100 \\ c_0 &= c_1 + 1. \end{align}

I think you can show that $c_i = c_{i+1} + 2i + 1$ (for $0 \le i \le 99$) by induction, which will then lead you to the answer.

Answer 3

Let $\mathbb{E}[T_{100}(n)]$ be the expected time to hit $100$ starting from $n$

Then you have $$\mathbb{E}[T_{100}(100)]=0$$ $$\mathbb{E}[T_{100}(0)]=1+\mathbb{E}[T_{100}(1)]$$ $$\mathbb{E}[T_{100}(n)]=1+\tfrac12 \mathbb{E}[T_{100}(n-1)] + \tfrac12 \mathbb{E}[T_{100}(n+1)] $$ for $0 < n<100$, giving you $101$ equations in $101$ unknowns. So solve it.

You get

• $\mathbb{E}[T_{100}(0)]=1+\mathbb{E}[T_{100}(1)]$ and $\mathbb{E}[T_{100}(1)]=1+\tfrac12 \mathbb{E}[T_{100}(0)] + \tfrac12 \mathbb{E}[T_{100}(2)] $ implying $\mathbb{E}[T_{100}(1)]=3+\mathbb{E}[T_{100}(2)]$ and $\mathbb{E}[T_{100}(0)]=4+\mathbb{E}[T_{100}(2)]$.
• Similarly the next step implies $\mathbb{E}[T_{100}(2)]=5+\mathbb{E}[T_{100}(3)]$ and $\mathbb{E}[T_{100}(0)]=9+\mathbb{E}[T_{100}(3)]$.
• It then becomes an easy induction to show $\mathbb{E}[T_{100}(n-1)]=(2n-1)+\mathbb{E}[T_{100}(n)]$ and $\mathbb{E}[T_{100}(0)]=n^2+\mathbb{E}[T_{100}(n)]$
• and thus the result you want $\mathbb{E}[T_{100}(0)]=100^2+\mathbb{E}[T_{100}(100)]=10000$