Linear AlgebraApplications1 of 6
Applications · 1

Markov Chains and Steady States

When a group keeps moving between states with fixed probabilities at every step, we want to track the numbers from one step to the next and find where they settle in the long run.

1

Building a Markov Transition Matrix

In a Markov chain, where someone goes next depends only on where they are right now, with fixed transition probabilities at every step. We want to put those probabilities into a single transition matrix M\trans{M} so that multiplying by M\trans{M} updates the counts at every state for the next step.

Suppose a town of 1,0001{,}000 coffee drinkers chooses between Shop A and Shop B each week: 80%80\% of Shop A's customers stay at A (while 20%20\% switch to B), and 60%60\% of Shop B's customers stay at B (while 40%40\% switch to A).

1,000 coffee drinkers1{,}000\text{ coffee drinkers}
Shop A\text{Shop A}
Shop B\text{Shop B}
80%80\%
20%20\%
60%60\%
40%40\%

Let's turn these weekly switching percentages into a matrix that moves the starting crowd v0=[10000]\state{v_0} = \begin{bmatrix} 1000 \\ 0 \end{bmatrix} forward from week to week.

Building a Markov Transition Matrix
Shop A\text{Shop A}
Shop B\text{Shop B}
80%80\%
20%20\%
60%60\%
40%40\%
1000\htmlClass{lc-blue}{1000}
0\htmlClass{lc-blue}{0}
New A=  ?New B=  ?\begin{aligned} \htmlClass{lc-blue}{\text{New } A} &= \;? \\ \htmlClass{lc-blue}{\text{New } B} &= \;? \end{aligned}
Text solution
Add the people staying and the people arriving at each shopThe crowd at each shop next week is the fraction who stayed there plus the fraction who switched over from the other shop.
New A=0.80A+0.40BNew B=0.20A+0.60B\displaystyle \begin{aligned} \state{\text{New } A} &= 0.80\state{A} + 0.40\state{B} \\ \state{\text{New } B} &= 0.20\state{A} + 0.60\state{B} \end{aligned}
Put the coefficients into the transition matrix M\trans{M}Put the starting states ("From A", "From B") across the columns and the destination states ("To A", "To B") down the rows so multiplying M\trans{M} by this week's counts [AB]\begin{bmatrix} \state{A} \\ \state{B} \end{bmatrix} gives next week's counts [New ANew B]\begin{bmatrix} \state{\text{New } A} \\ \state{\text{New } B} \end{bmatrix}.
FromAFromBTo ATo B[0.80.20.40.6]0.8⏟1.00.4⏟1.0[AB]=[New ANew B]\displaystyle \begin{aligned} & \begin{array}{rcc} & \begin{gathered}\scriptstyle\text{From} \\[-3pt] \scriptstyle A\end{gathered} & \begin{gathered}\scriptstyle\text{From} \\[-3pt] \scriptstyle B\end{gathered} \\ \begin{array}{r} \text{To } A \\ \text{To } B \end{array} & \left[\begin{array}{c} 0.8 \\ 0.2 \end{array}\right. & \left.\begin{array}{c} 0.4 \\ 0.6 \end{array}\right] \\ & \underbrace{\phantom{0.8}}_{1.0} & \underbrace{\phantom{0.4}}_{1.0} \end{array} \begin{bmatrix} \state{A} \\ \state{B} \end{bmatrix} \\ &\quad = \begin{bmatrix} \state{\text{New } A} \\ \state{\text{New } B} \end{bmatrix} \end{aligned}
2

Stepping to the Steady State and Balancing Flows

Now we want to see what happens to the crowds at the two shops when we multiply by M\trans{M} week after week. The steady state is the long-run split where the total count at each state stops changing from one step to the next.

Stepping to the Steady State and Balancing Flows
v0=[10000]\htmlClass{lc-blue}{v_0} = \htmlClass{lc-blue}{\begin{bmatrix} 1000 \\ 0 \end{bmatrix}}
vk+1=Mvk\htmlClass{lc-blue}{v_{k+1}} = \htmlClass{lc-violet}{M}\htmlClass{lc-blue}{v_k}
Week\text{Week}
A\text{A}
B\text{B}
00
11
22
33
1000\htmlClass{lc-blue}{1000}
0\htmlClass{lc-blue}{0}
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
Text solution
Multiply by M\trans{M} repeatedly using vk+1=Mvk\state{v_{k+1}} = \trans{M}\state{v_k}Stepping v0=[10000]\state{v_0} = \begin{bmatrix} 1000 \\ 0 \end{bmatrix} forward week by week moves the town toward two-thirds at Shop A and one-third at Shop B.
v0=[10000]→×Mv1=[800200]→×Mv2=[720280]→×Mv3=[688312]⟶[667333]\displaystyle \state{v_0} = \begin{bmatrix} 1000 \\ 0 \end{bmatrix} \xrightarrow{\times \trans{M}} \state{v_1} = \begin{bmatrix} 800 \\ 200 \end{bmatrix} \xrightarrow{\times \trans{M}} \state{v_2} = \begin{bmatrix} 720 \\ 280 \end{bmatrix} \xrightarrow{\times \trans{M}} \state{v_3} = \begin{bmatrix} 688 \\ 312 \end{bmatrix} \longrightarrow \begin{bmatrix} 667 \\ 333 \end{bmatrix}
Set the weekly outflow equal to the weekly inflowFor the totals at both shops to stay constant, the 20%20\% of Shop A leaving for B must equal the 40%40\% of Shop B leaving for A.
0.2A⏟outflow from A=0.4B⏟inflow from BA=2B\displaystyle \begin{aligned} \underbrace{0.2\state{A}}_{\text{outflow from } A} &= \underbrace{0.4\state{B}}_{\text{inflow from } B} \\ \state{A} &= 2\state{B} \end{aligned}
Combine A=2B\state{A} = 2\state{B} with A+B=1\state{A} + \state{B} = 1Since the two shops together hold 100%100\% of the town, substitute A=2B\state{A} = 2\state{B} to find the steady-state fractions.
A+B=12B+B=13B=1B=13,A=23\displaystyle \begin{aligned} \state{A} + \state{B} &= 1 \\ 2\state{B} + \state{B} &= 1 \\ 3\state{B} &= 1 \\ \state{B} &= \frac{1}{3}, \quad \state{A} = \frac{2}{3} \end{aligned}

