Kac's walk on rotation matrices mixes in $n^2 \log n$ steps

arxiv: 2604.23828 · v1 · submitted 2026-04-26 · 🧮 math.PR · math.ST· stat.CO· stat.TH

Kac's walk on rotation matrices mixes in n² log n steps

Natesh S. Pillai , Aaron Smith This is my paper

Pith reviewed 2026-05-08 05:25 UTC · model grok-4.3

classification 🧮 math.PR math.STstat.COstat.TH

keywords Kac's walkrotation groupmixing timetotal variation distanceMarkov chain couplinghigh-dimensional chainsmatrix martingalesLie algebra linearization

0 comments p. Extension

The pith

Kac's walk on the rotation group mixes in total variation distance after O(n² log n) steps.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that Kac's random walk on n by n rotation matrices reaches equilibrium in total variation after O(n² log n) steps, matching the decades-old conjecture up to constant factors. This bound is proved by splitting the coupling into two stages. The first stage uses a Wasserstein contraction to bring two independent copies of the chain into a small neighborhood of each other. The second stage introduces a new analytic framework that treats the chain's law as the pushforward of high-dimensional noise and shows the associated linearization is non-degenerate enough for small group translations to be absorbed with negligible extra cost.

Core claim

We prove that Kac's walk mixes in total variation in O(n² log n) steps, matching the conjectured mixing time up to constants. The proof is based on a refined two-stage coupling. Building on earlier work, the first stage contracts two copies of the chain to a small neighborhood via a Wasserstein coupling. Our main contribution is a new framework for analyzing the second-stage coupling. It can be viewed as a discrete analogue of Malliavin calculus for Markov chains. We represent the law of the chain as the pushforward of high-dimensional noise and prove quantitative non-degeneracy of the associated linearization using matrix martingale methods. This yields an approximately Gaussian law in the

What carries the argument

Two-stage coupling in which the second stage establishes quantitative non-degeneracy of the linearization of the chain's law via matrix martingale methods, allowing small translations to be absorbed at negligible total-variation cost.

If this is right

The total-variation mixing time is at most C n² log n for an absolute constant C.
The same two-stage method yields a general framework for high-dimensional Markov chains whose transition kernels are singular.
Matrix-martingale control of the linearized pushforward map applies to other walks whose increments generate the Lie algebra.
Once two chains are close in the Lie algebra, the remaining coupling time is negligible compared with the initial contraction time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The technique may adapt to random walks on other compact Lie groups whose increments are not conjugation-invariant.
The non-degeneracy argument could be used to prove cutoff or to obtain explicit constants in related statistical-physics models.
Implementation of the second-stage coupling as a practical sampler might improve mixing in high-dimensional rotation sampling tasks.

Load-bearing premise

The linearization of the chain's law remains quantitatively non-degenerate so that small group translations can be absorbed at negligible total-variation cost.

What would settle it

Numerical simulation of the walk for n around 20 that measures total variation distance to stationarity after c n² log n steps for various constants c and checks whether the distance falls below 0.1 when c is sufficiently large.

read the original abstract

Kac's walk on the rotation group, introduced by Hastings in 1970, is an important high-dimensional Markov chain with applications in statistical physics, statistics, cryptography, and computational science. Despite its simple transition rules, determining its total-variation mixing time has remained a challenging problem for decades. A key obstacle is that the walk is not conjugation-invariant, placing it beyond the reach of classical Fourier-analytic techniques that apply to many related random walks on compact groups. We prove that Kac's walk mixes in total variation in $O(n^2 \log n)$ steps, matching the conjectured mixing time up to constants. The proof is based on a refined two-stage coupling. Building on earlier work, the first stage contracts two copies of the chain to a small neighborhood via a Wasserstein coupling. Our main contribution is a new framework for analyzing the second-stage coupling. It can be viewed as a discrete analogue of Malliavin calculus for Markov chains. We represent the law of the chain as the pushforward of high-dimensional noise and prove quantitative non-degeneracy of the associated linearization using matrix martingale methods. This yields an approximately Gaussian distribution in the Lie algebra with well-conditioned covariance, allowing small group translations to be absorbed at negligible cost in total variation. Our approach provides a general framework for studying mixing in high-dimensional Markov chains in continuous state spaces with singular transition kernels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They prove the O(n² log n) mixing time for Kac's walk using a two-stage coupling with matrix martingales for the fine scale.

