betaFeedback

WorksMathematics

What the occupation law of a finite Markov chain determines: time reversal and principal minors

Abstract

What does the occupation law of a finite Markov chain determine about its generator QQ? From the stationary start, the law of the occupation times at one time determines QQ exactly up to time reversal and reversals of memoryless blocks, the sets of states that are all left at one rate with one landing law and are entered in proportion to the stationary law. These reversals commute and give exactly 2k2^k generators, with kk read off a tree of memoryless blocks. This leaves only time reversal when QQ has no rank-one cut, when there are at most 4 states, and generically. The law at one time determines the law at every time, and a generic start determines QQ. A renewal block is a set of states that is left at the same rates from each of its states, is entered with one law, and is charged by the start in proportion to that law. From every start the law determines QQ exactly up to lumped reversals, which lump disjoint renewal blocks to single states and reverse a memoryless block of the lumped chain. We also find every start that hides time reversal. At the scale of large deviations, the functional of Donsker and Varadhan determines exactly the principal minors of −Q-Q.

Mathematics Subject Classification (2020): 60J27, 60F10, 62M05, 15A15, 15A29.

Introduction

Suppose that we record how long a continuous-time Markov chain on [d]={1,…,d}[d] = \{1,\ldots,d\} spends in each state, and not the order of its visits or its jumps. What does this record determine about the generator QQ? Let O(T)O(T) be the vector of the times that the chain spends in each state up to time TT. We answer the question for the law of O(T)O(T), and for its logarithmic scale, the functional JVJ_V of Donsker and Varadhan [11], which is the rate function of O(T)/TO(T)/T.

A stationary chain and its time reversal spend the same time in each state. Hence, from the stationary start, the law of O(T)O(T) never separates QQ from its time reversal. We show that for generic QQ it separates QQ from every other generator. For an elliptic diffusion the analogous question has a classical answer at the scale of large deviations. Donsker and Varadhan [12] showed that the principal eigenvalues of the generator under all potentials, on all subdomains, determine it up to a ground-state transform and time reversal. In a companion paper on diffusions [27] we show that on a closed manifold of dimension at least 2 a single central limit covariance of the occupation integrals already leaves only time reversal. For finite chains, Kim and Landim [22 Section 5] recover a reversible QQ from JVJ_V (their Corollary 5.3) and show with the uniform 3-cycle that JVJ_V does not determine a nonreversible one (their Example 5.4). For a finite chain less is determined than for a diffusion. The functional JVJ_V determines only the principal minors of −Q-Q, and the stationary law of O(T)O(T) can fail to separate QQ from generators other than its time reversal.

ObservationWhat it determinesSource
the pathQQ
the law of O(T)O(T) at one TT, a start μ\mu without renewal blocksQQ if μ≠π\mu\ne\pi, and QQ up to time reversal if μ=π\mu= \piThm. B
the law of O(T)O(T) at one TT, stationary startQQ up to (Z/2)k(\mathbb{Z}/2)^k, generated by time reversal and commuting reversals of memoryless blocksThm. A
the law of O(T)O(T) at one TT, any start μ\muQQ up to lumped reversalsThm. B
the functional JVJ_Vthe principal minors of −Q-QProp. 1.1

Table 1. What the observations of a finite irreducible chain determine about its generator.

The stationary fiber

Write π\pi for the stationary law of an irreducible QQ and Q∗=Dπ−1QTDπQ^* = D_\pi^{-1}Q^\mathsf{T}D_\pi for its time reversal, with DπD_\pi the diagonal matrix of π\pi. Let BB be a set of states with 2≤∣B∣≤d−12 \le|B| \le d-1. We call BB a memoryless block of QQ if 2 conditions hold. First, all states of BB jump to each state outside BB at the same rate. Second, every jump into BB from outside lands with the law πB/π(B)\pi_B/\pi(B). For such a BB, the reversal of QQ inside BB replaces the block QBQ_B by DπB−1QBTDπBD_{\pi_B}^{-1}Q_B^\mathsf{T}D_{\pi_B} and keeps the other entries of QQ. We call a partition [d]=X∪Y[d] = X \cup Y with ∣X∣,∣Y∣≥2|X|, |Y| \ge2 a cut of QQ if the blocks Q[X,Y]Q[X,Y] and Q[Y,X]Q[Y,X] have rank at most 1.

