Markov Chains and Transition Matrices

Suppose you want to predict tomorrow's weather from today's. You don't care whether last Tuesday was sunny or rainy. How much of the past do you actually need to remember? This question — how much history matters — sits at the heart of one of the most useful ideas in all of probability. A Markov chain answers it by declaring, as a modeling assumption, that the future depends on the past only through the present state, no further back. This single postulate, the Markov property, is deceptively simple. Yet it compresses an infinite, unwieldy dependency structure into a finite table of numbers. The idea matters because an enormous range of random phenomena can be modeled this way. Genetic drift, board games, queueing systems, web-page ranking, weather, stock-price models, card shuffling, and language generation are examples. Each can be modeled, at least approximately, as a sequence of states. These states are visited according to fixed transition probabilities. Once we accept the Markov property, all of the chain's short-run and long-run behavior becomes computable. It all follows from a single object: the transition matrix. Matrix algebra then takes over where probabilistic reasoning alone would become intractable. The big picture is this: a Markov chain lives on a state space. This is a set of possible configurations the system can occupy. It evolves in discrete time steps. At each step, the chain jumps from its current state to a new one. It may even stay at the same one. This happens according to probabilities that depend only on the current state. They never depend on how it got there. Collecting these one-step probabilities into a matrix produces a distinctive algebraic signature. Every row is a probability distribution. This is the notion of a stochastic matrix. It is exactly the right structure to capture "one step of Markov evolution." This article gives the precise definition of a (discrete-time, time-homogeneous) Markov chain. It proves that the one-step transition matrix is stochastic. Conversely, it shows that any stochastic matrix generates a legitimate Markov chain. It also builds the intuition needed for later study. This includes multi-step transitions via the Chapman-Kolmogorov Equations. It also includes the long-run behavior captured by the Classification of States.

Key takeaways
  • A Markov chain is a sequence of random variables where the future depends on the past only through the present — the Markov property.
  • The state space SS is the (here, countable) set of values the chain can take.
  • The one-step transition matrix P=(pij)P = (p_{ij}) collects all conditional probabilities P(Xn+1=j∣Xn=i)P(X_{n+1}=j \mid X_n = i).
  • Every row of PP sums to 11 and every entry is nonnegative — PP is a stochastic matrix.
  • Conversely, any stochastic matrix paired with an initial distribution defines a genuine Markov chain, via Conditional Probability and the chain rule.
  • Key idea: memorylessness turns an infinite-dimensional dependency structure into a single finite matrix that fully governs the chain's evolution.

Where this lives today

Markov chains and their transition matrices are a working tool across quantitative science. In web search, Google's original PageRank algorithm models a "random surfer" clicking links as a Markov chain on the graph of web pages, with the transition matrix built directly from the hyperlink structure; the long-run distribution ranks pages by importance. In statistical physics, Markov chains underlie Monte Carlo methods (Metropolis–Hastings, Gibbs sampling) used to sample from complex distributions like the Boltzmann distribution of an Ising model, where the transition matrix is engineered so its stationary distribution matches the target. In genetics, DNA and protein sequence evolution and hidden Markov models for gene finding rely on state spaces of nucleotides or amino acids with empirically estimated transition matrices. In queueing theory and operations research, transition matrices model customers moving between service states, inventory levels, or machine breakdown/repair cycles, feeding directly into the study of stationary throughput and reliability. In finance, credit-rating migrations (e.g. a bond moving from AA to A to default) are modeled with transition matrices whose entries are estimated from historical rating-change data. In natural language processing, nn-gram models and simple text generators are literal instances of Markov's own original example, now scaled to billions of words. In cryptography and randomized algorithms, card-shuffling processes (e.g. the riffle shuffle) are Markov chains on the symmetric group, and their transition matrices are studied to bound how many shuffles are needed to reach near-uniform randomness — a question resolved using the tools that begin with the Chapman–Kolmogorov equations for computing PnP^n.

Ask the tutor: How do we compute nn-step transition probabilities from PP, and why does matrix multiplication correctly capture "summing over all intermediate paths"?

DefinitionDiscrete-Time Markov Chain and Transition Matrix

