Expected hitting time in a Markov chain

Question

Consider a Markov chain on $\{0, 1, \ldots\}$ with $p_{i, i-1}=q$ and $p_{i,i+1}=p$.

• If $p = q = 0.5$, find the expected hitting time to hit State $0$ from all states $k \geq 1$.

• If $q>p$, find the expected hitting time from each state $k\geq 1$.

---

I tried to set up systems of equations:

• $E(X_0) = 0$

• $E(X_n) = \frac{1}{2}(1 + E(X_{n-1})) + \frac{1}{2}(1 + E(X_{n+1}))$ for $n \geq 1$.

I need help analyzing this system in the two cases though. I think the answer in the first case is just $\infty$, so I'm guessing I get a divergent series or something. I'm not entirely sure.

Any help is greatly appreciated. I know it's related to the Gambler's ruin problem, but I can't find anything online.

Answer 1

Let $y_n=E[X_n]$ then you have a linear recurrence relation with constant coefficients:

$$y_{n+1}-2y_n+y_{n-1}=-2.$$

This system needs two boundary conditions. You only really have one, which is $y_0=0$. To fix that, you can artificially introduce $y_N=0$ (so that you are solving for the expected time to hit $0$ or $N$ from inside) and then send $N \to \infty$ (so that you are asymptotically guaranteed to hit $0$ first since $N$ is being moved further and further away).

To solve the finite problem, the procedure is to split into a homogeneous and particular solution. For a particular solution, you may first guess that a constant might work, but you find you're wrong (you get $0=-2$). Next you may guess that a linear function might work, but in this special case with the probabilities being equal you are again wrong (you get $0=-2$). So you continue all the way to a quadratic function and get

$$c \left ( (n+1)^2-2n^2+(n-1)^2 \right ) = c \left ( n^2 + 2n + 1 - 2n^2 + n^2 - 2n + 1 \right ) = 2c = -2$$

so $c=-1$. Thus a particular solution is $y_n=-n^2$.

Next you need the general homogeneous solution. It turns out that you already found it in the course of doing the guesswork to find the particular solution: the general homogeneous solution is $y_n=c_1 + c_2 n$. So you have

$$y_n=c_1 + c_2 n - n^2$$

where $c_1,c_2$ are to be found. Plugging in $0$ you get $c_1=0$. Plugging in $N$ you get $c_2 N - N^2 = 0$ so $c_2=N$. Thus

$$y_n=N n - n^2.$$

Now what happens when you send $N \to \infty$ for $n>0$ fixed?

The case $q>p$ is fairly similar. The differences are:

• In finding the particular solution, the linear function will actually work
• To get the homogeneous solution you will need to look for exponential solutions, i.e. the homogeneous solution will be of the form $c_1 \lambda_1^n + c_2 \lambda_2^n$.