Bounding the convergence time of local probabilistic evolution

07/11/2017
Publication GSI2017
OAI : oai:www.see.asso.fr:17410:22360
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
- Accès libre pour les ayants-droit
 

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.

Bounding the convergence time of local probabilistic evolution

Collection

application/pdf Bounding the convergence time of local probabilistic evolution Simon Apers, Alain Sarlette, Francesco Ticozzi
Détails de l'article
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
- Accès libre pour les ayants-droit

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.
Bounding the convergence time of local probabilistic evolution

Média

Voir la vidéo

Métriques

0
0
108.64 Ko
 application/pdf
bitcache://4d39e524048a3a42aaedddbc6b349f807909d3cf

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors Platine

alanturinginstitutelogo.png
logothales.jpg

Sponsors Bronze

logo_enac-bleuok.jpg
imag150x185_couleur_rvb.jpg

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors

smai.png
gdrmia_logo.png
gdr_geosto_logo.png
gdr-isis.png
logo-minesparistech.jpg
logo_x.jpeg
springer-logo.png
logo-psl.png

Organisateurs

logo_see.gif
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/17410/22360</identifier><creators><creator><creatorName>Alain Sarlette</creatorName></creator><creator><creatorName>Simon Apers</creatorName></creator><creator><creatorName>Francesco Ticozzi</creatorName></creator></creators><titles>
            <title>Bounding the convergence time of local probabilistic evolution</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2018</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sun 18 Feb 2018</date>
	    <date dateType="Updated">Sun 18 Feb 2018</date>
            <date dateType="Submitted">Mon 17 Dec 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">4d39e524048a3a42aaedddbc6b349f807909d3cf</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>37015</version>
        <descriptions>
            <description descriptionType="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.
</description>
        </descriptions>
    </resource>
.