Let SS be a finite or countable set, called the state space. A sequence of random variables (X0,X1,X2,… )(X_0, X_1, X_2, \dots), each taking values in SS, is a Markov chain if for every n≥0n \ge 0 and all states i0,i1,…,in,j∈Si_0, i_1, \dots, i_n, j \in S with

P(X0=i0,…,Xn=in)>0,P(X_0 = i_0, \dots, X_n = i_n) > 0,

the following Markov property holds:

P(Xn+1=j∣X0=i0,X1=i1,…,Xn=in)=P(Xn+1=j∣Xn=in).P(X_{n+1} = j \mid X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) = P(X_{n+1} = j \mid X_n = i_n).

The chain is time-homogeneous if, in addition, the right-hand side does not depend on nn: there exist numbers pijp_{ij}, for i,j∈Si, j \in S, such that

P(Xn+1=j∣Xn=i)=pijfor all n≥0 and all i with P(Xn=i)>0.P(X_{n+1} = j \mid X_n = i) = p_{ij} \quad \text{for all } n \ge 0 \text{ and all } i \text{ with } P(X_n = i) > 0.

The numbers pijp_{ij} are the one-step transition probabilities, and the matrix P=(pij)i,j∈SP = (p_{ij})_{i,j \in S} is the (one-step) transition matrix of the chain. Unless stated otherwise, "Markov chain" in this article means discrete-time and time-homogeneous. A matrix P=(pij)i,j∈SP = (p_{ij})_{i,j \in S} is called stochastic if

pij≥0 for all i,j∈S,and∑j∈Spij=1 for all i∈S.p_{ij} \ge 0 \text{ for all } i,j \in S, \qquad \text{and} \qquad \sum_{j \in S} p_{ij} = 1 \text{ for all } i \in S.

The distribution π(0)\pi^{(0)} of X0X_0, given by πi(0)=P(X0=i)\pi^{(0)}_i = P(X_0 = i), is the initial distribution of the chain.

Intuition

Picture the state space as a collection of nodes, and imagine standing at one node at each tick of a clock. At every tick you roll a state-dependent die and jump — possibly back to the same node — according to fixed odds that depend only on where you currently stand. The Markov property says the die's odds do not care about your itinerary before arriving; it is as if the chain has amnesia about everything except its current location. This is why one models it with a directed, weighted graph: nodes are states, and a directed edge from ii to jj carries weight pijp_{ij}, the probability of jumping from ii to jj in one step. The constraint that each row of PP sums to 11 is just the statement that, wherever you stand, you must go somewhere (possibly staying put) with total probability one — the outgoing edge-weights from each node form a probability distribution. This graph picture also explains why the transition matrix is the natural computational engine of the theory. Multiplying probability row-vectors by PP advances the chain by one time step; multiplying by PnP^n (matrix power) advances it by nn steps, a fact whose justification is exactly the content of the Chapman–Kolmogorov equations. For now, the goal is to nail down the correspondence between "Markov chain" (a probabilistic object, a sequence of random variables satisfying a conditional-independence condition) and "stochastic matrix" (a purely algebraic object, a nonnegative matrix with unit row sums) — and to see that this correspondence is exact: every Markov chain produces a stochastic matrix, and every stochastic matrix (with a chosen initial distribution) produces a Markov chain.

Figure
A three-state weather chain: nodes are states, directed edges carry one-step probabilities, and probabilities out of each node sum to 1
Sunny S Rainy R Cloudy C 0.3 0.2 0.4 0.5 0.2 0.3 0.5 0.3 Row sums: S: 0.5+0.3+0.2=1, C: 0.4+0.3+... , R: 0.2+0.3+0.5=1
TheoremThe Transition Matrix of a Markov Chain is Stochastic, and Every Stochastic Matrix Generates a Markov Chain

Part 1 (Necessity). Let (Xn)n≥0(X_n)_{n\ge0} be a time-homogeneous Markov chain on a countable state space SS with transition probabilities pij=P(X1=j∣X0=i)p_{ij} = P(X_1 = j \mid X_0 = i) (defined whenever P(X0=i)>0P(X_0=i)>0; extend arbitrarily, e.g. by pii=1p_{ii}=1, to states of prior probability zero, or restrict attention throughout to states that are reachable). Then the matrix P=(pij)i,j∈SP = (p_{ij})_{i,j\in S} is stochastic:

