1 Introduction↩︎

Stochastic chemical reaction networks are used in molecular programming, DNA nanotechnology, and synthetic biology to model and specify the behaviors of natural and engineered molecular systems. Stochastic chemical reaction networks are known to be Turing universal jSoCoWiBr08?, hence capable of extremely complex dynamical behavior.

Briefly and roughly (deferring details until later in the paper), a stochastic chemical reaction network \(N\) is a mathematical model of a chemical process in a volume \(V\) of solution. A state of \(N\) consists of the nonnegative integer populations of each of its finitely many species (types of molecules) at a given time. The state space is thus countable and discrete. The network stays in a state for a positive, real-valued sojourn time after which one of the finitely many reactions that \(N\) allows to occur among its species produces an instantaneous jump transition to a different state. Both the sojourn time and the choice of the reaction are probabilistic, with the network behaving as a certain kind of continuous-time Markov chain given by the parameters of \(N\). Hence, given an initial state at time \(t=0\), there are in general uncountably many trajectories (sequences of states and sojourn times) that \(N\) can traverse. Some of these trajectories are finite (because \(N\) reaches a state in which none of its reactions can occur), and some are infinite.

In this paper we develop the elements of the theory of algorithmic randomness in continuous-time Markov chains (CTMCs). Specifically, our main contribution is a rigorous, useful notion of what it means for an individual trajectory (also called a single orbit in dynamical systems theory) of a CTMC \(C\) to be random with respect to \(C\) and an initial state—or probability distribution of initial states—of \(C\). This is a first step toward carrying out Kolmogorov’s program of replacing probabilistic laws stating that almost every trajectory has a given property with stronger randomness laws stating that every random trajectory has the property. More generally, we are initiating an algorithmic “single orbit” approach (in the sense of Weiss Weis00?) to the dynamics of CTMCs. In a variety of contexts ranging from Bernoulli processes to ergodic theory, Brownian motion, and algorithmic learning, this algorithmic single-orbit approach has led to improved understanding of known results oLiVit19?, downey2010algorithmic?, nies2009computability?, shen2017kolmogorov?, v1998ergodic?, nandakumar2008effective?, fouche2009fractals?, jKjoNer09?, allen2015zeros?, fouche2015kolmogorov?, vovk2022algorithmic?, shafer2008tutorial?, ghosh2012predictive?, vovk1999machine?. In the context of fractal geometry, this approach has even led to recent solutions of classical open problems whose statements did not involve algorithms or single orbits CCLLMS26?, BusFie25?, FieStu23?, FieStu24a?, FieStuUniversal?, Fiedler2026-packing?, jLutStu20?, jLutz21?, LutStu24?, Sla21?, StullPinned?, AlBuWi2025?, StullOptimal?.

The fact that CTMCs have discrete state spaces and operate in continuous time, together with the fact that trajectories may or may not halt, presents challenges not encountered in more conventional developments of algorithmic randomness. Our formulation of randomness is nevertheless general. Because we are interested in the computational power of stochastic chemical reaction networks, we embrace situations in which the long-term behavior of a network depends essentially on its initial state. Our development thus does not make assumptions that are frequently used in Markov chain theory to avoid such dependencies.

Our approach is also general in another sense, one involving Kolmogorov’s program. Once one has succeeded in replacing an “almost every” probabilistic law with an “every random” law, a natural next question is, “How much randomness is sufficient for the latter?” Saying that an individual object is random is saying that it “appears random” to a class of computations. Roughly speaking, an object is algorithmically random (or Martin-Löf random) if it appears random to all computably enumerable sets. But weaker notions of randomness such as computable randomness, polynomial-space randomness, polynomial-time randomness, and finite-state randomness, have also been extensively investigated. Three examples of answers to the “how much randomness suffices” question in the context of infinite binary sequences are that (i) every algorithmically random sequence satisfies Birkhoff’s ergodic theorem v1998ergodic?; (ii) every polynomial-time random sequence satisfies the Khinchin-Kolmogorov law of the iterated logarithm wang1996randomness?; and (iii) every finite-state random sequence satisfies the strong law of large numbers SchSti72?.

Although we are primarily concerned with algorithmic randomness in the present paper, we want our randomness notion to be general enough to extend easily to other computational “levels” of randomness, so that “how much randomness” questions can be formulated and hopefully answered. For this reason, we define algorithmic randomness in CTMCs using the martingale (betting strategy) approach of Schnorr DBLP:journals/mst/Schnorr71?. This approach extends to other levels of randomness in a straightforward manner, while our present state (i.e., lack) of knowledge in computational complexity theory does not allow us to extend other approaches (e.g., Martin-Löf tests or Kolmogorov complexity, which are known to be equivalent to the martingale approach at the algorithmic level oLiVit19?, downey2010algorithmic?, nies2009computability?, shen2017kolmogorov?) to time-bounded complexity classes.

We develop our algorithmic randomness theory in stages. In section 2 we develop the underlying qualitative structure of Boolean transition systems, defined so that (i) state transitions are nontrivial, i.e., not from a state to itself, and (ii) trajectories may or may not terminate. We then show how to use these transition systems to model rate-free chemical reaction networks.

In section 3 we add probabilities, thereby defining probabilistic transition systems. For each probabilistic transition system \(\mathscr{Q}\) and each initialization \(\sigma\) of \(\mathscr{Q}\) we then define \((\mathscr{Q}, \sigma)\)-martingales, which are strategies for betting on the successive entries in a sequence of states of \((\mathscr{Q}, \sigma)\). Following the approach of Schnorr DBLP:journals/mst/Schnorr71?, we then define a maximal state sequence \(\boldsymbol{q}\) of \((\mathscr{Q}, \sigma)\) to be random if there is no lower semicomputable \((\mathscr{Q}, \sigma)\)-martingale that succeeds on \(\boldsymbol{q}\), i.e., makes unbounded money betting along \(\boldsymbol{q}\). This notion of randomness closely resembles the well-understood theory of random sequences over a finite alphabet oLiVit19?, downey2010algorithmic?, nies2009computability?, shen2017kolmogorov?, except that here the state set may be countably infinite; transitions from a state to itself are forbidden; and a positive-probability state sequence may terminate, in which case it is random.

Section 4 is where we confront the main challenge of algorithmic randomness in CTMCs, the fact that they operate in continuous, rather than discrete, time. There we develop the algorithmic randomness of sequences \(\boldsymbol{t} = (t_0, t_1, \ldots)\) of sojourn times \(t_i\) relative to corresponding sequences \({{\boldsymbol{\lambda}}} = (\lambda_0, \lambda_1, \ldots)\) of nonnegative real-valued rates \(\lambda_i\). Each \(\lambda_i\) in such a sequence is regarded as defining an exponential probability distribution function \(F_{\lambda_i}\), and the sojourn times \(t_i\) are to be independently random relative to these. We use a careful binary encoding of sojourn times to define \({{\boldsymbol{\lambda}}}\)-martingales that bet along sequences of sojourn times, and we again follow the Schnorr approach, defining a sequence \(\boldsymbol{t}\) of sojourn times to be \({{\boldsymbol{\lambda}}}\)-random if there is no lower semicomputable \({{\boldsymbol{\lambda}}}\)-martingale that succeeds on it.

In section 5 we put the developments of sections 3 and 4 together. A trajectory of a continuous-time Markov chain \(C\) is a sequence \(\boldsymbol{\tau}\) of ordered pairs \((q_n,t_n)\), where \(q_n\) is a state of \(C\) and \(t_n\) is the sojourn time that \(C\) spends in state \(q_n\) before jumping to state \(q_{n+1}\). For each continuous-time Markov chain \(C\), we define the notion of a \(C\)-martingale. In section 6, following Schnorr once again, we define a trajectory \(\boldsymbol{\tau}\) of \(C\) to be random if no lower semicomputable martingale succeeds on it. We prove analogs of Schnorr’s theorem and van Lambalgen’s theorem for CTMC trajectories. In section 7, we give a Kolmogorov complexity characterization of the randomness of trajectories of continuous-time Markov chains. As an example application, we prove in section 8 that, in any stochastic chemical reaction network, every random trajectory \(\boldsymbol{\tau}\) with bounded molecular counts has the non-Zeno property that infinitely many reactions do not occur in any finite interval of time. That is, random trajectories with bounded molecular counts do not exhibit “finite-time blowup.”

