Mixing of the upper triangular matrix walk

DOI10.1007/S00440-012-0436-1MaRDI QIDQ365712zbMATH OpenOpenAlexFDO

Authors Yuval Peres, Allan Sly

Publication date 9 September 2013

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

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

zbMATH Keywords

mixing timerandom walks on groups

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We study a natural random walk over the upper triangular matrices, with entries in the field $$, generated by steps which add row $i+1$ to row $i$. We show that the mixing time of the lazy random walk is $O(n^2)$ which is optimal up to constants. Our proof makes key use of the linear structure of the group and extends to walks on the upper triangular matrices over the fields $$ for $q$ prime.

Recommendations

• Random walk on upper triangular matrices mixes rapidly
• Two random walks on upper triangular matrices
• Random walks on the groups of upper triangular matrices
• The random walk on upper triangular matrices over \(\mathbb{Z} / m\mathbb{Z}\)
• scientific article; zbMATH DE number 1241392
• Random walks relative to multiple transition matrices
• Upcrossings of the random walk

Cites work

• A Chernoff Bound for Random Walks on Expander Graphs
• A note on various holding probabilities for random lazy random walks on finite groups
• A super-class walk on upper-triangular matrices
• An application of Harnack inequalities to random walk on nilpotent quotients
• Chernoff-type bound for finite Markov chains
• Generating a random permutation with random transpositions
• scientific article; zbMATH DE number 2070153 (Why is no real title available?)
• Kinetically constrained spin models
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing times are hitting times of large sets
• Moderate growth and random walk on finite groups
• Nash inequalities for finite Markov chains
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Random walk on upper triangular matrices mixes rapidly
• Random walks on the groups of upper triangular matrices
• The asymmetric one-dimensional constrained Ising model: Rigorous results
• Two random walks on upper triangular matrices

Cited in

(12)

• Random walk on upper triangular matrices mixes rapidly
• Super-character theory and comparison arguments for a random walk on the upper triangular matrices
• An exercise(?) in Fourier analysis on the Heisenberg group
• Mixing time of fractional random walk on finite fields
• Time scale separation and dynamic heterogeneity in the low temperature East model
• A random process related to a random walk on upper triangular matrices over a finite field
• Upper triangular matrix walk: cutoff for finitely many columns
• Mixing time and local exponential ergodicity of the east-like process in \(\mathbb{Z}^d\)
• The random walk on upper triangular matrices over \(\mathbb{Z} / m\mathbb{Z}\)
• The rank of a random triangular matrix over \(\mathbb{F}^q\)
• Mixing time of a matrix random walk generated by elementary transvections
• Relaxation to equilibrium of generalized east processes on \(\mathbb{Z}^{d}\): renormalization group analysis and energy-entropy competition

This page was built for publication: Mixing of the upper triangular matrix walk

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