Pith. sign in

REVIEW 2 major objections 4 minor 32 references

Can a Higher Order Markov Chain Be Treated as a First Order Markov Chain?

T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Treating a higher-order Markov chain as a first-order chain only works for two quantities; most properties, including ergodicity and passage times, change.

desk verdict Useful synthesis with two genuine new results, but the 'negative in general' verdict is overstated: the reduced chain is informationally equivalent, and the proof of Theorem 5.1 has a gap for long paths. read the letter →

arxiv 2512.01969 v1 pith:W2JT2NC6 submitted 2025-12-01 math.PR

Jianhong Xu This is my paper
classification math.PR MSC 60A0560J1060J9915A6915B51
keywords higherorderMarkovchainreducedfirsttransitiontensorergodicitymeanpassagetimeever-reachingprobabilitylimitingdistributionstateclassification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper takes on a common assumption in stochastic processes: that any higher-order Markov chain can be studied through the first-order chain obtained by sliding a window of past states. The author argues that this reduction is only reliable for two types of quantities: k-step transition probabilities and limiting probability distributions. For everything else—ergodicity, regularity, ever-reaching probabilities, mean first passage times, and the classification of states as recurrent or transient—the reduced chain can behave very differently from the original. The paper demonstrates each failure with explicit examples and concludes that the answer to the title question is negative in general. This has practical stakes because higher-order chains are used in many applied fields, and the result warns against blind simplification.

What carries the argument

The sliding-window reduction Q, a first-order Markov chain whose states are length-(m-1) tuples Y_t = (X_t,...,X_{t-m+2}), with transition entries q_{i1...i_{m-1}, j2...j_m} = p_{i1...i_{m-1} j_m} when the tuple components match appropriately and zero otherwise. The paper also uses the tensor product ⊠ to express k-step transition tensors and the first-passage tensor equations, and mode-1 matricization to connect stationary distributions to limiting distributions. The reduction is the central object; the paper's claim is that it does not carry the higher-order chain's structure faithfully.

What would settle it

For the second-order three-state chain in Section 4, compute P^2 (it is positive) and check that the reduced chain Q has an all-zero row; this shows a regular higher-order chain whose reduced chain is not even irreducible. If this calculation fails, the paper's negative claim would need revision.

Watch

Extended reading notes

Core claim

The paper defines the reduced first-order chain Y_t = (X_t, ..., X_{t-m+2}) for an (m-1)th order chain with transition tensor P. It proves two positive bridges: Theorem 3.1, which shows k-step transition probabilities of the original chain can be recovered by summing certain entries of the reduced chain's k-step transition matrix; and equation (7.1), which shows the limiting probability distribution of the original chain is obtained by applying the mode-1 matricization of the identity tensor to any stationary distribution of the reduced chain. Beyond these, the paper gives concrete examples where the reduced chain fails to inherit ergodicity or regularity, where ever-reaching probabilities d

Load-bearing premise

The conclusion depends on taking the sliding-window vector process as the only first-order representation; if another reduction can preserve these properties, the negative verdict would not apply to it.

Editorial extensions

If this is right

  • Any computation of ergodicity, regularity, ever-reaching probabilities, or mean first passage times for a higher-order chain must work directly with the transition tensor; using the reduced chain can give wrong answers.
  • The only safe bridges are Theorem 3.1 for k-step transitions (with a summation over intermediate states) and equation (7.1) for limiting distributions.
  • The state classification for higher-order chains needs its own definitions: a state is recurrent only if the ever-reaching probability is 1 for every possible past sequence, not merely for the vector states of the reduced chain.
  • In applications, results about higher-order chains that rely on passage times or recurrence should not be inferred from the reduced first-order chain.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The negative answer is shown for the specific sliding-window reduction; an alternative first-order embedding that augments the state with a probability distribution over histories might preserve more properties, but the paper does not explore that.
  • The discrepancies in mean first passage times suggest that any shortcut through the reduced chain must be derived from the tensor equations, not guessed from matrix formulas.
  • A testable extension would be to characterize precisely which real-valued functions of the higher-order chain are determined by the reduced chain's transition matrix alone; Theorem 3.1 and (7.1) give two examples.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the standard sliding-window reduction of an (m−1)th-order Markov chain X to a first-order chain Y_t=(X_t,...,X_{t−m+2}) on the space of length-(m−1) histories, with transition matrix Q. It establishes positive transfer results for k-step transition probabilities (Theorem 3.1) and for limiting probability distributions (Eq. (7.1)), and it presents explicit examples intended to show that ergodicity, regularity, ever-reaching probabilities, mean first passage times, and state classification do not transfer from X to Q. The paper concludes that the answer to its Question 2.1 is negative in general.

