×

Bounding the convergence time of local probabilistic evolution. (English) Zbl 1428.60035

Nielsen, Frank (ed.) et al., Geometric science of information. Third international conference, GSI 2017, Paris, France, November 7–9, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10589, 754-762 (2017).
Summary: Isoperimetric inequalities form a very intuitive yet powerful characterization of the connectedness of a state space, that has proven successful in obtaining convergence bounds. Since the seventies they form an essential tool in differential geometry, graph theory and Markov chain analysis. In this paper we use isoperimetric inequalities to construct a bound on the convergence time of any local probabilistic evolution that leaves its limit distribution invariant. We illustrate how this general result leads to new bounds on convergence times beyond the explicit Markovian setting, among others on quantum dynamics.
For the entire collection see [Zbl 1374.94006].

MSC:

60E15 Inequalities; stochastic orderings
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
94A17 Measures of information, entropy
PDFBibTeX XMLCite
Full Text: DOI arXiv