Random Walks on Wreath Products of Groups

Clyde H. Schoolfield ()
Additional contact information
Clyde H. Schoolfield: Harvard University

Journal of Theoretical Probability, 2002, vol. 15, issue 3, 667-693

Abstract: Abstract We bound the rate of convergence to uniformity for a certain random walk on the complete monomial groups G≀S n for any group G. Specifically, we determine that $${\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 2}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$2$}}$$ n log n+ $$\frac{1}{4}$$ n log (|G|−1|) steps are both necessary and sufficient for ℓ2 distance to become small. We also determine that $${\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 2}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$2$}}$$ n log n steps are both necessary and sufficient for total variation distance to become small. These results provide rates of convergence for random walks on a number of groups of interest: the hyperoctahedral group ℤ2≀S n , the generalized symmetric group ℤ m ≀S n , and S m ≀S n . In the special case of the hyperoctahedral group, our random walk exhibits the “cutoff phenomenon.”

Keywords: Random walk; Markov chain; wreath product; hyperoctahedral group; generalized symmetric group; complete monomial group; Fourier transform (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1016219932004 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:15:y:2002:i:3:d:10.1023_a:1016219932004

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1023/A:1016219932004

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().