11 4markow

Markov Chains

.

Markov chains are a discrete probability distribution where each outcome is conditional (dependent) only on the outcome of the experiment immediately before it.

.

We will only consider two state Markov chains. Two state Markov chains have two possible outcomes (2 states) at each experiment.

.

NOTE: In a two state Markov chain, the outcomes are not independent, so this is not a binomial distribution.

.

To understand a Markov chain, use a tree diagram:

.

Example 1

A school has 200 students.

Records show that 70% of the students who are absent on a particular day will be absent on the following day as well.

Also, 10% of the students who are present will be absent on the following day.

On a particular day (day 1), 20 students are absent.

a) .. Find the expected number of students absent day 2

b) .. Find the probability that a random students is present on day 2

c) .. Find the expected number of students absent on day 3

d) .. Find the probability that a random student is present on day 3 given that they were absent on Day 1
.

Solution

Note 1: The probabilities depend only on the outcome of the day before so this is a Markov Chain.

Note 2: There are only two possible outcomes (present or absent) so this is a two state Markov Chain.
.

a) .. Find the expected number of students absent day 2
.

11.4eg1a.gif

… … … The expected number of students absent on Day 2 will be the sum of the numbers in red:
.

… … … E(Abs day2) $= PA + AA$
.

… … … … $=18 + 14$
.

… … … … $=32$ (students absent)

.

b) .. Find the probability that a random students is present on day 2
.

… … … The number of students present is:
.

… … … … $162 + 6 = 168$ students present out of 200
.

… … … Pr(Pres day2) $= \dfrac{168}{200}$
.

… … … Pr(Pres day2) $= 0.84$
.

… … … OR
.

… … … Pr(Pres day2) $= PP + AP$
.

… … … … $= 0.9 \times 0.9 + 0.1 \times 0.3$
.

… … … … $= 0.84$

.

c) .. Find the expected number of students absent on day 3
.

11.4eg1b.gif

… … … The expected number of students absent on day 3 will be the sum of the numbers in red:
.

… … … E(Abs day3) $= PPA + PAA + APA + AAA$
.

… … … … $= 16.2 + 12.6 + 0.6 + 9.8$
.

… … … … $= 39.2$
.

Notice that mostly we are usually only interested in the total number present or absent on a given day.

.

d) .. Find the probability that a random student is present on day 3 given that they were absent on Day 1
.

… … … Pr(Pres day3 | Abs day1)
.

… … … … $= \dfrac{5.4 + 4.2}{20}$
.

… … … … = 0.48
.

… … … OR
.

… … … Pr(Pres day3 | Abs day1) $= APP + AAP$
.

… … … … $= 0.3 \times 0.9 + 0.7 \times 0.3$
.

… … … … $= 0.48$

.

As you can see, repeating a Markov chain for several cycles makes the tree diagram very big
.

Fortunately, there is another way.

.

Transition Matrices

.

Markov Chains can be solved using matrices provided we are only interested in the final numbers.

.

Example 1 (repeated)

A school has 200 students.

Records show that 70% of students who are absent on a particular day will be absent the following day as well.

Also 10% of the students who are present will be absent the following day.

On a particular day (day 1), 20 students are absent.

Find the number of students present on any given day.
.

Solution:

This situation can be set out in a transition probability table:

11.4eg1tbl.gif

Note 1: The columns should represent the current state and the rows represent the next state.

Note 2: Row 1 and Column 1 should refer to the same activity. It doesn't matter which way around you do it provided you are consistent.

.

The transition probability table can then be represented as a transition matrix (T)

  • {Keep track of which row/column represents which activity}

.

… … $T = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right]$

.

The initial state $S(0)$ and the current state $S(n)$ of the system after n cycles can then be represented by a column matrix.

.

