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

Thomas Godland  Thomas Godland: Institut für Mathematische Stochastik,
Westfälische Wilhelms-Universität Münster, Orléans-Ring 10, 48149 Münster,
Germany<EMAIL_ADDRESS>,  Zakhar Kabluchko  Zakhar Kabluchko:
Institut für Mathematische Stochastik, Westfälische Wilhelms-Universität
Münster, Orléans-Ring 10, 48149 Münster, Germany  zakhar.kabluchko@uni-
muenster.de and  Christoph Thäle  Christoph Thäle: Fakultät für Mathematik,
Ruhr-Universität Bochum, Universitätsstr. 150, 44780 Bochum, Germany
<EMAIL_ADDRESS>
###### Abstract.

Two models of random cones in high dimensions are considered, together with
their duals. The Donoho-Tanner random cone $D_{n,d}$ can be defined as the
positive hull of $n$ independent $d$-dimensional Gaussian random vectors. The
Cover-Efron random cone $C_{n,d}$ is essentially defined as the same positive
hull, conditioned on the event that it is not the whole space. We consider
expectations of various combinatorial and geometric functionals of these
random cones and prove that they satisfy limit theorems, as $d$ and $n$ tend
to infinity in a suitably coordinated way. This includes, for example, large
deviation principles and central as well as non-central limit theorems for the
expected number of $k$-faces and the $k$-th conic intrinsic volumes, as $n$,
$d$ and possibly also $k$ tend to infinity simultaneously. Furthermore, we
determine the precise high-dimensional asymptotic behaviour of the expected
statistical dimension for both models of random cones, uncovering thereby
another high-dimensional phase transition. As an application, limit theorems
for the number of $k$-faces of high-dimensional polytopes generated by random
Gale diagrams are discussed as well.

###### Key words and phrases:

Conic intrinsic volume, conic quermassintegral, Cover-Efron cone, Donoho-
Tanner cone, high dimensions, limit theorem, phase transition, random cone,
random Gale diagram, statistical dimension, stochastic geometry, threshold
phenomenon

###### 2010 Mathematics Subject Classification:

Primary: 52A22, 60D05. Secondary: 52A55, 52A23, 60F05, 60F10

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Limit theorems for binomial random variables and binomial coefficients
    3. 2.3 Convex cones, conic intrinsic volumes and quermassintegrals
  3. 3 Two models of random cones
    1. 3.1 The Donoho-Tanner random cones
    2. 3.2 The Schläfli and Cover-Efron random cones
  4. 4 Limit theorems for the expected face numbers
    1. 4.1 Fixed face-dimension $\boldsymbol{k}$
    2. 4.2 Increasing face-dimension $\boldsymbol{k}$
    3. 4.3 Large deviation principles
    4. 4.4 Application to random Gale diagrams
  5. 5 Limit theorems for the expected conic intrinsic volumes and quermassintegrals
    1. 5.1 Distributional limit theorems for the conic intrinsic volumes
    2. 5.2 Limit theorems for the conic quermassintegrals
    3. 5.3 Large deviation principles
  6. 6 Limit theorems for the expected statistical dimension
    1. 6.1 The Donoho-Tanner random cones
    2. 6.2 The Schläfli and Cover-Efron random cones

##  1\. Introduction

By a polyhedral cone in $\mathbb{R}^{d}$, $d\in\mathbb{N}$, one understands an
intersection of finitely many closed half-spaces whose bounding hyperplanes
all pass through the origin. Thus, a polyhedral cone (in this paper just
called a cone for simplicity, since we only deal with cones of this type) in
$\mathbb{R}^{d}$ is a set of solutions to a finite system of homogeneous
linear inequalities in $d$ variables. In the present paper we are interested
in randomly generated cones, which correspond to the set of solutions of a
finite random system of homogeneous linear inequalities. In the literature two
natural models for random cones have been considered and are in the focus of
part I of the present paper as well. To define them, let $\phi$ be an even
probability measure on $\mathbb{R}^{d}$ which puts zero mass on each
$(d-1)$-dimensional hyperplane. For example, $\phi$ could be the standard
Gaussian distribution on $\mathbb{R}^{d}$ or the uniform distribution on the
$(d-1)$-dimensional unit sphere. We let $X_{1},X_{2},\ldots$ be a sequence of
independent random points in $\mathbb{R}^{d}$ with distribution $\phi$. Then,

  * (i)

the Cover-Efron random cone $C_{n,d}$ in $\mathbb{R}^{d}$, introduced by Cover
and Efrom [6] and further studied by Hug and Schneider [24], is defined as the
positive hull

$C_{n,d}:=\operatorname{pos}(X_{1},\ldots,X_{n})=\Big{\\{}\sum_{i=1}^{n}\lambda_{i}X_{i}:\lambda_{1},\dots,\lambda_{n}\geq
0\Big{\\}}$

conditionally on the event that
$\operatorname{pos}(X_{1},\ldots,X_{n})\neq\mathbb{R}^{d}$.

  * (ii)

the Donoho-Tanner random cone $D_{n,d}$ in $\mathbb{R}^{d}$, introduced by
Donoho and Tanner [12], is defined as

$D_{n,d}:=\operatorname{pos}(X_{1},\ldots,X_{n})$

without any conditioning. Alternatively, we can write

$D_{n,d}=A\mathbb{R}_{+}^{n},\qquad n\in\mathbb{N},$

where $A$ is the $d\times n$ matrix with columns $X_{1},\ldots,X_{n}$ and
$\mathbb{R}_{+}^{n}=[0,\infty)^{n}$ is the positive orthant in
$\mathbb{R}^{n}$.

We remark that there is a close relation between the both models, because the
Cover-Efron cone is nothing but a Donoho-Tanner cone conditioned on the event
that it is not the whole $\mathbb{R}^{d}$.

For both models it has been shown that in certain regimes for the dimension
$d$ and the number of generating points $n$, the cones are with high
probability $k$-neighbourly for a sufficiently slow growth of $k=k(d)$
relative to $d$, meaning that with probability tending to $1$, as
$d\to\infty$, every $k$-tuple of the $n$ defining vectors spans a
$k$-dimensional face of the cone. On the other hand, if $k$ grows sufficiently
fast with $d$, the probability of being $k$-neighbourly goes to $0$ as
$d\to\infty$. The motivation for the investigation of such threshold phenomena
comes from the Grassmannian approach to linear programming suggested by
Vershik in the 1970’s and developed by Vershik and Sporyshev in [36, 37, 38].
It has subsequently been applied to a number of problems in convex
optimization by Donoho and Tanner [9, 10, 11, 12, 13] as well as by Amelunxen,
Lotz, McCoy and Tropp [2]. In this approach, one endows the space of instances
of an optimization problem with a natural probability measure and then asks
for the probability that the optimization problem is solvable. Threshold
phenomena therefore describe transitions from solvability to non-solvability.

For both types of random cones, $C_{n,d}$ and $D_{n,d}$, explicit formulas for
the expectations of various combinatorial and geometric functionals exist in
the literature. Examples of such functionals include the face numbers, the
conic intrinsic volumes as well as the conic quermassintegrals. Using these
formulas, Donoho and Tanner [12] for $D_{n,d}$ and Hug and Schneider [25] for
$C_{n,d}$ proved limit theorems for the expected functionals when the
parameters of the problem, that is, $d$ and $n$, diverge to infinity in a
suitably coordinated way. In particular, they established a number of
threshold phenomena for these high-dimensional random cones which are similar
to the ones that we described above. In this connection let us also mention
that there are numerous works on threshold phenomena for volumes of random
polytopes [3, 4, 5, 14, 15, 33]. For example, assuming that $n=n(d)$ is such
that $d/n\to\delta\in[0,1]$, Hug and Schneider in [25, Theorem 1] obtained
that

$\lim_{d\to\infty}{\mathbf{E}f_{k}(C_{n,d})\over{n\choose
k}}=\begin{cases}1&:\delta\in(1/2,1],\\\
(2\delta)^{k}&:\delta\in[0,1/2)\end{cases}$

for any fixed $k\in\mathbb{N}$, where $f_{k}(C_{n,d})$ denotes the number of
$k$-(dimensional) faces of $C_{n,d}$. In this threshold phenomenon the
critical case $\delta=1/2$ has been left open. As one of our first results we
prove that in this case, the above limit is still equal to $1$, see Theorem
4.1 below. We also look much more carefully into the critical window around
$\delta=1/2$ by considering the situation where

$n=2d+c\sqrt{d}+o(\sqrt{d}),$

as $d\to\infty$, for some parameter $c\in\mathbb{R}$ and some sequence
$o(\sqrt{d})$ which is asymptotically of lower order compared to $\sqrt{d}$.
We show that, for any fixed $k\in\mathbb{N}$,

$\lim_{d\to\infty}\sqrt{d}\bigg{(}1-{\mathbf{E}f_{k}(C_{n,d})\over{n\choose
k}}\bigg{)}={e^{-c^{2}/4}\over\Phi(-c/\sqrt{2})}\cdot{k\over 2\sqrt{\pi}},$

where $\Phi(\,\cdot\,)$ stands for the distribution function of a standard
Gaussian random variable, see Theorem 4.2 below. In the same regime for $n$ we
establish in Proposition 4.3 that for the Donoho-Tanner random cones $D_{n,d}$
one has that

$\lim_{d\to\infty}{\mathbf{E}f_{k}(D_{n,d})\over{n\choose
k}}=\Phi\Big{(}-{c\over\sqrt{2}}\Big{)}.$

We prove similar results also for increasing face dimensions $k=k(d)$,
especially in the case where $k$ growths with $d$ in a linearly coordinated
way. In addition and as anticipated above, not only the expected number of
$k$-faces of $C_{n,d}$ and $D_{n,d}$ is treated, but also the expected $k$-th
conic intrinsic volume and the expected $k$-th conic quermassintegral for
which we also uncover a number of limit theorems like central and non-central
limit theorems or large deviation principles. Generally speaking, our
investigations are always driven by the search for regimes of $d$, $n=n(d)$
and $k=k(d)$ for which these combinatorial and geometric parameters of the
random cones under investigation exhibit a non-trivial high-dimensional
limiting behaviour, which describes the phase transition of the parameter
under consideration. We apply our results also to study the phase transition
for the number of $k$-dimensional faces of polytopes in $\mathbb{R}^{d}$
generated by a random Gale diagram, as suggested by Schneider [34]. In the
background of our results are probabilistic interpretations of the
combinatorial and geometric parameters of the Cover-Efron and Donoho-Tanner
random cones in terms of probabilities for binomial random variables, which
are already present in [12, 25]. We can thus build on known limit theorems
from probability theory, such as the law of large numbers, the central limit
theorem, the local limit theorem, Cramér’s theorem for large deviations,
mod-$\phi$ convergence and the Cramér-Petrov theorem for moderate deviations.
We believe that this approach is more powerful than the one in [25], which is
based on various intricate inequalities for binomial coefficients.

This paper is organized as follows. In Section 2 we introduce some notation,
collect various limit theorems for binomial random variables, and formally
define the conic intrinsic volumes and conic quermassintegrals for polyhedral
convex cones. Section 3 formally introduces the above mentioned models of
random cones and rephrases some known results which are used in this text. The
following Sections 4–6 contain limit theorems for the expected number of
faces, the expected conic intrinsic volumes and the conic quermassintegrals as
well as the expected statistical dimension. Section 4 also contains the
application to polytopes generated by random Gale diagrams.

##  2\. Preliminaries

###  2.1. Notation

In this paper we write $\mathbb{N}=\\{1,2,\ldots\\}$ for the natural numbers
and $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}=\\{0,1,2,\ldots\\}$ for the natural
numbers including zero. Moreover, we work in a $d$-dimensional Euclidean space
$\mathbb{R}^{d}$, which is supplied with the standard scalar product
$\langle\,\cdot\,,\,\cdot\,\rangle$.

We will write $\textup{Bin}(m,p)$ for a binomial random variable with
$m\in\mathbb{N}$ being the number of trials and $p\in[0,1]$ being the success
probability. Similarly, $N(0,1)$ denotes a standard normal (Gaussian) random
variable. Moreover, we let $\Phi$ denote the probability distribution function
of $N(0,1)$, that is,

$\displaystyle\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-t^{2}/2}\,\textup{d}t,\qquad
x\in\mathbb{R}.$

We implicitly assume that such random variables are defined over some
probability space $(\Omega,\mathcal{A},\mathbf{P})$, and we denote expectation
(integration) with respect to the probability measure $\mathbf{P}$ by
$\mathbf{E}$. Convergence in distribution and almost sure convergence of a
sequence of random variables will be indicated by
$\overset{d}{\longrightarrow}$ and $\overset{a.s.}{\longrightarrow}$,
respectively. In the situations we consider, the random variables are usually
indexed by the dimension $d$ and we write
$\overset{d}{\underset{d\to\infty}{\longrightarrow}}$ and
$\overset{a.s.}{\underset{d\to\infty}{\longrightarrow}}$ in order to indicate,
respectively, convergence in distribution and almost sure convergences, as
$d\to\infty$.

Two sequences $(a_{d})_{d\geq 1}$ and $(b_{d})_{d\geq 1}$ of real numbers are
called asymptotically equivalent, as $d\to\infty$, if
$\lim_{d\to\infty}\frac{a_{d}}{b_{d}}=1$. We denote this by writing $a_{d}\sim
b_{d}$, as $d\to\infty$, or by $\underset{d\to\infty}{\sim}$ if there are
several parameters tending to infinity and we want to emphasize the role of
$d$. Furthermore, we use the usual Landau notation, that is we say that
$a_{d}=o(b_{d})$, as $d\to\infty$, if

$\displaystyle\lim_{d\to\infty}\frac{a_{d}}{b_{d}}=0,$

and similarly, $a_{d}=O(b_{d})$, as $d\to\infty$, if

$\displaystyle\limsup_{d\to\infty}\left|\frac{a_{d}}{b_{d}}\right|<\infty.$

By slight abuse of notation we shall write $o(b_{d})$ or $O(b_{d})$ for the
sequences $a_{d}$ themselves.

###  2.2. Limit theorems for binomial random variables and binomial
coefficients

In this section, we collect some limit theorems for binomial random variables,
and thus, also for binomial coefficients. Besides the well-known central limit
theorem and the law of large numbers for $\textup{Bin}(n,1/2)$, given by

$\displaystyle\frac{2\textup{Bin}(n,1/2)-n}{\sqrt{n}}\overset{d}{\underset{n\to\infty}{\longrightarrow}}N(0,1)\qquad\text{and}\qquad\frac{\textup{Bin}(n,1/2)}{n}\overset{a.s.}{\underset{n\to\infty}{\longrightarrow}}1,$

respectively, we will also need the local limit theorem. Following [32, VII.,
§1. Theorem 1], it can be written in the case of $\textup{Bin}(n,1/2)$ as
follows:

$\displaystyle\sup_{m\in\mathbb{Z}}\left|\sqrt{\frac{n}{4}}\cdot\mathbf{P}[\textup{Bin}(n,1/2)=m]-\frac{1}{\sqrt{2\pi}}\exp\left\\{-\frac{1}{2}\Big{(}\frac{2m-n}{\sqrt{n}}\Big{)}^{2}\right\\}\right|\underset{n\to\infty}{\longrightarrow}0.$
(2.1)

Additionally, we need an asymptotic expansion for the distribution function of
the centered and normalized version of $\textup{Bin}(n,1/2)$. More precisely,
for $Z_{n}:=2(\textup{Bin}(n,1/2)-n)/\sqrt{n}$, Theorem IV.3 of [16] states
that

$\displaystyle\mathbf{P}[Z_{n}\leq x]=\Phi(x)+\frac{\sqrt{2}}{\sqrt{\pi
n}}\psi_{n}(x)e^{-x^{2}/2}+o\Big{(}\frac{1}{\sqrt{n}}\Big{)},\qquad\text{as
}n\to\infty,$ (2.2)

uniformly in $x\in\mathbb{R}$ (the uniformity in $x$ is discussed in Chapter V
of [16]), where $\psi_{n}(x)$ is defined as

$\displaystyle\psi_{n}(x):=Q\left(\frac{x\sqrt{n}}{2}-\frac{n}{2}\right),$
(2.3)

for the $1$-periodic function $Q(x):=[x]-x+1/2$.

The classical Cramer’s theorem [8, Theorem I.3] in the particular case of
binomial random variables $\textup{Bin}(m,1/2)$ states that

$\lim_{m\to\infty}{1\over m}\log\mathbf{P}[\textup{Bin}(m,1/2)\geq
m(a+o(1))]=-\mathcal{I}(a),\qquad a\in(1/2,1)$ (2.4)

and

$\lim_{m\to\infty}{1\over m}\log\mathbf{P}[\textup{Bin}(m,1/2)\leq
m(a+o(1))]=-\mathcal{I}(a),\qquad a\in(0,1/2),$ (2.5)

where the information function $\mathcal{I}(a)$ is given by

$\displaystyle\mathcal{I}(a)=\log 2+a\log a+(1-a)\log(1-a),\qquad a\in[0,1].$
(2.6)

Here, $o(1)$ stands for any sequence tending to zero, as $m\to\infty$.
Throughout this paper, the notation $\mathcal{I}$ will be used solely for the
information function as defined in (2.6).

We shall also need a precise version of the above Cramer asymptotics. It can
be deduced as a special case from the general theory of mod-phi convergence
[18], in this case Theorem 3.2.2 from [18]. Let $(x_{m})_{m\geq 0}$ be a
sequence such that $x_{m}\to x$ and $mx_{m}\in\mathbb{N}$. Then, for all
$x\in(0,1)$ it holds that

