Research
On the Pseudo-Mixing of Kac's Walk
arXiv:2608.17374v1 Announce Type: cross Abstract: Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on SO(n): whether short trajectories are indistinguish
arXiv:2608.17374v1 Announce Type: cross Abstract: Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on SO(n): whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first k columns mix in Wasserstein distance in O(n(k+log n)log n) steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if T=omega(nk(k+log n)log n), then every degree-k polynomial normalized to have unit Haar variance has expectation under the T-step law within o(1) of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.
Related
- Beyond the d^{2.5}-mixing bound for Dikin walks on polytopes
- True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration
- Should the Boundary Term Be Learned in Reflected Diffusion? Conormal Trace and Reflection Masking
Source: arXiv cs.LG | 2026-08-19