Random cones in high dimensions I: Donoho-Tanner and Cover-Efron cones

Random cones in high dimensions I: Donoho-Tanner and Cover-Efron cones, Discrete Analysis 2020:5, 44 pp.

As its title makes clear, this paper is about random high-dimensional cones. A cone in $\mathbb R^d$ is a subset that is closed under addition and under multiplication by non-negative scalars. To define a random cone is less easy, since there is no single way of defining a probability measure on the set of all cones that stands out as being the most natural.

Such a situation can be regarded as an opportunity: one can try to find definitions that lead to interesting questions. One obvious randomized method of obtaining a cone in $\mathbb R^d$ is to pick $n$ vectors $v_1,\dots,v_n$ independently at random from some distribution on $\mathbb R^d$ and to take the cone that they generate. And an obvious distribution to take is the standard Gaussian distribution.

There is also the question of which $n$ to take. If $n$ is smaller than $d$, then the cone will not be of full dimension, and if $n$ is significantly larger than $d$, then with high probability it will be the whole of $\mathbb R^d$.

More precisely, a theorem of Schläfi from the 19th century gives that $n$ hyperplanes through the origin but otherwise in general position divide $\mathbb R^d$ into $C(n,d)=2\sum_{i=0}^{d-1}\binom{n-1}i$ regions. If the normal vectors are $v_1,\dots,v_n$, then each region is of the form $\{x:\forall i\ \langle x,\epsilon_iv_i\rangle>0\}$ for some choice of signs $\epsilon_1,\dots,\epsilon_n$. It follows that there are precisely $C(n,d)$ choices of signs $\epsilon_1,\dots,\epsilon_n$ for which there exists $x$ such that $\langle x,\epsilon_iv_i\rangle>0$.

It follows that if $v_1,\dots,v_n$ are any $n$ vectors in general position and $\epsilon_1,\dots,\epsilon_n$ are random signs, then the probability that there is a hyperplane such that all the vectors $\epsilon_iv_i$ lie on one side of the hyperplane is $C(n,d)/2^n$. And from that it follows that if $v_1,\dots,v_n$ are chosen independently at random from a distribution that is centrally symmetric and absolutely continuous with respect to Lebesgue measure, then the probability that they lie to one side of a hyperplane, and therefore generated a non-trivial cone, is also $C(n,d)/2^n$.

This implies that there is an important change when $n$ passes $2d$. If $d=\delta n$ for some $\delta<1/2$. then $C(n,d)/2^n$ is exponentially small, so the cone generated by $v_1,\dots,v_n$ is all of $\mathbb R^d$ with extremely high probability, whereas if $\delta>1/2$ then $1-C(n,d)/2^n$ is exponentially small, so the cone is almost certainly proper.

This threshold has been shown to be a phase transition for a number of important parameters associated with random cones. What is achieved in this paper is a set of much more precise results concerning how the changes take place over the “critical window” – that is, how the parameters depend on $c$ if $n=2d+c\sqrt d+o(\sqrt d)$.

The Donoho-Tanner random cones in the title are the ones just described. The Cover-Efron cones are ones where one conditions on the cone not being all of $\mathbb R^d$. The authors prove results for both models. One of the parameters they investigated is the number of faces of dimension $k$ for small $k$. This was known to be around $\binom nk$ if $\delta>1/2$ and around $(2\delta)^k\binom nk$ if $\delta<1/2$, but the authors provide a formula for the dependence on $c$ in the critical window (which in the case of the Donoho-Tanner random cones turns out to be given by the cumulative distribution function of a normal distribution). They also look at quermassintegrals: the $k$th quermassintegral of a random cone is the probability that it intersects non-trivially with a random subspace of codimension $k$.

Previous work in this area has tended to rely on detailed estimates for sums of binomial coefficients (as the simple argument given earlier exemplifies). The main idea that enables the authors to go beyond this is to interpret the quantities they are looking at in terms of binomial random variables, which allows them to make use several less elementary probabilistic tools.