$\displaystyle\mathbf{P}[\textup{Bin}(m,1/2)=mx_{m}]\underset{m\to\infty}{\sim}\frac{e^{-m\cdot\mathcal{I}(x_{m})}}{\sqrt{2\pi
m}}\frac{1}{\sqrt{x(1-x)}},$ (2.7)

and for all $x\in(1/2,1)$, we have

$\displaystyle\mathbf{P}[\textup{Bin}(m,1/2)\leq
m(1-x_{m})]=\mathbf{P}[\textup{Bin}(m,1/2)\geq
mx_{m}]\underset{m\to\infty}{\sim}\frac{e^{-m\cdot\mathcal{I}(x_{m})}}{\sqrt{2\pi
m}}\frac{1}{\sqrt{x(1-x)}}\frac{x}{2x-1}.$ (2.8)

The same asymptotic formulas also follow, e.g., from [31, Theorem 6].

Moreover, we make use of the well-known Stirling’s formula for $m!$, which
says that

$\displaystyle m!\underset{m\to\infty}{\sim}\sqrt{2\pi
m}\Big{(}\frac{m}{e}\Big{)}^{m}.$

###  2.3. Convex cones, conic intrinsic volumes and quermassintegrals

For a set $M\subset\mathbb{R}^{d}$, the positive hull $\operatorname{pos}M$ of
$M$ is defined as

$\displaystyle\operatorname{pos}M:=\Big{\\{}\sum_{i=1}^{m}\lambda_{i}t_{i}:\,m\in\mathbb{N},t_{1},\dots,t_{m}\in
M,\lambda_{1},\dots,\lambda_{m}\geq 0\Big{\\}}.$

A convex set $C\subset\mathbb{R}^{d}$ is called a convex cone if $\lambda C$
lies entirely in $C$ for all $\lambda\geq 0$. In particular,
$\operatorname{pos}M$ denotes the smallest convex cone containing $M$. In the
following, we shall be interested in polyhedral cones, that is positive hulls
of finite sets, and the word cone always refers to a polyhedral cone. A
supporting hyperplane for a cone $C$ is a linear hyperplane $H$ such that $C$
lies entirely in one of the closed half-spaces bounded by $H$. Then, the cones
$C\cap H$, where $H$ is a supporting hyperplane, are called faces of the cone
$C$. By convention, the cone $C$ is also a face of itself. A $k$-dimensional
face of $C$ is also called $k$-face, where the dimension of a face $F$ (and
for a convex set in general) is defined as the dimension of its affine hull.
The set of all $k$-faces of $C$ is denoted by $\mathcal{F}_{k}(C)$, and the
total number of distinct $k$-faces of $C$ is
$f_{k}(C):=\\#\mathcal{F}_{k}(C)$. The dual cone $C^{\circ}$ of a cone
$C\subset\mathbb{R}^{d}$ is defined as

$\displaystyle C^{\circ}:=\\{v\in\mathbb{R}^{d}:\langle v,x\rangle\leq
0\;\forall x\in C\\},$

where $\langle\,\cdot\,,\,\cdot\,\rangle$ denotes the standard Euclidean
scalar product.

Now, we briefly recall the definition of two geometric functionals of convex
cones. For a cone $C\subset\mathbb{R}^{d}$, the k-th conic intrinsic volume
$\upsilon_{k}(C)$ is defined as

$\displaystyle\upsilon_{k}(C):=\sum_{F\in\mathcal{F}_{k}(C)}\mathbf{P}[\Pi_{C}(g)\in\textup{relint}\,F],\quad
k\in\\{0,\dots,d\\}.$

Here, $g$ is a $d$-dimensional standard Gaussian distributed random vector and
$\textup{relint}\,F$ denotes the relative interior of $F$, which is the set of
all interior points of $F$ relative to its linear hull. Also, $\Pi_{C}(x)$,
for a point $x\in\mathbb{R}^{d}$, denotes the Euclidean projection of $x$ onto
$C$, which is the unique point $y\in C$ minimizing the Euclidean distance to
$x$. An equivalent definition of the conic intrinsic volumes using the
spherical Steiner formula can be found in [35, Section 6.5]. For more
background material and further properties we refer to [1, Section 2.2] and
[35, Section 6.5].

For a cone $C\subset\mathbb{R}^{d}$ that is not a linear subspace, the $k$-th
conic quermassintegral of $C$, for $k\in\\{0,\dots,d\\}$, is defined by

$\displaystyle U_{k}(C):=\frac{1}{2}\mathbf{P}[C\cap W_{d-k}\neq\\{0\\}],$

where $W_{d-k}$ is a random $(d-k)$-subspace uniformly distributed on the
Grassmannian $G(d,d-k)$ of all $(d-k)$-dimensional linear subspaces of
$\mathbb{R}^{d}$ (the uniform distribution refers here to the unique rotation-
invariant Haar probability measure). For a $j$-dimensional linear subspace
$L_{j}\subset\mathbb{R}^{d}$, we define

$\displaystyle U_{k}(L_{j})=\begin{cases}1&:j-k>0\text{ and odd},\\\
0&:j-k\leq 0\text{ or even}.\end{cases}$

Note that the values of $U_{k}$ for linear subspaces are chosen in such a way
that the following linear relation between the conic intrinsic volumes and the
conic quermassintegrals, called the conic Crofton formula, holds for each cone
$C\subset\mathbb{R}^{d}$:

$\displaystyle U_{k}(C)=\upsilon_{k+1}(C)+\upsilon_{k+3}(C)+\ldots,$ (2.9)

see, e.g., [35, p. 262]. If $C$ is not a linear subspace, the quantity
$2U_{k}(C)$ is also called $k$-th Grassmann angle of $C$ and was introduced by
Grünbaum [21]. For further properties of the conic quermassintegrals see also
[24, Section 2].

##  3\. Two models of random cones

We formally define the two models of random cones mentioned in the
introduction and collect some known properties. In this section, let
$X_{1},\dots,X_{n}$ be independent and $d$-dimensional random vectors
distributed according to a common probability distribution $\phi$. We assume
that $\phi$ is even (meaning that it is invariant under reflections at the
origin) and assigns measure zero to each $(d-1)$-dimensional hyperplane in
$\mathbb{R}^{d}$. Also, we always assume that $n\geq d$. Finally, we introduce
the numbers

$\displaystyle C(n,d):=2\sum_{r=0}^{d-1}{n-1\choose r},$ (3.1)

which will often appear in our considerations.

###  3.1. The Donoho-Tanner random cones

The Donoho-Tanner random cone $D_{n,d}$ is defined to be the positive hull of
the vectors $X_{1},\dots,X_{n}$. Equivalently, $D_{n,d}$ can be described as
the cone $A\mathbb{R}^{n}_{+}$, where $A$ is the $d\times n$ random matrix
with columns $X_{1},\dots,X_{n}$ and $\mathbb{R}_{+}^{n}=[0,\infty)^{n}$ is
the positive orthant. It was shown by Donoho and Tanner in [12, Theorem 1.6]
that

${\mathbf{E}f_{k}(D_{n,d})\over{n\choose k}}=1-{1\over
2^{n-k-1}}\sum_{r=0}^{n-d-1}{n-k-1\choose r}=1-{1\over 2^{n-k}}\,C(n-k,n-d)$
(3.2)

for all $k\in\\{1,\ldots,d-1\\}$. The dual cone of $D_{n,d}$, which is defined
as

$D_{n,d}^{\circ}:=\\{x\in\mathbb{R}^{d}:\langle x,y\rangle\leq 0\text{ for all
}y\in D_{n,d}\\},$

will be called the dual Donoho-Tanner random cone. It can equivalently be
described as

$\displaystyle D_{n,d}^{\circ}=\\{v\in\mathbb{R}^{d}:\langle
v,X_{i}\rangle\leq 0\text{ for all }i=1,\dots,n\\}.$

###  3.2. The Schläfli and Cover-Efron random cones

Consider $n\in\mathbb{N}$ independent linear random hyperplanes in
$\mathbb{R}^{d}$ whose unit normal vectors are $X_{1},\dots,X_{n}$. By a
formula of Schläfli [35, Lemma 8.2.1], these hyperplanes dissect
$\mathbb{R}^{d}$ into $C(n,d)$ non-degenerate cones, with probability $1$. The
Schläfli random cone $S_{n,d}$ is a cone chosen uniformly at random from these
$C(n,d)$ cones. Hug and Schneider [24] determined the expected number of
$k$-faces, the expected conic intrinsic volumes as well as the expected conic
quermassintegrals of $S_{n,d}$. For later purposes we only recall here the
formula for the expected conic intrinsic volumes of the Schläfli random cone
$S_{n,d}$ from [24, Corollary 4.3]:

$\displaystyle\mathbf{E}\upsilon_{j}(S_{n,d})=\begin{cases}\binom{n}{d-j}\frac{1}{C(n,d)}&:j\in\\{1,\dots,d\\},\\\
\binom{n-1}{d-1}\frac{1}{C(n,d)}&:j=0.\end{cases}$ (3.3)

The dual of the cone $S_{n,d}$, which is defined as

$S_{n,d}^{\circ}:=\\{x\in\mathbb{R}^{d}:\langle x,y\rangle\leq 0\text{ for all
}y\in S_{n,d}\\},$

is called the Cover-Efron random cone and will be denoted by $C_{n,d}$. It can
equivalently be described as the positive hull of $n$ independent random
vectors $X_{1},\ldots,X_{n}$ with distribution $\phi$, conditioned on the
event that this cone is not the whole space $\mathbb{R}^{d}$. By Wendel’s
formula [39] (see also [35, Theorem 8.2.1] and [29]), the probability of the
event $\\{D_{n,d}\neq\mathbb{R}^{d}\\}$ is $C(n,d)/2^{n}$. That is, $C_{n,d}$
is the random cone with distribution given by
$\mathbf{P}[C_{n,d}=\mathbb{R}^{d}]=0$ and

$\mathbf{P}[C_{n,d}\in\,\cdot\,]=\frac{2^{n}}{C(n,d)}\int_{(\SS^{d-1})^{n}}{\bf
1}\\{\operatorname{pos}(x_{1},\ldots,x_{n})\in\,\cdot\,\\}\,\phi^{n}(\textup{d}(x_{1},\ldots,x_{n})).$

Cover and Efron [6] have shown that

$\mathbf{E}f_{k}(C_{n,d})={2^{k}{n\choose k}C(n-k,d-k)\over C(n,d)}$ (3.4)

holds for any $k\in\\{0,\ldots,d-1\\}$, see also [24, Corollary 4.1]. From
[24, Corollaries 4.2, 4.3] it is also known that

$\displaystyle\mathbf{E}v_{k}(C_{n,d})=\begin{cases}{{n\choose k}\over
C(n,d)}&:k\in\\{0,1,\ldots,d-1\\}\\\ {{n-1\choose d-1}\over
C(n,d)}&:k=d.\end{cases}$ (3.5)

and

$\displaystyle\mathbf{E}U_{k}(C_{n,d})=\frac{C(n,d)-C(n,k)}{2C(n,d)},\quad
k\in\\{1,\dots,d\\}.$ (3.6)

It is important to note that the two constructions of random cones we
described are very similar in the following sense. The Cover-Efron random cone
$C_{n,d}$ has the same distribution as the Donoho-Tanner random cone $D_{n,d}$
conditioned on the event that $D_{n,d}\neq\mathbb{R}^{d}$. Similarly,
$S_{n,d}$ has the same distribution as $D_{n,d}^{\circ}$ conditioned on the
event that $D_{n,d}^{\circ}\neq\\{0\\}$.

##  4\. Limit theorems for the expected face numbers

In this section, our goal is to understand the asymptotic behaviour of the
expected number of $k$-faces of the random cones introduced in Section 3 in
high dimensions, meaning that the number of vectors $n$, the dimension $d$,
and in some cases also $k$ tend to infinity simultaneously and in a
coordinated way.

###  4.1. Fixed face-dimension $\boldsymbol{k}$

We start by considering the case where the face-dimension $k\in\mathbb{N}$ is
fixed. Let $C_{n,d}$ be a Cover-Efron random cone. In Theorem $1$ of [25], Hug
and Schneider proved that if $n=n(d)$ is such that

$\displaystyle\frac{d}{n}\to\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in[0,1]$, the Cover-Efron random cone satisfies the
following threshold phenomenon:

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=\begin{cases}1&:\delta\in(1/2,1],\\\
(2\delta)^{k}&:\delta\in[0,1/2).\end{cases}$

In this section, we are going to further evaluate what happens in the critical
case $\delta=1/2$. In addition, in their Theorem 2, Hug and Schneider [25]
proved that if $n=n(d)$ is such that $n-2d$ stays bounded from above, as
$d\to\infty$, then for every fixed $k\in\mathbb{N}$, one has that

$\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=1.$

They asked what happens under the weaker condition $n\sim 2d$. The next
theorem addresses both questions discussed so far.

######  Theorem 4.1.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $n=n(d)$ is such that

$\frac{d}{n}\to\frac{1}{2},\qquad\text{as $d\to\infty$}.$

Then, for every fixed $k\in\mathbb{N}$, it holds that

$\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=1.$

###### Proof.

Let us first introduce the quantity

$Q_{k}(n,d):=\frac{\mathbf{P}[\textup{Bin}(n-k,1/2)\leq
d-k]}{\mathbf{P}[\textup{Bin}(n,1/2)\leq d]}.$

By (3.4), we can write $\mathbf{E}f_{k}(C_{n,d})$ in terms of binomial
probabilities:

$\displaystyle\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=\frac{\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq
d-k-1]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]}.$ (4.1)

Assuming that $d/n\to 1/2$ our task is to prove that

$\lim_{d\to\infty}Q_{k}(n,d)=1,$

since we have $\mathbf{E}f_{k}(C_{n,d})/\binom{n}{k}=Q_{k}(n-1,d-1)$ by (4.1),
and the condition $n\sim 2d$ implies that $n-1\sim 2(d-1)$.

The main difficulty is that the condition $n\sim 2d$ is too general and leaves
open several possibilities for the asymptotic behaviour of the denominator and
the numerator in the definition of $Q_{k}(n,d)$. More precisely, the limit
$c:=\lim_{d\to\infty}(\frac{n}{2}-d)/\sqrt{n}$ may be finite (in which case
the denominator converges to $\Phi(-2c)$), it may be $-\infty$ (in which case
the denominator converges to $1$) or it may be $+\infty$ (in which case the
denominator converges to $0$), or it may not exist at all.

To determine the asymptotic behaviour of the denominator and the numerator in
the case when both converge to $0$, we shall use the the Cramér-Petrov theorem
on moderate deviations obtained by Cramér [7] and subsequently strengthened in
[17, 23, 30]; see also [32, Chapter VIII, § 2] and [26, Theorem 8.1.1]. The
theorem is valid for sums of i.i.d. random variables. Here, we use it in the
special case of the binomial distribution. To state the asymptotics, let
$y_{n}>0$ be a sequence such that $y_{n}/\sqrt{n}\to\infty$ and $y_{n}/n\to
0$. Then, we have

$\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}-y_{n}\right]\sim\frac{\sqrt{n}}{\sqrt{2\pi}y_{n}}\exp\left\\{-n\cdot\mathfrak{I}\left(\frac{y_{n}}{n}\right)\right\\},\qquad\text{
as }n\to\infty,$ (4.2)

where the information function
$\mathfrak{I}(z):[-\frac{1}{2},+\frac{1}{2}]\to[0,\infty)$ is given by

$\mathfrak{I}(z)=\log
2+\left(z+\frac{1}{2}\right)\log\left(z+\frac{1}{2}\right)+\left(\frac{1}{2}-z\right)\log\left(\frac{1}{2}-z\right).$

We define the sequences

$y_{n}:=\frac{n}{2}-d,\qquad z_{n}:=\frac{n}{2}-d+\frac{k}{2}.$ (4.3)

Then, our assumption $n\sim 2d$ implies that $y_{n}/n\to 0$, but in general we
need not have $y_{n}/\sqrt{n}\to+\infty$. Therefore, we consider several
cases.

Case 1. Assume first that $y_{n}/\sqrt{n}\to c\in\mathbb{R}\cup\\{-\infty\\}$
as $n\to\infty$. Then, the central limit theorem for binomial random
variables, applied twice, yields

$Q_{k}(n,d)=\frac{\mathbf{P}\left[\textup{Bin}(n-k,1/2)\leq\frac{n-k}{2}-z_{n}\right]}{\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}-y_{n}\right]}\to\frac{\Phi(-2c)}{\Phi(-2c)}=1.$

Note that the above argument applies if $c=-\infty$, in which case both the
denominator and the numerator converge to $\Phi(+\infty)=1$. Observe that in
the case $c=+\infty$ (which we excluded above), the argument would break down
because it would lead to an indeterminacy $0/0$. In the next step we shall
resolve the indeterminacy by using the Cramér-Petrov asymptotics.

Case 2. Assume now that $y_{n}/\sqrt{n}\to+\infty$, which also implies that
$z_{n}/\sqrt{n}\to+\infty$ and $z_{n}=y_{n}+\frac{k}{2}\sim y_{n}$. Applying
the Cramér-Petrov asymptotics (4.2) twice, we have

$\displaystyle
Q_{k}(n,d)=\frac{\mathbf{P}\left[\textup{Bin}(n-k,1/2)\leq\frac{n-k}{2}-z_{n}\right]}{\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}-y_{n}\right]}\sim\frac{\frac{\sqrt{n-k}}{\sqrt{2\pi}z_{n}}\exp\left\\{-(n-k)\cdot\mathfrak{I}\left(\frac{z_{n}}{n-k}\right)\right\\}}{\frac{\sqrt{n}}{\sqrt{2\pi}y_{n}}\exp\left\\{-n\cdot\mathfrak{I}\left(\frac{y_{n}}{n}\right)\right\\}}.$

