Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking

arXiv:2610.13505 · cond-mat.stat-mech, math.PR · Submitted 2026-10-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Condensed Matter. The day in condensed matter: materials, phases and the measurements under them.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "Graph-theoretic framework for semi-Markov networks".

Mira: Here's the gist of the paper. Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times, with applications ranging from biophysics and neuroscience to epidemiology and finance.

Kai: Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph.

Mira: These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

Kai: They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting.

Title and authors: Kai: So we’re looking at this paper today called "Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking." It’s by Julian B. Voits from Heidelberg University.

Mira: It sounds like a pretty dense title. Basically, they are taking semi-Markov networks—systems where the time you stay in a state isn't exponential—and showing you how to use graph theory to calculate things like occupation probabilities and hitting times in a structured way.

Lev: I’m curious how this connects to what we actually build. If we have real hardware, say superconducting qubits, which are inherently probabilistic and time-dependent, can these combinatorial representations be mapped onto our actual gate operations or error correction overheads?

Kai: Exactly that. The paper suggests they replace the constant jump rates in standard Markov networks with something different when dealing with these non-exponential dwell times. It's about making a structural representation—using spanning trees and forests—that works even when the transitions aren't memoryless, which is usually the case in complex physical systems <ref:2610.13505#pg1>.

Mira: The big implication here is that they extend a classical result, the Markov Chain Tree Theorem to these more realistic semi-Markov systems. It suggests that we can still find explicit combinatorial sums for occupation probabilities even when the sojourn times are not simple exponentials <ref:2610.13505#pg2>.

Lev: That sounds promising if we can handle the complexity of those weighted spanning trees. But what about the hardware constraints? If you're trying to run this on a real quantum processor, you need tractable computations. Can these sums be computed in polynomial time for small networks?

Kai: That’s the question for practical application. The paper focuses on showing these representations exist, and they do admit explicit combinatorial representations of the Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph <ref:2610.13505#pg1>.

Mira: So, in essence, they’re providing a way to calculate those probabilities directly from the network structure without having to simulate every single path over time. It moves the problem from dynamic simulation to static graph enumeration <ref:2610.13505#pg1>.

Lev: I need to see how this translates when we introduce those pseudo-rates, which they define as the inverse mean sojourn time weighted by the exit probability through a channel <ref:2610.13505#pg2>. That weighting part sounds like it adds a lot of complexity for an engineer.

Kai: It does add complexity, but Mira points out that for finite-mean waiting times, these pseudo-rates give you the same stationary occupation probabilities as in standard Markov networks <ref:2610.13505#pg3>.

Mira: That’s a key point. If the mean sojourn times are finite, the structure simplifies back to something familiar, just with those adjusted rates—the pseudo-rates kappa i j which is defined as p i j times the mean sojourn time in state i <ref:2610.13505#pg3>.

Lev: So for systems where we can bound the average time spent in a state, this framework lets us leverage existing Markov network tools, just with these new rate definitions. What happens when we move into those heavy-tailed sojourn times?

Kai: That’s what they tackle next. The paper extends this graph theory to infinite-mean sojourn times with power-law tails <ref:2610.13505#pg3>.

Mira: And for the infinite mean case, they show that only the heaviest-tailed states can serve as roots of spanning trees in the underlying graph and still have a positive occupation probability in the long time limit <ref:2610.13505#pg3>.

Lev: That sounds like it might impose a strong structural constraint on which states are relevant in those long-term distributions. If we have an infinite mean, you're dealing with very slow, rare events dominating the statistics.

Kai: It suggests that the structure of the graph itself dictates what survives in those long-time limits for those specific types of systems <ref:2610.13505#pg3>.

Mira: So this paper isn't just about finding formulas; it’s about revealing which parts of the network topology are actually important when the system spends a very long time in certain states.

Lev: It gives us a way to analyze those rare, slow transitions, which is crucial for understanding how systems behave over very long timescales before they settle into their steady state.

The paper's summary: Kai: So we’ve established that this paper tackles semi-Markov networks—systems with non-exponential dwell times—and introduces a graph theory approach to get explicit sums for occupation probabilities and hitting times in Laplace space <ref:2610.13505#pg1>.

Mira: The core idea is that they replace the usual constant jump rates with memory kernels in Laplace space, which is how you handle the non-exponential nature of those dwell times <ref:2610.13505#pg3>.

Lev: And they show that this mathematical machinery works for both finite-mean waiting times and those infinite-mean sojourn times with power-law tails <ref:2610.13505#pg3>.

Kai: The paper shows that for finite-mean waiting times, the stationary occupation probabilities have the same tree representation as in Eq. one but the transition rates are substituted by these pseudo-rates kappa i j equals p i j times the mean sojourn time in state i <ref:2610.13505#pg3>.

Mira: This is a major simplification because it connects the semi-Markov case back to a known Markov network result, suggesting that for finite means, you can use the standard machinery with these modified rates <ref:2610.13505#pg2>.

Lev: I’m still thinking about that connection. It seems like a way to bridge the gap between continuous time processes and discrete state transitions when the average time in those states is finite.

Kai: Right, and for infinite-mean sojourn times with power-law tails, they show an analogous identity holds for occupation probabilities <ref:2610.13505#pg3>.

Mira: But here it gets more subtle because only the heaviest-tailed states can be roots of spanning trees in the underlying graph and still have a positive occupation probability as time goes to infinity <ref:2610.13505#pg3>.

