Functions of random walks on hyperplane arrangements

DOI10.1016/J.AAM.2010.02.001zbMATH Open1239.60071arXiv0912.1686OpenAlexW2004035289MaRDI QIDQ990770FDOQ990770

Persi Diaconis, Christos A. Athanasiadis

Publication date: 1 September 2010

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Many seemingly disparate Markov chains are unified when viewed as random walks on the set of chambers of a hyperplane arrangement. These include the Tsetlin library of theoretical computer science and various shuffling schemes. If only selected features of the chains are of interest, then the mixing times may change. We study the behavior of hyperplane walks, viewed on a subarrangement of a hyperplane arrangement. These include many new examples, for instance a random walk on the set of acyclic orientations of a graph. All such walks can be treated in a uniform fashion, yielding diagonalizable matrices with known eigenvalues, stationary distribution and good rates of convergence to stationarity.

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

zbMATH Keywords

random walkeigenvalueshyperplane arrangementmixing rateTsetlin libraryacyclic orientationdescent setinverse shufflessubarrangement

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Oriented Matroids
• Trailing the dovetail shuffle to its lair
• Buildings of spherical type and finite BN-pairs
• Acyclic orientations of graphs
• Random walks and hyperplane arrangements
• Markov functions
• Semigroups, rings, and Markov chains
• Möbius functions and semigroup representation theory.
• Finite Continuous Time Markov Chains
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Carries, shuffling, and symmetric functions
• Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• A rule of thumb for riffle shuffling
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Deformations of Coxeter hyperplane arrangements
• The size distribution for Markov equivalence classes of acyclic digraph models.
• Characteristic polynomials of subspace arrangements and finite fields
• On the matrix occurring in a linear search problem
• Hyperplane arrangements, interval orders, and trees.
• Coxeter groups and Hopf algebras.
• A Hodge decomposition interpretation for the coefficients of the chromatic polynomial
• The coloring ideal and coloring complex of a graph
• Algebras associated to acyclic directed graphs
• Analysis of Top To Random Shuffles
• Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Limiting search cost distribution for the move-to-front rule with random request probabilities
• From association to causation via regression
• A general commutative descent algebra
• Spectra of some interesting combinatorial matrices related to oriented spanning trees on a directed graph

Cited In (22)

• Random walks on rings and modules
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• Generating a random signed permutation with random reversals
• Quivers of monoids with basic algebras
• Edge flipping in graphs
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Lumpings of algebraic Markov chains arise from subquotients
• Hopf algebras and Markov chains: two examples and a theory
• Mixing time bounds for edge flipping on regular graphs
• Title not available (Why is that?)
• Markov chains, ${\mathscr R}$-trivial monoids and representation theory
• Face monoid actions and tropical hyperplane arrangements
• Upper Bounds on Mixing Time of Finite Markov Chains
• Combinatorial Markov chains on linear extensions
• The full spectrum of random walks on complete finite \(d\)-ary trees
• Character theory of monoids over an arbitrary field.
• Combinatorial topology and the global dimension of algebras arising in combinatorics
• Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry
• Mixing time for Markov chain on linear extensions
• Edge flipping in the complete graph
• A rule of thumb for riffle shuffling
• Markov Chains for Promotion Operators

This page was built for publication: Functions of random walks on hyperplane arrangements

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