2 Boolean transition systems↩︎

Before developing algorithmic randomness for sequences of states with respect to computable, probabilistic transition systems, we develop the underlying qualitative (not probabilistic) structure by considering transition systems that are Boolean. Some care must be taken to accommodate the fact that, in cases of interest, a sequence of states may either be infinite or end in a terminal state.

Formally, we define a Boolean transition system to be an ordered pair \(\mathscr{Q} = (Q, \delta)\) where \(Q\) is a nonempty, countable set of states, and \(\delta:Q \times Q \rightarrow \{0,1\}\) is a Boolean state transition matrix satisfying \(\delta(q,q) = 0\) for all \(q \in Q\).

Intuitively, a Boolean transition system \(\mathscr{Q} = (Q, \delta)\) is a nondeterministic structure that may be initialized to any nonempty set of states in \(Q\). For \(q,r \in Q\), the entry \(\delta(q,r)\) in the Boolean transition matrix \(\delta\) is the Boolean value \((0 =\) false; \(1 =\) true\()\) of the condition that \(r\) is reachable from \(q\) in one “step” of \(\mathscr{Q}\). The irreflexivity requirement that every \(\delta(q,q) = 0\) (i.e., that \(\delta\) have a zero diagonal) reflects the fact that, in all cases of interest in this paper, transitions are nontrivial changes of state. We formalize this intuition, because the formalism will be useful here.

We write \(Q^*\) for the set of all finite sequences of states in \(Q\), \(Q^{\omega}\) for the set of all infinite sequences of states in \(Q\), and \(Q^{\leq \omega} = Q^* \cup Q^{\omega}\). The length of a sequence \(\boldsymbol{q} \in Q^{\leq \omega}\) is

\[|\boldsymbol{q}| = \begin{cases} \ell &\text{ if } \boldsymbol{q} = (q_0, q_1, \ldots, q_{\ell-1}) \in Q^*\\ \omega &\text{ if } \boldsymbol{q} \in Q^\omega. \end{cases}\]

A sequence \(\boldsymbol{q} \in Q^{\leq \omega}\) can thus be written as \(\boldsymbol{q} = (q_i \mid i < |\boldsymbol{q}|)\) in any case. We write \(()\) for the empty sequence, the sequence of length 0.

For \(\boldsymbol{q}, \boldsymbol{r} = (r_i \mid i < |\boldsymbol{r}|) \in Q^{\leq \omega}\), we say that \(\boldsymbol{q}\) is a prefix of \(\boldsymbol{r}\), and we write \(\boldsymbol{q} \sqsubseteq \boldsymbol{r}\), if \(|\boldsymbol{q}| \leq |\boldsymbol{r}|\) and \(\boldsymbol{q} = (r_i \mid i < |\boldsymbol{q}|)\). It is easy to see that \(\sqsubseteq\) is a partial ordering of \(Q^{\leq \omega}\).

An initialization of a Boolean transition system \(\mathscr{Q} = (Q, \delta)\) is a Boolean-valued function \(\sigma: Q \rightarrow \{0,1\}\) whose support \(supp(\sigma) = \{q\in Q\mid \sigma(q) \neq 0\}\) is nonempty.

A Boolean transition system \(\mathscr{Q} = (Q, \delta)\) admits a sequence \(\boldsymbol{q} = (q_i \mid i < |\boldsymbol{q}|) \in Q^{\leq \omega}\) with an initialization \(\sigma\), and we say that \(\boldsymbol{q}\) is \(\mathscr{Q}\)-admissible from \(\sigma\), if the following conditions hold for all \(0 \leq i < |\boldsymbol{q}|\).

1. If \(i = 0\), then \(\sigma(q_i) = 1\).

2. If \(i+1 < |\boldsymbol{q}|\), then \(\delta(q_i,q_{i+1}) = 1\).

A sequence \(\boldsymbol{q} \in Q^{\leq \omega}\) that is \(\mathscr{Q}\)-admissible from \(\sigma\) is maximal if, for every sequence \(\boldsymbol{r} \in Q^{\leq \omega}\) that is \(\mathscr{Q}\)-admissible from \(\sigma\), \(\boldsymbol{q} \sqsubseteq \boldsymbol{r} \implies \boldsymbol{q} = \boldsymbol{r}\).

We use the following notations. \[\begin{align} Adm_{\mathscr{Q}}(\sigma) &= \{\boldsymbol{x} \in Q^* \mid \boldsymbol{x}\text{ is }\mathscr{Q}\text{-admissible from }\sigma\}.\\ \mathbb{A}_{\mathscr{Q}}(\sigma) &= \{\boldsymbol{q} \in Q^{\leq\omega} \mid \boldsymbol{q}\text{ is a maximal }\mathscr{Q}\text{-admissible sequence from }\sigma\}. \end{align}\]

When \(\mathscr{Q}\) is obvious from the context, we omit it from the notation and write these sets as \(Adm(\sigma)\) and \(\mathbb{A}(\sigma)\). Note that elements of \(Adm_\mathscr{Q}(\sigma)\) are required to be finite sequences.

Intuitively, \(\mathbb{A}_{\mathscr{Q}}(\sigma)\) is the set of all possible “behaviors” of the Boolean transition system \(\mathscr{Q} = (Q,\delta)\) with the state initialization \(\sigma:Q \rightarrow \{0,1\}\). The fact that \(\delta\) is irreflexive implies that \(q_i \neq q_{i+1}\) holds for all \(i \in \mathbb{N}\) such that \(i+1 < |\boldsymbol{q}|\) in every admissible sequence \(\boldsymbol{q} = (q_i \mid i < |\boldsymbol{q}|) \in \mathbb{A}_{\mathscr{Q}}(\sigma)\). In this paper we do not regard the indices \(i = 0, 1, \ldots\) in a state sequence \(\boldsymbol{q} = (q_0, q_1, \ldots)\) as successive instants in discrete time. In our main applications, the amount of time spent in state \(q_i\) varies randomly and continuously, so it is more useful to think of the indices \(i = 0, 1, \ldots\) as finite ordinal numbers, i.e., to think of \(q_i\) as merely the \(i^{\textit{th}}\) state in the sequence \(\boldsymbol{q}\).

Each \(\boldsymbol{x} \in Adm_\mathscr{Q}(\sigma)\) is the name of the \(\mathscr{Q}\)-cylinder \[\label{eq:Qcylinder} \mathbb{A}_{\boldsymbol{x}}(\sigma) = \{\boldsymbol{q} \in \mathbb{A}_{\mathscr{Q}}(\sigma) \mid \boldsymbol{x} \sqsubseteq \boldsymbol{q}\}.\tag{1}\] Each \(\boldsymbol{x} \in Adm(\sigma)\) is a finite—and typically partial—specification of each sequence \(\boldsymbol{q} \in \mathbb{A}_{\boldsymbol{x}}(\sigma)\). The collection \[\mathscr{A}(\sigma) = \mathscr{A}_{\mathscr{Q}}(\sigma) = \{ \mathbb{A}_{\boldsymbol{x}}(\sigma) \mid \boldsymbol{x} \in Adm_\mathscr{Q}(\sigma)\}\] is a basis for a topology on \(\mathbb{A}(\sigma)\). The open sets in this topology are simply the sets that are unions of (finitely or infinitely many) cylinders in \(\mathscr{A}(\sigma)\). The metric (in fact, ultrametric) \(d\) on \(Q^{\leq\omega}\) defined by \[d(\boldsymbol{q},\boldsymbol{r}) = 2^{-|\boldsymbol{p}|},\] where \(\boldsymbol{p}\) is the longest common prefix of \(\boldsymbol{q}\) and \(\boldsymbol{r}\) (and \(2^{-\infty} = 0\)), induces this same topology on \(\mathbb{A}_{\mathscr{Q}}(\sigma)\) for each Boolean transition system \(\mathscr{Q} = (Q, \delta)\) and each state initialization \(\sigma: Q \rightarrow \{0,1\}\). With this topology, \(\mathbb{A}_{\mathscr{Q}}(\sigma)\) is a Polish space (a complete, separable metric space). This Polish space is not necessarily perfect, because it may have isolated points. Among these, when they exist, are finite sequences, i.e., sequences \(x \in Q^* \cap \mathbb{A}_{\mathscr{Q}}(\sigma)\). Such sequences \(\boldsymbol{x}\) are said to halt, or terminate, in \(\mathscr{Q}\) from \(\sigma\).

