Bounding the convergence time of local probabilistic evolution - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Bounding the convergence time of local probabilistic evolution

Résumé

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
Fichier principal
Vignette du fichier
isoperimetric-inequality.pdf (107.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01634611 , version 1 (14-11-2017)

Identifiants

  • HAL Id : hal-01634611 , version 1

Citer

Simon Apers, Francesco Ticozzi, Alain Sarlette. Bounding the convergence time of local probabilistic evolution. Geometric Science of Information, Second International Conference, GSI 2017, Nov 2017, Paris, France. ⟨hal-01634611⟩
408 Consultations
82 Téléchargements

Partager

Gmail Facebook X LinkedIn More