A recurrence system and Markov chain.

Question

I have troubles understanding the solution for the following exercise. It's about markov chain, but the part I don't understand is rather algebraic and about a recurrence system.

Exercise: Let $p \in ]0,1[$ and $(X_n)_{n\geq 0}$ be a Markov chain on $E=\{a,b,c\}$ with transition Matrix $$Q:=\begin{pmatrix}1-p &p &0\\1/2&0&1/2\\0&0&1 \end{pmatrix}$$ Compute the probabillity $P(X_n=b\mid X_0=a),\ n\in\mathbb{N}$ and find it's limit for $n\to \infty$

Solution: The graph looks like this:

First notice $Q_n=Q\cdot Q_{n-1}\quad \forall n\geq 1$. In particular $a_n:=P(X_n=b\mid X_0=a)$ and $b_n:=P(X_n=b\mid X_0=b)$ then $$\begin{cases}a_n=(1-p)a_{n-1}+pb_{n-1}\\ b_n=\frac{1}{2}a_{n-1}\end{cases}$$ Thus $(a_n)_{n\geq 0}$ is $$\begin{cases}a_n-(1-p)a_{n-1}-\frac{p}{2}a_{n-2}=0,\quad n\geq 2,\\ a_0=0,\ a_1=p\end{cases}$$

Here is the part I don't understand. I have no clue how to solve this recurrence system. I've never did this before.

Solution: Hence $$a_n=p\frac{(1-p+\sqrt{1+p^2})^n-(1-p-\sqrt{1+p^2})^n}{2^n\sqrt{1+p^2}}$$ And find $a_n\to 0$.

How do I get to that result? I tried $$a_n-(1-p)a_{n-1}-\frac{p}{2}a_{n-2}=a_n-(1-p)a_{n-1}-\frac{p}{2}\left((1-p)a_{n-2}-\frac{p}{2}a_{n-3}\right)=0$$ But I fail miserably. (I also find the solution quite not so "probabilistic", is this the only possible way to compute this?)

Answer 1

So we have: $${\bf Q}=\begin{pmatrix}1-p &p &0\\1/2&0&1/2\\0&0&1 \end{pmatrix}$$

Having a probability distribution row vector $\bf v$, the probability after a hop in the chain will be:

$$\bf vQ$$

Analogously, after $n$ hops: $${\bf vQ}^n$$

Now consider the vector $\bf v$ representing some probability distribution a priori. If we know the state is $a$, then ${\bf v} = [1,0,0]$, 100 % chance for first state? Then analogously for state $b$ : ${\bf v} = [0,1,0]$, because 100% chance for second state. Okay so far?

Now what remains is to try and express ${\bf vQ}^n$ in some simpler way. We can do this with an eigenvalue decomposition : $${\bf Q = S}^{-1}{\bf DS} $$ where $\bf D$ is diagonal, containing the eigenvalues $\lambda_1,\lambda_2,\lambda_3$, and $\bf S$ contains the corresponding eigenvectors as columns. $${\bf Q}^n = {\bf S}^{-1}{\bf D}^n{\bf S}$$ Here the ${\bf D}^n$ is much nicer to calculate than a general matrix power.

What is required to find the values in the $\bf D$ matrix (the $\lambda$s) this is to solve the equation:

$$\det ({\bf Q}-\lambda {\bf I}) = 0 \Leftrightarrow \left|\begin{pmatrix}1-p-\lambda &p &0\\1/2&-\lambda&1/2\\0&0&1-\lambda \end{pmatrix}\right|=0$$

Now this is a third order polynomial (in $\lambda$) which we leave as an exercise:

$$(1-p-\lambda)(-\lambda)(1-\lambda) - p/2(1-\lambda) = 0$$

If you solve it you will find the eigenvalues to be very resemblant to the expressions in your book and then you are almost done.

Answer 2

Hint: Check Recurrence relation to solve this linear recurrence relation.

Also, note that the given Markov chain is absorbing, with $ c $ being an absorbing state,

while $ a,b $ are transient states. Thus, $ \lim_{n\to \infty} P(X_n=b|X_0= a) = 0 $.