It follows from $y_{n}\sim z_{n}$ and $n-k\sim n$ that

$Q_{k}(n,d)\sim\exp\left\\{n\cdot\mathfrak{I}\left(\frac{y_{n}}{n}\right)-(n-k)\cdot\mathfrak{I}\left(\frac{z_{n}}{n-k}\right)\right\\}.$

The condition $n\sim 2d$ implies that $y_{n}=o(n)$ and $z_{n}=o(n)$, hence
$z_{n}/(n-k)\to 0$ and $kI(z_{n}/(n-k))\to 0$. It follows that the above
result can be simplified to

$Q_{k}(n,d)\sim\exp\left\\{n\mathfrak{I}\left(\frac{y_{n}}{n}\right)-n\mathfrak{I}\left(\frac{z_{n}}{n-k}\right)\right\\}.$

By (4.3) we have

$\frac{z_{n}}{n-k}=\frac{y_{n}}{n}\cdot\frac{1}{1-\frac{k}{n}}+\frac{k}{2(n-k)}=\frac{y_{n}}{n}\left(1+O\left(\frac{1}{n}\right)\right)+O\left(\frac{1}{n}\right)=\frac{y_{n}}{n}+O\left(\frac{1}{n}\right)$

since $y_{n}/n\to 0$. By the mean value theorem, for some sequence $\xi_{n}\to
0$ sandwiched between $y_{n}/n$ and $z_{n}/(n-k)$, we have

$\mathfrak{I}\left(\frac{y_{n}}{n}\right)-\mathfrak{I}\left(\frac{z_{n}}{n-k}\right)=O\left(\frac{1}{n}\right)\mathfrak{I}^{\prime}(\xi_{n})=O\left(\frac{\xi_{n}}{n}\right)=O\left(\frac{y_{n}}{n^{2}}\right),$

where we also used that $\mathfrak{I}^{\prime}(\xi_{n})=O(\xi_{n})$ by the
Taylor expansion of $\mathfrak{I}$ at $0$ and then that $y_{n}/n$ and
$z_{n}/(n-k)$ are asymptotically equivalent implying that $\xi_{n}\sim
y_{n}/n$. Altogether, it follows that

$Q_{k}(n,d)=(1+o(1))\exp\left\\{nO\left(\frac{y_{n}}{n^{2}}\right)\right\\}=(1+o(1))\exp\left\\{O\left(\frac{y_{n}}{n}\right)\right\\}\to
1,$

because $y_{n}/n\to 0$. This completes the proof under the assumption
$y_{n}/\sqrt{n}\to+\infty$.

Case 3. In the previous two steps we proved our claim in the case when the
limit of $y_{n}/\sqrt{n}$ exists in $\mathbb{R}\cup\\{+\infty,-\infty\\}$. In
general, the limit need not exist. To treat this case, we use the subsequence
argument. Assume by contraposition that the limit of $Q_{k}(n,d)$ over some
subsequence of $d$’s is not equal to $1$ or does not exist. Extracting a
further subsequence, we may assume that $y_{n}$ has a limit in
$\mathbb{R}\cup\\{+\infty,-\infty\\}$. Then, we apply either Step 1 or Step 2,
implying that over this subsequence $Q_{d}(n,d)$ converges to $1$, which is a
contradiction. ∎

In Theorem 2 of [25] Hug and Schneider also proved that if $n=2d$, then for
all fixed $k\in\mathbb{N}$, one has that

$\displaystyle\lim_{d\to\infty}\sqrt{d}\left(1-\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}\right)=\frac{k}{\sqrt{\pi}}.$

The next theorem refines this result by looking more closely into the critical
window.

######  Theorem 4.2.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $n=n(d)$ is such that

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for a parameter $c\in\mathbb{R}$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\sqrt{d}\left(1-\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}\right)=\frac{e^{-c^{2}/4}}{\Phi(-c/\sqrt{2})}\cdot\frac{k}{2\sqrt{\pi}}$

for all fixed $k\in\mathbb{N}$.

###### Proof.

Let $n=2d+c\sqrt{d}+o(\sqrt{d})$ as $d\to\infty$. In view of (4.1), we obtain

$\displaystyle 1-{\mathbf{E}f_{k}(C_{n,d})\over{n\choose
k}}=\frac{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]-\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq
d-k-1]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]}.$ (4.4)

Defining $Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$ and using the central
limit theorem for the binomial distribution, we find the following convergence
for the denominator:

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq\frac{2(d-1)-(n-1)}{\sqrt{n-1}}\right]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq-\frac{c}{\sqrt{2}}+o(1)\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

In order to obtain the asymptotic behaviour of the numerator of (4.4), we
define the sequences $(c_{n})_{n\geq 0}$ and $(d_{n})_{n\geq 0}$ by

$\displaystyle c_{n}:=\frac{2d-n-1}{\sqrt{n-1}}\qquad\text{and}\qquad
d_{n}:=\frac{2d-k-n-1}{\sqrt{n-k-1}}.$

Note that both sequences converge to $-c/\sqrt{2}$ as $d\to\infty$. Then, we
can use the asymptotic expansion (2.2) to obtain

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]-\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq d-k-1]$
$\displaystyle\quad=\mathbf{P}[Z_{n-1}\leq c_{n}]-\mathbf{P}[Z_{n-k-1}\leq
d_{n}]$
$\displaystyle\quad=\Phi(c_{n})-\Phi(d_{n})+\frac{\sqrt{2}}{\sqrt{\pi(n-1)}}\psi_{n-1}(c_{n})e^{-c^{2}/4}-\frac{\sqrt{2}}{\sqrt{\pi(n-k-1)}}\psi_{n-k-1}(d_{n})e^{-c^{2}/4}+o\Big{(}\frac{1}{\sqrt{n}}\Big{)}.$

Inserting $c_{n}$ and $d_{n}$ into the definitions of $\psi_{n-1}$ and
$\psi_{n-k-1}$, respectively (see (2.3)), yields
$\psi_{n-1}(c_{n})=0=\psi_{n-k-1}(d_{n})$, and thus

$\begin{split}&\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]-\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq d-k-1]\\\ &\hskip
199.16928pt=\Phi(c_{n})-\Phi(d_{n})+o\Big{(}\frac{1}{\sqrt{n}}\Big{)}.\end{split}$
(4.5)

Using the mean value theorem for the continuous and differentiable function
$\Phi$ yields that we can find a sequence $(\xi_{n})_{n\geq 0}$ such that
$\xi_{n}$ lies between $c_{n}$ and $d_{n}$, and satisfies

$\displaystyle\Phi(c_{n})-\Phi(d_{n})=(c_{n}-d_{n})\Phi^{\prime}(\xi_{n}).$

Since both sequences $(c_{n})_{n\geq 0}$ and $(d_{n})_{n\geq 0}$ converge to
$-c/\sqrt{2}$, as $d\to\infty$, we have that

$\displaystyle\lim_{n\to\infty}\Phi^{\prime}(\xi_{n})=\Phi^{\prime}\Big{(}-\frac{c}{\sqrt{2}}\Big{)}=\frac{1}{\sqrt{2\pi}}e^{-c^{2}/4}.$

Hence, it is left to determine the asymptotics of the difference
$c_{n}-d_{n}$. We can write

$\displaystyle
c_{n}=\frac{1}{\sqrt{n}}\cdot\frac{2d-n-1}{\sqrt{1-\frac{1}{n}}}\qquad\text{and}\qquad
d_{n}=\frac{1}{\sqrt{n}}\cdot\frac{2d-k-n-1}{\sqrt{1-\frac{k-1}{n}}}.$

Using that $(1+x)^{a}=1+ax+o(x)$ as $x\to 0$, we obtain

$\displaystyle\frac{1}{\sqrt{1-\frac{1}{n}}}=1+\frac{1}{2n}+o\Big{(}\frac{1}{n}\Big{)}\qquad\text{and}\qquad\frac{1}{\sqrt{1-\frac{k-1}{n}}}=1+\frac{k-1}{2n}+o\Big{(}\frac{1}{n}\Big{)}.$

This yields

$\displaystyle
c_{n}=\frac{2d-n-1}{\sqrt{n}}+\frac{2d-n-1}{2n^{3/2}}+o\Big{(}\frac{1}{\sqrt{n}}\Big{)}$

and

$\displaystyle
d_{n}=\frac{2d-n-1}{\sqrt{n}}-\frac{k}{\sqrt{n}}+\frac{(2d-k-n-1)(k-1)}{2n^{3/2}}+o\Big{(}\frac{1}{\sqrt{n}}\Big{)}.$

Thus, we obtain the following expansion for the difference of $c_{n}$ and
$d_{n}$:

$\displaystyle c_{n}-d_{n}$
$\displaystyle=\frac{k}{\sqrt{n}}+o\Big{(}\frac{1}{\sqrt{n}}\Big{)}.$

Inserting the results into (4.5) yields

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]-\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq d-k-1]=\frac{k}{\sqrt{2\pi
n}}e^{-c^{2}/4}+o\Big{(}\frac{1}{\sqrt{n}}\Big{)}.$

Combining this with (4.4) leads to

$\displaystyle\sqrt{d}\left(1-\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}\right)\underset{d\to\infty}{\sim}\sqrt{d}\cdot\frac{k}{\sqrt{2\pi
n}}e^{-c^{2}/4}\cdot\frac{1}{\Phi(-c/\sqrt{2})}.$

Finally, the fact that $\sqrt{d}/\sqrt{n}\to 1/\sqrt{2}$ proves the claim. ∎

The case of the Donoho-Tanner random cone $D_{n,d}$ is much simpler. The next
result is similar to [25, Theorem 1] for $\mathbf{E}f_{k}(D_{n,d})$ and
essentially present in [12]. We state it for completeness.

######  Proposition 4.3.

Let $D_{n,d}$ be a Donoho-Tanner random cone. Suppose that $n=n(d)$ is such
that

$\frac{d}{n}\to\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in[0,1]$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(D_{n,d})}{\binom{n}{k}}=\begin{cases}1&:\delta\in(1/2,1],\\\
0&:\delta\in[0,1/2).\end{cases}$

In the critical case where

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for some parameter $c\in\mathbb{R}$, we have

$\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(D_{n,d})}{\binom{n}{k}}=\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

###### Proof.

By (3.2), we can write $\mathbf{E}f_{k}(D_{n,d})/\binom{n}{k}$ in terms of
binomial probabilities:

$\displaystyle\frac{\mathbf{E}f_{k}(D_{n,d})}{\binom{n}{k}}=1-\mathbf{P}[\textup{Bin}(n-k-1,1/2)<n-d]=\mathbf{P}[\textup{Bin}(n-k-1,1/2)\geq
n-d].$ (4.6)

Since $(n-d)/(n-k-1)=(1-\delta)+o(1)$, we can use the law of large numbers to
obtain

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(D{n,d})}{\binom{n}{k}}=\mathbf{P}[\textup{Bin}(n-k-1,1/2)\geq(1-\delta+o(1))(n-k-1)]=\begin{cases}1&:\delta\in(1/2,1],\\\
0&:\delta\in[0,1/2),\end{cases}$

which proves the first claim.

In the critical case $n=2d+c\sqrt{d}+o(\sqrt{d})$, for a parameter
$c\in\mathbb{R}$, we can define $Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$ and
use the central limit theorem for binomial random variables to get

$\displaystyle\frac{\mathbf{E}f_{k}(D_{n,d})}{\binom{n}{k}}$
$\displaystyle=\mathbf{P}\left[Z_{n-k-1}\geq\frac{2(n-d)-(n-k-1)}{\sqrt{n-k-1}}\right]$
$\displaystyle=\mathbf{P}\left[Z_{n-k-1}\geq\frac{c}{\sqrt{2}}+o(1)\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)},$

which completes the proof.

∎

###  4.2. Increasing face-dimension $\boldsymbol{k}$

In this section our goal is to understand the asymptotic behaviour of the
expected face numbers when not only $n=n(d)$ but also $k=k(d)$ is a function
of $d$ and all parameters tend to infinity in a coordinated way. The next
theorem extends and considerably refines Theorem 5 of [25].

######  Theorem 4.4.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $k=k(d)$ and $n=n(d)$
are such that

$\displaystyle\frac{d}{n}\to\delta\quad\text{and}\quad\frac{k}{d}\to\varrho,\qquad\text{as
}d\to\infty,$ (4.7)

for $\delta\in(0,1)$ and $\varrho\in(0,1)$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=\begin{cases}1&:\varrho<\max\\{0,2-1/\delta\\},\\\
0&:\varrho>\max\\{0,2-1/\delta\\}.\end{cases}$ (4.8)

Furthermore, if $\delta>1/2$ and

$\displaystyle n=\frac{d}{\delta}+c\sqrt{d}+o(\sqrt{d})\quad\text{and}\quad
k=\Big{(}2-\frac{1}{\delta}\Big{)}d+b\sqrt{d}+o(\sqrt{d}),\qquad\text{as
}d\to\infty,$ (4.9)

for parameters $c,b\in\mathbb{R}$, then it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=\Phi\bigg{(}-\frac{c+b}{\sqrt{2/\delta-2}}\bigg{)}.$

In the case where

$\displaystyle n=2d+c\sqrt{d}+o(\sqrt{d})\quad\text{and}\quad
k=b\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$ (4.10)

for constants $c\in\mathbb{R}$ and $b\geq 0$, it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}=\frac{\Phi(-(c+b)/\sqrt{2})}{\Phi(-c/\sqrt{2})}.$

######  Remark 4.5.

  * (i)

Note that an analogous result to (4.8) for the Donoho-Tanner random cone was
proven in [12, Theorem 1.2].

  * (ii)

Hug and Schneider [25] proved (4.8) using various inequalities for the
binomial coefficients. We provide a different, more conceptual and
probabilistic, proof using the representation of $\mathbf{E}f_{k}(C_{n,d})$ as
binomial probabilities, which allows us to build on probabilistic limit
theorems.

###### Proof of Theorem 4.4.

Recall from (4.1) that

$\displaystyle\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{d}}=\frac{\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq
d-k-1]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]}.$ (4.11)

Assume that (4.7) holds true. We start with the case $2-1/\delta>0$, or
equivalently, $\delta>1/2$. The law of large numbers implies that

$\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]=1.$

Putting

$\displaystyle a:=\frac{1-\varrho}{1/\delta-\varrho},$

we observe that

$\displaystyle\frac{d-k-1}{n-k-1}=a+o(1).$

Since $a>1/2$ is equivalent to $\varrho<2-1/\delta$, we obtain that

$\displaystyle\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq d-k-1]$
$\displaystyle\qquad=\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq(a+o(1))(n-k-1)]$
$\displaystyle\qquad=\begin{cases}1&:\varrho<2-1/\delta,\\\
0&:\varrho>2-1/\delta,\end{cases}$

by the law of large numbers. Inserting both limits into (4.11) proves in the
case $\delta>1/2$.

For $\delta\leq 1/2$, we need to show that
$\lim_{d\to\infty}\mathbf{E}f_{k}(C_{n,d})/\binom{n}{k}=0$. At first consider
the case $\delta\in(0,1/2)$. Then, $a\in(0,1/2)$ and we can apply the
asymptotic equivalence (2.8) in both the numerator and the denominator of
(4.11). This yields

$\displaystyle\frac{\mathbf{E}f_{k}(C_{n,d})}{\binom{n}{k}}$
$\displaystyle\underset{d\to\infty}{\sim}C(\delta,\varrho)\cdot\frac{\exp\\{-(n-k-1)\cdot\mathcal{I}(\frac{d-k-1}{n-k-1})\\}}{\exp\\{-(n-1)\cdot\mathcal{I}(\frac{d-1}{n-1})\\}}$
$\displaystyle\underset{d\to\infty}{\sim}C(\delta,\varrho)\cdot\exp\left\\{-n\left(\Big{(}\frac{n-k-1}{n}\Big{)}\mathcal{I}\Big{(}\frac{d-k-1}{n-k-1}\Big{)}-\Big{(}\frac{n-1}{n}\Big{)}\mathcal{I}\Big{(}\frac{d-1}{n-1}\Big{)}\right)\right\\}$
$\displaystyle\underset{d\to\infty}{\sim}C(\delta,\varrho)\cdot\exp\left\\{-n\left((1-\delta\varrho)\mathcal{I}(a)-\mathcal{I}(\delta)+o(1)\right)\right\\},$

where $C(\delta,\varrho)>0$ is a constant which only depends on $\delta$ and
$\varrho$. Note that $\mathcal{I}$ again denotes the information function
(2.6). Thus, it suffices to prove that

$(1-\varrho\delta)\mathcal{I}(a)-\mathcal{I}(\delta)>0,$

or equivalently, that

$\frac{\mathcal{I}(a)}{\mathcal{I}(\delta)}>\frac{1}{1-\varrho\delta}.$

Using the convexity of the information function $\mathcal{I}$ and the fact
that $a<\delta<1/2$ and $\mathcal{I}(1/2)=0$, it follows that

$\displaystyle\mathcal{I}(a)\geq\mathcal{I}(\delta)\frac{1/2-a}{1/2-\delta}.$

Thus, it remains to show that

$\displaystyle\frac{1/2-a}{1/2-\delta}-\frac{1}{1-\varrho\delta}>0.$

With some elementary transformations, we obtain

$\displaystyle\frac{1/2-a}{1/2-\delta}-\frac{1}{1-\varrho\delta}=\frac{1+\varrho\delta-2\delta}{(1-\varrho\delta)(1-2\delta)}-\frac{1}{1-\varrho\delta}=\frac{\varrho\delta}{(1-\varrho\delta)(1-2\delta)}>0,$