read the letter

The main thing to know is that this paper gives the first proof that Kac's walk on the rotation group mixes in total variation in O(n² log n) steps, matching the old conjecture. They do it with a two-stage coupling: the first stage contracts in Wasserstein distance down to a small neighborhood, and the second stage absorbs the remaining small translations by writing the law as a pushforward of noise and showing the linearization is non-degenerate enough. The non-degeneracy comes from matrix martingale bounds that produce an approximately Gaussian measure on the Lie algebra with controlled covariance, so the translations cost little in total variation. They present this as a discrete analogue of Malliavin calculus, which lets them handle the singular kernel where Fourier methods do not apply directly. This is the real contribution. It resolves a long-open question and supplies a new analytic tool that could extend to other high-dimensional chains with similar structure. The authors are careful to build on existing Wasserstein work rather than starting from scratch. The soft spots are minor but worth checking. The quantitative martingale estimates and error terms in the second stage carry the proof, and one would want to see that the constants and approximation errors really deliver the claimed rate without extra log factors. The abstract outlines the strategy cleanly and there are no visible circularities or unsupported leaps, but the details matter here. This paper is for people working on mixing times for Markov chains on groups or in high dimensions with continuous states. Anyone interested in coupling methods or martingale techniques for non-smooth kernels will find it useful. It deserves a serious referee because the result is substantial and the framework looks reusable.

Referee Report

0 major / 2 minor

Summary. The paper proves that Kac's walk on the rotation group SO(n) mixes in total variation in O(n² log n) steps, matching the long-standing conjecture up to constants. The argument proceeds via a two-stage coupling: the first stage contracts two copies of the chain to a small neighborhood using a Wasserstein coupling, while the second stage represents the law as a pushforward of high-dimensional noise and establishes quantitative non-degeneracy of the linearization via matrix-martingale bounds, yielding an approximately Gaussian measure on the Lie algebra with well-conditioned covariance that absorbs small translations at negligible total-variation cost.

Significance. If the central claim holds, the result resolves a decades-old open problem on the mixing time of Kac's walk, a Markov chain with broad applications in statistical physics, statistics, cryptography, and computational science. The new framework, described as a discrete analogue of Malliavin calculus for Markov chains, supplies a general method for analyzing mixing times of high-dimensional chains on continuous state spaces with singular transition kernels; the use of matrix martingales to obtain explicit non-degeneracy and covariance control is a technical strength that could extend to other Lie-group walks.

minor comments (2)

The abstract refers to 'rotation matrices' in the title but 'rotation group' in the text; a brief clarification of the precise state space (SO(n) versus O(n)) would avoid minor ambiguity for readers.
The description of the second-stage coupling invokes 'quantitative non-degeneracy' and 'well-conditioned covariance' without an explicit statement of the conditioning constant or its dependence on n; adding a one-sentence summary of the bound obtained from the matrix-martingale argument would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. We are pleased that the two-stage coupling argument and the discrete Malliavin-calculus framework were viewed as a technical contribution.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper presents a direct mathematical proof via a two-stage coupling: Wasserstein contraction to a small neighborhood followed by a pushforward representation of the law whose linearization is shown non-degenerate by matrix-martingale bounds yielding an approximately Gaussian measure on the Lie algebra. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the O(n² log n) bound is obtained from these independent estimates. The argument is self-contained against external benchmarks and does not invoke uniqueness theorems or ansatzes from prior author work in a circular manner.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard facts about the special orthogonal group, total variation, and Wasserstein couplings (building on earlier work) plus the new non-degeneracy statement for the linearization; no free parameters or invented entities appear in the abstract.

axioms (2)