… … $S \big( 0 \big) = \left[ \begin{matrix} 20 \\ 180 \\ \end{matrix} \right] \qquad \qquad S \big( n \big) = \left[ \begin{matrix} \text{Absent after n days} \\ \text{Present after n days} \\ \end{matrix} \right]$
.

Note: In T, Absent is on the top row, so Absent must be on the top row in S as well.

.

Now, to find $S(1)$ we multiply $T \times S(0)$
.

… … $S \big( 1 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right] \, \left[ \begin{matrix} 20 \\ 180 \\ \end{matrix} \right] = \left[ \begin{matrix} 32 \\ 168 \\ \end{matrix} \right]$

.

Similarly, we can find $S(2)$ by multiplying $T \times S(1)$
.

… … $S \big( 2 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right] \, \left[ \begin{matrix} 32 \\ 168 \\ \end{matrix} \right] = \left[ \begin{matrix} 39.2 \\ 160.8 \\ \end{matrix} \right]$

.

And we can then find $S(3)$ by multiplying $T \times S(2)$
.

… … $S \big( 3 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right] \, \left[ \begin{matrix} 39.2 \\ 160.8 \\ \end{matrix} \right] = \left[ \begin{matrix} 43.52 \\ 156.48 \\ \end{matrix} \right]$

.

OR {This is easy on the calculator}

We can keep referring back to $S(0)$
.

… … $S \big( 1 \big) = T \times S \big( 0\big)$
.

… … $S \big( 2 \big) = T \times T \times S \big( 0 \big) = T^2 \times S \big( 0 \big)$
.

… … $S \big( 3 \big) = T \times T \times T \times S \big( 0 \big) = T^3 \times S \big( 0 \big)$

.

… … $S \big( 1 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right] \, \left[ \begin{matrix} 20 \\ 180 \\ \end{matrix} \right] = \left[ \begin{matrix} 32 \\ 168 \\ \end{matrix} \right]$

.

… … $S \big( 2 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right]^2 \, \left[ \begin{matrix} 20 \\ 180 \\ \end{matrix} \right] = \left[ \begin{matrix} 39.2 \\ 160.8 \\ \end{matrix} \right]$

.

… … $S \big( 3 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right]^3 \, \left[ \begin{matrix} 20 \\ 180 \\ \end{matrix} \right] = \left[ \begin{matrix} 43.52 \\ 156.48 \\ \end{matrix} \right]$

11.4calc1.gif

.

In general: $S(n) = T^n \times S(0)$

.

Steady State of a Markov Chain

.

By collecting the numbers present and absent over a sequence of days, we can see that the values are slowly converging on a specific number of students present/absent each day.

11.4tbl.gif

.

When they reach that number, the values will remain on that number each day without changing.
.

This is called a steady state, or the long term behaviour of the system.
.

Note: This is not asymptotic behaviour. The values actually adopt the numbers they are converging to and stay there.
.

Note: For any given system, the same steady state values will be achieved regardless of the initial values.
.

To find the long term behaviour (or the steady state) using transition matrices, choose a large number for n ( n = 50 is usually sufficient) and use your calculator to find S(50)

.

… … $S(steady) = T^{50} \times S(0)$

.

Example 1 (continued)

Find the number of students present/absent on each day in the long term (ie Find the steady state for this system.)

Solution

… … $S \big( 50 \big) = \left[ \begin{matrix} 0.7 & 0.1 \\ 0.3 & 0.9 \\ \end{matrix} \right]^{50} \, \left[ \begin{matrix} 20 \\ 180 \\ \end{matrix} \right] = \left[ \begin{matrix} 50 \\ 150 \\ \end{matrix} \right]$

.

… … Hence, in the long term, there will be 50 absent and 150 present on each day.

.

Finding the Steady State without a Calculator

.

Example 1 (continued)

Find the number of students present/absent on each day in the long term

Solution

… … Let P = the number present in the steady state

… … Let A = the number absent in the steady state
.

… … Total Students = $200$,
.

… … so $P + A = 200$
.

