Markov Chains: Predicting the Future from the Present

The Game That Doesn't Care How You Got There

Snakes and Ladders began life as an Indian board game called Moksha Patam (also known as Gyan Chaupar), a dice game with a moral map of virtues and vices, long before it was repackaged in Victorian England as the version sold in toy shops today. Play one round and notice something odd about how it works. You are sitting on square 47. Where you land next depends only on two things: the square you are on right now, and the number your die shows. It does not matter whether you got to square 47 by climbing a ladder from square 29, or by a plain roll from square 44, or by sliding down a snake from square 62. Two players who arrive at square 47 by completely different routes have exactly the same odds for what happens next.

That single property — the future depends on the present, not on the route you took to get to the present — is called the Markov property, and a random process that has it is a Markov chain. It sounds almost too simple to be useful. It is, in fact, one of the most productive ideas in probability, and it quietly runs things you use every week: the predictive text on your phone, the algorithm that first made Google's search results useful, weather forecasting models, and the way insurers and geneticists model transitions between states over time. This chapter builds the idea from scratch, gives you the matrix machinery to compute with it, and is honest about where the simplicity does and does not hold up.

Making It Precise: States, Sequences, and the Markov Property

Start with a system that occupies one of a fixed set of states at each tick of a clock. In Snakes and Ladders the states are the squares 1 to 100. Write X₀ for the state at time 0, X₁ for the state at time 1, X₂ at time 2, and so on — a sequence of random variables, one per time step, each taking a value from the same fixed list of states.

A process is a (first-order, time-homogeneous) Markov chain if, for every time n and every possible sequence of past states, the conditional probability of the next state satisfies:

P(X_n+1 = j | X_n = i, X_n−1 = i_n−1, …, X₀ = i₀) = P(X_n+1 = j | X_n = i) = p_ij

Read the left side first: "given everything I know about the entire history — every state visited from time 0 up to now." Read the right side: "given only the current state." The Markov property says these two conditional probabilities are equal — the entire left-hand history collapses down to just X_n without losing any predictive power. The number p_ij is called a transition probability: the chance of moving to state j given that you are currently in state i. "Time-homogeneous" means p_ij is the same number no matter which time step n you are at — the rule of the game does not change over time, only the state does. Every example in this chapter is time-homogeneous unless said otherwise.

Chennai's Weather: Building a Transition Matrix

Weather is the textbook Markov example for a good reason: whether tomorrow is sunny or rainy is influenced far more by today's weather than by what happened three weeks ago. Suppose, purely as an illustrative model (not a real meteorological statistic), that during a particular spell in Chennai the weather behaves like this: if today is Sunny, there is a 0.7 chance tomorrow stays Sunny and a 0.3 chance it turns Rainy; if today is Rainy, there is a 0.4 chance tomorrow turns Sunny and a 0.6 chance it stays Rainy. Two states — call them S and R — and four numbers completely describe the model.

These four numbers are collected into a transition matrix P, where row i holds the probabilities of leaving state i and column j holds the probabilities of arriving at state j:

