Random Walk, Recurrence relation Q: There is a particle that moves on the positive section of the real line with an
absorbing barrier at 0. It moves two units to the right with probability p and one unit to the left with q = 1 - p at every instant. Find the probability that it will be absorbed at 0 if it starts from the point r.
I originally planned on using a probability approach to solve this question (e.g. similar to gambler's ruin), but the recursion formula here is too messy to solve for.
Is there a way to do this using mainly linear algebra? Thanks.
 A: Let $a_n$ be the probability that the particle eventually gets absorbed when starting from $n$. That is, $a_0=1$ and for $n\gt0$,
$$
a_n=pa_{n+2}+(1-p)a_{n-1}\tag{1}
$$
Let's try to solve the recurrence
$$
a_n=\frac1pa_{n-2}-\frac{1-p}{p}a_{n-3}\tag{2}
$$
To do this, we need to find the roots of the associated polynomial
$$
x^3-\frac1px+\frac{1-p}p=(x-1)\left(x^2+x+1-\frac1p\right)\tag{3}
$$
the roots of which are $1$ and $\frac{-1\pm\sqrt{\frac4p-3}}{2}$ . Therefore, the solution to $(2)$ looks like
$$
a_n=c_0+c_1\left(\tfrac{-1+\sqrt{\frac4p-3}}{2}\right)^n+c_2\left(\tfrac{-1-\sqrt{\frac4p-3}}{2}\right)^n\tag{4}
$$
For $p\lt1$, we have $\frac{-1-\sqrt{\frac4p-3}}{2}\lt-1$. So to keep $a_n$ bounded, we need $c_2=0$. As long as $p\gt\frac13$, the mean motion is $3p-1$ away from $0$, so the probability of eventual absorption should decrease to $0$; therefore, we should have $c_0=0$. That leaves
$$
a_n=\left(\tfrac{-1+\sqrt{\frac4p-3}}{2}\right)^n\tag{5}
$$
If $p\le\frac13$, then the probability of eventual absorption is $1$ from any point.
