Large deviations of convex hulls of planar random walks and Brownian motions

Akopyan, Arseniy; Vysotsky, Vladislav

Annales Henri Lebesgue, Volume 4 (2021), pp. 1163-1201.

We prove large deviations principles (LDPs) for the perimeter and the area of the convex hull of a planar random walk with finite Laplace transform of its increments.

We give explicit upper and lower bounds for the rate function of the perimeter in terms of the rate function of the increments. These bounds coincide and thus give the rate function for a wide class of distributions which includes the Gaussians and the rotationally invariant ones. For random walks with such increments, large deviations of the perimeter are attained by the trajectories that asymptotically align into line segments. However, line segments may not be optimal in general.

Furthermore, we find explicitly the rate function of the area of the convex hull for random walks with rotationally invariant distribution of increments. For such walks, which necessarily have zero mean, large deviations of the area are attained by the trajectories that asymptotically align into half-circles. For random walks with non-zero mean increments, we find the rate function of the area for Gaussian walks with drift. Here the optimal limit shapes are elliptic arcs if the covariance matrix of increments is non-degenerate and parabolic arcs if otherwise.

The above results on convex hulls of Gaussian random walks remain valid for convex hulls of planar Brownian motions of all possible parameters. Moreover, we extend the LDPs for the perimeter and the area of convex hulls to general Lévy processes with finite Laplace transform.

Nous montrons des principes de grandes déviations pour le périmètre et l’aire de l’enveloppe convexe d’une marche aléatoire planaire dont les incréments ont une transformée de Laplace finie.

Nous donnons des bornes inférieures et supérieures explicites pour la fonction de taux pour le périmètre, en termes de la fonction de taux pour les incréments. Pour une large classe de distributions incluant les distributions gaussiennes et les distributions invariantes par rotation, ces bornes coïncident et donnent donc la fonction de taux exacte. Pour des marches aléatoires avec de tels incréments, les grandes déviations pour le périmètre sont atteintes par les trajectoires qui se comportent asymptotiquement comme des segments de droite. Cependant, les segments de droite ne sont pas optimaux en général.

De plus, nous trouvons explicitement la fonction de taux pour l’aire de l’enveloppe convexe des marches aléatoires è incréments invariants par rotation. Pour de telles marches, qui sont nécessairement centrées, les grandes déviations pour l’aire sont réalisées par les trajectoires qui se comportent asymptotiquement comme des demi-cercles. Pour des marches aléatoires avec des incréments non centrés, nous donnons la fonction de taux pour l’aire pour des marches gaussiennes non centrées. En ce cas, les trajectoires optimales sont des arcs elliptiques si la matrice de covariance des incréments est non dégénérée, et des arcs paraboliques sinon.

Les résultats précédents sur les enveloppes convexes de marches aléatoires gaussiennes restent valides pour les enveloppes convexes de mouvements browniens plans pour tous les paramètres. De plus, nous étendons le principe de grande déviation pour le périmètre et l’aire des enveloppes convexes à des processus de Lévy généraux avec transformée de Laplace finie.

Classification: 60D05, 60F10, 60G50, 26B25, 52A22, 60G70
Mots-clés : Random walk, Brownian motion, Wiener process, Lévy process, convex hull, large deviations, perimeter, area, mean width, rate function, non-convex rate function, radial minimum, radial maximum, Legendre–Fenchel transform, convex conjugate

[AKMV20] Alsmeyer, Gerold; Kabluchko, Zakhar; Marynych, Alexander; Vysotsky, Vladislav How long is the convex minorant of a one-dimensional random walk?, Electron. J. Probab., Volume 25 (2020), 105 | MR | Zbl

[AV17] Akopyan, Arseniy; Vysotsky, Vladislav On the lengths of curves passing through boundary points of a planar convex shape, Am. Math. Mon., Volume 124 (2017) no. 7, pp. 588-596 | DOI | MR | Zbl

[Ber96] Bertoin, Jean Lévy processes, Cambridge Tracts in Mathematics, 121, Cambridge University Press, 1996 | Zbl

[BM13] Borovkov, Aleksandr A.; Mogulskii, Anatolii A. Large deviation principles for random walk trajectories. II, Theory Probab. Appl., Volume 57 (2013) no. 1, pp. 1-27 | DOI | MR | Zbl

[BN78] Barndorff-Nielsen, Ole Information and exponential families in statistical theory, John Wiley & Sons, 1978 | MR | Zbl

[BNB63] Barndorff-Nielsen, Ole; Baxter, Glen Combinatorial lemmas in higher dimensions, Trans. Am. Math. Soc., Volume 108 (1963), pp. 313-325 | DOI | MR | Zbl

