From Queue Trajectories to Cycle Rewards
A queue’s long-run performance is often expressed through quantities observed continuously in time: the average number of customers in the system, the average number waiting, or the average unfinished service workload. Regeneration gives a direct way to calculate these quantities. Divide time into cycles that begin and end in the same probabilistic state, calculate the reward accumulated during one cycle, and compare its expected value with the expected cycle duration.
Let \((X_t)_{t\ge0}\) be a queueing process on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with time index \(t\ge0\). Suppose \(0=T_0<T_1<T_2<\cdots\) are regeneration times: after each \(T_k\), the future evolution has the same law as a fresh process and is independent of the past. Define the cycle duration \(C_k=T_k-T_{k-1}\). For a measurable rate \(r(X_t)\), the reward in cycle \(k\) is \(R_k=\int_{T_{k-1}}^{T_k}r(X_t)\,dt\). For example, choosing \(r(X_t)\) as the number in the system makes \(R_k\) the area under the customer-count path during that cycle.
The ratio uses the reward and duration from the same full cycle. A cycle may include an idle interval with zero customer-count reward, but that idle time still belongs in the denominator. The theorem concerns a time average, not the average reward per busy period or the reward seen at arrival epochs.
Queue Metrics as Cycle Rewards
Write \(N_t\) for the number of customers in the system at time \(t\), including any customer in service. The time-average number in the system, when the limit exists, is \(L=\lim_{t\to\infty}t^{-1}\int_0^t N_s\,ds\). The number waiting, excluding a customer in service, is \(Q_t=(N_t-1)^+\), where \(x^+=\max(x,0)\). If \(V_t\) is the total remaining service requirement, then \(V_t\) is the workload, measured in units of service time. Each is a rate function to which the renewal-reward theorem can be applied when its cycle reward is integrable.
For an empty-to-empty cycle, let \(C\) be its duration. The system-count reward is \(R_N=\int_0^C N_s\,ds\); the waiting-queue reward is \(R_Q=\int_0^C Q_s\,ds\); and the workload reward is \(R_V=\int_0^C V_s\,ds\). Thus \(L=\mathbb{E}R_N/\mathbb{E}C\), with analogous expressions for the time averages of \(Q_t\) and \(V_t\), provided the cycle assumptions hold. These integrals are areas: a customer present for two time units contributes two customer-time units to \(R_N\).
Proof. If \(N_t=0\), then \(Q_t=0\) and \(N_t-\mathbf{1}_{\{N_t>0\}}=0\). If \(N_t\ge1\), one customer is in service and \(N_t-1\) are waiting, so \(Q_t=N_t-1=N_t-\mathbf{1}_{\{N_t>0\}}\). Integrating this pointwise identity from \(0\) to \(C\) gives the cycle-reward identity. Applying the renewal-reward theorem to each integrand gives the asserted identity between the corresponding long-run rates. \(\square\)
Worked Example: Customer Counts in a Stable M/M/1 Queue
Worked Example: Customer Counts in a Stable M/M/1 Queue
Consider a single-server queue with Poisson arrivals of rate \(\lambda\) and independent exponential service times of rate \(\mu\), where \(0<\lambda<\mu\). The system regenerates whenever it becomes empty. We calculate the mean cycle duration and the expected area under \(N_t\) in a cycle, then find the long-run customer count and waiting-queue length.
An empty period has exponential duration with mean \(1/\lambda\). During a busy period, when the system contains \(i\ge1\) customers, arrivals occur at rate \(\lambda\) and service completions at rate \(\mu\). The generator has off-diagonal rates \(q_{i,i+1}=\lambda\) and \(q_{i,i-1}=\mu\), with \(q_{ii}=-(\lambda+\mu)\); each such row sums to zero. Put \(\delta=\mu-\lambda>0\).
Let \(b_i\) be the expected time to reach zero starting from \(i\) customers. The expected first holding time is \(1/(\lambda+\mu)\), after which the next state is \(i+1\) with probability \(\lambda/(\lambda+\mu)\) or \(i-1\) with probability \(\mu/(\lambda+\mu)\). The candidate \(b_i=i/\delta\), with \(b_0=0\), satisfies $$ \frac{1}{\lambda+\mu}+ \frac{\lambda}{\lambda+\mu}\frac{i+1}{\delta}+ \frac{\mu}{\lambda+\mu}\frac{i-1}{\delta} =\frac{i}{\delta}. $$ The expected hitting time is finite: for \(h_i=i/\delta\), the generator gives \(Qh(i)=-1\). Applying the stopped generator identity before reaching zero, a finite level \(K\), or time \(t\), bounds the expected stopped time by \(h_i\); letting \(K,t\) increase shows the expected time to zero is at most \(h_i\). First-step conditioning then gives the recurrence for \(b_i\). The difference between any two solutions of that recurrence with \(b_0=0\) has form \(a((\mu/\lambda)^i-1)\); the finite expectation bound and the linear candidate rule out \(a\ne0\). Hence \(b_i=i/\delta\), and a busy period starting with one customer has mean \(1/\delta\).
Now let \(g_i\) be the expected integral of the number in the system from the start of a busy period with \(i\) customers until it reaches zero. First-step conditioning gives $$ g_i=\frac{i}{\lambda+\mu}+ \frac{\lambda}{\lambda+\mu}g_{i+1}+ \frac{\mu}{\lambda+\mu}g_{i-1},\qquad g_0=0. $$ To solve it, apply the generator to \(f_i=A i^2+B i\). Direct expansion yields $$ Qf(i)=2A(\lambda-\mu)i+A(\lambda+\mu)+B(\lambda-\mu). $$ Setting this equal to \(-i\) gives \(A=1/(2\delta)\) and \(B=(\lambda+\mu)/(2\delta^2)\). Thus \(f_i=i^2/(2\delta)+(\lambda+\mu)i/(2\delta^2)\).
This solution is indeed the expected area, not just a formal recurrence solution. The stopped generator identity for the nonnegative function \(f\), stopped before zero, level \(K\), or time \(t\), gives an expected accumulated area at most \(f_i\), since \(Qf(i)=-i\) and the terminal value of \(f\) is nonnegative. Increasing the stopping limits shows that \(g_i\le f_i\), so the area is integrable and first-step conditioning is valid. The difference of two recurrence solutions has form \(a((\mu/\lambda)^i-1)\); the bound \(g_i\le f_i\), which grows quadratically, forces \(a=0\). Therefore $$ g_1=f_1=\frac{1}{2\delta}+\frac{\lambda+\mu}{2\delta^2} =\frac{\mu}{\delta^2}. $$
A full cycle consists of the idle period and the busy period. Its expected duration is \(1/\lambda+1/\delta=\mu/(\lambda\delta)\). The idle-period customer-count reward is zero, so the expected full-cycle customer-count reward is \(g_1=\mu/\delta^2\). The renewal-reward ratio gives \(L=\lambda/\delta\). The expected busy time per cycle is \(1/\delta\), so the busy fraction is \((1/\delta)/(\mu/(\lambda\delta))=\lambda/\mu\). The proposition then gives the average number waiting as \(\lambda/\delta-\lambda/\mu=\lambda^2/(\mu\delta)\).
Check: The cycle reward divided by the cycle duration is \((\mu/\delta^2)/(\mu/(\lambda\delta))=\lambda/\delta\), as obtained. Also, the waiting average is nonnegative because \(\lambda^2/(\mu\delta)>0\) under \(0<\lambda<\mu\).
Workload Rewards Under Exponential Service
For the same M/M/1 queue, workload has a useful cycle-level relation to customer count. Given that there are \(n\) customers in the system at time \(t\), the remaining service of the customer in service is exponential with mean \(1/\mu\), by the memoryless property. The \(n-1\) waiting customers have independent exponential service requirements with the same mean. Therefore the conditional expected workload is \(n/\mu\). This conditional statement is used only when \(N_t=n\); it is valid because exponential service is memoryless and the queue is observed without revealing future service requirements.
Proof. At each time \(t\) before the cycle ends, condition on the current customer count. The conditional expectation just established gives \(\mathbb{E}[V_t\mid N_t]=N_t/\mu\). Multiply by the indicator that the cycle has not ended by time \(t\), then take expectations. Integrate over \(t\ge0\). Since workload and customer count are nonnegative, Tonelli’s theorem permits exchanging expectation and integration, giving $$ \mathbb{E}\int_0^C V_t\,dt =\int_0^\infty\mathbb{E}\big[V_t\mathbf{1}_{\{t<C\}}\big]\,dt =\frac{1}{\mu}\int_0^\infty\mathbb{E}\big[N_t\mathbf{1}_{\{t<C\}}\big]\,dt =\frac{1}{\mu}\mathbb{E}\int_0^C N_t\,dt. $$ The cycle customer-count reward is integrable by the preceding calculation, so this also proves workload-reward integrability. Dividing both expected rewards by the same finite expected cycle duration proves the long-run statement. \(\square\)
Worked Example: Workload and Waiting Customers
Take \(\lambda=1\) and \(\mu=2\). The stability condition holds, and \(\delta=\mu-\lambda=2-1=1\). The expected idle time is \(1/\lambda=1\), and the expected busy time is \(1/\delta=1\), so the expected full-cycle duration is \(1+1=2\).
The expected customer-count area in the busy period is \(\mu/\delta^2=2/1^2=2\); the idle-period area is zero. Hence \(L=2/2=1\). The expected workload area is the customer-count area divided by \(\mu\), namely \(2/2=1\), so the average workload is \(1/2\). The busy fraction is \(1/2\), and the average waiting-queue length is \(1-1/2=1/2\).
Check: The independent formulas give \(L=\lambda/\delta=1/1=1\), average workload \(L/\mu=1/2\), and average waiting-queue length \(\lambda^2/(\mu\delta)=1^2/(2\cdot1)=1/2\). These agree with the cycle calculations.
Worked Example: A Deterministic Regenerative Queue
Consider a single-server queue that starts empty, remains idle for exactly one time unit, then receives one customer with a service requirement of exactly two time units. No other customer arrives before service is complete, and the same pattern repeats. Each empty-to-empty cycle has duration \(C=1+2=3\). During the two-unit service interval, \(N_t=1\), so the cycle customer-count reward is \(R_N=1\cdot2=2\). Thus the long-run average number in the system is \(2/3\). No customers wait, so the waiting-queue reward is zero.
During service, workload decreases linearly from \(2\) to \(0\); during the idle period it is zero. The workload reward is $$ R_V=\int_0^2(2-t)\,dt =\left[2t-\frac{t^2}{2}\right]_0^2 =4-2=2. $$ Therefore the time-average workload is also \(2/3\).
Check: In each cycle, customer count is one for two of the three time units, giving \(2/3\). The workload triangle has base \(2\) and height \(2\), giving area \((2\cdot2)/2=2\); dividing by the cycle duration \(3\) again gives \(2/3\). This example uses a different service and arrival pattern, but the same cycle-reward calculation.
Conditions and a Common Mistake
The renewal-reward ratio requires independent, identically distributed cycles with finite positive mean duration and integrable cycle reward. In the M/M/1 calculation, \(0<\lambda<\mu\) ensures the busy period has finite mean and the expected customer-count reward is finite. If \(\lambda\ge\mu\), the finite-cycle formulas above do not apply as a stable empty-to-empty regenerative calculation.
The finite-mean condition on cycle duration cannot simply be omitted. For example, let cycle durations be independent with \(\mathbb{P}(C_k>x)=1/(1+x)\) for \(x\ge0\), so \(\mathbb{E}C_k=\infty\), and let each cycle deliver one unit of reward at its endpoint. The extended strong law gives the sum of the first \(n\) cycle durations divided by \(n\) tending to infinity; consequently the number of completed cycles per unit time tends to zero. The reward rate is therefore zero, while the usual ratio \(\mathbb{E}R_1/\mathbb{E}C_1\) is not a finite-mean renewal-reward formula. This example shows why finite expected cycle duration is a substantive hypothesis.
Common mistake: In the M/M/1 example with \(\lambda=1,\mu=2\), dividing the busy-period reward \(2\) by the expected busy-period duration \(1\) gives \(2\). That is the reward rate within busy periods, not the long-run rate across calendar time. The full cycle also includes an idle period of expected duration \(1\), during which the customer-count reward is zero. The correct calculation is \(2/(1+1)=1\). Zero reward does not mean zero elapsed time.
| Queue quantity | Cycle reward | Long-run rate |
|---|---|---|
| Number in system | \(\int_0^C N_t\,dt\) | \(\mathbb{E}R_N/\mathbb{E}C\) |
| Number waiting, one server | \(\int_0^C (N_t-1)^+\,dt\) | System average minus busy fraction |
| Workload | \(\int_0^C V_t\,dt\) | \(\mathbb{E}R_V/\mathbb{E}C\) |
Check Your Understanding
For each question, identify the cycle reward and denominator before calculating a rate.
- Why must an idle interval with zero customer-count reward still be included in the cycle duration?
- In a single-server queue, express the waiting-queue reward using the system-count reward and the total busy time in a cycle.
- For an M/M/1 queue with \(0<\lambda<\mu\), state the expected full-cycle duration in terms of \(\lambda\) and \(\mu\).
- Under exponential service of rate \(\mu\), what is the expected workload conditional on \(N_t=n\), and which property of the service distribution is used?
- Which renewal-reward assumption fails if the cycle duration has infinite mean?