Convex Hulls of Multiple Random Walks: A Large-Deviation Study

Abstract

We study the polygons governing the convex hull of a point set created by the steps of $n$ independent two-dimensional random walkers. Each such walk consists of $T$ discrete time steps, where $x$ and $y$ increments are i.i.d. Gaussian. We analyze area $A$ and perimeter $L$ of the convex hulls. We obtain probability densities for these two quantities over a large range of the support by using a large-deviation approach allowing us to study densities below $10^{-900}$. We find that the densities exhibit a universal scaling behavior as a function of $A/T$ and $L/\sqrt{T}$, respectively. As in the case of one walker ($n=1$), the densities follow Gaussian distributions for $L$ and $\sqrt{A}$, respectively. We also obtained the rate functions for the area and perimeter, rescaled with the scaling behavior of their maximum possible values, and found limiting functions for $T\to \infty$, revealing that the densities follow the large-deviation principle. These rate functions can be described by a power law for $n\to \infty$ as found in the $n=1$ case. We also investigated the behavior of the averages as a function of the number of walks $n$ and found good agreement with the predicted behavior.

11 pages, 14 figures

References in corpus (18)

• The large deviation approach to statistical mechanics
• Non-intersecting Brownian walkers and Yang-Mills theory on the sphere
• Random Convex Hulls and Extreme Value Statistics
• Exact distribution of the maximal height of p vicious walkers
• 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
• Distribution of the time at which N vicious walkers reach their maximal height
• Reunion probability of N vicious walkers: typical and large fluctuations for large N
• Exact distributions of the number of distinct and common sites visited by N independent random walkers
• Convex Hulls of Random Walks: Large-Deviation Properties
• Volumetric Properties of the Convex Hull of an n-dimensional Brownian Motion
• The convex hull for a random acceleration process in two dimensions
• Maximum of N Independent Brownian Walkers till the First Exit From the Half Space
• Convex hull of a Brownian motion in confinement
• Diffusion of two repulsive particles in a one-dimensional lattice
• Maximal distance travelled by N vicious walkers till their survival

Cited by in corpus (10)

• Long time position distribution of an active Brownian particle in two dimensions
• High-precision simulation of the height distribution for the KPZ equation
• Large-deviation properties of the largest biconnected component for random graphs
• Mean perimeter and mean area of the convex hull over planar random walks
• Probing the large deviations of the Kardar-Parisi-Zhang equation at short time with an importance sampling of directed polymers in random media
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• 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
• Large deviations of a random walk model with emerging territories