stochastic (Markov) matrix

A stochastic matrix encodes random hops between states. Each entry is a probability, and a whole column (or row, by convention) sums to 1 because from any state the system must go somewhere. Multiply a probability vector by this matrix and you get the probability distribution one step later.

Precisely, a column-stochastic matrix P has P_ij >= 0 and sum over i of P_ij = 1 for each column j; entry P_ij is the probability of moving from state j to state i. A distribution evolves as p_{k+1} = P p_k, so the distribution after k steps is P^k p_0. The Markov property is baked in: the next state depends only on the current state, not the path that led there.

The number 1 is always an eigenvalue (the all-ones vector is a left eigenvector since columns sum to 1), and every eigenvalue satisfies |lambda| <= 1, which keeps probabilities bounded. The eigenvector for eigenvalue 1 is the candidate steady state. When the chain is irreducible and aperiodic, Perron-Frobenius makes that steady state unique and globally attracting.

Why it matters: Markov matrices model web surfing, language, queues, board games, and population genetics. The caveat is that real systems are only approximately memoryless, and chains that are periodic or reducible can fail to settle to a single limit, oscillating or splitting depending on where they start.