Stable Adiabatic Times for Markov Chains

Abstract

In this paper we continue our work on adiabatic time of time-inhomogeneous Markov chains first introduced in Kovchegov (2010) and Bradford and Kovchegov (2011). Our study is an analog to the well-known Quantum Adiabatic (QA) theorem which characterizes the quantum adiabatic time for the evolution of a quantum system as a result of applying of a series of Hamilton operators, each is a linear combination of two given initial and final Hamilton operators, i.e. $\mathbf{H}(s)=(1-s){\mathbf{H}}_0+s{\mathbf{H}}_1$. Informally, the quantum adiabatic time of a quantum system specifies the speed at which the Hamiltonian operators changes so that the ground state of the system at any time $s$ will always remain $\epsilon$-close to that induced by the Hamilton operator $\mathbf{H}(s)$ at time $s$. Analogously, we derive a sufficient condition for the stable adiabatic time of a time-inhomogeneous Markov evolution specified by applying a series of transition probability matrices, each is a linear combination of two given irreducible and aperiodic transition probability matrices, i.e., ${\mathbf{P}}_{\mathbf{t}}=(1-t){\mathbf{P}}_0+t{\mathbf{P}}_1$. In particular we show that the stable adiabatic time $t_{sad}(\mathbf{P_{0}}, \mathbf{P_{1}}, ε) = O (t_{mix}^{4}(ε\slash 2) \slash ε^{3}), $ where $t_{mix}$ denotes the maximum mixing time over all ${\mathbf{P}}_{\mathbf{t}}$ for $0\le t\le 1$.