Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 0 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|improve this answer
    
It could also be resolved by induction. But I like your answer. –  ablmf Jan 18 '12 at 2:37

Your Answer

 
discard

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.