Random walks and hyperplane arrangements

Kenneth S. Brown, Persi Diaconis

Type: Article

Publication Date: 1998-10-01

Citations: 165

DOI: https://doi.org/10.1214/aop/1022855884

Abstract

Letbe the set of chambers of a real hyperplane arrangement.We study a random walk on introduced by Bidigare, Hanlon and Rockmore.This includes various shuffling schemes used in computer science, biology and card games.It also includes random walks on zonotopes and zonotopal tilings.We find the stationary distributions of these Markov chains, give good bounds on the rate of convergence to stationarity, and prove that the transition matrices are diagonalizable.The results are extended to oriented matroids.

Locations

The Annals of Probability - View - PDF

Similar Works

Action	Title	Year	Authors
+	Random walks on hyperplane arrangements and stopping times	2016	Evita Nestoridi
+	Functions of random walks on hyperplane arrangements	2009	Christos A. Athanasiadis Persi Diaconis
+	Functions of random walks on hyperplane arrangements	2009	Christos A. Athanasiadis Persi Diaconis
+ PDF Chat	Functions of random walks on hyperplane arrangements	2010	Christos A. Athanasiadis Persi Diaconis
+	Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement	2017	Evita Nestoridi
+	Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement	2017	Evita Nestoridi
+	Random Walks and Plane Arrangements in Three Dimensions	1999	Louis J. Billera Kenneth S. Brown Persi Diaconis
+	Random Walks and Geometry	2004	Vadim A. Kaimanovich Klaus Schmidt Wolfgang Woess
+	Deterministic walks in random environments	2003	Leonid Bunimovich
+	Markov Chain Algorithms for Planar Lattice Structures	2001	Michael Luby Dana Randall Alistair Sinclair
+	Random Walks on a Lattice	2021
+	Random walks on a lattice	1982	Mark Westcott
+	Random walks in a random environment	2004	S. R. S. Varadhan
+	The geometry of random tournaments	2020	Mario Sánchez Brett Kolesnik
+	Phase Transitions in Random Dyadic Tilings and Rectangular Dissections	2018	Sarah Cannon Sarah Miracle Dana Randall
+	Mixing Times of Markov Chains of 2-Orientations	2016	Stefan Felsner Daniel Heldt
+	Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries	2008	Anders Björner
+	Random Walks	1996	Denis Bosq Hung T. Nguyen
+	Random walks	1994	Gunnar Blom Lars Holst Dennis Sandell
+	Phase Transitions in Random Dyadic Tilings and Rectangular Dissections	2014	Sarah Cannon Sarah Miracle Dana Randall

Works That Cite This (154)

Action	Title	Year	Authors
+	Hoffman–Newman–Radford	2020	Marcelo Aguiar Swapneel Mahajan
+ PDF Chat	Oriented Interval Greedoids	2011	Franco Saliola Hugh Thomas
+	Bimonads on species	2020	Marcelo Aguiar Swapneel Mahajan
+ PDF Chat	Combinatorial topology and the global dimension of algebras arising in combinatorics	2015	Stuart Margolis Franco Saliola Benjamin Steinberg
+	Generalized Riffle Shuffles and Quasisymmetric Functions	2001	Richard P. Stanley
+	None	2000	Kenneth S. Brown
+	Markov Chains from Descent Operators on Combinatorial Hopf Algebras	2016	C. Y. Amy Pang
+	Semigroups embeddable in hyperplane face monoids	2012	Stuart Margolis Franco Saliola Benjamin Steinberg
+	Threshold graph limits and random threshold graphs	2009	Persi Diaconis Susan Holmes Svante Janson
+	Carries, shuffling, and symmetric functions	2009	Persi Diaconis Jason Fulman

Works Cited by This (26)

Action	Title	Year	Authors
+ PDF Chat	None	1992	François Bergeron Nantel Bergeron Robert B. Howlett D. E. Taylor
+	Threshold Graphs and Related Topics	1995	N. V. R. Mahadev Uri N. Peled
+	Group representations in probability and statistics	1988	Persi Diaconis
+	A Homotopy Complementation Formula for Partially Ordered Sets	1983	Anders Björner James W. Walker
+	Enumeration of labelled threshold graphs and a theorem of frobenius involving eulerian polynomials	1987	Janet Beissinger Uri N. Peled
+	Analysis of Top To Random Shuffles	1992	Persi Diaconis James Allen Fill Jim Pitman
+	The cutoff phenomenon in finite Markov chains.	1996	Persi Diaconis
+	Asymptotic analysis of a random walk on a hypercube with many dimensions	1990	Persi Diaconis Ronald Graham J. A. Morrison
+ PDF Chat	Iterated random functions	2017	Persi Diaconis David A. Freedman
+	Facing up to arrangements: face-count formulas for partitions of space by hyperplanes	1975	Thomas Zasĺavsky