Lev: So, in the infinite mean case, the long-time behavior is dominated by those specific states that have the longest expected stay times. That’s a very different kind of dominance than what you see in finite mean systems.

Kai: And they also extend recently derived combinatorial formulas for hitting-time moments to this semi-Markov setting <ref:2610.13505#pg3>.

Mira: They can compute the k-th moment of the hitting time, E T k, if the sojourn times have finite moments up to order n, and that formula involves derivatives of the Laplace transform at zero <ref:2610.13505#pg3>.

Lev: So we can calculate higher moments for hitting times, which is useful when you need more than just the average time spent in a state. That's a step up from just finding the mean hitting time, E T.

Kai: And interestingly, they say that the mean hitting time formula itself is identical to that of a Markov network if you use those pseudo-rates <ref:2610.13505#pg3>.

Mira: That means for the average hitting time, you get a nice result from Markov chain theory applied to these pseudo-rates, which also leads to a short proof about Kemeny's constant for finite-mean semi-Markov networks <ref:2610.13505#pg3>.

Lev: That’s a neat little consistency check. The mean hitting time formula matching up across the two frameworks when you use those pseudo-rates as transition rates, it seems robust and provides some stability.

The paper's improvements: Kai: Now let's talk about what the authors suggest is new or improved in this work. They’re not just presenting a new framework; they are pushing it forward into asymptotic results <ref:2610.13505#pg1>.

Mira: Specifically, they generalize the Markov Chain Tree Theorem to semi-Markov networks, which gives us those asymptotic results for occupation probabilities <ref:2610.13505#pg2>.

Lev: Generalizing the MCTT is huge if it means we can get a clean formula instead of relying on approximations for these complex systems. What kind of generalization are we talking about?

Kai: They replace the constant jump rates with pseudo-rates, which they define as the inverse mean sojourn time weighted by the exit probability through that channel <ref:2610.13505#pg1>.

Mira: So instead of just using a rate, you use this weighted pseudo-rate that incorporates both how long you stay and how likely you are to leave for a specific neighbor <ref:2610.13505#pg2>.

Lev: That sounds like it accounts for the memory aspect more thoroughly than just using the average sojourn time alone. It’s incorporating the exit probability, which is a crucial piece of information that I don't think standard Markov models capture fully <ref:2610.13505#pg2>.

Kai: Exactly. And they also show this generalization applies to the long-time scaling of hitting-time survival probabilities in those infinite-mean sojourn times <ref:2610.13505#pg1>.

Mira: That means they can predict how fast the distribution of a hitting time shrinks over very long intervals, even when the waiting times are heavy-tailed <ref:2610.13505#pg3>.

Lev: For real hardware, predicting those long-time scaling behaviors is important because it tells you if your simulation needs to run forever or if it can settle down into a predictable regime.

Kai: Plus, they extend the combinatorial formulas for hitting-time moments to the semi-Markov setting <ref:2610.13505#pg3>.

Mira: So they're providing tools not just for the mean, but for calculating higher order moments of hitting times if you have those finite moments available <ref:2610.13505#pg3>.

Lev: Calculating higher moments means we can get more detailed information about the fluctuations around the average hitting time, which is useful for error analysis in error correction protocols.

Conclusion: Kai: So to wrap up this paper on "Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking," they’ve shown that we can use spanning trees and forests to get explicit combinatorial sums for these distributions <ref:2610.13505#pg1>.

Mira: And they’ve generalized the Markov Chain Tree Theorem, giving us asymptotic results by using those pseudo-rates derived from the inverse mean sojourn time weighted by exit probability through a channel <ref:2610.13505#pg2>.

Lev: I think for me, the most tangible improvement is seeing how this framework extends to higher moments of hitting times, which we can calculate if the underlying sojourn times have finite moments up to order n <ref:2610.13505#pg3>.

Kai: And they also confirmed that for finite-mean networks, the mean hitting time formula matches the Markov network with those pseudo-rates, and that's a nice consistency check <ref:2610.13505#pg3>.

Mira: The implication is that we have a solid way to analyze these complex systems by translating them into graph theory for calculating stationary occupation probabilities and hitting times <ref:2610.13505#pg1>.

Lev: So, when we look at the weak ergodicity breaking part, they show it occurs generically for time-additive state observables in heavy-tailed semi-Markov networks <ref:2610.13505#pg4>.

Kai: That means even if the system looks ergodic at first glance, if you have a nonconstant observable on the limiting distribution, weak ergodicity breaking happens generically in those heavy-tailed cases <ref:2610.13505#pg4>.

Mira: It’s a powerful way to detect when things aren't behaving like standard Markov chains, which is something we need to watch for when modeling things like aging or complex noise in our quantum systems <ref:2610.13505#pg4>.

Lev: So the bottom line is that this paper gives us a structured way to look at these memory-dependent systems, whether it’s for finite mean or infinite mean sojourn times, and it shows how to get better estimates for hitting times and moments in those complex scenarios <ref:2610.13505#pg3>.

Kai: It’s a lot of combinatorial machinery, but if you can map your system onto this graph structure, you get explicit results for occupation probabilities and hitting time distributions <ref:2610.13505#pg1>.

Institute for Theoretical Physics, Heidelberg University · BioQuant-Center for Quantitative Biology, Heidelberg University

cond-mat.stat-mech, math.PR

Submitted: 2026-10-09

Updated: 2026-11-05

