Why average load is not enough
A service station can receive work at a lower average rate than it processes work and still accumulate a queue: arrivals and service completions do not occur at perfectly regular times. A model can quantify this variability, but its conclusion belongs to its stated assumptions.
Definition 8.3.1
(The M/M/1 queue and its traffic intensity)
Customers arrive as a Poisson process of rate , service times are independent exponential random variables of rate , and arrivals and services are independent. One server works whenever the system is nonempty, serving customers first come, first served; the waiting room is unlimited and no customer leaves early. Let count customers waiting or in service. It is a continuous-time Markov chain that jumps from to at rate and from to at rate . The traffic intensity is .
Stationary balance
Theorem 8.3.2
(Stationary distribution of the M/M/1 queue)
If , the queue-length chain has the unique stationary distribution
If , it has no stationary probability distribution.
Proof
(Balance equations force a geometric distribution)
A stationary distribution must satisfy balance of total flow. At zero, . At ,
The zero equation gives . If for some , subtracting it from the equation at leaves . By induction for all , so any stationary distribution must have .
If , normalization gives , hence . Conversely, these probabilities sum to one and satisfy the balance equations. For this irreducible nonexplosive birth–death chain, a normalized invariant distribution is the unique stationary distribution; we use this standard continuous-time Markov-chain fact here.
If , the forced sequence has a divergent sum unless , in which case every . Neither can sum to one, so no stationary probability distribution exists. This is a stationary statement, not a claim that every finite observed queue must increase at every moment.
Proof X-ray
From one global equation per state to one cut equation per edge
The non-obvious move is the induction that turns each total-flow equation into the simpler statement that flow from up to equals flow from down to . It works because the chain only jumps between neighbors: a cut between and is crossed by exactly one upward and one downward transition. Once the cut equations hold, the geometric form is immediate.
The hypothesis is used at exactly one point, normalization. The balance equations themselves hold for every ; what fails for is that the forced sequence cannot be a probability distribution. Uniqueness is not proved here: it comes from irreducibility and nonexplosiveness through the cited Markov-chain fact. Substituting into the formula would give , which signals the violated hypothesis rather than a negative probability.
Mean occupancy and a capacity comparison
Theorem 8.3.3
(Stationary means)
For , in stationarity
where counts waiting customers only.
Proof
(Summing the geometric distribution)
Differentiating gives , so
The server is busy exactly when , with probability . Since , we get .
These are stationary averages, not hard capacity bounds or guarantees for a particular time.
Worked example 8.3.4
(A stable station)
With and per hour, . The stationary probabilities are , the mean number in the system is , and the mean number waiting is . A busy probability of does not say that exactly two customers are always present.
Worked example 8.3.5
(Comparing two service rates)
Suppose an illustrative operating model charges cost units per hour for capacity and three cost units per expected customer in the system per hour. Compare only the choices and , keeping . For , and . The total cost rates are and , so is better among these two choices. The capacity charge is an explicit modeling assumption, not a universal staffing law, and this comparison does not establish an optimum over other service rates.
Worked example 8.3.6
(A nearly critical load)
Keep and raise the arrival rate to . Then and
An arrival-rate increase of percent, from to , multiplies the mean occupancy by . As approaches one the stationary mean grows without bound, and at no stationary distribution exists.
Common mistakes
Counterexample mode
A finite average does not bound every observation
In the station with arrival rate 2 and service rate 3, every stationary probability is positive. The stationary average occupancy is two, yet the probability of seeing at least three customers is the geometric tail, . Average occupancy should not be presented as a maximum queue size.
Common mistake
(Using the stable formulas when )
With and , the formula gives customers. The number is meaningless: the theorem's hypothesis fails and there is no stationary distribution to average over.
Common mistake
(Confusing customers in the system with customers waiting)
counts the customer in service; does not. In the stable station they are and . The difference is the busy probability , not , because the server is idle with probability .
Exercises
Quick check
(With and , calculate , and .)
Solution · Answer
, , and .
Quick check
(In the stable station with , , compute in stationarity.)
Solution · Answer
The geometric tail is .
Quick check
(Explain why has no stationary probability distribution under this model.)
Solution · Answer
At , balance forces for every . A constant nonnegative sequence sums to or diverges, so it never sums to one.
Quick check
(With and , find the stationary busy probability and the mean waiting count.)
Solution · Answer
, so the busy probability is and .