🔢 mathematics

A unified evolution theory for workload distributions with mixed atomic and continuous components in Markov processes

This paper proposes a unified measure-theoretic framework that characterizes the evolution of mixed atomic and continuous workload distributions in scalar Markov processes through coupled equations, successfully recovering classical results and extending the analysis to complex systems involving dead bands, regime switching, and hysteresis control.

Original authors: Carlos Colchero, Jorge E. Pérez-García, Oliver Probst

Published 2026-09-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Carlos Colchero, Jorge E. Pérez-García, Oliver Probst

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 hidden machinery of modern life, from the flow of data through a server farm to the movement of goods in a warehouse, there is a constant struggle to manage waiting. Systems are rarely empty, nor are they perpetually full; they exist in a state of fluctuation, absorbing bursts of activity and then slowly processing them. To understand how these systems behave over time, scientists often look at "workload," a measure of how much is waiting to be done. In many simple cases, this workload behaves like a smooth, continuous stream, rising and falling in a predictable way. However, real-world systems are rarely that simple. They often hit a floor where the work vanishes completely, leaving the system idle. At that exact moment of emptiness, the mathematics changes. The smooth stream stops, and a distinct, sharp point of probability appears: the chance that the system is doing nothing at all. This creates a mixed picture, part smooth curve and part sharp spike, which has historically been very difficult to analyze when the rules of the system change or when the system has memory.

For decades, researchers have studied these mixed distributions on a case-by-case basis, treating each unique control mechanism as a separate puzzle. If a system had a rule that paused service when the workload was low, or if the rules changed depending on an external environment, the standard mathematical tools often failed to provide a unified view. The challenge was to find a single way to describe how the smooth part of the workload and the sharp spike of idleness interact and evolve together over time. Without such a framework, comparing different types of queues or predicting how a complex system would settle into a steady state remained a fragmented effort.

A team of researchers has now developed a unified theory that brings these scattered pieces together. They created a single mathematical framework capable of tracking both the smooth, continuous flow of work and the sudden, discrete moments of idleness as they happen simultaneously. Instead of treating the system as a single, monolithic block, they broke the problem down into two distinct but connected parts: the "atoms," which represent the probability of the system being completely empty, and the "density," which describes the likelihood of the system having a specific amount of work waiting. By representing the system's evolution as a set of rules that move probability mass between these two parts, they derived a set of coupled equations. These equations act like a map, showing exactly how the chance of idleness feeds into the busy states and how the busy states eventually collapse back into idleness.

The researchers first tested their new framework on the most basic model of a waiting line, known as the Lindley recursion. This is the standard benchmark for how a single server handles a stream of customers. When they applied their new equations to this simple case, the results perfectly matched the known solutions, proving that their method was sound. More importantly, they were able to derive a new, explicit solution for the steady state of this system using a specific type of random input, showing that their approach could generate precise answers where previous methods might have been too cumbersome.

Encouraged by this success, the team applied their theory to much more complex scenarios. They examined a system with a "dead band," a range of values where no action is taken, causing the workload to drift freely until it hits a boundary. In this model, the system can have positive work (a backlog) or negative work (excess capacity), and the researchers showed how the probability mass flows between these two sides and the central idle state. They then looked at systems where the rules change based on an external environment, such as a server that speeds up or slows down depending on the time of day or network traffic. Finally, they tackled a system with hysteresis, a type of memory where the system does not switch its behavior immediately when a threshold is crossed, but waits until the workload moves significantly further in the opposite direction. This mimics real-world thermostats or congestion controls that avoid rapid, jittery switching.

In every case, the unified framework successfully tracked the evolution of the workload. The researchers used computer simulations to verify their theoretical predictions, running millions of virtual scenarios to see if the math held up. The results were consistent: the equations accurately predicted how the system would settle into a steady state, capturing the exact proportion of time the system spent idle versus busy, and the precise shape of the workload distribution. The study demonstrated that despite the vast differences in how these systems operate—whether they are controlled by external switches, internal thresholds, or memory-based rules—they all follow the same underlying principles of probability transfer.

This work does not claim to solve every possible queuing problem, as it focuses on systems where the workload can be described by a mix of smooth curves and distinct points, excluding more exotic mathematical behaviors. However, it establishes a powerful new lens for viewing a wide class of waiting-line problems. By providing a common language to describe how the "empty" and "busy" states of a system interact, the researchers have offered a tool that can be applied to everything from inventory management to data center design. The finding is not just a new formula, but a new way of seeing: a realization that the complex, mixed behavior of waiting lines can be understood through a single, coherent set of rules that govern the dance between activity and stillness.

Technical Summary: A Unified Evolution Theory for Workload Distributions with Mixed Atomic and Continuous Components in Markov Processes

Problem Statement
Many queueing, storage, and inventory systems generate workload distributions that are not purely continuous but contain both atomic (discrete point masses, often at zero representing idling or dead-band states) and absolutely continuous components. While classical models like the Lindley recursion for GI/GI/1 queues are well-understood, more complex systems involving state-dependent control, dead bands, regime switching, and hysteresis often result in mixed probability laws.

Existing literature typically analyzes these mixed distributions on a case-by-case basis, exploiting specific structural properties of individual models. This approach creates a gap in the literature: there is no general framework to jointly evolve the atomic and continuous components of workload distributions across different control mechanisms. Consequently, it is difficult to compare different workload recursions within a common mathematical structure or to derive unified evolution principles for systems involving reflections, signed states, or augmented service modes.

Methodology
The authors develop a unified measure-theoretic framework for discrete-time stochastic recursions of the form $W_{n+1} = \Phi(W_n, X_{n+1})$ , where $\{X_n\}$ is an independent and identically distributed (IID) driving sequence. The core methodology proceeds in five steps:

Markov Kernel Representation: The recursion is represented as a Markov transition kernel $\kappa$ acting on probability measures.
Lebesgue Decomposition: Both the probability law of the workload ( $\Pi_n$ ) and the transition kernel ( $\kappa$ ) are decomposed into atomic and absolutely continuous components using the Lebesgue Decomposition Theorem and the Radon-Nikodym theorem. A reference measure $\rho$ is constructed to dominate both components (combining Dirac masses at atomic locations and Lebesgue measure elsewhere).
Derivation of Coupled Equations: By substituting these decompositions into the one-step law update equation ( $\Pi_{n+1} = \Pi_n \kappa$ ), the authors derive a system of coupled evolution equations. These equations explicitly characterize how probability mass transfers between the atomic set and the continuous region, and between different continuous regions, in a single time step.
Stationary Analysis: The framework reduces to a system of coupled integral equations (Fredholm equations of the second kind) for the stationary distribution.
Numerical Solution: The stationary equations are solved numerically using Nyström discretization with the composite trapezoidal rule, and analytically via Neumann series expansions for specific increment laws.

Key Contributions and Results
The paper validates this framework by applying it to four models of increasing complexity:

Classical Lindley Recursion (Benchmark): The framework successfully recovers the standard GI/GI/1 workload equations. For a shifted-Laplace increment law, the authors derive an explicit stationary solution for both the atom ( $p_0$ ) and the density ( $g$ ) using a Neumann series, demonstrating convergence with Nyström numerical solutions.
Two-Sided Dead-Band Recursion: Applied to inventory/make-to-stock systems where the state space is $\mathbb{R}$ (allowing negative values for surplus). The model features an atom at zero (the dead band) and two coupled continuous densities ( $g_-$ and $g_+$ ) representing negative and positive workloads. The results show that these branches cannot be solved independently due to mass transfer through the dead band.
Regime-Dependent (Markov-Modulated) Queue: The state space is augmented to include an external Markov regime. The framework derives coupled evolution equations for the joint distribution of workload and regime, capturing both fast relaxation within regimes and slow mixing between regimes.
Hysteresis-Controlled Service Queue: A model where the service mode (Low/High) switches deterministically based on workload thresholds ( $\ell, u$ ) and the previous mode. The framework explicitly handles the memory mechanism of hysteresis, deriving equations for mode-specific atoms and densities. Numerical validation against Monte Carlo simulations confirms the accuracy of the evolution equations in capturing the stationary density, tail probabilities, and mode-specific behaviors.

Significance and Claims
The paper claims to provide the first unified atom-density evolution approach for queueing workload processes. Its primary significance lies in:

Unification: Demonstrating that qualitatively different workload dynamics (reflections, dead bands, regime switching, hysteresis) can be analyzed within a single, common mathematical framework.
Explicit Mass Transfer: Providing equations that explicitly track the transfer of probability mass between atomic and continuous components, which is often obscured in model-specific analyses.
Generality: Establishing a principle for atom-density evolution that is independent of the specific control mechanism, provided the system can be modeled as a Markov recursion with a decomposable law.

The authors note that the current work is restricted to laws decomposable into countable atomic and absolutely continuous parts (excluding singular continuous components) and assumes an IID driving sequence. Future work is suggested to extend the framework to general stochastic inputs, higher-dimensional state spaces, and broader classes of state-dependent recursions.

Technical Summary: A Unified Evolution Theory for Workload Distributions with Mixed Atomic and Continuous Components in Markov Processes

More like this