Max Markov Chain
This provides a more efficient alternative for modeling stochastic processes in domains where HMCs struggle, though it is incremental as it builds on existing HMC frameworks.
The paper tackles the problem of modeling stochastic processes with high-order Markov chains (HMCs) by introducing Max Markov Chain (MMC), a novel representation that offers analytical solutions, better sample efficiency, and computational advantages over HMCs and approximate HMCs, enabling scalability to large domains.
In this paper, we introduce Max Markov Chain (MMC), a novel representation for a useful subset of High-order Markov Chains (HMCs) with sparse correlations among the states. MMC is parsimony while retaining the expressiveness of HMCs. Even though parameter optimization is generally intractable as with HMC approximate models, it has an analytical solution, better sample efficiency, and the desired spatial and computational advantages over HMCs and approximate HMCs. Simultaneously, efficient approximate solutions exist for this type of chains as we show empirically, which allow MMCs to scale to large domains where HMCs and approximate HMCs would struggle to perform. We compare MMC with HMC, first-order Markov chain, and an approximate HMC model in synthetic domains with various data types to demonstrate that MMC is a valuable alternative for modeling stochastic processes and has many potential applications.