The Gold Standard of Queueing Theory | Doob h-Transforms, Q-Processes and Conditioned Queue Dynamics

Find the mechanism before the formula

A killed queue eventually empties, fails or leaves the observed network. Asking it to survive far into the future changes which paths are likely: states with better long-run survival prospects receive more weight. The Q-process is the limiting dynamics of that conditioning, and the Doob h-transform is the mechanism that builds it.

We will distinguish a quasi-stationary snapshot from conditioned path dynamics, transform a two-state killed chain by hand, calculate its invariant law, repeat the calculation under a harmless rescaling, and mark the assumptions that make an infinite-horizon Q-process legitimate.

This guide belongs to the Gold Standard of Queueing Theory, the Gold Standard of Education and the How X Works hub.

Choose a reading route

Start with the question closest to the decision you need to make. Every route returns to the same worked evidence and transfer checks.

Chapter contents

Open the group you need, then use the chapter links. Teaching sections remain open on the page.

1. Begin with a process that can genuinely disappear

Let Q be the transition matrix restricted to active queue states. Its row sums can be below one because the missing mass is absorption: an empty system, a completed workload, a buffer failure or departure from an observed routing network. Q is therefore substochastic, not an ordinary transition matrix.

Conditioning on survival does not remove absorption from the model. It changes the probability assigned to active paths while the original killing rule remains the reference event. State that rule first, together with the time scale and initial state.

• Define the absorbing event physically.
• Retain the original substochastic operator.
• Separate finite-horizon conditioning from an infinite-horizon limit.
• Report how rare survival becomes in the unconditioned model.

Reading routes · Contents · Next chapter

2. The survival eigenfunction measures future persistence

For a finite irreducible transient class, let λ be the dominant eigenvalue of Q and let h be a strictly positive right eigenvector satisfying Qh=λh. The value h(i) measures relative long-horizon survival propensity from state i. Multiplying h by any positive constant changes no probability in the transformed chain.

The left eigenvector describes the quasi-stationary distribution, while the right eigenvector changes the path dynamics. Confusing those orientations is one of the most common mistakes in a Q-process calculation.

Reading routes · Previous chapter · Contents · Next chapter

3. The Doob h-transform turns survival weighting into transitions

In discrete time, define P^Q_ij=Q_ijh(j)/(λh(i)). Summing over j and using Qh=λh shows that each transformed row sums to one. The absorbing transition disappears because the new law describes a process conditioned to remain active indefinitely.

This is a change of measure, not a repair of the physical queue. Paths leading toward states with larger h receive more weight. The transformed process can have drift and long-run occupancy unlike the original queue, precisely because distant survival is an exceptional event.

Reading routes · Previous chapter · Contents · Next chapter

4. Worked example: construct the transformed transition matrix

Use Q=[[0.60,0.30],[0.20,0.50]]. Its dominant eigenvalue is λ=0.80. Solving Qh=0.80h gives h(2)=two-thirds h(1); choose h=[1,2/3].

The transformed first row is [0.60/0.80, 0.30(2/3)/0.80]=[0.75,0.25]. The second row is [0.20/(0.80·2/3), 0.50(2/3)/(0.80·2/3)]=[0.375,0.625]. Thus P^Q=[[0.75,0.25],[0.375,0.625]], and both rows sum to one.

Reading routes · Previous chapter · Contents · Next chapter

5. Worked example: combine the left and right eigenvectors

For this killed chain the quasi-stationary left eigenvector is α=[0.50,0.50]. The Q-process invariant law is proportional to α(i)h(i), giving [0.50,1/3]. After normalisation the stationary law is [0.60,0.40].

Check directly: [0.60,0.40]P^Q=[0.60,0.40]. The QSD and Q-process invariant law are not the same distribution. The first is a surviving snapshot under the original killed dynamics; the second is long-run occupancy under the conditioned path law.

Reading routes · Previous chapter · Contents · Next chapter

6. Transfer check: rescale h and recover the same process

Replace h by [3,2], exactly three times the previous vector. Every transformed probability contains h(j)/h(i), so the factor three cancels. The transition matrix remains [[0.75,0.25],[0.375,0.625]].

