Emergence of generic first-passage-time distributions for large Markovian networks

First-passage-times are often the most relevant aspect of a complex Markovian network because they signify when information processing has resulted in a definite decision. Previous studies have shown that for kinetic proofreading networks in the limit of large network size the first-passage-time distribution converges either to a δ or to an exponential distribution. Remarkably, these two forms correspond to the two extreme distributions of minimal and maximal entropy for a fixed mean, respectively. Here we build on the connection between first-passage-times and graph theory to show that these two limits are not model-specific, but arise generically in Markovian networks from the distribution of the eigenvalues of the generator matrix. A deterministic peak emerges when infinitely many eigenvalues contribute, while the exponential limit arises from a single dominant eigenvalue. We also show that the exponential limit emerges robustly for reversible networks when the mean first-passage-time from the initial state to the target state becomes much larger than the mean first-passage-time in the reverse direction. In contrast, the deterministic limit is not obtained from a simple reversal of this condition, but follows from a nonvanishing conductance or a mean-residual lifetime of the process which becomes small compared to the mean first-passage-time in the long-time limit. This reveals a fundamental asymmetry between the two regimes. Our theoretical analysis is illustrated and validated by computer simulations of one-step master equations and random networks.