Abstract
We consider the $G/G/1$ queue as an operator that maps inter-arrival times to inter-departure times of points, given the service times. For arbitrarily fixed statistics of service times, we are interested in the existence of distributions of inter-arrival times that induce identical distributions on the inter-departure times. In this note we prove, by construction, the existence of one of such distribution.
Introduction
In the study of queueing systems, a central question is how the statistical properties of arrival processes are transformed by the queueing mechanism. A landmark result in this field is Burke’s Theorem, which demonstrates that for an $M/M/1$ queue—characterized by Poisson arrivals and exponential service times—the departure process is also a Poisson process with the same rate. This "transparency" is vital for analyzing networks of queues, as it ensures that the output of one node remains a tractable input for the next.
However, the question remains: does such an invariant distribution exist for the more general $G/G/1$ queue? Given an arbitrary service time distribution, can we find an inter-arrival distribution that is preserved by the queueing operator? This paper provides a constructive proof that such a distribution exists for any fixed service time statistics.
The Queueing Operator and Lindley’s Equations
The $G/G/1$ queue can be viewed as a mathematical operator that maps a sequence of inter-arrival times $\tau$ to a sequence of inter-departure times $\tau^*$, mediated by a sequence of service times $\sigma$. The relationship between these variables is governed by Lindley’s equations, which track the waiting times and idle periods of the server. The goal is to find a fixed point for this operator—a distribution $P_\tau$ such that $P_\tau = P_{\tau^*}$.
Methodology: A Constructive Proof
Rather than relying on abstract existence theorems, the authors employ a constructive approach to identify the invariant distribution. The proof follows a sequence of logical steps involving tandem queues and limit processes:
- Tandem Queue Construction: Imagine an infinite sequence of queues arranged in tandem. Each queue has independent and identically distributed (i.i.d.) service times drawn from the fixed distribution $P_\sigma$.
- The Saturated Initial State: The system is initialized by assuming the first queue in the sequence is "saturated" or "heavy-headed," meaning it is never idle and always has a customer waiting to be served.
- Pathwise Evolution: The inter-departure times from the first queue serve as the inter-arrival times for the second, and so on. The authors track the evolution of these inter-departure times as they pass through successive stages of the tandem.
- Monotonicity and Convergence: The authors demonstrate that the inter-departure times change monotonically as they progress through the infinite series of queues. This monotonicity ensures that the sequence of distributions converges to a stable limit.
Key Insights
The Critical State
The invariant distribution identified by this construction corresponds to a queue operating at its "critical" limit. In this state, the arrival rate exactly matches the service rate. This is a significant finding, as it characterizes the boundary between stable and unstable queueing behavior.
Pathwise Convergence
A notable aspect of the proof is its reliance on pathwise limits. For a specific realization of service times, the sequence of inter-departure times settles into a specific value as it passes through the infinite tandem. This suggests a robust relationship between the input and output processes at the limit.
Dependencies in the Process
While the $M/M/1$ case is famous for producing independent inter-departure times, the authors note that in the general $G/G/1$ case, the invariant distribution may involve complex dependencies between successive inter-arrival times. Even if the service times are i.i.d., the resulting invariant process is not necessarily a simple renewal process.
Conclusion and Future Directions
This research successfully proves that for any service time distribution, an invariant inter-arrival distribution exists and can be constructed via the limit of a saturated tandem queue.
However, several questions remain open. The authors acknowledge that the finiteness of the resulting inter-arrival times requires further investigation under specific service time constraints. Furthermore, the study focuses on the critical case where the arrival rate equals the service rate. The paper concludes with a conjecture: for any stationary and ergodic service time sequence and any arrival rate lower than the service rate, there should exist a unique stationary arrival process that remains invariant. Proving this conjecture remains a significant challenge for future work in queueing theory.
Summary updated