This scale invariance is a useful audit. If rescaling h changes the result, the implementation has normalised the wrong quantity or mixed left and right eigenvectors. The invariant law may also be computed from α(i)h(i); its final normalisation removes the same scale factor.

Reading routes · Previous chapter · Contents · Next chapter

7. Finite-horizon conditioning approaches the Q-process

Condition on survival to a distant time T. Before T, the exact transition from i to j depends on the remaining horizon through a survival probability ratio. It is generally time-inhomogeneous. Under suitable assumptions, holding an early observation window fixed and letting T grow makes those transitions converge to the time-homogeneous h-transform.

This order of limits matters. A simulation conditioned only on surviving ten steps estimates a finite-horizon bridge, not automatically the Q-process. Increase T and compare early-window transition estimates before claiming convergence.

Reading routes · Previous chapter · Contents · Next chapter

8. Conditioned queue dynamics reveal survivor bias

For a queue killed on emptying, the Q-process favours trajectories that replenish work before the empty state is reached. For a network with defective routing, it favours phases whose routing and service history postpone leakage. The resulting drift is informative about long-lived active paths, not about typical unconditioned operation.

Operationally, the Q-process can help design rare-event simulations or understand persistent congestion episodes. It should not be used to report ordinary service levels unless the conditioning event is part of the decision being made.

Reading routes · Previous chapter · Contents · Next chapter

9. Compute with residual, row-sum and simulation checks

Verify Qh−λh, positivity of h, αQ−λα and every transformed row sum. Check that the proposed invariant law stays fixed under P^Q. For larger state spaces, use logarithmic scaling for h ratios when eigenvectors vary over many orders of magnitude.

Compare the transformed chain with direct simulations conditioned on survival to increasing horizons. Record effective sample size: when survival is extremely rare, apparent agreement can be driven by a handful of reused paths or aggressive resampling.

Reading routes · Previous chapter · Contents · Next chapter

10. Limits and misconceptions

• The Q-process is not the same object as the quasi-stationary distribution.
• The h-transform changes path probabilities; it does not make the original queue immortal.
• Finite-horizon conditioning can be time-inhomogeneous.
• Positive eigenfunctions may be nonunique on infinite state spaces.
• A formal transform still needs nonexplosion and conservativity checks.
• Truncating a large queue can select the wrong eigenfunction and conditioned drift.

In countably infinite or continuous systems, existence and uniqueness require more than a numerical eigenpair. Boundary behaviour, recurrence of the transformed process and the chosen conditioning scheme must be stated.

Reading routes · Previous chapter · Contents · Next chapter

11. Frequently asked questions

Why does the right eigenvector appear?

Conditioning compares future survival from the next state with survival from the current state. That ratio is h(j)/h(i), which is governed by the right eigenfunction.

Can the Q-process return to the absorbing state?

No under the conservative transformed law. It represents the limiting dynamics conditioned on avoiding absorption, although the original process still absorbs.

Is its invariant law always α times h?

That formula holds in the standard finite-state setting after normalisation. Infinite and continuous models require the corresponding eigenmeasure, eigenfunction and integrability conditions.

Reading routes · Previous chapter · Contents · Next chapter

12. A reproducible Q-process checklist

The gold standard is to show the disappearing original mass beside the conservative transformed dynamics. The Q-process becomes clear when the snapshot law, survival function and conditioned transition law are never given the same name.

Reading routes · Previous chapter · Contents · Continue reading

Continue through the Gold Standard ecosystem

Return to the Gold Standard of Queueing Theory, the Gold Standard of Education parent, or the How X Works hub.

Read next in this subject

• Quasi-Stationary Distributions, Killing and Yaglom Limits
• GI/M/1-Type Chains, G-Matrices and First-Passage Structure
• Matrix-Analytic Methods, M/G/1-Type Chains and Rate Matrices

Authoritative reading

• Lambert, Q-processes and Doob h-transforms for processes conditioned never to become extinct
• van Doorn and Pollett, quasi-stationary distributions for discrete-state models
• Champagnat and Villemonais, uniform convergence to the Q-process