A transition matrix is not a square table of numbers. Every row is a probability distribution — where the chain goes next, given where it is now — and a matrix whose rows do not sum to one is not a chain, so every quantity computed from it would still produce a number and none of them would mean anything. The lab adds each row up before it draws a single arc. Two objects come out of the matrix: the digraph, which records only which entries are nonzero, and Pⁿ, which is n steps taken at once and whose entries here are fractions rather than decimals.
Core ideas
Three ideas, and the first of them is the whole definition. The other two are the objects this course will keep taking out of the same matrix.
From state i the chain has to go somewhere, so the numbers in row i are non-negative and add to exactly 1. That is all a transition matrix is. The lab refuses a matrix that fails it and names the offending row, because a row summing to 9/10 says the chain goes somewhere nine times out of ten and vanishes the tenth — and every steady state, expected time and value on this course would still compute happily on such a matrix.
Draw an arc from i to j exactly when P[i][j] > 0. An arc of probability 1/1000 is as much an arc as one of probability 1/2, and the structure that “Communicating Classes, Recurrence and Period” reads — who can reach whom, what the chain cannot leave, how long the cycles are — depends on nothing but that yes-or-no answer.
Pⁿ[i][j] is the probability of being at j after exactly n steps having started at i, and it is obtained by multiplying the matrix by itself rather than by simulating anything. The arithmetic is exact: on the five-state example P¹² has numerators fifteen digits long over denominators of sixteen, which is past what a double can hold, so a decimal implementation would be storing the nearest number it had and calling it the answer.
The material
The definition, the one test the data must pass, the two directions a matrix can be read in, and where the decimals would have gone.
A finite set of states 1, …, n together with a transition matrix P, where P[i][j] is the probability that the chain is at j at the next step given that it is at i now. Every entry satisfies 0 ≤ P[i][j] ≤ 1 and every row satisfies Σⱼ P[i][j] = 1.
A distribution on the states is a row vector v with vᵢ ≥ 0 and Σᵢ vᵢ = 1. The chain is memoryless: the row used at each step depends on the current state and on nothing earlier.
The lab takes the matrix as text, rows separated by a semicolon and entries by spaces: 1/2 1/2; 1/4 3/4 is a two-state chain whose first row is an even split. Entries may be fractions, and they stay fractions — 7/10 is seven tenths exactly, not 0.7. The state names are yours, and they are labels: nothing below depends on them.
Before it draws anything the page adds each row up and prints the sum beside the row. This looks like fussiness for about as long as it takes to mistype one entry. A matrix with a bad row still has powers, still has an invariant vector, still yields expected times to absorption; all of those numbers are answers about an object that is not a chain, and no later check on this course would catch it.
A distribution is a row vector and it is multiplied on the left: (vP)ⱼ = Σᵢ vᵢ P[i][j]. Read the sum out loud and the reason is immediate — the chance of being at j next is the chance of being at each i now, times the chance of the step from i to j, added over every i. That is why the stationary vector solves πP = π rather than Pπ = π, and why it is a left eigenvector; a reader who has met eigenvectors as columns meets the transpose here and should notice.
P^(m+n) = Pᵐ Pⁿ for all m, n ≥ 0, with P⁰ the identity. Hence Pⁿ[i][j] is the probability of being at j after exactly n steps from i, and vPⁿ is the distribution after n steps from v.
To get from i to j in m + n steps the chain is somewhere at step m — at exactly one state k, and those events are disjoint and exhaust the possibilities.
So the probability is Σₖ P(i to k in m) · P(k to j in n), which by memorylessness is Σₖ Pᵐ[i][k] · Pⁿ[k][j], and that sum is the (i, j) entry of the matrix product. Nothing about the numbers was used, only that the intermediate state is exactly one of the n.
□
So there is no separate machinery for “n steps”. The lab computes Pⁿ by repeated multiplication and prints it whole, and the distribution bars beneath the digraph are that same walk shown one step at a time. Push the step count up on the two-state example and the bars stop moving long before the fractions stop growing, which is worth watching: those are two different facts and only one of them is about probability.
The five-state example has every entry over a denominator of 20, which looks harmless. Multiplying the matrix by itself multiplies denominators, and by the twelfth power the entries are fifteen-digit numerators over sixteen-digit denominators; by the twenty-fourth they are thirty-one over thirty-two. The lab prints the widest numerator and the largest denominator as figures, and warns when the denominator passes what a double can hold.
This is not a point about arithmetic hygiene for its own sake. The claim the whole of this course rests on is that certain quantities are exactly equal — πP is exactly π, two routes to a queue's distribution give exactly the same fractions — and an equality between two decimals that look alike is not evidence of anything.
Type 1/2 1/4; 1/4 3/4. The first row sums to 3/4, and the lab stops with the row named and nothing drawn.
Every quantity on this page would have computed. The powers exist, the digraph can be drawn, a distribution can be pushed through it. What they would describe is a process that disappears with probability 1/4 per step from state one, which is a fine object and is not a Markov chain. The page refuses rather than painting, because a number produced from bad data is worse than a blank panel.
Type 1 1 as the starting distribution on the two-state chain. It is refused: the entries have to be non-negative and sum to exactly 1.
Rescaling it silently to (1/2, 1/2) would answer a question nobody asked. A distribution that does not sum to one is a typo far more often than it is an unnormalised weight, and the two cases want opposite treatment.
Interactive
the support digraph, n steps at once, and denominators that outgrow a decimal
Method
The data first, then the structure, then the powers. Doing them in that order means a bad matrix never reaches the arithmetic.
One addition per state. If a row does not come to 1, stop: whatever you have is not a transition matrix and nothing computed from it describes a chain. This is the cheapest test on the course and the only one that can invalidate all the others at once.
An arc wherever the entry is positive, and nothing else. The next several ideas — classes, recurrence, period, which states the chain can never leave — are properties of that picture alone, and having it in front of you stops you from reasoning about magnitudes when the question is about reachability.
Distributions are rows and go on the left; vP is one step forward. If you find yourself computing Pv you are asking a different question, and the answer will not be a distribution.
Pⁿ answers “where is it after n” for every starting state at once, which is usually what you want; vPⁿ answers it for one. Both come from the same matrix product and neither needs a simulation.
If the denominators have outgrown sixteen digits, any decimal answer you have seen for the same quantity was rounded, and the rounding happened before you looked. The lab prints both widths so that this is a fact rather than a suspicion.
Two states, fine and wet, with P = [1/2 1/2; 1/4 3/4], started certainly fine. Every entry below is exact, and the arithmetic is one row vector times one matrix, repeated.
The numerators and denominators of the two-state walk are doing something regular: 1/2, 3/8, 11/32, 43/128, each denominator four times the last and each numerator four times the last minus one. That the decimals are creeping towards 0.3333 is the eye-catching part, and it is the part this course will be most careful about: it is a fact about a limit, and the number 1/3 is available from a linear system with no limit involved at all. That is the subject of “The Steady State as a Linear System”.
The five-state table is the reason nothing here is a decimal. At n = 12 the largest denominator has sixteen digits; a double carries about fifteen to seventeen significant figures altogether, so a floating-point implementation has already stopped holding these numbers and started holding the nearest ones it can. Nothing warns it, and the entries still sum to something that prints as 1.
For a rehearsal, take the two-state chain and start it at (0, 1) instead. The supplied first move is that vP = (1/4, 3/4). Work out where the walk is heading and then check it against the walk from (1, 0): both approach the same pair of numbers from opposite sides, which is a hint about what that pair is and a warning about what “approach” will turn out to be worth.
You should be able to test a matrix row by row and name the failing row, draw the support digraph from the pattern of nonzero entries, push a distribution forward by hand as a row vector, say what the (i, j) entry of Pⁿ means without hesitating over which index is which, and explain why the entries of a power outgrow a decimal and what that costs.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.