Search

This paper considers non-backtracking random walks on random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. The link is provided by the probability that the random walk has not yet stepped along a previously rewired edge. We use this link to compute the scaling of the mixing time for three specific classes of random rewirings. Depending on the speed and the range of the rewiring relative to the current location of the random walk, the mixing time may exhibit no cut-off, one-sided cut-off or two-sided cut-off, a trichotomy that was also found in earlier work. Interestingly, for a class of dynamics that are `mesoscopic', i.e., non-local and non-global, we find new behaviour with six subregimes. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk., Comment: 38 pages, 9 figures

We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand model unifying two closely related models: the subgraph world and the random cluster model. Through this new viewpoint, we show: (1) polynomial mixing time bounds for Swendsen-Wang dynamics and (edge-flipping) Glauber dynamics of the random cluster model, generalising the bounds and simplifying the proofs for the no-field case by Guo and Jerrum (2018); (2) near linear mixing time for the two dynamics above if the maximum degree is bounded and all fields are (consistent and) bounded away from $1$., Comment: Major revision and new results

We study bond percolation on the hypercube $\{0,1\}^m$ in the slightly subcritical regime where $p = p_c (1-\varepsilon_m)$ and $\varepsilon_m = o(1)$ but $\varepsilon_m \gg 2^{-m/3}$ and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality $\Theta\left(\varepsilon_m^{-2} \log(\varepsilon_m^3 2^m)\right)$, that the maximal diameter of all clusters is $(1+o(1)) \varepsilon_m^{-1} \log(\varepsilon_m^3 2^m)$, and that the maximal mixing time of all clusters is $\Theta\left(\varepsilon_m^{-3} \log^2(\varepsilon_m^3 2^m)\right)$. These results hold in different levels of generality, and in particular, some of the estimates hold for various classes of graphs such as high-dimensional tori, expanders of high degree and girth, products of complete graphs, and infinite lattices in high dimensions., Comment: 38 pages

Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running $k$ multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for worst-case start vertices (posed by Alon, Avin, Kouck\'y, Kozma, Lotker, and Tuttle~in 2008) remains an open problem. First, we improve and tighten various bounds on the stationary cover time when $k$ random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of $\Omega((n/k) \log n)$ on the stationary cover time, holding for any $n$-vertex graph $G$ and any $1 \leq k =o(n\log n )$. Secondly, we establish the stationary cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising worst-case cover times in terms of stationary cover times and a novel, relaxed notion of mixing time for multiple walks called the partial mixing time. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the worst-case cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes., Comment: 53 pages, 1 table

In the Fastest Mixing Markov Chain problem, we are given a graph G = (V, E) and desire the discrete-time Markov chain with smallest mixing time �� subject to having equilibrium distribution uniform on V and non-zero transition probabilities only across edges of the graph [Boyd et al., 2004]. It is well-known that the mixing time ��_RW of the lazy random walk on G is characterised by the edge conductance �� of G via Cheeger���s inequality: ��^{-1} ��� ��_RW ��� ��^{-2} log|V|. Edge conductance, however, fails to characterise the fastest mixing time ��^��� of G. Take, for example, a graph consisting of two n-vertex cliques connected by a perfect matching: its edge conductance is ��(1/n), while ��^��� can be shown to be O(log n). We show, instead, that is possible to characterise the fastest mixing time ��^��� via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance �� of G: ��^{-1} ��� ��^* ��� ��^{-2}(log|V|)^2. We prove this result by first relating vertex conductance to a new expansion measure, which we call matching conductance. We then relate matching conductance to a variational characterisation of ��^��� (or, more precisely, of the fastest relaxation time) due to Roch [Roch, 2005]. This is done by interpreting Roch���s characterisation as a particular instance of fractional vertex cover, which is dual to fractional matching. We believe matching conductance to be of independent interest and might have further applications in studying connectivity properties of graphs. This characterisation forbids fast mixing for graphs with small vertex conductance. To bypass this fundamental barrier, we consider Markov chains on G with equilibrium distribution which need not be uniform, but rather only ��-close to uniform in total variation. We call such chains almost mixing. We show that it is always possible to construct an almost mixing chain with mixing time �� ��� ��^{-1} (diam G)�� log |V|. Our proof is based on carefully constructing a reweighted spanning tree of G with good expansion properties and superimposing it over a simple "base" chain. In summary, our work together with known results shows that three fundamental geometric quantities characterise the mixing time on a graph according to three different notions of mixing: edge conductance characterises the mixing time of the lazy random walk, vertex conductance the fastest mixing time, while the diameter characterises the almost mixing time. Finally, we also discuss analogous questions for continuous-time and time-inhomogeneous chains., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 109:1-109:1

We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability $p \in (0,1)$ and a cluster weight $q > 0$. We establish that for every $q\ge 1$, the random-cluster Glauber dynamics mixes in optimal $\Theta(n\log n)$ steps on $n$-vertex random graphs having a prescribed degree sequence with bounded average branching $\gamma$ throughout the full high-temperature uniqueness regime $p, Comment: 45 pages, 3 figures

International audience; By viewing the $N$-simplex as the set of positions of $N-1$ ordered particles on the unit interval, the adjacent walk is the continuous time Markov chain obtained by updating independently at rate 1 the position of each particle with a sample from the uniform distribution over the interval given by the two particles adjacent to it. We determine its spectral gap and prove that both the total variation distance and the separation distance to the uniform distribution exhibit a cutoff phenomenon, with mixing times that differ by a factor $2$. The results are extended to the family of log-concave distributions obtained by replacing the uniform sampling by a symmetric log-concave Beta distribution.

We derive sufficient conditions for a probability measure on a finite product space (a spin system) to satisfy a (modified) logarithmic Sobolev inequality. We establish these conditions for various examples, such as the (vertex-weighted) exponential random graph model, the random coloring and the hard-core model with fugacity. This leads to two separate branches of applications. The first branch is given by mixing time estimates of the Glauber dynamics. The proofs do not rely on coupling arguments, but instead use functional inequalities. As a byproduct, this also yields exponential decay of the relative entropy along the Glauber semigroup. Secondly, we investigate the concentration of measure phenomenon (particularly of higher order) for these spin systems. We show the effect of better concentration properties by centering not around the mean, but a stochastic term in the exponential random graph model. From there, one can deduce a central limit theorem for the number of triangles from the CLT of the edge count. In the Erd\"os-R\'enyi model the first order approximation leads to a quantification and a proof of a central limit theorem for subgraph counts., Comment: completely restructured, merged with arXiv:1804.04424

We consider a natural local dynamic on the set of all rooted planar maps with $n$ edges that is in some sense analogous to “edge flip” Markov chains, which have been considered before on a variety of combinatorial structures (triangulations of the $n$-gon and quadrangulations of the sphere, among others). We provide the first polynomial upper bound for the mixing time of this “edge rotation” chain on planar maps: we show that the spectral gap of the edge rotation chain is bounded below by an appropriate constant times $n^{-11/2}$. In doing so, we provide a partially new proof of the fact that the same bound applies to the spectral gap of edge flips on quadrangulations as defined in [8], which makes it possible to generalise the result of [8] to a variant of the edge flip chain related to edge rotations via Tutte’s bijection.

We study the cyclic adjacent transposition (CAT) shuffle of $n$ cards, which is a systematic scan version of the random adjacent transposition (AT) card shuffle. In this paper, we prove that the CAT shuffle exhibits cutoff at $\frac{n^3}{2 \pi^2} \log n$, which concludes that it is twice as fast as the AT shuffle., Comment: 26 pages, 3 figures

We study convergence to stationarity for random walks on dynamic random digraphs with given degree sequences. The digraphs undergo full regeneration at independent geometrically distributed random time intervals with parameter $\alpha$. Relaxation to stationarity is the result of a competition between regeneration and mixing on the static digraph. When the number of vertices $n$ tends to infinity and the parameter $\alpha$ tends to zero, we find three scenarios according to whether $\alpha\log n$ converges to zero, infinity or to some finite positive value: when the limit is zero, relaxation to stationarity occurs in two separate stages, the first due to mixing on the static digraph, and the second due to regeneration; when the limit is infinite, there is not enough time for the static digraph to mix and the relaxation to stationarity is dictated by the regeneration only; finally, when the limit is a finite positive value we find a mixed behaviour interpolating between the two extremes. A crucial ingredient of our analysis is the control of suitable approximations for the unknown stationary distribution., Comment: 28 pages, 6 figures (v3: minor corrections)

We study bond percolation on the Hamming hypercube {0,1}^m around the critical probability p_c. It is known that if p=p_c(1+O(2^{-m/3})), then with high probability the largest connected component C_1 is of size Theta(2^{2m/3}) and that this quantity is non-concentrated. Here we show that for any sequence eps_m such that eps_m=o(1) but eps_m >> 2^{-m/3} percolation on the hypercube at p_c(1+eps_m) has |C_1| = (2+o(1)) eps_m 2^m and |C_2| = o(eps_m 2^m) with high probability, where C_2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [17]., 71 pages, 5 figures

We consider the generalised PageRank walk on a digraph $G$, with refresh probability $\alpha$ and resampling distribution $\lambda$. We analyse convergence to stationarity when $G$ is a large sparse random digraph with given degree sequences, in the limit of vanishing $\alpha$. We identify three scenarios: when $\alpha$ is much smaller than the inverse of the mixing time of $G$ the relaxation to equilibrium is dominated by the simple random walk and displays a cutoff behaviour; when $\alpha$ is much larger than the inverse of the mixing time of $G$ on the contrary one has pure exponential decay with rate $\alpha$; when $\alpha$ is comparable to the inverse of the mixing time of $G$ there is a mixed behaviour interpolating between cutoff and exponential decay. This trichotomy is shown to hold uniformly in the starting point and uniformly in the resampling distribution $\lambda$., Comment: 28 pages, 3 figures

We consider the biased card shuffling and the Asymmetric Simple Exclusion Process (ASEP) on the segment. We obtain the asymptotic of their mixing times: our result show that these two continuous-time Markov chains display cutoff. Our analysis combines several ingredients including: a study of the hydrodynamic profile for ASEP, the use of monotonic eigenfunctions, stochastic comparisons and concentration inequalities., 50 pages

We consider the exclusion process on segments of the integers in a site-dependent random environment. We assume to be in the ballistic regime in which a single particle has positive linear speed. Our goal is to study the mixing time of the exclusion process when the number of particles is linear in the size of the segment. We investigate the order of the mixing time depending on the support of the environment distribution. In particular, we prove for nestling environments that the order of the mixing time is different than in the case of a single particle., 29 pages, 1 figure, accepted for publication in EJP

We establish metastability in the sense of Lebowitz and Penrose under practical and simple hypothesis for (families of) Markov chains on finite configuration space in some asymptotic regime, including the case of configuration space size going to infinity. By comparing restricted ensemble and quasi-stationary measures, we study point-wise convergence velocity of Yaglom limits and prove asymptotic exponential exit law. We introduce soft measures as interpolation between restricted ensemble and quasi-stationary measure to prove an asymptotic exponential transition law on a generally different time scale. By using potential theoretic tools, we prove a new general Poincar\'e inequality and give sharp estimates via two-sided variational principles on relaxation time as well as mean exit time and transition time. We also establish local thermalization on a shorter time scale and give mixing time asymptotics up to a constant factor through a two-sided variational principal. All our asymptotics are given with explicit quantitative bounds on the corrective terms., Comment: 41 pages

Let $P$ be the transition matrix of a finite, irreducible and reversible Markov chain. We say the continuous time Markov chain $X$ has transition matrix $P$ and speed $\lambda$ if it jumps at rate $\lambda$ according to the matrix $P$. Fix $\lambda_X,\lambda_Y,\lambda_Z\geq 0$, then let $X,Y$ and $Z$ be independent Markov chains with transition matrix $P$ and speeds $\lambda_X,\lambda_Y$ and $\lambda_Z$ respectively, all started from the stationary distribution. What is the chance that $X$ and $Y$ meet before either of them collides with $Z$? For each choice of $\lambda_X,\lambda_Y$ and $\lambda_Z$ with $\max(\lambda_X,\lambda_Y)>0$, we prove a lower bound for this probability which is uniform over all transitive, irreducible and reversible chains. In the case that $\lambda_X=\lambda_Y=1$ and $\lambda_Z=0$ we prove a strengthening of our main theorem using a martingale argument. We provide an example showing the transitivity assumption cannot be removed for general $\lambda_X,\lambda_Y$ and $\lambda_Z$., Comment: 20 pages

Let $X$ be a lazy random walk on a graph $G$. If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $\mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$, where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.

The mixing time of a random walk, with or without backtracking, on a random graph generated according to the configuration model on $n$ vertices, is known to be of order $\log n$. In this paper we investigate what happens when the random graph becomes {\em dynamic}, namely, at each unit of time a fraction $\alpha_n$ of the edges is randomly rewired. Under mild conditions on the degree sequence, guaranteeing that the graph is locally tree-like, we show that for every $\varepsilon\in(0,1)$ the $\varepsilon$-mixing time of random walk without backtracking grows like $\sqrt{2\log(1/\varepsilon)/\log(1/(1-\alpha_n))}$ as $n \to \infty$, provided that $\lim_{n\to\infty} \alpha_n(\log n)^2=\infty$. The latter condition corresponds to a regime of fast enough graph dynamics. Our proof is based on a randomised stopping time argument, in combination with coupling techniques and combinatorial estimates. The stopping time of interest is the first time that the walk moves along an edge that was rewired before, which turns out to be close to a strong stationary time., Comment: 23 pages, 6 figures. Previous version contained a mistake in one of the proofs. In this version we look at nonbacktracking random walk instead of simple random walk

The random-cluster model with parameters $(p,q)$ is a random graph model that generalizes bond percolation ($q=1$) and the Ising and Potts models ($q\geq 2$). We study its Glauber dynamics on $n\times n$ boxes $\Lambda_{n}$ of the integer lattice graph $\mathbb Z^2$, where the model exhibits a sharp phase transition at $p=p_c(q)$. Unlike traditional spin systems like the Ising and Potts models, the random-cluster model has non-local interactions. Long-range interactions can be imposed as external connections in the boundary of $\Lambda_n$, known as boundary conditions. For select boundary conditions that do not carry long-range information (namely, wired and free), Blanca and Sinclair proved that when $q>1$ and $p\neq p_c(q)$, the Glauber dynamics on $\Lambda_n$ mixes in optimal $O(n^2 \log n)$ time. In this paper, we prove that this mixing time is polynomial in $n$ for every boundary condition that is realizable as a configuration on $\mathbb Z^2 \setminus \Lambda_{n}$. We then use this to prove near-optimal $\tilde O(n^2)$ mixing time for "typical'' boundary conditions. As a complementary result, we construct classes of non-realizable (non-planar) boundary conditions inducing slow (stretched-exponential) mixing at $p\ll p_c(q)$., Comment: 40 pages, 6 figures

Plaquette models are short range ferromagnetic spin models that play a key role in the dynamic facilitation approach to the liquid glass transition. In this paper we study the dynamics of the square plaquette model at the smallest of the three critical length scales discovered in arXiv:1707.03036. Our main result is the computation of the spectral gap, and mixing times, for two natural boundary conditions. We observe that these time scales depend heavily on the boundary condition in this scaling regime., 47 pages, 8 figures, shortened argument in Section 5 and minor corrections

We consider the simple exclusion process with $k$ particles on a segment of length $N$ performing random walks with transition $p>1/2$ to the right and $q=1-p$ to the left. We focus on the case where the asymmetry in the jump rates $b=p-q>0$ vanishes in the limit when $N$ and $k$ tend to infinity, and obtain sharp asymptotics for the mixing times of this sequence of Markov chains in the two cases where the asymmetry is either much larger or much smaller than $(\log k)/N$. We show that in the former case ($b \gg (\log k)/N$), the mixing time corresponds to the time needed to reach macroscopic equilibrium, like for the strongly asymmetric (i.e.\ constant $b$) case studied in [LL18], while the latter case ($b \ll (\log k)/N$) macroscopic equilibrium is not sufficient for mixing and one must wait till local fluctuations equilibrate, similarly to what happens in the symmetric case worked out in [Lac16b]. In both cases, convergence to equilibrium is abrupt: we have a cutoff phenomenon for the total-variation distance. We present a conjecture for the remaining regime when the asymmetry is of order $(\log k) / N$., 39 pages

A sequence of chains exhibits (total-variation) cutoff (resp., pre-cutoff) if for all $0, Comment: 35 pages, 7 figures. Section 3 was revised in the latest version

We show that the total-variation mixing time of the lamplighter random walk on fractal graphs exhibit sharp cutoff when the underlying graph is transient (namely of spectral dimension greater than two). In contrast, we show that such cutoff can not occur for strongly recurrent underlying graphs (i.e. of spectral dimension less than two)., 19 pages, 9 figures

We consider a dynamic random graph on $n$ vertices that is obtained by starting from a random graph generated according to the configuration model with a prescribed degree sequence and at each unit of time randomly rewiring a fraction $\alpha_n$ of the edges. We are interested in the mixing time of a random walk without backtracking on this dynamic random graph in the limit as $n\to\infty$, when $\alpha_n$ is chosen such that $\lim_{n\to\infty} \alpha_n (\log n)^2 = \beta \in [0,\infty]$. In [1] we found that, under mild regularity conditions on the degree sequence, the mixing time is of order $1/\sqrt{\alpha_n}$ when $\beta=\infty$. In the present paper we investigate what happens when $\beta \in [0,\infty)$. It turns out that the mixing time is of order $\log n$, with the scaled mixing time exhibiting a one-sided cutoff when $\beta \in (0,\infty)$ and a two-sided cutoff when $\beta=0$. The occurrence of a one-sided cutoff is a rare phenomenon. In our setting it comes from a competition between the time scales of mixing on the static graph, as identified by Ben-Hamou and Salez [4], and the regeneration time of first stepping across a rewired edge., Comment: 14 pages, 5 figures

We show that the spectral-gap of a general zero range process can be controlled in terms of the spectral-gap of a single particle. This is in the spirit of Aldous' famous spectral-gap conjecture for the interchange process. Our main inequality decouples the role of the geometry (defined by the jump matrix) from that of the kinetics (specified by the exit rates). Among other consequences, the various spectral-gap estimates that were so far only available on the complete graph or the $d$-dimensional torus now extend effortlessly to arbitrary geometries. As an illustration, we determine the exact order of magnitude of the spectral-gap of the rate-one $\textbf{ZRP}$ on any regular graph and, more generally, for any doubly stochastic jump matrix., Comment: 13 pages. Final version, to appear in Ann. Appl. Probab

For any discrete target distribution, we exploit the connection between Markov chains and Stein's method via the generator approach and express the solution of Stein's equation in terms of expected hitting time. This yields new upper bounds of Stein's factors in terms of the parameters of the Markov chain, such as mixing time and the gradient of expected hitting time. We compare the performance of these bounds with those in the literature, and in particular we consider Stein's method for discrete uniform, binomial, geometric and hypergeometric distribution. As another application, the same methodology applies to bound expected hitting time via Stein's factors. This article highlights the interplay between Stein's method, modern Markov chain theory and classical fluctuation theory., 10 pages

In this paper, we propose a new Markov chain which generalizes random-to-random shuffling on permutations to random-to-random shuffling on linear extensions of a finite poset of size $n$. We conjecture that the second largest eigenvalue of the transition matrix is bounded above by $(1+1/n)(1-2/n)$ with equality when the poset is disconnected. This Markov chain provides a way to sample the linear extensions of the poset with a relaxation time bounded above by $n^2/(n+2)$ and a mixing time of $O(n^2 \log n)$. We conjecture that the mixing time is in fact $O(n \log n)$ as for the usual random-to-random shuffling., Comment: 16 pages, 10 figures; v2: typos fixed plus extra information in figures; v3: added explicit conjecture 2.2 + Section 3.6 on the diameter of the Markov Chain as evidence + misc minor improvements; v4: fixed bibliography

Nous etudions un processus d’Ising avec contraintes cinetiques (PICC) associe a un graphe $G$ et un parametre de densite $p$. Ce processus est un systeme de particules en interaction avec espace d’etats $\Omega=\{0,1\}^{G}$, decrivant les positions des particules. Les « contraintes » apparaissant dans le nom de ce processus referent a la regle suivante: un sommet ne peut pas changer son etat a moins qu’il ait un voisin dans l’etat « 1 ». Le PICC a ete propose par des physiciens comme un modele pour la transition vitreuse. Dans ce travail, nous analysons le temps de melange d’un PICC sur le tore de dimension 2 $G=\mathbb{Z}_{L}^{2}$ dans le regime de faible densite $p=\frac{c}{L^{2}}$, ou $0

We study Markov chains for randomly sampling $k$-colorings of a graph with maximum degree $\Delta$. Our main result is a polynomial upper bound on the mixing time of the single-site update chain known as the Glauber dynamics for planar graphs when $k=\Omega(\Delta/\log{\Delta})$. Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most $\Delta^{1-\eps}$, for fixed $\eps > 0$. The main challenge when $k \le \Delta + 1$ is the possibility of "frozen" vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when $\Delta = O(1)$, even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using "local uniformity" properties., Comment: Preliminary version appeared in STOC 2007. This version contains revised proofs

We study the effect of boundary conditions on the relaxation time (i.e., inverse spectral gap) of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independent sets weighted by a parameter $\lambda$, called the activity or fugacity. The Glauber dynamics is the Markov chain that updates a randomly chosen vertex in each step. On the infinite tree with branching factor $b$, the hard-core model can be equivalently defined as a broadcasting process with a parameter $\omega$ which is the positive solution to $\lambda=\omega(1+\omega)^b$, and vertices are occupied with probability $\omega/(1+\omega)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and nonreconstruction regions at $\omega_r\approx \ln{b}/b$. Reconstruction has been of considerable interest recently since it appears to be intimately connected to the efficiency of local algorithms on locally tree-like graphs, such as sparse random graphs. In this paper we show that the relaxation time of the Glauber dynamics on regular trees $T_h$ of height $h$ with branching factor $b$ and $n$ vertices undergoes a phase transition around the reconstruction threshold. In particular, we construct a boundary condition for which the relaxation time slows down at the reconstruction threshold. More precisely, for any $\omega \le \ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is $\Omega(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction threshold we show that for every $\delta>0$, for $\omega=(1+\delta)\ln{b}/b$, the relaxation time on $T_h$ with any boundary condition is $O(n^{1+\delta + o_b(1)})$, and we construct a boundary condition where the relaxation time is $\Omega(n^{1+\delta/2 - o_b(1)})$. To prove this lower bound in the reconstruction region we introduce a general technique that transforms a reconstruction algorithm into a set with poor conductance.

In this paper, we investigate the mixing time of the adjacent transposition shuffle for a deck of $N$ cards. We prove that around time $N^2\log N/(2\pi^2)$, the total variation distance to equilibrium of the deck distribution drops abruptly from $1$ to $0$, and that the separation distance has a similar behavior but with a transition occurring at time $(N^2\log N)/\pi^2$. This solves a conjecture formulated by David Wilson. We present also similar results for the exclusion process on a segment of length $N$ with $k$ particles., Comment: Published at http://dx.doi.org/10.1214/15-AOP1004 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Consider the subgraph of the discrete $d$-dimensional torus of size length $N$, $d\ge3$, induced by the range of the simple random walk on the torus run until the time $uN^d$. We prove that for all $d\ge 3$ and $u>0$, the mixing time for the random walk on this subgraph is of order $N^2$ with probability at least $1 - Ce^{-(\log N)^2}$., 11 pages

We study the mixing time of random graphs in the $d$-dimensional toric unit cube $[0,1]^d$ generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights, drawn from some distribution. The connectivity threshold for GTGs is comparable to that of RGGs, essentially corresponding to a connectivity radius of $r=(\log n/n)^{1/d}$. However, the degree distributions at this threshold are quite different: in an RGG the degrees are essentially uniform, while RGGs have heterogeneous degrees that depend upon the weight distribution. Herein, we study the mixing times of random walks on $d$-dimensional GTGs near the connectivity threshold for $d \geq 2$. If the weight distribution function decays with $\mathbb{P}[W \geq x] = O(1/x^{d+��})$ for an arbitrarily small constant $��>0$ then the mixing time of GTG is $\mixbound$. This matches the known mixing bounds for the $d$-dimensional RGG.

The cutoff phenomenon describes the case when an abrupt transition occurs in the convergence of a Markov chain to its equilibrium measure. There are various metrics which can be used to measure the distance to equilibrium, each of which corresponding to a different notion of cutoff. The most commonly used are the total-variation and the separation distances. In this note we prove that the cutoff for these two distances are not equivalent by constructing several counterexamples which display cutoff in total-variation but not in separation and with the opposite behavior, including lazy simple random walk on a sequence of uniformly bounded degree expander graphs. These examples give a negative answer to a question of Ding, Lubetzky and Peres., Comment: 37 pages, 9 figures. Details added for some proofs and minor corrections

We prove a version of McDiarmid's bounded differences inequality for Markov chains, with constants proportional to the mixing time of the chain. We also show variance bounds and Bernstein-type inequalities for empirical averages of Markov chains. In the case of non-reversible chains, we introduce a new quantity called the "pseudo spectral gap", and show that it plays a similar role for non-reversible chains as the spectral gap plays for reversible chains. Our techniques for proving these results are based on a coupling construction of Katalin Marton, and on spectral techniques due to Pascal Lezaud. The pseudo spectral gap generalises the multiplicative reversiblication approach of Jim Fill., Comment: 42 pages. In the previous version, the proofs of Bernstein's inequalities for Markov chains on general state spaces were using an argument from the proofs of Theorems 1.1 and 1.5 on pages 100-101 of the doctoral thesis of Pascal Lezaud. A part of that argument was incomplete. In this version, we correct this

We consider two independent Markov chains on the same finite state space, and study their intersection time, which is the first time that the trajectories of the two chains intersect. We denote by $t_I$ the expectation of the intersection time, maximized over the starting states of the two chains. We show that, for any reversible and lazy chain, the total variation mixing time is $O(t_I)$. When the chain is reversible and transitive, we give an expression for $t_I$ using the eigenvalues of the transition matrix. In this case, we also show that $t_I$ is of order $\sqrt{n \mathbb {E}\!\left [I\right ]} $, where $I$ is the number of intersections of the trajectories of the two chains up to the uniform mixing time, and $n$ is the number of states. For random walks on trees, we show that $t_I$ and the total variation mixing time are of the same order. Finally, for random walks on regular expanders, we show that $t_I$ is of order $\sqrt{n} $.

Suppose that $\CG$ is a finite, connected graph and $X$ is a lazy random walk on $\CG$. The lamplighter chain $X^\diamond$ associated with $X$ is the random walk on the wreath product $\CG^\diamond = \Z_2 \wr \CG$, the graph whose vertices consist of pairs $(f,x)$ where $f$ is a labeling of the vertices of $\CG$ by elements of $\Z_2$ and $x$ is a vertex in $\CG$. There is an edge between $(f,x)$ and $(g,y)$ in $\CG^\diamond$ if and only if $x$ is adjacent to $y$ in $\CG$ and $f(z) = g(z)$ for all $z \neq x,y$. In each step, $X^\diamond$ moves from a configuration $(f,x)$ by updating $x$ to $y$ using the transition rule of $X$ and then sampling both $f(x)$ and $f(y)$ according to the uniform distribution on $\Z_2$; $f(z)$ for $z \neq x,y$ remains unchanged. We give matching upper and lower bounds on the uniform mixing time of $X^\diamond$ provided $\CG$ satisfies mild hypotheses. In particular, when $\CG$ is the hypercube $\Z_2^d$, we show that the uniform mixing time of $X^\diamond$ is $\Theta(d 2^d)$. More generally, we show that when $\CG$ is a torus $\Z_n^d$ for $d \geq 3$, the uniform mixing time of $X^\diamond$ is $\Theta(d n^d)$ uniformly in $n$ and $d$. A critical ingredient for our proof is a concentration estimate for the local time of random walk in a subset of vertices., Comment: 2 figures, 27 pages. We added a new section containing a detailed proof of that our conditions hold for the torii $Z_n^d$, uniformly in $n$ and $d$

The card-cyclic-to-random shuffle on $n$ cards is defined as follows: at time $t$ remove the card with label $t$ mod $n$ and randomly reinsert it back into the deck. Pinsky [Probabilistic and combinatorial aspects of the card-cyclic-to-random shuffle (2011). Unpublished manuscript] introduced this shuffle and asked how many steps are needed to mix the deck. He showed $n$ steps do not suffice. Here we show that the mixing time is on the order of $\Theta(n\log n)$.

We analyse a random walk on the ring of integers mod $n$, which at each time point can make an additive `step' or a multiplicative `jump'. When the probability of making a jump tends to zero as an appropriate power of $n$ we prove the existence of a total variation pre-cutoff for this walk. In addition, we show that the process obtained by subsampling our walk at jump times exhibits a true cutoff, with mixing time dependent on whether the step distribution has zero mean., 15 pages; accepted for publication in Bernoulli Journal

