Loading Web-Font TeX/Math/Italic
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 (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.)
- 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.
MathJax Math Υ