Bounding the convergence time of local probabilistic evolution Simon Apers1 , Alain Sarlette1,2 , and Francesco Ticozzi3,4 1 Department of Electronics and Information Systems, Ghent University, Belgium 2 QUANTIC lab, INRIA Paris, France 3 Dipartimento di Ingegneria dell’Informazione, Università di Padova, Italy 4 Department of Physics and Astronomy, Dartmouth College, NH 03755, USA simon.apers@ugent.be,alain.sarlette@inria.fr,ticozzi@dei.unipd.it Abstract. Isoperimetric inequalities form a very intuitive yet powerful charac- terization 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 con- vergence time of any local probabilistic evolution that leaves its limit distribution invariant. We illustrate how this general result leads to new bounds on conver- gence 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. (solid line) Dumbbell graph Kn-Kn for n = 6. (dashed line) superimposed cycle of length 4n in a construction towards faster mixing. Consider a locality structure (discrete geometry) prescribed by the “dumbbell” graph family Kn −Kn shown in Figure 1, consisting of two complete graphs over n nodes, con- nected by a single edge. The diameter of this graph, being the “longest shortest path” between any two nodes, is three. However, a random walk over this graph converging to the uniform distribution has an expected convergence time in O(n2 ). This conver- gence 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, the system designer has superimposed a cycle (dashed line) 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 [16, 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 tar- get 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 X0, some system “→” propagates it over t time steps as X0 t → Xt. For a subset W ⊆ V and a state X, we define X(W) the probability of W according to X, and X|W as the state X conditioned on being in W. We call N(W) the neighborhood of W ⊆ V, i.e., the nodes outside W that have an edge going to W. We impose the following fundamental properties. – linear initialization: X0 t → Xt, X̃0 t → X̃t ⇒ pX0 + (1-p)X̃0 t → pXt + (1-p)X̃t – locality: ∀X0, t ≥ 0, W ⊆ V : Xt+1(W) ≤ Xt(W) + Xt(N(W)) – invariance: X0 +∞ → Π ∀X0 ⇒ Π t → Π The last property states that the unique steady state distribution of the system must be invariant as an initial condition. The second property expresses that probability weight can only flow along an edge at each time, without referring to details of the system mapping “→”. The first property is natural as the input is a probability distribution. The point however is that the general process “→” may e.g. contain hidden states, and we here impose a linear initialization with the hidden states as well (see example below). Our theorem presents a bound on the convergence of a system “→” that obeys these conditions towards its steady state Π. Explicitly, let τ be a time step such that kXt−Πk1 ≤ 1/2 for all t ≥ τ. In discrete geometry, given a graph G and a limit distribution Π, the isoperimetric measure Φ, which we also call the “conductance” [18], can be defined as: Φ = max P Φ(P), Φ(P) = min W⊆V : Π(W)≤1/2 [P ◦ (Π|W)] (V \ W). The maximization is over all stochastic matrices P acting on R|V| that obey the locality of G and for which P ◦ Π = Π. In other words, “P◦” is the most basic type of system “→” satisfying our requirements: it is time-invariant and memoryless (“Markov”). If Π is the uniform distribution, then Φ is upper bounded by the edge expansion of G, which is 1/n for the dumbbell graph. We establish the following “conductance bound” for any more complicated system. Theorem 1. If a system is linear, local and invariant, then τ ≥ 1/(8Φ). So for the dumbbell graph with Π the uniform distribution, we find τ ≥ n/8 for any linear, local and invariant system. Mixing on graph structures has drawn much interest for sampling algorithms, see e.g. perfect matching [15], or the Metropolis-Hastings algorithm used a lot in statistical mechanics. Bounds similar to Thm.1 have originally been proven by Cheeger [1] and Buser [2] in a differential geometry setting, and by Fiedler [4], Dodziuk [8] and Alon [3] in a discrete geometry and graph setting. In Markov chain analysis, early uses trace back to Aldous [5], Lawler and Sokal [6] and Mihail [7]. More recent examples are by Chen, Lovász and Pak [9] who used a similar bound to prove that a restricted class of extended Markov chains called “lifted Markov chains” can at most quadratically accelerate convergence, and by Aharonov et al. [10] to (loosely) bound the convergence speed of certain quantum processes. Our result allows to improve known mixing bounds, e.g. for quantum processes, and to generalize bounds beyond usual Markov chain settings, e.g. by including nonlinear decision rules. Examples are briefly discussed after the proof. 2. Proof: Our proof essentially comes down to two steps: – locality implies particular simulability: the locality condition implies that the dy- namics can always be described using (time- and state-dependent) local stochastic matrices. This is not entirely trivial in such generality. – bound for extended Markov chains: we rather straightforwardly combine these ma- trices in an extended Markov chain model, for which we can prove the bound along standard lines. 2.1. Locality implies simulability: A stochastic matrix P is local if the system X0 → Xt = Pt ◦ X0 is local. It is not hard to check that this coincides with the traditional definition, where locality means Pi, j = 0 whenever (i, j) < E. The following Lemma kind of proves the converse. Its proof is inspired by a related result of Scott Aaronson [17], establishing the lemma for quantum systems whose evolution is governed by a local unitary matrix. Lemma 1. If “→” is a local system, then for every pair (X0, t) with t > 0 there exists a local stochastic matrix P(t, X0) such that X0 t → Xt = P(t, X0) ◦ Xt−1. Proof. Call Y = Xt−1 and Z = Xt. We make a digression to flows over capacitated networks [11] and consider the one shown in Figure 2. The network consists of a source node s, a sink node t, and two copies of the graph nodes V and V0 . Node s is connected to any node i ∈ V with capacity Y(i), any node i ∈ V is connected with capacity 1 to any node j ∈ V0 iff (i, j) ∈ E (else the nodes are not connected), and any node j ∈ V0 is connected to node t with capacity Z(j). If this network can route a steady flow of value 1 from node s to node t, then the fraction of Y(i) that is routed from i ∈ V towards j ∈ V0 directly defines Pj,i(t, X0), as Z( j) = P i∈V Pj,i(t, X0)Y(i) and so P(t, X0) ◦ Y = Z. s t Y(1) Y(N) Z(1) Z(N) 1 1 1 1 1 V V0 W W N(W) Fig. 2. Capacitated network construction used in Lemma 1. The max-flow-min-cut theorem [11] states that the maximum steady flow which can be routed from node s to node t is equal to the minimum cut value of the graph, where a cut value is the sum of the capacities of a set of edges that disconnects s from t. It is clear that cutting all edges arriving at t disconnects the graph, with a cut value of 1, whereas cutting any middle edge between V and V0 gives a cut value ≥ 1. So the minimum cut need involve no such middle edge. Let us try to not cut the edges from W ⊆ V0 to t. To block any flow from s to t while keeping all middle edges, we must then cut the edges from s to all the l ∈ V which have an edge to W. This corresponds to all l ∈ W ∪ N(W). The value of this cut is thus 1 − P j∈W Z(j) + P j∈W Y( j) + P j∈N(W) Y( j) . Recalling that Y = Xt−1 and Z = Xt, locality imposes P j∈W Z( j) ≤ P j∈W Y( j) + P j∈N(W) Y( j) , from which follows that the minimum cut value is ≥ 1. According to the previous arguments, this concludes the proof. u t 2.2. Bound for “extended” Markov chains: On the basis of these P(t, X0), we show how to construct a local Markov chain with at most twice the convergence time τ of our original system “→”. Thereto, we first define a closely related system t ≡ iterate τ → namely floor(t/τ) times, plus tmodτ steps of it  . By construction, “ ” has the same convergence time τ as “→”, it has the same limit and it obeys the same locality and invariance conditions. We will now build a standard, time-invariant Markov chain that simulates the system “ ”. To this end we first extend our state space: the original node set V is lifted to V̂ = (V; {0, . . . , τ − 1}; V). From the perspective of a random walker, the first item contains its starting position, the second item a clock variable, and the last item its current position. In matrix form, with ⊗ representing the Kronecker product and ·† the transpose, we now build the transition matrix M for a Markov chain on V̂ as follows: M = X i∈V τ−2 X t=0 eie† i ⊗ et+1e† t ⊗ P(t, ei) + X i, j∈V eje† i ⊗ e0e† τ−1 ⊗ eje† j P(τ − 1, ei). Here ei is the unit vector with 1 at index i, and P(t, ei) denotes the transition matrix obtained by Lemma 1 for X0 = ei, i.e., initial weight concentrated at node i ∈ V. This Markov chain simulates the “ ” system in the following sense: when we locally initialize it in the state v[X0] = X i∈V X0(i)ei ⊗ e0 ⊗ ei , the distribution over the subsets (V; {0, . . . , τ − 1}; i) of the resulting state Mt v[X0] at time t exactly corresponds to Xt resulting from X0 Xt. A priori our Markov chain only simulates “ ” for special initial states of the form v[X0] over V̂. The following lemma shows that in fact when starting from an arbitrary distribution over V̂, it takes at most twice the time to converge to kXt −Πk1 ≤ 1/2 (over sets as just mentioned). Lemma 2. If → has a convergence time τ, then the Markov chain M on V̂ has a con- vergence time at most 2τ over the subsets { (V; {0, . . . , τ − 1}; i) : i ∈ V }. Proof. Consider an arbitrary initial state ei ⊗ eT ⊗ ek for the Markov chain M. After τ − T steps, this state will necessarily have evolved to one of the special initial states of the form v[X0], for some X0. By construction, the distribution of this state over the subsets { (V; {0, . . . , τ − 1}; i) : i ∈ V } will then simulate the evolution X0 t Xt, which converges to kXt − Πk1 ≤ 1/2 for all t ≥ τ. Note indeed that and → are equivalent over the first τ time steps, and furthermore by invariance, iterating → via will never increase kXt − Πk1. Hence the Markov chain will have converged after τ − T + τ ≤ 2τ steps at most. We have thus proved the convergence time for initial states with all weight concentrated on one element of V̂. By linearity, this also proves the convergence time for arbitrary initial states. u t The last element of the proof is a lower bound on τ for standard Markov chains. It essentially follows from a result by Chen, Lovász and Pak [9], stating that a class of ex- tended Markov chains called “lifted Markov chains” that converge over V̂ can converge at best in order 1/Φ, with Φ the conductance of the original graph. Our Markov chain M does not exactly fit into this framework, because it is periodic on V̂ and only its projection onto V via the subsets of Lemma (2) will converge. The proof can however be adapted to this case. Due to space constraints we must refer the reader to [20] for a detailed proof, and we here only provide the statement: Lemma 3. The convergence time of M over the sets { (V; {0, . . . , τ − 1}; i) : i ∈ V } is lower bounded by 1/(4Φ). By combining Lemma 2 and Lemma 3, we obtain that 2τ must be larger than 1/(4Φ) and hence τ larger than 1/(8Φ), as stated in the main theorem. 3. Examples: We now discuss a few examples to illustrate the generality of our result. Note that the mathematical result is not restricted to cases where Xt represents a prob- ability distribution. It can apply to any situation where Xt remains positive, bounded and preserves the sum of its components. Such dynamics can appear in flow dynamics and e.g. average consensus algorithms for weight distribution [13]. In such settings our result might suggest how e.g. relaxing the linearity constraint is necessary for beating the conductance bound. 3.1 Time-inhomogeneous Markov chains and Cesaro mixing: The bound clearly includes time-varying Markov chains (that satisfy invariance), as appear in the proof. Practical examples of such processes can be found in [21], and in [22] for card shuffling. The difficulty to analyze the convergence time of such processes is explicitly stated. Our paper thus provides a clear bound on the maximal achievable acceleration by exploiting the time-inhomogeneity degree of freedom in mixing algorithms. Cesaro mixing [19] using a stochastic matrix P is defined by the system X0 t → Xt = 1 t+1 Pt k=0 Pk X0. There appears to be no obvious way to write this as a Markov chain. However, one can show that Cesaro mixing satisfies our assumptions, so Thm.1 allows to directly bound the mixing time of such processes. 3.2 Processes with state-dependent or nonlocal decision rules: The locality condi- tion concerns how much probability weight is transferred at each step, but not how the decision about this transfer is taken. The latter is constrained by linearity. In this sense, our result directly bounds any attempts at adapting fast converging nonlinear algorithms e.g. from consensus, towards truly probabilistic Markov chains where linearity is natu- ral. Consider a nonlinear update rule from consensus, like: Xt+1 = P(Zt) Xt . In [14], Zt is a static function of the weight differences on the respective links, e.g. the weight associated to link (i, j) in P(Z) is a function of Xt(i) − Xt( j). Our framework would even admit Zt being a dynamic function of X, possibly nonlinear, taking values in any space, and would not even require that it is based on local values of X only: e.g. the weight associated to link (i, j) in P(Z) might be a function of some Xt(k) where node k is totally elsewhere in the graph. Such update rule is in general not linear in X0, but one may attempt to adapt it in this sense in the hope of designing e.g. stochastic automata that improve mixing over standard Markov chains. For instance, one might imagine a system that distinguishes, in memory, each part of Xt that has started from a different node at X0. Once this is done, we are free to choose the evolution (possibly nonlinear, nonlocal) for each of these X0-indexed parts, postulating that the full Xt consists of their linear combination. One might thus wonder whether such heuristic approach could lead to faster mixing on e.g. the dumbbell graph. Our result implies that — provided also invariance is required — such acceleration attempts are all limited to the conductance bound. 3.3 Finite-time convergence: Consider the following algebraic problem, related to finite-time convergence [23] and the inverse eigenvalue problem [24]: What is the minimal number of symmetric stochastic matrices over a graph G whose product has all but one eigenvalue equal to zero? From Theorem 1 it follows that this number is bounded by 1/(8Φ). To see this, note that a set of local, symmetric, stochastic matrices {P(l), 1 ≤ l ≤ T} over a graph G defines a linear and local system by X0 t → Xt =  Πt l=1P(l)  X0 for t ≤ T. The system is also invariant as the matrix product leaves the all-ones vector 1 invariant: 1 t → 1. If the product ΠT l=1P(l) has all but one eigenvalue equal to zero, the remaining eigen- value necessarily being 1 with eigenvector 1, then necessarily the system has converged: X0 T → 1/kX0k1, ∀X0 and so τ ≤ T. By Theorem 1 the convergence of any linear, local and invariant system is bounded, specifically stating that T ≥ 1/(8Φ). 3.4 Quantum walks: The convergence properties of quantum processes spreading over localized state spaces play a role both in physics (e.g. transport of excitations in photo- synthesis [12]) and in quantum computation (e.g. quantum random walks [10]). A discrete-time quantum walk is (although to our knowledge this has never been said explicitly) the generalization of a lifted walk, by keeping coherences among the node options. Denote by ρ the quantum state, i.e. a positive definite “density matrix” with trace one, whose diagonal represents probabilities over V̂ = {(i, z)} where i ∈ V is a graph node and z is a possible auxiliary degree of freedom (see introductory example [16], coined quantum walks [10], or Section 2.1). A general quantum walk follows: ρt+1 = Ψ ◦ ρt where Ψ is a completely positive trace-preserving map; most popular is the unitary quantum walk, where Ψ ◦ρt = UρtU† , with U a unitary matrix satisfying the locality of the graph G, exactly as P does for a Markov chain and M does in Section 2.1. If ρt would remain diagonal, this would correspond exactly to a lifted Markov chain [9]. Authors have been wondering for some time whether the additional information contained in the off-diagonal elements of ρt (“quantum coherences”) might allow faster mixing. In [10] a conductance bound is given for unitary quantum walks and within a factor of the graph degree; but such factor becomes dominant for e.g. the dumbbell graph. As will be further worked out in a future publication, quantum walks do satisfy the conditions of this paper, for most reasonable initializations. Then our result improves the bound of [10], both by generalizing it to non-unitary walks and by getting rid of the degree-dependent factor. Quantum walks indeed satisfy locality, including the hidden (complex) variables representing coherences. Linearity trivially holds, except if one al- lows to initialize the walk with nonlocal coherences already. In other words, since ρ0 would necessarily be block-diagonal when all the initial weight is concentrated on a sin- gle node, introducing off-diagonal initial blocks when starting with a distribution over nodes would break linearity — and by Thm.1, this would be necessary to potentially beat the conductance bound. References 1. Cheeger, Jeff. “A lower bound for the smallest eigenvalue of the Laplacian.” Proceedings of the Princeton conference in honor of Professor S. Bochner. 1969. 2. Buser, Peter. “A note on the isoperimetric constant.” Annales scientifiques de l’Ecole Normale Supérieure. Vol. 15. No. 2. 1982; Buser, Peter. ”Ueber den ersten Eigenwert des Laplace- Operators auf kompakten Flächen.” Commentarii Mathematici Helvetici 54.1 (1979): 477- 493. 3. Alon, Noga, and Vitali D. Milman. “λ1, isoperimetric inequalities for graphs, and super- concentrators.” Journal of Combinatorial Theory, Series B 38.1 (1985): 73-88; Alon, Noga. ”Eigenvalues and expanders.” Combinatorica 6.2 (1986): 83-96. 4. Fiedler, Miroslav. “Algebraic connectivity of graphs.” Czechoslovak mathematical journal 23.2 (1973): 298-305. 5. Aldous, David. “On the Markov chain simulation method for uniform combinatorial distri- butions and simulated annealing.” Probability in the Engineering and Informational Sciences 1.01 (1987): 33-46. 6. Lawler, Gregory F., and Alan D. Sokal. “Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality.” Transactions of the American mathematical society 309.2 (1988): 557-580. 7. Mihail, Milena. “Conductance and convergence of Markov chains-A combinatorial treatment of expanders.” IEEE Ann. Symp. on Foundations of computer science, (1989). 8. Dodziuk, Jozef. “Difference equations, isoperimetric inequality and transience of certain ran- dom walks.” Transactions of the American Mathematical Society 284.2 (1984): 787-794. 9. Chen, Fang, László Lovász, and Igor Pak. “Lifting Markov chains to speed up mixing.” Pro- ceedings of the thirty-first annual ACM symposium on Theory of computing. ACM, 1999. 10. Aharonov, Dorit, et al. “Quantum walks on graphs.” Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM, 2001. 11. Ford, Lester R., and Delbert R. Fulkerson. “Maximal flow through a network.” Canadian journal of Mathematics 8.3 (1956): 399-404. 12. Mohseni, Masoud, et al. “Environment-assisted quantum walks in photosynthetic energy transfer.” The Journal of chemical physics 129.17 (2008): 11B603. 13. John N. Tsitsiklis and Michael Athans (advisor). “Problems in decentralized decision making and computation.” PhD Thesis, MIT (1984). 14. Murray, Richard and Reza Olfati Saber. “Consensus protocols for networks of dynamic agents.” Proc. American Control Conference (2003). 15. Jerrum, Mark, and Alistair Sinclair. “Approximating the permanent.” SIAM journal on com- puting 18.6 (1989): 1149-1178. 16. Diaconis, Persi, Susan Holmes, and Radford M. Neal. “Analysis of a nonreversible Markov chain sampler.” Annals of Applied Probability (2000): 726-752. 17. Aaronson, Scott. “Quantum computing and hidden variables.” Physical Review A 71.3 (2005): 032325. 18. Aldous, David, and Jim Fill. “Reversible Markov chains and random walks on graphs.” (2002). 19. Levin, David Asher, Yuval Peres, and Elizabeth Lee Wilmer. “Markov chains and mixing times”. American Mathematical Soc., 2009. 20. Apers, Simon, Alain Sarlette, and Francesco Ticozzi. “Lifting Markov chains to mix faster: Limits and Opportunities.” In preparation for IEEE Trans. Information Theory, (2017). 21. Saloff-Coste, Laurent, and Jessica Zúniga. “Convergence of some time inhomogeneous Markov chains via spectral techniques.” Stochastic processes and their applications 117.8 (2007): 961-979 ; Touri, Behrouz, and Angelia Nedić. “Alternative characterization of er- godicity for doubly stochastic chains.” Proc. IEEE Conf. on Decision and Control (2011). 22. Mossel, Elchanan, Yuval Peres, and Alistair Sinclair. “Shuffling by semi-random transposi- tions.” Proc. IEEE Symp. on Foundations of Computer Science (2004) ; Diaconis, Persi, and Arun Ram. “Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques.” Department of Statistics, Stanford University, (2000). 23. Hendrickx, Julien M., et al. “Graph diameter, eigenvalues, and minimum-time consensus.” Automatica 50.2 (2014): 635-640 ; Hendrickx, Julien M., Guodong Shi, and Karl H. Johans- son. “Finite-time consensus using stochastic matrices with positive diagonals.” IEEE Trans- actions on Automatic Control 60.4 (2015): 1070-1073. 24. Hogben, Leslie. “Spectral graph theory and the inverse eigenvalue problem of a graph.” Elec- tronic Journal of Linear Algebra 14.1 (2005): 3.