standard math Standard properties of the special orthogonal group SO(n) and total-variation distance on compact groups.
Invoked as background for the mixing-time definition and the group structure.
domain assumption Existence of a Wasserstein coupling that contracts two copies of the chain to a small neighborhood in the first stage.
Explicitly stated as building on earlier work.

pith-pipeline@v0.9.0 · 5558 in / 1358 out tokens · 77063 ms · 2026-05-08T05:25:26.696226+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

46 extracted references · 1 canonical work pages

[1]

Approximate nearest neighbors and the fast Johnson--Lindenstrauss transform

Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast Johnson--Lindenstrauss transform. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing , pages 557--563. ACM, 2006

2006
[2]

David J. Aldous. Random walks on finite groups and rapidly mixing M arkov chains. S \'e minaire de probabilit \'e s de Strasbourg , 17:243--297, 1983

1983
[3]

Moment conditions and bayesian non-parametrics

Luke Bornn, Neil Shephard, and Reza Solgi. Moment conditions and bayesian non-parametrics. Journal of the Royal Statistical Society Series B: Statistical Methodology , 81(1):5--43, 2019

2019
[4]

On the spectral gap of the Kac walk and other binary collision processes

Pietro Caputo. On the spectral gap of the Kac walk and other binary collision processes. ALEA. Latin American Journal of Probability and Mathematical Statistics , 4:205--222, 2008

2008
[5]

Carlen, Maria C

Eric A. Carlen, Maria C. Carvalho, and Michael Loss. Determination of the spectral gap for Kac 's master equation and related stochastic evolution. Acta Mathematica , 191(1):1--54, 2003

2003
[6]

Mixing time of the adjacent walk on the simplex

Pietro Caputo, Cyril Labb \'e , and Hubert Lacoin. Mixing time of the adjacent walk on the simplex. The Annals of Probability , 48(5):2449--2493, 2020

2020
[7]

Spectral gap and cutoff phenomenon for the gibbs sampler of interfaces with convex potential

Pietro Caputo, Cyril Labb \'e , and Hubert Lacoin. Spectral gap and cutoff phenomenon for the gibbs sampler of interfaces with convex potential. Annales de l'Institut Henri Poincar \'e Probabilit \'e s et Statistiques , 58(2):794--826, 2022

2022
[8]

The cutoff phenomenon in finite M arkov chains

P Diaconis. The cutoff phenomenon in finite M arkov chains. Proceedings of the National Academy of Sciences , 93(4):1659--1664, 1996

1996
[9]

Generating a random permutation with random transpositions

Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Zeitschrift f \"u r Wahrscheinlichkeitstheorie und Verwandte Gebiete , 57(2):159--179, 1981

1981
[10]

Bounds for Kac 's master equation

Persi Diaconis and Laurent Saloff-Coste. Bounds for Kac 's master equation. Communications in Mathematical Physics , 209(3):729--755, 2000

2000
[11]

On malliavin's proof of h \"o rmander's theorem

Martin Hairer. On malliavin's proof of h \"o rmander's theorem. Bulletin des Sciences Math \'e matiques , 135(6--7):650--666, 2011

2011
[12]

W. K. Hastings. Monte C arlo sampling methods using M arkov chains and their applications. Biometrika , 57(1):97--109, 1970

1970
[13]

Nicholas J. Higham. Functions of Matrices: Theory and Computation . Society for Industrial and Applied Mathematics, Philadelphia, PA, 2008

2008
[14]

Cut-off phenomenon in the uniform plane Kac walk

Bob Hough and Yunjiang Jiang. Cut-off phenomenon in the uniform plane Kac walk. The Annals of Probability , 45(4):2248--2308, 2017

2017
[15]

Mattingly

Martin Hairer and Jonathan C. Mattingly. Ergodicity of the 2d navier--stokes equations with degenerate stochastic forcing. Annals of Mathematics , 164(3):993--1032, 2006

2006
[16]

Hypoelliptic second order differential equations

Lars H \"o rmander. Hypoelliptic second order differential equations. Acta Mathematica , 119:147--171, 1967

1967
[17]

Spectral gap for Kac 's model of Boltzmann equation

