A transition matrix stores the one-step probabilities of a discrete Markov chain. For states 1,…,K, define Aᵢⱼ = P(Xₜ = j | Xₜ₋₁ = i). Row i lists every possible next state given the current state i, so its entries are nonnegative and sum to 1. The chain also needs an initial distribution over states; its next state depends on its current state, not the full sequence of earlier states. section 2.1.2 section 7.1
Two states
Suppose state 1 switches to state 2 with probability α, and state 2 switches to state 1 with probability β. Then A = [[1−α, α], [β, 1−β]]. The diagonal entries are probabilities of staying put. If α and β remain fixed over time, the matrix is time invariant. For a row distribution π₀, one transition gives π₁ = π₀A; n transitions give πₙ = π₀Aⁿ. A stationary distribution satisfies πA = π. When α,β > 0, balancing the flows π₁α = π₂β and using π₁+π₂ = 1 gives π = [β/(α+β), α/(α+β)]. section 7.1
For page ranking, states are web pages and directed links supply possible moves. Let Lᵢⱼ be the probability of choosing link i→j uniformly among page i’s outgoing links. For a page with links, set Aᵢⱼ = pLᵢⱼ + (1−p)/n, where n is the number of pages and 0.5 < p < 1. For a page without outgoing links, set Aᵢⱼ = 1/n. The random jump makes every page reachable and permits self-transitions. The resulting stationary probability πⱼ serves as page j’s rank. section 7.1.1
To compute ranks, construct the transition probabilities, choose an initial distribution, and repeatedly multiply by A until successive distributions change little: π ← πA. Keep the multiplication convention consistent with Aᵢⱼ meaning “from i to j.” A power-iteration listing instead multiplies A by a column vector and tests on a constructed matrix; using that code for this row-oriented page model requires adapting its orientation and input. section 7.1 section 7.1.1
