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


Hendrik Schawe

Alexander K. Hartmann

Satya N. Majumdar

Random Walks
  • position →x(t) is sum of random Gaussian steps →δi →x(t)=t∑i=1→δi,t≤T
  • same asymptotics when on a lattice
  • scales as r∝Tν,ν=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∈{0,..,T}}
Ω(T⌊d/2⌋)
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
    • ∂V surface
    • V volume
  • e.g. home ranges of animals in d=2
  • mean values known for T→∞[2] ⟨V⟩/Td/2=(π2)d/2Γ(d2+1)−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≪10−100 tails?
    • (modified[4]) Wang Landau sampling[3]
    • accept with Metropolis probabilty
pacc(Si→Si+1)=min(g(Si)g(Si+1),1)
    • iteratively adapt g → 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]:
    • lngi+1=lngi+f
    • f↦f/2 after every histogram reset
  • modifying g → no detailed balance
  • to reduce systematic error, different schedule[4] (t is Monte Carlo time)
  • lngi+1=lngi+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 Td/2 with their effective dimension.
Here d=4 dimensional hypervolume V.
10/12
˜S(d−1)/de−b˜S2/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

Use a spacebar or arrow keys to navigate