Algorithmic Randomness in Continuous-Time Markov Chains

arXiv1910.13620MaRDI QIDQ6328141FDOQ6328141

Authors: Xiang Huang, Jack H. Lutz, Andrei N. Migunov

Publication date: 29 October 2019

Abstract: In this paper, we develop the elements of the theory of algorithmic randomness in continuous-time Markov chains (CTMCs). Our main contribution is a rigorous, useful notion of what it means for an

e x t i t i n d i v i d u a l t r a j e c t o r y

of a CTMC to be

e x t i t r a n d o m

. CTMCs have discrete state spaces and operate in continuous time. This, together with the fact that trajectories may or may not halt, presents challenges not encountered in more conventional developments of algorithmic randomness. Although we formulate algorithmic randomness in the general context of CTMCs, we are primarily interested in the

e x t i t c o m p u t a t i o n a l

power of stochastic chemical reaction networks, which are special cases of CTMCs. This leads us to embrace situations in which the long-term behavior of a network depends essentially on its initial state and hence to eschew assumptions that are frequently made in Markov chain theory to avoid such dependencies. After defining the randomness of trajectories in terms of a new kind of martingale (algorithmic betting strategy), we prove equivalent characterizations in terms of constructive measure theory and Kolmogorov complexity. As a preliminary application, we prove that, in any stochastic chemical reaction network,

e x t i t e v e r y

random trajectory with bounded molecular counts has the

e x t i t n o n - Z e n o p r o p e r t y

that infinitely many reactions do not occur in any finite interval of time.

This page was built for publication: Algorithmic Randomness in Continuous-Time Markov Chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328141)