\'E lise Janvresse. Spectral gap for Kac 's model of Boltzmann equation. The Annals of Probability , 29(1):288--304, 2001

2001
[18]

Bounds on semigroups of random rotations on SO(n)

\'E lise Janvresse. Bounds on semigroups of random rotations on SO(n) . Theory of Probability & Its Applications , 47(3):526--532, 2003

2003
[19]

Hoff, and David B

Michael Jauch, Peter D. Hoff, and David B. Dunson. Random orthogonal matrices and the Cayley transform . Bernoulli , 26(2):1560 -- 1586, 2020

2020
[20]

Total variation bound for K ac's random walk

Yunjiang Jiang. Total variation bound for K ac's random walk. The Annals of Applied Probability , 22(6):2242--2262, 2012

2012
[21]

Kac 's random walk on the special orthogonal group mixes in polynomial time

Yunjiang Jiang. Kac 's random walk on the special orthogonal group mixes in polynomial time. Proceedings of the American Mathematical Society , 145(10):4533--4541, 2017

2017
[22]

Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith

Vishesh Jain, Natesh S. Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith. Fast and memory-optimal dimension reduction using Kac 's walk. The Annals of Applied Probability , 32(5):4038--4064, 2022

2022
[23]

Foundations of kinetic theory

Mark Kac. Foundations of kinetic theory. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume III: Contributions to Astronomy and Physics , pages 171--197. University of California Press, 1956

1956
[24]

Shigeo Kusuoka and Daniel W. Stroock. Applications of the malliavin calculus, part i. In Stochastic Analysis , volume 32 of North-Holland Mathematical Library , pages 271--306. North-Holland, 1984

1984
[25]

Shigeo Kusuoka and Daniel W. Stroock. Applications of the malliavin calculus, part ii. Journal of the Faculty of Science, University of Tokyo, Section IA, Mathematics , 32(1):1--76, 1985

1985
[26]

Mixing time and cutoff for one-dimensional particle systems

Hubert Lacoin. Mixing time and cutoff for one-dimensional particle systems. arXiv preprint arXiv:2111.06436 , 2021

work page arXiv 2021
[27]

Markov chains and mixing times , volume 107

David A Levin and Yuval Peres. Markov chains and mixing times , volume 107. American Mathematical Soc., 2017

2017
[28]

Hydrodynamic limit and cutoff for the biased adjacent walk on the simplex

Cyril Labb \'e and Engu \'e rand Petit. Hydrodynamic limit and cutoff for the biased adjacent walk on the simplex. Annales de l'Institut Henri Poincar \'e Probabilit \'e s et Statistiques , 61(2):769--802, 2025

2025
[29]

Quantum pseudorandom scramblers

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. In Theory of Cryptography: 22nd International Conference, TCC 2024, Milan, Italy, December 2–6, 2024, Proceedings, Part II , page 3–35, Berlin, Heidelberg, 2024. Springer-Verlag

2024
[30]

Parallel kac's walk generates pru

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Parallel kac's walk generates pru. 2025

2025
[31]

Random walks in a convex body and an improved volume algorithm

L \'a szl \'o Lov \'a sz and Mikl \'o s Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms , 4(4):359--412, 1993

1993
[32]

Stochastic calculus of variations and hypoelliptic operators

Paul Malliavin. Stochastic calculus of variations and hypoelliptic operators. In Proceedings of the International Symposium on Stochastic Differential Equations , pages 195--263. Wiley, 1978

1978
[33]

David K. Maslen. The eigenvalues of Kac 's master equation. Mathematische Zeitschrift , 243(2):291--331, 2003

2003
[34]

Kac's program in kinetic theory

St \'e phane Mischler and Cl \'e ment Mouhot. Kac's program in kinetic theory. Inventiones mathematicae , 193(1):1--147, 2013

2013
[35]

James R. Norris. Simplified malliavin calculus. S \'e minaire de Probabilit \'e s XX , 1204:101--130, 1986

1986
[36]

The Malliavin Calculus and Related Topics

