A random walk on the rook placements on a Ferrers board (Q1918903)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A random walk on the rook placements on a Ferrers board |
scientific article |
Statements
A random walk on the rook placements on a Ferrers board (English)
0 references
21 July 1996
0 references
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.
0 references
Ferrers board
0 references
Ferrers diagram
0 references
chessboard
0 references
Markov chain
0 references
rook placements
0 references
rate of convergence
0 references
eigenvalues
0 references
transition matrix
0 references
random walks
0 references