Stable Adiabatic Times For A Continuous Evolution Of Markov Chains

Abstract

This paper continues the discussion on the stability of time-inhomogeneous Markov chains. In particular, this paper defines a time-inhomogeneous, discrete-time Markov chain governed by a continuous evolution in the appropriate martrix space. This matrix space, ${\mathcal{P}}_n^{ia}$, is the space of all stochastic matrices that are irreducible and aperiodic. For this new type of evolution there is a definition of a specific type of stability called the stable adiabatic time. This measure is bounded by a function of the optimal mixing time over the evolution. Namely, for a time-inhomogeneous, discrete-time Markov chain governed by a continuous evolution through a function $\mathbf{P}:[0,1]\to {\mathcal{P}}_n^{ia}$ and $0<\epsilon <\frac{1}{2\sqrt{n}}$ $$t_{sad}(\mathbf{P}, ε) \leq \frac{3n^{3 \slash 2} L t_{mix}^{2}(\mathbf{P}_{\infty}, ε)}{(1-2\sqrt{n} ε) ε}$$ \noindent where $L$ is a Lipschitz constant related to the function $\mathbf{P}$.

References in corpus (2)

• An Elementary Proof of the Quantum Adiabatic Theorem
• On the adiabatic condition and the quantum hitting time of Markov chains