PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Pseudo-Mixing of Kac's Walk

Natesh S. Pillai, Aaron Smith, Vinod Vaikuntanathan

arXiv:2608.17374v1math.PRcs.CRcs.LG

TL;DR

The paper studies whether short Kac-walk trajectories can evade low-complexity tests designed to distinguish them from Haar-random orthogonal matrices. It develops Wasserstein mixing and representation-theoretic variance arguments, showing low-degree polynomials cannot distinguish sufficiently long trajectories and highlighting implications for natural MCMC functions.

  • Problem

    The paper addresses whether Kac’s walk becomes computationally indistinguishable from Haar measure after n·(log n)^O(1) steps, extending beyond its known relevance to Johnson–Lindenstrauss transforms.

  • Method

    The paper combines Wasserstein mixing analysis for the k-column walk with a representation-theoretic lower bound on polynomial variance.

  • Results

    O(n log(n)·max(k, log(n))) steps suffice for Wasserstein mixing of the k-column walk, while low-degree polynomials cannot distinguish Kac-walk samples from Haar measure after T≈n polylog(n) steps.

  • Takeaways & Limitations

    The results resolve conjectures concerning Kac-walk mixing and provide an example where ordinary mixing time is conservative for natural, important functions of a Markov chain.

  • Takeaways & Limitations

    The proof faces a limitation absent from the full-walk argument: the needed local contraction bound for the k-column walk does not seem straightforward, and computational distance lacks familiar Wasserstein properties such as single-step contraction.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies Kac’s walk through both conventional Wasserstein mixing and pseudo-mixing against low-degree polynomial tests. It proves rapid mixing for the k-column walk, establishes indistinguishability from Haar measure for low-degree polynomials, and applies this to fast Johnson–Lindenstrauss transforms.

  • Our First Result: O(n log(n)·max(k, log(n))) steps suffice for the k-column walk to mix uniformly in Wasserstein distance, resolving Oliveira’s conjecture.The result applies uniformly in k and n.
  • Our First Result: For k=n, the k-column chain becomes the usual Kac walk and its Wasserstein contraction estimate matches Oliveira’s result.
  • Our First Result: Ω(nk) steps are necessary for convergence, making the Wasserstein bound essentially optimal for every k and n.
  • Pseudo-Mixing and Our Main Result: Degree-k polynomials cannot distinguish Haar samples from matrices produced by T≈n polylog(n) Kac steps, resolving an open problem of Vaikuntanathan and Zamir.
  • Mathematical Techniques: The representation-theoretic variance bounds used for the polynomial result may also interest researchers studying computational hardness against low-degree polynomials.
  • Applications: The pseudo-mixing result supports a fast Johnson–Lindenstrauss transform at the usual target dimension, using Kac-generated matrices with fast multiplication.The paper presents this as a theorem-inspired application of the low-degree analysis.

2 Technical Overview

The paper formalizes pseudo-mixing as indistinguishability from Haar measure by low-degree polynomial tests and sketches a proof combining column-wise Wasserstein mixing with variance bounds. This yields weak indistinguishability after the stated time scale and supports a fast Johnson–Lindenstrauss application.

  • Definitions: Pseudo-mixing compares distributions through low-degree polynomial tests rather than traditional mixing metrics.The paper defines computational distance using bounded-degree polynomials and distinguishes weak indistinguishability through sequences of such tests.
  • Main strategy: Theorem 1 establishes Wasserstein contraction for the k-column walk from every pair of starting points.The corresponding estimate also covers the full Kac walk when k=n through Oliveira’s prior result.
  • Variance and application: Theorem 2 gives weak degree-k indistinguishability when T=ω(nk(k+log n)log n).The proof combines the expectation-difference upper bound with the variance lower bound.
  • Main strategy: A degree-k monomial depends on at most k columns, reducing polynomial expectation control to Wasserstein mixing of the k-column walk.The proof separately bounds expectation differences and Haar variance for low-degree polynomials.
  • Proof sketch: Uniform contraction fails because the local rate depends on row norms, ranging from nearly zero to order n^-2 across nearby points.Typical Haar-like points instead have contraction of order 1/[n(k+log n)], motivating burn-in and high-contraction-region arguments.
  • Proof sketch: The coupling is locally contracting and globally non-expansive, while burn-in shows chains typically enter regions with row norms of order k+log n.A local-to-global path-coupling argument then yields multi-step contraction.
  • Variance and application: The representation-theoretic variance argument projects away zero-variance polynomials before applying exact calculations on SO(n).This is necessary because distinct nontrivial entry polynomials can have zero Haar variance.
  • Variance and application: The same low-degree moment strategy is applied to the fast Johnson–Lindenstrauss transform.The argument replaces exponential-moment bounds in the elementary JL proof with low-degree polynomial moment bounds.