We prove that the noisy voter model mixes extremely fast -- in time of $O(\log n)$ on any graph with $n$ vertices -- for arbitrarily small values of the `noise parameter'. We then explain why, as a result, this is an example of a spin system that is always in the `high-temperature regime'., 9 pages

In this paper, we investigate the mixing time of the simple exclusion process on the circle with $N$ sites, with a number of particle $k(N)$ tending to infinity, both from the worst initial condition and from a typical initial condition. We show that the worst-case mixing time is asymptotically equivalent to $(8\pi^2)^{-1}N^2\log k$, while the cutoff window, is identified to be $N^2$. Starting from a typical condition, we show that there is no cutoff and that the mixing time is of order $N^2$., Comment: 37 pages, 3 Figures

Given a finite, connected graph $G$, the lamplighter chain on $G$ is the lazy random walk $X^\diamond$ on the associated lamplighter graph $G^\diamond={\mathbf Z}_2 \wr G$. The mixing time of the lamplighter chain on the torus ${\mathbf Z}_n^d$ is known to have a cutoff at a time asymptotic to the cover time of ${\mathbf Z}_n^d$ if $d=2$, and to half the cover time if $d \ge 3$. We show that the mixing time of the lamplighter chain on $G_n(a)={\mathbf Z}_n^2 \times {\mathbf Z}_{a \log n}$ has a cutoff at $\psi(a)$ times the cover time of $G_n(a)$ as $n \to \infty$, where $\psi$ is an explicit weakly decreasing map from $(0,\infty)$ onto $[1/2,1)$. In particular, as $a > 0$ varies, the threshold continuously interpolates between the known thresholds for ${\mathbf Z}_n^2$ and ${\mathbf Z}_n^3$. Perhaps surprisingly, we find a phase transition (non-smoothness of $\psi$) at the point $a_*=\pi r_3 (1+\sqrt{2})$, where high dimensional behavior ($\psi(a)=1/2$ for all $a \ge a_*$) commences. Here $r_3$ is the effective resistance from $0$ to $\infty$ in ${\mathbf Z}^3$., Comment: 40 pages and 5 figures

