Conditioned Functional Limits and Applications to Queues

Harsha Honnappa, Rahul Jain, Amy R. WardarXiv 2017 · DOI · arXiv

Abstract

This paper investigates renewal processes conditioned on a fixed number of events occurring within a specified time horizon. We establish that a centered and scaled version of this process converges to a Brownian bridge as the number of events grows large. This derivation relies on first proving a functional strong law of large numbers (FSLLN) to determine the appropriate centering. Unlike standard renewal processes, the conditioning destroys independence; however, we demonstrate that the resulting triangular arrays of random variables maintain exchangeability. By constructing martingale difference sequences, we prove functional limit theorems that generalize the known behavior of conditioned Poisson processes. Finally, we apply these results to queueing theory, showing that the workload process of a single-server queue with conditioned arrivals can be approximated by a reflected diffusion driven by the sum of a Brownian bridge and a standard Brownian motion.

Introduction: Modeling the "Rush Hour"

In classical queueing theory, systems are typically analyzed in "steady state" (long-term averages) or under "heavy traffic" conditions (where arrival rates nearly match service capacity). However, many real-world scenarios—such as vaccination clinics, call centers, or scheduled appointments—operate on a finite horizon with a known, fixed population of customers.

Consider a clinic with 500 appointments scheduled between 9:00 AM and 5:00 PM. In this scenario, the total number of arrivals is not a random variable governed by a rate, but a fixed constraint. Mathematically, this is a conditioned renewal process. While Poisson processes under such conditioning are well-understood due to their "Order Statistics" property (where arrivals behave like uniform random variables), general renewal processes with non-exponential inter-arrival times lack this property. This paper addresses the gap by determining how these conditioned processes behave as the number of events ($n$) becomes large.

Mathematical Framework and Methodology

To analyze these systems, the authors move away from the assumption of independent inter-arrival times. Once we condition on the total number of events in a fixed window, the time between arrivals becomes dependent: if many arrivals occur early, fewer must occur later to satisfy the fixed total.

Triangular Arrays and Exchangeability

The study utilizes triangular arrays to manage the sequence of processes as $n$ increases. Although conditioning destroys independence, the authors prove that it preserves exchangeability—the property that any permutation of the arrival sequence is equally likely. This allows the application of specialized limit theorems that do not require the strict independence found in standard renewal theory.

Martingale Techniques

To prove the Functional Strong Law of Large Numbers (FSLLN) and the Functional Central Limit Theorem (FCLT), the authors construct martingale difference sequences with respect to these triangular arrays. By leveraging martingale convergence results and tools like the Azuma-Hoeffding inequality, they demonstrate that the scaled counting process settles into a predictable shape with quantifiable fluctuations.

Key Insights: The Brownian Bridge Emergence

The central discovery of this research is that general conditioned renewal processes converge to a Brownian bridge. A Brownian bridge is a stochastic process that is "tied down" at both the start (time 0) and the end (the fixed horizon $T$).

This emergence highlights the "depleting points" effect: in a conditioned queue, the pool of remaining arrivals shrinks over time. This creates long-range correlations where the history of the process dictates its future trajectory more strictly than in an unconditioned system. Crucially, the authors show that this Brownian bridge limit holds regardless of the service rate, providing a robust tool for transient analysis that does not rely on the system being in "heavy traffic."

Applications to Queueing Performance

The paper illustrates the practical utility of these limits by applying them to the workload process of a single-server ($GI/GI/1$) queue. Using the Skorokhod Reflection Mapping, the authors model the physics of a server processing a queue where the workload cannot drop below zero.

Theorem 4.1 establishes that the fluctuations of the arrival process around its mean converge to a Brownian bridge. When this is fed into the regulator mapping, the resulting workload approximation is a reflected diffusion. The input to this diffusion is the sum of:

  1. A Brownian bridge, representing the uncertainty in arrival timings.
  2. A standard Brownian motion, representing the uncertainty in service times.

This provides a closed-form approximation for managers to predict queue lengths and wait times in scheduled environments without needing complex, computationally expensive simulations.

Conclusion and Future Directions

This work generalizes the asymptotic behavior of conditioned Poisson processes to a much broader class of renewal models. By proving that the Brownian bridge is the universal limit for these systems, the authors provide a rigorous foundation for studying transient queueing behavior.

Future research may expand these findings in several directions:

  • Non-I.I.D. Arrivals: Relaxing the assumption that underlying inter-arrival times are independent and identically distributed before conditioning.
  • Complex Networks: Moving beyond the single-server model to multi-stage systems, such as hospital workflows or manufacturing lines.
  • Operational Tools: Developing software implementations of these Brownian bridge approximations to assist in real-time capacity planning for appointment-based services.

Summary updated

Abstract

We consider a renewal process that is conditioned on the number of events in a fixed time horizon. We prove that a centered and scaled version of this process converges to a Brownian bridge, as the number of events grows large, which relies on first establishing a functional strong law of large numbers result to determine the centering. These results are consistent with the asymptotic behavior of a conditioned Poisson process. We prove the limit theorems over triangular arrays of exchangeable random variables, obtained by conditionning a sequence of independent and identically distributed renewal processes. We construct martingale difference sequences with respect to these triangular arrays, and use martingale convergence results in our proofs. To illustrate how these results apply to performance analysis in queueing, we prove that the workload process of a single server queue with conditioned renewal arrival process can be approximated by a reflected diffusion having the sum of a Brownian Bridge and Brownian motion as input to its regulator mapping.
BibTeX
@misc{honnappa2017conditioned,
  author = {Harsha Honnappa and Rahul Jain and Amy R. Ward},
  title = {{Conditioned Functional Limits and Applications to Queues}},
  year = {2017},
  eprint = {1711.02148},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.02148},
}

Loading related content...

Figure