📊 statistics

Transient Probabilities and Switching Levels in a Vacation Queue with Catastrophes

This paper analyzes a discrete-time single-server queue with vacations and catastrophes by employing a two-color Motzkin path representation to derive transient and stationary probabilities, establish a composition scheme for service-return cycles, and identify distinct relaxation factors and critical scaling behaviors.

Original authors: Igor Kleiner

Published 2026-10-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Igor Kleiner

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computer networks, traffic control systems, and even the lines at a bank, there is a constant struggle to manage how things arrive and how they are served. Imagine a single server, like a lone cashier or a single data processor, that handles a stream of customers or tasks. Sometimes, this server takes a break, a period known as a "vacation," where it stops working but the customers keep arriving and piling up. When the server returns, it must clear the backlog. However, in some chaotic systems, a sudden disaster, or "catastrophe," can wipe out the entire line instantly, sending everyone back to zero. Understanding how these systems behave over time—how likely it is that the line is empty at a specific moment, or how long the server stays on vacation before returning—is crucial for designing efficient systems. Mathematicians and scientists study these patterns using probability, trying to predict the future state of a system based on its current rules.

A researcher at the Holon Institute of Technology has taken a deep dive into this problem, focusing on a specific type of queue where the server takes vacations and faces the risk of sudden catastrophes. The study looks at two main questions. First, if you check the system at a random, fixed moment, what is the likelihood of finding it in a specific state, such as empty or busy? Second, if you look at a long cycle of activity that ends when the last customer is served, how many customers were waiting at the exact moment the server finished its vacation and switched back to work? To answer these, the researcher used a clever visual method, mapping the movement of customers onto a grid. In this map, time moves forward step by step, and the height of the path represents the number of people in line. Different colors on the path show whether the server is on vacation or working, and special steps show when the server switches roles or when a catastrophe clears the line.

The study reveals that the way a system relaxes, or settles down, into a steady pattern is more complex than previously thought. It turns out that the probability of finding the system completely empty can decay toward its long-term average at a different speed than the probability of the server simply being on vacation. In other words, the system does not settle into a calm state all at once; different parts of the system calm down at their own unique rates. The researcher provided a specific example where the error in predicting an empty system shrinks by a factor of 30 out of 32 with each step, while the error in predicting the vacation state shrinks by a factor of 31 out of 32. This separation of speeds is a significant finding because it shows that looking at just one part of the system, like the empty state, does not tell the whole story of how the entire system is stabilizing.

When the researcher examined long cycles of activity, specifically those that end with the server clearing the last customer, they discovered a precise mathematical relationship between the length of the cycle and the number of customers present when the vacation ended. By treating the switch from vacation to work as a specific point to mark, the study found that the number of customers follows a predictable pattern that depends on the weights of the different events, such as arrivals and services. In a critical scenario where the system is balanced on the edge of stability, the researcher derived an exact formula for the average number of customers waiting at the switch. This formula involves specific counting numbers known as central trinomial coefficients, which allow for a precise calculation of the average wait, along with corrections that become smaller as the cycle gets longer.

The work also bridges the gap between discrete steps and continuous time. While the model counts time in distinct slots, like seconds on a clock, the researcher showed how to translate these results into a continuous flow, similar to how water flows in a pipe. By using a method called uniformization, which connects the step-by-step probabilities to a smooth timeline, the study confirms that the same underlying patterns hold true whether time is measured in ticks or in a continuous stream. This allows the findings to be applied to real-world systems that operate in continuous time, such as telecommunications networks or manufacturing lines.

Ultimately, the paper provides a complete toolkit for understanding the transient, or temporary, behavior of these complex queues. It moves beyond just calculating the final, steady state and explains exactly how the system gets there. By breaking down the path of the queue into its fundamental components—arrivals, stays, switches, and catastrophes—the researcher has created a clear picture of the system's journey. The findings confirm that while the system eventually reaches a stable state, the path to that stability is nuanced, with different aspects of the system relaxing at different rates. This level of detail is essential for engineers and scientists who need to predict not just where a system will end up, but how it behaves along the way, ensuring that systems remain efficient and resilient even when faced with sudden disruptions or long periods of inactivity.

Technical Summary: Transient Probabilities and Switching Levels in a Vacation Queue with Catastrophes

Problem Statement
This research investigates a discrete-time, single-server queueing system characterized by two distinct regimes: a "vacation" regime (blue) and a "working" regime (red). The system operates under specific boundary conditions: the server enters a vacation when the system is empty and can only return to work when the queue reaches a positive level. Crucially, the system is subject to "catastrophes" in either regime, which instantaneously empty the queue and return the process to the empty vacation state.

