← Back to Problems
ProbabilityResearchAI-Generated

For a higher order Markov chain on a finite state space, does the spectral gap of the lifted first order chain on the history space determine the optimal mixing time up to universal constants, independent of the order of the chain?

Related: Peres-Sousi theorem on mixing times and hitting times, Aldous spectral gap conjecture now theorem of Caputo-Liggett-Richthammer, Sinclair-Jerrum conductance bound

Higher order Markov chains remember a fixed window of past states, and to analyze them one typically lifts them into a first order chain on a larger state space of histories. The question is whether the spectral gap of this lifted chain is the right and essentially complete invariant for mixing time, in the sense that it controls convergence to the marginal stationary distribution on the original state space up to constants that do not depend on the order or the size of the history window. This would mean that no hidden structural obstacle to mixing exists beyond what the spectrum already reveals in the lifted picture.

View Source Paper →