Formal Approximations of the Transient Distributions of the M/G/1 Workload Process
Fabian Michel ✉, Markus Siegle · 2025
Read Formal Approximations of the Transient Distributions of the M/G/1 Workload Process by Fabian Michel ✉, Markus Siegle (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01193.txt.
Introduction
Fabian Michel and Markus Siegle compute how a queue's workload evolves over time, with a guaranteed error bound. Their target processes, like the M/G/1 workload, live on a continuous state space, making transient distributions hard to get. The method approximates the process with a finite-state Markov chain, producing a distribution whose density is constant on small intervals. The error is measured in the Wasserstein distance and bounded by a formula that is easy to compute.
In practice the computation is fast: seconds to a few minutes for usable accuracy. That speed plus an error certificate distinguishes the approach from simulation, which gives estimates without guarantees. Queueing analysts sizing buffers or service capacity need this: how full the system might be at a given moment, not just on average. The formalism extends to one-sided jump processes. The result is a tool rigorous and quick enough for routine use.
Catalog record
| CREATOR | Fabian Michel ✉, Markus Siegle |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01193
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Formal Approximations of the Transient Distributions of the M/G/1 Workload Process Fabian Michel ✉, Markus Siegle Abstract This paper calculates transient distributions of a special class of Markov processes with continuous state space and in continuous time, up to an explicit error bound. We approximate specific queues on ℝ \mathbb{R} with one-sided Lévy input, such as the M/G/1 workload process, with a finite-state Markov chain. The transient distribution of the original process is approximated by a distribution with a density which is piecewise constant on the state space. Easy-to-calculate error bounds for the difference between the approximated and actual transient distributions are provided in the Wasserstein distance. Our method is fast: to achieve a practically useful error bound, it usually requires only a few seconds or at most minutes of computation time. 1 Introduction Most of the theory in formal methods for stochastic systems is restricted to systems where either the state space or the time is discrete. In contrast, we consider systems where both the state space as well as the time are continuous. In particular, we would like to calculate transient distributions of a Markov process in continuous time and with continuous state space. As exact computations are typically infeasible, we approximate the transient distributions using a discretization approach, and we provide formal error bounds for the difference between the actual and approximated transient distribution. In this paper, we focus on queues with one-sided Lévy input, as the case of a general Markov process seems to be very difficult to analyze. The queues covered by our method include the M/G/1 workload process. As a motivating example, consider a server setup where the capacity was chosen such that all jobs can be dealt with reasonably quickly under the average expected load. Now, assume that a higher than usual job arrival rate is expected during a short time period (e.g. due to new events becoming available in a booking system, which many users try to book at once). Then, we can look at the transient workload distribution of the server with the higher job arrival rate to assess how congested the server will become in the short heavy load period. Using our error bounds, we can provide guarantees that the server’s workload at a given time will e.g. not exceed a given amount with high probability. In practice, if the probability of a catastrophic congestion in the heavy load period is too high, the system administrator could decide to temporarily increase the system’s capacity. While many results on particular properties of the transient distributions are available for these types of processes (e.g. moments, probability of being idle, see also Section 1.1 ), calculating the transient distributions itself up to some controllable formal error has received little attention. Our method can be used to do exactly that and with the transient distribution available, a variety of questions about the underlying process can be answered. The error bounds are explicit and easy to calculate, and the computational cost to meet a predetermined accuracy is reasonably small. Other approaches, such as the numerical inversion of Laplace transforms of the transient distributions, usually do not offer error bounds or only at an unreasonable amount of computational cost. Compared to the Laplace transform inversion algorithms which are most widely available in libraries, our method is both faster and more accurate in our numerical experiments (see Section 4 ). 1.1 Literature review Formal error bounds for approximations of Markov processes have been considered in various settings, but mostly for models where either space or time are discrete. An exception is [ 12 ] , but it only looks at pure jump processes. Next to [ 12 ] , one of the most similar papers to the present work is [ 11 ] , which considers a Markov process with general state space in discrete time. The transition kernel as well as the initial distribution are assumed to be expressible with a (Lipschitz-continuous) probability density, the process is approximated with a finite-state Markov chain and the densities of the transient distributions are approximated by piecewise constant densities. This is the same approach that we follow below. However, we look at continuous-time models and do not assume that the transient distributions of the original model admit a density. We therefore use a different metric to measure the error: the Wasserstein distance instead of the \left\lVert\cdot\right\rVert_{\infty} -norm applied to densities as in [ 11 ] . On the other hand, we restrict ourselves to the state space \mathbb{R} , unlike [ 11 ] . There are some works, such as [ 2 ] , on approximate model checking for stochastic hybrid systems, which usually have a continuous component in the state space. For more literature in that direction, also consult the reference lists from [ 11 , 2 ] . There is also a large body of work on models with discrete state space and continuous time, i.e. continuous time Markov chains. For example, [ 1 , 10 ] provide error bounds for an approximation of discrete- and continuous-time Markov chains via state space reduction. While there seems to be no literature on formal error bounds for approximating the transient distribution of general Markov processes, some models with continous time and continuous state space have received considerable attention, in particular in the analysis of queueing systems. In [ 4 ] , some transient characteristics of the M/G/1 workload process are considered, in particular its moments. [ 7 ] gives a good overview on the theory behind a more general class of queues with continuous state space and in continuous time: so-called Lévy-driven queues. They are defined using a Lévy process (a special type of Markov process with stationary and independent increments) whose state space is then restricted to the non-negative reals. This is the setting we focus on, and we will give more details in Section 2.1 . As it turns out, the transient distribution of such queues can often be characterized by explicit expressions for their Laplace transforms. Thus, another approach for calculating transient distributions is the numerical inversion of these transforms. One should note that the characterizations are often only given in terms of double or triple transforms, where next to the Laplace transform of the distribution, additional transforms in the time variable or in the initial state are considered. [ 6 ] follows this approach for the distribution of the running maximum of a Lévy process, and reports promising results using the inversion technique from [ 8 ] , albeit without formal error bounds. [ 3 , 5 ] propose to use different inversion techniques and compare the results to estimate the error, as the computational cost for meeting a pre-defined formal error bound is often excessive. We will show that a Markov chain approximation can remedy this problem for transient distributions of Lévy-driven queues. 1.2 Our contribution We present an easy-to-implement method which approximates specific queues with one-sided Lévy input by a finite-state Markov chain, and which provides explicit and easy-to-calculate error bounds for the transient distributions in the Wasserstein distance. In particular, the transient distribution of the original Lévy-driven queue at time points which are multiples of the discretization parameter \Delta will be approximated