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