which completes the proof of the case $\delta\in(0,1/2)$.

In the case $\delta=1/2$, take an $\varepsilon\in(0,1)$ and use (4.11) to
obtain

$\displaystyle\frac{\mathbf{E}f_{k}(C_{n,d})}{{n\choose k}}$
$\displaystyle=\frac{\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq\frac{d-k-1}{n-k-1}(n-k-1)]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq\frac{d-1}{n-1}(n-1)]}$
$\displaystyle\leq\frac{\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq\frac{d-k-1}{n-k-1}(n-k-1)]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq\frac{(1-\varepsilon)d-1}{n-1}(n-1)]}.$

Again, applying (2.8) this yields

$\displaystyle\frac{\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq\frac{d-k-1}{n-k-1}(n-k-1)]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq\frac{(1-\varepsilon)d-1}{n-1}(n-1)]}$
$\displaystyle\quad\underset{d\to\infty}{\sim}D(\varrho,\varepsilon)\cdot\exp\left\\{-n\left(\Big{(}\frac{n-k-1}{n}\Big{)}\mathcal{I}\Big{(}\frac{d-k-1}{n-k-1}\Big{)}-\Big{(}\frac{n-1}{n}\Big{)}\mathcal{I}\Big{(}\frac{(1-\varepsilon)d-1}{n-1}\Big{)}\right)\right\\}$
$\displaystyle\quad\underset{d\to\infty}{\sim}D(\varrho,\varepsilon)\cdot\exp\left\\{-n\left(\Big{(}1-\frac{\varrho}{2}\Big{)}\mathcal{I}(a)-\mathcal{I}\Big{(}\frac{1-\varepsilon}{2}\Big{)}+o(1)\right)\right\\},$

where $D(\varrho,\varepsilon)$ is some constant which only depends on
$\varrho$ and $\varepsilon$. Since $a<\delta=1/2$, we can choose
$\varepsilon>0$ sufficiently close to zero, such that

$\displaystyle\Big{(}1-\frac{\varrho}{2}\Big{)}\mathcal{I}(a)>\mathcal{I}\Big{(}\frac{1-\varepsilon}{2}\Big{)}.$

This proves the claim.

Now, consider the regime (4.9). Since $\delta>1/2$, it holds that

$\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]=1.$

Defining $Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$, yields

$\displaystyle\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq d-k-1]$
$\displaystyle=\mathbf{P}\bigg{[}Z_{n-k-1}\leq\frac{2(d-k-1)-(n-k-1)}{\sqrt{n-k-1}}\bigg{]}.$

Since

$\displaystyle
n-k-1=\Big{(}\frac{2}{\delta}-2\Big{)}d+(c-b)\sqrt{d}+o(\sqrt{d})$

and

$\displaystyle 2(d-k-1)-(n-k-1)=-(c+b)\sqrt{d}+o(\sqrt{d}),$

we have

$\displaystyle\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq
d-k-1]=\mathbf{P}\bigg{[}Z_{n-k-1}\leq-\frac{c+b}{\sqrt{2/\delta-2}}+o(1)\Big{]}\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\bigg{(}-\frac{c+b}{\sqrt{2/\delta-2}}\bigg{)},$

following from the central limit theorem for the binomial distribution.
Combining this with (4.11) yields the claim.

Finally, consider the regime (4.10). Similar to the previous case, we obtain

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq\frac{2(d-1)-(n-1)}{\sqrt{n-1}}\right]$
$\displaystyle=\mathbf{P}\bigg{[}Z_{n-1}\leq-\frac{c}{\sqrt{2}}+o(1)\bigg{]}\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}$

and in the same way also

$\displaystyle\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq d-k-1]$
$\displaystyle=\mathbf{P}\bigg{[}Z_{n-k-1}\leq\frac{2(d-k-1)-(n-k-1)}{\sqrt{n-k-1}}\bigg{]}$
$\displaystyle=\mathbf{P}\bigg{[}Z_{n-k-1}\leq-\frac{c+b}{\sqrt{2}}+o(1)\bigg{]}\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c+b}{\sqrt{2}}\Big{)}.$

Combining this with (4.11) completes the proof. ∎

###  4.3. Large deviation principles

In this section, we state a kind of large deviation principle for the expected
face numbers of both $D_{n,d}$ and $C_{n,d}$, as $n$, $d$ and $k$ tend to
infinity in a linearly coordinated way. That is, we consider the regime where
$k=k(d)$ and $n=n(d)$ are such that

$\displaystyle{k\over d}\to\varrho\quad\text{and}\quad{d\over
n}\to\delta,\qquad\text{as }d\to\infty,$ (4.12)

for parameters $\varrho,\delta\in(0,1)$. We start with the result for the
expected number of $k$-faces of $D_{n,d}$. It is illustrated in Figure 1 and
uncovers a threshold phenomenon around the point where $\varrho=2-1/\delta$.

######  Theorem 4.6.

Consider the Donoho-Tanner random cone $D_{n,d}$ and suppose that (4.12)
holds. Then

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}f_{k}(D_{n,d})=\begin{cases}-{1\over\delta}\log(2-2\delta)+\varrho\log\big{(}{2\over\varrho}-2\big{)}+\log\big{(}{1-\delta\over\delta(1-\varrho)}\big{)}&:\varrho>2-1/\delta,\\\
{1\over\delta}\log{1\over\delta}-\varrho\log\varrho-({1\over\delta}-\varrho)\log({1\over\delta}-\varrho)&:\varrho<2-1/\delta.\end{cases}$

Figure 1. In black: Values of ${1\over d}\log\mathbf{E}f_{k}(D_{n,d})$ for
$\delta=2/3$ and $d=100$;  In red: Information functions in the corresponding
case. Left panel: Information function for $\varrho>2-1/\delta=1/2$ (that is,
$k>d/2$); Right panel: Information function for $\varrho<2-1/\delta=1/2$ (that
is, $k<d/2$).

###### Proof.

Recalling that $\textup{Bin}(m,p)$ stands for a binomial random variable with
parameters $m\in\mathbb{N}$ and $p\in(0,1)$, the expression in (3.2) can be
rewritten in the form

$\displaystyle{\mathbf{E}f_{k}(D_{n,d})\over{n\choose k}}$
$\displaystyle=1-\mathbf{P}[\textup{Bin}(n-k-1,1/2)<n-d]=\mathbf{P}[\textup{Bin}(n-k-1,1/2)\geq
n-d].$

Now, put

$a:=\frac{1/\delta-1}{1/\delta-\varrho}$

and observe that, as $d\to\infty$, we have $n-d=(n-k-1)(a+o(1))$. Assuming
first that $a>1/2$, which is equivalent to $\varrho>2-1/\delta$, we may now
apply (2.4) with $m=n-k-1$ to conclude that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{P}[\textup{Bin}(n-k-1,1/2)\geq n-d]$
$\displaystyle=\lim_{d\to\infty}{1\over
d}\log\mathbf{P}[\textup{Bin}[n-k-1,1/2]\geq(n-k-1)(a+o(1))]$
$\displaystyle=\lim_{d\to\infty}{n-k-1\over d}{1\over
n-k-1}\log\mathbf{P}[\textup{Bin}[n-k-1,1/2]\geq(n-k-1)(a+o(1))]$
$\displaystyle=-\Big{(}{1\over\delta}-\varrho\Big{)}\mathcal{I}(a),$

since $(n-k-1)/d$ tends to $(1/\delta)-\varrho$, as $d\to\infty$, by
assumption (4.12). Note that $\mathcal{I}(a)$ is given by

$\displaystyle\mathcal{I}(a)=\mathcal{I}\bigg{(}{{1\over\delta}-1\over{1\over\delta}-\varrho}\bigg{)}=-{1\over
1-\delta\varrho}\Big{[}\log\Big{(}{1-\delta\varrho\over
2-2\delta}\Big{)}+\delta\log\Big{(}{1-\delta\over\delta(1-\varrho)}\Big{)}+\delta\varrho\log\Big{(}{2\delta(1-\varrho)\over
1-\delta\varrho}\Big{)}\Big{]},$

due to (2.6). To conclude the result in this case, it remains to observe that

$\displaystyle\log\mathbf{E}f_{k}(D_{n,d})=\log{\mathbf{E}f_{k}(D_{n,d})\over{n\choose
k}}+\log{n\choose k}.$

The second summand on the right-hand side, divided by $d$, converges to the
follwing function depending on $\delta$ and $\varrho$:

$\lim_{d\to\infty}{1\over d}\log{n\choose
k}={1\over\delta}\log{1\over\delta}-\varrho\log\varrho-\Big{(}{1\over\delta}-\varrho\Big{)}\log\Big{(}{1\over\delta}-\varrho\Big{)}=:\mathcal{J}(\delta,\varrho).$
(4.13)

Indeed, using three times Stirling’s formula together with our assumption on
the linear growth of $k$ and $n$ relative to $d$ we see that

$\displaystyle\lim_{d\to\infty}{1\over d}\log{n\choose k}$
$\displaystyle=\lim_{d\to\infty}{1\over
d}\log{(n/e)^{n}\over(k/e)^{k}((n-k)/e)^{n-k}}$
$\displaystyle=\lim_{d\to\infty}{1\over
d}\Big{[}{d\over\delta}\log{d\over\delta}-\varrho d\log(\varrho
d)-d\Big{(}{1\over\delta}-\varrho\Big{)}\log\Big{(}n\Big{(}{1\over\delta}-\varrho\Big{)}\Big{)}\Big{]}$
$\displaystyle={1\over\delta}\log{1\over\delta}-\varrho\log\varrho-\Big{(}{1\over\delta}-\varrho\Big{)}\log\Big{(}{1\over\delta}-\varrho\Big{)}.$

Thus, using (4.13) we conclude that

$\displaystyle\lim_{d\to\infty}{1\over d}\log\mathbf{E}f_{k}(D_{n,d})$
$\displaystyle=\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}f_{k}(D_{n,d})\over{n\choose k}}+\lim_{d\to\infty}{1\over
d}\log{n\choose k}$
$\displaystyle=-\Big{(}{1\over\delta}-\varrho\Big{)}\mathcal{I}(a)+\mathcal{J}(\delta,\varrho).$

Simplifying this expression yields the result.

On the other hand, if $a<1/2$, which is equivalent to $\varrho<2-1/\delta$, we
have that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}f_{k}(D_{n,d})=\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}f_{k}(D_{n,d})\over{n\choose k}}+\lim_{d\to\infty}{1\over
d}\log{n\choose k}=0+\mathcal{J}(\delta,\varrho).$

This completes the argument. ∎

Our next result is the analogue to Theorem 4.6 in the Cover-Efron case with
the same assumption on the growth of $n$, $d$ and $k$. It is illustrated in
Figure 2.

######  Theorem 4.7.

Consider the Cover-Efron random cone $C_{n,d}$ and suppose that (4.12) holds.
Then

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}f_{k}(C_{n,d})=\begin{cases}{1\over\delta}\log{1\over\delta}-\varrho\log\varrho-\big{(}{1\over\delta}-\varrho\big{)}\log\big{(}{1\over\delta}-\varrho\big{)}&:\delta>{1\over
2}\text{ and }\varrho<2-{1\over\delta},\\\
-{1\over\delta}\log(2-2\delta)+\varrho\log\big{(}{2\over\varrho}-2\big{)}+\log\big{(}{1-\delta\over\delta(1-\varrho)}\big{)}&:\delta>{1\over
2}\text{ and }\varrho>2-{1\over\delta},\\\
\varrho\log\big{(}{2\over\varrho}-2\big{)}-\log(1-\varrho)&:\delta<{1\over
2}.\end{cases}$

Figure 2. In black: Values of ${1\over d}\log\mathbf{E}f_{k}(C_{n,d})$ for
$d=100$;  In red: Information functions in the corresponding case. Left panel:
$\delta=2/3$ and information function for $\varrho<2-1/\delta=1/2$ (that is,
$k<d/2$); Middle panel: $\delta=2/3$ and information function for
$\varrho>2-1/\delta=1/2$ (that is, $k>d/2$); Right panel: $\delta=1/3$.

###### Proof.

Like in the proof of Theorem 4.4, we put

$a:=\frac{1-\varrho}{1/\delta-\varrho}$

and obtain $d-k-1=(a+o(1))(n-k-1)$. Using the representation (4.1) of
$\mathbf{E}f_{k}(C_{n,d})$ as binomial coefficients yields

$\displaystyle{1\over d}\log{\mathbf{E}f_{k}(C_{n,d})\over{n\choose k}}$
$\displaystyle={1\over d}\log\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq
d-k-1]-{1\over d}\log\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]$
$\displaystyle={n-k-1\over d}{1\over
n-k-1}\log\mathbf{P}[\textup{Bin}(n-k-1,1/2)\leq(n-k-1)(a+o(1))]$
$\displaystyle\qquad-{n-1\over d}{1\over
n-1}\log\mathbf{P}[\textup{Bin}(n-1,1/2)\leq(n-1)(\delta+o(1))].$

Since $(n-k-1)/d\to(1/\delta)-\varrho$ and $(n-1)/d\to 1/\delta$, as
$d\to\infty$, we conclude from (2.5) that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}f_{k}(C_{n,d})\over{n\choose
k}}=-\Big{(}{1\over\delta}-\varrho\Big{)}\mathcal{I}(a)+{1\over\delta}\mathcal{I}(\delta)$

provided that $a<1/2$ and $\delta<1/2$. Since $a<1/2$ is equivalent to
$\varrho>2-1/\delta$, the latter condition is automatically fulfilled as long
as $\delta<1/2$. Note that the function $\mathcal{I}(a)$ is defined in (2.6).
Now, assume that still $\delta>1/2$, but $a<1/2$. Then

$\displaystyle\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}f_{k}(C_{n,d})\over{n\choose
k}}=-\Big{(}{1\over\delta}-\varrho\Big{)}\mathcal{I}(a).$

On the other hand, if $a>1/2$ and $\delta>1/2$, then the limit is just zero.
Combining these observations with (4.13), we obtain that

$\displaystyle\lim_{d\to\infty}{1\over d}\log{\mathbf{E}f_{k}(C_{n,d})}$
$\displaystyle=\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}f_{k}(C_{n,d})\over{n\choose k}}+\lim_{d\to\infty}{1\over
d}\log{n\choose k}$
$\displaystyle=\begin{cases}\mathcal{J}(\delta,\varrho)&:\delta>{1\over
2}\text{ and }\varrho<2-{1\over\delta},\\\
-\big{(}{1\over\delta}-\varrho\big{)}\mathcal{I}(a)+\mathcal{J}(\delta,\varrho)&:\delta>{1\over
2}\text{ and }\varrho>2-{1\over\delta},\\\
-\big{(}{1\over\delta}-\varrho\big{)}\mathcal{I}(a)+{1\over\delta}\mathcal{I}(\delta)+\mathcal{J}(\delta,\varrho)&:\delta<{1\over
2},\\\ \end{cases}$

where $\mathcal{J}(\delta,\varrho)$ is defined in (4.13). Simplification of
the right hand side completes the argument. ∎

###  4.4. Application to random Gale diagrams

A new model to generate combinatorially isomorphic polytopes by choosing their
so-called Gale diagram at random has recently been introduced by Schneider
[34], taking up a suggestion of Gale [19]. For completeness we recall that
with $n\geq d+1$ points $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$ with affine hull
equal to $\mathbb{R}^{d}$ one can associate points
$\bar{x}_{1},\ldots,\bar{x}_{n}\in\mathbb{R}^{n-d-1}$ which linearly span
$\mathbb{R}^{n-d-1}$, a so-called Gale transform of $x_{1},\ldots,x_{n}$, as
follows. Consider the $(d+1)\times n$-matrix

$A:=\begin{pmatrix}1&1&\cdots&1\\\ |&|&&|\\\ x_{1}&x_{2}&\cdots&x_{n}\\\
|&|&&|\end{pmatrix}.$

By assumption on $x_{1},\ldots,x_{n}$ the kernel $\ker(A)$ of $A$ has
dimension $n-d-1$. Let $\tilde{x}_{1},\ldots,\tilde{x}_{n-d-1}$ be a basis of
$\ker(A)$. If $\bar{A}$ denotes the matrix with columns
$\tilde{x}_{1},\ldots,\tilde{x}_{n-d-1}$ then $A\bar{A}=0$. The $n$ ordered
rows $\bar{x}_{1},\ldots,\bar{x}_{n}$ of $\bar{A}$ are called a Gale transform
of $x_{1},\ldots,x_{n}$, and by a Gale diagram one understands the vector
configuration $\\{\bar{x}_{1},\ldots,\bar{x}_{n}\\}$ drawn in
$\mathbb{R}^{n-d-1}$. The vectors $\bar{x}_{1},\ldots,\bar{x}_{n}$ satisfy
$\bar{x}_{1}+\ldots+\bar{x}_{n}=o$ with $o$ being the origin of
$\mathbb{R}^{n-d-1}$. Of course, Gale transforms are not unique, since the
choice of a basis for $\ker(A)$ was arbitrary. On the other hand, all choices
for $\bar{A}$ differ by multiplication with a non-singular matrix. Since we
are interested in the combinatorial quantities only, the precise choice for
$\bar{A}$ is therefore irrelevant for us. We also remark that a collection
$\bar{x}_{1},\ldots,\bar{x}_{n}$ of vectors in $\mathbb{R}^{n-d-1}$ with
$\operatorname{pos}(\bar{x}_{1},\ldots,\bar{x}_{n})=\mathbb{R}^{n-d-1}$ is the
Gale diagram of a sequence $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$ (more
precisely, of many sequences, but their convex hulls are combinatorially all
equivalent). We refer, for example, to the monographs [22, 28] for further
background material on Gale transforms and diagrams.