David Nualart. The Malliavin Calculus and Related Topics . Springer, 2 edition, 2006

2006
[37]

A method to derive concentration of measure bounds on M arkov chains

Stephen Ng and Meg Walters. A method to derive concentration of measure bounds on M arkov chains. Electronic Communications in Probability , 20:1--13, 2015

2015
[38]

On the convergence to equilibrium of Kac 's random walk on matrices

Roberto Imbuzeiro Oliveira. On the convergence to equilibrium of Kac 's random walk on matrices. The Annals of Applied Probability , 19(3):1200--1231, 2009

2009
[39]

The cut-off phenomenon for random reflections

Ursula Porod. The cut-off phenomenon for random reflections. The Annals of Probability , 24(1):74--96, 1996

1996
[40]

Convergence of Kac 's random walk, 2007

Igor Pak and Sergiy Sidenko. Convergence of Kac 's random walk, 2007. Preprint

2007
[41]

Pillai and Aaron Smith

Natesh S. Pillai and Aaron Smith. Kac's walk on n-sphere mixes in n log n steps. The Annals of Applied Probability , 27(1):631--650, 2017

2017
[42]

Pillai and Aaron Smith

Natesh S. Pillai and Aaron Smith. On the mixing time of Kac 's walk and other high-dimensional Gibbs samplers with constraints. The Annals of Probability , 46(4):2345--2399, 2018

2018
[43]

Rosenthal

Jeffrey S. Rosenthal. Random rotations: Characters and random walks on SO(N) . The Annals of Probability , 22(1):398--423, 1994

1994
[44]

Authentication protocol using trapdoored matrices

Aikaterini Sotiraki. Authentication protocol using trapdoored matrices. Master's thesis, Massachusetts Institute of Technology, 2016. EECS

2016
[45]

Joel A. Tropp. Freedman 's inequality for matrix martingales. Electronic Communications in Probability , 16:262--270, 2011

2011
[46]

Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications , pages 2554--2574

Vinod Vaikuntanathan and Or Zamir. Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications , pages 2554--2574. 2026

2026

[1] [1]

Approximate nearest neighbors and the fast Johnson--Lindenstrauss transform

Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast Johnson--Lindenstrauss transform. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing , pages 557--563. ACM, 2006

2006

[2] [2]

David J. Aldous. Random walks on finite groups and rapidly mixing M arkov chains. S \'e minaire de probabilit \'e s de Strasbourg , 17:243--297, 1983

1983

[3] [3]

Moment conditions and bayesian non-parametrics

Luke Bornn, Neil Shephard, and Reza Solgi. Moment conditions and bayesian non-parametrics. Journal of the Royal Statistical Society Series B: Statistical Methodology , 81(1):5--43, 2019

2019

[4] [4]

On the spectral gap of the Kac walk and other binary collision processes

Pietro Caputo. On the spectral gap of the Kac walk and other binary collision processes. ALEA. Latin American Journal of Probability and Mathematical Statistics , 4:205--222, 2008

2008

[5] [5]

Carlen, Maria C

Eric A. Carlen, Maria C. Carvalho, and Michael Loss. Determination of the spectral gap for Kac 's master equation and related stochastic evolution. Acta Mathematica , 191(1):1--54, 2003

2003

[6] [6]

Mixing time of the adjacent walk on the simplex

Pietro Caputo, Cyril Labb \'e , and Hubert Lacoin. Mixing time of the adjacent walk on the simplex. The Annals of Probability , 48(5):2449--2493, 2020

2020

[7] [7]

Spectral gap and cutoff phenomenon for the gibbs sampler of interfaces with convex potential

Pietro Caputo, Cyril Labb \'e , and Hubert Lacoin. Spectral gap and cutoff phenomenon for the gibbs sampler of interfaces with convex potential. Annales de l'Institut Henri Poincar \'e Probabilit \'e s et Statistiques , 58(2):794--826, 2022

2022

[8] [8]

The cutoff phenomenon in finite M arkov chains

