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

DOI10.1007/S00440-018-0872-7MaRDI QIDQ2312684zbMATH OpenOpenAlexWikidataFDO

Authors Evita Nestoridi

Publication date 17 July 2019

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.00310

zbMATH Keywords

Markov chainsreal hyperplane arrangements

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: 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.

Recommendations

• Functions of random walks on hyperplane arrangements
• Random walks and hyperplane arrangements
• Cutoff for a stratified random walk on the hypercube
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Cutoff for a stratified random walk on the hypercube

Cites work

• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• A rule of thumb for riffle shuffling
• An exact formula for the move-to-front rule for self-organizing lists
• Analyzing randomized search heuristics: tools from probability theory
• Can extra updates delay mixing?
• Functions of random walks on hyperplane arrangements
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 903457 (Why is no real title available?)
• Information Loss in Riffle Shuffling
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing time for the Ising model: a uniform lower bound for all graphs
• On the matrix occurring in a linear search problem
• Random walks and hyperplane arrangements
• Semigroups, rings, and Markov chains
• Shuffling Cards and Stopping Times
• Speed and concentration of the covering time for structured coupon collectors
• Stochastic rearrangement rules for self-organizing data structures
• The collector's problem with group drawings
• The cutoff phenomenon in finite Markov chains.
• The heaps process, libraries, and size-biased permutations
• Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model
• Trailing the dovetail shuffle to its lair

Cited in

(6)

• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Random Walks and Plane Arrangements in Three Dimensions
• Upper Bounds on Mixing Time of Finite Markov Chains
• Mixing time bounds for edge flipping on regular graphs
• Enumerative theory for the Tsetlin library
• Functions of random walks on hyperplane arrangements

This page was built for publication: Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312684)