Comments: 47 pages, 4 figures

Code: https://github.com/JVoits/Illustration-two-state-semi-Markov-network

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 85/100

The gist: Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times…

Key concepts

Semi-Markov Networks
These are mathematical models describing stochastic transitions between states where the time spent in a state (dwell time) is not exponentially distributed. They are used to describe systems with non-constant transition rates, common in fields like biophysics or finance.
Laplace Transform and Combinatorial Representation
The framework uses the Laplace transform of occupation probabilities and hitting times. The key finding is that these complex distributions can be represented as sums over weighted spanning trees and forests of a modified graph, offering an explicit combinatorial structure for analysis.
Weak Ergodicity Breaking
This phenomenon occurs in heavy-tailed semi-Markov networks where the system's long-term behavior becomes sensitive to the initial state. It is detected when the variance of a time-additive observable shows specific scaling related to whether different states have different limiting probabilities.
Pseudo-rates ($ ilde{ ho}_{ij}$)
For finite mean sojourn times, the standard transition rates are replaced by 'pseudo-rates' calculated as the probability of exiting state i divided by its average sojourn time. These pseudo-rates allow the graph theory to yield results identical to those found in simpler Markov networks.

Terminology

Summary

Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times, with applications ranging from biophysics and neuroscience to epidemiology and finance. p. 0

Where the paper says it

uni-heidelberg. de Abstract Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times, with applications ranging from biophysics and neuroscience to epidemiology and finance.

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. p. 0
Where the paper says it

de Abstract Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times, with applications ranging from biophysics and neuroscience to epidemiology and finance. Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph.

These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times. p. 0
Where the paper says it

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting. p. 0
Where the paper says it

These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times. They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting.

In particular, the mean hitting-time formula coincides with that of a Markov network with the corresponding pseudo-rates, which also yields a short proof of the constancy of Kemeny’s constant for finite-mean semi-Markov networks. p. 0
Where the paper says it

They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting. In particular, the mean hitting-time formula coincides with that of a Markov network with the corresponding pseudo-rates, which also yields a short proof of the constancy of Kemeny’s constant for finite-mean semi-Markov networks.

Finally, we use the same framework to show that weak ergodicity breaking occurs generically for time-additive state observables that are nonconstant on the support of the limiting distribution in heavy-tailed semi-Markov networks. p. 0
Where the paper says it

In particular, the mean hitting-time formula coincides with that of a Markov network with the corresponding pseudo-rates, which also yields a short proof of the constancy of Kemeny’s constant for finite-mean semi-Markov networks. Finally, we use the same framework to show that weak ergodicity breaking occurs generically for time-additive state observables that are nonconstant on the support of the limiting distribution in heavy-tailed semi-Markov networks.

Graph-Theoretic Representation of Probabilities

The graph-theoretic framework is extended to semi-Markov networks by replacing constant jump rates with memory kernels in Laplace space, showing that Eqs. (3) and (4) retain validity for semi-Markov networks. p. 2

Where the paper says it

Replacing the constant jump rates in the Markovian case by memory kernels in Laplace space, kij 7→ K˜ ij (s), Eqs. (3) and (4) are shown to retain validity for semi-Markov networks (Theorem 8 and Proposition 13, respectively).

For finite-mean waiting times, stationary occupation probabilities have the same tree representation as in Eq. p. 2
Where the paper says it

(3) and (4) are shown to retain validity for semi-Markov networks (Theorem 8 and Proposition 13, respectively). In particular, for finite-mean waiting times, the stationary occupation probabilities have the same tree representation as in Eq.

(1), with transition rates replaced by pseudo-rates κij = pij / E[τi]. p. 2
Where the paper says it

In particular, for finite-mean waiting times, the stationary occupation probabilities have the same tree representation as in Eq. (1), with the transition rates replaced by pseudo-rates κij = pij E[τi] , where pij is the probability for a transition from i to j and E[τi ] is the mean sojourn time in state i (Theorem 10).

For infinite-mean sojourn times with power-law tails, an analogous graph-theoretic identity holds, but only the heaviest-tailed states that can serve as roots of spanning trees of the underlying graph retain positive occupation probability in the t → ∞ limit. p. 2
Where the paper says it

(1), with the transition rates replaced by pseudo-rates κij = pij E[τi] , where pij is the probability for a transition from i to j and E[τi ] is the mean sojourn time in state i (Theorem 10). We also show that, for infinite-mean sojourn times with power-law tails, an analogous graph-theoretic identity holds, but only the heaviest-tailed states that can serve as roots of spanning trees of the underlying graph retain positive occupation probability in the t → ∞-limit.

The long-time scaling of hitting-time distribution is also dominated by the heaviest tails in the presence of infinite-mean sojourn times, and in the finite-mean case, the graph-theoretic formula for the mean hitting time again coincides with the known expression for Markov networks with pseudo-rates. p. 2
Where the paper says it

We also show that, for infinite-mean sojourn times with power-law tails, an analogous graph-theoretic identity holds, but only the heaviest-tailed states that can serve as roots of spanning trees of the underlying graph retain positive occupation probability in the t → ∞-limit. The long-time scaling of the hitting-time distribution is also dominated by the heaviest tails in the presence of infinite-mean sojourn times, and in the finite-mean case, the graph-theoretic formula for the mean hitting time again coincides with the known expression for Markov networks with the pseudo-rates, while higher moments involve additional terms which vanish in the Markovian case (Theorem 15).

