Mixing times for the interchange process

MaRDI QIDQ2863811zbMATH OpenFDO

Authors Johan Jonasson

Publication date 4 December 2013

Published in ALEA. Latin American Journal of Probability and Mathematical Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.6916, http://alea.impa.br/articles/v9/09-26.pdf

zbMATH Keywords

card shufflingcomparison techniqueelectrical networkrandom graphWilson's technique

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Consider the interchange process on a connected graph $G=(V,E)$ on $n$ vertices. I.e. shuffle a deck of cards by first placing one card at each vertex of $G$ in a fixed order and then at each tick of the clock, picking an edge uniformly at random and switching the two cards at the end vertices of the edge with probability 1/2. Well known special cases are the random transpositions shuffle, where $G$ is the complete graph, and the transposing neighbors shuffle, where $G$ is the $n$-path. Other cases that have been studied are the $d$-dimensional grid, the hypercube, lollipop graphs and ErdH os-R'enyi random graphs above the threshold for connectedness. In this paper the problem is studied for general $G$. Special attention is focused on trees, random trees and the giant component of critical and supercritical $G(N,p)$ random graphs. Upper and lower bounds on the mixing time are given. In many of the cases, we establish the exact order of the mixing time. We also mention the cases when $G$ is the hypercube and when $G$ is a bounded-degree expander, giving upper and lower bounds on the mixing time.

Recommendations

• scientific article; zbMATH DE number 1195779
• Sensitivity of mixing times
• The mixing time for simple exclusion
• Entry times distribution for mixing systems
• Mixing times and moving targets
• Recurrence times and rates of mixing
• Mixing time for the solid-on-solid model
• Mixing time for the solid-on-solid model
• On sensitivity of mixing times and cutoff

Cited in

(14)

• Rate of convergence for shuffling cards by transpositions
• Comparing with octopi
• The full spectrum of random walks on complete finite \(d\)-ary trees
• A sharp log-Sobolev inequality for the multislice
• SPEck: mining statistically-significant sequential patterns efficiently with exact sampling
• The exclusion process mixes (almost) faster than independent particles
• The interchange process on high-dimensional products
• Existence of a phase transition of the interchange process on the Hamming graph
• A version of Aldous' spectral-gap conjecture for the zero range process
• The mixing time of the giant component of a random graph
• Entry times distribution for mixing systems
• Mixing of the averaging process and its discrete dual on finite-dimensional geometries
• Cutoff on trees is rare
• On the diameters of friends-and-strangers graphs

This page was built for publication: Mixing times for the interchange process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2863811)