A random walk on the rook placements on a Ferrers board

Phil Hanlon

The electronic journal of combinatorics, The Foata Festschrift volume, Tome 3 (1996) no. 2

Résumé

Let $B$ be a Ferrers board, i.e., the board obtained by removing the Ferrers diagram of a partition from the top right corner of an $n\times n$ chessboard. We consider a Markov chain on the set $R$ of rook placements on $B$ in which you can move from one placement to any other legal placement obtained by switching the columns in which two rooks sit. We give sharp estimates for the rate of convergence of this Markov chain using spectral methods. As part of this analysis we give a complete combinatorial description of the eigenvalues of the transition matrix for this chain. We show that two extremes cases of this Markov chain correspond to random walks on groups which are analyzed in the literature. Our estimates for rates of convergence interpolate between those two results.

Détail

DOI : 10.37236/1284

Classification : 60G50, 05B99
Mots-clés : Ferrers board, Ferrers diagram, chessboard, Markov chain, rook placements, rate of convergence, eigenvalues, transition matrix, random walks