Stationary Solutions and Limiting Distributions

The long-time scaling of hitting-time distribution is determined by a small-s expansion of the Laplace transform, where for nonlattice transition-time distributions, the limiting state distribution is uniquely determined by the network. Theorem 10 provides a generalization of the MCTT to semi-Markov networks of this shape, stating that if a limiting state distribution π exists, it is given by a specific combinatorial sum involving pseudo-rates. p. 0

Where the paper says it

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

For finite-mean sojourn times with nonlattice transition-time distributions, the stationary distribution is guaranteed to exist and is given by Eq. p. 0
Where the paper says it

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

(93).

Hitting Times and Moments

The graph-theoretic framework allows for the generalization of hitting-time formulas to higher moments in semi-Markov networks, where the mean hitting time formula coincides with that of a Markov network with pseudo-rates. For moments up to order n, if sojourn times have finite moments up to order n, the k-th moment of the hitting time E[Tk] is given by a formula involving derivatives of the Laplace transform at s=0. p. 2

Where the paper says it

We also show that, for infinite-mean sojourn times with power-law tails, an analogous graph-theoretic identity holds, but only the heaviest-tailed states that can serve as roots of spanning trees of the underlying graph retain positive occupation probability in the t → ∞-limit. The long-time scaling of the hitting-time distribution is also dominated by the heaviest tails in the presence of infinite-mean sojourn times, and in the finite-mean case, the graph-theoretic formula for the mean hitting time again coincides with the known expression for Markov networks with the pseudo-rates, while higher moments involve additional terms which vanish in the Markovian case (Theorem 15).

The mean hitting time E[T] is identical to that for a Markov network with pseudo-rates as transition rates. p. 0
Where the paper says it

They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting. In particular, the mean hitting-time formula coincides with that of a Markov network with the corresponding pseudo-rates, which also yields a short proof of the constancy of Kemeny’s constant for finite-mean semi-Markov networks.

Weak Ergodicity Breaking

Weak ergodicity breaking occurs generically for time-additive state observables that are nonconstant on the support of the limiting distribution in heavy-tailed semi-Markov networks. The variance of a time-additive observable A(t) exhibits weak ergodicity breaking if there is at least one state n with πn > 0 and αn 0 such that gn ≠ gm. p. 3

Where the paper says it

A time-additive state observable A(t) = Z t 0 g(Xt ′ )dt ′ , (5) where Xt is the stochastic process on the semi-Markov network and g : V (G) → R is an arbitrary function assigning weights to the different states, exhibits weak ergodicity breaking if E[A(t)] t converges to the expectation value of g in the limiting state distribution for long times but A(t) t does not converge almost surely [27]. Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions.

