GOLD STANDARD · QUEUEING THEORY · HOW X WORKS
Find the decision hidden inside the model
A GI/G/1 queue replaces the convenient exponential assumptions with general independent interarrival and service times. Lindley’s recursion then gives a small, exact bookkeeping rule for the unfinished workload seen by each arrival—and makes the stability boundary visible without pretending that a mean determines the whole wait distribution.
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.
Start with the workload recursion
Work the arrival-by-arrival ledger
Understand stability and stationary limits
Transfer the model and test evidence
Use sources and connected routes
CHAPTER 1 OF 12 · DEFINE THE WORKLOAD
1. The state is unfinished work, not just a headcount
In a single-server first-come queue, two lines with the same number of jobs can imply very different waits. Three one-minute jobs leave less unfinished work than one twenty-minute job. The workload state records the service time still required before a new arrival can begin.
Let Wn be the waiting time, or equivalently the workload just before customer n starts service under the usual GI/G/1 assumptions. Let Sn be customer n’s service requirement and An+1 the time until the next arrival. Between arrivals, the server removes work; a queue cannot hold negative work.
CHAPTER 2 OF 12 · DEFINE THE WORKLOAD
2. Lindley’s recursion is a reflected balance equation
The update is Wn+1 = max(0, Wn + Sn − An+1). Add the arriving customer’s service requirement to the work already ahead, subtract the service delivered before the next arrival, then reflect any negative result at zero.
This identity does not require exponential interarrival or service times. It does require a clearly defined single work-conserving server, ordered arrivals and consistent service requirements. Priorities, vacations, simultaneous batches or feedback need an adapted state or a different recursion.
CHAPTER 3 OF 12 · BUILD THE LEDGER
3. Build the ledger one arrival at a time
Start empty with W1 = 0. Take service times 4, 7, 2 and 5 minutes, with following interarrival gaps 3, 6 and 5 minutes. The next waits are max(0,0+4−3)=1, then max(0,1+7−6)=2, then max(0,2+2−5)=0.
The last zero matters: the server clears all prior work before the fourth arrival. Do not carry a negative value forward. The reflection is the moment an idle period begins.
| Arrival | Wait before service | Service time | Next gap | Next wait |
|---|---|---|---|---|
| 1 | 0 min | 4 min | 3 min | 1 min |
| 2 | 1 min | 7 min | 6 min | 2 min |
| 3 | 2 min | 2 min | 5 min | 0 min |
CHAPTER 4 OF 12 · BUILD THE LEDGER
4. The same means can hide different paths
Reorder the same service times to 7, 4, 2, 5 while keeping the gaps 3, 6 and 5. The waits become 0, 4, 2 and 0. The average service time and average interarrival gap are unchanged, yet the transient path differs because a long job arrives earlier.
GI/G/1 notation says the sequences are generally distributed and independent within the standard model. It does not say their realised order is irrelevant. A mean-level load calculation is a stability clue, not a reconstruction of every wait.
CHAPTER 5 OF 12 · BUILD THE LEDGER
5. Connect the recursion to a random walk
Define the increment Xn = Sn − An+1. Lindley’s equation repeatedly adds these net-input increments but prevents the workload from crossing below zero. Its stationary waiting-time distribution, when it exists under standard conditions, is tied to the maximum of a random walk with negative mean drift.
That connection explains why rare clusters of positive increments can create a large wait even when the average drift is negative. It also shows why tail behaviour depends on more than utilisation: variability and dependence shape the upward excursions.
CHAPTER 6 OF 12 · TEST STABILITY
6. Stability means negative average workload drift
With finite positive means, traffic intensity is ρ = E[S]/E[A]. The familiar stable GI/G/1 condition is ρ < 1, equivalently E[S] < E[A]. Average service requirement per arrival is then smaller than average service time available between arrivals.
At ρ = 1 there is no spare average drift to pull a growing workload back. At ρ > 1, net input is positive on average. Finite buffers or abandonment may keep the recorded queue bounded, but only by rejecting or losing work; that is a changed outcome, not proof of adequate capacity.
CHAPTER 7 OF 12 · TEST STABILITY
7. A worked stability and sensitivity check
Suppose mean service is 5 minutes and mean interarrival time is 6 minutes. Then ρ = 5/6 ≈ 0.833. If mean interarrival falls to 5.2 minutes while service stays unchanged, ρ ≈ 0.962. Both values are below one, but the second leaves far less spare drift.
The table is deliberately not a waiting-time forecast. GI/G/1 mean wait also depends on distributional information and may be very large when service times are heavy-tailed. Near the boundary, small measurement errors in either mean can change the operational interpretation.
| Case | E[S] | E[A] | ρ | Interpretation |
|---|---|---|---|---|
| Baseline | 5.0 min | 6.0 min | 0.833 | Negative drift with margin |
| Busier arrivals | 5.0 min | 5.2 min | 0.962 | Stable baseline, narrow margin |
| Boundary | 5.0 min | 5.0 min | 1.000 | No negative mean drift |
CHAPTER 8 OF 12 · TRANSFER AND CHECK
8. Changed-context transfer: a feedback queue
Move from a service desk to student feedback. An assignment joins one tutor’s review queue, service time is active review, and the interarrival gap is time between submissions. Lindley’s bookkeeping still applies if one ordered server works continuously on one stream.
The transfer breaks when submissions arrive as simultaneous class batches, tutors share work, or a draft returns for revision. Then batch arrivals, parallel servers or feedback loops must enter the model. Successful transfer preserves the balance structure while rebuilding the boundary.
CHAPTER 9 OF 12 · TRANSFER AND CHECK
9. Estimate the inputs without completed-only bias
A snapshot that averages only completed jobs can miss long jobs still in service or waiting. Preserve arrival time, service start, service end and right-censoring at the observation boundary. Separate calendar delay from active service.
Check stationarity rather than assuming it. Plot interarrival and service distributions by time, regime and job type. Serial dependence, scheduled bursts and service slowdowns under load violate the simplest independent-sequence model and can make a fitted GI/G/1 baseline optimistic.
CHAPTER 10 OF 12 · TRANSFER AND CHECK
10. Limits and common misconceptions
ρ < 1 does not promise a short wait, and ρ close to one is not the only route to long tails. A heavy-tailed service distribution can create rare but dominant backlogs. Independence is an assumption, not something guaranteed by the letter G.
The recursion gives waiting before service in the stated FCFS workload model. It does not automatically include the arriving customer’s own service time, downstream stages, abandonment, priorities or server setup. State which clock and population each quantity uses.
CHAPTER 11 OF 12 · EVIDENCE AND ROUTES
11. Questions readers often ask
A finite sample can show decreasing workload even when the long-run system is unstable, or a severe temporary backlog in a stable model. Stability is a property of the assumed process and its long-run drift, not a label attached to one short trace.
Is GI/G/1 the same as G/G/1?
GI/G/1 usually emphasises independent, identically distributed interarrival and service sequences. G/G/1 is sometimes used more broadly. Read the author’s definitions rather than inferring every assumption from the label.
Can the recursion be used in a spreadsheet?
Yes. One row per arrival with columns for prior workload, service requirement, next gap and the reflected update is a strong audit. The spreadsheet is exact for the supplied sequence; forecasting still needs a defensible process model.
CHAPTER 12 OF 12 · EVIDENCE AND ROUTES
12. Evidence, connected routes and the next check
D. V. Lindley’s 1952 single-server paper established the general recursion. The Indian Institute of Science GI/GI/1 lecture derives the random-walk connection and stability condition, while the GI/GI/1 teaching notes connect workload, traffic intensity and bounds.
Continue through unfinished jobs and right-censored service times, Markov-modulated arrivals and serial dependence, and Burke’s theorem and the special Poisson case. The next evidence check is to rebuild the workload ledger from raw event timestamps and compare its empty periods with the observed server-idle record.
Contents · Previous chapter · Return to the Queueing Theory root