Random Convex Hulls and Extreme Value Statistics

Abstract

In this paper we study the statistical properties of convex hulls of $N$ random points in a plane chosen according to a given distribution. The points may be chosen independently or they may be correlated. After a non-exhaustive survey of the somewhat sporadic literature and diverse methods used in the random convex hull problem, we present a unifying approach, based on the notion of support function of a closed curve and the associated Cauchy's formulae, that allows us to compute exactly the mean perimeter and the mean area enclosed by the convex polygon both in case of independent as well as correlated points. Our method demonstrates a beautiful link between the random convex hull problem and the subject of extreme value statistics. As an example of correlated points, we study here in detail the case when the points represent the vertices of $n$ independent random walks. In the continuum time limit this reduces to $n$ independent planar Brownian trajectories for which we compute exactly, for all $n$, the mean perimeter and the mean area of their global convex hull. Our results have relevant applications in ecology in estimating the home range of a herd of animals. Some of these results were announced recently in a short communication [Phys. Rev. Lett. {\bf 103}, 140602 (2009)].

61 pages (pedagogical review); invited contribution to the special issue of J. Stat. Phys. celebrating the 50 years of Yeshiba/Rutgers meetings

References in corpus (60)

• Level-Spacing Distributions and the Airy Kernel
• Shape Fluctuations and Random Matrices
• Universality Classes for Extreme Value Statistics
• Level-Spacing Distributions and the Airy Kernel
• Glass transition of a particle in a random potential, front selection in nonlinear RG and entropic phenomena in Liouville and SinhGordon models
• Large Deviations of Extreme Eigenvalues of Random Matrices
• Extreme Value Statistics of Eigenvalues of Gaussian Random Matrices
• Airy Distribution Function: From the Area Under a Brownian Excursion to the Maximal Height of Fluctuating Interfaces
• Exact Maximal Height Distribution of Fluctuating Interfaces
• Freezing and extreme value statistics in a Random Energy Model with logarithmically correlated potential
• Large Deviations of the Maximum Eigenvalue for Wishart and Gaussian Random Matrices
• Universal Record Statistics of Random Walks and Lévy Flights
• Driven particle in a random landscape: disorder correlator, avalanche distribution and extreme value statistics of records
• Large Deviations of the Maximum Eigenvalue in Wishart Random Matrices
• Maximal Height Scaling of Kinetically Growing Surfaces
• Exact distribution of the maximal height of p vicious walkers
• Statistical Mechanics of Logarithmic REM: Duality, Freezing and Extreme Value Statistics of $1/f$ Noises generated by Gaussian Free Fields
• Extreme Value Statistics of Hierarchically Correlated Variables: Deviation from Gumbel Statistics and Anomalous Persistence
• Statistics at the tip of a branching random walk and the delay of traveling waves
• Convex Hull of N Planar Brownian Motions: Exact Results and an Application to Ecology
• Exact solutions for the statistics of extrema of some random 1D landscapes, Application to the equilibrium and the dynamics of the toy model
• On the time to reach maximum for a variety of constrained Brownian motions
• Non-intersecting Brownian Interfaces and Wishart Random Matrices
• Precise Asymptotics for a Random Walker's Maximum
• Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
• On the area under a continuous time Brownian motion till its first-passage time
• Extreme Value Statistics and Traveling Fronts: Various Applications
• Breaking records in the evolutionary race
• Universal Asymptotic Statistics of Maximal Relative Height in One-dimensional Solid-on-solid Models
• Extreme value problems in Random Matrix Theory and other disordered systems
• Density of near-extreme events
• Traveling Waves, Front Selection, and Exact Nontrivial Exponents in a Random Fragmentation Problem
• Extreme value statistics from the Real Space Renormalization Group: Brownian Motion, Bessel Processes and Continuous Time Random Walks
• Maximal height statistics for 1/f^alpha signals
• Records in a changing world
• Exact Asymptotic Results for a Model of Sequence Alignment
• Condensation and Extreme Value Statistics
• Unified Solution of the Expected Maximum of a Random Walk and the Discrete Flux to a Spherical Trap
• Extremal Paths on a Random Cayley Tree
• Statistics of extremal intensities for Gaussian interfaces
• Extreme statistics for time series: Distribution of the maximum relative to the initial value
• Extremal properties of random trees
• The longest excursion of stochastic processes in nonequilibrium systems
• Exact Minimum Eigenvalue Distribution of an Entangled Random Pure State
• Extreme statistics of complex random and quantum chaotic states
• A record-driven growth process
• Distribution of the time at which the deviation of a Brownian motion is maximum before its first-passage time
• Universal Extremal Statistics in a Freely Expanding Jepsen Gas
• Statistical Properties of the Final State in One-dimensional Ballistic Aggregation
• Exact solution of a model of time-dependent evolutionary dynamics in a rugged fitness landscape
• The longest excursion of fractional Brownian motion : numerical evidence of non-Markovian effects
• Probability distribution of the maximum of a smooth temporal signal
• Statistical properties of single-file diffusion front
• Crowding at the Front of the Marathon Packs
• Maximum relative height of one-dimensional interfaces : from Rayleigh to Airy distribution
• Sylvester's question and the Random Acceleration Process
• Contest based on a directed polymer in a random medium
• Multiparticle random walks
• Probability distribution of the sizes of largest erased-loops in loop-erased random walks
• The mean perimeter of some random plane convex sets generated by a Brownian motion

