Aug 2026· 3 citations· ⚡ 1 influential· 46 references
MathematicsComputer 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.
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
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
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...
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$....
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...
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
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduOct 14, 2026
Learn how Google DeepMind and GovTech Singapore uses lightweight on-device Gemma models to intercept conversational scams in private chats with zero cloud data egress.
MIT News · Artificial Intelligence· news.mit.eduOct 13, 2026
Machine-learning networks can learn without detailed instructions from a designer. Those that do may offer insight into how the brain reorganizes itself during learning.
Microsoft Research Blog· microsoft.comOct 12, 2026
StudentSim is a research system for evaluating and improving AI tutoring tools before they are tested with learners. It models how individuals may engage with tutors, giving feedback to improve tutor performance across subjects like chess, writing, and mathematics. The post Simulating student learning for better AI tutoring appeared first on Microsoft Research.
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
