Markov Chains: States, Transitions & Applications

TAKEAWAYS:

• Markov Chains model systems where future states depend only on the current state (Markov Property), ignoring history.
• A transition matrix $P$ encodes probabilities of moving between states, with rows summing to 1.
• Steady-state probabilities (π) solve $\pi P=\pi$ and model long-term behavior (e.g., equilibrium traffic flow).
• Applications include page-rank algorithms (Google), weather forecasting, and financial risk modeling.
• Discrete-time chains (e.g., daily stock prices) vs. continuous-time (e.g., radioactive decay) differ in state evolution.
• Exam focus: Derive transition matrices, compute steady states, and interpret real-world traces (e.g., customer loyalty in eSewa).

1. What Are Markov Chains?

A Markov Chain is a stochastic (random) process that moves between states over discrete time steps, where the next state depends only on the current state. This is called the Markov Property: $$P(X_{n+1}=x\mid X_n=x_n,X_{n-1}=x_{n-1},\dots )=P(X_{n+1}=x\mid X_n=x_n).$$ Key Idea: The future is independent of the past given the present.

Visual: State Space as a Graph

graph TD
    A["State 1"] -->|"0.3"| B["State 2"]
    A -->|"0.7"| C["State 3"]
    B -->|"0.5"| A
    B -->|"0.5"| C
    C -->|"0.2"| A
    C -->|"0.8"| B

Caption: A 3-state Markov Chain with transition probabilities. Bold arrows show a possible path: $A\to C\to B$.

2. Definitions and Notation

• State Space (S): Set of all possible states (e.g., $S=\{1,2,3\}$).
• Transition Probability: $P_{ij}=P(X_{n+1}=j\mid X_n=i)$.
• Transition Matrix (P): Square matrix where $P_{ij}$ is the probability of moving from state $i$ to $j$. Example: $$P=\left[\begin{array}{cc}0.3& 0.7\\ 0.5& 0.5\\ 0.2& 0.8\end{array}\right]$$ Rows sum to 1 (probability conservation).

Real Picture: Markov Chain in eSewa

3. How Markov Chains Work: Worked Example

Scenario: A customer using Khalti for payments has 3 states:

1. Active User (uses Khalti weekly),
2. Inactive User (no transactions for a month),
3. Churned (deleted app).

Given transition matrix: $$P=\left[\begin{array}{ccc}0.6& 0.3& 0.1\\ 0.2& 0.5& 0.3\\ 0& 0& 1\end{array}\right]$$ Question: If 100 users start as Active, what’s the distribution after 2 weeks?

Step-by-Step Trace

1. Initial State Vector: ${\pi }_0=[1,0,0]$ (all users active).
2. After 1 Week (${\pi }_1={\pi }_{0}P$): $${\pi }_1=[0.6,0.3,0.1]$$
   • 60 users stay active, 30 become inactive, 10 churn.
3. After 2 Weeks (${\pi }_2={\pi }_{1}P$): $${\pi }_2=[0.6\times 0.6+0.3\times 0.2+0.1\times 0,0.6\times 0.3+0.3\times 0.5+0.1\times 0,\dots ]$$ $${\pi }_2=[0.42,0.39,0.19]$$
   • 42 active, 39 inactive, 19 churned.

Visual: State Evolution

graph LR
    A["Week 0: 100 Active"] --> B["Week 1: 60A, 30I, 10C"]
    B --> C["Week 2: 42A, 39I, 19C"]

Caption: User distribution over 2 weeks. Churn grows due to high transition from Inactive to Churned.

4. Steady-State Probabilities

In the long run, the state distribution stabilizes to $\pi$, where: $$\pi P=\pi \text{and}\sum {\pi }_i=1.$$ For Khalti Example: Solve $\pi P=\pi$: $$\begin{gathered} {\pi }_1=0.6{\pi }_1+0.2{\pi }_2+0{\pi }_3 \\ {\pi }_2=0.3{\pi }_1+0.5{\pi }_2+0{\pi }_3 \\ {\pi }_3=0.1{\pi }_1+0.3{\pi }_2+1{\pi }_3 \end{gathered}$$ Solution: $$\pi =[0.2857,0.3571,0.3571]$$ Interpretation:

• 28.57% of users stay active long-term.
• 35.71% churn or become inactive permanently.

Real World: Google’s PageRank

Google’s PageRank algorithm uses Markov Chains to rank web pages. Each page is a state, and links are transitions. The steady-state vector $\pi$ gives the "importance" of each page.

• Example: If Page A links to Page B (probability 0.8), and Page B links back to A (probability 0.3), the transition matrix encodes these probabilities.
• Result: Pages with more "incoming transitions" (links) have higher ${\pi }_i$.