P Diaconis. The cutoff phenomenon in finite M arkov chains. Proceedings of the National Academy of Sciences , 93(4):1659--1664, 1996

1996

[9] [9]

Generating a random permutation with random transpositions

Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Zeitschrift f \"u r Wahrscheinlichkeitstheorie und Verwandte Gebiete , 57(2):159--179, 1981

1981

[10] [10]

Bounds for Kac 's master equation

Persi Diaconis and Laurent Saloff-Coste. Bounds for Kac 's master equation. Communications in Mathematical Physics , 209(3):729--755, 2000

2000

[11] [11]

On malliavin's proof of h \"o rmander's theorem

Martin Hairer. On malliavin's proof of h \"o rmander's theorem. Bulletin des Sciences Math \'e matiques , 135(6--7):650--666, 2011

2011

[12] [12]

W. K. Hastings. Monte C arlo sampling methods using M arkov chains and their applications. Biometrika , 57(1):97--109, 1970

1970

[13] [13]

Nicholas J. Higham. Functions of Matrices: Theory and Computation . Society for Industrial and Applied Mathematics, Philadelphia, PA, 2008

2008

[14] [14]

Cut-off phenomenon in the uniform plane Kac walk

Bob Hough and Yunjiang Jiang. Cut-off phenomenon in the uniform plane Kac walk. The Annals of Probability , 45(4):2248--2308, 2017

2017

[15] [15]

Mattingly

Martin Hairer and Jonathan C. Mattingly. Ergodicity of the 2d navier--stokes equations with degenerate stochastic forcing. Annals of Mathematics , 164(3):993--1032, 2006

2006

[16] [16]

Hypoelliptic second order differential equations

Lars H \"o rmander. Hypoelliptic second order differential equations. Acta Mathematica , 119:147--171, 1967

1967

[17] [17]

Spectral gap for Kac 's model of Boltzmann equation

\'E lise Janvresse. Spectral gap for Kac 's model of Boltzmann equation. The Annals of Probability , 29(1):288--304, 2001

2001

[18] [18]

Bounds on semigroups of random rotations on SO(n)

\'E lise Janvresse. Bounds on semigroups of random rotations on SO(n) . Theory of Probability & Its Applications , 47(3):526--532, 2003

2003

[19] [19]

Hoff, and David B

Michael Jauch, Peter D. Hoff, and David B. Dunson. Random orthogonal matrices and the Cayley transform . Bernoulli , 26(2):1560 -- 1586, 2020

2020

[20] [20]

Total variation bound for K ac's random walk

Yunjiang Jiang. Total variation bound for K ac's random walk. The Annals of Applied Probability , 22(6):2242--2262, 2012

2012

[21] [21]

Kac 's random walk on the special orthogonal group mixes in polynomial time

Yunjiang Jiang. Kac 's random walk on the special orthogonal group mixes in polynomial time. Proceedings of the American Mathematical Society , 145(10):4533--4541, 2017

2017

[22] [22]

Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith

Vishesh Jain, Natesh S. Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith. Fast and memory-optimal dimension reduction using Kac 's walk. The Annals of Applied Probability , 32(5):4038--4064, 2022

2022

[23] [23]

Foundations of kinetic theory

Mark Kac. Foundations of kinetic theory. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume III: Contributions to Astronomy and Physics , pages 171--197. University of California Press, 1956

1956

[24] [24]

Shigeo Kusuoka and Daniel W. Stroock. Applications of the malliavin calculus, part i. In Stochastic Analysis , volume 32 of North-Holland Mathematical Library , pages 271--306. North-Holland, 1984

1984

[25] [25]

Shigeo Kusuoka and Daniel W. Stroock. Applications of the malliavin calculus, part ii. Journal of the Faculty of Science, University of Tokyo, Section IA, Mathematics , 32(1):1--76, 1985

1985

[26] [26]

Mixing time and cutoff for one-dimensional particle systems

Hubert Lacoin. Mixing time and cutoff for one-dimensional particle systems. arXiv preprint arXiv:2111.06436 , 2021

work page arXiv 2021

[27] [27]

Markov chains and mixing times , volume 107

