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}}

  • [AMN-Euclidean] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document . 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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