We initiate the study of mixing times of Markov chain under monotone censoring. Suppose we have some Markov Chain $M$ on a state space $\Omega$ with stationary distribution $\pi$ and a monotone set $A \subset \Omega$. We consider the chain $M'$ which is the same as the chain $M$ started at some $x \in A$ except that moves of $M$ of the form $x \to y$ where $x \in A$ and $y \notin A$ are {\em censored} and replaced by the move $x \to x$. If $M$ is ergodic and $A$ is connected, the new chain converges to $\pi$ conditional on $A$. In this paper we are interested in the mixing time of the chain $M'$ in terms of properties of $M$ and $A$. Our results are based on new connections with the field of property testing. A number of open problems are presented., Comment: 6 pages

In this note, we demonstrate an instance of bounded-degree graphs of size $n$, for which the total variation mixing time for the random walk is decreased by a factor of $\log n/ \log\log n$ if we multiply the edge-conductances by bounded factors in a certain way., 7pages, 2 figures

We prove an upper bound for the $\varepsilon$-mixing time of the symmetric exclusion process on any graph G, with any feasible number of particles. Our estimate is proportional to $\mathsf{T}_{\mathsf{RW}(G)}\ln(|V|/\varepsilon)$, where |V| is the number of vertices in G, and $\mathsf{T}_{\mathsf{RW}(G)}$ is the 1/4-mixing time of the corresponding single-particle random walk. This bound implies new results for symmetric exclusion on expanders, percolation clusters, the giant component of the Erdos-Renyi random graph and Poisson point processes in $\mathbb{R}^d$. Our technical tools include a variant of Morris's chameleon process., Comment: Published in at http://dx.doi.org/10.1214/11-AOP714 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We study the convergence rate to stationarity for a class of exchangeable partition-valued Markov chains called cut-and-paste chains. The law governing the transitions of a cut-and-paste chain are determined by products of i.i.d. stochastic matrices, which describe the chain induced on the simplex by taking asymptotic frequencies. Using this representation, we establish upper bounds for the mixing times of ergodic cut-and-paste chains, and under certain conditions on the distribution of the governing random matrices we show that the "cutoff phenomenon" holds.

