Simulation Lecture Notes

Lecture Notes for Simulation

27 April 2005 - Markov Chains

The idea is to unroll the equality a random variable at a time, working backwards from t to 1. The probability

P({ X₁, ..., X_t } = { s₁, ..., s_t })

is equivalent to the conditional probability

P({ X₂, ..., X_t } = { s₂, ..., s_t } | X₁ = s₁)

by the Markov property. The equality

P(intersection(A, B) | C) = P(A | P(B | intersection(A, C))

provides a tool to pick apart the conditional probability by defining

A = { X₂, ..., X_t-1 } = { s₂, ..., s_t-1 }

B = { X_t = s_t }

C = X₁ = s₁

intersection(A, B) represents the intersection of all Markov-chain instances that have s_t as their t-th element and all Markov-chain instances that have s₂ through s_t-1 as their second through t-1th elements; that is, it's the Markov chain { X₂, ..., X_t } = { s₂, ..., s_t }.

The conditional probability can be rewritten as

P({ X₂, ..., X_t } = { s₂, ..., s_t } | X₁ = s₁) =
P({ X₂, ..., X_t-1 } = { s₂, ..., s_t-1 } | X₁ = s₁)
P(X_t = s_t | { X₁, ..., X_t-1 } = { s₁, ..., s_t-1 })

By the Markov property,

P(X_t = s_t | { X₁, ..., X_t-1 } = { s₁, ..., s_t-1 }) = P(X_t = s_t | X_t-1 } = s_t-1)

and P(X_t = s_t | X_t-1 = s_t-1) is equal to the single-step transition probability p_{s_t-1}_{s_t}. The conditional probability

P({ X₂, ..., X_t } = { s₂, ..., s_t } | X₁ = s₁)

can now be rewritten as

P({ X₂, ..., X_t-1 } = { s₂, ..., s_t-1 } | X₁ = s₁)p_{s_t-1}_{s_t}

and that's the first turn of the crank. Turning the crank t-2 more times reduces the conditional probability to

P(X₁ = s₁) p_s₁_s₂ ... p_{s_t-1}_{s_t}

P(X₁ = s₁) is given by the Markov chain's initial distribution.

This page last modified on 2 March 2005.