Significance. If the claims are properly qualified, the paper provides a useful, checkable catalog of which standard first-order state-level quantities do and do not pass through the sliding-window reduction. The positive results in Section 3 and Section 7 are clean and genuinely useful. The explicit examples in Sections 4 and 6 are reproducible and illustrate real phenomena. However, the central negative claim is currently too broad: since Y_t is a deterministic function of X and X_t is the first coordinate of Y_t, every property of X is in principle recoverable from Q at the level of subsets of the state space T. The paper never acknowledges or addresses this set-level translation, so the conclusion in Section 8 overstates what the examples establish.

major comments (2)
  1. [Section 8, Question 2.1] The conclusion 'the answer to Question 2.1 is negative in general' is not supported by the supplied evidence. For each i1∈S, let A_i1={i1 j2...j_{m−1} : j2,...,j_{m−1}∈S}⊂T. Then X_t=i1 iff Y_t∈A_i1. Consequently, the ever-reaching probability f_{i1 i2...im} is exactly the probability that Q, started from (i2,...,im), ever hits the set A_i1; the mean first passage time µ_{i1...im} is the expected hitting time to A_i1; and ergodicity/regularity of X are set-reachability conditions on Q. The examples in Sections 4 and 6 show only that single-state entries of Q (e.g., state 11 rather than the set A_1) do not match the tensor entries of X. They do not show that X cannot be studied through Q. Please either narrow the claim to 'negative if one insists on state-level equality of the same indices' and state that explicitly, or add a discussion of how the set-level translation recovers the higher
  2. [Theorem 5.1 proof] The proof has a gap in the concatenation of events. The inequality p^{(γ+β+α)}_{i i3...im} ≥ Pr(ABC) is asserted with Pr(ABC)=p^{(α)}_{j i i3...im} p^{(β)}_{j j j3...jm} p^{(γ)}_{i j k3...km}. This requires that after event A the chain is exactly in the starting history of B, and after event B in the starting history of C. For α≥2, the post-A history contains random intermediate states, so a single tuple j3...jm cannot be used. Likewise, after a β-step return to j, the full history at the return time is not fixed, while C starts from a specified history j k3...km. The proof also leaves the case α≥m−1 completely unspecified (the displayed bullet list ends at α=m−2). The theorem may be true, but as written it is not proved. Please repair the argument by defining A and B as particular paths (using the positivity of p^{(α)} and the recurrence sum to choose such paths) or by a rigorous regene
minor comments (4)
  1. [Section 3, end of Theorem 3.1 proof] The sentence 'The conclusion in (3.1) follows now by induction' should refer to equation (3.3), not (3.1), which is the definition of the first passage time variable.
  2. [Theorem 5.1] The definition of j3,...,jm for α≥m−1 is left as an ellipsis. Please spell it out, since the proof's concatenation depends on the actual history after α steps.
  3. [Section 2] The column-stochastic convention for Q and P is stated in the introduction, but it would help to repeat it where Q is first introduced, since many readers expect row-stochastic transition matrices and the displayed Q and equation (6.2) depend on the convention.
  4. [Section 5] The bullet 'A state i is current iff ...' uses a nonstandard term; in the Markov-chain literature the property is usually called recurrence (or persistence). Please add a remark or change the terminology to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's negative answer rests on explicit examples and direct computations, while the self-cited prior results are used as external theorems rather than as definitions of the conclusion.

full rationale

The central claim—that a higher order chain cannot in general be studied through its sliding-window reduced first order chain via the usual state-level quantities—is supported by explicit transition tensors and computed reduced matrices. Section 4 exhibits a regular higher order chain whose reduced Q is not ergodic; Section 5 gives computed ever-reaching probability tensors showing classification differences; Section 6 solves the mean first passage time equation (6.1) and contrasts the result with the reduced chain's M computed from (6.2). These are self-contained examples, not predictions obtained by fitting parameters to the conclusion. Theorem 3.1 is proved by direct expansion and induction, and Theorem 5.1 is proved in the paper. The reliance on the author's prior work [12,13,14,15] is substantial, but those cited results are not machine-checked in this paper; nevertheless, they are external mathematical theorems with proofs elsewhere, and the examples here independently illustrate the main negative conclusions. The only self-citation that could be called load-bearing is the limiting-distribution formula (7.1) from [15], but that supports a positive tie rather than the paper's negative central claim. The more substantive concern is scope: the paper compares state-level properties of Q with properties of X and does not consider set-level recoverability or alternative embeddings. That is a limitation of the argument, not circularity. No step in the derivation reduces by construction to its own input.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's conclusions are conditional on the correctness of the author's prior tensor results [12-15] and on accepting the sliding-window reduction as the canonical first-order embedding. No numerical data are fitted; the only free-parameter-like choices are the hand-picked example transition tensors, which are not fitted parameters.

