{"id":"25c43a48-8784-413e-b19d-a42b513817b5","arxiv_id":"2506.08874","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For a higher order Markov chain, if some power of its transition tensor has all positive entries, then the chain has a unique positive limiting probability distribution.","lead":"This paper analyzes when a higher order Markov chain, where the next state may depend on several previous states, has a limiting probability distribution that is independent of how the chain started. It proves that if the chain's transition tensor is regular, such a distribution exists and is positive, extending classical first order results to higher orders.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's regular-case proof is not a routine extension: the proposed contraction over K steps would require positivity of Q^K, which can fail when P is regular (as the paper's own Example 3.4 shows), so the main existence theorem rests on an unjustified step.","rationale":"The reader's weakest-assumption analysis correctly identifies the regular-case proof of Theorem 3.3 as the central gap. My reading confirms that this is not merely a matter of filling in routine details. The P > 0 proof obtains a uniform contraction of the auxiliary tensor y(k) because the coefficients in the (m-1)-step expansion of (3.6) are all bounded below by epsilon^{m-1}, which is equivalent to Q^{m-1} > 0. For a general regular P, only P^{(K)} = P(0)Q^K > 0 is guaranteed; the K-step recurrence for y(k) has coefficients q^{(K)}, the entries of Q^K, which may have zeros for every K. The paper's own Example 3.4 demonstrates this: P is regular but Q has a double eigenvalue 1 and is non-regular. Therefore the proposed substitution of epsilon = min P^{(K)} and the analogous subsequence cannot be justified by 'the same fashion' without an additional argument that works on the projected dynamics. This is a genuine gap in the proof of the main existence theorem. I do not conclude the theorem is false; it may well be true, and the example actually provides evidence that the conclusion can hold even when Q is non-regular. However, the manuscript currently does not supply the needed argument, so a conditional verdict with a request for a complete proof of the regular case is appropriate. The proposed concrete test would settle whether the literal proof strategy fails and would guide the required revision.","tokens_in":13796,"tokens_out":29864,"duration_ms":321181,"concrete_test":"Take Example 3.4, compute the reduced chain Q and the regular power P^{(10)} > 0. Form the K-step coefficient tensor q^{(K)}_{i2...im, h1...h_{m-1}} (equivalently, the entries of Q^K) for K = 10, 20, 40. Verify that min_{i2...im, h1...h_{m-1}} q^{(K)} = 0 for every K while min P^{(K)} > 0. Then test the literal claim of the proof by checking whether U_{k+K}-L_{k+K} <= (1 - 2 epsilon^{m-1})(U_k-L_k) holds with epsilon = min P^{(K)} for a generic initial vector x in (3.5). If this inequality fails, the regular-case proof's proposed 'same fashion' contraction is not a consequence of P^{(K)} > 0, confirming the gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the P > 0 case, the contraction proof of Theorem 3.3 uses (3.6), y(k+1)_{i2...im} = sum_j p_{j i2...im} y(k)_{j i2...im-1}, and iterates it m-1 times. Each factor p_{j...} is at least epsilon = min P, so the coefficient of any singled-out minimum entry is at least epsilon^{m-1}. This is equivalent to Theorem 3.2, which shows Q^{m-1} > 0. When P is only regular, the paper sets epsilon = min P^{(K)} and asserts the proof can be done 'in exactly the same fashion' using the subsequence U0-L0, UK-LK, UmK-LmK, etc. This does not follow. Iterating (3.6) K times produces coefficients q^{(K)}_{i2...im, h1...h_{m-1}}, the K-step transition probabilities of the reduced chain Q, not the entries of P^{(K)}. Positivity of P^{(K)} = P(0)Q^K says only that every state is reachable after K steps from every history; it does not imply that every history is reachable from every history after K steps. Indeed, Example 3.4 exhibits a regular P whose reduced Q is not regular and has a double dominant eigenvalue 1, so Q^K is never strictly positive. Thus the coefficient lower bound epsilon^{m-1} is unavailable, and the uniform contraction of the full tensor y(k) cannot be justified from P^{(K)} > 0 alone. The proof must instead analyze the projection P(0)y(k), a substantially different argument that is not supplied. Since Theorem 3.3 is the central result and Theorems 3.4 and 3.6 depend on it, this gap is load-bearing. The theorem may be correct, but the proof as written is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the limiting probability distribution of a homogeneous (m-1)th order Markov chain on a finite state space. The central result, Theorem 3.3, asserts that if the transition tensor P is regular in the sense that some power P^(K) has all entries positive, then the k-step transition tensors converge to pi ⊗ e ⊗ ... ⊗ e with pi > 0, independent of the initial distributions; Theorem 3.4 transfers this to convergence of the marginal distributions x_t. The paper also proves a lemma relating matricized tensor powers to powers of the reduced first-order chain Q, a theorem showing P > 0 implies Q regular, a tightness example in which ergodicity without regularity fails to yield a limit, and an eigenvector identity pi = P^(0)y that remains valid when Q is non-regular. Several illustrative examples are provided.","tokens_in":14220,"tokens_out":24136,"duration_ms":273358,"significance":"If Theorem 3.3 is correct, the paper makes a useful contribution: it gives an exact, approximation-free sufficient condition for existence of a limiting probability distribution of a higher-order Markov chain, generalizing the first-order regular matrix case and going beyond approaches that require the reduced chain Q to be regular. The contraction proof for the P > 0 case is detailed and internally consistent, and Example 3.4 is a valuable demonstration that Q can be non-regular even when P is regular. The main claims are stated cleanly and the examples are informative. However, the extension from P > 0 to regular P is not justified in the text, and because Theorem 3.3 is the source of the main conclusions, the manuscript is not yet fully established.","major_comments":[{"comment":"The proof of the regular case is not a routine extension of the P > 0 case. In the positive case the contraction factor 1 - 2ε^(m-1) is obtained by iterating (3.6) m-1 times, where every coefficient p_{j i2...im} is at least ε. If P is only regular, replacing ε by min p^(K) would require a block analogue of (3.6) whose coefficients are the K-step probabilities p^(K)_{...}; the manuscript proves no such recurrence. The coefficients that actually appear by iterating (3.6) K times are entries of Q^K, not entries of P^(K), and by the authors' own Example 3.4, Q^K need not be positive when P is regular. Hence the asserted subsequence U0-L0, UK-LK, UmK-LmK, ... has no demonstrated contraction, and convergence of U_k-L_k to zero is not established. Because Theorems 3.4 and 3.6 rely on Theorem 3.3, this gap is load-bearing. The authors should either supply a complete argument for the regular case or restrict the theorem to the positive case until such an argument is available.","section":"§3, Theorem 3.3, final paragraph (Eq. (3.6))"},{"comment":"The phrase \"The proof can be done in exactly the same fashion\" is also problematic for a structural reason. One might try to apply the positive-case proof to the positive tensor P^(K) itself, but that requires an identity of the form (P^(K))^(r) = P^(rK). No such identity is stated or proved, and since Section 2 notes that the tensor product ⊠ is neither associative nor commutative, the identity is not automatic; the recurrence (2.1) only provides P^(k+1) = P^(k) ⊠ P. Thus a reader cannot infer the inequality U_{k+K} - L_{k+K} ≤ (1 - 2ε^(m-1))(U_k - L_k) from the displayed argument. Please add the missing recurrence or a different substitution.","section":"§3, Theorem 3.3, final paragraph"}],"minor_comments":[{"comment":"\"Several illustrative example are also given\" should read \"Several illustrative examples are also given.\"","section":"Abstract"},{"comment":"Because ⊠ is non-associative, the phrase \"P^(k) can be thought of as the kth power of P\" should be clarified: it is the recursively defined k-step transition tensor, not a k-fold product in the usual sense. An explicit statement would prevent confusion in the proof of Theorem 3.3.","section":"§2, after Eq. (2.1)"},{"comment":"The example asserts P^(10) > 0 and describes the double dominant eigenvalue and eigenvectors of Q without showing the computation. Since the example is used to show that Theorem 3.3 applies beyond the Q-regular case, please provide the verification or a precise reference.","section":"§3, Example 3.4"},{"comment":"The word \"tight\" is stronger than the example supports: Example 3.2 shows that ergodicity without regularity can fail to yield a limiting distribution, but it does not show that regularity is necessary for the existence of such a distribution. Please rephrase the claim.","section":"§3, after Example 3.2"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the positive case is solid, but the regular-case proof as written is incomplete. I would be willing to accept after a revision that either supplies a complete proof of Theorem 3.3 for regular P or modifies the theorem's statement accordingly. The gap is central enough that a major revision is appropriate. No concerns about citation behavior or scope; the topic fits a probability journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe paper does two useful things. First, it proves that if the transition tensor P is positive, then lim_k P^(k) = pi tensor e tensor ... tensor e with pi > 0, so the limiting distribution exists and is independent of the initial probabilities. The contraction proof for the P > 0 case is detailed and, as far as I can tell, correct. Second, Lemma 3.1 (P^(u+v) = P^(u)Q^v) and Theorem 3.6 (pi = P(0)y for any normalized nonnegative dominant eigenvector y of the reduced chain Q, even when Q is non-regular) are clean generalizations that should be citable. Theorem 3.2, showing that P > 0 implies Q^{m-1} > 0, is a nice explicit computation.\n\nThe soft spot is Theorem 3.3's jump from P > 0 to P regular. The proof says the same argument goes through with epsilon = min P^(K), but it does not. The contraction step iterates y(k+1) = M y(k), where M is the one-step transition matrix of the reduced chain. Positivity of P^(K) = P(0)Q^K implies every state is reachable from every history in K steps, but it does not imply every history is reachable from every history, i.e., Q^K need not be positive. Example 3.4 in the paper itself shows P can be regular while Q is not. So the lower bound epsilon^{m-1} is unavailable, and the regular case rests on an unjustified assertion. The theorem may be true, and the example is consistent with it, but the proof as written is incomplete.\n\nThe rest of the paper is fine. Theorem 3.4 is a straightforward corollary of 3.3; Theorem 3.5 is a minor observation; and the examples illustrate the claims without overreaching. The tightness remark about regularity is okay in spirit, though it only shows one ergodic non-regular chain without a limit.\n\nI would send this to a serious referee. The machinery is sound, the P > 0 case is complete, and the Q-eigenvector connection is worth having. What's missing is a correct contraction argument for P^(K) > 0, or a counterexample, which I don't expect. The current version is not ready to accept.\n\nBest,\n[Your name]","headline":"Solid P>0 case and useful Q-eigenvector connection, but the regular-case proof of Theorem 3.3 has a load-bearing gap.","tokens_in":14724,"tokens_out":31267,"would_cite":false,"duration_ms":297243,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","15A69"],"pacs":[],"model":"deepseek-v4-flash","headline":"A higher-order Markov chain whose transition tensor is regular has a unique limiting probability distribution: the tensor powers converge to a positive rank-one limit, and the state probabilities converge to that limit regardless of the…","keywords":["higher order Markov chains","limiting probability distribution","regular transition tensor","transition tensor powers","reduced first order chain","dominant eigenvectors","tensor matricization","stationary probability distribution"],"falsifier":"Compute the tensor powers of a small regular transition tensor, for example a third-order chain with $n=3$ and $K=2$, and check numerically whether the fiberwise spread $\\max_{i_2\\dots i_m} p^{(k)}_{i i_2\\dots i_m}-\\min_{i_2\\dots i_m} p^{(k)}_{i i_2\\dots i_m}$ converges to zero; the theorem would be false if a regular $P$ produced a periodic or nonconvergent sequence of powers, or if two different normalized nonnegative eigenvectors $y$ of $Q$ with $Qy=y$ gave different values of $P^{(0)}y$ in a case where $P$ is regular.","tokens_in":13617,"feed_emoji":"🎲","tokens_out":7683,"duration_ms":87082,"temperature":0.7,"pith_summary":"The paper aims to prove that a higher-order Markov chain has a true limiting probability distribution whenever its transition tensor is regular, meaning some power of the tensor has all entries positive. If correct, this extends the classical first-order Markov chain theorem about regular transition matrices to chains with memory of length $m-1$, without relying on approximation schemes or two-phase power iterations. The authors also show that the limiting probabilities can be recovered from an eigenvector of the reduced first-order chain, even in cases where that reduced chain is itself not regular. The upshot is a sharper and more general picture of when long-run behavior of a higher-order chain is well defined.","feed_headline":"Regular transition tensors give higher-order chains a long-run limit","feed_subtitle":"Extends the classic regular-matrix condition from first-order to any memory length, with limits independent of starting probabilities.","key_machinery":"The main workhorse is the mode-1 matricization of the transition tensor, which flattens the tensor into a matrix by stacking frontal slices side by side, together with the tensor-power recurrence $P^{(k+1)}=P^{(k)}\\boxtimes P$. Lemma 3.1, $P^{(u+v)}=P^{(u)}Q^v$, links tensor powers of $P$ to ordinary matrix powers of the reduced first-order chain $Q$, allowing regularity of $P$ to be read off from $Q$ and allowing the limiting tensor to be expressed through eigenvectors of $Q$. The convergence proof itself is a contraction argument: tracking the maximum $U_k$ and minimum $L_k$ of entries of $P^{(k)}$ along mode-1 fibers, the positive-tensor case shows $U_k-L_k$ shrinks by a factor $(1-2\\epsilon^{m-1})$ at lags $m-1,2m-1,3m-2,\\dots$; Theorem 3.3 asserts the same argument applies to a regular tensor by replacing $\\epsilon$ with $\\min_{i_1\\dots i_m} p^{(K)}_{i_1\\dots i_m}$. Theorem 3.4 completes the link from the rank-one tensor limit to marginal probabilities by summing over all joint initial histories.","core_discovery":"On the paper's own terms, the central discovery is Theorem 3.3: if the $m$th-order transition tensor $P$ is regular, so some tensor power $P^{(K)}$ is entrywise positive, then the tensor powers converge to a rank-one limit $\\lim_{k\\to\\infty} P^{(k)}=\\pi\\otimes e\\otimes\\cdots\\otimes e$, where $\\pi$ is a strictly positive probability vector. Theorem 3.4 turns this into a statement about the chain's marginals: for every state $i$, $\\lim_{t\\to\\infty}\\Pr(X_t=i)=\\pi_i$, and this limit does not depend on the initial probability distributions $x_1,\\dots,x_{m-1}$. The paper additionally proves that regularity of the reduced first-order transition matrix $Q$ implies regularity of $P$ (Theorem 3.1) and that for $P>0$ the reduced chain $Q$ is regular (Theorem 3.2). Finally, Theorem 3.6 identifies the limiting vector as $\\pi=P^{(0)}y$ for any normalized nonnegative right eigenvector $y$ of $Q$ with eigenvalue $1$, and Example 3.4 shows this identification remains valid when $Q$ is non-regular and has a two-dimensional dominant eigenspace.","pith_inferences":["The unproved step in the regular case suggests a concrete numerical check: compute the lags $U_{mK}-L_{mK}$ for a regular tensor to see whether the contraction factor from the positive case actually holds; this would either close the gap or reveal the need for a different argument.","Because Theorem 3.4 does not require $\\pi>0$, the same framework may describe absorbing higher-order chains where some states have limiting probability zero; one could test this on a small absorbing example.","The eigenvector recipe $\\pi=P^{(0)}y$ suggests a projection-type estimator for limiting probabilities that works when power iteration on $Q$ diverges, which could be tested against the example in the paper."],"forward_implications":["If $P$ is regular, its tensor powers converge to $\\pi\\otimes e\\otimes\\cdots\\otimes e$ with $\\pi>0$, so long-run state probabilities are well defined.","The limiting marginal probabilities are independent of how the chain is started, matching the first-order regular-chain guarantee.","Regularity of the reduced first-order chain $Q$ is a sufficient way to certify regularity of $P$, so standard matrix regularity tests can be reused.","When a limiting distribution exists, it can be obtained from any normalized nonnegative dominant eigenvector of $Q$ via $\\pi=P^{(0)}y$, even if $Q$ is non-regular and the dominant eigenspace has dimension greater than one.","Ergodicity alone does not guarantee a limiting distribution; the paper gives an ergodic non-regular chain whose marginals oscillate."],"supporting_citations":[{"why":"Supplies the second-order analogue of Theorem 3.3 that the paper generalizes to arbitrary higher order.","marker":"[25]"},{"why":"The two-phase power iteration method whose regularity assumption on Q the paper shows is unnecessary; motivates Theorems 3.3 and 3.6.","marker":"[26]"},{"why":"Provides the tensor-power recurrence and the ergodicity and irreducibility facts used in Section 2.","marker":"[9]"},{"why":"Gives the relation $x_{t+1}=P y_t$ between chain marginals and the reduced chain, used throughout.","marker":"[21]"},{"why":"Source of Example 3.4, a chain with regular P but non-regular Q and two dominant eigenvectors, used to illustrate Theorem 3.6.","marker":"[7]"}],"fun_headline_variants":["Regular tensor powers force higher-order Markov chains to settle","From first to m-th order: regularity guarantees a limit distribution","Tensor regularity: the missing key to long-run limits for higher-order chains","Higher-order Markov chains converge when transition tensors are regular","One condition, any memory: regular tensors yield limit laws"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that the contraction argument extends from strictly positive tensors to merely regular tensors is asserted without details; the load-bearing premise is that taking subsequences at multiples of K preserves the same coefficient lower bounds, even though the reduced chain Q can be non-regular in that setting.","fun_headline_variants_meta":{"raw":{"variants":["Regular tensor powers force higher-order Markov chains to settle","From first to m-th order: regularity guarantees a limit distribution","Tensor regularity: the missing key to long-run limits for higher-order chains","Higher-order Markov chains converge when transition tensors are regular","One condition, any memory: regular tensors yield limit laws"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000918,"raw_usage":{"total_tokens":3909,"prompt_tokens":881,"completion_tokens":3028,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":2943}},"tokens_in":497,"tokens_out":3028,"duration_ms":25946,"temperature":1.0,"reasoning_tokens":2943,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:04:15.572753+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the tensor powers of a small regular transition tensor, for example a third-order chain with $n=3$ and $K=2$, and check numerically whether the fiberwise spread $\\max_{i_2\\dots i_m} p^{(k)}_{i i_2\\dots i_m}-\\min_{i_2\\dots i_m} p^{(k)}_{i i_2\\dots i_m}$ converges to zero; the theorem would be false if a regular $P$ produced a periodic or nonconvergent sequence of powers, or if two different normalized nonnegative eigenvectors $y$ of $Q$ with $Qy=y$ gave different values of $P^{(0)}y$ in a case where $P$ is regular.","supporting_citations":[{"cited_title":"Vladimirescu, Regular homogeneous Markov chains of order two, Analele Universitatii din Craiova, Seria Matematica, Fizica-Chimie 13 (1985): 59–63 (Romanian)","cited_arxiv_id":null,"evidence_quote":"Supplies the second-order analogue of Theorem 3.3 that the paper generalizes to arbitrary higher order."},{"cited_title":"Wu and M.T","cited_arxiv_id":null,"evidence_quote":"The two-phase power iteration method whose regularity assumption on Q the paper shows is unnecessary; motivates Theorems 3.3 and 3.6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the tensor-power recurrence and the ergodicity and irreducibility facts used in Section 2."},{"cited_title":"Li and M","cited_arxiv_id":null,"evidence_quote":"Gives the relation $x_{t+1}=P y_t$ between chain marginals and the reduced chain, used throughout."},{"cited_title":"Geiger, A sufficient condition for a unique invariant distribution of a higher-order Markov chain, Statistics and Probability Letters 130 (2017): 49–56","cited_arxiv_id":null,"evidence_quote":"Source of Example 3.4, a chain with regular P but non-regular Q and two dominant eigenvectors, used to illustrate Theorem 3.6."}],"review_version":1}