3 Contraction in Columns of Kac’s Walk

This section proves global Wasserstein contraction for the k-column walk by combining an optimized local coupling, burn-in control of row norms, and a local-to-global path-coupling argument.

  • Global contraction: The resulting theorem provides a global multi-step Wasserstein contraction bound for every 1≤k<n.The full case k=n is identified with the usual Kac walk and is covered by prior work.
  • Setup: The k-column walk is the Markov chain formed by tracking the first k columns of Kac’s walk on SO(n).Its state space is the Stiefel manifold St(n,k), equipped with a Riemannian metric.
  • Local contraction: The local coupling optimizes the rotation-angle shift for the two selected rows, maximizing their overlap while preserving valid one-step marginals.The shifted angle remains uniform conditionally, so the construction is a legitimate coupling.
  • Local contraction: The coupling gives a local Frobenius-norm contraction for nearby states and is also deterministically non-expansive.The construction is analyzed through the two updated rows and an angle chosen from the current pair of states.
  • Burn-in and averaging: Worst-case local contraction can be only 1−Θ(n^-2), so the proof uses burn-in to reach typical high-contraction regions.After order n log n steps, the relevant row-norm quantity is typically of order k+log n.
  • Global contraction: After an epoch of order n log n steps, the Wasserstein distance contracts by a factor governed by the local estimate.The argument combines high-contraction behavior with non-expansion outside those regions.
  • Global contraction: A standard local-to-global lemma on the compact geodesic Stiefel manifold extends local contraction to arbitrary starting points.This path-coupling step is applied after establishing the epoch contraction.

4 Bounds on Moments of Polynomials

The section bounds moments of low-degree polynomials under Kac’s walk and Haar measure by controlling entrywise differences through Wasserstein distance and handling polynomial degeneracies via reduction and representation theory.

  • Combining bounds: The moment analysis combines Wasserstein mixing bounds with coefficient-norm control and Haar variance estimates.A telescoping-sum argument connects the polynomial representation to the expectation difference.
  • Expectation differences: Theorem 4.1 bounds the expectation difference for a polynomial function of SO(n) under the T-step Kac law and Haar measure.The bound applies to functions depending on a restricted set of matrix entries specified in the theorem.
  • Expectation differences: Wasserstein control of the first k columns yields entrywise control, which bounds polynomial expectation differences.The proof uses the norm relation between entrywise supnorm and the Riemannian distance, together with boundedness of the test function.
  • Variance bounds: The representation-theoretic variance bound applies to reduced degree-k polynomials with zero Haar mean.Reduction removes components that vanish in variance on the orthogonal group.
  • Variance bounds: The polynomial reduction f* is required because distinct ambient polynomials can agree on SO(n).For example, the sum of squared matrix entries equals the constant n on SO(n) and therefore has zero Haar variance.

5 Proof of Our Main Theorem (Theorem 2)