So the steady-state vector is v=[2313]\state{v} = \begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix} (or about 667667 people at Shop A and 333333 at Shop B), where 0.2(667)≈0.4(333)≈1330.2(667) \approx 0.4(333) \approx 133 people switch in each direction every week.

For every starting split of the 1,0001{,}000 coffee drinkers, any mismatch between the 20%20\% leaving Shop A and the 40%40\% leaving Shop B pushes the weekly totals toward the 22-to-11 split, and right at 667667 at A and 333333 at B the two flows match at 133133 people each way.

No matter how the crowd starts split between the two shops, it always settles to the balance point where both shops trade the exact same number of people.
3

Finding the Steady State with (M−I)v=0(M - I)v = 0

Balancing two opposite flows in our head works for two states, but when there are three or more states, people move between all of them at once. We want a matrix equation that finds the steady-state vector v\state{v} for a chain of any size.

Remember that an eigenvector of M\trans{M} with eigenvalue λ\lambda satisfies Mv=λv\trans{M}v = \lambda v, which we solve by subtracting λ\lambda from the diagonal of M\trans{M}: (M−λI)v=0(\trans{M - \lambda I})v = 0.

Finding the Steady State with (M − I)v = 0
M=[0.80.40.20.6](M−I) v=0v=  ?\displaystyle \begin{aligned} \trans{M} &= \begin{bmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{bmatrix} \\ (\trans{M - I})\,\state{v} &= 0 \\ \state{v} &= \;? \end{aligned}
Steady-state equation:Mv\displaystyle \text{Steady-state equation:}\quad \trans{M}\state{v} =v⟺(M−I)v\displaystyle = \state{v} \quad\Longleftrightarrow\quad (\trans{M - I})\state{v} =0with entries of v summing to 1\displaystyle = 0 \quad \text{with entries of } \state{v} \text{ summing to } 1
Text solution
Subtract 11 from the diagonal of M\trans{M} to set up (M−I)v=0(\trans{M - I})\state{v} = 0Because Mv=1v\trans{M}\state{v} = 1\state{v} at the steady state, v\state{v} is an eigenvector with eigenvalue λ=1\lambda = 1. Subtracting 11 from the diagonal turns each "staying" entry into minus the "leaving" fraction.
[0.8−10.40.20.6−1][AB]=[−0.20.40.2−0.4][AB]=[00]\displaystyle \begin{bmatrix} 0.8 - 1 & 0.4 \\ 0.2 & 0.6 - 1 \end{bmatrix} \begin{bmatrix} \state{A} \\ \state{B} \end{bmatrix} = \begin{bmatrix} -0.2 & 0.4 \\ 0.2 & -0.4 \end{bmatrix} \begin{bmatrix} \state{A} \\ \state{B} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}
Drop the redundant row and solve for A\state{A} in terms of B\state{B}Every column of M−I\trans{M - I} adds up to 00, so the rows always sum to the zero row. Keeping Row 1 says that the net change at Shop A is zero.
−0.2A⏟leaving A+0.4B⏟arriving at A=00.2A=0.4BA=2B\displaystyle \begin{aligned} \underbrace{-0.2\state{A}}_{\text{leaving } A} + \underbrace{0.4\state{B}}_{\text{arriving at } A} &= 0 \\ 0.2\state{A} &= 0.4\state{B} \\ \state{A} &= 2\state{B} \end{aligned}
Plug A=2B\state{A} = 2\state{B} into A+B=1\state{A} + \state{B} = 1Since the probabilities must add up to 11, use A+B=1\state{A} + \state{B} = 1 to find the exact entries of v\state{v}.
2B+B=1B=13,A=23,v=[2313]\displaystyle \begin{aligned} 2\state{B} + \state{B} &= 1 \\ \state{B} &= \frac{1}{3}, \quad \state{A} = \frac{2}{3}, \quad \state{v} = \begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix} \end{aligned}

For a 2×22 \times 2 matrix, setting the two switching flows equal (0.2A=0.4B0.2\state{A} = 0.4\state{B}) gives A=2B\state{A} = 2\state{B} right away, though a test often expects the (M−I)v=0(\trans{M - I})\state{v} = 0 steps written out.

4

Finding the Steady State for Three States

Now let's use (M−I)v=0(\trans{M - I})\state{v} = 0 on a three-state chain where a delivery driver moves between Zone A, Zone B, and Zone C according to

