Markov Chains: States, Transitions, Steady-State & Applications

What is a Markov Chain?

A Markov Chain is a mathematical model describing a sequence of possible events where the probability of each event depends only on the state attained in the previous event. This is called the Markov property or memorylessness.

Key Terms:

• State: A distinct condition or configuration of the system (e.g., "busy," "idle," "broken").
• Transition: Movement from one state to another, governed by probabilities.
• Transition Probability Matrix (P): A square matrix where $P_{ij}$ = probability of moving from state $i$ to state $j$.
• Steady-State Probabilities: Long-term probabilities of being in each state (denoted by vector $\pi$).

How Markov Chains Work: The Markov Property

The Markov property states: $$P(X_{n+1}=x|X_n=x_n,X_{n-1}=x_{n-1},\dots )=P(X_{n+1}=x|X_n=x_n)$$ Example: Predicting weather tomorrow depends only on today’s weather, not yesterday’s.

Visualizing States and Transitions

graph TD
    A["State 1 (e.g., Busy)"] -->|"0.3"| B["State 2 (e.g., Idle)"]
    A -->|"0.7"| A
    B -->|"0.4"| A
    B -->|"0.6"| B

This is a state transition diagram for a simple two-state Markov Chain (e.g., a server being busy or idle).

Transition Probability Matrix

For the above diagram, the transition matrix $P$ is: $$P=\left[\begin{array}{cc}0.7& 0.3\\ 0.4& 0.6\end{array}\right]$$

• Row 1: From State 1 (Busy), 70% chance to stay Busy, 30% to move to Idle.
• Row 2: From State 2 (Idle), 40% chance to become Busy, 60% to stay Idle.

Steady-State Probabilities

The steady-state vector $\pi =[{\pi }_1,{\pi }_2]$ satisfies: $$\pi P=\pi \text{and}\sum {\pi }_i=1$$ For our example: $${\pi }_1=0.57,{\pi }_2=0.43$$ Interpretation: In the long run, the server is 57% Busy and 43% Idle.

Worked Example: Traffic Light Cycle

Assume a traffic light cycles between Red (R), Yellow (Y), and Green (G) with the following transition probabilities:

• From R: 80% to Y, 20% stays R.
• From Y: 100% to G.
• From G: 60% to R, 40% stays G.

Step 1: Build the Transition Matrix

$$P=\left[\begin{array}{ccc}0.2& 0.8& 0\\ 0& 0& 1\\ 0.6& 0& 0.4\end{array}\right]$$ (Rows: R → Y → G; Columns: R, Y, G)

Step 2: Find Steady-State Probabilities

Solve $\pi P=\pi$: $${\pi }_1=0.24,{\pi }_2=0.16,{\pi }_3=0.60$$ Result: The light is 60% Green, 24% Red, and 16% Yellow in the long run.

Applications of Markov Chains

1. Queueing Systems (e.g., Daraz Order Processing)

• States: "Order Received," "Processing," "Shipped," "Delivered."
• Transitions: Orders move between states based on probabilities (e.g., 90% of "Processing" orders ship within an hour).
• Use: Predict average wait times or optimize staffing.

2. Finance (e.g., Stock Price Movements)

• States: "Up," "Down," "Stable."
• Transitions: Probabilities of price changes (e.g., 60% chance to stay "Up" if currently "Up").
• Use: Model long-term trends or risk assessment.

3. AI and Natural Language Processing (e.g., WhatsApp Chatbots)

• States: User inputs (e.g., "Hello," "Order," "Cancel").
• Transitions: Probabilities of moving to the next state (e.g., 70% chance "Hello" leads to "How can I help?").
• Use: Predict user behavior or improve response accuracy.

In the Real World

1. eSewa (Nepal):

   • Idea: Markov Chains model user transitions between "Browsing," "Adding to Cart," and "Checkout."
   • How: Predicts peak checkout times to allocate servers efficiently.

2. Ncell Network Congestion:

   • Idea: States = "Low Traffic," "Medium Traffic," "High Traffic."
   • How: Transition probabilities help forecast when to add more towers.

3. Khalti Loan Default Risk:

   • Idea: Borrower states = "Good," "At Risk," "Default."
   • How: Steady-state probabilities estimate long-term default rates for loan approvals.

Advantages and Disadvantages

Exam Tip

Markov Chains are frequently tested in three ways:

1. Definitions: Know the Markov property and steady-state conditions.
2. Calculations: Given a transition matrix, compute steady-state probabilities (use $\pi P=\pi$).
3. Applications: Link Markov Chains to real-world scenarios (e.g., queues, finance). Always draw a state diagram in your answer—it’s worth marks!

Visual: Markov Chain for a Simple Queue

graph TD
    A["Idle"] -->|"0.7"| A
    A -->|"0.3"| B["Busy"]
    B -->|"0.4"| A
    B -->|"0.6"| B

Real Picture: Traffic Light Controller (Physical Implementation)

Worked Example: Bank Loan Approval (Steady-State)

A bank classifies loans as:

• State 1 (Good): 60% stay Good, 40% default.
• State 2 (Default): All loans default (absorbing state).

Transition Matrix: $$P=\left[\begin{array}{cc}0.6& 0.4\\ 0& 1\end{array}\right]$$

Steady-State: $${\pi }_1=0,{\pi }_2=1$$ Interpretation: Eventually, all loans default (State 2 is absorbing). This models a high-risk portfolio where defaults dominate over time.

Key Formulas to Remember

1. Steady-State Equation: $$\pi P=\pi$$
2. Normalization: $$\sum _i{\pi }_i=1$$
3. Transition Probability: $$P_{ij}=P(X_{n+1}=j|X_n=i)$$