pij≥0  for all i,j,∑j∈Spij=1  for all i.p_{ij} \ge 0 \ \text{ for all } i,j, \qquad \sum_{j \in S} p_{ij} = 1 \ \text{ for all } i.

Part 2 (Sufficiency / Construction). Conversely, let SS be countable, let π(0)=(πi(0))i∈S\pi^{(0)} = (\pi^{(0)}_i)_{i \in S} be any probability distribution on SS, and let P=(pij)i,j∈SP = (p_{ij})_{i,j \in S} be any stochastic matrix. Then there exists a probability space and a sequence of random variables (Xn)n≥0(X_n)_{n \ge 0} on it, taking values in SS, such that (Xn)(X_n) is a time-homogeneous Markov chain with initial distribution π(0)\pi^{(0)} and one-step transition matrix PP.

Part 3 (Determination of the finite-dimensional distributions). Under the hypotheses of Part 2, for every n≥1n \ge 1 and states i0,i1,…,in∈Si_0, i_1, \dots, i_n \in S,

P(X0=i0,X1=i1,…,Xn=in)=πi0(0) pi0i1 pi1i2⋯pin−1in.P(X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) = \pi^{(0)}_{i_0}\, p_{i_0 i_1}\, p_{i_1 i_2} \cdots p_{i_{n-1} i_n}.
Proof

We prove the three parts in order. The technique throughout is direct manipulation of conditional probabilities via the definition and the multiplication (chain) rule, together with a standard existence construction (Kolmogorov-type extension for countable products, done explicitly here since the state space is countable and no abstract extension theorem is needed).

Part 1. Fix i∈Si \in S with P(X0=i)>0P(X_0 = i) > 0. By definition, pij=P(X1=j∣X0=i)p_{ij} = P(X_1 = j \mid X_0 = i) for each j∈Sj \in S. Conditional probabilities are themselves probabilities of events (with respect to the conditional measure P(⋅∣X0=i)P(\cdot \mid X_0 = i)), hence: 1. Nonnegativity. pij=P(X1=j∣X0=i)≥0p_{ij} = P(X_1 = j \mid X_0 = i) \ge 0 for every jj, since probabilities are nonnegative by the axioms of probability. 2. Row sums equal 1. The events {X1=j}\{X_1 = j\}, as jj ranges over SS, are pairwise disjoint (a random variable takes only one value at a time) and their union is the whole sample space (since X1X_1 must take some value in SS, as SS is by hypothesis the full state space of the chain). Hence by countable additivity of the conditional probability measure P(⋅∣X0=i)P(\cdot \mid X_0 = i),

∑j∈Spij=∑j∈SP(X1=j∣X0=i)=P(⋃j∈S{X1=j}  ∣  X0=i)=P(Ω∣X0=i)=1.\sum_{j \in S} p_{ij} = \sum_{j \in S} P(X_1 = j \mid X_0 = i) = P\Big(\bigcup_{j \in S} \{X_1 = j\} \;\Big|\; X_0 = i\Big) = P(\Omega \mid X_0 = i) = 1.

For states ii with P(X0=i)=0P(X_0 = i) = 0, we adopted the convention (stated in the theorem) of assigning some valid row, e.g. pii=1p_{ii}=1 and pij=0p_{ij}=0 for j≠ij \ne i; this row trivially satisfies nonnegativity and sums to 11, and it does not affect any computation of actual chain probabilities since X0=iX_0 = i has probability zero (so no conditioning on it is ever actually invoked along a positive-probability path — see the finite-dimensional formula in Part 3, all of whose terms multiply against πi0(0)\pi^{(0)}_{i_0}). This proves PP is stochastic.

Part 2 and Part 3. We construct the process explicitly on the countable product space and verify it satisfies the Markov property with the prescribed transition matrix; along the way we obtain the finite-dimensional distribution formula of Part 3, which we then use to re-derive the Markov property directly (avoiding any circularity, since we build the distributions of the process first and check the defining conditional-probability identity from them afterward). Construction. Let Ω=S∞=S×S×S×⋯\Omega = S^{\infty} = S \times S \times S \times \cdots, whose elements are sequences ω=(ω0,ω1,ω2,… )\omega = (\omega_0, \omega_1, \omega_2, \dots) with each ωn∈S\omega_n \in S. Define Xn:Ω→SX_n : \Omega \to S by Xn(ω)=ωnX_n(\omega) = \omega_n (the coordinate maps). Since SS is countable, the collection of cylinder sets

