Statistics & decisions

Markov Chain Mixing Lab

A discrete-time Markov chain of 2 to 6 states drawn as arrows: the exact class structure (closed classes, transient states, the period), the long-run distribution from the start and the chance of ending in each closed class with the expected steps, the exact matrix powers for 100 steps, the worst-case total-variation distance, the mixing time and a rate estimated from the distance curve, a lazy switch that removes cycles, and one seeded random walk. Five scored challenges are included. For learning how a chain forgets its start.

Last updated

Calculator overview

Inputs and outputs

This summary comes from the calculator's published input and output contract.

Inputs

Start state (required)
About this input

Where the chain starts, a whole number from 1 to the number of states. Clicked on the canvas.

Default 1 Range 1 to 6
Your prediction (challenge 1) (required)
About this input

Challenge 1: your prediction of the long-run share of state 2, in 5% steps; Not yet predicted keeps the long-run results hidden. Not used outside challenge 1.

Default Not yet predicted Allowed Not yet predicted, About 0%, About 5%, About 10%, About 15%, About 20%, About 25%, About 30%, About 35%, About 40%, About 45%, About 50%, About 55%, About 60%, About 65%, About 70%, About 75%, About 80%, About 85%, About 90%, About 95%, About 100%
Transition chances (row i is from state i to the column's state; the chance of staying is the rest of the row)
When omitted Blank
About this input

The arrows: row i, column j is the chance of moving from state i to state j in one step, blank or 0 for no arrow or from 0.001 to 1. The chance of staying is the rest of the row, so a row may add up to at most 1. Only the cells of states 1 to N off the diagonal are read. Drawn on the canvas.

Default 4 rows
ColumnRange or allowed values
To state 1 0 to 1
To state 2 0 to 1
To state 3 0 to 1
To state 4 0 to 1
To state 5 0 to 1
To state 6 0 to 1
Number of states (required)
About this input

The number of states in use, a whole number from 2 to 6. Set on the canvas; arrows of states above it are ignored.

Default 4 Range 2 to 6
Lazy chain (required)
About this input

Lazy off, or Lazy on: the lazy chain (P + I)/2 halves every move and stays put with the other half, which removes any cycle.

Default Lazy off Allowed Lazy off, Lazy on
Challenge (required)
About this input

Selects a challenge: 0 for none, 1 to 5 for a predefined challenge, which fixes some arrows and settings and leaves the rest to you.

Default 0 Range 0 to 5
Random seed (required)
About this input

The seed of the walker, a whole number from 1 to 2147483646; the same seed always gives the same path.

Default 2026 Range 1 to 2147483646
Mixing threshold (required)
About this input

The worst-case distance at which the chain counts as mixed, from 0.01 to 0.5.

Default 0.25 Range 0.01 to 0.5

Outputs

Matrix powers P^k at steps 0, 1, 2, 3, 5, 10, 20, 50 and 100: row i is the distribution after k steps from state i
About this output

The matrix powers P^k at steps 0, 1, 2, 3, 5, 10, 20, 50 and 100: one row per step and starting state (rows above N blank), the chance of being in each state after k steps. The chance columns are blank while challenge 1 awaits a prediction.

No unit declared
Convergence rate, estimated from the distance curve
About this output

An estimate of the convergence rate read from the distance curve: the factor by which the worst-case distance shrinks each step over the last 10 steps above 0.000001 (an estimate of the second-largest eigenvalue size; exact for two states). Blank when the chain is periodic or has several closed classes, when the distance falls below 0.000001 within 10 steps, when the inputs are not valid or while challenge 1 awaits a prediction.

No unit declared
Formula module versions
About this output

The formula modules the model is built from, with their versions.

No unit declared
Model Status
About this output

NOT VALID with the reason when an input cannot be used; CHECK when the worst-case distance meets the threshold, or crosses the rate floor, only to within rounding (the reported step could then be one step off); otherwise OK. Periodic and absorbing chains read OK.

No unit declared
Model version
About this output

The model version.

No unit declared
The states: long-run share, closed class, recurrence, level, the average over steps 0 to 100, the chance of ending in the class and the walker's visit share
About this output

One row per state (rows above N blank): the state, its long-run share from the start, its closed class and level (blank when transient), 1 when recurrent, its average share over steps 0 to 100, the chance of ending in its class and the walker's visit share. The long-run, average, ending and visit columns are blank while challenge 1 awaits a prediction.

No unit declared
Walker distance from the long run
About this output

The total-variation distance between the walker's visit shares over steps 1 to 100 and the long-run shares (one sample). Blank when the inputs are not valid or while challenge 1 awaits a prediction.

No unit declared
One seeded random walk of 100 steps from the start (one sample, for illustration)
About this output

One seeded random walk: the step k = 0 to 100 and the state visited. The state column is blank while challenge 1 awaits a prediction.

No unit declared
The used transition matrix (with the stay chances; halved toward staying when lazy)
About this output

The used transition matrix: one row per state (rows above N blank), with the chances of staying on the diagonal (halved toward staying when lazy). Never withheld.

No unit declared
Long-run residual
About this output

The largest difference between the long-run shares and the shares one step later (a check of the solve, near 1E-16). Blank when the inputs are not valid or while challenge 1 awaits a prediction.

No unit declared
Transient states
About this output

The number of transient states: states the chain eventually leaves for good. Blank when the inputs are not valid.

No unit declared
Mixing time (steps)
About this output

The first step at which the worst-case distance to the long run is at most the threshold. Blank when the chain is periodic, has several closed classes or has not mixed within 100 steps, when the inputs are not valid or while challenge 1 awaits a prediction.

No unit declared
Challenge goal
About this output

The goal of the selected challenge (blank with none).

No unit declared
Challenge: the value scored
About this output

The value the selected challenge scores: the long-run share of state 2 (challenge 1), the mixing time (2), the period (3), the long-run share of state 1 (4) or the chance of ending in state 6 (5); blank with none, when not valid, when a fixed cell was changed or while challenge 1 awaits a prediction.

No unit declared
Challenge feedback
About this output

Feedback on the selected challenge: the prediction prompt, the integrity text, the met text or the not-met hint (blank with none).

No unit declared
Period
About this output

The period of the single closed class: 1 when aperiodic, d when the chain returns to a state only in multiples of d steps. Blank with several closed classes and when the inputs are not valid.

No unit declared
What the chain does
About this output

What the chain does: one closed class that settles (or not within 100 steps), one closed class with a period that cycles, or several closed classes where the ending depends on the start. Blank when the inputs are not valid.

No unit declared
Challenge score
About this output

The challenge score: 100 when met, else 0.

No unit declared
The distribution after each step from the start (the player), with the distance from the start and the worst-case distance to the long run
About this output

One row per step k = 0 to 100: the step, the chance of being in each state after k steps from the start (blank above N), the total-variation distance from the start to the long run and the worst-case distance over every start (both blank with several closed classes). Every column but the step is blank while challenge 1 awaits a prediction.

No unit declared
Expected steps to reach a closed class
About this output

The expected number of steps from the start until the chain is in a closed class (0 when the start is already in one). Blank when the inputs are not valid.

No unit declared
Worst-case distance after 100 steps
About this output

The worst-case total-variation distance to the long run after 100 steps. Blank with several closed classes, when the inputs are not valid or while challenge 1 awaits a prediction.

No unit declared
Challenge result
About this output

No challenge selected, MET or NOT MET.

No unit declared
Closed classes
About this output

The number of closed classes: groups of states the chain can never leave. Blank when the inputs are not valid.

No unit declared
This page is provided by LogicCommons for informational purposes only. Results are analysis outputs computed from the inputs you supply and are not professional advice. Verify all inputs and results independently.

LogicCommons is in beta. If a result, label, or reference looks wrong, tell us here; we read every message.

Methodology

Purpose and model boundary

This lab models a discrete-time Markov chain on 2 to 6 states with a fixed transition matrix. You draw the arrows, the chances of moving from one state to another in one step; the chance of staying put is the rest of each row. For that chain the model finds the class structure exactly (the closed classes, the transient states and the period), the long-run distribution from the chosen start, the chance of ending in each closed class and the expected steps to reach one, the matrix powers for 100 steps, the worst-case total-variation distance to the long run, the mixing time and a convergence rate estimated from the distance curve. A lazy switch halves every move, which removes any cycle, and one seeded random walk of 100 steps illustrates a single path. Five scored challenges use the same model.

It is a lab for learning how a chain forgets where it started: why a chain with one closed class settles to one long-run distribution, why a periodic chain cycles and never settles, why a chain with several closed classes ends where its start leads it, and how a narrow bridge between groups of states slows mixing. It is not a tool for fitting a chain to data. It handles at most six states and 100 steps, finds no eigenvalues, and the walk is one sample for illustration only.

The model is the calculation authority. The page sends the values you set to the model and draws only what it returns: the arrow widths, the node fills step by step, the walker's token, the heat maps of the matrix powers and the distance curve. The page computes no share, distance, class, period or step itself.

Inputs and units

Transition chances are probabilities from 0 to 1 and the threshold is a distance from 0 to 1; the lab has no physical units. Every scalar input is required. The arrows are optional: a blank arrow is no arrow.

Input Meaning and unit
Number of states N, a whole number from 2 to 6 (default 4). Arrows of states above N are ignored.
Transition chances Row i, column j: the chance of moving from state i to state j in one step, blank or 0 for no arrow, or from 0.001 to 1. The arrows out of a state may add up to at most 1; the chance of staying is the rest. Only the arrows between states 1 to N, off the diagonal, are read. Default: a ring 1 to 2 (0.2), 2 to 3 (0.3), 3 to 4 (0.4), 4 to 1 (0.6), with a shortcut 3 to 1 (0.1).
Start state Where the chain starts, a whole number from 1 to N (default 1).
Lazy chain Lazy off (default), or Lazy on: the lazy chain (P + I)/2 halves every move and stays put with the other half.
Mixing threshold ε, the worst-case distance at which the chain counts as mixed, from 0.01 to 0.5 (default 0.25).
Random seed The seed of the walker, a whole number from 1 to 2,147,483,646 (default 2026). The same seed always gives the same path.
Challenge 0 for free exploration, or 1 to 5 to load a challenge.
Your prediction (challenge 1) Not yet predicted, or About 0% to About 100% in 5% steps: your prediction of the long-run share of state 2.

Where each input is set:

  • On the canvas only: the number of states (its chip), the transition chances (drag the handle along an arrow, or type a value in its popover; a zero arrow is drawn faint and can be raised), the start state (click a node), and your prediction for challenge 1.
  • In the input panel: the lazy setting, the mixing threshold, the random seed and the challenge number.

Governing relationships

The used matrix. For each state i ≤ N, with Sᵢ the sum of its arrows, the stay chance is 1 − Sᵢ. A row whose arrows add up to 1 within 1×10⁻⁹ is rescaled by Sᵢ and its stay chance is exactly 0, so a rounding residue such as 1 − (0.1 + 0.2 + 0.7) never makes a tiny negative or positive stay. When the lazy chain is on, every move is halved and the stay chance becomes (pᵢᵢ + 1)/2, the matrix (P + I)/2. Rows and columns above N are 0.

Class structure. State i reaches state j when there is a path of arrows (with positive chance) from i to j, found exactly in whole numbers by repeated Boolean squaring of I + A, A the 0/1 arrow pattern. A state is recurrent when every state it reaches reaches it back, and transient otherwise. The recurrent states fall into closed classes, groups the chain can never leave, numbered in the order of their lowest state.

Period. With exactly one closed class, the model measures each member's level, its fewest steps from the class's lowest state, by breadth-first search, and the period is

d = gcd of (level(u) + 1 − level(v)) over every arrow u to v in the class,

the greatest common divisor of the cycle lengths. The class is aperiodic when d = 1. A lazy chain is always aperiodic, because every state has a stay loop.

Absorption from the start. With Q the moves among transient states, the start's row of the fundamental matrix N = (I − Q)⁻¹ gives the expected visits to each transient state before the chain enters a closed class. Their sum is the expected number of steps to reach a closed class (0 when the start is already in one). The chance of ending in each closed class is the chance that the first recurrent state reached belongs to it.

Long-run distribution. Within each closed class C the shares x satisfy the balance equations x = xP, and they add up to the chance wC of ending in that class. The model solves all classes at once in one linear system, in which each class's lowest state has its balance equation replaced by the class total; that system is never singular. A transient state's long-run share is 0. With exactly one closed class this is the stationary distribution π, the same from every start. The residual is the largest difference between x and xP.

Matrix powers and the distribution after k steps. P⁰ is the identity and Pᵏ = Pᵏ⁻¹ · P for k = 1 to 100, each entry an exact sum of six products. Row i of Pᵏ is the distribution after k steps from state i; the row of the start state is what the canvas plays.

Total-variation distance. With exactly one closed class, the distance after k steps from state i is

dᵢ(k) = ½ · Σⱼ |Pᵏ(i, j) − πⱼ|,

and the worst-case distance is d(k) = the largest dᵢ(k) over every state. It never increases with k. For a periodic class it never falls below 1 − 1/d.

Mixing time. With one closed class and an aperiodic chain, the mixing time is the first step k from 0 to 100 at which d(k) ≤ ε. A distance within 1×10⁻⁹ (relative) of ε counts as meeting it.

Convergence-rate estimate. With one closed class and an aperiodic chain, the model finds the last step k₂ at which d(k) is still at least 0.000001, and reports

rate = (d(k₂) / d(k₂ − 10))^(1/10),

the factor by which the distance shrinks each step over the last 10 steps. It estimates the size of the second-largest eigenvalue of P once the slower terms dominate; for two states it is exactly |1 − p − q|. When the distance falls below 0.000001 within 10 steps, no estimate is shown.

The walker. The walk uses Park and Miller's minimal standard generator (MINSTD) with the multiplier 48271. Starting from g₀ = the seed, each state is

gₖ = MOD(48271 · gₖ₋₁, 2³¹ − 1), and each draw is uₖ = gₖ / (2³¹ − 1), k = 1 to 100,

which lies strictly between 0 and 1. The walk starts at the start state; at step k, from state X, it moves to the first state j whose cumulative chance along row X (scaled by the row total) exceeds uₖ, so a state with chance 0 is never chosen. The visit shares count steps 1 to 100. The walker's distance from the long run is ½ · Σⱼ |visit shareⱼ − xⱼ|.

Calculation sequence

The model works through the relationships above in this order:

  1. It checks the entered values in the order of the status list under Errors and warnings.
  2. It builds the used matrix, with the stay chances and, when lazy, the halved moves.
  3. It finds reachability, the recurrent and transient states, the closed classes and, with one closed class, the levels and the period.
  4. It solves the start's absorption row: the chance of ending in each closed class and the expected steps to reach one.
  5. It solves the long-run distribution from the start and its residual.
  6. It computes the matrix powers for steps 0 to 100, the distribution after each step from the start and, with one closed class, the distances from every start.
  7. It reads the mixing time and the rate estimate from the distance curve.
  8. It runs the seeded walk.
  9. It sets the status and, in a challenge, scores the challenge.

Outputs and interpretation

  • Closed classes, mixing time and worst-case distance after 100 steps: the primary results. The mixing time is blank when the chain is periodic, has several closed classes or has not mixed within 100 steps.
  • What the chain does: one of four plain sentences: one closed class that settles; one closed class that has not mixed within 100 steps; one closed class with period d, which cycles and never settles (the lazy chain removes the cycle); or several closed classes, where the ending depends on the start.
  • Transient states, period (with one closed class) and expected steps to reach a closed class.
  • Convergence rate, estimated from the distance curve: an estimate, not an exact eigenvalue.
  • Long-run residual: a check of the solve, near 1×10⁻¹⁶.
  • Walker distance from the long run: how far one sample's visit shares lie from the long-run shares. It wanders from seed to seed and is not used by any status or score.
  • States table: for each state its long-run share from the start, its closed class and level (blank when transient), whether it is recurrent, its average share over steps 0 to 100, the chance of ending in its class and the walker's visit share. Shares and chances are shown as percentages.
  • Used transition matrix: the matrix the model used, with the stay chances on the diagonal (halved toward staying when lazy).
  • Distribution after each step: for k = 0 to 100, the chance of being in each state after k steps from the start (as percentages), the distance from the start's distribution to the long run, and the worst-case distance.
  • Matrix powers: Pᵏ at steps 0, 1, 2, 3, 5, 10, 20, 50 and 100, one row per starting state.
  • Walker path: the state visited at each step 0 to 100.
  • Model version and formula module versions.

Reading the canvas: the arrows are drawn with widths from the used matrix; the node fills play the distribution step by step from the start; the heat maps show every row of Pᵏ becoming the same row as the chain forgets its start; the distance curve is drawn on a log scale with the threshold line; and the walker's token follows the seeded path.

What to take from the lab: with one aperiodic closed class, every start leads to the same long-run distribution, and the worst-case distance falls roughly geometrically, at the rate of the second-largest eigenvalue. A cycle stops the distribution from settling, though the average over time still approaches the long-run shares; laziness breaks the cycle at the cost of slower mixing. With several closed classes, the start decides where the chain ends.

Challenges

Choosing a challenge number from 1 to 5 loads that challenge's starting chain. Nothing is replaced: your chain is scored as you draw it. Each challenge fixes some arrows and settings and leaves the others to you; if a fixed value is changed, the challenge reads NOT MET with the text "Not yet: this challenge keeps some arrows and settings fixed; reload the challenge to start again." and no value is scored. The result reads MET (score 100) or NOT MET (score 0), with the goal, the value the challenge is scored on and a short explanation or hint.

  1. Predict a long-run share. Predict the share of time this two-state chain spends in state 2 in the long run, then reveal it. Fixed: two states and both arrows. Scored on the long-run share of state 2: met when your prediction is within 2.5 percentage points of it, half of the 5% prediction step.
  2. Widen the bottleneck. Change only the two highlighted arrows (2 to 3 and 3 to 2) so the chain mixes within 4 steps (worst-case distance at most 0.25). Fixed: four states, every other arrow, the lazy setting and the threshold. Scored on the mixing time: met with one aperiodic closed class and a mixing time of 4 or less.
  3. Build a clock of period 3. Build a chain with one closed class that has period 3. Fixed: the lazy setting (off). Scored on the period: met with one closed class of period exactly 3.
  4. Favour state 1 without starving the rest. Make state 1 hold at least half of the long-run share while every state keeps at least 10%. Fixed: four states. Scored on the long-run share of state 1: met with one closed class, a share of state 1 of at least 50% and every share at least 10%.
  5. Tilt the gambler's game. Starting with 2 coins (state 3), change only the two arrows out of state 3 so the chance of reaching 5 coins (state 6) is at least 60%. Fixed: six states, every other arrow (states 1 and 6 absorb) and the start. Scored on the chance of ending in state 6: met at 60% or more.

Bounds within 1×10⁻⁹ (relative) of a challenge threshold count as met.

Challenge 1 holds back the answer until you predict: while your prediction reads Not yet predicted, the mixing time, the distance after 100 steps, the rate estimate, the residual, the walker distance, the value scored, the distributions after each step, the matrix powers, the long-run, average, ending and visit columns of the states table, and the walker's states are blank. The result reads NOT MET with the prompt, and the status reads OK. The structure, the used matrix and the step numbers still show. Your prediction changes nothing outside challenge 1.

Validation and status logic

The status reads the first match in the list under Errors and warnings. The NOT VALID checks apply to the entered values, inside a challenge too. A CHECK does not stop the calculation: every result is still shown. A periodic chain, an absorbing chain or a chain that has not mixed within 100 steps is a lesson, not a warning: it reads OK, and "What the chain does" says what happens.

Assumptions and limitations

  • At most six states and 100 steps. A nonzero arrow is at least 0.001, which keeps every linear solve well conditioned. A long-run share as small as 1×10⁻¹⁵ is not accurate relative to its own size.
  • The chain is time-homogeneous: the same matrix applies at every step.
  • No eigenvalues are computed. The rate is an estimate read from the distance curve; it is exact for two states and approximate otherwise.
  • The distances and the mixing time need exactly one closed class; with several, the long-run share depends on the start and a worst case over starts has no single target.
  • A distance within 1×10⁻⁹ (relative) of the threshold counts as meeting it, and the status then reads CHECK, because another computation could place that step one earlier or later. The same holds for the 0.000001 floor of the rate window.
  • The walker's generator is a small linear congruential generator, deterministic and reproducible, fine for teaching and wrong for cryptography or serious simulation. A walk step within about 1×10⁻⁹ of a boundary between two states could go either way in another computation. The walk is one sample: its visit shares wander from the long-run shares.

Restrictions and non-computing states

Only the arrows between states 1 to N, off the diagonal, are read and checked; shrinking the number of states never needs the hidden arrows cleared. A challenge number that is not a whole number from 0 to 5 counts as no challenge selected.

Under NOT VALID every result and every table is blank, except the model and module versions, the challenge result (No challenge selected, or NOT MET with a challenge selected), a score of 0, and the goal and hint of a selected challenge.

With several closed classes the period, the mixing time, the distance after 100 steps, the rate estimate and both distance columns are blank, and the levels are blank. With a periodic class the mixing time and the rate are blank.

In challenge 1, until you predict, the results named under Challenges are held back.

Errors and warnings

The status messages, first match wins (i and j are state numbers):

  • NOT VALID: the number of states must be a whole number from 2 to 6
  • NOT VALID: the arrow from state i to state j must be blank, 0, or a probability from 0.001 to 1: the first such arrow, row by row.
  • NOT VALID: the arrows out of state i add up to more than 1; lower one of them: the lowest such state; a sum within 1×10⁻⁹ of 1 counts as 1.
  • NOT VALID: the start state must be a whole number from 1 to the number of states
  • NOT VALID: choose the lazy setting from the list
  • NOT VALID: the mixing threshold must be from 0.01 to 0.5
  • NOT VALID: the seed must be a whole number from 1 to 2147483646
  • NOT VALID: the challenge number must be a whole number from 0 to 5, and the prediction one of the listed choices
  • CHECK: the worst-case distance meets the mixing threshold at step t only to within rounding; the mixing time counts that step: a distance within 1×10⁻⁹ (relative) of the threshold decides the mixing time t.
  • CHECK: the distance curve crosses 0.000001 at step k to within rounding, so the rate window may start one step earlier or later in another engine: a distance within 1×10⁻⁶ (relative) of the floor ends the rate window at k.
  • OK: the chain is computed with nothing to flag, including periodic and absorbing chains.

References

This laboratory is an educational model of a finite discrete-time Markov chain. It finds the closed classes and the transient states from the arrows alone, the period as the greatest common divisor of the cycle lengths, the long-run distribution by solving the balance equations, and the chance and expected time of reaching a closed class from the fundamental matrix of the transient states. It follows the total-variation distance from every start to the long run through the exact matrix powers, reads the mixing time where that worst-case distance first meets a threshold, and estimates the convergence rate from the slope of the distance curve. One illustrative walk uses the Park-Miller minimal standard (MINSTD) generator with the multiplier 48271.

Sources and further reading

  • Transient and recurrent states, closed and irreducible sets: K. Siegrist, Random: Probability, Mathematical Statistics, Stochastic Processes, chapter 15, Markov Processes, section 4, Transience and Recurrence. Random (University of Alabama in Huntsville)
  • The period of a state and of a class: K. Siegrist, Random: Probability, Mathematical Statistics, Stochastic Processes, chapter 15, Markov Processes, section 5, Periodicity. Random (University of Alabama in Huntsville)
  • Absorbing chains, the fundamental matrix, the expected steps before absorption and the absorption probabilities: C. M. Grinstead and J. L. Snell, Introductory Probability, section 11.2, Absorbing Markov Chains. LibreTexts
  • The fixed (stationary) vector and the convergence of the matrix powers to equal rows: C. M. Grinstead and J. L. Snell, Introductory Probability, section 11.3, Ergodic Markov Chains. LibreTexts
  • Total-variation distance, the worst-case mixing time and the lazy chain: D. A. Levin, Y. Peres and E. L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2009, chapter 4, Introduction to Markov Chain Mixing. An overview of the definition is in the encyclopedia entry Markov chain mixing time. Wikipedia
  • The minimal standard generator used by the walker: S. K. Park and K. W. Miller, "Random number generators: good ones are hard to find", Communications of the ACM 31(10), 1988, pages 1192-1201. doi:10.1145/63039.63042

No table or text from any of these publications is reproduced, and none of their authors or publishers has reviewed or endorses this laboratory.

This laboratory is for learning. Its results hold only within its stated ranges; the convergence rate is an estimate read from the distance curve, not a computed eigenvalue.

Links were current at build time. If one moves, search the document's title rather than reporting a broken link as a defect.

Results are informational and not professional advice. See our Terms of Use. Powered by SpreadsheetWeb · About · Privacy · Terms