M=From AFrom BFrom CTo ATo BTo C[0.80.200.20.60.200.40.6]\displaystyle \trans{M} = \begin{array}{rccc} & \text{From } A & \text{From } B & \text{From } C \\ \begin{array}{r} \text{To } A \\ \text{To } B \\ \text{To } C \end{array} & \left[\begin{array}{c} 0.8 \\ 0.2 \\ 0 \end{array}\right. & \begin{array}{c} 0.2 \\ 0.6 \\ 0.2 \end{array} & \left.\begin{array}{c} 0 \\ 0.4 \\ 0.6 \end{array}\right] \end{array}

and we want to find the steady-state vector v=[ABC]\state{v} = \begin{bmatrix} \state{A} \\ \state{B} \\ \state{C} \end{bmatrix} giving the fraction of time the driver spends in each zone over the long run.

Finding the Steady State for Three States
A\text{A}
B\text{B}
C\text{C}
0.80.8
0.60.6
0.60.6
0.20.2
0.20.2
0.20.2
0.40.4
v=[ABC]=  ?\htmlClass{lc-blue}{v} = \htmlClass{lc-blue}{\begin{bmatrix} A \\ B \\ C \end{bmatrix}} = \;?
Text solution
Subtract 11 from the diagonal to form M−I\trans{M - I}Subtracting 11 from each diagonal entry makes every column sum to 00, so one of the three rows is always redundant.
M−I=[−0.20.200.2−0.40.400.2−0.4]\displaystyle \trans{M - I} = \begin{bmatrix} -0.2 & 0.2 & 0 \\ 0.2 & -0.4 & 0.4 \\ 0 & 0.2 & -0.4 \end{bmatrix}
Pick the two rows with zeros to write every state in terms of C\state{C}Row 1 and Row 3 each have a zero entry, so they immediately relate two states at a time.
Row 1:−0.2A+0.2B=0  ⟹  0.2A=0.2B  ⟹  A=BRow 3:−0.2B−0.4C=0  ⟹  0.2B=0.4C  ⟹  B=2C,A=2C\displaystyle \begin{aligned} & \text{Row 1:}\quad -0.2\state{A} + 0.2\state{B} = 0 \\ &\quad \implies 0.2\state{A} = 0.2\state{B} \\ &\quad \implies \state{A} = \state{B} \\ & \text{Row 3:}\quad \phantom{-}0.2\state{B} - 0.4\state{C} = 0 \\ &\quad \implies 0.2\state{B} = 0.4\state{C} \\ &\quad \implies \state{B} = 2\state{C}, \quad \state{A} = 2\state{C} \end{aligned}
Substitute into A+B+C=1\state{A} + \state{B} + \state{C} = 1Writing A\state{A} and B\state{B} in terms of C\state{C} turns the sum of probabilities into an equation in C\state{C} alone.
2C+2C+1C=15C=1C=15=0.20,A=0.40,B=0.40\displaystyle \begin{aligned} 2\state{C} + 2\state{C} + 1\state{C} &= 1 \\ 5\state{C} &= 1 \\ \state{C} &= \frac{1}{5} = 0.20, \\ \state{A} &= 0.40, \quad \state{B} = 0.40 \end{aligned}

So the steady state is v=[0.400.400.20]\state{v} = \begin{bmatrix} 0.40 \\ 0.40 \\ 0.20 \end{bmatrix}, meaning the driver spends 40%40\% of the time in Zone A, 40%40\% in Zone B, and 20%20\% in Zone C in the long run.

5

Why the Chain Forgets Where It Started

Solving (M−I)v=0(\trans{M - I})\state{v} = 0 shows that a chain already at the steady state stays there. Now we want to see why any starting state v0\state{v_0} gets pulled into that same steady state as we take powers vk=Mkv0\state{v_k} = \trans{M^k} \state{v_0}, and find an exact formula for vk\state{v_k} after kk steps.

When we write a starting vector v0\state{v_0} in terms of the eigenvectors of M\trans{M} as v0=c1v1+c2v2\state{v_0} = \keep{c_1 v_1} + \imbal{c_2 v_2}, each multiplication by M\trans{M} multiplies each eigenvector by its own eigenvalue:

vk\displaystyle \state{v_k} =Mkv0\displaystyle = \trans{M^k} \state{v_0} =c1λ1kv1+c2λ2kv2\displaystyle = \keep{c_1 \lambda_1^k v_1} + \imbal{c_2 \lambda_2^k v_2}

Also remember that for any 2×22 \times 2 matrix, the two eigenvalues always add up to the trace (the sum of the diagonal entries): λ1+λ2=trace⁡(M)\keep{\lambda_1} + \imbal{\lambda_2} = \operatorname{trace}(\trans{M}).

