2
$\begingroup$

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

1 Answers 1

1

For any sequence $S=(s_1,\dots,s_k)$ of intermediate states, $0, 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}. $

  • 0
    It could also be resolved by induction. But I like your answer.2012-01-18