Random walks and hyperplane arrangements

• 成果类型: Article
• 署名作者: Brown, KS; Diaconis, P
• 署名单位: Cornell University; Cornell University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 1998
• 页码: 1813-1854
• 关键词: orders

摘要

Let E be the set of chambers of a real hyperplane arrangement. We study a random walk on E 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.