David A Levin and Yuval Peres. Markov chains and mixing times , volume 107. American Mathematical Soc., 2017

2017

[28] [28]

Hydrodynamic limit and cutoff for the biased adjacent walk on the simplex

Cyril Labb \'e and Engu \'e rand Petit. Hydrodynamic limit and cutoff for the biased adjacent walk on the simplex. Annales de l'Institut Henri Poincar \'e Probabilit \'e s et Statistiques , 61(2):769--802, 2025

2025

[29] [29]

Quantum pseudorandom scramblers

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. In Theory of Cryptography: 22nd International Conference, TCC 2024, Milan, Italy, December 2–6, 2024, Proceedings, Part II , page 3–35, Berlin, Heidelberg, 2024. Springer-Verlag

2024

[30] [30]

Parallel kac's walk generates pru

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Parallel kac's walk generates pru. 2025

2025

[31] [31]

Random walks in a convex body and an improved volume algorithm

L \'a szl \'o Lov \'a sz and Mikl \'o s Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms , 4(4):359--412, 1993

1993

[32] [32]

Stochastic calculus of variations and hypoelliptic operators

Paul Malliavin. Stochastic calculus of variations and hypoelliptic operators. In Proceedings of the International Symposium on Stochastic Differential Equations , pages 195--263. Wiley, 1978

1978

[33] [33]

David K. Maslen. The eigenvalues of Kac 's master equation. Mathematische Zeitschrift , 243(2):291--331, 2003

2003

[34] [34]

Kac's program in kinetic theory

St \'e phane Mischler and Cl \'e ment Mouhot. Kac's program in kinetic theory. Inventiones mathematicae , 193(1):1--147, 2013

2013

[35] [35]

James R. Norris. Simplified malliavin calculus. S \'e minaire de Probabilit \'e s XX , 1204:101--130, 1986

1986

[36] [36]

The Malliavin Calculus and Related Topics

David Nualart. The Malliavin Calculus and Related Topics . Springer, 2 edition, 2006

2006

[37] [37]

A method to derive concentration of measure bounds on M arkov chains

Stephen Ng and Meg Walters. A method to derive concentration of measure bounds on M arkov chains. Electronic Communications in Probability , 20:1--13, 2015

2015

[38] [38]

On the convergence to equilibrium of Kac 's random walk on matrices

Roberto Imbuzeiro Oliveira. On the convergence to equilibrium of Kac 's random walk on matrices. The Annals of Applied Probability , 19(3):1200--1231, 2009

2009

[39] [39]

The cut-off phenomenon for random reflections

Ursula Porod. The cut-off phenomenon for random reflections. The Annals of Probability , 24(1):74--96, 1996

1996

[40] [40]

Convergence of Kac 's random walk, 2007

Igor Pak and Sergiy Sidenko. Convergence of Kac 's random walk, 2007. Preprint

2007

[41] [41]

Pillai and Aaron Smith

Natesh S. Pillai and Aaron Smith. Kac's walk on n-sphere mixes in n log n steps. The Annals of Applied Probability , 27(1):631--650, 2017

2017

[42] [42]

Pillai and Aaron Smith

Natesh S. Pillai and Aaron Smith. On the mixing time of Kac 's walk and other high-dimensional Gibbs samplers with constraints. The Annals of Probability , 46(4):2345--2399, 2018

2018

[43] [43]

Rosenthal

Jeffrey S. Rosenthal. Random rotations: Characters and random walks on SO(N) . The Annals of Probability , 22(1):398--423, 1994

1994

[44] [44]

Authentication protocol using trapdoored matrices

Aikaterini Sotiraki. Authentication protocol using trapdoored matrices. Master's thesis, Massachusetts Institute of Technology, 2016. EECS

2016

[45] [45]

Joel A. Tropp. Freedman 's inequality for matrix martingales. Electronic Communications in Probability , 16:262--270, 2011

2011

[46] [46]

Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications , pages 2554--2574

Vinod Vaikuntanathan and Or Zamir. Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications , pages 2554--2574. 2026

2026