Kac’s walk on rotation matrices mixes in n 2 log n n^{2}\log n steps
Natesh S. Pillai, Aaron Smith · 2026
Read Kac’s walk on rotation matrices mixes in n 2 log n n^{2}\log n steps by Natesh S. Pillai, Aaron Smith (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23828.txt.
Introduction
Pillai and Smith prove that Kac's walk on rotation matrices mixes in total variation in on the order of n squared log n steps, matching the conjectured time up to constants. The walk lacks conjugation invariance, blocking classical Fourier methods. Their proof uses a refined two-stage coupling. The second stage, a discrete analogue of Malliavin calculus for Markov chains, shows the chain's law is nearly Gaussian over the Lie algebra, its covariance well-conditioned.
Catalog record
| CREATOR | Natesh S. Pillai, Aaron Smith |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80062 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23828
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Kac’s walk on rotation matrices mixes in n 2 log n n^{2}\log n steps Natesh S. Pillai, Aaron Smith Abstract . Kac’s walk on SO ( n ) \mathrm{SO}(n) , introduced in [ 12 ] , is an important high-dimensional Markov chain with applications in statistical physics, statistics, cryptography, and computational sciences. 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 ) 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 our earlier work [ 42 ] , the first stage contracts two copies of the chain to a small neighborhood via a Wasserstein coupling defined and analyzed in [ 38 ] . 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 new general framework for studying mixing in high dimensional Markov chains in continuous state space with singular transition kernels. 2020 Mathematics Subject Classification Primary 60J10; Secondary 60J20 1. Introduction Introduced by Kac in the 1950s, Kac’s random walk on the sphere is one of the canonical stochastic models for the Boltzmann equation [ 23 , 34 ] . The analogous walk on the special orthogonal group \mathrm{SO}(n) was defined in the seminal paper introducing Markov chain Monte Carlo to statistics, where it was used as the most-developed sample algorithm [ 12 ] . Although the modern theory of mixing times had not been developed when [ 12 ] was written, the last sentence of that paper asks essentially the same question that we study in this paper: how dependent are widely-spaced samples from Kac’s walk, and how does this relate to computational efficiency? Since 1970, Kac-type dynamics have become a natural test case for a basic question that appears across probability, statistics, and computation: how rapidly can a high-dimensional constrained system be randomized using only local low-dimensional updates? The simplicity of the dynamics is an asset when using the walk as an algorithm: it makes both single-step computations (as in [ 12 ] ) and downstream applications (as in [ 44 , 22 , 46 ] ) faster. The same simplicity, however, makes the walk harder to analyze than superficially similar walks on the same group [ 14 , 39 , 43 ] . Kac-like dynamics have continued to be used in Bayesian statistics [ 3 ] , and are important in developing Gibbs samplers for distributions with hard constraints [ 38 , 42 ] and especially orthogonality constraints [ 19 ] . More recently, the same dynamics have been used as steps in other algorithms, including fast dimension reduction [ 1 , 22 ] , trapdoored pseudorandom matrices in cryptography [ 44 ] , parallel Kac-type constructions in quantum pseudorandomness [ 29 , 30 ] , other applications in machine learning [ 46 ] , and as a tool to prove stronger results in other areas of probability [ 37 ] . Let \mathrm{SO}(n) denote the group of n\times n rotation matrices and let N=\binom{n}{2} be the dimension of \mathrm{SO}(n) . Fix an ordering of the N coordinate pairs [n]_{\neq}=\{(a,b):1\leq a<b\leq n\}. For i\in\{1,\dots,N\} and \theta\in[0,2\pi) , let R(i,\theta) denote the rotation by angle \theta in the coordinate plane associated with the i^{\mathrm{th}} element of [n]_{\neq} . The chain \{X_{t}\}_{t\geq 0} evolves by (1.1) X_{t+1}=R(i_{t},\theta_{t})X_{t}, where i_{t} is uniform on \{1,\dots,N\} and \theta_{t} is uniform on [0,2\pi) . Thus each step acts in only one two-dimensional coordinate plane, while the stationary distribution is Haar measure on a manifold of dimension N . The closely-related walk on the sphere is obtained by taking the first column of X_{t} ; this is also a Markov chain. The total variation mixing time for Kac’s walk on \mathrm{SO}(n) has been a long standing open problem. The best bound to date, \tau_{\mathrm{mix}}=O(n^{4}\log n), was obtained in [ 42 , Theorem 1.1] . Combined with the \Omega(n^{2}) lower bound from [ 42 ] , this left a factor n^{2} gap in the main quantitative question for the chain. In this paper, we close this gap and prove an upper bound that is tight up to a factor of O(\log(n)) : Theorem 1 . The total-variation mixing time of Kac’s walk on \mathrm{SO}(n) satisfies \tau_{\mathrm{mix}}=O(n^{2}\log n). A nearly-matching lower bound of \Omega(n^{2}) can be obtained by dimension-counting: \mathrm{SO}(n) has dimension N , while each step is constrained to a union of 1-dimensional submanifolds. We conjecture that our upper bound of O(n^{2}\log(n)) is tight. 1.1. Our contribution and its connection to Malliavin calculus There is a large literature on bounding the mixing times of Markov chains in many contexts. The theory is best developed for chains on discrete spaces [ 27 ] , while in continuous state spaces the best available results are, as noted in [ 26 ] , “very far from being as nice as in the finite case”; see also the discussions in [ 6 , 28 , 7 ] . A key difficulty in continuous state spaces is the lack of a general mechanism for upgrading convergence in weaker metrics to total variation. In contrast, in discrete settings this upgrade typically follows from a spectral gap bound at logarithmic cost in the inverse of the smallest stationary probability. For Markov chains like Kac’s walk that make low-dimensional updates, it is well-known that knowledge of the highest eigenvalue “does not improve the mixing time” in general [ 40 ] . Previous work on these upgrades has either taken advantage of symmetries that apply to very narrow families of Markov chains [ 43 , 39 , 14 ] or has effectively sought a “warm start” (introduced in [ 31 ] ) via truncation or perturbation estimates [ 21 , 42 ] . The main difficulty in proving total-variation mixing for Kac’s walk is not the absence of contraction. Wasserstein contraction is already known at the conjectural time scale by Oliveira’s coupling [ 38 ] . The difficulty is that the transition kernel is singular. At each step the chain moves only along a one-dimensional family of rotations, while the state space \mathrm{SO}(n) has dimension N=\binom{n}{2} . Thus, for short and moderate times, the usual smoothing mechanisms available for Markov chains with everywhere positive transition densities are absent. One must instead understand how many singular, highly structured updates combine to create a distribution that is spread in all tangent directions, and one must do so quantitatively enough to compare nearby translates in total variation. This problem is closely analogous to