Extremal points of high-dimensional random walks and mixing times of a brownian motion on the sphere

Eldan, Ronen

doi:10.1214/12-AIHP515

Eldan, Ronen

Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) no. 1, pp. 95-110

Abstract (VO)
Résumé

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 / (C log n)}$ and $e^{C n log n}$ for some constant $C > 0$ . As a result, we attain a bound for the $\frac{π}{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 / (C log n)}$ et $e^{C n log n}$ pour une certaine constante $C > 0$ . Comme corollaire, nous obtenons une borne pour le temps de $\frac{π}{2}$ -recouvrement d’un mouvement brownien sphérique.

MR Zbl

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},
     year = {2014},
     publisher = {Gauthier-Villars},
     volume = {50},
     number = {1},
     doi = {10.1214/12-AIHP515},
     mrnumber = {3161524},
     zbl = {1290.60079},
     language = {en},
     url = {https://www.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  - https://www.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 https://www.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, Tome 50 (2014) no. 1, pp. 95-110. doi: 10.1214/12-AIHP515

Bibliographie
Cité par

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

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

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

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

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

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

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

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

Cité par Sources :