Tighter Bounds on the Expected Absorbing Time of Ungarian Markov Chains
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911162331824128 |
|---|---|
| author | Shen, Eric |
| author_facet | Shen, Eric |
| contents | In $2023$, Defant and Li defined the Ungarian Markov chain $\mathbf{U}_L$ associated to a finite lattice $L$. This Markov chain has state space $L$, and from any state $x \in L$ transitions to the meet of $\{x\} \cup T$, where $T$ is a randomly selected subset of the elements of $L$ covered by $x$. For any lattice $L$, let $\mathcal{E}(L)$ be the expected number of steps until the maximal element of $L$ transitions into the minimal element in the Ungarian Markov chain. We show that $\mathcal{E}(L)$ is linear in $n$ when $L$ is the weak order on the symmetric group $S_n$, and satisfies an $n^{1-o(1)}$ lower bound when $L$ is the $n^\text{th}$ Tamari lattice. This completely resolves a conjecture by Defant and Li and partially resolves another. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11728 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tighter Bounds on the Expected Absorbing Time of Ungarian Markov Chains Shen, Eric Combinatorics Probability 60J10, 05C05, 06B10, 06D75 In $2023$, Defant and Li defined the Ungarian Markov chain $\mathbf{U}_L$ associated to a finite lattice $L$. This Markov chain has state space $L$, and from any state $x \in L$ transitions to the meet of $\{x\} \cup T$, where $T$ is a randomly selected subset of the elements of $L$ covered by $x$. For any lattice $L$, let $\mathcal{E}(L)$ be the expected number of steps until the maximal element of $L$ transitions into the minimal element in the Ungarian Markov chain. We show that $\mathcal{E}(L)$ is linear in $n$ when $L$ is the weak order on the symmetric group $S_n$, and satisfies an $n^{1-o(1)}$ lower bound when $L$ is the $n^\text{th}$ Tamari lattice. This completely resolves a conjecture by Defant and Li and partially resolves another. |
| title | Tighter Bounds on the Expected Absorbing Time of Ungarian Markov Chains |
| topic | Combinatorics Probability 60J10, 05C05, 06B10, 06D75 |
| url | https://arxiv.org/abs/2405.11728 |