Source-linked AI summary
Distributions of Angles in Random Packing on Spheres
Tony Cai, Jianqing Fan, Tiefeng Jiang
TL;DR
The paper asks how pairwise angles behave among many random unit vectors when n grows while dimension is fixed or growing. It derives empirical and extreme-angle laws, showing Gaussian normalized angles and concentration near π/2 in high dimensions, while identifying scope limits for some asymptotic approximations.
Problem
The paper studies the empirical and extreme laws of pairwise angles among many random unit vectors, including their implications for spurious correlations and isotropy testing.
Method
The authors analyze pairwise-angle distributions for independent uniform points on a sphere in fixed- and growing-dimension regimes, including empirical and extreme statistics.
Results
In growing dimensions, the normalized empirical angle distribution is Gaussian and most angles concentrate around π/2; fixed dimensions yield explicit empirical and extreme laws.
Takeaways & Limitations
The results rigorously characterize near-orthogonality in high dimensions and provide angle-based quantities for statistical testing and measuring spurious correlations.
Takeaways & Limitations
The asymptotic distribution of Θmax + Θmin −π when both n and p grow is left for future work, and the fixed-dimension Θmin approximation is poor when p is comparable with n.
Abstract
from arXiv · showhide
This paper studies the asymptotic behaviors of the pairwise angles among n randomly and uniformly distributed unit vectors in R^p as the number of points n -> infinity, while the dimension p is either fixed or growing with n. For both settings, we derive the limiting empirical distribution of the random angles and the limiting distributions of the extreme angles. The results reveal interesting differences in the two settings and provide a precise characterization of the folklore that "all high-dimensional random vectors are almost always nearly orthogonal to each other". Applications to statistics and machine learning and connections with some open problems in physics and mathematics are also discussed.
1 Introduction
The paper analyzes empirical and extreme distributions of pairwise angles among many independent uniform points on a sphere, covering both fixed and growing dimensions. It connects these results to near-orthogonality, statistical applications, and geometric problems.
- Scope: The study examines empirical and extreme laws of pairwise angles among independent uniformly distributed points on the unit sphere as n grows, with p fixed or growing.It considers the empirical distribution together with the minimum, maximum, and sum of the two extreme angles.
- Main results: For fixed p, the empirical distribution µn converges to a distribution with a density determined by the angle law.The paper states this convergence as n →∞ and introduces the corresponding density.
- Main results: For growing p, the normalized empirical distribution µn,p is Gaussian, with most angles concentrated around π/2.This gives a precise description of the nearly orthogonal behavior of high-dimensional random vectors.
- Main results: The limiting distributions of Θmin and Θmax, and of Θmin + Θmax, are derived in both fixed- and growing-dimension settings.The sum of the two extreme angles is highly concentrated at π.
- Applications: The angle laws can support tests of spherical symmetry and quantify maximum spurious correlations among random data points.The minimum angle is also connected to upper quantiles of spurious correlations and to sparse-recovery regularity conditions.
- Connections: The results connect random-angle behavior with sphere-packing and particle-configuration problems, as well as random-matrix coherence.The paper discusses links to deterministic problems in physics and mathematics and to coherence of random matrices.
2 When The Dimension p Is Fixed
For fixed dimension, the empirical law of pairwise angles converges to the single-angle density, while the smallest and largest angles approach 0 and π. Simulations illustrate concentration near π/2 and the behavior of the extreme-angle sum.
- Empirical law: As n →∞ with fixed p, µn converges almost surely to the density of an individual pairwise angle Θij.Although the angles are dependent, their average asymptotically has the same density as Θ12.
- Empirical law: For p = 2, h(θ) is uniform on [0, π], whereas for p > 2 it is unimodal with mode π/2.The concentration around π/2 strengthens as p grows.
- Empirical law: As p grows, almost all angles approach π/2 at rate √p.Figure 1 shows the corresponding densities becoming close to the normal density as p increases.
- Extreme laws: For fixed p, n^2/(p−1)Θmin and n^2/(p−1)(π −Θmax) converge weakly to limiting extreme-angle distributions.Thus Θmin approaches zero and Θmax approaches π as n grows.
- Simulation evidence: For n = 50, simulations with p = 2, 3, and 30 show close finite-sample agreement for empirical distributions, while p = 30 poorly approximates the asymptotic law of Θmin.When p = 30, Θmin does not even tend to zero in the simulation setting because p is comparable with n.
- Extreme laws: The limiting law of Θmax + Θmin −π is the difference of two independent identically distributed extreme limits and is symmetric.Consequently, the sum is larger or smaller than π equally likely in the limiting description.
3 When Both n and p Grow
When both n and p grow, the normalized empirical angle distribution converges to Gaussian, while extreme-angle limits depend on the growth regime of p relative to log n.
- Empirical law: The normalized empirical distribution µn,p converges almost surely to N(0, 1) whenever p grows with n.This conclusion holds regardless of the relative growth speed of p and n.
- Extreme laws: In the sub-exponential regime, both extreme angles converge in probability to π/2 and have an extreme-value limit after normalization.Theorem 5 uses the normalization 2p log sin Θmin + 4 log n − log log n.
- Extreme laws: In the exponential regime, Θmin and Θmax converge to different constants determined by β = lim(log n)/p rather than to π/2.Theorem 6 gives distinct limiting behavior for the two extremes when β ∈ (0, ∞).
- Extreme laws: In the super-exponential regime, the extreme-angle limits and their normalizations differ again, with Θmax approaching π.Across the three regimes, Θmax increases as β increases, with limits π/2, a β-dependent value in (π/2, π), and π.
- Proof strategy: The paper derives asymptotic extreme laws using Chen–Stein analysis because the pairwise correlations are dependent rather than i.i.d.The proofs modify coherence results and analyze maxima and minima of the pairwise quantities.
4 Applications to Statistics
The angle laws support statistical tests for spherical symmetry and quantify spurious correlations, while the proposed packing test does not detect gaps in spherical data and requires further null-distribution work for an alternative statistic.
- Spherical symmetry testing: The paper applies the empirical and minimum-angle statistics to test whether data are spherically symmetric in R^p.Under the null, normalized observations are uniformly distributed on the sphere, and unusually small Θmin motivates rejection.
- Simulation study: The packing test is evaluated by rejection percentages from 2000 simulations across six data-generating distributions.For Distribution 0, the reported power corresponds to the test size and is slightly below α = 5%.
- Test scope: The packing test does not examine whether the spherical data contain a gap.The paper identifies the empirical distribution µn or normalized µn,p as alternative statistics for this purpose.
- Test scope: A Kolmogorov–Smirnov distance between µn and h(θ) is proposed as an alternative, but its null distribution is left for future work.Deriving that null distribution is beyond the paper’s scope.
- Spurious correlation: The minimum angle quantifies the largest spurious correlation among random variables, including correlations arising purely by chance.For p = 30 and n = 50, the paper reports a spurious correlation as large as 0.615.
- Spurious correlation: Spurious correlation also contributes to underestimating residual variance in sparse linear models by a factor of 1 − cos^2(Θmin).The asymptotic result gives the order of magnitude of this bias.
5 Discussions
The paper connects random-angle laws to machine-learning problems and deterministic optimization questions in mathematics and physics. These connections include geometric random graphs, isotropy and clique detection, PCA, and randomized study of spherical energy configurations.
- Connections to Machine Learning: Random geometric graphs connect sphere-angle thresholds to edge counts, vertex degrees, and implanted-clique detection.Vertices are random points on the p-dimensional unit sphere, with an edge when Θij > δ.
- Connections to Machine Learning: The angle results are related to hypothesis testing for isotropic covariance matrices through connections with geometric random-graph clique numbers.
- Connections to Machine Learning: PCA provides a high-dimensional statistical setting where understanding principal eigenvectors of sample covariance matrices is central.The paper discusses this alongside prior work on asymptotic conical structure.
- Connections to Some Open Problems in Mathematics and Physics: The random-angle results can potentially be used to study open deterministic problems in mathematics and physics.
- Connections to Some Open Problems in Mathematics and Physics: The cited spherical optimization problems vary with α and include the Tammes, Thomson, maximum average distance, and maximal product-of-distances problems.The α = 0 problem is identified as one of Smale’s 17 challenging mathematics problems.
- Connections to Some Open Problems in Mathematics and Physics: Random sampling approximates the essential upper bound of Θmax, providing a stochastic route to deterministic spherical-configuration problems.The discussion links this approach to extremal energy problems, including the Tammes, Thomson, maximum average distance, and maximal product-of-distances problems.
6 Proofs
The proofs establish the angle laws from pairwise independence and spherical symmetry, then apply weak-convergence and extreme-value arguments in fixed and growing dimensions. They obtain almost-sure empirical limits and limiting distributions for the extreme angles.
- Technical foundations: Pairwise angles are identically distributed and pairwise independent, and the same holds after replacing each angle by its supplement.This follows from the Gaussian representation of uniform spherical points and the monotonic transformation ρij = cos Θij.
- Empirical laws: For fixed dimension, the empirical angle distribution converges almost surely to the density h(θ) stated in Theorem 1.The result is obtained by applying the general empirical-convergence lemma with ϕn(θ) = θ.
- Empirical laws: For growing dimension, a dependency-neighborhood argument controls the pairwise-angle empirical process and yields almost-sure convergence after normalization.The proof combines a local-dependence bound with Markov’s inequality and Borel–Cantelli.
- Growing dimension: The growing-dimension extreme analysis shows both Θmin and Θmax converge in probability to π/2, with refined extreme-value limits for their normalized deviations.The argument derives the upper and lower extremes from corresponding correlation limits and symmetry.