Max Markov Chain

High-order Markov Chains are useful in a variety of situations. However, theseprocesses are limited in the complexity of the domains they can model. In complex domains, Markov models can require 100’s of Gigabytes of ram leading to the need of a parsimonious model. In this work, I present the Max Markov Chain (MMC). A robust model for estimating high-order datasets using only first-order parameters. High-order Markov chains (HMC) and Markov approximations (MTDg) struggle to scale to large state spaces due to the exponentially growing number of parameters required to model these domains. MMC can accurately approximate these models using only first-order parameters given the domain fulfills the MMC assumption. MMC naturally has better sample efficiency, and the desired spatial and computational advantages over HMCs and approximate HMCs. I will present evidence demonstrating the effectiveness of MMC in a variety of domains and compare its performance with HMCs and Markov approximations. Human behavior is inherently complex and challenging to model. Due to the high number of parameters required for traditional Markov models, the excessive computing requirements make real-time human simulation computationally expensive and impractical. I argue in certain situations, the behavior of humans follows that of a sparsely connected Markov model. In this work I focus on the subset of Markov Models which are just that, sparsely connected.