The proof of Theorem 2 combines the k-column mixing estimate with coefficient and variance bounds to show that low-degree polynomial tests cannot distinguish Kac’s walk from Haar measure at the stated time scale.

  • Main theorem: Theorem 2 states weak degree-k indistinguishability when T=ω(nk(k+log n)log n).The conclusion holds for the T-step law of Kac’s walk from any starting point versus Haar measure.
  • Conclusion: The resulting expectation difference tends to zero for the normalized low-degree tests covered by the theorem.This is the final comparison between the Kac-walk law and Haar measure.
  • Polynomial reduction: Reducing a polynomial to f* preserves its values on SO(n), allowing normalization through the reduced representation.The proof assumes the reduced polynomial has a convenient coefficient norm without changing the tested function on the group.
  • Decay estimate: The coefficient comparison contributes a polynomial prefactor, while repeated contraction contributes a factor n^-r.Their combination tends to zero superpolynomially fast under the theorem’s time condition.

6 An Application to a Fast Johnson-Lindenstrauss Transform

The section applies Kac’s-walk estimates to construct a Johnson–Lindenstrauss transform with the usual target dimension and substantially faster matrix-vector multiplication than dense projection.

  • The Kac-walk matrix yields a Johnson–Lindenstrauss transform at the usual target dimension when the walk is run long enough to control low moments.The result confirms the Johnson–Lindenstrauss conjecture from, up to an extra logarithmic factor in running time.
  • Controlling |Z_v(G)| for every v in the pair-difference set is exactly the Johnson–Lindenstrauss condition for the point set.
  • T≥C_A n log^3 n achieves target dimension ℓ=O_A(ε^-2 log n) for fixed ε and N/δ≤n^A.
  • O(T+ℓ) arithmetic cost per vector is achieved by applying the T elementary rotations successively and then projecting to the first ℓ coordinates.In the polynomial-size regime, this is ~O(n), compared with O(nℓ) for a dense ℓ×n projection matrix.

7 Open Questions

The section identifies open questions about strengthening mixing and indistinguishability results, extending the framework to spectral tests, and generalizing trapdoored constructions beyond matrices.

  • Immediate Open Questions: Extending k-column mixing from Wasserstein distance to total variation remains an open problem that appears plausible to the authors.
  • Immediate Open Questions: The polynomial indistinguishability theorem becomes uninteresting near k≈√n, raising the question of whether it can extend to k≈n.
  • Immediate Open Questions: Indistinguishability against degree-k polynomials currently requires roughly nk^2 walk steps, and whether this dependence is necessary is unresolved.
  • Immediate Open Questions: It remains open whether low-degree polynomials of a Kac matrix’s spectrum can distinguish it, because the spectrum is not itself a Markov chain.
  • Trapdoored Functions: Beyond matrices, the authors ask whether other function classes permit automatically hiding fast circuits inside larger classes of mostly slow circuits.They specifically ask whether such classes exist with complexity worse than n^2.

A.3 Metric comparisons

This appendix develops geometric and probabilistic tools for comparing metrics on the Stiefel manifold and controlling the Kac walk’s coupling behavior.

  • A.3 Metric comparisons: The Riemannian distance on St(n,k) is compared with the ambient Frobenius distance through a path constructed by polar normalization.The construction uses a positive-definite Gram-matrix interpolation between two Stiefel points.
  • A.3 Metric comparisons: For sufficiently close X and Y, universal constants ρ_D and C_D provide a local comparison between the two distances.
  • A.3 Metric comparisons: The polar-normalized path stays on St(n,k), begins at X, ends at Y, and can be analyzed because its Gram matrices commute with their derivatives.
  • A.3 Metric comparisons: The coupled Kac update is chosen to minimize the post-update Frobenius distance over angle shifts in the selected coordinate plane.

C.3 Contraction Over Epochs

The contraction-over-epochs argument combines burn-in, deterministic non-expansion, and local contraction to obtain Wasserstein contraction for the k-column walk.

  • C.3 Contraction Over Epochs: Each epoch consists of a burn-in period followed by a contraction period whose lengths are collected in the epoch definition.
  • C.3 Contraction Over Epochs: A local coupling contracts nearby k-column-walk states over an epoch while preserving the required local-distance regime.Lemma C.4 applies when the initial Stiefel distance is at most the universal radius ρ_loc.
  • C.3 Contraction Over Epochs: The burn-in portion is deterministically non-expanding, allowing the conditional contraction estimate to be applied to the shifted process.
  • C.3 Contraction Over Epochs: T_epoch≤C n(k+log n) log n after increasing the universal constant, while the epoch failure probability is o(n^-10).The contraction period is O(n(k+log n) log n), and the burn-in plus contraction decomposition yields the stated epoch bound.

