Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
It could also be resolved by induction. But I like your answer. – ablmf Jan 18 '12 at 2:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.