Why the Chain Forgets Where It Started
23\htmlClass{lc-blue}{\dfrac{2}{3}}
00
11
22
33
44
[10]\htmlClass{lc-blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}
00
11
22
33
44
[01]\htmlClass{lc-blue}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}}
vk=Mkv0=  ?\htmlClass{lc-blue}{v_k} = \htmlClass{lc-violet}{M^k}\htmlClass{lc-blue}{v_0} = \;?
Text solution
Find the second eigenvalue λ2\imbal{\lambda_2} using the traceFor the coffee shop matrix M=[0.80.40.20.6]\trans{M} = \begin{bmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{bmatrix}, the diagonal adds up to 0.8+0.6=1.40.8 + 0.6 = 1.4 and we already know λ1=1\keep{\lambda_1} = 1.
λ1+λ2=0.8+0.6=1.4λ2=1.4−1=0.4\displaystyle \begin{aligned} \keep{\lambda_1} + \imbal{\lambda_2} &= 0.8 + 0.6 = 1.4 \\ \imbal{\lambda_2} &= 1.4 - 1 = 0.4 \end{aligned}
Find the second eigenvector v2\imbal{v_2} from (M−0.4I)v=0(\trans{M - 0.4I})\imbal{v} = 0Subtract 0.40.4 from the diagonal to find the eigenvector for the starting imbalance from the steady state.
M−0.4I=[0.40.40.20.2]0.4x+0.4y=0  ⟹  x=−y,v2=[1−1]\displaystyle \begin{aligned} \trans{M - 0.4I} &= \begin{bmatrix} 0.4 & 0.4 \\ 0.2 & 0.2 \end{bmatrix} \\ 0.4x + 0.4y &= 0 \implies x = -y, \\ \imbal{v_2} &= \begin{bmatrix} 1 \\ -1 \end{bmatrix} \end{aligned}
Write the starting state v0=[10]\state{v_0} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} as c1v1+c2v2\keep{c_1 v_1} + \imbal{c_2 v_2}Use the steady state v1=[2313]\keep{v_1} = \begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix} and v2=[1−1]\imbal{v_2} = \begin{bmatrix} 1 \\ -1 \end{bmatrix} to solve for c1\keep{c_1} and c2\imbal{c_2}.
[10]=c1[2313]+c2[1−1]13c1−c2=0  ⟹  c2=13c123c1+13c1=1  ⟹  c1=1,c2=13\displaystyle \begin{aligned} & \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} = \keep{c_1} \keep{\begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix}} + \imbal{c_2} \imbal{\begin{bmatrix} 1 \\ -1 \end{bmatrix}} \\ & \frac{1}{3}\keep{c_1} - \imbal{c_2} = 0 \implies \imbal{c_2} = \frac{1}{3}\keep{c_1} \\ & \frac{2}{3}\keep{c_1} + \frac{1}{3}\keep{c_1} = 1 \implies \keep{c_1} = 1, \\ & \imbal{c_2} = \frac{1}{3} \end{aligned}
Multiply each piece by λk\lambda^k to get vk\state{v_k}At step kk, λ1k=1k=1\keep{\lambda_1^k} = 1^k = 1 keeps the steady state fixed while λ2k=(0.4)k\imbal{\lambda_2^k} = \imbal{(0.4)^k} shrinks the starting imbalance.
vk=Mkv0=[2313]⏟steady state (λ1=1)+13(0.4)k[1−1]⏟imbalance →[00]\displaystyle \state{v_k} = \trans{M^k} \state{v_0} = \underbrace{\keep{\begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix}}}_{\text{steady state } (\keep{\lambda_1} = 1)} + \underbrace{\imbal{\frac{1}{3}(0.4)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix}}}_{\text{imbalance } \to \begin{bmatrix} 0 \\ 0 \end{bmatrix}}

Because ∣λ2∣=0.4<1|\imbal{\lambda_2}| = 0.4 < 1, (0.4)k→0\imbal{(0.4)^k} \to 0 as kk grows, so the starting imbalance shrinks to zero and vk\state{v_k} settles at [2313]\keep{\begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix}} from every starting state.

6

Regular Markov Chains and When Convergence Fails

The starting imbalance only shrinks to zero when every other eigenvalue satisfies ∣λ∣<1|\imbal{\lambda}| < 1. We want a quick way to tell from M\trans{M}, without finding eigenvalues, whether a chain always settles to one steady state or gets stuck in a loop or separate pieces.

A Markov chain is regular if some power Mk\trans{M^k} has all positive entries (no zeros anywhere), meaning it is possible to go from any state to any state in kk steps.

A\text{A}
B\text{B}
100%100\%
100%100\%
P=\htmlClass{lc-violet}{P} =
00
11
11
00
λ2=−1\htmlClass{lc-pink}{\lambda_2} = -1
A\text{A}
B\text{B}
100%100\%
100%100\%
T=\htmlClass{lc-violet}{T} =
11
00
00
11
λ2=1\htmlClass{lc-pink}{\lambda_2} = 1
Regular Markov Chains and When Convergence Fails
vk=c1λ1kv1+c2λ2kv2λ1=1,∣λ2∣<1   always?\displaystyle \begin{aligned} \state{v_k} &= \keep{c_1 \lambda_1^k v_1} + \imbal{c_2 \lambda_2^k v_2} \\ \keep{\lambda_1} &= 1, \quad |\imbal{\lambda_2}| < 1 \;\text{ always?} \end{aligned}
Regularity test:Mk>0 (all entries positive)for some step k⟹∣λ∣<1 for all other eigenvalues\displaystyle \begin{aligned} & \text{Regularity test:}\quad \trans{M^k} > 0 \\ &\quad \text{ (all entries positive)} \\ &\quad \text{for some step } k \\ &\quad \Longrightarrow\quad |\imbal{\lambda}| < 1 \\ &\quad \text{ for all other eigenvalues} \end{aligned}
Text solution
Check M\trans{M} for 1-step zerosIn the delivery driver matrix M\trans{M}, the top-right and bottom-left entries are 00 because the driver cannot move directly between Zone A and Zone C in 1 step.
M=[0.80.200.20.60.400.20.6]\displaystyle \trans{M} = \begin{bmatrix} 0.8 & 0.2 & 0 \\ 0.2 & 0.6 & 0.4 \\ 0 & 0.2 & 0.6 \end{bmatrix}
Multiply M\trans{M} by itself to check 2-step transitions in M2\trans{M^2}Both zero spots become positive because in 2 steps the driver can go A→B→C\state{A} \to \state{B} \to \state{C} (0.2×0.2=0.040.2 \times 0.2 = 0.04) and C→B→A\state{C} \to \state{B} \to \state{A} (0.4×0.2=0.080.4 \times 0.2 = 0.08).
M2=[0.80.200.20.60.400.20.6][0.80.200.20.60.400.20.6]=[0.680.280.080.280.480.480.040.240.44]>0\displaystyle \begin{aligned} & \trans{M^2} \\ &\quad = \begin{bmatrix} 0.8 & 0.2 & 0 \\ 0.2 & 0.6 & 0.4 \\ 0 & 0.2 & 0.6 \end{bmatrix} \\ &\qquad \begin{bmatrix} 0.8 & 0.2 & 0 \\ 0.2 & 0.6 & 0.4 \\ 0 & 0.2 & 0.6 \end{bmatrix} \\ &\quad = \begin{bmatrix} 0.68 & 0.28 & 0.08 \\ 0.28 & 0.48 & 0.48 \\ 0.04 & 0.24 & 0.44 \end{bmatrix} > 0 \end{aligned}

