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

2017/05/31 by Evita Nestoridi, Nestoridi, Evita
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1706.00310

openalex publication_date 2017/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Random walks on hyperplane arrangements and stopping times
• Functions of random walks on hyperplane arrangements
• Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
• Strong stationary times for features of random walks
• Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries