A partition method for bounding continuous-time Markov chain models of general reaction network
Guillaume Ballif, Laurent Pfeiffer, Jakob Ruess · 2025
Read A partition method for bounding continuous-time Markov chain models of general reaction network by Guillaume Ballif, Laurent Pfeiffer, Jakob Ruess (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-2505-18735.txt.
Introduction
Guillaume Ballif, Laurent Pfeiffer, and Jakob Ruess gave in 2025 a general recipe for proving facts about stochastic chemical reaction networks without simulating every molecule. Such networks are modeled as Markov chains with huge state spaces. Their method groups states into blocks, then builds two simple one-dimensional processes that provably bracket the real one from below and above.
The brackets are easy to analyze and compute with. They answer whether a steady state exists and how much error comes from chopping the state space down to a solvable size. Formulas produce the tightest such brackets for any chosen grouping. The authors stress that choosing the grouping well decides how sharp the conclusions are, and they demonstrate on an example network.
Catalog record
| CREATOR | Guillaume Ballif, Laurent Pfeiffer, Jakob Ruess |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18735
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A partition method for bounding continuous-time Markov chain models of general reaction network Guillaume Ballif, Laurent Pfeiffer, Jakob Ruess Abstract Abstract: In this work, we present a general method to establish properties of multi-dimensional continuous-time Markov chains representing stochastic reaction networks. This method consists of grouping states together (via a partition of the state space), then constructing two one-dimensional birth and death processes that lower and upper bound the initial process under simple assumptions on the infinitesimal generators of the processes. The construction of these bounding processes is based on coupling arguments and transport theory. The bounding processes are easy to analyse analytically and numerically and allow us to derive properties on the initial continuous-time Markov chain. We focus on two important properties: the behavior of the process at infinity through the existence of a stationary distribution and the error in truncating the state space to numerically solve the master equation describing the time evolution of the probability distribution of the process. We derive explicit formulas for constructing the optimal bounding processes for a given partition, making the method easy to use in practice. We finally discuss the importance of the choice of the partition to obtain relevant results and illustrate the method on an example chemical reaction network. Mathematics Subject Classification: 60J27 Continuous-time Markov processes on discrete state spaces, 60G10 Stationary stochastic processes, 92C40 Biochemistry, molecular biology 1 Introduction Stochastic reaction networks have been widely used in many fields such as chemistry [ 3 ] , biology [ 14 , 2 ] and ecology, medicine [ 9 ] , epidemiology [ 4 ] , economics [ 7 ] to model complex and often multi-dimensional random phenomena. Mathematically, it is straightforward to represent such models as continuous-time Markov chains (CTMCs) but the multi-dimensional nature of the real process greatly complicates the study of properties of the corresponding CTMC (such as explosion in finite time and the behaviour when time tends to infinity) and the numerical simulation of trajectories. For example, the existence of a stationary distribution is a crucial property in the study of the long-term behaviour but whether or not a given CTMC admits a stationary distribution is often hard to say a priori . This question has been studied extensively and several methods have been developed to address it: coupling techniques [ 21 ] , conditions on the semi-group or the study of the generator spectrum [ 5 , 12 ] , extension of the Perron-Frobenius theorem [ 26 ] or existence of a Lyapunov function [ 23 , 10 ] . However, the size of the state space and the assumptions to be verified make these methods difficult to apply systematically to multidimensional CTMCs. From a numerical point of view, the time evolution of the probability distribution of a CTMC is described by a master equation (also called Kolmogorov equation) composed of an infinite system of ordinary differential equations. The size of the state space often makes solving the master equation numerically impossible due to the exponential increase in computation time with the state space dimension. Two classes of methods have been developed in the literature to circumvent this problem: Monte Carlo methods and approximation methods. Monte Carlo methods [ 17 ] are based on the simulation of a large number of trajectories of the process with the stochastic simulation algorithm (SSA) [ 17 ] also known as the Gillespie algorithm in order to reconstruct the probability distribution of the CTMC. Various improvements have been developed over the past few years to improve the precision and computation speed of the method [ 18 , 1 ] . However, a large number of trajectories of the process is required to obtain good approximations of the probability distribution, which is very costly in terms of computing time. The second type of methods aims to solve an approximation of the master equation [ 6 , 20 , 13 ] . One of the most commonly used methods is the truncation of the state space to replace numerical solving of the master equation by that of a linear system of ordinary differential equations [ 24 , 28 ] but in the case of a multi-dimensional CTMC, even after truncation the state space is often still much too large for numerical solution of this linear system to be efficient or even just feasible. Moreover, most of these methods do not provide an estimate of the error caused by this approximation that can be calculated in practice. In this work, we present a general method for constructing one-dimensional bounding processes (in a certain sense) for any CTMC under some simple assumptions on the infinitesimal generator. We can then analyse the one-dimensional bounding processes to derive properties of the multi-dimensional original CTMC that would be hard to obtain directly. Concretely, we focus on two essential aspects when studying CTMC models: the behavior of the process at infinity through the existence of a stationary distribution and the quantification of the approximation error when the infinite state space is truncated. The method for constructing the bounding processes is based on an ordered partition of the state space (that we will refer to as classes) that allows us to reduce the dimension of the CTMC by studying its behavior only on classes. Coupling arguments and transport theory are used to derive these bounding results (upper and lower bounds). Different methods have been developed in order to reduce the state space of a CTMC to be able to derive properties on this CTMC: aggregation of states (also called lumping) for Markov chain on finite state space [ 8 ] or for some particular cases of Markov chain on an infinite state space [ 25 , 16 , 22 ] , decomposition of the reaction network into subnetworks [ 19 ] or comparisons between processes through coupling [ 15 ] . To make our framework useful in practice, we derive explicit formulas for constructing the infinitesimal generator of the optimal bounding processes from assumptions on the generator of the original process. These explicit formulas are used to illustrate on an example the results that we can derive on the multi-dimensional original CTMC. The choice of optimal classes to partition the state space (i.e. leading to the best possible bounds) is also discussed by comparing the upper-bounding process and properties derived from a naive choice and those derived from a set of classes taking into account the structure of the reaction network. The manuscript is organized as follows. Section 2 focuses on the construction of an upper-bounding process. The construction is done in two main steps. In Theorem 2.1 , we construct an upper-bounding process based on an infinitesimal generator satisfying some monotonicity properties. We provide in Proposition 2.4 an explicit formula for such an infinitesimal generator that most closely upper-bounds the initial process. The adaptation of these results for a lower-bounding process is presented in Section 3 . In Section 4 , the method is used to derive results on the existence of a stationary distribution and on the error made in numerically solving the master equation on truncated state spaces and all these results are illustrated on an example. Notation We fix a countable state space \mathcal{S} and