Markov Matrix Theory

$\newenvironment {prompt}{}{} \newcommand {\Sec }[2]{\section {#1}} \newcommand {\trademark }[0]{{R\!\!\!\!\!\bigcirc }} \newcommand {\EXER }[0]{\section *{Exercises}} \newcommand {\CEXER }[0]{} \newcommand {\TEXER }[0]{} \newcommand {\R }[0]{\mbox {$\Bbb {R}$}} \newcommand {\C }[0]{\mbox {$\Bbb {C}$}} \newcommand {\Z }[0]{\mbox {$\Bbb {Z}$}} \newcommand {\N }[0]{\mbox {$\Bbb {N}$}} \newcommand {\D }[0]{\mbox {{\bf D}}} \newcommand {\setmin }[0]{\;\mbox {--}\;} \newcommand {\Matlab }[0]{{M\small {AT\-LAB}} } \newcommand {\Matlabp }[0]{{M\small {AT\-LAB}}} \newcommand {\computer }[0]{\Matlab Instructions} \newcommand {\half }[0]{\mbox {$\frac {1}{2}$}} \newcommand {\compose }[0]{\raisebox {.15ex}{\mbox {{\scriptsize $\circ $}}}} \newcommand {\AND }[0]{\quad \mbox {and}\quad } \newcommand {\vect }[2]{\left (\begin {array}{c} #1_1 \\ \vdots \\ #1_{#2}\end {array}\right )} \newcommand {\mattwo }[4]{\left (\begin {array}{rr} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\mattwoc }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\vectwo }[2]{\left (\begin {array}{r} #1 \\ #2\end {array}\right )} \newcommand {\vectwoc }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\inv }[0]{^{-1}} \newcommand {\CC }[0]{{\cal C}} \newcommand {\CCone }[0]{\CC ^1} \newcommand {\Span }[0]{{\rm span}} \newcommand {\rank }[0]{{\rm rank}} \newcommand {\trace }[0]{{\rm tr}} \newcommand {\RE }[0]{{\rm Re}} \newcommand {\IM }[0]{{\rm Im}} \newcommand {\nulls }[0]{{\rm null\;space}} \newcommand {\dps }[0]{\displaystyle } \newcommand {\arraystart }[0]{\renewcommand {\arraystretch }{1.8}} \newcommand {\arrayfinish }[0]{\renewcommand {\arraystretch }{1.2}} \newcommand {\Start }[1]{\vspace {0.08in}\noindent {\bf Section~\ref {#1}}} \newcommand {\exer }[1]{\noindent {\bf \ref {#1}}} \newcommand {\ans }[0]{} \newcommand {\matthree }[9]{\left (\begin {array}{rrr} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\cvectwo }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\cmatthree }[9]{\left (\begin {array}{ccc} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\vecthree }[3]{\left (\begin {array}{r} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cvecthree }[3]{\left (\begin {array}{c} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cmattwo }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\thehelp }[0]{\thesection .\arabic {equation}} \newcommand {\matlabEquation }[0]{\let \oldtheequation \theequation \renewcommand {\theequation }{\oldtheequation *}\begin {equation}} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$ $% This file was *autogenerated* from markovMatrixTheory.sagetex.sage with % sagetex.py version 2015/08/26 v3.0-92d9f7a %058af3c6194e61fab8f1299884dc954d% md5sum of corresponding .sage file (minus "goboom","current_tex_line",and pause/unpause lines)$

In this appendix we use the Jordan normal form theorem to study the asymptotic dynamics of transition matrices such as those of Markov chains introduced in Section ??.

The basic result is the following theorem.

Let $A$ be an $n\times n$ matrix and assume that all eigenvalues $\lambda$ of $A$ satisfy $|\lambda |<1$ . Then for every vector $v_0\in \R ^n$ $\begin{equation} \label{E:convergeto0} \lim_{k\to\infty} A^kv_0 = 0. \end{equation}$

Proof

Suppose that $A$ and $B$ are similar matrices; that is, $B=SAS\inv$ for some invertible matrix $S$ . Then $B^k = SA^kS\inv$ and for any vector $v_0\in \R ^n$ (??) is valid if and only if $\lim _{k\to \infty } B^kv_0 = 0.$ Thus, when proving this theorem, we may assume that $A$ is in Jordan normal form.

Suppose that $A$ is in block diagonal form; that is, suppose $A=\mattwo {C}{0}{0}{D},$ where $C$ is an $\ell \times \ell$ matrix and $D$ is a $(n-\ell )\times (n-\ell )$ matrix. Then $A^k = \mattwo {C^k}{0}{0}{D^k}.$ So for every vector $v_0=(w_0,u_0)\in \R ^\ell \times \R ^{n-\ell }$ (??) is valid if and only if $\lim _{k\to \infty } C^kv_0 = 0 \AND \lim _{k\to \infty } D^kv_0 = 0.$ So, when proving this theorem, we may assume that $A$ is a Jordan block.

Consider the case of a simple Jordan block. Suppose that $n=1$ and that $A=(\lambda )$ where $\lambda$ is either real or complex. Then $A^kv_0 = \lambda ^kv_0.$ It follows that (??) is valid precisely when $|\lambda |<1$ . Next, suppose that $A$ is a nontrivial Jordan block. For example, let $A=\mattwo {\lambda }{1}{0}{\lambda } = \lambda I_2+N$ where $N^2=0$ . It follows by induction that $A^kv_0 = \lambda ^kv_0 + k\lambda ^{k-1}Nv_0 = \lambda ^kv_0 + k\lambda ^k\frac {1}{\lambda }Nv_0.$ Thus (??) is valid precisely when $|\lambda |<1$ . The reason for this convergence is as follows. The first term converges to $0$ as before but the second term is the product of three terms $k$ , $\lambda ^k$ , and $\frac {1}{\lambda }Nv_0$ . The first increases to infinity, the second decreases to zero, and the third is constant independent of $k$ . In fact, geometric decay ( $\lambda ^k$ , when $|\lambda |<1$ ) always beats polynomial growth. Indeed,

$\begin{equation} \label{E:PG} \lim_{m\to\infty}m^j\lambda^m = 0 \end{equation}$ for any integer $j$ . This fact can be proved using l’Hôspital’s rule and induction.

So we see that when $A$ has a nontrivial Jordan block, convergence is subtler than when $A$ has only simple Jordan blocks, as initially the vectors $Av_0$ grow in magnitude. For example, suppose that $\lambda =0.75$ and $v_0=(1,0)^t$ . Then $A^8v_0 = (0.901,0.075)^t$ is the first vector in the sequence $A^kv_0$ whose norm is less than $1$ ; that is, $A^8v_0$ is the first vector in the sequence closer to the origin than $v_0$ .

It is also true that (??) is valid for any Jordan block $A$ and for all $v_0$ precisely when $|\lambda |<1$ . To verify this fact we use the binomial theorem. We can write a nontrivial Jordan block as $\lambda I_n+N$ where $N^{k+1}=0$ for some integer $k$ . We just discussed the case $k=1$ . In this case

$\begin{align*} (\lambda I_n+N)^m &= \lambda^mI_n+m\lambda^{m-1}N + \left(\begin{array}{@{}c@{}} m\\2\end{array}\right)\lambda^{m-2}N^2 +\cdots \\ &\quad + \left(\begin{array}{@{}c@{}} m\\k \end{array}\right)\lambda^{m-k}N^k, \end{align*}$

where $\left (\begin {array}{@{}c@{}} m \\ j\end {array}\right ) = \frac {m!}{j!(m-j)!}=\frac {m(m-1)\cdots (m-j+1)}{j!}.$ To verify that $\lim _{m\to \infty }(\lambda I_n+N)^m = 0$ we need only verify that each term $\lim _{m\to \infty }\left (\begin {array}{@{}c@{}} m\\j \end {array}\right ) \lambda ^{m-j}N^j = 0$ Such terms are the product of three terms $m(m-1)\cdots (m-j+1) \AND \lambda ^m \AND \frac {1}{j!\lambda ^j}N^j.$ The first term has polynomial growth to infinity dominated by $m^j$ , the second term decreases to zero geometrically, and the third term is constant independent of $m$ . The desired convergence to zero follows from (??). $\blacksquare$

The $n\times n$ matrix $A$ has a dominant eigenvalue $\lambda _0>0$ if $\lambda _0$ is a simple eigenvalue and all other eigenvalues $\lambda$ of $A$ satisfy $|\lambda |<\lambda _0$ .

Let $P$ be a Markov matrix. Then $1$ is a dominant eigenvalue of $P$ .

Proof

Recall from Chapter ??, Definition ?? that a Markov matrix is a square matrix $P$ whose entries are nonnegative, whose rows sum to $1$ , and for which a power $P^k$ that has all positive entries. To prove this theorem we must show that all eigenvalues $\lambda$ of $P$ satisfy $|\lambda |\leq 1$ and that $1$ is a simple eigenvalue of $P$ .

Let $\lambda$ be an eigenvalue of $P$ and let $v=(v_1,\ldots ,v_n)^t$ be an eigenvector corresponding to the eigenvalue $\lambda$ . We prove that $|\lambda |\leq 1$ . Choose $j$ so that $|v_j|\ge |v_i|$ for all $i$ . Since $Pv=\lambda v$ , we can equate the $j^{th}$ coordinates of both sides of this equality, obtaining $p_{j1}v_1 + \cdots + p_{jn}v_n = \lambda v_j.$ Therefore, $|\lambda | |v_j| = |p_{j1}v_1 + \cdots + p_{jn}v_n| \leq p_{j1}|v_1| + \cdots + p_{jn}|v_n|,$ since the $p_{ij}$ are nonnegative. It follows that $|\lambda | |v_j| \leq (p_{j1}+\cdots +p_{jn})|v_j| =|v_j|,$ since $|v_i|\le |v_j|$ and rows of $P$ sum to $1$ . Since $|v_j|>0$ , it follows that $\lambda \leq 1$ .

Next we show that $1$ is a simple eigenvalue of $P$ . Recall, or just calculate directly, that the vector $(1,\ldots ,1)^t$ is an eigenvector of $P$ with eigenvalue $1$ . Now let $v=(v_1,\ldots ,v_n)^t$ be an eigenvector of $P$ with eigenvalue $1$ . Let $Q=P^k$ so that all entries of $Q$ are positive. Observe that $v$ is an eigenvector of $Q$ with eigenvalue $1$ , and hence that all rows of $Q$ also sum to $1$ .

To show that $1$ is a simple eigenvalue of $Q$ , and therefore of $P$ , we must show that all coordinates of $v$ are equal. Using the previous estimates (with $\lambda =1$ ), we obtain

$\begin{equation} \label{E:ineqM} |v_j|= |q_{j1}v_1 + \cdots + q_{jn}v_n| \leq q_{j1}|v_1| + \cdots + q_{jn}|v_n| \leq |v_j|. \end{equation}$ Hence $|q_{j1}v_1 + \cdots + q_{jn}v_n| = q_{j1}|v_1| + \cdots + q_{jn}|v_n|.$ This equality is valid only if all of the $v_i$ are nonnegative or all are nonpositive. Without loss of generality, we assume that all $v_i\geq 0$ . It follows from (??) that $v_j= q_{j1}v_1 + \cdots + q_{jn}v_n.$ Since $q_{ji}>0$ , this inequality can hold only if all of the $v_i$ are equal. $\blacksquare$

(a) Let $Q$ be an $n\times n$ matrix with dominant eigenvalue $\lambda >0$ and associated eigenvector $v$ . Let $v_0$ be any vector in $\R ^n$ . Then $\lim _{k\to \infty }\frac {1}{\lambda ^k}Q^kv_0 = cv,$ for some scalar $c$ .

(b) Let $P$ be a Markov matrix and $v_0$ a nonzero vector in $\R ^n$ with all entries nonnegative. Then $\lim _{k\to \infty }(P^t)^kv_0 = V$ where $V$ is the eigenvector of $P^t$ with eigenvalue $1$ such that the sum of the entries in $V$ is equal to the sum of the entries in $v_0$ .

Proof: (a) After a similarity transformation, if needed, we can assume that $Q$ is in Jordan normal form. More precisely, we can assume that $\frac {1}{\lambda }Q = \mattwo {1}{0}{0}{A}$ where $A$ is an $(n-1)\times (n-1)$ matrix with all eigenvalues $\mu$ satisfying $|\mu |<1$ . Suppose $v_0=(c_0,w_0)\in \R \times \R ^{n-1}$ . It follows from Theorem ?? that $\lim _{k\to \infty }\frac {1}{\lambda ^k}Q^kv_0 = \lim _{k\to \infty }(\frac {1}{\lambda }Q)^kv_0 = \lim _{k\to \infty }\mattwo {c_0}{0}{0}{A^kw_0} = c_0e_1.$ Since $e_1$ is the eigenvector of $Q$ with eigenvalue $\lambda$ Part (a) is proved.
(b) Theorem ?? states that a Markov matrix has a dominant eigenvalue equal to $1$ . The Jordan normal form theorem implies that the eigenvalues of $P^t$ are equal to the eigenvalues of $P$ with the same algebraic and geometric multiplicities. It follows that $1$ is also a dominant eigenvalue of $P^t$ . It follows from Part (a) that $\lim _{k\to \infty }(P^t)^kv_0 = cV$ for some scalar $c$ . But Theorem ?? in Chapter ?? implies that the sum of the entries in $v_0$ equals the sum of the entries in $cV$ which, by assumption equals the sum of the entries in $V$ . Thus, $c=1$ . $\blacksquare$

Exercises

Let $A$ be an $n\times n$ matrix. Suppose that $\lim _{k\to \infty } A^kv_0 = 0.$ for every vector $v_0\in \R ^n$ . Then the eigenvalues $\lambda$ of $A$ all satisfy $|\lambda |<1$ .