Two sets overlap if they meet and neither contains the other. The memoryless blocks that overlap no other memoryless block, together with [d][d], form a tree under inclusion. We call a node NN of this tree active if πiqij≠πjqji\pi_iq_{ij} \ne\pi_jq_{ji} for some states ii and jj of NN that lie together in no smaller node. Let kk be the number of active nodes.

Theorem A (the stationary fiber). Let QQ and Q′Q' be irreducible generators on [d][d], each started from its stationary law.

(a) O(T)O(T) has the same law under QQ and Q′Q', for one T>0T > 0 or equivalently for every TT, if and only if Q′Q' is reached from QQ or from Q∗Q^* by reversals of memoryless blocks, each a memoryless block of the current generator.

(b) There are exactly 2k2^k such Q′Q'. The reversals commute, and (Z/2)k(\mathbb{Z}/2)^k acts on these generators simply transitively.

(c) They are only QQ and Q∗Q^* when d≤4d \le4, when QQ has no cut, and for all positive rates outside a finite union of proper linear subspaces. For d=5d = 5 there are others.

This is Theorems 4.12 and 4.17, Corollary 4.19 and Example 4.11. When QQ has no memoryless block, as for generic rates, and when d≤3d \le3, the proof needs only the theorems of Loewy and of Hartfiel and Loewy (Remark 4.14). Inside a memoryless block each sojourn starts in the stationary law of the block and leaves it in a way that does not depend on the state, so it can be reversed. For the converse we border QQ by π\pi. Every cut of the bordered matrix is a memoryless block (Lemma 4.13), and the theorem of Chatterjee, Ghosh, Gurjar and Raj [8] on matrices with equal principal minors does the rest.

One time and every start

A renewal block of a start μ\mu is a set BB of at least 2 and at most d−1d-1 states that every state of BB leaves at the same rates, that every jump into BB enters with one law ρ\rho, and that μ\mu charges in proportion to ρ\rho, possibly not at all. A lumped reversal lumps disjoint renewal blocks to single states and then reverses a memoryless block of the lumped chain that the lumped start charges in proportion to its stationary law, or reverses the whole lumped chain when the lumped start is stationary.

Theorem B (one time and every start). Let QQ be an irreducible generator on [d][d] and Q′Q' a generator.

(i) If O(T0)O(T_0) has the same law under QQ from a start μ\mu and under Q′Q' from a start μ′\mu', for one T0>0T_0>0, then it has the same law for every TT, μ′=μ\mu'=\mu, and −Q′-Q' has the principal minors of −Q-Q.

(ii) If μ\mu has no renewal block, then the law of O(T0)O(T_0) at one T0>0T_0>0 from μ\mu determines QQ, or QQ up to time reversal when μ=π\mu=\pi. This holds for every start outside a finite union of proper linear subspaces, which depend on QQ, and for some starts with zeros.

(iii) For every start μ\mu, the law of O(T0)O(T_0) at one T0>0T_0>0 from μ\mu determines QQ exactly up to finitely many lumped reversals.