[CFG91] Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. Unsolved problems in geometry, Problem Books in Mathematics, Springer, 1991 | Zbl

[CHM15] Claussen, Gunnar; Hartmann, Alexander K.; Majumdar, Satya N. Convex hulls of random walks: large-deviation properties, Phys. Rev. E, Volume 91 (2015) no. 5, 052104 | DOI | MR

[DZ10] Dembo, Amir; Zeitouni, Ofer Large deviations techniques and applications, Stochastic Modelling and Applied Probability, 38, Springer, 2010 corrected reprint of the second (1998) edition | MR | Zbl

[GSO16] Glaeser, Georg; Stachel, Hellmuth; Odehnal, Boris The Universe of Conics: From the ancient Greeks to 21st century developments, Springer, 2016 | Zbl

[Kho92] Khoshnevisan, Davar Local asymptotic laws for the Brownian convex hull, Probab. Theory Relat. Fields, Volume 93 (1992) no. 3, pp. 377-392 | DOI | MR | Zbl

[KL98] Kuelbs, James; Ledoux, Michel On convex limit sets and Brownian motion, J. Theor. Probab., Volume 11 (1998) no. 2, pp. 461-492 | DOI | MR | Zbl

[Mog76] Mogulskii, Anatolii A. Large deviations for the trajectories of multidimensional random walks, Theory Probab. Appl., Volume 21 (1976) no. 2, pp. 300-315 | DOI | MR | Zbl

[Mor46] Moran, Patrick A. P. On a problem of S. Ulam, J. Lond. Math. Soc., Volume 21 (1946), pp. 175-179 | DOI | Zbl

[MW16] Molchanov, Ilya; Wespi, Florian Convex hulls of Lévy processes, Electron. Commun. Probab., Volume 21 (2016), 69 | Zbl

[MW18] McRedmond, James; Wade, Andrew R. The convex hull of a planar random walk: perimeter, diameter, and shape, Electron. J. Probab., Volume 23 (2018), 131 | MR | Zbl

[Pac78] Pach, János On an isoperimetric problem, Stud. Sci. Math. Hung., Volume 13 (1978), pp. 43-45 | MR | Zbl

[Roc70] Rockafellar, R. Tyrrell Convex analysis, Princeton University Press, 1970 | DOI | Zbl

[RY99] Revuz, Daniel; Yor, Marc Continuous martingales and Brownian motion, Grundlehren der Mathematischen Wissenschaften, 293, Springer, 1999 | MR | Zbl

[SS93] Snyder, Timothy Law; Steele, J. Michael Convex hulls of random walks, Proc. Am. Math. Soc., Volume 117 (1993) no. 4, pp. 1165-1173 | DOI | MR | Zbl

[SW61] Spitzer, Frank; Widom, Harold The circumference of a convex polygon, Proc. Am. Math. Soc., Volume 12 (1961), pp. 506-509 | DOI | MR | Zbl

[SW08] Schneider, Rolf; Weil, Wolfgang Stochastic and integral geometry, Probability and Its Applications, Springer, 2008 | DOI | Zbl

[Til10] Tilli, Paolo Isoperimetric inequalities for convex hulls and related questions, Trans. Am. Math. Soc., Volume 362 (2010) no. 9, pp. 4497-4509 | DOI | MR | Zbl

[Vys21a] Vysotsky, Vladislav Contraction principle for trajectories of random walks and Cramér’s theorem for kernel-weighted sums, ALEA, Lat. Am. J. Probab. Math. Stat., Volume 18 (2021), pp. 1103-1125 | DOI | MR | Zbl

[Vys21b] Vysotsky, Vladislav When is the rate function of a random vector strictly convex?, Electron. Commun. Probab., Volume 26 (2021), 41 | DOI | MR

[VZ18] Vysotsky, Vladislav; Zaporozhets, Dmitry Convex hulls of multidimensional random walks, Trans. Am. Math. Soc., Volume 370 (2018) no. 11, pp. 7985-8012 | DOI | MR | Zbl

[WX15a] Wade, Andrew R.; Xu, Chang Convex hulls of planar random walks with drift, Proc. Am. Math. Soc., Volume 143 (2015) no. 11, pp. 433-445 | MR | Zbl

[WX15b] Wade, Andrew R.; Xu, Chang Convex hulls of random walks and their scaling limits, Stochastic Processes Appl., Volume 125 (2015) no. 11, pp. 4300-4320 | DOI | MR | Zbl