Cited by in corpus (59)

• Extreme value statistics of correlated random variables: a pedagogical review
• Universal First-passage Properties of Discrete-time Random Walks and Levy Flights on a Line: Statistics of the Global Maximum and Records
• Spatial extent of an outbreak in animal epidemics
• Generalised `Arcsine' laws for run-and-tumble particle in one dimension
• The convex hull of the run-and-tumble particle in a plane
• Extremal statistics of curved growing interfaces in 1+1 dimensions
• Distribution of the time at which N vicious walkers reach their maximal height
• Mean perimeter and area of the convex hull of a planar Brownian motion in the presence of resetting
• Distribution of the time of the maximum for stationary processes
• Time between the maximum and the minimum of a stochastic process
• Unravelling intermittent features in single particle trajectories by a local convex hull method
• Distribution of the Time Between Maximum and Minimum of Random Walks
• 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
• Time to reach the maximum for a stationary stochastic process
• Maximum of N Independent Brownian Walkers till the First Exit From the Half Space
• Mean area of the convex hull of a run and tumble particle in two dimensions
• Discrete Sampling of Extreme Events Modifies Their Statistics
• Learning in High Dimension Always Amounts to Extrapolation
• Survival probability of a Brownian motion in a planar wedge of arbitrary angle
• Convex hulls of random walks and their scaling limits
• Generating discrete-time constrained random walks and Lévy flights
• Convex hull of a Brownian motion in confinement
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Roots of random polynomials whose coefficients have logarithmic tails
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Smoluchowski flux and Lamb-Lion Problems for Random Walks and Lévy Flights with a Constant Drift
• Generating stochastic trajectories with global dynamical constraints
• Exact distributions of cover times for $N$ independent random walkers in one dimension
• The convex hull of a planar random walk: perimeter, diameter, and shape
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Generating constrained run-and-tumble trajectories
• Last-passage time for linear diffusions and application to the emptying time of a box
• Slow Kinetics of Brownian Maxima
• Mean perimeter of the convex hull of a random walk in a semi-infinite medium
• Extreme-value statistics from Lagrangian convex hull analysis for homogeneous turbulent Boussinesq convection and MHD convection
• Estimating the probability that a given vector is in the convex hull of a random sample
• Generalized arcsine laws for a sluggish random walker with subdiffusive growth
• 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
• Convex hull of n planar Brownian paths: an exact formula for the average number of edges
• Algebraic and arithmetic area for $m$ planar Brownian paths
• Random Gaussian Tetrahedra
• Iterated-logarithm laws for convex hulls of random walks with drift
• Exact joint distributions of three global characteristic times for Brownian motion
• First-passage and extreme value statistics for overdamped Brownian motion in a linear potential
• Large deviations of a random walk model with emerging territories
• Capturing, Ordering and Gaussianity in 2D
• A Decomposition Algorithm for Nested Resource Allocation Problems
• Convex hulls of random walks: Expected number of faces and face probabilities
• More on the convergence of Gaussian convex hulls
• Errata and Addenda to Mathematical Constants
• Convex hulls of planar random walks
• On sequences of convex records in the plane
• On the convex hull of symmetric stable processes
• On convex hull of Gaussian samples
• Survival probability of random walks leaping over traps
• On the asymptotic of convex hulls of Gaussian fields