The M/PH 2/1 Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks

arXiv:2608.06414 · cs.PF, math.PR · Submitted 2026-08-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The M/PH 2/1 Queue".

Paper summary: Tom: So to summarize this paper, "The M/PH two/one Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks," the main thesis is that they provide explicit closed-form distributions for all four two-phase phase-type service models: Erlang-two hypoexponential-two hyperexponential-two and Coxian-two > <ref:2608.06414#pg1,Erlang-2, hypoexponential-2, hyperexponential-2, and Coxian-2>

Jane: They claim to derive the queue length distribution as pn equals A1 r to n one plus A2 r to n two and the sojourn time density as fWs t equals c1 e alpha one t plus c2 e alpha two t >

Lu: The authors argue that they achieve this by combining both the scalar transform tradition, using the Pollaczek–Khinchine formula, with a matrix-spectral approach based on eigenvalue decomposition of the rate matrix >

Meng: They claim this results in ready-to-use formulas where every coefficient is given as an explicit function of system parameters and consolidated in reference tables >

Tom: The real significance they point to is that because these are functions rather than just numerical values, they support analytical operations like exact sensitivity derivatives and closed-form threshold optimization >

Jane: So, instead of just running a simulation to guess how sensitive the results are to a parameter change, you can calculate it exactly using these formulas >

Lalam: They also prove that the two-phase phase-type queues mark the boundary of algebraic tractability >

Conclusion: Tom: Looking at "The M/PH two/one Queue: Explicit Distributions, Sojourn Times and Numerical Benchmarks," the authors Yossi Luzon put out these explicit formulas for the queue length distribution and sojourn times for all four models > <ref:2608.06414#pg1>

Jane: What does that mean in simple terms for someone listening? It means that if you are designing a system where service times can be described by those two-phase behaviors—like a patient waiting in a hospital or a call center agent being busy—you have the math to calculate exactly what the queue looks like and how long things will take >

Lu: The implication is that researchers and practitioners who model service systems with these two-phase distributions now have access to ready-to-use formulas for queue length, sojourn times, tail probabilities, and sensitivity measures >

Meng: For me at the operational level, it means we can move beyond just running models to having a mathematical backbone for designing better capacity sizing based on exact distribution properties >

Lalam: The work essentially serves as that reference point because it gives these people the formulas they need when they are trying to model service systems with two-phase distributions >

Yossi Luzon

School of Industrial Engineering and Management, AFEKA – The Tel Aviv Academic College of Engineering

cs.PF, math.PR

Submitted: 2026-08-05

Updated: 2026-11-14

Comments: 18 pages, 10 figures, 5 tables. v3: revised and restructured as a reference; title changed. Verification scripts included as ancillary files

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 89/100

The gist: Two-phase phase-type (P H2) service distributions are widely used in call center, healthcare and manufacturing models…

Key concepts

Phase-Type (PH) Distributions
These distributions model service times that can take on a variety of specific, discrete values rather than just continuous ones. They are used in complex systems like call centers or manufacturing where service processes have distinct stages or patterns, allowing for more detailed statistical modeling.
Pollaczek–Khinchine (PK) Formula
This is a foundational formula used to find the generating function for the steady-state queue-length distribution in queueing theory. It links the system's arrival and service rates to how many customers are waiting in line at any given time.
Matrix–Spectral Tradition
This approach uses linear algebra, specifically eigenvalue decomposition of a rate matrix (R), to derive the same results as the PK formula. It provides an alternative mathematical framework for analyzing phase-type queues by focusing on the system's rate structure.

Terminology

Summary

Two-phase phase-type (P H2) service distributions are widely used in call center, healthcare and manufacturing models: they capture coefficients of variation both above and below unity while remaining parsimonious enough for reliable statistical fitting. p. 0

Where the paper says it

Two-Phase Phase-Type Queues: Closed-Form Distributions, Sensitivity Analysis and the Boundary of Algebraic Tractability Yossi Luzon∗ August 11, 2026 Abstract Two-phase phase-type (P H2) service distributions are widely used in call center, healthcare and manufacturing models: they capture coefficients of variation both above and below unity while remaining parsimonious enough for reliable statistical fitting. We derive explicit closed-form queue-length distributions pn = A1r n 1 + A2r n 2 and sojourn-time densities fWs (t) = c1e α1t + c2e α2t for the complete M/P H2/1 family (Erlang-2, hypoexponential-2, hyperexponential-2 and Coxian-2), with every coefficient given as an explicit function of the system parameters and consolidated in ready-to-use reference tables.

