1
$\begingroup$

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.

  • 0
    Classic hitting time problem, also called first-passage problem. There is an [entire book](http://www.amazon.com/Guide-First-Passage-Processes-Sidney-Redner/dp/0521652480/ref=cm_cr_pr_product_top) devoted to it.2010-12-09

1 Answers 1

4

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