A Boolean transition system \(\mathscr{Q} = (Q, \delta)\) is computable if the elements of \(Q\) are naturally represented in such a way that \((i)\) the Boolean-valued function \(\delta\) is computable, and \((ii)\) the set of terminal states (i.e., states \(q \in Q\) such that \(\delta(q, r) = 0\) for all \(r \in Q\)) is decidable. An initialization \(\sigma:Q \rightarrow \{0,1\}\) is computable if its support is decidable.

An important class of examples of Boolean transition systems consists of those that model rate-free chemical reaction networks. Formally, let \(\boldsymbol{S} = \{X_0, X_1, X_2, \ldots\}\) be a countable set of distinct species \(X_n\), each of which we regard as an abstract type of molecule. A rate-free chemical reaction network (or rate-free CRN) is an ordered pair \(N=(S,R)\), where \(S \subseteq \boldsymbol{S}\) is a finite set of species, and \(R\) is a finite set of (rate-free) reactions on \(S\), each of which is formally an ordered pair \(\rho = (r, p)\) of distinct vectors \(r, p \in \mathbb{N}^S\) (equivalently, functions \(r,p:S \rightarrow \mathbb{N}\)). Informally, we write species in notations convenient for specific problems (\(X, Y, Z, \widehat{X}, \overline{Y}\), etc.) rather than as subscripted elements of \(\boldsymbol{S}\), and we write reactions in a notation more suggestive of chemical reactions. For example, \[\label{raction:example} X + Z \rightarrow 2Y + Z\tag{2}\] is a rate-free reaction on the set \(S = \{X, Y, Z\}\). If we consider the elements of \(S\) to be ordered as written, then the left-hand side of (2 ) is formally the reactant vector \(r = (1, 0, 1)\), and the right-hand side of (2 ) is the product vector \(p = (0, 2, 1)\). A species \(Y \in S\) is called a reactant of a reaction \(\rho = (r, p)\) if \(r(Y) > 0\) and a product of \(\rho\) if \(p(Y) > 0\).

Intuitively, the reaction \(\rho\) in (2 ) means that, if a molecule of species \(X\) encounters a molecule of species \(Z\), then the reaction \(\rho\) may occur, in which case the reactants \(X\) and \(Z\) disappear and the products—two molecules of species \(Y\) and a molecule of species \(Z\)—appear in their place. Accordingly, the net effect of a reaction \(\rho = (r,p)\) is the vector \(\Delta\rho \in \mathbb{Z}^S\) defined by \[\Delta\rho(Y) = p(Y) - r(Y)\] for all \(Y \in S\). Since we have required \(r\) and \(p\) to be distinct, \(\Delta\rho\) is never the zero vector in \(\mathbb{Z}^S\).

In this paper, a state of a chemical reaction network \(N = (S,R)\) is a vector \(q \in \mathbb{N}^S\). Intuitively, \(N\) is modeling chemical processes in a solution, and the state \(q\) denotes a situation in which, for each \(Y \in S\), exactly \(q(Y)\) molecules of species \(Y\) are present in the solution.

A reaction \(\rho = (r,p) \in R\) of a chemical reaction network \(N = (S,R)\) can occur (or is enabled) in a state \(q \in \mathbb{N}^S\) if \[q(Y) \geq r(Y)\] holds for every \(Y \in S\), i.e. if the reactants of \(\rho\) are present in \(q\). If this reaction \(\rho\) does occur in state \(q\), then it transforms \(q\) to the new state \(q + \Delta\rho\).

The behavior of a rate-free chemical reaction network \(N = (S,R)\) clearly coincides with that of the Boolean transition system \(\mathscr{Q}_N = (\mathbb{N}^S, \delta)\), where \(\delta: \mathbb{N}^S \times \mathbb{N}^S \rightarrow \{0,1\}\) is defined by setting each \(\delta(q, q')\) to be the Boolean value of the condition that some reaction \(\rho \in R\) transforms the state \(q\) to the state \(q'\). Boolean transition systems of this form are clearly computable and have other special properties. As one example, for each \(q \in \mathbb{N}^S\), there are only finitely many \(q' \in \mathbb{N}^S\) for which \(\delta(q, q') = 1\).

Rate-free chemical reaction networks, and Boolean transition systems more generally, raise significant and deep problems in distributed computing leroux2015demystifying?, czerwinski2019reachability?, but our focus here is on randomness, which we introduce in the following section.

3 Random state sequences↩︎

This section develops the elements of algorithmic randomness for sequences of states with respect to computable, probabilistic transition rules. The probabilistic transition systems defined in this section, in which self-transitions have probability zero, correspond to the state sequences of continuous-time Markov chains.

Formally, we define a probabilistic transition system to be an ordered pair \(\mathscr{Q} = (Q,\pi)\), where \(Q\) is a countable set of states, and \(\pi:Q \times Q \rightarrow [0,1]\) is a probabilistic transition matrix, by which we mean that \(\pi\) satisfies the following two conditions for each state \(q \in Q\).

1. \(\pi(q,q) = 0\).

2. The sum \(\pi(q) = \sum_{r\in Q} \pi(q, r)\) is either 0 or 1.

If \(\pi(q)=0\), then \(q\) is a terminal state. If \(\pi(q)=1\), then \(q\) is a nonterminal state.

If \(\mathscr{Q} = (Q, \pi)\) is a probabilistic transition system, and we define \(\delta: Q \times Q \rightarrow \{0,1\}\) by \[\delta(q, r) = sgn(\pi(q,r))\] for all \(q, r \in Q\), where \(sgn:[0,\infty) \rightarrow \{0,1\}\) is the signum function \[sgn(x)= \begin{cases} 0 &\textit{if } x = 0\\ 1 &\textit{if } x > 0, \end{cases}\] then \(\mathscr{Q}_B = (Q, \delta)\) is the Boolean transition system corresponding to \(Q\). The essential difference between \(\mathscr{Q}_B\) and \(\mathscr{Q}\) is that, while \(\delta(q,r)\) merely says whether it is possible for \(\mathscr{Q}_B\) (or \(\mathscr{Q}\)) to transition from \(q\) to \(r\) in one step, \(\pi(q,r)\) is the quantitative probability of doing so.

An initialization of a probabilistic transition system \(\mathscr{Q}= (Q, \pi)\) is a discrete probability measure \(\sigma\) on \(Q\), i.e., a function \(\sigma: Q \rightarrow [0,1]\) satisfying \(\sum_{q \in Q} \sigma(q) = 1\). The Boolean version of such an initialization \(\sigma\) is the function \(\sigma_B:Q \rightarrow \{0,1\}\) defined by \[\sigma_B(q) = sgn(\sigma(q))\] for each \(q \in Q\). It is clear that \(\sigma_B\) is an initialization of \(\mathscr{Q}_B\).

Given a probabilistic transition system \(\mathscr{Q}= (Q, \pi)\) and an initialization \(\sigma\) of \(\mathscr{Q}\), we define the sets

\[\begin{align} Adm(\sigma) &= Adm_\mathscr{Q}(\sigma) = Adm_{\mathscr{Q}_B}(\sigma_B)\\ \mathbb{A}(\sigma) &= \mathbb{A}_{\mathscr{Q}}(\sigma) = \mathbb{A}_{\mathscr{Q}_B}(\sigma_B), \end{align}\] relying on the fact that the right-hand sets were defined in section 2. The notations and terminology in section 2 leading up to these definitions are similarly extended to probabilistic transition systems, as are the definitions of the \(\mathscr{Q}\)-cylinders \(\mathbb{A}_{\boldsymbol{x}}(\sigma)\) and the basis \(\mathscr{A}(\sigma)\) for the topology \(\mathbb{A}(\sigma)\).

What we can do here that we could not do for Boolean transition systems is define a Borel probability measure on each set \(\mathbb{A}_{\mathscr{Q}}(\sigma)\). Specifically, for each probabilistic transition system \(\mathscr{Q}= (Q, \pi)\) and each initialization \(\sigma\) of \(\mathscr{Q}\), define the function \[\mu_{\mathscr{Q}, \sigma}: Adm_\mathscr{Q}(\sigma) \rightarrow [0,1]\] as follows. Let \(\boldsymbol{x} = (x_i \mid i < |\boldsymbol{x}|) \in Adm_\mathscr{Q}(\sigma)\). If \(|\boldsymbol{x}| = 0\), then \(\mu_{\mathscr{Q},\sigma}(x) = 1\). If \(|\boldsymbol{x}| > 0\), then \[\mu_{\mathscr{Q},\sigma}(\boldsymbol{x}) = \sigma(x_0){\displaystyle \prod_{i=0}^{|\boldsymbol{x}|-2}\pi(x_i, x_{i+1})}.\]