D Representation-Theoretic Variance Bounds for Haar Polynomials

The appendix develops compact-group representation-theoretic tools for bounding variances of polynomial observables, then applies them to Kac’s walk on SO(n).

  • Representation decomposition: The proof decomposes representations into isotypic components using canonical decomposition and analyzes the resulting operator blocks.The argument uses Schur’s lemma, partial traces, and Hilbert–Schmidt orthogonality to characterize the centered component.
  • General variance inequality: Theorem D.3 establishes a compact-group variance inequality for finite-dimensional real orthogonal representations.The result is presented as a general theorem for compact Lie groups with Haar probability measure.
  • Centered subspace: The centered subspace consists of operators whose nontrivial diagonal blocks lie in ker L_λ, together with arbitrary off-diagonal and trivial-isotypic diagonal components.This block characterization identifies exactly which operator components contribute to variance.

D.1 Equality cases and the Peter–Weyl–Plancherel picture

The appendix characterizes sharpness through representation multiplicities and connects the finite-dimensional variance argument to Peter–Weyl–Plancherel harmonic analysis.

  • Equality cases: The proof yields exact identities beyond the universal lower bound, with equality governed by multiplicity ratios m_λ/d_λ.The sharp constant and equality conditions are stated after Equation (D.8).
  • Equality cases: The universal estimate follows from the crude bounds m_λ≥1 and d_λ≤dim U, and this constant is sharp for irreducible nontrivial representations.The irreducible case realizes the stated extremal pattern.
  • Peter–Weyl–Plancherel picture: The finite-dimensional identities correspond to operator-valued Fourier coefficients and Plancherel weights in the Peter–Weyl decomposition.The ratio m_λ/d_λ measures how closely the representation resembles the regular representation.
  • Peter–Weyl–Plancherel picture: When m_λ=d_λ for all relevant λ, the comparison becomes termwise identical to the Plancherel identity.This is the multiplicity pattern of the regular representation.
  • Polynomial observables: For the tensor-power representation, homogeneous and inhomogeneous polynomial observables are represented through Frobenius-orthogonal projections onto the centered complement.The inhomogeneous construction uses a graded representation to combine degrees.

E Proof of Theorem 6.1

The proof transfers moderate-degree Haar moment bounds to pseudo-Haar distributions, showing that pseudo-mixing suffices for the usual Johnson–Lindenstrauss estimate.

  • Pseudo-Haar reduction: Pseudo-Haar in supnorm means matching Haar expectations for every bounded polynomial of degree at most d_ph.The definition constrains both polynomial degree and supnorm.
  • Johnson–Lindenstrauss transfer: Theorem E.1 states that an SO(n)-valued random matrix with this pseudo-Haar property yields the usual Johnson–Lindenstrauss guarantee.The theorem applies to any N-point subset of R^n with accuracy ε and failure probability δ.
  • Moment transfer: The proof uses moderate-degree polynomial moments rather than exponential moments, together with a standard Haar moment estimate.For a Haar matrix, the projected squared norm has a beta distribution and satisfies a spherical-cap concentration bound.
  • Moment transfer: The moment-transfer proposition converts uniform polynomial-moment control into the required embedding estimate after a union bound over the finite point set.The argument normalizes degree-4r polynomials and splits the error probability into two terms.
  • Parameter regime: For N/δ≤n^A and fixed ε, the parameter choices reduce to ℓ=O_A(ε^-2 log n) and T≥C_A n log^3 n.These conditions follow after reducing r to O_A(log n).
Loading 2608.17374v1…