The paper addresses two primary observation problems:

Fixed-Time Transient Analysis: Determining the joint distribution of the queue level and server regime at a prescribed time slot $n$ , specifically analyzing the relaxation rates of individual states versus aggregate events (such as the entire vacation regime).
Switch Level in Long Cycles: Analyzing the queue level at the moment the server switches from vacation to work, conditioned on the service-return cycle having a prescribed large length $n$ .

Methodology
The author employs a combinatorial approach using two-color lattice paths (Motzkin paths) to represent system trajectories.

Path Representation: The horizontal axis represents time slots, and the vertical axis represents the number of customers. Blue steps denote the vacation regime, and red steps denote the working regime.
- Up-steps: Arrivals.
- Down-steps: Service completions (red only) or catastrophes (jump to zero).
- Horizontal steps: Stays (ordinary) or regime switches (vacation to work).
Generating Functions and Kernel Method: The study utilizes generating functions to encode path weights. Key techniques include:
- First-Passage Decomposition: Decomposing trajectories into completed returns to the empty state and an uncompleted positive prefix.
- Kernel Cancellation: Solving functional equations for the generating functions of red and blue prefixes by identifying and canceling kernel roots.
- Singularity Analysis: Applying analytic combinatorics to extract asymptotic behavior from the singularities of the generating functions.
- Uniformization: Mapping the discrete-time slot probabilities to continuous-time probabilities using a Poisson clock mechanism.

Key Contributions and Results

Transient and Stationary Laws:
- The paper derives explicit generating functions for the transient state probabilities ( $b_{n,i}$ and $r_{n,i}$ ) by decomposing paths into sequences of first returns and a final uncompleted prefix.
- It establishes the stationary distribution, showing that the system is positive recurrent under specific conditions (e.g., when catastrophe rates are positive or service rates exceed arrival rates).
- A conditional distributional decomposition is provided for the stationary level, expressing the queue length as a sum of independent geometric random variables conditioned on the regime.
Divergent Relaxation Rates:
- A significant finding is that in a common-rate family (where arrival and catastrophe probabilities are equal across regimes), the relaxation rate of a specific fixed state (e.g., the empty state) can differ from the relaxation rate of the aggregate vacation regime.
- The author provides an explicit example where the error for the empty state decays with a factor of $(30/32)^n$ , while the error for the probability of being in the vacation regime decays with $(31/32)^n$ . This demonstrates that the convergence of the total variation distance is governed by the aggregate behavior, not necessarily the fastest-decaying individual state.
Switch Level in Service-Return Cycles:
- For cycles conditioned on length $n$ , the paper analyzes the distribution of the queue level at the moment of the vacation-to-work switch.
- Using composition schemes and singularity analysis, the author identifies three scaling regimes (bounded, square-root, and linear) for the switch level, depending on the relationship between the system parameters (specifically the competition between the zero of the blue generating function and the branch point of the red kernel).
- At criticality, the paper derives an exact finite-length mean for the switch level in terms of central trinomial coefficients, along with its asymptotic corrections.
Combinatorial Correspondence:
- The paper establishes a bijection between the two-color service-return cycles and ordinary Motzkin excursions. Specifically, the level at the switch corresponds to the source height of the first down-step in the associated ordinary Motzkin path. This provides a direct combinatorial interpretation of the vacation-ending statistic.
Continuous-Time Recovery:
- The discrete-time results are shown to recover continuous-time transient probabilities via uniformization, validating the discrete model as a robust framework for analyzing continuous-time vacation queues with catastrophes.

Significance and Claims
The paper claims to advance the understanding of vacation queues with disasters by providing a unified path-based framework that handles both transient and stationary behaviors. Its primary theoretical contribution is the demonstration that local and aggregate relaxation rates can be distinct, challenging the assumption that the slowest-decaying state dictates the convergence of the entire system's distribution.

Furthermore, the work bridges discrete-time queueing analysis with advanced combinatorial methods (Motzkin paths, singularity analysis), offering exact finite-length formulas and precise asymptotic limits for the "switch level"—a statistic previously difficult to characterize in the presence of catastrophes. The author positions this work as a complement to their previous manuscript (Paper I), which focused on disaster-free models, by extending the two-color event-clock model to include catastrophic resets and analyzing the specific conditioning problems of fixed-time states and long-cycle switch levels.

Technical Summary: Transient Probabilities and Switching Levels in a Vacation Queue with Catastrophes

More like this