Cutoff for Contingency Table and Torus Random Walks with Low Incremental Correlations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918384923312128 |
|---|---|
| author | Fang, Zihao Heeszel, Andrew |
| author_facet | Fang, Zihao Heeszel, Andrew |
| contents | We use the correlation matrix of the generating distribution to determine the mixing time for random walks on the torus $(\mathbb{Z}/q\mathbb{Z})^n$. We present our method in the context of the Diaconis-Gangolli random walk on both the $1 \times n$ and $m \times n$ contingency tables over $\mathbb{Z}/q\mathbb{Z}$. In the $1 \times n$ case, we prove that the random walk exhibits cutoff at time $\dfrac{n q^2 \log(n)}{8 π^2}$ when $q \gg n$; in the $m \times n$ case, where $m, n$ are of the same order, we establish cutoff for the random walk at time $\dfrac{mn q^2 \log(mn)}{16 π^2}$ when $q \gg n^2$. Our method reveals that a general class of random walks on the torus $(\mathbb{Z}/q\mathbb{Z})^n$ has cutoff. If each coordinate of the lifted random walk onto $\mathbb{Z}^n$ has variance $σ^2/n$ in each jump, and the between-coordinate correlations are sufficiently low, then cutoff occurs at time $\dfrac{nq^2 \log(n)}{4π^2 σ^2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16203 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cutoff for Contingency Table and Torus Random Walks with Low Incremental Correlations Fang, Zihao Heeszel, Andrew Probability 60J27, 60B15 We use the correlation matrix of the generating distribution to determine the mixing time for random walks on the torus $(\mathbb{Z}/q\mathbb{Z})^n$. We present our method in the context of the Diaconis-Gangolli random walk on both the $1 \times n$ and $m \times n$ contingency tables over $\mathbb{Z}/q\mathbb{Z}$. In the $1 \times n$ case, we prove that the random walk exhibits cutoff at time $\dfrac{n q^2 \log(n)}{8 π^2}$ when $q \gg n$; in the $m \times n$ case, where $m, n$ are of the same order, we establish cutoff for the random walk at time $\dfrac{mn q^2 \log(mn)}{16 π^2}$ when $q \gg n^2$. Our method reveals that a general class of random walks on the torus $(\mathbb{Z}/q\mathbb{Z})^n$ has cutoff. If each coordinate of the lifted random walk onto $\mathbb{Z}^n$ has variance $σ^2/n$ in each jump, and the between-coordinate correlations are sufficiently low, then cutoff occurs at time $\dfrac{nq^2 \log(n)}{4π^2 σ^2}$. |
| title | Cutoff for Contingency Table and Torus Random Walks with Low Incremental Correlations |
| topic | Probability 60J27, 60B15 |
| url | https://arxiv.org/abs/2407.16203 |