Limiting behaviour of n-step transition probabilities, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Example 15.1. Assume that the transition matrix is given by 

Recall that the n-step transition probabilities are given by powers of P. So let’s look at some large powers of P, beginning with 

Then, to four decimal places

and subsequent powers are the same to this precision. The matrix elements appear to converge and the rows become almost identical. Why? What determines the limit? These questions will be answered in this chapter.
We say that a state  implies that d|n, and (2) d is the largest positive integer that satisfies (1).

Example 15.2. Simple random walk on Z, with p ∈ (0,1). The period of any state is 2 because the walker can return to her original position in any even number of steps, but in no odd number of steps.

Example 15.3. Random walk on vertices of a square. Again, the period of any state is 2, for the same reason.

Example 15.4. Random walk on vertices of triangle. The period of any state is 1 because the walker can return in two steps (one step out and then back) or three steps (around the triangle).

Example 15.5. Deterministic cycle. In a chain with n states 0,1,...,n−1, which moves from i ti (i + 1) mod n with probability 1, has period n. So, any period is possible. However, if the following two transition probabilities are changed: P₀₁ = 0.9 and P₀₀ = 0.1, then the chain has period 1. In fact, the period of any state i with P_ii > 0 is trivially 1.

It can be shown that a period is the same for all states in the same class. If a state, and therefore its class, has period 1, it is called aperiodic. If the chain is irreducible, we call the entire chain aperiodic if all states have period 1.

For a state i ∈ S, let
R_i = min{n ≥ 1 : X_n = i}
be the first time, after time 0, that the chain is in i ∈ S. Also, let

be the p. m. f. of R_i when the starting state is i itself (in which case we may call R_i the return time). We can connect these to a familiar quantity,

so that the state i is recurrent exactly when  Then we define

If the above series converges, i.e., m_i < ∞, then we say that i is positive recurrent. It can be shown that positive recurrence is also a class property: a state shares it with all members of its class. Thus an irreducible chain is positive recurrent if each of its states is. 

It is not hard to show that a finite irreducible chain is positive recurrent. In this case there must exist a m ≥ 1 and an ǫ > 0 so that i can be reached from any j in m steps with probability at least ǫ. Then P(R_i ≥ n) ≤ (1 − ǫ)^⌊n/m⌋, which goes to 0 geometrically fast.

We now state the key theorems. Some of these have rather involved proofs (although none are all that difficult), which we will merely sketch or omit altogether.
 

Theorem 15.1. Proportion of the time spent at i.

Proof. The idea is quite simple: once the chain visits i, it returns on the average once per m_i time steps, hence the proportion of time spent there is 1/m_i. We skip a more detailed proof.

A vector of probabilities, π_i, i ∈ S, such that  is called an invariant, or stationary, distribution for a Markov chain with transition matrix P if 

In matrix form, if we put π into a row vector [π₁,π₂,...], then
[π₁,π₂,...] � P = [π₁,π₂,...],
thus [π₁,π₂,...] is the left eigenvector of P, for eigenvalue 1. More important for us is the probabilistic interpretation. If πi is the p. m. f. for X₀, that is, P(X₀ = i) = π_i, for all i ∈ S, it is also p. m. f. for X₁, and then for all other X_n, that is, P(X_n = i) = π_i, for all n.

Theorem 15.2. Existence and uniqueness of invariant distributions.
 

In fact, an irreducible chain is positive recurrent if and only if a stationary distribution exists.

The formula for π should not be a surprise: if the probability that the chain is in i is always π_i, then one should expect the proportion of time spent at i, which we already know to be 1/m_i, to be equal to π_i. We will not, however, go deeper into the proof.

Theorem 15.3. Convergence to invariant distribution.

Recall that    and note that the limit is independent of the initial state. Thus the rows of Pn are more and more similar to the row vector π as n becomes large.

The most elegant proof of this theorem uses coupling, an important idea first developed by a young French probabilist Wolfgang Doeblin in the late 1930s. (Doeblin’s life is a very sad story. An immigrant from Germany, he died as a soldier in the French army in 1940, at the age of 25. He made significant mathematical contributions during his army service.) Start with two independent copies of the chain — two particles moving from state to state according to transition probabilities — one started from i, the other using initial distribution π. Under the stated assumptions, they will eventually meet. Afterwards, the two particles move together in unison, that is, they are coupled. Thus the difference between the two probabilities at time n is bounded above by twice the probability that coupling does not happen by time n, which goes to 0. We will not go into greater details, but, as we will see in the next example, periodicity is necessary.

Example 15.6. Deterministic cycle with a = 3 has transition matrix 

This is an irreducible chain, with invariant distribution  (as it is very easy to check). Moreover 

P³ = I, P⁴ = P, etc. Although the chain does spend 1/3 of the time at each state, the transition probabilities are a periodic sequence of 0’s and 1’s and do not converge.
Our final theorem is mostly a summary of results for the special, and for us the most common, case.

Theorem 15.4. Convergence theorem for finite state space S.

Example 15.7. We begin by our first example, Example 15.1. That was clearly an irreducible, and also aperiodic (note that P₀₀ > 0) chain. The invariant distribution [π₁,π₂,π₃] is given by

This system has infinitely many solutions, and we need to use

π₁ + π₂ + π₃ = 1

to get the unique solution

Example 15.8. General two-state Markov chain. Here S = {1,2} and 

and we assume that 0 < α,β < 1

and after a little algebra,

Here are a few common follow-up questions:

• Start the chain at 1. In the long run, what proportion of time does the chain spend at 2? Answer: π₂ (and does not depend on the starting state).

• Start the chain at 2. What is the expected return time to 2? Answer:  .

• In the long run, what proportion of time is the chain at 2, while at the previous time it was at 1? Answer: π₁P₁₂, as it needs to be at 1 at the previous time, and then make a transition to 2 (again, the answer does not depend on the starting state).

Example 15.9. Assume that a machine can be in 4 states labeled 1, 2, 3, and 4. In states 1 and 2, the machine is up, working properly. In states 3 and 4, the machine is down, out of order. Suppose that the transition matrix is

(a) Compute the average length of time the machine remains up after it goes up. (b) Compute the proportion of times that the system is up, but down at the next time step (this is called the breakdown rate).

We begin with computing the invariant distribution, which works out to be    The breakdown rate is then

the answer to (b).

Now let u be the average stretch of time machine remains up and d be the average stretch of time it is down. We need to compute u to answer (a). We will achieve this by figuring out two equations that u and d must satisfy. For the first equation, we use that the proportion of time the system is up is 

For the second equation, we use that there is a single breakdown in every interval of time consisting of the stretch of up time followed by the stretch of down time, i.e., from a repair to the next repair. This means 

the breakdown rate from (b). The system of two equations gives d = 2 and, to answer (a), 

Computing the invariant distribution amounts to solving a system of linear equations. Nowadays this is not a big deal, even for enormous systems; still, it is worthwhile to observe that there are cases when the invariant distribution is very easy to identify.

We call a square matrix with nonnegative entries doubly stochastic if the sum of the the entries in each row and in each column is 1.

Proposition 15.5. Invariant distribution in a doubly stochastic case.

Proof. Assume that S = {1,...,m}, as usual. If [1,...,1] is the row vector with m 1’s, then [1,...,1]P is exactly the vextor of column sums, thus [1,...,1]. This vector is preserved by right multiplication by P and then so is . This vector specifies the uniform p. m. f. on S.

Example 15.10. Simple random walk on a circle. Pick a probability p ∈ (0,1) Assume that a points labeled 0,1,...,a − 1 are arranged on a circle clockwise. From i, the walker moves to i + 1 (with a identified with 0) with probability p and to i − 1 (with −1 identified with a − 1) with probability 1 − p. The transition matrix is
 

and is doubly stochastic. Moreover, the chain is aperiodic if a is odd and otherwise periodic with period 2. Therefore, the proportion of time the walker spends at any state is which is also the limit of  for all i and j if a is odd. If a is even, then  = 0 if (i − j) and n have a different parity, while if they are of the same parity,  

Assume that we change the transition probabilities a little: assume that, only when she is at 0, the walker stays at 0 with probability r ∈ (0,1), moves to 1 with probability (1 − r)p and to a− 1 with probability (1 − r)(1 − p). The other transition probabilities are unchanged. Clearly now the chain is aperiodic for any a, but the transition matrix is no longer doubly stochastic. What happens is the invariant distribution?

The walker spends a longer time at 0; if we stop the time while she transitions from 0 to 0 the chain is the same as before, and spends equal proportion of time in all states. It follows that our perturbed chain spends the same proportion of time in all states except 0, where it spends a Geometric(1 − r) time at every visit. Therefore π₀ is larger by the factor  than other π_i. The row vector with invariant distributions thus is 

Thus we can still determine invariant distribution if only self-transitions P_ii are changed.