Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement

• 成果类型: Article
• 署名作者: Nestoridi, Evita
• 署名单位: Princeton University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-018-0872-7
• 发表日期: 2019
• 页码: 929-943
• 关键词: rule

摘要

This paper studies Markov chains on the chambers of real hyperplane arrangements, a model that generalizes famous examples, such as the Tsetlin library and riffle shuffles. We discuss cutoff for the Tsetlin library for general weights, and we give an exact formula for the separation distance for the hyperplane arrangement walk. We introduce lower bounds, which allow for the first time to study cutoff for hyperplane arrangement walks under certain conditions. Using similar techniques, we also prove a uniform lower bound for the mixing time of Glauber dynamics on a monotone system.