Since \(\boldsymbol{x}\) is a name of the cylinder \(\mathbb{A}_{\mathscr{Q},\boldsymbol{x}}(\sigma)\), each \(\mu_{\mathscr{Q},\sigma}(\boldsymbol{x})\) here should be understood as an abbreviation of \(\mu_{\mathscr{Q},\sigma}(\mathbb{A}_{\boldsymbol{x}}(\sigma))\), which is intuitively the probability that an element of \(\mathbb{A}_{\mathscr{Q},\boldsymbol{x}}(\sigma)\) begins with the finite sequence \(\boldsymbol{x}\).

The above observation implies that \(\mu_{\mathscr{Q},\sigma}\) can, by standard techniques (e.g., Dynkin’s \(\pi\)-\(\lambda\) theorem billingsley1995probability?), be extended to a Borel probability measure on \(\mathbb{A}_{\mathscr{Q}}(\sigma)\), i.e., to a function \(\mu_{\mathscr{Q},\sigma}\) that assigns probability \(\mu_{\mathscr{Q},\sigma}(E)\) to every Borel set \(E \subseteq \mathbb{A}_{\mathscr{Q}}(\sigma)\).

An arbitrary set \(E\subseteq\mathbb{A}_{\mathscr{Q}}(\sigma)\) has probability 0, and we write \(\mu_{\mathscr{Q},\sigma}(E)=0\), if there is some Borel set \(F\supseteq E\) such that \(\mu_{\mathscr{Q},\sigma}(F)=0\). It has algorithmic probability 0, and we write \(\mu_{\mathscr{Q},\sigma,\mathop{\mathrm{alg}}}(E)=0\), if there is a computable function \(g:\mathbb{N}\times\mathbb{N}\to Adm_\mathscr{Q}(\sigma)\) such that, for all \(k\in\mathbb{N}\), \[E\subseteq\bigcup_{\ell\in\mathbb{N}}\mathbb{A}_{g(k,\ell)}(\sigma)\] and \[\sum_{\ell\in\mathbb{N}}\mu_{\mathscr{Q},\sigma}(g(k,\ell))\leq 2^{-k}.\]

If \(\mathscr{Q}\) is a probabilistic transition system and \(\sigma\) is an initialization of \(\mathscr{Q}\), then a \((\mathscr{Q}, \sigma)\)-martingale is a function \[d:Adm_\mathscr{Q}(\sigma) \rightarrow [0, \infty)\] such that, for every non-terminating sequence \(\boldsymbol{x} \in Adm_\mathscr{Q}(\sigma)\), \[\label{eq:state95martingale} d(\boldsymbol{x})\mu_{\mathscr{Q},\sigma}(\boldsymbol{x}) = \sum_{\substack{\boldsymbol{x} \sqsubseteq \boldsymbol{y} \in Adm_\mathscr{Q}(\sigma)\\|\boldsymbol{y}| = |\boldsymbol{x}| + 1}} d(\boldsymbol{y})\mu_{\mathscr{Q}, \sigma}(\boldsymbol{y}).\tag{3}\]

Intuitively, a \((\mathscr{Q}, \sigma)\)-martingale \(d\) is a gambler that bets on the successive states in a sequence \[\boldsymbol{q} = (q_i \mid i < |\boldsymbol{q}|) \in \mathbb{A}_{\mathscr{Q}}(\sigma).\] The gambler’s initial capital is \(d(())\), and its capital after betting on a prefix \(\boldsymbol{x} \in Adm_\mathscr{Q}(\sigma)\) of \(\boldsymbol{q}\) is \(d(\boldsymbol{x})\). The condition (3 ) says that the payoffs are fair with respect to the probability measure \(\mu = \mu_{\mathscr{Q},\sigma}\) in the sense that the conditional expectation of the gambler’s capital after betting on the state following \(\boldsymbol{x}\) in \(\boldsymbol{q}\), given that \(\boldsymbol{x} \sqsubseteq \boldsymbol{q}\), is exactly the gambler’s capital before placing this bet.

A \((\mathscr{Q}, \sigma)\)-martingale \(d\) succeeds on a sequence \(\boldsymbol{q} \in \mathbb{A}_{\mathscr{Q}}(\sigma)\) if the set \[\{d(\boldsymbol{x}) \mid \boldsymbol{x} \in Adm_\mathscr{Q}(\sigma) \text{ and } \boldsymbol{x} \sqsubseteq \boldsymbol{q}\}\] is unbounded. The success set of a \((\mathscr{Q}, \sigma)\)-martingale \(d\) is \[S^\infty[d] = \{ \boldsymbol{q} \in \mathbb{A}_{\mathscr{Q}}(\sigma) \mid d \text{ succeeds on } \boldsymbol{q} \}.\]

Following standard practice, we develop randomness by imposing computability conditions on martingales. Recall that, if \(D\) is a discrete domain, then a function \(f:D \rightarrow \mathbb{R}\) is computable if there is a computable function \(\hat{f}:D \times \mathbb{N} \rightarrow \mathbb{Q}\) such that, for all \(x \in D\) and \(r \in \mathbb{N}\), \[|\hat{f}(x,r) - f(x)| \leq 2^{-r}.\] The parameter \(r\) here is called a precision parameter.

A function \(f: D \rightarrow \mathbb{R}\) is lower semicomputable if there is a computable function \(\hat{f}:D \times \mathbb{N} \rightarrow \mathbb{Q}\) such that the following two conditions hold for all \(x \in D\).

1. For all \(s \in \mathbb{N}, \hat{f}(x,s) \leq \hat{f}(x, s+1) < f(x)\).

2. \(\displaystyle\lim_{s \rightarrow \infty} \hat{f}(x,s) = f(x)\).

The parameter \(s\) is sometimes called a patience parameter, because the convergence in the second condition can be very slow.

A probabilistic transition system \(\mathscr{Q}= (Q, \pi)\) is computable if the elements of \(Q\) are naturally represented in such a way that (i) the probability transition matrix \(\pi:Q \times Q \rightarrow [0,1]\) is computable in the above sense, and (ii) the support of \(\pi\) and the set of terminal states are decidable. (It is well known that (ii) does not follow from (i) oKo91?, oWeih00?. Fortunately, (ii) does hold in many cases of interest, including chemical reaction networks.)

Similarly, an initialization \(\sigma\) of a probabilistic transition system \(\mathscr{Q}= (Q, \pi)\) is computable if (i) the function \(\sigma:Q \rightarrow [0,1]\) is computable, and (ii) the support of \(\sigma\) is decidable.

Let \(\mathscr{Q}\) be a probabilistic transition system that is computable, and let \(\sigma\) be an initialization of \(\mathscr{Q}\) that is also computable. A state sequence \(\boldsymbol{q} \in \mathbb{A}_{\mathscr{Q}}(\sigma)\) is (algorithmically) random if there is no lower semicomputable \((\mathscr{Q}, \sigma)\)-martingale that succeeds on \(\boldsymbol{q}\).

This notion of random sequences in \(\mathbb{A}_{\mathscr{Q}}(\sigma)\) closely resembles the well-understood theory of random sequences on a finite alphabet zvonkin1970complexity?, schnorr1977survey?. The main differences are that here the state set may be countably infinite; transitions from a state to itself are forbidden; and a positive-probability state sequence may terminate, in which case it is clearly random. The following analogs of the theorems of Ville and Schnorr hold for probabilistic transition systems.

4 Random sequences of sojourn times↩︎

The “sojourn time” that a continuous-time Markov chain spends in a state before jumping to a new state may be any element of \((0,\infty]\), i.e., any duration \(t\) that is either a (strictly) positive real number or \(\infty\). This section thus develops the elements of algorithmic randomness for sequences of durations \(t \in (0,\infty]\) with respect to sequences of probability measures that occur in continuous-time Markov chains.

A rate in this paper is a nonnegative real number \(\lambda \in [0,\infty)\). We rely on context to distinguish this standard use of \(\lambda\) from the equally standard use of \(\lambda\) to denote the empty string.

