Markov Chains

Markov Chains
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Preliminaries

Random Variable:
- A function that assigns a number to every element in a sample space
Stochastic Process:
- A collection of random variables with the same sample space
- The collection is often written as \(X_1, X_2, \ldots , X_N\) and a generic element is often written as \(X_t\) (because stochastic processes often evolve over time)

Preliminaries (cont.)

(Courtesy of Hackles)

Markov Chains

Definition:
- The stochastic process \(\{X_1, X_2, \ldots , X_N\}\) is a Markov chain iff \(X_{t+1}\) is independent of \(\{X_1, X_2, \ldots , X_{t-1}\}\) provided that we know \(X_t\)
Interpretation:
- The past is summarized by the present

Transition Probabilities

An Observation:
- Since the past doesn't matter, we can simply consider the probabilities of moving from any state, \(i\), to any other state, \(j\), at time \(t\)
Notation:
- \( p_{ij}^{t} = P(X_{t+1} = j | X_{t} = i) \) for all \(i,j \in \mathcal{S}\) and \(t\)
A Requirement:
- \( \sum_{j \in \mathcal{S}} p_{ij}^{t} = 1 \) for all \(i \in \mathcal{S}\) and \(t\)

A Special Class of Markov Chains

Homogeneous Markov Chains:
- \( p_{ij}^{t} = p_{ij} \) for all \(i,j \in \mathcal{S}\) and \(t\)
For Our Purposes:
- We will only consider homogeneous Markov chains so we will simply omit the term "homogeneous"

An Example

The Setting:
- People can be either "not dieting" (0) or "dieting" (1)
- Every week, people decide whether to diet or not
- A person that is "not dieting" will start dieting with probability 1/2 and will continue not to diet with probability 1/2
- A person that is "dieting" will stop with probability 1/3 and will continue with probability 2/3
The Transition Matrix:
- It is convenient to represent the transition probabilities in a matrix, as follows:
- \(\mathbf{P} = \left[ \begin{array}{c c} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{3} & \frac{2}{3} \end{array} \right] \)
An Observation:
- The requirement on probabilities means that each row must sum to 1

An Example (cont.)

Notation:
- Let \(\mathbf{a}_0\) denote the (row vector) of people in each state at time \(0\)
The Dynamics:
- \(\mathbf{a}_1 = \mathbf{a}_0 \mathbf{P}\)
  \(\mathbf{a}_2 = \mathbf{a}_1 \mathbf{P} = \mathbf{a}_0 \mathbf{P} \mathbf{P} = \mathbf{a}_0 \mathbf{P}^{2}\)
  \(\vdots\)
  \(\mathbf{a}_t = \mathbf{a}_{t-1} \mathbf{P} = \mathbf{a}_0 \mathbf{P}^{t}\)

An Example (cont.)

Some Powers of \(\mathbf{P}\):
- \(\mathbf{P} = \left[ \begin{array}{l l} 0.5000000& 0.5000000 \\ 0.3333333& 0.6666667 \end{array} \right] \)
- \(\mathbf{P}^{2} = \left[ \begin{array}{l l} 0.4166667& 0.5833333\\ 0.3888889& 0.6111111\end{array} \right] \)
- \(\mathbf{P}^{3} = \left[ \begin{array}{l l} 0.4027778& 0.5972222\\ 0.3981481& 0.6018519\end{array} \right] \)
An Obvious Question:
- Is this a converging sequence?
Some More Powers of \(\mathbf{P}\):
- \(\mathbf{P}^{10} = \left[ \begin{array}{l l} 0.4000000& 0.6000000\\ 0.4000000& 0.6000000\end{array} \right] \)
- \(\mathbf{P}^{11} = \left[ \begin{array}{l l} 0.4000000& 0.6000000\\ 0.4000000& 0.6000000\end{array} \right] \)

Another Example

The Transition Matrix:
- \(\mathbf{P} = \left[ \begin{array}{l l} 0& 1 \\ 1& 0 \end{array} \right] \)
Some Powers of \(\mathbf{P}\):
- \(\mathbf{P}^{2} = \left[ \begin{array}{l l} 1& 0\\ 0& 1\end{array} \right] \)
- \(\mathbf{P}^{3} = \left[ \begin{array}{l l} 0& 1\\ 1& 0\end{array} \right] \)

Some Important Results

Sylvester's Formula:
- Let \(\mathbf{P}\) be a square matrix of (finite) order \(s+1\) and let \(\lambda_0 , \lambda_1 , \ldots , \lambda_s\) be the distinct eigenvalues of \(\mathbf{P}\). Then:
- \( \mathbf{P}^n = \sum_{k=0}^{s} \lambda_k^n \mathbf{Z}_k \)
- where:
- \( \mathbf{Z}_k = \frac{\Pi_{j \neq k}(\mathbf{P} - \lambda_j \mathbf{I})} {\Pi_{j \neq k}(\lambda_k - \lambda_j)} \)
Existence of the Limit:
- Let \(\mathbf{P}\) be a transition matrix with distinct eigenvalues, \(\lambda_k\), such that \(| \lambda_k | \lt 1\). Then:
- \( \mathbf{P}^{\infty} = \lim_{n \rightarrow \infty} \mathbf{P}^n \)
- exists with:
- \( \mathbf{P}^{\infty} = \mathbf{Z}_0 \)
- and the rows of \(\mathbf{P}^{\infty}\) sum to 1.

