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 certifies a stationary probability distribution of a continuous-time Markov chain by pairing its transitions with those of a candidate reversed chain. On a finite state space, start with valid rate matrices \(Q\) and \(\widetilde Q\) and a normalized candidate distribution \(\pi\). If the chains have the same total exit rate from each state and each forward weighted transition satisfies \(\pi_iq_{ij}=\pi_j\widetilde q_{ji}\), then the incoming and outgoing rates balance at every state, so \(\pi Q=0\) and \(\pi\) is stationary.[^ref-360fc77a2a5f]
The candidate reverse generator may differ from the forward generator, allowing nonreversible stationary chains. If the two generators are the same, the equations reduce to the stronger detailed-balance special case. Recognizing the candidate rates as those of the actual time-reversed process uses a separate result after stationarity is established on positive-probability states.[^ref-360fc77a2a5f]
Scope of Application¶
The same test works in unlike CTMC models. In an explicitly constructed three-state one-way cycle, \(Q\) moves clockwise at rate \(a>0\), \(\widetilde Q\) moves counterclockwise at the same rate and \(\pi\) is uniform. Every exit rate is \(a\) and each positive weighted forward/reverse pair equals \(a/3\), certifying stationarity even though detailed balance within \(Q\) fails. This is a direct calculation from the theorem, not an historical example claimed for Walrand.[^ref-360fc77a2a5f]
Walrand applies the lemma to a three-component queue network: under stated load conditions, a proposed product-form distribution and guessed reversed-flow network satisfy the pair and exit tests. Product form is an additional property of that model, not a universal consequence of the lemma. The finite-state statement here must not be extended to countable models without normalization and well-defined, suitably regular processes.[^ref-360fc77a2a5f]
Clarity¶
The lemma distinguishes global balance, same-generator detailed balance and two-generator reverse pairing. A chain can be stationary while carrying directional flow; a separate reverse chain may cancel its weighted edges even when the forward chain does not cancel them internally. It also distinguishes an invariant formal measure from a normalized stationary probability distribution.[^ref-360fc77a2a5f]
Manages Complexity¶
Instead of solving all coupled global-balance equations directly, one can check a proposed \(\pi\), a valid \(\widetilde Q\), matched off-diagonal exit-rate sums and paired weighted rates. This can simplify a network with a recognizable reversal. It does not discover \(\pi\) or \(\widetilde Q\) automatically, and failure of one proposed pairing invalidates that proof certificate rather than proving that no stationary law exists.[^ref-360fc77a2a5f]
Abstract Reasoning¶
Check that both matrices are generators and that \(\pi\) sums to one. For each state, compare \(\sum_{j\ne i}q_{ij}\) with \(\sum_{j\ne i}\widetilde q_{ij}\)—not the full generator-row sums, which are always zero. Then verify \(\pi_iq_{ij}=\pi_j\widetilde q_{ji}\) for all distinct pairs and sum over incoming states. Only after the resulting stationary law is established should the actual reverse-rate interpretation be invoked where \(\pi_i>0\).[^ref-360fc77a2a5f]
Knowledge Transfer¶
The role structure—forward generator, candidate law, candidate reversed generator, exit equality and paired flows—transfers literally from the finite directed cycle to Walrand's queue network. Their state meanings, candidate-distribution shapes and stability requirements differ. The broader idea of proving a global invariant through local obligations may suggest future work on primes, but the named lemma remains a domain-specific CTMC theorem. Live Detailed Balance is its special case, not an asserted strict parent.[^ref-360fc77a2a5f]
[^ref-360fc77a2a5f]: Jean Walrand, “Networks—B”, in Probability in Electrical Engineering and Computer Science (Springer, 2021), original publisher chapter, §6.2.5 Theorems 6.2–6.3 and §6.3 Theorem 6.4 and proof, inspected 2026-10-01. The publisher HTML proof has an apparent \(p/\pi\) typography error; the finite-state algebra stated here has been checked independently.
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