We interpret each rate \(\lambda >0\) as a name of the exponential probability measure with rate \(\lambda\), i.e., the probability measure on \((0,\infty]\) whose cumulative distribution function \(F_\lambda:(0,\infty] \rightarrow [0,1]\) is given by \[F_\lambda(t) = 1-e^{-\lambda t}\] for all \(t \in (0,\infty]\), where \(e^{-\infty} = 0\). We interpret the rate \(\lambda = 0\) as a name of the point-mass probability on \((0, \infty]\) that concentrates all the probability at \(\infty\). This has the cumulative distribution function \(F_0:(0,\infty] \rightarrow [0,1]\) given by

\[F_0(t) = \begin{cases} 0 &\text{ if } t \in (0,\infty)\\ 1 &\text{ if } t = \infty. \end{cases}\]

We associate each string \(w \in \{0,1\}^*\) with the interval \(I_w \subseteq [0,1]\) defined as follows. Let \(w\) be the lexicographically \(i^{\text{th}}\) \((0 \leq i < 2^{|w|})\) element of \(\{0,1\}^{|w|}\) where \(0^{|w|}\) is the \(0^{\text{th}}\) element and \(1^{|w|}\) is the \((2^{|w|} -1)^{\text{st}}\) element. Then \[I_w = (2^{-|w|}i, 2^{-|w|}(i+1)].\] Note that, for each \(w \in \{0,1\}^*\) and \(\ell \in \mathbb{N}\), the intervals \(I_{wu}\), for \(u \in \{0,1\}^\ell\), form a left-to-right partition of \(I_w\), i.e., a partition of \(I_w\) in which \(I_{wu}\) lies to the left of \(I_{wv}\) if and only if \(u\) lexicographically precedes \(v\).

For each rate \(\lambda \in [0,\infty)\) and each string \(w \in \{0,1\}^*\), define the interval \[D_\lambda(w) = F_\lambda^{-1}(I_w) \subseteq (0,\infty].\]

Example 4 shows that the assumption \(\lambda >0\) is essential here.

For each rate \(\lambda \in [0,\infty)\), each duration \(t \in (0,\infty]\), and each \(w \in \{0,1\}^*\), we call \(w\) a \(\lambda\)-approximation (or a partial \(\lambda\)-specification) of \(t\), and we write \(w \sqsubseteq_\lambda t\), if \(t \in D_\lambda(w)\). Note that, for each duration \(t\in (0,\infty]\), there is a unique sequence \(\mathop{\mathrm{bin}}_{\lambda}(t)\in\{0,1\}^{\omega}\) such that, for every prefix \(w\sqsubseteq \mathop{\mathrm{bin}}_{\lambda}(t)\), we have \(w\sqsubseteq_{\lambda}t\). Note also that for \(\lambda>0\) the function \(t\mapsto \mathop{\mathrm{bin}}_{\lambda}(t)\) is a measure-preserving one-to-one correspondence between \((0, \infty]\), endowed with the probability measure \(\mu_{\lambda}\) whose cumulative distribution function is \(F_{\lambda}\), and the Lebesgue measure 1 subset of \(\{0,1\}^{\omega}\) consisting of those sequences containing infinitely many 1s.

For this discussion, consider a martingale to be as originally defined by Ville Ville39?, namely, a function \(d:\{0,1\}^*\to[0,\infty)\) such that, for all \(w\in\{0,1\}^*\), \[d(w)= \frac{d(w0)+d(w1)}{2}.\] Given a rate \(\lambda\in [0,\infty)\), say that a martingale \(d\) \(\lambda\)-succeeds on a duration \(t\in (0,\infty]\), and write \(t\in S_{\lambda}[d]\), if the set \[\{d(w)\mid w \sqsubseteq_{\lambda} t\}\] is unbounded. We call \(S_{\lambda}[d]\) the \(\lambda\)-success set of \(d\). By the preceding paragraph, the following theorem follows immediately from Ville’s original theorem.

1. \(\mu_{\lambda}(E)=0.\)

2. There is a martingale \(d\) such that \(E\subseteq S_{\lambda}[d]\).

Motivated by Theorem 6, for each rate \(\lambda\in [0,\infty)\), we define a duration \(t \in (0,\infty]\) to be (algorithmically) \(\lambda\)-random if there is no lower semicomputable martingale \(d\) such that \(t\in S_{\lambda}[d]\).

Our next objective is to extend the above definition to the independent randomness of a finite sequence \((t_0, \ldots,t_{n-1})\in (0,\infty]^{n}\) of durations with respect to a corresponding sequence \((\lambda_0,\ldots, \lambda_{n-1})\in [0,\infty)^n\) of rates. There are several equivalent ways of doing this, but the simplest for our purpose here is to adapt van Lambalgen’s interleaving method jLamb87? to the present context.

Given \(n\) binary sequences \(x_0,\ldots,x_{n-1}\in\{0,1\}^{\leq\omega}\) of equal length, define the interleaving of these sequences \(z=\bigsqcup_{r=0}^{n-1} x_r\) by \[z[qn+r]=x_r[q]\] for each \(q<|x_0|\) and \(0\leq r <n\). Intuitively, \(\bigsqcup_{r=0}^{n-1} x_r\) is a “perfect shuffle” of the sequences \(x_0,\ldots,x_{n-1}\).

For any finite rate sequence \((\lambda_0, \ldots, \lambda_{n-1})\in[0,\infty)^n\) and duration sequence \((t_0,\ldots, t_{n-1})\in (0,\infty]^n\), define the sequence \[\mathop{\mathrm{bin}}_{(\lambda_0,\ldots,\lambda_{n-1})}(t_0,\ldots, t_{n-1})=\bigsqcup_{r=0}^{n-1}\mathop{\mathrm{bin}}_{\lambda_r}(t_r).\] Given a martingale \(d\), we say the martingale \((\lambda_0, \ldots, \lambda_{n-1})\)-succeeds on the sequence \((t_0,\ldots, t_{n-1})\), and write \((t_0,\ldots, t_{n-1})\in S_{(\lambda_0,\ldots, \lambda_{n-1})}[d]\), if \[\limsup_{k\to \infty}d\big(\mathop{\mathrm{bin}}_{(\lambda_0,\ldots,\lambda_{n-1})}(t_0,\ldots, t_{n-1})[0\ldots k-1]\big)=\infty.\] Then a finite sequence \((t_0,\ldots, t_{n-1})\in (0,\infty]^n\) of durations is independently \((\lambda_0,\ldots,\lambda_{n-1})\)-random, where \((\lambda_0,\ldots, \lambda_{n-1})\in[0,\infty)^n\), if there is no lower semicomputable martingale \(d\) such that \[(t_0,\ldots, t_{n-1})\in S_{(\lambda_0,\ldots,\lambda_{n-1})}[d].\]

We now lift the above ideas to possibly infinite sequences of rates and durations. A rate sequence is a nonempty sequence \(\boldsymbol{\lambda} = (\lambda_i \mid 0 \leq i < |\boldsymbol{\lambda}|) \in [0,\infty)^{\leq \omega}\) with the property that, for each \(0 \leq i < |\boldsymbol{\lambda}|\), \[i+1 < |\boldsymbol{\lambda}| \iff \lambda_i > 0.\] That is, either \(\boldsymbol{\lambda}\) is finite with a single 0 entry, occurring at the end, or \(\boldsymbol{\lambda}\) is infinite with no \(0\) entries.

If \(\boldsymbol{\lambda} = (\lambda_i \mid 0 \leq i < |\boldsymbol{\lambda}|)\) is a rate sequence, then a \({\boldsymbol{\lambda}}\)-duration sequence is a sequence \[\boldsymbol{t} = (t_i \mid i < |{\boldsymbol{\lambda}}|) \in (0, \infty]^{\leq \omega}\] such that, for each \(0 \leq i < |{\boldsymbol{\lambda}}|\), \[t_i < \infty \iff \lambda_i > 0.\] We write \(\boldsymbol{D_\lambda}\) for the set of all \({\boldsymbol{\lambda}}\)-duration sequences. Note that