Because every entry of M2\trans{M^2} is positive, the delivery chain is regular, so every starting zone settles to the same steady state v=[0.400.400.20]\state{v} = \begin{bmatrix} 0.40 \\ 0.40 \\ 0.20 \end{bmatrix}.

Try dragging the transition probabilities to the extremes where 100%100\% stay or 100%100\% switch to see when the zeros in Mk\trans{M^k} never disappear and the imbalance never shrinks away.

Whenever the two shops mix so that the matrix powers have no zeros, the second eigenvalue stays smaller than one in size and the starting imbalance shrinks away.

Key concepts

Setting up M\trans{M} and stepping forward (vk+1=Mvk\state{v_{k+1}} = \trans{M}\state{v_k})

Label columns From and rows To, and check that every column adds to 11. When a problem only asks for the state after 11 or 22 steps, just multiply v1=Mv0\state{v_1} = \trans{M}\state{v_0} and v2=Mv1\state{v_2} = \trans{M}\state{v_1} directly, without solving for eigenvalues or the steady state.

Finding the steady state ((M−I)v=0(\trans{M - I})\state{v} = 0 with entries summing to 11)

  • Two states (balance flows directly): For M=[0.80.40.20.6]\trans{M} = \begin{bmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{bmatrix}, you do not need full row reduction. Set the off-diagonal switching flows equal (0.2A=0.4B0.2\state{A} = 0.4\state{B}) to get A=2B\state{A} = 2\state{B}, then use A+B=1\state{A} + \state{B} = 1 to get v=[2313]\state{v} = \begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix}.
  • Three or more states (use M−I\trans{M - I}): Subtract 11 from the diagonal, drop one redundant row, pick the rows that already have zeros to write every state in terms of a single state (such as A=2C\state{A} = 2\state{C} and B=2C\state{B} = 2\state{C}), and plug into A+B+C=1\state{A} + \state{B} + \state{C} = 1.
Exact formula after kk steps (vk=v1+c2λ2kv2\state{v_k} = \keep{v_1} + \imbal{c_2 \lambda_2^k v_2})

For a 2×22 \times 2 chain, use λ1=1\keep{\lambda_1} = 1 and λ2=trace⁡(M)−1\imbal{\lambda_2} = \operatorname{trace}(\trans{M}) - 1. The steady-state probability vector v1\keep{v_1} always gets weight c1=1\keep{c_1} = 1, and the imbalance eigenvector v2=[1−1]\imbal{v_2} = \begin{bmatrix} 1 \\ -1 \end{bmatrix} gets multiplied by λ2k\imbal{\lambda_2^k}: for M=[0.80.40.20.6]\trans{M} = \begin{bmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{bmatrix} and v0=[10]\state{v_0} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, λ2=1.4−1=0.4\imbal{\lambda_2} = 1.4 - 1 = 0.4 and vk=[2313]+13(0.4)k[1−1]\state{v_k} = \keep{\begin{bmatrix} \tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix}} + \imbal{\frac{1}{3}(0.4)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix}}.

Checking regularity (Mk>0\trans{M^k} > 0 for some kk)

A chain will always settle to one unique steady state from every starting state when some power Mk\trans{M^k} has no zeros. If M\trans{M} already has all positive entries, it is regular right away (k=1k = 1). Only multiply out M2\trans{M^2} (and higher powers) when M\trans{M} has zeros to see whether multi-step paths fill them in or whether the zeros stay in place or alternate forever.

7

Practice

1

A fitness club has 500500 members who work out at either the North Gym (N\state{N}) or the South Gym (S\state{S}) each month. Every month, 70%70\% of North Gym members stay at North and the rest switch to South, while 20%20\% of South Gym members switch to North and the rest stay at South. Set up the transition matrix M\trans{M} (with columns From N\state{N}, From S\state{S} and rows To N\state{N}, To S\state{S}), and find how many members are at each gym after 11 month and after 22 months if all 500500 members start at the North Gym (v0=[5000]\state{v_0} = \begin{bmatrix} 500 \\ 0 \end{bmatrix}).

