Wize University Linear Algebra Textbook > Eigenvalues and Eigenvectors (Spectral Theory)

Markov Chains (Random Walks)

Markov Chains

A Markov matrix is a square matrix whose columns are numbers in $\left[0,1\right]$ which sum to 1.

This is also known as a transition matrix, a stochastic matrix, or a migration matrix.

Examples

Markov matrix

$A = \left[ \begin{array}{ccc} 1/3 & 0 & 1\\ 1/3 & 1/4 & 0\\ 1/3 & 3/4 & 0\\ \end{array} \right]$

Not a Markov matrix

$B= \left[ \begin{array}{cc} -1 & 0\\ 2 & 1/2 \end{array} \right]$

First column: contains numbers that are not between 0 and 1.
Second column: the sum of the entries is not 1.

Interpretation

The entries in a Markov matrix represent proportions or probabilities.

For example, entry $a_{ij}$ of a migration matrix is the proportion of the population moving from location $j$ to location $i$ .

Example

$\begin{array}{rrc} && \textbf{From}\\ && \text{loc 1} \quad\quad \text{loc 2}\\[0.8em] \textbf{To} & \begin{array}{r} \text{loc 1}\\[0.5em] \text{loc 2} \end{array} & \left[ \begin{array}{rr} \quad 1/4 \quad & \quad 1 \quad\\[0.5em] \quad 3/4 \quad & \quad 0 \quad \end{array} \right] \end{array}$

$1/4$ of the population in location 1 stays in location 1
$3/4$ of the population in location 1 moves to location 2
All of the population in location 2 moves to location 1
None of the population in location 2 stays in location 2

Markov Chain Equation

The state vector at time $n$ is given by:

$\vec x_n= \begin{bmatrix} x_{\colorTwo{ 1} n}\\ \vdots\\ x_{\colorTwo{ m} n} \end{bmatrix} \begin{array}{l} \leftarrow \text{amount at \textbf{location }} \bm{\colorTwo {1}} \text{ at time } n\\ \\ \leftarrow \text{amount at \textbf{location }} \bm{\colorTwo {m}} \text{ at time } n\\ \end{array}$

If $A$ is a Markov matrix, we can determine the next state vector by computing:

\boxed{\quad \vec{x}_{n+1}=A \vec{x}_n \quad}

Steady State

If $A$ is a Markov matrix, then there exists a steady state vector $\vec x_s$ such that $\vec x_s=A\vec x_s$ .

As $\bm {\colorTwo n}$ increases, the state vectors $\vec x_{\colorTwo{\bm{ n}}}$ approach the steady state $\vec x_{\bm s}$ :

$\vec x_0 \quad \longrightarrow \quad \underbrace{\vec x_1}_{\normalsize A\vec x_0} \quad \longrightarrow \quad \underbrace{\vec x_2}_{\normalsize A\vec x_1} \quad \longrightarrow \quad \dots \quad \longrightarrow \quad \underbrace{\vec x_n}_{\normalsize A\vec x_{n-1}} \quad \longrightarrow \quad \dots \quad \longrightarrow \quad \underbrace{\vec x_s}_{\normalsize A\vec x_{s}}$

Finding the Steady State Vector

$\vec x_s$ can be found by solving:

$\boxed{\quad (I−A)\vec x_s= \vec0 \quad}$

We can solve this homogeneous equation using Gauss-Jordan elimination (just like with eigenvectors!)

Example: Markov Chains

Consider the migration matrix $A=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}$ .

Suppose there are initially:

180 residents in location 1
180 residents in location 2
180 residents in location 3

Part A)

Find the population of each location after 1 and 2 units of time.

$X_1=AX_0=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}\begin{bmatrix}180\\180\\180\end{bmatrix}=\begin{bmatrix}150\\210\\180\end{bmatrix}$

Therefore, after one time period, location 1 has 150 residents, location 2 has 210 residents, and location 3 has 180 residents.

$X_2=AX_1=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}\begin{bmatrix}150\\210\\180\end{bmatrix}=\begin{bmatrix}140\\205\\195\end{bmatrix}$

Therefore, after two time periods, location 1 has 140 residents, location 2 has 205 residents, and location 3 has 195 residents.

Part B)

Find the population of each location after a very long time.

We must find a solution to $(I-A)X_s = 0$ , so we will reduce the augmented matrix:

$\begin{aligned} &\left[\begin{array}{rrr} 2/3&0&-1/2\\ -2/3&1/2&0\\ 0&-1/2&1/2 \end{array}\right]\\[2em] \underrightarrow{R_2+R_1\to R_2} &\left[\begin{array}{rrr} \ \ \ 2/3&0&-1/2\\ 0&1/2&-1/2\\ 0&-1/2&1/2 \end{array}\right]\\[2em] \underrightarrow{R_3+R_2\to R_3} &\left[\begin{array}{rrr} \ \ \ 2/3&0&-1/2\\ 0&\ \ \ 1/2&-1/2\\ 0&0&0 \end{array}\right]\\[2em] \xrightarrow[\normalsize 2R_2 \to R_2]{\normalsize \frac{3}{2}R_1\to R_1} &\left[\begin{array}{rrr} \ \ \ \ \ \ \ 1&\ \ \ \ \ \ \ 0&-3/4\\ 0&1&-1\\ 0&0&0 \end{array}\right] \end{aligned}$

Solving for when this system equals the zero vector, we obtain a general solution $\vec x_s = t\begin{bmatrix}3/4\\1\\1\end{bmatrix}$ .

Now we must find a value of $t$ such that this vector has the same sum as $\vec x_0$ (and every state vector).

$\begin{aligned} t\left(\frac{3}{4}+1+1\right)&=180+180+180=540\\[1em] \frac{11}{4}t &= 540\\[1em] t &= \frac{2160}{11} \end{aligned}$

Therefore, the population in the long run is:

$\vec x_s = \dfrac{2160}{11}\begin{bmatrix}3/4\\1\\1\end{bmatrix}=\begin{bmatrix}1620/11\\2160/11\\2160/11\end{bmatrix}\approx\begin{bmatrix}147\\196\\196\end{bmatrix}$

Practice: Markov Chains

Consider the following three temperature scenarios:

If it is hot today, it will not be hot tomorrow, and there is a 50% it will be mild tomorrow.
If it is mild today, there is a 2/3 chance it will be hot tomorrow, and a 1/3 chance it will be cold tomorrow.
If it is cold today, there is a 50% chance it will be hot tomorrow, and it will certainly not be mild tomorrow.

If today is Thursday and it is cold, what temperature scenario is most likely to occur on Saturday? What is its probability?

Most likely temperature scenario on Saturday (hot, mild, or cold):Probability (answer as a fraction):

I don't know

Extra Practice

Consider a random walk with three states that has transition:

P=\begin{bmatrix} 8/10 &3/10 &1/10\\ 2/10& 3/10& 7/10\\ 0& 4/10& 2/10 \end{bmatrix}

a) If the walker is equally likely to start in each of the three states, what is the chance

Consider a random walk with three states that has transition:

P=\begin{bmatrix} 8/10 &3/10 &1/10\\ 2/10& 3/10& 7/10\\ 0& 4/10& 2/10 \end{bmatrix}

a) If the walker is equally likely to start in each of the three states, what is the chance

Limiting matrix

For an absorbing Markov Chain $P$ , the powers $P^2,\ P^3,\ P^4,...$ get closer and closer to a limiting matrix $\overline P$ . To find the limiting matrix, first put the transition matrix into standard form by relabeling the states so that the absorbing states come first. The transition matrix then has an identity matrix in the top left and a matrix $Q$ in the bottom right such that $I-Q$ is invertible. The inverse $F = (I-Q)^{-1}$ is called the fundamental matrix for $P$ and is used to construct the limiting matrix.

P= \left[ \begin{array}{c|c} I & \mathbf{0} \\ \hline R &Q \\ \end{array} \right] \text{ standard form transition matrix}

F = (I-Q)^{-1} \text{ fundamental matrix}

Markov Chains

Practice: Markov Chains

Consider the following three temperature scenarios:

If it is hot today, it will not be hot tomorrow, and there is a 50% it will be mild tomorrow.

Markov Chains Example With 3 Outcomes

On any given night, I might go to a pub, go to the club, or stay home.

If I go out one night, there's a 1/2 chance I'll stay home the next night, and a 1/4 chance I'll go to the same sort of establishment the next night.

If I stay home one night, there's a 1/2 chance I'll stay home the next night, a 1/4 chance I'll go to the pub the next night, and a 1/4 chance I'll go to a club.

Markov Chains Example With 3 Outcomes

Consider Romeo, a single guy, who wishes to date one of two different women, Juliet a pretty tall girl, and Erica, a short girl with beautiful eyes. Romeo has long days sword fighting with his friends. Coming home tired he decides to roll a die. If it shows an even number, he will go knock on Juliet's door and asks her on a date. If it shows a "1" he will stay home and do nothing. Otherwise, he will go ask Erica for a date. In the meantime, Erica is staying making herself pretty in front of a mirror. Juliet is indifferent between going to see Romeo, hang out with Erica or stay home.

Write the transition matrix for the Markov Chain that computes the probabilities of each person going to a place or staying home each day.

Can the following matrix be the transition matrix of a Markov Chain?

\begin{bmatrix} 1 & 1 \\ .2 & .8 \\ \end{bmatrix}

The office printer is kind of unreliable:

If it jams printing a page, then there is a 40% chance it will jam printing the next page.
If it prints a page without jamming, then there is a 90% chance it will print the next page without jamming

Practice Question: Linear Dynamical Systems

An old printer has the following behavior:

If it jams printing a page, then there is a 40% chance it will jam printing the next page.
If it prints a page without jamming, then there is a 90% chance it will print the next page without jamming

A gambler starts with a fortune of $2. At each play, he has a 0.3 probability of winning; he either wins $2 or loses $2.

If he makes it to $6, he will stop and call it a win. If he runs out of money, he will stop and call it a loss.

Find the probability that he will win.

Concept Clarier

$\text{Is the transition matrix}P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ .1 & .6 &.3 \\ \end{bmatrix}\ regular?$

Here is the transition matrix of an absorbing Markov chain.

\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ .3 & .2 & 0 & .5 \\ 0 & 0 & .4 & .6 \\ \end{bmatrix}

Assuming the system starts out in State 3, what is the probability that it is eventually absorbed into State 2?

The transition matrix of a certain 3-state Markov chain is

R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}

Given that the initial state of the system is $S_0 = \begin{bmatrix} .2 & .8 & 0 \end{bmatrix}$

Is the following transition matrix P regular?

P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ .1 & .6 &.3 \end{bmatrix}

Concept Clarifier

Student loans have me in a jam, and I'm stuck using second-rate equipment

in most facets of life. My printer, for example, has the following behavior.

If it jams printing a page, then there is a 40% chance it will jam printing the next page.

Assume for simplicity that every serve in a game of tennis is of one of the following types.

\text{Legal Serve (L)},\ \text{First Fault (F1)} ,\ \text{Second Fault (F2)}

After making a First Fault, the server is more careful, so the chance that their next serve is Legal is 0.9. Otherwise, they are less careful, so the chance that their next serve is Legal is only 0.8.

Determine which of the following transition matrices are regular.

P = \begin{bmatrix} 0.5 & 0.5 \\ 1 & 0 \\ \end{bmatrix} ,\ Q= \begin{bmatrix} 0 & 0 & 1 \\ .4 & .1 & .5 \\ 1 & 0 & 0 \\ \end{bmatrix} ,\ R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}

Suppose $X_n$ is the state vector at period $n$ , and $A$ is a (left) Markov matrix so that $X_{n+1}=AX_n$ . Which of the following matrices is a possible matrix for $A$ ?

Consider the migration matrix

$A=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}$

Suppose there are initially 180 residents in location 1, 180 in location 2, and 180 in location 3.

On any given day this autumn, if it rains today then there is a 0.6 probability that it will rain tomorrow. If it doesn't rain today, there is a 0.3 probability that it will rain tomorrow. If it rains on Sunday, what is the probability that it will rain on Wednesday?

Determine which of the following transition matrices are regular.

P = \begin{bmatrix} 0.5 & 0.5 \\ 1 & 0 \\ \end{bmatrix} ,\ Q= \begin{bmatrix} 0 & 0 & 1 \\ .4 & .1 & .5 \\ 1 & 0 & 0 \\ \end{bmatrix} ,\ R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}

Assume for simplicity that every serve in a game of tennis is of one of the following types.

\text{Legal Serve (L)},\ \text{First Fault (F1)} ,\ \text{Second Fault (F2)}

Given the absorbing transition matrix T below, find the probability that the Markov process will be absorbed into state B assuming that it begins in state D.

Find the value of the first element and of the second element in the distribution vector X2 for stage 2 of a Markov Chain, when the initial distribution vector and transition matrix are:

Concept Clarifier

For each of the following transition matrices:

Draw a transition diagram.
Identify any absorbing states.

Given the absorbing transition matrix T below, find the probability that the Markov process will be absorbed into state B assuming that it begins in state D.

\begin{array}{rc} & \begin{array}{ccccc} A\ \ &\ B\ \ \ &\ C\ &\ \ \ D\ &\ \ E \end{array}\\ T=\begin{array}{c} A\\B\\C\\D\\E\end{array} & \begin{bmatrix} 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&0&0.67&0.33\\ 0.25&0&0.75&0&0\\ 0&0.75&0.25&0&0 \end{bmatrix} \end{array}

Use

Students study for their exams in three libraries at Oxford College. The university has 3 libraries, which are Sylvan (S), Main (M), and Thode (T). When students study at Sylvan, they have a 40% chance of studying at Main library the next day, but they never go to Thode the next day. When students study at Main library, they have a 50% chance of studying at each of the other two libraries the next day. Students that study at Thode tend to study at the same library the next day.

a) Draw a transition diagram for this Markov Chain.

b) Write the transition matrix for the diagram in (a)

Markov Chains (Random Walks)

Create a free account to get started

Markov Chains

Interpretation

Markov Chain Equation

Steady State

Create a free account to get started

Example: Markov Chains

Part A)

Part B)

Practice: Markov Chains

Create a free account to get started

Extra Practice

Practice: Markov Chains