\[\boldsymbol{D_\lambda} = \begin{cases} (0,\infty)^{|{\boldsymbol{\lambda}}| -1} \times \{\infty\} &\text{if } |{\boldsymbol{\lambda}}| < \omega.\\ (0,\infty)^\omega &\text{if } |{\boldsymbol{\lambda}}| = \omega \end{cases}\] depends only on the length of \({\boldsymbol{\lambda}}\), not on the components of \({\boldsymbol{\lambda}}\).

If \(\boldsymbol{\lambda} = (\lambda_i \mid 0 \leq i < |\boldsymbol{\lambda}|)\) is a rate sequence, \(\boldsymbol{t} = (t_i \mid i < |{\boldsymbol{\lambda}}|) \in \boldsymbol{D_\lambda}\) is a \({\boldsymbol{\lambda}}\)-duration sequence, and \(\boldsymbol{w} = (w_i \mid i < |\boldsymbol{w}|) \in (\{0,1\}^*)^*\) is a finite sequence of binary strings with \(|\boldsymbol{w}| \leq |{\boldsymbol{\lambda}}|\), then we call \(\boldsymbol{w}\) a \({\boldsymbol{\lambda}}\)-approximation (or a partial \({\boldsymbol{\lambda}}\)-specification) of \(\boldsymbol{t}\), and we write \(\boldsymbol{w} \sqsubseteq_{{\boldsymbol{\lambda}}} \boldsymbol{t}\), if \(w_i \sqsubseteq_{\lambda_i} t_i\) holds for all \(0 \leq i < |\boldsymbol{w}|\).

If \({\boldsymbol{\lambda}}\) is a rate sequence and \(\boldsymbol{w} \in (\{0,1\}^*)^*\) is a finite sequence of binary strings with \(|\boldsymbol{w}| \leq |{\boldsymbol{\lambda}}|\), then the \({\boldsymbol{\lambda}}\)-cylinder generated by \(\boldsymbol{w}\) is the set \[\boldsymbol{D_\lambda}(\boldsymbol{w}) = \{\boldsymbol{t} \in \boldsymbol{D_\lambda} \mid \boldsymbol{w} \sqsubseteq_{{\boldsymbol{\lambda}}} \boldsymbol{t}\}.\]

Given a rate sequence \({\boldsymbol{\lambda}}\), let \[\Phi=\Phi[{\boldsymbol{\lambda}}]=\bigcup_{n\in\mathbb{N}}(\{0,1\}^n)^{\min\{n,|{\boldsymbol{\lambda}}|\}}.\] It is routine to verify that the collection \[\mathscr{D}_{{\boldsymbol{\lambda}}}= \{\boldsymbol{D_\lambda}(\boldsymbol{w}) \mid \boldsymbol{w} \in \Phi\}\] is a semi-algebra of subsets of \(\boldsymbol{D_\lambda}\) that generates the \(\sigma\)-algebra \(\mathscr{B}_{\boldsymbol{\lambda}}\) of all Borel subsets of \(\boldsymbol{D}_{{\boldsymbol{\lambda}}}\). Defining the function \(\mu_{\boldsymbol{\lambda}}:\mathscr{D}_{{\boldsymbol{\lambda}}}\rightarrow [0,1]\) by \[\mu_{\boldsymbol{\lambda}}(\boldsymbol{D}_{{\boldsymbol{\lambda}}}(\boldsymbol{w})) = \begin{cases} 2^{-|\boldsymbol{w}|^2}&\text{if }|\boldsymbol{w}|<|{\boldsymbol{\lambda}}|\\ 2^{-(|{\boldsymbol{\lambda}}|-1)|w_0|}&\text{if }|\boldsymbol{w}|=|{\boldsymbol{\lambda}}|\text{ and }w_{|{\boldsymbol{\lambda}}|-1}=1^{|w_0|}\\ 0&\text{otherwise}. \end{cases}\] for all \(\boldsymbol{w}=(w_0,\ldots,w_{n-1}) \in \Phi\), it follows by standard techniques that \(\mu_{\boldsymbol{\lambda}}\) extends uniquely to a probability measure \(\mu_{\boldsymbol{\lambda}}: \mathscr{B}_{\boldsymbol{\lambda}}\rightarrow [0,1]\). When convenient, we use the abbreviation \[\mu_{\boldsymbol{\lambda}}(\boldsymbol{w}) = \mu_{\boldsymbol{\lambda}}(\boldsymbol{D_{\boldsymbol{\lambda}}}(\boldsymbol{w})).\]

An arbitrary set \(E\subseteq\boldsymbol{D}_{\boldsymbol{\lambda}}\) has probability 0, and we write \(\mu_{\boldsymbol{\lambda}}(E)=0\), if there is some Borel set \(F\supseteq E\) such that \(\mu_{\boldsymbol{\lambda}}(F)=0\). It has algorithmic probability 0, and we write \(\mu_{{\boldsymbol{\lambda}},\mathop{\mathrm{alg}}}(E)=0\), if there is a computable function \(g:\mathbb{N}\times\mathbb{N}\to\Phi\) such that, for all \(k\in\mathbb{N}\), \[E\subseteq\bigcup_{\ell\in\mathbb{N}}\boldsymbol{D}_{\boldsymbol{\lambda}}(g(k,\ell))\] and \[\sum_{\ell\in\mathbb{N}}\mu_{\boldsymbol{\lambda}}(g(k,\ell))\leq 2^{-k}.\]

If \(\boldsymbol{\lambda}\) is a rate sequence, then a \({\boldsymbol{\lambda}}\)-martingale is a function \[d:\Phi \rightarrow [0,\infty)\] that satisfies \[d(\boldsymbol{w})\mu_{\boldsymbol{\lambda}}(\boldsymbol{w}) = \sum_{\substack{b_0,\ldots,b_n\in\{0,1\}\\w_n\in\{0,1\}^n}}d(w_0b_0,\ldots,w_{n}b_{n})\mu_{\boldsymbol{\lambda}}(w_0b_0,\ldots,w_{n}b_{n})\] for all \(\boldsymbol{w} = (w_0, \ldots, w_{n-1}) \in\Phi\) such that \(n<|{\boldsymbol{\lambda}}|\) and \[d(\boldsymbol{w})\mu_{\boldsymbol{\lambda}}(\boldsymbol{w}) = \sum_{b_0,\ldots,b_{n-1}\in\{0,1\}}d(w_0b_0,\ldots,w_{n-1}b_{n-1})\mu_{\boldsymbol{\lambda}}(w_0b_0,\ldots,w_{n-1}b_{n-1})\] for all \(\boldsymbol{w} = (w_0, \ldots, w_{n-1}) \in\Phi\) such that \(n=|{\boldsymbol{\lambda}}|\).

Intuitively, a \({\boldsymbol{\lambda}}\)-martingale \(d\) is a strategy that a gambler may use for betting on approximations \(w_i\) of the durations \(t_i\) in a \({\boldsymbol{\lambda}}\)-duration sequence \(\boldsymbol{t} = (t_i \mid i < |\boldsymbol{t}|)\). The gambler’s initial amount of money is the value \(d(())\) of \(d\) at the empty sequence \(()\) of binary strings. If \(\boldsymbol{w} = (w_0, \ldots, w_{n-1}) \sqsubseteq_{\boldsymbol{\lambda}}\boldsymbol{t}\), meaning that each \(t_i\) is in the interval \(\boldsymbol{D_{\boldsymbol{\lambda}}}(w_i) \subseteq (0,\infty]\), then \(d(\boldsymbol{w})\) is the amount of money that the gambler has after betting on \(\boldsymbol{w}\).

A \({\boldsymbol{\lambda}}\)-martingale \(d\) succeeds on a \({\boldsymbol{\lambda}}\)-duration sequence \(\boldsymbol{t}\) if the set \[\{d(\boldsymbol{w}) \mid \boldsymbol{w}\in\Phi\text{ and }\boldsymbol{w} \sqsubseteq_{\boldsymbol{\lambda}}\boldsymbol{t} \}\] is unbounded. The success set of a \({\boldsymbol{\lambda}}\)-martingale \(d\) is \[S^\infty[d] = \{\boldsymbol{t} \in \boldsymbol{D_{\boldsymbol{\lambda}}} \mid d \text{ succeeds on } \boldsymbol{t}\}.\] We define a sequence \(\boldsymbol{t} \in \boldsymbol{D_{\lambda}}\) to be (algorithmically) \({\boldsymbol{\lambda}}\)-random if there is no lower semicomputable \({\boldsymbol{\lambda}}\)-martingale that succeeds on \(\boldsymbol{t}\).

