Math 413                                   Markov Chains(1)                      Winter 2002

                                                

 

 is a Stochastic Process.  

The process is in state i at time n if .

Unless otherwise mentioned, .

Whenever the process is in state i, there is a fixed probability  that it will next be in state j. 

 

Let P be the matrix of one-step transition probabilities  then

 

P =

    

                    

, where      for all i.

 

 

Markov Chain: is a STOCHASTIC process such that the conditional distribution of any 

                           future state is independent of the past states and depends ONLY on the 

                           present state. That is,  

                                                                   

                                                     

 

 

 

1. Suppose that the chance of rain tomorrow depends on previous weather conditions only through whether or not it is raining today and not on past weather conditions. Suppose also that if it rains today, then it will rain tomorrow with probability a; and if it does not rain today, then it will rain tomorrow with probability b.

If we say that the process is in state 0 when it rains and state 1 when it does not rain, then the above is a two-state Markov chain. Express its matrix of transition probabilities.

 

 

 

 

2. A communications system transmits the digits 0 and 1. Each digit transmitted must pass through several stages, at each of which there is a probability p that the digit entered will be unchanged when it leaves. Letting denote the digit entering the nth stage, thenis a two-state Markov chain. Express its matrix of transition probabilities.

 

 

 

 

 

 

 

 

3. On a given day, Gary is either cheerful (C), so-so (S), or glum (G). If he is cheerful today, then he will be C, S, or G tomorrow with respective probabilities 0.5, 0.4, 0.1. If he is feeling so-so today, then he will be C, S, or G tomorrow with probabilities 0.3, 0.4, 0.3. If he is glum today, then he will be C, S, or G tomorrow with probabilities 0.2, 0.3, 0.5. 

Letting denote Gary’s mood on the n-th day, then is a three-state Markov chain (state 0 = C, state 1 = S, state 2 = G). Express its matrix of transition probabilities.

 

 

 

 

 

 

 

 

 

 

4. A Markov chain whose state space is given by integers i = 0, ±1, ±2, … is called a random walk if, for some number 0 < p < 1,

 

, ,   i = 0, ±1, ±2, … 

 

Remark: We may consider a random walk as a model for a person walking on a straight

                line who at each point of time either takes one step to the right with probability

                p or one step to the left with probability 1-p.

 

 

 

 

 

 

5. Consider a gambler who, at each play of the game, either wins $1 with probability p or loses $1 with probability 1-p.

If we suppose that our gambler quits playing either when he goes broke or he attains a fortune of $N, then the gambler’s fortune is a Markov chain having transition probabilities

 

, , i = 0, ±1, ±2, … 

 

States 0 and N are called absorbing states since once entered they are never left.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Math 413                                             Markov Chains(2)                         Winter 2002

 

                                                Chapman-Kolmogorov Equations

 

We define the

 n-step transition probabilities :  n ³ 0,  i, j ³ 0

 

= P( a process in state i will be in state j after n additional transitions)

= P

 

Chapman-Kolmogorov Equations:       for all n, m ³ 0, all i, j

 

 

 

 

 

 

 

Remark: The above C-K equations provide a method for computing n-step transition 

               probabilities .

 

 

Let P (n) be the matrix of n-step transition probabilities , then Chapman-Kolmogorov Equations give us:

 

                                P (n+m) = P (n) ×P (m)

 

 

As a result, P (n) = P (n-1)×P (1) = P×P×P×P×××P = P n

 

 

 

 

1. If the one-step transition probability matrix is given by P = , find P (4) and .

 

 

 

 

 

2. Given the transition probability matrix with states 0 and 1

    P = , find

a)      the probability that it will be in state 1 after 4 transition given that it is in state 0 now.

 

 

 

 

b)      P() if P() = 0.4 and P() = 0.6.

 

 

 

 

 

Remark:  are conditional probabilities. It is necessary to specify the probability distribution of the initial state in order to obtain the unconditional probability distribution of the state at time, say n.

 

3.

State 0   if it rained both today and yesterday

State 1   if it rained today but not yesterday

State 2   if it rained yesterday but not today

State 3   if it did not rain either yesterday or today        

 

Basing on a four-state Markov Chain having the following transition probability matrix

 

P = , given that it rained on Monday and Tuesday, what is the probability that it will rain on Thursday?

 

 

 

 

 

 

 

 

 

 

 

 

Math 413                                             Markov Chains(3)                         Winter 2002

 

 

                                                         Classification of States

 

 

The state j is accessible from state i if and only if, starting in i, it is possible that the process will ever enter state j. That is>0 for some n ³ 0.

 

Two states i and j are said to communicate if they are accessible to each other.

 

We write

                       i  j

Three properties for communication:

 

1.      State i communicates with state i, all i ³ 0.

2.      If state i communicates with state j, then state j communicate with state i.

3.      If state i communicates with state i, and state j communicates with state k, then state i communicates with state k.

 

 

 

 

 

 

 

 

 

 

 

 

 

Class: Two states that communicate are said to be in the same class.

 

Any two classes of states are either identical or disjoint. (why?)

Communication divides the state space up into a number of  separate classes.

 

Irreducible: The Markov chain is said to be irreducible if there is only one class. (All states communicate with each other.)

 

 

 

 

 

 

 

1.

 

Is this Markov chain irreducible? Verify.

 

 

 

 

 

 

 

 

 

2.

 

 

Is this Markov chain irreducible? Verify.

 

 

 

 

 

 

 

 

 

Recurrent

 

