# Random walks in Euclidean space

### Abstract

Fix a probability measure on the space of isometries of Euclidean space $\mathbf{R}^d$. Let $Y_0=0,Y_1,Y_2,\ldots\in\mathbf{R}^d$ be a sequence of random points such that $Y_{l+1}$ is the image of $Y_l$ under a random isometry of the previously fixed probability law, which is independent of $Y_l$. We prove a Local Limit Theorem for $Y_l$ under necessary nondegeneracy conditions. Moreover, under more restrictive but still general conditions we give a quantitative estimate which describes the behavior of the law of $Y_l$ on scales $e^{-cl^{1/4}} Note: To view the article, click on the URL link for the DOI number. • [AMN-Euclidean] M. Ådahl, I. Melbourne, and M. Nicol, "Random iteration of Euclidean isometries," Nonlinearity, vol. 16, iss. 3, pp. 977-987, 2003. @article{AMN-Euclidean, mrkey = {1975792}, author = {{\AA}dahl, Markus and Melbourne, Ian and Nicol, Matthew}, title = {Random iteration of {E}uclidean isometries}, journal = {Nonlinearity}, fjournal = {Nonlinearity}, volume = {16}, year = {2003}, number = {3}, pages = {977--987}, issn = {0951-7715}, coden = {NONLE5}, mrclass = {37A50 (37H99 60F05 60F17)}, mrnumber = {1975792}, mrreviewer = {Viorel Ni{\c{t}}ic{\u{a}}}, doi = {10.1088/0951-7715/16/3/311}, zblnumber = {1037.37006}, } • [AK-uniform] V. I. Arnolcprimed and A. L. Krylov, "Uniform distribution of points on a sphere and certain ergodic properties of solutions of linear ordinary differential equations in a complex domain," Dokl. Akad. Nauk SSSR, vol. 148, pp. 9-12, 1963. @article{AK-uniform, mrkey = {0150374}, author = {Arnol{\cprime}d, V. I. and Krylov, A. L.}, title = {Uniform distribution of points on a sphere and certain ergodic properties of solutions of linear ordinary differential equations in a complex domain}, journal = {Dokl. Akad. Nauk SSSR}, fjournal = {Doklady Akademii Nauk SSSR}, volume = {148}, year = {1963}, pages = {9--12}, issn = {0002-3264}, mrclass = {34.06 (10.33)}, mrnumber = {0150374}, mrreviewer = {J. C. Lillo}, zblnumber = {0237.34008}, } • [BBC-LLT] P. Baldi, P. Bougerol, and P. Crépel, "Théorème central limite local sur les extensions compactes de${\bf R}^{d}$," Ann. Inst. H. Poincaré Sect. B, vol. 14, iss. 1, pp. 99-111, 1978. @article{BBC-LLT, mrkey = {0501239}, author = {Baldi, Paolo and Bougerol, Philippe and Cr{é}pel, Pierre}, title = {Théorème central limite local sur les extensions compactes de {${\bf R}\sp{d}$}}, journal = {Ann. Inst. H. Poincaré Sect. B}, volume = {14}, year = {1978}, number = {1}, pages = {99--111}, mrclass = {60B15 (60F05 60J15)}, mrnumber = {0501239}, mrreviewer = {Luis G. Gorostiza}, zblnumber = {0382.60013}, } • [Bas-Jordan-Burnside] H. Bass, "Theorems of Jordan and Burnside for algebraic groups," J. Algebra, vol. 82, iss. 1, pp. 245-254, 1983. @article{Bas-Jordan-Burnside, mrkey = {0701045}, author = {Bass, Hyman}, title = {Theorems of {J}ordan and {B}urnside for algebraic groups}, journal = {J. Algebra}, fjournal = {Journal of Algebra}, volume = {82}, year = {1983}, number = {1}, pages = {245--254}, issn = {0021-8693}, coden = {JALGA4}, mrclass = {20G15}, mrnumber = {0701045}, mrreviewer = {James E. Humphreys}, doi = {10.1016/0021-8693(83)90182-5}, zblnumber = {0506.20016}, } • [BG-SU2] J. Bourgain and A. Gamburd, "On the spectral gap for finitely-generated subgroups of$ SU(2)$," Invent. Math., vol. 171, iss. 1, pp. 83-121, 2008. @article{BG-SU2, mrkey = {2358056}, author = {Bourgain, Jean and Gamburd, Alex}, title = {On the spectral gap for finitely-generated subgroups of {$\rm SU(2)$}}, journal = {Invent. Math.}, fjournal = {Inventiones Mathematicae}, volume = {171}, year = {2008}, number = {1}, pages = {83--121}, issn = {0020-9910}, coden = {INVMBH}, mrclass = {22E30 (11B75 43A75)}, mrnumber = {2358056}, mrreviewer = {Ben Joseph Green}, doi = {10.1007/s00222-007-0072-z}, zblnumber = {1135.22010}, } • [BG-SUd] J. Bourgain and A. Gamburd, "A spectral gap theorem in${ SU}(d)$," J. Eur. Math. Soc.$($JEMS$)$, vol. 14, iss. 5, pp. 1455-1511, 2012. @article{BG-SUd, mrkey = {2966656}, author = {Bourgain, J. and Gamburd, A.}, title = {A spectral gap theorem in {${\rm SU}(d)$}}, journal = {J. Eur. Math. Soc.$($JEMS$)$}, fjournal = {Journal of the European Mathematical Society (JEMS)}, volume = {14}, year = {2012}, number = {5}, pages = {1455--1511}, issn = {1435-9855}, mrclass = {22E30 (11B30)}, mrnumber = {2966656}, mrreviewer = {B. Sury}, doi = {10.4171/JEMS/337}, zblnumber = {1254.43010}, } • [Bre-survey] E. Breuillard, Random walks on Lie groups. @misc{Bre-survey, author = {Breuillard, E.}, title = {Random walks on {L}ie groups}, url = {http://www.math.u-psud.fr/~breuilla/part0gb.pdf}, } • [Bur-martingale] D. L. Burkholder, "Distribution function inequalities for martingales," Ann. Probability, vol. 1, pp. 19-42, 1973. @article{Bur-martingale, mrkey = {0365692}, author = {Burkholder, D. L.}, title = {Distribution function inequalities for martingales}, journal = {Ann. Probability}, volume = {1}, year = {1973}, pages = {19--42}, mrclass = {60G45 (30A78)}, mrnumber = {0365692}, mrreviewer = {Martin L. Silverstein}, zblnumber = {0301.60035}, doi = {10.1214/aop/1176997023}, } • [CG-spectralgap] J. -P. Conze and Y. Guivarc’h, "Ergodicity of group actions and spectral gap, applications to random walks and Markov shifts," Discrete Contin. Dyn. Syst., vol. 33, iss. 9, pp. 4239-4269, 2013. @article{CG-spectralgap, mrkey = {3038061}, author = {Conze, J.-P. and Guivarc'h, Y.}, title = {Ergodicity of group actions and spectral gap, applications to random walks and {M}arkov shifts}, journal = {Discrete Contin. Dyn. Syst.}, fjournal = {Discrete and Continuous Dynamical Systems. Series A}, volume = {33}, year = {2013}, number = {9}, pages = {4239--4269}, issn = {1078-0947}, mrclass = {37A30 (22D40 28D05 60F05 60J05)}, mrnumber = {3038061}, mrreviewer = {Nhan-Phu Chung}, doi = {10.3934/dcds.2013.33.4239}, zblnumber = {06224557}, } • [DN-Solovay-Kitaev] C. M. Dawson and M. A. Nielsen, "The Solovay-Kitaev algorithm," Quantum Inf. Comput., vol. 6, iss. 1, pp. 81-95, 2006. @article{DN-Solovay-Kitaev, mrkey = {2212257}, author = {Dawson, Christopher M. and Nielsen, Michael A.}, title = {The {S}olovay-{K}itaev algorithm}, journal = {Quantum Inf. Comput.}, fjournal = {Quantum Information \& Computation}, volume = {6}, year = {2006}, number = {1}, pages = {81--95}, issn = {1533-7146}, mrclass = {81P68 (68Q05 81-02)}, mrnumber = {2212257}, zblnumber = {1152.81706}, url = {http://www.rintonpress.com/xqic6/qic-6-1/081-095.pdf}, } • [Dol-mixing] D. Dolgopyat, "On mixing properties of compact group extensions of hyperbolic systems," Israel J. Math., vol. 130, pp. 157-205, 2002. @article{Dol-mixing, mrkey = {1919377}, author = {Dolgopyat, Dmitry}, title = {On mixing properties of compact group extensions of hyperbolic systems}, journal = {Israel J. Math.}, fjournal = {Israel Journal of Mathematics}, volume = {130}, year = {2002}, pages = {157--205}, issn = {0021-2172}, coden = {ISJMAP}, mrclass = {37D30 (37A25 37C20 37C40)}, mrnumber = {1919377}, mrreviewer = {Boris Hasselblatt}, doi = {10.1007/BF02764076}, zblnumber = {1005.37005}, } • [Gor-CLT] L. G. Gorostiza, "The central limit theorem for random motions of$d$-dimensional Euclidean space," Ann. Probability, vol. 1, pp. 603-612, 1973. @article{Gor-CLT, mrkey = {0353408}, author = {Gorostiza, Luis G.}, title = {The central limit theorem for random motions of \hbox{{$d$}-dimen}sional {E}uclidean space}, journal = {Ann. Probability}, volume = {1}, year = {1973}, pages = {603--612}, mrclass = {60B15 (60F05)}, mrnumber = {0353408}, mrreviewer = {Wilfried Hazod}, zblnumber = {0263.60010}, doi = {10.1214/aop/1176996889}, } • [Got-commutator] M. Gotô, "A Theorem on compact semi-simple groups," J. Math. Soc. Japan, vol. 1, pp. 270-272, 1949. @article{Got-commutator, mrkey = {0033829}, author = {Got{ô}, Morikuni}, title = {A {T}heorem on compact semi-simple groups}, journal = {J. Math. Soc. Japan}, fjournal = {Journal of the Mathematical Society of Japan}, volume = {1}, year = {1949}, pages = {270--272}, issn = {0025-5645}, mrclass = {20.0X}, mrnumber = {0033829}, mrreviewer = {G. W. Mackey}, doi = {10.2969/jmsj/00130270}, zblnumber = {0041.36208}, } • [Gri-CLT] A. Grintsyavichyus, "The domain of normal attraction of a stable law for the group of motions of a Euclidean space," Litovsk. Mat. Sb., vol. 25, iss. 3, pp. 39-52, 1985. @article{Gri-CLT, mrkey = {0823642}, author = {Grintsyavichyus, A.}, title = {The domain of normal attraction of a stable law for the group of motions of a {E}uclidean space}, journal = {Litovsk. Mat. Sb.}, fjournal = {Lietuvos TSR Moksl\polhk u Akademija. Lietuvos TSR Aukštosios Mokyklos. Lietuvos Matematikos Rinkinys. Akademiya Nauk LitovskoĭSSR. Vysshie Uchebnye Zavedeniya LitovskoĭSSR. LitovskiĭMatematicheskiĭSbornik}, volume = {25}, year = {1985}, number = {3}, pages = {39--52}, issn = {0132-2818}, mrclass = {60B15}, mrnumber = {0823642}, mrreviewer = {N. Sarapa}, } • [Gui-uniform] Y. Guivarc’h, "Equirépartition dans les espaces homogènes," in Théorie Ergodique, New York: Springer-Verlag, 1976, vol. 532, pp. 131-142. @incollection{Gui-uniform, mrkey = {0480860}, author = {Guivarc'h, Yves}, title = {Equirépartition dans les espaces homogènes}, booktitle = {Théorie Ergodique}, venue = {{A}ctes {J}ournées {E}rgodiques, {R}ennes, 1973/1974}, pages = {131--142}, series = {Lecture Notes in Math.}, volume = {532}, publisher = {Springer-Verlag}, year = {1976}, mrclass = {22E30 (10K05)}, mrnumber = {0480860}, mrreviewer = {Marthe Grandet}, address = {New York}, zblnumber = {0368.28024}, DOI = {10.1007/BFb0080176}, } • [Kaz-uniform] D. A. Kavzdan, "Uniform distribution on a plane," Trudy Moskov. Mat. Obšč., vol. 14, pp. 299-305, 1965. @article{Kaz-uniform, mrkey = {0193187}, author = {Ka{ž}dan, D. A.}, title = {Uniform distribution on a plane}, journal = {Trudy Moskov. Mat. Obšč.}, fjournal = {Trudy Moskovskogo Matematičeskogo Obščestva}, volume = {14}, year = {1965}, pages = {299--305}, issn = {0134-8663}, mrclass = {22.60 (10.33)}, mrnumber = {0193187}, mrreviewer = {M. Hasumi}, zblnumber = {0225.26018}, } • [Kho-LLT] . Y. S. Khokhlov, "A local limit theorem for the composition of random motions of Euclidean space," Dokl. Akad. Nauk SSSR, vol. 260, iss. 2, pp. 295-299, 1981. @article{Kho-LLT, mrkey = {0630143}, author = {Khokhlov, {\relax Yu} S.}, title = {A local limit theorem for the composition of random motions of {E}uclidean space}, journal = {Dokl. Akad. Nauk SSSR}, fjournal = {Doklady Akademii Nauk SSSR}, volume = {260}, year = {1981}, number = {2}, pages = {295--299}, issn = {0002-3264}, mrclass = {60B15 (60F05)}, mrnumber = {0630143}, mrreviewer = {V. M. Maksimov}, ZBLNUMBER = {0494.60026}, } • [Kho-CLT] . Y. S. Khokhlov, "The domain of normal attraction of a semistable distribution on a semidirect product compact group and$\Bbb {R}^d$," J. Math. Sci., vol. 76, iss. 1, pp. 2147-2152, 1995. @article{Kho-CLT, mrkey = {1356652}, author = {Khokhlov, {\relax Yu} S.}, title = {The domain of normal attraction of a semistable distribution on a semidirect product compact group and {$\bold {R}\sp d$}}, journal = {J. Math. Sci.}, fjournal = {Journal of Mathematical Sciences}, volume = {76}, year = {1995}, number = {1}, pages = {2147--2152}, issn = {1072-3374}, coden = {JMTSEW}, mrclass = {60B15}, mrnumber = {1356652}, doi = {10.1007/BF02363227}, } • [Kit-Solovay-Kitaev] Y. A. Kitaev, "Quantum computations: algorithms and error correction," Uspekhi Mat. Nauk, vol. 52, iss. 6(318), pp. 53-112, 1997. @article{Kit-Solovay-Kitaev, mrkey = {1611329}, author = {Kitaev, A. Yu.}, title = {Quantum computations: algorithms and error correction}, journal = {Uspekhi Mat. Nauk}, fjournal = {Rossiĭskaya Akademiya Nauk. Moskovskoe Matematicheskoe Obshchestvo. Uspekhi Matematicheskikh Nauk}, volume = {52}, year = {1997}, number = {6(318)}, pages = {53--112}, issn = {0042-1316}, mrclass = {68Q05 (81P99 94B60)}, mrnumber = {1611329}, mrreviewer = {V. Ya. Kreinovich}, doi = {10.1070/RM1997v052n06ABEH002155}, ZBLNUMBER = {0917.68063}, } • [Max-LLT] V. M. Maximov, "Local theorems for Euclidean motions. I," Z. Wahrsch. Verw. Gebiete, vol. 51, iss. 1, pp. 27-38, 1980. @article{Max-LLT, mrkey = {0566105}, author = {Maximov, V. M.}, title = {Local theorems for {E}uclidean motions. {I}}, journal = {Z. Wahrsch. Verw. Gebiete}, fjournal = {Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete}, volume = {51}, year = {1980}, number = {1}, pages = {27--38}, issn = {0044-3719}, mrclass = {60B15 (60J15)}, mrnumber = {0566105}, mrreviewer = {Paolo Baldi}, doi = {10.1007/BF00533814}, zblnumber = {0427.60010}, } • [RY-CLT] S. T. Rachev and J. E. Yukich, "Rates of convergence of$\alpha$-stable random motions," J. Theoret. Probab., vol. 4, iss. 2, pp. 333-352, 1991. @article{RY-CLT, mrkey = {1100238}, author = {Rachev, S. T. and Yukich, J. E.}, title = {Rates of convergence of {$\alpha$}-stable random motions}, journal = {J. Theoret. Probab.}, fjournal = {Journal of Theoretical Probability}, volume = {4}, year = {1991}, number = {2}, pages = {333--352}, issn = {0894-9840}, coden = {JTPREO}, mrclass = {60F05 (60B15 60F15)}, mrnumber = {1100238}, mrreviewer = {Ludger R{ü}schendorf}, doi = {10.1007/BF01258741}, zblnumber = {0724.60019}, } • [Roy-CLT] B. Roynette, "Théorème central-limite pour le groupe des déplacements de${\bf R}^{d}$," Ann. Inst. H. Poincaré Sect. B, vol. 10, pp. 391-398 (1975), 1974. @article{Roy-CLT, mrkey = {0375422}, author = {Roynette, Bernard}, title = {Théorème central-limite pour le groupe des déplacements de {${\bf R}\sp{d}\$}},   journal = {Ann. Inst. H. Poincaré Sect. B},   volume = {10},   year = {1974},   pages = {391--398 (1975)},   mrclass = {60B15},   mrnumber = {0375422},   mrreviewer = {Eberhard Siebert},   zblnumber = {0324.60026},   URL = {http://www.numdam.org/item?id=AIHPB_1974__10_4_391_0},   }
• [Tut-CLT] V. N. Tutubalin, "The central limit theorem for random motions of Euclidean space," Vestnik Moskov. Univ. Ser. I Mat. Meh., vol. 22, iss. 6, pp. 100-108, 1967.
@article{Tut-CLT, mrkey = {0242233},   author = {Tutubalin, V. N.},   title = {The central limit theorem for random motions of {E}uclidean space},   journal = {Vestnik Moskov. Univ. Ser. I Mat. Meh.},   fjournal = {Vestnik Moskovskogo Universiteta. Serija I. Matematika, Mehanika},   volume = {22},   year = {1967},   number = {6},   pages = {100--108},   issn = {0201-7385},   mrclass = {60.30},   mrnumber = {0242233},   }
• [Var-compact] P. Pál. Varjú, "Random walks in compact groups," Doc. Math., vol. 18, pp. 1137-1175, 2013.
@article{Var-compact, mrkey = {3138842},   author = {Varj{ú},   P{é}ter P{á}l},   title = {Random walks in compact groups},   journal = {Doc. Math.},   fjournal = {Documenta Mathematica},   volume = {18},   year = {2013},   pages = {1137--1175},   issn = {1431-0635},   mrclass = {60B15 (05E15 22E30)},   mrnumber = {3138842},   mrreviewer = {Martin V. Hildebrand},   zblnumber = {1278.60011},   url = {http://www.math.uiuc.edu/documenta/vol-18/35.pdf},   }

## Authors

Péter Pál Varjú

Centre for Mathematical Sciences, University of Cambridge, Cambridge CB3 0WB, England and Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel