证明了Kac随机游走的伪混合性质，为快速降维提供理论支持。
On the Pseudo-Mixing of Kac's Walk
- 通过水波距离分析随机游走的混合速度
- 在O(n(k+log n)log n)步内完成前k列混合
- 适用于低复杂度测试，适合算法设计者
受Vaikuntanathan和Zamir猜想启发，我们研究了Kac在SO(n)上的伪混合问题：短轨迹是否对低复杂度测试不可区分。我们证明，对于固定精度，前k列在水波距离下于O(n(k+log n)log n)步内混合，解决了Oliveira的猜想。结合表示论方差界，若T=ω(nk(k+log n)log n)，则每个单位哈尔回方差的k次多项式，在T步分布下的期望与哈尔回期望相差o(1)。作为应用，该伪混合估计可用于证明一种快速约翰逊-林登斯特拉概率变换的有效性，其目标维度符合常规要求。
原文摘要 · Abstract (English)
Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on $\mathrm{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=ω(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。