Some Important Times

First Passage Times:
- Let \(i,j\) be two states of the Markov chain \(\{ X_t \}\) and for a given \(t\) let \(X_t = i\). Then the first passage time from \(i\) to \(j\) is given by:
- \( T_{ij} = \inf \{k : X_{t+k} = j \} \)
First Return:
- \(T_{ii}\) is called the time of the first return to state \(i\)

Probability of First Passage

Notation:
- \( g_{ij}(t) = P\{ T_{ij} = t \} \) for all \(i,j \in \mathcal{S}\)
An Important Result:
- \( g_{ij}(1) = p_{ij} \)
- \( g_{ij}(t) = \sum_{k \neq j} p_{ik} g_{kj}(t - 1) \) for \(t=2, 3, \ldots\)

Classification of States

Persistent States:
- State \(j\) is called persistent iff \(P\{T_{jj} \lt \infty \} = 1\)
- Otherwise it is called transient
Null States:
- State \(j\) is called null iff \(E(T_{jj}) = \infty\)
- Otherwise it is called non-null
Absorbing States:
- State \(j\) is called absorbing iff \(p_{jj} = 1\)

Existence of the Limit Revisited

Intuition:
- In a steady state, the effects of the initial condition have vanished
A Sufficient Condition:
- The limit
- \( p_j = \lim_{n \rightarrow \infty} P\{X_t = j \} = \frac{1}{E(T_{jj})} \)
- exists (and is positive) if all of the states are persistent and non-null

A Real World Example

Setting:
- Transition probabilities describe the probability of advancing within an organization
Transition Probabilities:
- \( \mathbf{P} = \left[ \begin{array}{l l l l l l l} & &\mbox{VP}&\mbox{AVP}&\mbox{Proj. Ldr.}&\mbox{Sen. An.}&\mbox{Analyst}&\mbox{Quit}\\ \mbox{VP}&0.83&0.00&0.00&0.00&0.00&0.17\\ \mbox{AVP}&0.23&0.65&0.00&0.00&0.00&0.12\\ \mbox{Proj. Ldr.}&0.00&0.04&0.86&0.00&0.00&0.10\\ \mbox{Sen. An.}&0.00&0.00&0.08&0.89&0.00&0.03\\ \mbox{Analyst}&0.00&0.00&0.00&0.03&0.93&0.04\\ \mbox{Hired}&0.00&0.00&0.00&0.00&1.00&0.00\end{array} \right] \)

A Real World Example (cont.)

Limiting Probabilities:
- \( \mathbf{P}^{\infty} = \left[ \begin{array}{r r r r r r} 0.0156425&0.0115618&0.1011660&0.1770406&0.6491487&0.0454404\\ 0.0156425&0.0115618&0.1011660&0.1770406&0.6491487&0.0454404\\ 0.0156425&0.0115618&0.1011660&0.1770406&0.6491487&0.0454404\\ 0.0156425&0.0115618&0.1011660&0.1770406&0.6491487&0.0454404\\ 0.0156425&0.0115618&0.1011660&0.1770406&0.6491487&0.0454404\\ 0.0156425&0.0115618&0.1011660&0.1770406&0.6491487&0.0454404\end{array} \right] \)
A Question:
- What happens to this organization in the long run?

Expanding the State Space

An Intersting Situation:
- Suppose we try to model the probability that a person votes for the Democrat or Republican in a presidential election
- Does the history matter?
Suppose History Matters:
- How can we expand the state space to include history?

Applications

2D Random Walk:
- Equal probability of walking to the north, south, east, and west
3D Random Walk:
- Equal probability of walking to the six neighboring points (that differ by one unit in each dimension)

Applications (cont.)

Baseball:
- 24 states involving the locations of runners (2³ possibilities) and the number of outs (3 possibilities)
- Bukiet, B. et al. (1997) "A Markov Chain Approach to Baseball", Operations Research, Vol. 45, pp. 14-23.
Biology:
- Describe a complete genome in terms of constituent nucleotides
- The transition probabilities are the probability of seeing a string of Gs,As,Ts, or Cs given the last string
- Cuticchia, A.J. et al. (1992) Nucleic Acids Research, Vol. 20, pp. 3651-3657.

Applications (cont.)

Chemical Engineering:
- Transitions involve the probabilities of different chemical reactions
- Tami, A. (1998) Applications of Markov Chains in Chemical Engineering
Epidemiology:
- Transitions involve the probabilities of the spread of disease
- Lefevre, C. (1988) "A Markov Chain Model of Population Growth with an Application in Epidemiology", Biometric Journal, Vol. 30, pp. 165-173.
- Trajstman, A.C. (2002) "A Markov Chain Model for Newcastle Disease and its Relevance to the Intracerebral Pathogenicity Index", Biometric Journal, Vol. 44, pp. 43-57.

Applications (cont.)

Economics:
- Stokes, J.R. et al. (2007) "Mortgage Delinquency Migration: An Application of Maximum Entropy Econometrics", Journal of Real Estate Portfolio Management
Water Resources:
- Weismann, G.S. et al. (1999) "Three-dimensional hydrofacies modeling based on soil survey analysis and transition probability geostatistics", Water Resources Research, Vol. 35, pp. 1761-1770.