Chapter IV.1: Regular matrices

Relating to first step analysis

• One very important "first step" problem is the stationary distribution.
• Under sutiable regularity conditions the stationary distribution instead of being a matrix is just a vector.
• What are these magic conditions?

Regular transition matrices

• regular: P to a large power has only positive elements
• Note: thus there is an epsilon such that P^t > epsilon for all large t.
• Via first step analysis: If we check for power n, we can show for power n+1.
• Claim: Probability of going from i to j at some point in time is 1. (called recurence)
• Proof: (1 - epsilon)^t - - > zero.

Limiting distribution

• P_ij^t --> P_ij^infinity
• But does it really depend on i?
• We will use the "long run mean fraction" of times in state j starting from state i as our probability of interest.
• Let f_j(t) be the actual fraction of times in state j if we start in state i. (NOTE: this is a random variable.)
• Let g_kj(t) be the actual fraction of times in state j AFTER we touch state k.
• Let T_k be the first time we touch k.
• Then: t f_j(t) < t g_j(t) + T_k
• And: t f_j(t) > t g_j(t)
• But: g_kj(t) --> P_kj^infinity
• But: f_j(t) --> P_ij^infinity
• So P_kj^infinity = P_ij^infinity
• Call it pi_j

Powers of matrices

• Computing p^infinity by computer: keep squaring it.
• For regularity: we only need to know 0*x = 0, x*y > 0.
• Keep track of signs.
• If you raise it to power larger than n², it will be regular if it is ever going to be regular. (proof by induction.)
• Need all n squared steps. (Consider cyclic shift with one alternate path of length 1 vs length 2.)

What if it isn't regular?

• One case we have already studied: absorbing states. (Note: dependence on initial condition.)
• Another is periodic (Note: dependence on initional conditions.)
• We'll discuss both of these later in the chapter.