Bounding the convergence time of local probabilistic evolution

International audience ; 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 ...