… … so $A = 200 - P${Equation 1}

.

… … Express the rule for P(next) in terms of P and A
.

… … $P(next) = 0.9 \times P + 0.3 \times A$
.

… … but in the steady state, $P(next) = P(previous)$
.

… … so
.

… … $P = 0.9P + 0.3A${Equation 2}

.

… … {Substitute Eqn 1 into Eqn 2}
.

… … $P = 0.9P + 0.3(200 - P)$
.

… … $P = 0.9P + 60 – 0.3P$
.

… … $P = 0.6P + 60$
.

… … $0.4P = 60$
.

… … $P = 150$
.

… … {Using Eqn 1}
.

… … $A = 200 - P$
.

… … $A = 50$
.

… … So in the long term , on any given day

… … … 150 students will be present
… … … 50 students will be absent

.

Example 2

.

Commuters travelling into the centre of Trenchtown use either the bus or the train. Research shows that each month, 20% of those using the bus switch to train travel and 30% of those using the train switch to bus travel.

At the start of January, 4800 were using the bus and 3600 were using the train.

Assume the total number of commuters does not change.

Solution:

… … This situation can be set out in a transition probability table:

11.4eg2tbl.gif

.

… … This gives us a transition matrix:
.

… … $T = \left[ \begin{matrix} 0.7 & 0.2 \\ 0.3 & 0.8 \\ \end{matrix} \right]$
.

… … And the intial state and current state are given by:
.

… … $S \big( 0 \big) = \left[ \begin{matrix} 3600 \\ 4800 \\ \end{matrix} \right]$
.

… … $S \big( n \big) = \left[ \begin{matrix} \text{Train after n months} \\ \text{Bus after n months} \\ \end{matrix} \right]$
.

a) .. Find the number of people using train and bus at the beginning of May.
.

… … … Beginning of May is after 4 months
.

… … … $S \big( 4 \big) = \left[ \begin{matrix} 0.7 & 0.2 \\ 0.3 & 0.8 \\ \end{matrix} \right]^{4} \, \left[ \begin{matrix} 3600 \\ 4800 \\ \end{matrix} \right] = \left[ \begin{matrix} 3375 \\ 5025 \\ \end{matrix} \right]$
.

… … … Hence, at the beginning of May,

… … … … 3375 will use the train
… … … … 5025 will use the bus.

.

b) .. Find the number of people using train and bus in the long term.
.

… … … $S \big( 50 \big) = \left[ \begin{matrix} 0.7 & 0.2 \\ 0.3 & 0.8 \\ \end{matrix} \right]^{50} \, \left[ \begin{matrix} 3600 \\ 4800 \\ \end{matrix} \right] = \left[ \begin{matrix} 3360 \\ 5040 \\ \end{matrix} \right]$

11.4calc2.gif

.

… … … Hence, in the long term,

… … … … 3360 will use the train
… … … … 5040 will use the bus.
.

c) .. Find steady state for this system without a calculator.
.

… … … Use

… … … … T = number on Train
… … … … B = number of Bus

… … … Total $= 8400$

…. … … $B = 8400 - T$ …. {1}
.

… … … Express the rule for T(next) in terms of T and B:
.

… … … $T(next) = 0.7T + 0.2B$
.

… … … In the long term, $T(next) = T$
.

… … … $T = 0.7T + 0.2B$ ….. {sub 1}
.

… … … $T = 0.7T + 0.2(8400 - T)$
.

… … … $T = 0.7T + 1680 - 0.2T$
.

… … … $T = 0.5T + 1680$
.

… … … $0.5T = 1680$
.

… … … $T = 3360$
.

… … … $B = 8400 - T$ ….. {1}
.

… … … $B = 5040$
.

… … … Hence, in the long term,

… … … … 3360 would use the train
… … … … 5040 would use the bus.

NOTE: There is an assumption built into the idea of Markov Chains that the total population stays constant.

.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License