Markov Chains

Handout #8 Markov Chains

Suppose there is a random sequence, X, such that:

X = {a, b, �, N }

That corresponds to a time interval [0, t].

X = {	a,	b,	�,	N }
	�	�		�

So,

X_t=0 = X₀ = ��

X_t=1 = X₁ = ��

X_t_=t = X_t = ��

[Note:� The values that X_t take on are finite or countably infinite.]

Then, the Markov Chain Property is:

P[X_t-1= j | X₀ = a, X₁ = b, K, X_t = i ] = P[X_t-1= j | X_t = i ] = q_ij ( t )

= the conditional probability that the Markov Chain is at time t in state j,

given that at time (t-1) it was in state i.

q_ij ( t ) is also called the transition probability

What does this mean?

P [ future states | past & present states ] is independent of the past events and depends only on the present state of the probability p_j( t + 1 ) {which represents the random value X_t+1takes on in state j}.

Or, in matrix and vector representation,

p( t + 1 ) = p( t ) Q( t )

where,

p( t ) is an N-dimensional row vector with elements p_j( t ), for j = 1, 2, �, N

Q( t ) is an N x N matrix with the elements q_ij( t ) and is called the Markov transition probability matrix at time t.

Stationary or Homogeneous

If all q_ij( t ) are independent of time t, then,

p( t + 1 ) = p( t ) Q

Q and Q( t ) must follow the properties:

q_ij( t ) � 0, for all i, j and t = 0, 1, 2, �

Example:� State Transition Diagram, page 83 of handout

States:� { 1, 2, 3 }

Transitions:

q₁₂ = 1, q₂₃ = 1/2, q₃₃ = 1/2, q₃₂ = 1/2, q₂₂ = 1/4, q₂₁ = 1/4

So,

	q₁₁	q₁₂	q₁₃
Q =	q₂₁	q₂₂	q₂₃
	q₃₁	q₃₂	q₃₃


Q =

Nonstationary:

p( t ) = p( 0 ) Q( 0 ) Q( 1 ) � Q( t � 1 )

Stationary:

p( t ) = p( 0 ) Q^t

If we let t = s + n, then:

p( s + n ) = p( 0 ) Q^s Qⁿ = p( s ) Qⁿ

Then,

From magic, we end up with:

P( z ) = p( 0 ) [ I � Qz ]^-1, where I is the identity matrix

Asymptotic Behavior:

length of time = "first passage of time"

(in terms of number of transitions)

when i = j

length of time = "recurrence time" for state i

Let be the probability that the first passage time from state i to state j is equal to n.

Then,

is the probability that starting in state i, the system reaches state j.

If:

f_ij �� :� may never reach j

f_ij �� :� probability distribution of the first passage of time

If i = j, �is the probability that starting in state i, system reaches state j (so if i = j, system gets back to i).

If:

f_ii �� :� transient state

f_ii �� :� recurrent state � probability distribution of recurrence time

Since they are just probability distributions, then we know they have mean values!

So, whenever f_ij = 1,

Look at Figure 2.10.

Difficult to find

i	j	n =	1	2	3	4�
1	1		0	1(1/4) = ��	1(1/4)(1/4) =	�

The mean though is easy to find:

etc.

When j = i,� m_ii = expected recurrence time

If:

m_ii �� , then recurrent state i is a null-recurrent state

m_ii �� , then recurrent state i is a positive-recurrent state or regular-recurrent state

Periodic state:� A state is periodic if n/t is not integer divisible (t is the greatest integer with this property) and ��In other words, a return to state i is impossible unless it occurs in t, 2t, 3t,� steps.

Ergodic state:� A state that is neither null nor periodic.

Absorbing state:� A state where once in, one can never leave.

Reachable state: , for n � 1.� If a state is reachable, then the state can communicate.

If all states in a state diagram can communicate, then the chain is irreducible.

So (page 88)

� States of an irreducible chain are either all recurrent or all transient.

� If one is periodic with period t, then all states are periodic with period t.

Question:� Does a system converge to some limiting distribution?

Assume an aperiodic, irreducible system is stable.� Let,

Then, by page 83,

p( t + 1 ) = p( t ) Q

p = p Q

A probability distribution p satisfying this equation is called a stationary distribution.� See Theorem 2.9.2., page 89.

An irreducible aperiodic Markov Chain has:

� At most one stationary distribution

� And either

1. All states are transient or all are null, so there's no stationary distribution.

2. All states are ergodic, so there's a unique stationary distribution.