\documentclass[12pt]{article}
% These packages help with equations, math symbols, etc.
\usepackage{amsmath,amssymb}
% This EXCELLENT resource is your guide to writing equations in LaTeX!
% ftp://ftp.ams.org/pub/tex/doc/amsmath/short-math-guide.pdf
% The following gives us better margins and spacing
\usepackage[margin=1in]{geometry}
\setlength{\topskip}{0in} % No blank space on first page
\setlength{\parindent}{0in} % 0 = no paragraph indentation
\setlength{\parskip}{0.5em} % space between paragraphs
%% remove ligatures (e.g. ``ff") to allow text copying from PDF
\usepackage{microtype}
\DisableLigatures{encoding = *, family = * }
% In case you want to hyperlink anything...
\usepackage[colorlinks=true, urlcolor=blue, anchorcolor=black, linkcolor=black, citecolor=black]{hyperref}
% For more compact numbered lists...
\usepackage{enumitem}
\setlist{noitemsep, topsep=-0.5em}
%% DRAFT watermark across each page:
%\usepackage[printwatermark]{xwatermark}
%\usepackage{xcolor}
%\newwatermark[allpages,color=gray!30,angle=55,scale=6,xpos=0,ypos=0]{DRAFT}
% If you want to include an image
\usepackage{graphicx}
% For fancy code box formatting
\usepackage{listings,xcolor}
\lstset{basicstyle=\footnotesize\ttfamily,breaklines=true}
%multiple columsn
\usepackage{multicol}
%% Strike out text with horizontal line via \sout
%\usepackage{ulem}
% Strole out text with ascending diagonal \cancel, descending diagonal \bcancel,
% x \xcancel, or ascending diagonal arrow to some limit with \cancelto{}{}
\usepackage{cancel}
\begin{document}
\textbf{\large MATH 420 HW \#3 \hfill Due: 3 Nov 2017} % Replace Due date with your name.
\vspace{1pt}
\hrule
\vspace{4pt}
%~\\ % this just forces a blank line.
\textbf{Instructions:} A printed copy of your homework should be handed in at \textbf{the start of class} the day it is due. Supplementary electronic files (e.g. R scripts or wxMaxima files;) should be emailed to the instructor prior to class with file name format LASTNAME-HWX.EXT \\
\textbf{1. Asymptotic Distributions.} We begin with a few useful definitions and facts about finite dimensional Markov Chains (adapted from Resnik (2005)\footnote{Resnik, S. L. 2005. \textit{Adventures in Stochastic Processes.} Ch. 2}):
If it is possible to reach state $j$ from state $i$, we say $j$ \textit{is \textbf{accessible} from} $i$, denoted as $i \to j$.
If $i \to j$ and $j \to i$, we say that states $i$ and $j$ \textbf{\textit{communicate}}, which we denote as $i \leftrightarrow j$. This is an equivalence relation (i.e., it is reflexive, symmetric, and transitive) and thus defines equivalence classes among states of a Markov Chain.
If a transition matrix $\mathbf{P}$ is \textbf{\textit{irreducible}} (i.e., $i \leftrightarrow j$ for all $i$,$j$ in the state space), then it has a left eigenvalue $\lambda_*=1$ (which may or may not be unique!) and the associated left eigenvector $\mathbf{v}$ is positive-valued. Thus, when scaled appropriately, that eigenvector is a \textbf{\textit{stationary distribution}} of the Markov Chain, since $\mathbf{v\,P}=\mathbf{v}$
\textbf{Convergence Condition:} If $\mathbf{P}$ is \textit{irreducible} and \textbf{\textit{aperiodic}} (i.e., $\mathbf{P}^n$ converges to some limit as $n \to \infty$) then initial distributions converge to that unique stationary distribution. An $n$x$n$ transition matrix \underline{$\mathbf{P}$ is irreducible and aperiodic \textit{iff} all entries in $\mathbf{P}^{n^2-2n+2}$ are positive,} \underline{i.e., \textit{iff} $\mathbf{P}$ is \textit{power-positive}.}
\textbf{Note:} Finite dimensional transition matrices have at most 1 stationary distribution, and exactly one if they are aperiodic. If $\mathbf{P}^n \to \mathbf{Q}$, the rows of $\mathbf{Q}$ are identical and are the unique stationary distribution.
\textbf{For each transition matrix below (i) determine if an arbitrary initial distribution converges to a stationary distribution by determining if the matrix is irreducible and aperiodic, (ii) find a stationary distribution of the matrix if one exists.}\\
\textbf{1a. (10 points)} $$\mathbf{P} = \begin{bmatrix} 4/5 & 1/5 \\ 4/7 & 3/7 \end{bmatrix}$$
\textbf{1b. (10 points)} $$\mathbf{P} = \begin{bmatrix} 1/3 & 1/3 & 1/3 \\ 0 & 9/11 & 2/11 \\ 1/5 & 4/5 & 0 \end{bmatrix}$$
\textbf{1c. (10 points)}
$$\mathbf{P} = \begin{bmatrix} 0 & 1 & 0\\ 1/3 & 0 & 2/3\\ 0 & 1 & 0 \end{bmatrix}$$
\clearpage
\textbf{2. Classification of States: \textit{Recurrence} and \textit{Transience}.}
Some questions require analyses that decompose the state space of a Markov Chain into \textit{recurrent} and \textit{transient} states. To do this we use the following definitions:
State $j$ is \textbf{\textit{recurrent}} if the markov chain returns to that state in a finite number of steps with probability 1. Otherwise, the state is called \textbf{\textit{transient}}.
\textbf{Proposition:} The state space $S$ of a Markov Chain can be partitioned into a set of \textbf{transient} states ($T$), and closed disjoint classes of \textbf{recurrent} states ($C_i$), so that $S=T\cup C_1 \cup C_2 ...$
\textbf{Procedure to identify transient and recurrent states.}
First, we define a collection of closed sets (\textit{closed} here means starting in a set, the Markov Chain can only transition among events in that set). Second, we identify equivalence classes (of states that communicate with each other) within each closed set. The equivalence classes that are closed contain the recurrent states. The non-closed classes contain transient states.
More specifically,
\begin{enumerate}
\item Choose a state $i$ and find all states accessible from $i$, all states accessible from those states, etc. This closed set of states that can (eventually) be reached from state $i$ will be denoted as $cl(i)$. This is the smallest closed set containing $i$. Find a state $k$ not in $cl(i)$ and repeat for all remaining states.
\item Next, identify the number of equivalence classes within each closed set. Some closed sets are a single equivalence class (i.e., $i \leftrightarrow j$ for all $i$,$j$ in that equivalence class). Those closed equivalence classes contain recurrent states. Closed sets may also contain more than 1 equivalence class. Non-closed equivalence classes (i.e. states that all communicate with one another, but can also access other states and thus never return) are the transient states.
\end{enumerate}
\begin{multicols}{2}
\textbf{Example:} %\vspace{-1em}
$$\mathbf{P} = \begin{bmatrix}
\frac12 & \frac12 & 0 & 0\\ \frac12 & \frac12 & 0 & 0 \\ \frac12 & \frac14 & 0 & \frac14 \\ 0 & 0 & \frac12 & \frac12 \\
\end{bmatrix}$$
\columnbreak
%
\begin{center}
Directed Graph representation.
\includegraphics[width=0.15\textwidth]{1234graph.png}
\end{center}
\end{multicols}
\vspace{-1em}
\quad The only closed equivalence class is \{1,2\}. Those are the recurrent states. It is possible\\ \vspace{0em}
\quad to start at 3 or 4, and (via $3 \rightarrow 2$) never return. Thus, \{3,4\} are the transient states.
\textbf{2. (\textbf{5 points} each) Find the \textit{transient} and \textit{recurrent} states for the Markov Chains implied by the following transition matrices:}
\textbf{2a. } $\begin{bmatrix} 1/2 & 0 & 0 & 1/2 \\ 0 & 2/3 & 1/3 & 0 \\ 0 & 1/3 & 2/3 & 0 \\ 1/8 & 0 & 0 & 7/8 \end{bmatrix}$ \qquad \textbf{2b. } $\begin{bmatrix} 1/2 & 0 & 0 & 1/2 \\ 0 & 2/3 & 1/3 & 0 \\ 0 & 1/3 & 1/3 & 1/3 \\ 1/8 & 0 & 0 & 7/8 \end{bmatrix}$ \qquad \textbf{2c. } $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1/3 & 1/3 & 1/3 & 0 \\ 0 & 1/3 & 1/3 & 1/3 \\ 0 & 0 & 1/2 & 1/2 \end{bmatrix}$
\clearpage
\textbf{3. Absorption Probabilities and Expected Hitting Times.} \\
Once states are classified as transient and recurrent, the transition matrix $\mathbf{P}$ can be rearranged so that the transient states make up the first rows (columns) of the matrix, and the recurrent states make up the remaining rows (columns). This puts the matrix into the form $$ \mathbf{P} = \begin{bmatrix} Q & R \\ 0 & P_{rec} \\ \end{bmatrix}.$$ The \textit{fundamental matrix} $$(I-Q)^{-1}$$ can be used to calculate absorption times and probabilities as detailed below.
\textbf{Absorption Probabilities}: It is sometimes desirable to know the probability of a certain state being reached before a set of other states. This is often accomplished by modifying the transition probabilities so that set of target states become \textit{absorbing states} (i.e., once at state $j$ the chain remains there w.p. 1) which are a special kind of recurrent state. We then can frame the question as ``What is the probability that the first recurrent state reached is the $j^\text{th}$ recurrent state, given that the Markov Chain started at the $i^\text{th}$ transient state?"
The probability of reaching the $j^\text{th}$ absorbing state, starting from the $i^\text{th}$ transient state is calculated from the matrix $U$ where $u_{ij}$ is the desired probability, and $U$ is given by $$ U = (I-Q)^{-1}\,R.$$
\textbf{Example:} Using the example transition matrix from exercise 2 above, what is the probability of hitting 1 before 2, given that we start in state 3?
To answer this, let us first rearrange the given transition matrix $\mathbf{P}$ as described above, and call the result $\mathbf{P}'$ (rows are labeled to clarify the rearrangement).\begin{multicols}{2}
$$\mathbf{P} = \begin{matrix} 1\\ 2\\ 3\\ 4\\ \end{matrix} \begin{bmatrix}
\frac12 & \frac12 & 0 & 0\\ \frac12 & \frac12 & 0 & 0 \\ \frac12 & \frac14 & 0 & \frac14 \\ 0 & 0 & \frac12 & \frac12 \\
\end{bmatrix} $$
\columnbreak
$$\mathbf{P}' = \begin{matrix} 3\\ 4\\ 1\\ 2\\ \end{matrix} \begin{bmatrix}
0 & \frac14 & \frac12 & \frac14 \\ \frac12 & \frac12 & 0 & 0 \\ 0 & 0 & \frac12 & \frac12\\ 0 & 0 & \frac12 & \frac12 \\
\end{bmatrix} $$
\end{multicols}
This implies $Q = \begin{bmatrix} 0 & \frac14 \\ \frac12 & \frac12 \\ \end{bmatrix}$ and $R = \begin{bmatrix} \frac12 & \frac14\\ 0 & 0 \\ \end{bmatrix}$.
Now we can rephrase our question: \textit{what is the probability of hitting 1 (the first recurrent state) first, given that we start in state 3 (the first transient state)?} The answer to our question is therefore given by $u_{11}$, which is obtained from $$U = (I-Q)^{-1}R = \begin{bmatrix}\frac{4}{3} & \frac{2}{3} \\ \frac{4}{3} & \frac{8}{3}\end{bmatrix} \begin{bmatrix} \frac12 & \frac14\\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix}\frac{2}{3} & \frac{1}{3}\\ \frac{2}{3} & \frac{1}{3}\end{bmatrix}. $$ These results are perhaps not unexpected: Inspecting the directed graph and transition probabilities given on the previous page, we see that the only way to exit the set of transients is via 3, and that transitioning to 1 is twice as likely as 2.
\textbf{Expected Absorption Times.} Let $\tau$ be the number of transitions it takes from starting at transient state $i$ until hitting the first recurrent state. Then we can define a function $g$ and compute the expected cumulative values starting from $i$ until reaching a recurrent state as $$w_i = \mathbf{E}\left(\sum_{n=0}^{\tau-1}g(X_n)\right). $$
If $T$ is the set of transients, it can be shown that for the vector of values $\mathbf{g} = [g(i), i \in T]'$ that the vector expected values $w = [w_i, i \in T]'$ is given by $$ w = (I-Q)^{-1}\,\mathbf{g}.$$
In the special case that $g=1$, this yields the expected time spent in the transient states.
\textbf{Example:} Continuing with the above example, we see that the expected times until leaving the transient state (starting from either state 3 or 4) are given by $$w = \begin{bmatrix}\frac{4}{3} & \frac{2}{3} \\ \frac{4}{3} & \frac{8}{3}\end{bmatrix}\begin{bmatrix} 1 \\ 1\end{bmatrix} = \begin{bmatrix} 2 \\ 4 \end{bmatrix}$$
\textbf{3. (10 points)} For the following transition matrix, find (1) the absorption probability matrix $U$ and use it to answer which recurrent state (C or D) is most likely to be reached first, given each possible (transient) starting state. (2) Find vector $w$ above and use it to give the expected time until leaving the transient states given each possible starting state.
$$\mathbf{P} = \begin{matrix} A\\ B\\ C\\ D \end{matrix}\begin{bmatrix} 1/2 & 1/3 & 1/6 & 0 \\ 1/5 & 1/5 & 0 & 3/5 \\ 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$
\end{document}