We derive asymptotics for the probability that the origin is an extremal point of a random walk in . We show that in order for the probability to be roughly , the number of steps of the random walk should be between and for some constant . As a result, we attain a bound for the -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 . Nous montrons que cette probabilité est proche de si le nombre de pas de la marche aléatoire est entre et pour une certaine constante . Comme corollaire, nous obtenons une borne pour le temps de -recouvrement d’un mouvement brownien sphérique.
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}, pages = {95--110}, publisher = {Gauthier-Villars}, volume = {50}, number = {1}, year = {2014}, doi = {10.1214/12-AIHP515}, mrnumber = {3161524}, zbl = {1290.60079}, language = {en}, url = {http://archive.numdam.org/articles/10.1214/12-AIHP515/} }
TY - JOUR AU - Eldan, Ronen TI - Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2014 SP - 95 EP - 110 VL - 50 IS - 1 PB - Gauthier-Villars UR - http://archive.numdam.org/articles/10.1214/12-AIHP515/ DO - 10.1214/12-AIHP515 LA - en ID - AIHPB_2014__50_1_95_0 ER -
%0 Journal Article %A Eldan, Ronen %T Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere %J Annales de l'I.H.P. Probabilités et statistiques %D 2014 %P 95-110 %V 50 %N 1 %I Gauthier-Villars %U http://archive.numdam.org/articles/10.1214/12-AIHP515/ %R 10.1214/12-AIHP515 %G en %F 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://archive.numdam.org/articles/10.1214/12-AIHP515/
[1] An introduction to covering problems for random walks on graphs. J. Theoret. Probab. 2 (1989) 87-89. | MR | Zbl
.[2] The grand tour: A tool for viewing multidimensional data. SIAM J. Sci. Statist. Comput. 6 (1985) 128-143. | MR | Zbl
.[3] A combinatorial lemma for complex numbers. Ann. Math. Statist. 32 (1961) 901-904. | MR | Zbl
.[4] On certain modifications of Chebyshev's inequality. (Russian) Doklady Akademii Nauk SSSR 17(6) (1937) 275-277.
.[5] Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. (2) 160 (2004) 433-464. | MR | Zbl
, , and .[6] Covering problems for Brownian motion on spheres. Ann. Probab. 16(1) (1988) 189-199. | MR | Zbl
.[7] Brownian Motion. Cambridge Univ. Press, Cambridge, 2010. | MR | Zbl
and .[8] Empirical Processes with Applications to Statistics. Wiley, New York, 1986. | MR | Zbl
and .[9] A problem in geometric probability. Math. Scand. 11 (1962) 109-111. | MR | Zbl
.Cited by Sources: