High School
SAT
ACT
University
MCAT
LSAT
DAT

Concept Clari fier

Related Topics

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

Markov Chains (Random Walks)

3 Activities

checklist
Mark Yourself Question
  1. Grab a piece of paper and try this problem yourself.
  2. When you're done, check the "I have answered this question" box below.
  3. View the solution and report whether you got it right or wrong.
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.
  • If it prints a page without jamming, then there is a 90% chance it will print the next page without jamming
(a) Write down a transition diagram and a transition matrix for this scenario.

(b) What is the probability that it jams printing the third page?
(Assume the probability of first page being jammed is 10%)

c) Given that the printer doesn't jam the first page, what is the probability that it will jam the 3rd page?
More Markov Chains (Random Walks) Questions:
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)
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.
A   B    C    D   ET=ABCDE[10000010000000.670.330.2500.750000.750.2500]\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
Concept Clarifier
For each of the following transition matrices:
Draw a transition diagram.
Identify any absorbing states.
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:
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.
Assume for simplicity that every serve in a game of tennis is of one of the following types.
Legal Serve (L), First Fault (F1), Second Fault (F2)\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=[0.50.510], Q=[001.4.1.5100], R=[.1.2.7.5.3.2001]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}
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?
Consider the migration matrix
A=[1/301/22/31/2001/21/2]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.
Suppose XnX_n is the state vector at period nn, and AA is a (left) Markov matrix so that Xn+1=AXnX_{n+1}=AX_n. Which of the following matrices is a possible matrix for AA?
Determine which of the following transition matrices are regular.
P=[0.50.510], Q=[001.4.1.5100], R=[.1.2.7.5.3.2001]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.
Legal Serve (L), First Fault (F1), Second Fault (F2)\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.
Is the following transition matrix P regular?
P=[010001.1.6.3]P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ .1 & .6 &.3 \end{bmatrix}
The transition matrix of a certain 3-state Markov chain is
R=[.1.2.7.5.3.2001] R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}
Given that the initial state of the system is S0=[.2.80]S_0 = \begin{bmatrix} .2 & .8 & 0 \end{bmatrix}
Here is the transition matrix of an absorbing Markov chain.
[10000100.3.20.500.4.6] \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?
Concept Clari er
Is the transition matrixP=[010001.1.6.3] regular?\text{Is the transition matrix}P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ .1 & .6 &.3 \\ \end{bmatrix}\ regular?
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.
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
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
Can the following matrix be the transition matrix of a Markov Chain?
[11.2.8] \begin{bmatrix} 1 & 1 \\ .2 & .8 \\ \end{bmatrix}
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.
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
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.
Limiting matrix
For an absorbing Markov Chain PP, the powers P2, P3, P4,...P^2,\ P^3,\ P^4,... get closer and closer to a limiting matrix P‾\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 QQ in the bottom right such that I−QI-Q is invertible. The inverse F=(I−Q)−1F = (I-Q)^{-1} is called the fundamental matrix for PP and is used to construct the limiting matrix.
P=[I0RQ] standard form transition matrixP= \left[ \begin{array}{c|c} I & \mathbf{0} \\ \hline R &Q \\ \end{array} \right] \text{ standard form transition matrix}
F=(I−Q)−1 fundamental matrix F = (I-Q)^{-1} \text{ fundamental matrix}
Consider a random walk with three states that has transition:
P=[8/103/101/102/103/107/1004/102/10]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=[8/103/101/102/103/107/1004/102/10]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