Convex Hulls of Random Walks: Large-Deviation Properties

Abstract

We study the convex hull of the set of points visited by a two-dimensional random walker of T discrete time steps. Two natural observables that characterize the convex hull in two dimensions are its perimeter L and area A. While the mean perimeter <L> and the mean area <A> have been studied before, analytically and numerically, and exact results are known for large T (Brownian motion limit), little is known about the full distributions P(A) and P(L). In this paper, we provide numerical results for these distributions. We use a sophisticated large-deviation approach that allows us to study the distributions over a larger range of the support, where the probabilities P(A) and P(L) are as small as 10^{-300}. We analyze (open) random walks as well as (closed) Brownian bridges on the two-dimensional discrete grid as well as in the two-dimensional plane. The resulting distributions exhibit, for large T, a universal scaling behavior (independent of the details of the jump distributions) as a function of A/T and L/\sqrt{T}, respectively. We are also able to obtain the rate function, describing rare events at the tails of these distributions, via a numerical extrapolation scheme and find a linear and square dependence as a function of the rescaled perimeter and the rescaled area, respectively.

arXiv comment10 pages, 12 figures, 2 tables

References in corpus (9)

• The large deviation approach to statistical mechanics
• Random Convex Hulls and Extreme Value Statistics
• Convex Hull of N Planar Brownian Motions: Exact Results and an Application to Ecology
• Sampling rare events: statistics of local sequence alignments
• Large-deviation properties of largest component for random graphs
• Spatial extent of an outbreak in animal epidemics
• Exact distributions of the number of distinct and common sites visited by N independent random walkers
• The convex hull for a random acceleration process in two dimensions
• Maximal distance travelled by N vicious walkers till their survival

Cited by in corpus (27)

• Long time position distribution of an active Brownian particle in two dimensions
• The convex hull of the run-and-tumble particle in a plane
• High-precision simulation of the height distribution for the KPZ equation
• Mean perimeter and area of the convex hull of a planar Brownian motion in the presence of resetting
• Unravelling intermittent features in single particle trajectories by a local convex hull method
• Large-deviation properties of the largest biconnected component for random graphs
• Critical behavior of the Anderson model on the Bethe lattice via a large-deviation approach
• Mean area of the convex hull of a run and tumble particle in two dimensions
• Mean perimeter and mean area of the convex hull over planar random walks
• Ground state energy of noninteracting fermions with a random energy spectrum
• Probing the large deviations of the Kardar-Parisi-Zhang equation at short time with an importance sampling of directed polymers in random media
• Observing symmetry-broken optimal paths of stationary Kardar-Parisi-Zhang interface via a large-deviation sampling of directed polymers in random media
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Confined run and tumble particles with non-Markovian tumbling statistics
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• Large Deviations of Convex Hulls of the "True" Self-Avoiding Random Walk
• Large deviations in statistics of the convex hull of passive and active particles: A theoretical study
• A unified perspective on exponential tilt and bridge algorithms for rare trajectories of discrete Markov processes
• Optimal finite-differences discretization for the diffusion equation from the perspective of large-deviation theory
• Large deviations of a random walk model with emerging territories
• The shape of a memorised random walk
• Dimensionality-induced dynamical phase transition in the large deviation of local time density for Brownian motion
• Convex hulls of planar random walks
• Sampling rare trajectories using stochastic bridges