Idle Periods and Busy-Cycle Lengths

From an Empty System to a Complete Cycle

When an M/M/1 queue empties, the server waits for the next arrival. That wait is an idle period. The arrival starts a busy period, which ends when the system next empties. Together, one idle period and the busy period that follows form a complete cycle. This decomposition separates a simple waiting time from the more involved duration of a busy spell.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). The queue-length process \((X_t)_{t\ge0}\) has state space \(S=\{0,1,2,\ldots\}\) and continuous time. Arrivals form a Poisson process of rate \(\lambda>0\); service times are independent exponential random variables of rate \(\mu>0\), independent of arrivals. The server works whenever \(X_t>0\), and customers are served one at a time. Write \((\mathcal{F}_t)_{t\ge0}\) for the history of arrivals, service completions, and queue lengths up to time \(t\). Assume throughout that \(0<\lambda<\mu\), the stability condition for the M/M/1 queue. In particular, a busy period begun by one customer ends in finite time almost surely and has finite mean.

At an empty system, no service is in progress. Thus the first arrival after that time starts the busy period, and the wait for that arrival determines the idle period. The Poisson arrival assumption gives the idle-period law directly.

Proof. The event \(I>t\) means that no arrival occurs during the interval of length \(t\) following the start of the idle period. The number of arrivals in that interval has the Poisson distribution with mean \(\lambda t\), so its probability of being zero is \(e^{-\lambda t}\). This proves the survival formula. Differentiating the distribution function \(1-e^{-\lambda t}\) gives \(f_I(t)=\lambda e^{-\lambda t}\). For \(s\ge0\), integration gives \(\mathbb{E}[e^{-sI}]=\int_0^\infty e^{-st}\lambda e^{-\lambda t}\,dt=\lambda/(\lambda+s)\). Integrating \(t f_I(t)\), or using the tail integral, gives \(\mathbb{E}[I]=\int_0^\infty e^{-\lambda t}\,dt=1/\lambda\). \(\square\)

Busy and Complete-Cycle Transforms

The busy period starts with one customer, so its distribution is the busy-period distribution for a queue initially containing one customer. The earlier material on busy periods gives its transform. Here is a short derivation to show how it enters the cycle calculation. During a customer’s service, arrivals can be viewed as descendants of that customer; each such arrival in turn has descendants arriving during its service. This constructs a branching tree of customers. The expected number of children per customer is \(\lambda\mathbb{E}[S]=\lambda/\mu<1\), where \(S\) is an exponential service time of rate \(\mu\). If generation \(n\) consists of descendants at depth \(n\), its expected size is \((\lambda/\mu)^n\). The probability that this generation is nonempty is at most its expected size, which tends to zero. Thus the tree has finitely many generations almost surely; because each customer has finitely many arrivals during its finite service time, the tree has finitely many customers almost surely. The busy period is therefore finite almost surely.

Let \(b(s)=\mathbb{E}[e^{-sB}]\). Given the first service time \(S\), the number of arrivals during it is Poisson with mean \(\lambda S\). Each of those arrivals initiates a descendant busy period with the same transform \(b(s)\). The total busy duration is the first service time plus the busy durations generated by those arrivals. Conditioning on \(S\), and then averaging over \(S\), yields \[ b(s)=\mathbb{E}\!\left[e^{-sS}b(s)^{N(S)}\right] =\frac{\mu}{\mu+s+\lambda(1-b(s))}, \] where \(N(S)\) is the number of arrivals during the first service. The last equality follows because, given \(S\), the Poisson probability generating function is \(\mathbb{E}[z^{N(S)}\mid S]=e^{-\lambda S(1-z)}\), and \(S\) has exponential rate \(\mu\).