assumptions (4)
  • domain assumption The transition tensor P is homogeneous and stochastic (Section 1).
    All chains considered are time-homogeneous with entries summing to 1 over the next state; this is the standard setting for the tensor calculus used throughout.
  • domain assumption The tensor product ⊠ and the identities for P^k, F[k], and mean first passage times from [12] and [13] are correct.
    Sections 3-6 import k-step transition probabilities, ever-reaching probabilities, and equation (6.1) from the author's prior papers without re-deriving them; if any of these tensor identities fail, several of the transfer arguments lose their foundation.
  • standard math Perron-Frobenius theorem applies to the reduced transition matrix Q (Section 7).
    Used to guarantee existence and positivity of stationary distributions of the reduced first-order chain.
  • domain assumption The definitions and classification scheme for states of higher-order chains from [14] are accepted.
    Recurrence, full transience, and equivalence classes are taken from [14]; Theorem 5.1 is proved within that framework.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Can a Higher Order Markov Chain Be Treated as a First Order Markov Chain?." pith.science (2026). https://pith.science/paper/W2JT2NC6

@misc{pith2026251201969,
  author       = {Pith},
  title        = {Pith review of: Can a Higher Order Markov Chain Be Treated as a First Order Markov Chain?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W2JT2NC6}},
  note         = {Machine review of arXiv:2512.01969}
}
read the original abstract

It is well known that any higher order Markov chain can be associated with a first order Markov chain. In this primarily expository article, we present the first fairly comprehensive analysis of the relationship between higher order and first order Markov chains, together with illustrative examples. Our main objective is to address the central question as posed in the title.

Figures

Figures reproduced from arXiv: 2512.01969 by the authors.

