Discrete-time, discrete-state multistate Markov models from the perspective of algebraic statistics

Technical Summary: Discrete-time, Discrete-state Multistate Markov Models from the Perspective of Algebraic Statistics

Problem Statement
The paper addresses the algebraic structure underlying discrete-time, discrete-state multistate Markov models, a class of models widely used in event history analysis to describe processes evolving through sequences of states. While the probabilistic factorization of path probabilities is well-understood, the polynomial relations (algebraic constraints) among joint path probabilities have not been systematically explored within the framework of algebraic statistics. Specifically, the authors aim to establish a bridge between event history analysis and algebraic statistics by characterizing these models via monomial parametrizations and studying their associated vanishing ideals. A key distinction is made between nonhomogeneous models (where transition probabilities vary with time) and homogeneous models (where transition probabilities are time-invariant), as well as models with structural constraints like forbidden transitions or absorbing states.

Methodology
The authors employ the tools of algebraic statistics, specifically focusing on:

1. Monomial Parametrization: They formalize the joint probability of a finite path as a monomial in terms of initial distribution parameters ($\pi$) and transition probabilities ($a$). This defines a map $\phi$ from the parameter space to the probability simplex.
2. Implicitization and Vanishing Ideals: The core algebraic object of study is the kernel of the pullback map $\phi^*$, denoted as the vanishing ideal $I$. This ideal consists of all polynomial relations that vanish on the joint path probabilities implied by the model.
3. Toric Ideals and Hierarchical Models: The authors analyze whether these models correspond to decomposable hierarchical models (whose vanishing ideals are toric and generated by binomials). They utilize results from the theory of simplicial complexes and decomposable graphical models.
4. Maximum Likelihood Estimation (MLE): The paper compares classical statistical MLE formulas with algebraic approaches (solving likelihood equations via Lagrange multipliers or analyzing the likelihood ideal) to determine if the algebraic formulation offers computational advantages or reveals structural differences (e.g., strict inclusion of the model within its Zariski closure).
5. Computational Verification: Examples are verified using Macaulay2 and R, including real-world applications to Shakespearean text data to illustrate the theoretical findings.

Key Contributions and Results

• Nonhomogeneous Models:

  • The authors prove that nonhomogeneous $k$-th order multistate Markov models, when statistical constraints (non-negativity and sum-to-one) are disregarded, are decomposable hierarchical models.
  • Consequently, their vanishing ideals are toric ideals generated by explicit families of binomials. These generators correspond to conditional independence statements between blocks of variables (Proposition 4.5).
  • Models with forbidden transitions (e.g., illness-death models) are shown to be coordinate slices of the general model. Their vanishing ideals are obtained by adding linear equations ($p_{path} = 0$) to the general ideal (Corollary 4.7).
  • Crucially, in the nonhomogeneous setting, the statistical model $M$ is exactly equal to the intersection of the algebraic variety $V$ and the probability simplex $\Delta$ (Proposition 4.9).
  • The classical statistical formula for MLE coincides with the algebraic MLE for decomposable hierarchical models, yielding a unique, closed-form rational estimator.

• Homogeneous Models:

  • Time homogeneity imposes additional algebraic constraints because transition parameters are identified across different time steps. This causes homogeneous models to generally fall outside the class of decomposable hierarchical models.
  • The vanishing ideal for homogeneous models is strictly larger than that of their nonhomogeneous counterparts. The authors derive a general family of binomial relations induced by time homogeneity (Proposition 5.2), analogous to odds-ratio relations.
  • However, computational examples (e.g., Example 1 and Example 5) demonstrate that these derived binomials do not generate the full vanishing ideal in general; higher-degree polynomials are required.
  • A significant result is that for homogeneous models, the statistical model $M$ is strictly included in the intersection $V \cap \Delta$ (Proposition 6.2). This means the algebraic variety contains points that satisfy the polynomial constraints but do not correspond to valid probability distributions under the homogeneous Markov assumption.
  • Consequently, solving the MLE problem algebraically (via the likelihood ideal) can be substantially more complex than using classical statistical methods, which yield direct closed-form estimators by summing transition counts over time.

• Applications:

  • The theory is applied to an illness-death model and a reversible illness-death model.
  • A real-data application involves modeling English words from Shakespeare's works as Markov paths. The authors compute MLEs for both homogeneous and nonhomogeneous first-order models, as well as a second-order homogeneous model (collapsing states to vowels, consonants, and space). They demonstrate discrepancies between empirical path frequencies and fitted model probabilities, particularly highlighting how homogeneous models fail to capture position-specific bigram frequencies (e.g., "th" at the start of words) that nonhomogeneous models capture.

Significance and Claims
The paper claims to provide the first systematic algebraic-statistical study of discrete-time multistate Markov models. Its primary significance lies in:

1. Unifying Framework: It translates modeling assumptions (forbidden transitions, absorbing states, time homogeneity) into precise algebraic constraints (coordinate slices, additional binomial relations).
2. Structural Insight: It clarifies that while nonhomogeneous models fit neatly into the well-understood class of decomposable hierarchical models, homogeneous models exhibit more complex algebraic behavior, leading to a gap between the statistical model and its Zariski closure.
3. Methodological Caution: It highlights that for homogeneous models, classical statistical methods for MLE are often superior in simplicity and directness compared to algebraic approaches, which may involve solving complex systems with multiple solutions or higher-degree polynomials.
4. Future Directions: The authors identify open problems, including the algebraic treatment of right-censored data, the full generation of vanishing ideals for homogeneous models, and the extension of these results to mixtures of Markov models and colored graphical models.

The authors maintain a modest tone regarding the utility of algebraic methods for inference, noting that while algebraic viewpoints provide deep structural understanding, classical statistical methods often remain the simpler route for parameter estimation, particularly in the homogeneous case.