Proof. First, multiplying the busy-transform equation by its denominator gives $$ \lambda b(s)^2-(\lambda+\mu+s)b(s)+\mu=0. $$ The quadratic formula gives roots $$ \frac{\lambda+\mu+s\ \pm\ \sqrt{(\lambda+\mu+s)^2-4\lambda\mu}}{2\lambda}. $$ For \(s>0\), a Laplace transform of a nonnegative random variable is at most \(1\). The root with the plus sign is greater than \(1\), so it cannot equal \(b(s)\). The minus-sign root is the transform. At \(s=0\), the two roots are \(1\) and \(\mu/\lambda>1\), and \(b(0)=1\), as required. Hence $$ b(s)=\frac{\lambda+\mu+s-\sqrt{(\lambda+\mu+s)^2-4\lambda\mu}}{2\lambda}. $$ The idle period is independent of the busy period that follows: the future arrival process after the first arrival has independent Poisson increments, and service times are independent of arrivals and of one another. The idle and busy durations therefore have independent transforms, so $$ \mathbb{E}[e^{-sC}] =\mathbb{E}[e^{-sI}]\mathbb{E}[e^{-sB}] =\frac{\lambda}{\lambda+s} \frac{\lambda+\mu+s-\sqrt{(\lambda+\mu+s)^2-4\lambda\mu}}{2\lambda}, $$ which is the stated expression. At the end of a busy period the system is empty. The independent-increments and memoryless properties of the Poisson arrival and exponential service processes give the same law for the future as at the start of the preceding cycle, independent of the past. Repeating this argument at each empty epoch shows that successive pairs of idle and busy durations, and hence successive complete-cycle lengths, are independent and identically distributed. \(\square\)

At \(s=0\), the transform must equal \(1\), because \(C\) is finite almost surely. Indeed, the square root becomes \(\sqrt{(\lambda+\mu)^2-4\lambda\mu}=\mu-\lambda\), using \(\mu>\lambda\), so the numerator is \(2\lambda\), equal to the denominator. This is a useful check on the formula before using it for calculations.

Cycle Means and the Role of Stability

Because \(I\) and \(B\) are independent and have finite means in the stable case, the mean complete-cycle length is the sum of their means. The idle-period result gives \(\mathbb{E}[I]=1/\lambda\). The busy-period mean follows either from the busy-period transform or from the expected total service time of the branching tree: generation \(n\) has expected size \((\lambda/\mu)^n\), and each customer has mean service time \(1/\mu\). Summing the expected service contributions gives $$ \mathbb{E}[B]=\frac1\mu\sum_{n=0}^\infty\left(\frac{\lambda}{\mu}\right)^n =\frac1{\mu-\lambda}. $$ The geometric series converges because \(\lambda/\mu<1\). Consequently, $$ \mathbb{E}[C]=\frac1\lambda+\frac1{\mu-\lambda} =\frac{\mu}{\lambda(\mu-\lambda)}. $$

The stability condition is not a cosmetic assumption. If \(\lambda>\mu\), the branching offspring mean \(\lambda/\mu\) exceeds \(1\); the customer tree has positive probability of never becoming extinct, so the busy period can be infinite and a finite complete cycle need not occur. At the boundary \(\lambda=\mu\), extinction occurs almost surely but the expected total number of customers, and hence the expected busy-period duration, is infinite. The formulas for finite cycle means therefore require the strict inequality \(\lambda<\mu\).

Common mistake. The complete-cycle transform is the product of the idle and busy transforms. Multiplying by \(\lambda/(\lambda+s)\) cancels the \(2\lambda\) in the busy-transform denominator, but it does not remove the \(\mu\) from the busy-transform numerator. For \(\lambda=1\), \(\mu=3\), and \(s=1\), omitting that term would give $$ \frac{1+1-\sqrt{(1+3+1)^2-4(1)(3)}}{2(1+1)} =\frac{2-\sqrt{13}}4<0, $$ which is impossible for a Laplace transform. The correct numerator is \(1+3+1-\sqrt{13}=5-\sqrt{13}>0\), and the transform is \((5-\sqrt{13})/4\), as obtained by multiplying the two component transforms.