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

The distribution of the hypervolume $V$ and surface $\partial V$ of convex hulls of (multiple) random walks in higher dimensions are determined numerically, especially containing probabilities far smaller than $P={10}^{-1000}$ to estimate large deviation properties. For arbitrary dimensions and large walk lengths $T$, we suggest a scaling behavior of the distribution with the length of the walk $T$ similar to the two-dimensional case and behavior of the distributions in the tails. We underpin both with numerical data in $d=3$ and $d=4$ dimensions. Further, we confirm the analytically known means of those distributions and calculate their variances for large $T$.

Figure 1

Examples for Gaussian random walks in $d=2$ and $d=3$. Their convex hull is visualized in red. (a) $d=2,T=2048$ and (b) $d=3,T=2048$.

Figure 2

Visualization of (a) the idea to calculate the volume of a convex polygon given its facets and an interior point, perpendicular distances are shown with dashed lines. In (b) and (c) examples of two consecutive recursive steps of the quickhull algorithm are shown. The point $d$ is left of and farthest away from $(a,c)$. Parts of the convex hull are black, discarded points are light gray.

Figure 3

Scaled mean of the surface ${\mu }_{\partial V}=〈\partial V〉/T^{(d-1)\nu }$ (open symbols) and volume ${\mu }_V=〈V〉/T^{d\nu }$ (solid symbols) for different dimensions (different shapes) and walk lengths $T$ obtained by ${10}^6$ samples each. Lines are fits [cf. Eq. (8)] to extrapolate for $T\to \infty$. Crosses are exact values [cf. Eq. (4)] and show very good agreement with the extrapolation. The asymptotic values are shown in Table 1. Fits disregard small walk lengths for higher dimensions, since the expansion is valid for large $T$. To be precise, the fit ranges are $d\ge 5$: $T\ge 256$ for the surface and $d\ge 5$: $T\ge 512$ for the volume. They are chosen such that ${\chi }_{\mathrm{red}}^2$ reaches a plateau, i.e., does not change significantly if even larger $T$ are ignored (same ranges for the variances). The goodness of fit ${\chi }_{\mathrm{red}}^2$ is between 0.3 and 1.2 for all fits. Error bars are smaller than the line of the fit.

Figure 4

Distribution of the volume of a $d=4$ RW for different system sizes $T$. The inset shows the peak region in linear scale.

Figure 5

Distributions of the surface (top) and volume (bottom) for $d\in \{3,4\}$ scaled according to Eq. (9). Statistical errors are smaller than the symbols. The scaling indeed collapses the distributions on one scaling function $\tilde{P}$. Fits are shown for the largest system size. The inset shows the peak region in linear scale. For larger values of $T$ the collapse works better. (Only a small fraction of all data points are visualized.) (a) $d=3,\tilde{S}>500,b_r=1.56,{\chi }_{\mathrm{red}}^2=2.5$, (b) $d=4,\tilde{S}>200,b_r=6.33,{\chi }_{\mathrm{red}}^2=1.2$, (c) $d=3,\tilde{S}>500,b_r=10.61,{\chi }_{\mathrm{red}}^2=0.8$, and (d) $d=4,\tilde{S}>2500,b_r=26.60,{\chi }_{\mathrm{red}}^2=1.1$.

Figure 6

Fit of the exponential Eq. (10) to the left tail. Note, that the prefactor is constant in this case (for clarity, only every tenths data point is plotted).

Figure 7

Point-wise extrapolation of the value of the rate function at a fixed value $V/T^d$ to $T\to \infty$ with a power law, here for a $d=4$-dimensional volume. The power-law fit seems to be a reasonable approximation.

Figure 8

Rate function of the distribution of the $d=4$-dimensional volume of the convex hull of RWs for different walk lengths $T$. Crosses mark the $T\to \infty$ extrapolated values of the asymptotic rate function as shown in Fig. 7. To those a power law is fitted yielding an estimate for the rate function consistent with the guess in Eq. (13). Further, the expected power law behavior of the left tail is approached.