Stable Adiabatic Times For A Continuous Evolution Of Markov Chains
Kyle Bradford · arXiv (Cornell University) · 2015
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] \rightarrow \mathcal{P}_{n}^{ia}$ and $0 < ε< \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} ε) ε}$$ oindent where $L$ is a Lipschitz constant related to the function $\mathbf{P}$.