# Expected hitting time in a Markov chain

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.

• Do you know anything about linear recurrence relations with constant coefficients? That one is effectively $y_n=1+y_{n-1}/2+y_{n+1}/2$, or equivalently $y_{n+1}-2y_n+y_{n-1}=-1$.
– Ian
Commented Mar 4, 2021 at 14:56
• @Ian Your last right-hand side should be $-2$, right? Commented Mar 4, 2021 at 15:11
• @WoolierThanThou Yes, thanks, simple careless mistake. (I was thinking of the generator equation $Lu=-1$ for the hitting time but the generator still has the division in there in this context.)
– Ian
Commented Mar 4, 2021 at 15:43
• I'm not too familiar with them but this is just independent study so if there's no easier way then I'd be happy to learn
– user882487
Commented Mar 4, 2021 at 22:54
• I see where the linear recurrence relation comes from. However, I'm not sure how to find the result even with that.
– user882487
Commented Mar 5, 2021 at 1:10

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$$.
• I found a particular solution of $y_n = -n$ for the $q > p$ case from $c = -1$ Is that okay? I'm asking because I can't get the second part correct
– user882487
Commented Mar 5, 2021 at 3:41
• @fda The particular solution $y_n=-n$ is correct. But now you need to find what $\lambda_1$ and $\lambda_2$ are. The trick is that you have the principle of superposition, so you can plug in $\lambda_1^n$ and solve for $\lambda_1$ and then plug in $\lambda_2^n$ and solve for $\lambda_2$. Note that this is in the homogeneous equation so the $-2$ is now just $0$.
– Ian
Commented Mar 5, 2021 at 3:45