C(i0,…,in)={ω∈Ω:ω0=i0,…,ωn=in},i0,…,in∈S, n≥0,C(i_0,\dots,i_n) = \{\omega \in \Omega : \omega_0 = i_0, \dots, \omega_n = i_n\}, \qquad i_0,\dots,i_n \in S,\ n\ge 0,

generates the product σ\sigma-algebra F=σ(X0,X1,X2,… )\mathcal{F} = \sigma(X_0, X_1, X_2, \dots). Define, for each n≥0n \ge 0 and each choice of i0,…,in∈Si_0, \dots, i_n \in S, the number

q(i0,…,in):=πi0(0) pi0i1 pi1i2⋯pin−1inq(i_0, \dots, i_n) := \pi^{(0)}_{i_0}\, p_{i_0 i_1} \, p_{i_1 i_2} \cdots p_{i_{n-1} i_n}

(an empty product for n=0n=0, so q(i0)=πi0(0)q(i_0) = \pi^{(0)}_{i_0}). We check these numbers are consistent: for fixed i0,…,in−1i_0,\dots,i_{n-1},

∑in∈Sq(i0,…,in)=q(i0,…,in−1)∑in∈Spin−1in=q(i0,…,in−1)⋅1=q(i0,…,in−1),\sum_{i_n \in S} q(i_0,\dots,i_n) = q(i_0,\dots,i_{n-1}) \sum_{i_n \in S} p_{i_{n-1} i_n} = q(i_0,\dots,i_{n-1}) \cdot 1 = q(i_0,\dots,i_{n-1}),

using that PP is a stochastic matrix (row sums 11). This consistency, together with ∑i0q(i0)=∑i0πi0(0)=1\sum_{i_0} q(i_0) = \sum_{i_0}\pi_{i_0}^{(0)} = 1, means the assignment C(i0,…,in)↦q(i0,…,in)C(i_0,\dots,i_n) \mapsto q(i_0,\dots,i_n) is a finitely additive, countably-additive-on-cylinders set function that extends (by the standard countable-product measure construction — the countable-state-space case of the [Kolmogorov extension theorem], here elementary because at each stage we are just distributing mass over a countable index set) to a unique probability measure PP on (Ω,F)(\Omega, \mathcal F) satisfying

P(X0=i0,…,Xn=in)=q(i0,…,in)=πi0(0) pi0i1⋯pin−1inP\big(X_0 = i_0, \dots, X_n = i_n\big) = q(i_0,\dots,i_n) = \pi^{(0)}_{i_0}\,p_{i_0i_1}\cdots p_{i_{n-1}i_n}

for every nn and every choice of states. This is exactly the claimed formula of Part 3. Verifying the Markov property (completing Part 2). We must show that for all n≥0n\ge0 and all i0,…,in,j∈Si_0,\dots,i_n,j\in S with P(X0=i0,…,Xn=in)>0P(X_0=i_0,\dots,X_n=i_n)>0,

P(Xn+1=j∣X0=i0,…,Xn=in)=P(Xn+1=j∣Xn=in)=pinj.P(X_{n+1}=j \mid X_0=i_0,\dots,X_n=i_n) = P(X_{n+1}=j\mid X_n = i_n) = p_{i_nj}.

By the definition of conditional probability and the formula from Part 3,

P(Xn+1=j∣X0=i0,…,Xn=in)=P(X0=i0,…,Xn=in,Xn+1=j)P(X0=i0,…,Xn=in)=πi0(0)pi0i1⋯pin−1in pinjπi0(0)pi0i1⋯pin−1in=pinj,P(X_{n+1}=j \mid X_0=i_0,\dots,X_n=i_n) = \frac{P(X_0=i_0,\dots,X_n=i_n,X_{n+1}=j)}{P(X_0=i_0,\dots,X_n=i_n)} = \frac{\pi^{(0)}_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}\,p_{i_nj}}{\pi^{(0)}_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}} = p_{i_nj},

