Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking
summary
The gist
Semi-Markov networks provide a natural framework for describing stochastic transitions between coarse-grained states with non-exponential dwell times…
In short
The paper develops a graph-theoretic framework for semi-Markov networks to compute occupation probabilities and hitting times using sums over spanning trees and forests of an augmented graph. This method generalizes Markov Chain Tree Theorems, providing asymptotic results for hitting times and stationary distributions, while also detecting weak ergodicity breaking in heavy-tailed systems.
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 used across episodes
This episode discusses
- Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking · Paper Radio
- A graph theoretic interpretation of the mean first passage times
The paper
Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking · Read on arXiv
Institute for Theoretical Physics, Heidelberg University · BioQuant-Center for Quantitative Biology, Heidelberg University
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.
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>.
More episodes
- 2610.32678-Probing the limits of materials design via a comprehensive crystal database of 14.6 million structures with 140 properties
- 2610.33595-Native-oxide-driven layer asymmetry, two-step switching and exchange bias in Co/Ir/Co trilayers
- 2503.19572-Spin models from nonlinear cellular automata
- 2606.23350-Irreversibility Enhances Quantum-Enhanced Markov-Chain Monte Carlo
- 2608.02744-Two-Parameter Ansatz for the Violation of Eigenstate Thermalization
- 2210.00806-Low- and high-energy localization landscapes for tight-binding Hamiltonians in two-dimensional lattices
- 2409.09625-Selective switch for band-edge alignments in pentagonal CdSeTe monolayer: Atom-valley locking
- 2606.20168-Norms, overlaps and Yangian descendants for the Haldane-Shastry spin chain
- 2512.19503-Strain-induced splitting of the CCDW-NCCDW phase transition in 1T-TaS 2
- 2307.12638-Strong localization of microwaves beyond two dimensions in aperiodic Vogel spirals