CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Mixing times for the interchange process

Johan Jonasson (Institutionen för matematiska vetenskaper, matematik)
Alea-Latin American Journal of Probability and Mathematical Statistics (1980-0436). Vol. 9 (2012), 2, p. 667-683.
[Artikel, refereegranskad vetenskaplig]

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 completegraph, and the transposing neighbors shuffle, where G is the n-path. Other cases that have been studied are thed-dimensional grid, the hypercube, lollipop graphs and Erdos-Renyi 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) randomgraphs. 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.

Nyckelord: card shuffling, random graph, comparison technique, Wilson's technique, electrical network



Denna post skapades 2013-09-24. Senast ändrad 2013-10-14.
CPL Pubid: 183935

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Sannolikhetsteori och statistik

Chalmers infrastruktur