To recall the model suggested in [34], we let $X_{1},\ldots,X_{n}$ be $n\geq
d+1$ independent $(n-d-1)$-dimensional random vectors distributed according to
a probability measure $\phi$ in $\mathbb{R}^{n-d-1}$ which has the property
that $\phi$ is even and puts mass zero to each linear hyperplane. Following
[34], a $(\phi,n)$ random Gale diagram is the collection of random points
$X_{1},\ldots,X_{n}$, conditionally on the event that the origin $o$ belongs
to the (interior) of their convex hull. As a consequence, there are almost
surely random scalars $\lambda_{1},\ldots,\lambda_{n}>0$ such that
$\bar{a}_{1}:=\lambda_{1}X_{1},\ldots,\bar{a}_{n}:=\lambda_{n}X_{n}$ satisfy
$\bar{a}_{1}+\ldots+\bar{a}_{n}=o$. Therefore,
$\bar{a}_{1},\ldots,\bar{a}_{n}$ is the Gale transform of some random points
$a_{1},\ldots,a_{n}$ in $\mathbb{R}^{d}$ whose convex hull is denoted by
$G_{n,d}$. Following [34], $G_{n,d}$ is called a random Gale polytope. As
explained above, this does not define the random Gale polytope $G_{n,d}$
uniquely. Rather is defines a whole class of random polytopes. On the other
hand, all random polytopes arising in this way are combinatorially equivalent,
which implies that for any $k\in\\{0,1,\ldots,d-1\\}$ the random variable
$f_{k}(G_{n,d})$ is well defined. Since we are interested in these quantities
only, without ambiguity we refer to $G_{n,d}$ as the random Gale polytope in
$\mathbb{R}^{d}$ generated by $n$ points.

Theorem 2 in [34] uncovers a threshold phenomenon for the expected number of
$k$-dimensional faces of the random Gale polytopes $G_{n,d}$ in high
dimensions, more precisely, if $d$, $n$ and $k$ tend to infinity in a linearly
coordinated way (this is rephrased as (4.14) below). As an application of the
results developed in this section we can strengthen and refine this as
follows.

######  Corollary 4.8.

Let $G_{n,d}$ be a random Gale polytope. Suppose that $k=k(d)$ and $n=n(d)$
are such that

${d\over n}\to\delta\qquad\text{and}\qquad{k\over d}\to\varrho,\qquad{\rm
as}\;\;d\to\infty$

for $\delta\in(0,1)$ and $\varrho\in(0,1)$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(G_{n,d})}{{n\choose
k+1}}=\begin{cases}1&:\varrho<\max\\{0,2-1/\delta\\},\\\
0&:\varrho>\max\\{0,2-1/\delta\\}.\end{cases}$ (4.14)

Furthermore, if $\delta>1/2$ and

$\displaystyle n=\frac{d}{\delta}+c\sqrt{d}+o(\sqrt{d})\quad\text{and}\quad
k=\Big{(}2-\frac{1}{\delta}\Big{)}d+b\sqrt{d}+o(\sqrt{d}),\qquad\text{as
}d\to\infty,$

for parameters $c,b\in\mathbb{R}$, then it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(G_{n,d})}{{n\choose
k+1}}=\Phi\bigg{(}-\frac{c+b}{\sqrt{2/\delta-2}}\bigg{)}.$

In the case where

$\displaystyle n=2d+c\sqrt{d}+o(\sqrt{d})\quad\text{and}\quad
k=b\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for constants $c\in\mathbb{R}$ and $b\geq 0$, it holds that

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}f_{k}(G_{n,d})}{{n\choose
k+1}}=\frac{\Phi(-(c+b)/\sqrt{2})}{\Phi(-c/\sqrt{2})}.$

###### Proof.

Using the description of faces by means of Gale diagrams, it has been shown in
[34, Equation (3)] that $\mathbf{E}f_{k}(G_{n,d})$ can be expressed in terms
of binomial probabilities:

${\mathbf{E}f_{k}(G_{n,d})\over{n\choose
k+1}}={\mathbf{P}[\textup{Bin}(n-k-2,1/2)\leq
d-k-1]\over\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d]}.$

Comparing this to (4.1) yields that

$\mathbf{E}f_{k}(G_{n,d})=\mathbf{E}f_{k+1}(C_{n,d+1}),$

where $C_{n,d+1}$ is the Cover-Efron random cone in $\mathbb{R}^{d+1}$
generated by $n$ points, see also [34, Equation (4)]. The result thus follows
from that on the Cover-Efron random cone in Theorem 4.4. ∎

##  5\. Limit theorems for the expected conic intrinsic volumes and
quermassintegrals

This section covers various limit theorems for the expected conic intrinsic
volumes and conic quermassintegrals of the random cones introduced in Section
3.

###  5.1. Distributional limit theorems for the conic intrinsic volumes

Here, we state distributional limit theorems, including central limit
theorems, for random variables that take value $k\in\\{0,1,\ldots,d\\}$ with
probability $\mathbf{E}\upsilon_{k}(D_{n,d})$ in the Donoho-Tanner case, and
$\mathbf{E}\upsilon_{k}(C_{n,d})$ in the Cover-Efron case.

Starting with the Donoho-Tanner random cone $D_{n,d}$, we first provide an
explicit formula for $\mathbf{E}\upsilon_{k}(D_{n,d})$, which we couldn’t
locate in the existing literature.

######  Lemma 5.1.

Fix integers $0<d\leq n$. Let $D_{n,d}$ be a Donoho-Tanner random cone. Then,
it holds that

$\displaystyle\mathbf{E}v_{k}(D_{n,d})=\begin{cases}{1\over 2^{n}}{n\choose
k}&:k\in\\{0,\ldots,d-1\\},\\\
1-\sum_{j=0}^{d-1}\frac{1}{2^{n}}\binom{n}{j}&:k=d.\end{cases}$

###### Proof.

Recall from Section 3 that the Donoho-Tanner random cone $D_{n,d}$,
conditioned on the event that $D_{n,d}\neq\mathbb{R}^{d}$, has the same
distribution as the Cover-Efron random cone $C_{n,d}$. Thus, we can retrace
the formulas for the expected conic intrinsic volumes of $D_{n,d}$ back to
(3.5). For $k\in\\{0,\dots,d-1\\}$, this yields

$\displaystyle\mathbf{E}[\upsilon_{k}(D_{n,d})]$
$\displaystyle=\mathbf{E}\big{[}\upsilon_{k}(D_{n,d})\mathbbm{1}_{\\{D_{n,d}\neq\mathbb{R}^{d}\\}}\big{]}+\mathbf{E}\big{[}\upsilon_{k}(\mathbb{R}^{d})\mathbbm{1}_{\\{D_{n,d}=\mathbb{R}^{d}\\}}\big{]}$
$\displaystyle=\mathbf{P}[D_{n,d}\neq\mathbb{R}^{d}]\cdot\mathbf{E}[\upsilon_{k}(D_{n,d})|D_{n,d}\neq\mathbb{R}^{d}].$

Now, we can use (3.5) and Wendel’s formula
$\mathbf{P}[D_{n,d}\neq\mathbb{R}^{d}]=C(n,d)/2^{n}$, see [35, Theorem 8.2.1]
or [39], to obtain

$\displaystyle\mathbf{E}[\upsilon_{k}(D_{n,d})]=\frac{C(n,d)}{2^{n}}\cdot\binom{n}{k}\frac{1}{C(n,d)}=\binom{n}{k}\frac{1}{2^{n}},$

for $k\in\\{0,\dots,d-1\\}$. Using that
$\upsilon_{0}(C)+\ldots+\upsilon_{d}(C)=1$ for a cone
$C\subset\mathbb{R}^{d}$, we obtain

$\displaystyle\mathbf{E}[\upsilon_{d}(D_{n,d})]=1-\sum_{j=0}^{d-1}\binom{n}{j}\frac{1}{2^{n}},$

which completes the proof. ∎

We are now prepared to present our main result for the expected conic
intrinsic volumes of the Donoho-Tanner random cones, which is illustrated in
Figure 3.

######  Theorem 5.2.

Let $D_{n,d}$ be a Donoho-Tanner random cone and let $X_{n,d}$ be a random
variable with probability law
$\mathbf{P}[X_{n,d}=k]=\mathbf{E}\upsilon_{k}(D_{n,d})$ for $k=0,\dots,d$.
Suppose $n=n(d)$ is such that

$\displaystyle\frac{d}{n}\longrightarrow\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(1/2,1)$. Then, we obtain the central limit theorem

$\displaystyle\frac{2X_{n,d}-n}{\sqrt{n}}\overset{d}{\underset{d\to\infty}{\longrightarrow}}N(0,1).$

In the case where $\delta=1/2$, and more precisely, where

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for a parameter $c\in\mathbb{R}$, it holds that

$\displaystyle\frac{2X_{n,d}-n}{\sqrt{n}}\overset{d}{\underset{d\to\infty}{\longrightarrow}}Z,$

where $Z$ is a random variable with distribution

$\displaystyle\mathbf{P}[Z\leq t]=\Phi(t),\quad
t<-\frac{c}{\sqrt{2}},\qquad\text{and}\qquad\mathbf{P}\Big{[}Z=-\frac{c}{\sqrt{2}}\Big{]}=\Phi\Big{(}\frac{c}{\sqrt{2}}\Big{)}.$

Figure 3. In black: Distribution function of $(2X_{n,d}-n)/\sqrt{n}$ at
discontinuity points; In red: Limiting distribution function. Left panel:
First case with $\delta=2/3$, $d=400$; Right panel: Second case with $c=-2$,
$d=400$.

###### Proof.

For $\delta\in(1/2,1)$ and $t\in\mathbb{R}$, we have

$\displaystyle\mathbf{P}\bigg{[}\frac{2X_{n,d}-n}{\sqrt{n}}\leq
t\bigg{]}=\mathbf{P}\left[X_{n,d}\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\right]=\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\right],$

where we used that $\frac{n}{2}+t\sqrt{\frac{n}{4}}<d$ for sufficiently large
$d$ and in this case, the $k$-th conic intrinsic volume of $D_{n,d}$ coincides
with the probability of the event $\\{\textup{Bin}(n,1/2)=k\\}$, see Lemma
5.1. Then, the central limit theorem for the binomial distribution yields the
claim.

Now, let $n=2d+c\sqrt{d}+o(\sqrt{d})$ for a parameter $c\in\mathbb{R}$. In the
case $t<-c/\sqrt{2}$, we observe that for $d$ sufficiently large, we have

$\displaystyle\frac{n}{2}+t\sqrt{\frac{n}{4}}=d+\frac{c}{2}\sqrt{d}+t\sqrt{\frac{d}{2}+\frac{c}{4}\sqrt{d}+o(\sqrt{d})}+o(\sqrt{d})=d+\bigg{(}\frac{c}{2}+\frac{t}{\sqrt{2}}\bigg{)}\sqrt{d}+o(\sqrt{d})<d.$

Thus, we obtain

$\displaystyle\mathbf{P}\left[X_{n,d}\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\right]=\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\right]\to\Phi(t)$

for $t<-c/\sqrt{2}$. In the case $t>-c/\sqrt{2}$, we have that
$\frac{n}{2}+t\sqrt{\frac{n}{4}}>d$ for $d$ sufficiently large, and the
probability converges to $1$, which yields the claim. ∎

Similar to the Donoho-Tanner case, we can also derive distributional limit
theorems for the expected intrinsic volumes of the Cover-Efron random cone.
This is illustrated in Figure 4.

Figure 4. Illustration of Theorem 5.3 for $d=400$. Left panel: The case
$\delta=2/3$; distribution function of $2(X_{n,d}-n)/\sqrt{n}$ in black,
limiting distribution function in  red. Middle panel: The case $\delta=2/5$,
counting density of $X_{n,d}$ in black, counting density of $d-Z$ in  red.
Right panel: The critical case $\delta=1/2$, $b=-2$; distribution function of
$2(X_{n,d}-n)/\sqrt{n}$ in black, limiting distribution function in  red.

######  Theorem 5.3.

Let $C_{n,d}$ be a Cover-Efron random cone and let $X_{n,d}$ be the random
variables with probability law
$\mathbf{P}[X_{n,d}=k]=\mathbf{E}\upsilon_{k}(C_{n,d})$ for $k=0,\dots,d$.
Suppose that $n=n(d)$ is such that

$\displaystyle\frac{d}{n}\longrightarrow\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(0,1)$. In the case where $\delta\in(1/2,1)$, we
obtain the central limit theorem

$\displaystyle\frac{2X_{n,d}-n}{\sqrt{n}}\overset{d}{\underset{d\to\infty}{\longrightarrow}}N(0,1).$

In the case where $\delta\in(0,1/2)$, it holds that

$\displaystyle d-X_{n,d}\overset{d}{\underset{d\to\infty}{\longrightarrow}}Z,$

where $Z$ is a random variable with values in $\mathbb{N}_{0}$ whose
distribution is given by

$\displaystyle\mathbf{P}[Z=0]=\frac{1}{2}\cdot\frac{1-2\delta}{1-\delta},\qquad\text{and}\qquad\mathbf{P}[Z=k]=\frac{1}{2\delta}\cdot\frac{1-2\delta}{1-\delta}\cdot\Big{(}1-\frac{1-2\delta}{1-\delta}\Big{)}^{k},\quad
k\in\mathbb{N}.$ (5.1)

For $\delta=1/2$, and more precisely,

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for a parameter $c\in\mathbb{R}$, we obtain

$\displaystyle\frac{2X_{n,d}-n}{\sqrt{n}}\overset{d}{\underset{d\to\infty}{\longrightarrow}}N(0,1)\,\Big{|}\Big{\\{}N(0,1)<-\frac{c}{\sqrt{2}}\Big{\\}},$

where the latter notation indicates a random variable whose distribution is
given by the conditional distribution of $N(0,1)$ given the event
$\\{N(0,1)<-c/\sqrt{2}\\}$.

###### Proof.

For $\delta\in(1/2,1)$, the law of large numbers implies that

$\displaystyle\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]=1.$

Recall the formulas (3.5) for the conic intrinsic volumes of $C_{n,d}$. Since

$\displaystyle\frac{n}{2}+t\sqrt{\frac{n}{4}}=\frac{d}{2\delta}+o(d)<d$

for all $t\in\mathbb{R}$ and $d$ sufficiently large, we obtain

$\displaystyle\mathbf{P}\left[X_{n,d}\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\,\right]$
$\displaystyle=\frac{1}{2^{n}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}\sum_{k=0}^{\lfloor\frac{n}{2}+t\sqrt{\frac{n}{4}}\rfloor}\binom{n}{k}$
$\displaystyle\underset{d\to\infty}{\sim}\sum_{k=0}^{\lfloor\frac{n}{2}+t\sqrt{\frac{n}{4}}\rfloor}\frac{\binom{n}{k}}{2^{n}}$
$\displaystyle=\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\,\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi(t)$

from the central limit theorem for binomial random variables. This proves the
first claim.

In the case $\delta\in(0,1/2)$ we obtain for, $k\in\mathbb{N}$,

$\displaystyle\mathbf{P}[d-X_{n,d}=k]$ $\displaystyle=\mathbf{P}[X_{n,d}=d-k]$
$\displaystyle=\frac{\mathbf{P}[\textup{Bin}(n,1/2)=d-k]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}$
$\displaystyle=\frac{\mathbf{P}\left[\textup{Bin}(n,1/2)=(\frac{d-k}{n})n\right]}{\mathbf{P}\big{[}\textup{Bin}(n-1,1/2)\leq(\frac{d-1}{n-1})(n-1)\big{]}}.$

Since both sequences $(d-k)/n$ and $(d-1)/(n-1)$ converge to
$\delta\in(0,1/2)$, as $d\to\infty$, we can apply the asymptotic equivalence
(2.8) in the denominator and (2.7) in the numerator and arrive at

$\displaystyle\mathbf{P}[d-X_{n,d}=k]\underset{d\to\infty}{\sim}\frac{\exp\left\\{-n\cdot\mathcal{I}(\frac{d-k}{n})\right\\}}{\exp\big{\\{}-(n-1)\cdot\mathcal{I}(1-\frac{d-1}{n-1})\big{\\}}}\cdot\frac{2(1-\delta)-1}{1-\delta}.$

Combined with the definition of the information function $\mathcal{I}(x)$, see
(2.6), we obtain

$\displaystyle\exp\left\\{-n\cdot\mathcal{I}\Big{(}\frac{d-k}{n}\Big{)}\right\\}=2^{-n}\Big{(}\frac{n-d+k}{n}\Big{)}^{d-n-k}\Big{(}\frac{n}{d-k}\Big{)}^{d-k}$

and

$\displaystyle\exp\left\\{-(n-1)\cdot\mathcal{I}\Big{(}1-\frac{d-1}{n-1}\Big{)}\right\\}=2^{-(n-1)}\Big{(}\frac{n-d}{n-1}\Big{)}^{d-n}\Big{(}\frac{n-1}{d-1}\Big{)}^{d-1}.$

This yields

