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\} [ d ] = { 1 , … , d } spends in each state, and not the order of its visits or its jumps. What does this record determine about the generator Q Q Q ? Let O ( T ) O(T) O ( T ) be the vector of the times that the chain spends in each state up to time T T T . We answer the question for the law of O ( T ) O(T) O ( T ) , and for its logarithmic scale, the functional J V J_V J V of Donsker and Varadhan [11 ] , which is the rate function of O ( T ) / T O(T)/T O ( 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) O ( T ) never separates Q Q Q from its time reversal. We show that for generic Q Q Q it separates Q Q Q 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 Q Q Q from J V J_V J V (their Corollary 5.3) and show with the uniform 3-cycle that J V J_V J V does not determine a nonreversible one (their Example 5.4). For a finite chain less is determined than for a diffusion. The functional J V J_V J V determines only the principal minors of − Q -Q − Q , and the stationary law of O ( T ) O(T) O ( T ) can fail to separate Q Q Q from generators other than its time reversal.
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 Q Q Q and Q ∗ = D π − 1 Q T D π Q^* = D_\pi^{-1}Q^\mathsf{T}D_\pi Q ∗ = D π − 1 Q T D π for its time reversal, with D π D_\pi D π the diagonal matrix of π \pi π . Let B B B be a set of states with 2 ≤ ∣ B ∣ ≤ d − 1 2 \le|B| \le d-1 2 ≤ ∣ B ∣ ≤ d − 1 . We call B B B a memoryless block of Q Q Q if 2 conditions hold. First, all states of B B B jump to each state outside B B B at the same rate. Second, every jump into B B B from outside lands with the law π B / π ( B ) \pi_B/\pi(B) π B / π ( B ) . For such a B B B , the reversal of Q Q Q inside B B B replaces the block Q B Q_B Q B by D π B − 1 Q B T D π B D_{\pi_B}^{-1}Q_B^\mathsf{T}D_{\pi_B} D π B − 1 Q B T D π B and keeps the other entries of Q Q Q . We call a partition [ d ] = X ∪ Y [d] = X \cup Y [ d ] = X ∪ Y with ∣ X ∣ , ∣ Y ∣ ≥ 2 |X|, |Y| \ge2 ∣ X ∣ , ∣ Y ∣ ≥ 2 a cut of Q Q Q if the blocks Q [ X , Y ] Q[X,Y] Q [ X , Y ] and Q [ Y , X ] 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] [ d ] , form a tree under inclusion. We call a node N N N of this tree active if π i q i j ≠ π j q j i \pi_iq_{ij} \ne\pi_jq_{ji} π i q ij = π j q j i for some states i i i and j j j of N N N that lie together in no smaller node. Let k k k be the number of active nodes.
Theorem A (the stationary fiber). Let Q Q Q and Q ′ Q' Q ′ be irreducible generators on [ d ] [d] [ d ] , each started from its stationary law.
(a) O ( T ) O(T) O ( T ) has the same law under Q Q Q and Q ′ Q' Q ′ , for one T > 0 T > 0 T > 0 or equivalently for every T T T , if and only if Q ′ Q' Q ′ is reached from Q Q Q or from Q ∗ Q^* Q ∗ by reversals of memoryless blocks, each a memoryless block of the current generator.
(b) There are exactly 2 k 2^k 2 k such Q ′ Q' Q ′ . The reversals commute, and ( Z / 2 ) k (\mathbb{Z}/2)^k ( Z /2 ) k acts on these generators simply transitively.
(c) They are only Q Q Q and Q ∗ Q^* Q ∗ when d ≤ 4 d \le4 d ≤ 4 , when Q Q Q has no cut, and for all positive rates outside a finite union of proper linear subspaces. For d = 5 d = 5 d = 5 there are others.
This is Theorems 4.12 and 4.17, Corollary 4.19 and Example 4.11. When Q Q Q has no memoryless block, as for generic rates, and when d ≤ 3 d \le3 d ≤ 3 , 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 Q Q Q 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 B B B of at least 2 and at most d − 1 d-1 d − 1 states that every state of B B B leaves at the same rates, that every jump into B B B 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 Q Q Q be an irreducible generator on [ d ] [d] [ d ] and Q ′ Q' Q ′ a generator.
(i) If O ( T 0 ) O(T_0) O ( T 0 ) has the same law under Q Q Q from a start μ \mu μ and under Q ′ Q' Q ′ from a start μ ′ \mu' μ ′ , for one T 0 > 0 T_0>0 T 0 > 0 , then it has the same law for every T T T , μ ′ = μ \mu'=\mu μ ′ = μ , and − Q ′ -Q' − Q ′ has the principal minors of − Q -Q − Q .
(ii) If μ \mu μ has no renewal block, then the law of O ( T 0 ) O(T_0) O ( T 0 ) at one T 0 > 0 T_0>0 T 0 > 0 from μ \mu μ determines Q Q Q , or Q Q Q up to time reversal when μ = π \mu=\pi μ = π . This holds for every start outside a finite union of proper linear subspaces, which depend on Q Q Q , and for some starts with zeros.
(iii) For every start μ \mu μ , the law of O ( T 0 ) O(T_0) O ( T 0 ) at one T 0 > 0 T_0>0 T 0 > 0 from μ \mu μ determines Q Q Q exactly up to finitely many lumped reversals.
This is Theorems 4.2 , 4.5 and 4.26 . The renewal blocks are the cuts of Q Q Q 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 d d d . 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^* Q ↦ 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 2 k 2^k 2 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 + h Q I+hQ I + h Q for all N N N at one fixed h h h .
Starts that hide time reversal
The stationary start never separates Q Q Q from Q ∗ Q^* Q ∗ , and a generic start does. Write a start as μ = π ∘ f \mu=\pi\circ f μ = π ∘ f . A circulation component of Q Q Q is a connected component of the graph of the edges { i , j } \{i,j\} { i , j } with π i q i j ≠ π j q j i \pi_iq_{ij}\ne\pi_jq_{ji} π i q ij = π j q j i , and a closed block is a memoryless block with no net flux across its boundary.
Theorem C (which starts hide time reversal). Let Q Q Q be irreducible. A start μ = π ∘ f \mu=\pi\circ f μ = π ∘ f gives the same law of O ( T ) O(T) O ( T ) under Q Q Q and under Q ∗ Q^* Q ∗ if and only if f f f 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 E π [ f ( ξ T ) − f ( ξ 0 ) ∣ O ( T )] = 0 for every T T T . 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 − Q T D π D_\pi Q-Q^\mathsf{T}D_\pi D π Q − Q T D π (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 Q Q Q and Q ′ Q' Q ′ be irreducible generators on [ d ] [d] [ d ] . Then J V = J V ′ J_V=J'_V J V = J V ′ on the simplex if and only if − Q -Q − Q and − Q ′ -Q' − Q ′ have the same principal minors. In that case the exit rate λ F ( v ) \lambda_F(v) λ F ( v ) of every face F F F under every field v v v , and the functional J F J_F J F of the chain killed on leaving F F F , are the same for Q Q Q and Q ′ 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 − Q are Q Q Q and Q ∗ Q^* Q ∗ when Q Q Q has no cut and when d ≤ 3 d \le3 d ≤ 3 (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) O ( T ) at one time, from any start, determines the principal minors, so it determines J V J_V J 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) v ↦ ϱ ( A + 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 ≥ 2 d \ge2 d ≥ 2 and a generator Q Q Q on [ d ] = { 1 , … , d } [d]=\{1,\ldots,d\} [ d ] = { 1 , … , d } . Its rates are q i j ≥ 0 q_{ij} \ge0 q ij ≥ 0 for i ≠ j i \ne j i = j , the exit rates are q i = ∑ j ≠ i q i j q_i=\sum_{j\ne i}q_{ij} q i = ∑ j = i q ij , Q i i = − q i Q_{ii}=-q_i Q ii = − q i , and q max = max i q i q_{\max}=\max_i q_i q m a x = max i q i . A start is a probability law μ \mu μ on [ d ] [d] [ d ] , and V = [ d ] V=[d] V = [ d ] is the set of all states. If Q Q Q is irreducible, π \pi π is its stationary law, D π D_\pi D π the diagonal matrix of π \pi π , and Q ∗ = D π − 1 Q T D π Q^*=D_\pi^{-1}Q^\mathsf{T}D_\pi Q ∗ = D π − 1 Q T D π its time reversal.
Faces. A face is a nonempty set F ⊆ [ d ] F \subseteq[d] F ⊆ [ d ] . Let Δ F \Delta_F Δ F be the set of probability vectors on [ d ] [d] [ d ] that vanish off F F F , and Δ F ∘ \Delta_F^\circ Δ F ∘ the set of those that are positive on F F F . The killed generator of F F F is Q F = ( Q i j ) i , j ∈ F Q_F=(Q_{ij})_{i,j\in F} Q F = ( Q ij ) i , j ∈ F . Its diagonal keeps the full exit rates q i q_i q i , so it generates the chain killed when it leaves F F F . For A ⊆ F A \subseteq F A ⊆ F the principal submatrix of − Q F -Q_F − Q F on A A A is − Q A -Q_A − Q A . The graph G F G_F G F has an edge i → j i \to j i → j whenever i , j ∈ F i,j \in F i , j ∈ F , i ≠ j i \ne j i = j and q i j > 0 q_{ij}>0 q ij > 0 , and F F F is irreducible if G F G_F G F is strongly connected. Every singleton is irreducible.
Perron roots. A square matrix B B B is Metzler if its off-diagonal entries are nonnegative, and its Perron root ϱ ( B ) \varrho(B) ϱ ( B ) is then its largest real eigenvalue. If B B B is irreducible, ϱ ( B ) \varrho(B) ϱ ( B ) is simple and has positive left and right eigenvectors, and a positive eigenvector of B B B belongs to ϱ ( B ) \varrho(B) ϱ ( B ) [2 Chapter 2] . For a face F F F and a field v ∈ R d v \in\mathbb{R}^{d} v ∈ R d put
λ F ( v ) = − ϱ ( Q F + diag v F ) , λ F = λ F ( 0 ) . \lambda_F(v)=-\varrho\left(Q_F+\operatorname{diag}v_F\right), \qquad\lambda_F=\lambda_F(0). λ F ( v ) = − ϱ ( Q F + diag v F ) , λ F = λ F ( 0 ) .
The number λ F \lambda_F λ F is the exit rate of F F F , and λ { i } ( v ) = q i − v i \lambda_{\{i\}}(v)=q_i-v_i λ { i } ( v ) = q i − v i . If F F F is reducible, Q F Q_F Q F is block triangular in an order of the strongly connected components of G F G_F G F , and λ F ( v ) \lambda_F(v) λ F ( v ) is the least of the numbers λ C ( v ) \lambda_C(v) λ C ( v ) over these components C C C . The shift rule λ F ( v + c 1 ) = λ F ( v ) − c \lambda_F(v+c\mathbf{1})=\lambda_F(v)-c λ F ( v + c 1 ) = λ F ( v ) − c holds for every face. If F F F is irreducible, let r r r and l l l be positive right and left Perron vectors of Q F + diag v F Q_F+\operatorname{diag}v_F Q F + diag v F with l ⋅ r = 1 l\cdot r=1 l ⋅ r = 1 , and put α F ∗ ( v ) = l ∘ r \alpha_F^*(v)=l\circ r α F ∗ ( v ) = l ∘ r , where x ∘ y x\circ y x ∘ y is the entrywise product. Since the Perron root is simple, v ↦ λ F ( v ) v\mapsto\lambda_F(v) v ↦ λ F ( v ) is real-analytic on R F \mathbb{R}^{F} R F , and first-order perturbation gives
∂ λ F ∂ v i ( v ) = − α F ∗ ( v ) i < 0 , i ∈ F . (1) \frac{\partial\lambda_F}{\partial v_i}(v)=-\alpha_F^*(v)_i<0,\qquad i\in F. \tag*{(1)} ∂ v i ∂ λ F ( v ) = − α F ∗ ( v ) i < 0 , i ∈ F . (1)
Lemma 2.1 (monotonicity in the face). If F ⊊ G F\subsetneq G F ⊊ G are faces and G G G is irreducible, then λ G ( v ) < λ F ( v ) \lambda_G(v)<\lambda_F(v) λ G ( v ) < λ F ( v ) for every field v v v . In particular every proper face of an irreducible chain has λ F > λ V = 0 \lambda_F>\lambda_V=0 λ F > λ V = 0 .
Proof. Let B = Q G + diag v G B=Q_G+\operatorname{diag}v_G B = Q G + diag v G and let B 0 B_0 B 0 be B B B with the entries outside F × F F\times F F × F replaced by 0 0 0 off the diagonal. Then ϱ ( B 0 ) = max ( ϱ ( Q F + diag v F ) , max i ∈ G ∖ F B i i ) \varrho(B_0)=\max\left(\varrho(Q_F+\operatorname{diag}v_F),\max_{i\in G\setminus F}B_{ii}\right) ϱ ( B 0 ) = max ( ϱ ( Q F + diag v F ) , max i ∈ G ∖ F B ii ) . The Perron root of a Metzler matrix is nondecreasing in its entries, and strictly increasing when the larger matrix is irreducible and the two differ [2 Chapter 2] . Since G G G is irreducible and F ≠ G F\ne G F = G , some entry of B B B off F × F F\times F F × F is positive, so ϱ ( B ) > ϱ ( B 0 ) ≥ − λ F ( v ) \varrho(B)>\varrho(B_0)\ge-\lambda_F(v) ϱ ( B ) > ϱ ( B 0 ) ≥ − λ F ( v ) . For G = V G=V G = V and v = 0 v=0 v = 0 , the vector 1 \mathbf{1} 1 is a positive null vector of Q Q Q , so λ V = 0 \lambda_V=0 λ V = 0 . ▫
The functional. For α ∈ Δ F \alpha\in\Delta_F α ∈ Δ F let
J F ( α ) = sup u ∈ ( 0 , ∞ ) F ∑ i ∈ F α i ( − ( Q F u ) i u i ) . J_F(\alpha)=\sup_{u\in(0,\infty)^F}\sum_{i\in F}\alpha_i\left(-\frac{(Q_Fu)_i}{u_i}\right). J F ( α ) = u ∈ ( 0 , ∞ ) F sup i ∈ F ∑ α i ( − u i ( Q F u ) i ) .
the Donsker and Varadhan functional of the chain killed on leaving F F F [11 ] , and write J V J_V J V for that of the whole chain. It is the rate function of the occupation measure T − 1 O ( T ) T^{-1}O(T) T − 1 O ( T ) of § 4 as T → ∞ T\to\infty T → ∞ [11 ] . We use 2 facts.
Proposition 2.2 (the variational formula). Let F F F be a face.
(a) J G = J F J_G=J_F J G = J F on Δ F \Delta_F Δ F for every face G ⊇ F G\supseteq F G ⊇ F . In particular J F = J V J_F=J_V J F = J V on Δ F \Delta_F Δ F .
(b) For every v ∈ R F v\in\mathbb{R}^{F} v ∈ R F
λ F ( v ) = min α ∈ Δ F ( J F ( α ) − v ⋅ α ) . \lambda_F(v)=\min_{\alpha\in\Delta_F}\left(J_F(\alpha)-v\cdot\alpha\right). λ F ( v ) = α ∈ Δ F min ( J F ( α ) − v ⋅ α ) . So − λ F -\lambda_F − λ F is the Legendre transform of J F J_F J F , and J F ( α ) = sup v ∈ R F ( v ⋅ α + λ F ( v ) ) J_F(\alpha)=\sup_{v\in\mathbb{R}^{F}}\left(v\cdot\alpha+\lambda_F(v)\right) J F ( α ) = sup v ∈ R F ( v ⋅ α + λ F ( v ) ) for every α ∈ Δ F \alpha\in\Delta_F α ∈ Δ F .
Proof. (a) Let α ∈ Δ F \alpha\in\Delta_F α ∈ Δ F and u ∈ ( 0 , ∞ ) G u\in(0,\infty)^G u ∈ ( 0 , ∞ ) G . For i ∈ F i\in F i ∈ F , − ( Q G u ) i = q i u i − ∑ j ∈ F ∖ { i } q i j u j − ∑ j ∈ G ∖ F q i j u j ≤ − ( Q F u F ) i -(Q_Gu)_i=q_i u_i-\sum_{j\in F\setminus\{i\}}q_{ij}u_j-\sum_{j\in G\setminus F}q_{ij}u_j\le-(Q_Fu_F)_i − ( Q G u ) i = q i u i − ∑ j ∈ F ∖ { i } q ij u j − ∑ j ∈ G ∖ F q ij u j ≤ − ( Q F u F ) i , so J G ( α ) ≤ J F ( α ) J_G(\alpha)\le J_F(\alpha) J G ( α ) ≤ J F ( α ) . Letting u j ↓ 0 u_j\downarrow0 u j ↓ 0 for j ∈ G ∖ F j\in G\setminus F j ∈ G ∖ F gives the reverse inequality.
(b) Write Q F = L F − diag k F Q_F=L_F-\operatorname{diag}k_F Q F = L F − diag k F , where L F L_F L F is the generator on F F F with the rates of Q Q Q inside $F and k i = ∑ j ∉ F q i j k_i=\sum_{j\notin F}q_{ij} k i = ∑ j ∈ / F q ij is the rate of killing at i i i . Then Q F + diag v F = L F + diag ( v F − k F ) Q_F+\operatorname{diag}v_F=L_F+\operatorname{diag}(v_F-k_F) Q F + diag v F = L F + diag ( v F − k F ) , and J F ( α ) J_F(\alpha) J F ( α ) is the functional of L F L_F L F plus k ⋅ α k\cdot\alpha k ⋅ α . If F F F is irreducible, the formula is that of Donsker and Varadhan [11 ] for the generator L F L_F L F and the potential v F − k F v_F-k_F v F − k F . In general put B = Q F + diag v F B=Q_F+\operatorname{diag}v_F B = Q F + diag v F , so that ϱ ( B ) = − λ F ( v ) \varrho(B)=-\lambda_F(v) ϱ ( B ) = − λ F ( v ) . Let C C C be a strongly connected component of G F G_F G F with ϱ ( B C ) = ϱ ( B ) \varrho(B_C)=\varrho(B) ϱ ( B C ) = ϱ ( B ) . By the irreducible case and (a), ϱ ( B ) = max α ∈ Δ C ( v ⋅ α − J F ( α ) ) \varrho(B)=\max_{\alpha\in\Delta_C}(v\cdot\alpha-J_F(\alpha)) ϱ ( B ) = max α ∈ Δ C ( v ⋅ α − J F ( α )) , so ϱ ( B ) \varrho(B) ϱ ( B ) is at most the maximum over Δ F \Delta_F Δ F . Conversely, for every ε > 0 \varepsilon>0 ε > 0 there is u ∈ ( 0 , ∞ ) F u\in(0,\infty)^F u ∈ ( 0 , ∞ ) F with B u ≤ ( ϱ ( B ) + ε ) u Bu\leq(\varrho(B)+\varepsilon)u B u ≤ ( ϱ ( B ) + ε ) u entrywise. This is the formula of Collatz and Wielandt, which holds for every Metzler matrix, since a positive matrix B + s I + δ 11 T B+sI+\delta11^{\mathsf T} B + s I + δ 1 1 T has a positive Perron vector and its Perron root tends to ϱ ( B ) + s \varrho(B)+s ϱ ( B ) + s as δ ↓ 0 \delta\downarrow0 δ ↓ 0 . For α ∈ Δ F \alpha\in\Delta_F α ∈ Δ F the vector u u u gives J F ( α ) ≥ ∑ i α i ( v i − ( B u ) i / u i ) ≥ v ⋅ α − ϱ ( B ) − ε J_F(\alpha)\geq\sum_i\alpha_i(v_i-(Bu)_i/u_i)\geq v\cdot\alpha-\varrho(B)-\varepsilon J F ( α ) ≥ ∑ i α i ( v i − ( B u ) i / u i ) ≥ v ⋅ α − ϱ ( B ) − ε . So the maximum over Δ F \Delta_F Δ F is at most ϱ ( B ) \varrho(B) ϱ ( B ) , and it is attained since J F J_F J F is lower semicontinuous and Δ F \Delta_F Δ F is compact.
The function J F J_F J F is a supremum of affine functions of α \alpha α , so it is convex and lower semicontinuous, and it is finite on Δ F \Delta_F Δ F , since u = 1 u=1 u = 1 shows J F ≥ 0 J_F\geq0 J F ≥ 0 and every term is at most q max q_{\max} q m a x . Extend it by + ∞ +\infty + ∞ off Δ F \Delta_F Δ F . Then the first sentence says that the convex conjugate of J F J_F J F is − λ F -\lambda_F − λ F , and the theorem of Fenchel and Moreau gives J F = J F ∗ ∗ J_F=J_F^{**} J F = J F ∗∗ , which is the second.
The Donsker and Varadhan functional and the principal minors
This section proves Proposition 1.1 and describes the generators with given principal minors. Section 3.1 shows that the Perron root of a face on an open set of fields determines the principal minors of the face. Section 3.2 deduces that J V J_V J V determines exactly the principal minors of − Q -Q − Q , and Section 3.3 describes the generators with given minors.
The polynomial of a face and the Perron branch
The principal minors of − Q F -Q_F − Q F are the numbers det ( − Q A ) \det(-Q_A) det ( − Q A ) for A ⊆ F A\subseteq F A ⊆ F , with det ( − Q ∅ ) = 1 \det(-Q_\varnothing)=1 det ( − Q ∅ ) = 1 . They are the coefficients of the multiaffine polynomial
R F ( w ) = det ( − Q F − diag w ) = ∑ A ⊆ F det ( − Q A ) ∏ i ∈ F ∖ A ( − w i ) , w ∈ R F . R_F(w)=\det(-Q_F-\operatorname{diag}w)=\sum_{A\subseteq F}\det(-Q_A)\prod_{i\in F\setminus A}(-w_i),\qquad w\in\mathbb{R}^F. R F ( w ) = det ( − Q F − diag w ) = A ⊆ F ∑ det ( − Q A ) i ∈ F ∖ A ∏ ( − w i ) , w ∈ R F .
For every field v v v , λ F ( v ) \lambda_F(v) λ F ( v ) is a real root of t ↦ R F ( v + t 1 ) t\mapsto R_F(v+t1) t ↦ R F ( v + t 1 ) , and if F F F is irreducible it is the smallest real root, since the other real eigenvalues of − Q F − diag v F -Q_F-\operatorname{diag}v_F − Q F − diag v F exceed the Perron eigenvalue.
Lemma 3.1 (irreducibility). If F F F is irreducible, then R F R_F R F is irreducible over C \mathbb{C} C . If F F F is reducible, R F R_F R F is the product of the polynomials of the strongly connected components of G F G_F G F .
Proof. Al Ahmadieh [1 Lemma 5.1] proves, over any field and for every order, that a square matrix A A A is irreducible exactly when det ( diag x + A ) \det(\operatorname{diag}x+A) det ( diag x + A ) is an irreducible polynomial in x x x . Take the field C \mathbb{C} C and A = − Q F A=-Q_F A = − Q F . Then R F ( w ) = det ( diag ( − w ) + A ) R_F(w)=\det(\operatorname{diag}(-w)+A) R F ( w ) = det ( diag ( − w ) + A ) , and the linear change of variables x = − w x=-w x = − w preserves irreducibility. For a reducible face, − Q F -Q_F − Q F is block triangular with the blocks of the components on the diagonal, and the determinant factors accordingly.
The proof of Al Ahmadieh rests on a theorem of Hartfiel and Loewy [20 Theorem 1] , that every entry of the adjugate of diag x + A \operatorname{diag}x+A diag x + A is a nonzero polynomial when A A A is irreducible. The next lemma turns the vanishing of a polynomial along one root of an irreducible polynomial into a divisibility.
Lemma 3.2 (vanishing on a graph). Let P ∈ C [ s , w ] \mathcal{P}\in\mathbb{C}[s,w] P ∈ C [ s , w ] , with w = ( w 1 , … , w n ) w=(w_1,\ldots,w_n) w = ( w 1 , … , w n ) , be irreducible and monic in s s s of degree m > 1 m>1 m > 1 . Let U ⊂ R n U\subset\mathbb{R}^n U ⊂ R n be nonempty and open, and let θ \theta θ be a function on U U U with P ( θ ( w ) , w ) = 0 \mathcal{P}(\theta(w),w)=0 P ( θ ( w ) , w ) = 0 . If R ∈ C [ s , w ] \mathcal{R}\in\mathbb{C}[s,w] R ∈ C [ s , w ] and R ( θ ( w ) , w ) = 0 \mathcal{R}(\theta(w),w)=0 R ( θ ( w ) , w ) = 0 for all w ∈ U w\in U w ∈ U , then P \mathcal{P} P divides R \mathcal{R} R .
Proof. Divide by the monic P \mathcal{P} P in s s s , so R = A P + B \mathcal{R}=\mathcal{A}\mathcal{P}+\mathcal{B} R = A P + B with deg s B < m \deg_s\mathcal{B}<m deg s B < m and B ( θ ( w ) , w ) = 0 \mathcal{B}(\theta(w),w)=0 B ( θ ( w ) , w ) = 0 on U U U . Suppose B ≠ 0 \mathcal{B}\ne0 B = 0 . Then P \mathcal{P} P does not divide B \mathcal{B} B , so by Gauss’s lemma they have no common factor over C ( w ) \mathbb{C}(w) C ( w ) , and the resultant ρ = Res s ( P , B ) ∈ C [ w ] \rho=\operatorname{Res}_{s}(\mathcal{P},\mathcal{B})\in\mathbb{C}[w] ρ = Res s ( P , B ) ∈ C [ w ] is not zero. Since P \mathcal{P} P is monic, ρ ( w ) \rho(w) ρ ( w ) is the product of B ( σ , w ) \mathcal{B}(\sigma,w) B ( σ , w ) over the roots σ \sigma σ of P ( ⋅ , w ) \mathcal{P}(\cdot,w) P ( ⋅ , w ) , and one of them is θ ( w ) \theta(w) θ ( w ) . So ρ \rho ρ vanishes on U U U , which is impossible for a nonzero polynomial.
Lemma 3.3 (the Perron branch). Let F F F be irreducible, let Q ′ Q' Q ′ be another generator whose face F F F is irreducible, and let c ∈ R c\in\mathbb{R} c ∈ R . Suppose that λ F ′ ( v ) = λ F ( v ) + c \lambda'_F(v)=\lambda_F(v)+c λ F ′ ( v ) = λ F ( v ) + c for all v v v in a nonempty open set U ⊆ R F U\subseteq\mathbb{R}^F U ⊆ R F . Then − Q F ′ -Q'_F − Q F ′ and − Q F + c I -Q_F+cI − Q F + c I have the same principal minors, and λ F ′ = λ F + c \lambda'_F=\lambda_F+c λ F ′ = λ F + c on all of R F \mathbb{R}^F R F . In particular, for c = 0 c=0 c = 0 , − Q F ′ -Q'_F − Q F ′ and − Q F -Q_F − Q F have the same principal minors.
Proof. Let k = ∣ F ∣ k=|F| k = ∣ F ∣ and put R ~ ( w ) = det ( − Q F + c I − diag w ) = R F ( w − c 1 ) \widetilde{R}(w)=\det(-Q_F+cI-\operatorname{diag}w)=R_F(w-c\mathbf{1}) R ( w ) = det ( − Q F + c I − diag w ) = R F ( w − c 1 ) , which is irreducible over C \mathbb{C} C by Lemma 3.1 . In the variables ( t , v ) (t,v) ( t , v ) put P ( t , v ) = ( − 1 ) k R ~ ( v + t 1 ) P(t,v)=(-1)^k\widetilde{R}(v+t\mathbf{1}) P ( t , v ) = ( − 1 ) k R ( v + t 1 ) and P ′ ( t , v ) = ( − 1 ) k R F ′ ( v + t 1 ) P'(t,v)=(-1)^kR'_F(v+t\mathbf{1}) P ′ ( t , v ) = ( − 1 ) k R F ′ ( v + t 1 ) . Both are monic of degree k k k in t t t , and P P P is irreducible, since it is ± R ~ \pm\widetilde{R} ± R composed with the linear surjection ( t , v ) ↦ v + t 1 (t,v)\mapsto v+t\mathbf{1} ( t , v ) ↦ v + t 1 . For v ∈ U v\in U v ∈ U the number θ ( v ) = λ F ′ ( v ) = λ F ( v ) + c \theta(v)=\lambda'_F(v)=\lambda_F(v)+c θ ( v ) = λ F ′ ( v ) = λ F ( v ) + c is an eigenvalue of − Q F ′ − diag v -Q'_F-\operatorname{diag}v − Q F ′ − diag v and of − Q F + c I − diag v -Q_F+cI-\operatorname{diag}v − Q F + c I − diag v , so P ( θ ( v ) , v ) = 0 = P ′ ( θ ( v ) , v ) P(\theta(v),v)=0=P'(\theta(v),v) P ( θ ( v ) , v ) = 0 = P ′ ( θ ( v ) , v ) . Lemma 3.2 gives that P P P divides P ′ P' P ′ , and both are monic of degree k k k in t t t , so P ′ = P P'=P P ′ = P . At t = 0 t=0 t = 0 this says R F ′ = R ~ R'_F=\widetilde{R} R F ′ = R . Finally λ F ′ ( v ) \lambda'_F(v) λ F ′ ( v ) is the smallest real root of t ↦ R F ′ ( v + t 1 ) = R ~ ( v + t 1 ) t\mapsto R'_F(v+t\mathbf{1})=\widetilde{R}(v+t\mathbf{1}) t ↦ R F ′ ( v + t 1 ) = R ( v + t 1 ) , which is λ F ( v ) + c \lambda_F(v)+c λ F ( v ) + c .
Cohen [9 ] proved that v ↦ ϱ ( A + diag v ) v\mapsto\varrho(A+\operatorname{diag}v) v ↦ ϱ ( A + diag v ) is convex for a Metzler matrix A A A , and Friedland [16 Theorem 4.1] showed that for irreducible A A A it is affine only along 1 \mathbf{1} 1 . Lemma 3.3 goes the other way. It recovers the principal minors of A A A from this map on an open set.
The functional determines exactly the principal minors
Proposition 3.4 (the functional and the minors). For two irreducible generators Q Q Q and Q ′ Q' Q ′ on [ d ] [d] [ d ] the following are equivalent.
J V = J V ′ J_V=J'_V J V = J V ′ on Δ V \Delta_V Δ V .
λ V = λ V ′ \lambda_V=\lambda'_V λ V = λ V ′ on a nonempty open set of fields.
− Q -Q − Q and − Q ′ -Q' − Q ′ have the same principal minors.
If they hold, then λ F = λ F ′ \lambda_F=\lambda'_F λ F = λ F ′ on R F \mathbb{R}^F R F and J F = J F ′ J_F=J'_F J F = J F ′ on Δ F \Delta_F Δ F for every face F F F , and F F F is irreducible for Q Q Q exactly when it is irreducible for Q ′ Q' Q ′ .
Proof. (i) implies (iii). By Proposition 2.2 (a), J F = J V = J V ′ = J F ′ J_F=J_V=J'_V=J'_F J F = J V = J V ′ = J F ′ on Δ F \Delta_F Δ F for every face F F F , so Proposition 2.2 (b) gives λ F = λ F ′ \lambda_F=\lambda'_F λ F = λ F ′ , and in particular λ F ( 0 ) = λ F ′ ( 0 ) \lambda_F(0)=\lambda'_F(0) λ F ( 0 ) = λ F ′ ( 0 ) . We show det ( − Q F ) = det ( − Q F ′ ) \det(-Q_F)=\det(-Q'_F) det ( − Q F ) = det ( − Q F ′ ) by induction on ∣ F ∣ |F| ∣ F ∣ , starting from det ( − Q ∅ ) = 1 \det(-Q_\varnothing)=1 det ( − Q ∅ ) = 1 . If − Q F -Q_F − Q F and − Q F ′ -Q'_F − Q F ′ have the same proper principal minors, then R F ′ − R F R'_F-R_F R F ′ − R F is the constant det ( − Q F ′ ) − det ( − Q F ) \det(-Q'_F)-\det(-Q_F) det ( − Q F ′ ) − det ( − Q F ) . The number λ F ( 0 ) \lambda_F(0) λ F ( 0 ) is an eigenvalue of − Q F -Q_F − Q F , and λ F ′ ( 0 ) = λ F ( 0 ) \lambda'_F(0)=\lambda_F(0) λ F ′ ( 0 ) = λ F ( 0 ) is one of − Q F ′ -Q'_F − Q F ′ , so both polynomials vanish at λ F ( 0 ) 1 \lambda_F(0)\mathbf{1} λ F ( 0 ) 1 , and the constant is 0. With M = Q + c I M=Q+cI M = Q + c I for c ≥ max ( q max , q max ′ ) c\geq\max(q_{\max},q'_{\max}) c ≥ max ( q m a x , q m a x ′ ) , this is the case of the theorem of Delmas, Drönnier and Zitt [10 Theorem 2.1] that nonnegative matrices M M M and M ′ M' M ′ with ϱ ( M F ) = ϱ ( M F ′ ) \varrho(M_F)=\varrho(M'_F) ϱ ( M F ) = ϱ ( M F ′ ) for every F F F have the same principal minors.
(ii) implies (iii). This is Lemma 3.3 with F = V F=V F = V and c = 0 c=0 c = 0 .
(iii) implies (i) and (ii). Equal principal minors give R F ′ = R F R'_F=R_F R F ′ = R F for every face F F F , since the minors of − Q F ′ -Q'_F − Q F ′ are among those of − Q -Q − Q . By Lemma 3.1 , F F F is irreducible for Q Q Q exactly when R F R_F R F is irreducible, which is the last claim. Every real eigenvalue of the Metzler matrix Q F + diag v Q_F+\operatorname{diag}v Q F + diag v is at most its Perron root, so for every face λ F ( v ) \lambda_F(v) λ F ( v ) is the smallest real root of t ↦ R F ( v + t 1 ) t\mapsto R_F(v+t\mathbf{1}) t ↦ R F ( v + t 1 ) , and likewise for Q ′ Q' Q ′ . So λ F ′ = λ F \lambda'_F=\lambda_F λ F ′ = λ F , which gives (ii). By Proposition 2.2 (b), J F ( α ) = sup v ⋅ α + λ F ( v ) J_F(\alpha)=\sup_{v\cdot\alpha+\lambda_F(v)} J F ( α ) = sup v ⋅ α + λ F ( v ) on Δ F \Delta_F Δ F , and likewise for Q ′ Q' Q ′ , so J F ′ = J F J'_F=J_F J F ′ = J F on Δ F \Delta_F Δ F . With F = V F=V F = V this is (i).
Lemma 3.3 is needed for (ii), when only the Perron root of the whole space is known, and only on an open set of fields. That is also the situation of the law of O ( T ) O(T) O ( T ) at one time, and Step 5 of the proof of Theorem 4.2 runs the same argument.
The generators with given minors
Without reversibility the exit rates and the edge products q i j q j i q_{ij}q_{ji} q ij q j i do not determine Q Q Q , since Q ∗ Q^* Q ∗ has the same exit rates, the same products and the same stationary law. The next corollary describes the generators with the principal minors of − Q -Q − Q when Q Q Q has no cut. A matrix C C C is a Z-matrix if − C -C − C is Metzler.
Lemma 3.5 (the generator point). Let Q Q Q be an irreducible generator and C C C an irreducible Z-matrix with the principal minors of − Q -Q − Q . Then − C -C − C has the spectrum of Q Q Q , and there is a positive diagonal matrix D D D , unique up to a factor, such that − D − 1 C D -D^{-1}CD − D − 1 C D is a generator. It is irreducible, and every real invertible diagonal D ′ D' D ′ for which − D ′ − 1 C D ′ -D'^{-1}CD' − D ′ − 1 C D ′ has zero row sums is a multiple of D D D . For C = − Q C=-Q C = − Q this generator is Q Q Q , and for C = − Q T C=-Q^{\mathsf T} C = − Q T it is Q ∗ Q^* Q ∗ .
Proof. The characteristic polynomial det ( t I − C ) = ∑ s = 0 d ( − 1 ) s t d − s E s ( C ) \det(tI-C)=\sum_{s=0}^{d}(-1)^s t^{d-s}E_s(C) det ( t I − C ) = ∑ s = 0 d ( − 1 ) s t d − s E s ( C ) , with E s E_s E s the sum of the principal minors of order s s s , is that of − Q -Q − Q . So − C -C − C has the spectrum of Q Q Q , whose eigenvalue of largest real part is the simple eigenvalue 0. The theorem of Perron and Frobenius for the irreducible Metzler matrix − C -C − C gives a vector x > 0 x>0 x > 0 , unique up to a factor, with C x = 0 Cx=0 C x = 0 . With D = diag x D=\operatorname{diag}x D = diag x the matrix − D − 1 C D -D^{-1}CD − D − 1 C D has off-diagonal entries − c i j x j / x i ≥ 0 -c_{ij}x_j/x_i\ge0 − c ij x j / x i ≥ 0 and zero row sums, so it is an irreducible generator. If D ′ D' D ′ is real, diagonal and invertible and − D ′ − 1 C D ′ -D'^{-1}CD' − D ′ − 1 C D ′ has zero row sums, then C ( D ′ 1 ) = 0 C(D'{\bf1})=0 C ( D ′ 1 ) = 0 , so D ′ D' D ′ is a multiple of D D D and gives the same matrix. For C = − Q C=-Q C = − Q the generator is Q Q Q , and for C = − Q T C=-Q^{\mathsf T} C = − Q T , whose null vector is π \pi π , it is Q ∗ Q^* Q ∗ .
Definition 3.6 (generator point). The generator − D − 1 C D -D^{-1}CD − D − 1 C D of Lemma 3.5 is the generator point of $C.
Corollary 3.7 (the generator fiber). Let Q Q Q be an irreducible generator.
(a) Every generator Q ′ Q' Q ′ with the principal minors of − Q -Q − Q is irreducible and has the spectrum of Q Q Q . The set of such generators contains Q Q Q and its time reversal Q ∗ Q^* Q ∗ .
(b) If Q Q Q has no cut, that is, for every partition V = X ∪ Y V=X\cup Y V = X ∪ Y with ∣ X ∣ , ∣ Y ∣ ≥ 2 |X|,|Y|\ge2 ∣ X ∣ , ∣ Y ∣ ≥ 2 one of the blocks Q [ X , Y ] Q[X,Y] Q [ X , Y ] , Q [ Y , X ] Q[Y,X] Q [ Y , X ] has rank at least 2, then the set in (a) is { Q , Q ∗ } \{Q,Q^*\} { Q , Q ∗ } . It is a single point exactly when Q Q Q is reversible.
(c) If d ≤ 3 d\le3 d ≤ 3 , the set in (a) is { Q , Q ∗ } \{Q,Q^*\} { Q , Q ∗ } with no condition.
What is borrowed. The matrix theorems used are Loewy [24 Theorem 1] for order n ≥ 4 n\ge4 n ≥ 4 without a cut and Hartfiel and Loewy [20 Theorem 3] for $n\le 3, combined in [8 Lemma 2.8] . Chatterjee, Ghosh, Gurjar and Raj [8 Theorem 1.1] describe the whole fiber by cut-transposes, and § 4.4 uses their theorem for the stationary law. What we add here is Lemma 3.5 and the irreducibility of every member.
Proof. We first record a fact used in (b) and (c).
( R ) (R) ( R ) Real similarities. If − Q ′ = E ( − Q ) E − 1 -Q'=E(-Q)E^{-1} − Q ′ = E ( − Q ) E − 1 or − Q ′ = E ( − Q ) T E − 1 -Q'=E(-Q)^{\mathsf T}E^{-1} − Q ′ = E ( − Q ) T E − 1 for a complex invertible diagonal E E E , then E E E may be taken real. In the first case q i j ′ = e i q i j / e j q'_{ij}=e_iq_{ij}/e_j q ij ′ = e i q ij / e j , so e i / e j = q i j ′ / q i j e_i/e_j=q'_{ij}/q_{ij} e i / e j = q ij ′ / q ij is real on every edge of the graph of Q Q Q . That graph is strongly connected, so every ratio e i / e 1 e_i/e_1 e i / e 1 is a product of such ratios and is real, and E / e 1 E/e_1 E / e 1 is a real diagonal similarity. The second case is the same with q j i q_{ji} q j i in place of q i j q_{ij} q ij . (a) Let Q ′ Q' Q ′ be a generator with the principal minors of − Q -Q − Q , and suppose that − Q ′ -Q' − Q ′ is reducible. Then there is a proper nonempty A ⊂ V A \subset V A ⊂ V with Q ′ [ V ∖ A , A ] = 0 Q'[V \setminus A,A]=0 Q ′ [ V ∖ A , A ] = 0 , and det ( − Q ′ ) = det ( − Q A ′ ) det ( − Q V ∖ A ′ ) \det(-Q')=\det(-Q'_A)\det(-Q'_{V\setminus A}) det ( − Q ′ ) = det ( − Q A ′ ) det ( − Q V ∖ A ′ ) . Both factors are proper principal minors, so they equal det ( − Q A ) \det(-Q_A) det ( − Q A ) and det ( − Q V ∖ A ) \det(-Q_{V\setminus A}) det ( − Q V ∖ A ) . By Lemma 2.1 every irreducible component of a proper face has a positive exit rate, so every eigenvalue of − Q A -Q_A − Q A has positive real part and det ( − Q A ) > 0 \det(-Q_A)>0 det ( − Q A ) > 0 , and likewise det ( − Q V ∖ A ) > 0 \det(-Q_{V\setminus A})>0 det ( − Q V ∖ A ) > 0 . This contradicts det ( − Q ′ ) = det ( − Q ) = 0 \det(-Q')=\det(-Q)=0 det ( − Q ′ ) = det ( − Q ) = 0 . So Q ′ Q' Q ′ is irreducible, and the same argument applies to every real matrix with the principal minors of − Q -Q − Q . This also follows from Lemma 3.1 , since such a matrix has the polynomial R V R_V R V of − Q -Q − Q . The spectra agree by Lemma 3.5 . The time reversal Q ∗ Q^* Q ∗ is a generator, since Q ∗ 1 = D π − 1 Q T π = 0 Q^*\mathbf{1}=D_\pi^{-1}Q^\mathsf{T}\pi=0 Q ∗ 1 = D π − 1 Q T π = 0 and its off-diagonal entries are π j q j i / π i ≥ 0 \pi_jq_{ji}/\pi_i\ge0 π j q j i / π i ≥ 0 , and − Q ∗ = D π − 1 ( − Q ) T D π -Q^*=D_\pi^{-1}(-Q)^\mathsf{T}D_\pi − Q ∗ = D π − 1 ( − Q ) T D π has the principal minors of − Q -Q − Q , since transposition and diagonal similarity preserve them.
(b) For d ≤ 3 d\le3 d ≤ 3 the claim is (c). Let d ≥ 4 d\ge4 d ≥ 4 . Loewy’s theorem [24 Theorem 1] applies to the irreducible matrix − Q -Q − Q without a cut, with no condition on − Q ′ -Q' − Q ′ . It gives an invertible diagonal E E E with − Q ′ = E ( − Q ) E − 1 -Q'=E(-Q)E^{-1} − Q ′ = E ( − Q ) E − 1 or − Q ′ T = E ( − Q ) E − 1 -Q'^\mathsf{T}=E(-Q)E^{-1} − Q ′ T = E ( − Q ) E − 1 , and by (R) we may take E E E real. In the first case Lemma 3.5 with C = − Q C=-Q C = − Q gives Q ′ = Q Q'=Q Q ′ = Q , and in the second case Q ′ = E − 1 Q T E Q'=E^{-1}Q^\mathsf{T}E Q ′ = E − 1 Q T E and Lemma 3.5 with C = − Q T C=-Q^\mathsf{T} C = − Q T gives Q ′ = Q ∗ Q'=Q^* Q ′ = Q ∗ . Finally Q ∗ = Q Q^*=Q Q ∗ = Q exactly when π i q i j = π j q j i \pi_iq_{ij}=\pi_jq_{ji} π i q ij = π j q j i for all i , j i,j i , j , that is when Q Q Q is reversible.
(c) For d = 2 d=2 d = 2 a generator is fixed by q 1 q_1 q 1 and q 2 q_2 q 2 , which are principal minors. Let d = 3 d=3 d = 3 and let Q ′ Q' Q ′ be in the fiber, so Q ′ Q' Q ′ is irreducible by (a). The theorem of Hartfiel and Loewy [20 Theorem 3] , as restated in [8 Lemma 2.8] , says that for an irreducible matrix A A A of order 2 or 3 over a field, every matrix with the principal minors of A A A is diagonally similar to A A A or to A T A^\mathsf{T} A T over that field. So − Q ′ = E ( − Q ) E − 1 -Q'=E(-Q)E^{-1} − Q ′ = E ( − Q ) E − 1 or − Q ′ = E ( − Q ) T E − 1 -Q'=E(-Q)^\mathsf{T}E^{-1} − Q ′ = E ( − Q ) T E − 1 with E E E diagonal and invertible, real by (R), and Lemma 3.5 gives Q ′ = Q Q'=Q Q ′ = Q or Q ′ = Q ∗ Q'=Q^* Q ′ = Q ∗ , as in (b).
The exact occupation law
Reductions
Let ( ξ t ) t ≥ 0 (\xi_t)_{t\ge0} ( ξ t ) t ≥ 0 be the chain with generator Q Q Q and start μ \mu μ , and let O ( T ) ∈ [ 0 , T ] d O(T)\in[0,T]^d O ( T ) ∈ [ 0 , T ] d be its vector of occupation times, O i ( T ) = ∫ 0 T 1 { ξ t = i } d t O_i(T)=\int_0^T\mathbf{1}\{\xi_t=i\}\,\mathrm{d}t O i ( T ) = ∫ 0 T 1 { ξ t = i } d t . For x ∈ C d x\in\mathbb{C}^d x ∈ C d put
F Q μ ( x ) = μ ( diag x − Q ) − 1 1 , F Q = F Q π when Q is irreducible , F_Q^\mu(x)=\mu(\operatorname{diag}x-Q)^{-1}\mathbf{1},\qquad F_Q=F_Q^\pi\quad\text{when }Q\text{ is irreducible}, F Q μ ( x ) = μ ( diag x − Q ) − 1 1 , F Q = F Q π when Q is irreducible ,
a rational function of x x x . We write W = diag w W=\operatorname{diag}w W = diag w for w ∈ R d w\in\mathbb{R}^d w ∈ R d and D = D π D=D_\pi D = D π for the diagonal matrix of π \pi π .
Lemma 4.1 (reductions). Let Q Q Q be a generator and μ \mu μ a start.
(a) E μ e − w ⋅ O ( T ) = μ e T ( Q − W ) 1 \mathbb{E}_\mu e^{-w\cdot O(T)}=\mu e^{T(Q-W)}\mathbf{1} E μ e − w ⋅ O ( T ) = μ e T ( Q − W ) 1 for w ∈ R d w\in\mathbb{R}^d w ∈ R d . The laws of O ( T ) O(T) O ( T ) for all T ≥ 0 T\ge0 T ≥ 0 determine F Q μ F_Q^\mu F Q μ , and F Q μ F_Q^\mu F Q μ determines them.
(b) Let h > 0 h>0 h > 0 with h q max ≤ 1 hq_{\max}\le1 h q m a x ≤ 1 , and let n ( N ) n(N) n ( N ) be the composition of X 1 , … , X N X_1,\ldots,X_N X 1 , … , X N , where X 1 ∼ μ X_1\sim\mu X 1 ∼ μ and the transition matrix is I + h Q I+hQ I + h Q . For small ∣ y ∣ |y| ∣ y ∣ and nonzero z ∈ C d z\in\mathbb{C}^d z ∈ C d ,
∑ N ≥ 1 y N E μ ∏ i z i n i ( N ) = h − 1 F Q μ ( x ) , x i = 1 / ( y z i ) − 1 h . \sum_{N\ge1}y^N\mathbb{E}_\mu\prod_i z_i^{n_i(N)}=h^{-1}F_Q^\mu(x),\qquad x_i=\frac{1/(yz_i)-1}{h}. N ≥ 1 ∑ y N E μ i ∏ z i n i ( N ) = h − 1 F Q μ ( x ) , x i = h 1/ ( y z i ) − 1 .
So at a fixed h h h the laws of n ( N ) n(N) n ( N ) for all N ≥ 1 N\ge1 N ≥ 1 determine F Q μ F_Q^\mu F Q μ , and F Q μ F_Q^\mu F Q μ determines them.
{#eq:4.1}
Proof. (a) The function u ( T ) = E e − w ⋅ O ( T ) u(T)=\mathbb{E}\,e^{-w\cdot O(T)} u ( T ) = E e − w ⋅ O ( T ) solves u ′ = ( Q − W ) u u'=(Q-W)u u ′ = ( Q − W ) u with u ( 0 ) = 1 u(0)=1 u ( 0 ) = 1 , by the Feynman and Kac formula, which for a finite chain is the backward equation. For real s s s larger than the real parts of the spectrum of Q − W Q-W Q − W ,
∫ 0 ∞ e − s T μ e T ( Q − W ) 1 d T = μ ( s I − Q + W ) − 1 1 = F Q μ ( s 1 + w ) . \int_{0}^{\infty}e^{-sT}\,\mu e^{T(Q-W)}\mathbf{1}\,\mathrm{d}T=\mu(sI-Q+W)^{-1}\mathbf{1}=F_Q^\mu(s\mathbf{1}+w). ∫ 0 ∞ e − s T μ e T ( Q − W ) 1 d T = μ ( s I − Q + W ) − 1 1 = F Q μ ( s 1 + w ) .
The law of O ( T ) O(T) O ( T ) lives on [ 0 , T ] d [0,T]^d [ 0 , T ] d , so it is determined by its Laplace transform on R d \mathbb{R}^d R d . Hence the laws for all T T T give the continuous functions T ↦ μ e T ( Q − W ) 1 T\mapsto\mu e^{T(Q-W)}\mathbf{1} T ↦ μ e T ( Q − W ) 1 , these give F Q μ F_Q^\mu F Q μ on a nonempty open subset of R d \mathbb{R}^d R d , and a rational function is determined there. Conversely, for each w w w the function s ↦ F Q μ ( s 1 + w ) s\mapsto F_Q^\mu(s\mathbf{1}+w) s ↦ F Q μ ( s 1 + w ) for large s s s is the Laplace transform of T ↦ μ e T ( Q − W ) 1 T\mapsto\mu e^{T(Q-W)}\mathbf{1} T ↦ μ e T ( Q − W ) 1 , which it determines.
(b) With Z = diag z Z=\operatorname{diag}z Z = diag z and P = I + h Q P=I+hQ P = I + h Q we have E μ ∏ i z i n i ( N ) = μ Z ( P Z ) N − 1 1 \mathbb{E}_\mu\prod_i z_i^{n_i(N)}=\mu Z(PZ)^{N-1}\mathbf{1} E μ ∏ i z i n i ( N ) = μ Z ( P Z ) N − 1 1 . Summing the geometric series gives μ y Z ( I − y P Z ) − 1 1 = μ ( ( y Z ) − 1 − P ) − 1 1 \mu yZ(I-yPZ)^{-1}\mathbf{1}=\mu\bigl((yZ)^{-1}-P\bigr)^{-1}\mathbf{1} μ y Z ( I − y P Z ) − 1 1 = μ ( ( y Z ) − 1 − P ) − 1 1 , and ( y Z ) − 1 − I − h Q = h ( diag x − Q ) (yZ)^{-1}-I-hQ=h(\operatorname{diag}x-Q) ( y Z ) − 1 − I − h Q = h ( diag x − Q ) . The laws for all N N N give the power series, hence F Q μ F_Q^\mu F Q μ on an open set of x x x , since z ↦ x z\mapsto x z ↦ x is open for fixed y y y . Conversely F Q μ F_Q^\mu F Q μ gives the power series.
By (a) and (b), each result of this section that assumes equal laws of O ( T ) O(T) O ( T ) for all T T T , or at one T T T (which is the same by Theorem 4.2 ), holds verbatim for equal laws of the counts of I + h Q I+hQ I + h Q for all N N N at one fixed h h h .
One time determines every time
Put P ( s , w ) = det ( s I − Q + W ) \mathcal{P}(s,w)=\det(sI-Q+W) P ( s , w ) = det ( s I − Q + W ) . In the variables ( s , s 1 + w ) (s,s\mathbf{1}+w) ( s , s 1 + w ) it is the polynomial R V ( − ( s 1 + w ) ) R_V(-(s\mathbf{1}+w)) R V ( − ( s 1 + w )) of § 3.1 , which does not involve s s s . So if Q Q Q is irreducible, P \mathcal{P} P is irreducible over C \mathbb{C} C by Lemma 3.1 , and it is monic of degree d d d in s s s , so Lemma 3.2 applies to it.
Theorem 4.2 (one time). Let Q Q Q be an irreducible generator and Q ′ Q' Q ′ any generator on [ d ] [d] [ d ] , with starts μ \mu μ and μ ′ \mu' μ ′ . If O ( T 0 ) O(T_0) O ( T 0 ) has the same law under ( Q , μ ) (Q,\mu) ( Q , μ ) and under ( Q ′ , μ ′ ) (Q',\mu') ( Q ′ , μ ′ ) for one T 0 > 0 T_0>0 T 0 > 0 , then − Q ′ -Q' − Q ′ has the principal minors of − Q -Q − Q , so Q ′ Q' Q ′ is irreducible, and F Q ′ μ ′ = F Q μ F_{Q'}^{\mu'}=F_Q^\mu F Q ′ μ ′ = F Q μ . So the laws agree at every T T T .
Proof. Step 1, the data. By Lemma 4.1(a) the hypothesis says μ e T 0 ( Q − W ) 1 = μ ′ e T 0 ( Q ′ − W ) 1 \mu e^{T_0(Q-W)}\mathbf{1}=\mu'e^{T_0(Q'-W)}\mathbf{1} μ e T 0 ( Q − W ) 1 = μ ′ e T 0 ( Q ′ − W ) 1 for all w ∈ R d w\in\mathbb{R}^d w ∈ R d .
Step 2, one exponential. Let q = max ( q max , q max ′ ) > 0 q=\max(q_{\max},q'_{\max})>0 q = max ( q m a x , q m a x ′ ) > 0 , and for v ∈ R d v\in\mathbb{R}^d v ∈ R d with distinct entries let δ ( v ) \delta(v) δ ( v ) be the least distance between 2 of them. By the theorem of Gershgorin the eigenvalues of V − ϵ Q V-\epsilon Q V − ϵ Q , V = diag v V=\operatorname{diag}v V = diag v , lie within 2 ∣ ϵ ∣ q 2|\epsilon|q 2∣ ϵ ∣ q of the entries of v v v . So for ∣ ϵ ∣ < ϵ 0 ( v ) = δ ( v ) / ( 4 q ) |\epsilon|<\epsilon_0(v)=\delta(v)/(4q) ∣ ϵ ∣ < ϵ 0 ( v ) = δ ( v ) / ( 4 q ) they are simple, given by analytic functions κ i ( ϵ ) \kappa_i(\epsilon) κ i ( ϵ ) with κ i ( 0 ) = v i \kappa_i(0)=v_i κ i ( 0 ) = v i , and so are their spectral projectors E i ( ϵ ) E_i(\epsilon) E i ( ϵ ) . The same holds for Q ′ Q' Q ′ . Fix v 0 v^0 v 0 with distinct entries and v 1 0 v_1^0 v 1 0 the smallest, and a ball B B B around v 0 v^0 v 0 whose closure consists of such vectors. Then ϵ ∗ = min ϵ 0 > 0 \epsilon_*=\min\epsilon_0>0 ϵ ∗ = min ϵ 0 > 0 on B B B , because δ \delta δ is continuous and positive on the closure. This is what makes the set U U U below open.
For v ∈ B v\in B v ∈ B and t > 1 / ϵ ∗ t>1/\epsilon_* t > 1/ ϵ ∗ the eigenvalues of Q − t V Q-tV Q − t V are − t κ i ( 1 / t ) -t\kappa_i(1/t) − t κ i ( 1/ t ) and
e T 0 t v 1 μ e T 0 ( Q − t V ) 1 = ϕ v ( 1 / t ) + O ( e − T 0 t δ ( v ) / 2 ) , ϕ v ( ϵ ) = μ E 1 ( ϵ ) 1 exp ( − T 0 κ 1 ( ϵ ) − v 1 ϵ ) , e^{T_0tv_1}\mu e^{T_0(Q-tV)}\mathbf{1}=\phi_v(1/t)+O(e^{-T_0t\delta(v)/2}),\qquad
\phi_v(\epsilon)=\mu E_1(\epsilon)\mathbf{1}\exp\left(-T_0\frac{\kappa_1(\epsilon)-v_1}{\epsilon}\right), e T 0 t v 1 μ e T 0 ( Q − t V ) 1 = ϕ v ( 1/ t ) + O ( e − T 0 t δ ( v ) /2 ) , ϕ v ( ϵ ) = μ E 1 ( ϵ ) 1 exp ( − T 0 ϵ κ 1 ( ϵ ) − v 1 ) ,
where ϕ v \phi_v ϕ v is analytic for ∣ ϵ ∣ < ϵ ∗ |\epsilon|<\epsilon_* ∣ ϵ ∣ < ϵ ∗ . With ϕ v ′ \phi'_v ϕ v ′ formed from Q ′ Q' Q ′ and μ ′ \mu' μ ′ , Step 1 gives ϕ v ( ϵ ) − ϕ v ′ ( ϵ ) = O ( e − c / ϵ ) \phi_v(\epsilon)-\phi'_v(\epsilon)=O(e^{-c/\epsilon}) ϕ v ( ϵ ) − ϕ v ′ ( ϵ ) = O ( e − c / ϵ ) as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 . Every Taylor coefficient of ϕ v − ϕ v ′ \phi_v-\phi'_v ϕ v − ϕ v ′ at 0 is therefore 0, and ϕ v = ϕ v ′ \phi_v=\phi'_v ϕ v = ϕ v ′ . On the open cone U = { t v ∣ v ∈ B , t > 1 / ϵ ∗ } U=\{tv\mid v\in B,\ t>1/\epsilon_*\} U = { t v ∣ v ∈ B , t > 1/ ϵ ∗ } let θ ( w ) \theta(w) θ ( w ) be the eigenvalue of Q − W Q-W Q − W within 2 q 2q 2 q of − w 1 -w_1 − w 1 , which is simple and real since its conjugate is also an eigenvalue there, and let χ ( w ) = μ E ( w ) 1 \chi(w)=\mu E(w)\mathbf{1} χ ( w ) = μ E ( w ) 1 with E ( w ) E(w) E ( w ) its spectral projector. Define θ ′ \theta' θ ′ and χ ′ \chi' χ ′ from Q ′ Q' Q ′ and μ ′ \mu' μ ′ . We have shown that
χ ( w ) e T 0 θ ( w ) = χ ′ ( w ) e T 0 θ ′ ( w ) , w ∈ U . (2) \chi(w)e^{T_0\theta(w)}=\chi'(w)e^{T_0\theta'(w)},\qquad w\in U. \tag*{(2)} χ ( w ) e T 0 θ ( w ) = χ ′ ( w ) e T 0 θ ′ ( w ) , w ∈ U . (2)
Step 3, the residue. Write μ ( s I − Q + W ) − 1 1 = N μ / P \mu(sI-Q+W)^{-1}\mathbf{1}=N_\mu/\mathcal{P} μ ( s I − Q + W ) − 1 1 = N μ / P with N μ = μ adj ( s I − Q + W ) 1 N_\mu=\mu\operatorname{adj}(sI-Q+W)\mathbf{1} N μ = μ adj ( s I − Q + W ) 1 . Then χ = N μ ( θ , w ) / ∂ s P ( θ , w ) \chi=N_\mu(\theta,w)/\partial_s\mathcal{P}(\theta,w) χ = N μ ( θ , w ) / ∂ s P ( θ , w ) , the residue at the simple pole s = θ ( w ) s=\theta(w) s = θ ( w ) . The polynomial N μ N_\mu N μ has degree d − 1 d-1 d − 1 in s s s and leading coefficient μ ⋅ 1 = 1 \mu\cdot\mathbf{1}=1 μ ⋅ 1 = 1 , so P \mathcal{P} P does not divide it, and by Lemma 3.2 N μ ( θ ( w ) , w ) N_\mu(\theta(w),w) N μ ( θ ( w ) , w ) does not vanish identically on any open subset of U U U . So there is a ball U 1 ⊆ U U_1\subseteq U U 1 ⊆ U on which χ ≠ 0 \chi\ne0 χ = 0 , and then χ ′ ≠ 0 \chi'\ne0 χ ′ = 0 by (2) .
Step 4, transcendence. Fix w 0 ∈ U 1 w^0\in U_1 w 0 ∈ U 1 and ζ ∈ R d \zeta\in\mathbb{R}^d ζ ∈ R d , and put f ( r ) = T 0 ( θ ′ − θ ) ( w 0 + r ζ ) f(r)=T_0(\theta'-\theta)(w^0+r\zeta) f ( r ) = T 0 ( θ ′ − θ ) ( w 0 + r ζ ) and g ( r ) = ( χ / χ ′ ) ( w 0 + r ζ ) g(r)=(\chi/\chi')(w^0+r\zeta) g ( r ) = ( χ / χ ′ ) ( w 0 + r ζ ) for real r r r near 0. Both are real-analytic, and both are algebraic over C ( r ) \mathbb{C}(r) C ( r ) , since θ \theta θ and θ ′ \theta' θ ′ are roots of polynomials in s s s with coefficients in C [ r ] \mathbb{C}[r] C [ r ] , and χ , χ ′ \chi,\chi' χ , χ ′ are rational in them and r r r . By (2) , e f = g e^f=g e f = g . We claim that f f f is constant. The field C ( r , f , g ) \mathbb{C}(r,f,g) C ( r , f , g ) is the field of meromorphic functions of a compact Riemann surface, on which f f f and g g g are meromorphic, and e f = g e^f=g e f = g continues to the surface minus the poles of f f f and g g g . If f f f were not constant it would have a pole p p p , with f = a τ − k ( 1 + O ( τ ) ) f=a\tau^{-k}(1+O(\tau)) f = a τ − k ( 1 + O ( τ )) , a ≠ 0 a\ne0 a = 0 , k ≥ 1 k\ge1 k ≥ 1 , in a local coordinate τ \tau τ at p p p . Along the directions where a τ − k > 0 a\tau^{-k}>0 a τ − k > 0 the function ∣ e f ∣ |e^f| ∣ e f ∣ grows faster than every power of 1 / ∣ τ ∣ 1/|\tau| 1/∣ τ ∣ , while g g g is meromorphic at p p p . So f f f is constant. As ζ \zeta ζ is arbitrary, the gradient of θ ′ − θ \theta'-\theta θ ′ − θ vanishes on U 1 U_1 U 1 , and θ ′ = θ + c \theta'=\theta+c θ ′ = θ + c there for a real constant c c c .
Step 5, the minors. Put P ′ ( s , w ) = det ( s I − Q ′ + W ) \mathcal{P}'(s,w)=\det(sI-Q'+W) P ′ ( s , w ) = det ( s I − Q ′ + W ) . The polynomial P ′ ( s + c , w ) \mathcal{P}'(s+c,w) P ′ ( s + c , w ) vanishes at s = θ ( w ) s=\theta(w) s = θ ( w ) for every w ∈ U 1 w\in U_1 w ∈ U 1 . This holds only for real w w w , and Lemma 3.2 turns it into an identity of polynomials. It gives that P \mathcal{P} P divides P ′ ( s + c , w ) \mathcal{P}'(s+c,w) P ′ ( s + c , w ) , and both are monic of degree d d d in s s s , so they are equal. At s = 0 s=0 s = 0 this says that − Q ′ + c I -Q'+cI − Q ′ + c I and − Q -Q − Q have the same principal minors, and at w = 0 w=0 w = 0 that the spectrum of Q ′ Q' Q ′ is that of Q Q Q shifted by c c c . Every eigenvalue of a generator has real part at most 0. Since 0 is an eigenvalue of Q ′ Q' Q ′ , − c -c − c is one of Q Q Q , so c ≥ 0 c\ge0 c ≥ 0 , and since 0 is an eigenvalue of Q Q Q , c c c is one of Q ′ Q' Q ′ , so c ≤ 0 c\le0 c ≤ 0 . Hence c = 0 c=0 c = 0 , − Q ′ -Q' − Q ′ has the principal minors of − Q -Q − Q , and Q ′ Q' Q ′ is irreducible by Corollary 3.7 (a).
Step 6, the transforms. Now P ′ = P \mathcal{P}'=\mathcal{P} P ′ = P , θ ′ = θ \theta'=\theta θ ′ = θ , and χ = χ ′ \chi=\chi' χ = χ ′ on U 1 U_1 U 1 by (2) . So N μ − N μ ′ ′ N_\mu-N'_{\mu'} N μ − N μ ′ ′ vanishes at s = θ ( w ) s=\theta(w) s = θ ( w ) on U 1 U_1 U 1 , and by Lemma 3.2 it is divisible by P \mathcal{P} P . Its degree in s s s is less than d d d , so it is 0. Hence F Q μ ( s 1 + w ) = F Q ′ μ ′ ( s 1 + w ) F_Q^\mu(s\mathbf{1}+w)=F_{Q'}^{\mu'}(s\mathbf{1}+w) F Q μ ( s 1 + w ) = F Q ′ μ ′ ( s 1 + w ) , and Lemma 4.1(a) gives the laws at every T T T .
A start without renewal blocks
Definition 4.3 (renewal block). Let Q Q Q be irreducible and μ \mu μ a start. A set B B B with 2 ≤ ∣ B ∣ ≤ d − 1 2\le|B|\le d-1 2 ≤ ∣ B ∣ ≤ d − 1 is a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) if Q [ B , B c ] = 1 r ⊤ Q[B,B^c]=\mathbf{1}r^\top Q [ B , B c ] = 1 r ⊤ , Q [ B c , B ] = c ρ ⊤ Q[B^c,B]=c\rho^\top Q [ B c , B ] = c ρ ⊤ and μ B = m ρ \mu_B=m\rho μ B = m ρ for some r , c ∈ [ 0 , ∞ ) B c r,c\in[0,\infty)^{B^c} r , c ∈ [ 0 , ∞ ) B c , a law ρ \rho ρ on B B B and m ≥ 0 m\ge0 m ≥ 0 . So every state of B B B leaves B B B at the same rates, every jump into B B B lands with the law ρ \rho ρ , and μ \mu μ is a multiple of ρ \rho ρ on B B B , possibly 0.
Since Q Q Q is irreducible, c ≠ 0 c\ne0 c = 0 , so ρ \rho ρ is determined by Q Q Q . Put
M ( Q , μ ) = ( Q 1 μ 0 ) , M(Q,\mu)=\begin{pmatrix} Q & \mathbf{1} \\ \mu& 0 \end{pmatrix}, M ( Q , μ ) = ( Q μ 1 0 ) ,
indexed by [ d ] ∪ { 0 } [d]\cup\{0\} [ d ] ∪ { 0 } . A cut of a matrix of order at least 4 is a partition of its indices into 2 sets of at least 2 elements such that both off-diagonal blocks have rank at most 1, as in Loewy [24 ] .
Lemma 4.4 (the bordered matrix with the start). Let Q Q Q be irreducible and μ \mu μ a start.
(a) det ( diag ( x , t ) − M ( Q , μ ) ) = P Q ( x ) ( t − F Q μ ( x ) ) \det(\operatorname{diag}(x,t)-M(Q,\mu))=P_Q(x)(t-F_Q^\mu(x)) det ( diag ( x , t ) − M ( Q , μ )) = P Q ( x ) ( t − F Q μ ( x )) with P Q ( x ) = det ( diag x − Q ) P_Q(x)=\det(\operatorname{diag}x-Q) P Q ( x ) = det ( diag x − Q ) .
(b) For a generator Q ′ Q' Q ′ and a start μ ′ \mu' μ ′ , O ( T ) O(T) O ( T ) has the same law under ( Q ′ , μ ′ ) (Q',\mu') ( Q ′ , μ ′ ) as under ( Q , μ ) (Q,\mu) ( Q , μ ) , for one T > 0 T>0 T > 0 or equivalently every T T T , if and only if M ( Q ′ , μ ′ ) M(Q',\mu') M ( Q ′ , μ ′ ) has the principal minors of M ( Q , μ ) M(Q,\mu) M ( Q , μ ) . Then μ ′ = μ \mu'=\mu μ ′ = μ .
(c) M ( Q , μ ) M(Q,\mu) M ( Q , μ ) is irreducible, and a set B ⊆ [ d ] B \subseteq[d] B ⊆ [ d ] is the side avoiding ∂ \partial ∂ of a cut of M ( Q , μ ) M(Q,\mu) M ( Q , μ ) if and only if B B B is a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) .
Proof. (a) For x x x with large entries the formula of Schur gives det ( diag x − Q ) ( t − μ ( diag x − Q ) − 1 1 ) \det(\operatorname{diag} x-Q)\left(t-\mu(\operatorname{diag} x-Q)^{-1}\mathbf{1}\right) det ( diag x − Q ) ( t − μ ( diag x − Q ) − 1 1 ) , and both sides are polynomials.
(b) The left side of (a) is multiaffine in ( x , t ) (x,t) ( x , t ) , its coefficients are the principal minors of M ( Q , μ ) M(Q,\mu) M ( Q , μ ) up to sign, and its coefficient of t t t is P Q P_Q P Q . So equal principal minors mean P Q ′ = P Q P_{Q'}=P_Q P Q ′ = P Q and F Q ′ μ ′ = F Q μ F_{Q'}^{\mu'}=F_Q^\mu F Q ′ μ ′ = F Q μ . Equal laws give both by Theorem 4.2 , and the converse is Lemma 4.1(a). With m i = 1 / x i m_i=1/x_i m i = 1/ x i , the expansion ( diag x − Q ) − 1 = ∑ k ≥ 0 ( diag m Q ) k diag m (\operatorname{diag} x-Q)^{-1}=\sum_{k\geq0}(\operatorname{diag} mQ)^k\operatorname{diag}m ( diag x − Q ) − 1 = ∑ k ≥ 0 ( diag m Q ) k diag m for large x x x gives F Q μ = μ ⋅ m + O ( ∣ m ∣ 2 ) F_Q^\mu=\mu\cdot m+O(|m|^2) F Q μ = μ ⋅ m + O ( ∣ m ∣ 2 ) , so μ ′ = μ \mu'=\mu μ ′ = μ .
(c) Every i i i has the edge i → ∂ i\to\partial i → ∂ , ∂ \partial ∂ has edges into the support of μ \mu μ , and Q Q Q is irreducible. Let J = B c ∪ { ∂ } J=B^c\cup\{\partial\} J = B c ∪ { ∂ } . Both sides have at least 2 elements exactly when 2 ≤ ∣ B ∣ ≤ d − 1 2\leq|B|\leq d-1 2 ≤ ∣ B ∣ ≤ d − 1 . The column ∂ \partial ∂ of M [ B , J ] M[B,J] M [ B , J ] is 1 B \mathbf{1}_B 1 B , so M [ B , J ] M[B,J] M [ B , J ] has rank at most 1 exactly when Q [ B , B c ] = 1 r ⊤ Q[B,B^c]=\mathbf{1}r^\top Q [ B , B c ] = 1 r ⊤ . The rows of M [ J , B ] M[J,B] M [ J , B ] are the rows Q [ y , B ] ≥ 0 Q[y,B]\geq0 Q [ y , B ] ≥ 0 for y ∉ B y\notin B y ∈ / B , not all 0, and μ B ≥ 0 \mu_B\geq0 μ B ≥ 0 . They span a space of dimension at most 1 exactly when they are multiples c y ρ c_y\rho c y ρ and m ρ m\rho m ρ of one law ρ \rho ρ , with c y , m ≥ 0 c_y,m\geq0 c y , m ≥ 0 . □
Theorem 4.5 (a start without renewal blocks). Let Q Q Q be irreducible, let μ \mu μ be a start, and let Q ′ Q' Q ′ be a generator and μ ′ \mu' μ ′ a start such that O ( T 0 ) O(T_0) O ( T 0 ) has the same law under ( Q ′ , μ ′ ) (Q',\mu') ( Q ′ , μ ′ ) as under ( Q , μ ) (Q,\mu) ( Q , μ ) for one T 0 > 0 T_0>0 T 0 > 0 . Then μ ′ = μ \mu'=\mu μ ′ = μ . If ( Q , μ ) (Q,\mu) ( Q , μ ) has no renewal block, then Q ′ = Q Q'=Q Q ′ = Q , or μ = π \mu=\pi μ = π and Q ′ = Q ∗ Q'=Q^* Q ′ = Q ∗ . For a fixed Q Q Q , every start outside a finite union of proper linear subspaces of R d \mathbb{R}^d R d has no renewal block and differs from π \pi π . So does μ = e y \mu=e_y μ = e y when every set B B B with uniform exit rates and rank-one entries contains y y y and has an entry law other than e y e_y e y .
Proof. Let M = M ( Q , μ ) M=M(Q,\mu) M = M ( Q , μ ) and M ′ = M ( Q ′ , μ ) M'=M(Q',\mu) M ′ = M ( Q ′ , μ ) , which have the same principal minors by Lemma 4.4 (b), and M M M is irreducible. If d ≥ 3 d\geq3 d ≥ 3 , then M M M has order at least 4 and no cut by Lemma 4.4 (c), and Loewy’s theorem [24 Theorem 1] , with no condition on M ′ M' M ′ , gives an invertible diagonal E E E with M ′ = E − 1 M E M'=E^{-1}ME M ′ = E − 1 M E or M ′ = E − 1 M ⊤ E M'=E^{-1}M^\top E M ′ = E − 1 M ⊤ E . If d ≤ 2 d\leq2 d ≤ 2 , the theorem of Hartfiel and Loewy [20 Theorem 3] , as in the proof of Corollary 3.7 (c), gives the same. In the first case the entries ( i , ∂ ) (i,\partial) ( i , ∂ ) give 1 = E ∂ / E i 1=E_\partial/E_i 1 = E ∂ / E i , so E E E is a multiple of I I I and Q ′ = Q Q'=Q Q ′ = Q . In the second case they give 1 = μ i E ∂ / E i 1=\mu_iE_\partial/E_i 1 = μ i E ∂ / E i , so μ i ≠ 0 \mu_i\ne0 μ i = 0 , E i = μ i E ∂ E_i=\mu_iE_\partial E i = μ i E ∂ and q i j ′ = μ j q j i / μ i q'_{ij}=\mu_jq_{ji}/\mu_i q ij ′ = μ j q j i / μ i . The rows of Q ′ Q' Q ′ sum to 0, so μ Q = 0 \mu Q=0 μ Q = 0 , μ = π \mu=\pi μ = π and Q ′ = Q ∗ Q'=Q^* Q ′ = Q ∗ .
A set B B B with uniform exit rates and rank-one entries is a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) only if μ B \mu_B μ B lies on the line of ρ B \rho_B ρ B , and this line is a proper subspace of R B \mathbb{R}^B R B . There are finitely many such sets, and the starts proportional to π \pi π form a line as well. For μ = e y \mu=e_y μ = e y and such a set B B B , μ B = e y \mu_B=e_y μ B = e y is not a multiple of ρ B \rho_B ρ B , and e y ≠ π e_y\ne\pi e y = π since π > 0 \pi>0 π > 0 and d ≥ 2 d\geq2 d ≥ 2 . □
A renewal block can be lumped to one state. Let A A A be a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) with r , c , ρ , m r,c,\rho,m r , c , ρ , m as in Definition 4.3 and κ A = r ⋅ 1 > 0 \kappa_A=r\cdot\mathbf{1}>0 κ A = r ⋅ 1 > 0 , so that the rows A A A of Q 1 = 0 Q\mathbf{1}=0 Q 1 = 0 give Q A 1 = − κ A 1 Q_A\mathbf{1}=-\kappa_A\mathbf{1} Q A 1 = − κ A 1 . The lumped pair ( Q / A , μ / A ) (Q/A,\mu/A) ( Q / A , μ / A ) lives on A c ∪ { a } A^c\cup\{a\} A c ∪ { a } . The generator Q / A Q/A Q / A has the off-diagonal entries of Q Q Q on A c A^c A c , the entries ( Q / A ) y a = c y (Q/A)_{ya}=c_y ( Q / A ) y a = c y and ( Q / A ) a y = r y (Q/A)_{ay}=r_y ( Q / A ) a y = r y , zero row sums, and the start is μ \mu μ on A c A^c A c and m m m at a a a . Put g A ( x A ) = ρ ( diag x A − Q A ) − 1 1 g_A(x_A)=\rho(\operatorname{diag}x_A-Q_A)^{-1}\mathbf{1} g A ( x A ) = ρ ( diag x A − Q A ) − 1 1 , the transform of one sojourn in A A A .
Lemma 4.6 (lumping). For x ∈ ( 0 , ∞ ) d x\in(0,\infty)^d x ∈ ( 0 , ∞ ) d we have g A ( x A ) > 0 g_A(x_A)>0 g A ( x A ) > 0 , u A = 1 / g A ( x A ) − κ A ≥ min i ∈ A x i u_A=1/g_A(x_A)-\kappa_A\geq\min_{i\in A}x_i u A = 1/ g A ( x A ) − κ A ≥ min i ∈ A x i and F Q μ ( x ) = F Q / A μ / A ( x A c , u A ) F_Q^\mu(x)=F_{Q/A}^{\mu/A}(x_{A^c},u_A) F Q μ ( x ) = F Q / A μ / A ( x A c , u A ) .
Proof. The matrix X A = diag x A − Q A X_A=\operatorname{diag}x_A-Q_A X A = diag x A − Q A is strictly diagonally dominant with nonpositive off-diagonal entries, so X A − 1 ≥ 0 X_A^{-1}\geq0 X A − 1 ≥ 0 and g A > 0 g_A>0 g A > 0 . If x A ≥ s 1 x_A\geq s\mathbf{1} x A ≥ s 1 , then X A 1 ≥ ( s + κ A ) 1 X_A\mathbf{1}\geq(s+\kappa_A)\mathbf{1} X A 1 ≥ ( s + κ A ) 1 , so g A ≤ 1 / ( s + κ A ) g_A\leq1/(s+\kappa_A) g A ≤ 1/ ( s + κ A ) .
Let z = ( diag x − Q ) − 1 1 z=(\operatorname{diag}x-Q)^{-1}\mathbf{1} z = ( diag x − Q ) − 1 1 and z ′ = z A c z'=z_{A^c} z ′ = z A c . The rows A A A give X A z A = ( 1 + r ⋅ z ′ ) 1 X_Az_A=(1+r\cdot z')\mathbf{1} X A z A = ( 1 + r ⋅ z ′ ) 1 , so ρ ⋅ z A = ζ \rho\cdot z_A=\zeta ρ ⋅ z A = ζ with ζ = ( 1 + r ⋅ z ′ ) g A \zeta=(1+r\cdot z')g_A ζ = ( 1 + r ⋅ z ′ ) g A . The rows y ∉ A y\notin A y ∈ / A involve z A z_A z A only through c y ρ ⋅ z A = c y ζ c_y\rho\cdot z_A=c_y\zeta c y ρ ⋅ z A = c y ζ , and ( u A + κ A ) ζ − r ⋅ z ′ = 1 (u_A+\kappa_A)\zeta-r\cdot z'=1 ( u A + κ A ) ζ − r ⋅ z ′ = 1 . So ( z ′ , ζ ) (z',\zeta) ( z ′ , ζ ) solves ( diag ( x A c , u A ) − Q / A ) ( z ′ , ζ ) = 1 (\operatorname{diag}(x_{A^c},u_A)-Q/A)(z',\zeta)=\mathbf{1} ( diag ( x A c , u A ) − Q / A ) ( z ′ , ζ ) = 1 , whose matrix is strictly diagonally dominant, and F Q μ = μ A c ⋅ z ′ + m ζ = F Q / A μ / A ( x A c , u A ) F_Q^\mu=\mu_{A^c}\cdot z'+m\zeta=F_{Q/A}^{\mu/A}(x_{A^c},u_A) F Q μ = μ A c ⋅ z ′ + m ζ = F Q / A μ / A ( x A c , u A ) . □
The stationary start and memoryless blocks
Theorem 4.7 (the stationary start). Let Q Q Q be irreducible. Then O ( T ) O(T) O ( T ) has the same stationary law under Q ∗ Q^* Q ∗ as under Q Q Q for every T T T .
Proof. By Lemma 4.1(a) it suffices that F Q ∗ ( x ) = π D − 1 ( diag x − Q T ) − 1 D 1 = 1 T ( diag x − Q T ) − 1 π = F Q ( x ) F_{Q^*}(x)=\pi D^{-1}(\operatorname{diag}x-Q^{\mathsf T})^{-1}D\mathbf{1}=\mathbf{1}^{\mathsf T}(\operatorname{diag}x-Q^{\mathsf T})^{-1}\pi=\ F_Q(x) F Q ∗ ( x ) = π D − 1 ( diag x − Q T ) − 1 D 1 = 1 T ( diag x − Q T ) − 1 π = F Q ( x ) .
Definition 4.8 (memoryless block). A set B B B of states with 2 ≤ ∣ B ∣ ≤ d − 1 2\leq|B|\leq d-1 2 ≤ ∣ B ∣ ≤ d − 1 is a memoryless block of the irreducible Q Q Q if there are κ > 0 \kappa>0 κ > 0 , a law ν \nu ν on B c B^c B c and c ∈ [ 0 , ∞ ) B c c\in[0,\infty)^{B^c} c ∈ [ 0 , ∞ ) B c such that q i y = κ ν y q_{iy}=\kappa\nu_y q i y = κ ν y and q y i = c y π i / π ( B ) q_{yi}=c_y\pi_i/\pi(B) q y i = c y π i / π ( B ) for all i ∈ B i\in B i ∈ B and y ∉ B y\notin B y ∈ / B . That is, every state of B B B leaves B B B at the same rate and with the same landing law, and every jump into B B B lands with the law π B / π ( B ) \pi_B/\pi(B) π B / π ( B ) . We write Q [ B ] Q^{[B]} Q [ B ] for Q Q Q with the block Q B Q_B Q B replaced by Q B ∗ = D B − 1 Q B T D B Q_B^*=D_B^{-1}Q_B^{\mathsf T}D_B Q B ∗ = D B − 1 Q B T D B , where D B D_B D B is the diagonal matrix of π B \pi_B π B , and the other entries kept.
A memoryless block is a strong lumpability. In the terms of Marin and Rossi [25 ] , after Buchholz [7 ] , B B B is a memoryless block of Q Q Q if and only if the partition into B B B and the single states outside B B B is a strong lumpability for Q Q Q and for Q ∗ Q^* Q ∗ . For y ∉ B y\notin B y ∈ / B the first says that q i y q_{iy} q i y , and the second that π y q y i / π i \pi_yq_{yi}/\pi_i π y q y i / π i , does not depend on i ∈ B i\in B i ∈ B .
Theorem 4.9 (reversal of a memoryless block). Let B B B be a memoryless block of the irreducible Q Q Q . Then Q [ B ] Q^{[B]} Q [ B ] is an irreducible generator with stationary law π \pi π , and F Q [ B ] μ = F Q μ F^{\mu}_{Q^{[B]}}=F^{\mu}_Q F Q [ B ] μ = F Q μ for every start μ \mu μ with μ B \mu_B μ B proportional to π B \pi_B π B , possibly 0 0 0 . So O ( T ) O(T) O ( T ) has the same law under ( Q , μ ) (Q,\mu) ( Q , μ ) and ( Q [ B ] , μ ) (Q^{[B]},\mu) ( Q [ B ] , μ ) for every T T T , in particular for μ = π \mu=\pi μ = π , and so do the counts of I + h Q I+hQ I + h Q and I + h Q [ B ] I+hQ^{[B]} I + h Q [ B ] for every N N N and every admissible h h h . Moreover Q [ B ] = Q Q^{[B]}=Q Q [ B ] = Q exactly when Q B ∗ = Q B Q_B^*=Q_B Q B ∗ = Q B , which holds when ∣ B ∣ = 2 |B|=2 ∣ B ∣ = 2 , and Q [ B ] = Q ∗ Q^{[B]}=Q^* Q [ B ] = Q ∗ when ∣ B c ∣ = 1 |B^c|=1 ∣ B c ∣ = 1 .
Proof. Put ρ = π B / π ( B ) \rho=\pi_B/\pi(B) ρ = π B / π ( B ) , so Q [ B , B c ] = κ 1 ν T Q[B,B^c]=\kappa\mathbf{1}\nu^{\mathsf T} Q [ B , B c ] = κ 1 ν T and Q [ B c , B ] = c ρ Q[B^c,B]=c\rho Q [ B c , B ] = c ρ . The flux out of B B B equals the flux in, so κ π ( B ) = ∑ y π y c y \kappa\pi(B)=\sum_y\pi_yc_y κπ ( B ) = ∑ y π y c y . The columns B B B of π Q = 0 \pi Q=0 π Q = 0 then give π B Q B = − κ π B \pi_BQ_B=-\kappa\pi_B π B Q B = − κ π B , and the rows give Q B 1 = − κ 1 Q_B\mathbf{1}=-\kappa\mathbf{1} Q B 1 = − κ 1 . Hence Q B ∗ 1 = D B − 1 Q B T π B T = − κ 1 Q_B^*\mathbf{1}=D_B^{-1}Q_B^{\mathsf T}\pi_B^{\mathsf T}=-\kappa\mathbf{1} Q B ∗ 1 = D B − 1 Q B T π B T = − κ 1 , so the rows of Q [ B ] Q^{[B]} Q [ B ] sum to 0 0 0 , and π B Q B ∗ = 1 T Q B T D B = − κ π B \pi_BQ_B^*=\mathbf{1}^{\mathsf T}Q_B^{\mathsf T}D_B=-\kappa\pi_B π B Q B ∗ = 1 T Q B T D B = − κ π B , which the inflow κ π B \kappa\pi_B κ π B cancels in the columns B B B of π Q [ B ] \pi Q^{[B]} π Q [ B ] . The other columns do not change. The off-diagonal entries π j q j i / π i \pi_jq_{ji}/\pi_i π j q j i / π i of Q B ∗ Q_B^* Q B ∗ are nonnegative. The generator Q [ B ] Q^{[B]} Q [ B ] is irreducible. It has the same jumps as Q Q Q out of B B B , into B B B and inside B c B^c B c , and κ > 0 \kappa>0 κ > 0 and c ≠ 0 c\neq0 c = 0 since Q Q Q is irreducible. Take states s s s and t t t . If s ∈ B s\in B s ∈ B , jump out of B B B first, which is possible from every state of B B B . A path of Q Q Q between two states of B c B^c B c stays a path of Q [ B ] Q^{[B]} Q [ B ] when each of its sojourns in B B B is cut to its entry state, since the jumps out of B B B have the same rates from every state of B B B . So we reach every state of B c B^c B c . If t ∈ B t\in B t ∈ B , go to a state y y y with c y > 0 c_y>0 c y > 0 and jump to t t t , which is possible since ρ t > 0 \rho_t>0 ρ t > 0 .
Let μ B \mu_B μ B be proportional to π B \pi_B π B . Then B B B is a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) with entry law ρ \rho ρ , and of ( Q [ B ] , μ ) (Q^{[B]},\mu) ( Q [ B ] , μ ) with the same data off B × B B\times B B × B , so Q [ B ] / B = Q / B Q^{[B]}/B=Q/B Q [ B ] / B = Q / B . The sojourn transform of Q [ B ] Q^{[B]} Q [ B ] is ρ D B − 1 ( diag x B − Q B T ) − 1 D B 1 = π B ( diag x B − Q B ) − 1 1 / π ( B ) = g B \rho D_B^{-1}(\operatorname{diag}x_B-Q_B^{\mathsf T})^{-1}D_B\mathbf{1}=\pi_B(\operatorname{diag}x_B-Q_B)^{-1}\mathbf{1}/\pi(B)=g_B ρ D B − 1 ( diag x B − Q B T ) − 1 D B 1 = π B ( diag x B − Q B ) − 1 1 / π ( B ) = g B , and Lemma 4.6 for both gives F Q [ B ] μ = F Q μ F^{\mu}_{Q^{[B]}}=F^\mu_Q F Q [ B ] μ = F Q μ . The statement on the counts is Lemma 4.1(b).
If ∣ B ∣ = 2 |B|=2 ∣ B ∣ = 2 , then Q B + κ I Q_B+\kappa I Q B + κ I is a generator on 2 2 2 states with stationary law ρ \rho ρ , hence reversible. If B c = { y } B^c=\{y\} B c = { y } , then q i y ∗ = π y q y i / π ( B ) = κ = q i y q_{iy}^*=\pi_yq_{yi}/\pi(B)=\kappa=q_{iy} q i y ∗ = π y q y i / π ( B ) = κ = q i y and q y i ∗ = π i κ / π y = c y π i / π ( B ) = q y i q_{yi}^*=\pi_i\kappa/\pi_y=c_y\pi_i/\pi(B)=q_{yi} q y i ∗ = π i κ / π y = c y π i / π ( B ) = q y i , so Q [ B ] = Q ∗ Q^{[B]}=Q^* Q [ B ] = Q ∗ . □ \square □
Remark 4.10 (memoryless blocks are sides of cuts). If ∣ B c ∣ ≥ 2 |B^c|\geq2 ∣ B c ∣ ≥ 2 , then B ∪ B c B\cup B^c B ∪ B c is a cut of Q Q Q , since Q [ B , B c ] = κ 1 ν T Q[B,B^c]=\kappa\mathbf{1}\nu^{\mathsf T} Q [ B , B c ] = κ 1 ν T and Q [ B c , B ] = c π B T / π ( B ) Q[B^c,B]=c\pi_B^{\mathsf T}/\pi(B) Q [ B c , B ] = c π B T / π ( B ) have rank one.
Example 4.11 (five states). Let d = 5 d=5 d = 5 and B = { 1 , 2 , 3 } B=\{1,2,3\} B = { 1 , 2 , 3 } . Inside B B B put q 12 = q 23 = q 31 = 2 q_{12}=q_{23}=q_{31}=2 q 12 = q 23 = q 31 = 2 and q 21 = q 32 = q 13 = 1 q_{21}=q_{32}=q_{13}=1 q 21 = q 32 = q 13 = 1 . Each state of B B B jumps to 4 4 4 at rate 1 1 1 and to 5 5 5 at rate 2 2 2 . State 4 4 4 jumps to each state of B B B at rate 1 and to 5 at rate 1, and state 5 jumps to each state of B B B at rate 2 and to 4 at rate 4. The balance equations give π = ( 4 , 4 , 4 , 6 , 3 ) / 21 \pi= (4, 4, 4, 6, 3)/21 π = ( 4 , 4 , 4 , 6 , 3 ) /21 . So B B B is a memoryless block with κ = 3 \kappa= 3 κ = 3 , ν = ( 1 / 3 , 2 / 3 ) \nu= (1/3, 2/3) ν = ( 1/3 , 2/3 ) and c = ( 3 , 6 ) c = (3, 6) c = ( 3 , 6 ) , and since π B \pi_B π B is uniform, Q [ B ] Q^{[B]} Q [ B ] is Q Q Q with the block Q B Q_B Q B transposed. It differs from Q Q Q , since Q B Q_B Q B is not reversible, and from Q ∗ Q^* Q ∗ , since q 14 = 1 q_{14} = 1 q 14 = 1 while q 14 ∗ = π 4 q 41 / π 1 = 3 / 2 q^*_{14} = \pi_4q_{41}/\pi_1 = 3/2 q 14 ∗ = π 4 q 41 / π 1 = 3/2 . By Theorem 4.9 the stationary laws of O ( T ) O(T) O ( T ) agree for every T T T , and so do the laws of the counts of I + h Q I + hQ I + h Q and I + h Q [ B ] I + hQ^{[B]} I + h Q [ B ] from π \pi π for every N N N and every h ≤ 1 / 10 h \le1/10 h ≤ 1/10 .
The reversals of memoryless blocks are the only obstruction.
Theorem 4.12 (the stationary fiber). Let Q Q Q and Q ′ Q' Q ′ be irreducible generators on [ d ] [d] [ d ] . Then O ( T ) O(T) O ( T ) has the same law under Q Q Q and under Q ′ Q' Q ′ , each started from its stationary law, for one T > 0 T > 0 T > 0 or equivalently for every T T T , if and only if Q ′ Q' Q ′ is reached from Q Q Q or from Q ∗ Q^* Q ∗ by finitely many reversals of memoryless blocks, each a memoryless block of the current generator. Theorem 4.17 counts these generators.
The proof puts the stationary transform into a determinant by adding one index. Let π \pi π be the stationary law of Q Q Q , put e = ( π i 1 / 2 ) i ∈ [ d ] e = (\pi_i^{1/2})_{i\in[d]} e = ( π i 1/2 ) i ∈ [ d ] and K = D π 1 / 2 Q D π − 1 / 2 K = D_\pi^{1/2}QD_\pi^{-1/2} K = D π 1/2 Q D π − 1/2 , and let
H ( Q ) = ( K e e T 0 ) H(Q) = \begin{pmatrix} K & e \\ e^\mathsf{T} & 0 \end{pmatrix} H ( Q ) = ( K e T e 0 )
a matrix indexed by [ d ] ∪ { ∂ } [d]\cup\{\partial\} [ d ] ∪ { ∂ } . Then K e = 0 = e T K Ke = 0 = e^\mathsf{T}K K e = 0 = e T K , and H ( Q ) T = H ( Q ∗ ) H(Q)^\mathsf{T} = H(Q^*) H ( Q ) T = H ( Q ∗ ) since K T = D π 1 / 2 Q ∗ D π − 1 / 2 K^\mathsf{T} = D_\pi^{1/2}Q^*D_\pi^{-1/2} K T = D π 1/2 Q ∗ D π − 1/2 . Also H ( Q ) = E − 1 M ( Q , π ) E H(Q) = E^{-1}M(Q,\pi)E H ( Q ) = E − 1 M ( Q , π ) E with E = diag ( D π − 1 / 2 , 1 ) E = \operatorname{diag}(D_\pi^{-1/2},1) E = diag ( D π − 1/2 , 1 ) , so by Lemma 4.4 H ( Q ) H(Q) H ( Q ) is irreducible, and for 2 generators with the same stationary law, H ( Q ) H(Q) H ( Q ) and H ( Q ′ ) H(Q') H ( Q ′ ) have the same principal minors exactly when the stationary laws of O ( T ) O(T) O ( T ) agree.
Lemma 4.13 (the added index selects memoryless blocks). Let B ⊆ [ d ] B \subseteq[d] B ⊆ [ d ] with $2 \le |B| \le d - 1$. Then B B B is a side of a cut of H ( Q ) H(Q) H ( Q ) if and only if B B B is a memoryless block of Q Q Q . In that case the cut-transpose of H ( Q ) H(Q) H ( Q ) that transposes the block on B B B is H ( Q [ B ] ) H(Q^{[B]}) H ( Q [ B ] ) , for suitable rank-one factors, and the one that transposes the other side is $H(Q^{[B]})^\mathsf{T} = H((Q^{[B]})^*).
Proof. Put J = ( [ d ] ∖ B ) ∪ { ∂ } J = ([d]\setminus B)\cup\{\partial\} J = ([ d ] ∖ B ) ∪ { ∂ } . The column ∂ \partial ∂ of H ( Q ) [ B , J ] H(Q)[B,J] H ( Q ) [ B , J ] is e B e_B e B and the row ∂ \partial ∂ of H ( Q ) [ J , B ] H(Q)[J,B] H ( Q ) [ J , B ] is e B T e_B^\mathsf{T} e B T , both positive. So the 2 blocks have rank one exactly when H ( Q ) [ B , J ] = e B r T H(Q)[B,J] = e_Br^\mathsf{T} H ( Q ) [ B , J ] = e B r T and H ( Q ) [ J , B ] = s e B T H(Q)[J,B] = se_B^\mathsf{T} H ( Q ) [ J , B ] = s e B T with r ∂ = s ∂ = 1 r_\partial= s_\partial= 1 r ∂ = s ∂ = 1 . For i ∈ B i \in B i ∈ B and y ∉ B y \notin B y ∈ / B this says q i y = r y e y q_{iy} = r_ye_y q i y = r y e y and q y i = s y π i / e y q_{yi} = s_y\pi_i/e_y q y i = s y π i / e y . The first rate does not depend on i i i , and the second is proportional to π i \pi_i π i . The total rate κ = ∑ y r y e y \kappa= \sum_y r_ye_y κ = ∑ y r y e y out of B B B is positive since Q Q Q is irreducible, so B B B is memoryless with ν y = r y e y / κ \nu_y = r_ye_y/\kappa ν y = r y e y / κ and c y = π ( B ) s y / e y c_y = \pi(B)s_y/e_y c y = π ( B ) s y / e y . The converse reads the same equations backwards.
We use the cut-transpose ct ( A , X ) \operatorname{ct}(A,X) ct ( A , X ) of [8 Definition 2.10] , defined for any matrix with a cut X X X . It keeps the block on X X X , transposes the block on the complement, and replaces the crossing blocks p q T p q^\mathsf{T} p q T on X × X c X \times X^c X × X c and u v T u v^\mathsf{T} u v T on X c × X X^c \times X X c × X by p u T p u^\mathsf{T} p u T and q v T q v^\mathsf{T} q v T . In the order ( B , J ) (B,J) ( B , J ) we have
H ( Q ) = ( K B e B r T s e B T N ) H(Q) = \begin{pmatrix} K_B & e_B r^\mathsf{T} \\ s e_B^\mathsf{T} & N \end{pmatrix} H ( Q ) = ( K B s e B T e B r T N )
Take X = J X = J X = J , with p = s p = s p = s , q = e B q = e_B q = e B , u = e B u = e_B u = e B and v = r v = r v = r . Then ct ( H ( Q ) , J ) \operatorname{ct}(H(Q),J) ct ( H ( Q ) , J ) keeps N N N and the crossing blocks s e B T s e_B^\mathsf{T} s e B T and e B r T e_Br^\mathsf{T} e B r T , and replaces K B K_B K B by K B T K_B^\mathsf{T} K B T . That is H ( Q [ B ] ) H(Q^{[B]}) H ( Q [ B ] ) , since K B T = D B 1 / 2 ( D B − 1 Q B T D B ) D B − 1 / 2 K_B^\mathsf{T} = D_B^{1/2}(D_B^{-1}Q_B^\mathsf{T}D_B)D_B^{-1/2} K B T = D B 1/2 ( D B − 1 Q B T D B ) D B − 1/2 . By Theorem 4.9, Q [ B ] Q^{[B]} Q [ B ] is an irreducible generator with stationary law π \pi π , so H ( Q [ B ] ) H(Q^{[B]}) H ( Q [ B ] ) has the same border. With X = B X = B X = B , p = e B p = e_B p = e B , q = r q = r q = r , u = s u = s u = s and v = e B v = e_B v = e B , the same computation gives ct ( H ( Q ) , B ) = H ( Q [ B ] ) T \operatorname{ct}(H(Q),B) = H(Q^{[B]})^\mathsf{T} ct ( H ( Q ) , B ) = H ( Q [ B ] ) T . Other factorizations change the result by a diagonal similarity [8 Remark 2.11] . ▫
Proof of Theorem 4.12 . The if part is Theorems 4.9 and 4.7 , applied along the sequence. Conversely, suppose the stationary laws agree. The first moments give π ′ = π \pi'=\pi π ′ = π , and Theorem 4.2 gives P Q ′ = P Q P_{Q'}=P_Q P Q ′ = P Q and F Q ′ = F Q F_{Q'}=F_Q F Q ′ = F Q . So H ( Q ) H(Q) H ( Q ) and H ( Q ′ ) H(Q') H ( Q ′ ) are irreducible matrices of order d + 1 d+1 d + 1 with the same principal minors. By the theorem of Chatterjee, Ghosh, Gurjar and Raj [8 Theorem 1.1] , there are fewer than 2 ( d + 1 ) 2(d+1) 2 ( d + 1 ) cut-transposes H ( Q ) = C 0 , C 1 , … , C k H(Q)=C_0,C_1,\ldots,C_k H ( Q ) = C 0 , C 1 , … , C k , with C s + 1 = ct ( C s , X s ) C_{s+1}=\operatorname{ct}(C_s,X_s) C s + 1 = ct ( C s , X s ) for a cut X s X_s X s of C s C_s C s , such that H ( Q ′ ) H(Q') H ( Q ′ ) is diagonally similar to C k C_k C k or to C k ⊤ C_k^{\top} C k ⊤ . A cut there has between 2 and d − 1 d-1 d − 1 elements on each side [8 Definition 2.5] .
We show by induction that each C s C_s C s is diagonally similar to H ( R s ) H(R_s) H ( R s ) for an irreducible generator R s R_s R s with stationary law π \pi π , obtained from Q Q Q by s s s reversals of memoryless blocks, each a memoryless block of the current generator, and some time reversals in between. This holds for s = 0 s=0 s = 0 . A cut of C s C_s C s is a cut of H ( R s ) H(R_s) H ( R s ) , since cuts do not change under diagonal similarity, and a diagonal similarity of a matrix changes its cut-transpose by a diagonal similarity. Indeed, for E = diag ( E X , E X c ) E=\operatorname{diag}(E_X,E_{X^c}) E = diag ( E X , E X c ) a short computation with the blocks gives ct ( E C E − 1 , X ) = E ′ ct ( C , X ) E ′ − 1 \operatorname{ct}(ECE^{-1},X)=E'\operatorname{ct}(C,X)E'^{-1} ct ( E C E − 1 , X ) = E ′ ct ( C , X ) E ′ − 1 with E ′ = diag ( E X , E X c − 1 ) E'=\operatorname{diag}(E_X,E_{X^c}^{-1}) E ′ = diag ( E X , E X c − 1 ) . Exactly one side of the cut avoids ∂ \partial ∂ , and it has between 2 and d − 1 d-1 d − 1 states. By Lemma 4.13 it is a memoryless block B B B of R s R_s R s , and C s + 1 C_{s+1} C s + 1 is diagonally similar to H ( R s [ B ] ) H(R_s^{[B]}) H ( R s [ B ] ) or to H ( ( R s [ B ] ) ∗ ) H((R_s^{[B]})^*) H (( R s [ B ] ) ∗ ) .
So H ( Q ′ ) H(Q') H ( Q ′ ) is diagonally similar to H ( R ) H(R) H ( R ) for some R R R of this form, or to H ( R ) ⊤ = H ( R ∗ ) H(R)^\top=H(R^*) H ( R ) ⊤ = H ( R ∗ ) . If H ( R 2 ) = E − 1 H ( R 1 ) E H(R_2)=E^{-1}H(R_1)E H ( R 2 ) = E − 1 H ( R 1 ) E with E E E diagonal, the entries ( i , ∂ ) (i,\partial) ( i , ∂ ) give e i = E i − 1 e i E ∂ e_i=E_i^{-1}e_iE_\partial e i = E i − 1 e i E ∂ , so E E E is a multiple of the identity and R 2 = R 1 R_2=R_1 R 2 = R 1 . Hence Q ′ Q' Q ′ is R R R or R ∗ R^* R ∗ . Finally, a memoryless block of a generator is a memoryless block of its time reversal, with the rates π y c y / π ( B ) \pi_yc_y/\pi(B) π y c y / π ( B ) out of B B B and π i κ ν y / π y \pi_i\kappa_{\nu y}/\pi_y π i κ ν y / π y into B B B , and ( R [ B ] ) ∗ = ( R ∗ ) [ B ] (R^{[B]})^*=(R^*)^{[B]} ( R [ B ] ) ∗ = ( R ∗ ) [ B ] , since both have the entries of R ∗ R^* R ∗ off B × B B\times B B × B and those of R R R on it. So every time reversal in the sequence can be moved to the front, where 2 of them cancel. This writes Q ′ Q' Q ′ as a sequence of memoryless-block reversals of Q Q Q or of Q ∗ Q^* Q ∗ , one for each cut-transpose. □
We now count the fiber. Write Σ i j = π i q i j + π j q j i \Sigma_{ij}=\pi_iq_{ij}+\pi_jq_{ji} Σ ij = π i q ij + π j q j i and Φ i j = π i q i j − π j q j i \Phi_{ij}=\pi_iq_{ij}-\pi_jq_{ji} Φ ij = π i q ij − π j q j i for i ≠ j i\ne j i = j . For a fixed π \pi π , a matrix R R R with zero row sums and π R = 0 \pi R=0 π R = 0 is determined by its diagonal, Σ R \Sigma^R Σ R and Φ R \Phi^R Φ R . Write ρ B ( R ) = R [ B ] \rho_B(R)=R^{[B]} ρ B ( R ) = R [ B ] and ρ [ d ] ( R ) = R ∗ \rho_{[d]}(R)=R^* ρ [ d ] ( R ) = R ∗ . Then ρ B \rho_B ρ B keeps the diagonal and Σ \Sigma Σ and changes the sign of Φ i j \Phi_{ij} Φ ij for i , j ∈ B i,j\in B i , j ∈ B . So the maps ρ B \rho_B ρ B are involutions and commute with each other, also for 2 sets that overlap, which means that they meet and neither contains the other. Let M ( Q ) \mathcal{M}(Q) M ( Q ) be the set of memoryless blocks of Q Q Q .
Lemma 4.15 (overlapping blocks). Let B , B ′ ∈ M ( Q ) B,B'\in\mathcal{M}(Q) B , B ′ ∈ M ( Q ) overlap, and put A = B ∩ B ′ A=B\cap B' A = B ∩ B ′ , X = B ∖ B ′ X=B\setminus B' X = B ∖ B ′ and Y = B ′ ∖ B Y=B'\setminus B Y = B ′ ∖ B . Then there is σ ≥ 0 \sigma\ge0 σ ≥ 0 with q i j = σ π j q_{ij}=\sigma\pi_j q ij = σ π j whenever i i i and j j j lie in different sets among A A A , X X X and Y Y Y . So Φ i j = 0 \Phi_{ij}=0 Φ ij = 0 for such i , j i,j i , j , and every union of some of these 3 sets with at least 2 and at most d − 1 d-1 d − 1 states is a memoryless block. This includes B ∪ B ′ B\cup B' B ∪ B ′ , B ∩ B ′ B\cap B' B ∩ B ′ , B ∖ B ′ B\setminus B' B ∖ B ′ and B △ B ′ B\mathbin{\triangle}B' B △ B ′ .
Proof. Put Z = [ d ] ∖ ( B ∪ B ′ ) Z=[d]\setminus(B\cup B') Z = [ d ] ∖ ( B ∪ B ′ ) . There are r y , s y ≥ 0 r_y,s_y\ge0 r y , s y ≥ 0 with q i y = r y q_{iy}=r_y q i y = r y and q y i = s y π i q_{yi}=s_y\pi_i q y i = s y π i for i ∈ B i\in B i ∈ B and y ∉ B y\notin B y ∈ / B , and likewise r y ′ , s y ′ r'_y,s'_y r y ′ , s y ′ for B ′ B' B ′ . The entries q a z q_{az} q a z and q z a q_{za} q z a with a ∈ A a\in A a ∈ A and z ∈ Z z\in Z z ∈ Z give r z = r z ′ r_z=r'_z r z = r z ′ and s z = s z ′ s_z=s'_z s z = s z ′ . For x ∈ X x\in X x ∈ X and y ∈ Y y\in Y y ∈ Y we have q x y = r y = s x ′ π y q_{xy}=r_y=s'_x\pi_y q x y = r y = s x ′ π y and q y x = s y π x = r x ′ π x q_{yx}=s_y\pi_x=r'_x\pi_x q y x = s y π x = r x ′ π x . So s x ′ = σ ′ s'_x=\sigma' s x ′ = σ ′ is constant on X X X and s y = σ s_y=\sigma s y = σ is constant on Y Y Y . The rates from X X X to A ∪ Y A\cup Y A ∪ Y and from A A A to Y Y Y are then σ ′ π j \sigma'\pi_j σ ′ π j , and those from Y Y Y to A ∪ X A\cup X A ∪ X and from A A A to X X X are σ π j \sigma\pi_j σ π j . The flux out of X X X equals the flux into X X X , which gives ( σ ′ − σ ) ( π ( A ) + π ( Y ) ) + Δ = 0 (\sigma'-\sigma)(\pi(A)+\pi(Y))+\Delta=0 ( σ ′ − σ ) ( π ( A ) + π ( Y )) + Δ = 0 with Δ = ∑ z ∈ Z ( r z − π z s z ) \Delta=\sum_{z\in Z}(r_z-\pi_zs_z) Δ = ∑ z ∈ Z ( r z − π z s z ) . The set Y Y Y gives ( σ − σ ′ ) ( π ( A ) + π ( X ) ) + Δ = 0 (\sigma-\sigma')(\pi(A)+\pi(X))+\Delta=0 ( σ − σ ′ ) ( π ( A ) + π ( X )) + Δ = 0 . Subtracting, ( σ ′ − σ ) ( 2 π ( A ) + π ( X ) + π ( Y ) ) = 0 (\sigma'-\sigma)(2\pi(A)+\pi(X)+\pi(Y))=0 ( σ ′ − σ ) ( 2 π ( A ) + π ( X ) + π ( Y )) = 0 , so σ = σ ′ \sigma=\sigma' σ = σ ′ . Now let P P P be a union of some of the sets A A A , X X X and Y Y Y . A state of P P P jumps to a state j ∈ ( B ∪ B ′ ) ∖ P j\in(B\cup B')\setminus P j ∈ ( B ∪ B ′ ) ∖ P at rate σ π j \sigma\pi_j σ π j and to z ∈ Z z\in Z z ∈ Z at rate r z r_z r z , and a state outside P P P jumps to i ∈ P i\in P i ∈ P at a rate proportional to π i \pi_i π i . So P P P is memoryless when 2 ≤ ∣ P ∣ ≤ d − 1 2\le|P|\le d-1 2 ≤ ∣ P ∣ ≤ d − 1 . □
Lemma 4.16 (reversal keeps the blocks). If B ∈ M ( Q ) B \in\mathcal{M}(Q) B ∈ M ( Q ) , then M ( Q [ B ] ) = M ( Q ) \mathcal{M}(Q^{[B]}) = \mathcal{M}(Q) M ( Q [ B ] ) = M ( Q ) . Also M ( Q ∗ ) = M ( Q ) \mathcal{M}(Q^*) = \mathcal{M}(Q) M ( Q ∗ ) = M ( Q ) .
Proof. The second claim is in the proof of Theorem 4.12 . Let R = Q [ B ] R = Q^{[B]} R = Q [ B ] and B ′ ∈ M ( Q ) B' \in\mathcal{M}(Q) B ′ ∈ M ( Q ) . Only the entries of R R R with both indices in B B B differ from those of Q Q Q . If B ′ B' B ′ is disjoint from B B B or contains it, the entries r i y r_{iy} r i y and r y i r_{yi} r y i with i ∈ B ′ i \in B' i ∈ B ′ and y ∉ B ′ y \notin B' y ∈ / B ′ are entries of Q Q Q . If B ′ ⊂ B B' \subset B B ′ ⊂ B and y ∈ B ∖ B ′ y \in B \setminus B' y ∈ B ∖ B ′ , then r i y = π y q y i / π i = π y s y ′ r_{iy} = \pi_y q_{yi}/\pi_i = \pi_y s'_y r i y = π y q y i / π i = π y s y ′ and r y i = π i r y ′ / π y r_{yi} = \pi_i r'_y/\pi_y r y i = π i r y ′ / π y , in the notation of the last proof. If B ′ B' B ′ overlaps B B B , the changed entries are r a x r_{ax} r a x and r x a r_{xa} r x a with a ∈ B ∩ B ′ a \in B \cap B' a ∈ B ∩ B ′ and x ∈ B ∖ B ′ x \in B \setminus B' x ∈ B ∖ B ′ , and Lemma 4.15 gives r a x = π x q x a / π a = σ π x = q a x r_{ax} = \pi_x q_{xa}/\pi_a = \sigma\pi_x = q_{ax} r a x = π x q x a / π a = σ π x = q a x and r x a = q x a r_{xa} = q_{xa} r x a = q x a . So M ( Q ) ⊆ M ( R ) \mathcal{M}(Q) \subseteq\mathcal{M}(R) M ( Q ) ⊆ M ( R ) , and since B ∈ M ( R ) B \in\mathcal{M}(R) B ∈ M ( R ) and R [ B ] = Q R^{[B]} = Q R [ B ] = Q , equality holds.
So every generator of Theorem 4.12 has the memoryless blocks of Q Q Q . Call a member of M ( Q ) ∪ { [ d ] } \mathcal{M}(Q) \cup\{[d]\} M ( Q ) ∪ {[ d ]} strong if it overlaps no member of M ( Q ) \mathcal{M}(Q) M ( Q ) . The strong members form a laminar family L \mathcal{L} L that contains [ d ] [d] [ d ] , so they form a tree under inclusion with at most d − 1 d - 1 d − 1 members. For i ≠ j i \ne j i = j let N ( i , j ) N(i,j) N ( i , j ) be the smallest member of L \mathcal{L} L that contains i i i and j j j . Call N ∈ L N \in\mathcal{L} N ∈ L active if Φ i j ≠ 0 \Phi_{ij} \ne0 Φ ij = 0 for some i , j i,j i , j with N ( i , j ) = N N(i,j) = N N ( i , j ) = N , and let k k k be the number of active members. For ε ∈ { ± 1 } L \varepsilon\in\{\pm1\}^{\mathcal{L}} ε ∈ { ± 1 } L let Q ε Q^\varepsilon Q ε have the diagonal of Q Q Q and the entries π i q i j ε = ( Σ i j + ε N ( i , j ) Φ i j ) / 2 \pi_i q^\varepsilon_{ij} = (\Sigma_{ij} + \varepsilon_{N(i,j)}\Phi_{ij})/2 π i q ij ε = ( Σ ij + ε N ( i , j ) Φ ij ) /2 for i ≠ j i \ne j i = j .
Theorem 4.17 (the size of the stationary fiber). Let Q Q Q be irreducible. The generators Q ′ Q' Q ′ of Theorem 4.12 are exactly the Q ε Q^\varepsilon Q ε , and Q ε = Q η Q^\varepsilon= Q^\eta Q ε = Q η exactly when ε \varepsilon ε and η \eta η agree on the active members. So there are exactly 2 k 2^k 2 k of them, and ( Z / 2 ) k (\mathbb{Z}/2)^k ( Z /2 ) k acts on them simply transitively by changing the signs of Φ \Phi Φ on the pairs of the active members. Each of them is obtained from Q Q Q or from Q ∗ = Q − 1 Q^* = Q^{-1} Q ∗ = Q − 1 by at most d − 2 d - 2 d − 2 commuting reversals of strong memoryless blocks. In particular they are only Q Q Q and Q ∗ Q^* Q ∗ exactly when k ≤ 1 k \le1 k ≤ 1 .
Proof. Given ε \varepsilon ε , apply ρ N \rho_N ρ N for each N ∈ L N \in\mathcal{L} N ∈ L at which ε \varepsilon ε differs from its value at the parent of N N N , with the value 1 1 1 above [ d ] [d] [ d ] . For N ( i , j ) = P N(i,j) = P N ( i , j ) = P the sign of Φ i j \Phi_{ij} Φ ij changes once for each change of ε \varepsilon ε along the chain from P P P up to [ d ] [d] [ d ] , so the result is Q ε Q^\varepsilon Q ε . Each N ≠ [ d ] N \ne[d] N = [ d ] is a memoryless block of the current generator by Lemma 4.16 , so Q ε Q^\varepsilon Q ε is in the fiber by Theorems 4.9 and 4.7 . Starting from Q ∗ Q^* Q ∗ when ε [ d ] = − 1 \varepsilon_{[d]} = -1 ε [ d ] = − 1 leaves at most ∣ L ∣ − 1 ≤ d − 2 |\mathcal{L}| - 1 \le d - 2 ∣ L ∣ − 1 ≤ d − 2 block reversals.
Conversely, every B ∈ M ( Q ) ∪ { [ d ] } B \in\mathcal{M}(Q) \cup\{[d]\} B ∈ M ( Q ) ∪ {[ d ]} contains disjoint N 1 , … , N r ∈ L N_1,\ldots,N_r \in\mathcal{L} N 1 , … , N r ∈ L such that a pair { i , j } \{i,j\} { i , j } with Φ i j ≠ 0 \Phi_{ij} \ne0 Φ ij = 0 lies in B B B exactly when it lies in some N t N_t N t . This is clear for a strong B B B . Otherwise B B B overlaps some B ′ ∈ M ( Q ) B' \in\mathcal{M}(Q) B ′ ∈ M ( Q ) , and by Lemma 4.15 B B B is the disjoint union of B ∩ B ′ B \cap B' B ∩ B ′ and B ∖ B ′ B \setminus B' B ∖ B ′ , each a memoryless block or a single state, with Φ = 0 \Phi= 0 Φ = 0 on the pairs between them. So induction on ∣ B ∣ |B| ∣ B ∣ applies. Hence ρ B ( Q ε ) = ρ N 1 ⋯ ρ N r ( Q ε ) \rho_B(Q^\varepsilon) = \rho_{N_1} \cdots\rho_{N_r}(Q^\varepsilon) ρ B ( Q ε ) = ρ N 1 ⋯ ρ N r ( Q ε ) , since both sides have the diagonal and Σ \Sigma Σ of Q Q Q and the same Φ \Phi Φ , and this is some Q η Q^\eta Q η . By Theorem 4.12 and Lemma 4.16 , every Q ′ Q' Q ′ in the fiber arises from Q Q Q or Q ∗ Q^* Q ∗ by such steps with B ∈ M ( Q ) B \in\mathcal{M}(Q) B ∈ M ( Q ) , so it is some Q ε Q^\varepsilon Q ε . Finally, a pair with N ( i , j ) = N N(i,j) = N N ( i , j ) = N and Φ i j ≠ 0 \Phi_{ij} \ne0 Φ ij = 0 recovers ε N \varepsilon_N ε N from Q ε Q^\varepsilon Q ε .
The blocks that carry circulation need not be laminar. If B B B carries a 3-cycle and B ∪ { y } B \cup\{y\} B ∪ { y } and B ∪ { z } B \cup\{z\} B ∪ { z } are memoryless, both carry circulation and overlap, and both act as ρ B \rho_B ρ B .
Remark 4.18 (modules). Label the arc from i i i to j j j by q i j / π j q_{ij}/\pi_j q ij / π j . The memoryless blocks are exactly the sets M M M with 2 ≤ ∣ M ∣ ≤ d − 1 2 \le|M| \le d - 1 2 ≤ ∣ M ∣ ≤ d − 1 whose outside states see the same labels to and from every i ∈ M i \in M i ∈ M , the modules of these labels, and by Lemma 4.15 they form, with [ d ] [d] [ d ] and the singletons, a partitive family [19 ] whose tree of strong members is L \mathcal{L} L . A count 2 k 2^k 2 k over a tree of non-overlapping blocks has the shape of Gallai’s theorem on transitive orientations of a comparability graph [17 ] and of the reversal of clans of 2-structures [13 , 14 ] , a lineage that the introduction of [8 ] also states.
Corollary 4.19 (when the stationary law sees only time reversal). Let Q Q Q and Q ′ Q' Q ′ be irreducible and give the same stationary law of O ( T ) O(T) O ( T ) . Then Q ′ Q' Q ′ is Q Q Q or Q ∗ Q^* Q ∗ when d ≤ 4 d \le4 d ≤ 4 , when Q Q Q has no cut, and
when Q Q Q has no memoryless block B B B with ∣ B ∣ ≥ 3 |B| \ge3 ∣ B ∣ ≥ 3 and ∣ B c ∣ ≥ 2 |B^{c}| \ge2 ∣ B c ∣ ≥ 2 . The last holds for all generators with positive rates outside a finite union of proper linear subspaces, given by equal rates out of 2 states into a third.
Proof. If ∣ B c ∣ ≥ 2 |B^{c}| \ge2 ∣ B c ∣ ≥ 2 , then B B B is a side of a cut by Remark 4.10, and when d ≤ 4 d \le4 d ≤ 4 every memoryless block has ∣ B ∣ = 2 |B| = 2 ∣ B ∣ = 2 or ∣ B c ∣ = 1 |B^{c}| = 1 ∣ B c ∣ = 1 . So in each case every member of M ( Q ) \mathcal{M}(Q) M ( Q ) , which by Lemma 4.16 is a memoryless block of every generator R R R of the fiber, has ∣ B ∣ = 2 |B| = 2 ∣ B ∣ = 2 or ∣ B c ∣ = 1 |B^{c}| = 1 ∣ B c ∣ = 1 , and Theorem 4.9 gives R [ B ] = R R^{[B]} = R R [ B ] = R or R [ B ] = R ∗ R^{[B]} = R^{*} R [ B ] = R ∗ . So the fiber is { Q , Q ∗ } \{Q, Q^{*}\} { Q , Q ∗ } by Theorem 4.17 . With positive rates, a memoryless block needs q i y = q i ′ y q_{iy} = q_{i'y} q i y = q i ′ y for distinct i , i ′ ∈ B i,i' \in B i , i ′ ∈ B and y ∉ B y \notin B y ∈ / B .
Which starts hide time reversal
By Theorem 4.7 the stationary start never separates Q Q Q from Q ∗ Q^{*} Q ∗ , and by Theorem 4.5 a generic start does. We now find every start that does not. Write a start as μ = π ∘ f \mu= \pi\circ f μ = π ∘ f with f ≥ 0 f \ge0 f ≥ 0 and π ⋅ f = 1 \pi\cdot f = 1 π ⋅ f = 1 , and put
Φ = D π Q − Q T D π , \Phi= D_{\pi}Q - Q^{\mathsf{T}}D_{\pi}, Φ = D π Q − Q T D π ,
the matrix of the net probability fluxes Φ i j = π i q i j − π j q j i \Phi_{ij} = \pi_iq_{ij} - \pi_jq_{ji} Φ ij = π i q ij − π j q j i . It is antisymmetric, Φ 1 = 0 \Phi\mathbf{1} = 0 Φ 1 = 0 , and Φ = 0 \Phi= 0 Φ = 0 exactly when Q Q Q is reversible. A circulation component of Q Q Q is a connected component, with at least 2 states, of the graph on [ d ] [d] [ d ] with an edge { i , j } \{i,j\} { i , j } whenever Φ i j ≠ 0 \Phi_{ij} \ne0 Φ ij = 0 . For a face F F F we write A F = diag x F − Q F A_F = \operatorname{diag} x_F - Q_F A F = diag x F − Q F , a matrix of affine functions of x ∈ R F x \in\mathbb{R}^{F} x ∈ R F .
Lemma 4.20 (the flux form). Let Q Q Q be irreducible, f ∈ R d f \in\mathbb{R}^{d} f ∈ R d and μ = π ∘ f \mu= \pi\circ f μ = π ∘ f . With u = ( diag x − Q ) − 1 1 u = (\operatorname{diag} x - Q)^{-1}\mathbf{1} u = ( diag x − Q ) − 1 1 and v = ( diag x − Q ) − 1 f v = (\operatorname{diag} x - Q)^{-1}f v = ( diag x − Q ) − 1 f ,
F Q ∗ μ ( x ) − F Q μ ( x ) = u T Φ v . F_{Q^{*}}^{\mu}(x) - F_{Q}^{\mu}(x) = u^{\mathsf{T}}\Phi v. F Q ∗ μ ( x ) − F Q μ ( x ) = u T Φ v . If F Q ∗ μ = F Q μ F_{Q^{*}}^{\mu} = F_{Q}^{\mu} F Q ∗ μ = F Q μ , then ( A F − 1 1 ) T Φ F ( A F − 1 f F ) = 0 (A_F^{-1}\mathbf{1})^{\mathsf{T}}\Phi_F(A_F^{-1}f_F) = 0 ( A F − 1 1 ) T Φ F ( A F − 1 f F ) = 0 identically in x ∈ R F x \in\mathbb{R}^{F} x ∈ R F , for every face F F F , where Φ F \Phi_F Φ F is the restriction of Φ \Phi Φ to F × F F \times F F × F .
Proof. Since ( diag x − Q ∗ ) − 1 = D π − 1 ( diag x − Q T ) − 1 D π (\operatorname{diag} x - Q^{*})^{-1} = D_{\pi}^{-1}(\operatorname{diag} x - Q^{\mathsf{T}})^{-1}D_{\pi} ( diag x − Q ∗ ) − 1 = D π − 1 ( diag x − Q T ) − 1 D π , we have F Q ∗ μ = f T ( diag x − Q T ) − 1 π T = π ⋅ v F_{Q^{*}}^{\mu} = f^{\mathsf{T}}(\operatorname{diag} x - Q^{\mathsf{T}})^{-1}\pi^{\mathsf{T}} = \pi\cdot v F Q ∗ μ = f T ( diag x − Q T ) − 1 π T = π ⋅ v , while F Q μ = ( π ∘ f ) ⋅ u F_{Q}^{\mu} = (\pi\circ f) \cdot u F Q μ = ( π ∘ f ) ⋅ u . Insert 1 = ( diag x − Q ) u \mathbf{1} = (\operatorname{diag} x - Q)u 1 = ( diag x − Q ) u in the first and f = ( diag x − Q ) v f = (\operatorname{diag} x - Q)v f = ( diag x − Q ) v in the second. The terms with diag x \operatorname{diag} x diag x cancel, and
π ⋅ v − ( π ∘ f ) ⋅ u = u T D π Q v − v T D π Q u = u T Φ v . \pi\cdot v - (\pi\circ f) \cdot u = u^{\mathsf{T}}D_{\pi}Qv - v^{\mathsf{T}}D_{\pi}Qu = u^{\mathsf{T}}\Phi v. π ⋅ v − ( π ∘ f ) ⋅ u = u T D π Q v − v T D π Q u = u T Φ v .
For the second claim let x j → ∞ x_j \to\infty x j → ∞ for j ∉ F j \notin F j ∈ / F . By the formula of Schur, the block of ( diag x − Q ) − 1 (\operatorname{diag} x - Q)^{-1} ( diag x − Q ) − 1 on F F F tends to A F − 1 A_F^{-1} A F − 1 and the other blocks tend to 0. So u u u and v v v tend to A F − 1 1 A_F^{-1}\mathbf{1} A F − 1 1 and A F − 1 f F A_F^{-1}f_F A F − 1 f F on F F F and to 0 off F F F .
The blocks that matter are memoryless blocks that no net flux crosses. For X ⊆ [ d ] X \subseteq[d] X ⊆ [ d ] , say that a state z ∉ X z \notin X z ∈ / X is attached to X X X if the rates q i z q_{iz} q i z , i ∈ X i \in X i ∈ X , are not all equal, or if Φ i z ≠ 0 \Phi_{iz} \ne0 Φ i z = 0 for some i ∈ X i \in X i ∈ X .
Lemma 4.21 (closed blocks). (a) A set B B B with 2 ≤ ∣ B ∣ ≤ d − 1 2 \le|B| \le d - 1 2 ≤ ∣ B ∣ ≤ d − 1 has no attached state if and only if it is a memoryless block with Φ i z = 0 \Phi_{iz} = 0 Φ i z = 0 for all i ∈ B i \in B i ∈ B and z ∉ B z \notin B z ∈ / B . We call such a block closed.
(b) Let ∣ X ∣ ≥ 2 |X| \ge2 ∣ X ∣ ≥ 2 , put X 0 = X X_0 = X X 0 = X , and let X k + 1 X_{k+1} X k + 1 be X k X_k X k together with the states attached to X k X_k X k . The sequence becomes constant at a set N ( X ) N(X) N ( X ) . If X X X lies in a closed block, then N ( X ) N(X) N ( X ) is the smallest closed block containing X X X , and it lies in every closed block containing X X X . Otherwise N ( X ) = [ d ] N(X) = [d] N ( X ) = [ d ] .
Proof. (a) Let B B B have no attached state, and write w z w_z w z for the common value of q i z q_{iz} q i z , i ∈ B i \in B i ∈ B , for z ∉ B z \notin B z ∈ / B . Since Φ i z = 0 \Phi_{iz}=0 Φ i z = 0 , q z i = π i w z / π z q_{zi}=\pi_iw_z/\pi_z q z i = π i w z / π z , which is proportional to π i \pi_i π i on B B B . The total rate κ = ∑ z ∉ B w z \kappa=\sum_{z\notin B}w_z κ = ∑ z ∈ / B w z is positive since Q Q Q is irreducible, so B B B is memoryless with ν z = w z / κ \nu_z=w_z/\kappa ν z = w z / κ and c z = π ( B ) w z / π z c_z=\pi(B)w_z/\pi_z c z = π ( B ) w z / π z . The converse is the definition.
(b) Let B B B be a closed block that contains X k X_k X k , and let z ∉ B z\notin B z ∈ / B . The rates q i z q_{iz} q i z are equal for i ∈ B i\in B i ∈ B , hence for i ∈ X k i\in X_k i ∈ X k , and Φ i z = 0 \Phi_{iz}=0 Φ i z = 0 for i ∈ X k i\in X_k i ∈ X k . So z z z is not attached to X k X_k X k , and every state attached to X k X_k X k lies in B B B . By induction every X k X_k X k lies in B B B . The final set N ( X ) N(X) N ( X ) has no attached state, so by (a) it is a closed block or [ d ] [d] [ d ] .
A closed block B B B satisfies Φ i z = 0 \Phi_{iz}=0 Φ i z = 0 across its boundary. So if Φ \Phi Φ is supported on B × B B\times B B × B , then Q ∗ Q^* Q ∗ agrees with Q Q Q off B × B B\times B B × B , and Q ∗ = Q [ B ] Q^*=Q^{[B]} Q ∗ = Q [ B ] in the notation of Definition 4.8. The 5 states of Example 4.11 form a memoryless block B = { 1 , 2 , 3 } B=\{1,2,3\} B = { 1 , 2 , 3 } that is not closed, since Φ 14 = π 1 q 14 − π 4 q 41 = − 2 / 21 \Phi_{14}=\pi_1q_{14}-\pi_4q_{41}=-2/21 Φ 14 = π 1 q 14 − π 4 q 41 = − 2/21 .
Theorem 4.22 (which starts hide time reversal). Let Q Q Q be irreducible and let μ = π ∘ f \mu=\pi\circ f μ = π ∘ f be a start. Then O ( T ) O(T) O ( T ) has the same law under ( Q , μ ) (Q,\mu) ( Q , μ ) and under ( Q ∗ , μ ) (Q^*,\mu) ( Q ∗ , μ ) , for one T > 0 T>0 T > 0 or equivalently for every T T T , if and only if f f f is constant on N ( C ) N(C) N ( C ) for every circulation component C C C of Q Q Q . Equivalently, E π [ f ( ξ T ) − f ( ξ 0 ) ∣ O ( T ) ] = 0 \mathbb{E}_{\pi}[f(\xi_T)-f(\xi_0)\mid O(T)]=0 E π [ f ( ξ T ) − f ( ξ 0 ) ∣ O ( T )] = 0 almost surely for every T T T . In particular, if some circulation component lies in no closed block, then only the stationary start hides time reversal.
The if part is the mechanism of Theorem 4.9 . The only if part rests on the next lemma, which we prove by induction along the construction of N ( C ) N(C) N ( C ) .
Lemma 4.23 (attached states are visible). Let C C C be a circulation component. Let P 0 = C P_0=C P 0 = C and P j = P j − 1 ∪ { z j } P_j=P_{j-1}\cup\{z_j\} P j = P j − 1 ∪ { z j } for 1 ≤ j ≤ k 1\leq j\leq k 1 ≤ j ≤ k , where each z j z_j z j is attached to P j − 1 P_{j-1} P j − 1 . Write A j = A P j A_j=A_{P_j} A j = A P j and Φ j = Φ P j \Phi_j=\Phi_{P_j} Φ j = Φ P j .
(a) If b ∈ R P k b\in\mathbb{R}^{P_k} b ∈ R P k and ( A k − 1 1 ) T Φ k ( A k − 1 b ) = 0 (A_k^{-1}\mathbf{1})^\mathsf{T}\Phi_k(A_k^{-1}b)=0 ( A k − 1 1 ) T Φ k ( A k − 1 b ) = 0 for all x x x , then b b b is constant.
(b) For 1 ≤ j ≤ k 1\leq j\leq k 1 ≤ j ≤ k , ( A j − 1 1 ) T Φ j ( A j − 1 e z j ) (A_j^{-1}\mathbf{1})^\mathsf{T}\Phi_j(A_j^{-1}e_{z_j}) ( A j − 1 1 ) T Φ j ( A j − 1 e z j ) is not identically zero.
Proof. We prove (a) for k = 0 k=0 k = 0 , and then (b) for j j j and (a) for k = j k=j k = j from (a) for k = j − 1 k=j-1 k = j − 1 .
(a) for k = 0 k=0 k = 0 . Put x = t ξ x=t\xi x = t ξ with ξ ∈ ( 0 , ∞ ) C \xi\in(0,\infty)^C ξ ∈ ( 0 , ∞ ) C fixed and t → ∞ t\to\infty t → ∞ . Then A 0 − 1 = t − 1 diag ( ξ ) − 1 + O ( t − 2 ) A_0^{-1}=t^{-1}\operatorname{diag}(\xi)^{-1}+O(t^{-2}) A 0 − 1 = t − 1 diag ( ξ ) − 1 + O ( t − 2 ) , and the form equals
t − 2 ∑ i , j ∈ C Φ i j b j ξ i ξ j + O ( t − 3 ) = t − 2 2 ∑ i , j ∈ C Φ i j ( b j − b i ) ξ i ξ j + O ( t − 3 ) , t^{-2}\sum_{i,j\in C}\frac{\Phi_{ij}b_j}{\xi_i\xi_j}+O(t^{-3})=\frac{t^{-2}}{2}\sum_{i,j\in C}\frac{\Phi_{ij}(b_j-b_i)}{\xi_i\xi_j}+O(t^{-3}), t − 2 i , j ∈ C ∑ ξ i ξ j Φ ij b j + O ( t − 3 ) = 2 t − 2 i , j ∈ C ∑ ξ i ξ j Φ ij ( b j − b i ) + O ( t − 3 ) ,
by the antisymmetry of Φ \Phi Φ . The leading coefficient is a quadratic form in 1 / ξ 1/\xi 1/ ξ that vanishes on an open set, so Φ i j ( b j − b i ) = 0 \Phi_{ij}(b_j-b_i)=0 Φ ij ( b j − b i ) = 0 for all i , j i,j i , j . The graph of the edges with Φ i j ≠ 0 \Phi_{ij}\ne0 Φ ij = 0 is connected on C C C , so b b b is constant.
A Schur complement . Let P = P j − 1 P=P_{j-1} P = P j − 1 , z = z j z=z_j z = z j and X = P j X=P_j X = P j , and write a = ( q i z ) i ∈ P a=(q_{iz})_{i\in P} a = ( q i z ) i ∈ P , e = ( q z i ) i ∈ P e=(q_{zi})_{i\in P} e = ( q z i ) i ∈ P , ϕ = ( Φ i z ) i ∈ P \phi=(\Phi_{iz})_{i\in P} ϕ = ( Φ i z ) i ∈ P and s = x z + q z s=x_z+q_z s = x z + q z . For r ∈ R X r\in\mathbb{R}^X r ∈ R X the solution of A X y ′ = r A_Xy'=r A X y ′ = r is y ′ = ( y , t ) y'=(y,t) y ′ = ( y , t ) with
t = r z + e ⋅ y s , ( A P − a e T s ) y = r P + r z s a . t=\frac{r_z+e\cdot y}{s},\qquad\left(A_P-\frac{ae^\mathsf{T}}{s}\right)y=r_P+\frac{r_z}{s}a. t = s r z + e ⋅ y , ( A P − s a e T ) y = r P + s r z a .
For 2 vectors r , r ′ r,r' r , r ′ with solutions ( y , t ) (y,t) ( y , t ) and ( y ′ , t ′ ) (y',t') ( y ′ , t ′ ) ,
( A X − 1 r ) T Φ X ( A X − 1 r ′ ) = y T Φ P y ′ + t ′ y ⋅ ϕ − t y ′ ⋅ ϕ . (3) (A_X^{-1}r)^\mathsf{T}\Phi_X(A_X^{-1}r')=y^\mathsf{T}\Phi_Py'+t'\,y\cdot\phi-ty'\cdot\phi. \tag*{(3)} ( A X − 1 r ) T Φ X ( A X − 1 r ′ ) = y T Φ P y ′ + t ′ y ⋅ ϕ − t y ′ ⋅ ϕ . (3)
As x z → ∞ x_z\to\infty x z → ∞ with x P x_P x P fixed, s → ∞ s\to\infty s → ∞ and A P − a e T / s → A P A_P-ae^\mathsf{T}/s\to A_P A P − a e T / s → A P . (b) for j j j . Take r = 1 r=1 r = 1 and r ′ = e z r'=e_z r ′ = e z . Then y = A P − 1 1 + O ( 1 / s ) y=A_P^{-1}\mathbf{1}+O(1/s) y = A P − 1 1 + O ( 1/ s ) , y ′ = O ( 1 / s ) y'=O(1/s) y ′ = O ( 1/ s ) , s y ′ = A P − 1 a + O ( 1 / s ) sy'=A_P^{-1}a+O(1/s) s y ′ = A P − 1 a + O ( 1/ s ) , t = O ( 1 / s ) t=O(1/s) t = O ( 1/ s ) and s t ′ = 1 + O ( 1 / s ) st'=1+O(1/s) s t ′ = 1 + O ( 1/ s ) . Multiplying (3) by s s s and letting s → ∞ s\to\infty s → ∞ , the identity ( A X − 1 1 ) T Φ X ( A X − 1 e z ) = 0 (A_X^{-1}\mathbf{1})^{\mathsf T}\Phi_X(A_X^{-1}e_z)=0 ( A X − 1 1 ) T Φ X ( A X − 1 e z ) = 0 would give
( A P − 1 1 ) T Φ P ( A P − 1 a ) + ( A P − 1 1 ) ⋅ ϕ = 0 (4) (A_P^{-1}\mathbf{1})^{\mathsf T}\Phi_P(A_P^{-1}a)+(A_P^{-1}\mathbf{1})\cdot\phi=0 \tag*{(4)} ( A P − 1 1 ) T Φ P ( A P − 1 a ) + ( A P − 1 1 ) ⋅ ϕ = 0 (4)
for all x P x_P x P . If ϕ ≠ 0 \phi\ne0 ϕ = 0 , put x P = t ξ x_P=t\xi x P = t ξ as above. The first term is O ( t − 2 ) O(t^{-2}) O ( t − 2 ) and the second is t − 1 ∑ i ϕ i / ξ i + O ( t − 2 ) t^{-1}\sum_i\phi_i/\xi_i+O(t^{-2}) t − 1 ∑ i ϕ i / ξ i + O ( t − 2 ) , and ∑ i ϕ i / ξ i ≠ 0 \sum_i\phi_i/\xi_i\ne0 ∑ i ϕ i / ξ i = 0 for some ξ \xi ξ , a contradiction. If ϕ = 0 \phi=0 ϕ = 0 , then z z z is attached through unequal rates, so a a a is not constant, and (4) contradicts (a) for k = j − 1 k=j-1 k = j − 1 .
(a) for k = j k=j k = j . The form is unchanged when a constant vector is added to b b b , because ( A X − 1 1 ) T Φ X ( A X − 1 1 ) = 0 (A_X^{-1}\mathbf{1})^{\mathsf T}\Phi_X(A_X^{-1}\mathbf{1})=0 ( A X − 1 1 ) T Φ X ( A X − 1 1 ) = 0 . So we may assume b z = 0 b_z=0 b z = 0 . Take r = 1 r=1 r = 1 and r ′ = b r'=b r ′ = b . Then y ′ = A P − 1 b P + O ( 1 / s ) y'=A_P^{-1}b_P+O(1/s) y ′ = A P − 1 b P + O ( 1/ s ) and t , t ′ = O ( 1 / s ) t,t'=O(1/s) t , t ′ = O ( 1/ s ) , so (3) tends to ( A P − 1 1 ) T Φ P ( A P − 1 b P ) (A_P^{-1}\mathbf{1})^{\mathsf T}\Phi_P(A_P^{-1}b_P) ( A P − 1 1 ) T Φ P ( A P − 1 b P ) as s → ∞ s\to\infty s → ∞ . By (a) for k = j − 1 k=j-1 k = j − 1 , b P = β 1 b_P=\beta\mathbf{1} b P = β 1 for some β \beta β , so b = β 1 − β e z b=\beta\mathbf{1}-\beta e_z b = β 1 − β e z , and the form of b b b is − β -\beta − β times the form of e z e_z e z . By (b) for j j j , β = 0 \beta=0 β = 0 . □
Proof of Theorem 4.22. By Lemma 4.1(a) and Theorem 4.2, the laws agree for one T T T if and only if they agree for all T T T , and if and only if F Q ∗ μ = F Q μ F_{Q^*}^{\mu}=F_Q^{\mu} F Q ∗ μ = F Q μ . By Lemma 4.20 this is u T Φ v = 0 u^{\mathsf T}\Phi v=0 u T Φ v = 0 for all x x x . Every edge with Φ i j ≠ 0 \Phi_{ij}\ne0 Φ ij = 0 lies inside one circulation component, so Φ = ∑ C Φ ( C ) \Phi=\sum_C\Phi^{(C)} Φ = ∑ C Φ ( C ) , where Φ ( C ) \Phi^{(C)} Φ ( C ) agrees with Φ \Phi Φ on C × C C\times C C × C and vanishes elsewhere, and u T Φ v = ∑ C u C T Φ C v C u^{\mathsf T}\Phi v=\sum_Cu_C^{\mathsf T}\Phi_Cv_C u T Φ v = ∑ C u C T Φ C v C .
If. Fix C C C and let B = N ( C ) B=N(C) B = N ( C ) , with f = c f=c f = c on B B B . If B = [ d ] B=[d] B = [ d ] , then v = c u v=cu v = c u and u C T Φ C v C = c u C T Φ C u C = 0 u_C^{\mathsf T}\Phi_Cv_C=cu_C^{\mathsf T}\Phi_Cu_C=0 u C T Φ C v C = c u C T Φ C u C = 0 . Otherwise B B B is a closed block, so Q [ B , B c ] = κ 1 ν T Q[B,B^c]=\kappa\mathbf{1}\nu^{\mathsf T} Q [ B , B c ] = κ 1 ν T . The rows B B B of ( diag x − Q ) u = 1 (\operatorname{diag}x-Q)u=\mathbf{1} ( diag x − Q ) u = 1 and ( diag x − Q ) v = f (\operatorname{diag}x-Q)v=f ( diag x − Q ) v = f give
u B = ( 1 + κ ν ⋅ u B c ) A B − 1 1 , v B = ( c + κ ν ⋅ v B c ) A B − 1 1. u_B=(1+\kappa\,\nu\cdot u_{B^c})A_B^{-1}\mathbf{1},\qquad v_B=(c+\kappa\,\nu\cdot v_{B^c})A_B^{-1}\mathbf{1}. u B = ( 1 + κ ν ⋅ u B c ) A B − 1 1 , v B = ( c + κ ν ⋅ v B c ) A B − 1 1 .
So u C u_C u C and v C v_C v C are multiples of the same vector, and u C T Φ C v C = 0 u_C^{\mathsf T}\Phi_Cv_C=0 u C T Φ C v C = 0 .
Only if. Let u T Φ v = 0 u^{\mathsf T}\Phi v=0 u T Φ v = 0 for all x x x , and fix C C C . By Lemma 4.20 with F = C F=C F = C and Lemma 4.23(a) with k = 0 k=0 k = 0 , f f f is constant on C C C , say f = c f=c f = c there. List the states of N ( C ) ∖ C N(C)\setminus C N ( C ) ∖ C as z 1 , … , z k z_1,\ldots,z_k z 1 , … , z k , in the order in which Lemma 4.21(b) adds them, in any order within one step. A state added at step m + 1 m+1 m + 1 is attached to X m X_m X m , hence to every larger set, so z j z_j z j is attached to P j − 1 = C ∪ { z 1 , … , z j − 1 } P_{j-1}=C\cup\{z_1,\ldots,z_{j-1}\} P j − 1 = C ∪ { z 1 , … , z j − 1 } . Suppose that f f f is not constant on N ( C ) N(C) N ( C ) , and let j j j be the least index with f z j ≠ c f_{z_j}\ne c f z j = c . Then f = c f=c f = c on P j − 1 P_{j-1} P j − 1 , and f P j = c 1 + ( f z j − c ) e z j f_{P_j}=c\mathbf{1}+(f_{z_j}-c)e_{z_j} f P j = c 1 + ( f z j − c ) e z j . Lemma 4.20 with F = P j F=P_j F = P j gives ( f z j − c ) ( A j − 1 1 ) T Φ j ( A j − 1 e z j ) = 0 (f_{z_j}-c)(A_j^{-1}\mathbf{1})^{\mathsf T}\Phi_j(A_j^{-1}e_{z_j})=0 ( f z j − c ) ( A j − 1 1 ) T Φ j ( A j − 1 e z j ) = 0 , which contradicts Lemma 4.23(b).
Conditional form. By path reversal, E Q ∗ μ [ ϕ ( O ( T ) ) ] = E Q π [ f ( ξ T ) ϕ ( O ( T ) ) ] \mathbb{E}^{\mu}_{Q^*}[\phi(O(T))]=\mathbb{E}^{\pi}_{Q}[f(\xi_T)\phi(O(T))] E Q ∗ μ [ ϕ ( O ( T ))] = E Q π [ f ( ξ T ) ϕ ( O ( T ))] for bounded ϕ \phi ϕ , while E Q μ [ ϕ ( O ( T ) ) ] = E Q π [ f ( ξ 0 ) ϕ ( O ( T ) ) ] \mathbb{E}^{\mu}_{Q}[\phi(O(T))]=\mathbb{E}^{\pi}_{Q}[f(\xi_0)\phi(O(T))] E Q μ [ ϕ ( O ( T ))] = E Q π [ f ( ξ 0 ) ϕ ( O ( T ))] . The 2 laws agree for every ϕ \phi ϕ exactly when f ( ξ T ) − f ( ξ 0 ) f(\xi_T)-f(\xi_0) f ( ξ T ) − f ( ξ 0 ) has conditional mean 0 0 0 given O ( T ) O(T) O ( T ) . Finally, if N ( C ) = [ d ] N(C)=[d] N ( C ) = [ d ] for some C C C , then f f f is constant and μ = π \mu=\pi μ = π . □
So the starts that hide time reversal form, after the normalization π ⋅ f = 1 \pi\cdot f=1 π ⋅ f = 1 , the nonnegative part of the space of functions constant on the blocks N ( C ) N(C) N ( C ) . For a generic Q Q Q this space is the constants, and for a reversible Q Q Q it is everything.
Lumped reversals
If A 1 A_1 A 1 and A 2 A_2 A 2 are disjoint renewal blocks of ( Q , μ ) (Q,\mu) ( Q , μ ) , then A 2 A_2 A 2 is a renewal block of ( Q / A 1 , μ / A 1 ) (Q/A_1,\mu/A_1) ( Q / A 1 , μ / A 1 ) with the same Q A 2 Q_{A_2} Q A 2 , ρ \rho ρ and κ A 2 \kappa_{A_2} κ A 2 . Indeed the rate from x ∈ A 2 x\in A_2 x ∈ A 2 to a 1 a_1 a 1 is ∑ i ∈ A 1 q x i \sum_{i\in A_1}q_{xi} ∑ i ∈ A 1 q x i , which does not depend on x x x , and the rates from a 1 a_1 a 1 into A 2 A_2 A 2 are the rates q i y q_{iy} q i y , i ∈ A 1 i\in A_1 i ∈ A 1 , y ∈ A 2 y\in A_2 y ∈ A 2 , which are proportional to ρ A 2 \rho_{A_2} ρ A 2 . So a family P \mathcal{P} P of disjoint renewal blocks can be lumped at once, to ( Q / P , μ / P ) (Q/\mathcal{P},\mu/\mathcal{P}) ( Q / P , μ / P ) on the atoms, the members of P \mathcal{P} P and the other single states, with ( Q / P ) A B = ∑ j ∈ B q i j (Q/\mathcal{P})_{AB}=\sum_{j\in B}q_{ij} ( Q / P ) A B = ∑ j ∈ B q ij for any i ∈ A i\in A i ∈ A , and
F Q μ ( x ) = F Q / P μ / P ( x ~ ) , x ~ { j } = x j , x ~ A = u A ( A ∈ P ) . (5) F_Q^\mu(x)=F_{Q/\mathcal{P}}^{\mu/\mathcal{P}}(\widetilde{x}),\qquad\widetilde{x}_{\{j\}}=x_j,\qquad\widetilde{x}_A=u_A\ (A\in\mathcal{P}). \tag*{(5)} F Q μ ( x ) = F Q / P μ / P ( x ) , x { j } = x j , x A = u A ( A ∈ P ) . (5)
The lumped generator is irreducible, and its stationary law π ~ / P \widetilde{\pi}/\mathcal{P} π / P is π ~ \widetilde{\pi} π summed over the atoms, since
∑ i ∈ A π i ( Q / P ) A B = ∑ i ∈ A , j ∈ B π i q i j . \sum_{i\in A}\pi_i(Q/\mathcal{P})_{AB}=\sum_{i\in A,j\in B}\pi_iq_{ij}. i ∈ A ∑ π i ( Q / P ) A B = i ∈ A , j ∈ B ∑ π i q ij .
Conversely, let R ~ \widetilde{R} R be a generator on the atoms with the diagonal of Q / P Q/\mathcal{P} Q / P , and let un P ( R ~ ) \operatorname{un}_{\mathcal{P}}(\widetilde{R}) un P ( R ) have the entries R ~ A ( i ) A ( j ) ρ A ( j ) ( j ) \widetilde{R}_{A(i)A(j)}\rho_{A(j)}(j) R A ( i ) A ( j ) ρ A ( j ) ( j ) for i i i and j j j in different atoms, with ρ { j } ( j ) = 1 \rho_{\{j\}}(j)=1 ρ { j } ( j ) = 1 , the block Q A Q_A Q A on each A ∈ P A\in\mathcal{P} A ∈ P , and the diagonal of Q Q Q . Its rows sum to 0, since R ~ A A = − κ A \widetilde{R}_{AA}=-\kappa_A R AA = − κ A . Each A ∈ P A\in\mathcal{P} A ∈ P is a renewal block of ( un P ( R ~ ) , μ ) (\operatorname{un}_{\mathcal{P}}(\widetilde{R}),\mu) ( un P ( R ) , μ ) with the data Q A Q_A Q A , ρ \rho ρ and κ A \kappa_A κ A it has for Q Q Q , and un P ( R ~ ) / P = R ~ \operatorname{un}_{\mathcal{P}}(\widetilde{R})/\mathcal{P}=\widetilde{R} un P ( R ) / P = R .
Definition 4.24 (lumped reversal). Let P \mathcal{P} P be a family, possibly empty, of disjoint renewal blocks of ( Q , μ ) (Q,\mu) ( Q , μ ) , and put Q ~ = Q / P \widetilde{Q}=Q/\mathcal{P} Q = Q / P , μ ~ = μ / P \widetilde{\mu}=\mu/\mathcal{P} μ = μ / P and π ~ = π / P \widetilde{\pi}=\pi/\mathcal{P} π = π / P . Let R ~ \widetilde{R} R be Q ~ [ B ~ ] \widetilde{Q}[\widetilde{B}] Q [ B ] for a memoryless block B ~ \widetilde{B} B of Q ~ \widetilde{Q} Q with μ ~ B ~ \widetilde{\mu}_{\widetilde{B}} μ B proportional to π ~ B ~ \widetilde{\pi}_{\widetilde{B}} π B , possibly 0, or Q ~ ∗ \widetilde{Q}^{*} Q ∗ when μ ~ = π ~ \widetilde{\mu}=\widetilde{\pi} μ = π . Then un P ( R ~ ) \operatorname{un}_{\mathcal{P}}(\widetilde{R}) un P ( R ) is a lumped reversal of ( Q , μ ) (Q,\mu) ( Q , μ ) .
Theorem 4.25 (lumped reversals hide). Every lumped reversal R R R of ( Q , μ ) (Q,\mu) ( Q , μ ) is an irreducible generator , and O ( T ) O(T) O ( T ) has the same law under ( R , μ ) (R,\mu) ( R , μ ) as under ( Q , μ ) (Q,\mu) ( Q , μ ) for every T T T . The same holds after finitely many lumped reversals, each of the current generator.
Proof. By Theorem 4.9 , or Theorem 4.7 when R ~ = Q ~ ∗ \widetilde{R}=\widetilde{Q}^{*} R = Q ∗ , F R ~ μ ~ = F Q ~ ∗ μ ~ F_{\widetilde{R}}^{\widetilde{\mu}}=F_{\widetilde{Q}^{*}}^{\widetilde{\mu}} F R μ = F Q ∗ μ . Both choices of R ~ \widetilde{R} R keep the diagonal of Q ~ \widetilde{Q} Q , so R = un P ( R ~ ) R=\operatorname{un}_{\mathcal{P}}(\widetilde{R}) R = un P ( R ) is a generator with R / P = R ~ R/\mathcal{P}=\widetilde{R} R / P = R . It is irreducible, since R ~ \widetilde{R} R is (Theorem 4.9 ), every state of A ∈ P A\in\mathcal{P} A ∈ P leaves A A A , and every state of A A A is reached inside A A A from the support of ρ A \rho_A ρ A , as for Q Q Q . Its blocks A ∈ P A\in\mathcal{P} A ∈ P are renewal blocks of ( R , μ ) (R,\mu) ( R , μ ) with the g A g_A g A and κ A \kappa_A κ A of Q Q Q . So (5) for R R R and for Q Q Q gives F R μ = F Q μ F_R^\mu=F_Q^\mu F R μ = F Q μ on ( 0 , ∞ ) d (0,\infty)^d ( 0 , ∞ ) d , hence as rational functions, and Lemma 4.1(a) gives the laws.
The converse holds, so lumped reversals are the whole fiber from every start. We prove it in § 4.7 .
Theorem 4.26 (the fiber from every start). Let Q Q Q be an irreducible generator and μ \mu μ a start. A generator Q ′ Q' Q ′ and a start μ ′ \mu' μ ′ give O ( T 0 ) O(T_0) O ( T 0 ) the law it has under ( Q , μ ) (Q,\mu) ( Q , μ ) , for one T 0 > 0 T_0>0 T 0 > 0 , if and only if μ ′ = μ \mu'=\mu μ ′ = μ and Q ′ Q' Q ′ is reached from Q Q Q by finitely many lumped reversals, each a lumped reversal of the current pair.
Example 4.27 (a lumped reversal that is not a block reversal). Let d = 6 d=6 d = 6 , B 1 = { 0 , 1 } B_1=\{0,1\} B 1 = { 0 , 1 } , Z = { 2 , 3 } Z=\{2,3\} Z = { 2 , 3 } , B 2 = B 1 ∪ Z B_2=B_1\cup Z B 2 = B 1 ∪ Z , ρ = ( 3 / 4 , 1 / 4 ) \rho=(3/4,1/4) ρ = ( 3/4 , 1/4 ) and μ = e 4 \mu=e_4 μ = e 4 . Put q 01 = q 10 = 1 q_{01}=q_{10}=1 q 01 = q 10 = 1 , and for i ∈ B 1 i\in B_1 i ∈ B 1 put q i 2 = 2 q_{i2}=2 q i 2 = 2 , q i 3 = 1 q_{i3}=1 q i 3 = 1 and q i 4 = q i 5 = 1 q_{i4}=q_{i5}=1 q i 4 = q i 5 = 1 . For z ∈ Z z\in Z z ∈ Z put q z i = c z ρ i q_{zi}=c_z\rho_i q z i = c z ρ i ( i ∈ B 1 ) (i\in B_1) ( i ∈ B 1 ) with ( c 2 , c 3 ) = ( 1 , 2 ) (c_2,c_3)=(1,2) ( c 2 , c 3 ) = ( 1 , 2 ) , q 23 = 2 q_{23}=2 q 23 = 2 , q 32 = 1 q_{32}=1 q 32 = 1 and q z 4 = q z 5 = 1 q_{z4}=q_{z5}=1 q z 4 = q z 5 = 1 . For y ∈ { 4 , 5 } y\in\{4,5\} y ∈ { 4 , 5 } put q y j = c y ′ ( 3 / 4 , 1 / 4 , 1 , 1 ) j q_{yj}=c'_y(3/4,1/4,1,1)_j q y j = c y ′ ( 3/4 , 1/4 , 1 , 1 ) j ( j ∈ B 2 ) (j\in B_2) ( j ∈ B 2 ) with ( c 4 ′ , c 5 ′ ) = ( 1 , 2 ) (c'_4,c'_5)=(1,2) ( c 4 ′ , c 5 ′ ) = ( 1 , 2 ) , and q 45 = q 54 = 1 q_{45}=q_{54}=1 q 45 = q 54 = 1 . Then π = ( 171 , 81 , 252 , 252 , 224 , 140 ) / 1120 \pi=(171,81,252,252,224,140)/1120 π = ( 171 , 81 , 252 , 252 , 224 , 140 ) /1120 . The renewal blocks of ( Q , e 4 ) (Q,e_4) ( Q , e 4 ) are B 1 B_1 B 1 , B 2 B_2 B 2 and B 2 ∪ { 5 } B_2\cup\{5\} B 2 ∪ { 5 } . Their entry laws give the states 0 and 1 the weights 3 and 1, while π / π 1 = 171 / 81 \pi/\pi_1=171/81 π / π 1 = 171/81 , so none is a memoryless block, and e 4 ≠ π e_4\ne\pi e 4 = π . Lump B 1 B_1 B 1 to a state b b b . In Q / B 1 Q/B_1 Q / B 1 the set B ~ = { b , 2 , 3 } \widetilde{B}=\{b,2,3\} B = { b , 2 , 3 } is left at rate 1 to each of 4 and 5 from each of its states, it is entered from y y y at the rates c y ′ ( 1 , 1 , 1 ) c'_y(1,1,1) c y ′ ( 1 , 1 , 1 ) , and π ~ b = π 2 = π 3 \widetilde{\pi}_b=\pi_2=\pi_3 π b = π 2 = π 3 . So B ~ \widetilde{B} B is a memoryless block of Q / B 1 Q/B_1 Q / B 1 with μ ~ B ~ = 0 \widetilde{\mu}_{\widetilde{B}}=0 μ B = 0 , and its rates are 2 along b → 2 → 3 → b b\to2\to3\to b b → 2 → 3 → b and 1 backwards. The lumped reversal Q ′ ′ Q'' Q ′′ has q i 2 ′ ′ = 1 q''_{i2}=1 q i 2 ′′ = 1 and q i 3 ′ ′ = 2 q''_{i3}=2 q i 3 ′′ = 2 for i ∈ B 1 i\in B_1 i ∈ B 1 , q i ⋅ ′ ′ = ( 2 , 1 ) z ρ i q''_{i\cdot}=(2,1)_z\rho_i q i ⋅ ′′ = ( 2 , 1 ) z ρ i , q 23 ′ ′ = 1 q''_{23}=1 q 23 ′′ = 1 , q 32 ′ ′ = 2 q''_{32}=2 q 32 ′′ = 2 , and the entries of Q Q Q elsewhere. By Theorem 4.25 it gives the law of O ( T ) O(T) O ( T ) of ( Q , e 4 ) (Q,e_4) ( Q , e 4 ) , although Q ′ ′ ≠ Q Q''\ne Q Q ′′ = Q . At x = ( 3 , 5 , 7 / 2 , 4 , 9 / 2 , 6 ) x=(3,5,7/2,4,9/2,6) x = ( 3 , 5 , 7/2 , 4 , 9/2 , 6 ) both transforms are 290948 / 1250769 290948/1250769 290948/1250769 .
The fiber from every start
This subsection proves the only if part of Theorem 4.26 . The fiber of ( Q , μ ) (Q,\mu) ( Q , μ ) is the set of generators Q ′ Q' Q ′ such that O ( T ) O(T) O ( T ) has the same law under ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) as under ( Q , μ ) (Q,\mu) ( Q , μ ) for one T > 0 T>0 T > 0 . By Theorem 4.2 and Lemma 4.4 (b), a pair ( Q ′ , μ ′ ) (Q',\mu') ( Q ′ , μ ′ ) with this property has μ ′ = μ \mu'=\mu μ ′ = μ , and Q ′ Q' Q ′ is in the fiber exactly when M ( Q ′ , μ ) M(Q',\mu) M ( Q ′ , μ ) has the principal minors of M ( Q , μ ) M(Q,\mu) M ( Q , μ ) . Every Q ′ Q' Q ′ in the fiber is irreducible, − Q ′ -Q' − Q ′ has the principal minors of − Q -Q − Q , so P Q ′ = P Q P_{Q'}=P_Q P Q ′ = P Q , and F Q ′ μ = F Q μ F_{Q'}^\mu=F_Q^\mu F Q ′ μ = F Q μ . For a set B B B with *uniform exits and rank-one entries, that is Q [ B , B c ] = 1 r T Q[B,B^{c}] = \mathbf{1}r^{\mathsf{T}} Q [ B , B c ] = 1 r T and Q [ B c , B ] = c ρ T Q[B^{c},B] = c\rho^{\mathsf{T}} Q [ B c , B ] = c ρ T with r , c ≥ 0 r,c \ge0 r , c ≥ 0 and ρ \rho ρ a law on B B B , we put κ B = r ⋅ 1 \kappa_B = r \cdot\mathbf{1} κ B = r ⋅ 1 and L B = Q B + κ B I L_B = Q_B + \kappa_B I L B = Q B + κ B I . If Q Q Q is irreducible and 2 ≤ ∣ B ∣ ≤ d − 1 2 \le|B| \le d-1 2 ≤ ∣ B ∣ ≤ d − 1 , then κ B > 0 \kappa_B > 0 κ B > 0 and c ≠ 0 c \ne0 c = 0 , and the rows B B B of Q 1 = 0 Q\mathbf{1}=0 Q 1 = 0 give L B 1 = 0 L_B\mathbf{1}=0 L B 1 = 0 , so L B L_B L B is a generator on B B B . Every state of B B B is reached from supp ρ \operatorname{supp}\rho supp ρ by L B L_B L B , since every visit of the chain to B B B starts in supp ρ \operatorname{supp}\rho supp ρ and moves inside B B B with the rates of L B L_B L B . If A A A is a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) , then Q / A Q/A Q / A is irreducible, since replacing each sojourn of a path of Q Q Q in A A A by the state a a a gives a path of Q / A Q/A Q / A .
Lemma 4.28 (M-matrices). Let R R R be a generator on [ d ] [d] [ d ] , S ⊆ [ d ] S \subseteq[d] S ⊆ [ d ] nonempty and x ∈ ( 0 , ∞ ) S x \in(0,\infty)^S x ∈ ( 0 , ∞ ) S . Then X = diag x − R S X = \operatorname{diag}x - R_S X = diag x − R S is invertible, G = X − 1 ≥ 0 G=X^{-1}\ge0 G = X − 1 ≥ 0 entrywise, G j k > 0 G_{jk}>0 G j k > 0 exactly when j = k j=k j = k or the graph of R S R_S R S has a path from j j j to k k k , det X > 0 \det X>0 det X > 0 , and G 1 ≤ ( min j x j ) − 1 1 G\mathbf{1}\le(\min_j x_j)^{-1}\mathbf{1} G 1 ≤ ( min j x j ) − 1 1 .
Proof. Write X = D − N X=D-N X = D − N with D = diag ( x j − r j j ) D=\operatorname{diag}(x_j-r_{jj}) D = diag ( x j − r j j ) and N ≥ 0 N\ge0 N ≥ 0 the off-diagonal part of R S R_S R S . The row j j j of N N N sums to at most − r j j -r_{jj} − r j j , so D − 1 N D^{-1}N D − 1 N has row sums at most − r j j / ( x j − r j j ) < 1 -r_{jj}/(x_j-r_{jj})<1 − r j j / ( x j − r j j ) < 1 , and the series ∑ m ≥ 0 ( D − 1 N ) m D − 1 \sum_{m\ge0}(D^{-1}N)^mD^{-1} ∑ m ≥ 0 ( D − 1 N ) m D − 1 converges to X − 1 X^{-1} X − 1 . Its terms are nonnegative, and the entry ( j , k ) (j,k) ( j , k ) of the term m m m is positive exactly when there is a path of length m m m from j j j to k k k . Along x + s 1 x+s\mathbf{1} x + s 1 , s ≥ 0 s\ge0 s ≥ 0 , the matrix stays invertible, and det X → + ∞ \det X\to+\infty det X → + ∞ as s → ∞ s\to\infty s → ∞ , so det X > 0 \det X>0 det X > 0 . Finally X 1 ≥ ( min j x j ) 1 X\mathbf{1}\ge(\min_j x_j)\mathbf{1} X 1 ≥ ( min j x j ) 1 , since the row sums of − R S -R_S − R S are nonnegative, and applying G ≥ 0 G\ge0 G ≥ 0 gives 1 ≥ ( min j x j ) G 1 \mathbf{1}\ge(\min_j x_j)G\mathbf{1} 1 ≥ ( min j x j ) G 1 .
Lemma 4.29 (memoryless renewal blocks). Let Q Q Q be irreducible and let B B B , with 2 ≤ ∣ B ∣ ≤ d − 1 2\le|B|\le d-1 2 ≤ ∣ B ∣ ≤ d − 1 , have uniform exits and rank-one entries with entry law ρ \rho ρ . Then B B B is a memoryless block of Q Q Q if and only if ρ = π B / π ( B ) \rho=\pi_B/\pi(B) ρ = π B / π ( B ) , and if and only if ρ L B = 0 \rho L_B=0 ρ L B = 0 .
Proof. With ν = r / κ B \nu=r/\kappa_B ν = r / κ B , Definition 4.8 asks exactly that ρ = π B / π ( B ) \rho=\pi_B/\pi(B) ρ = π B / π ( B ) . The columns B B B of π Q = 0 \pi Q=0 π Q = 0 give π B ( κ B I − L B ) = s ρ \pi_B(\kappa_B I-L_B)=s\rho π B ( κ B I − L B ) = s ρ with s = π B c ⋅ c > 0 s=\pi_{B^c}\cdot c>0 s = π B c ⋅ c > 0 . The matrix κ B I − L B \kappa_B I-L_B κ B I − L B is invertible, since every eigenvalue of the generator L B L_B L B has real part at most 0. If ρ L B = 0 \rho L_B=0 ρ L B = 0 , then π B = ( s / κ B ) ρ \pi_B=(s/\kappa_B)\rho π B = ( s / κ B ) ρ solves this equation, so it is the solution. If π B = t ρ \pi_B=t\rho π B = tρ , then ρ L B = ( κ B − s / t ) ρ \rho L_B=(\kappa_B-s/t)\rho ρ L B = ( κ B − s / t ) ρ , and applying both sides to 1 \mathbf{1} 1 gives κ B = s / t \kappa_B=s/t κ B = s / t , so ρ L B = 0 \rho L_B=0 ρ L B = 0 .
Lemma 4.30 (a common renewal block). Let Q ′ Q' Q ′ be in the fiber of ( Q , μ ) (Q,\mu) ( Q , μ ) , and let A A A be a renewal block of both ( Q , μ ) (Q,\mu) ( Q , μ ) and ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) . Then A A A has the same entry law ρ \rho ρ , exit rate κ A \kappa_A κ A , transform g A g_A g A and multiple m m m for Q Q Q and Q ′ Q' Q ′ , and Q ′ / A Q'/A Q ′ / A is in the fiber of ( Q / A , μ / A ) (Q/A,\mu/A) ( Q / A , μ / A ) . If moreover A A A contains no smaller renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) , then Q A ′ = Q A Q'_A=Q_A Q A ′ = Q A , or ρ L A = 0 \rho L_A=0 ρ L A = 0 and Q A ′ = D ρ − 1 Q A T D ρ Q'_A=D_\rho^{-1}Q_A^{\mathsf{T}}D_\rho Q A ′ = D ρ − 1 Q A T D ρ .
Proof. Write r , c , ρ , κ , m r,c,\rho,\kappa,m r , c , ρ , κ , m for the data of A A A for Q Q Q and r ′ , c ′ , ρ ′ , κ ′ , m ′ r',c',\rho',\kappa',m' r ′ , c ′ , ρ ′ , κ ′ , m ′ for Q ′ Q' Q ′ . Put X A = diag x A − Q A X_A=\operatorname{diag}x_A-Q_A X A = diag x A − Q A and X = diag x A c − Q A c X=\operatorname{diag}x_{A^c}-Q_{A^c} X = diag x A c − Q A c , and X A ′ , X ′ X'_A,X' X A ′ , X ′ likewise for Q ′ Q' Q ′ . Since P Q ′ = P Q P_{Q'}=P_Q P Q ′ = P Q , the matrices − Q ′ -Q' − Q ′ and − Q -Q − Q have the same principal minors, so det X A ′ = det X A \det X'_A=\det X_A det X A ′ = det X A and det X ′ = det X \det X'=\det X det X ′ = det X . For x ∈ ( 0 , ∞ ) d x\in(0,\infty)^d x ∈ ( 0 , ∞ ) d the formula of Schur on A A A and the identity det ( Y − γ c r T ) = det Y − γ r T adj ( Y ) c \det(Y-\gamma cr^{\mathsf{T}})=\det Y-\gamma r^{\mathsf{T}}\operatorname{adj}(Y)c det ( Y − γ c r T ) = det Y − γ r T adj ( Y ) c give
P Q ( x ) = det X A ( det X − g A D ) , D = r T adj ( X ) c . P_Q(x)=\det X_A(\det X-g_A\mathcal{D}), \qquad\mathcal{D}=r^{\mathsf{T}}\operatorname{adj}(X)c. P Q ( x ) = det X A ( det X − g A D ) , D = r T adj ( X ) c .
since Q [ A c , A ] X − 1 Q [ A , A c ] = g A c r T Q[A^c,A]X^{-1}Q[A,A^c]=g_Acr^{\mathsf{T}} Q [ A c , A ] X − 1 Q [ A , A c ] = g A c r T , and likewise P Q ′ = det X A ′ ( det X ′ − g A ′ D ′ ) P_{Q'}=\det X'_A(\det X'-g'_A\mathcal{D}') P Q ′ = det X A ′ ( det X ′ − g A ′ D ′ ) . Hence g A D = g A ′ D ′ g_A\mathcal{D}=g'_A\mathcal{D}' g A D = g A ′ D ′ . Here D > 0 \mathcal{D}>0 D > 0 for x ∈ ( 0 , ∞ ) d x\in(0,\infty)^d x ∈ ( 0 , ∞ ) d . Indeed some y y y has r y > 0 r_y>0 r y > 0 , and a path of Q Q Q from y y y back to A A A stays in A c A^c A c until it enters A A A from a state y ′ y' y ′ with c y ′ > 0 c_{y'}>0 c y ′ > 0 . So ( X − 1 ) y ′ y ′ > 0 (X^{-1})_{y'y'}>0 ( X − 1 ) y ′ y ′ > 0 by Lemma 4.28, r T X − 1 c > 0 r^{\mathsf{T}}X^{-1}c>0 r T X − 1 c > 0 and D = det X r T X − 1 c > 0 \mathcal{D}=\det X\,r^{\mathsf{T}}X^{-1}c>0 D = det X r T X − 1 c > 0 . Likewise D ′ > 0 \mathcal{D}'>0 D ′ > 0 . So g A / g A ′ = D ′ / D g_A/g'_A=\mathcal{D}'/\mathcal{D} g A / g A ′ = D ′ / D , where the left side depends only on x A x_A x A and the right side only on x A c x_{A^c} x A c , and both are one constant. Since ( t I − Q A ) 1 = ( t + κ ) 1 (tI-Q_A)\mathbf{1}=(t+\kappa)\mathbf{1} ( t I − Q A ) 1 = ( t + κ ) 1 , we have g A ( t 1 ) = 1 / ( t + κ ) g_A(t\mathbf{1})=1/(t+\kappa) g A ( t 1 ) = 1/ ( t + κ ) , and likewise g A ′ ( t 1 ) = 1 / ( t + κ ′ ) g'_A(t\mathbf{1})=1/(t+\kappa') g A ′ ( t 1 ) = 1/ ( t + κ ′ ) , so the constant is 1 1 1 and κ ′ = κ \kappa'=\kappa κ ′ = κ . Hence g A ′ = g A g'_A=g_A g A ′ = g A and D ′ = D \mathcal{D}'=\mathcal{D} D ′ = D . With m i = 1 / x i m_i=1/x_i m i = 1/ x i , the expansion ( diag x A − Q A ) − 1 = ∑ k ≥ 0 ( diag m Q A ) k diag m (\operatorname{diag}x_A-Q_A)^{-1}=\sum_{k\ge0}(\operatorname{diag}m\,Q_A)^k\operatorname{diag}m ( diag x A − Q A ) − 1 = ∑ k ≥ 0 ( diag m Q A ) k diag m gives g A = ρ ⋅ m + O ( ∣ m ∣ 2 ) g_A=\rho\cdot m+O(|m|^2) g A = ρ ⋅ m + O ( ∣ m ∣ 2 ) , so ρ ′ = ρ \rho'=\rho ρ ′ = ρ , and μ A = m ρ = m ′ ρ \mu_A=m\rho=m'\rho μ A = m ρ = m ′ ρ gives m ′ = m m'=m m ′ = m . So Q / A Q/A Q / A and Q ′ / A Q'/A Q ′ / A have the same start μ / A \mu/A μ / A . Expanding along the row a a a , det ( diag ( x A c , u ) − Q / A ) = ( u + κ ) det X − D \det(\operatorname{diag}(x_{A^c},u)-Q/A)=(u+\kappa)\det X-\mathcal{D} det ( diag ( x A c , u ) − Q / A ) = ( u + κ ) det X − D , and same holds for Q ′ / A Q^{\prime}/A Q ′ / A . By Lemma 4.6 for Q Q Q and for Q ′ Q^{\prime} Q ′ , with u A = 1 / g A ( x A ) − κ u_A=1/g_A(x_A)-\kappa u A = 1/ g A ( x A ) − κ , which equals t t t at x A = t 1 x_A=t1 x A = t 1 ,
F Q ′ / A μ / A ( x A c , t ) = F Q ′ μ ( x A c , t 1 ) = F Q μ ( x A c , t 1 ) = F Q / A μ / A ( x A c , t ) F^{\mu/A}_{Q^{\prime}/A}(x_{A^c},t)=F^{\mu}_{Q^{\prime}}(x_{A^c},t1)=F^{\mu}_{Q}(x_{A^c},t1)=F^{\mu/A}_{Q/A}(x_{A^c},t) F Q ′ / A μ / A ( x A c , t ) = F Q ′ μ ( x A c , t 1 ) = F Q μ ( x A c , t 1 ) = F Q / A μ / A ( x A c , t )
for all x A c ∈ ( 0 , ∞ ) A c x_{A^c}\in(0,\infty)^{A^c} x A c ∈ ( 0 , ∞ ) A c and t > 0 t>0 t > 0 . So the 2 rational functions agree, and Q ′ / A Q^{\prime}/A Q ′ / A is in the fiber of ( Q / A , μ / A ) (Q/A,\mu/A) ( Q / A , μ / A ) by Lemma 4.1(a).
For the interior, Lemma 4.4 (a) holds with the same proof for every square matrix in place of Q Q Q and every row vector in place of μ \mu μ . Applied to Q A Q_A Q A and ρ \rho ρ , it gives det ( diag ( x A , t ) − N ) = det X A ( t − g A ) \det(\operatorname{diag}(x_A,t)-N)=\det X_A(t-g_A) det ( diag ( x A , t ) − N ) = det X A ( t − g A ) for
N = ( Q A 1 ρ 0 ) , N=\begin{pmatrix} Q_A & 1 \\ \rho& 0 \end{pmatrix}, N = ( Q A ρ 1 0 ) ,
and the same with Q A ′ Q^{\prime}_A Q A ′ for the analogous N ′ N^{\prime} N ′ . So N N N and N ′ N^{\prime} N ′ have the same principal minors, and so have N + diag ( κ 1 A , 0 ) = M ( L A , ρ ) N+\operatorname{diag}(\kappa1_A,0)=M(L_A,\rho) N + diag ( κ 1 A , 0 ) = M ( L A , ρ ) and M ( L A ′ , ρ ) M(L^{\prime}_A,\rho) M ( L A ′ , ρ ) , since the principal minors of a matrix determine those of its diagonal shifts. The matrix M ( L A , ρ ) M(L_A,\rho) M ( L A , ρ ) is irreducible, since every state of A A A is reached from supp ρ \operatorname{supp}\rho supp ρ by L A L_A L A and has the edge to ∂ \partial ∂ . Suppose that it has a cut, and let C ⊆ A C\subseteq A C ⊆ A be the side avoiding ∂ \partial ∂ , so 2 ≤ ∣ C ∣ ≤ ∣ A ∣ − 1 2\leq|C|\leq|A|-1 2 ≤ ∣ C ∣ ≤ ∣ A ∣ − 1 . Then L A [ C , A ∖ C ] = 1 s ⊤ L_A[C,A\setminus C]=1s^{\top} L A [ C , A ∖ C ] = 1 s ⊤ , and the rows of L A [ A ∖ C , C ] L_A[A\setminus C,C] L A [ A ∖ C , C ] and ρ C \rho_C ρ C are multiples of one law σ \sigma σ on C C C . So C C C has uniform exits for Q Q Q , since the exits of A A A to A c A^c A c are uniform, its entries from A c A^c A c are the rows c y ρ C c_y\rho_C c y ρ C , which are multiples of σ \sigma σ , and μ C = m ρ C \mu_C=m\rho_C μ C = m ρ C is a multiple of σ \sigma σ . So C C C is a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) inside A A A , which is excluded. If ∣ A ∣ ≥ 3 |A|\geq3 ∣ A ∣ ≥ 3 , Loewy’s theorem [24 Theorem 1] applies to M ( L A , ρ ) M(L_A,\rho) M ( L A , ρ ) , and if ∣ A ∣ = 2 |A|=2 ∣ A ∣ = 2 the theorem of Hartfiel and Loewy [20 Theorem 3] does, as in the proof of Theorem 4.5 . They give an invertible diagonal E E E with M ( L A ′ , ρ ) = E − 1 M ( L A , ρ ) E M(L^{\prime}_A,\rho)=E^{-1}M(L_A,\rho)E M ( L A ′ , ρ ) = E − 1 M ( L A , ρ ) E or M ( L A ′ , ρ ) = E − 1 M ( L A , ρ ) ⊤ E M(L^{\prime}_A,\rho)=E^{-1}M(L_A,\rho)^{\top}E M ( L A ′ , ρ ) = E − 1 M ( L A , ρ ) ⊤ E . In the first case the entries ( i , ∂ ) (i,\partial) ( i , ∂ ) give 1 = E ∂ / E i 1=E_{\partial}/E_i 1 = E ∂ / E i , so E E E is a multiple of I I I and L A ′ = L A L^{\prime}_A=L_A L A ′ = L A . In the second case they give 1 = ρ i E ∂ / E i 1=\rho_iE_{\partial}/E_i 1 = ρ i E ∂ / E i , so ρ i ≠ 0 \rho_i\ne0 ρ i = 0 , E i = ρ i E ∂ E_i=\rho_iE_{\partial} E i = ρ i E ∂ and ( L A ′ ) i j = ρ j ( L A ) j i / ρ i (L^{\prime}_A)_{ij}=\rho_j(L_A)_{ji}/\rho_i ( L A ′ ) ij = ρ j ( L A ) j i / ρ i . The rows of L A ′ L^{\prime}_A L A ′ sum to 0 0 0 , so ρ L A = 0 \rho L_A=0 ρ L A = 0 , and L A ′ = D ρ − 1 L A ⊤ D ρ L^{\prime}_A=D_{\rho}^{-1}L_A^{\top}D_{\rho} L A ′ = D ρ − 1 L A ⊤ D ρ . Subtracting κ I \kappa I κ I gives the claim.
The next step shows that the renewal blocks that contain no smaller one are shared by the whole fiber. It uses 2 lemmas of Chatterjee, Ghosh, Gurjar and Raj, stated for matrices with nonzero off-diagonal entries, so we first transfer them. We use their notions: a cut of a matrix of order n ≥ 4 n\geq4 n ≥ 4 is a set X X X of indices with 2 ≤ ∣ X ∣ ≤ n − 2 2\leq|X|\leq n-2 2 ≤ ∣ X ∣ ≤ n − 2 such that both off-diagonal blocks between X X X and its complement have rank at most one [8 Definition 2.5] , so X X X is a cut exactly when its complement is, and a cut is minimal if it contains no other cut. Their Lemma 3.5 says the following. If A A A and B B B are n × n n\times n n × n matrices over a field with nonzero off-diagonal entries and the same principal minors, and S = { s 1 , s 2 } S=\{s_1,s_2\} S = { s 1 , s 2 } is a cut of A A A , then either S S S is a cut of B B B , or for each i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } the set X i = { t ∉ S : A [ S ∪ { t } ] is diagonally similar to B [ S ∪ { t } ] } ∪ { s i } X_i=\{t\notin S:A[S\cup\{t\}] \text{ is diagonally similar to } B[S\cup\{t\}]\}\cup\{s_i\} X i = { t ∈ / S : A [ S ∪ { t }] is diagonally similar to B [ S ∪ { t }]} ∪ { s i } is a cut of B B B , and S S S is a cut of ct ( B , X i ) \operatorname{ct}(B,X_i) ct ( B , X i ) . Their Lemma 3.6 says that under the same hypothesis on A A A and B B B , a minimal cut of A A A with more than 2 elements is a cut of B B B .
Lemma 4.31 (two lemmas of Chatterjee, Ghosh, Gurjar and Raj, with zero entries). Let M M M and M ′ M^{\prime} M ′ be irreducible real matrices of order n ≥ 4 n\geq4 n ≥ 4 with the same principal minors.
(a) A minimal cut of M M M with at least 3 elements is a cut of M ′ M^{\prime} M ′ .
(b) If S = { s 1 , s 2 } S=\{s_1,s_2\} S = { s 1 , s 2 } is a cut of M M M , then S S S is a cut of M ′ M^{\prime} M ′ , or M ′ M^{\prime} M ′ has the cuts P ∪ { s 1 } P\cup\{s_1\} P ∪ { s 1 } and P ∪ { s 2 } P\cup\{s_2\} P ∪ { s 2 } for some set P P P of indices disjoint from S S S .
Proof. By the theorem of Hartfiel and Loewy [20 Theorem 1] , every entry of adj ( diag z + M ) \operatorname{adj}(\operatorname{diag}z+M) adj ( diag z + M ) is a nonzero polynomial in z z z , and so is every entry of adj ( diag z + M ′ ) \operatorname{adj}(\operatorname{diag}z+M^{\prime}) adj ( diag z + M ′ ) , since M M M and M ′ M^{\prime} M ′ are irreducible. The determinants det ( diag z + M ) \det(\operatorname{diag}z+M) det ( diag z + M ) and det ( diag z + M ′ ) \det(\operatorname{diag}z+M^{\prime}) det ( diag z + M ′ ) are nonzero polynomials as well, with the coefficient 1 1 1 at z 1 ⋯ z n z_1\cdots z_n z 1 ⋯ z n . So there is a real diagonal Z Z Z such that M + Z M+Z M + Z and M ′ + Z M^{\prime}+Z M ′ + Z are invertible and M ‾ = ( M + Z ) adj \overline{M}=(M+Z)^{\operatorname{adj}} M = ( M + Z ) adj and M ‾ ′ = ( M ′ + Z ) adj \overline{M}^{\prime}=(M^{\prime}+Z)^{\operatorname{adj}} M ′ = ( M ′ + Z ) adj have nonzero off-diagonal entries. By [8 Lemma 2.1] they have the same principal minors, and by [8 Lemma 2.6] M ‾ \overline{M} M has exactly the cuts of M M M and M ~ ′ \widetilde{M}' M ′ exactly those of M ′ M' M ′ . Since the cuts are the same sets, so are the minimal cuts. Now (a) is [8 Lemma 3.6] for M ~ \widetilde{M} M and M ~ ′ \widetilde{M}' M ′ , and (b) is the first part of [8 Lemma 3.5] for them, with X i = P ∪ { s i } X_i=P\cup\{s_i\} X i = P ∪ { s i } . The second part of that lemma, on ct ( M ~ ′ , X i ) \operatorname{ct}(\widetilde{M}',X_i) ct ( M ′ , X i ) , transfers as well by [8 Lemma 2.13] , but we do not need it.
The case of 2 states needs more than the cuts: Lemma Lemma A.3, proved in Appendix § 6 , shows that the second alternative of Lemma Lemma 4.31(b) forces the block anyway.
Proposition 4.32 (shared blocks). Let Q ′ Q' Q ′ be in the fiber of ( Q , μ ) (Q,\mu) ( Q , μ ) . Then every renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) with 2 states, and every renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) that contains no smaller one, is a renewal block of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) .
Proof. Let A A A be such a block. Since ∣ A ∣ ≤ d − 1 |A|\le d-1 ∣ A ∣ ≤ d − 1 , d ≥ 3 d\ge3 d ≥ 3 , and M = M ( Q , μ ) M=M(Q,\mu) M = M ( Q , μ ) and M ′ = M ( Q ′ , μ ) M'=M(Q',\mu) M ′ = M ( Q ′ , μ ) have order at least 4. They are irreducible and have the same principal minors (Lemma Lemma 4.4 ), and A A A is a cut of M M M by Lemma Lemma 4.4 (c). Every cut of M M M or of M ′ M' M ′ has exactly one side avoiding ∂ \partial ∂ , and by Lemma Lemma 4.4 (c) the sides avoiding ∂ \partial ∂ are the renewal blocks of ( Q , μ ) (Q,\mu) ( Q , μ ) and of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) .
If A A A contains no smaller renewal block and ∣ A ∣ ≥ 3 |A|\ge3 ∣ A ∣ ≥ 3 , then A A A is a minimal cut of M M M : a cut inside A A A avoids ∂ \partial ∂ , so it is a renewal block inside A A A . By Lemma Lemma 4.31(a) it is a cut of M ′ M' M ′ , hence a renewal block of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) .
Let A = { 1 , 2 } A=\{1,2\} A = { 1 , 2 } . By Lemma Lemma 4.31(b), either A A A is a cut of M ′ M' M ′ , and so a renewal block of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) , or M ′ M' M ′ has the cuts X 1 = P ∪ { 1 } X_1=P\cup\{1\} X 1 = P ∪ { 1 } and X 2 = P ∪ { 2 } X_2=P\cup\{2\} X 2 = P ∪ { 2 } for a set P P P of indices in ( [ d ] ∪ { ∂ } ) ∖ A ([d]\cup\{\partial\})\setminus A ([ d ] ∪ { ∂ }) ∖ A . If ∂ ∉ P \partial\notin P ∂ ∈ / P , then X 1 X_1 X 1 and X 2 X_2 X 2 avoid ∂ \partial ∂ , so P ∪ { 1 } P\cup\{1\} P ∪ { 1 } and P ∪ { 2 } P\cup\{2\} P ∪ { 2 } are renewal blocks of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) , and P ≠ ∅ P\ne\varnothing P = ∅ since ∣ X 1 ∣ ≥ 2 |X_1|\ge2 ∣ X 1 ∣ ≥ 2 . If ∂ ∈ P \partial\in P ∂ ∈ P , the sides avoiding ∂ \partial ∂ are the complements W ∪ { 2 } W\cup\{2\} W ∪ { 2 } and W ∪ { 1 } W\cup\{1\} W ∪ { 1 } with W = [ d ] ∖ ( P ∪ A ) W=[d]\setminus(P\cup A) W = [ d ] ∖ ( P ∪ A ) , and W ≠ ∅ W\ne\varnothing W = ∅ since the complement of X 1 X_1 X 1 has at least 2 elements. In both cases Lemma Lemma A.3, with Y = P Y=P Y = P or Y = W Y=W Y = W , shows that A A A is a renewal block of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) .
In particular every renewal block with 2 states is shared by all members of the fiber.
The last tool lifts lumped reversals of a lumped pair. Let A A A be a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) with the data ρ \rho ρ , κ A \kappa_A κ A , m m m . For a generator S S S on A c ∪ { a } A^c\cup\{a\} A c ∪ { a } with S a a = − κ A S_{aa}=-\kappa_A S aa = − κ A , let un A ( S ) \operatorname{un}_A(S) un A ( S ) be the matrix R R R on [ d ] [d] [ d ] with R i y = S a y R_{iy}=S_{ay} R i y = S a y and R y i = S y a ρ i R_{yi}=S_{ya}\rho_i R y i = S y a ρ i for i ∈ A i\in A i ∈ A and y ∈ A c y\in A^c y ∈ A c , with the off-diagonal entries of S S S on A c × A c A^c\times A^c A c × A c , with R A = Q A R_A=Q_A R A = Q A , and with R y y = S y y R_{yy}=S_{yy} R y y = S y y for y ∈ A c y\in A^c y ∈ A c . Its rows sum to 0: for y ∈ A c y\in A^c y ∈ A c since ρ \rho ρ is a law, and for i ∈ A i\in A i ∈ A since Q A 1 = − κ A 1 Q_A\mathbf{1}=-\kappa_A\mathbf{1} Q A 1 = − κ A 1 and ∑ y S a y = κ A \sum_y S_{ay}=\kappa_A ∑ y S a y = κ A . So R R R is a generator, A A A is a renewal block of ( R , μ ) (R,\mu) ( R , μ ) with the data ρ \rho ρ , κ A \kappa_A κ A , m m m , and R / A = S R/A=S R / A = S . For S = Q / A S=Q/A S = Q / A it is Q Q Q , and for a family P = { A } \mathcal{P}=\{A\} P = { A } it is un P ( S ) \operatorname{un}_{\mathcal{P}}(S) un P ( S ) of Section § 4.6 .
Lemma 4.33 (lifting). Let S S S be an irreducible generator on A c ∪ { a } A^c\cup\{a\} A c ∪ { a } with S a a = − κ A S_{aa}=-\kappa_A S aa = − κ A such that R = un A ( S ) R=\operatorname{un}_A(S) R = un A ( S ) is irreducible, and let S ′ S' S ′ be a lumped reversal of ( S , μ / A ) (S,\mu/A) ( S , μ / A ) . Then un A ( S ′ ) \operatorname{un}_A(S') un A ( S ′ ) is a lumped reversal of ( R , μ ) (R,\mu) ( R , μ ) .
Proof. Write ν = μ / A \nu=\mu/A ν = μ / A , let P \mathcal{P} P be the family of renewal blocks of ( S , ν ) (S,\nu) ( S , ν ) of the lumped reversal, and R ~ \widetilde{R} R the generator on the atoms with S ′ = un P ( R ~ ) S'=\operatorname{un}_{\mathcal{P}}(\widetilde{R}) S ′ = un P ( R ) . For P ∈ P P\in\mathcal{P} P ∈ P with a ∉ P a\notin P a ∈ / P put P ^ = P \widehat{P}=P P = P , for P ∋ a P\ni a P ∋ a put P ^ = ( P ∖ { a } ) ∪ A \widehat{P}=(P\setminus\{a\})\cup A P = ( P ∖ { a }) ∪ A , and let P ^ \widehat{\mathcal{P}} P consist of these sets, together with A A A if no member of P \mathcal{P} P contains a a a . The members of P ^ \widehat{\mathcal{P}} P are pairwise disjoint. We show that they are renewal blocks of ( R , μ ) (R,\mu) ( R , μ ) . Recall that R i y = S a y R_{iy}=S_{ay} R i y = S a y and R y i = S y a ρ i R_{yi}=S_{ya}\rho_i R y i = S y a ρ i for i ∈ A i\in A i ∈ A and y ∈ A c y\in A^c y ∈ A c , that R R R agrees with S S S on A c × A c A^c\times A^c A c × A c off the diagonal, and that μ A = m ρ \mu_A=m\rho μ A = m ρ with ν a = m \nu_a=m ν a = m . Let P ∈ P P\in\mathcal{P} P ∈ P have the entry law σ \sigma σ for S S S .
If a ∉ P a\notin P a ∈ / P , then P ⊆ A c P\subseteq A^c P ⊆ A c . A state p ∈ P p\in P p ∈ P jumps to y ∈ A c ∖ P y\in A^c\setminus P y ∈ A c ∖ P at the rate S p y S_{py} S p y and to i ∈ A i\in A i ∈ A at the rate S p a ρ i S_{pa}\rho_i S p a ρ i , and both do not depend on p p p . A state y ∈ A c ∖ P y\in A^c\setminus P y ∈ A c ∖ P jumps into P P P with the rates S y P S_{yP} S y P , and i ∈ A i\in A i ∈ A with the rates S a P S_{aP} S a P , and both are multiples of σ \sigma σ , as is μ P = ν P \mu_P=\nu_P μ P = ν P . Also 2 ≤ ∣ P ∣ ≤ d − 1 2\le|P|\le d-1 2 ≤ ∣ P ∣ ≤ d − 1 .
If a ∈ P a\in P a ∈ P , then P ^ \widehat{P} P is left to y ∉ P ^ y\notin\widehat{P} y ∈ / P at the rates S p y S_{py} S p y from p ∈ P ∖ { a } p\in P\setminus\{a\} p ∈ P ∖ { a } and S a y S_{ay} S a y from A A A , which agree. A state y ∉ P ^ y\notin\widehat{P} y ∈ / P jumps to j ∈ P ∖ { a } j\in P\setminus\{a\} j ∈ P ∖ { a } at the rate S y j S_{yj} S y j and to i ∈ A i\in A i ∈ A at the rate S y a ρ i S_{ya}\rho_i S y a ρ i , so its rates into P ^ \widehat{P} P are S y P S y_P S y P spread by ρ \rho ρ over A A A , a multiple of the law σ ^ \widehat{\sigma} σ with σ ^ j = σ j \widehat{\sigma}_j = \sigma_j σ j = σ j off A A A and σ ^ i = σ a ρ i \widehat{\sigma}_i = \sigma_a\rho_i σ i = σ a ρ i on A A A . Likewise μ P ^ \mu_{\widehat{P}} μ P is ν P \nu_P ν P spread in the same way, a multiple of σ ^ \widehat{\sigma} σ . Also 3 ≤ ∣ P ^ ∣ = ∣ P ∣ − 1 + ∣ A ∣ ≤ d − 1 3 \leq|\widehat{P}| = |P| - 1 + |A| \leq d - 1 3 ≤ ∣ P ∣ = ∣ P ∣ − 1 + ∣ A ∣ ≤ d − 1 , since ∣ P ∣ ≤ ∣ A c ∣ |P| \leq|A^c| ∣ P ∣ ≤ ∣ A c ∣ . Finally A A A itself is a renewal block of ( R , μ ) (R,\mu) ( R , μ ) .
The atoms of P ^ \widehat{P} P correspond to the atoms of P P P , and the rate between 2 atoms is in both cases the sum of the rates into the second atom from any state of the first, so R / P ^ = S / P R/\widehat{P} = S/P R / P = S / P , with the same start and the same stationary law, π \pi π summed over the atoms. So R ~ \widetilde{R} R is an admissible choice in Definition 4.24 for ( R , μ ) (R,\mu) ( R , μ ) and P ^ \widehat{P} P , and un P ^ ( R ~ ) \operatorname{un}_{\widehat{P}}(\widetilde{R}) un P ( R ) is a lumped reversal of ( R , μ ) (R,\mu) ( R , μ ) . It equals un A ( S ′ ) \operatorname{un}_A(S') un A ( S ′ ) . Both have the blocks of R R R on the members of P ^ \widehat{P} P , since un P \operatorname{un}_P un P keeps the block of S S S on P P P and un A \operatorname{un}_A un A then restores the block of R R R on P ^ \widehat{P} P . Both have the diagonal of R R R . Between different atoms both have the entries R ~ U V \widetilde{R}_{UV} R U V times the entry law of V V V for R R R , which is σ ^ \widehat{\sigma} σ for V = P ^ V = \widehat{P} V = P , ρ \rho ρ for V = A V = A V = A and 1 1 1 for a single state.
Proof of Theorem 4.26. The if part and the irreducibility of every generator reached are Theorem 4.25 , and μ ′ = μ \mu' = \mu μ ′ = μ is Lemma 4.4 (b). For the only if part let Q ′ Q' Q ′ be in the fiber of ( Q , μ ) (Q,\mu) ( Q , μ ) . We argue by induction on d d d . If ( Q , μ ) (Q,\mu) ( Q , μ ) has no renewal block, which holds when d ≤ 2 d \leq2 d ≤ 2 , then by Theorem 4.5 either Q ′ = Q Q' = Q Q ′ = Q , or μ = π \mu= \pi μ = π and Q ′ = Q ∗ Q' = Q^* Q ′ = Q ∗ , which is the lumped reversal with P = ∅ P = \varnothing P = ∅ and R ~ = Q ∗ \widetilde{R} = Q^* R = Q ∗ .
Otherwise let A A A be a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) that contains no smaller one. By Proposition 4.32 it is a renewal block of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) , so by Lemma 4.30 it has the same ρ \rho ρ , κ A \kappa_A κ A and m m m for Q Q Q and Q ′ Q' Q ′ , and Q ′ / A Q'/A Q ′ / A is in the fiber of ( Q / A , μ / A ) (Q/A,\mu/A) ( Q / A , μ / A ) , a pair on d − ∣ A ∣ + 1 < d d - |A| + 1 < d d − ∣ A ∣ + 1 < d states with an irreducible generator. By induction there are generators Q / A = S 0 , S 1 , … , S k = Q ′ / A Q/A = S_0, S_1, \ldots, S_k = Q'/A Q / A = S 0 , S 1 , … , S k = Q ′ / A , each S j + 1 S_{j+1} S j + 1 a lumped reversal of ( S j , μ / A ) (S_j,\mu/A) ( S j , μ / A ) . All of them are irreducible and have the diagonal of Q / A Q/A Q / A , since lumped reversals keep the diagonal, so S j , a a = − κ A S_{j,aa} = -\kappa_A S j , aa = − κ A . By Lemma 4.33 and induction on j j j , using Theorem 4.25 for the irreducibility of un A ( S j ) \operatorname{un}_A(S_j) un A ( S j ) , each un A ( S j + 1 ) \operatorname{un}_A(S_{j+1}) un A ( S j + 1 ) is a lumped reversal of ( un A ( S j ) , μ ) (\operatorname{un}_A(S_j),\mu) ( un A ( S j ) , μ ) , and un A ( S 0 ) = Q \operatorname{un}_A(S_0) = Q un A ( S 0 ) = Q . So R = un A ( Q ′ / A ) R = \operatorname{un}_A(Q'/A) R = un A ( Q ′ / A ) is reached from Q Q Q by lumped reversals. The generators Q ′ Q' Q ′ and R R R have the same lumped generator Q ′ / A Q'/A Q ′ / A and the same entry law ρ \rho ρ of A A A , so they agree off A × A A \times A A × A , and R A = Q A R_A = Q_A R A = Q A . By Lemma 4.30 , either Q A ′ = Q A Q'_A = Q_A Q A ′ = Q A , and then Q ′ = R Q' = R Q ′ = R , or ρ L A = 0 \rho L_A = 0 ρ L A = 0 and Q A ′ = D ρ − 1 Q A ⊤ D ρ Q'_A = D_\rho^{-1} Q_A^\top D_\rho Q A ′ = D ρ − 1 Q A ⊤ D ρ . In the second case L A = R A + κ A I L_A = R_A + \kappa_A I L A = R A + κ A I is also the interior of A A A for R R R , so by Lemma 4.29 A A A is a memoryless block of R R R with ρ = π A R / π R ( A ) \rho= \pi_A^R/\pi^R(A) ρ = π A R / π R ( A ) , where π R \pi^R π R is the stationary law of R R R , and μ A = m ρ \mu_A = m\rho μ A = m ρ is proportional to π A R \pi_A^R π A R . So R [ A ] R^{[A]} R [ A ] , which replaces R A R_A R A by D ρ − 1 R A ⊤ D ρ D_\rho^{-1}R_A^\top D_\rho D ρ − 1 R A ⊤ D ρ , is the lumped reversal of ( R , μ ) (R,\mu) ( R , μ ) with P = ∅ P = \varnothing P = ∅ and B ~ = A \widetilde{B} = A B = A , and Q ′ = R [ A ] Q' = R^{[A]} Q ′ = R [ A ] .
Computations and open questions
Every statement is proved in the text. The explicit numbers in Example 4.11 were computed in rational arithmetic, and the scripts verify_exactly.py and verify_reconstruction.py, which verify_all.py runs, check them, together with Corollary 3.7 (c) on random generators and the derivative (1) . The script verify_lumped.py, also run by verify_all.py, checks Example 4.27 in exact arithmetic: the stationary law, Q ′ ′ ≠ Q Q'' \ne Q Q ′′ = Q , the value of both transforms, and the equality of the 128 principal minors of M ( Q , e 4 ) M(Q,e_4) M ( Q , e 4 ) and M ( Q ′ ′ , e 4 ) M(Q'',e_4) M ( Q ′′ , e 4 ) . Some finite and algebraic steps are also proved in Lean 4 with Mathlib; the code is in the ancillary files. There the positive null vector of Lemma 3.5 is a hypothesis, since Mathlib has no Perron and Frobenius theorem for irreducible Metzler matrices. One question remains open: how many visits of the discrete chain does one stationary count law need to determine the principal minors?
Use of AI in the research. We wrote the proofs in this paper. An AI model (Claude Opus 5.5) was used as follows. It suggested bordering the generator by the start (Lemma 4.4 ) and applying Loewy’s theorem to the bordered matrix (Theorem 4.5 and Remark 4.14 ), and it proposed a first conjecture for general starts, which was false; we found the counterexample and proved Theorem 4.26 . The model was also used to search the literature and check citations, and to check proofs for errors. The Lean code was generated by Claude Opus 5.5 from our outlines of the written proofs; it covers the finite and algebraic steps mentioned above and assumes the positive null vector of Lemma 3.5 . We verified all statements and proofs and take full responsibility for them.
Two-state renewal blocks
This appendix proves Lemma A.3, which Proposition 4.32 uses for renewal blocks with 2 states. We first record what P Q ′ = P Q P_{Q'} = P_Q P Q ′ = P Q says near such a block.
Lemma A.1 (invariants). Let A = { 1 , 2 } A = \{1,2\} A = { 1 , 2 } have uniform exits and rank-one entries for Q Q Q , so q 1 j = q 2 j = r j q_{1j}=q_{2j}=r_j q 1 j = q 2 j = r j and ( q j 1 , q j 2 ) = c j ( ρ 1 , ρ 2 ) (q_{j1},q_{j2})=c_j(\rho_1,\rho_2) ( q j 1 , q j 2 ) = c j ( ρ 1 , ρ 2 ) for j ∉ A j \notin A j ∈ / A . Put α = q 12 \alpha=q_{12} α = q 12 and β = q 21 \beta=q_{21} β = q 21 , and let Q ′ Q' Q ′ be a generator with P Q ′ = P Q P_{Q'}=P_Q P Q ′ = P Q .
(a) q i i ′ = q i i q'_{ii}=q_{ii} q ii ′ = q ii , q i j ′ q j i ′ = q i j q j i q'_{ij}q'_{ji}=q_{ij}q_{ji} q ij ′ q j i ′ = q ij q j i and q k j ′ q j k ′ q i k ′ + q i k ′ q k j ′ q j i ′ = q i j q j k q k i + q i k q k j q j i q'_{kj}q'_{jk}q'_{ik}+q'_{ik}q'_{kj}q'_{ji}=q_{ij}q_{jk}q_{ki}+q_{ik}q_{kj}q_{ji} q k j ′ q j k ′ q ik ′ + q ik ′ q k j ′ q j i ′ = q ij q j k q k i + q ik q k j q j i for distinct i , j , k i,j,k i , j , k .
(b) For x ∈ ( 0 , ∞ ) A c x\in(0,\infty)^{A^c} x ∈ ( 0 , ∞ ) A c put G = ( diag x − Q A c ′ ) − 1 G=(\operatorname{diag}x-Q'_{A^c})^{-1} G = ( diag x − Q A c ′ ) − 1 , W = Q ′ [ A , A c ] G Q ′ [ A c , A ] W=Q'[A,A^c]GQ'[A^c,A] W = Q ′ [ A , A c ] G Q ′ [ A c , A ] , a 2 × 2 2\times2 2 × 2 matrix, and w = r T ( diag x − Q A c ) − 1 c w=r^{\mathsf T}(\operatorname{diag}x-Q_{A^c})^{-1}c w = r T ( diag x − Q A c ) − 1 c . Then W 11 = ρ 1 w W_{11}=\rho_1w W 11 = ρ 1 w , W 22 = ρ 2 w W_{22}=\rho_2w W 22 = ρ 2 w and q 12 ′ W 21 + q 21 ′ W 12 − det W = w ( ρ 1 α + ρ 2 β ) q'_{12}W_{21}+q'_{21}W_{12}-\det W=w(\rho_1\alpha+\rho_2\beta) q 12 ′ W 21 + q 21 ′ W 12 − det W = w ( ρ 1 α + ρ 2 β ) .
Proof. (a) The coefficient of ∏ k ∉ S x k \prod_{k\notin S}x_k ∏ k ∈ / S x k in P Q ( x ) P_Q(x) P Q ( x ) is det ( − Q S ) \det(-Q_S) det ( − Q S ) , so Q Q Q and Q ′ Q' Q ′ have the same principal minors. Those of order 1 give the diagonal. With the diagonal equal, those of order 2, q i i q j j − q i j q j i q_{ii}q_{jj}-q_{ij}q_{ji} q ii q j j − q ij q j i , give the products. With both equal, the expansion of det ( − Q { i , j , k } ) \det(-Q_{\{i,j,k\}}) det ( − Q { i , j , k } ) leaves the sum of the 2 cyclic products as the only other term.
(b) Fix x x x and let x 1 , x 2 > 0 x_1,x_2>0 x 1 , x 2 > 0 . By Lemma 4.28 , X = diag x − Q A c X=\operatorname{diag}x-Q_{A^c} X = diag x − Q A c and diag x − Q A c ′ \operatorname{diag}x-Q'_{A^c} diag x − Q A c ′ are invertible, with the same determinant, a principal minor polynomial of A c A^c A c . The formula of Schur gives P Q ( x 1 , x 2 , x ) = det X det ( X A − Q [ A , A c ] X − 1 Q [ A c , A ] ) P_Q(x_1,x_2,x)=\det X\det(X_A-Q[A,A^c]X^{-1}Q[A^c,A]) P Q ( x 1 , x 2 , x ) = det X det ( X A − Q [ A , A c ] X − 1 Q [ A c , A ]) , with X A = diag ( x 1 , x 2 ) − Q A X_A=\operatorname{diag}(x_1,x_2)-Q_A X A = diag ( x 1 , x 2 ) − Q A , and the same for Q ′ Q' Q ′ , so the 2 determinants of order 2 agree for all x 1 , x 2 > 0 x_1,x_2>0 x 1 , x 2 > 0 . For Q Q Q we have Q [ A , A c ] X − 1 Q [ A c , A ] = w 1 ρ T Q[A,A^c]X^{-1}Q[A^c,A]=w\mathbf{1}\rho^{\mathsf T} Q [ A , A c ] X − 1 Q [ A c , A ] = w 1 ρ T , and
det ( x 1 − q 11 − w ρ 1 − α − w ρ 2 − β − w ρ 1 x 2 − q 22 − w ρ 2 ) = det X A − w ρ 2 ( x 1 − q 11 ) − w ρ 1 ( x 2 − q 22 ) − w ( ρ 1 α + ρ 2 β ) . \det\begin{pmatrix} x_1-q_{11}-w\rho_1 & -\alpha-w\rho_2 \\ -\beta-w\rho_1 & x_2-q_{22}-w\rho_2 \end{pmatrix}
=\det X_A-w\rho_2(x_1-q_{11})-w\rho_1(x_2-q_{22})-w(\rho_1\alpha+\rho_2\beta). det ( x 1 − q 11 − w ρ 1 − β − w ρ 1 − α − w ρ 2 x 2 − q 22 − w ρ 2 ) = det X A − w ρ 2 ( x 1 − q 11 ) − w ρ 1 ( x 2 − q 22 ) − w ( ρ 1 α + ρ 2 β ) .
For Q ′ Q' Q ′ the same expansion gives det X A ′ − W 22 ( x 1 − q 11 ′ ) − W 11 ( x 2 − q 22 ′ ) + det W − q 12 ′ W 21 − q 21 ′ W 12 \det X'_A-W_{22}(x_1-q'_{11})-W_{11}(x_2-q'_{22})+\det W-q'_{12}W_{21}-q'_{21}W_{12} det X A ′ − W 22 ( x 1 − q 11 ′ ) − W 11 ( x 2 − q 22 ′ ) + det W − q 12 ′ W 21 − q 21 ′ W 12 , with X A ′ = diag ( x 1 , x 2 ) − Q A ′ X'_A=\operatorname{diag}(x_1,x_2)-Q'_A X A ′ = diag ( x 1 , x 2 ) − Q A ′ . Here det X A ′ = det X A \det X'_A=\det X_A det X A ′ = det X A and q i i ′ = q i i q'_{ii}=q_{ii} q ii ′ = q ii by (a). After cancelling det X A \det X_A det X A both sides are affine in x 1 x_1 x 1 and in x 2 x_2 x 2 , without a term x 1 x 2 x_1x_2 x 1 x 2 , and they agree on an open set. The coefficients of x 1 x_1 x 1 and of x 2 x_2 x 2 and the constant terms give the 3 identities.
Lemma A.2 (the shape of Q ′ Q' Q ′ ). Let Q ′ Q' Q ′ be irreducible, let Y ⊆ [ d ] ∖ { 1 , 2 } Y\subseteq[d]\setminus\{1,2\} Y ⊆ [ d ] ∖ { 1 , 2 } be nonempty, and let B 1 = Y ∪ { 1 } B_1=Y\cup\{1\} B 1 = Y ∪ { 1 } and B 2 = Y ∪ { 2 } B_2=Y\cup\{2\} B 2 = Y ∪ { 2 } be renewal blocks of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) , with entry laws σ 1 , σ 2 \sigma_1,\sigma_2 σ 1 , σ 2 and multiples m 1 , m 2 m_1,m_2 m 1 , m 2 . Put U = Y ∪ { 1 , 2 } U=Y\cup\{1,2\} U = Y ∪ { 1 , 2 } and K = [ d ] ∖ U K=[d]\setminus U K = [ d ] ∖ U , and write q i Y ′ q'_{iY} q iY ′ for the row vector ( q i y ′ ) y ∈ Y (q'_{iy})_{y\in Y} ( q i y ′ ) y ∈ Y and ∣ q i Y ′ ∣ |q'_{iY}| ∣ q iY ′ ∣ for its sum.
(a) There are ϵ ∈ [ 0 , ∞ ) K \epsilon\in[0,\infty)^K ϵ ∈ [ 0 , ∞ ) K and a , b ≥ 0 a,b\geq0 a , b ≥ 0 with q i k ′ = ϵ k q'_{ik}=\epsilon_k q ik ′ = ϵ k for i ∈ U i\in U i ∈ U and k ∈ K k\in K k ∈ K , and q y 2 ′ = q 12 ′ = a q'_{y2}=q'_{12}=a q y 2 ′ = q 12 ′ = a and q y 1 ′ = q 21 ′ = b q'_{y1}=q'_{21}=b q y 1 ′ = q 21 ′ = b for y ∈ Y y\in Y y ∈ Y . So q 11 ′ = − ( a + ∣ q 1 Y ′ ∣ + ∣ ϵ ∣ ) q'_{11}=-(a+|q'_{1Y}|+|\epsilon|) q 11 ′ = − ( a + ∣ q 1 Y ′ ∣ + ∣ ϵ ∣ ) and q 22 ′ = − ( b + ∣ q 2 Y ′ ∣ + ∣ ϵ ∣ ) q'_{22}=-(b+|q'_{2Y}|+|\epsilon|) q 22 ′ = − ( b + ∣ q 2 Y ′ ∣ + ∣ ϵ ∣ ) .
(b) ( b , q 1 Y ′ ) = c 1 1 σ 1 (b,q'_{1Y})=c^1_1\sigma_1 ( b , q 1 Y ′ ) = c 1 1 σ 1 , ( q k 1 ′ , q k Y ′ ) = c k 1 σ 1 (q'_{k1},q'_{kY})=c^1_k\sigma_1 ( q k 1 ′ , q k Y ′ ) = c k 1 σ 1 , ( a , q 1 Y ′ ) = c 1 2 σ 2 (a,q'_{1Y})=c^2_1\sigma_2 ( a , q 1 Y ′ ) = c 1 2 σ 2 and ( q k 2 ′ , q k Y ′ ) = c k 2 σ 2 (q'_{k2},q'_{kY})=c^2_k\sigma_2 ( q k 2 ′ , q k Y ′ ) = c k 2 σ 2 for k ∈ K k\in K k ∈ K , with all c j i ≥ 0 c^i_j\geq0 c j i ≥ 0 , and μ B i = m i σ i \mu_{B_i}=m_i\sigma_i μ B i = m i σ i .
(c) If b = 0 b=0 b = 0 , then q 2 Y ′ = 0 q'_{2Y}=0 q 2 Y ′ = 0 . If a = 0 a=0 a = 0 , then q 1 Y ′ = 0 q'_{1Y}=0 q 1 Y ′ = 0 .
(d) If b > 0 b > 0 b > 0 and q 2 Y ′ = 0 q'_{2Y} = 0 q 2 Y ′ = 0 , then no state of K ∪ { 2 } K \cup\{2\} K ∪ { 2 } jumps into Y Y Y . If a > 0 a > 0 a > 0 and q 1 Y ′ = 0 q'_{1Y} = 0 q 1 Y ′ = 0 , then no state of K ∪ { 1 } K \cup\{1\} K ∪ { 1 } jumps into Y Y Y .
(e) If q 1 Y ′ = q 2 Y ′ ≠ 0 q'_{1Y} = q'_{2Y} \ne0 q 1 Y ′ = q 2 Y ′ = 0 , or if a = b = 0 a = b = 0 a = b = 0 , then { 1 , 2 } \{1, 2\} { 1 , 2 } is a renewal block of ( Q ′ , μ ) (Q', \mu) ( Q ′ , μ ) .
Proof. (a) The uniform exits of B 1 B_1 B 1 say that the rows i ∈ B 1 i \in B_1 i ∈ B 1 agree on K ∪ { 2 } K \cup\{2\} K ∪ { 2 } , and those of B 2 B_2 B 2 that the rows i ∈ B 2 i \in B_2 i ∈ B 2 agree on K ∪ { 1 } K \cup\{1\} K ∪ { 1 } . Since Y ≠ ∅ Y \ne\varnothing Y = ∅ , the rows 1 1 1 , 2 2 2 and y ∈ Y y \in Y y ∈ Y agree on K K K , the rows 1 1 1 and y y y agree at 2 2 2 , and the rows 2 2 2 and y y y agree at 1 1 1 . The diagonal makes the rows sum to 0 0 0 .
(b) This is the condition on the entries. The rows of Q ′ [ B 1 c , B 1 ] Q'[B_1^c,B_1] Q ′ [ B 1 c , B 1 ] are the rows 2 2 2 and k ∈ K k \in K k ∈ K restricted to B 1 B_1 B 1 , and likewise for B 2 B_2 B 2 .
(c) Let b = 0 b = 0 b = 0 and suppose that q 2 Y ′ ≠ 0 q'_{2Y} \ne0 q 2 Y ′ = 0 . By (b), c 2 1 > 0 c_2^1 > 0 c 2 1 > 0 and σ 1 ( 1 ) = 0 \sigma_1(1) = 0 σ 1 ( 1 ) = 0 , so no state of K ∪ { 2 } K \cup\{2\} K ∪ { 2 } jumps to 1 1 1 , and by (a) no y ∈ Y y \in Y y ∈ Y does. So no state jumps to 1 1 1 , which contradicts irreducibility. The second claim is the same with 1 1 1 and 2 2 2 exchanged.
(d) By (b), c 2 1 σ 1 = ( b , 0 ) c_2^1 \sigma_1 = (b, 0) c 2 1 σ 1 = ( b , 0 ) with b > 0 b > 0 b > 0 , so σ 1 \sigma_1 σ 1 is the point mass at 1 1 1 , and by (b) again q k Y ′ = 0 q'_{kY} = 0 q k Y ′ = 0 for k ∈ K k \in K k ∈ K . The second claim is the same with 1 1 1 and 2 2 2 exchanged.
(e) First let v = q 1 Y ′ = q 2 Y ′ ≠ 0 v = q'_{1Y} = q'_{2Y} \ne0 v = q 1 Y ′ = q 2 Y ′ = 0 . By (c), a > 0 a > 0 a > 0 and b > 0 b > 0 b > 0 . By (b), σ 1 = ( b , v ) / ( b + ∣ v ∣ ) \sigma_1 = (b, v)/(b + |v|) σ 1 = ( b , v ) / ( b + ∣ v ∣ ) and σ 2 = ( a , v ) / ( a + ∣ v ∣ ) \sigma_2 = (a, v)/(a + |v|) σ 2 = ( a , v ) / ( a + ∣ v ∣ ) . For k ∈ K k \in K k ∈ K , (b) gives q k Y ′ = c k 1 v / ( b + ∣ v ∣ ) = c k 2 v / ( a + ∣ v ∣ ) q'_{kY} = c_k^1v/(b + |v|) = c_k^2v/(a + |v|) q k Y ′ = c k 1 v / ( b + ∣ v ∣ ) = c k 2 v / ( a + ∣ v ∣ ) , so c k 1 / ( b + ∣ v ∣ ) = c k 2 / ( a + ∣ v ∣ ) = λ k c_k^1/(b + |v|) = c_k^2/(a + |v|) = \lambda_k c k 1 / ( b + ∣ v ∣ ) = c k 2 / ( a + ∣ v ∣ ) = λ k and ( q k 1 ′ , q k 2 ′ ) = λ k ( b , a ) (q'_{k1},q'_{k2}) = \lambda_k(b,a) ( q k 1 ′ , q k 2 ′ ) = λ k ( b , a ) . For y ∈ Y y \in Y y ∈ Y , ( q y 1 ′ , q y 2 ′ ) = ( b , a ) (q'_{y1},q'_{y2}) = (b,a) ( q y 1 ′ , q y 2 ′ ) = ( b , a ) by (a). Likewise μ Y = m 1 v / ( b + ∣ v ∣ ) = m 2 v / ( a + ∣ v ∣ ) \mu_Y = m_1v/(b + |v|) = m_2v/(a + |v|) μ Y = m 1 v / ( b + ∣ v ∣ ) = m 2 v / ( a + ∣ v ∣ ) gives m 1 / ( b + ∣ v ∣ ) = m 2 / ( a + ∣ v ∣ ) = λ m_1/(b + |v|) = m_2/(a + |v|) = \lambda m 1 / ( b + ∣ v ∣ ) = m 2 / ( a + ∣ v ∣ ) = λ and μ { 1 , 2 } = λ ( b , a ) \mu_{\{1,2\}} = \lambda(b,a) μ { 1 , 2 } = λ ( b , a ) . The rows 1 1 1 and 2 2 2 agree off { 1 , 2 } \{1,2\} { 1 , 2 } , with v v v on Y Y Y and ε \varepsilon ε on K K K . So { 1 , 2 } \{1,2\} { 1 , 2 } has uniform exits, its entries are multiples of the law ( b , a ) / ( a + b ) (b,a)/(a+b) ( b , a ) / ( a + b ) , and so is μ { 1 , 2 } \mu_{\{1,2\}} μ { 1 , 2 } , and 2 ≤ ∣ { 1 , 2 } ∣ ≤ d − 1 2 \le|\{1,2\}| \le d - 1 2 ≤ ∣ { 1 , 2 } ∣ ≤ d − 1 since Y ≠ ∅ Y \ne\varnothing Y = ∅ .
Now let a = b = 0 a = b = 0 a = b = 0 . By (c), q 1 Y ′ = q 2 Y ′ = 0 q'_{1Y} = q'_{2Y} = 0 q 1 Y ′ = q 2 Y ′ = 0 , so the rows 1 1 1 and 2 2 2 vanish on U U U off the diagonal and are ε \varepsilon ε on K K K , which are uniform exits. Every jump into Y Y Y from outside Y Y Y comes from K K K , and by irreducibility there is one, from some k 0 k_0 k 0 . By (b), c k 0 1 σ 1 ∣ Y = c k 0 2 σ 2 ∣ Y ≠ 0 c_{k_0}^1\sigma_1|_Y = c_{k_0}^2\sigma_2|_Y \ne0 c k 0 1 σ 1 ∣ Y = c k 0 2 σ 2 ∣ Y = 0 , so σ 2 ∣ Y = λ σ 1 ∣ Y \sigma_2|_Y = \lambda\sigma_1|_Y σ 2 ∣ Y = λ σ 1 ∣ Y with λ = c k 0 1 / c k 0 2 > 0 \lambda= c_{k_0}^1/c_{k_0}^2 > 0 λ = c k 0 1 / c k 0 2 > 0 . For every k ∈ K k \in K k ∈ K , c k 1 σ 1 ∣ Y = λ c k 2 σ 1 ∣ Y c_k^1\sigma_1|_Y = \lambda c_k^2\sigma_1|_Y c k 1 σ 1 ∣ Y = λ c k 2 σ 1 ∣ Y gives c k 1 = λ c k 2 c_k^1 = \lambda c_k^2 c k 1 = λ c k 2 , so ( q k 1 ′ , q k 2 ′ ) = c k 2 θ (q'_{k1},q'_{k2}) = c_k^2\theta ( q k 1 ′ , q k 2 ′ ) = c k 2 θ with θ = ( λ σ 1 ( 1 ) , σ 2 ( 2 ) ) \theta= (\lambda\sigma_1(1),\sigma_2(2)) θ = ( λ σ 1 ( 1 ) , σ 2 ( 2 )) , and the rows y ∈ Y y \in Y y ∈ Y vanish on { 1 , 2 } \{1,2\} { 1 , 2 } by (a). From μ Y = m 1 σ 1 ∣ Y = m 2 λ σ 1 ∣ Y \mu_Y = m_1\sigma_1|_Y = m_2\lambda\sigma_1|_Y μ Y = m 1 σ 1 ∣ Y = m 2 λ σ 1 ∣ Y we get m 1 = λ m 2 m_1 = \lambda m_2 m 1 = λ m 2 and μ { 1 , 2 } = m 2 θ \mu_{\{1,2\}} = m_2\theta μ { 1 , 2 } = m 2 θ . Finally θ ≠ 0 \theta\ne0 θ = 0 , since otherwise no state outside { 1 , 2 } \{1,2\} { 1 , 2 } jumps into it, which contradicts irreducibility. So { 1 , 2 } \{1,2\} { 1 , 2 } is a renewal block with entry law θ / ( θ ⋅ 1 ) \theta/(\theta\cdot\mathbf{1}) θ / ( θ ⋅ 1 ) . □
Lemma A.3 (crossing blocks). Let Q Q Q and Q ′ Q' Q ′ be irreducible with P Q ′ = P Q P Q' = P Q P Q ′ = P Q , and let A = { 1 , 2 } A = \{1,2\} A = { 1 , 2 } be a renewal block of ( Q , μ ) (Q,\mu) ( Q , μ ) . Let Y ⊆ [ d ] ∖ A Y \subseteq[d] \setminus A Y ⊆ [ d ] ∖ A be nonempty, and suppose that Y ∪ { 1 } Y \cup\{1\} Y ∪ { 1 } and Y ∪ { 2 } Y \cup\{2\} Y ∪ { 2 } are renewal blocks of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) . Then A A A is a renewal block of ( Q ′ , μ ) (Q',\mu) ( Q ′ , μ ) .
Proof. Use the notation of Lemmas A.1 and A.2 , and put R y = r y c y ≥ 0 R_y = r_yc_y \ge0 R y = r y c y ≥ 0 for y ∈ Y y \in Y y ∈ Y and s = ∣ q 1 Y ′ ∣ s = |q'_{1Y}| s = ∣ q 1 Y ′ ∣ . For y ∈ Y y \in Y y ∈ Y , Lemma A.1 (a) on the pairs { 1 , 2 } \{1,2\} { 1 , 2 } , { 1 , y } \{1,y\} { 1 , y } and { 2 , y } \{2,y\} { 2 , y } , on the triple { 1 , 2 , y } \{1,2,y\} { 1 , 2 , y } and on the diagonal entries 1 1 1 and 2 2 2 , with Lemma A.2 (a), gives
α β = a b , (6) \alpha\beta= ab, \tag*{(6)} α β = ab , (6)
R y ρ 1 = b q 1 y ′ , R y ρ 2 = a q 2 y ′ , (7) R_y\rho_1 = bq'_{1y}, \qquad R_y\rho_2 = aq'_{2y}, \tag*{(7)} R y ρ 1 = b q 1 y ′ , R y ρ 2 = a q 2 y ′ , (7)
R y ( ρ 1 α + ρ 2 β ) = a b ( q 1 y ′ + q 2 y ′ ) , (8) R_y(\rho_1\alpha+ \rho_2\beta) = ab\left(q'_{1y} + q'_{2y}\right), \tag*{(8)} R y ( ρ 1 α + ρ 2 β ) = ab ( q 1 y ′ + q 2 y ′ ) , (8)
( a + ∣ q 1 Y ′ ∣ ) − ( b + ∣ q 2 Y ′ ∣ ) = α − β . (9) (a + |q'_{1Y}|) - (b + |q'_{2Y}|) = \alpha- \beta. \tag*{(9)} ( a + ∣ q 1 Y ′ ∣ ) − ( b + ∣ q 2 Y ′ ∣ ) = α − β . (9)
For (7) , q 1 y q y 1 = r y c y ρ 1 q_{1y}q_{y1} = r_yc_y\rho_1 q 1 y q y 1 = r y c y ρ 1 and q 1 y ′ q y 1 ′ = q 1 y ′ b q'_{1y}q'_{y1} = q'_{1y}b q 1 y ′ q y 1 ′ = q 1 y ′ b , and likewise for 2 2 2 . For (8) , the cyclic products are α r y c y ρ 1 + r y c y ρ 2 β \alpha r_yc_y\rho_1 + r_yc_y\rho_2\beta α r y c y ρ 1 + r y c y ρ 2 β for Q Q Q and α q 2 y ′ b + q 1 y ′ q 2 y ′ a \alpha q'_{2y}b + q'_{1y}q'_{2y}a α q 2 y ′ b + q 1 y ′ q 2 y ′ a for Q ′ Q' Q ′ . For (9) , q 11 − q 22 = β − α q_{11} - q_{22} = \beta- \alpha q 11 − q 22 = β − α , since the rows 1 1 1 and 2 2 2 of Q Q Q have the same exit total r ⋅ 1 \mathbf{r} \cdot\mathbf{1} r ⋅ 1 , and q 11 ′ − q 22 ′ q'_{11} - q'_{22} q 11 ′ − q 22 ′ is read off Lemma A.2 (a).
Case a > 0 a > 0 a > 0 and b > 0 b > 0 b > 0 . By (7) , q 1 y ′ = ρ 1 R y / b q'_{1y} = \rho_1R_y/b q 1 y ′ = ρ 1 R y / b and q 2 y ′ = ρ 2 R y / a q'_{2y} = \rho_2R_y/a q 2 y ′ = ρ 2 R y / a . If Σ = ∑ y ∈ Y R y \Sigma= \sum_{y \in Y} R_y Σ = ∑ y ∈ Y R y were 0 0 0 , then q 1 Y ′ = q 2 Y ′ = 0 q'_{1Y} = q'_{2Y} = 0 q 1 Y ′ = q 2 Y ′ = 0 , and by both halves of Lemma A.2 (d) no state outside Y Y Y would jump into Y Y Y , which contradicts irreducibility. So R y 0 > 0 R_{y_0} > 0 R y 0 > 0 for some y 0 y_0 y 0 , and (8) at y 0 y_0 y 0 , divided by R y 0 R_{y_0} R y 0 , reads ρ 1 α + ρ 2 β = a b ( ρ 1 / b + ρ 2 / a ) = ρ 1 a + ρ 2 b \rho_1\alpha+\rho_2\beta=ab(\rho_1/b+\rho_2/a)=\rho_1a+\rho_2b ρ 1 α + ρ 2 β = ab ( ρ 1 / b + ρ 2 / a ) = ρ 1 a + ρ 2 b . With (6) , the numbers ρ 1 α \rho_1\alpha ρ 1 α and ρ 2 β \rho_2\beta ρ 2 β have the sum ρ 1 a + ρ 2 b \rho_1a+\rho_2b ρ 1 a + ρ 2 b and the product ρ 1 ρ 2 a b \rho_1\rho_2ab ρ 1 ρ 2 ab , so they are ρ 1 a \rho_1a ρ 1 a and ρ 2 b \rho_2b ρ 2 b in some order. Equation (9) reads
a − b + Σ ( ρ 1 b − ρ 2 a ) = α − β . (10) a-b+\Sigma\left(\frac{\rho_1}{b}-\frac{\rho_2}{a}\right)=\alpha-\beta. \tag*{(10)} a − b + Σ ( b ρ 1 − a ρ 2 ) = α − β . (10)
If ρ 2 = 0 \rho_2=0 ρ 2 = 0 , then ρ 1 = 1 \rho_1=1 ρ 1 = 1 and α ∈ { a , 0 } \alpha\in\{a,0\} α ∈ { a , 0 } . Since α β = a b > 0 \alpha\beta=ab>0 α β = ab > 0 , α = a \alpha=a α = a and β = b \beta=b β = b , and (10) gives Σ / b = 0 \Sigma/b=0 Σ/ b = 0 , a contradiction. The case ρ 1 = 0 \rho_1=0 ρ 1 = 0 is the same with 1 and 2 exchanged. If ρ 1 ρ 2 > 0 \rho_1\rho_2>0 ρ 1 ρ 2 > 0 and ( α , β ) = ( a , b ) (\alpha,\beta)=(a,b) ( α , β ) = ( a , b ) , then (10) gives Σ ( ρ 1 a − ρ 2 b ) / ( a b ) = 0 \Sigma(\rho_1a-\rho_2b)/(ab)=0 Σ ( ρ 1 a − ρ 2 b ) / ( ab ) = 0 , so ρ 1 a = ρ 2 b \rho_1a=\rho_2b ρ 1 a = ρ 2 b . If ρ 1 ρ 2 > 0 \rho_1\rho_2>0 ρ 1 ρ 2 > 0 and ( ρ 1 α , ρ 2 β ) = ( ρ 2 b , ρ 1 a ) (\rho_1\alpha,\rho_2\beta)=(\rho_2b,\rho_1a) ( ρ 1 α , ρ 2 β ) = ( ρ 2 b , ρ 1 a ) , then, since ρ 1 + ρ 2 = 1 \rho_1+\rho_2=1 ρ 1 + ρ 2 = 1 , α − β − a + b = b / ρ 1 − a / ρ 2 = ( ρ 2 b − ρ 1 a ) / ( ρ 1 ρ 2 ) \alpha-\beta-a+b=b/\rho_1-a/\rho_2=(\rho_2b-\rho_1a)/(\rho_1\rho_2) α − β − a + b = b / ρ 1 − a / ρ 2 = ( ρ 2 b − ρ 1 a ) / ( ρ 1 ρ 2 ) , and (10) gives ( ρ 1 a − ρ 2 b ) ( Σ / ( a b ) + 1 / ( ρ 1 ρ 2 ) ) = 0 (\rho_1a-\rho_2b)(\Sigma/(ab)+1/(\rho_1\rho_2))=0 ( ρ 1 a − ρ 2 b ) ( Σ/ ( ab ) + 1/ ( ρ 1 ρ 2 )) = 0 , so again ρ 1 a = ρ 2 b \rho_1a=\rho_2b ρ 1 a = ρ 2 b . Hence q 1 y ′ = ρ 1 R y / b = ρ 2 R y / a = q 2 y ′ q'_{1y}=\rho_1R_y/b=\rho_2R_y/a=q'_{2y} q 1 y ′ = ρ 1 R y / b = ρ 2 R y / a = q 2 y ′ for all y ∈ Y y\in Y y ∈ Y , and q 1 Y ′ = q 2 Y ′ ≠ 0 q'_{1Y}=q'_{2Y}\ne0 q 1 Y ′ = q 2 Y ′ = 0 since Σ > 0 \Sigma>0 Σ > 0 . Lemma A.2 (e) gives the claim.
Case b = 0 < a b=0<a b = 0 < a . By Lemma A.2 (c), q 2 Y ′ = 0 q'_{2Y}=0 q 2 Y ′ = 0 , so the row 2 of Q ′ Q' Q ′ vanishes on U ∖ { 2 } U\setminus\{2\} U ∖ { 2 } , and by Lemma A.2 (a) no state of U ∖ { 1 } U\setminus\{1\} U ∖ { 1 } jumps to 1. By (6) , α β = 0 \alpha\beta=0 α β = 0 , and by (9) , α − β = a + s > 0 \alpha-\beta=a+s>0 α − β = a + s > 0 , so β = 0 \beta=0 β = 0 and α = a + s \alpha=a+s α = a + s . Now take G G G and W W W as in Lemma A.1 (b), and split A c = Y ∪ K A^c=Y\cup K A c = Y ∪ K . The rows of Q ′ [ A , A c ] Q'[A,A^c] Q ′ [ A , A c ] are ( q 1 Y ′ , ε ) (q'_{1Y},\varepsilon) ( q 1 Y ′ , ε ) and ( 0 , ε ) (0,\varepsilon) ( 0 , ε ) , and its columns Q ′ [ A c , A ] Q'[A^c,A] Q ′ [ A c , A ] are ( 0 , q K 1 ′ ) (0,q'_{K1}) ( 0 , q K 1 ′ ) and ( a 1 Y , q K 2 ′ ) (a1_Y,q'_{K2}) ( a 1 Y , q K 2 ′ ) . Hence
W 11 = W 21 + Δ , W 12 = W 22 + Γ , Δ = q 1 Y ′ G Y K q K 1 ′ , Γ = q 1 Y ′ ( a G Y Y 1 + G Y K q K 2 ′ ) , W_{11}=W_{21}+\Delta,\qquad W_{12}=W_{22}+\Gamma,\qquad\Delta=q'_{1Y}G_{YK}q'_{K1},\qquad\Gamma=q'_{1Y}(aG_{YY}1+G_{YK}q'_{K2}), W 11 = W 21 + Δ , W 12 = W 22 + Γ , Δ = q 1 Y ′ G Y K q K 1 ′ , Γ = q 1 Y ′ ( a G Y Y 1 + G Y K q K 2 ′ ) ,
and det W = Δ W 22 − Γ W 21 \det W=\Delta W_{22}-\Gamma W_{21} det W = Δ W 22 − Γ W 21 . The last identity of Lemma A.1 (b), with q 12 ′ = a q'_{12}=a q 12 ′ = a , q 21 ′ = 0 q'_{21}=0 q 21 ′ = 0 , β = 0 \beta=0 β = 0 and w ρ 1 = W 11 w\rho_1=W_{11} w ρ 1 = W 11 , reads a W 21 − det W = ( a + s ) W 11 aW_{21}-\det W=(a+s)W_{11} a W 21 − det W = ( a + s ) W 11 , that is
( Γ − s ) W 21 = Δ ( W 22 + a + s ) . (11) (\Gamma-s)W_{21}=\Delta(W_{22}+a+s). \tag*{(11)} ( Γ − s ) W 21 = Δ ( W 22 + a + s ) . (11)
Suppose that s > 0 s>0 s > 0 , and take x = t 1 x=t1 x = t 1 with t > a + max k ∈ K q k 2 ′ t>a+\max_{k\in K}q'_{k2} t > a + max k ∈ K q k 2 ′ , the maximum being 0 if K = ∅ K=\varnothing K = ∅ . By Lemma 4.28 , G ≥ 0 G\ge0 G ≥ 0 and G 1 ≤ t − 1 1 G1\le t^{-1}1 G 1 ≤ t − 1 1 , so Γ ≤ s ( a + max k q k 2 ′ ) / t < s \Gamma\le s(a+\max_k q'_{k2})/t<s Γ ≤ s ( a + max k q k 2 ′ ) / t < s , while W 21 , W 22 , Δ ≥ 0 W_{21},W_{22},\Delta\ge0 W 21 , W 22 , Δ ≥ 0 . So the left side of (11) is at most 0 and the right side at least 0, and both vanish. Hence W 21 = 0 W_{21}=0 W 21 = 0 and, since W 22 + a + s > 0 W_{22}+a+s>0 W 22 + a + s > 0 , Δ = 0 \Delta=0 Δ = 0 , so W 11 = 0 W_{11}=0 W 11 = 0 . But Q ′ Q' Q ′ is irreducible, so there is a path 1 = i 0 → i 1 → ⋯ → i n = 1 1=i_0\to i_1\to\cdots\to i_n=1 1 = i 0 → i 1 → ⋯ → i n = 1 with n ≥ 2 n\ge2 n ≥ 2 . Its last step comes from K K K , since only states of K K K jump to 1. Let p p p be the last index below n n n with i p ∈ A i_p\in A i p ∈ A , so p < n − 1 p<n-1 p < n − 1 and i p + 1 , … , i n − 1 ∈ A c i_{p+1},\ldots,i_{n-1}\in A^c i p + 1 , … , i n − 1 ∈ A c . By Lemma 4.28 , q i p i p + 1 ′ G i p + 1 i n − 1 q i n − 1 1 ′ > 0 q'_{i_pi_{p+1}}G_{i_{p+1}i_{n-1}}q'_{i_{n-1}1}>0 q i p i p + 1 ′ G i p + 1 i n − 1 q i n − 1 1 ′ > 0 , and this is one of the nonnegative terms of W i p 1 W_{i_p1} W i p 1 . So W 11 + W 21 > 0 W_{11}+W_{21}>0 W 11 + W 21 > 0 , a contradiction. Hence s = 0 s=0 s = 0 , that is q 1 Y ′ = 0 = q 2 Y ′ q'_{1Y}=0=q'_{2Y} q 1 Y ′ = 0 = q 2 Y ′ with a > 0 a>0 a > 0 . By Lemma A.2 (d), no state of K ∪ { 1 } K\cup\{1\} K ∪ { 1 } jumps into Y Y Y , and neither does 2, which contradicts irreducibility. So this case does not occur.
Case a = 0 < b a=0<b a = 0 < b . This is the previous case with 1 and 2 exchanged, and it does not occur.
Case a = b = 0 a=b=0 a = b = 0 . Lemma A.2 (e) gives the claim.
Data and code availability
The Python scripts and the Lean library of Section 5 are ancillary files of the arXiv version. They are also archived at Zenodo, doi:10.5281/zenodo.24099075 .
The scripts need Python 3 with numpy, scipy, sympy and mpmath. Running python3 verify_all.py repeats the checks of Section 5. It saves the output of each script together with the sha256 of that script.
The Lean library is in the folder lean. It uses Lean 4.33.1 and Mathlib v4.33.1, and the files lean-toolchain and lake-manifest.json fix these versions. To build it, we run lake exe cache get and then lake build PaperC. The file MAP.md lists the statements of this paper that each Lean file proves. In the folder lean, the command python3 verify_lean.py PaperC --workspace . builds the library and checks that each theorem uses only the axioms propext, Classical.choice and Quot.sound.
Funding
This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.
Declaration of competing interest
The author declares that he has no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Declaration of generative AI and AI-assisted technologies in the manuscript preparation process
During the preparation of this work the author used Claude Opus 5.5 to proofread, to check notation for consistency, and to review drafts in the style of a referee; these reviews informed the phrasing of the abstract and the framing of the main theorems. After using this tool, the author reviewed and edited the content and takes full responsibility for the content of the published article.
Acknowledgments
This work grew out of Problem 131 of Peter Kagey’s Open Problem Collection [21 ] . We thank him for posing it.