Convex Hulls of Random Walks in High Dimensions:
A Large-Deviation Study

Hendrik Schawe

Alexander K. Hartmann

Satya N. Majumdar

position $\vec{x}(t)$ is sum of random Gaussian steps $\vec\delta_i$ $$\vec x(t) = \sum_{i=1}^t \vec\delta_i, \quad t \le T$$
same asymptotics when on a lattice
scales as $r \propto T^{\nu}, \nu=1/2$
model for diffusion/Brownian motion
simple model for animal movement

1/12

$T=500$

2/12

Convex Hull of a point set

smallest convex polytope around points $$\{x(t) | t \in \{0, .., T\}\}$$

$\Omega(T^{\left \lfloor d/2 \right \rfloor})$
Divide and Conquer:
Quickhull^[1]

[1] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, ACM TOMS 22, 469 (1996)

3/12

$T=500$

4/12

characterizes a random walk

$\partial V$ surface
$V$ volume

e.g. home ranges of animals in $d=2$
mean values known for $T\to\infty$^[2] $$\left< V \right> / T^{d/2} = \left( \frac{\pi}{2} \right)^{d/2} \Gamma \left( \frac{d}{2} + 1 \right)^{-2}$$
we will look at their full distribution

[2] R. Eldan, Electron. J. Probab. 19, 45 (2014)

5/12

Sampling the Distribution

Simple sampling works only for high $P$
What about the $P \ll 10^{-100}$ tails?

(modified^[4]) Wang Landau sampling^[3]
accept with Metropolis probabilty

$$p_\mathrm{acc}(S_i \to S_{i+1}) = \min\left(\frac{g(S_{i})}{g(S_{i+1})}, 1\right)$$

iteratively adapt $g$ $\to$ flat histogram

[3] F. Wang and D. P. Landau, Phys. Rev. Lett. 86, 2050 (2001)
[4] R. E. Belardinelli and V. D. Pereyra, Phys. Rev. E 75, 046701 (2007)

6/12

7/12

classical^[3]:
- $\ln g_{i+1} = \ln g_{i} + f$
- $f \mapsto f/2$ after every histogram reset
modifying $g$ $\to$ no detailed balance
to reduce systematic error, different schedule^[4] ($t$ is Monte Carlo time)
$\ln g_{i+1} = \ln g_{i} + t^{-1}$

[3] F. Wang and D. P. Landau, Phys. Rev. Lett. 86, 2050 (2001)
[4] R. E. Belardinelli and V. D. Pereyra, Phys. Rev. E 75, 046701 (2007)

8/12

Distribution

$d=4$

9/12

Scaling

Observables scale as $T^{d/2}$ with their effective dimension.

Here $d=4$ dimensional hypervolume $V$.

10/12

$$\widetilde{S}^{(d-1)/d} \mathrm{e}^{-b\widetilde{S}^{2/d}}$$ from the distribution of the $d=1$ span

G. Claussen, A. K. Hartmann, and S. N. Majumdar, Phys. Rev. E 91, 052104 (2015)

Left Tail

11/12

Conclusion

The large deviation properties of the $d=1$ span of random walks seem to be easily extended to larger $d$.

Outlook

Multiple Walks
Self-Interacting Walks (SAW, LERW, ...) Poster session DY 60.1 on Thursday

12/12