315-Lec11 - Lecture notes 11 PDF

Preview

Summary

fall 2015 lecture notes...

Description

IEMS 315: Stochastic Models and Simulation Fall 2015, Prof. Ohad Perry

Lecture 11 Page 1 of 5

Lecture 11: Stationarity and Limiting Probabilities As usual, we let Pi,j denote the one-step probabilities of a Markov chain on a state space E, and P denote the transition matrix. Stationary Distribution. A probability vector π = (π 1 , π 2 , . . . ) is a stationary probability vector (or a “stationary distribution”) of the Markov chain if X πj = π i Pi,j for all j ∈ E. i∈E

In matrix form π = πP,

(1)

with π being a row vector of the appropriate dimension (possibly infinite, if the state space E is infinite). Recall that P(X1 = j) =

X

αi Pi,j

and P(Xn = j) =

i∈E

X

n , αi P i,j

i∈E

where α = (α1 , α2 , . . . ) is the vector of initial probabilities. Now assume that there exists a stationary probability vector π and that we take the initial distribution to be that vector, i.e., we take α = π, so that X0 ∼ π. In particular, P(X0 = j) = π j for all j ∈ E. Then X P(X1 = j) = π i Pi,j = π j for all j ∈ E, i∈E

where the second equality follows from the definition of the stationary distribution. Therefore, P(X1 = j) = P(X0 = j) for all j ∈ E, so that X1 ∼ π. By exactly the same simple calculation we get that X2 ∼ π and, by induction, Xn ∼ π for all n ≥ 0: P(Xn = j) = π j

for all

n ≥ 0 and j ∈ E.

The probability distribution of the chain does not change with time; it is stationary. It is important to realize that when we say that the chain is stationary, we do not mean that it doesn’t move, but that its probability distribution doesn’t change with time (the chain itself keeps moving according to its transition probabilities). Another term which is often used is steady state: The stationary distribution is also called the “steady-state distribution” of the Markov chain, and the chain is said to be “in steady state”, if it is distributed according to π. I will use the terms “steady state” and “stationarity” interchangeably. There can exist a unique stationary distribution for a Markov chain, but there can also be more than one or none at all. If we know that there exists a unique steady state, then one hopes to have the Markov chain converge to this unique steady state as time increases, i.e., to have n = πj lim Pi,j

n→∞

as n → ∞,

2

IEMS 315, Lecture 11

regardless of the initial state i. The question is what conditions ensure that such convergence holds. To summarize the above, we are looking for two things: 1. Conditions ensuring the existence of a unique stationary distribution. 2. Conditions ensuring the convergence (as time grows) of the Markov chain to stationarity. The following theorem is a version of Theorem 4.1 in pg. 215 in the book, connecting the stationary n distribution to the limiting probabilities Pi,j as n → ∞. However, here the theorem is stated for finite state-space Markov chains because extra conditions are needed for the infinite state-space case. (We discuss this case later.) Theorem 1. For an irreducible Markov chain on a finite state-space E there exists a unique stationary distribution π . If, in addition, the chain is aperiodic, then the limits limn→∞ Pi,jn exist for all i, j ∈ E and are independent of i, and for all i ∈ E , n = πj , lim Pi,j

n→∞

j ∈ E.

Remark 1. By Theorem 1, if the chain is irreducible and finite, then we can find the stationary distribution by solving (1). If the chain is also aperiodic, then the solution π to (1) is also the limiting P probabilities. However, we must make sure that the solution π is a probability vector, i.e., that i∈E π i = 1 (positivity of π always holds). When we solve the system of linear equations in (1) we find that one of the equations is redundant. Therefore, if there exists a solution, then there are infinitely many solutions. However, since π must be a probability vector, to find the (unique) stationary distribution, we solve π = πP X

π i = 1.

(2)

i∈E

The trick in solving (2) is to remember that one of the linear equations in π = πP is redundant. We then get rid of the equation that P seems the most difficult to handle. Of course, we must always have the normalization equation i π i = 1 to ensure that the solution is a probability vector. Since the limits in Theorem 1 are independent of the initial state i (and of the initial distribution α), we have π i = lim P(Xn = i), i ∈ E. n→∞

It can also be shown that the long-run proportion of time that the process spends in state i is also equal to π i : n 1X 1(Xk = i) → π i , as n → ∞, n k=1

where 1(Xk = i) is the indicator function which is equal to q if Xk = i and equals 0 otherwise. That is, a version of the SLLN holds for DTMC’s that satisfy the conditions of Theorem 1. Remark 2. It follows from Theorem 1 that the sequence of transition matrices {Pn : n ≥ 1} converges to a matrix with all rows equal to π as n → ∞. That is so, because the components of

IEMS 315, Lecture 11

3

n , and for each i, Pi,jn converges to π j . For example, if the state space has m states, we Pn are Pi,j get in the limit a matrix of the form   π1 π2 π3 · · · πm π π π · · · π  m  1 2 3  .. . .. . . ..  . . . .  . . π1 π2 π3 · · · πm