This is shown by analyzing the long-time scaling of the second moment, which results in a limiting variance of VarA(t)t = 1 − α Xj(g j squared - Xjπ jj squared. p. 0
Where the paper says it

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

Conclusion

The graph-theoretic framework for semi-Markov networks is a promising approach to the study of these systems, as it expresses occupation probabilities or hitting-time distributions in Laplace space as combinatorial sums over spanning trees and forests. This structure facilitates the derivation of asymptotic results, such as the shape of stationary occupation probabilities and weak ergodicity breaking. p. 0

Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

References

[1] Gillespie, D.T.: A rigorous derivation of the chemical master equation. p. 3

Where the paper says it

These tools may help deepen our understanding of semi-Markov networks in the future. 2 Semi-Markov networks and generalized master equation In this section, we introduce basic concepts for the theory of semi-Markov networks.

[2] Gunawardena, J.: A linear framework for time-scale separation in nonlinear biochemical systems. p. 1

Where the paper says it

, natural for chemical reaction networks on a fundamental level [1, 2] but only retains validity for meta-stable coarse-grained states and a strong separation of timescales [3]. However, for many complex systems of interest, this assumption fails and sojourn time distributions clearly deviate from exponential laws.

[3] Prinz, J.-H., Wu, H., Sarich, M., Keller, B., Senne, M., Held, M., Chodera, J.D., Sch¨utte, C., No´e, F.: Markov models of molecular kinetics: Generation and validation.

[4] Goychuk, I., H¨anggi, P.: Ion channel gating: a first-passage time analysis of the kramers type. p. 1

Where the paper says it

However, for many complex systems of interest, this assumption fails and sojourn time distributions clearly deviate from exponential laws. Examples from biophysics include ion-channel opening [4], cell-cycle progression [5] and neural dynamics [6].

[5] Jolly, A., Fanti, A.-K., Kongsaysak-Lengyel, C., Claudino, N., Gr¨aßer, I., Becker, N.B., H¨ofer, T.: Cycleflow simultaneously quantifies cell-cycle phase lengths and quiescence in vivo. p. 1

Where the paper says it

However, for many complex systems of interest, this assumption fails and sojourn time distributions clearly deviate from exponential laws. Examples from biophysics include ion-channel opening [4], cell-cycle progression [5] and neural dynamics [6].

[6] Chen, Z., Vijayan, S., Barbieri, R., Wilson, M.A., Brown, E.N.: Discrete-and continuous-time probabilistic models and algorithms for inferring neuronal up and down states. p. 1

Where the paper says it

A classical result in the theory of finite Markov networks is the Markov Chain Tree Theorem (MCTT) [9, 10], which states that for an irreducible network, the stationary occupation probability of a state i can be expressed as πi = P T ∈T[i] w(T ) P T ∈T w(T ) , (1) where T denotes the set of spanning trees of the network interpreted as a directed graph G = (V (G), E(G)) and T[i] is the set of spanning trees with root i ∈ V (G). For continuous-time Markov networks, the weights w(T ) are defined as products over the transition rates kij on the tree: w(T ) = Y (i,j)∈E(T ) kij .

[7] Worthington, J., Feletto, E., He, E., Wade, S., Graaff, B., Nguyen, A.L.T., George, J., Canfell, K., Caruana, M.: Evaluating semi-markov processes and other epidemiological time-to-event models by computing disease sojourn density as partial differential equations. p. 3

Where the paper says it

A time-additive state observable A(t) = Z t 0 g(Xt ′ )dt ′ , (5) where Xt is the stochastic process on the semi-Markov network and g : V (G) → R is an arbitrary function assigning weights to the different states, exhibits weak ergodicity breaking if E[A(t)] t converges to the expectation value of g in the limiting state distribution for long times but A(t) t does not converge almost surely [27]. Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions.

[8] D’Amico, G., Janssen, J., Manca, R.: Homogeneous semi-markov reliability models for credit risk management. p. 1

Where the paper says it

Moreover, semi-Markov networks also provide an important modeling framework, e. , for epidemiology [7] or credit-risk [8].

[9] Anantharam, V., Tsoucas, P.: A proof of the Markov chain tree theorem. p. 0

Where the paper says it

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

[10] Pitman, J., Tang, W.: Tree formulas, mean first passage times and Kemeny’s constant of a Markov chain. p. 0

Where the paper says it

These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times. They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting.

[11] Schnakenberg, J.: Network theory of microscopic and macroscopic behavior of master equation systems. p. 3

Where the paper says it

These tools may help deepen our understanding of semi-Markov networks in the future. 2 Semi-Markov networks and generalized master equation In this section, we introduce basic concepts for the theory of semi-Markov networks.

[12] Freidlin, M.I., Wentzell, A.D.: Random perturbations. p. 1

Where the paper says it

For continuous-time Markov networks, the weights w(T ) are defined as products over the transition rates kij on the tree: w(T ) = Y (i,j)∈E(T ) kij . (2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15].

[13] Mirzaev, I., Gunawardena, J.: Laplacian dynamics on general graphs. p. 1

Where the paper says it

However, for many complex systems of interest, this assumption fails and sojourn time distributions clearly deviate from exponential laws. Examples from biophysics include ion-channel opening [4], cell-cycle progression [5] and neural dynamics [6].

[14] Owen, J.A., Horowitz, J.M.: Size limits the sensitivity of kinetic schemes.

[15] Bebon, R., Speck, T.: Mutual linearity is a generic property of steady-state Markov networks. p. 1

Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

[16] Khodabandehlou, F. p. 1

Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

, Maes, C., Netoˇcn´y, K.: Trees and Forests for Nonequilibrium Purposes: An Introduction to Graphical Representations. p. 0
Where the paper says it

de Abstract Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times, with applications ranging from biophysics and neuroscience to epidemiology and finance. Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph.

[17] Khodabandehlou, F. p. 1

Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

, Maes, I.: Drazin-inverse and heat capacity for driven random walkers on the ring. p. 0
Where the paper says it

Here, it is shown that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph. These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times.

[18] Khodabandehlou, F. p. 1

Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

, Maes, C., Maes, I., Netoˇcn´y, K.: The vanishing of excess heat for nonequilibrium processes reaching zero ambient temperature. p. 1
Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

[19] Khodabandehlou, F. p. 1

Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

, Maes, C., Netoˇcn´y, K.: On the Poisson equation for nonreversible Markov jump processes. p. 7
Where the paper says it

The occupation probabilities of semi-Markov processes obey a generalized master equation in Laplace space. The proof is standard, but the form is instructive for the graph-theoretic formulation developed below.

[20] Nam, K.-M., Gunawardena, J.: Algebraic formulas for first-passage times of Markov processes in the linear framework. p. 2

Where the paper says it

Moreover, the expressions for the stationary occupation probabilities and the mean hitting times allow for a simple proof that Kemeny’s constant remains independent of the starting state in semi-Markov networks with finite-mean sojourn times, including an explicit graph-theoretic representation [10], a result that was previously obtained by algebraic means [24]. Finally, the graph-theoretic framework for finite semi-Markov networks is applied to weak ergodicity breaking.

[21] Voits, J. p. 0

Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

B., Schwarz, U.S.: Emergence of generic first-passage-time distributions for large Markovian networks. p. 2
Where the paper says it

We also show that, for infinite-mean sojourn times with power-law tails, an analogous graph-theoretic identity holds, but only the heaviest-tailed states that can serve as roots of spanning trees of the underlying graph retain positive occupation probability in the t → ∞-limit. The long-time scaling of the hitting-time distribution is also dominated by the heaviest tails in the presence of infinite-mean sojourn times, and in the finite-mean case, the graph-theoretic formula for the mean hitting time again coincides with the known expression for Markov networks with the pseudo-rates, while higher moments involve additional terms which vanish in the Markovian case (Theorem 15).

[22] Voits, J. p. 0

Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

B., Schwarz, U.S.: Graph theoretic derivation of mutual linearity for transient probabilities and hitting time distributions in Markov networks. p. 1
Where the paper says it

Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19]. While such a graph-theoretic approach to Markov networks remained widely regarded as specific for the stationary case, recent work has extended the framework to transient probabilities and hitting-time densities [20–22].

