# Hitting time of simple random walk

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?

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.$$

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.

• @Henry Thanks for catching that Commented Jan 2, 2021 at 22:59

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$$