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

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