$\displaystyle\mathbf{P}[d-X_{n,d}=k]$
$\displaystyle\underset{d\to\infty}{\sim}\frac{1-2\delta}{2(1-\delta)}\Big{(}\frac{n-d+k}{n}\Big{)}^{d-n-k}\Big{(}\frac{n}{d-k}\Big{)}^{d-k}\Big{(}\frac{n-1}{n-d}\Big{)}^{d-n}\Big{(}\frac{d-1}{n-1}\Big{)}^{d-1}$
$\displaystyle\hskip
6.25958pt=\frac{1-2\delta}{2(1-\delta)}\frac{n^{n}}{(n-1)^{n-1}}\frac{(d-1)^{d-1}}{(d-k)^{d}}\Big{(}\frac{n-d}{n-d+k}\Big{)}^{n-d}\Big{(}\frac{d-k}{n-d+k}\Big{)}^{k}$
$\displaystyle\hskip
6.25958pt=\frac{1-2\delta}{2(1-\delta)}\frac{n-1}{d-k}\Big{(}1-\frac{1}{n}\Big{)}^{-n}\Big{(}1-\frac{k-1}{d-1}\Big{)}^{1-d}\Big{(}1+\frac{k}{n-d}\Big{)}^{d-n}\Big{(}\frac{d-k}{n-d+k}\Big{)}^{k}.$

Now, we use that $d/n\to\delta$ and that

$\displaystyle\Big{(}1-\frac{1}{n}\Big{)}^{-n}\overset{}{\underset{d\to\infty}{\longrightarrow}}e,\quad\Big{(}1-\frac{k-1}{d-1}\Big{)}^{1-d}\overset{}{\underset{d\to\infty}{\longrightarrow}}e^{k-1},\quad\Big{(}1+\frac{k}{n-d}\Big{)}^{d-n}\overset{}{\underset{d\to\infty}{\longrightarrow}}e^{-k},$

to finally obtain

$\displaystyle\lim_{d\to\infty}\mathbf{P}[d-X_{n,d}=k]=\frac{1}{2\delta}\cdot\frac{1-2\delta}{1-\delta}\Big{(}\frac{\delta}{1-\delta}\Big{)}^{k}=\frac{1}{2\delta}\cdot\frac{1-2\delta}{1-\delta}\Big{(}1-\frac{1-2\delta}{1-\delta}\Big{)}^{k}.$

We consider the case $k=0$ separately. Here, we have

$\displaystyle\mathbf{P}[d-X_{n,d}=0]=\mathbf{P}[X_{n,d}=d]=\frac{\binom{n-1}{d-1}}{C(n,d)}=\frac{\mathbf{P}\big{[}\textup{Bin}(n-1,1/2)=(\frac{d-1}{n-1})(n-1)\big{]}}{2\mathbf{P}\big{[}\textup{Bin}(n-1,1/2)\leq(\frac{d-1}{n-1})(n-1)\big{]}}.$

Using (2.7) and (2.8), we arrive at

$\displaystyle\lim_{d\to\infty}\mathbf{P}[d-X_{n,d}=0]=\frac{1}{2}\cdot\frac{2(1-\delta)-1}{1-\delta}=\frac{1}{2}\cdot\frac{1-2\delta}{1-\delta},$

which completes the proof of the second claim.

Now, let $n=2d+c\sqrt{d}+o(\sqrt{d})$ for a parameter $c\in\mathbb{R}$. In the
same way as in the proof of Theorem 5.2 we observe that for $t<-c/\sqrt{2}$
and $d$ sufficiently large, we have $\frac{n}{2}+t\sqrt{\frac{n}{4}}<d.$
Furthermore, defining $Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$ and using the
central limit theorem for the binomial distribution, we obtain

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq\frac{2(d-1)-(n-1)}{\sqrt{n-1}}\right]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq-\frac{c}{\sqrt{2}}+o(1)\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

Thus, we obtain

$\displaystyle\mathbf{P}\left[X_{n,d}\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\right]$
$\displaystyle=\frac{1}{2^{n}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}\sum_{k=0}^{\lfloor\frac{n}{2}+t\sqrt{\frac{n}{4}}\rfloor}\binom{n}{k}$
$\displaystyle\underset{d\to\infty}{\sim}\frac{1}{\Phi(-c/\sqrt{2})}\mathbf{P}\left[\textup{Bin}(n,1/2)\leq\frac{n}{2}+t\sqrt{\frac{n}{4}}\,\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\frac{\Phi(t)}{\Phi(-c/\sqrt{2})},$

for $t<-c/\sqrt{2}$. In the case $t>-c/\sqrt{2}$, we have that
$\frac{n}{2}+t\sqrt{\frac{n}{4}}>d$ for $d$ sufficiently large, which yields
the claim. ∎

###  5.2. Limit theorems for the conic quermassintegrals

Recall from (2.9) that the conic intrinsic volumes $\upsilon_{k}$ and the
conic quermassintegrals $U_{k}$ satisfy the relation

$\displaystyle 2U_{k}(C)=2(\upsilon_{k+1}(C)+\upsilon_{k+3}(C)+\ldots)$

for any cone $C$ that is not a linear subspace. Thus, the quermassintegrals
$U_{k}$ are essentially the tail functions of the random variables $X_{n,d}$.
Hence, Theorem 5.3 suggests that for $k\to\infty$, the expectation
$\mathbf{E}U_{k}(C)$ behaves like the tail function of the limit distribution
given in Theorem 5.3. This is specified by the following theorem and
illustrated in Figure 5.

######  Theorem 5.4.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $n=n(d)$ and $k=k(d)$
are such that

$\displaystyle\frac{d}{n}\to\delta\quad\text{and}\quad
k=\frac{n}{2}+b\sqrt{\frac{n}{4}}+o(\sqrt{n}),\qquad\text{as }d\to\infty,$
(5.2)

for parameters $\delta\in(1/2,1)$ and $b\in\mathbb{R}$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\mathbf{E}2U_{k}(C_{n,d})=1-\Phi(b).$

In the case where

$\displaystyle n=2d+c\sqrt{d}+o(\sqrt{d})\quad\text{and}\quad
k=\frac{n}{2}+b\sqrt{\frac{n}{4}}+o(\sqrt{n}),\qquad\text{as }d\to\infty,$
(5.3)

for parameters $c,b\in\mathbb{R}$, it holds that

$\displaystyle\lim_{d\to\infty}\mathbf{E}2U_{k}(C_{n,d})=\begin{cases}1-\frac{\Phi(b)}{\Phi(-c/\sqrt{2})},&:b<-\frac{c}{\sqrt{2}},\\\
0,&:b\geq-\frac{c}{\sqrt{2}}.\end{cases}$

######  Remark 5.5.

In the case $\delta\in(0,1/2)$ which has been omitted above, the conic Crofton
formula (2.9) together with Theorem 5.3 imply an explicit formula for
$\lim_{d\to\infty}\mathbf{E}2U_{d-k}(C_{n,d})$, for fixed $k\in\mathbb{N}$, in
terms of the probabilities given in (5.1).

Figure 5. Left panel: Convergence in the regime (5.2) with $d=100$ and
$\delta=2/3$. Right panel: Convergence in the regime (5.3) with $d=100$ and
$c=-1$. The black points represent the values of $\mathbf{E}2U_{k}(C_{n,d})$
for $k=0,1,\dots d$. The  curve in red is the tail function of the
corresponding approximating distribution.

###### Proof of Theorem 5.4.

Consider the regime (5.2). Following (3.6), we can express the expected
quermassintegrals of $C_{n,d}$ in terms of binomial probabilities:

$\displaystyle\mathbf{E}2U_{k}(C_{n,d})=\frac{C(n,d)-C(n,k)}{C(n,d)}=1-\frac{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
k-1]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]}.$ (5.4)

The assumption $\delta>1/2$ yields that the denominator of (5.4) converges to
$1$ as $d\to\infty$, due to the law of large numbers. For the numerator, we
can use the central limit theorem for binomial random variables and obtain

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq k-1]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq\frac{2(k-1)-(n-1)}{\sqrt{n-1}}\right]=\mathbf{P}\left[Z_{n-1}\leq
b+o(1)\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi(b),$

where we defined $Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$. This proves the
first claim.

Now consider the regime (5.3). For $b<-c/\sqrt{2}$, we obtain that

$\displaystyle
k=\frac{n}{2}+b\sqrt{\frac{n}{4}}+o(\sqrt{n})=d+\Big{(}\frac{c}{2}+\frac{b}{\sqrt{2}}\Big{)}\sqrt{d}+o(\sqrt{d})<d$

for sufficiently large $d$. Thus, we can use the representation (5.4) of
$\mathbf{E}U_{k}(C_{n,d})$ and apply the central limit theorem for the
binomial distribution to the denominator:

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq\frac{2(d-1)-(n-1)}{\sqrt{n-1}}\right]$
$\displaystyle=\mathbf{P}\left[Z_{n-1}\leq-\frac{c}{\sqrt{2}}+o(1)\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

Similarly, the numerator of (5.4) converges to $\Phi(b)$ as $d\to\infty$,
which yields

$\displaystyle\lim_{d\to\infty}\mathbf{E}2U_{k}(C_{n,d})=1-\frac{\Phi(b)}{\Phi(-c/\sqrt{2})},\quad
b<-\frac{c}{\sqrt{2}}.$

For $b>-c/\sqrt{2}$, we have that $k>d$ for sufficiently large $d$, which
implies

$\displaystyle\lim_{d\to\infty}\mathbf{E}2U_{k}(C_{n,d})=0.$

This completes the proof. ∎

We want to prove a similar result for $D_{n,d}$. To this end, we state the
fromulas for the expected conic quermassintegrals of $D_{n,d}$ in the
following lemma.

######  Lemma 5.6.

Fix integers $0\leq k\leq d\leq n$. Let $D_{n,d}$ be a Donoho-Tanner random
cone. Then, it holds that

$\displaystyle\mathbf{E}U_{k}(D_{n,d})=\begin{cases}{1\over
2^{n}}\sum_{l=k}^{n-1}\binom{n-1}{l}&:n-k\text{ even},\\\
\frac{1}{2^{n}}\sum_{l=k}^{n-2}\binom{n-1}{l}+\frac{1}{2^{n}}\sum_{l=d}^{n}\binom{n}{l}&:n-k\text{
odd}.\end{cases}$

###### Proof.

Suppose at first that $n-k$ is even. Then, the conic Crofton formula (2.9)
together with Lemma 5.1 yields

$\displaystyle\mathbf{E}U_{k}(D_{n,d})$
$\displaystyle=\mathbf{E}\upsilon_{k+1}(D_{n,d})+\mathbf{E}\upsilon_{k+3}(D_{n,d})+\ldots=\frac{1}{2^{n}}\left(\binom{n}{k+1}+\binom{n}{k+3}+\ldots+\binom{n}{n-1}\right).$

Using the relation $\binom{n}{k+1}=\binom{n-1}{k}+\binom{n-1}{k+1}$ yields the
first claim. In the case where $n-k$ is odd, we similarly obtain

$\displaystyle\mathbf{E}U_{k}(D_{n,d})$
$\displaystyle=\frac{1}{2^{n}}\left(\binom{n}{k+1}+\binom{n}{k+3}+\ldots+\binom{n}{n-2}\right)+\Bigg{(}1-\sum_{j=0}^{d-1}\frac{1}{2^{n}}\binom{n}{j}\Bigg{)}$
$\displaystyle=\frac{1}{2^{n}}\sum_{l=k}^{n-2}\binom{n-1}{l}+\frac{1}{2^{n}}\sum_{l=d}^{n}\binom{n}{l},$

which completes the proof. ∎

We can now present the analogue of Theorem 5.4 for the Donoho-Tanner random
cones. We remark that in this situation the case $\delta=1/2$ does not yield a
proper limit for $\mathbf{E}2U_{k}(D_{n,d})$ and is therefore omitted. The
case $\delta>1/2$ is illustrated in Figure 6.

######  Theorem 5.7.

Let $D_{n,d}$ be a Donoho-Tanner random cone. Suppose that $n=n(d)$ and
$k=k(d)$ are such that

$\displaystyle\frac{d}{n}\to\delta\quad\text{and}\quad
k=\frac{n}{2}+b\sqrt{\frac{n}{4}}+o(\sqrt{n}),\qquad\text{as }d\to\infty,$
(5.5)

for parameters $\delta\in(1/2,1)$ and $b\in\mathbb{R}$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\mathbf{E}2U_{k}(D_{n,d})=1-\Phi(b).$

Figure 6. Convergence in the regime (5.5) with $d=100$ and $\delta=2/3$. The
black points represent the values of $\mathbf{E}2U_{k}(C_{n,d})$ for
$k=0,1,\dots d$. The  red curve is the tail function of the approximating
distribution.

###### Proof.

By Lemma 5.6, the expected conic quermassintegrals of $D_{n,d}$ can be written
in terms of binomial probabilities:

$\displaystyle\mathbf{E}2U_{k}(D_{n,d})=\begin{cases}\mathbf{P}[\textup{Bin}(n-1,1/2)\geq
k]&:n-k\text{ even},\\\ \mathbf{P}[k\leq\textup{Bin}(n-1,1/2)\leq
n-2]+2\mathbf{P}[\textup{Bin}(n,1/2)\geq d]&:n-k\text{ odd}.\end{cases}$

In the given regime when additionally $n-k$ is even, we can use the central
limit theorem for binomial random variables to obtain

$\displaystyle\mathbf{E}2U_{k}(D_{n,d})=\mathbf{P}\left[Z_{n}\geq\frac{2k-n}{\sqrt{n}}\right]=\mathbf{P}\left[Z_{n}\geq
b+o(1)\right]\overset{}{\underset{d\to\infty}{\longrightarrow}}1-\Phi(b),$

where $Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$. In the case where $n-k$ is
odd, we use the law of large numbers and the fact that $\delta>1/2$ to observe
that

$\displaystyle\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n,1/2)\geq
d]=0,\qquad\text{and}\qquad\lim_{n\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)=n-1]=0.$

Thus, we also obtain

$\displaystyle\lim_{d\to\infty}\mathbf{E}2U_{k}(D_{n,d})=1-\Phi(b)$

in the case where $n-k$ is odd. This completes the proof. ∎

To conclude this section, we take a look at a critical case in the convergence
of $\mathbf{E}U_{d-k}(C_{n,d})$. In Theorem 4 of [25] Hug and Schneider proved
for all fixed $k\in\mathbb{N}$ that

$\displaystyle\lim_{d\to\infty}\mathbf{E}U_{d-k}(C_{n,d})=0$

if $n-2d$ is bounded from above, and that

$\displaystyle\lim_{d\to\infty}\sqrt{d}\cdot\mathbf{E}U_{d-k}(C_{n,d})=\frac{k}{\sqrt{\pi}}$

if $n=2d$. The next theorem considerably generalizes the last statement.

######  Theorem 5.8.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $n=n(d)$ is such that

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for a parameter $c\in\mathbb{R}$. Then, it holds that

$\displaystyle\lim_{d\to\infty}\sqrt{d}\cdot\mathbf{E}2U_{d-k}(C_{n,d})=\frac{e^{-c^{2}/4}}{\Phi(-c/\sqrt{2})}\cdot\frac{k}{\sqrt{\pi}}$

for all fixed $k\in\mathbb{N}$.

###### Proof.

Following (3.6), we can express the expected quermassintegral of $C_{n,d}$ in
terms of binomial probabilities:

$\displaystyle\mathbf{E}2U_{d-k}(C_{n,d})=1-\frac{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-k-1]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}=\frac{\sum_{l=1}^{k}\mathbf{P}[\textup{Bin}(n-1,1/2)=d-l]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}.$ (5.6)

As we already observed, the central limit theorem for the binomial
distribution implies that

$\displaystyle\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]=\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

Furthermore, the local limit theorem (2.1) yields that

$\displaystyle\mathbf{P}[\textup{Bin}(n-1,1/2)=d-l]$
$\displaystyle=\frac{\sqrt{2}}{\sqrt{\pi(n-1})}\exp\left\\{-\frac{1}{2}\left(\frac{2(d-l)-(n-1)}{\sqrt{n-k-1}}\right)^{2}\right\\}+o\left(\frac{1}{\sqrt{n}}\right)$
$\displaystyle=\frac{\sqrt{2}\cdot e^{-c^{2}/4}}{\sqrt{\pi
n}}+o\left(\frac{1}{\sqrt{n}}\right).$

Inserting both asymptotics into (5.6) yields

$\displaystyle\mathbf{E}2U_{d-k}(C_{n,d})\underset{d\to\infty}{\sim}\frac{k\sqrt{2}\cdot
e^{-c^{2}/4}}{\Phi(-c/\sqrt{2})\sqrt{\pi n}}$

Together with the observation that $\sqrt{d}/\sqrt{n}\to 1/\sqrt{2}$, this
yields the claim. ∎

###  5.3. Large deviation principles

Like in Section 4.3, we provide a kind of large deviation principle for both
$\mathbf{E}\upsilon_{k}(D_{n,d})$ and $\mathbf{E}\upsilon_{k}(C_{n,d})$ as
$n$, $k$ and $d$ all tend to infinity in a linearly coordinated way. A similar
theorem is stated for the expected quermassintegrals
$\mathbf{E}U_{d-k}(C_{n,d})$.

######  Theorem 5.9.

Consider the Donoho-Tanner random cone $D_{n,d}$. Suppose that $n=n(d)$ and
$k=k(d)$ are such that

$\displaystyle{k\over d}\to\varrho\quad\text{and}\quad{d\over
n}\to\delta,\qquad\text{as }d\to\infty,$ (5.7)

for parameters $\varrho,\delta\in(0,1)$. Then, it holds that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}v_{k}(D_{n,d})=-{1\over\delta}\log(2(1-\delta\varrho))-\varrho\log\varrho+\varrho\log\Big{(}{1\over\delta}-\varrho\Big{)}.$

###### Proof.

Since $\varrho<1$ we can assume that $k\neq d$. Then, Lemma 5.1 yields that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}v_{k}(D_{n,d})=-\lim_{d\to\infty}{n\over d}\log
2+\lim_{d\to\infty}{1\over d}\log{n\choose k}.$

