Cutoff for Contingency Table and Torus Random Walks with Low Incremental Correlations
Zihao Fang & Andrew Heeszel
What the paper says
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$$ ( Z / q Z ) n . We present our method in the context of the Diaconis–Gangolli random walk on both the $$1 \times n$$ 1 × n and $$m \times n$$ m × n contingency tables over $$\mathbb {Z}/q\mathbb {Z}$$ Z / q Z . In the $$1 \times n$$ 1 × n case, we prove that the random walk exhibits cutoff at time $$\dfrac{n q^2 \log (n)}{8 \pi ^2}$$ n q 2 log ( n ) 8 π 2 when $$q \gg n$$ q ≫ n ; in the $$m \times n$$ m × n case, where m and n are of the same order, we establish cutoff for the random walk at time $$\dfrac{mn q^2 \log (mn)}{16 \pi ^2}$$ m n q 2 log ( m n ) 16 π 2 when $$q \gg n^2$$ q ≫ n 2 . Our method reveals that a general class of random walks on the torus $$(\mathbb {Z}/q\mathbb {Z})^n$$ ( Z / q Z ) n has cutoff. If each coordinate of the
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.50 × 0.4 = 0.20 |
| M · momentum | 0.50 × 0.15 = 0.07 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.