Idle and Busy Cycles as Queue Regeneration

Empty-System Epochs as Regeneration Times

In a single-server queue, the system empties between periods of work. Those empty-system epochs provide natural points at which the future queueing evolution starts afresh: the server has no unfinished work, and future arrivals have not been affected by the past. This makes idle periods and busy periods useful cycle components. Their distributions depend on the arrival and service assumptions, so those assumptions must be stated before calculations begin.

Consider a probability space \((\Omega,\mathcal{F},\mathbb{P})\) carrying a queue with count-valued state \(Q_t\in S=\{0,1,2,\ldots\}\), where \(Q_t\) is the number of customers in the system at time \(t\ge0\). Arrivals form a Poisson process of rate \(\lambda>0\). Service is first-come, first-served, one customer at a time, and the server works whenever the system is nonempty. Service times \(S_1,S_2,\ldots\) are independent and identically distributed, independent of the arrival process, with \(S_k>0\) almost surely and \(a=\mathbb{E}[S_1]\in(0,\infty)\). Write \(\rho=\lambda a\).

For the finite-mean results below, assume \(\rho<1\). This condition ensures the busy period ends almost surely and has finite expectation. The first idle period \(I\) has the exponential distribution with rate \(\lambda\): \(\mathbb{P}(I>t)=e^{-\lambda t}\) for \(t\ge0\), and \(\mathbb{E}[I]=1/\lambda\). The busy period \(B\) begins with one arriving customer. Its length depends on that customer’s service and on all arrivals whose work is completed before the system next empties.

Proof. Let \(T_k\) be the time the system becomes empty at the end of the \(k\)th busy period, with \(T_0=0\) when the system starts empty. At \(T_k\), there is no customer in service and no remaining service requirement. By the strong Markov property of the Poisson arrival process, its arrivals after \(T_k\) have the same law as a fresh Poisson process and are independent of the history through \(T_k\). The service times of customers arriving after \(T_k\) are also fresh independent copies of \(S_1\). Thus the idle and busy components following \(T_k\) have the same joint law for each \(k\), and are independent of the preceding cycles. This proves the cycle assertion. The strong Markov property used here is a standard result for Poisson processes.

For the busy-period formula, regard the initial customer as the root of a family tree. The arrivals during that customer’s service are its children; arrivals during each child’s service are that child’s children, and so on. Given service length \(S_1\), the number of children is Poisson with mean \(\lambda S_1\). Each child initiates an independent busy-period subtree. Conditional on \(S_1\) and on \(K\), the number of children, the transform of the root’s service plus all child busy periods is \(e^{-sS_1}b(s)^K\). Averaging over \(K\) uses the Poisson generating function: $$ \mathbb{E}[b(s)^K\mid S_1]=\exp\{-\lambda S_1(1-b(s))\}. $$ Taking expectation over \(S_1\) gives the stated transform equation.

For the mean, let \(Z_n\) be the number of customers in generation \(n\), with \(Z_0=1\). Each customer has expected number \(\lambda a=\rho\) of children, so conditioning on generation \(n\) gives \(\mathbb{E}[Z_{n+1}]=\rho\mathbb{E}[Z_n]\). Induction yields \(\mathbb{E}[Z_n]=\rho^n\). Since \(\rho<1\), \(\mathbb{P}(Z_n>0)\le\mathbb{E}[Z_n]=\rho^n\to0\); hence the family tree becomes extinct almost surely. Each generation has finite size almost surely, so extinction implies a finite total number of customers and a finite busy period almost surely.

The service times in generation \(n\) have not been used to determine that generation’s size: its size is determined by earlier generations’ services and arrivals. They are therefore independent of \(Z_n\), and the expected total service in generation \(n\) is \(a\mathbb{E}[Z_n]=a\rho^n\). Summing the nonnegative generation totals and using monotone convergence, $$ \mathbb{E}[B]=\sum_{n=0}^{\infty}a\rho^n=\frac{a}{1-\rho}. $$ This proves the theorem. \(\square\)

Calculating Cycle Components

The transform equation applies beyond exponential service. Define the service-time Laplace transform \(\beta(q)=\mathbb{E}[e^{-qS_1}]\) for \(q\ge0\). Then the busy-period equation is \(b(s)=\beta(s+\lambda(1-b(s)))\). For exponential service with rate \(\mu>0\), \(\beta(q)=\mu/(\mu+q)\), so the transform equation becomes a quadratic. In either setting, the relevant solution is the transform value in \([0,1]\); algebraic roots outside this interval cannot be transforms.

Why the Stability Condition Matters

The condition \(\rho<1\) is not a technical decoration. It makes the expected number of customers in generation \(n\) decrease geometrically, which is what made the mean busy-period sum finite. At the boundary, the same calculation shows the problem: if service times are exponential with \(\lambda=\mu=1\), then \(a=1\) and \(\rho=1\). The expected number in every generation is \(1\), and expected service in every generation is also \(1\). The sum of these expected generation services is infinite, so the busy-period expectation is infinite. The finite-mean cycle calculations above therefore do not apply at this boundary.

Common mistake. It is incorrect to set the mean busy period equal to the mean of one service time. For the exponential example with \(\lambda=2\) and \(\mu=5\), that mistake gives \(1/5\). It counts only the initial customer and ignores arrivals during service that create further work. The correct calculation includes all generations: $$ \mathbb{E}[B]=\frac15+\frac15\left(\frac25\right)+\frac15\left(\frac25\right)^2+\cdots =\frac13. $$ The first term is the initial customer’s expected service; the remaining terms account for descendants. In contrast, the idle period ends at the first arrival, so its mean is \(1/\lambda\), not \(1/\mu\).