Find the mechanism before the formula
A queue can have infinitely many levels and still be computationally manageable when its transition blocks repeat. Matrix-analytic methods compress that infinite structure into a small collection of phase matrices, retaining correlations that a scalar traffic rate would discard.
We will distinguish quasi-birth-and-death and M/G/1-type chains, calculate a two-phase rate-matrix step, test its spectral tail, transfer the logic to batch upward jumps, and mark where a matrix-geometric shortcut stops being valid.
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.
| Route | Chapters | Use it when |
|---|---|---|
| 1 | 1–3 | You need the level–phase model and block structure. |
| 2 | 4–5 | You want the worked rate-matrix calculation. |
| 3 | 6–8 | You need M/G/1-type recursion and transfer checks. |
| 4 | 9–10 | You must validate numerics and respect model limits. |
| 5 | 11–12 | You want FAQs and a reproducible matrix-analytic checklist. |
Chapter contents
Open the group you need, then use the chapter links. Teaching sections remain open on the page.
Build the model
Test the mechanism
1. Separate queue level from background phase
Let the state be (n,j), where n is a queue level and j is one of m background phases. The level may count customers, jobs or workload bands. The phase can record an arrival mode, service mode or environment state. A scalar model keeps n and averages away j; a matrix-analytic model keeps both.
The advantage appears when transitions repeat for all sufficiently high levels. Instead of solving an unrelated balance equation at every n, we work with a few m-by-m blocks that describe movement down, within and up between neighbouring or more distant levels.
- Define exactly what one level means.
- List the phase states and their physical interpretation.
- State discrete or continuous time.
- Keep boundary blocks separate from repeating interior blocks.
2. A QBD repeats one-level moves
In a homogeneous quasi-birth-and-death process, interior transitions move at most one level down, stay at the same level or move one level up. In discrete time these blocks are often written A₂, A₁ and A₀, with a separate boundary block B. Continuous-time generators use an analogous block-tridiagonal form.
When a stationary distribution exists, its interior level vectors have the matrix-geometric form πn=π0Rn, after the boundary convention is aligned. R is the minimal nonnegative solution of the relevant nonlinear matrix equation. It is not an arbitrary fitted transition matrix.
The scalar M/M/1 ratio ρ=λ/μ is the one-phase shadow of this construction. With several phases, R controls both decay across levels and mixing among phases.
3. The rate matrix encodes visits and tail decay
For the standard discrete-time QBD convention, R satisfies R=A₀+RA₁+R²A₂. Other row-versus-column and continuous-time conventions produce equations that look different, so a calculation must publish its block order rather than quote R without context.
The spectral radius ρ(R), the largest modulus of its eigenvalues, is central. A proper positive recurrent matrix-geometric tail requires ρ(R)<1 together with valid boundary normalisation and the model-specific drift condition. Powers of R then decay, though not every component decays at the same finite-level rate.
| Object | Meaning | Check |
|---|---|---|
| A₂ | one level down | rows and units |
| A₁ | same level | phase transitions |
| A₀ | one level up | arrival convention |
| R | level propagation | minimal nonnegative solution |
| ρ(R) | asymptotic decay control | strictly below one |
4. Worked example: propagate a two-phase level
Consider an illustrative nonnegative rate matrix R=[[0.45,0.10],[0.05,0.30]]. Let the unnormalised boundary level vector be π₀=[0.60,0.40]. Multiplying on the right gives π₁=π₀R=[0.29,0.18]. The total mass carried to the next level is 0.47, but the calculation also shows how phase composition changes.
One more multiplication gives π₂=[0.1395,0.0830], with total 0.2225. A scalar approximation based only on the first total ratio would predict 0.47²=0.2209, close here by accident. It would not recover the separate phase probabilities and need not stay close for another matrix.
This example demonstrates propagation, not derivation. In a real queue, solve R from its transition blocks, then use boundary balance and the condition that all level probabilities sum to one.
5. Worked example: read the spectral tail
The eigenvalues of the example R solve λ²−0.75λ+0.13=0, giving approximately 0.5137 and 0.2363. The spectral radius is therefore about 0.514, safely below one. At high levels, the dominant mode tends to decay by roughly this factor per level when its coefficient is nonzero.
That does not mean every adjacent probability ratio equals 0.514 at every n. Subdominant eigenmodes and boundary effects remain visible near the origin. Complex eigenvalues or non-diagonalisable matrices can also make finite-level behaviour less simple than a single geometric curve.
The changed-context test is immediate: if a fitted or computed R has spectral radius 1.02, its powers do not provide a summable stationary tail. Fix the queue or the computation; do not normalise away the warning.
6. M/G/1-type chains allow larger upward jumps
An M/G/1-type Markov chain keeps skip-free movement in one direction while allowing arbitrarily large jumps in the other, such as a service completion moving down one level and a batch arrival moving up several. Its repeating transition matrix is block Hessenberg rather than block tridiagonal.
The stationary calculation is therefore not, in general, the same simple πn=π₀Rn formula used for a homogeneous QBD. Matrix generating functions, a minimal nonnegative matrix solution and Ramaswami-type recursions recover level vectors while accounting for all permitted batch sizes.
This distinction prevents a common mistake: calling every structured chain “matrix geometric” and forcing one rate matrix to do work that belongs to an infinite block sequence.
7. Transfer check: add two-customer batches
Suppose a one-phase queue receives either one or two customers at an arrival epoch. The embedded level chain can jump from n to n+2, so the QBD tridiagonal picture is broken even though the process is still highly structured. The balance at level n depends on flows from several lower levels.
With phases, each batch-size probability becomes a matrix block Ak. The matrix generating function A(z)=ΣAkzk packages those jumps. A numerical method evaluates its minimal solution and then uses a stable recursion to form stationary level vectors.
If the two-customer probability is set to zero, the model may collapse back to a QBD. That reduction is a useful software test: the general algorithm should agree with the simpler matrix-geometric answer.
8. Boundary balance supplies scale and behaviour near zero
Interior repetition does not determine the whole stationary distribution. Empty-system rules, blocked arrivals, setup phases and server vacations appear in boundary blocks. These equations determine π₀ and connect it to the interior solution.
After solving the boundary equations, normalise with Σn≥0πn1=1. For a QBD, the infinite sum becomes π₀(I−R)−11 when ρ(R)<1. For a general M/G/1-type chain, use the level vectors produced by its recursion and a justified truncation or generating-function identity.
A correct R paired with the wrong boundary can produce a plausible-looking but physically false queue. Always test flow conservation at level zero separately.
9. Compute the minimal solution, not merely any solution
Nonlinear matrix equations can have several algebraic solutions. Queueing theory selects the minimal nonnegative solution compatible with probabilistic interpretation. Functional iteration, logarithmic reduction, cyclic reduction and invariant-subspace methods have different stability and speed properties.
Check residual norms, nonnegativity, spectral radius and stationary balance. Compare two algorithms when the system is near criticality, because R close to spectral radius one makes truncation and round-off more demanding. Report the matrix norm and stopping tolerance.
For M/G/1-type recursions, monitor loss of significance across many levels and retain tail-mass bounds. A small equation residual alone does not prove that the final normalised probabilities are accurate.
10. Limits and misconceptions
- R is not the ordinary transition matrix of the full chain.
- A QBD formula does not automatically apply to every M/G/1-type chain.
- Spectral radius below one is necessary in the matrix-geometric tail but does not replace all drift and boundary conditions.
- Phase labels must represent real state memory, not arbitrary hidden categories.
- Finite truncation needs a tail-error check.
- A stationary solution cannot describe a deliberately time-varying queue without augmentation.
Matrix-analytic structure is valuable because it keeps dependence while compressing repetition. It is not a licence to hide an infinite-state model behind an unexplained software routine.
11. Frequently asked questions
Why not average the phases first?
Averaging destroys temporal correlation between the phase and future arrivals or service. Two systems with the same phase-average rates can have different queue tails.
Is the largest entry of R its decay rate?
No. The asymptotic rate is governed by spectral structure, especially ρ(R), not by whichever individual entry happens to be largest.
Does M/G/1-type mean the service time is literally general?
The name describes a block structure analogous to an embedded M/G/1 chain. A model can have that structure even when its physical story is not a textbook M/G/1 queue.
12. A reproducible matrix-analytic checklist
| Stage | Evidence to retain |
|---|---|
| State | level and phase definitions |
| Blocks | boundary and repeating matrices |
| Class | QBD, M/G/1-type or another structure |
| Solution | matrix equation and algorithm |
| Checks | residual, nonnegativity and spectral radius |
| Output | normalisation, truncation and performance measure |
The gold standard is to publish the block convention, show one level-vector calculation and verify both the interior and boundary balance. The matrix should make phase memory visible rather than make the reasoning disappear.
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
- Markov-Additive Arrivals, Matrix Kernels and Workload Phase Memory
- Effective Bandwidth, Effective Capacity and Exponential Backlog Tails
- Busy-Period Duration, Laplace Transforms and Extinction Time