The paper derives explicit closed-form queue-length distributions pn = A1r n 1 + A2r n 2 and sojourn-time densities fWs(t) = c1e α1t + c2e α2t for the complete M/P H2/1 family. p. 0
Where the paper says it

Two-Phase Phase-Type Queues: Closed-Form Distributions, Sensitivity Analysis and the Boundary of Algebraic Tractability Yossi Luzon∗ August 11, 2026 Abstract Two-phase phase-type (P H2) service distributions are widely used in call center, healthcare and manufacturing models: they capture coefficients of variation both above and below unity while remaining parsimonious enough for reliable statistical fitting. We derive explicit closed-form queue-length distributions pn = A1r n 1 + A2r n 2 and sojourn-time densities fWs (t) = c1e α1t + c2e α2t for the complete M/P H2/1 family (Erlang-2, hypoexponential-2, hyperexponential-2 and Coxian-2), with every coefficient given as an explicit function of the system parameters and consolidated in ready-to-use reference tables.

This work is significant because it provides ready-to-use formulas that support analytical operations like exact sensitivity derivatives and closed-form threshold optimization, which are inaccessible through numerical output alone. p. 0
Where the paper says it

We derive explicit closed-form queue-length distributions pn = A1r n 1 + A2r n 2 and sojourn-time densities fWs (t) = c1e α1t + c2e α2t for the complete M/P H2/1 family (Erlang-2, hypoexponential-2, hyperexponential-2 and Coxian-2), with every coefficient given as an explicit function of the system parameters and consolidated in ready-to-use reference tables. Because the results are functions rather than numerical values, they support analytical operations that numerical output cannot deliver directly: exact sensitivity derivatives, closed-form threshold optimization, capacity sizing by bisection on an exact cumulative distribution, and O(1) tail-probability evaluation at arbitrary queue length.

Analytical Framework

The paper establishes a unified analytical framework by combining the scalar transform tradition, rooted in the Pollaczek–Khinchine (PK) formula, and the matrix–spectral tradition, which operates with phase-type generators and rate matrices. The PK formula provides a generating function P(z) for the steady-state queue-length distribution, while the matrix approach uses eigenvalue decomposition of the rate matrix R to derive it. p. 4

Where the paper says it

In each case, the distribution takes the form pn = A1r n 1 + A2r n 2 , where the coefficients and geometric ratios are explicit functions of the queue parameters. These expressions were derived by substituting each model’s service-time LST into the PK formula (1), performing partial-fraction decomposition on the resulting rational generating function, and cross-validating all results against eigenvalue decomposition of the corresponding QBD rate matrix (Appendix E) as well as the Tak´acs probability generating function series expansion.

The paper notes that both traditions yield the same geometric form pn = A1r n 1 + A2r n 2 for two-phase queues, but neither has provided these expressions in a unified, explicit treatment for the complete P H2 family. p. 1
Where the paper says it

The scalar approach derives queue-length distributions by inverting PGFs via partial fractions; the matrix approach derives them by computing the rate matrix R and its spectral decomposition. Both yield the same geometric form pn = A1r n 1 +A2r n 2 for two-phase queues, but neither tradition has provided these expressions in a unified, explicit, directly usable treatment for the complete P H2 family.

Closed-Form Results

The paper presents explicit steady-state distributions for all four two-phase models: M/E2/1, M/Hypo2/1, M/Hyper2/1, and M/Coxian2/1. For the queue-length distribution, the results are given by pn = A1r n 1 + A2r n 2. p. 0

Where the paper says it

We derive explicit closed-form queue-length distributions pn = A1r n 1 + A2r n 2 and sojourn-time densities fWs (t) = c1e α1t + c2e α2t for the complete M/P H2/1 family (Erlang-2, hypoexponential-2, hyperexponential-2 and Coxian-2), with every coefficient given as an explicit function of the system parameters and consolidated in ready-to-use reference tables. Because the results are functions rather than numerical values, they support analytical operations that numerical output cannot deliver directly: exact sensitivity derivatives, closed-form threshold optimization, capacity sizing by bisection on an exact cumulative distribution, and O(1) tail-probability evaluation at arbitrary queue length.