where the cancellation is valid precisely because the denominator, which equals πi0(0)pi0i1⋯pin−1in\pi^{(0)}_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n} by Part 3, is assumed strictly positive. This quantity does not depend on i0,…,in−1i_0,\dots,i_{n-1} at all — it depends only on ini_n and jj — which simultaneously establishes the Markov property and shows that the conditional probability P(Xn+1=j∣Xn=in)P(X_{n+1}=j\mid X_n=i_n) (computed the same way, dropping the earlier coordinates) equals the same pinjp_{i_nj}, and does not depend on nn. Hence (Xn)n≥0(X_n)_{n\ge0} is a time-homogeneous Markov chain with initial distribution π(0)\pi^{(0)} and one-step transition matrix PP, completing Part 2. ■\blacksquare

∎

Worked examples

Example 1 — A three-state inventory/weather-type chain with asymmetric transitions. Consider a chain on S={1,2,3}S=\{1,2,3\} (think: Low, Medium, High stock level at the end of the day) with transition matrix

P=(0.50.40.10.30.20.50.00.60.4).P = \begin{pmatrix} 0.5 & 0.4 & 0.1 \\ 0.3 & 0.2 & 0.5 \\ 0.0 & 0.6 & 0.4 \end{pmatrix}.

Step 1 — check it is stochastic. All entries are ≥0\ge 0. Row sums: row 1 is 0.5+0.4+0.1=1.00.5+0.4+0.1=1.0; row 2 is 0.3+0.2+0.5=1.00.3+0.2+0.5=1.0; row 3 is 0.0+0.6+0.4=1.00.0+0.6+0.4=1.0. All nonnegative, all rows sum to 11: PP is indeed a valid stochastic matrix, consistent with Part 1 of the theorem applied in reverse — this matrix is a legitimate candidate transition matrix. Step 2 — initial distribution. Suppose π(0)=(0.2,0.5,0.3)\pi^{(0)} = (0.2, 0.5, 0.3) (started at Medium most likely). Check: 0.2+0.5+0.3=10.2+0.5+0.3=1, valid. Step 3 — compute a specific path probability using Part 3 of the theorem. Find P(X0=2,X1=3,X2=2,X3=1)P(X_0=2, X_1=3, X_2=2, X_3=1).

P(X0=2,X1=3,X2=2,X3=1)=π2(0)⋅p23⋅p32⋅p21=0.5×0.5×0.6×0.3.P(X_0=2,X_1=3,X_2=2,X_3=1) = \pi^{(0)}_2 \cdot p_{23}\cdot p_{32}\cdot p_{21} = 0.5 \times 0.5 \times 0.6 \times 0.3.

Compute stepwise: 0.5×0.5=0.250.5 \times 0.5 = 0.25; then 0.25×0.6=0.150.25\times0.6=0.15; then 0.15×0.3=0.0450.15\times0.3=0.045. So

P(X0=2,X1=3,X2=2,X3=1)=0.045.P(X_0=2,X_1=3,X_2=2,X_3=1) = 0.045.

Step 4 — a marginal one-step-ahead distribution. Find the distribution of X1X_1 given π(0)\pi^{(0)}: P(X1=j)=∑iπi(0)pijP(X_1=j)=\sum_i \pi^{(0)}_i p_{ij}, i.e. π(1)=π(0)P\pi^{(1)} = \pi^{(0)}P (row vector times matrix).

π1(1)=0.2(0.5)+0.5(0.3)+0.3(0.0)=0.10+0.15+0.00=0.25,\pi^{(1)}_1 = 0.2(0.5) + 0.5(0.3) + 0.3(0.0) = 0.10+0.15+0.00 = 0.25,
π2(1)=0.2(0.4)+0.5(0.2)+0.3(0.6)=0.08+0.10+0.18=0.36,\pi^{(1)}_2 = 0.2(0.4)+0.5(0.2)+0.3(0.6) = 0.08+0.10+0.18=0.36,
π3(1)=0.2(0.1)+0.5(0.5)+0.3(0.4)=0.02+0.25+0.12=0.39.\pi^{(1)}_3 = 0.2(0.1)+0.5(0.5)+0.3(0.4)=0.02+0.25+0.12=0.39.

Check: 0.25+0.36+0.39=1.000.25+0.36+0.39 = 1.00. Good — π(1)\pi^{(1)} is again a valid probability distribution, exactly as it must be since PP is stochastic (a probability row-vector times a stochastic matrix is again a probability row-vector, a fact used repeatedly when studying the Chapman-Kolmogorov Equations).