5. Types of Markov Chains

Visual: Irreducible vs. Reducible Chain

graph TD
    A["Irreducible"] --> B["All states reachable"]
    C["Reducible"] --> D["States 1 & 2 communicate"]
    D --> E["State 3 isolated"]

Caption: Irreducible chains (left) allow transitions between all states, while reducible chains (right) have isolated states (e.g., churned users in Khalti).

6. Applications in Nepal and Globally

In Nepal

1. Traffic Flow Modeling (Kathmandu)

   • States: "Moving," "Idle," "Red Light."
   • Transitions: Probability of stopping at a red light or getting stuck in traffic.
   • Use Case: Optimize signal timings using steady-state probabilities to reduce congestion.

2. NEPSE Stock Market

   • States: "Bull Market," "Bear Market," "Stable."
   • Transitions: Historical data shows 60% chance of staying in the same state, 30% chance of switching.
   • Use Case: Predict long-term trends for investment strategies.

3. Pathao Driver Availability

   • States: "Available," "On Trip," "Offline."
   • Transitions: Drivers go offline after 3 trips (80% probability).
   • Use Case: Estimate driver supply to meet demand spikes.

Global Examples

1. YouTube Recommendation System

   • States: "Watching Video," "Paused," "Closed."
   • Transitions: Probability of clicking a suggested video (0.4) vs. closing the app (0.1).
   • Use Case: Maximize watch time using Markov rewards.

2. Netflix Binge-Watching

   • States: "Watching Episode," "Paused," "Switched Show."
   • Transitions: 70% chance of watching the next episode if engaged.
   • Use Case: Personalize recommendations based on steady-state engagement.

3. Bank Loan Default Prediction (Global Banks)

   • States: "Good Credit," "Risky," "Default."
   • Transitions: Historical data shows 5% of "Risky" customers default monthly.
   • Use Case: Adjust interest rates dynamically (e.g., higher rates for "Risky" states).

7. Advantages and Limitations

8. Worked Example: NTC Call Center

Scenario: NTC’s call center has 3 states:

1. Idle (no calls),
2. Handling Call,
3. Queueing.

Transition matrix: $$P=\left[\begin{array}{ccc}0.1& 0.6& 0.3\\ 0.4& 0.3& 0.3\\ 0.2& 0.5& 0.3\end{array}\right]$$ Question: What’s the steady-state probability of the system being Idle?

Solution Steps

1. Set up equations for $\pi =[{\pi }_1,{\pi }_2,{\pi }_3]$: $$\begin{gathered} {\pi }_1=0.1{\pi }_1+0.4{\pi }_2+0.2{\pi }_3 \\ {\pi }_2=0.6{\pi }_1+0.3{\pi }_2+0.5{\pi }_3 \\ {\pi }_3=0.3{\pi }_1+0.3{\pi }_2+0.3{\pi }_3 \end{gathered}$$
2. Solve with ${\pi }_1+{\pi }_2+{\pi }_3=1$.
3. Result: $\pi =[0.25,0.45,0.30]$.
   • 25% chance the call center is idle long-term.

Real Picture: Call Center Dashboard

Exam Tip

1. Derive Transition Matrices:

   • Given a scenario (e.g., Khalti users), always write the matrix first.
   • Example: If 30% of active users churn monthly, set $P_{13}=0.3$.

2. Steady-State Questions:

   • Solve $\pi P=\pi$ systematically:
     1. Write equations for each state.
     2. Use $\sum {\pi }_i=1$ to eliminate one variable.
     3. Solve the remaining system.
   • Shortcut: For 2-state chains, use ${\pi }_1=\frac{1-P_{21}}{1-P_{12}-P_{21}}$.

3. Interpretation:

   • Steady-state: "In the long run, what fraction of time is the system in state X?"
   • Transient: "What’s the probability of being in state X after 3 steps?"

4. Common Pitfalls:

   • Forgetting rows sum to 1 in $P$.
   • Misapplying the Markov Property (e.g., assuming future depends on past states).
   • Always check if the chain is irreducible (no isolated states).

5. Graphical Help:

   • Draw the state diagram before writing equations.
   • Label arrows with probabilities to avoid errors.

Summary Checklist

• Can you write the transition matrix for a given scenario?
• Do you know how to compute steady-state probabilities?
• Can you distinguish between discrete-time and continuous-time chains?
• Do you recognize Markov Chains in real-world systems (e.g., Google PageRank)?
• Can you interpret steady-state results (e.g., "25% idle time" for NTC)?