A random walk on the rook placements on a Ferrers board
type: Item
instance of: scholarly article
title: A random walk on the rook placements on a Ferrers board
zbMATH Open document ID: 0851.05100
published in: The Electronic Journal of Combinatorics
publication date: 1996-07-21T00:00:00Z
full work available at URL: https://eudml.org/doc/118912
full work available at URL: R26
review text: Summary: 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 extreme 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.
Mathematics Subject Classification ID: 05E35
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 05B99
zbMATH DE Number: 907665
zbMATH Keywords: Ferrers board
zbMATH Keywords: Ferrers diagram
zbMATH Keywords: chessboard
zbMATH Keywords: Markov chain
zbMATH Keywords: rook placements
zbMATH Keywords: rate of convergence
zbMATH Keywords: eigenvalues
zbMATH Keywords: transition matrix
zbMATH Keywords: random walks
author: Philip J. Hanlon
MaRDI profile type: Publication
Recommended article: Rooks on Ferrers boards and matrix integrals
Recommended article: Invisible permutations and rook placements on a Ferrers board
Recommended article: On criteria for rook equivalence of Ferrers boards
Recommended article: The rook numbers of Ferrers boards and the related restricted permutation numbers
Recommended article: A graph theory of rook placements
Recommended article: Derangements on a Ferrers board
Recommended article: The computational challenge of enumerating high-dimensional rook walks
Recommended article: Q3479330
Recommended article: Rook problem on a fractal lattice
Recommended article: Q4883335
description: scientific article; zbMATH DE number 907665