Since $n/d\to{1\over\delta}$, relation (4.13) shows that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}v_{k}(D_{n,d})=-{1\over\delta}\log
2+\mathcal{J}(\delta,\varrho).$

This yields the result. ∎

We turn now to a corresponding result for the Cover-Efron random cones.

######  Theorem 5.10.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $k=k(d)$ and $n=n(d)$
are such that

$\displaystyle{k\over d}\to\varrho\quad\text{and}\quad{d\over
n}\to\delta,\qquad\text{as }d\to\infty,$

for parameters $\varrho,\delta\in(0,1)$. Then, it holds that

$\lim_{d\to\infty}{1\over
d}\log\mathbf{E}v_{k}(C_{n,d})=\begin{cases}{1\over\delta}\log{1\over\delta}-\varrho\log\varrho-\big{(}{1\over\delta}-\varrho\big{)}\log\big{(}{1\over\delta}-\varrho\big{)}&:\delta>1/2,\\\
\log\delta-\log(1-\delta)-\varrho\log\varrho+\varrho\log\big{(}{1\over\delta}-\varrho\big{)}+{1\over\delta}\log\big{(}{1-\delta\over
1-\delta\varrho}\big{)}&:\delta<1/2.\end{cases}$

###### Proof.

Since $\delta<1$ by assumption it is sufficient to consider the case $k\neq
d$. Using the explicit formula for $\mathbf{E}v_{k}(C_{n,d})$ from (3.5) we
can write

$\displaystyle\mathbf{E}v_{k}(C_{n,d})={{n\choose k}\over
2^{n}\,\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]}$

and hence

$\displaystyle\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}v_{k}(C_{n,d})\over{n\choose k}}=-\log
2\lim_{d\to\infty}{n\over d}-\lim_{d\to\infty}{1\over
d}\log\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1].$

Since $d/n\to\delta$, as $d\to\infty$, the first term is equal to
$-{1\over\delta}\log 2$, while for the second term we have that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]=\lim_{d\to\infty}{n-1\over
d}{1\over n-1}\log\mathbf{P}[\textup{Bin}(n-1,1/2)\leq n(\delta+o(1))].$

If $\delta<1/2$ we conclude from Cramer’s theorem (2.5) that

$\lim_{d\to\infty}{1\over d}\log\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]=-{1\over\delta}\mathcal{I}(\delta),$

while for $\delta>1/2$ the limit is zero. Combined with (4.13) this yields
that

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}v_{k}(C_{n,d})=\lim_{d\to\infty}{1\over
d}\log{\mathbf{E}v_{k}(C_{n,d})\over{n\choose k}}+\lim_{d\to\infty}{1\over
d}\log{n\choose k}={1\over\delta}(\mathcal{I}(\delta)-\log
2)+\mathcal{J}(\delta,\varrho)$

if $\delta<1/2$ and

$\displaystyle\lim_{d\to\infty}{1\over
d}\log\mathbf{E}v_{k}(C_{n,d})=\mathcal{J}(\delta,\varrho)$

for $\delta>1/2$. This completes the proof. ∎

In Theorem 3 of [25] Hug and Schneider proved that

$\displaystyle\lim_{d\to\infty}\mathbf{E}U_{d-k}(C_{n,d})=0$

if $d/n\to\delta$ as $d\to\infty$ and a parameter $\delta\in(1/2,1)$. The next
theorem gives the rate with which $\mathbf{E}U_{d-k}(C_{n,d})$ converges to
$0$.

######  Theorem 5.11.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $n=n(d)$ is such that

$\frac{d}{n}\longrightarrow\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(1/2,1)$. Then, for all fixed $k\in\mathbb{N}$, it
holds that

$\displaystyle\lim_{d\to\infty}\frac{1}{d}\log\mathbf{E}U_{d-k}(C_{n,d})=-\frac{1}{\delta}(\log
2+\delta\log\delta+(1-\delta)\log(1-\delta))<0.$

###### Proof.

Recall the representation

$\displaystyle\mathbf{E}2U_{d-k}(C_{n,d})=\frac{\sum_{l=1}^{k}\mathbf{P}[\textup{Bin}(n-1,1/2)=d-l]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]},$

of $\mathbf{E}2U_{d-k}(C_{n,d})$ in terms of binomial probabilities; see
(5.6). The law of large numbers yields that

$\displaystyle\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]=1.$

Using the asymptotic equivalence (2.7), we obtain that

$\displaystyle\sum_{l=1}^{k}\mathbf{P}[\textup{Bin}(n-1,1/2)=d-l]$
$\displaystyle=\sum_{l=1}^{k}\mathbf{P}\Big{[}\textup{Bin}(n-1,1/2)=\Big{(}\frac{d-l}{n-1}\Big{)}(n-1)\Big{]}$
$\displaystyle\underset{d\to\infty}{\sim}\sum_{l=1}^{k}\frac{1}{\sqrt{2\pi(n-1)\delta(1-\delta)}}\exp\left\\{-(n-1)\mathcal{I}\Big{(}\frac{d-l}{n-1}\Big{)}\right\\}$
$\displaystyle\underset{d\to\infty}{\sim}\frac{k}{\sqrt{2\pi
n\delta(1-\delta)}}\exp\left\\{-(n-1)\mathcal{I}(\delta+o(1))\right\\}.$

Thus, we arrive at

$\displaystyle\lim_{d\to\infty}\frac{1}{d}\log\mathbf{E}U_{d-k}(C_{n,d})$
$\displaystyle=-\lim_{d\to\infty}\frac{n}{d}\mathcal{I}(\delta)=-\frac{1}{\delta}(\log
2+\delta\log\delta+(1-\delta)\log(1-\delta)),$

which completes the proof. ∎

##  6\. Limit theorems for the expected statistical dimension

The statistical dimension $\Delta(C)$ of a cone $C\subset\mathbb{R}^{d}$
measures its ‘true’ or ‘intrinsic’ size or complexity and is defined as

$\displaystyle\Delta(C):=\sum_{j=0}^{d}j\upsilon_{j}(C).$

Note that if $L\subset\mathbb{R}^{d}$ is an $\ell$-dimensional linear subspace
for some $\ell\in\\{0,1,\ldots,d\\}$ then $\upsilon_{k}(L)=1$ of $k=\ell$ and
$0$ otherwise, which yields $\Delta(L)=\ell\cdot\upsilon_{\ell}(L)=\ell$. The
statistical dimension is in fact the canonical extension of the dimension of a
subspace as it has been argued in Section 5.3 of [2] that the statistical
dimension is the only continuous, rotation-invariant and localizable valuation
$\Delta(\,\cdot\,)$ on the space of cones in $\mathbb{R}^{d}$ satisfying
$\Delta(L)=\ell$ for $\ell$-dimensional subspaces. For more properties of the
statistical dimension, we refer to [2].

In this section, our goal is to understand the asymptotic behaviour of the
expected statistical dimension of the random cones introduced in Section 3, as
$d$ and $n$ tend to infinity in a coordinated way.

###  6.1. The Donoho-Tanner random cones

We start by considering the dual Donoho-Tanner random cone $D_{n,d}^{\circ}$.
Using the well-known duality relation
$\upsilon_{k}(C)=\upsilon_{d-k}(C^{\circ})$ for a cone
$C\subset\mathbb{R}^{d}$, we can deduce the expected conic intrinsic volumes
of $D_{n,d}^{\circ}$ from Lemma 5.1:

$\displaystyle\mathbf{E}\upsilon_{k}(D_{n,d}^{\circ})=\begin{cases}\frac{1}{2^{n}}\binom{n}{d-k}&:k\in\\{1,\dots,d\\},\\\
1-\sum_{j=1}^{d}\frac{1}{2^{n}}\binom{n}{d-j}&:k=0.\end{cases}$

Thus, the expected statistical dimension is given by

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})=\sum_{j=0}^{d}j\cdot\mathbf{E}\upsilon_{j}(D_{n,d}^{\circ})=\sum_{j=0}^{d}\frac{j}{2^{n}}\binom{n}{d-j}={1\over
2^{n}}\sum_{l=0}^{d}(d-l)\binom{n}{l}.$ (6.1)

The next theorem describes the asymptotic behaviour of
$\mathbf{E}\Delta(D_{n,d}^{\circ})$ as $d$ and $n=n(d)$ tend to infinity
simultaneously.

######  Theorem 6.1.

Let $D_{n,d}^{\circ}$ be a dual Donoho-Tanner random cone. Suppose that
$n=n(d)$ is such that

$\frac{d}{n}\to\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(0,1]$. Then, it holds that

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})\underset{d\to\infty}{\sim}d\Big{(}1-\frac{1}{2\delta}\Big{)},\quad\text{for
}\delta\in(1/2,1],$

and

$\displaystyle\lim_{d\to\infty}\mathbf{E}\Delta(D_{n,d}^{\circ})=0,\quad\text{for
}\delta\in(0,1/2).$

In the case where $\delta=1/2$, we have that

$\mathbf{E}\Delta(D_{n,d}^{\circ})=o(d),\qquad\text{as }d\to\infty.$

More precisely, if

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for a parameter $c\in\mathbb{R}$, then it holds that

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})\underset{d\to\infty}{\sim}\sqrt{d}\left(\frac{e^{-c^{2}/4}}{2\sqrt{\pi}}-\frac{c}{2}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}\right).$

###### Proof.

Suppose that $d/n\to\delta$ as $d\to\infty$. We start with the case
$\delta\in(1/2,1]$. Following (6.1), we can rewrite the expected statistical
dimension of $D_{n,d}^{\circ}$ in terms of binomial random variables:

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})$
$\displaystyle=\mathbf{E}\big{[}(d-\textup{Bin}(n,1/2))\mathbbm{1}_{\\{\textup{Bin}(n,1/2)\leq
d\\}}\big{]}$
$\displaystyle=\mathbf{E}\big{[}d-\textup{Bin}(n,1/2)]-\mathbf{E}\big{[}(d-\textup{Bin}(n,1/2))\mathbbm{1}_{\\{\textup{Bin}(n,1/2)>d\\}}\big{]}.$

We have $d-n\leq d-\textup{Bin}(n,1/2)\leq d$ and it follows that
$d-\textup{Bin}(n,1/2)\in[-Cd,Cd]$ for all $d\in\mathbb{N}$ and a constant
$C>0$. Thus, we have

$\displaystyle\big{|}\mathbf{E}\big{[}(d-\textup{Bin}(n,1/2))\mathbbm{1}_{\\{\textup{Bin}(n,1/2)>d\\}}\big{]}\big{|}$
$\displaystyle\leq\mathbf{E}\big{[}|d-\textup{Bin}(n,1/2)|\mathbbm{1}_{\\{\textup{Bin}(n,1/2)>d\\}}\big{]}$
$\displaystyle\leq Cd\cdot\mathbf{P}[\textup{Bin}(n,1/2)>d]$
$\displaystyle\leq
Cd\cdot\mathbf{P}\left[\textup{Bin}(n,1/2)>n(\delta+o(1))\right],$

which converges to $0$ as $d\to\infty$ due to Cramer’s theorem (2.4) and the
assumption $\delta>1/2$. This yields

$\displaystyle\lim_{d\to\infty}\frac{\mathbf{E}\Delta(D_{n,d}^{\circ})}{d}=\lim_{d\to\infty}\frac{\mathbf{E}\big{[}d-\textup{Bin}(n,1/2)]}{d}=\lim_{d\to\infty}\Big{(}1-\frac{n}{2d}\Big{)}=1-\frac{1}{2\delta},$

which completes the proof of the case $\delta\in(1/2,1]$.

Now, we turn to the case $\delta\in(0,1/2)$. Consider the term

$\displaystyle\sum_{l=0}^{d}(d-l)\binom{n}{l}=\binom{n}{d}\sum_{k=0}^{d}k\frac{\binom{n}{d-k}}{\binom{n}{d}}$

and note that for every fixed $k\in\mathbb{N}_{0}$,

$\displaystyle\frac{\binom{n}{d-k}}{\binom{n}{d}}=\frac{d(d-1)\cdot\ldots\cdot(d-k+1)}{(n-d+k)\cdot\ldots\cdot(n-d+1)}\underset{d\to\infty}{\sim}\frac{d^{k}}{(n-d)^{k}}\overset{}{\underset{d\to\infty}{\longrightarrow}}\Big{(}\frac{\delta}{1-\delta}\Big{)}^{k}.$

Now, we can apply the dominated convergence theorem, since there is an
$\varepsilon\in(0,1)$ such that for sufficiently large $d$, we have

$\displaystyle k\frac{\binom{n}{d-k}}{\binom{n}{d}}\leq
k\Big{(}\frac{d}{n-d}\Big{)}^{k}\leq k(1-\varepsilon)^{k},$

which is summable over $k$. This yields

$\displaystyle\sum_{l=0}^{d}(d-l)\binom{n}{l}\underset{d\to\infty}{\sim}\binom{n}{d}\sum_{k=0}^{\infty}k\Big{(}\frac{\delta}{1-\delta}\Big{)}^{k}=\binom{n}{d}\frac{\delta(1-\delta)}{(1-2\delta)^{2}}$
(6.2)

and together with (6.1), we arrive at

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})\underset{d\to\infty}{\sim}\frac{\delta(1-\delta)}{(1-2\delta)^{2}}\frac{\binom{n}{d}}{2^{n}}=\frac{\delta(1-\delta)}{(1-2\delta)^{2}}\mathbf{P}[\textup{Bin}(n,1/2)=d]\overset{}{\underset{d\to\infty}{\longrightarrow}}0,$

which completes the proof of the case $\delta\in(0,1/2)$.

Now, let us turn to the case $\delta=1/2$, that is, $d/n(d)\to 1/2$, as
$d\to\infty$. Our goal is to show that $\mathbf{E}\Delta(D_{n,d}^{\circ})/d\to
0$. To this end, fix some $\varepsilon\in(0,1)$. For
$n^{\prime}(d):=[n(d)(1-\varepsilon)]$, we have

$\displaystyle\frac{d}{n^{\prime}(d)}\overset{}{\underset{d\to\infty}{\longrightarrow}}\frac{1}{2(1-\varepsilon)}>\frac{1}{2}.$

Thus, the first case of the theorem implies that
$\mathbf{E}\Delta(D_{n^{\prime}(d),d}^{\circ})\sim d\cdot\varepsilon$, as
$d\to\infty$. For each sufficiently large $d\in\mathbb{N}$, there is a natural
coupling of $D_{n(d),d}^{\circ}$ and $D_{n^{\prime}(d),d}^{\circ}$ such that
$D_{n(d),d}^{\circ}\subset D_{n^{\prime}(d),d}^{\circ}$ since
$n^{\prime}(d)<n(d)$. Using the monotonicity of the statistical dimension, see
[2, Proposition 3.1], yields

$\displaystyle\limsup_{d\to\infty}\frac{\mathbf{E}\Delta(D_{n(d),d}^{\circ})}{d}\leq\limsup_{d\to\infty}\frac{\mathbf{E}\Delta(D_{n^{\prime}(d),d}^{\circ})}{d}=\varepsilon.$

Letting $\varepsilon$ approach zero from above yields the claim.

Now, let $n=2d+c\sqrt{d}+o(\sqrt{d})$ for some $c\in\mathbb{R}$. By defining
$Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$, we can write

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})$
$\displaystyle=\mathbf{E}\big{[}(d-\textup{Bin}(n,1/2))\mathbbm{1}_{\\{\textup{Bin}(n,1/2)\leq
d\\}}\big{]}$
$\displaystyle=\mathbf{E}\bigg{[}\Big{(}d-\sqrt{\frac{n}{4}}Z_{n}-\frac{n}{2}\Big{)}\mathbbm{1}_{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\big{\\}}}\bigg{]}$
$\displaystyle=\Big{(}d-\frac{n}{2}\Big{)}\mathbf{P}\bigg{[}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\bigg{]}-\sqrt{\frac{n}{4}}\mathbf{E}\Big{[}Z_{n}\mathbbm{1}_{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\big{\\}}}\Big{]}.$
(6.3)

Following the central limit theorem for binomial random variables, we know
that

$\displaystyle\mathbf{P}\bigg{[}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\bigg{]}=\mathbf{P}\bigg{[}Z_{n}\leq-\frac{c}{\sqrt{2}}+o(1)\bigg{]}\overset{}{\underset{d\to\infty}{\longrightarrow}}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

Hence, it is left to determine the asymptotics of the term
$\mathbf{E}[Z_{n}\mathbbm{1}{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\big{\\}}}]$.
The central limit theorem for the binomial distribution yields the weak
convergence of $Z_{n}$ to $N(0,1)$. Using Skorokhod’s representation theorem
we can assume, after passing to a different probability space, that $Z_{n}$
almost surely converges to a random variable $N(0,1)$, as $d\to\infty$. Thus,
we also obtain

$\displaystyle
Z_{n}\mathbbm{1}_{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\big{\\}}}\overset{a.s.}{\underset{d\to\infty}{\longrightarrow}}N(0,1)\mathbbm{1}_{\big{\\{}N(0,1)\leq-\frac{c}{\sqrt{2}}\big{\\}}}.$

Since

$\displaystyle\mathbf{E}\bigg{[}\Big{(}Z_{n}\mathbbm{1}_{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\big{\\}}}\Big{)}^{2}\bigg{]}\leq\mathbf{E}\big{[}Z_{n}^{2}\big{]}=1,$

the sequence
$(Z_{n}\mathbbm{1}{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\\}})_{d\geq 0}$ is
uniformly integrable and we obtain the convergence of expectations

