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?
 A: 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.$$
A: 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.
A: 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$
