Volume 4 (2021)
Akopyan, Arseniy; Vysotsky, Vladislav
Large deviations of convex hulls of planar random walks and Brownian motions
Annales Henri Lebesgue, Volume 4 (2021), pp. 1163-1201.

Metadata

DOI10.5802/ahl.100
Keywords 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

Abstract

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.


References

[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