期刊名称：Latin American Journal of Probability and Mathematical Statistics
电子版ISSN：1980-0436
出版年度：2012
卷号：IX
期号：2
页码：667-683
出版社：Instituto Nacional De Matemática Pura E Aplicada
摘要：Consider the interchange process on a connected graph G = (V,E) onn vertices. I.e. shuffle a deck of cards by first placing one card at each vertex ofG in a fixed order and then at each tick of the clock, picking an edge uniformly atrandom and switching the two cards at the end vertices of the edge with probability1/2. Well known special cases are the random transpositions shuffle, where G is thecomplete graph, and the transposing neighbors shuffle, where G is the n-path. Othercases that have been studied are the d-dimensional grid, the hypercube, lollipopgraphs and Erd˝os-R´enyi random graphs above the threshold for connectedness.In this paper the problem is studied for general G. Special attention is focusedon 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 manyof the cases, we establish the exact order of the mixing time. We also mention thecases when G is the hypercube and when G is a bounded-degree expander, givingupper and lower bounds on the mixing time.
关键词：card shuffling; random graph; comparison technique; Wilson’s tech-;nique; electrical network
