- Forward


Markov Chains
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Preliminaries
Back SMYC Forward
  • 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.)
Back SMYC Forward
Hackles-Stochastic
(Courtesy of Hackles)
Markov Chains
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • Baseball:
    • 24 states involving the locations of runners (23 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.
There's Always More to Learn
Back -