Solving a recurrence relation with eigenvectors

Question

Suppose you are given a recurrence relation describing the gambler's ruin with absorbing states 0 and 100. The probability of winning is given by the recurrence relationship: $$P_{n}=\frac{1}{2}P_{n-1}+\frac{1}{2}P_{n+1}$$ with $P_{0}=0$ and $P_{100}=1$ Is there a way to solve this problem, i.e achieving state 100, with eigenvalues and matrices?

Answer 1

Write the recurrence as $$ P_{n+1} = 2P_{n}-P_{n-1} $$ Then $$ v_n=\begin{pmatrix} P_{n+1} \\ P_{n} \end{pmatrix} = \begin{pmatrix} 2&-1\\1&0\end{pmatrix} \begin{pmatrix} P_{n} \\ P_{n-1} \end{pmatrix} =Av_{n-1} $$ and so $$ v_n = A^n v_0 $$ Now write $A=QJQ^{-1}$ so that $A^n=QJ^nQ^{-1}$. Eigenvalues and eigenvectors enter here.

However, in this particular case it is easy to compute $A^n$ directly: $$ \begin{pmatrix} 2&-1\\1&0\end{pmatrix}^n = \begin{pmatrix} n+1&-n\\n&-(n-1)\end{pmatrix} $$ This gives $$ \begin{pmatrix} P_{n+1} \\ P_{n} \end{pmatrix} = \begin{pmatrix} n+1&-n\\n&-(n-1)\end{pmatrix} \begin{pmatrix} P_{1} \\ P_{0} \end{pmatrix} $$ Since $P_0=0$, we get $$ P_{n} = nP_1 $$