Convergence Concepts Slides Module 01: System Stability
STEADY
STATE
Regular Markov Chains and the Path to Equilibrium
The Eternal Shuffle
Imagine a deck of cards. You perform a specific shuffle over and over again.
Does the deck eventually become "random enough" that the original order is forgotten?
"Most systems with enough freedom eventually lose memory of where they started."
Definition
Regular Markov Chains
A Markov chain is regular if there exists some power of the transition matrix \( P^k \) such that all entries are strictly positive (\( > 0 \)).
Translation:
Every state is reachable from every other state in exactly \( k \) steps.
Significance:
The system never gets stuck in a loop or a subset of states forever.
The Convergence Effect
Step 1
Highly Variable
Step 5
Smoothing Out
Step \(\infty\)
Equilibrium Reach
"As \( n \to \infty \), the probability of being in any state \( j \) approaches a unique constant value, regardless of the initial state."
Weather Logic
In a simple weather model:
Sunny tomorrow given Sunny today: 0.9
Rainy tomorrow given Sunny today: 0.1
Sunny tomorrow given Rainy today: 0.5
Rainy tomorrow given Rainy today: 0.5
Long run? \( 83.3\% \) Sun, \( 16.7\% \) Rain.
Challenge Prep
01
Can we find a state that is impossible to leave? (Absorbing)
02
Is there a shortcut to calculating Step \(\infty\) without doing 100 multiplications?
Regular Chain Simulations Worksheet Equilibrium Hunt
Lesson 01: Regular Chains & Limits
Student:
Date:
Part 1: Identifying Regularity
Recall: A chain is regular if \( P^k \) has all positive entries for some \( k \).
Matrix A:
\[ A = \begin{bmatrix} 0.5 & 0.5 \\ 1 & 0 \end{bmatrix} \]
Calculate \( A^2 \):
Is A regular? Why/Why not?
Matrix B:
\[ B = \begin{bmatrix} 1 & 0 \\ 0.5 & 0.5 \end{bmatrix} \]
Calculate \( B^2 \):
Is B regular? Why/Why not?
Part 2: The Path to Stability
Consider the consumer behavior transition matrix \( T \) between two competing coffee brands, Bean (B) and Roast (R):
\[ T = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} \]
1. Start at a state where everyone drinks Bean: \( \mathbf{v}_0 = [1, 0] \). Calculate the next three states.
Step 1: \( \mathbf{v}_0 T \)
Step 2: \( \mathbf{v}_1 T \)
Step 3: \( \mathbf{v}_2 T \)
2. Start at a state where everyone drinks Roast: \( \mathbf{w}_0 = [0, 1] \). Calculate the next three states.
Step 1: \( \mathbf{w}_0 T \)
Step 2: \( \mathbf{w}_1 T \)
Step 3: \( \mathbf{w}_2 T \)
Observation Challenge
Compare the final vectors of Step 3 for both starting points. What do you notice about their values? Predict the state at \( \mathbf{v}_{100} \).
Regular Chains Facilitator Guide Facilitator Guide
Lesson 01: Regular Chains & Limits
Instructional Goal
Students will conceptually understand why "regularity" is a prerequisite for a unique steady state. They move from manual matrix multiplication to recognizing the numerical stabilization of probabilities.
Pacing
Hook/Intro 10m
Classification 15m
Simulation 25m
Debrief 10m
Key Discussion Prompts
1
"Why do we need a power of the matrix to be all positive?"
Ensure students realize that if a state is unreachable (0 entries forever), the system cannot distribute itself globally, potentially leading to multiple or no steady states.
2
"Did the starting position matter in the long run?"
This is the 'Eureka' moment. Regardless of \( \mathbf{v}_0 \), a regular chain collapses to the same \( \mathbf{w} \). Use the card shuffling analogy here.
Common Pitfalls
Regular vs. Irreducible
Students might confuse "being able to reach every state eventually" with "every state reachable in exactly \( k \) steps." Regularity prevents cyclic behavior (e.g., oscillating between state 1 and 2 every other step).
0s are okay... for now
Students often think a matrix with any 0 is not regular. Remind them: \( P \) doesn't have to be all positive; \( P^k \) does.
Activity Quick-Key
// Coffee Matrix T
Steady State: [2/3, 1/3]
Approx: [0.667, 0.333]
// Matrix A (Regular)
A^2 = [0.75, 0.25; 0.5, 0.5]
All positive! It is regular.
Steady State Algebra Slides Module 02: Algebraic Solutions
SOLVING FOR
BALANCE
Finding the Stationary Distribution via Linear Algebra
The Definition of Stability
A vector \( \mathbf{\pi} \) is a stationary distribution if:
\[ \mathbf{\pi} P = \mathbf{\pi} \]
"Applying the transitions doesn't change the distribution anymore. We've hit the limit."
Breaking it Down
For a \( 2 \times 2 \) matrix \( P = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \):
\[ [x, y] \begin{bmatrix} a & b \\ c & d \end{bmatrix} = [x, y] \]
This yields two equations:
\( ax + cy = x \)
\( bx + dy = y \)
The Secret Rule
The equations above are linearly dependent. You always need the Normalization Constraint:
\( x + y = 1 \)
Step-by-Step Example
STEP 01
Setup
Matrix \( P = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \)
Set up \( \mathbf{\pi} P = \mathbf{\pi} \)
STEP 02
Isolate
\( 0.7x + 0.4y = x \)
\( -0.3x + 0.4y = 0 \)
\( 3x = 4y \)
STEP 03
Normalize
Substitute into \( x + y = 1 \)
\( x + \frac{3}{4}x = 1 \)
\( x = \frac{4}{7}, y = \frac{3}{7} \)
Money Flow
In a closed economy, money circulates between three sectors: Industry, Services, and Households.
A stationary distribution tells us the long-run wealth share of each sector.
Equilibrium Equations Worksheet The Balance Point
Lesson 02: Algebraic Equilibrium Solutions
Collaborator:
System Date:
Scenario 1: Population Migration
In a certain region, people move between the City (C) and the Suburbs (S) every year. The transition matrix is:
\[ P = \begin{bmatrix} 0.85 & 0.15 \\ 0.10 & 0.90 \end{bmatrix} \]
1. Set up the vector equation \( [x, y] P = [x, y] \) and write out the resulting system of linear equations.
2. Include the normalization constraint and solve for the steady-state distribution \( \mathbf{\pi} \). Show your work.
Final City %:
Final Suburb %:
Advanced: The Three-State Flow
Find the stationary distribution for the following transition matrix:
\[ M = \begin{bmatrix} 0.5 & 0.5 & 0 \\ 0.2 & 0.6 & 0.2 \\ 0 & 0.4 & 0.6 \end{bmatrix} \]
3. Write the system of equations derived from \( [x, y, z] M = [x, y, z] \).
4. Solve the system. (Hint: Use substitution or elimination to relate all variables to \( y \) first).
Final Equilibrium Vector:
State 1
State 2
State 3
Absorbing Chains Slides Module 03: The Trap State
ABSORBING
CHAINS
"Some doors only open one way."
The Absorbing State
Characteristics:
Once you enter, you cannot leave (\( p_{ii} = 1 \)).
It is possible to reach an absorbing state from any non-absorbing state.
Matrix Architecture
To analyze these, we rearrange the matrix into Canonical Form:
\[ P = \begin{bmatrix} I & 0 \\ R & Q \end{bmatrix} \]
I The absorbing states
Q Transitions between non-absorbing states
R Moving from non-absorbing to absorbing
Calculating Time
The Fundamental Matrix (N) tells us the average number of steps before absorption.
\[ N = (I - Q)^{-1} \]
Wait Time:
The sum of the entries in a row of \( N \) is the expected time to reach absorption from that state.
Absorption Prob:
The matrix \( B = N \times R \) gives the probability of ending up in each specific absorbing state.
Gambler's Ruin
You have $2. You bet $1 each turn.
If you hit $4, you WIN (Stop).
What is the probability you leave rich?
Gamblers Ruin Activity The Exit Matrix
Lesson 03: Absorbing States & Fundamental Matrices
Player:
Stake:
Part 1: Identifying the Trap
For each matrix, circle the absorbing states and then rewrite the matrix in canonical form: \( P = \begin{bmatrix} I & 0 \\ R & Q \end{bmatrix} \)
Matrix A:
\[ A = \begin{bmatrix} 1 & 0 & 0 \\ 0.2 & 0.6 & 0.2 \\ 0 & 0 & 1 \end{bmatrix} \]
Canonical Form
Fill in I, 0, R, Q sub-matrices
Matrix B:
\[ B = \begin{bmatrix} 0.5 & 0.5 & 0 \\ 0 & 1 & 0 \\ 0.3 & 0 & 0.7 \end{bmatrix} \]
Canonical Form
Fill in I, 0, R, Q sub-matrices
Part 2: Escape Analysis
Consider a simple health insurance model where a customer starts in the Active (A) state, may become Disabled (D), or may leave the company by Lapsing (L). Lapsing is an absorbing state.
\[ P = \begin{bmatrix} 1 & 0 & 0 \\ 0.1 & 0.8 & 0.1 \\ 0.2 & 0.3 & 0.5 \end{bmatrix} \begin{matrix} \text{(L)} \\ \text{(A)} \\ \text{(D)} \end{matrix} \]
1. Identify the \( Q \) matrix and calculate the Fundamental Matrix \( N = (I - Q)^{-1} \).
Step 1: Write (I - Q)
Step 2: Invert it to find N
2. What is the expected number of years an "Active" customer stays with the company before lapsing?
(Hint: Sum the first row of N)
The Gambler's Choice
Calculate \( B = N \times R \). What is the probability that a customer starting in the Disabled state eventually reaches the Lapsed state?
Surfing the Web Slides Module 04: Real World Application
PAGE
RANK
Ranking the Internet with Steady-State Vectors
How do we rank "Importance"?
In 1996, search engines just counted keywords. It was easily gamed.
Larry Page and Sergey Brin had a better idea:
"A page is important if important pages link to it."
The Random Surfer Model
Imagine a user who starts on a random webpage and just clicks random links forever.
Transitions
If a page has 3 links, the surfer has a \( 1/3 \) chance of clicking each.
Long Run
The surfer eventually spends more time on some pages than others.
The Rank
Your PageRank is your steady-state probability!
Building the Matrix
Page A links to B and C.
Page B links only to C.
Page C links only to A.
\[ P = \begin{bmatrix} 0 & 0.5 & 0.5 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \]
Observation:
Notice there are 0s. Is this matrix regular?
Calculate \( P^k \) to check!
What if there are no links?
Dead ends (sinks) destroy the chain's regularity. Google fixed this with a Damping Factor (\( d = 0.85 \)).
85% chance of clicking a link.
15% chance of teleporting to a random page.
Regularity Guaranteed.
PageRank Ranking Challenge Network Ranker
Lesson 04: The PageRank Algorithm
Analyst:
Node ID:
The Mini-Web Model
A
B
C
Link Map Architecture
Connectivity Rules:
Page A links to B and C
Page B links only to C
Page C links back to A and B
Assume a "Random Surfer" who clicks links with equal probability. If they are on Page A, they have a 50% chance of going to B and a 50% chance of going to C.
Task 01: The Matrix
Construct the transition matrix \( P \) for this 3-node internet.
[ P ]
Task 02: Verification
Show that this matrix is regular. Calculate \( P^2 \) or explain the connectivity.
Steady State Ranking
Calculate the stationary distribution vector \( \mathbf{\pi} = [x, y, z] \) using algebra. This vector represents the "Rank" of each page.
3. Solve the system \( [x, y, z] P = [x, y, z] \) and \( x + y + z = 1 \).
Page A Score
Page B Score
Page C Score
Which page is the search result winner?
Random Processes Final Test Final Mastery Assessment
System Mastery
Stochastic Processes & Stationarity
Name:
Score:
01 Classification & Classification
1. Define a "Regular Markov Chain" and explain its significance regarding the initial state of a system.
2. Match the matrix type to its property:
A. Regular Matrix
B. Absorbing Matrix
C. Irreducible but Not Regular
(____) Oscillates forever without settling.
(____) Always settles to a unique steady state.
(____) Has states you can never leave.
02 The Equilibrium Solution
Find the stationary distribution \( \mathbf{\pi} \) for the transition matrix \( P \). Round values to 3 decimal places.
\[ P = \begin{bmatrix} 0.2 & 0.8 \\ 0.6 & 0.4 \end{bmatrix} \]
Show your work (Systems of Equations)
\(\pi_1 = \) ________
\(\pi_2 = \) ________
03 The Labyrinth (Case Study)
A mouse is in a maze with 3 rooms. Room 3 has cheese (it stays there). In Room 1, it moves to Room 2 with prob 0.7 or stays in Room 1. In Room 2, it moves to Room 3 with prob 0.4 or Room 1 with prob 0.6.
\[ M = \begin{bmatrix} 0.3 & 0.7 & 0 \\ 0.6 & 0 & 0.4 \\ 0 & 0 & 1 \end{bmatrix} \]
a. Is this an absorbing chain? Identify the absorbing state(s).
b. Write the canonical form sub-matrices \( Q \) and \( R \).
Q =
R =
c. Calculate the Fundamental Matrix \( N = (I - Q)^{-1} \).
Critical Thinking Challenge:
How many total steps, on average, will the mouse take before reaching the cheese if it starts in Room 1?
________ Steps
Unit Solutions Manual Solutions & Grading Guide
Sequence: System Equilibrium and Random Processes
Teacher Resource
Lesson 01: Regular Chain Simulations
Part 1: Identifying Regularity
Matrix A: Regular. \( A^2 = \begin{bmatrix} 0.75 & 0.25 \\ 0.5 & 0.5 \end{bmatrix} \). All entries \( > 0 \).
Matrix B: Not Regular. It is an absorbing chain (State 1 is a trap). \( B^k \) will always have a 0 in the top right.
Part 2: Coffee Matrix T
\( \mathbf{v}_1 = [0.8, 0.2] \)
\( \mathbf{v}_2 = [0.72, 0.28] \)
\( \mathbf{v}_3 = [0.688, 0.312] \)
Prediction: Both paths converge to \( [0.667, 0.333] \) or \( [2/3, 1/3] \).
Lesson 02: Equilibrium Equations
Scenario 1: Population Migration
System: \( 0.85x + 0.1y = x \) and \( 0.15x + 0.9y = y \). Both simplify to \( 0.15x = 0.1y \Rightarrow 3x = 2y \).
Normalization: \( x + 1.5x = 1 \Rightarrow 2.5x = 1 \Rightarrow x = 0.4 \).
Solution: City = 40%, Suburbs = 60%
The 3x3 Challenge (Matrix M)
Eqs: \( 0.5x + 0.2y = x \); \( 0.5x + 0.6y + 0.4z = y \); \( 0.2y + 0.6z = z \).
From Eq1: \( 0.2y = 0.5x \Rightarrow x = 0.4y \). From Eq3: \( 0.2y = 0.4z \Rightarrow z = 0.5y \).
Sum: \( 0.4y + y + 0.5y = 1 \Rightarrow 1.9y = 1 \Rightarrow y = 10/19 \approx 0.526 \).
Solution: [4/19, 10/19, 5/19] or [0.211, 0.526, 0.263]
Lesson 03: Gambler's Ruin / Insurance
Canonical Form (Matrix P)
Rearrange states: L (1), A (2), D (3). \( Q = \begin{bmatrix} 0.8 & 0.1 \\ 0.3 & 0.5 \end{bmatrix} \), \( R = \begin{bmatrix} 0.1 \\ 0.2 \end{bmatrix} \).
Fundamental Matrix N
\( I - Q = \begin{bmatrix} 0.2 & -0.1 \\ -0.3 & 0.5 \end{bmatrix} \). Determinant = \( (0.2)(0.5) - (-0.1)(-0.3) = 0.1 - 0.03 = 0.07 \).
\( N = \frac{1}{0.07} \begin{bmatrix} 0.5 & 0.1 \\ 0.3 & 0.2 \end{bmatrix} = \begin{bmatrix} 7.14 & 1.43 \\ 4.29 & 2.86 \end{bmatrix} \).
Active Time: 7.14 + 1.43 = 8.57 years.
Lesson 05: Final Mastery Assessment
Theory: Regular chains reach a unique limiting distribution regardless of starting state. Oscillating/cyclic or absorbing chains do not.
Equilibrium: \( 0.2x + 0.6y = x \Rightarrow 0.6y = 0.8x \Rightarrow y = 4/3 x \). \( x + 4/3x = 1 \Rightarrow 7/3x = 1 \). \(\pi = [3/7, 4/7] \approx [0.429, 0.571]\).
Labyrinth: \( Q = \begin{bmatrix} 0.3 & 0.7 \\ 0.6 & 0 \end{bmatrix} \). \( I-Q = \begin{bmatrix} 0.7 & -0.7 \\ -0.6 & 1 \end{bmatrix} \). \( det = 0.7 - 0.42 = 0.28 \).
\( N = \frac{1}{0.28} \begin{bmatrix} 1 & 0.7 \\ 0.6 & 0.7 \end{bmatrix} = \begin{bmatrix} 3.57 & 2.5 \\ 2.14 & 2.5 \end{bmatrix} \).
