GOLD STANDARD · QUEUEING THEORY · HOW X WORKS
Find the decision hidden inside the model
An arrival count can look ordinary in the long run while short bursts are organised by an unobserved background phase. Markov-additive and Markovian arrival models keep that phase inside the workload calculation, so serial dependence is not mistaken for independent traffic.
This guide connects the Gold Standard of Queueing Theory, Gold Standard of Education, and How X Works hub.
Chapter contents and reading routes
Choose the route closest to your present task. Every chapter remains expanded, so the article also reads naturally from start to finish.
Orient phase-modulated arrivals
Work the matrix example
Build workload checks
Transfer and diagnose
Use evidence and next routes
CHAPTER 1 OF 12 · ORIENT THE PHASE
1. The count and the environment move together
A renewal model describes successive interarrival times as independent draws from one law. A Markov-additive model instead lets arrivals accumulate while a finite background chain changes phase. Conditional on the current phase, the future follows the same rule; without that phase, consecutive gaps and counts can remain dependent.
The phase need not be a literal observable mode. It may summarise traffic intensity, a source population or an operating regime. Its value is operational only when the fitted phases reproduce the dependence relevant to waiting time, overflow or staffing.
CHAPTER 2 OF 12 · ORIENT THE PHASE
2. A MAP separates silent and arrival transitions
For a Markovian arrival process, the matrix D0 contains phase transitions with no arrival and D1 contains transitions accompanied by one arrival. Their sum Q=D0+D1 is the generator of the background continuous-time chain: off-diagonal entries are nonnegative and every row of Q sums to zero.
If π is the stationary row vector satisfying πQ=0 and π1=1, the stationary arrival rate is λ=πD1 1. This matrix notation preserves which phase produced an arrival. Replacing it with λ alone discards the dependence that made the model necessary.
CHAPTER 3 OF 12 · WORK THE KERNEL
3. Work a two-phase arrival rate
Take D0=[[-5,1],[0.5,-2.5]] and D1=[[3,1],[0.5,1.5]]. Then Q=D0+D1=[[-2,2],[1,−1]]. The stationary background weights are π=(1/3,2/3).
The row sums of D1 are 4 in phase 1 and 2 in phase 2, so λ=(1/3)×4+(2/3)×2=8/3 arrivals per time unit. That rate is a necessary summary, but it does not reveal whether arrivals occur singly, in bursts or after persistent quiet phases.
CHAPTER 4 OF 12 · WORK THE KERNEL
4. The matrix kernel retains the next phase
The transform or probability kernel for an interarrival step is matrix-valued because it records both elapsed time and the phase after the arrival. For the MAP, the density matrix for the next arrival after time t has the form exp(D0t)D1. Integrating over t gives the embedded phase transition matrix when the inverse exists.
This is the bridge to queueing calculations. Service transforms are combined with phase transitions, and the workload law is a vector or matrix object before its components are summed for a marginal answer.
| Object | Keeps | Loses if reduced too early |
|---|---|---|
| Q | Background phase motion | Arrival labels |
| D0 and D1 | Silent versus arrival transitions | Nothing at the MAP level |
| λ | Mean arrival rate | Serial dependence and phase |
| Matrix kernel | Time and next phase | Only what the chosen phase model omits |
CHAPTER 5 OF 12 · WORK THE KERNEL
5. Workload has a phase as well as a height
At an arbitrary time, the workload V is the unfinished service time in the system. Under a Markov-modulated input, the joint stationary quantity is P(V≤x,J=i), not merely P(V≤x). A low workload observed in an intense phase can have a different short-term risk from the same workload in a quiet phase.
Matrix-analytic methods solve for these phase-conditioned probabilities or transforms. The final tail probability sums across phases only after the stationary phase weights and boundary conditions have been handled.
CHAPTER 6 OF 12 · BUILD THE WORKLOAD
6. Arrival epochs see a biased phase distribution
The phase distribution seen at an arbitrary time is π. The phase distribution seen just after arrivals is proportional to πD1, because phases with more arrival-labelled transitions are sampled more often by arrivals. Confusing the two is a phase version of exposure bias.
In the worked example, phase 1 has one third of clock time but a higher row arrival intensity. Customer-average delay and time-average workload therefore need not use the same phase mixture. State clearly which observer the performance measure represents.
CHAPTER 7 OF 12 · BUILD THE WORKLOAD
7. Validate matrices with count and queue consequences
A fitted MAP should reproduce more than the mean count. Check count variance across several window lengths, lagged count dependence, interarrival autocorrelation, and the distribution of runs of quiet or busy intervals. Then test the downstream quantity that motivated the model, such as waiting-time quantiles.
Different matrix parameterisations can generate similar low-order count moments. Hold out complete time blocks and compare predictive workload or overflow, not just likelihood on the fitting sample.
| Check | Question | Failure signal |
|---|---|---|
| Windowed variance | Is clustering present at several scales? | Variance curve misses shape |
| Lagged counts | Does phase persistence match? | Residual serial dependence |
| Arrival-phase mix | Are arrivals sampling phases correctly? | Wrong customer-average delay |
| Held-out workload | Does dependence matter operationally? | Tail error despite count fit |
CHAPTER 8 OF 12 · TRANSFER AND DIAGNOSE
8. Changed-context transfer: packets to emergency calls
A network source may switch between low and high packet intensity. An emergency-call centre may switch with weather, public events or incident clusters. Both can use a background phase, but the observable covariates, persistence and decision horizon differ.
Transfer succeeds when the analyst rebuilds the phase interpretation and tests it against new count windows. Copying the same two-state matrices because both datasets look bursty is not a mechanism.
CHAPTER 9 OF 12 · TRANSFER AND DIAGNOSE
9. Know when a batch model is required
A MAP records at most one arrival on each D1-labelled transition. If events arrive in groups, a batch Markovian arrival process uses matrices Dk for transitions carrying k arrivals. The generator is the sum over k, and the mean rate weights each matrix by k.
Forcing a batch process into a single-arrival MAP can mimic clustering by rapid phase switches, but the resulting workload and customer grouping may be wrong. Preserve whether simultaneous records are genuine batches or merely coarse timestamps.
CHAPTER 10 OF 12 · TRANSFER AND DIAGNOSE
10. Limits and common misconceptions
A background phase is not automatically a discovered physical state. Phase labels can be permuted, parameterisations can be weakly identified, and adding phases can improve in-sample fit without improving tail prediction. Select dimension with held-out evidence and stability checks.
Markov-additive structure also does not repair nonstationarity by itself. If the traffic law drifts through the day, use covariates, piecewise modelling or a time-varying design rather than asking one stationary phase chain to absorb every trend.
CHAPTER 11 OF 12 · CHECK AND CONTINUE
11. Questions readers often ask
Is a two-state MAP just a mixture of two Poisson processes?
No. A static mixture chooses a rate but does not necessarily evolve through a continuous-time phase chain. A MAP labels phase transitions as arrivals or non-arrivals, creating serial dependence and a distinct arrival-epoch phase distribution.
Can I replace the MAP with a Poisson process having the same λ?
Only if the decision is insensitive to the dependence being discarded. Equal mean rates can produce different waiting tails, overflow risks and customer-average experiences. Compare those outputs before simplifying.
CHAPTER 12 OF 12 · CHECK AND CONTINUE
12. Evidence, connected routes and the next check
Neuts and related matrix-analytic work underpin the nonpreemptive priority MAP/G/1 analysis, which retains arrival phases in waiting-time and queue-length calculations. Lucantoni and co-authors’ moment matrices for MAP counts show how count moments arise from the matrix structure.
Continue through semi-regenerative hidden-state memory, regenerative cycle estimation, Lindley workloads, and vacation decomposition. The next check is to compare clock-time and arrival-epoch phase weights before reporting a delay.
Contents · Previous chapter · Return to the Queueing Theory root