Two properties always hold for a transition matrix, and both are worth checking as a sanity test on any Markov model you build: every entry is between 0 and 1 (it's a probability), and every row sums to exactly 1 (from any given state, the chain must go somewhere, possibly back to itself — the row lists a complete probability distribution over "what happens next"). Check the example: 0.7 + 0.3 = 1, and 0.4 + 0.6 = 1. Good.

State Vectors and One-Step Prediction

Instead of tracking a single certain state, track a probability distribution over states — a row vector π = [π_S, π_R] where π_S is the probability the chain is currently Sunny and π_R the probability it is Rainy (π_S + π_R = 1). If today is known to be Sunny with certainty, π₀ = [1, 0].

To get tomorrow's distribution, multiply the row vector by the transition matrix: π₁ = π₀P. This is ordinary matrix multiplication — if you haven't formally met it yet, here is exactly what it does: the j-th entry of π₁ is the sum, over every current state i, of (probability of being in i) × (probability of moving from i to j). For our two states:

π₁[Sunny] = π₀[S]·P[S→S] + π₀[R]·P[R→S] = 1×0.7 + 0×0.4 = 0.7
π₁[Rainy] = π₀[S]·P[S→R] + π₀[R]·P[R→R] = 1×0.3 + 0×0.6 = 0.3

So π₁ = [0.7, 0.3] — unsurprising, it's just row one of P, because starting from certainty in one state, one step later you land exactly on that state's row of transition probabilities. The vector-times-matrix machinery becomes essential once the starting distribution is not a certainty, or once you go more than one step.

Two, Three, n Steps Ahead: the Chapman–Kolmogorov Idea

What's the probability of being Sunny two days from now, given today is Sunny? You cannot skip day 1. To be Sunny on day 2, the chain must be in some state on day 1 (Sunny or Rainy) and then transition from there to Sunny on day 2. Summing over that intermediate state:

P(X₂=S | X₀=S) = P(X₁=S|X₀=S)·P(X₂=S|X₁=S) + P(X₁=R|X₀=S)·P(X₂=S|X₁=R)

This is exactly the rule for matrix multiplication again — each two-step transition probability is a sum of products over an intermediate state. In general, the n-step transition matrix is simply P multiplied by itself n times: P⁽ⁿ⁾ = Pⁿ. This identity (splitting an n-step move into a first leg and a remaining leg, summed over every possible midpoint state) is called the Chapman–Kolmogorov equation, and it is the entire reason Markov chains reduce to matrix algebra: predicting arbitrarily far into the future is just repeated matrix multiplication, never anything more complicated, no matter how many states the chain has.

Applying this to π rather than a single starting certainty: π_n = π₀Pⁿ = π_n−1P. Compute it iteratively, one day at a time, starting from π₀ = [1, 0]:

def multiply(vec, matrix):
    return [sum(vec[i] * matrix[i][j] for i in range(len(vec)))
            for j in range(len(matrix[0]))]

P = [[0.7, 0.3],
     [0.4, 0.6]]

state = [1, 0]  # today: Sunny with certainty
for day in range(1, 4):
    state = multiply(state, P)
    print(f"Day {day}: Sunny={state[0]:.3f}, Rainy={state[1]:.3f}")

Trace it by hand to confirm what the computer will print. Day 1: state = [1×0.7+0×0.4, 1×0.3+0×0.6] = [0.7, 0.3]. Day 2: state = [0.7×0.7+0.3×0.4, 0.7×0.3+0.3×0.6] = [0.49+0.12, 0.21+0.18] = [0.61, 0.39]. Day 3: state = [0.61×0.7+0.39×0.4, 0.61×0.3+0.39×0.6] = [0.427+0.156, 0.183+0.234] = [0.583, 0.417]. So the program prints:

Day 1: Sunny=0.700, Rainy=0.300
Day 2: Sunny=0.610, Rainy=0.390
Day 3: Sunny=0.583, Rainy=0.417

Notice the probability of Sunny is drifting downward each day — 0.700, then 0.610, then 0.583 — the sharp certainty from day 0 is fading. That drift is heading somewhere specific, and finding out where is the next question.

Where the Weather Settles: the Stationary Distribution

Keep iterating and the numbers keep moving, but by smaller and smaller amounts: day 4 gives [0.575, 0.425]. Eventually the distribution stops changing from one day to the next — this limiting distribution is called the stationary distribution, written π*, and it satisfies π*P = π* (apply one more transition and you get back exactly what you started with).

Solve for it algebraically instead of iterating forever. Let π* = [a, b] with a + b = 1. The equation π*P = π* gives, for the Sunny column:

0.7a + 0.4b = a  ⟹  0.4b = 0.3a  ⟹  a = (4/3)b

Substitute into a + b = 1: (4/3)b + b = 1 ⟹ (7/3)b = 1 ⟹ b = 3/7, so a = 4/7. That gives π* = [4/7, 3/7] ≈ [0.571, 0.429]. Compare this to the iteration: 0.700 → 0.610 → 0.583 → 0.575 → … visibly closing in on 0.571 from above, exactly as the algebra predicts. In the long run, this hypothetical model says Chennai is Sunny on 4 out of every 7 days and Rainy on 3 out of every 7 days — a fact that no longer depends on whether today happens to be Sunny or Rainy. Where you start only affects the short term; the transition rule itself determines the long-run behaviour.

Why "Present Only" Isn't As Limiting As It Sounds

A fair objection: real weather surely depends on more than just yesterday — a three-day heatwave behaves differently going forward than a single hot day after a cool spell. Does that break the Markov approach? No — because the definition of "state" is entirely up to you.

If tomorrow's weather genuinely depends on both today's and yesterday's weather, redefine the state as the pair (yesterday, today) instead of just today. With two underlying weather values there are now four such pairs — (S,S), (S,R), (R,S), (R,R) — and the chain hops between these four states. Crucially, this new four-state chain is still first-order Markov: the next pair depends only on the current pair, because the current pair already contains everything from the last two days that matters. Any process that depends on a fixed, finite window of past states can always be rewritten as a first-order Markov chain by folding that window into a bigger state. This is exactly the trick language models use to go from "depends on the previous word" (bigram) to "depends on the previous two words" (trigram) — you'll see it in the next section. The Markov property is not a claim that the past doesn't matter; it's a claim that once you've defined the state correctly, the past that matters is already packed inside it.

A Second Example: How Predictive Text Guesses Your Next Word

Older-generation predictive keyboards (and the classic n-gram language models that preceded modern transformer-based ones like GPT) use exactly this idea. States are words. A transition probability P(next word | current word) is estimated from how often that pair of words occurs consecutively in a large body of text. This is a first-order ("bigram") Markov chain over the vocabulary — guessing the next word using only the current word, discarding everything said earlier in the sentence.

transitions = {
    "I": {"am": 0.8, "want": 0.2},
    "am": {"going": 0.6, "happy": 0.4},
    "going": {"to": 1.0},
}

word = "I"
sentence = [word]
for _ in range(3):
    next_word = max(transitions[word], key=transitions[word].get)
    sentence.append(next_word)
    word = next_word

print(" ".join(sentence))

Trace it: word starts as "I". Loop 1 looks up transitions["I"] = {"am": 0.8, "want": 0.2} and picks the higher-probability key, "am" (0.8 > 0.2); sentence becomes ["I", "am"]. Loop 2 looks up transitions["am"] = {"going": 0.6, "happy": 0.4} and picks "going" (0.6 > 0.4); sentence becomes ["I", "am", "going"]. Loop 3 looks up transitions["going"] = {"to": 1.0} and picks "to"; sentence becomes ["I", "am", "going", "to"]. The program prints:

I am going to

This "always pick the single most likely next word" strategy is called greedy decoding, and it is a real simplification of what production keyboards do (they typically keep several candidate continuations alive at once and also weight by how often you personally use each word) — but the underlying mechanism, that the next-word probability is a function of the current state, is genuinely how bigram language models work. It's also worth being precise about the limit: modern large language models are not simple Markov chains over words — they condition on the entire preceding context via attention, not on a fixed small window folded into a state. The Markov chain is the ancestor of that idea, not a description of how today's chatbots work.

Application: PageRank

Before Google was a company, Larry Page and Sergey Brin, then researchers at Stanford, described an algorithm called PageRank in a 1998 paper for ranking web pages. Picture a "random surfer" who, from whatever page they're on, clicks a random outgoing link to move to the next page — the sequence of pages visited is a Markov chain, with states being individual web pages and transition probabilities built from the link structure of the web. A page's long-run importance score is precisely the stationary distribution of that chain: the fraction of time the random surfer spends on that page if they kept clicking forever. The same steady-state idea you solved algebraically for two weather states — just scaled up to billions of states — was the mathematical core of the search engine that made Google's early results dramatically better than its competitors'.

Common Misconceptions, Corrected

"A Markov chain has no memory, so it can't capture anything that depends on the past." This gets the property backwards. The chain's future depends on the past entirely — through the current state. The Markov property doesn't discard history; it claims that the current state is a complete summary of whatever history is relevant, so nothing more needs to be carried along separately. As the previous section showed, if a single day of weather isn't enough of a summary, you fold more days into the state definition until it is.

"The transition matrix tells you exactly what happens next." It tells you a probability distribution over what happens next, never a certainty (unless some p_ij = 1). Given Sunny today, you cannot say tomorrow will be Rainy or will be Sunny — you can only say there's a 0.3 chance of Rainy. Individual futures generated by a Markov chain are genuinely random; only the distribution of outcomes is exactly predictable.

"Once the stationary distribution is reached, the state stops changing." The weather in the stationary regime still flips between Sunny and Rainy every day exactly as before — what has stopped changing is the probability of each state, not the sequence of actual outcomes. "Stationary" describes the distribution settling down, not the chain freezing in place.

Exam Connections

Markov chains themselves sit just outside the core CBSE Class 10–12 and JEE syllabi, but every tool this chapter used is squarely inside them, and recognising the connection pays off directly. The Markov property is a statement about conditional probability — P(A|B) — the exact object built up in CBSE Class 12 Probability, including its use with Bayes' theorem. The transition matrix and its powers are ordinary matrix multiplication from the Class 12 Matrices chapter; computing π_n = π₀Pⁿ by hand is direct practice for JEE Main/Advanced matrix questions. Solving πP = π by treating it as a pair of simultaneous linear equations is standard JEE/BITSAT algebra. In combinatorics-flavoured KVPY and Olympiad problem sets, "random walk" and "gambler's ruin" questions — a walker on a number line moving left or right with fixed probabilities, or a game ending once a player's money hits zero — are Markov chains in disguise, often solved by setting up exactly this kind of stationary or absorption equation. And at the GATE / undergraduate-CS level, Markov chains generalise directly into Hidden Markov Models (used in speech recognition) and Markov Decision Processes (the mathematical backbone of reinforcement learning) — both built by adding one extra layer onto precisely the machinery in this chapter.

Absorbing States: Back to the Board

One more idea completes the picture, and it brings us back to where we started. In Snakes and Ladders, square 100 behaves differently from every other square: once you land there, the game ends — you never leave. In transition-matrix terms, p_100,100 = 1 and every other entry in row 100 is 0. A state with this property (probability 1 of staying, probability 0 of leaving) is called an absorbing state. Not every Markov chain has one — the weather chain doesn't, which is exactly why it has a nontrivial stationary distribution instead of eventually freezing at a single square. Whether a chain settles into a fixed distribution that keeps circulating between states, or gets permanently trapped in one absorbing state, is itself something the transition matrix determines completely — which is the real punchline of this whole chapter. A short table of numbers, checked once for non-negativity and row-sums-to-one, is enough to tell you everything about how the system behaves arbitrarily far into the future.

Check Your Understanding

• A student's daily study habit is modelled as a 2-state chain: Focused (F) and Distracted (D), with P(F→F)=0.6, P(F→D)=0.4, P(D→F)=0.5, P(D→D)=0.5. Write out the transition matrix and confirm both rows sum to 1.
• Using that matrix, if the student is Focused today (π₀ = [1,0]), compute π₁ and π₂ by hand, the same way π₁ and π₂ were computed for the weather chain.
• Solve π*P = π* algebraically for the study-habit chain to find its stationary distribution. (Set up 0.6a+0.5b=a with a+b=1, exactly as done for the weather example.)
• Explain, in one or two sentences and without redoing the algebra, why the study-habit chain's stationary distribution does not depend on whether the student happened to be Focused or Distracted on day 0.
• A trigram predictive-text model predicts the next word from the previous two words rather than one. Using the idea from "Why Present Only Isn't As Limiting As It Sounds," describe precisely what the "state" would need to be for a trigram model to qualify as a first-order Markov chain.
• Is square 100 in Snakes and Ladders the only possible absorbing state in a board game modelled this way? Give one other example of a real process (not from this chapter) that has a natural absorbing state, and identify what that state is.

Summary

A Markov chain is a sequence of states where the probability of the next state depends only on the current one, captured formally by P(X_n+1=j | X_n=i, past) = P(X_n+1=j | X_n=i) = p_ij. These transition probabilities form a matrix P whose rows are probability distributions (non-negative, summing to 1). A probability distribution over states, π, evolves one step at a time by right-multiplication: π_n+1 = π_nP, and n steps at once by π_n = π₀Pⁿ — the Chapman–Kolmogorov equation, which is nothing more than matrix multiplication applied repeatedly. Many chains converge to a stationary distribution π* satisfying π*P = π*, found by solving simultaneous linear equations; this long-run distribution is independent of the starting state and, in applications like PageRank, becomes the very quantity you're trying to compute. States that depend on more history than "just the present" can be folded into a bigger, still-first-order state (as with weather pairs or trigram word models), and chains can also contain absorbing states from which there is no escape — the two very different long-run behaviours (settling into circulation versus getting permanently trapped) are both fully determined by nothing more than the transition matrix itself.

Think About It

Think about this: How would you explain markov chains: predicting the future from the present to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.