# Generating function of a stochastic matrix

This is an example demonstrating my answer to this math.stackexchange post: Let ${\{X_n:n\in\mathbb N_0\}}$ be a Markov chain on ${\{0,1\}}$ with transition matrix

$\displaystyle P = \begin{pmatrix}1-\alpha&\alpha\\\beta&1-\beta\end{pmatrix}$

where ${\alpha,\beta\in(0,1)}$. Then ${P}$ is irreducible and aperiodic, so there exists a unique stationary distribution ${\pi}$ satisfying

$\displaystyle \lim_{n\rightarrow\infty}(P^n)_{i\cdot} = \pi,\quad i=1,2$

where ${(P^n)_{i\cdot} }$ denotes the ${i^{\mathrm{th}}}$ row of ${P^n}$. From the global balance equation ${\alpha\pi_0 = \beta\pi_1}$ we see that ${\pi_1 = \frac\alpha\beta\pi_0}$, and normalization yields

$\displaystyle \pi = \left(\frac\beta{\alpha+\beta},\frac\alpha{\alpha+\beta} \right).$

To actually compute ${P^n}$, we could write ${P^n=AD^nA^{-1}}$ where the columns of ${A}$ are linearly independent eigenvectors of ${P}$ and ${D}$ is a diagonal matrix whose entries are the corresponding eigenvalues. This is possible because the Perron-Frobenius theorem implies that the eigenspace corresponding to the eigenvalue ${1}$ is one-dimensional, and the rank of ${P}$ is two. Instead, we will compute the generating function of ${P}$. Let

$\displaystyle P(s) = \sum_{n=0}^\infty P^n s^n,$

then

\displaystyle \begin{aligned} P(s) &= (I-sP)^{-1}\\ &= \frac{1}{\det (I-sP)}\mathrm{adj} A\\ &= \frac1{(1-s)(1-(1-\alpha-\beta)s)}\begin{pmatrix}1-(1-\beta)s&\alpha s\\\beta s& 1-(1-\alpha)s\end{pmatrix}. \\ &= \begin{pmatrix}P_{00}(s) & P_{01}(s)\\ P_{10}(s) & P_{11}(s), \end{pmatrix} \end{aligned}

where

$\displaystyle P_{ij}(s):=\sum_{n=0}^\infty \mathbb P(X_n=j\mid X_0=i)s^n.$

Partial fraction decomposition yields

\displaystyle \begin{aligned} &\quad\frac1{(1-s)(1-(1-\alpha-\beta)s}\\ &= (\alpha+\beta)^{-1}\frac1{1-s} + \left(1-(\alpha+\beta)^{-1}\right)\frac1{1-(1-\alpha-\beta)s}, \end{aligned}

and so we have

\displaystyle \begin{aligned} P_{00}(s) &= \left(\frac{1-(1-\beta)s}{\alpha+\beta}\right)\left(\frac1{1-s} + \frac1{1-(1-\alpha-\beta)s}\right)\\ &= \left(\frac{1-(1-\beta)s}{\alpha+\beta}\right) \left( \sum_{n=0}^\infty s^n + \sum_{n=0}^\infty (1-\alpha-\beta)^ns^n\right)\\ &= \sum_{n=0}^\infty \left(\frac\beta{\alpha+\beta}+\frac{\alpha(1-\alpha-\beta)^n}{\alpha+\beta}\right) s^n. \end{aligned}

Similar computations yield

\displaystyle \begin{aligned} P_{01}(s) &= \sum_{n=0}^\infty \left(\frac\alpha{\alpha+\beta}-\frac{\alpha(1-\alpha-\beta)^n}{\alpha+\beta}\right) s^n,\\\\ P_{10}(s) &= \sum_{n=0}^\infty \left(\frac\beta{\alpha+\beta}-\frac{\beta(1-\alpha-\beta)^n}{\alpha+\beta}\right) s^n,\\\\ P_{11}(s) &= \sum_{n=0}^\infty \left(\frac\alpha{\alpha+\beta}+\frac{\beta(1-\alpha-\beta)^n}{\alpha+\beta}\right) s^n, \end{aligned}

and it follows that

$\displaystyle P(s) = \begin{pmatrix} \pi_0(1+(1-\alpha-\beta)^n) & \pi_1 (1-(1-\alpha-\beta)^n) \\ \pi_0(1-(1-\alpha-\beta)^n) & \pi_1(1+(1-\alpha-\beta)^n)\end{pmatrix} s^n.$

## One thought on “Generating function of a stochastic matrix”

1. Anonymous says:

Great stuff, thanks for sharing!

Like