Distributions of convex hulls of random walks
Final Report Abstract
The measurement of the territories of animals can be achieved by using tracking data of animal paths. After stripping outliers, the calculation of the convex hull, i.e., the smallest convex set containing the visited locations, gives a good impression of the territory, its area and its perimeter. Since in the most simple approximation, animal paths are given by random walks, the study of convex hulls of random walks has become a subject of interest in mathematics and statistical physics. Naturally, different variants like walks in higher dimensions and different types of random walks, e.g. with self avoidance or multiple walks have been studied. For all this previous work, only results for the behaviour of the mean area (or volume in higher dimensions) and of the mean perimeter (surface) have been calculated. No results concerning the distribution had been available. Since only obtaining the full distribution reveals the full nature of a stochastic process, it was the aim of this project to obtain the distribution of volume and surface of the convex hull of various types of walks by numerical simulations. Nevertheless, by applying standard simulation, i.e., repeating many times independent simulations of the walks and determining the convex hull, one can access only a minor part of the distribution, where the probabilities are not smaller than, say, 10^−9 . In contrast, in the present project, we addressed numerically the full probability distributions by developing and implementing large-deviation algorithms. They work by sampling the space of walks with biased probabilities, where one can shift the focus of the algorithm, controlled by some parameter resembling a temperature in physics, to regions of interest. Since this bias is controlled, we can recover the true probabilities in the end. By using many different values of the temperatures, we can address different regions, and “glue” the different distributions together to finally obtain (almost) the full distribution, covering probabilities from larges values P ∼ O(1) down to values such as P ∼ O(10^−300 ) or smaller. Beyond obtaining the distributions, we were able to compare them between different dimension and different types of walks. Our results show that the shape of the distributions, over hundreds of decades in probability, can be related to the result for the one-dimensional simple random walk by suitable rescaling. Thus, the distribution is in a sense universal, a quite surprising result. This rescaling only has to take into account the dimension d of the system and the exponent ν which describes the grow of the end-to-end distance r of the walk on the walk duration T via r ∼ T ν . Note that for a standard random walk ν = 1/2 holds, while self interactions can lead to higher values. We also applied our approach for a model of walks, which is closer to actual animal behaviour, because the model considers animals which mark their traces by scents and try to avoid the scents of other animals. We found that the typical behaviour of the convex hulls for the biologically-realistic model differs much from the behaviour observed for random walks. On the other hand, the tail, i.e. the region of small probabilities, appear to be very similar. Since we gathered in this project a lot of technical expertise in large-deviation algorithms, we used similar approaches to study other models where it is of interest to observe corresponding probability distribution over a large range of the support. In particular we studied ground states of non-interacting fermions, the length of longest increasing subsequences and the sizes of the largest connected and of the largest biconnected components for various models of random graphs.
Publications
- Convex hulls of multiple random walks: a large-deviation study, Phys. Rev. E 94, 052120 (2016)
T. Dewenter, G. Claussen, A.K. Hartmann, and S.N. Majumdar
(See online at https://doi.org/10.1103/PhysRevE.94.052120) - Convex hulls of random walks in high dimensions: a large-deviation study, Phys. Rev. E 96, 062101 (2017)
H. Schawe, A.K. Hartmann, and S.N. Majumdar
(See online at https://doi.org/10.1103/PhysRevE.96.062101) - Ground state energy of noninteracting fermions with a random energy spectrum, Europhys. Lett. 124, 40005 (2018)
H. Schawe, A.K. Hartmann, S.N. Majumdar, and G. Schehr
(See online at https://doi.org/10.1209/0295-5075/124/40005) - Large deviations of convex hulls of self-avoiding random walks, Phys. Rev. E 97, 062159 (2018)
H. Schawe, A.K. Hartmann, and S.N. Majumdar
(See online at https://doi.org/10.1103/PhysRevE.97.062159) - Large deviations of convex hulls of ”true” self avoiding walks, J. Phys. Conf. Ser. 1290, 012029 (2019)
H. Schawe and A.K. Hartmann
(See online at https://doi.org/10.1088/1742-6596/1290/1/012029) - Large deviations of the length of the longest increasing subsequence of random permutations and random walks, Phys. Rev. E 99, 042104 (2019)
J. Börjes, H. Schawe, and A.K. Hartmann
(See online at https://doi.org/10.1103/PhysRevE.99.042104) - Large-deviation properties of the largest biconnected components for random graphs, Eur. Phys. J. B 92, 73 (2019)
H. Schawe and A.K. Hartmann
(See online at https://doi.org/10.1140/epjb/e2019-90667-y) - Convex hull of run-and-tumble particle, JSTAT 2020, 053401 (2020)
A.K. Hartmann, S.N. Majumdar, H. Schawe and G. Schehr
(See online at https://doi.org/10.1088/1742-5468/ab7c5f) - Large deviations of a random walk model with emerging territories, Phys. Rev. E 102, 062141 (2020)
H. Schawe and A.K. Hartmann
(See online at https://doi.org/10.1103/PhysRevE.102.062141) - On the asymptotic behaviour of the length of the longest increasing subsequences of random walks, Phys. Rev. E 101, 032102 (2020)
J.R.G. Mendonca, H. Schawe, and A.K. Hartmann
(See online at https://doi.org/10.1103/PhysRevE.101.032102)
