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

• Published in: arXiv.org 2016-05
• Main Authors: Dewenter, Timo, Claussen, Gunnar, Hartmann, Alexander K, Majumdar, Satya N
• Format: Article
• Language: English
• Subjects: Convexity; Deviation; Hulls; Random walk; Scaling
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.1605.06958

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 \rightarrow \infty\), revealing that the densities follow the large-deviation principle. These rate functions can be described by a power law for \(n \rightarrow \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.