Lecture Notes for Simulation

27 April 2005 - Markov Chains

Outline

• Modeling dependence.

• The Markov property and Markov chains.

• Transition probability and the transition probability matrix.

• State diagrams and path probabilities.

• Step transition probabilities.

Independence

• We've been assuming independence for samples.

  • Simplifying assumptions; for calculations, for example.

  • Necessary assumptions; for the CLT, for example.

• Unfortunately, independence is an unrealistic assumption.

• Accommodate dependence between outcomes.

  • Simple

  • Using conditional probabilities.

Basics

• Let S be a set of outcomes.

  • S has at most countably infinite outcomes.

  • S is called a state space.

  • An element in S is called a state.

• Let { X₁, ..., X_t } be a sequence of t >= 1 random variables.

  • t is the time index (or just time).

  • X_i is the outcome at time i.

Examples

• A coin-flip game costs $1 to play. A player guessing the flip gets $2 ($1 up); a player missing the flip gets nothing ($1 down).

  • The state space S = { ..., -2, -1, 0, 1, 2, ... } is a player's winnings (or losing) when playing the game.

  • The sequence { X₁, ..., X_t } is a player's history through t turns in the game.

    • X_i is the history after i turns.

• A biological population exists in an environment.

• The state space S = { 0, 1, 2, ... } are possible values of the population census.

• The sequence { X₁, ..., X_t } is the population's demographics through time.

Conditional Probabilities

• The conditional probability P(AP(AA will occur given that B occurs. the number of events containing both A and B/
  the number of events containing B. P(intersection(A, B)/P(B)))

Dependence

• Most generally, given { X₁ = x₁, ..., X_i = x_i }
  the probability that X_i+1 equals some state s is
  P(X_i+1 = s | X₁ = x₁ and ... and X_i = x_i)

• The next step is conditioned on all the previous steps.

The Markov Property

• The Markov property holds for a distribution if, for any t > 0 and any sequence { X₁ = x₁, ..., X_i = x_t }
  P(X_i+1 = s | X₁ = x₁ and ... and X_i = x_i) = P(X_i+1 = s | X_i = x_i)

  That is, the probability of the next state is conditioned only by the current state and not by past states.

• A Markov chain is a sequence { X₁, ..., X_t } where each X_i is a IID random variable from a distribution with the Markov property.

Transition Probability

• Given the Markov chain { X₁, ..., X_t } and states i and jfrom S, the conditional probability
  P_ij(t) = P(X_t+1 = j | X_t = i)

  is the transition probability of moving from i to j at time t.

• If the transition probabilities don't depend on time, the Markov chain is called time homogeneous.

Transition Probability Matrix

• Given a finite state space { 1, ..., N } and a Markov-chain distribution, the transition probabilities can be arranged in an N-by-N matrix A such that
  A[i, j] = p_ij

• A is called a transition probability (or stochastic) matrix.

• A row of A p_i = [ p_i1, ..., p_iN ] gives the transitions out of state i.

  • sum(j = 1 to N, p_ij) = 1.

• Any square matrix A for which

  • all elements A[i, j] are non-negative and

  • sum(j = 1 to N, A[i, j]) = 1 for all rows i

  is a transition probability matrix.

State Diagrams

• Given a transition probability matrix A, the state-transition graph is a graph with

  • the set of nodes representing S and

  • the set of directed edges E a subset of SxS such that (i, j) is in E if and only if A[i, j] is non-zero.

Path Probabilities

• A Markov chain { X₁, X₂, ... } produces a path { s₁, s₂, ... } through the state space S.

• The path probability of s₁, s₂, ... } is the probability that it actually occurs; that is
  P('{ X₁)

  • Path probabilities involve using joint probabilities.

• Path probabilities are (or were) useful in determining when software testing can stop.

Computing Path Probabilities

• With lots of straightforward (mostly) math, the path probability
  P({ X₁, X₂, ... } = { s₁, s₂, ... })

  can be reduced to

  P(X₁ = s₁)p_s1s2p_s2s3...

  for the steady state transition probabilities p_ij.

• The value P_s⁽¹⁾ = P(X₁ = s) for all s in S is the initial distribution of the Markov chain.

• A Markov chain is defined by its probability transition matrix and initial distribution.

M-Step Transition Probabilities

• The conditional probability
  P_ij^(m)(t) = P(X_t+m = j | X_t = i)

  is the m-step transition probability, where i and j are states and m is positive.

• Given the transition probability matrix T, P_ij^(m)(t) = T^m+t[i, j].

Unconditional Transition Probabilities

• Assuming t = 0 (and is dropped), the probability of a Markov chain being in state j after n steps is

  P(Xn = j)	=	sum(i in S, P(Xn = j | X0 = i)P(X0 = i))
  	=	sum(i in S, Pij(n)P(X0 = i))

• If there exists an n > 0 such that P_ij⁽ⁿ⁾ > 0 for all i, j in S, then P(X_n = j) converges to the value P_j as n goes to infinity.

  • For large enough n, the probabilities P_j are constant for all j in S and the distribution is stationary.

• A Markov chain with a stationary distribution is called an ergodic Markov chain.

Row Probabilities

• Given the probabilities r^(t) = P(X_t = i), the vector
  r^(t) = (r₁^(t), r₂^(t), ..., r_n^(t)

  is the row probability.

• Given a probability transition matrix T,

  • r^(t) = r^(t-1)T and

  • r^(t) = r⁽¹⁾T^t-1.

Points to Remember

• Markov chains are a way to model (limited) dependence between outcomes.

• A Markov chain is defined by a transition probability matrix and an initial distribution.

• Ergodic Markov chains are based on a stationary distribution.

This page last modified on 2 May 2005.