Put "From N\state{N}" in column 1 and "From S\state{S}" in column 2: the problem gives the 20%20\% who switch from South to North, so which row of column 2 does 0.20.2 belong in?

Set up the transition matrix M\trans{M}Since each column must sum to 11, 30%30\% of North members switch to South (bottom of column 1) and 80%80\% of South members stay at South (bottom of column 2). (Watch out: 20%20\% of South members switch to North rather than stay at South. Putting 0.20.2 on the diagonal gives [0.70.80.30.2]\begin{bmatrix} 0.7 & 0.8 \\ 0.3 & 0.2 \end{bmatrix} and a wrong Month 2 answer of [365135]\begin{bmatrix} 365 \\ 135 \end{bmatrix}, while swapping rows and columns to [0.70.30.20.8]\begin{bmatrix} 0.7 & 0.3 \\ 0.2 & 0.8 \end{bmatrix} gives v1=[350100]\state{v_1} = \begin{bmatrix} 350 \\ 100 \end{bmatrix} where 5050 members disappear.)
M=From NFrom STo NTo S[0.70.30.20.8]\displaystyle \trans{M} = \begin{array}{rcc} & \text{From } N & \text{From } S \\ \begin{array}{r} \text{To } N \\ \text{To } S \end{array} & \left[\begin{array}{c} 0.7 \\ 0.3 \end{array}\right. & \left.\begin{array}{c} 0.2 \\ 0.8 \end{array}\right] \end{array}
Step to Month 1 (v1=Mv0\state{v_1} = \trans{M}\state{v_0})
v1=[0.70.20.30.8][5000]=[350150]\displaystyle \state{v_1} = \begin{bmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{bmatrix} \state{\begin{bmatrix} 500 \\ 0 \end{bmatrix}} = \begin{bmatrix} 350 \\ 150 \end{bmatrix}
Step to Month 2 (v2=Mv1\state{v_2} = \trans{M}\state{v_1})
v2=[0.70.20.30.8][350150]=[0.7(350)+0.2(150)0.3(350)+0.8(150)]=[245+30105+120]=[275225]\displaystyle \state{v_2} = \begin{bmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{bmatrix} \state{\begin{bmatrix} 350 \\ 150 \end{bmatrix}} = \begin{bmatrix} 0.7(\state{350}) + 0.2(\state{150}) \\ 0.3(\state{350}) + 0.8(\state{150}) \end{bmatrix} = \begin{bmatrix} 245 + 30 \\ 105 + 120 \end{bmatrix} = \begin{bmatrix} 275 \\ 225 \end{bmatrix}
M=[0.70.20.30.8]\trans{M} = \begin{bmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{bmatrix}; after 11 month: 350350 at North, 150150 at South; after 22 months: 275275 at North, 225225 at South.
2

In a town of 1,0001{,}000 commuters, people take either the Train (T\state{T}) or the Bus (B\state{B}) each week. Every week, 80%80\% of Train riders stay on the Train (20%20\% switch to the Bus), and 70%70\% of Bus riders stay on the Bus (30%30\% switch to the Train). Find the steady-state probability vector v=[TB]\state{v} = \begin{bmatrix} \state{T} \\ \state{B} \end{bmatrix}, the long-run number of commuters on each mode, and how many commuters switch in each direction every week once the steady state is reached.

Balance the weekly outflow from the Train against the weekly inflow from the Bus: what fraction of T\state{T} leaves the Train, and what fraction of B\state{B} leaves the Bus?

Balance outflow and inflow (or solve (M−I)v=0(\trans{M - I})\state{v} = 0)With M−I=[−0.20.30.2−0.3]\trans{M - I} = \begin{bmatrix} -0.2 & 0.3 \\ 0.2 & -0.3 \end{bmatrix}, set the 20%20\% leaving the Train equal to the 30%30\% leaving the Bus. (Watch out: set the switching fractions equal, 0.2T=0.3B0.2\state{T} = 0.3\state{B}, rather than the staying fractions 0.8T=0.7B0.8\state{T} = 0.7\state{B}, which gives [715815]\begin{bmatrix} \tfrac{7}{15} \\[4pt] \tfrac{8}{15} \end{bmatrix}; and solve 0.2T=0.3B0.2\state{T} = 0.3\state{B} as T=1.5B\state{T} = 1.5\state{B} rather than B=1.5T\state{B} = 1.5\state{T}, which flips the steady state to [0.400.60]\begin{bmatrix} 0.40 \\ 0.60 \end{bmatrix} and 400400 on the Train, 600600 on the Bus.)
0.2T=0.3BT=1.5B\displaystyle \begin{aligned} 0.2\state{T} &= 0.3\state{B} \\ \state{T} &= 1.5\state{B} \end{aligned}
Substitute into T+B=1\state{T} + \state{B} = 1
1.5B+B=12.5B=1B=25=0.40,T=35=0.60,v=[0.600.40]\displaystyle \begin{aligned} 1.5\state{B} + \state{B} &= 1 \\ 2.5\state{B} &= 1 \\ \state{B} &= \frac{2}{5} = 0.40, \quad \state{T} = \frac{3}{5} \\ &= 0.60, \\ \state{v} &= \begin{bmatrix} 0.60 \\ 0.40 \end{bmatrix} \end{aligned}
Multiply by 1,0001{,}000 commuters and find the weekly number of switchers
1000v=[600400]Weekly switchers=0.20(600)=0.30(400)=120\displaystyle \begin{aligned} & 1000\state{v} = \begin{bmatrix} 600 \\ 400 \end{bmatrix} \\ & \text{Weekly switchers} = 0.20(600) \\ &\quad = 0.30(400)= 120 \end{aligned}
v=[0.600.40]\state{v} = \begin{bmatrix} 0.60 \\ 0.40 \end{bmatrix}; 600600 on the Train and 400400 on the Bus; 120120 commuters switch each way every week.
3

Find the steady-state vector v=[ABC]\state{v} = \begin{bmatrix} \state{A} \\ \state{B} \\ \state{C} \end{bmatrix} for the three-state Markov chain with transition matrix

M=[0.80.20.20.20.60.200.20.6]\displaystyle \trans{M} = \begin{bmatrix} 0.8 & 0.2 & 0.2 \\ 0.2 & 0.6 & 0.2 \\ 0 & 0.2 & 0.6 \end{bmatrix}

After subtracting 11 from the diagonal to form M−I\trans{M - I}, start with Row 3, since its zero in the first column gives B\state{B} directly in terms of C\state{C}.

Subtract 11 from the diagonal to get M−I\trans{M - I}
M−I=[−0.20.20.20.2−0.40.200.2−0.4]\displaystyle \trans{M - I} = \begin{bmatrix} -0.2 & 0.2 & 0.2 \\ 0.2 & -0.4 & 0.2 \\ 0 & 0.2 & -0.4 \end{bmatrix}
Use Row 3 and Row 1 to write B\state{B} and A\state{A} in terms of C\state{C} (Watch out: the top-right entry of M−I\trans{M - I} is 0.20.2, not 00. Leaving out +0.2C+0.2\state{C} in Row 1 gives A=B=2C\state{A} = \state{B} = 2\state{C} and the wrong steady state [252515]\begin{bmatrix} \tfrac{2}{5} \\[4pt] \tfrac{2}{5} \\[4pt] \tfrac{1}{5} \end{bmatrix}.)
Row 3:−0.2B−0.4C=0  ⟹  B=2CRow 1:−0.2A+0.2B+0.2C=0  ⟹  A=B+C=2C+C=3C\displaystyle \begin{aligned} & \text{Row 3:}\quad \phantom{-}0.2\state{B} - 0.4\state{C} = 0 \\ &\quad \implies \state{B} = 2\state{C} \\ & \text{Row 1:}\quad -0.2\state{A} + 0.2\state{B} \\ &\quad + 0.2\state{C} = 0 \\ &\quad \implies \state{A} = \state{B} + \state{C} \\ &\quad = 2\state{C} + \state{C} = 3\state{C} \end{aligned}
Use A+B+C=1\state{A} + \state{B} + \state{C} = 1 to solve for C\state{C}, B\state{B}, and A\state{A}
3C+2C+C=16C=1C=16,B=13,A=12\displaystyle \begin{aligned} & 3\state{C} + 2\state{C} + \state{C} = 1 \\ & 6\state{C} = 1 \\ & \state{C} = \frac{1}{6}, \quad \state{B} = \frac{1}{3}, \quad \state{A} = \frac{1}{2} \end{aligned}
v=[121316]\state{v} = \begin{bmatrix} \tfrac{1}{2} \\[4pt] \tfrac{1}{3} \\[4pt] \tfrac{1}{6} \end{bmatrix}.
4

For the transition matrix M=[0.90.30.10.7]\trans{M} = \begin{bmatrix} 0.9 & 0.3 \\ 0.1 & 0.7 \end{bmatrix} and starting state v0=[01]\state{v_0} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, find both eigenvalues of M\trans{M}, the corresponding eigenvectors v1\keep{v_1} (the steady state with entries summing to 11) and v2\imbal{v_2}, and the exact formula for vk=Mkv0\state{v_k} = \trans{M^k} \state{v_0} after kk steps.

Use λ1=1\keep{\lambda_1} = 1 and trace⁡(M)\operatorname{trace}(\trans{M}) to find λ2\imbal{\lambda_2} in one step, then solve v0=[01]=c1v1+c2v2\state{v_0} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \keep{c_1 v_1} + \imbal{c_2 v_2} for c1\keep{c_1} and c2\imbal{c_2}.

Find λ1\keep{\lambda_1} and λ2\imbal{\lambda_2} using the trace
trace⁡(M)=0.9+0.7=1.6λ1=1,λ2=1.6−1=0.6\displaystyle \begin{aligned} \operatorname{trace}(\trans{M}) &= 0.9 + 0.7 = 1.6 \\ \keep{\lambda_1} &= 1, \quad \imbal{\lambda_2} = 1.6 - 1 = 0.6 \end{aligned}
Find the eigenvectors v1\keep{v_1} and v2\imbal{v_2}For λ1=1\keep{\lambda_1} = 1, 0.1A=0.3B  ⟹  A=3B0.1\state{A} = 0.3\state{B} \implies \state{A} = 3\state{B} with A+B=1\state{A} + \state{B} = 1. For λ2=0.6\imbal{\lambda_2} = 0.6, subtract 0.60.6 from the diagonal.
λ1=1:3B+B=1  ⟹  v1=[3414]λ2=0.6:M−0.6I=[0.30.30.10.1]  ⟹  v2=[1−1]\displaystyle \begin{aligned} \keep{\lambda_1} = 1: &\quad 3\state{B} + \state{B} = 1 \\ &\implies \keep{v_1} = \begin{bmatrix} \tfrac{3}{4} \\[4pt] \tfrac{1}{4} \end{bmatrix} \\ \imbal{\lambda_2} = 0.6: &\quad \trans{M - 0.6I} \\ &= \begin{bmatrix} 0.3 & 0.3 \\ 0.1 & 0.1 \end{bmatrix} \\ &\implies \imbal{v_2} = \begin{bmatrix} 1 \\ -1 \end{bmatrix} \end{aligned}
Find c1,c2\keep{c_1}, \imbal{c_2} from v0=[01]\state{v_0} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} and write vk\state{v_k} (Watch out: v0=[01]\state{v_0} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} has 00 in the top entry, so 34c1+c2=0\frac{3}{4}\keep{c_1} + \imbal{c_2} = 0 gives c2=−34\imbal{c_2} = -\frac{3}{4}; solving as if v0=[10]\state{v_0} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} gives c2=+14\imbal{c_2} = +\frac{1}{4} and the wrong formula [3414]+14(0.6)k[1−1]\begin{bmatrix} \tfrac{3}{4} \\[4pt] \tfrac{1}{4} \end{bmatrix} + \frac{1}{4}(0.6)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix}.)
[01]=c1[3414]+c2[1−1]  ⟹  c1=1,c2=−34vk=[3414]−34(0.6)k[1−1]\displaystyle \begin{aligned} \state{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} &= \keep{c_1} \keep{\begin{bmatrix} \tfrac{3}{4} \\[4pt] \tfrac{1}{4} \end{bmatrix}} + \imbal{c_2} \imbal{\begin{bmatrix} 1 \\ -1 \end{bmatrix}} \\ &\implies \keep{c_1} = 1, \\ \imbal{c_2} &= -\frac{3}{4} \\ \state{v_k} &= \keep{\begin{bmatrix} \tfrac{3}{4} \\[4pt] \tfrac{1}{4} \end{bmatrix}} - \imbal{\frac{3}{4}(0.6)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix}} \end{aligned}
λ1=1,λ2=0.6\keep{\lambda_1} = 1, \imbal{\lambda_2} = 0.6; v1=[3414],v2=[1−1]\keep{v_1} = \begin{bmatrix} \tfrac{3}{4} \\[4pt] \tfrac{1}{4} \end{bmatrix}, \imbal{v_2} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}; vk=[3414]−34(0.6)k[1−1]\state{v_k} = \begin{bmatrix} \tfrac{3}{4} \\[4pt] \tfrac{1}{4} \end{bmatrix} - \frac{3}{4}(0.6)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix}.
5

