#machine learning #cybersecurity Preprint

On the Pseudo-Mixing of Kac's Walk

N. Pillai Aaron Smith Vinod Vaikuntanathan

Aug 2026 · 3 citations · ⚡ 1 influential · 46 references

Mathematics Computer Science

Abstract

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=\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.

arXiv Semantic Scholar

View source

Similar papers

Preprint Jul 2026

Hitting time mixing for random $k$-cycles

In this paper, we study the random walk on the symmetric group $\mathfrak{S}_n$ generated by the conjugacy class of $k$-cycles, where $2\le k=o(n/(\log n)^4)$. We prove that the walk exhibits hitting-time mixing: at the first time when every card has been touched, the distribution is already close to equilibrium. For o...

Chen Shang, Jiahe Shen, Jiyue Zeng et al. · 1 citation

Jul 2026

On the Order-Conditional Optimality of Gaffke's Bound

Let $X = (X_1, \ldots, X_n)$ be a random vector from any Borel probability law on $\mathbb{R}_+^n$. We revisit the problem of deriving a lower confidence bound (LCB) on a scalar parameter of that law. We recast classical work, beginning with Buehler, in purely probabilistic terms to form a more accessible and extensibl...

G. Bissias, E. Learned-Miller · arXiv.org · 0 citations

Preprint Jul 2026

On a conjecture of Lamkin and Tkocz: Log-convexity of moments of Bernoulli sample means

Let $X_1,X_2,\ldots$ be independent $\mathrm{Bernoulli}(\theta)$ random variables, and let $\bar X_n = n^{-1}(X_1 + \cdots + X_n)$. We prove that, for every real $p \geq 1$, the sequence $\{\mathsf{E}(\bar X_n^p)\}_{n \geq 1}$ is log-convex. This proves the Bernoulli case of a conjecture of Lamkin and Tkocz [Canad. Mat...

Frédéric Ouimet · 1 citation

Preprint Jul 2026

Engel probability in wreath products of $p$-groups

We give upper and lower bounds for the number of solutions of the equation $e_n(x,y) = g$ in the group $W_k=(C_p\wr C_{p^k})^2$, where $e_n(x,y)$ is the $n$-th Engel word and $g\in W_k$. We obtain several corollaries from this. First, we prove a stronger version of the Amit-Ashurst conjecture for Engel words in $W_k$....

Iker Heras, Tommaso Toti, Matteo Vannacci · 0 citations

Preprint Aug 2026

A dynamical generalization of Chowla's conjecture on average

Let $k\ge1$ be an integer and let $\lambda$ be the Liouville function. In 1965, Chowla gave a conjecture that the values of $\lambda(n+h_1),\dots, \lambda(n+h_k)$ are asymptotically unrelated for any distinct natural numbers $h_1, \dots, h_k$. In this article, motivated by the recent work of Bergelson and Richter on th...

Biao Wang · 0 citations

Preprint Jul 2026

The local product condition implies cutoff

In the theory of mixing times, a famously wrong conjecture predicts that a sequence of Markov processes exhibits cutoff as soon as the product of their Poincar\'e constant and mixing time diverges. We prove that this statement becomes correct once the Poincar\'e constant $\gamma$ is replaced with its natural non-equili...

Francesco Pedrotti, Justin Salez · 0 citations