Everything on this course comes out of one matrix or one equation, and the point of it is a distinction that is easy to state and easy to lose: a steady state is the solution of a linear system, not the limit of anything. On one matrix here the system has exactly one answer and the powers never converge at all — they return to the identity every third step, for ever — so the two ideas can be seen coming apart rather than argued about. The second half turns the same machinery on queues. Cut the chain between two states, balance the crossings, and M/M/1, several servers, a finite waiting room and a customer who declines to join are four readings of one equation rather than four formulas; the closed forms are borrowed from the System Design path so that two Subjects cannot disagree about the same model. Every figure is an exact fraction except one, which is named.
Overview
By the end you can read a chain's structure off its arcs, solve for a steady state exactly and say what an iteration would and would not have given you, compute how long a chain runs and where it ends, choose an action in every state with a stopping argument rather than a tolerance, and build any queue on the course from one cut equation while naming what your model left out.
A transition matrix tested row by row with the failing row named, the support digraph drawn from the pattern of nonzero entries alone, a distribution pushed forward as a row vector, and Pⁿ computed exactly — with the width of its entries printed, because past a certain power a decimal has quietly stopped holding them.
Communicating classes from reachability, recurrence from whether any arc leaves a class, and the period as a gcd obtained from a breadth-first levelling rather than from an enumeration of cycles — which together are the two hypotheses of the one result this path states without proving.
The dependency of the n balance equations shown from the row sums, one equation dropped by name and Σπ = 1 put in its place, exact Gauss-Jordan over the rationals, and the answer verified on the page by recomputing πP — beside a power iteration whose error is measured rather than assumed to shrink.
The canonical blocks extracted from the matrix, N = (I − Q)⁻¹ derived as the sum of the powers of Q with the partial sums shown climbing towards it, expected times as row sums and absorption probabilities as N·R, and a singular I − Q recognised as a second closed class rather than as a numerical failure.
A policy evaluated by solving v = r + γPᵈv exactly rather than iterating it, greedy improvement from that value, and termination argued from finiteness and monotonicity — with value iteration on the same problem shown approaching from below the number the solve already had.
πₙλₙ = πₙ₊₁μₙ₊₁ chained into a distribution and checked against the full balance system solved by elimination; M/M/1 with its truncation error printed, min(n, s)μ and Erlang C read off the same π, a bounded queue where ρ ≥ 1 is permitted and λ(1 − π_K) is the divisor, and a balking chain no closed form covers.
Lessons
The object first — what a transition matrix is and what a power of one means — then the structure its arcs force, because the two hypotheses of the convergence result are needed before anything can be said about limits. Then the central claim, with the solve and the iteration on the same page and one matrix where they come apart completely. Absorption and the decision problem follow, both of them the same linear solve wearing different clothes. The queueing half then starts from one cut equation and never leaves it: four named models and one homemade one, each a different pair of rate lists handed to the same function, and the arrival process itself last, because it is the only place on the course where exactness stops.
Linear programming models, the simplex method, duality and sensitivity analysis, networks, integer programming, scheduling and dynamic programming and sequential decisions from this path: exact elimination over fractions is used as a tool throughout and is not re-derived, and the discounted value of a policy here is the backward recursion of Dynamic Programming and Sequential Decisions written as a linear system instead. From discrete mathematics, graphs and trees for reachability, connectivity and directed cycles, and Discrete Probability in full: conditional probability, random variables, expected value, linearity of expectation, variance, and the binomial and geometric distributions. From algebra, matrix products and inverse matrices, solving linear systems by elimination, infinite geometric series for the normalisation of an unbounded queue, and the number e, which is where the one rounded quantity on this course comes from.
Ask whether a question is about the arcs or about the numbers, and answer it with the right one. Classes, recurrence, irreducibility and the period depend only on which entries are nonzero; steady states, expected times and values depend on the magnitudes. Reasoning about a probability when the question was structural is how a reader decides that an arc of 1/1000 out of a class may as well not be there, and the stationary probability it forces to exactly zero says otherwise.
Solve, then compare an iteration against the solve — never the other way round. Every iterative method on this course is present to be measured, and it can only be measured because the exact answer is sitting beside it. Reporting an iterate as the answer concedes precision for nothing where a limit exists, and on the three-cycle it reports a number for a limit that does not.
Say which rate you divided by. W = L/λ is right only when nothing is lost and the arrival rate does not depend on the state, and the whole second half of this course is about chains where one or the other fails. The lab prints both divisions side by side on the bounded queue because the wrong one is the commonest error in the subject and it is always too small.
Quote the truncation mass beside any figure from a finite chain that stands in for an unbounded one. It is ρ^(N+1), it costs one power, and it is the difference between a figure you can defend and one you are hoping about: at four fifths loaded on forty states it is 0.000106 and the answer is good to three decimals, and at nineteen twentieths on sixty states it is 0.043766 and the mean is out by nearly three.
Continuous-time chains as a theory in their own right. The queueing half writes rates and balances flows, which is the continuous-time picture used as a tool; generator matrices, uniformisation and the exponential of a matrix are the machinery behind it and are not built here. Nothing on the course needs them, and the cut equation is derived from an argument about crossings rather than from a generator.
Chains on infinitely many states, other than as a limit compared against. Every computation here is on a finite chain, and where the model is genuinely unbounded the page prints the mass the truncation discarded rather than waving at it. The closed forms for the unbounded queues are imported from the System Design path and named where they are used.
Mixing times, coupling, and the rate at which Pⁿ approaches its limit. The convergence itself is stated and not proved here, and a quantitative version of it needs spectral gaps or a coupling argument. What is measured instead is the disagreement between an iteration and an exact answer at a given step count, which is a different and much more concrete thing.
Hidden Markov models, parameter estimation, and anything that infers a chain from data. Every matrix on this course is given. Fitting one — maximum likelihood, the forward-backward recursion, the expectation-maximisation algorithm — is a statistics course, and the modelling hazard this path warns about would need restating for it rather than reusing.
Queueing networks, priority disciplines and non-exponential service. Jackson networks, the M/G/1 queue and the Pollaczek-Khinchine formula all need machinery beyond a birth-death chain, and Kingman's variability approximation belongs to the System Design path, in “Variability: the Kingman Approximation”. What this course gives instead is one equation that survives every state-dependent rate, which is the direction the textbook formulas cannot go.
The result this course cites and does not prove. The convergence of Pⁿ to the steady state on an irreducible aperiodic chain, which is one of the three the footer of this Subject names. Both of its hypotheses are computed here on whatever matrix a reader types, and its conclusion's π is obtained by solving a linear system rather than by taking the limit — so the unproved statement is never load-bearing for any figure on the course.