We analyze the mixing time of a class of oriented kinetically constrained spin models (KCMs) on a d-dimensional lattice of $n^d$ sites. A typical example is the North-East model, a 0-1 spin system on the two-dimensional integer lattice that evolves according to the following rule: whenever a site's southerly and westerly nearest neighbours have spin 0, with rate one it resets its own spin by tossing a p-coin, at all other times its spin remains frozen. Such models are very popular in statistical physics because, in spite of their simplicity, they display some of the key features of the dynamics of real glasses. We prove that the mixing time is O(n log n) whenever the relaxation time is O(1). Our study was motivated by the "shape" conjecture put forward by G. Kordzakhia and S.P. Lalley., 10 pages, 1 figure; fixed typos, added acknowledgement

Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product H\wr G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_{v\in V(G)} is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H., 30 pages, 1 figure

We show that the measure on markings of $\mathbf {Z}_n^d$, $d\geq3$, with elements of ${0,1}$ given by i.i.d. fair coin flips on the range $\mathcal {R}$ of a random walk $X$ run until time $T$ and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold $T=1/2T_{{\mathrm {cov}}}(\mathbf {Z}_n^d)$. As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph $\mathbf {Z}_2\wr \mathbf {Z}_n^d$, $d\geq3$, has a cutoff with threshold $1/2T_{{\mathrm {cov}}}(\mathbf {Z}_n^d)$. We give a general criterion under which both of these results hold; other examples for which this applies include bounded degree expander families, the intersection of an infinite supercritical percolation cluster with an increasing family of balls, the hypercube and the Caley graph of the symmetric group generated by transpositions. The proof also yields precise asymptotics for the decay of correlation in the uncovered set., Comment: Published in at http://dx.doi.org/10.1214/10-AOP624 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)