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

I'm modeling a process with a Markov chain like this:

$$ Pr(i \rightarrow i) = \alpha, Pr(i \rightarrow i+1) = \beta, Pr(i \rightarrow i+2) = \gamma $$

All other probabilities are zero.

Is there any way to calculate the expected number of steps it takes to reach state $n$ from state $0$? So far, all I've come up is binomial distribution in the case of $\alpha = 0$, but I'm unsure of even that.

share|cite|improve this question
Classic hitting time problem, also called first-passage problem. There is an entire book devoted to it. – Raskolnikov Dec 9 '10 at 11:58
up vote 4 down vote accepted

If $\beta,\gamma > 0$ then the expected number is infinity (unless $n = 0$), because either $n < 0$ and then you never reach $n$, or $n > 0$ and then with some positive probability you "hop" over $n$.

Suppose that state $n+1$ is also good, and $n > 0$. Let $E_i$ be the expected number of steps to get to states $n$ or $n+1$ starting at state $i$. Then

$$ E_i = \alpha E_i + \beta E_{i+1} + \gamma E_{i+2} + 1. $$

This is a non-homogeneous recurrence relation that you can solve by first finding some non-homogeneous solution (try $E_i = a i + b$) and then solving the corresponding homogeneous recurrence (without the $+1$) in the usual way (this amounts to solving the quadratic $(1-\alpha)x^2-\beta x-\gamma$; note the singular solution if this is a square). You will get a two-dimensional solution space which can you collapse by using $$E_n = E_{n+1} = 0.$$ Then the answer is $E_0$.

share|cite|improve this answer

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.