Example 2 — Verifying the Markov property fails to be violated (a "trap" check) using conditioning on more history. Take the same PP as above. Someone claims: "surely P(X2=1∣X1=3,X0=2)P(X_2 = 1 \mid X_1 = 3, X_0 = 2) differs from P(X2=1∣X1=3)P(X_2=1\mid X_1=3) in general, since X0X_0 gives extra information." Let's actually verify the Markov property holds here, using Part 3's formula directly (not assuming the conclusion). We compute both sides from the joint law constructed in the theorem.

P(X2=1∣X1=3,X0=2)=P(X0=2,X1=3,X2=1)P(X0=2,X1=3).P(X_2 = 1 \mid X_1=3, X_0=2) = \frac{P(X_0=2,X_1=3,X_2=1)}{P(X_0=2,X_1=3)}.

Numerator: π2(0) p23 p31=0.5×0.5×0.0=0\pi^{(0)}_2\,p_{23}\,p_{31} = 0.5\times0.5\times0.0 = 0. Denominator: π2(0) p23=0.5×0.5=0.25\pi^{(0)}_2\,p_{23} = 0.5\times0.5=0.25. So P(X2=1∣X1=3,X0=2)=0/0.25=0P(X_2=1\mid X_1=3,X_0=2) = 0/0.25 = 0. Now the unconditional-on-X0X_0 version:

P(X2=1∣X1=3)=p31=0,P(X_2=1\mid X_1=3) = p_{31} = 0,

directly from the matrix (row 3, column 1 entry is 0.00.0). Indeed 0=00 = 0: the two match, confirming the Markov property numerically for this instance (as the theorem guarantees it must, for every choice of history with positive probability) — the apparent "extra information" from X0=2X_0=2 turns out not to change the conditional law of X2X_2 at all, because it is already fully screened off by X1=3X_1=3. This also illustrates a genuinely structural fact: entry p31=0p_{31}=0 means state 11 ("Low") is not reachable in one step from state 33 ("High"); no amount of extra conditioning on the past can create a transition probability that the matrix itself forbids.

CounterexampleWhy time-homogeneity — or, weakening further, the Markov property itself — cannot be dropped

The theorem's construction (Part 2) crucially used a single fixed matrix PP applied at every time step. Two things can go wrong if we relax the hypotheses, and both destroy the clean "one matrix governs everything" picture.

(a) Dropping time-homogeneity. Consider a chain that does satisfy the Markov property (the conditional law of Xn+1X_{n+1} given the whole past depends only on XnX_n) but where the transition probabilities are allowed to depend on nn: say S={1,2}S=\{1,2\} and

P(Xn+1=2∣Xn=1)=1n+2,P(Xn+1=1∣Xn=2)=12,P(X_{n+1}=2\mid X_n=1) = \frac{1}{n+2}, \qquad P(X_{n+1}=1\mid X_n=2) = \frac{1}{2},

with the complementary probabilities filling out each row to sum to 11. This is a perfectly good non-homogeneous (time-inhomogeneous) Markov chain: it still has the property that the future depends on the past only through the present. But there is no single transition matrix PP with P(Xn+1=j∣Xn=i)=pijP(X_{n+1}=j\mid X_n=i)=p_{ij} valid for all nn, because the (1,2)(1,2) entry genuinely changes with nn (it is 1/21/2 at n=0n=0, 1/31/3 at n=1n=1, 1/41/4 at n=2n=2, and so on, never stabilizing). The clean statement "the chain's whole future is governed by a single stochastic matrix PP," which is the entire payoff of Part 2 and Part 3 of the theorem, simply fails: one would instead need an infinite sequence of matrices P(0),P(1),P(2),…P^{(0)}, P^{(1)}, P^{(2)}, \dots, one per time step, and the elegant matrix-power formula for nn-step transitions (Chapman–Kolmogorov) does not hold in the simple form PnP^n.

