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


KeywordsRandom 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


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.


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

[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 | Article | MR 3681589 | Zbl 1391.52003

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

[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 | Article | MR 3201636 | Zbl 1279.60037

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

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

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

[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 | Article | MR 3476267

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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 | Article | MR 4282184 | Zbl 07379415

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

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

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

[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 | Article | MR 3385604 | Zbl 1322.60052