Algebraic formulas for first-passage times of Markov processes in the linear framework

The linear framework is an approach to analysing biochemical systems based on directed graphs with labelled edges. When applied to individual molecular systems, graph vertices correspond to system states, directed edges to transitions, and edge labels to transition rates. Such a graph specifies the infinitesimal generator of a continuous-time Markov process. The master equation of this Markov process, which describes the forward evolution of vertex probabilities, is a linear differential equation, after which the framework is named, whose operator is the Laplacian matrix of the graph. The Matrix-Tree theorem, when applied to this Laplacian matrix, allows the steady-state probabilities of the Markov process to be expressed as rational algebraic functions of the transition rates. This capability gives algebraic access to problems that have otherwise been treated by approximations or numerical simulations, and enables theorems to be proved about biochemical systems that rise above their underlying molecular complexity. Here, we extend this capability from the steady state to the transient regime. We use the All-Minors Matrix-Tree theorem to express the moments of the conditional first-passage time distribution, and the corresponding splitting probabilities, as rational algebraic functions of the transition rates. This extended capability brings many new biological problems within the scope of the linear framework.