[23] Chaiken, S. p. 9

Where the paper says it

The All-Minors Matrix-Tree Theorem allows us to express the determinants of minors of the Laplacian matrix of a weighted and directed graph in terms of sums over the weight of spanning forests. It was first proved in full generality by Chaiken [23].

: A combinatorial proof of the all minors matrix tree theorem. p. 1
Where the paper says it

While such a graph-theoretic approach to Markov networks remained widely regarded as specific for the stationary case, recent work has extended the framework to transient probabilities and hitting-time densities [20–22]. A key observation to derive this extension is that the resolvent (s1 − W) −1 of a Markov network permits an explicit combinatorial representation by identifying s1 − W as the principal minor of an augmented graph as a result of the All-Minors Matrix-Tree Theorem [23].

[24] Hunter, J.J.: Kemeny’s function for Markov chains and Markov renewal processes. p. 3

Where the paper says it

A time-additive state observable A(t) = Z t 0 g(Xt ′ )dt ′ , (5) where Xt is the stochastic process on the semi-Markov network and g : V (G) → R is an arbitrary function assigning weights to the different states, exhibits weak ergodicity breaking if E[A(t)] t converges to the expectation value of g in the limiting state distribution for long times but A(t) t does not converge almost surely [27]. Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions.

[25] Gallavotti, G.: Ergodicity, ensembles, irreversibility in Boltzmann and beyond. p. 2

Where the paper says it

The concept of ergodicity is central to the foundations of statistical mechanics and the idea can be traced back to the works of Boltzmann and others in the late nineteenth century [25]. Ergodicity theory then became a mathematical discipline in its own right with several applications in statistical physics and beyond [26].

[26] Einsiedler, M., Ward, T.: Ergodic Theory: with a View Towards Number Theory. p. 0

Where the paper says it

Finally, we use the same framework to show that weak ergodicity breaking occurs generically for time-additive state observables that are nonconstant on the support of the limiting distribution in heavy-tailed semi-Markov networks. Keywords: semi-Markov networks, graph theory, hitting times, weak ergodicity breaking 1 arXiv:2610.

[27] Bouchaud, J.-P.: Weak ergodicity breaking and aging in disordered systems. p. 0

Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

[28] Bel, G. p. 2

Where the paper says it

In comparison, the study of weak ergodicity breaking is relatively recent: in the 1990s, it was realized that semi-Markov networks with heavy-tailed waiting times can give rise to time-averaged occupation fractions which converge to the occupation probabilities on average but not almost surely [27]. This notion was investigated more thoroughly in the context of continuous-time random walks in the 2000s by Bel, Barkai, Metzler and others, who derived non-trivial limiting distributions for general time-averaged observables in the presence of heavy-tailed waiting times [28–30].

, Barkai, E. p. 2
Where the paper says it

In comparison, the study of weak ergodicity breaking is relatively recent: in the 1990s, it was realized that semi-Markov networks with heavy-tailed waiting times can give rise to time-averaged occupation fractions which converge to the occupation probabilities on average but not almost surely [27]. This notion was investigated more thoroughly in the context of continuous-time random walks in the 2000s by Bel, Barkai, Metzler and others, who derived non-trivial limiting distributions for general time-averaged observables in the presence of heavy-tailed waiting times [28–30].

p. 2
Where the paper says it

In comparison, the study of weak ergodicity breaking is relatively recent: in the 1990s, it was realized that semi-Markov networks with heavy-tailed waiting times can give rise to time-averaged occupation fractions which converge to the occupation probabilities on average but not almost surely [27]. This notion was investigated more thoroughly in the context of continuous-time random walks in the 2000s by Bel, Barkai, Metzler and others, who derived non-trivial limiting distributions for general time-averaged observables in the presence of heavy-tailed waiting times [28–30].

p. 2
Where the paper says it

In comparison, the study of weak ergodicity breaking is relatively recent: in the 1990s, it was realized that semi-Markov networks with heavy-tailed waiting times can give rise to time-averaged occupation fractions which converge to the occupation probabilities on average but not almost surely [27]. This notion was investigated more thoroughly in the context of continuous-time random walks in the 2000s by Bel, Barkai, Metzler and others, who derived non-trivial limiting distributions for general time-averaged observables in the presence of heavy-tailed waiting times [28–30].

: Weak ergodicity breaking in the continuous-time random walk. p. 3
Where the paper says it

A time-additive state observable A(t) = Z t 0 g(Xt ′ )dt ′ , (5) where Xt is the stochastic process on the semi-Markov network and g : V (G) → R is an arbitrary function assigning weights to the different states, exhibits weak ergodicity breaking if E[A(t)] t converges to the expectation value of g in the limiting state distribution for long times but A(t) t does not converge almost surely [27]. Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions.

[29] Rebenshtok, A., Barkai, E.: Distribution of time-averaged observables for weak ergodicity breaking. p. 2

Where the paper says it

In comparison, the study of weak ergodicity breaking is relatively recent: in the 1990s, it was realized that semi-Markov networks with heavy-tailed waiting times can give rise to time-averaged occupation fractions which converge to the occupation probabilities on average but not almost surely [27]. This notion was investigated more thoroughly in the context of continuous-time random walks in the 2000s by Bel, Barkai, Metzler and others, who derived non-trivial limiting distributions for general time-averaged observables in the presence of heavy-tailed waiting times [28–30].

