Chapter 2 Exercise 2 Question (a) Page 84 Linda J. S. Allen 2010

Question

Exercise 2 Question (a) Page 84

Textbook: An Introduction to Stochastic Processes with Applications to Biology 2nd Edition Linda J. S. Allen 2010

Exercise

Suppose $P$ is an $N\times N$ stochastic Matrix (column sums equal one), $P= \begin{pmatrix} p_{11} & p_{12} & \ldots & p_{1N} \\ p_{21} & p_{22} & \ldots & p_{2N} \\ \vdots & \vdots & \ldots & \vdots \\ p_{N1} & p_{N2} & \ldots & p_{NN} \end{pmatrix}$

• (a) Show that $P^{2}$ is a stochastic matric. Then show that $P^{n}$ is a stochastic matrix for all positive integers $n$.

My attempts:

Suggested solution:

Let's prove the first part of the question.

• Let's Show that $P^{2}$ is a stochastic matric.

$P^{2}$ is a stochastic matric $\iff \begin{cases} \forall i,j\in [\![1,N]\!];\; p^{2}_{ij}\geq 0 \\ \\ \forall j\in [\![1,N]\!];\; \sum_{i=1}^{N}p^{2}_{ij}=1 \end{cases}$

(1) $\forall i,j\in [\![1,N]\!];\; p^{2}_{ij}\geq 0$

Let $i,j\in [\![1,N]\!];$ we've $p^{2}_{ij}=\sum_{k=1}^{N}p_{ik}p_{kj}\geq 0$ since $\forall i,j\in [\![1,N]\!];\; p_{ij}\geq 0$

(2) $\forall j\in [\![1,N]\!];\; \sum_{i=1}^{N}p^{2}_{ij}=1$

Let $j\in [\![1,N]\!];$ we've

$\begin{align*} \sum_{i=1}^{N}p^{2}_{ij}&=\sum_{i=1}^{N}\sum_{k=1}^{N}p_{ik}p_{kj}\\ &=\sum_{k=1}^{N}\left(\sum_{i=1}^{N}p_{ik}p_{kj} \right)\\ &=\sum_{k=1}^{N}\left(p_{kj}\sum_{i=1}^{N}p_{ik}\right)\\ &=\sum_{k=1}^{N}\left(p_{kj}.1\right)\\ &=\sum_{k=1}^{N}p_{kj}=1 \end{align*}$

which completes the proof.

Let's prove the second part of the question.

Show that $P^{n}$ is a stochastic matrix for all positive integers $n$.

First, let's recall the principle of induction:  Let $p(k)$ be a statement depending on a variable $k\in \mathbb{N}$. In order to prove the statement "$p(k)$ is true for all $k\in\mathbb{N}$" it is sufficient to prove:

• (i) $p(1)$ is true and
• (ii) For any given $n\in\mathbb{N},$ if $p(n)$ is true then $p(n+1)$ is true.

Base case:

From the first part of the question, we have If $P$ is a stochastic matrix, then $P^{2}$ is so.

Induction step: Let $n\in\mathbb{N}$; assume that $P^{n}$ is a stochastic matrix. Then, we prove that $P^{n+1}$ is also a stochastic matrix

$P^{n+1}=P^{n}P$

Now $P^{n}$ is stochastic by the inductive hypothesis. Hence, $P^{n}P$ is stochastic by the Base Step.

Please correct me if I am wrong. Thank you in advance.

Answer 1

Let's say we have two stochastic $n\times n$ matrices $A$ and $B$, with $$A=\begin{pmatrix} a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots&a_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\a_{n,1} &a_{n,2}&a_{n,n}&\ldots\end{pmatrix}$$ $$B=\begin{pmatrix} b_{1,1}&b_{1,2}&\ldots &b_{1,n}\\b_{2,1}&b_{2,2}&\ldots&b_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\b_{n,1} &b_{n,2}&\ldots&b_{n,n}\end{pmatrix}$$ Note that the $i^\text{th},j^\text{th}$ entry of the matrix $AB$ is $$\sum_{k=1}^n a_{i,k}b_{k,j}$$ Hence, the sum of the elements in the $j^\text{th}$ column of $AB$ is $$\sum_{i=1}^n\sum_{k=1}^n a_{i,k}b_{k,j}$$ Since $A,B$ are both stochastic, we have $$\sum_{i=1}^n a_{i,j}=\sum_{i=1}^n b_{i,j}=1~\forall j\in [1,n]\cap\mathbb{Z}$$ Going back to the sum of the $j^\text{th}$ column of $AB$, we can switch the indices to get that it is equivalent to $$=\sum_{k=1}^n\sum_{i=1}^n a_{i,k}b_{k,j}$$ $$=\sum_{k=1}^n \left(b_{k,j}\sum_{i=1}^n a_{i,k}\right)$$ $$=\sum_{k=1}^n b_{k,j}$$ $$\boxed{=1}$$

Hence, we have proved that the product of two arbitrary stochastic matrices is another stochastic matrix. Using this lemma will be essential to a possible solution to both of your problems.

Answer 2

Show that $P^{n}$ is a stochastic matrix for all positive integers $n$.

We prove this by induction on $n$. The base step is $n=2$. Let $P$ and $Q$ be two $N\times M$ stochastic matrices, with $$P=\begin{pmatrix} p_{1,1}&p_{1,2}&\ldots &p_{1,M}\\ p_{2,1}&p_{2,2}&\ldots&p_{2,M}\\ \vdots&\vdots&\ddots&\vdots\\ p_{N,1} &p_{N,2}&\ldots&p_{N,M} \end{pmatrix}, \rm{and} \quad Q=\begin{pmatrix} q_{1,1}&q_{1,2}&\ldots &q_{1,M}\\ q_{2,1}&q_{2,2}&\ldots &q_{2,M}\\ \vdots&\vdots&\ddots&\vdots\\ q_{N,1}&q_{N,2}&\ldots&q_{N,M} \end{pmatrix}$$ Then the entries of $PQ$ are nonnegative, since the entries of both $P$ and $Q$ are nonnegative. Furthermore, the sum of the entries in the $j^\text{th}$ column of $PQ$ is $$\sum_{i=1}^{N}\left(i^\text{th} row of P \right)\left( j^\text{th} row of Q\right)=\sum_{i=1}^N\sum_{k=1}^M p_{i,k}q_{k,j}$$ Since $P,Q$ are both stochastic, we have $$~\forall j\in [\![1,M]\!];~~\sum_{i=1}^N p_{i,j}=\sum_{i=1}^N q_{i,j}=1$$

Also for every column with index $j$:

$\begin{align*} \sum_{i=1}^N\sum_{k=1}^M p_{i,k}q_{k,j}&=\sum_{k=1}^M\sum_{i=1}^N p_{i,k}q_{k,j}\\ &=\sum_{k=1}^N \left(q_{k,j}\sum_{i=1}^N p_{i,k}\right)\\ &=\sum_{k=1}^N q_{k,j}\\ &\boxed{=1} \end{align*}$

Hence, $PQ$ is stochastic.

For the Inductive Step, we assume that $P^{n}$ is a $N\times M$ stochastic matrix for all positive integers $n$, and we must show that $P^{n+1}$ is a $N\times M$ stochastic matrix for all positive integers $n$. Now $P^{n}$ is stochastic by the inductive hypothesis. Hence, $P^{n}P$ is stochastic by the Base Step.