5 Measure and martingales for continuous-time Markov chains↩︎

5.1 Continuous-time Markov chains↩︎

A continuous-time Markov chain (CTMC) is an ordered triple \[C = (Q, \lambda, \sigma),\] where \(Q\) is a countable set of states, \(\lambda:Q \times Q \rightarrow [0,\infty)\) is a rate matrix satisfying \(\lambda(q,q) = 0\) for every \(q \in Q\), and \(\sigma: Q \rightarrow [0,1]\) is a state initialization as described in section 3.

Let \(C = (Q, \lambda, \sigma)\) be a CTMC. At each time \(t \in [0, \infty)\), \(C\) is probabilistically in some state. At time \(t = 0\), this state is chosen according to \(\sigma\). For each state \(q \in Q\), the real number \[\lambda_q = \sum_{r \in Q}\lambda(q, r)\] is the rate out of state \(q\). If \(\lambda_q = 0\), then \(q\) is a terminal state, meaning that if \(C\) ever enters state \(q\), then \(C\) remains in state \(q\) forever. If \(\lambda_q > 0\), then \(q\) is a nonterminal state, and if \(C\) enters \(q\) at some time \(t\), then the sojourn time for which \(C\) remains in state \(q\) before moving to a new state is a random variable that has the exponential distribution with rate \(\lambda_q\). Hence the expected sojourn time of \(C\) in state \(q\) is \(\frac{1}{\lambda_q}\). When \(C\) does move to a new state, it moves to state \(r \in Q\) with probability \[p(q, r) = \frac{\lambda(q,r)}{\lambda_q}.\]

Note that the CTMC model uses continuous time, with sojourn times ranging over \((0, \infty]\), but a discrete state space. Accordingly, its state transitions, called jump transitions, are instantaneous.

5.2 Trajectories in CTMCs↩︎

A trajectory of a CTMC \(C = (Q, \lambda, \sigma)\) is a sequence \(\boldsymbol{\tau}\) of the form \[\boldsymbol{\tau} = ((q_n,t_n) \mid n \in \mathbb{N}) \in (Q \times (0,\infty])^\omega.\] Intuitively, such a trajectory \(\boldsymbol{\tau}\) denotes the turn of events in which \(q_0, q_1, \ldots\) are the successive states of \(C\) and \(t_0, t_1,\ldots\) are the successive sojourn times of \(C\) in these states. Accordingly, we write \[state_{\boldsymbol{\tau}}(n) = q_n, \text{ } soj_{\boldsymbol{\tau}}(n) = t_n\] for each \(n \in \mathbb{N}\). When convenient, we write \(\boldsymbol{\tau}\) as an ordered pair \[\boldsymbol{\tau} = (\boldsymbol{q}, \boldsymbol{t}),\] where \(\boldsymbol{q} = (q_n \mid n \in \mathbb{N})\) and \(\boldsymbol{t} = (t_n \mid n \in \mathbb{N})\).