(b) Dropping the Markov property outright. Let S={0,1}S = \{0,1\} and let XnX_n be defined by Xn=1X_n = 1 if a fair coin flip at time nn matches the flip at time n−1n-1 (for n≥1n\ge1; set X0=X_0= a fresh fair coin flip encoded as 0/10/1), and Xn=0X_n = 0 otherwise — i.e. XnX_n records whether consecutive flips of an i.i.d. fair-coin sequence agree. Then P(Xn+1=j∣Xn=in,Xn−1=in−1)P(X_{n+1}=j \mid X_n = i_n, X_{n-1}=i_{n-1}) can depend on in−1i_{n-1} as well as ini_n (knowing whether flips n−2,n−1n-2,n-1 matched, combined with whether n−1,nn-1,n matched, gives partial information about the actual flip at time nn, which affects whether n,n+1n,n+1 will match, in a way not reducible to XnX_n alone). Concretely, XnX_n alone does not determine enough about the underlying coin sequence to screen off Xn−1X_{n-1}: the pair (Xn−1,Xn)(X_{n-1},X_n) carries strictly more predictive information about Xn+1X_{n+1} than XnX_n alone. Hence no matrix PP with pij=P(Xn+1=j∣Xn=i)p_{ij}=P(X_{n+1}=j\mid X_n=i) can correctly predict Xn+1X_{n+1} from the full past — the entire premise of Part 1 (that a well-defined, past-independent pijp_{ij} exists at all) fails, so there is no legitimate "transition matrix" for (Xn)(X_n) as a chain in XnX_n alone. (One repairs this by passing to a bigger state space, e.g. tracking the last flip rather than just the agreement indicator — a standard trick, but it shows the Markov property is a genuine restriction on which processes admit a transition-matrix description, not an automatic feature of "nice" processes.)

Scope, edge cases & common traps

SituationWhat holdsWhat can fail
Finite state space SSPP is a finite stochastic matrix; row sums exactly 11, computable by direct summation—
Countably infinite SSPP is an infinite stochastic matrix; row sums still =1=1 (a convergent series)Column sums need not be 11; PP need not be doubly stochastic
Time-homogeneousSingle matrix PP governs all steps; nn-step transitions are PnP^nFails if transition rule genuinely varies with nn (see counterexample (a))
State ii with P(X0=i)=0P(X_0=i)=0Row pi⋅p_{i\cdot} can be defined arbitrarily (as a valid distribution) without affecting any actual path probabilityCareless choices can make an unreachable state look reachable in naive computations if one forgets πi(0)=0\pi^{(0)}_i=0
Continuous or general state spaceAnalogous theory exists (transition kernels replace matrices)The clean finite/countable row-sum-11 picture must be replaced by measure-theoretic kernels; outside Tier-1 scope

The mathematician behind it

Origins · 1 minAndrei Andreyevich Markov and how this was discovered
AA
Andrei Andreyevich Markov
1856–1922 · Imperial Academy of Sciences, St. Petersburg, Russia

Andrei Markov was a Russian mathematician working in the tradition of Chebyshev, initially known for contributions to number theory and the theory of continued fractions before turning to probability. He is best remembered for introducing, around 1906, chains of dependent random variables in which each term depends on its immediate predecessor — partly as a rebuttal to critics (notably Pavel Nekrasov) who argued that the Law of Large Numbers required independence. Markov showed dependent sequences could still obey striking regularities, using as his first examples the alternation of vowels and consonants in Pushkin's verse Eugene Onegin, an early instance of what would become statistical language modeling.

History
- 1856 — Andrei Markov born in Ryazan, Russian Empire.
- 1906 — Markov introduces chains of dependent trials and proves a law of large numbers for them, launching the theory of Markov chains.
- 1913 — Markov applies his chain model to letter sequences in Pushkin's Eugene Onegin, demonstrating dependence structure in text.
- 1931 — Andrei Kolmogorov extends the theory to continuous time and general state spaces, laying rigorous measure-theoretic foundations.
- 1922 — Markov dies in Petrograd (Saint Petersburg); his name becomes permanently attached to the memoryless property he formalized.
Does every random process with a "matrix of probabilities" automatically satisfy the Markov property?

No. Having some table of transition-like numbers around does not make a process Markov; the Markov property is a genuine, checkable condition on the process's full joint distribution. As Counterexample (b) shows, you can define a process on a small state space where naive one-step frequencies exist, yet the true conditional law of Xn+1X_{n+1} given the whole past depends on more than just XnX_n. The correct logical order is: first verify the Markov property holds (for every history and every nn), and only then read off the transition matrix from the resulting well-defined conditional probabilities P(Xn+1=j∣Xn=i)P(X_{n+1}=j\mid X_n=i).

