Week 8 - Markov chains (steady-state probabilities, absorbing states)

Question 1

Limiting distribution

Answer 1

Probabilities converge to some distribution π, independent of the initial state i

Question 2

Accessible state?
2 states communicate?

Answer 2

1. state j is ACCESSIBLE from state i if we can get from i to j with positive probability
   ie. there is a directed path from i to j in the state transition diagram
2. 2 states i and j COMMUNICATE if i is accessible from j & j is accessible from i
3. A Markov chain is IRREDUCIBLE if every pair of states COMMUNICATES
   - the state transition diagram is strongly connected

Question 3

What is a class?

Answer 3

A set of states that can MUTUALLY COMMUNICATE with each other

Question 4

3 properties of communication between states

Answer 4

1. Reflexitivity
   - every state communicates with itself
2. Symmetry
   - if i communicates with j, then j also comm. with i
3. Transitivity
   - if i communicates with j & j comm. with k, i then i communicates with k

Equivalence relation - a relation that has all these 3 properties

Question 5

3 classifications of states

Answer 5

1. ABSORBING state
   - if pii = 1
   - cannot access other states; if the process enters this state, it remains there forever
2. TRANSIENT state
   - upon entering this state, the process MIGHT never return again
   - a state where the probability of returning to it at some point in the future is strictly < 1 (eventually it will be absorbed to the recurrent states and never return)
3. RECURRENT state
   - upon entering this state, the process will certainly return to the same state (infinitely many times)
   - a state where the probability of returning to this state at some point in time in the future is 1

Question 6

2 properties that makes a Markov chain IRREDUCIBLE

Answer 6

1. If every pair of states COMMUNICATES!
2. If there is only a single class of states

Question 7

What makes a Markov chain aperiodic?

*Periodicity can always be broken by adding a LOOP

Answer 7

If all states are aperiodic.

*All states in the same class have the same period

Question 8

What makes a Markov chain ergodic?

Ergodic theorem

Answer 8

1. If the Markov chain is IRREDUCIBLE and APERIODIC
2. Ergodic theorem - Every irreducible and aperiodic (ergodic) Markov chain has a LIMITING DISTRIBUTION π

(and π is a UNIQUE STATIONARY distribution)

Question 9

Stationary distribution theorem

Answer 9

1. Every finite Markov chain has a stationary distribution
2. If the Markov chain is irreducible, then there is a unique stationary distribution π and πi > 0 for all states i

*limiting distributions are stationary

Question 10

What is the Period of a state A mean?

Answer 10

Let R be the set of times that A can be revisited.

p is the greatest common divisor GCD of R (and 0 ∈ R)

Question 11

Ergodic theorem - Why must the Markov chain be irreducible and aperiodic?

Answer 11

1. If the chain is not irreducible, some state j is not accessible from some state i, and if we start in state i the probability of being in state j is 0, always, so we cannot have πj > 0.
2. Even if all states are recurrent and the chain is aperiodic, there can be multiple stationary distributions (therefore no limiting distribution)
   » ie. 2 absorbing states lead to 2 stationary distributions
3. Example with period 3. No limiting distribution, but there is a stationary distribution.