There are two ways in which a trajectory \((\boldsymbol{q}, \boldsymbol{t})\) may fail to represent a “true trajectory” of the CTMC \(C\) in the above intuitive sense. First, it may be the case that \(p(q_n, q_{n+1}) = 0\) (i.e., \(\lambda(q_n, q_{n+1}) = 0\)) for some \(n \in \mathbb{N}\). This presents no real difficulty, since it merely says that the event “\(state_{\boldsymbol{\tau}}(n) = q_n\) and \(state_{\boldsymbol{\tau}}(n+1) = q_{n+1}\)” has probability \(0\). The second way in which \((\boldsymbol{q}, \boldsymbol{t})\) may fail to represent a “true trajectory” is for some \(q_n\) to be a terminal state of \(C\). We deal with this by defining the length of a trajectory \(\boldsymbol{\tau} = (\boldsymbol{q}, \boldsymbol{t})\) to be \[\|\boldsymbol{\tau}\| = \min\{n \in \mathbb{N} \mid q_n \text{ is terminal}\},\] where \(\min\emptyset = \infty\). We then intuitively interpret a trajectory \(\boldsymbol{\tau} = (\boldsymbol{q}, \boldsymbol{t})\) with \(\|\boldsymbol{\tau}\| < \infty\) as the finite sequence \[\boldsymbol{\tau}' = ((q_n,t_n') \mid n \leq \|\boldsymbol{\tau}\|),\] where each \[t_n' = \begin{cases} t_n & \text{if } n < \|\boldsymbol{\tau}\|\\ \infty & \text{if } n = \|\boldsymbol{\tau}\|. \end{cases}\] We write \[\Omega = \Omega[C] = (Q \times (0,\infty])^\omega\] for the set of all trajectories of \(C\).

5.3 Measure in CTMCs↩︎

Elements of \((Q\times\{0,1\}^*)^*\) are called approximations or partial specifications of trajectories. The cylinder generated by an approximation \(w = ((q_0,u_0),\ldots,(q_{n-1},u_{n-1}))\) is the set \[\Omega_w =\big\{ \boldsymbol{\tau} \in \Omega \mid (\forall\, 0 \leq i < n)\;\big(state_{\boldsymbol{\tau}}(i) = q_i\text{ and } soj_{\boldsymbol{\tau}}(i) \in D_{\lambda_{q_i}}(u_i)\big)\big\};\] in particular, the cylinder generated by the empty sequence \(()\) is \(\Omega_{()}=\Omega\). For two approximations \(w,x\) and \(\boldsymbol{\tau}\in \Omega\), we write \(w \sqsubseteq\boldsymbol{\tau}\) to indicate that \(\boldsymbol{\tau}\in \Omega_w\) and \(w \sqsubseteq x\) to indicate that \(\Omega_x \subseteq \Omega_w\). It is easily verified that the latter condition is decidable. When it is convenient, we will write partial specifications in the form \((\boldsymbol{q},\boldsymbol{t})\), where \(\boldsymbol{q}\in Q^*\), \(\boldsymbol{t}\in(\{0,1\}^*)^*\), and \(|\boldsymbol{q}|=|\boldsymbol{t}|\).

Let \[\Psi=\Psi[C]=\bigcup_{n\in\mathbb{N}}(Q\times\{0,1\}^n)^n,\] the set of all partial specifications which, for some \(n\), specify \(n\) states and \(n\) sojourn times, each up to \(n\) bits of precision. For each \(w\in\Psi\), the probability of the cylinder \(\Omega_w\) in \(C\), written \(\mu_C(\Omega_w)\) or \(\mu_C(w)\), is defined by \(\mu_C(())=1\) and, for each \(n\geq 1\) and \(w=((q_0,u_0),\ldots,(q_{n-1},u_{n-1}))\in (Q\times\{0,1\}^n)^n\), \[\mu_C(w)=\begin{cases} \sigma(q_0)\prod\limits_{i=0}^{\min\{n,\|w\|\}-2}\left(p(q_i,q_{i+1})2^{-|u_i|}\right)&\text{if }(\forall\, \|w\|\leq i<n)\;(q_i,u_i)=(q_{\|w\|},1^{n})\\ 0&\text{otherwise}, \end{cases}\] where \[\|w\|=\min\{i<n\mid q_i\text{ is terminal}\},\] again with the convention \(\min\emptyset=\infty\).

A set \(X \subseteq \Omega\) has probability 0, and we write \(\mu_C(X)=0\), if there is a function \(g:\mathbb{N}\times\mathbb{N}\to\Psi\) such that, for all \(k\in\mathbb{N}\), \[X\subseteq \bigcup_{\ell\in\mathbb{N}}\Omega_{g(k,\ell)}\] and \[\sum_{\ell\in\mathbb{N}}\mu_C(g(k,\ell))\leq 2^{-k}.\]

5.4 Martingales for CTMCs↩︎

A \(C\)-supermartingale is a function \(d:\Psi\to[0,\infty)\) such that, for all \(w\in\Psi\), \[\label{eq:supermartingale} d(w)\mu_C(w) \geq\sum_{\substack{w'\in\Psi\\w\sqsubseteq w'\\|w'|=|w|+1}}d(w')\mu_C(w').\tag{4}\] If equality holds in 4 for all \(w\in\Psi\), then \(d\) is a \(C\)-martingale. A \(C\)-supermartingale \(d\) succeeds on a trajectory \(\boldsymbol{\tau}\in\Omega\), and we write \(\boldsymbol{\tau}\in S_C[d]\), if the set \[\{d(w)\mid w\in\Psi\text{ and }w\sqsubseteq \boldsymbol{\tau}\}\] is unbounded.

5.5 Analog of Ville’s theorem for CTMC trajectories↩︎

In order to prove an analog of Ville’s theorem holds for CTMC trajectories, we first prove the following lemma, which is analogous to Kraft’s inequality for prefix codes. A set \(B\) of partial specifications of trajectories is a prefix-free set if, for all distinct \(w,x\in B\), we do not have \(w\sqsubseteq x\).

We now prove the following analog of Ville’s theorem Ville39? for CTMC trajectories.

A slightly simplified version of the above proof yields the following analog of Ville’s theorem Ville39? for sojourn time sequences.

6 Random CTMC trajectories↩︎

6.1 Algorithmic measure and randomness in CTMCs↩︎

Let \(C=(Q,\lambda,\sigma)\) be a CTMC. We assume that the states \(q\in Q\) have canonical representations, so that it is clear what it means for functions \(f:Q\rightarrow Q\) etc. to be computable.

A set \(X \subseteq \Omega[C]\) has algorithmic probability 0, and we write \(\mu_{C,\mathop{\mathrm{alg}}}(X)=0\), if there is a computable function \(g:\mathbb{N}\times\mathbb{N}\to\Psi\) such that, for all \(k\in\mathbb{N}\), \[X\subseteq \bigcup_{\ell\in\mathbb{N}}g(k,\ell)\] and \[\sum_{\ell\in\mathbb{N}}\mu_C(g(k,\ell))\leq 2^{-k}.\] We define an individual trajectory \(\boldsymbol{\tau}\) of a CTMC \(C\) to be algorithmically random if there is no lower semicomputable \(C\)-martingale \(d\) such that \(\boldsymbol{\tau}\in S_C[d]\).

6.2 Analog of Schnorr’s theorem for CTMCs↩︎

A slightly simplified version of the above proof yields the following analog of Schnorr’s theorem DBLP:journals/mst/Schnorr71? for sequences of sojourn times.

6.3 Analog of van Lambalgen’s theorem for CTMC trajectories↩︎

7 Kolmogorov complexity and CTMC randomness↩︎

Random trajectories can also be characterized using Kolmogorov complexity. First, we briefly review this notion in the classical setting. We fix a universal self-delimiting Turing machine (see oLiVit19?), \(U\). The Kolmogorov complexity, \(K\), of a (finite) string \(x\) in \(\{0,1\}^*\) is the length of a shortest program for a self-delimiting Turing machine which prints \(x\). That is, \(K: \{0,1\}^* \rightarrow \mathbb{N}\) is defined by \[K(x) = \min \{|\pi| \mid U(\pi) = x\;\text{ and } \pi \in \{0,1\}^*\}.\] When \(x\) is not a binary string, but some other finite object, \(K(x)\) is defined from the above by routine coding.

In the terminology of chaitin1987incompleteness?, an information content measure is a function \(f:\mathbb{N}\to\mathbb{N}\) that is upper semicomputable and satisfies \(\sum_{n\in\mathbb{N}}2^{-n}<1\). Will repeatedly use the fact that \(K\) is a minimal information content measure, in the sense that for every information content measure \(f\), there is a constant \(c\) such that, for all \(i\in\mathbb{N}\), we have \(K(n)\leq f(n)+c\).

In this section, we deal with the full class \((Q\times\{0,1\}^*)^*\) of partial specifications of trajectories rather than just the restricted class \(\Psi\) that we used to define measure and randomness in sections 5 and 6. This allows a partial specification to approximate different sojourn times to different levels of precision, which lets us state the following results in a more general way, although these theorems also hold for the restricted class \(\Psi\). The profile of a cylinder \(\Omega_w\), where \(w=((q_0,u_0),\ldots,(q_{n-1},u_{n-1}))\in (Q\times\{0,1\}^*)^n\), is an element of \(\mathbb{N}^n\), denoted \[\mathop{\mathrm{prof}}(w) = (|u_0|,\ldots ,|u_{n-1}|).\] The profile of the empty sequence is \(\mathop{\mathrm{prof}}(())=()\).

For each partial specification \(w\in(Q\times\{0,1\}^*)^*\) of a CTMC \(C\), the self-information of \(w\) is \[h(w)=\log\left(\frac{1}{\mu_C(w)}\right).\] The following two lemmas are analogous to standard results used in the Kolmogorov complexity characterization of algorithmically random sequences. We let \(p\) range over all profiles, and assume some natural encoding (enumerating process) between natural numbers and profiles, and also between natural numbers and cylinders.

When \(W\) is a set of partial specifications, we write \(\mu_C(W)\) as shorthand for \(\mu_C\big(\bigcup_{w\in W}\Omega_w\big)\).

With these lemmas, we can establish the Kolmogorov complexity characterization of randomness for trajectory objects, which is exactly analogous to a well-known characterization of the algorithmic randomness of sequences over finite alphabets zvonkin1970complexity?, schnorr1977survey?.

8 Chemical reaction network randomness and Zeno phenomena↩︎

In this last section we use our machinery to prove a fundamental fact about random trajectories in stochastic mass-action chemical reaction networks. We first briefly review the varieties of such chemical reaction networks and indicate how they are all special cases of CTMCs. More extensive discussions of this appear in jSoCoWiBr08?, oCSWB09?, oFeinberg19? and elsewhere.

A chemical reaction network (CRN) is a pair \(N = (S, R)\), where \(S\) is a finite set of species (intuitively, types of molecules), and \(R\) is a finite set of reactions, each of which is a triple \(\rho = (r, p, k) \in \mathbb{N}^S \times \mathbb{N}^S \times [0, \infty)\), where \(r\) and \(p\) are as in the rate-free CRNs defined in section 2 above (recalling that \(p\) and \(r\) are distinct), and \(k\) is the rate constant of the reaction \(\rho\).

Stochastic mass-action CRNs are usually just called stochastic CRNs, because mass-action kinetics are so commonly used as to be the default. Even so, there are several inequivalent definitions. These definitions have the following commonalities.

(i) A state of a stochastic CRN \(N = (S, R)\) is a vector \(q \in \mathbb{N}^S\) whose intuitive meaning is that, for each \(X \in S\), there are \(q(X)\) molecules of the species \(X\) in solution in the state \(q\). That is, \(q(X)\) is the molecular count of the species \(X\) in the state \(q\).

(ii) The rate \(\lambda(\rho, q)\) of a reaction \(\rho = (r, p, k)\) of \(N\) in a state \(q\) is determined by \(\rho\), \(q\), and perhaps the volume \(V\) of the solution, which is taken to be a constant. In all the definitions, \[\label{eq:crn1} \lambda(\rho, q) = k u P,\tag{6}\] where the factor \(u\) is bounded by a constant and \[\label{eq:crn2} P = \prod_{X \in S} q(X)^{r(X)}.\tag{7}\] It is the form of the product in 7 that characterizes the kinetics here as “mass-action”. The factor \(u\) above incorporates two variabilities in the literature, namely, whether and how the volume \(V\) is incorporated and whether the “sampling with replacement” factors \(q(X)^{r(X)}\) are replaced by the corresponding “sampling without replacement” factors, which are potentially smaller but more realistic in nanoscale applications with small molecular counts.

(iii) Given a stochastic CRN \(N = (S, R)\) as above, together with a probabilistic initialization \(\sigma: \mathbb{N}^S \to [0,1]\) defined as in section 3 (and noting that this initialization is deterministic if some \(\sigma(q) = 1\)), the CTMC of \(N\) initialized by \(\sigma\) is the CTMC \[C(N, \sigma) = (\mathbb{N}^S, \hat{\lambda}, \sigma),\] where \[\hat{\lambda}: \mathbb{N}^S \times \mathbb{N}^S \to [0, \infty)\] is defined by \[\hat{\lambda}(q, r) = \sum_{\substack{\rho \in R\\\rho\text{ transforms }q\text{ to }r}} \lambda(\rho, q)\] for all \(q, r \in \mathbb{N}^S\).

The behavior of the stochastic CRN \(N\) with the initialization \(\sigma\) is by definition the behavior of the CTMC \(C(N, \sigma)\) defined as above.

By 6 and 7 , we have the following.

We now prove our final result.