Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere
Annales de l'I.H.P. Probabilités et statistiques, Volume 50 (2014) no. 1, p. 95-110

We derive asymptotics for the probability that the origin is an extremal point of a random walk in n . We show that in order for the probability to be roughly 1/2, the number of steps of the random walk should be between e n/(Clogn) and e Cnlogn for some constant C>0. As a result, we attain a bound for the π 2-covering time of a spherical Brownian motion.

Nous étudions le comportement asymptotique de la probabilité que l’origine soit un point extrémal d’une marche aléatoire dans n . Nous montrons que cette probabilité est proche de 1/2 si le nombre de pas de la marche aléatoire est entre e n/(Clogn) et e Cnlogn pour une certaine constante C>0. Comme corollaire, nous obtenons une borne pour le temps de π 2-recouvrement d’un mouvement brownien sphérique.

DOI : https://doi.org/10.1214/12-AIHP515
Classification:  52A22,  52A38,  60J65
Keywords: random walk, convex hull, mixing time, spherical coverings
@article{AIHPB_2014__50_1_95_0,
     author = {Eldan, Ronen},
     title = {Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {50},
     number = {1},
     year = {2014},
     pages = {95-110},
     doi = {10.1214/12-AIHP515},
     zbl = {1290.60079},
     mrnumber = {3161524},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2014__50_1_95_0}
}
Eldan, Ronen. Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere. Annales de l'I.H.P. Probabilités et statistiques, Volume 50 (2014) no. 1, pp. 95-110. doi : 10.1214/12-AIHP515. http://www.numdam.org/item/AIHPB_2014__50_1_95_0/

[1] D. J. Aldous. An introduction to covering problems for random walks on graphs. J. Theoret. Probab. 2 (1989) 87-89. | MR 981766 | Zbl 0684.60054

[2] D. Asimov. The grand tour: A tool for viewing multidimensional data. SIAM J. Sci. Statist. Comput. 6 (1985) 128-143. | MR 773286 | Zbl 0552.62052

[3] G. Baxter. A combinatorial lemma for complex numbers. Ann. Math. Statist. 32 (1961) 901-904. | MR 126290 | Zbl 0119.14201

[4] S. N. Bernstein. On certain modifications of Chebyshev's inequality. (Russian) Doklady Akademii Nauk SSSR 17(6) (1937) 275-277.

[5] A. Dembo, Y. Peres, J. Rosen and O. Zeitouni. Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. (2) 160 (2004) 433-464. | MR 2123929 | Zbl 1068.60018

[6] P. Matthews. Covering problems for Brownian motion on spheres. Ann. Probab. 16(1) (1988) 189-199. | MR 920264 | Zbl 0638.60014

[7] P. Mörters and Y. Peres. Brownian Motion. Cambridge Univ. Press, Cambridge, 2010. | MR 2604525 | Zbl 1243.60002

[8] G. R. Shorack and J. A. Wellner. Empirical Processes with Applications to Statistics. Wiley, New York, 1986. | MR 838963 | Zbl 1170.62365

[9] J. G. Wendel. A problem in geometric probability. Math. Scand. 11 (1962) 109-111. | MR 146858 | Zbl 0108.31603