This is Theorems 4.2, 4.5 and 4.26. The renewal blocks are the cuts of QQ bordered by the column 1 and the row μ\mu. Such a set can hide something, since lumping it can produce a memoryless block (Example 4.27). For the converse in (iii) we show that the minimal renewal blocks, and those with 2 states, are renewal blocks of every generator with the same law, and we lump one of them and induct on dd. With μ=π\mu=\pi the renewal blocks are the memoryless blocks, and a lumped reversal is a composition of reversals of memoryless blocks and of Q↦Q∗Q\mapsto Q^*: it reverses the set of states that the reversed lumped block stands for, or the whole chain, and then reverses again each lumped renewal block inside it. So Theorem A(a) is the case μ=π\mu=\pi of (iii). We keep its own proof, which is short, rests on the stated theorem of Chatterjee, Ghosh, Gurjar and Raj [8 Theorem 1.1], and gives the count 2k2^k. The proof of (iii) rests on more: two lemmas from inside the proof of that theorem [8 Lemmas 3.5 and 3.6], which are in the arXiv version and in the STOC 2025 version of their paper, and which we transfer to matrices with zero entries (Lemma 4.31). Theorems A and B hold for the counts of the discrete chain I+hQI+hQ for all NN at one fixed hh.

Starts that hide time reversal

The stationary start never separates QQ from Q∗Q^*, and a generic start does. Write a start as μ=π∘f\mu=\pi\circ f. A circulation component of QQ is a connected component of the graph of the edges {i,j}\{i,j\} with πiqij≠πjqji\pi_iq_{ij}\ne\pi_jq_{ji}, and a closed block is a memoryless block with no net flux across its boundary.

Theorem C (which starts hide time reversal). Let QQ be irreducible. A start μ=π∘f\mu=\pi\circ f gives the same law of O(T)O(T) under QQ and under Q∗Q^* if and only if ff is constant on the smallest closed block containing each circulation component, and equivalently if and only if Eπ[f(ξT)−f(ξ0)∣O(T)]=0\mathbb{E}_{\pi}[f(\xi_T)-f(\xi_0)\mid O(T)]=0 for every TT. If some circulation component lies in no closed block, only the stationary start does.

This is Theorem 4.22. The difference of the 2 transforms is a bilinear form in the flux matrix DπQ−QTDπD_\pi Q-Q^\mathsf{T}D_\pi (Lemma 4.20), and an induction along the construction of the closed block shows that it sees every state the construction adds.

The functional of Donsker and Varadhan

At the logarithmic scale the answer is a statement about principal minors.

Proposition 1.1 (what the functional determines). Let QQ and Q′Q' be irreducible generators on [d][d]. Then JV=JV′J_V=J'_V on the simplex if and only if −Q-Q and −Q′-Q' have the same principal minors. In that case the exit rate λF(v)\lambda_F(v) of every face FF under every field vv, and the functional JFJ_F of the chain killed on leaving FF, are the same for QQ and Q′Q'.

This is Proposition 3.4, by the variational formula of Donsker and Varadhan [11] for the killed chains and an induction over the faces, which is a case of a theorem of Delmas, Dronnier and Zitt [10 Theorem 2.1]. The generators with the principal minors of −Q-Q are QQ and Q∗Q^* when QQ has no cut and when d≤3d \le3 (Corollary 3.7), and in general they are described by the theorem of Chatterjee, Ghosh, Gurjar and Raj [8]. By Theorem B(i) the law of O(T)O(T) at one time, from any start, determines the principal minors, so it determines JVJ_V.

Related work

The exact law of the occupation times of a finite chain goes back to Good [18], and the joint rate of the empirical measure and the flow is that of Bertini, Faggionato and Gabrielli [3, 4]. The matrix theory behind the fiber is credited in § 3.3. Cohen [9] and Friedland [16] study the convexity of v↦ϱ(A+diag⁡v)v \mapsto\varrho(A+\operatorname{diag}v). Brydges, van der Hofstad and König [6 Theorem 2.1] write the density of the local times at a fixed time through cofactors of the generator. In [26] we study the occupation counts of a chain that rarely switches states, which is a forward problem. We compute the local laws of the counts, and we find their support and their boundary layer.