State i is said to be recurrent if =1 ( is the probability that, starting in state i, the process will ever reenter state i.)

 

 

 

 

 

 

 

Transient

 

State i is said to be transient if <1.

 

 

 

Propositions:

1.      State i is recurrent if .

2.      State i is transient if .

3.      If state i is recurrent, and state j communicates with state i, then state j is recurrent.

 

4.      If state i is transient and communicates with state j, then state j is transient.

 

5.      All states of a finite irreducible Markov chain are recurrent.

 

 

1. Determine which states are transient and which are recurrent.

 

 

 

 

 

 

 

2. Determine which states are transient and which are recurrent.

 

 

3. For a random walk,

, i = 0, ±1, ±2, … 

Which states are recurrent?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Compute the probability of whether the one-dimensional random walk ever returns to state 0 when p¹1/2.

 

 

 

 

 

 

 

 

 

5. Consider a communications facility in which the numbers of messages arriving during each of the time periods n = 1, 2, … are independent and identically distributed random variables. Let and suppose that Each arriving message will transmit at the end of the period in which it arrives. If exactly one message is transmitted, then the transmission is successful and the message leaves the system. However, if at any time two or more messages simultaneously transmit, then a collision is deemed to occur and these messages remain in the system. Once a message is involved in a collision it will, independently of all else, transmit at the end of each additional period with probability p (--called Aloha protocol)

 

Such a system is asymptotically unstable in the sense that the number of successful transmissions will, with PROBABILITY 1, be FINITE.

 

 

 

 

 

Math 413                                             Markov Chains(4)                         Winter 2002

 

                                                         Limiting Probabilities

 

In some cases, is converging to some value as . The value is the same for all i.

That is, all the rows of the matrix are the same as .

This is the limiting probability that he process will be in state j after a large number of transitions, and the probability is independent of the initial state i.

 

 

Period

 

State i is said to have period d if  whenever n is not divisible by d, and d is the largest integer with this property.

 

Periodicity is a class property. If state I has period d, and states i and j communicate, then state j also has period d.

 

Aperiodic

 

A state with period 1 is said to be aperiodic.

 

 

Positive Recurrent

 

State i is said to be positive recurrent if it is recurrent and if, starting in i, the expected time until the process returns to state i is finite.   

 

In a finite-state Markov chain all recurrent states are positive recurrent.

 

 

 

Ergodic

 

Positive recurrent, aperiodic states are called ergodic.

 

Theorem

 

For an irreducible ergodic Markov chain exists and is independent of i.

Furthermore, letting   , then

 

 is the unique solution of

 

 

 

Remark 1:

 

The long run proportions , are called stationary probabilities. If the initial state is chosen according to the probabilities , then the probability of being in state j at any time n is equal to .

 

In other words, if         then for all n, j 0.

 

 

Remark 2:

 

Let be the expected number of transitions until a Markov chain starting in state j, returns to that state.

 

It follows that             (on average, the process will spend 1 unit of time in state j for every  units of time.)

 

 

1. In Ellensburg, if it rains today, then it will rain tomorrow with probability a; and if it does not rain today, then it will rain tomorrow with probability b. If we say that the state is 0 when it  rains and 1 when it does not rain, then

(a)    find and .

(b)   find the limiting probability of rain when a=0.7 and b=0.4.

 

 

 

 

 

 

 

 

 

 

 

2. Suppose the mood of an individual is considered as a three-state Markov chain having a transition probability matrix

 

P = .

 

In the long run, what proportion of time is the process in each of the three states?

 

 

 

 

 

 

 

 

 

3. A problem of interest to sociologists is to determine the proportion of society that has an upper- or lower-class occupation. One possible mathematical model would be to assume that transitions between social classes of the successive generations in a family can be regarded as transitions of a Markov chain. That is, we assume that the occupation of a child depends only on his or her parent’s occupation. Let us suppose that such a model is appropriate and that the transition probability matrix is given by

 

P = .

 

That is, the child of a middle-class worker will attain an upper-, middle, or lower-class occupation with respective probabilities 0.05, 0.70, 0.25.

In the long run, what percent of people are in upper-class jobs? Middle-class jobs? Lower-class jobs?

 

 

 

 

 

 

 

 

 

 

 

 

4. Suppose that the Coca Cola production process changes states in accordance with a Markov chain having the following transition probability matrix.

 

Suppose that the acceptable states are 0, 1 (up) and the unacceptable states are 2, 3 (down). Determine

a)      the rate at which the production process goes from up to down.

b)      The average length of time the process remains down when it goes down.

c)      The average length of time the process remains up when it goes up

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Math 413                                             Markov Chains(5)                         Winter 2002

 

The Gambler’s Ruin Problem

 

1. Suppose that Sean plays a game and at each play of the game he has probability p of winning one dollar and probability 1-p of losing one dollar. Assuming that successive plays of the game are independent and Sean will stop playing if he lost all his money or his fortune reaches $7 , what is the probability that, starting with 2 dollars, Sean’s fortune will reach 7 dollars before reaching 0?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Suppose that Jon and Rocklyn decide to flip pennies; the one coming closest to the wall wins. Jon, being the better player, has a probability of 0.6 of winning on each flip.

a)      If Jon starts with 5 pennies and Rocklyn with 10, then what is the probability that Jon will wipe Rocklyn out?

b)      What if Jon starts with 10 and Rocklyn with 20? 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Continued from the first problem, supposed that Sean will win each play with probability 0.4 and he will quit if he lost all the money or reach $7.

a)      find the expected amount of time Sean has 5 dollars.

b)      find the expected amount of time Sean has 2 dollars.