Stable adiabatic times for Markov chains

DOI10.1080/17442508.2015.1102267MaRDI QIDQ2804560zbMATHOpenAlexFDO

Authors Kyle Bradford, Thinh Tien Nguyen, Yevgeniy Kovchegov

Publication date 4 May 2016

Published in Stochastics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.4733

zbMATH Keywords

mixing timetime-inhomogeneous Markov chainsstable adiabatic times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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. $mathbfH(s)=(1-s)mathbf{H}_0+smathbf{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 $mathbfH(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}_t=(1-t)mathbf{P}_0+tmathbf{P}_1$. In particular we show that the stable adiabatic time $t_{sad}(mathbf{P}_0,mathbf{P}_1,epsilon)=O(t_{mix}^4(epsilonslash2)slashepsilo{n}^3),$ where $t_{mix}$ denotes the maximum mixing time over all $mathbf{P}_t$ for $0leqtleq1$.

Recommendations

• Adiabatic times for Markov chains and applications
• A note on adiabatic theorem for Markov chains
• A note on the switching adiabatic theorem
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• scientific article; zbMATH DE number 956418

Cites work

• scientific article; zbMATH DE number 3493681 (Why is no real title available?)
• A note on adiabatic theorem for Markov chains
• Adiabatic times for Markov chains and applications
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
• Merging for time inhomogeneous finite Markov chains. I: Singular values and stability

Cited in

(3)

• A note on adiabatic theorem for Markov chains
• Adiabatic times for Markov chains and applications
• Adiabatic theorem for classical stochastic processes

This page was built for publication: Stable adiabatic times for Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804560)