Why must every row of a transition matrix sum to exactly 1, but not necessarily every column?

Each row corresponds to "starting in state ii, where do I go next?" — and wherever you start, you must end up somewhere in the state space with total probability 11, since SS is assumed to contain all possible outcomes. That is a probabilistic law-of-total-probability fact, forced by the axioms. Columns, by contrast, correspond to "how much probability flows into state jj from various sources," and there is no a priori reason this has to total 11 — some states might be easy to enter from many states (column sum >1>1) or hard to reach at all (column sum small). Matrices where both rows and columns sum to 11 are a special class called doubly stochastic matrices.

Can a state have pii=1p_{ii} = 1? What does that mean?

Yes — this means state ii is absorbing: once the chain enters ii, it stays there forever, since the entire row's probability mass is concentrated on the diagonal entry. This is consistent with the definition, since the row pi⋅p_{i\cdot} still sums to 11 (as pii=1p_{ii}=1 and all other entries in that row are forced to be 00). Absorbing states show up naturally in models of eventual outcomes, such as "game over," "bankruptcy," or "fixation of an allele" in population genetics, and they become central objects when one studies the Classification of States.

Is the initial distribution π(0)\pi^{(0)} part of the transition matrix, or separate?

Separate. The transition matrix PP encodes only the dynamics — how probability moves from one step to the next — and is entirely independent of where the chain starts. The initial distribution π(0)\pi^{(0)} specifies the starting point's randomness. Together, (π(0),P)(\pi^{(0)}, P) fully determine every finite-dimensional distribution of the chain, exactly as shown in Part 3 of the theorem: P(X0=i0,…,Xn=in)=πi0(0)pi0i1⋯pin−1inP(X_0=i_0,\dots,X_n=i_n) = \pi^{(0)}_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}. Changing π(0)\pi^{(0)} changes the chain's law but never changes PP, and vice versa.

Why is the state space allowed to be only finite or countable in this treatment?

Restricting to countable SS lets every conditional probability P(Xn+1=j∣Xn=i)P(X_{n+1}=j\mid X_n=i) be an honest, elementary conditional probability (a ratio of two probabilities of events), and lets the transition matrix be an actual matrix (rows/columns indexed by a countable set) with row sums given by a convergent series that must equal 11. When the state space is uncountable (say, R\mathbb{R}), individual points typically have probability zero, so "P(X1=j∣X0=i)P(X_1=j\mid X_0=i)" is not meaningful as stated; one needs measure-theoretic transition kernels P(i,A)=P(X1∈A∣X0=i)P(i, A) = P(X_1\in A\mid X_0=i) for (measurable) sets AA, which generalize stochastic matrices. That extension is a deliberately more advanced topic than this foundational treatment.

How does the transition matrix relate to predicting several steps ahead, not just one?

The single-step matrix PP already contains, in principle, all information about multi-step behavior, because nn-step transition probabilities turn out to equal the entries of the matrix power PnP^n. Proving this rigorously — that P(Xm+n=j∣Xm=i)=(Pn)ijP(X_{m+n}=j\mid X_m=i) = (P^n)_{ij} — is precisely the content of the Chapman-Kolmogorov Equations, which build directly on the Markov property and the stochastic-matrix structure established here. This article deliberately stops at the one-step matrix so that the foundational correspondence (chain ↔\leftrightarrow stochastic matrix) is completely nailed down before layering on multi-step machinery.

What is the quickest way to check a proposed table of numbers is a legitimate transition matrix?

Two checks, both mechanical: first, scan every entry and confirm none is negative (probabilities cannot be negative); second, sum each row separately and confirm every row total equals exactly 11 (probabilities of mutually exclusive, exhaustive outcomes from a fixed starting state must add to 11). Both checks are necessary and, together, sufficient — this is exactly the definition of a stochastic matrix proved to correspond to genuine one-step chain dynamics in Part 1 and Part 2 of the theorem above. Skipping the row-sum check is the single most common bookkeeping error when constructing chain models by hand.

Before this

Where this leads