We introduce the exit time finite state projection (ETFSP) scheme, a truncation-based method that yields approximations to the exit distribution and occupation measure associated with the time of exit from a domain (i.e., the time of first passage to the complement of the domain) of time-homogeneous continuous-time Markov chains. We prove that: (i) the computed approximations bound the measures from below; (ii) the total variation distances between the approximations and the measures decrease monotonically as states are added to the truncation; and (iii) the scheme converges, in the sense that, as the truncation tends to the entire state space, the total variation distances tend to zero. Furthermore, we give a computable bound on the total variation distance between the exit distribution and its approximation, and we delineate the cases in which the bound is sharp. We also revisit the related finite state projection scheme and give a comprehensive account of its theoretical properties. We demonstrate the use of the ETFSP scheme by applying it to two biological examples: the computation of the first passage time associated with the expression of a gene, and the fixation times of competing species subject to demographic noise. chain that is identical to the original chain except that every state outside of the domain is turned into an absorbing state [54, 35] . There exists a rich literature on exit times, especially in physics and biomathematics [31, 41, 49] . Recently, there has been renewed interest in exit times of continuous-time Markov chains with discrete state space [2, 23, 55, 51] , such as those we study in this paper. While the exit problem from a small finite domain is tractable [25, 26] , the exit problem from an infinite or large domain can only be solved in special cases [17, 23, 47] . Various approximation schemes have been developed to address this issue [3, 12, 29, 51] . However, most of them do not provide bounds or error estimates on their accuracy. The popular finite state projection (FSP) scheme [45] yields lower bounds on the time-varying law of the continuous-time chain of interest. The scheme chooses a finite truncation of the state space and solves an associated system of linear ordinary differential equations (ODEs) indexed by the states contained in the truncation. Inbuilt in the procedure is a computable upper bound on the total variation distance between the lower bounds obtained and the time-varying law. However, the FSP does not provide information about the exit from a domain. To fill this gap, we introduce the exit time finite state projection (ETFSP) scheme (Sec. 1.1), that involves applying an FSP-like scheme to the auxiliary chain with an absorbing complement mentioned above. We show that the scheme yields lower bounds on the exit distribution and the occupation measure associated with an exit time. For the exit distribution, we explain how to compute a bound on the error of its approximation. Theorem 1.1 delineates the theoretical properties of ETFSP showing that: (i) the error bound is sharp if and only if the exit event occurs with probability one, and (ii) the scheme converges in total variation to the exit distribution and occupation measure as the truncation approaches the entire state space. A secondary contribution is Theorem 2.5, which gathers the theoretical properties of the FSP scheme. In particular, we show that the error bound of the FSP scheme is sharp if and only if the chain is non-explosive, in which case the error bound can indeed be made arbitrarily small by including enough states in the truncation. In the explosive case, the error bound remains non-zero, as observed in [37] , and is limited by the probability of explosion. The final contribution of this paper is a new proof of an old theorem: Theorem 2.6 expresses the exit distribution in terms of the time-varying law of the aforementioned auxiliary chain. Versions of this theorem pepper the literature (e.g., [21, 56, 48, 38, 49, 54] ). Our variant relaxes the nonexplosive and deterministic initial condition assumptions in [54] , and adds the analogous result for the occupation measure. Related literature To the best of our knowledge, the ideas underpinning the FSP and ETFSP schemes were first delineated in the 1980's queuing literature (see [27, 38, 39] and references therein) centred around randomisation techniques for continuous-time chains with bounded rate matrices. Recently, schemes based on the FSP have been used to bound the cumulative density function of the exit time of stochastic reaction networks, a subclass of the continuous-time chains that we consider here [5, 6, 12] . Given that the ETFSP scheme bounds not only the cumulative density functions but also the corresponding densities, our results imply the convergence of those other schemes as a special case. We briefly define our problem setting, introduce the ETFSP scheme, and state our main result (Theorem 1.1) detailing the theoretical properties of the scheme.
In Ref. REF the authors propose a finite state-space projection scheme to bound first passage time distributions
The exit time finite state projection scheme: bounding exit distributions and occupation measures of continuous-time Markov chains
SIAM Journal on Scientific Computing (2019) 41:A748-A769
Mathematics Physics Biology Computer Science