Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking
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 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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). (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. 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). (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. 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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). 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
References
[1] Gillespie, D.T.: A rigorous derivation of the chemical master equation. p. 3 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.Where the paper says it
[2] Gunawardena, J.: A linear framework for time-scale separation in nonlinear biochemical systems. p. 1 , 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.Where the paper says it
[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 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].Where the paper says it
[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 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].Where the paper says it
[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 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 .Where the paper says it
[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 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.Where the paper says it
[8] D’Amico, G., Janssen, J., Manca, R.: Homogeneous semi-markov reliability models for credit risk management. p. 1 Moreover, semi-Markov networks also provide an important modeling framework, e. ,
for epidemiology [7] or credit-risk [8].Where the paper says it
[9] Anantharam, V., Tsoucas, P.: A proof of the Markov chain tree theorem. p. 0 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.Where the paper says it
[10] Pitman, J., Tang, W.: Tree formulas, mean first passage times and Kemeny’s constant of a Markov chain. p. 0 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.Where the paper says it
[11] Schnakenberg, J.: Network theory of microscopic and macroscopic behavior of master equation systems. p. 3 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.Where the paper says it
[12] Freidlin, M.I., Wentzell, A.D.: Random perturbations. p. 1 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].Where the paper says it
[13] Mirzaev, I., Gunawardena, J.: Laplacian dynamics on general graphs. p. 1 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].Where the paper says it
[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 (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].Where the paper says it
[16] Khodabandehlou, F. p. 1 (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]. 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.Where the paper says it
Where the paper says it
[17] Khodabandehlou, F. p. 1 (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]. 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.Where the paper says it
Where the paper says it
[18] Khodabandehlou, F. p. 1 (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]. (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].Where the paper says it
Where the paper says it
[19] Khodabandehlou, F. p. 1 (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]. 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.Where the paper says it
Where the paper says it
[20] Nam, K.-M., Gunawardena, J.: Algebraic formulas for first-passage times of Markov processes in the linear framework. p. 2 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.Where the paper says it
[21] Voits, J. p. 0 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. 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).Where the paper says it
Where the paper says it
[22] Voits, J. p. 0 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. 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].Where the paper says it
Where the paper says it
[23] Chaiken, S. p. 9 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]. 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].Where the paper says it
Where the paper says it
[24] Hunter, J.J.: Kemeny’s function for Markov chains and Markov renewal processes. p. 3 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.Where the paper says it
[25] Gallavotti, G.: Ergodicity, ensembles, irreversibility in Boltzmann and beyond. p. 2 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].Where the paper says it
[26] Einsiedler, M., Ward, T.: Ergodic Theory: with a View Towards Number Theory. p. 0 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.Where the paper says it
[27] Bouchaud, J.-P.: Weak ergodicity breaking and aging in disordered systems. p. 0 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.Where the paper says it
[28] Bel, G. p. 2 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]. 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]. 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]. 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]. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[29] Rebenshtok, A., Barkai, E.: Distribution of time-averaged observables for weak ergodicity breaking. p. 2 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].Where the paper says it
[30] He, Y., Burov, S., Metzler, R. p. 2 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]. 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].Where the paper says it
Where the paper says it
[31] Norris, J.R.: Markov Chains vol. p. 0 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. 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.Where the paper says it
Where the paper says it
[32] Doetsch, G.: Introduction to the Theory and Application of the Laplace Transformation. p. 1 1 Introduction
Markov networks describe memoryless transitions between discrete states, implying
exponentially distributed dwell (or sojourn) times. This description is, e.Where the paper says it
[33] Athreya, K.B., McDonald, D., Ney, P.: Limit theorems for semi-Markov processes and renewal theory for Markov chains. p. 3 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.Where the paper says it
[34] Athreya, K., Ney, P.: Limit theorems for semi-Markov processes. p. 3 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.Where the paper says it
[35] Hill, T.L.: Studies in irreversible thermodynamics iv. diagrammatic representation of steady state fluxes for unimolecular systems. p. 1 (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].Where the paper says it
[36] Chebotarev, P.: A graph theoretic interpretation of the mean first passage times. p. 1 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].Where the paper says it
[37] Nam, K.-M., Gunawardena, J.: The linear framework II: using graph theory to analyse the transient regime of Markov processes. p. 0 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.Where the paper says it
[38] Feller, W.: An Introduction to Probability Theory and Its Applications vol. p. 2 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].Where the paper says it
[39] Seifert, U.: Stochastic Thermodynamics. p. 0 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. 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.Where the paper says it
Where the paper says it
[40] Akimoto, T.: Statistics of the number of renewals, occupation times, and correlation in ordinary, equilibrium, and aging alternating renewal processes. p. 3 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.Where the paper says it
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 (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 . 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 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. , ϕ˜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. , ϕ˜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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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
- Emergent long-tail dynamics in driven magnets with dynamical frustration
- Statistical Mechanics of Dynamical System Identification
- Second law of thermodynamics in closed quantum many-body systems
- Chemical potentials from structure factors: II. Charged multi-component mixtures
- Genuine quantum scars in Floquet chaotic many-body systems
- Stochastic Thermodynamics for Autoregressive Generative Models: A Non-Markovian Perspective