Markov Chains, an example

 

If we have a situation where the next state depends only upon the current state and the transitions from this current state, then we have a Markov Chain.� If the transition probabilities are independent of the time then we have a homogeneous Markov Chain.

 

Given a diagram of cities:

 

 

 

 

 

 

 

 

This relates to the transition matrix:

 

 

 

 

 

 

 

 

 

 

Stochastic?� Do the rows sum to one and every element of the matrix � 0.

Doubly Stochastic?� Is it stochastic and do the columns sum to one?

 

So:

i

j

qij

1

1

 

1

2

 

1

3

 

2

1

 

2

2

 

2

3

 

3

1

 

3

2

 

3

3

 

fii = Prob [ ever returning to state i ]

 

fii(n) = Prob [ going from state i to state i for the first time in n transitions ]

 

So:

i

j

qij

fij(1)

fij(2)

fij(1)

fij(4)

1

1

 

 

 

 

 

1

2

 

 

 

 

 

1

3

 

 

 

 

 

2

1

 

 

 

 

 

2

2

 

 

 

 

 

2

3

 

 

 

 

 

3

1

 

 

 

 

 

3

2

 

 

 

 

 

3

3

 

 

 

 

 

 

fii = S fii(n) , for n = 1 to �

 

This is just the probability that we ever return to i.

 

We classify states of a Markov Chain according to the value of fii.

 

If:

�         fii = 1 then state i is recurrent,

�         fii < 1 then state i is transient.

 

Also, if the only possible steps at which we can return to state i is t, 2t, 3t, etc., where t > 1, and t is the largest possible integer where this holds, then state i is periodic with period t.� If t = 1, then state i is aperiodic.

 

For example:

 

 

 

 

 

 

 

 

is periodic with period t = 2 because from state A to get back takes 2, 4, 6, etc. transitions.� So, this is t, 2t, 3t, etc.,... period t = 2.

 

If we can reach state i from every other state, then state i is reachable.� If two states are reachable from each other then they can communicate.� In the little example above, both A and B are reachable from each other and can communicate.

 

If every state can be reached from every other state then the chain is irreducible.

 

A group of states is closed if there is no one-step transition from the group to any other state.� Here's an example:

 

 

 

 

 

 

 

 

 

Note that once you're in state Z you can never leave.� This is an absorbing state.

 

So, if we don't have any closed subsets then we have an irreducible chain.� If we have closed subsets, then the chain is reducible.

 

Given recurrent states, fii = 1, we may want to know the average time to return to state i.� This is given by:

mii = S n fii(n), for n = 1 to �, and state i is recurrent non-null.

 

Note that if fii < 1, then,

mii = � and state i is recurrent null.

 

One more thing:� an ergodic state is a recurrent non-null, aperiodic state.