Determine which of the two transition matrices

A=[00.5010100.50]andB=[0.500.50.50.5000.50.5]\displaystyle \begin{aligned} & \trans{A} = \begin{bmatrix} 0 & 0.5 & 0 \\ 1 & 0 & 1 \\ 0 & 0.5 & 0 \end{bmatrix} \quad \\ & \text{and} \quad \trans{B} \\ & = \begin{bmatrix} 0.5 & 0 & 0.5 \\ 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \end{bmatrix} \end{aligned}

is regular and will always settle to a unique steady state from every starting state.

Both matrices have zeros in 1 step, so multiply each matrix by itself to check whether all entries become positive in 2 steps (A2\trans{A^2} and B2\trans{B^2}).

Multiply B\trans{B} by itself to check 2-step transitions (Watch out: don't rule out B\trans{B} just because B1\trans{B^1} has zeros, and use full matrix multiplication rather than squaring each entry on its own. Squaring entry by entry leaves the zeros in place and misses the 2-step paths around the cycle.)
B2=[0.500.50.50.5000.50.5][0.500.50.50.5000.50.5]=[0.250.250.500.500.250.250.250.500.25]>0\displaystyle \trans{B^2} = \begin{bmatrix} 0.5 & 0 & 0.5 \\ 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \end{bmatrix} \begin{bmatrix} 0.5 & 0 & 0.5 \\ 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \end{bmatrix} = \begin{bmatrix} 0.25 & 0.25 & 0.50 \\ 0.50 & 0.25 & 0.25 \\ 0.25 & 0.50 & 0.25 \end{bmatrix} > 0
Multiply A\trans{A} by itself to see why its zeros never disappearThe chain moves back and forth between State 2 and {State 1,State 3}\{\text{State 1}, \text{State 3}\} at every step, so the zeros swap places between odd and even powers forever.
A2=[00.5010100.50][00.5010100.50]=[0.500.50100.500.5],A3=A\displaystyle \trans{A^2} = \begin{bmatrix} \stuck{0} & 0.5 & \stuck{0} \\ 1 & \stuck{0} & 1 \\ \stuck{0} & 0.5 & \stuck{0} \end{bmatrix} \begin{bmatrix} \stuck{0} & 0.5 & \stuck{0} \\ 1 & \stuck{0} & 1 \\ \stuck{0} & 0.5 & \stuck{0} \end{bmatrix} = \begin{bmatrix} 0.5 & \stuck{0} & 0.5 \\ \stuck{0} & 1 & \stuck{0} \\ 0.5 & \stuck{0} & 0.5 \end{bmatrix}, \quad \trans{A^3} = \trans{A}
B\trans{B} is regular (and A\trans{A} is not).