Convex hulls of random walks in higher dimensions: A large-deviation study

Large deviations in statistics of the convex hull of passive and active particles: A theoretical study

We investigate analytically the distribution tails of the area A and perimeter L of a convex hull for different types of planar random walks. For N noninteracting Brownian motions of duration T we find that the large-L and -A tails behave as P(L)∼e^{-b_{N}L^{2}/DT} and P(A)∼e^{-c_{N}A/DT}, while the small-L and -A tails behave as P(L)∼e^{-d_{N}DT/L^{2}} and P(A)∼e^{-e_{N}DT/A}, where D is the diffusion coefficient. We calculated all of the coefficients (b_{N},c_{N},d_{N},e_{N}) exactly. Strikingly, we find that b_{N} and c_{N} are independent of N for N≥3 and N≥4, respectively. We find that the large-L (A) tails are dominated by a single, most probable realization that attains the desired L (A). The left tails are dominated by the survival probability of the particles inside a circle of appropriate size. For active particles and at long times, we find that large-L and -A tails are given by P(L)∼e^{-TΨ_{N}^{per}(L/T)} and P(A)∼e^{-TΨ_{N}^{area}(sqrt[A]/T)}, respectively. We calculate the rate functions Ψ_{N} exactly and find that they exhibit multiple singularities. We interpret these as DPTs of first order. We extended several of these results to dimensions d>2. Our analytic predictions display excellent agreement with existing results that were obtained from extensive numerical simulations.

Mean perimeter and area of the convex hull of a planar Brownian motion in the presence of resetting

We compute exactly the mean perimeter and the mean area of the convex hull of a two-dimensional isotropic Brownian motion of duration t and diffusion constant D, in the presence of resetting to the origin at a constant rate r. We show that for any t, the mean perimeter is given by 〈L(t)〉=2πsqrt[D/r]f_{1}(rt) and the mean area is given by 〈A(t)〉=2πD/rf_{2}(rt) where the scaling functions f_{1}(z) and f_{2}(z) are computed explicitly. For large t≫1/r, the mean perimeter grows extremely slowly as 〈L(t)〉∝ln(rt) with time. Likewise, the mean area also grows slowly as 〈A(t)〉∝ln^{2}(rt) for t≫1/r. Our exact results indicate that the convex hull, in the presence of resetting, approaches a circular shape at late times due to the isotropy of the Brownian motion. Numerical simulations are in perfect agreement with our analytical predictions.

Large deviations of a random walk model with emerging territories

We study an agent-based model of animals marking their territory and evading adversarial territory in one dimension with respect to the distribution of the size of the resulting territories. In particular, we use sophisticated sampling methods to determine it over a large part of territory sizes, including atypically small and large configurations, which occur with probability of less than 10^{-30}. We find hints for the validity of a large deviation principle, the shape of the rate function for the right tail of the distribution, and insight into the structure of atypical realizations.

Position distribution in a generalized run-and-tumble process

We study a class of stochastic processes of the type d^{n}x/dt^{n}=v_{0}σ(t) where n>0 is a positive integer and σ(t)=±1 represents an active telegraphic noise that flips from one state to the other with a constant rate γ. For n=1, it reduces to the standard run-and-tumble process for active particles in one dimension. This process can be analytically continued to any n>0, including noninteger values. We compute exactly the mean-squared displacement at time t for all n>0 and show that at late times while it grows as ∼t^{2n-1} for n>1/2, it approaches a constant for n<1/2. In the marginal case n=1/2, it grows very slowly with time as ∼lnt. Thus, the process undergoes a localization transition at n=1/2. We also show that the position distribution p_{n}(x,t) remains time-dependent even at late times for n≥1/2, but approaches a stationary time-independent form for n<1/2. The tails of the position distribution at late times exhibit a large deviation form, p_{n}(x,t)∼exp[-γtΦ_{n}(x/x^{*}(t))], where x^{*}(t)=v_{0}t^{n}/Γ(n+1). We compute the rate function Φ_{n}(z) analytically for all n>0 and also numerically using importance sampling methods, finding excellent agreement between them. For three special values n=1, n=2, and n=1/2 we compute the exact cumulant-generating function of the position distribution at all times t.

Long-time position distribution of an active Brownian particle in two dimensions

We study the late-time dynamics of a single active Brownian particle in two dimensions with speed v_{0} and rotation diffusion constant D_{R}. We show that at late times t≫D_{R}^{-1}, while the position probability distribution P(x,y,t) in the x-y plane approaches a Gaussian form near its peak describing the typical diffusive fluctuations, it has non-Gaussian tails describing atypical rare fluctuations when sqrt[x^{2}+y^{2}]∼v_{0}t. In this regime, the distribution admits a large deviation form, P(x,y,t)∼exp{-tD_{R}Φ[sqrt[x^{2}+y^{2}]/(v_{0}t)]}, where we compute the rate function Φ(z) analytically and also numerically using an importance sampling method. We show that the rate function Φ(z), encoding the rare fluctuations, still carries the trace of activity even at late times. Another way of detecting activity at late times is to subject the active particle to an external harmonic potential. In this case we show that the stationary distribution P_{stat}(x,y) depends explicitly on the activity parameter D_{R}^{-1} and undergoes a crossover, as D_{R} increases, from a ring shape in the strongly active limit (D_{R}→0) to a Gaussian shape in the strongly passive limit (D_{R}→∞).

Large deviations of the length of the longest increasing subsequence of random permutations and random walks

We study numerically the length distribution of the longest increasing subsequence (LIS) for random permutations and one-dimensional random walks. Using sophisticated large-deviation algorithms, we are able to obtain very large parts of the distribution, especially also covering probabilities smaller than 10^{-1000}. This enables us to verify for the length of the LIS of random permutations the analytically known asymptotics of the rate function and even the whole Tracy-Widom distribution. We observe a rather fast convergence in the larger than typical part to this limiting distribution. For the length L of LIS of random walks no analytical results are known to us. We test a proposed scaling law and observe convergence of the tails into a collapse for increasing system size. Further, we obtain estimates for the leading-order behavior of the rate functions in both tails.

Large deviations of convex hulls of self-avoiding random walks

A global picture of a random particle movement is given by the convex hull of the visited points. We obtained numerically the probability distributions of the volume and surface of the convex hulls of a selection of three types of self-avoiding random walks, namely, the classical self-avoiding walk, the smart-kinetic self-avoiding walk, and the loop-erased random walk. To obtain a comprehensive description of the measured random quantities, we applied sophisticated large-deviation techniques, which allowed us to obtain the distributions over a large range of support down to probabilities far smaller than P=10^{-100}. We give an approximate closed form of the so-called large-deviation rate function Φ which generalizes above the upper critical dimension to the previously studied case of the standard random walk. Further, we show correlations between the two observables also in the limits of atypical large or small values.