[30] He, Y., Burov, S., Metzler, R. p. 2

Where the paper says it

In comparison, the study of weak ergodicity breaking is relatively recent: in the 1990s, it was realized that semi-Markov networks with heavy-tailed waiting times can give rise to time-averaged occupation fractions which converge to the occupation probabilities on average but not almost surely [27]. This notion was investigated more thoroughly in the context of continuous-time random walks in the 2000s by Bel, Barkai, Metzler and others, who derived non-trivial limiting distributions for general time-averaged observables in the presence of heavy-tailed waiting times [28–30].

, Barkai, E.: Random time-scale invariant diffusion and transport coefficients. p. 1
Where the paper says it

For continuous-time Markov networks, the weights w(T ) are defined as products over the transition rates kij on the tree: w(T ) = Y (i,j)∈E(T ) kij . (2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15].

[31] Norris, J.R.: Markov Chains vol. p. 0

Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

2. Cambridge university press, Cambridge (1998). p. 0
Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

[32] Doetsch, G.: Introduction to the Theory and Application of the Laplace Transformation. p. 1

Where the paper says it

1 Introduction Markov networks describe memoryless transitions between discrete states, implying exponentially distributed dwell (or sojourn) times. This description is, e.

[33] Athreya, K.B., McDonald, D., Ney, P.: Limit theorems for semi-Markov processes and renewal theory for Markov chains. p. 3

Where the paper says it

Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions. The memoryless property provides a rich mathematical structure for studying Markov networks in terms of semigroups, spectral theory, and martingale methods [31], but this structure does not directly carry over to the semi-Markov case.

[34] Athreya, K., Ney, P.: Limit theorems for semi-Markov processes. p. 3

Where the paper says it

A time-additive state observable A(t) = Z t 0 g(Xt ′ )dt ′ , (5) where Xt is the stochastic process on the semi-Markov network and g : V (G) → R is an arbitrary function assigning weights to the different states, exhibits weak ergodicity breaking if E[A(t)] t converges to the expectation value of g in the limiting state distribution for long times but A(t) t does not converge almost surely [27]. Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions.

[35] Hill, T.L.: Studies in irreversible thermodynamics iv. diagrammatic representation of steady state fluxes for unimolecular systems. p. 1

Where the paper says it

(2) This identity has proven useful for deriving structural statements about the stationary state of finite Markov networks, for example, in the theory of random perturbations and in the mathematical description of biochemical networks [11–15]. Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19].

[36] Chebotarev, P.: A graph theoretic interpretation of the mean first passage times. p. 1

Where the paper says it

Related expressions also exist for stationary currents and mean hitting times and have been developed into a thermodynamic calculus for nonequilibrium steady states by Khodabandehlou and collaborators [16–19]. While such a graph-theoretic approach to Markov networks remained widely regarded as specific for the stationary case, recent work has extended the framework to transient probabilities and hitting-time densities [20–22].

[37] Nam, K.-M., Gunawardena, J.: The linear framework II: using graph theory to analyse the transient regime of Markov processes. p. 0

Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

[38] Feller, W.: An Introduction to Probability Theory and Its Applications vol. p. 2

Where the paper says it

The concept of ergodicity is central to the foundations of statistical mechanics and the idea can be traced back to the works of Boltzmann and others in the late nineteenth century [25]. Ergodicity theory then became a mathematical discipline in its own right with several applications in statistical physics and beyond [26].

2. John Wiley & Sons, New York (1991)

[39] Seifert, U.: Stochastic Thermodynamics. p. 0

Where the paper says it

uni-heidelberg. de Abstract Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times, with applications ranging from biophysics and neuroscience to epidemiology and finance.

Cambridge University Press Cambridge, Cambridge (2025). p. 0
Where the paper says it

Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking Julian B. Voits Institute for Theoretical Physics, Heidelberg University, Germany.

[40] Akimoto, T.: Statistics of the number of renewals, occupation times, and correlation in ordinary, equilibrium, and aging alternating renewal processes. p. 3

Where the paper says it

A time-additive state observable A(t) = Z t 0 g(Xt ′ )dt ′ , (5) where Xt is the stochastic process on the semi-Markov network and g : V (G) → R is an arbitrary function assigning weights to the different states, exhibits weak ergodicity breaking if E[A(t)] t converges to the expectation value of g in the limiting state distribution for long times but A(t) t does not converge almost surely [27]. Weak ergodicity breaking is shown to be a general property of finite semi-Markov networks under a mild small-s scaling condition on the memory kernels if g is not constant on the support of the limiting state distribution (Theorem 24), recovering the known relation for random-walk-like processes, and extending it to finite directed semi-Markov networks with heterogeneous transition-time distributions.

Physical Review E 108(5), 054113 (2023).

Appendix

Definition A.1 Let B([0,∞)) be the Borel-σ-algebra on [0, ∞) be the Laplace–Stieltjes transform of Q is defined as Q˜(s) = Z [0,∞) e−stQ(dt), for s ∈ (0,∞). p. 4

Where the paper says it

(10) If Qi has a density ψi = P j:(i,j)∈E(G) ψij , this reduces to ϕi(t) = Z ∞ t ψi(t ′ )dt ′ . (11) We also introduce the memory kernels Kij , defined via the following relation in Laplace space: K˜ ij (s) := Q˜ ij (s) ϕ˜ i(s) , (12) where Q˜ ij (s) := Z [0,∞) e −stQij (dt) (13) denotes the Laplace-Stieltjes transform of Qij .

