Chapter 2 Exercise 2 Question (a) Page 84 Linda J. S. Allen 2010 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.
 A: 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.
A: 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.