Furthermore, for sojourn-time distributions, fWs(t) = c1e α1t + c2e α2t is derived directly from the PK sojourn-time LST. p. 2
Where the paper says it

Drawing on both the PK formula and eigenvalue decomposition, and cross-validating all results through multiple independent methods including the Tak´acs series expansion, we derive: • Queue-length distributions: pn = A1r n 1 + A2r n 2 , with all coefficients and geometric ratios given as explicit functions of system parameters. • Sojourn-time distributions: fWs (t) = c1e α1t + c2e α2t , derived directly from the PK sojourn-time transform, with explicit poles and residues for each model.

The paper shows that the two-exponential form for sojourn times contrasts with conditioning on N, yielding a more compact and directly usable form. p. 8
Where the paper says it

This two-exponential form contrasts with the conditioning-on-N approach, which produces sojourn-time expressions involving infinite sums of incomplete gamma functions (Erlang-type services) or confluent hypergeometric functions (hyperexponential services). The PK transform route yields the same distributions in a more compact and directly usable form.

Numerical Validation and Accuracy Characterization

The paper validates the closed-form solutions against numerical computations from the matrix-analytic library BuTools. The validation reveals distinct failure modes within the same software: queue-length computation via cyclic reduction achieves machine-precision accuracy across all tested configurations, while sojourn-time computation relies on the matrix exponential and exhibits accuracy degradation of up to ten significant digits when high traffic intensity and high service variability act jointly. p. 3

Where the paper says it

Queuelength computation via cyclic reduction achieves machine-precision accuracy across the entire parameter space tested. Sojourn-time computation, however, relies on the matrix exponential, and our experiments reveal accuracy degradation of up to ten significant digits when high ρ and high C 2 s act jointly.

This highlights that closed-form expressions bypass both limitations. p. 3
Where the paper says it

Sojourn-time computation, however, relies on the matrix exponential, and our experiments reveal accuracy degradation of up to ten significant digits when high ρ and high C 2 s act jointly. The closed-form expressions bypass both limitations.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Exact queue-length distribution calculation allows for O(1) tail-probability evaluation at arbitrary queue length, which is superior to iterative matrix-power computation that eventually underflows at large n.

  2. Sensitivity analysis can be performed exactly using the closed-form expressions, yielding an exact closed-form expression involving partial derivatives of the coefficients, rather than relying on finite-difference approximations.

  3. Capacity sizing can be achieved by bisection on an exact cumulative distribution to find the smallest buffer n star such that P(N = 1 - epsilon, bypassing numerical truncation errors.

  4. Sojourn-time accuracy at extreme parameters is maintained by closed-form results, as they bypass the numerical sensitivity of the matrix exponential when high traffic intensity and high service variability act jointly.

  5. The system can determine which thresholds are exposed to case-mix drift and through which channel by using an exact affine law for the elasticity of overflow risk, where the slope equals the elasticity of the dominant geometric ratio.

Abstract

Two-phase phase-type (PH 2) distributions are among the service-time models used most often in applied queueing, because they capture coefficients of variation above and below one with few parameters. This note collects, in one place and in ready-to-use form, the stationary queue-length distribution p n = A 1 r 1 n + A 2 r 2 n and the sojourn-time density f W s(t) = c 1 e α 1 t + c 2 e α 2 t for the M/E 2/1, M/Hypo 2/1, M/Hyper 2/1 and M/Coxian 2/1 queues, with every coefficient written in the parameters that a fitting procedure returns. None of these results is new in substance; however, obtaining them from the general theory takes work that each user would otherwise have to repeat. The formulas are obtained from the Pollaczek-Khinchine transforms, related to the matrix-geometric and phase-type representations of the same queues, and verified numerically in 40-digit arithmetic. The note also gives the matrices needed to reproduce the results in standard software, a comparison with the matrix-analytic library BuTools, formulas for tail and threshold quantities and their derivatives, and a worked example calibrated to published surgical-time data.

Related papers