Transition kernels and two-step laws

What you will learn

Derive finite-state distribution propagation by conditional transition kernels, compose two-step laws and distinguish endpoint probabilities from path visit events.

Prerequisites: From outcomes to random variables · Combining conditional branches · Replacement and sampling protocols

Choose a state that carries the required memory

A small fictional job controller is inspected at equally spaced ticks. Its state is Ready, Busy or Offline. We model its state at tick n by X_n. Ready means the controller can accept work; Busy means a job occupies it; Offline means a recovery tick is required. These are abstract labels, not ordered numerical scores. The model is stipulated for instruction and is not a measurement of real servers, poker opponents or market regimes. Assume the recorded state contains all information relevant to the next transition, and assume the same transition rule applies at every tick. Those are separate assumptions: sufficiency of the present state is the Markov property, while a rule that does not vary with time is time homogeneity.

The Markov property does not say successive states are independent. Starting Busy gives a different next-state law from starting Ready. It says that once the present state is given, an earlier history provides no further change to that next-state law. If the recovery probability depended on how long the controller had been Busy, this three-label state would generally omit relevant memory. We would need to add duration to the state or abandon this kernel. A tidy transition table alone cannot establish that an observed process is Markov. Here we specify a complete mechanism, so calculations are exact consequences of assumptions rather than evidence that those assumptions fit data.

Read a conditional row before multiplying

Use the order Ready, Busy, Offline for both rows and columns. Four equally likely transition tickets are available at every tick. From Ready, two tickets lead to Ready and two to Busy. From Busy, one leads to Busy and three to Offline. From Offline, all four lead to Ready. The transition matrix P therefore has rows (1/2,1/2,0), (0,1/4,3/4) and (1,0,0). A row is a conditional distribution given the current state, so every row sums to one. Columns need not sum to one: the Ready column totals 3/2 because its entries condition on different starting states.

Write q_n as a row vector containing the unconditional distribution at tick n. Conditioning on the current state gives q_(n+1)(j)=sum_i q_n(i)P(i,j). In compact notation q_(n+1)=q_n P. The factor q_n(i) supplies the chance of reaching row i; P(i,j) supplies the conditional chance of then moving to j. Summing P(i,j) without those weights mixes incompatible denominators. For a known Ready start q_0=(1,0,0), the first distribution is (1/2,1/2,0). At time zero the start is certain, so a zero-step transition is the identity operation, not an application of P.

Compose kernels by summing mutually exclusive routes

To find a two-step probability from i to j, partition according to the intermediate state k. The probability of route i,k,j is P(i,k)P(k,j). The two factors are conditional transition probabilities, not an assertion that the two state variables are independent. Distinct k values describe disjoint paths, so add their products. This gives P²(i,j)=sum_k P(i,k)P(k,j), where the superscript denotes matrix multiplication. Squaring each individual matrix entry retains only repeated edges and drops valid routes through other states. The same conditioning argument yields q_2=q_0 P².

Start Ready. The nine intermediate/end pairs have probability numerators over sixteen, arranged by intermediate row, of (4,4,0), (0,2,6) and (0,0,0). For example Ready,Busy,Offline has probability (1/2)(3/4)=6/16. Add by final column: q_2=(4,6,6)/16=(1/4,3/8,3/8). Independently enumerate sixteen equally likely ordered pairs of fresh transition tickets. Eight pairs enter Ready at the first tick, producing four Ready and four Busy endpoints. Eight pairs enter Busy, producing two Busy and six Offline endpoints. This checks the calculation without matrix notation. Both constructions total sixteen, and neither invents a positive path through Offline at the first tick.

Separate an endpoint from a visit event

The event X_2=Busy includes only paths ending Busy. The event that Busy occurs during ticks one or two includes a path if its intermediate state or its final state is Busy. We deliberately exclude tick zero from this visit definition. Starting Ready, the visiting paths with positive mass are Ready,Ready,Busy with 4/16, Ready,Busy,Busy with 2/16 and Ready,Busy,Offline with 6/16. The visit probability is 12/16=3/4, twice the Busy endpoint probability. Leaving Busy before the last inspection removes a path from the endpoint event but does not erase its earlier visit.

Adding P(X_1=Busy)=1/2 to P(X_2=Busy)=3/8 gives 7/8 and double-counts the Busy,Busy overlap of 2/16=1/8. Subtract that overlap to recover 3/4. This is an independent event-algebra check on the path calculation. Alternatively the only positive path avoiding Busy at both future ticks is Ready,Ready,Ready, with probability 1/4, so complementing gives 3/4. An absorbing copy of Busy could track whether a visit has occurred, but changing Busy to absorbing in the original process would also change endpoint laws. Keep the physical process and the event-memory device conceptually separate.

Change the mechanism and rebuild the audit

The workshop changes how many of Busy’s four tickets lead Offline. Counts zero through four preserve the conditional row total, while shifting probability between staying Busy and exiting. Choose a starting state, classify all nine intermediate/end pairs by whether they visit Busy, and enter the three endpoint probabilities plus the visit probability. Zero-mass paths still have well-defined state labels: classify their logical membership even though they contribute nothing to the current probability. The live marked-mass ledger lets you see whether a classification double-counts or omits complete paths. Any mechanism or start change clears the audit entries and classifications.

Try exit count zero with a Ready start. Busy cannot be left, so its endpoint and visit probabilities both become 3/4. Then use exit count four: a first-tick Busy state certainly exits, and only the Ready,Ready,Busy route remains Busy at tick two, giving endpoint 1/4 while visits remain 3/4. Finally start Offline. The first tick is certainly Ready, so the two-step distribution is (1/2,1/2,0), regardless of Busy’s exit count. These boundary experiments expose why a conditional row cannot simply be copied forward. Hints and reset are available; the draft lasts only for this visit and is separate from account progress. We derive finite-horizon distributions here, without claiming stationarity, eventual recovery or an empirical forecast.

Hands-on: Route a two-step state law

Change a conditional row and start state, classify complete paths, and reconcile endpoint and visit probabilities.

Common mistakes

• Normalizing columns when rows encode conditional laws.
• Squaring entries rather than summing products through all intermediate states.
• Treating the Markov property as independence of successive states.
• Counting a path twice when Busy occurs at both future ticks.
• Applying a state-only kernel when hidden duration changes the next transition.

Keep these ideas

• Specify state sufficiency and time homogeneity separately.
• A row-stochastic kernel propagates row distributions as qP.
• Two-step laws sum disjoint intermediate-state products.
• An endpoint event can omit earlier visits.
• Check route totals, ticket enumeration and boundary mechanisms.

Further reading

• Data 140: Transitions, sections 10.1.1–10.1.6 ↗

  Read Markov property, initial laws, time homogeneity, conditional rows, path products and intermediate-state derivation of matrix powers. Original controller kernel, visit-event derivation and workshop. No source exercises or videos reviewed; no long-run claim. Checked 2026-10-24.