Open Access
2023 Ungarian Markov chains
Colin Defant, Rupert Li
Author Affiliations +
Electron. J. Probab. 28: 1-39 (2023). DOI: 10.1214/23-EJP1056

Abstract

We introduce the Ungarian Markov chain UL associated to a finite lattice L. The states of this Markov chain are the elements of L. When the chain is in a state xL, it transitions to the meet of {x}T, where T is a random subset of the set of elements covered by x. We focus on estimating E(L), the expected number of steps of UL needed to get from the top element of L to the bottom element of L. Using direct combinatorial arguments, we provide asymptotic estimates when L is the weak order on the symmetric group Sn and when L is the n-th Tamari lattice. When L is distributive, the Markov chain UL is equivalent to an instance of the well-studied random process known as last-passage percolation with geometric weights. One of our main results states that if L is a trim lattice, then E(L)E(spine(L)), where spine(L) is a specific distributive sublattice of L called the spine of L. Combining this lattice-theoretic theorem with known results about last-passage percolation yields a powerful method for proving upper bounds for E(L) when L is trim. We apply this method to obtain uniform asymptotic upper bounds for the expected number of steps in the Ungarian Markov chains of Cambrian lattices of classical types and the Ungarian Markov chains of ν-Tamari lattices.

Funding Statement

Colin Defant was supported by the National Science Foundation under Award No. 2201907 and by a Benjamin Peirce Fellowship at Harvard University.

Acknowledgments

We are grateful to Noga Alon, Dor Elboim, Dan Romik, and Nathan Williams for very helpful conversations. We thank the anonymous referee for reading our manuscript carefully and providing several useful comments.

Citation

Download Citation

Colin Defant. Rupert Li. "Ungarian Markov chains." Electron. J. Probab. 28 1 - 39, 2023. https://doi.org/10.1214/23-EJP1056

Information

Received: 26 January 2023; Accepted: 8 November 2023; Published: 2023
First available in Project Euclid: 5 December 2023

arXiv: 2301.08206
Digital Object Identifier: 10.1214/23-EJP1056

Subjects:
Primary: 05E16 , 06B05 , 06D75 , 60J10

Keywords: Cambrian lattice , Coxeter group , Markov chain , Tamari lattice , trim lattice , weak order

Vol.28 • 2023
Back to Top