See also the example in the beginning of Section 4.4, pg. 214 in the book. Remark 3. It is important to remember that a stationary distribution can exist even if there exists no limiting distribution. For instance, in the Markov-fly example from the previous lecture, the limit Pn does not exist as n → ∞ because the chain is periodic. However, one can check that there exists a unique solution π to the system of equations (2), which is thus the vector of stationary distribution. The aperiodicity condition in the statement of Theorem 1 is needed to ensure that the limiting probabilities exist and converge to the unique stationary distribution. Example (4.21) in Ross: For a Markov chain with state space {0, 1, 2} transition matrix   0.5 0.4 0.1 P =  0.3 0.4 0.3  0.2 0.3 0.5 find the long-run proportion of time that the chain spends in each state. Solution: Since the state space is finite, and the chain is irreducible and aperiodic, the long-run proportion of time that the chain spends in each state is the stationary probability of being in each state. We thus solve (2): π 0 = 0.5π 0 + 0.3π 1 + 0.2π 2 , π 1 = 0.4π 0 + 0.4π 1 + 0.3π 2 , π 2 = 0.1π 0 + 0.3π 1 + 0.5π 2 , π 0 + π 1 + π 2 = 1, solving this system of equation yields the result π = (π 0 , π 1 , π 2 ) = (21/62, 23/62, 18/62).

The infinite State-Space Case An analogous theorem to Theorem 1 for Markov chains on infinite state spaces requires extra conditions. We start by discussing what is different in infinite state spaces. We next show why irreducibility in the infinite state-space case is not a sufficient condition for the existence of a stationary distribution.

4

IEMS 315, Lecture 11

Transience and Recurrence on Infinite State Spaces Recall that in a finite state-space not all states can be transient. Moreover, if the chain is irreducible, then all states are recurrent. However, for chains on an infinite state space, situations in which all states are transient do exist. Example - Random Walk on the integers. Let {Sn : n ≥ 0} denote the position of a stochastic process on Z := {. . . , −2, −1, 0, 1, 2 . . . }, which at any time moves one unit up with probability p, or one unit down, with probability 1 − p. Then Sn is a Markov chain which we called a “random walk on the integers” (see Lecture 8), with transition probabilities Pi,i+1 = p

and Pi,i−1 = 1 − p,

0 < p < 1,

i ∈ Z.

A random walk is clearly an irreducible Markov chain, so that all states are either transient or recurrent. It is thus sufficient to check whether state 0 is transient or recurrent (since all states are in the same class). To that end, consider a random walk initialized at state 0. We will show that the random walk must eventually drift away from state 0, never to return to that state again. Observe that a random walk can be represented as a sum of r.v’s in the following way: Let {Yn : n ≥ 0} denote IID r.v.’s with P(Yn = 1) = p and P(Yn = −1) = 1 − p. Then Sn :=

n X

Yi ,

n ≥ 1,

i=1

S0 = 0. Since Sn is a sum of IID r.v.’s, we can apply the strong-law of large numbers (SLLN) to obtain Sn /n → E[Y1 ] w.p.1 as n → ∞,

where E[Y1 ] = p − (1 − p) = 2p − 1.

If p < 1/2, then E[Y1 ] < 0, which imply that Sn → −∞ w.p.1 as n → ∞. If p > 1/2, then E[Y1 ] > 0, which imply that Sn → +∞ w.p.1 as n → ∞. In both these cases, we see that the process eventually drifts arbitrarily far from state 0 (or any other state), so that state 0 is transient. Since transience is a class property, irreducibility implies that all the states are necessarily transient. It can be shown that when p = 1/2, state 0, and thus all other states, is recurrent. (A random walk with p = 1/2 is called a symmetric random walk.) The proof of that fact is simple, and uses Stirling’s formula; see Example 4.18 in pg. 208 of the book. The main message of the above is that a DTMC on an infinite state space can have all its states be transient, so that irreducibility does not ensure the existence of stationary probabilities. In particular, the statement of Theorem 1 does not generalize immediately to the infinite state space case; more conditions (in addition to irreducibility and aperiodicity) are needed.

IEMS 315, Lecture 11

5

summary of the lecture 1. A Markov chain is stationary if its probability law does not change with time, i.e., if there exists a probability vector π satisfying π = πP. 2. A unique stationary distribution exists for a finitePstate space DTMC that is irreducible. It can be found by solving (2). (We add the equation i π i = 1 to the system of linear equations π = πP.) If, in addition, the chain is aperiodic, then the limiting probabilities exist and coincide with the stationary probabilities: For every j ∈ E , n → πj Pi,j

as n → ∞ independent of i.

The stationary probability π j is also the long-run proportion of time that the processes spends in state j . 3. For a Markov chain on an infinite state space it is possible that all the states are transient, as in the random walk example when 0 < p < 1 and p 6= 1/2. We will therefore need to work harder to ensure that a unique stationary distribution exists for such chains....