Identifiability from coarse observations has a long history for aggregated Markov chains, where one observes which class of states the chain occupies at each time, as in models of ion channels. Fredkin and Rice [15], Rydén [28], Larget [23] and Bruno, Yang and Pearson [5] study when 2 generators give the same law of the lumped path. Xiang, Zhou, Deng and Yang [29] identify the generator of a stationary chain from hitting-time distributions observed at some states. An aggregated chain is seen in the order of its visits, with the states of each class merged. In our problem every state is seen, but only through the total time spent in it. Hence neither observation determines the other.

§ 3 proves Proposition 1.1, § 4 proves Theorems A to C, and § 5 lists the computations and the open questions.

Setting

The chain. Fix d≥2d \ge2 and a generator QQ on [d]={1,…,d}[d]=\{1,\ldots,d\}. Its rates are qij≥0q_{ij} \ge0 for i≠ji \ne j, the exit rates are qi=∑j≠iqijq_i=\sum_{j\ne i}q_{ij}, Qii=−qiQ_{ii}=-q_i, and qmax⁡=max⁡iqiq_{\max}=\max_i q_i. A start is a probability law μ\mu on [d][d], and V=[d]V=[d] is the set of all states. If QQ is irreducible, π\pi is its stationary law, DπD_\pi the diagonal matrix of π\pi, and Q∗=Dπ−1QTDπQ^*=D_\pi^{-1}Q^\mathsf{T}D_\pi its time reversal.

