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)
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:
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:
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}\)
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.