Stable Adiabatic Times for Markov Chains

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}}_{\mathbf{0}}+s{\mathbf{H}}_{\mathbf{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 $ϵ$-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}}_{\mathbf{0}}+t{\mathbf{P}}_{\mathbf{1}}$. In particular we show that the stable adiabatic time $t_{sad}(${\mathbf{P}}_{\mathbf{0}}$, ${\mathbf{P}}_{\mathbf{1}}$, \epsilon) = O (t_{mix}^{4}(\epsilon \slash 2) \slash \epsilon^{3}), $where$t_{mix}$denotesthemaximummixingtimeoverall$${\mathbf{P}}_{\mathbf{t}}$$for$0 \leq t \leq 1$.