Spectral gap of Markov chains on a cycle

Gerencsér, Balázs and Hendrickx, Julien and Van Dooren, Paul (2015) Spectral gap of Markov chains on a cycle. In: 2015 European Control Conference (ECC). IEEE, Piscataway (NJ), pp. 765-769. ISBN 9783952426937

Preview

Text cycle_spectral_gap.pdf Download (308kB) | Preview

Abstract

We search for the Markov chain with the optimal mixing rate where transitions are restricted to happen along a cycle of the states. We show that homogeneous, reversible chains are locally optimal for perturbations that make them inhomogeneous and non-reversible. Moreover, we show the optimality holds globally if only a single type of perturbation (either inhomogeneous or non-reversible) is applied. However, we conjecture global optimality holds for mixed perturbations as well, which is backed by simulation results. This paper complements previous results on bounds for mixing times of general Markov chains on the cycle [1].

Actions (login required)

Edit Item