Lemma A.2 Let Q be a probability measure on [0,∞) and let Q˜(s) be its Laplace–Stieltjes transform. p. 4
Where the paper says it

More details on the Laplace-Stieltjes transform are given in the Appendix. The Laplace transform of the survival probability is given by ϕ˜ i(s) = Z ∞ 0 e −stQi((t, ∞))dt (15) = Z ∞ 0 e −st Z [0,∞) 1{t ′>t}Qi(dt ′ )dt (16) 5

Then the moments of τ ∼ Q are given by E[τn] = (−1)n lims→0 d n ds n Q˜(s), for n ∈ N0. p. 0
Where the paper says it

These representations yield asymptotic results, including a generalization of the Markov Chain Tree Theorem to semi-Markov networks, in which the rate constants replaced by pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel, as well as the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times. They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting.

Theorem A.4 (Karamata)

Let f: [0,∞) → [0,∞) be a locally integrable function and ultimately monotone. Let ˜f(s) be its Laplace transform. p. 1

Where the paper says it

A key observation to derive this extension is that the resolvent (s1 − W) −1 of a Markov network permits an explicit combinatorial representation by identifying s1 − W as the principal minor of an augmented graph as a result of the All-Minors Matrix-Tree Theorem [23]. This allows for an explicit expression of the Laplace transform of the occupation probability p˜i(s) of a state i ∈ V (G) in terms of spanning trees and forests of the augmented graph G∗ = V (G) ∪ {∗}, E(G) ∪ {(n, ∗) | n ∈ V (G)} , similarly to Eq.

p. 1
Where the paper says it

A key observation to derive this extension is that the resolvent (s1 − W) −1 of a Markov network permits an explicit combinatorial representation by identifying s1 − W as the principal minor of an augmented graph as a result of the All-Minors Matrix-Tree Theorem [23]. This allows for an explicit expression of the Laplace transform of the occupation probability p˜i(s) of a state i ∈ V (G) in terms of spanning trees and forests of the augmented graph G∗ = V (G) ∪ {∗}, E(G) ∪ {(n, ∗) | n ∈ V (G)} , similarly to Eq.

Then the following holds: f(t) ∼ c t(α-1)/Γ(α) for t → ∞. p. 5
Where the paper says it

, ϕ˜N (s) and W˜ (s) and Q˜(s) as defined above. Then the following identity holds: (s1 − W˜ (s))diagϕ˜(s) = 1 − Q˜T (s), (24) where 1 denotes the identity matrix in N-dimensions.

p. 5
Where the paper says it

, ϕ˜N (s) and W˜ (s) and Q˜(s) as defined above. Then the following identity holds: (s1 − W˜ (s))diagϕ˜(s) = 1 − Q˜T (s), (24) where 1 denotes the identity matrix in N-dimensions.

Theorem A.6 (Karamata)

Let f: [0,∞) → [0,∞) be a locally integrable function and ultimately monotone. Let ˜f(s) be its Laplace transform. Then the following holds: f(t) ∼ c t(α-1)/Γ(α) for t → ∞.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Graph theoretic framework for semi-Markov networks: The system can explicitly compute Laplace-transformed occupation probabilities and hitting time distributions as sums over weighted spanning trees and forests of an augmented graph.

  2. Generalization of Markov Chain Tree Theorem: The system can derive asymptotic results for semi-Markov networks by replacing constant jump rates with pseudo-rates given by the inverse mean sojourn time weighted by the exit probability through this channel.

  3. Hitting time moment calculation: The system can compute higher moments of hitting times in semi-Markov networks, which involves additional terms that vanish in Markovian cases, extending combinatorial formulas to this setting.

  4. Stationary distribution determination: For semi-Markov networks with finite mean sojourn times and nonlattice distributions, the system can uniquely determine the limiting state distribution by calculating its Laplace transform limit as s approaches zero.

  5. Weak ergodicity breaking detection: The system can identify weak ergodicity breaking in finite semi-Markov networks by checking if there is at least one state n with pi n > 0 and alpha n < 1 such that gn is not equal to gm.

Abstract

We show that finite semi-Markov networks admit explicit combinatorial representations of their Laplace-transformed occupation probabilities and hitting-time distributions as sums over weighted spanning trees and forests of an augmented graph, generalizing the previously developed graph-theoretic framework for Markov networks. These representations yield asymptotic results, including the long-time scaling of hitting-time survival probabilities in the presence of infinite-mean sojourn times. They also extend recently derived combinatorial formulas for hitting-time moments to the semi-Markov setting, where non-Markovian corrections appear in higher moments. For finite-mean sojourn times, the framework recovers the known stationary distribution through a generalization of the Markov Chain Tree Theorem, with transition rates replaced by pseudo-rates. In particular, the mean hitting-time formula coincides with that of a Markov network with the corresponding pseudo-rates, which also yields a short graph-theoretic proof of the previously established constancy of Kemeny's constant for finite-mean semi-Markov networks. Finally, we use the same framework to extend established results on weak ergodicity breaking for time-additive state observables that are nonconstant on the support of the limiting distribution in heavy-tailed semi-Markov networks, allowing for generally heterogeneous, transition-dependent waiting-time distributions.

Sources

Related papers