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.

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: 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},
     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] D. J. Aldous. An introduction to covering problems for random walks on graphs. J. Theoret. Probab. 2 (1989) 87-89. | MR | Zbl

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

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

[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 | Zbl

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

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

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

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

Cited by Sources: