# Hitting time of a Markov chain.

A Markov chain with $m + 1$ states. The transition probability is

$$p_{i,j} = 0, j \leq i$$ $$p_{i,j} = 1/2^{j-i}, i < j < m$$ $$p_{i,j} = 1/2^{m-1-i}, j = m \quad \text{(to make the sum probabilities to 1)}$$

(Sorry, I don't know how to write it in conditional expression)

For example, if we start from state $0$, then the probability to go to next state $1$ is $1/2$, and to state $2$ is $1/4$, etc.

My question is, what is the expectation of hitting time $T_{0, m}$, i.e. the time it takes to go from state $0$ to state $m$?

-

For any sequence $S=(s_1,\dots,s_k)$ of intermediate states, $0<s_1<\dots<s_k<m$, the probability that you travel from 0 to $m$ via $S$ is $$2^{-s_1} 2^{-(s_2-s_1)}\cdots 2^{-(s_k-s_{k-1})} 2^{-(m-1-s_k)} = 2^{-(m-1)}.$$ Therefore, since there are ${m-1}\choose{k}$ ways of choosing $S$ with length $k$, the probability that it takes time $k+1$ to travel from 0 to $m$ is $2^{-(m-1)} {m-1\choose k}$, and the expected time is $$\sum_{0\le k\le m-1} 2^{-(m-1)} (k+1) {m-1\choose k}$$ $$= \sum_{0\le k\le m-1} 2^{-(m-1)} {m-1\choose k}+ \sum_{1\le k\le m-1} (m-1) 2^{-(m-1)} {m-2\choose k-1}$$ $$= \frac{m+1}{2}.$$