Bounding the convergence time of local probabilistic evolution

Simon Apers 1 Francesco Ticozzi 2, 3 Alain Sarlette 4
4 QUANTIC - QUANTum Information Circuits
Inria de Paris, MINES ParisTech - École nationale supérieure des mines de Paris, UPMC - Université Pierre et Marie Curie - Paris 6, ENS Paris - École normale supérieure - Paris
Abstract : 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 [1, 2], graph theory [4, 3] and Markov chain analysis [8, 5, 6]. 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. This paper is concerned with the discrete-time spreading of a distribution along the edges of a graph. In essence we establish that even by exploiting global information about the graph and allowing a very general use of this information, this spreading can still not be accelerated beyond the conductance bound. Before providing more ample context, we start with a motivating example ascribed to Eugenio Calabi, but which came to our attention through the seminal 1969 paper by Jeff Cheeger [1]. Whereas the original example concerns differential geometry, we will apply it to a graph setting. W V\W Fig. 1. (in black) Dumbbell graph K n-K n for n = 6. (in blue) superimposed cycle of length 4n in a construction towards faster mixing. Consider a locality structure (discrete geometry) prescribed by the " dumbbell " graph family K n − K n shown in Figure 1, consisting of two complete graphs over n nodes, connected by a single edge. The diameter of this graph is three, but a random walk over this graph converging to the uniform distribution has an expected convergence time in O(n 2). This convergence time can be improved with a " global design " but without violating locality of the evolution, by adding some memory to the walker. In Figure 1 (in blue), the system designer has superimposed a cycle over the dumbbell graph. By adding subnodes that allow to conditionally select different subflows through the graph (formally we " lift " the walk [9]), the walker can be restricted to walk along this cycle. Using this cycle, we can impose a strategy by Diaconis, Holmes and Neal [18, 9] to efficiently speed-up mixing over this cycle: let the walker cycle in the same direction with a probability 1 − 1/n, and switch direction with probability 1/n. This way the walk will mix over the graph in O(n), i.e. quadratically faster than the original random walk. But this is still order n times slower than the diameter. Nevertheless, we show in our paper that this improvement is the best possible for any local probabilistic process that leaves the target distribution invariant. So mixing in diameter time may be possible, but not without loosening any of these constraints. 1. Problem description and main result: Consider a graph G with nodes V and edges E ⊆ V × V. We use the convention that (i, i) ∈ E ∀i ∈ V. We define " states " X as probability distributions over V. Given an initial state X 0 , some system " → " propagates it over t time steps as X 0
Type de document :
Communication dans un congrès
Frank Nielsen; Frédéric Barbaresco. Geometric Science of Information, Second International Conference, GSI 2017, Nov 2017, Paris, France. Springer, 10589, LNCS - Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger
Contributeur : Alain Sarlette <>
Soumis le : mardi 14 novembre 2017 - 12:17:25
Dernière modification le : jeudi 26 avril 2018 - 10:29:05
Document(s) archivé(s) le : jeudi 15 février 2018 - 14:53:58


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01634611, version 1



Simon Apers, Francesco Ticozzi, Alain Sarlette. Bounding the convergence time of local probabilistic evolution. Frank Nielsen; Frédéric Barbaresco. Geometric Science of Information, Second International Conference, GSI 2017, Nov 2017, Paris, France. Springer, 10589, LNCS - Lecture Notes in Computer Science. 〈hal-01634611〉



Consultations de la notice


Téléchargements de fichiers