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 matrixM so that multiplying by M updates the counts at every state for the next step.
Suppose a town of 1,000 coffee drinkers chooses between Shop A and Shop B each week: 80% of Shop A's customers stay at A (while 20% switch to B), and 60% of Shop B's customers stay at B (while 40% switch to A).
Let's turn these weekly switching percentages into a matrix that moves the starting crowd v0=[10000] forward from week to week.
Building a Markov Transition Matrix
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 ANew B=0.80A+0.40B=0.20A+0.60B
Put the coefficients into the transition matrix MPut the starting states ("From A", "From B") across the columns and the destination states ("To A", "To B") down the rows so multiplying M by this week's counts [AB] gives next week's counts [New ANew B].
To ATo BFromA[0.80.21.00.8FromB0.40.6]1.00.4[AB]=[New ANew B]
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 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
Text solution
Multiply by M repeatedly using vk+1=MvkStepping v0=[10000] forward week by week moves the town toward two-thirds at Shop A and one-third at Shop B.
Set the weekly outflow equal to the weekly inflowFor the totals at both shops to stay constant, the 20% of Shop A leaving for B must equal the 40% of Shop B leaving for A.
outflow from A0.2AA=inflow from B0.4B=2B
Combine A=2B with A+B=1Since the two shops together hold 100% of the town, substitute A=2B to find the steady-state fractions.
A+B2B+B3BB=1=1=1=31,A=32
So the steady-state vector is v=[3231] (or about 667 people at Shop A and 333 at Shop B), where 0.2(667)≈0.4(333)≈133 people switch in each direction every week.
For every starting split of the 1,000 coffee drinkers, any mismatch between the 20% leaving Shop A and the 40% leaving Shop B pushes the weekly totals toward the 2-to-1 split, and right at 667 at A and 333 at B the two flows match at 133 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
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 for a chain of any size.
Remember that an eigenvector of M with eigenvalue λ satisfies Mv=λv, which we solve by subtracting λ from the diagonal of M:(M−λI)v=0.
Finding the Steady State with (M − I)v = 0
M(M−I)vv=[0.80.20.40.6]=0=?
Steady-state equation:Mv=v⟺(M−I)v=0with entries of v summing to 1
Text solution
Subtract 1 from the diagonal of M to set up (M−I)v=0Because Mv=1v at the steady state, v is an eigenvector with eigenvalue λ=1. Subtracting 1 from the diagonal turns each "staying" entry into minus the "leaving" fraction.
Drop the redundant row and solve for A in terms of BEvery column of M−I adds up to 0, so the rows always sum to the zero row. Keeping Row 1 says that the net change at Shop A is zero.
leaving A−0.2A+arriving at A0.4B0.2AA=0=0.4B=2B
Plug A=2B into A+B=1Since the probabilities must add up to 1, use A+B=1 to find the exact entries of v.
2B+BB=1=31,A=32,v=[3231]
For a 2×2 matrix, setting the two switching flows equal (0.2A=0.4B) gives A=2B right away, though a test often expects the (M−I)v=0 steps written out.
4
Finding the Steady State for Three States
Now let's use (M−I)v=0 on a three-state chain where a delivery driver moves between Zone A, Zone B, and Zone C according to
M=To ATo BTo CFrom A0.80.20From B0.20.60.2From C00.40.6
and we want to find the steady-state vector v=ABC giving the fraction of time the driver spends in each zone over the long run.
Finding the Steady State for Three States
Text solution
Subtract 1 from the diagonal to form M−ISubtracting 1 from each diagonal entry makes every column sum to 0, so one of the three rows is always redundant.
M−I=−0.20.200.2−0.40.200.4−0.4
Pick the two rows with zeros to write every state in terms of CRow 1 and Row 3 each have a zero entry, so they immediately relate two states at a time.
Substitute into A+B+C=1Writing A and B in terms of C turns the sum of probabilities into an equation in C alone.
2C+2C+1C5CCA=1=1=51=0.20,=0.40,B=0.40
So the steady state is v=0.400.400.20, meaning the driver spends 40% of the time in Zone A, 40% in Zone B, and 20% in Zone C in the long run.
5
Why the Chain Forgets Where It Started
Solving (M−I)v=0 shows that a chain already at the steady state stays there. Now we want to see why any starting state v0 gets pulled into that same steady state as we take powers vk=Mkv0, and find an exact formula for vk after k steps.
When we write a starting vector v0 in terms of the eigenvectors of M as v0=c1v1+c2v2, each multiplication by M multiplies each eigenvector by its own eigenvalue:
vk=Mkv0=c1λ1kv1+c2λ2kv2
Also remember that for any 2×2 matrix, the two eigenvalues always add up to the trace (the sum of the diagonal entries): λ1+λ2=trace(M).
Why the Chain Forgets Where It Started
32
0
1
2
3
4
[10]
0
1
2
3
4
[01]
vk=Mkv0=?
Text solution
Find the second eigenvalue λ2 using the traceFor the coffee shop matrix M=[0.80.20.40.6], the diagonal adds up to 0.8+0.6=1.4 and we already know λ1=1.
λ1+λ2λ2=0.8+0.6=1.4=1.4−1=0.4
Find the second eigenvector v2 from (M−0.4I)v=0Subtract 0.4 from the diagonal to find the eigenvector for the starting imbalance from the steady state.
Multiply each piece by λk to get vkAt step k,λ1k=1k=1 keeps the steady state fixed while λ2k=(0.4)k shrinks the starting imbalance.
vk=Mkv0=steady state (λ1=1)[3231]+imbalance →[00]31(0.4)k[1−1]
Because ∣λ2∣=0.4<1,(0.4)k→0 as k grows, so the starting imbalance shrinks to zero and vk settles at [3231] 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. We want a quick way to tell from 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 has all positive entries (no zeros anywhere), meaning it is possible to go from any state to any state in k steps.
A
B
100%
100%
P=
0
1
1
0
λ2=−1
A
B
100%
100%
T=
1
0
0
1
λ2=1
Regular Markov Chains and When Convergence Fails
vkλ1=c1λ1kv1+c2λ2kv2=1,∣λ2∣<1 always?
Regularity test:Mk>0 (all entries positive)for some step k⟹∣λ∣<1 for all other eigenvalues
Text solution
Check M for 1-step zerosIn the delivery driver matrix M, the top-right and bottom-left entries are 0 because the driver cannot move directly between Zone A and Zone C in 1 step.
M=0.80.200.20.60.200.40.6
Multiply M by itself to check 2-step transitions in M2Both zero spots become positive because in 2 steps the driver can go A→B→C (0.2×0.2=0.04) and C→B→A (0.4×0.2=0.08).
Because every entry of M2 is positive, the delivery chain is regular, so every starting zone settles to the same steady state v=0.400.400.20.
Try dragging the transition probabilities to the extremes where 100% stay or 100% switch to see when the zeros in Mk 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 and stepping forward (vk+1=Mvk)
Label columns From and rows To, and check that every column adds to 1. When a problem only asks for the state after 1 or 2 steps, just multiply v1=Mv0 and v2=Mv1 directly, without solving for eigenvalues or the steady state.
Finding the steady state ((M−I)v=0 with entries summing to 1)
Two states (balance flows directly): For M=[0.80.20.40.6], you do not need full row reduction. Set the off-diagonal switching flows equal (0.2A=0.4B) to get A=2B, then use A+B=1 to get v=[3231].
Three or more states (use M−I): Subtract 1 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 and B=2C), and plug into A+B+C=1.
Exact formula after k steps (vk=v1+c2λ2kv2)
For a 2×2 chain, use λ1=1 and λ2=trace(M)−1. The steady-state probability vector v1 always gets weight c1=1, and the imbalance eigenvector v2=[1−1] gets multiplied by λ2k: for M=[0.80.20.40.6] and v0=[10],λ2=1.4−1=0.4 and vk=[3231]+31(0.4)k[1−1].
Checking regularity (Mk>0 for some k)
A chain will always settle to one unique steady state from every starting state when some power Mk has no zeros. If M already has all positive entries, it is regular right away (k=1). Only multiply out M2 (and higher powers) when 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 500 members who work out at either the North Gym (N) or the South Gym (S) each month. Every month, 70% of North Gym members stay at North and the rest switch to South, while 20% of South Gym members switch to North and the rest stay at South. Set up the transition matrix M (with columns From N, From S and rows To N, To S), and find how many members are at each gym after 1 month and after 2 months if all 500 members start at the North Gym (v0=[5000]).
Put "From N" in column 1 and "From S" in column 2: the problem gives the 20% who switch from South to North, so which row of column 2 does 0.2 belong in?
Set up the transition matrix MSince each column must sum to 1,30% of North members switch to South (bottom of column 1) and 80% of South members stay at South (bottom of column 2). (Watch out: 20% of South members switch to North rather than stay at South. Putting 0.2 on the diagonal gives [0.70.30.80.2] and a wrong Month 2 answer of [365135], while swapping rows and columns to [0.70.20.30.8] gives v1=[350100] where 50 members disappear.)
M=[0.70.30.20.8]; after 1 month: 350 at North, 150 at South; after 2 months: 275 at North, 225 at South.
2
In a town of 1,000 commuters, people take either the Train (T) or the Bus (B) each week. Every week, 80% of Train riders stay on the Train (20% switch to the Bus), and 70% of Bus riders stay on the Bus (30% switch to the Train). Find the steady-state probability vector v=[TB], 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.
Watch out: set the switching fractions equal, 0.2T=0.3B, rather than the staying fractions 0.8T=0.7B, which gives [157158]; and solve 0.2T=0.3B as T=1.5B rather than B=1.5T, which flips the steady state to [0.400.60] and 400 on the Train, 600 on the Bus.
Balance the weekly outflow from the Train against the weekly inflow from the Bus: what fraction of T leaves the Train, and what fraction of B leaves the Bus?
Balance outflow and inflow (or solve (M−I)v=0)With M−I=[−0.20.20.3−0.3], set the 20% leaving the Train equal to the 30% leaving the Bus. (Watch out: set the switching fractions equal, 0.2T=0.3B, rather than the staying fractions 0.8T=0.7B, which gives [157158]; and solve 0.2T=0.3B as T=1.5B rather than B=1.5T, which flips the steady state to [0.400.60] and 400 on the Train, 600 on the Bus.)
v=[0.600.40];600 on the Train and 400 on the Bus; 120 commuters switch each way every week.
3
Find the steady-state vector v=ABC for the three-state Markov chain with transition matrix
M=0.80.200.20.60.20.20.20.6
Watch out: the top-right entry of M−I is 0.2, not 0. Leaving out +0.2C in Row 1 gives A=B=2C and the wrong steady state 525251.
After subtracting 1 from the diagonal to form M−I, start with Row 3, since its zero in the first column gives B directly in terms of C.
Subtract 1 from the diagonal to get M−I
M−I=−0.20.200.2−0.40.20.20.2−0.4
Use Row 3 and Row 1 to write B and A in terms of C(Watch out: the top-right entry of M−I is 0.2, not 0. Leaving out +0.2C in Row 1 gives A=B=2C and the wrong steady state 525251.)
For the transition matrix M=[0.90.10.30.7] and starting state v0=[01], find both eigenvalues of M, the corresponding eigenvectors v1 (the steady state with entries summing to 1) and v2, and the exact formula for vk=Mkv0 after k steps.
Use λ1=1 and trace(M) to find λ2 in one step, then solve v0=[01]=c1v1+c2v2 for c1 and c2.
Find λ1 and λ2 using the trace
trace(M)λ1=0.9+0.7=1.6=1,λ2=1.6−1=0.6
Find the eigenvectors v1 and v2For λ1=1,0.1A=0.3B⟹A=3B with A+B=1. For λ2=0.6, subtract 0.6 from the diagonal.
Find c1,c2 from v0=[01] and write vk(Watch out: v0=[01] has 0 in the top entry, so 43c1+c2=0 gives c2=−43; solving as if v0=[10] gives c2=+41 and the wrong formula [4341]+41(0.6)k[1−1].)
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 and B2).
Multiply B by itself to check 2-step transitions(Watch out: don't rule out B just because B1 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.)
Multiply A by itself to see why its zeros never disappearThe chain moves back and forth between State 2 and {State 1,State 3} at every step, so the zeros swap places between odd and even powers forever.