Concentration of Volume in High Dimensional Spheres: A Dice Thrower's Interpretation

#math/PR

Abstract.

A review and proof of the mathematics of concentration of volume to near the surface in high-dimensional spheres. In particular, an intuitive probabilistic perspective based on collections of dice.

Introduction

The Dice Thrower’s Perspective

Let’s explore this concept from a dice thrower’s perspective, the probabilistic interpretation of rolling pools of dice and examining the highest result: roll nn six-sided dice nd6n\textrm{d}6 and consider the roll a success if any die shows the high possible value: a six. We intuitively know that rolling more dice, increasing nn. Mathematically we write this as:

p(success;n)=1−(56)n.p(\textrm{success}; n) = 1 - \left(\frac{5}{6}\right)^n.

Extension to nn dice with kk sides

More generally roll nn kk-sided dice and consider the roll a success if at least one die shows a kk.

p(success;n)=1−(k−1k)n,p(\textrm{success}; n) = 1 - \left(\frac{k - 1}{k}\right)^n,

which can be envisioned as an nn-dimensional cube of side length kk. Highlight the shell of the cube: where xi=kx_i=k, for some i∈{1,...,n}i\in\{1, ..., n\}. With two parameters we can consider multiple limits:

For fixed kk as n→∞n\to\infty:

(k−1k)n→0.\left(\frac{k - 1}{k}\right)^n \to 0.

For fixed nn as k→∞k\to\infty:

(k−1k)n→1.\left(\frac{k - 1}{k}\right)^n \to 1.

Next, we can learn a lot about our system by considering the multi-scale limit: k=k(m)k = k(m) and n=n(m)n = n(m) as m→∞m\to\infty. By continuity of the exponential, let’s first transform the problem:

lim⁡m→∞(k(m)−1k(m))n(m)=lim⁡m→∞exp⁡(log⁡(k(m)−1k(m))n(m))=exp⁡lim⁡m→∞n(m)⋅log⁡(k(m)−1k(m)),\begin{align*} \lim_{m\to\infty} \left(\frac{k(m) - 1}{k(m)}\right)^{n(m)} =& \lim_{m\to\infty} \exp\left(\log\left(\frac{k(m) - 1}{k(m)} \right)^{n(m)} \right) \\ =& \exp\lim_{m\to\infty} n(m) \cdot \log\left(\frac{k(m) - 1}{k(m)} \right), \end{align*}

and we’ll focus on the limit:

lim⁡m→∞L(k,n;m)=lim⁡m→∞n(m)⋅log⁡(k(m)−1k(m)).\lim_{m\to\infty}{\mathcal L}(k, n; m) = \lim_{m\to\infty} n(m) \cdot \log\left(\frac{k(m) - 1}{k(m)} \right).

The previously considered limits: constant kk and constant nn are special cases of this limit and provides an interesting nugget of intuition. For constant k(m):=k∗k(m) := k^* and n(m):=mn(m) := m, lim⁡m→∞L(k∗,m;m)=∞\lim_{m\to\infty}{\mathcal{L}(k^*, m; m)} = \infty, but we don’t learn how quickly this limit diverges. Of course, a quick look at the definition of L(k,n;m){\mathcal L}(k, n; m) shows that it diverges linearly. To show this rigorously, one considers not lim⁡m→∞L\lim_{m\to\infty}{\mathcal L}, but instead:

lim⁡m→∞L(k∗,m;m)m=log⁡k∗−1k∗=C (a constant).\lim_{m\to\infty}\frac{\mathcal L(k^*, m; m)}{m} = \log\frac{k^* - 1}{k*} = C \textrm{ (a constant)}.

Similarly for the constant nn case: n(m)=n∗n(m) = n^* and k(m)=mk(m) = m, lim⁡m→∞L(m,n∗;m)=0\lim_{m\to\infty}{\mathcal{L}(m, n^*; m)} = 0, the philosophical counterpart to ∞\infty; again, hiding the convergence rate in the sinkhole of information that is 00 (or ∞\infty):

lim⁡m→∞m⋅L(n∗,m;m)=n∗lim⁡m→∞mlog⁡(m−1m)=−n∗=C′.\lim_{m\to\infty} m \cdot {\mathcal L(n^*, m; m)} = n^* \lim_{m\to\infty} m \log\left(\frac{m - 1}{m}\right) = -n^* = C'.

This all guides us to selecting a multi-scale limit procedure for kk and nn simultaneously, and if we choose the correct relative scaling. Let k(m)=mk(m) = m and n(m)=mn(m) = m. Let’s temporarily detour returning directly to the dice-rolling setting with a numerical experiment. For

However, how many sides to the dice would give us approximately the same rate of success? We can answer this by solving

1−(k−1k)2≈16.1 - \left(\frac{k - 1}{k}\right)^2 \approx \frac{1}{6}.

This may not have an integer solution, so we will take the integer valued kk which gives at least 16\frac{1}{6} rate of success. This gives us

56=k−1k  ⟹  1=(1−(56)12)k  ⟹  k=11−(56)12≈11.48  ⟹  k∗=⌊11−(56)12⌋=11.\begin{split} & \sqrt{\frac{5}{6}} = \frac{k - 1}{k} \\ &\implies 1 = \left(1 - \left(\frac{5}{6}\right)^{\frac{1}{2}}\right) k \\ &\implies k = \frac{1}{1 - \left(\frac{5}{6}\right)^{\frac{1}{2}}} \approx 11.48 \\ &\implies k^* = \left\lfloor{\frac{1}{1 - \left(\frac{5}{6}\right)^{\frac{1}{2}}} }\right\rfloor = 11. \end{split}

Generally, we have

k∗=⌊11−(56)1/n⌋k^* = \left\lfloor \frac{1}{1 - \left(\frac{5}{6}\right)^{1/n}} \right\rfloor

Rigor

If this is the correct relative scaling, lim⁡m→∞L(m,m)=C\lim_{m\to\infty}{\mathcal L}(m, m) = C with 0<∣C∣<∞0 < |C| < \infty

lim⁡m→∞L(m,m)=lim⁡m→∞m⋅log⁡m−1m=−1\lim_{m\to\infty} {\mathcal L}(m , m) = \lim_{m\to\infty} m \cdot \log\frac{m - 1}{m} = -1