Kac's walk on rotation matrices mixes in $n^2 \log n$ steps
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913063295254528 |
|---|---|
| author | Pillai, Natesh S. Smith, Aaron |
| author_facet | Pillai, Natesh S. Smith, Aaron |
| contents | Kac's walk on the rotation group, introduced by Hastings in 1970, is an important high-dimensional Markov chain with applications in statistical physics, statistics, cryptography, and computational science. Despite its simple transition rules, determining its total-variation mixing time has remained a challenging problem for decades. A key obstacle is that the walk is not conjugation-invariant, placing it beyond the reach of classical Fourier-analytic techniques that apply to many related random walks on compact groups.
We prove that Kac's walk mixes in total variation in \(O(n^2 \log n)\) steps, matching the conjectured mixing time up to constants. The proof is based on a refined two-stage coupling. Building on earlier work, the first stage contracts two copies of the chain to a small neighborhood via a Wasserstein coupling.
Our main contribution is a new framework for analyzing the second-stage coupling. It can be viewed as a discrete analogue of Malliavin calculus for Markov chains. We represent the law of the chain as the pushforward of high-dimensional noise and prove quantitative non-degeneracy of the associated linearization using matrix martingale methods. This yields an approximately Gaussian distribution in the Lie algebra with well-conditioned covariance, allowing small group translations to be absorbed at negligible cost in total variation. Our approach provides a general framework for studying mixing in high-dimensional Markov chains in continuous state spaces with singular transition kernels. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23828 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Kac's walk on rotation matrices mixes in $n^2 \log n$ steps Pillai, Natesh S. Smith, Aaron Probability Statistics Theory Computation Kac's walk on the rotation group, introduced by Hastings in 1970, is an important high-dimensional Markov chain with applications in statistical physics, statistics, cryptography, and computational science. Despite its simple transition rules, determining its total-variation mixing time has remained a challenging problem for decades. A key obstacle is that the walk is not conjugation-invariant, placing it beyond the reach of classical Fourier-analytic techniques that apply to many related random walks on compact groups. We prove that Kac's walk mixes in total variation in \(O(n^2 \log n)\) steps, matching the conjectured mixing time up to constants. The proof is based on a refined two-stage coupling. Building on earlier work, the first stage contracts two copies of the chain to a small neighborhood via a Wasserstein coupling. Our main contribution is a new framework for analyzing the second-stage coupling. It can be viewed as a discrete analogue of Malliavin calculus for Markov chains. We represent the law of the chain as the pushforward of high-dimensional noise and prove quantitative non-degeneracy of the associated linearization using matrix martingale methods. This yields an approximately Gaussian distribution in the Lie algebra with well-conditioned covariance, allowing small group translations to be absorbed at negligible cost in total variation. Our approach provides a general framework for studying mixing in high-dimensional Markov chains in continuous state spaces with singular transition kernels. |
| title | Kac's walk on rotation matrices mixes in $n^2 \log n$ steps |
| topic | Probability Statistics Theory Computation |
| url | https://arxiv.org/abs/2604.23828 |