By viewing the @math -simplex as the set of positions of @math 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 @math . The results are extended to the family of log-concave distributions obtained by replacing the uniform sampling by a symmetric log-concave Beta distribution.
The sharp upper bound for the extremal processes (by symmetry, we may consider only the highest process) is performed in Section . This part of the proof is based on a strategy developed in the discrete setting by @cite_12 for the adjacent transposition process. It relies on the FKG inequality and a version of the censoring inequality from @cite_8 . Censoring inequalities are known to hold provided one has monotonicity of the density of the initial condition with respect to the invariant measure. While in the discrete setting this adapts well to the extremal process, in our context a nontrivial adaptation is required since the initial condition is singular with respect to the invariant measure.
@cite_12 @cite_8
1661853172 2031651515
In this paper, we investigate the mixing time of the adjacent transposition shuffle for a deck of cards. We prove that around time N^2 N (2 ^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 N) ^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. We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Toninelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.