From a Busy Period to a Family Tree
In a single-server M/G/1 queue, a busy period can be long because customers arrive while earlier customers are being served. Those arrivals may in turn generate more arrivals before the system empties. A useful way to organize this dependence is to regard each customer as a parent of the arrivals that occur during that customer's service. The busy period then becomes the total service time of a branching family.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Arrivals form a Poisson process of rate \(\lambda>0\), independent of the service times. Service times are iid nonnegative random variables with distribution \(F\), mean \(b=\mathbb{E}[S]<\infty\), and Laplace transform \(\beta(s)=\mathbb{E}[e^{-sS}]\), \(s\ge0\). The queue has one work-conserving server, and a busy period starts with one customer at time \(0\), when the system was empty immediately before that customer arrived. Write \(L_t\in\{0,1,2,\ldots\}\) for the number of customers in the system at time \(t\ge0\). The busy-period duration is \(B=\inf\{t\ge0:L_t=0\}\), with \(B=0\) if the initial customer's service time is zero.
The offspring count \(K\) depends on the parent's service time. Conditional on \(S=u\), it is Poisson with mean \(\lambda u\). Thus its probability generating function \(G(z)=\mathbb{E}[z^K]\), for \(0\le z\le1\), and its mean are
Here \(\rho=\lambda b\) is the traffic intensity. The service time shared by a parent and its offspring count matters: conditional on a long service, that parent is more likely to have many children. The branching construction preserves this dependence rather than replacing service time by its mean.
Why the Branching Representation Works
During a busy period the server does not become idle before all customers in the family have been served. Every arrival during a customer's service joins that family and is served before the busy period ends. Conversely, every customer served in the busy period either is the initial customer or arrived during the service of an earlier member of the family. Therefore the family tree contains exactly the customers served during the busy period. Service intervals are disjoint; the Poisson process's independent increments (at service-start times, using its strong Markov property) and the iid service times give each customer an independent offspring count with the law above.
Proof. Let \(Z_0=1\). Given generation \(n\), each of its \(Z_n\) members has expected \(\rho\) children, independently of the other members. Hence \(\mathbb{E}[Z_{n+1}\mid Z_n]=\rho Z_n\), so induction gives \(\mathbb{E}[Z_n]=\rho^n\). The total number of customers is \(Z=\sum_{n\ge0}Z_n\). By monotone convergence, \(\mathbb{E}[Z]=\sum_{n\ge0}\rho^n=1/(1-\rho)<\infty\). A nonnegative integer-valued total that is infinite with positive probability has infinite expectation; therefore \(Z<\infty\) almost surely. Each customer's service time is finite almost surely because its mean is finite. Thus the total busy-period service time is finite almost surely. The family-tree correspondence shows that this total is \(B\).
For the transform equation, condition on the initial service time \(S\) and the number \(K\) of arrivals during it. After that service, each of the \(K\) customers starts an independent family with busy-period duration distributed as \(B\). Consequently \(B\) has the distributional decomposition \(B=S+\sum_{r=1}^{K}B_r\), where the \(B_r\) are iid copies of \(B\), independent of the initial service and its arrivals. For \(s\ge0\), conditioning first on \(S\) and \(K\) gives $$ \mathbb{E}[e^{-sB}\mid S,K] =e^{-sS}\bigl(B^*(s)\bigr)^K. $$ Conditional on \(S\), \(K\) is Poisson with mean \(\lambda S\); its probability generating function at \(z\in[0,1]\) is \(e^{-\lambda S(1-z)}\). Taking expectations therefore gives $$ B^*(s)=\mathbb{E}\!\left[e^{-sS-\lambda S(1-B^*(s))}\right] =\beta\bigl(s+\lambda(1-B^*(s))\bigr), $$ as claimed. \(\square\)
Mean Busy-Period Duration
Proof. Let \(S_{n,r}\) be the service time of member \(r\) of generation \(n\). The busy period is the sum of all service times, so $$ B=\sum_{n\ge0}\sum_{r=1}^{Z_n}S_{n,r}. $$ Whether a customer belongs to generation \(n\) is determined by the service and arrivals of its ancestors; that customer's own service time is independent of this membership and has mean \(b\). Conditional on \(Z_n\), the expected total service in generation \(n\) is therefore \(bZ_n\). By monotone convergence and the generation means already calculated, $$ \mathbb{E}[B] =\sum_{n\ge0}b\,\mathbb{E}[Z_n] =b\sum_{n\ge0}\rho^n =\frac{b}{1-\rho}. $$ This also verifies that the expected duration is finite under the stated condition. \(\square\)
The transform equation gives the same mean when differentiated at zero, provided the mean is finite. The generation argument above proves finiteness and the formula directly, so differentiation is a useful check rather than a needed assumption. In particular, \(\beta'(0)=-b\). Differentiating the transform equation at zero, where \(B^*(0)=1\), gives \(B^{*\prime}(0)=\beta'(0)(1-\lambda B^{*\prime}(0))\). Solving yields \(-B^{*\prime}(0)=b/(1-\rho)\), consistent with the theorem.
Worked Example: Offspring Counts with Two Service Durations
Suppose a service time is \(1/2\) or \(3/2\), each with probability \(1/2\), and arrivals have rate \(\lambda=1/2\). Find the offspring generating function, its mean, and the probabilities that the busy-period family contains one or two customers.
The mean service time is \(b=(1/2)(1/2)+(1/2)(3/2)=1\), so \(\rho=\lambda b=(1/2)(1)=1/2<1\). Given service time \(1/2\), the offspring count is Poisson with mean \(1/4\); given service time \(3/2\), it is Poisson with mean \(3/4\). Averaging the two Poisson generating functions gives $$ G(z)=\tfrac12e^{-(1-z)/4}+\tfrac12e^{-3(1-z)/4}. $$ Its mean is \(G'(1)=\tfrac12(1/4)+\tfrac12(3/4)=1/2\), as also follows from \(\lambda b=(1/2)(1)=1/2\).
The family has one customer exactly when the initial customer has no children. For a Poisson variable with mean \(a\), the probability of zero is \(e^{-a}\); hence $$ \mathbb{P}(Z=1)=\tfrac12e^{-1/4}+\tfrac12e^{-3/4}. $$ For exactly two customers, the initial customer must have one child, and that child must have no children. The offspring counts of different customers are independent. The unconditional probabilities of zero and one child are, respectively, $$ p_0=\tfrac12e^{-1/4}+\tfrac12e^{-3/4}, \qquad p_1=\tfrac12\left(\tfrac14e^{-1/4}+\tfrac34e^{-3/4}\right). $$ Thus \(\mathbb{P}(Z=2)=p_1p_0\). The factor \(p_1\) uses \(\mathbb{P}(\mathrm{Poisson}(a)=1)=ae^{-a}\), and \(p_0\) is the probability that the sole child has no children.
Check: The expected number of customers is \(\sum_{n\ge0}(1/2)^n=2\). The expected busy-period duration is \(b/(1-\rho)=1/(1-1/2)=2\). These are different quantities: the first counts customers, while the second sums their service times.
Worked Example: An Explicit Transform with Exponential Service
Let service times be exponential with rate \(2\), so \(b=1/2\) and \(\beta(u)=2/(2+u)\). Take arrival rate \(\lambda=1\). Compute the busy-period transform and check its value at \(s=1\).
Here \(\rho=\lambda b=1/2\). Substitution into the transform equation gives $$ B^*(s)=\frac{2}{2+s+1-B^*(s)} =\frac{2}{3+s-B^*(s)}. $$ Multiplying by the denominator and collecting terms gives $$ \bigl(B^*(s)\bigr)^2-(3+s)B^*(s)+2=0. $$ The quadratic formula gives roots $$ \frac{3+s\pm\sqrt{(3+s)^2-8}}{2}. $$ Since \(B^*(0)=1\), the root with the minus sign is the transform; the other root equals \(2\) at \(s=0\), which cannot be a Laplace transform value. Therefore $$ B^*(s)=\frac{3+s-\sqrt{(3+s)^2-8}}{2}. $$
At \(s=1\), this is \(B^*(1)=(4-\sqrt{8})/2=2-\sqrt{2}\). Substitution into the transform equation gives the right-hand side \(2/(4-(2-\sqrt{2}))=2/(2+\sqrt{2})=2-\sqrt{2}\), so the value satisfies the equation. The mean formula gives \(\mathbb{E}[B]=(1/2)/(1-1/2)=1\). Differentiating the displayed transform at zero also gives \(B^{*\prime}(0)=-1\), confirming that \(-B^{*\prime}(0)=1\).
Worked Example: Erlang-2 Service and a Mean Check
Suppose service time is the sum of two independent exponential variables, each with rate \(2\), and arrivals have rate \(\lambda=1/2\). Derive the implicit transform equation and use it to check the mean.
The service-time transform is \(\beta(u)=(2/(2+u))^2=4/(2+u)^2\), and the mean is \(b=1/2+1/2=1\). Thus \(\rho=(1/2)(1)=1/2\). The busy-period transform equation becomes $$ B^*(s)=\frac{4}{\left(s+2+\tfrac12(1-B^*(s))\right)^2} =\frac{4}{(s+\tfrac52-\tfrac12B^*(s))^2}. $$ At \(s=0\), \(B^*(0)=1\) makes the right side \(4/(5/2-1/2)^2=4/4=1\), as required.
To check the derivative, set \(D=s+\tfrac52-\tfrac12B^*(s)\). Differentiation gives \(B^{*\prime}(s)=-8D^{-3}(1-\tfrac12B^{*\prime}(s))\). At zero, \(D=2\), so \(B^{*\prime}(0)=-(1-\tfrac12B^{*\prime}(0))\). Rearranging gives \(\tfrac12B^{*\prime}(0)=-1\), hence \(B^{*\prime}(0)=-2\). The mean is therefore \(2\), agreeing with \(b/(1-\rho)=1/(1-1/2)=2\).
Assumptions and a Common Mistake
The condition \(\rho<1\) is what makes the geometric sum of expected generation sizes finite. For example, if service time is always \(1\) and \(\lambda=1\), then \(\rho=1\) and each generation has expected size \(1\). The expected total number of customers is \(\sum_{n\ge0}1=\infty\); the mean busy-period formula cannot be applied, and the expected busy-period duration is infinite. Thus the strict inequality in the theorem is essential for its finite-mean conclusion.
A common mistake is to put \(+\lambda B^*(s)\) inside the service transform. That sign does not represent the branching decomposition: each child contributes a factor \(B^*(s)\), while the Poisson generating function contributes \(e^{-\lambda S(1-B^*(s))}\). The correct argument is \(s+\lambda(1-B^*(s))\). For the exponential-service example, the incorrect sign would give \(B^*(0)=2/(2+B^*(0))\), whose positive solution is \(\sqrt{3}-1\), not \(1\). Since every Laplace transform must equal \(1\) at zero, this immediately detects the error.
The branching representation is useful because it separates two aspects of the queue: the offspring law describes how many customers a service generates, while the service-time distribution determines how long each member contributes to the busy period. It also makes clear why the mean depends on the service mean through \(\rho\), while the full transform depends on the entire function \(\beta\).
Check Your Understanding
Use the assumptions and equations in this tutorial; for numerical checks, substitute the stated parameters into the relevant formula.
- If the service mean is \(2\) and the arrival rate is \(1/4\), calculate \(\rho\) and the mean busy-period duration.
- For service time \(1\) with probability \(1/3\) and \(2\) with probability \(2/3\), and arrival rate \(1/2\), write the offspring generating function and calculate its mean.
- Explain why the total number of customers in the busy period equals the total progeny of the constructed branching process.
- For exponential service of rate \(3\) and arrival rate \(1\), write the implicit equation for \(B^*(s)\), and state the condition that permits the finite-mean formula.
- What value must any busy-period Laplace transform have at \(s=0\), and how does that check help detect a sign error in the transform equation?