References

  1. [1]A. Al Ahmadieh, The fiber of the principal minor map, preprint, arXiv:2309.00806v2, 2023. https://arxiv.org/abs/2309.00806v2.
  2. [2]A. Berman, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM, Philadelphia, 1994. https://doi.org/10.1137/1.9781611971262.
  3. [3]L. Bertini, A. Faggionato, D. Gabrielli, From level 2.5 to level 2 large deviations for continuous time Markov chains, Markov Process. Related Fields 20 (2014) 545–562. https://arxiv.org/abs/1212.6908.
  4. [4]L. Bertini, A. Faggionato, D. Gabrielli, Large deviations of the empirical flow for continuous time Markov chains, Ann. Inst. Henri Poincaré Probab. Stat. 51 (2015) 867–900. https://doi.org/10.1214/14-AIHP601.
  5. [5]W. J. Bruno, J. Yang, J. E. Pearson, Using independent open-to-closed transitions to simplify aggregated Markov models of ion channel gating kinetics, Proc. Natl. Acad. Sci. USA 102 (2005) 6326–6331. https://doi.org/10.1073/pnas.0409110102.
  6. [6]D. Brydges, R. van der Hofstad, W. König, Joint density for the local times of continuous-time Markov chains, Ann. Probab. 35 (2007) 1307–1332. https://doi.org/10.1214/009171906000001024.
  7. [7]P. Buchholz, Exact and ordinary lumpability in finite Markov chains, J. Appl. Probab. 31 (1994) 59–75. https://doi.org/10.2307/3215235.
  8. [8]A. Chatterjee, S. Ghosh, R. Gurjar, R. Raj, Characterizing and testing principal minor equivalence of matrices, in: Proc. 57th Annual ACM Symposium on Theory of Computing (STOC 2025), ACM, New York, 2025, pp. 1067–1078. https://doi.org/10.1145/3717823.3718464. Full version: preprint, arXiv:2410.01961v1, 2024, https://arxiv.org/abs/2410.01961v1. Results, including Lemmas 3.5 and 3.6, are cited with the numbering of the arXiv version.
  9. [9]J. E. Cohen, Convexity of the dominant eigenvalue of an essentially nonnegative matrix, Proc. Amer. Math. Soc. 81 (1981) 657–658. https://doi.org/10.1090/S0002-9939-1981-0601750-2.
  10. [10]J.-F. Delmas, D. Dronnier, P.-A. Zitt, Transformations preserving the effective spectral radius of a matrix, Linear Multilinear Algebra 73 (2025) 2354–2360. https://doi.org/10.1080/03081087.2024.2447523.
  11. [11]M. D. Donsker, S. R. S. Varadhan, On a variational formula for the principal eigenvalue for operators with maximum principle, Proc. Natl. Acad. Sci. USA 72 (1975) 780–783. https://doi.org/10.1073/pnas.72.3.780.
  12. [12]M. D. Donsker, S. R. S. Varadhan, On the principal eigenvalue of second-order elliptic differential operators, Comm. Pure Appl. Math. 29 (1976) 595–621. https://doi.org/10.1002/cpa.3160290606.
  13. [13]A. Ehrenfeucht, G. Rozenberg, Theory of 2-structures, part I: clans, basic subclasses, and morphisms, Theoret. Comput. Sci. 70 (1990) 277–303. https://doi.org/10.1016/0304-3975(90)90129-6.
  14. [14]A. Ehrenfeucht, G. Rozenberg, Theory of 2-structures, part II: representation through labeled tree families, Theoret. Comput. Sci. 70 (1990) 305–342. https://doi.org/10.1016/0304-3975(90)90130-A.
  15. [15]D. R. Fredkin, J. A. Rice, On aggregated Markov processes, J. Appl. Probab. 23 (1986) 208–214. https://doi.org/10.2307/3214130.
  16. [16]S. Friedland, Convex spectral functions, Linear Multilinear Algebra 9 (1981) 299–316. https://doi.org/10.1080/03081088108817381.
  17. [17]T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66. https://doi.org/10.1007/BF02020961.
  18. [18]I. J. Good, The frequency count of a Markov chain and the transition to continuous time, Ann. Math. Statist. 32 (1961) 41–48. https://doi.org/10.1214/aoms/1177705138.
  19. [19]M. Habib, C. Paul, A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev. 4 (2010) 41–59. https://doi.org/10.1016/j.cosrev.2010.01.001.
  20. [20]D. J. Hartfiel, R. Loewy, On matrices having equal corresponding principal minors, Linear Algebra Appl. 58 (1984) 147–167. https://doi.org/10.1016/0024-3795(84)90209-X.
  21. [21]P. Kagey, Problem 131, Open Problem Collection. https://peterkagey.com/problems/131/, 2026 (accessed October 2026).
  22. [22]S. Kim, C. Landim, Γ-expansion of the measure-current large deviations rate functional of non-reversible finite-state Markov chains, Stochastic Process. Appl. 189 (2025) 104733. https://doi.org/10.1016/j.spa.2025.104733. Section 5 is cited with the numbering of arXiv:2412.13515v2.
  23. [23]B. Larget, A canonical representation for aggregated Markov processes, J. Appl. Probab. 35 (1998) 313–324. https://doi.org/10.1239/jap/1032192850.
  24. [24]R. Loewy, Principal minors and diagonal similarity of matrices, Linear Algebra Appl. 78 (1986) 23–64. https://doi.org/10.1016/0024-3795(86)90015-7.
  25. [25]A. Marin, S. Rossi, On the relations between Markov chain lumpability and reversibility, Acta Inform. 54 (2017) 447–485. https://doi.org/10.1007/s00236-016-0266-1.
  26. [26]A. Pemmasani, Occupation counts of rarely switching Markov chains: stratified local laws, support selection and the boundary layer, preprint, arXiv:2610.09258v2, 2026. https://arxiv.org/abs/2610.09258.
  27. [27]A. Pemmasani, What occupation statistics determine about a diffusion, in preparation.
  28. [28]T. Rydén, On identifiability and order of continuous-time aggregated Markov chains, Markov-modulated Poisson processes, and phase-type distributions, J. Appl. Probab. 33 (1996) 640–653. https://doi.org/10.2307/3215346.
  29. [29]X. Xiang, J. Zhou, Y. Deng, X. Yang, Identifying the generator matrix of a stationary Markov chain using partially observable data, Chaos 34 (2024) 023132. https://doi.org/10.1063/5.0156458.

Paper details

vlnc:W_6h9zk5xh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5

View statement
Looking for related papers…
Contents