The dice on a Snakes and Ladders board don't care how you got here
Play Snakes and Ladders with a younger cousin and ask them a strange question mid-game: "Does the die care whether you reached square 47 by climbing a ladder from square 29, or by a run of ordinary rolls from square 40?" The honest answer is no. Whatever happened earlier in the game — every roll, every ladder, every snake bite — is irrelevant to what happens next. All that matters is the single fact of where the token sits right now. The next roll adds a number to your current square, and the game moves on. History is erased the instant a new state is reached.
Now contrast that with something that looks similar but isn't. Your final percentage in a CBSE board exam depends on your entire year's performance — unit tests, half-yearly, pre-boards, the works. Knowing only "today's marks" tells you almost nothing; the whole trajectory matters. That is the opposite situation: a process where the past genuinely has to be carried forward to predict the future.
A Markov chain is the mathematical object built for processes of the first kind — where the present state is a complete summary of everything you need to predict what comes next, and the entire past before that can be thrown away. This single idea, formalised by the Russian mathematician Andrey Markov in 1906, turns out to be one of the most useful modelling tools in probability: it underlies PageRank (the original Google search-ranking algorithm), speech and text prediction, genetics, queueing at a bank counter, and the weather forecast on your phone. This chapter builds the idea from scratch, makes it precise with real computation, and shows you exactly where it shows up in competitive exams.
Making "depends only on now" precise
Let's set up notation carefully, because the whole chapter rests on it. Suppose a system moves through a sequence of states over time — day 0, day 1, day 2, and so on. Let Xn denote the state of the system at time step n. The sequence X0, X1, X2, ... is called a stochastic process — a sequence of random variables evolving over time.
This process is a Markov chain if, for every n and every possible sequence of states, the following holds:
P(Xn+1 = j | Xn = i, Xn-1 = in-1, ..., X0 = i0) = P(Xn+1 = j | Xn = i)
Read the left side out loud: "the probability that the next state is j, given the entire history of states up to and including the current one." Read the right side: "the probability that the next state is j, given only the current state." The Markov property is the claim that these two are equal — every state before Xn can be deleted from the conditioning without changing the probability at all. This is exactly the Snakes and Ladders fact stated as an equation.
Notice what the Markov property does not say: it does not say the next state is independent of the current one. It says the opposite — the next state depends heavily on the current state. What it deletes is dependence on anything older than the current state. This distinction is worth sitting with, because it is the single most common point of confusion, addressed properly in the next section.
Building a real transition model: a two-state weather chain
Formal definitions are empty without a worked model, so let's build one from the ground up. Consider a simplified, illustrative weather model for a monsoon-affected city — the numbers below are a teaching example, not actual IMD data. Each day is classified as one of two states: Rainy (R) or Dry (D). Suppose, from long-run pattern-watching, we settle on these one-day transition probabilities:
- If today is Rainy: probability 0.6 that tomorrow is Rainy, probability 0.4 that tomorrow is Dry.
- If today is Dry: probability 0.3 that tomorrow is Rainy, probability 0.7 that tomorrow is Dry.
Each row of possibilities sums to 1, as it must — starting from a fixed state, the system must land in some state tomorrow. We arrange these four numbers into a grid, called the transition matrix P, with rows indexed by today's state and columns indexed by tomorrow's state, in the fixed order (Rainy, Dry):
Rainy Dry
Rainy [ 0.6 0.4 ]
Dry [ 0.3 0.7 ]Formally, the entry Pij = P(Xn+1 = j | Xn = i). Because these transition probabilities don't change from one day to the next — the same matrix P applies whether we're going from day 3 to day 4 or from day 50 to day 51 — this is called a time-homogeneous Markov chain, which is the version this entire chapter deals with. A matrix whose rows are each non-negative and sum to 1 is called a stochastic matrix; every valid transition matrix is one.
Here is the same information drawn as a state diagram — the standard way to visualise a Markov chain, with a node per state and a labelled directed arrow per transition probability:
The misconception to kill now: "Markov" does not mean "random and unpredictable"
Students who meet Markov chains for the first time often lump them together with independent random trials — coin flips, dice rolls, lottery draws — reasoning that "the future doesn't depend on the past, so it must basically be pure randomness with no pattern." This is exactly backwards, and it's worth being precise about why.
In a sequence of independent coin flips, the probability of heads is 0.5 no matter what the current state is — there is no state at all in any meaningful sense, and every trial is a fresh, unconditioned experiment. In the weather chain above, the very opposite is true: knowing today's state changes tomorrow's probabilities dramatically (0.6 vs 0.3 chance of rain, depending entirely on today). A Markov chain has strong state-to-state dependence — that is the whole content of the model. What it lacks is dependence on anything before the current state. "Memoryless" in the Markov sense means "forgets everything except the last data point," not "has no structure at all." Confusing the two will cost you marks on any question that asks you to justify why a process is or isn't Markov.
Looking two days ahead: the Chapman–Kolmogorov equation
Here is where the Markov property earns its keep computationally. Suppose today (day 0) is Rainy. What is the probability that the day after tomorrow (day 2) is also Rainy? We cannot read this off the one-step matrix directly — we need to account for both possible states tomorrow (day 1) and how each connects to day 2. This is a job for the law of total probability, applied carefully:
P(X2 = R | X0 = R)
= P(X1 = R, X2 = R | X0 = R) + P(X1 = D, X2 = R | X0 = R) [partition over day-1 state]
= P(X1 = R | X0 = R) . P(X2 = R | X1 = R, X0 = R)
+ P(X1 = D | X0 = R) . P(X2 = R | X1 = D, X0 = R) [chain rule]
= P(X1 = R | X0 = R) . P(X2 = R | X1 = R)
+ P(X1 = D | X0 = R) . P(X2 = R | X1 = D) [Markov property drops X0]
= (0.6)(0.6) + (0.4)(0.3)
= 0.36 + 0.12 = 0.48Look closely at the third line — that is the only step where the Markov property was actually used, to erase the "given X0 = R" from inside each term once X1 is already fixed. Without that property, we would have no right to make that deletion, and the calculation would require tracking the entire history. This calculation, done in general, is called the Chapman–Kolmogorov equation, and it has a beautifully compact form once you notice what the arithmetic is doing: multiplying and adding along a row of P and a column of P is exactly matrix multiplication. Concretely, if P(2) denotes the two-step transition matrix, then:
P(2) = P × P = P2
where matrix multiplication is defined, for two 2×2 matrices, by taking the dot product of each row of the first matrix with each column of the second. Let's compute all four entries of P2 by hand, since the (Rainy, Rainy) entry should match 0.48 from above as a check:
P^2[R][R] = 0.6*0.6 + 0.4*0.3 = 0.36 + 0.12 = 0.48 (matches the derivation above)
P^2[R][D] = 0.6*0.4 + 0.4*0.7 = 0.24 + 0.28 = 0.52
P^2[D][R] = 0.3*0.6 + 0.7*0.3 = 0.18 + 0.21 = 0.39
P^2[D][D] = 0.3*0.4 + 0.7*0.7 = 0.12 + 0.49 = 0.61Each row still sums to 1 (0.48+0.52=1, 0.39+0.61=1), which is a good self-check — P2 is itself a valid stochastic matrix, describing two-day-ahead transitions. More generally, the n-step transition probability P(Xn = j | X0 = i) is exactly the (i,j) entry of Pn, the matrix P multiplied by itself n times. This is the single most important computational fact about time-homogeneous Markov chains: all n-step transition probabilities live inside successive powers of one small matrix.
Here is the calculation coded directly, with no library shortcuts, so you can trace exactly what the computer does — it is literally the two dot-products above, done in a loop:
def multiply(A, B):
n, k, m = len(A), len(B), len(B[0])
C = [[0.0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
total = 0.0
for t in range(k):
total += A[i][t] * B[t][j]
C[i][j] = total
return C
P = [[0.6, 0.4],
[0.3, 0.7]]
P2 = multiply(P, P)
print(P2) # [[0.48, 0.52], [0.39, 0.61]] (up to tiny floating-point rounding)Trace it: for C[0][0], t runs over 0 and 1, giving A[0][0]*B[0][0] + A[0][1]*B[1][0] = 0.6*0.6 + 0.4*0.3 = 0.48, exactly the hand computation. The loop structure is doing nothing but the row-times-column dot product, four times.
Where does the chain settle? The stationary distribution
A natural question: if this weather chain runs for a very long time, does the fraction of rainy days settle down to some fixed number, regardless of whether it started on a rainy or dry day? The answer, for this chain, is yes — and finding that number is one of the most useful things you can do with a Markov chain.
A probability distribution π = (πR, πD) over the states is called stationary if applying one more step of the chain leaves it unchanged:
π P = π, with πR + πD = 1
Writing πP = π out entry by entry for our matrix gives two equations (only one is independent, since both come from rows summing to 1):
pi_R = pi_R * 0.6 + pi_D * 0.3
pi_D = pi_R * 0.4 + pi_D * 0.7Take the first equation and collect terms:
pi_R - 0.6*pi_R = 0.3*pi_D
0.4*pi_R = 0.3*pi_D
pi_D = (4/3) * pi_RSubstitute into the normalisation condition πR + πD = 1:
pi_R + (4/3)*pi_R = 1
(7/3) * pi_R = 1
pi_R = 3/7 ≈ 0.4286
pi_D = 4/7 ≈ 0.5714So in the long run, this model predicts roughly 3 rainy days out of every 7, regardless of how the sequence started. This is not a coincidence of arithmetic — it reflects a genuine theorem. Because every entry of P here is strictly positive (from any state you can reach any other state in a single step), this chain is called regular (or ergodic), and for any finite regular Markov chain, a standard theorem guarantees a unique stationary distribution, and further guarantees that Pn converges to it — every row of Pn approaches the same numbers as n grows, no matter which state you began in.
We can watch this convergence happen numerically. Continuing the matrix-power calculation started earlier (P4 = P2 × P2, then P8 = P4 × P4, computed the same dot-product way):
starting from Rainy starting from Dry
n=1 : [0.6000, 0.4000] [0.3000, 0.7000]
n=2 : [0.4800, 0.5200] [0.3900, 0.6100]
n=4 : [0.4332, 0.5668] [0.4251, 0.5749]
n=8 : [0.4286, 0.5714] [0.4285, 0.5715]
stationary: [3/7, 4/7] = [0.4286, 0.5714]By n = 8, the two rows — one starting from Rainy, one from Dry — have become almost indistinguishable, and both sit right on top of the hand-solved stationary distribution (3/7, 4/7). The chain has "forgotten" its starting state entirely, purely through repeated application of the one-step rule. That forgetting is itself a consequence of the Markov property: since only the current state ever matters, and the current state's own influence fades geometrically with each step, the starting point's influence must eventually vanish.
A state that never lets go: absorbing states
Not every Markov chain behaves like the well-mixed weather example. If a state i has Pii = 1 — probability 1 of transitioning to itself — it is called an absorbing state, and once entered, the chain never leaves. The "Game Over" square in many board games, or a "ticket cancelled" status in a booking system, behaves this way: it is a valid state of the system, but a terminal one. Chains containing absorbing states do not have a single, chain-wide stationary distribution the way the regular weather chain does — long-run behaviour instead concentrates entirely on the absorbing states. This is a different (and equally standard) branch of Markov chain theory, worth knowing exists even though the full analysis is beyond this chapter.
Where this shows up in your exams
- CBSE Class 12 boards / JEE Main / BITSAT: Markov chains are not named explicitly in these syllabi, but multi-stage conditional-probability "tree diagram" problems — where an event on day/stage 2 depends on which branch was taken at stage 1 — are structurally two- or three-state Markov chains. Recognising the state-transition skeleton underneath a wordy tree-diagram problem is often the fastest route to the answer.
- KVPY / Math Olympiad: problems about random walks on a number line or a graph, or repeated-game probability questions ("what's the probability of returning to the start after n moves"), are Markov chains in their native form — the transition matrix approach shown here generalises directly to random walks.
- GATE (Engineering Mathematics — Probability and Statistics, applies across CS, EE, and several other GATE papers): Markov chains and stochastic processes appear as a named, examinable topic, typically as exactly this kind of transition-matrix and stationary-distribution computation.
- Computer science foundations more broadly: Markov chains are the backbone of the original PageRank algorithm (a giant transition matrix over web pages), of Markov Chain Monte Carlo methods used in modern machine learning, and of language models that predict the next token from recent context — all descendants of the same "future depends only on now" idea built up in this chapter.
Practice — work these out before checking the numbers
1. A student's daily study mode is either Focused (F) or Distracted (D), with one-day transition probabilities P(F|F) = 0.7, P(D|F) = 0.3, P(F|D) = 0.5, P(D|D) = 0.5. If today the student is Distracted, find the probability of being Focused two days from now, using the Chapman–Kolmogorov approach shown above (condition on tomorrow's state, then use the Markov property to drop today's).
2. For the same chain, solve for the stationary distribution (πF, πD) using the balance equation πP = π and normalisation, the same way the weather example was solved.
3. (Stretch, for the curious): In a simple random walk on the integers 0, 1, 2, 3, 4, where a token moves +1 with probability p and −1 with probability 1−p each step, and 0 and 4 are absorbing states ("Game Over" at either end) — explain in one or two sentences why this is a Markov chain, and why it does not have a single stationary distribution the way the weather chain does.
Answers: (1) P(F two days from now | D today) = P(F|D)·P(F|F) + P(D|D)·P(F|D) = 0.5×0.7 + 0.5×0.5 = 0.35 + 0.25 = 0.60. (2) Balance equation gives 0.3πF = 0.5πD, so πD = 0.6πF; with πF + πD = 1 this gives πF = 1/1.6 = 5/8 = 0.625, πD = 3/8 = 0.375. (3) It is Markov because the next position depends only on the current position and the coin flip, never on how the walk arrived there; it has no single stationary distribution because 0 and 4 are absorbing — probability mass eventually gets trapped at one of them rather than settling into a fixed mix across all five states.
Summary
A Markov chain models a system moving through states over time where the Markov property holds: P(Xn+1 = j | Xn = i, past) = P(Xn+1 = j | Xn = i) — the entire past collapses into the single current state. A time-homogeneous chain is fully described by its transition matrix P, a stochastic matrix (non-negative entries, rows summing to 1) whose entry Pij gives the one-step probability of moving from state i to state j. The n-step transition probabilities are exactly the entries of the matrix power Pn, a fact (the Chapman–Kolmogorov equation) that follows directly from applying the law of total probability and then using the Markov property to drop old conditioning — never assume it, always be ready to derive it as shown above. A regular chain (all transitions eventually possible) has a unique stationary distribution π satisfying πP = π and Σπ = 1, solvable as an ordinary system of linear equations, and Pn provably converges to it regardless of the starting state — a fact you can watch happen by computing successive matrix powers by hand. The property being modelled is dependence on the present, not the absence of structure: a Markov chain is a highly structured, state-dependent process, sharply different from a sequence of independent trials, and that distinction is the one most worth remembering.
Think About It
Think about this: How would you explain markov chains: future only depends on now 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.