  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.