$\displaystyle\mathbf{E}\Big{[}Z_{n}\mathbbm{1}_{\big{\\{}Z_{n}\leq\frac{2d-n}{\sqrt{n}}\big{\\}}}\Big{]}\overset{}{\underset{d\to\infty}{\longrightarrow}}\mathbf{E}\Big{[}N(0,1)\mathbbm{1}_{\big{\\{}N(0,1)\leq-\frac{c}{\sqrt{2}}\big{\\}}}\Big{]}.$

The latter expectation can be further simplified as follows:

$\displaystyle\mathbf{E}\Big{[}N(0,1)\mathbbm{1}_{\big{\\{}N(0,1)\leq-\frac{c}{\sqrt{2}}\big{\\}}}\Big{]}=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{-\frac{c}{\sqrt{2}}}xe^{-\frac{x^{2}}{2}}\textup{d}x=-\frac{1}{\sqrt{2\pi}}e^{-\frac{c^{2}}{4}}.$

Together with (6.1), we finally arrive at

$\displaystyle\mathbf{E}\Delta(D_{n,d}^{\circ})$
$\displaystyle\underset{d\to\infty}{\sim}\Big{(}d-\frac{n}{2}\Big{)}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}+\sqrt{\frac{n}{4}}\cdot\frac{1}{\sqrt{2\pi}}e^{-\frac{c^{2}}{4}}\underset{d\to\infty}{\sim}\sqrt{d}\left(\frac{e^{-c^{2}/4}}{2\sqrt{\pi}}-\frac{c}{2}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}\right).$

where we used $n=2d+c\sqrt{d}+o(\sqrt{d})$ in the last step. This completes
the proof. ∎

By duality, the previous result implies asymptotic results for the expected
statistical dimension of the Donoho-Tanner random cone.

######  Corollary 6.2.

Let $D_{n,d}$ be a Donoho-Tanner random cone. Suppose that $n=n(d)$ is such
that

$\frac{d}{n}\to\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(0,1]$. Then, it holds that

$\displaystyle\mathbf{E}\Delta(D_{n,d})\underset{d\to\infty}{\sim}\begin{cases}\frac{d}{2\delta}&:\delta\in(1/2,1],\\\
d&:\delta\in(0,1/2].\\\ \end{cases}$

###### Proof.

This follows directly from Theorem 6.1 using the duality relation [2, Eq.
(3.7)]

$\displaystyle\Delta(C)+\Delta(C^{\circ})=d,$

for each $d$-dimensional cone $C\subset\mathbb{R}^{d}$. ∎

###  6.2. The Schläfli and Cover-Efron random cones

Let $S_{n,d}$ be a Schläfli random cone. By (3.3) the expected statistical
dimension of $S_{n,d}$ is given by

$\displaystyle\mathbf{E}\Delta(S_{n,d})=\sum_{j=0}^{d}j\mathbf{E}\upsilon_{j}(S_{n,d})=\sum_{j=0}^{d}j\frac{\binom{n}{d-j}}{C(n,d)}=\frac{\sum_{l=0}^{d}(d-l)\binom{n}{l}}{C(n,d)}.$
(6.4)

The following theorem provides asymptotic results for
$\mathbf{E}\delta(C_{n,d})$ as $d$ and $n$ tend to infinity simultaneously.
This should be compared to Theorem 6.1.

######  Theorem 6.3.

Let $S_{n,d}$ be a Schläfli random cone. Suppose that $n=n(d)$ is such that

$\frac{d}{n}\to\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(0,1]$. Then, it holds that

$\displaystyle\mathbf{E}\Delta(S_{n,d})\underset{d\to\infty}{\sim}\begin{cases}d(1-\frac{1}{2\delta})&:\delta\in(1/2,1],\\\
\frac{1}{2(1-2\delta)}&:\delta\in(0,1/2).\end{cases}$

In the case where $\delta=1/2$, we have that

$\mathbf{E}\Delta(S_{n,d})=o(d),\qquad\text{as }d\to\infty.$

More precisely, if

$n=2d+c\sqrt{d}+o(\sqrt{d}),\qquad\text{as }d\to\infty,$

for a parameter $c\in\mathbb{R}$, then it holds that

$\displaystyle\mathbf{E}\Delta(S_{n,d})\underset{d\to\infty}{\sim}\sqrt{d}\left(\frac{e^{-c^{2}/4}}{2\sqrt{\pi}\Phi(-c/\sqrt{2})}-\frac{c}{2}\right).$

###### Proof.

Following (6.1) and (6.4), we observe that

$\displaystyle\mathbf{E}\Delta(S_{n,d})=\mathbf{E}\Delta(D_{n,d}^{\circ})\cdot\frac{2^{n}}{C(n,d)}.$
(6.5)

Consequently, some results for the expected statistical dimension of the
Schläfli random cone follow from the corresponding results in Theorem 6.1.

Now, let $d/n\to\delta$ for some $\delta\in(1/2,1]$. Then, the law of large
numbers implies that

$\displaystyle\lim_{d\to\infty}\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]=1,$

Thus, we obtain

$\displaystyle\frac{2^{n}}{C(n,d)}=\frac{1}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}\overset{}{\underset{d\to\infty}{\longrightarrow}}1.$

Together with Theorem 6.1 this proves the case $\delta\in(1/2,1]$.

Now, suppose that $\delta\in(0,1/2)$. At first, we want to determine the
asymptotic behaviour of the term $C(n,d)$. In the same way as in the proof of
Theorem 6.1, we obtain that

$\displaystyle
C(n+1,d+1)=2\sum_{l=0}^{d}\binom{n}{l}=2\binom{n}{d}\sum_{k=0}^{d}\frac{\binom{n}{d-k}}{\binom{n}{d}}\underset{d\to\infty}{\sim}2\binom{n}{d}\sum_{k=0}^{\infty}\Big{(}\frac{\delta}{1-\delta}\Big{)}^{k}=2\binom{n}{d}\frac{1-\delta}{1-2\delta}.$

Together with (6.4) and (6.2), we arrive at

$\displaystyle\mathbf{E}\Delta(S_{n,d})=\frac{\sum_{l=0}^{d}{(d-l)\binom{n}{l}}}{2\sum_{l=0}^{d-1}\binom{n-1}{l}}\underset{d\to\infty}{\sim}\frac{\binom{n}{d}}{\binom{n-1}{d-1}}\cdot\frac{\delta}{2(1-2\delta)}=\frac{n}{d}\cdot\frac{\delta}{2(1-2\delta)}\underset{d\to\infty}{\sim}\frac{1}{2(1-2\delta)},$

which completes the proof of the case $\delta\in(0,1/2)$.

Now, we turn to the case $\delta=1/2$. Unfortunately, a monotonicity argument
like the one used in a similar situation in the proof of Theorem 6.1 fails for
Schläfli cones. To work around this difficulty, fix an $\varepsilon\in(0,1)$.
We can split the sum on the right-hand side of (6.4) to obtain

$\displaystyle\frac{\mathbf{E}\Delta(S_{n,d})}{d}=\frac{1}{d\cdot
C(n,d)}\left(\sum_{l\in((1-\varepsilon)d,d]}(d-l)\binom{n}{l}+\sum_{l\in[0,(1-\varepsilon)d]}(d-l)\binom{n}{l}\right).$

For the first sum, we can use that $d-l\leq\varepsilon d$ and obtain

$\displaystyle\limsup_{d\to\infty}\frac{1}{d\cdot
C(n,d)}\sum_{l\in((1-\varepsilon)d,d]}(d-l)\binom{n}{l}$
$\displaystyle\leq\varepsilon\cdot\limsup_{d\to\infty}\frac{\sum_{l=0}^{d}\binom{n}{l}}{C(n,d)}$
$\displaystyle\leq\varepsilon\cdot\limsup_{d\to\infty}\frac{\mathbf{P}[\textup{Bin}(n,1/2)\leq
d]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq d-1]}=\varepsilon,$

where in the last step we used (4.1) and Theorem 4.1. For the second sum, we
use that $d-l\leq d$ and obtain

$\displaystyle\frac{1}{d\cdot
C(n,d)}\sum_{l\in[0,(1-\varepsilon)d]}(d-l)\binom{n}{l}$
$\displaystyle\leq\frac{\sum_{l\in[0,(1-\varepsilon)d]}\binom{n}{l}}{C(n,d)}=\frac{\mathbf{P}[\textup{Bin}(n,1/2)\leq(1-\varepsilon)d]}{\mathbf{P}[\textup{Bin}(n-1,1/2)\leq
d-1]}\overset{}{\underset{d\to\infty}{\longrightarrow}}0.$

Note that we used the fact that the numerator converges to $0$ with an
exponential rate, whereas it is not clear whether the denominator converges at
all. This case was already treated in the proof of Theorem 4.4 (see the case
$\delta=1/2$) and can be proven in the same way here. Letting $\varepsilon$
approach zero from above yields that $\mathbf{E}\Delta(S_{n,d})/d$ converges
to $0$ as $d\to\infty$.

Now, we consider the critical case where $n=2d+c\sqrt{d}+o(\sqrt{d})$ as
$d\to\infty$ for some constant $c\in\mathbb{R}$. By defining
$Z_{n}:=(2\textup{Bin}(n,1/2)-n)/\sqrt{n}$, we can use the central limit
theorem for binomial random variables to obtain

$\displaystyle
C(n,d)=2^{n}\mathbf{P}\bigg{[}Z_{n-1}\leq\frac{2(d-1)-(n-1)}{\sqrt{n-1}}\bigg{]}=2^{n}\mathbf{P}\left[Z_{n-1}\leq-\frac{c}{\sqrt{2}}+o(1)\right]\underset{d\to\infty}{\sim}2^{n}\Phi\Big{(}-\frac{c}{\sqrt{2}}\Big{)}.$

Hence, we also have

$\displaystyle\frac{2^{n}}{C(n,d)}\overset{}{\underset{d\to\infty}{\longrightarrow}}\frac{1}{\Phi(-c/\sqrt{2})}.$

Combining this with (6.5) and Theorem 6.1 proves the claim. ∎

By the same duality argument as in the Donoho-Tanner case, Theorem 6.3 yields
the following corollary for the Cover-Efron random cone.

######  Corollary 6.4.

Let $C_{n,d}$ be a Cover-Efron random cone. Suppose that $n=n(d)$ is such that

$\frac{d}{n}\to\delta,\qquad\text{as }d\to\infty,$

for a parameter $\delta\in(0,1]$. Then, it holds that

$\displaystyle\mathbf{E}\Delta(C_{n,d})\underset{d\to\infty}{\sim}\begin{cases}\frac{d}{2\delta}&:\delta\in(1/2,1],\\\
d&:\delta\in(0,1/2].\\\ \end{cases}$

### Acknowledgement

The authors were supported by the DFG priority program SPP 2265 Random
Geometric Systems. TG and ZK also acknowledge support by the German Research
Foundation (DFG) under Germany’s Excellence Strategy EXC 2044 – 390685587,
Mathematics Münster: Dynamics – Geometry – Structure.

## References

  * [1] D. Amelunxen and M. Lotz.  Intrinsic volumes of polyhedral cones: A combinatorial perspective.  Discrete & Computational Geometry, 58(2):371–409, jul 2017.
  * [2] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp.  Living on the edge: phase transitions in convex programs with random data.  Inf. Inference, 3(3):224–294, 2014.
  * [3] G. Bonnet, G. Chasapis, J. Grote, D. Temesvari, and N. Turchi.  Threshold phenomena for high-dimensional random polytopes.  Commun. Contemp. Math., 21(5):1850038, 30, 2019.
  * [4] G. Bonnet, Z. Kabluchko, and N. Turchi.  Phase transition for the volume of high-dimensional random polytopes, 2019\.  Preprint at arXiv: 1911.12696.
  * [5] D. Chakraborti, T. Tkocz, and B.-H. Vritsiou.  A note on volume thresholds for random polytopes, 2020.  Preprint at arXiv: 2004.01119.
  * [6] T. M. Cover and B. Efron.  Geometrical probability and random points on a hypersphere.  Ann. Math. Statist., 38(1):213–220, 1967.
  * [7] H. Cramér, P. Lévy, and R. de Mises.  Les Sommes et les Fonctions de Variables Aléatoires. Paris: Hermann, 1938.
  * [8] F. den Hollander.  Large Deviations.  American Mathematical Society, Providence, RI, 2000.
  * [9] D. Donoho and J. Tanner.  Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing.  Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 367(1906):4273–4293, 2009.  With electronic supplementary materials available online.
  * [10] D. L. Donoho and J. Tanner.  Neighborliness of randomly projected simplices in high dimensions.  Proc. Natl. Acad. Sci. USA, 102(27):9452–9457, 2005.
  * [11] D. L. Donoho and J. Tanner.  Sparse nonnegative solution of underdetermined linear equations by linear programming.  Proc. Natl. Acad. Sci. USA, 102(27):9446–9451, 2005.
  * [12] D. L. Donoho and J. Tanner.  Counting the faces of randomly-projected hypercubes and orthants, with applications.  Discrete & Computational Geometry, 43(3):522–541, sep 2009.
  * [13] D. L. Donoho and J. Tanner.  Exponential bounds implying construction of compressed sensing matrices, error-correcting codes, and neighborly polytopes by random sampling.  IEEE Trans. Inform. Theory, 56(4):2002–2016, 2010.
  * [14] M. E. Dyer, Z. Füredi, and C. McDiarmid.  Random volumes in the $n$-cube.  In Polyhedral Combinatorics (Morristown, NJ, 1989), volume 1 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 33–38. Amer. Math. Soc., Providence, RI, 1990.
  * [15] M. E. Dyer, Z. Füredi, and C. McDiarmid.  Volumes spanned by random points in the hypercube.  Random Structures Algorithms, 3(1):91–106, 1992.
  * [16] C.-G. Esseen.  Fourier analysis of distribution functions. a mathematical study of the laplace-gaussian law.  Acta Math., 77:1–125, 1945.
  * [17] W. Feller.  Generalization of a probability limit theorem of Cramér.  Trans. Amer. Math. Soc., 54:361–372, 1943.
  * [18] V. Féray, P.-L. Méliot, and A. Nikeghbali.  Mod-$\upphi$ Convergence.  Springer International Publishing, 2016.
  * [19] D. Gale.  Neighboring vertices on a convex polyhedron.  In Linear Inequalities and Related System, Annals of Mathematics Studies, no. 38, pages 255–263. Princeton University Press, Princeton, N.J., 1956.
  * [20] L. Goldstein, I. Nourdin, and G. Peccati.  Gaussian phase transitions and conic intrinsic volumes: Steining the Steiner formula.  Ann. Appl. Probab., 27(1):1–47, 2017.
  * [21] B. Grünbaum.  Grassmann angles of convex polytopes.  Acta Math., 121:293–302, 1968.
  * [22] B. Grünbaum.  Convex Polytopes, volume 221 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 2003.  Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler.
  * [23] T. Höglund.  A unified formulation of the central limit theorem for small and large deviations from the mean.  Z. Wahrsch. Verw. Gebiete, 49(1):105–117, 1979.
  * [24] D. Hug and R. Schneider.  Random conical tessellations.  Discrete & Computational Geometry, 56(2):395–426, may 2016.
  * [25] D. Hug and R. Schneider.  Threshold phenomena for random cones.  arXiv preprint: 2004.11473, 2020.
  * [26] I. A. Ibragimov and Y. V. Linnik.  Independent and Stationary Sequences of Random Variables.  Wolters-Noordhoff Publishing, Groningen, 1971.
  * [27] M. B. McCoy and J. A. Tropp.  From Steiner formulas for cones to concentration of intrinsic volumes.  Discrete Comput. Geom., 51(4):926–963, 2014.
  * [28] P. McMullen and G. C. Shephard.  Convex Polytopes and the Upper Bound Conjecture.  Cambridge University Press, London-New York, 1971.  Prepared in collaboration with J. E. Reeve and A. A. Ball, London Mathematical Society Lecture Note Series, 3.
  * [29] J. Mycielski.  On random convex hulls.  Colloq. Math., 51:263–265, 1987.
  * [30] V. V. Petrov.  Generalization of Cramér’s limit theorem.  Uspehi Matem. Nauk (N.S.), 9(4(62)):195–202, 1954.
  * [31] V. V. Petrov.  On the probabilities of large deviations for sums of independent random variables.  Theory Probab. Appl., 10:287–298, 1965.
  * [32] V. V. Petrov.  Sums of Independent Random Variables.  Springer Berlin Heidelberg, 1975.
  * [33] P. Pivovarov.  Volume thresholds for Gaussian and spherical random polytopes and their duals.  Studia Math., 183(1):15–34, 2007.
  * [34] R. Schneider.  Random Gale diagrams and neighbourly polytopes in high dimensions.  To appear in Beitr. Algebra Geom., 2020+.
  * [35] R. Schneider and W. Weil.  Stochastic and Integral Geometry.  Probability and its Applications (New York). Springer-Verlag, Berlin, 2008\.
  * [36] A. M. Vershik and P. V. Sporyshev.  Estimation of the mean number of steps in the simplex method, and problems of asymptotic integral geometry.  Dokl. Akad. Nauk SSSR, 271(5):1044–1048, 1983.
  * [37] A. M. Vershik and P. V. Sporyshev.  An asymptotic estimate for the average number of steps in the parametric simplex method.  Zh. Vychisl. Mat. i Mat. Fiz., 26(6):813–826, 958, 1986.
  * [38] A. M. Vershik and P. V. Sporyshev.  Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem.  volume 11, pages 181–201. 1992.  Selected translations.
  * [39] J. G. Wendel.  A problem in geometric probability.  Math. Scand., 11:109–111, 1962.