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

Jiang, Yunjiang

doi:10.1090/proc/13598

Kac’s random walk on the special orthogonal group mixes in polynomial time
HTML articles powered by AMS MathViewer

by Yunjiang Jiang PDF

Proc. Amer. Math. Soc. 145 (2017), 4533-4541 Request permission

Abstract:

We give the first proof of polynomial total variation mixing time bound for the Kac random walk on the special orthogonal groups. The proof relies on the exact spectral gap computation by E. A. Carlen et al. and D. Maslen, and hinges on two novel ingredients: a multi-dimensional generalization of Turan’s lemma for polynomials on the unit circle, proved by F. L. Nazarov, and a Morse-theoretic result due to J. Milnor. The techniques are robust in the sense that the step distribution of the walk does not have to be uniformly supported on the circles and that the model can be generalized to higher dimensional particles or other compact Lie groups, provided the corresponding relaxation time is polynomial in the dimension.

References

E. A. Carlen, M. C. Carvalho, and M. Loss, Determination of the spectral gap for Kac’s master equation and related stochastic evolution, Acta Math. 191 (2003), no. 1, 1–54. MR 2020418, DOI 10.1007/BF02392695
Eric A. Carlen, Maria C. Carvalho, Jonathan Le Roux, Michael Loss, and Cédric Villani, Entropy and chaos in the Kac model, Kinet. Relat. Models 3 (2010), no. 1, 85–122. MR 2580955, DOI 10.3934/krm.2010.3.85
Persi Diaconis and Laurent Saloff-Coste, Bounds for Kac’s master equation, Comm. Math. Phys. 209 (2000), no. 3, 729–755. MR 1743614, DOI 10.1007/s002200050036
Natacha Fontes-Merz, A multidimensional version of Turán’s lemma, J. Approx. Theory 140 (2006), no. 1, 27–30. MR 2226674, DOI 10.1016/j.jat.2005.11.012
Elise Janvresse, Spectral gap for Kac’s model of Boltzmann equation, Ann. Probab. 29 (2001), no. 1, 288–304. MR 1825150, DOI 10.1214/aop/1008956330
Yunjiang Jiang, Total variation bounds of Kac random walk, Ann. Appl. Probab. (2011). MR2985175
David K. Maslen, The eigenvalues of Kac’s master equation, Math. Z. 243 (2003), no. 2, 291–331. MR 1961868, DOI 10.1007/s00209-002-0466-y
J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 161339, DOI 10.1090/S0002-9939-1964-0161339-9
F. L. Nazarov, On the theorems of Turán, Amrein and Berthier, and Zygmund, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 201 (1992), no. Issled. po Lineĭn. Oper. Teor. Funktsiĭ. 20, 117–123, 191 (Russian, with English summary); English transl., J. Math. Sci. 78 (1996), no. 2, 195–198. MR 1172761, DOI 10.1007/BF02366034
Roberto Imbuzeiro Oliveira, On the convergence to equilibrium of Kac’s random walk on matrices, Ann. Appl. Probab. 19 (2009), no. 3, 1200–1231. MR 2537204, DOI 10.1214/08-AAP550
Natesh S. Pillai and Aaron Smith, Kac’s walk on $n$-sphere mixes in $n\log n$ steps, preprint, arXiv:1507.08554 (2015).
—, On the mixing time of Kac’s walk and other high-dimensional Gibbs samplers with constraints, preprint, arXiv:1605.08122 (2016).
R. Potrie, Communication via mathoverflow, http://mathoverflow.net/questions/45199/.
I. Rivin, Communication via mathoverflow, http://mathoverflow.net/questions/84471/.
Sergiy Sidenko, Kac’s random walk and coupon collector’s process on posets, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)–Massachusetts Institute of Technology. MR 2717533
Aaron Smith, A Gibbs sampler on the $n$-simplex, Ann. Appl. Probab. 24 (2014), no. 1, 114–130. MR 3161643, DOI 10.1214/12-AAP916
René Thom, Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press, Princeton, N.J., 1965, pp. 255–265 (French). MR 0200942