Figure 1
Figure 1. Digraph of Reduced First Order Chain [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [14]

    L. Han, J. Xu, On classification of states in higher order Markov chains, Linear Algebra & Its Applications685: 24–45, 2024

    2024

  2. [1]

    Baena-Mirabete, P

    S. Baena-Mirabete, P. Puig, Parsimonious higher order Markov models for rating transitions,Journal of the Royal Statistical Society A: Statistics in Society181: 107–131, 2018

    2018

  3. [2]

    Burks, R

    D. Burks, R. Azad, Higher-order Markov models for metagenomic se- quence classification,Bioinformatics36: 4130–4136, 2020

    2020

  4. [3]

    Chang, T

    K. Chang, T. Zhang, On the uniqueness and non-uniqueness of the pos- itiveZ-eigenvector for transition probability tensors,Journal of Mathe- matical Analysis & Applications408: 525–540, 2013

    2013

  5. [4]

    J. Culp, K. Pearson, T. Zhang, On the uniqueness of theZ 1-eigenvector of transition probability tensors,Linear & Multilinear Algebra65: 891–896, 2017

    2017

  6. [5]

    Doob,Stochastic Processes, Wiley Classic Library Edition, Wiley, 1990

    J. Doob,Stochastic Processes, Wiley Classic Library Edition, Wiley, 1990

    1990

  7. [6]

    Flett, N

    G. Flett, N. Kelly, An occupant-differentiated, higher-order Markov chain method for prediction of domestic occupancy,Energy & Buildings125: 219–230, 2016

    2016

  8. [7]

    Geiger, A sufficient condition for a unique invariant distribution of a higher-order Markov chain,Statistics & Probability Letters130: 49–56, 2017

    B. Geiger, A sufficient condition for a unique invariant distribution of a higher-order Markov chain,Statistics & Probability Letters130: 49–56, 2017

    2017

Show all 32 references
  1. [8]

    Gleich, L

    D. Gleich, L. Lim, Y. Yu, Multilinear pagerank,SIAM Journal on Matrix Analysis & Applications36: 1507–1541, 2015. 22

    2015

  2. [9]

    L. Ho, J. Rajapakse, Splice site detection with a higher-order Markov model implemented on a neural network,Genome Informatics14: 64–72, 2003

    2003

  3. [10]

    S. Hu, L. Qi, Convergence of a second order Markov chain,Applied Mathematics & Computation241: 183–192, 2014

    2014

  4. [11]

    Hunter,Mathematical Techniques of Applied Probability, Volume I: Discrete Time Models: Basic Theory, Academic Press, 1983

    J. Hunter,Mathematical Techniques of Applied Probability, Volume I: Discrete Time Models: Basic Theory, Academic Press, 1983

    1983

  5. [12]

    L. Han, K. Wang, J. Xu, Higher order ergodic Markov chains and first passage times,Linear & Multilinear Algebra70: 6772–6779, 2022

    2022

  6. [13]

    L. Han, J. Xu, Ever-reaching probabilities and mean first passage times of higher order ergodic Markov chains,Linear & Multilinear Algebra72: 59–75, 2024

    2024

  7. [15]

    L. Han, J. Xu, On limiting probability distributions of higher order Markov chains, under review,https://doi.org/10.48550/arXiv.2506. 08874

    doi

  8. [16]

    R. Horn, C. Johnson,Matrix Analysis, Cambridge University Press, 1990

    1990

  9. [17]

    Iosifescu,Finite Markov Processes & Their Applications, Dover Pub- lications, 2007

    M. Iosifescu,Finite Markov Processes & Their Applications, Dover Pub- lications, 2007

    2007

  10. [18]

    Islam, R

    M. Islam, R. Chowdhury, A higher order Markov model for analyzing covariate dependence,Applied Mathematical Modelling30: 477–488, 2006

    2006

  11. [19]

    Kemeny, J

    J. Kemeny, J. Snell,Finite Markov Chains, Springer-Verlag, 1960

    1960

  12. [20]

    Kolda, B

    T. Kolda, B. Bader, Tensor decompositions and applications,SIAM Review51: 455–500, 2009

    2009

  13. [21]

    J. Kwak, C. Lee, D. Eun, A high-order Markov-chain-based scheduling algorithm for low delay in CSMA networks,IEEE/ACM Transactions on Networking24: 2278–2290, 2015. 23

    2015

  14. [22]

    J. Lan, X. Li, V. Jilkov, C. Mu, Second-order Markov chain based multiple-model algorithm for maneuvering target tracking,IEEE Trans- actions on Aerospace & Electronic Systems49: 3–19, 2013

    2013

  15. [23]

    C. Li, S. Zhang, Stationary probability vectors of higher-order Markov chains,Linear Algebra & Its Applications473: 114–125, 2016

    2016

  16. [24]

    W. Li, M. Ng, On the limiting probability distribution of a transition probability tensor,Linear Algebra & Its Applications62: 362–385, 2014

    2014

  17. [25]

    Z. Liu, Y. Luo, Y. Zhu, State estimation for linear dynamic system with multiple-step random delays using higher-order Markov chain,IEEE Access8: 76218–76227, 2020

    2020

  18. [26]

    Martin, R

    C. Martin, R. Shafer, B. Larue, An order-ptensor factorization with applications in imaging,SIAM Journal on Scientific Computing35: 474– 490, 2013

    2013

  19. [27]

    Masseran, Markov chain model for the stochastic behaviors of wind- direction data,Energy Conversion & Management92: 266–274, 2015

    N. Masseran, Markov chain model for the stochastic behaviors of wind- direction data,Energy Conversion & Management92: 266–274, 2015

    2015

  20. [28]

    Sanjari, H

    M. Sanjari, H. Gooi, Probabilistic forecast of PV power generation based on higher order Markov chain,IEEE Transactions on Power Systems32: 2942–2952, 2016

    2016

  21. [29]

    S. Wu, M. Chu, Markov chains with memory, tensor formulation, and the dynamics of power iteration,Applied Mathematics & Computation303: 226–239, 2017

    2017

  22. [30]

    Xiong, R

    H. Xiong, R. Mamon, A higher-order Markov chain-modulated model for electricity spot-price dynamics,Applied Energy233-234: 495–515, 2019

    2019

  23. [31]

    Xu, HOMC: a MATLAB package for higher order Markov chains, under review,https://doi.org/10.48550/arXiv.2510.02664

    J. Xu, HOMC: a MATLAB package for higher order Markov chains, under review,https://doi.org/10.48550/arXiv.2510.02664

    doi arXiv

  24. [32]

    Y. Yang, H. Jang, B. Kim, A hybrid recommender system for sequential recommendation: combining similarity models with Markov chains,IEEE Access8: 190136–190146, 2020. 24

    2020

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.