Kelly's Lemma¶
Certify a continuous-time Markov chain's stationary law by matching each forward transition's weighted flow to a candidate reverse transition and matching their statewise exit rates.
Core Idea¶
Kelly's Lemma gives a sufficient way to certify a stationary probability distribution of a continuous-time Markov chain (CTMC) by comparing it with a candidate reversed chain. Let \(Q=(q_{ij})\) and \(\widetilde Q=(\widetilde q_{ij})\) be valid rate generators on the same finite state space, and let \(\pi\) be a probability distribution. Write \(q_i=\sum_{j\ne i}q_{ij}\) and \(\widetilde q_i=\sum_{j\ne i}\widetilde q_{ij}\) for the actual total exit rates, excluding the negative diagonal entries. If \(q_i=\widetilde q_i\) for each state and \(\pi_iq_{ij}=\pi_j\widetilde q_{ji}\) for every \(i\ne j\), then \(\pi Q=0\) and \(\pi\) is stationary for the forward chain.[1]
The proof is a controlled summation, not a claim that forward and reverse dynamics must be identical. Incoming forward flow at \(i\) becomes \(\sum_{j\ne i}\pi_jq_{ji}=\pi_i\sum_{j\ne i}\widetilde q_{ij}=\pi_iq_i\), exactly its outgoing forward flow. The candidate reverse generator may differ from \(Q\); when it does, the method can certify stationary nonreversible behavior. Taking \(\widetilde Q=Q\) recovers the stronger special case of detailed balance.[1]
The immediate theorem is a stationarity certificate. Identifying \(\widetilde Q\) as the actual time-reversed process additionally uses stationarity and the positive-support formula \(\widetilde q_{ij}=\pi_jq_{ji}/\pi_i\); Walrand states that separately. A positive but unnormalizable measure is not a stationary probability distribution. On countable state spaces, normalization and the existence/regularity of the associated processes must be handled before the finite-state conclusion is extended.[1]
Structural Signature¶
Sig role-phrases: forward generator — candidate probability law — candidate reverse generator — equal exits — weighted reverse pairing — stationarity certificate and reversal interpretation.
- Forward generator. \(Q\) supplies nonnegative rates between distinct states and a diagonal \(q_{ii}=-q_i\). It defines the chain whose stationary law is sought; without a valid generator there is no CTMC claim to certify.[1]
- Candidate probability law. \(\pi_i\ge 0\) and \(\sum_i\pi_i=1\) supply proposed state weights. The normalization makes the conclusion a probability law rather than merely a formal invariant measure. The method still has to discover or guess these weights.[1]
- Candidate reverse generator. \(\widetilde Q\) is a second valid rate matrix on the same state set. Its reverse-oriented transition channels give the comparison. It need not equal \(Q\); requiring equality would lose legitimate nonreversible examples.[1]
- Equal-exit condition. \(q_i=\widetilde q_i\) compares off-diagonal rate sums for each \(i\). This turns the reverse-paired incoming flow into the forward outgoing flow. Including the diagonal would make every generator's row sum zero and empty the hypothesis of content.[1]
- Weighted reverse pairing. Each forward flow \(\pi_iq_{ij}\) matches the candidate reverse flow \(\pi_j\widetilde q_{ji}\). If this fails for a needed pair, this particular certificate fails even when another argument might still prove stationarity.[1]
- Stationarity certificate and reversal interpretation. Summing the pair relations proves \(\pi Q=0\); after a genuine stationary chain is established, a separate time-reversal result identifies \(\widetilde Q\) on the positive support of \(\pi\). Conflating these logical steps overstates what the local algebra alone says.[1]
What It Is Not¶
Kelly's Lemma is not detailed balance in different notation. Detailed balance pairs \(\pi_iq_{ij}\) with \(\pi_jq_{ji}\) using the same rate matrix. Kelly's candidate \(\widetilde Q\) can be different. A clockwise three-state cycle with constant jump rate is stationary under a uniform law and has a counterclockwise reversed generator; its one-way forward current violates same-generator detailed balance while satisfying Kelly's two-generator pairing.[1]
It is not a product-form theorem by itself. Walrand uses it in a particular queueing network, but first proposes a product-form candidate and imposes load restrictions. The lemma checks the candidate; it does not manufacture factorization or stability for every queue.[1]
It is not the assertion that a reversed movie has already been constructed merely because rates were written in opposite directions. The second rate matrix must be valid; the pair and exit conditions must hold; and actual process reversal is interpreted after stationarity, on states where the quotient defining reverse rates is meaningful. It is also not a discrete-time theorem obtained by pasting transition probabilities into the CTMC exit-rate conditions without reformulation.[1]
Scope of Application¶
The clean statement here is finite-state CTMC analysis. It includes reversible chains as a special case but becomes most distinctive when the proposed reverse dynamics have a different directed flow. A finite directed cycle displays that difference without queueing assumptions. In either case, the same candidate-law, equal-exit and paired-flow checks are literal mathematical tests, not an analogy.[1]
Queueing networks are an important applied habitat. Walrand's §6.3 network has three components, a customer-class state description, a guessed reversed-flow network and a proposed product-form distribution under explicit \(\lambda_k<\mu_k\) conditions. A particular forward/reverse transition pair is checked, and the proof applies analogous relations to other pairs. This is a worked application, not evidence that every queueing network has that product form.[1] Kelly's earlier original paper reports equilibrium results for irreversible queue models used in communication networks, machine interference and birth–illness–death settings, but its accessible abstract does not give the detailed rates required to claim those as independently reconstructed examples here.[2]
An infinite or countable CTMC may also admit a reversal argument, but the elementary finite-state summation does not license dropping normalizability or ignoring explosion and process-construction issues. In such a model, distinguish an invariant Measure from a stationary probability distribution, and state the regularity conditions actually available.[1]
Clarity¶
The lemma separates global balance from pairwise detailed balance. Global balance requires each state's aggregate incoming and outgoing probability rates to agree. Detailed balance forces each forward channel to be canceled by its reverse channel within the same process. Kelly's condition instead uses a second process to organize the aggregate cancellation; therefore a nonzero directed stationary current can coexist with a stationary law. The finite cycle makes the distinction visible.[1]
It also separates three often-collapsed claims: a proposed \(\pi\) is normalized; the pair-and-exit algebra proves \(\pi Q=0\); and a stationary process has a genuine reversed generator. A reader can now ask exactly which layer a model has established. Calling all three “the reversed chain is stationary” would conceal missing assumptions.[1]
Manages Complexity¶
For a large state space, direct global balance means solving a coupled equation for each state. If the reverse-oriented transitions have a recognizable structure, Kelly's Lemma organizes the work around one normalized candidate distribution, one valid reversed generator, statewise exit equality and pairwise flow identities. Walrand's network proof illustrates that a product-form guess can turn a complicated global-state calculation into local rate comparisons.[1]
The compression is conditional, not free. It relocates difficulty to choosing the candidate \(\pi\) and \(\widetilde Q\), checking every permitted transition class, and proving that the candidate normalizes. If these are harder than global balance, the lemma has not simplified the problem. It also does not remove the need to identify the actual model's state space and rate conventions.[1]
Abstract Reasoning¶
Given a proposed stationary law, first ensure that \(Q\) and \(\widetilde Q\) really are generators and \(\pi\) is normalized. Test exits \(\sum_{j\ne i}q_{ij}\) rather than vacuous full row sums. Then test all forward/reverse pairings. If both identities hold, sum over the incoming states to establish \(\pi Q=0\). In a finite state space, this yields a stationary law; only then identify reverse rates on positive-\(\pi\) states through the separate time-reversal formula.[1]
A failed pairing does not prove \(\pi\) nonstationary: it invalidates that proposed certificate. One can seek another candidate reverse generator or solve global balance directly. Conversely, a candidate that satisfies flow pairings but has infinite total mass cannot be advertised as a stationary probability law. These diagnostic branches make the theorem useful as a proof method rather than an incantation.[1]
Knowledge Transfer¶
The calculation transfers literally from the three-state cycle to Walrand's queue network: a forward \(Q\), a proposed \(\pi\), a candidate \(\widetilde Q\), matched exit rates and matched reversed weighted flows occur in both. The cycle has just three positions and directed circulation; the network state records queues and customer classes, and its candidate law factors under model-specific load restrictions. The theorem does not require one case's physical interpretation in the other.[1]
Outside continuous-time Markov modeling, the idea of certifying a global invariant by local paired obligations may be suggestive, but that is a possible future-prime pattern, not an extension of Kelly's exact rate-matrix theorem. No literal application to an unrelated domain is claimed here.
Examples¶
Canonical — finite one-way cycle¶
Take states $0,1,2$ and a rate \(a>0\). Let the forward chain move only \(0\to1\to2\to0\) at rate \(a\), with diagonal entries \(-a\). Propose \(\pi_i=1/3\) and a second chain moving only \(0\to2\to1\to0\) at rate \(a\). All exits are \(a\). A forward positive edge has weighted flow \(a/3\), exactly the flow on its reverse edge in the second chain; other off-diagonal pairs have zero on both sides. Kelly's Lemma therefore certifies \(\pi Q=0\). This is an explicit calculation derived from Walrand's theorem, not a historical example attributed to him. Same-generator detailed balance fails because a forward clockwise edge has no corresponding counterclockwise edge in \(Q\).[1]
Mapped back: the forward generator is the clockwise \(Q\); candidate probability law is uniform \(\pi\); candidate reverse generator is counterclockwise \(\widetilde Q\); equal exits are \(a=a\) at each state; weighted reverse pairings are \(a/3=a/3\) on each directed edge; the stationarity certificate is \(\pi Q=0\), and the positive finite-state law permits the subsequent actual-reversal interpretation.
Applied — Walrand's three-component queue network¶
Walrand's §6.3 network uses queue and customer-class configurations as states. He assumes \(\lambda_k<\mu_k\) for the three components, proposes a factored distribution, and guesses a network whose customer flows run in reverse. His proof shows one concrete transition-pair equality and says the other allowed pairs follow analogously; it checks the conditions of Kelly's Lemma and concludes the proposed law is invariant. The resulting factorization belongs to that qualifying network, not to the lemma's definition.[1]
Mapped back: the forward generator is the original network's \(Q\); candidate probability law is Walrand's normalized product-form \(\pi\); candidate reverse generator is the guessed reversed-flow network's \(\widetilde Q\); equal exits hold statewise in the checked model; weighted reverse pairing is \(\pi(x)q(x,y)=\pi(y)\widetilde q(y,x)\) for the displayed and analogous transition classes; the stationarity certificate is \(\pi Q=0\), while identifying the reverse path process uses the separate theorem.
Structural Tensions¶
Reversible shortcut versus nonreversible fidelity. Setting \(\widetilde Q=Q\) is a simple sufficient check, but it would incorrectly exclude the one-way cycle and the irreversible networks that motivated reversal-based reasoning. Allowing a distinct \(\widetilde Q\) preserves those cases at the cost of specifying and validating an additional generator. Diagnostic: does the candidate system have stationary directional current that defeats same-generator detailed balance, and is there a coherent distinct reverse model?[1][2]
Local checking versus candidate construction. A recognizable reverse network can turn a large global-balance system into repeated transition-pair identities. But guessing its rate matrix and a normalizable \(\pi\) can be the hardest part; the lemma does not optimize both requirements away. Favoring the local route before a plausible guess may obscure rather than simplify the proof. Diagnostic: are candidate reverse transitions and weights independently motivated enough that their checks are simpler than directly solving \(\pi Q=0\)?[1]
Formal algebra versus stochastic scope. Extending the same summation to countably many states widens potential use, but an unnormalized measure and a poorly specified or explosive process do not automatically yield a stationary CTMC. Keeping the finite statement makes the inference clean but leaves some applications outside the immediate argument. Diagnostic: have normalization and process regularity been established for the actual infinite-state model rather than inherited from the finite calculation?[1]
Structural–Framed Character¶
Kelly's Lemma lies toward the structural side of the structural–framed spectrum: its core is an exact algebraic condition on rate matrices and state weights. Evaluative weight: the theorem itself does not say a network is desirable, efficient or fair; usefulness as a proof strategy is assessed separately. Human-practice dependence: its truth is mathematical rather than dependent on a particular investigator's choice of notation, although applying it requires modeling decisions and a candidate guess. Institutional origin: the eponym and queueing-theory tradition locate its scholarship, but no institution defines which valid generators satisfy the identities. Vocabulary travel: “local balance” and “reversal” can appear elsewhere, yet the named lemma's literal claims use CTMC rates and stationary probabilities. Import versus recognition: one may recognize that a proposed pair of generators satisfies the conditions without imposing those conditions on the modeled system; constructing a reverse model is a proof device, not a physical alteration of a queue.[1]
Its character: a highly structural but domain-specific probability lemma whose exact mathematical test travels among different CTMC models, not unchanged into systems without Markov generators and stationary laws.
Structural Core vs. Domain Accent¶
The portable skeleton is a global invariant certified by local paired flow obligations plus a conservation condition. That broader proof shape may be a future-prime question; no existing prime is asserted to subsume the exact lemma. Live prime Detailed Balance has related paired-flow mathematics but is a stronger same-generator condition and so is not the lemma's general parent. Live prime Equilibrium names a balanced state rather than this method of proving one.
The irreducible domain mechanism is the off-diagonal CTMC rate generator, the stationary probability vector, and the generator-specific exit and reversed-flow equations. Remove them and the Kelly conclusion \(\pi Q=0\) no longer has its literal meaning. The theorem therefore does not clear the prime bar under this named identity, even though the diagram of local-to-global certification is broadly intelligible.[1]
Instantiates / Related Primes¶
No strict typed parent is proposed pending independent DAG review. Detailed Balance is a neighboring prime and an important special case at \(\widetilde Q=Q\), not a necessary genus of every Kelly-lemma use. Equilibrium is related through the stationary conclusion, not the lemma's proof identity. Domain-specific Continuous-time Markov Chain supplies the carrier and Time Reversibility names a property of path laws; neither is an is-a parent of the lemma. Jackson's Theorem is an application-family neighbor that may use reversal reasoning under special queueing assumptions. The same surname does not connect this lemma to domain-specific Kelly Criterion.[1]
Neighborhood in Abstraction Space¶
Kelly's Lemma sits in a sparse region of the domain-specific corpus (80th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Foundations of Probability & Inference (29 abstractions)
Nearest neighbors
- Kolmogorov Equations for Continuous-Time Markov Chains — 0.85
- Noisy Channel Model — 0.82
- Jensen's Inequality — 0.82
- Hellinger Distance — 0.82
- Buzen's Algorithm — 0.82
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Detailed balance: compare flows within one generator; Kelly's broader pairing compares \(Q\) with candidate \(\widetilde Q\).[1]
- Global balance alone: \(\pi Q=0\) is the target conclusion; Kelly's conditions are one sufficient route to it, not a necessary test for stationarity.[1]
- A stationary time-reversed process: the separate reversal theorem identifies actual reverse rates after the stationary law and positive support are established.[1]
- Product-form queueing results: factorization and load conditions belong to the network model, not every CTMC meeting the lemma.[1]
- Kelly Criterion: the live financial bet-sizing abstraction shares an eponym, not this Markov-chain identity.
References¶
[1] Jean Walrand, “Networks—B”, in Probability in Electrical Engineering and Computer Science (Springer, 2021), original open-access publisher chapter, §6.2.5 Theorems 6.2–6.3 and §6.3 Theorem 6.4 and proof, inspected 2026-10-01. The online proof has an apparent \(p/\pi\) typographical inconsistency; this entry independently checks the finite-state algebra rather than reproducing that line. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28 ↩29 ↩30 ↩31 ↩32 ↩33 ↩34
[2] F. P. Kelly, “Networks of queues”, Advances in Applied Probability 8(2), 416–432 (1976), original publisher abstract inspected 2026-10-01. It supports the historical irreversible-model and application-context claims only; its full mathematical text was not inspected. Kelly's author-hosted 1979 book listing and Cambridge reprint contents locate §1.7 “Reversed processes”; no specific original lemma number or uninspected wording is claimed. registry ↩a ↩b