Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

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

## Satya N. Majumdar

Random Walks
• 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 Hulls

# 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

# 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
Results

# 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)

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

Use a spacebar or arrow keys to navigate