# General stochastic separation theorems with optimal bounds

Bogdan Grechuk<EMAIL_ADDRESS>https://orcid.org/0000-0002-2624-5765 Alexander
N. Gorban<EMAIL_ADDRESS>https://orcid.org/0000-0001-6224-1430 Ivan Y. Tyukin
<EMAIL_ADDRESS>https://orcid.org/0000-0002-7359-7966 Department of Mathematics,
University of Leicester, Leicester, LE1 7RH, UK  Lobachevsky University,
Nizhni Novgorod, Russia

###### Abstract

Phenomenon of stochastic separability was revealed and used in machine
learning to correct errors of Artificial Intelligence (AI) systems and analyze
AI instabilities. In high-dimensional datasets under broad assumptions each
point can be separated from the rest of the set by simple and robust Fisher’s
discriminant (is Fisher separable). Errors or clusters of errors can be
separated from the rest of the data. The ability to correct an AI system also
opens up the possibility of an attack on it, and the high dimensionality
induces vulnerabilities caused by the same stochastic separability that holds
the keys to understanding the fundamentals of robustness and adaptivity in
high-dimensional data-driven AI. To manage errors and analyze vulnerabilities,
the stochastic separation theorems should evaluate the probability that the
dataset will be Fisher separable in given dimensionality and for a given class
of distributions. Explicit and optimal estimates of these separation
probabilities are required, and this problem is solved in present work. The
general stochastic separation theorems with optimal probability estimates are
obtained for important classes of distributions: log-concave distribution,
their convex combinations and product distributions. The standard i.i.d.
assumption was significantly relaxed. These theorems and estimates can be used
both for correction of high-dimensional data driven AI systems and for
analysis of their vulnerabilities. The third area of application is the
emergence of memories in ensembles of neurons, the phenomena of grandmother’s
cells and sparse coding in the brain, and explanation of unexpected
effectiveness of small neural ensembles in high-dimensional brain.

###### keywords:

AI, blessing of dimensionality, curse of dimensionality, concentration of
measure, AI errors, discriminant

##  1 Introduction: Data mining in post-classical world

Big data ‘revolution’ and the growth of the data dimension are commonplace.
However, some implications of this growth are not so well known. In his
‘millennium lecture’, Donoho [2000] sought to present major 21st century
challenges for data analysis. He described the multidimensional post-classical
world where the number of attributes $d$ (dimensionality of the dataspace)
exceeds the sample size $N$:

$d\gg N.$ (1)

Of course, there are many practical tricks for handling data when the
condition (1) holds. In such a situation, tools of the first choice are
Principal Component Analysis with retaining of major components, the
correlation transformation, that transforms the data set into its Gram matrix
(the matrix of inner products or correlation coefficients between the data
vectors), or their combination (for a case study see [Moczko et al., 2016]).
These methods return the situation from (1) to $d\leq N$ but this is not the
end of the story. For the non-classical effects, the inequality (1) is not
necessary. Many such effects arise when

$d\gg\log N.$ (2)

Various examples of these effects are presented by Kainen & Kůrková [1993],
Kainen [1997], Donoho & Tanner [2009], Gorban et al. [2016a]. High-dimensional
data are very rarefied and have large data-free holes, even if the data sets
are exponentially large [Kainen, 1997]. Two effects are especially important:

  * 1.

Random vectors are quasiorthogonal: $N$ random vectors $\boldsymbol{x}_{i}$
$(i=1,\ldots,N)$ on a unit $d$-dimensional sphere are almost orthogonal: for a
given $\varepsilon>0$ and sufficiently large $d$ ($d\gg 1/\varepsilon$), we
can expect with high probability that
$|(\boldsymbol{x}_{i},\boldsymbol{x}_{j})|<\varepsilon$ fo all $i\neq j$ when
$d>A\ln N$ and $A$ depends on $\varepsilon$ only. (For various versions of
exact formulations we refer to [Kainen & Kůrková, 1993, Gorban et al., 2016a].
Very recently, Kainen & Kůrková [2020] reviewed the concept of quasiorthogonal
dimension and related notions.)

  * 2.

Random points are extreme: for a given $\varepsilon>0$ with a probability
$p>1-\varepsilon$ all $N$ random points are vertices of their convex hull. It
is sufficient that $d>B\ln N$ for some $B$ that depends on $\varepsilon$ only
(for exact formulations we refer to [Donoho & Tanner, 2009, Bárány & Füredi,
1988]).

Of course, detailing these properties should include clarifying what ‘random’
means. A fairly regular distribution is usually assumed, while Donoho [2000]
claimed that such ‘blessing of dimensionality’ effects hold for an
unexpectedly wide class of distributions.

One more comment to (1), (2) is necessary: existence of many attributes does
not mean large dimensionality of data. The naïve definition that
dimensionality of data refers to how many attributes a dataset has leads to
some confusions. Indeed, in the simplest example, when data are distributed
along a straight line, data are one-dimensional despite large number of
attributes. To distinguish between the number of attributes and the
dimensionality of a dataset, the latter is often referred to as the “intrinsic
dimensionality” of the data. Not the number of attributes but the
dimensionality of data should be used in the definition of the post-classical
world:

$\dim(Dataset)\gg\log N.$ (3)

Evaluation of the (intrinsic) dimensionality of data is a non-trivial problem
discussed by many authors, and many approaches are used, ranged from classical
Principal Component Analysis (PCA) [Jolliffe, 1993] and their generalizations
[Gorban et al., 2008], to principal graphs and manifolds [Gorban & Zinovyev,
2010], and fractal dimension [Camastra, 2003]. In recent review by Bac &
Zinovyev [2020] the typology of these methods is proposed and a new family of
methods based on the data separability properties is presented.

In the post-classical world, classical machine learning theory does not make
much sense because it works near the limits of large $N$, when the law of
large numbers and the central limit theorem can be used. The unlimited
appetite of classical approaches for data is often considered as a ‘curse of
dimensionality’. But the properties (1), (2), or (3) themselves are neither a
curse, nor a blessing, and can be beneficial. The idea of a ‘blessing of
dimensionality’ was formulated by Kainen [1997], but some properties of the
situations with (1) were exploited much earlier. In general situation, if
$d\leq N-1$, then any subsample is linearly separable from the rest of data.
Therefore, Rosenblatt [1962, Theorem 1] used a non-linear extension of the set
of attributes ($A$-elements, Fig. 1) to prove the omnipotence of elementary
peceptrons in solving any classification problem (on a large training set, at
least).

Figure 1: Rosenblatt’s elementary perceptron [Rosenblatt, 1962]. $A$-and
$R$-element are the classical threshold neurons. $R$ element is trainable by
the Rosenblatt algorithm, while $A$-elements should represent a sufficient
collection of features.

Other examples of post-classical phenomena are exponentially large sets of
quasiorthogonal (almost orthogonal) random vectors we have already mentioned
and stochastic separation in exponentially large datasets: with high
probability, any sample point is linearly separable from other points and this
separation could be performed by the simple and explicit Fisher discriminant
[Gorban et al., 2018, Gorban and Tyukin, 2017, Gorban et al., 2016b]. This is
a strengthening of the statements [Bárány & Füredi, 1988, Donoho, 2000, Donoho
& Tanner, 2009]) that random points are extreme ones. These properties were
proven for sufficiently regular probability distribution or for products of
large number of low-dimensional distributions. For other examples we refer to
the book by Vershynin [2018].

The new characterization of post-classical data (3) captures one of the
qualitative characterization of the post-classical world. Fundamental open
questions, however, are:

  1. 1.

Are there quantitatively accurate estimates of the boundary between the
“classical” and the “post-classical” cases?

  2. 2.

How these boundaries depend on statistical properties of the data?

  3. 3.

If the “post-classical” limit always obeys $\log(N)\ll\dim(Dataset)$ or could
have different forms such as $\log(N)\ll\dim(Dataset)^{p}$?

Answering these would allow us to determine applicability bounds for a host of
relevant measure concentration-based algorithms in machine learning, including
one-shot error correction and learning, randomized approximation, and
prevention of vulnerabilities to attacks.

The present work aims to answer these questions. In Sec. 2 we introduce the
stochastic separation phenomenon in detail and prove Theorem 1 that is a
prototype of most stochastic separation theorems. Estimates given in this
theorem can be improved for specific classes of distributions but it does not
use the i.i.d. assumption at al. This major departure from the classical
i.i.d. assumption in machine learning enables and justifies one-shot learning
and AI correction algorithms in presence of concept drifts, sample
dependencies, and non-stationarity.

Further in this work, we present such estimates for many practically important
classes of probability distributions, in particular, for log-concave
distributions and their convex combinations. In contrast to Theorem 1 and
Corollary 1 of Sec. 2, these estimates are in many cases asymptotically sharp.

In Sec. 3 the previously known results are analyzed, including estimations for
uniform distributions in a ball and a cube. In Sec. 4 we prove the stochastic
separation theorems with estimates of separation probability and sample sizes
for strongly log-concave distributions using the logarithmic Sobolev
inequality and Poincare inequality. For special classes of distributions
stronger results are obtained, for example, for spherically invariant log-
concave distributions including multivariate exponential distribution (Sec.
5). The known estimates for some distributions like uniform distribution in a
ball and the standard normal distribution are significantly improved and
optimal separation theorem for explicitly given distributions are found. Sec.
6 derives separation theorems for independent data from product distributions,
while Sec. 7 generalizes some of these theorems to the case of dependent data
relaxing the i.i.d. assumption. Sec. 8 briefly summarized the results, and in
Sec. 9 we discuss what these estimates are for and present the main areas of
applications.

##  2 Stochastic separation phenomenon

The ‘post-classical’ phenomenon of separability of random points from random
sets in high dimensionality opens up the possibility for fast and non-
iterative correction of errors of data-driven Artificial Intelligence (AI).
Each situation of AI functioning is represented by a vector that combines
inputs, internal signals and outputs of the AI system. If a situation with
error can be separated by an explicit and simple functional (Fisher’s
discriminant, for example) from the known situations with correct functioning
then this error can be corrected forever without destroying the existing
skills [Gorban et al., 2016b, Gorban and Tyukin, 2018]. The corrector is a
combination of the two-class classifier of situations (‘AI error’ versus
‘correct functioning’) with a modified decision rule for the ‘error’ class.

Below in this section, a prototype of most stochastic separation theorems is
introduces.

Recall that the classical Fisher discriminant between two classes with means
$\boldsymbol{\mu}_{1}$ and $\boldsymbol{\mu}_{2}$ is separation of the classes
by a hyperplane orthogonal to $\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}$ in
the inner product

$\langle\boldsymbol{x},\boldsymbol{y}\rangle=(\boldsymbol{x},\boldsymbol{S}^{-1}\boldsymbol{y}),$

where $(\cdot,\cdot)$ is the standard inner product and $\boldsymbol{S}$ is
the average (or the weighted average) of the sample covariance matrix of these
two classes. The classification rule is: if
$\langle\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2},\boldsymbol{x}\rangle\geq\vartheta$
then $\boldsymbol{x}$ belongs to the first class, otherwise it belongs to the
second class. The threshold $\vartheta$ should be chosen in such a way as to
maximize the quality of classification evaluated by a preselected criterion.

Applications of stochastic separation theory consider separating a single
point (error) or a small cluster of such points from a relatively large data
set. Thus, $\boldsymbol{S}$ is by default the empiric covariance matrix of a
large data set. Further on, assume that the dataset is preprocessed, this
includes centralization (zero mean) and whitening. Whitening uses PCA to
remove minor components and transform coordinates, making the empirical
covariance matrix the identity matrix. After whitening, we get out of the
situation described by the condition (1) but the conditions (2) or (3) can
persist.

It is necessary to stress that the precise whitening in applications to high-
dimensional datasets could be unavailable, and $\boldsymbol{S}$ may differ
from $\boldsymbol{1}$. If $\boldsymbol{S}$ remains a well-conditioned matrix
then this difference does not change qualitatively the separability
properties. Analysis of the quantitative differences that may appear for non-
isotropic $\boldsymbol{S}$ for some classes of probability distributions is
presented in Sec. 4.2.

Presuming the described preprocessing with whitening, we take
$\boldsymbol{S}=\boldsymbol{1}$ and
$\langle\boldsymbol{x},\boldsymbol{y}\rangle=(\boldsymbol{x},\boldsymbol{y})$.

###### Definition 1

A point $\boldsymbol{x}$ is _Fisher separable_ from a set
$Y\subset{\mathbb{R}}^{n}$ with center $\boldsymbol{c}\in{\mathbb{R}}^{n}$ and
threshold $\alpha\in(0,1]$ if inequality

$\alpha(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{x}-\boldsymbol{c})>(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{y}-\boldsymbol{c}),$
(4)

holds for all $\boldsymbol{y}\in Y$. If (4) does not hold for some
$\boldsymbol{x}$ and $\boldsymbol{y}$, we say that $\boldsymbol{x}$ and
$\boldsymbol{y}$ forms an (ordered) $(\alpha,\boldsymbol{c})$-inseparable pair
(see Fig. 2).

Figure 2: Geometry of separation:
$\alpha(\boldsymbol{x},\boldsymbol{x})>(\boldsymbol{x},\boldsymbol{y})$ for
all $\boldsymbol{x}$ outside the outlined ball (‘excluded volume’) with
diameter $\|y\|/\alpha$. Here, $c$ is the origin (the data mean), $L_{x}$ is
the hyperplane orthogonal to $x$. If $\boldsymbol{x}$ belongs to the ball of
excluded volume then) $\boldsymbol{x}$ and $\boldsymbol{y}$ forms an ordered
$\alpha$-inseparable pair.

If $\boldsymbol{c}=\boldsymbol{0}$ is the origin, we will write
$(\alpha,\boldsymbol{0})$-inseparable pair as just “$\alpha$-inseparable
pair”, to simplify the notation. For a given $\boldsymbol{y}$, the set of such
$\boldsymbol{x}$ that $\boldsymbol{x},\boldsymbol{y}$ form an ordered
$\alpha$-inseparable pair is a ball given by inequality

$\left\\{\boldsymbol{z}\ \left|\
\left\|\boldsymbol{z}-\frac{\boldsymbol{y}}{2\alpha}\right\|<\frac{\|\boldsymbol{y}\|}{2\alpha}\right.\right\\}.$
(5)

This is the ball of excluded volume from Fig. 2.

Two heuristic condition for the probability distribution are used in the
stochastic separation theorems:

  * 1.

The probability distribution has no heavy tails;

  * 2.

The sets of small volume should not have large probability (what “small” and
“large” mean should be strictly defined for different contexts).

In the following Theorem 1 the absence of heavy tails is formalized as the
tail cut: the support of the distribution is the $n$-dimensional unit ball
$\mathbb{B}_{n}$.

The absence of the sets of small volume but large probability is formalized in
this theorem by the following inequality:

$\rho(\boldsymbol{x})<\frac{C}{r^{n}V_{n}(\mathbb{B}_{n})},$ (6)

where $\rho$ is the distribution density, $C>0$ is an arbitrary constant,
$V_{n}(\mathbb{B}_{n})$ is the volume of the ball $\mathbb{B}_{n}$, and
$1>r>1/(2\alpha)$. This inequality guarantees that the probability measure of
each ball with the radius less or equal than $1/(2\alpha)$ exponentially
decays for $n\to\infty$. It should be stressed that the constant $C>0$ is
arbitrary but must not depend on $n$ in asymptotic analysis for large $n$.
Condition $1>r>1/(2\alpha)$ is possible only if $\alpha>0.5$. Thus, the
interval of possible $\alpha$ for Theorem 1 is $\alpha\in(0.5,1]$.

###### Theorem 1

[Gorban et al., 2018] Let $1\geq\alpha>1/2$, $1>r>1/(2\alpha)$, $1>\delta>0$,
$Y\subset\mathbb{B}_{n}$ be a finite set, $|Y|<\delta(2r\alpha)^{n}/C$, and
$\boldsymbol{x}$ be a randomly chosen point from a distribution in the unit
ball with the bounded probability density $\rho(\boldsymbol{x})$. Assume that
$\rho(\boldsymbol{x})$ satisfies inequality (6). Then with probability
$p>1-\delta$ point $\boldsymbol{x}$ is Fisher-separable from $Y$ with
threshold $\alpha$ (4).

Proof The volume of the ball (5) does not exceed
$V=\left(\frac{1}{2\alpha}\right)^{n}V_{n}(\mathbb{B}_{n})$ for each
$\boldsymbol{y}\in Y$. The probability that point $\boldsymbol{x}$ belongs to
such a ball does not exceed

$V\sup_{z\in\mathbb{B}_{n}}\rho(z)\leq C\left(\frac{1}{2r\alpha}\right)^{n}.$

The probability that $\boldsymbol{x}$ belongs to the union of $|Y|$ such balls
does not exceed $|Y|C\left(\frac{1}{2r\alpha}\right)^{n}$. For
$|Y|<\delta(2r\alpha)^{n}/C$ this probability is smaller than $\delta$ and
$p>1-\delta$. $\Box$

###### Remark 1

Note that:

  * 1.

The finite set $Y$ in Theorem 1 is just a finite subset of the ball
$\mathbb{B}_{n}$ without any assumption of its randomness. We only used the
assumption about distribution of $\boldsymbol{x}$.

  * 2.

The distribution of $\boldsymbol{x}$ may deviate significantly from the
uniform distribution in the ball $\mathbb{B}_{n}$. Moreover, this deviation
may grow with dimension $n$ as a geometric progression:

$\rho(\boldsymbol{x})/\rho_{\rm uniform}\leq{C}/{r^{n}},$

where $\rho_{\rm uniform}=1/V_{n}(\mathbb{B}_{n})$ is the density of uniform
distribution and $1/(2\alpha)<r<1$ (assuming that $1/2<\alpha\leq 1$).

###### Example 1

Let $\alpha=0.8$, $r=0.75$, $C=1$, $\delta=0.01$. Table 1 shows the upper
bounds on $|Y|$ given by Theorem 1 in various dimensions $n$ if the ratio
$\rho(\boldsymbol{x})/\rho_{\rm uniform}$ is bounded by the geometric
progression $1/r^{n}$.

Table 1:  The upper bound on $|Y|$ that guarantees separation of $\boldsymbol{x}$ from $Y$ by Fisher’s discriminant with probability 0.99 according to Theorem 1 for $\alpha=0.8$, $r=0.75$, $C=1$ in various dimensions. $n$ | $\rho(\boldsymbol{x})/\rho_{\rm uniform}\leq$ | $|Y|\leq$
---|---|---
$10$ | $17.7$ | $0.06$
$50$ | $1.7\cdot 10^{6}$ | $91$
$100$ | $3.1\cdot 10^{12}$ | $828,180$
$200$ | $9.7\cdot 10^{24}$ | $6.8\cdot 10^{13}$
$500$ | $2.9\cdot 10^{62}$ | $3.9\cdot 10^{37}$
$1000$ | $8.6\cdot 10^{124}$ | $1.5\cdot 10^{77}$

For example, for $n=100$, we see that for any set with $|Y|<828,180$ points in
the unit ball, and any distribution whose density $\rho$ deviates from the
uniform one by a factor at most $3.1\cdot 10^{12}$, a random point from this
distribution is Fisher-separable from all points in $Y$ with $99\%$
probability.

In the following Definition we consider separation of each points of a set
from all other points by Fisher discriminant.

###### Definition 2

A finite set $Y\subset{\mathbb{R}}^{n}$ is _Fisher separable_ with center
$\boldsymbol{c}\in{\mathbb{R}}^{n}$ and threshold $\alpha\in(0,1]$, or
$(\alpha,\boldsymbol{c})$-Fisher separable in short, if inequality

$\alpha(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{x}-\boldsymbol{c})>(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{y}-\boldsymbol{c}),$

holds for all $\boldsymbol{x},\boldsymbol{y}\in Y$ such that
$\boldsymbol{x}\neq\boldsymbol{y}$.

If $\boldsymbol{c}=\boldsymbol{0}$ is the origin, we will write
$(\alpha,\boldsymbol{0})$-Fisher separable set as just “$\alpha$-Fisher
separable”, to simplify the notation. From Theorem 1 we obtain the following
corollary.

###### Corollary 1

If $Y\subset\mathbb{B}_{n}$ is a random set
$Y=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{|Y|}\\}$ and for each $j$ the
conditional distributions of vector $\boldsymbol{y}_{j}$ for any given
positions of the other $\boldsymbol{y}_{k}$ in $\mathbb{B}_{n}$ satisfy the
same conditions as the distribution of $\boldsymbol{x}$ in Theorem 1, then the
probability of the random set $Y$ to be $\alpha$-Fisher separable can be
easily estimated:

$p\geq 1-|Y|^{2}C\left(\frac{1}{2r\alpha}\right)^{n}.$

So, $p>0.99$ if $|Y|<(1/10)\,C^{-1/2}(2r\alpha)^{n/2}$.

For this estimate, elements of $Y$ should not be i.i.d. random vectors and
each of them can have its own distribution but with the same restrictions
(with support in a ball and inequality (6)). The flight from i.i.d assumption
in machine learning is recognized as an important problem [Kůrková, 2019]. The
measure concentration phenomena can provide an instrument for avoiding this
assumption [Gorban et al., 2018, Kůrková & Sanguineti, 2019].

###### Example 2

Let $\alpha=0.8$, $r=0.75$, $C=1$. Table 2 shows the upper bounds on $|Y|$
given by Corollary 1 in various dimensions $n$ if the ratio
$\rho(\boldsymbol{x})/\rho_{\rm uniform}$ is bounded by the geometric
progression $1/r^{n}$.

Table 2:  The upper bound on $|Y|$ that guarantees $\alpha$-Fisher separability of $Y$ with probability 0.99, according to Corollary 1 for $\alpha=0.8$, $r=0.75$, $C=1$ in various dimensions. $n$ | $\rho(\boldsymbol{x})/\rho_{\rm uniform}\leq$ | $|Y|\leq$
---|---|---
$10$ | $17.7$ | $0.25$
$50$ | $1.7\cdot 10^{6}$ | $9.54$
$100$ | $3.1\cdot 10^{12}$ | $910$
$200$ | $9.7\cdot 10^{24}$ | $8.2\cdot 10^{6}$
$500$ | $2.9\cdot 10^{62}$ | $6.2\cdot 10^{18}$
$1000$ | $8.6\cdot 10^{124}$ | $3.9\cdot 10^{38}$

For example, for $n=100$, we see that for any distribution whose density
$\rho$ deviates from the uniform one by a factor at most $3.1\cdot 10^{12}$,
any set with $|Y|<910$ points from this distribution is Fisher-separable with
$99\%$ probability. In dimension $n=200$, we may deviate from the uniform
density by a factor $9.7\cdot 10^{24}$ and still separate over $8$ millions
points.

In the post-classical world correction of AI errors is possible by separation
of situations with errors from the situations of correct functioning. This can
be done because the intrinsically high-dimensional data are very ‘rarefied’.
At the same time, the possibility of repairing AI is closely related to the
possibility of its attack. The specific post-classical vulnerabilities and new
types of attacks were identified recently Tyukin et al. [2020]. The exact line
between the classic world of ‘condensed’ data and the post-classic world of
rarefied data is important for both analyzing AI fixes and fixing AI
vulnerability to attacks.

Theorem 1 and Corollary 1 ensure us that if the probability distributions have
no heavy tails and sets of relatively small volume cannot have high
probability, then the exponentially large sets are Fisher separable.
Nevertheless, the presented estimates are far from being optimal, and sharp
estimations of probabilities and sample sizes are very desirable.

The formalization of the idea ‘no heavy tails’ does not require a bounded
distribution support. Below, we show that the exponential asymptotics at
infinity will be fast enough to constructively describe the phenomenon of
stochastic separation. For this purpose, we use the class log-concave
distributions, but already the first estimate shows that the asymptotics of
$|Y|$ guaranteeing Fisher separability for such a general class of
distributions are nonexponential: the boundary $|Y|$ that guarantees
separability with a fixed probability, grows with dimension $n$ as
$a\exp(b\sqrt{n})$ (Theorem 3). It is demonstrated that this estimate cannot
be significantly improved (Example 4). Exponential asymptotic is proved for a
narrower class, strongly log-concave distributions (Sec. 4). The most
prominent member of this family is the normal distribution. The separability
properties for the normal distribution are studied in detail in Sec. 5.1.

The general stochastic separation theorems are proven for convex combinations
of strongly log-concave distributions (Theorem 11). The conditions of Theorem
11 formalize both no heavy tails condition (through strong log-concavity) and
no small sets with high probability condition. In some sense, the generality
of this theorem is sufficient for most of practical purposes, but in specific
cases, for narrower classes and selected distributions the estimates can be
much better than for a wide general class. Therefore, we explore additional
classes like product distributions (data with independent attributes) (Sec.
6), spherically invariant distributions (Sec. 5) and some special examples:
uniform distributions in a ball or in a cube and normal distribution. For data
with independent attributes, the dependent samples are studied (Sec. 7). A
short guide on proven theorems is presented in Sec. 8, and in Sec. 9 we
briefly discuss the application of the stochastic separation theorems in
machine learning and neuroscience.

##  3 Analysis of known stochastic separation theorems

Let us focus on Fisher separability because Fisher discriminants are robust
and can be created by simple, explicit and one-shot rule. The results of
Bárány & Füredi [1988] and Donoho & Tanner [2009] about linear separability
remain beyond the scope of this analysis.

Gorban and Tyukin [2017] proved that if $M$ points are selected independently
uniformly at random in the unit ball in ${\mathbb{R}}^{n}$, then they are
$1$-Fisher separable with high probability, provided that $M$ is bounded by
some exponential function of $n$. A simple version of this result was later
proved111The proof in [Gorban et al., 2018] is presented for $\alpha=1$, but
the argument works for general $\alpha$. in [Gorban et al., 2018].

###### Theorem 2

[Gorban et al., 2018] Let points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$
be i.i.d points from uniform distribution in a ball. For any $\delta>0$, if

$M<\sqrt{2\delta}(2\alpha)^{n/2}=\sqrt{2\delta}\exp\left(\frac{1}{2}\log(2\alpha)n\right),$
(7)

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$\alpha$-Fisher separable with probability greater than $1-\delta$.

The estimate (7) grows exponentially fast in $n$ provided that $\alpha>1/2$.

###### Example 3

Let $\delta=0.01$. Table 3 shows the upper bounds on $M$ in Theorem 2 for
$\alpha=0.6,0.8$ and $1$ in various dimensions $n$.

Table 3:  The upper bounds on $M$ that guarantees Fisher separability of $M$ i.i.d. points from uniform distribution in an $n$-dimensional ball with probability $p>0.99$ for $\alpha=0.6,0.8$ and $1$, according to Theorem 2. | $\alpha=0.6$ | $\alpha=0.8$ | $\alpha=1$
---|---|---|---
$n=10$ | $0.35$ | $1.48$ | $4.52$
$n=50$ | $13.5$ | $17,927$ | $4.7\cdot 10^{6}$
$n=100$ | $1287$ | $2.2\cdot 10^{9}$ | $1.6\cdot 10^{14}$
$n=200$ | $1.1\cdot 10^{7}$ | $3.6\cdot 10^{19}$ | $1.8\cdot 10^{29}$
$n=500$ | $8.8\cdot 10^{18}$ | $1.5\cdot 10^{50}$ | $2.5\cdot 10^{74}$
$n=1000$ | $5.5\cdot 10^{38}$ | $1.6\cdot 10^{101}$ | $4.6\cdot 10^{149}$

For example, for $n=100$, we see that over $2$ billions points from the
uniform distribution in the unit ball are Fisher-separable at level
$\alpha=0.8$ with probability greater than $99\%$.

Of course, uniform distribution in a ball is a very special case, and
separation theorems have been proved for various other families of
distributions. We say that density $\rho:{\mathbb{R}}^{n}\to[0,\infty)$ of
random vector $\boldsymbol{x}$ (and the corresponding probability
distribution) is _log-concave_ , if set
$D=\\{z\in{\mathbb{R}}^{n}\,|\,\rho(z)>0\\}$ is convex and
$g(z)=-\log(\rho(z))$ is a convex function on $D$. We say that $\rho$ is
whitened, or _isotropic_ , if ${\mathbb{E}}[\boldsymbol{x}]=\boldsymbol{0}$,
and

${\mathbb{E}}[(\boldsymbol{x},\theta)^{2})]=1\quad\quad\forall\theta\in\mathbb{S}^{n-1},$
(8)

where $\mathbb{S}^{n-1}$ is the unit sphere in ${\mathbb{R}}^{n}$. Equation
(8) is equivalent to the statment that the variance-covariance matrix for the
components of $\boldsymbol{x}$ is the identity matrix. This can be achieved by
linear transformation of the data during the pre-processing step, therefore
this assumption is not restrictive.

###### Theorem 3

[Gorban et al., 2018, Corollary 2] Let
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from an isotropic log-concave distribution in
${\mathbb{R}}^{n}$. Then set
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is $1$-Fisher separable
with probability greater than $1-\delta$, $\delta>0$, provided that

$M\leq ae^{b\sqrt{n}},$ (9)

where $a>0$ and $b>0$ are constants, depending only on $\delta$.

The following Example demonstrates that $\sqrt{n}$ in (9) cannot be replaced
by $n^{0.5+\epsilon}$ for any $\epsilon>0$, even if points are selected from a
product distribution with identical log-concave components.

###### Example 4

Let $||{\boldsymbol{x}}||_{1}=\sum_{i=1}^{n}|x_{i}|$ denotes the $l_{1}$ norm
of ${\boldsymbol{x}}=(x_{1},x_{2},\dots,x_{n})\in{\mathbb{R}}^{n}$. Let points
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ be i.i.d points from (isotropic
log-concave) distribution in ${\mathbb{R}}^{n}$ with density

$\rho({\boldsymbol{x}})=2^{-n/2}e^{-\sqrt{2}\cdot||{\boldsymbol{x}}||_{1}}.$

For any $\alpha\in(0,1]$, $a>0$, $b>0$, and $\epsilon>0$, if

$M\geq a\exp\left(b\cdot n^{0.5+\epsilon}\right),$ (10)

then set $\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is _not_
$\alpha$-Fisher separable with probability tending to $1$ as $n\to\infty$.

Detail. The probability that any two i.i.d. points
${\boldsymbol{x}}=(x_{1},x_{2},\dots,x_{n})$ and
${\boldsymbol{y}}=(y_{1},y_{2},\dots,y_{n})$ from the given distribution are
_not_ $\alpha$-Fisher separable is bounded by

$\begin{split}&{\mathbb{P}}\left[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})\right]\geq{\mathbb{P}}\left[(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})\right]=\\\
&\;\;\;\;\;{\mathbb{P}}\left[\sum_{i=1}^{n}(x_{i}y_{i}-x_{i}^{2})\geq
0\right]={\mathbb{P}}\left[\sum_{i=1}^{n}z_{i}\geq n\right],\end{split}$

where $z_{i}=x_{i}y_{i}-x_{i}^{2}+1,i=1,\dots,n$ are i.i.d. random variables
with zero mean. Next,

$\begin{split}{\mathbb{P}}\left[\sum_{i=1}^{n}z_{i}\geq
n\right]\geq&{\mathbb{P}}\left[z_{1}\geq
n\right]\cdot{\mathbb{P}}\left[\sum_{i=2}^{n}z_{i}\geq 0\right]=\\\
&{\mathbb{P}}\left[z_{1}\geq
n\right]\left(\frac{1}{2}+o(1)\right),\end{split}$

where the last equality follows from central limit theorem, and $o(1)$ is the
quantity which goes to $0$ as $n\to\infty$. Further,

$\begin{split}\frac{1}{2}{\mathbb{P}}\left[z_{1}\geq
n\right]\geq&\frac{1}{2}{\mathbb{P}}\left[\sqrt{n}\leq x_{1}\leq
2\sqrt{n}\right]\times{\mathbb{P}}\left[3\sqrt{n}\leq y_{1}\right]=\\\
&\frac{1}{8}e^{-4\sqrt{2}\sqrt{n}}\left(1+o(1)\right).\end{split}$

Because $M$ points can be divided into $M/2$ independent pairs, the
probability that all these pairs are $\alpha$-Fisher separable is at most

$\left(1-\frac{1}{8}e^{-4\sqrt{2}\sqrt{n}}\left(1+o(1)\right)\right)^{M/2},$

and the last expression vanishes as $n\to\infty$ if (10) holds. a $\Box$

Example 4 demonstrates that, to recover exponential dependence of $M$ from
$n$, one must consider subclasses of log-concave distributions.

We say that density $\rho:{\mathbb{R}}^{n}\to[0,\infty)$ is strongly log-
concave with constant $\gamma>0$, or $\gamma$-SLC in short, if
$g(z)=-\log(\rho(z))$ is strongly convex, that is,
$g(z)-\frac{\gamma}{2}||z||$ is a convex function on $D$.

###### Theorem 4

[Gorban et al., 2018, Corollary 4] Let
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from an isotropic $\gamma$-SLC distribution in
${\mathbb{R}}^{n}$. Then set
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is $1$-Fisher separable
with probability greater than $1-\delta$, $\delta>0$, provided that

$M\leq ae^{bn},$

where $a>0$ and $b>0$ are some constants, which depends on $\delta$ and
$\gamma$.

Separation theorems have also be proved for various families of distributions
which are not log-concave. As an example, consider “randomly perturbed data”
model (Example 2 in Gorban et al. [2018]). For a fixed $\epsilon\in(0,1)$, let
$\boldsymbol{y}_{1},\boldsymbol{y}_{2},\dots,\boldsymbol{y}_{M}$ be the set of
$M$ arbitrary (non-random) points inside the ball with radius $1-\epsilon$ in
${\mathbb{R}}^{n}$. Let $\boldsymbol{x}_{i},i=1,2,\dots,M$ be a point,
selected uniformly at random from a ball with center $\boldsymbol{y}_{i}$ and
radius $\epsilon$. We think about $\boldsymbol{x}_{i}$ as “perturbed” version
of $\boldsymbol{y}_{i}$. In this model, we say that set
$F=\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is _$\alpha$ -Fisher
separable_ if

$\alpha(\boldsymbol{x}_{i}-\boldsymbol{y}_{i},\boldsymbol{x}_{i}-\boldsymbol{y}_{i})>(\boldsymbol{x}_{i}-\boldsymbol{y}_{i},\boldsymbol{x}_{j}-\boldsymbol{y}_{i}),$

holds for all $i=1,2,\dots,M$ and $j=1,2,\dots,M$ such that $i\neq j$.

###### Theorem 5

[Gorban et al., 2018, Theorem 7] Let
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ random
points in the “randomly perturbed” model with parameter $\epsilon>0$. For any
$\vartheta$ such that $\frac{1}{\sqrt{n}}<\vartheta<1$, set
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is $1$-Fisher separable
with probability at least

$1-\frac{2M^{2}}{\vartheta\sqrt{n}}\left(\sqrt{1-\vartheta^{2}}\right)^{n+1}-M\left(\frac{2\vartheta}{\epsilon}\right)^{n}.$
(11)

In particular, set $\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is
$1$-Fisher separable with probability at least $1-\delta$, $\delta>0$,
provided that $M<ab^{n}$, where $a,b$ are constants depending only on $\delta$
and $\epsilon$.

In Theorem 5 we can, for any fixed $\epsilon,n$ and $M$, select
$\vartheta\in\left(n^{-1/2},1\right)$ to maximize the lower bound (11) for the
probability. The optimal $\vartheta$ can be easily found numerically.

###### Example 5

Let $\vartheta=\vartheta(\epsilon,n,M)$ be such that (11) is maximized. Table
4 shows the lower bound for the probability that $M=100,000$ points in the
“randomly perturbed data” model are $1$-Fisher separable, for various values
of $n$ and $\epsilon$.

Table 4:  The lower bound for probability that 100,000 points in the “randomly perturbed data” (Theorem 5) are Fisher separable for various dimension $n$ and noise bound $\epsilon$. | $\epsilon=1/10$ | $\epsilon=1/5$ | $\epsilon=1/2$
---|---|---|---
$n=500$ | $<0$ | $<0$ | $<0$
$n=1000$ | $<0$ | $<0$ | $0.9998$
$n=2000$ | $<0$ | $<0$ | $1-5.8\cdot 10^{-18}$
$n=5000$ | $<0$ | $0.95$ | $1-1.2\cdot 10^{-57}$
$n=10000$ | $<0$ | $1-5\cdot 10^{-13}$ | $1-1.3\cdot 10^{-123}$
$n=20000$ | $0.96$ | $1-8\cdot 10^{-35}$ | $1-2.2\cdot 10^{-255}$

We see that Theorem 5 is starting to give meaningful results only if the
dimension $n$ is rather large, and the smaller $\epsilon$ the large dimension
we need. This is not much surprising taking into account that the bounds in
Table 4 are valid for an arbitrary set of $M$ points in the $n$-dimensional
ball with radius $1-\epsilon$ and the perturbations make this random finite
set closer to the i.i.d. sample from the uniform distribution in the unit
ball. In the limit $\epsilon\to 1$ this randomly perturbed set turns into such
an i.i.d. sample.

Our final example concerns i.i.d. random points from a product distribution in
a unit cube $U_{n}=[0,1]^{n}$.

###### Theorem 6

[Gorban and Tyukin, 2017, Corollary 2] Let
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from a product distribution in a unit cube. Let
$\boldsymbol{c}\in U_{n}$ be an arbitrary (non-random) point. Then set
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is
$(1,\boldsymbol{c})$-Fisher separable with probability greater than
$1-\delta$, $\delta>0$, provided that

$(M+1)^{2}<\frac{\delta}{3}\exp(0.5n\sigma_{0}^{4}),$ (12)

where $\sigma_{0}$ is the minimal standard deviation of a component
distribution.

Theorems 2, 3, 4, 5 and 6 are proved in works by Gorban and Tyukin [2017],
Gorban et al. [2018] based on the following general principle, which, however,
was not formulated explicitly. The high-dimensional stochastic separation
theorems are formulated for the classes of distributions in ${\mathbb{R}}^{n}$
for all sufficiently large $n$. For these classes, the probability that two
random points are $(\alpha,\boldsymbol{c})$-Fisher inseparable is estimated
from above by some function $f(n,\alpha)$. After that, further estimates of
$M$ and probabilities of separability of sets are constructed from this
function, $f(n,\alpha)$. Let us formulate this principle explicitly.

###### Theorem 7

Let ${\cal F}$ be a family of $M$-point distributions in ${\mathbb{R}}^{n}$,
$F\subset{\mathbb{R}}^{n}$ be a random $M$-point set chosen according to some
distribution in ${\cal F}$, $\boldsymbol{c}\in{\mathbb{R}}^{n}$,
$\delta\in(0,1)$, and $I\subset(0,1]$. Assume that there exists a function
$f(n,\alpha)$ such that for any two points $\boldsymbol{x}\in F$ and
$\boldsymbol{y}\in F$

${\mathbb{P}}[\alpha(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{x}-\boldsymbol{c})\leq(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{y}-\boldsymbol{c})]\leq
f(n,\alpha),\quad\alpha\in I,\,n=1,2,\dots$ (13)

and

$M<\frac{1}{2}+\sqrt{\frac{1}{4}+\frac{\delta}{f(n,\alpha)}}.$ (14)

Then, for all $n$ and $\alpha\in I$, the expected number of
$(\alpha,\boldsymbol{c})$-inseparable pairs in $F$ is less than $\delta$. In
particular, set $F$ is $(\alpha,\boldsymbol{c})$-Fisher separable with
probability greater than $1-\delta$.

Proof If $I(i,j)$ is the indicator function for the event that pair
$\boldsymbol{x}_{i}$, $\boldsymbol{x}_{j}$ is
$(\alpha,\boldsymbol{c})$-inseparable. Then the expected number of
$(\alpha,\boldsymbol{c})$-inseparable pairs is

$\begin{split}{\mathbb{E}}\left[\sum_{i\neq j}I(i,j)\right]=&\sum_{i\neq
j}{\mathbb{E}}[I(i,j)]\leq\sum_{i\neq j}f(n,\alpha)=\\\
&M(M-1)f(n,\alpha)<\delta,\end{split}$

where the last inequality follows from (14).

If set $F$ would be $(\alpha,\boldsymbol{c})$-Fisher separable with
probability $p\leq 1-\delta$, then the expected number $E$ of
$(\alpha,\boldsymbol{c})$-inseparable pairs would be

$E\geq p\cdot 0+(1-p)\cdot 1\geq\delta,$

which is a contradiction. Here, the first inequality follows from the fact
that the number of $(\alpha,c)$-inseparable pairs is integer hence it is at
least $1$. $\Box$

If $\boldsymbol{c}=\boldsymbol{0}$ is the origin, inequality (13) simplifies
to

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]\leq
f(n,\alpha),\quad\alpha\in I,\,n=1,2,\dots$ (15)

A sufficient condition for (14) is the simpler estimate

$M\leq\sqrt{\frac{\delta}{f(n,\alpha)}}.$ (16)

We will always use (16) in place of (14) unless we aim for the exact
(necessary and sufficient) bound for $M$. In particular, Theorem 2 follows
from Theorem 7 with (16) and inequality

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]\leq\frac{1}{2}(2\alpha)^{-n},\quad\alpha\in(0,1],\,n=1,2,\dots$
(17)

which holds as equality for $\alpha=1$, see [Gorban et al., 2018]. Theorems 3
and 4 are proved in the same way. This implies the following corollary.

###### Corollary 2

The conclusion “set $\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ is
$1$-Fisher separable with probability greater than $1-\delta$” in Theorems 2,
3, 4, 5 and 6 can be replaced by a stronger conclusion that the expected
number of inseparable pairs in this set is less than $\delta$.

This stronger conclusion is important for practical purposes because it
prevents a scenario when we have many (maybe exponentially many in $n$)
inseparable pairs with probability $\delta$.

The proof of Theorem 7 implies that the bound (14) is in fact _necessary and
sufficient_ condition in the i.i.d case.

###### Corollary 3

Let $\boldsymbol{c}\in{\mathbb{R}}^{n}$ be fixed,
$F=\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from an arbitrary distribution in ${\mathbb{R}}^{n}$. Let
$f(n,\alpha):={\mathbb{P}}[\alpha(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{x}-\boldsymbol{c})\leq(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{y}-\boldsymbol{c})]$,
where the probability does not depend on the choice of $\boldsymbol{x}\in F$
and $\boldsymbol{y}\in F$. Then the expected number of $\alpha$-inseparable
pairs in $F$ is less than $\delta$ if and only if inequality (14) holds.

For example, the fact that inequality (17) is an equality for $\alpha=1$
implies the following optimal separation result.

###### Corollary 4

Let $\alpha=1$, and let
$F=\left\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\right\\}$ be the set of
i.i.d points from uniform distribution in a ball. For any $\delta>0$, the
expected number of $1$-inseparable pairs from $F$ is less than $\delta$ if and
only if

$M<\frac{1}{2}+\sqrt{\frac{1}{4}+\delta 2^{n+1}}.$ (18)

In particular, (18) implies that $F$ is $1$-Fisher separable with probability
greater than $1-\delta$.

In this paper, we prove a version of Corollary 4 for arbitrary
$\alpha\in(0,1]$.

The disadvantage of Theorems 3, 4 and 5 is that constants $a$ and $b$ in the
bounds for $M$ are not explicitly given. In Theorem 6, the upper bound for $M$
is explicit but impractical in the important case if the dimension $n$ is
measured in hundreds rather than in thousands.

###### Example 6

For $\delta=0.01$ (which corresponds to $99\%$ confidence), $n=500$, and
$\sigma_{0}=0.5$ (maximal possible standard deviation for distribution with
$[0,1]$ support), (12) holds provided $M<141.7$.

In practise, however, datasets often have much more than $141$ point, but
Fisher separability still holds. This motivates the search for stochastic
Fisher separability theorems with better bounds.

In this paper we obtain separation theorems for various classes of log-concave
and product distributions with _explicit_ bounds on $M$. Moreover, we will aim
to provide as good bounds as possible, ideally the optimal ones. In addition
to better bounds, we also relax the i.i.d assumption.

In the i.i.d. case, Corollary 3 implies that, if we can calculate the
probability in (13) _exactly_ , then (14) provides the optimal (necessary and
sufficient) bound for $M$. This exact bound, however, is usually quite
complicated, based on some integral expressions, and in such cases we will aim
for simpler asymptotically tight bounds. We will write

$f(n)\sim g(n)$

if $\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=1$. We say that function $g(n)$
is asymptotically tight lower (respectively, upper) bound for $f(n)$ if
$f(n)\geq g(n)$ (respectively, $f(n)\leq g(n)$) and $f(n)\sim g(n)$. If
$f(n,\alpha)$ in (13) is the asymptotically tight upper bound for the
probability in question, then (14) and (16) provide asymptotically tight upper
bounds for $M$.

If one can prove (13) with $f(n,\alpha)=ae^{-2bn}$ for some constants $a$, $b$
depending on $\alpha$, one get (16) with bound
$M\leq\sqrt{\frac{\delta}{a}}e^{bn}$. If $f(n,\alpha)=ae^{-2bn}$, then
$b=-\frac{\log(f(n,\alpha)/a)}{2n}$. In general, the last expression may
depend on $n$, and we define

$b(\alpha)=b_{f}(\alpha):=\lim\limits_{n\to\infty}-\frac{\log(f(n,\alpha))}{2n}=-\frac{1}{2}\lim\limits_{n\to\infty}\log\sqrt[n]{f(n,\alpha)}.$
(19)

Let ${\cal G}$ be the set of all functions $f(n,\alpha)$ for which (13) holds.
We say that separation theorem 7 has optimal exponent if $b_{f}(\alpha)\geq
b_{g}(\alpha)$ for all $g\in{\cal G}$. Obviously, if bound in (13) is
asymptotically tight, it also has optimal exponent, but not vice versa. For
non-optimal separation theorems the exponent $b(\alpha)$ is a good way to
measure the “quality” of the theorem. We show that in all our non-optimal
theorems the exponents differ from optimal by a factor less than $2$.

##  4 Separation theorems for strongly log-concave distributions

###  4.1 Separation of i.i.d. data from isotropic strongly log-concave
distribution

This Section proves the following explicit versions of Theorem 4.

###### Theorem 8

Let $\delta>0$, $\alpha\in(0,1]$, $\gamma>0$, and let
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from an isotropic $\gamma$-SLC distribution in
${\mathbb{R}}^{n}$. If

$M<\sqrt{\frac{\delta}{2}}\exp\left(\frac{\alpha^{2}(\gamma
n-1)}{4(1+\alpha)^{2}}\right),$

then the expected number of $\alpha$-inseparable pairs in $F$ is less than
$\delta$. In particular, set $F$ is $\alpha$-Fisher separable with probability
greater than $1-\delta$.

###### Theorem 9

Let $\delta>0$, $\alpha\in(0,1]$, $\gamma>0$, and let
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from an isotropic $\gamma$-SLC distribution in
${\mathbb{R}}^{n}$. If $n>\frac{1+2\alpha^{2}}{\gamma\alpha^{2}}$ and

$\begin{split}M<&\sqrt{\delta}\left(\frac{\alpha^{2}}{(1+\alpha^{2})^{3/2}}\sqrt{2\pi(\gamma
n-1)}\exp\left(-\frac{\alpha^{2}(\gamma
n-1)}{2(1+\alpha^{2})}\right)\right.+\\\
&\;\;\;\;\;\;\;\;\;\left.\exp\left(-\frac{\alpha^{2}(\gamma
n-1)}{2}\right)\right)^{-1/2},\end{split}$ (20)

then the expected number of $\alpha$-inseparable pairs in $F$ is less than
$\delta$. In particular, set $F$ is $\alpha$-Fisher separable with probability
greater than $1-\delta$.

Theorem 9 provides a less restrictive upper bound for $M$ for large $n$, while
the upper bound in Theorem 8 is substantially simpler.

###### Example 7

Let $\delta=0.01$ and $\alpha=1$. Table 5 shows the upper bounds on $M$ in
Theorem 9 for $\gamma=0.6,0.8$ and $1$ in various dimensions $n$.

Table 5:  The upper bound of $M$ (20) that guarantees Fisher separability of a $M$-element i.i.d. sample from an isotropic $\gamma$-SLC distribution in ${\mathbb{R}}^{n}$ for $\gamma=0.6,0.8$ and $1$ with probability $p>0.99$ for various dimensions $n$. | $\gamma=0.6$ | $\gamma=0.8$ | $\gamma=1$
---|---|---|---
$n=10$ | $0.12$ | $0.15$ | $0.18$
$n=50$ | $1.71$ | $5.56$ | $18$
$n=100$ | $61$ | $692$ | $7974$
$n=200$ | $92,783$ | $1.2\cdot 10^{7}$ | $1.8\cdot 10^{9}$
$n=500$ | $4.3\cdot 10^{14}$ | $1.1\cdot 10^{20}$ | $2.7\cdot 10^{25}$
$n=1000$ | $7\cdot 10^{30}$ | $4.7\cdot 10^{41}$ | $3.2\cdot 10^{52}$

For example, for $n=200$, we see that $12$ millions points from a strictly
log-concave distribution with $\gamma=0.8$ are $1$-Fisher-separable with
probability greater than $99\%$.

The exponent $b(\alpha)$ defined in (19) is

$b(\alpha)=\frac{\alpha^{2}\gamma}{4(1+\alpha)^{2}}$

for Theorem 8, and

$b(\alpha)=\frac{\alpha^{2}\gamma}{4(1+\alpha^{2})}$

for Theorem 9. For example, if $\gamma=1$ (which is the case for normal
distribution) and $\alpha=1$, the exponents are $b=\frac{1}{16}=0.0625$ and
$b=\frac{1}{8}=0.125$, respectively. The optimal exponent for normal
distribution is given in Theorem 12 below and is equal to
$\frac{1}{4}\log(2)=0.173..$, hence exponent in Theorem 9 cannot be improved
more than by a factor $2\log(2)=1.386...$.

The first step in the proof of Theorems 8 and 9 is the following estimate.

###### Proposition 1

Let $\boldsymbol{x}$ and $\boldsymbol{y}$ be two i.i.d. points from an
isotropic $\gamma$-SLC distribution. Then

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]\leq{\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}].$
(21)

Proof Theorem 5.2 in the book of Ledoux [2001] states that, if random vector
$\boldsymbol{z}$ follows a $\gamma$-SLC distribution, then logarithmic Sobolev
inequality

${\mathbb{E}}[f^{2}(\boldsymbol{z})\log
f^{2}(\boldsymbol{z})]-{\mathbb{E}}[f^{2}(\boldsymbol{z})]{\mathbb{E}}[\log
f^{2}(\boldsymbol{z})]\leq\frac{2}{\gamma}{\mathbb{E}}[||\nabla
f(\boldsymbol{z})||^{2}]$ (22)

holds for every locally Lipschitz function $f$ on ${\mathbb{R}}^{n}$. By
[Ledoux, 2001, Theorem 5.3], this implies that inequality

${\mathbb{P}}[g(\boldsymbol{z})\geq E[g(\boldsymbol{z})]+r]\leq e^{-\gamma
r^{2}/2}$ (23)

holds for every $r\geq 0$ and every $1$-Lipschitz function $g$ on
${\mathbb{R}}^{n}$.

Assuming that $\boldsymbol{x}\neq\boldsymbol{0}$ is fixed, and applying (23)
to $1$-Lipschitz function
$g(\boldsymbol{y})=\frac{(\boldsymbol{x},\boldsymbol{y})}{||\boldsymbol{x}||}$
with
${\mathbb{E}}[g(\boldsymbol{y})]=\frac{(\boldsymbol{x},{\mathbb{E}}[\boldsymbol{y}])}{||\boldsymbol{x}||}=\frac{(\boldsymbol{x},\boldsymbol{0})}{||\boldsymbol{x}||}=0$
and $r=\alpha||\boldsymbol{x}||$, we obtain

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]={\mathbb{P}}\left[\frac{(\boldsymbol{x},\boldsymbol{y})}{||\boldsymbol{x}||}\geq
0+\alpha||\boldsymbol{x}||\right]\leq
e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}$ (24)

Now let $\boldsymbol{x}$ and $\boldsymbol{y}$ be both random, and let $I$ be
the indicator function of the event
$\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})$.
Then

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]={\mathbb{E}}[I]={\mathbb{E}}_{\boldsymbol{x}}[{\mathbb{E}}_{\boldsymbol{y}}[I|\boldsymbol{x}]]\leq{\mathbb{E}}_{\boldsymbol{x}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}],$

where the second equality follows from independence of $\boldsymbol{x}$ and
$\boldsymbol{y}$, and the inequality follows from (24). $\Box$

The next proposition provides an easy estimate for the right-hand side of
(21).

###### Proposition 2

Let $\boldsymbol{x}$ be a points from an isotropic $\gamma$-SLC distribution.
Then

${\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}]\leq
2\exp\left(-\frac{\gamma\alpha^{2}}{2(1+\alpha)^{2}}\mu^{2}\right),$ (25)

where $\mu={\mathbb{E}}[||\boldsymbol{x}||]$.

Proof For every $t>0$,

$\begin{split}{\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}]=&{\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}\,|\,||\boldsymbol{x}||>t]{\mathbb{P}}[||\boldsymbol{x}||>t]+\\\
&\;\;\;{\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}\,|\,||\boldsymbol{x}||\leq
t]{\mathbb{P}}[||\boldsymbol{x}||\leq t].\end{split}$

Now,

${\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}\,|\,||\boldsymbol{x}||>t]\leq{\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}t^{2}}\,|\,||\boldsymbol{x}||>t]=e^{-\frac{\gamma\alpha^{2}}{2}t^{2}},$
${\mathbb{P}}[||\boldsymbol{x}||>t]\leq 1,$
${\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}\,|\,||\boldsymbol{x}||\leq
t]\leq{\mathbb{E}}[1\,|\,||\boldsymbol{x}||\leq t]=1,$

and

${\mathbb{P}}[||\boldsymbol{x}||\leq
t]={\mathbb{P}}[\mu-||\boldsymbol{x}||\geq\mu-t]\leq
e^{-\gamma(\mu-t)^{2}/2},$

where the last inequality is an application of (23) to $1$-Lipschitz function
$g(\boldsymbol{x})=\mu-||\boldsymbol{x}||$. Hence,

${\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}]\leq
e^{-\frac{\gamma\alpha^{2}}{2}t^{2}}+e^{-\gamma(\mu-t)^{2}/2}.$

Applying the last inequality with $t=\frac{\mu}{\alpha+1}$, we get the result.
$\Box$

The next Proposition provides an estimate for
$\mu={\mathbb{E}}[||\boldsymbol{x}||]$.

###### Proposition 3

Let $\boldsymbol{x}$ be a points from an isotropic $\gamma$-SLC distribution
and let $\mu={\mathbb{E}}[||\boldsymbol{x}||]$. Then

$\mu^{2}\geq n-\frac{1}{\gamma}.$ (26)

Proof As remarked by Ledoux [2001, p. 92], the logarithmic Sobolev inequality
(22) implies Poincare inequality

$Var[f(\boldsymbol{x})]\leq\frac{1}{\gamma}{\mathbb{E}}[||\nabla
f(\boldsymbol{x})||^{2}].$

Applying it with $f(\boldsymbol{x})=||\boldsymbol{x}||$, we obtain

${\mathbb{E}}[||\boldsymbol{x}||^{2}]-\mu^{2}=Var[||\boldsymbol{x}||]\leq\frac{1}{\gamma}||\nabla(||\boldsymbol{x}||)||=\frac{1}{\gamma}.$

Because ${\mathbb{E}}[||\boldsymbol{x}||^{2}]=n$ for isotropic distributions,
this implies (26). $\Box$

Proof of Theorem 8. The combination of (21), (25), and (26) implies that (15)
holds with

$f_{\gamma}(n,\alpha)=2\exp\left(-\frac{\gamma\alpha^{2}}{2(1+\alpha)^{2}}\left(n-\frac{1}{\gamma}\right)\right),$

and Theorem 8 follows from Theorem 7. $\Box$

To prove Theorem 9, we need an improved version of Proposition 2.

###### Proposition 4

Let $\boldsymbol{x}$ be a points from an isotropic $\gamma$-SLC distribution.
Then

$\begin{split}&{\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}]\leq\\\
&\frac{\alpha^{2}}{(1+\alpha^{2})^{3/2}}\sqrt{2\pi\gamma}\mu\exp\left(-\frac{\gamma\alpha^{2}\mu^{2}}{2(1+\alpha^{2})}\right)+\exp\left(-\frac{\gamma\alpha^{2}\mu^{2}}{2}\right),\end{split}$
(27)

where $\mu={\mathbb{E}}[||\boldsymbol{x}||]$.

Proof Because $e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}$ takes
value between $0$ and $1$,

${\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}]=\int_{0}^{1}{\mathbb{P}}\left[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}>z\right]dz.$

We have

$\begin{split}p(z):=&{\mathbb{P}}\left[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}>z\right]={\mathbb{P}}\left[||\boldsymbol{x}||<\sqrt{-\frac{2\log
z}{\gamma\alpha^{2}}}\,\right]=\\\
&{\mathbb{P}}\left[\mu-||\boldsymbol{x}||>\mu-\sqrt{-\frac{2\log
z}{\gamma\alpha^{2}}}\,\right]\end{split}$

If $z\geq z_{0}:=e^{-\frac{1}{2}\gamma\alpha^{2}\mu^{2}}$, then
$r:=\mu-\sqrt{-\frac{2\log z}{\gamma\alpha^{2}}}\geq 0$, and (23) with
$1$-Lipschitz function $g(\boldsymbol{x})=\mu-||\boldsymbol{x}||$ yields

$p(z)\leq q(z):=\exp\left(-\frac{\gamma}{2}\left(\mu-\sqrt{-\frac{2\log
z}{\gamma\alpha^{2}}}\right)^{2}\right).$

We also have a trivial estimate $p(z)\leq 1$ for $z\leq z_{0}$, which implies

$\int_{0}^{1}p(z)dz\leq\int_{0}^{z_{0}}1\,dz+\int_{z_{0}}^{1}q(z)\,dz=z_{0}+I,$

where $I=\int_{z_{0}}^{1}q(z)\,dz$. Integration in Mathematica returns

$I=\frac{\alpha^{2}}{2(1+\alpha^{2})^{3/2}}\exp\left(-\frac{1}{2}\gamma(2+\alpha^{2})\mu^{2}\right)(S_{1}+S_{2}),$

where

$S_{1}=-2\sqrt{1+\alpha^{2}}(e^{\gamma\mu^{2}}-e^{\frac{1}{2}(1+\alpha^{2})\gamma\mu^{2}}),$

and

$\begin{split}S_{2}=&\exp\left(\frac{(2+2\alpha^{2}+\alpha^{4})\gamma\mu^{2}}{2(1+\alpha^{2})}\right)\sqrt{2\pi\gamma}\mu\left(\phi\left(\sqrt{\frac{\gamma}{2+2\alpha^{2}}}m\right)\right.+\\\
&\;\;\;\;\;\left.\phi\left(\alpha^{2}\sqrt{\frac{\gamma}{2+2\alpha^{2}}}m\right)\right),\end{split}$

where $\phi(y):=\frac{1}{\sqrt{\pi}}\int_{-y}^{y}e^{-t^{2}}dt$. Inequality
$\alpha\leq 1$ implies that $S_{1}\leq 0$. Using this and the fact that
$\phi(y)\leq 1$ for all $y$, we get an estimate

$\begin{split}\int_{0}^{1}p(z)dz\leq z_{0}+I\leq
z_{0}+&\frac{\alpha^{2}}{2(1+\alpha^{2})^{3/2}}\exp\left(-\frac{1}{2}\gamma(2+\alpha^{2})\mu^{2}\right)\times\\\
&\exp\left(\frac{(2+2\alpha^{2}+\alpha^{4})\gamma\mu^{2}}{2(1+\alpha^{2})}\right)\sqrt{2\pi\gamma}\mu\cdot
2,\end{split}$

which simplifies to (27). $\Box$

Proof of Theorem 9.

Let us consider the left-hand side of (27) as a function $f(\mu)$ of $\mu$ and
show that $f$ is a decreasing function. The second term is clearly decreasing,
while the first term is decreasing if the derivative of
$\mu\exp\left(-\frac{\gamma\alpha^{2}\mu^{2}}{2(1+\alpha^{2})}\right)$ is
negative, which holds if $\mu^{2}>\frac{1+\alpha^{2}}{\gamma\alpha^{2}}$. The
last inequality follows from condition
$n>\frac{1+2\alpha^{2}}{\gamma\alpha^{2}}$ and Proposition 3.

Because $f(\mu)$ is a decreasing function, and $\mu\geq n-\frac{1}{\gamma}$ by
Proposition 3, we have

${\mathbb{E}}[e^{-\frac{\gamma\alpha^{2}}{2}||\boldsymbol{x}||^{2}}]\leq
f\left(n-\frac{1}{\gamma}\right).$

This together with (21) implies that (15) holds with
$f_{\gamma}(n,\alpha)=\delta(R_{n})^{-2}$, where $R_{n}$ is the right-hand
side of (20). Then (20) follows from Theorem 7. $\Box$

###### Remark 2

In fact, the only place when we have used that the underlying distribution is
$\gamma$-SLC is the assertion that Sobolev inequality (22) holds. Hence, the
condition that the distribution is $\gamma$-SLC in Theorems 8 and 9 can be
relaxed to the condition that the distribution is isotropic, log-concave, and
such that (22) holds.

###  4.2 Some generalizations

This section provides some generalizations of Theorem 8. We first consider the
case when the data are independent, but

  * -

the data are not identically distributed, and

  * -

the distributions for the data points are strongly log-concave but not
necessarily isotropic.

###### Theorem 10

Let $\delta>0$, $\alpha\in(0,1]$, and let
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be a set of $M$
independent random points in ${\mathbb{R}}^{n}$. Let $\boldsymbol{x}_{i}$
follow a $\gamma_{i}$-SLC distribution with $\gamma_{i}>0$, with expectation
$x_{i}^{0}=E[\boldsymbol{x}_{i}]$ and norm expectation
$\mu_{i}={\mathbb{E}}[||\boldsymbol{x}_{i}||]$. Assume that inequality

$||x_{j}^{0}||<\alpha\mu_{i}$ (28)

holds for every pair $1\leq i,j\leq M$. If

$M<\sqrt{\frac{\delta}{2}}\exp\left(\min_{i,j}\left(\frac{\gamma_{i}\gamma_{j}(\mu_{i}\alpha-||x_{j}^{0}||)^{2}}{2(\sqrt{\gamma_{j}}\alpha+\sqrt{\gamma_{i}})^{2}}\right)\right),$
(29)

then the expected number of $\alpha$-inseparable pairs in $F$ is less than
$\delta$. In particular, set $F$ is $\alpha$-Fisher separable with probability
greater than $1-\delta$.

Proof We will use inequality (23), which is valid for every $\gamma$-SLC
distribution, not necessarily isotropic. Fix some indices $i$ and $j$. Define

$t=\frac{\sqrt{\gamma_{i}}\mu_{i}+\sqrt{\gamma_{j}}||x_{j}^{0}||}{\sqrt{\gamma_{j}}\alpha+\sqrt{\gamma_{i}}}.$
(30)

Then

$\mu_{i}-t=\frac{\sqrt{\gamma_{j}}(\alpha\mu_{i}-||x_{j}^{0}||)}{\sqrt{\gamma_{j}}\alpha+\sqrt{\gamma_{i}}}>0,$
(31)

where the inequality follows from (28).

We have

$\begin{split}&{\mathbb{P}}[\alpha(\boldsymbol{x}_{i},\boldsymbol{x}_{i})\leq(\boldsymbol{x}_{i},\boldsymbol{x}_{j})]\leq\\\
&\;\;\;{\mathbb{P}}[||\boldsymbol{x}_{i}||\leq
t]+{\mathbb{P}}[\alpha(\boldsymbol{x}_{i},\boldsymbol{x}_{i})\leq(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\text{
conditional to }||\boldsymbol{x}_{i}||\geq t].\end{split}$ (32)

Applying (23) to $1$-Lipschitz function
$g(\boldsymbol{x}_{i})=\mu_{i}-||\boldsymbol{x}_{i}||$, we obtain

${\mathbb{P}}[||\boldsymbol{x}_{i}||\leq
t]={\mathbb{P}}[\mu_{i}-||\boldsymbol{x}_{i}||\geq\mu_{i}-t]\leq
e^{-\gamma_{i}(\mu_{i}-t)^{2}/2}.$ (33)

Let us now estimate the second term in (32). Assume that $\boldsymbol{x}_{i}$
such that $||\boldsymbol{x}_{i}||\geq t$ is fixed. Applying (23) to
$1$-Lipschitz function
$g(\boldsymbol{x}_{j})=\frac{(\boldsymbol{x}_{i},\boldsymbol{x}_{j})}{||\boldsymbol{x}_{i}||}$
with
${\mathbb{E}}[g(\boldsymbol{x}_{j})]=\frac{(\boldsymbol{x}_{i},x_{j}^{0})}{||\boldsymbol{x}_{i}||}$
and
$r=\alpha||\boldsymbol{x}_{i}||-\frac{(\boldsymbol{x}_{i},x_{j}^{0})}{||\boldsymbol{x}_{i}||}$,
we obtain

${\mathbb{P}}[\alpha(\boldsymbol{x}_{i},\boldsymbol{x}_{i})\leq(\boldsymbol{x}_{i},\boldsymbol{x}_{j})]={\mathbb{P}}\left[\frac{(\boldsymbol{x}_{i},\boldsymbol{x}_{j})}{||\boldsymbol{x}_{i}||}\geq\frac{(\boldsymbol{x}_{i},x_{j}^{0})}{||\boldsymbol{x}_{i}||}+r\right]\leq
e^{-\frac{\gamma_{j}}{2}r^{2}},$

provided that $r>0$. In fact,

$r=\alpha||\boldsymbol{x}_{i}||-\frac{(\boldsymbol{x}_{i},x_{j}^{0})}{||\boldsymbol{x}_{i}||}\geq\alpha
t-\frac{||\boldsymbol{x}_{i}||\cdot||x_{j}^{0}||}{||\boldsymbol{x}_{i}||}=\alpha
t-||x_{j}^{0}||=\frac{\sqrt{\gamma_{i}}}{\sqrt{\gamma_{j}}}(\mu_{i}-t),$

where the last equality follows from (30). This implies that $r>0$, and also
that

$\begin{split}&{\mathbb{P}}[\alpha(\boldsymbol{x}_{i},\boldsymbol{x}_{i})\leq(\boldsymbol{x}_{i},\boldsymbol{x}_{j})]\leq\exp\left(-\frac{\gamma_{j}}{2}r^{2}\right)\leq\\\
&\;\;\;\;\;\exp\left(-\frac{\gamma_{j}}{2}\left(\frac{\sqrt{\gamma_{i}}}{\sqrt{\gamma_{j}}}(\mu_{i}-t)\right)^{2}\right)=e^{-\gamma_{i}(\mu_{i}-t)^{2}/2}.\end{split}$

Because this inequality holds for every fixed $\boldsymbol{x}_{i}$ such that
$||\boldsymbol{x}_{i}||\geq t$, it implies that

${\mathbb{P}}[\alpha(\boldsymbol{x}_{i},\boldsymbol{x}_{i})\leq(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\text{
conditional to }||\boldsymbol{x}_{i}||\geq t]\leq
e^{-\gamma_{i}(\mu_{i}-t)^{2}/2}.$

Combining this with (33) and (32), we obtain

$\begin{split}{\mathbb{P}}[\alpha(\boldsymbol{x}_{i},\boldsymbol{x}_{i})\leq&(\boldsymbol{x}_{i},\boldsymbol{x}_{j})]\leq
2e^{-\gamma_{i}(\mu_{i}-t)^{2}/2}\leq\\\
&2\exp\left(-\min_{i,j}\left(\frac{\gamma_{i}\gamma_{j}(\mu_{i}\alpha-||x_{j}^{0}||)^{2}}{2(\sqrt{\gamma_{j}}\alpha+\sqrt{\gamma_{i}})^{2}}\right)\right),\end{split}$
(34)

where we have used (31). The last bound holds for any pair of indices $i,j$,
and application of Theorem 7 finishes the proof. $\Box$

Repeating the proof of Proposition 3, we get that

$\mu_{i}^{2}\geq{\mathbb{E}}[||\boldsymbol{x}_{i}||^{2}]-\frac{1}{\gamma_{i}}.$

Writing $\boldsymbol{x}_{i}=(x_{i}^{1},\dots,x_{i}^{n})$ component-wise, we
obtain that

${\mathbb{E}}[||\boldsymbol{x}_{i}||^{2}]=\sum\limits_{k=1}^{n}{\mathbb{E}}[(x_{i}^{k})^{2}].$

Hence, if we assume that

  * -

All $\gamma_{i}$ are bounded from below by some constant independent of $n$,
and

  * -

The averages $\frac{1}{n}\sum\limits_{k=1}^{n}{\mathbb{E}}[(x_{i}^{k})^{2}]$
are bounded from below by some constant independent of $n$, and

  * -

Ratios $\frac{||x_{j}^{0}||}{\alpha\mu_{i}}$ are bounded from above by some
constant $\beta<1$ independent from $n$,

then the bound in (29) grows exponentially in $n$.

Next we consider the case when the data are i.i.d. but follow the distribution
which is a mixture of $\gamma$-SLC distributions.

###### Theorem 11

Let $\delta>0$, $\alpha\in(0,1]$, and let
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points in ${\mathbb{R}}^{n}$, which follow the distribution with
density

$f(x)=\sum\limits_{i=1}^{k}\beta_{i}f_{i}(x),$

where $\beta_{i}\geq 0$ are coefficients such that
$\sum\limits_{i=1}^{k}\beta_{i}=1$, and $f_{i}$ are densities of
$\gamma_{i}$-SLC distributions with $\gamma_{i}>0$. Let $x_{i}^{0}$ and
$\mu_{i}$ be the expectation and norm expectation, respectively, of a random
vector following distribution with density $f_{i}$. Assume that inequality

$||x_{j}^{0}||<\alpha\mu_{i}$

holds for every pair $1\leq i,j\leq k$. If

$M<\sqrt{\frac{\delta}{2}}\exp\left(\min_{i,j}\left(\frac{\gamma_{i}\gamma_{j}(\mu_{i}\alpha-||x_{j}^{0}||)^{2}}{2(\sqrt{\gamma_{j}}\alpha+\sqrt{\gamma_{i}})^{2}}\right)\right),$

then the expected number of $\alpha$-inseparable pairs in $F$ is less than
$\delta$. In particular, set $F$ is $\alpha$-Fisher separable with probability
greater than $1-\delta$.

Proof Let $\Omega\subset{\mathbb{R}}^{2n}$ be the set of points
$(x_{1},\dots,x_{n},y_{1},\dots,y_{n})\in{\mathbb{R}}^{2n}$ such that
$\alpha\sum\limits_{k=1}^{n}x_{k}^{2}\leq\sum\limits_{k=1}^{n}x_{k}y_{k}$.
Then, for any $\boldsymbol{x},\boldsymbol{y}\in F$,

$\begin{split}&{\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]=\int_{\Omega}f(x)f(y)dxdy=\\\
&\;\;\;\;\;\int_{\Omega}\left(\sum\limits_{i=1}^{k}\beta_{i}f_{i}(x)\right)\left(\sum\limits_{j=1}^{k}\beta_{j}f_{j}(y)\right)dxdy=\\\
&\;\;\;\;\;\sum\limits_{i=1}^{k}\sum\limits_{j=1}^{k}\beta_{i}\beta_{j}\int_{\Omega}f_{i}(x)f_{j}(y)dxdy\leq\sum\limits_{i=1}^{k}\sum\limits_{j=1}^{k}\beta_{i}\beta_{j}B=B,\end{split}$

where

$B=2\exp\left(-\min_{i,j}\left(\frac{\gamma_{i}\gamma_{j}(\mu_{i}\alpha-||x_{j}^{0}||)^{2}}{2(\sqrt{\gamma_{j}}\alpha+\sqrt{\gamma_{i}})^{2}}\right)\right)$

is the right-hand side of (34). Then application of Theorem 7 finishes the
proof. $\Box$

A straightforward combination of Theorems 10 and 11 allows to treat even more
general case when the data are independent but not identically distributed,
and the distribution of each data point is a mixture of log-concave ones, but
the notation become messy so we omit the details.

##  5 Separation theorems for spherically invariant log-concave distributions

Assume that points in ${\mathbb{R}}^{n}$ are selected from distribution whose
density $\hat{\rho}:{\mathbb{R}}^{n}\to{\mathbb{R}}_{+}$, where
${\mathbb{R}}_{+}=[0,\infty)$, is spherically invariant, that is,

$\hat{\rho}(x)=C_{n}\rho(||x||),\quad\forall x\in{\mathbb{R}}^{n}$ (35)

for some function $\rho:{\mathbb{R}}_{+}\to{\mathbb{R}}_{+}$, where the factor
$C_{n}$ is selected such that the density integrates to $1$. In fact,

$C_{n}=\frac{\Gamma\left(\frac{n}{2}\right)}{2\pi^{n/2}}\left(\int_{0}^{\infty}r^{n-1}\rho(r)dr\right)^{-1},$

where $\Gamma(z)=\int_{0}^{\infty}x^{z-1}e^{-x}dx$ is the gamma function.

This section derives separation theorems for such distributions. We start with
optimal separation theorem for the most famous example of spherically
invariant distribution, the standard normal one.

###  5.1 Standard normal distribution

For standard normal distribution, the following result is presented in the
conference paper [Grechuk, 2019, Corollary 6].

###### Theorem 12

Let points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ are i.i.d points from
standard normal distribution. For any $\delta>0$, if

$M<\sqrt{\delta}\exp\left(\frac{1}{4}\log(1+\alpha^{2})n\right)=\sqrt{\delta}(1+\alpha^{2})^{n/4},$
(36)

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$\alpha$-Fisher separable with probability greater than $1-\delta$.

Theorem 12 follows from Theorem 7 and estimate

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]\leq(1+\alpha^{2})^{-n/2}$

for i.i.d. points $\boldsymbol{x}$ and $\boldsymbol{y}$ from standard normal
distribution. Here, we derive the _exact_ expression for
${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]$.

From rotation invariance, we may assume that
$\boldsymbol{x}=(||\boldsymbol{x}||,0,0,\dots,0)$. Then

$\begin{split}&{\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]={\mathbb{P}}[\alpha||\boldsymbol{x}||^{2}\leq||\boldsymbol{x}||y_{1}]=\\\
&\;\;\;\;\;{\mathbb{P}}[0<y_{1}]{\mathbb{P}}\left[\frac{||\boldsymbol{x}||}{y_{1}}\leq\frac{1}{\alpha}\right]=\frac{1}{2}{\mathbb{P}}\left[\frac{||\boldsymbol{x}||^{2}/n}{y_{1}^{2}}\leq\frac{1}{n\alpha^{2}}\right],\end{split}$

where $y_{1}$ is the first component of $\boldsymbol{y}$, which follows the
standard normal distribution. The sum of squares of $k$ independent standard
normal random variables follows the chi-squared distribution $\chi(k)$ with
degree $k$. Hence, $\frac{||\boldsymbol{x}||^{2}/n}{y_{1}^{2}}$ is the ratio
of two independent random variables from chi-squared distributions with
degrees $n$ and $1$, respectively, scaled by their degrees. This ratio is
known to follow so-called F-distribution $F(d_{1},d_{2})$ with parameters
$d_{1}=n$ and $d_{2}=1$. The cumulative distribution function of
F-distribution is

$F(x;d_{1},d_{2})=I_{\frac{d_{1}x}{d_{1}x+d_{2}}}\left(\frac{d_{1}}{2},\frac{d_{2}}{2}\right),$

where $I_{z}(a,b)$ is the cumulative distribution function of beta
distribution, also known as regularized incomplete beta function. It is given
by

$I_{z}(a,b)=\frac{B_{z}(a,b)}{B(a,b)},$ (37)

where $B_{z}(a,b)=\int_{0}^{z}t^{a-1}(1-t)^{b-1}dt$ is the incomplete beta
function, and

$B(a,b)=\int_{0}^{1}t^{a-1}(1-t)^{b-1}dt=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$

is the beta function.

Hence,

${\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]=\frac{1}{2}F\left(\frac{1}{n\alpha^{2}};n,1\right)=\frac{1}{2}I_{\frac{1}{1+\alpha^{2}}}\left(\frac{n}{2},\frac{1}{2}\right)$
(38)

With Theorem 7, this implies the following optimal separation result.

###### Theorem 13

Let points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ are i.i.d points from
standard normal distribution. For any $\delta>0$, the expected number of
$\alpha$-inseparable pairs from set
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is less than $\delta$ if
and only if

$M<\frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2\delta}{I_{\frac{1}{1+\alpha^{2}}}\left(\frac{n}{2},\frac{1}{2}\right)}}.$
(39)

In particular, (39) implies that $F$ is $\alpha$-Fisher separable with
probability greater than $1-\delta$.

###### Example 8

Let $\delta=0.01$. Table 6 shows the upper bounds on $M$ in Theorem 13 for
$\alpha=0.6,0.8$ and $1$ in various dimensions $n$.

Table 6:  The upper bound of $M$ (39) that guarantees $\alpha$-Fisher separability of an $M$-element i.i.d. sample from the standard normal distribution with probability $p>0.99$ for various $\alpha$ and dimensions. | $\alpha=0.6$ | $\alpha=0.8$ | $\alpha=1$
---|---|---|---
$n=10$ | $1.19$ | $1.45$ | $1.99$
$n=50$ | $14$ | $164$ | $2075$
$n=100$ | $794$ | $93,806$ | $1.4\cdot 10^{7}$
$n=200$ | $2\cdot 10^{6}$ | $2.6\cdot 10^{10}$ | $5.6\cdot 10^{14}$
$n=500$ | $2.6\cdot 10^{16}$ | $4.2\cdot 10^{26}$ | $2.6\cdot 10^{37}$
$n=1000$ | $1.5\cdot 10^{33}$ | $3.6\cdot 10^{53}$ | $1.3\cdot 10^{75}$

For example, for $n=100$, we see that $14$ millions points from the standard
normal distribution are $1$-Fisher-separable with probability greater than
$99\%$. In dimension $n=200$, millions of points become Fisher separable even
at level $\alpha=0.6$.

The following proposition establishes asymptotic behaviour of (38) as $n$ goes
to infinity.

###### Proposition 5

For every $a>0$, $b\in(0,1)$ and $z\in(0,1)$, we have

$I_{z}(a,b)\leq\frac{z^{a}(1-z)^{b-1}a^{b-1}}{\Gamma(b)},$ (40)

and the bound is asymptotically tight if $b$ and $z$ are fixed but
$a\to\infty$, in sense that ratio of the right and left sides converges to
$1$. In particular,

$\frac{1}{2}I_{\frac{1}{1+\alpha^{2}}}\left(\frac{n}{2},\frac{1}{2}\right)\leq\sqrt{\frac{1+\alpha^{2}}{2\pi
n\alpha^{2}}}(1+\alpha^{2})^{-n/2},$ (41)

and the bound is asymptotically tight if $\alpha$ is fixed and $n\to\infty$.

Proof Wendel [1948] proved that for every $a>0$ and $b\in(0,1)$
$\frac{\Gamma(a+b)}{a^{b}\Gamma(a)}\leq 1,$ and
$\lim\limits_{a\to\infty}\frac{\Gamma(a+b)}{a^{b}\Gamma(a)}=1$. This is
equivalent to

$B(a,b)\geq\Gamma(b)a^{-b}\quad\text{and}\quad\lim\limits_{a\to\infty}\frac{B(a,b)}{\Gamma(b)a^{-b}}=1.$
(42)

Asymptotic expansion [Lopez & Sesma, 1999] implies that

$B_{x}(a,b)\leq\frac{x^{a}(1-x)^{b-1}}{a},$

and $\lim\limits_{a\to\infty}\frac{B_{x}(a,b)a}{x^{a}(1-x)^{b-1}}=1$. Hence,
inequality (40) holds and is asymptotically tight. Applying it with
$z=\frac{1}{1+\alpha^{2}}$, $a=n/2$, $b=1/2$, and using the fact that
$\Gamma(1/2)=\pi$, we get (41). $\Box$

Theorem 13 and Proposition 5 implies the following corollary, which provide a
simple but asymptotically tight estimate for $M$.

###### Corollary 5

Let points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ are i.i.d points from
standard normal distribution. For any $\delta>0$, if

$M<\sqrt[4]{\frac{2\pi
n\alpha^{2}\delta^{2}}{1+\alpha^{2}}}(1+\alpha^{2})^{n/4},$ (43)

then the expected number of $\alpha$-inseparable pairs in set
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is less than $\delta$.
In particular, (43) implies that set $F$ is $\alpha$-Fisher separable with
probability greater than $1-\delta$.

The bound in (43) is weaker than in (39), but the ratio of these bounds
converges to $1$ if $\alpha$ is fixed and $n$ goes to infinity. In particular,
the optimal exponent (19) for standard normal distribution is

$b(\alpha)=\frac{1}{4}\log(1+\alpha^{2}).$

Corollary 5 is an improvement over Theorem 12 if
$n>\frac{1+\alpha^{2}}{2\pi\alpha^{2}}$.

###### Example 9

If $\delta=0.01$, $\alpha=0.9$ and $n=100$, then (36) in Theorem 12 reduces to
$M<276,671$, (43) in Corollary 5 reduces to $M<1,132,950$, while the optimal
bound (39) in Theorem 13 is $M<1,141,060$.

###  5.2 Optimal separation theorem for explicitly given distribution

This section establishes optimal separation theorem if the rotation invariant
distribution is not necessary standard normal but is explicitly given.

###### Proposition 6

Let ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$ be two points selected
independently from spherically invariant distributions with the same center.
Then

$\begin{split}&{\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]=\\\
&\;\;\;\;\;\frac{\alpha}{B(\frac{n-1}{2},\frac{1}{2})}\int_{0}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}{\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]dt,\end{split}$ (44)

where $B(.)$ is the beta function.

Proof Note that

$\begin{split}&{\mathbb{P}}[\alpha(\boldsymbol{x},\boldsymbol{x})\leq(\boldsymbol{x},\boldsymbol{y})]=\\\
&\;\;\;\;\;{\mathbb{P}}[\alpha||\boldsymbol{x}||^{2}\leq||\boldsymbol{x}||\cdot||\boldsymbol{y}||\cos\beta]={\mathbb{P}}\left[\alpha
t\leq\cos\beta\right],\end{split}$

where $t=\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}$, and $\beta$ is an
angle between ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$. By spherical
invariance, the last probability is equal to the ratio of the area of the
hyperspherical cap with angle $\beta_{0}=\arccos(\alpha
t)=\arcsin(\sqrt{1-\alpha^{2}t^{2}})$ to the area of the whole hypersphere,
provided that $t\leq\frac{1}{\alpha}$. By [Li, 2011], this ratio is equal to
$\frac{1}{2}I_{\sin^{2}\beta_{0}}\left(\frac{n-1}{2},\frac{1}{2}\right)$,
where $I_{z}(a,b)$ is given by (37). Hence,

${\mathbb{P}}\left[\alpha
t\leq\cos\beta\right]=\frac{1}{2}\int_{0}^{1/\alpha}I_{1-\alpha^{2}t^{2}}\left(\frac{n-1}{2},\frac{1}{2}\right)u(t)dt,$

where $u$ is the density of the distribution of
$\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}$.

Using the formula for density of beta distribution, we get

$\begin{split}&\frac{d}{dt}I_{1-\alpha^{2}t^{2}}\left(\frac{n-1}{2},\frac{1}{2}\right)=\\\
&\;\;\;\;\;\frac{(1-\alpha^{2}t^{2})^{\frac{n-1}{2}-1}(1-(1-\alpha^{2}t^{2}))^{1/2-1}}{B(\frac{n-1}{2},\frac{1}{2})}\frac{d}{dt}(1-\alpha^{2}t^{2})=\\\
&\;\;\;\;\;\frac{-2\alpha(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}}{B(\frac{n-1}{2},\frac{1}{2})},\end{split}$

where $B(a,b)=\int_{0}^{1}z^{a-1}(1-z)^{b-1}dz$ is the beta function. Hence,
integration by parts yields (44). $\Box$

If ${\boldsymbol{x}}$ has density given by (35), then $||{\boldsymbol{x}}||$
has density given by $C_{n}r^{n-1}\rho(r)$, where
$C_{n}=\left(\int_{0}^{\infty}r^{n-1}\rho(r)dr\right)^{-1}$ is the
normalization constant. Hence,

${\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]=h(n,t):=\frac{\int_{0}^{\infty}y^{n-1}\rho(y)dy\int_{0}^{ty}x^{n-1}\rho(x)dx}{\left(\int_{0}^{\infty}r^{n-1}\rho(r)dr\right)^{2}},$
(45)

where $\rho$ is defined in (35). Hence, Proposition 6 in combination Theorem 7
implies the following optimal separation theorem.

###### Theorem 14

Let $\delta>0$, $\alpha\in(0,1]$, and let
$F=\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from a spherically invariant distribution in ${\mathbb{R}}^{n}$.
Then the expected number of $\alpha$-inseparable pairs from set $F$ is less
than $\delta$ if and only if

$\begin{split}&M<\frac{1}{2}+\sqrt{\frac{1}{4}+\frac{\delta}{p(n,\alpha)}},\\\
&\mbox{where
}p(n,\alpha)=\frac{\alpha}{B(\frac{n-1}{2},\frac{1}{2})}\int_{0}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}h(n,t)dt,\end{split}$
(46)

and $h(n,t)$ is defined in (45). In particular, (46) implies that $F$ is
$\alpha$-Fisher separable with probability greater than $1-\delta$.

We next apply Theorem 14 to some famous rotation invariant distributions.

###  5.3 Uniform distribution in a ball

We may assume that the ball has radius $1$. Uniform distibution in the unit
ball is given by (35) with $\rho(r)=1,0\leq r\leq 1$. Substituting this into
(45) and integrating, we get

$h(n,t)=\begin{cases}t^{n}/2,\quad\quad 0\leq t\leq 1\\\ 1-t^{-n}/2,\quad
1\leq t.\end{cases}$

Hence $p(n,\alpha)$ in (46) is given by:

$\begin{split}p(n,\alpha)=&\frac{\alpha}{2B(\frac{n-1}{2},\frac{1}{2})}\left(\int_{0}^{1}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}t^{n}dt\right.+\\\
&\left.\int_{1}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}(2-t^{-n})dt\right).\end{split}$
(47)

Note that the answer may be written down explicitly using hypergeometric
functions, but we find it more convenient to work with the integral
expression.

With Theorem 14, this implies the following result.

###### Theorem 15

Let $\alpha\in(0,1]$, and let points
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ be i.i.d points from uniform
distribution in a ball. For any $\delta>0$, the expected number of
$\alpha$-inseparable pairs from set
$F=\left\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\right\\}$ is less than
$\delta$ if and only if
$M<\frac{1}{2}+\sqrt{\frac{1}{4}+\frac{\delta}{p(n,\alpha)}},$ where
$p(n,\alpha)$ is given by (47). In particular, in this case $F$ is
$\alpha$-Fisher separable with probability greater than $1-\delta$.

To find the asymptotic growth of (47) as $n\to\infty$, we will use the
Laplace’s method. Informally, it states that, if function $h(t)$ has a unique
maximum on $[a,b]$ attained at $t=c$, and $\phi(c)\neq 0$, then, for large
$n$, the value of integral

$I(n)=\int_{a}^{b}\phi(t)e^{nh(t)}dt$ (48)

depends mainly on $\phi(c)$ and the behaviour of $h(t)$ is the neighbourhood
of $c$. We can then replace in (48) $\phi(t)$ by $\phi(c)$ and $h(t)$ by its
Taylor expansion at $t=c$ up to the first non-zero term, and integrate. We get

$I(n)\sim\phi(c)e^{nh(c)}\sqrt{\frac{2\pi}{n|h^{\prime\prime}(c)|}}$ (49)

if $a<c<b$, $h^{\prime}(c)=0$, $h^{\prime\prime}(c)\neq 0$,

$I(n)\sim\phi(c)e^{nh(c)}\sqrt{\frac{\pi}{2n|h^{\prime\prime}(c)|}}$

if $c=a$ or $c=b$, and $h^{\prime}(c)=0$, $h^{\prime\prime}(c)\neq 0$, and

$I(n)\sim\frac{\phi(c)e^{nh(c)}}{n|h^{\prime}(c)|}$ (50)

if $c=a$ or $c=b$, and $h^{\prime}(c)\neq 0$, we refer to Wong [2001, Theorem
1, p. 58] for a formal statement and proof.

Applying this method to (47), we get the following estimate.

###### Proposition 7

Let $p(n,\alpha)$ be given by (47) and $n>3$.

  * I.

If $0<\alpha<\frac{\sqrt{2}}{2}$, then

$\begin{split}&p(n,\alpha)\leq
q(n,\alpha):=\sqrt{\frac{1}{2\pi}}\frac{1}{\alpha(1-2\alpha^{2})}\frac{n^{3/2}}{(n-3)^{2}}(1-\alpha^{2})^{\frac{n+3}{2}},\\\
&\quad\text{and}\quad p(n,\alpha)\sim q(n,\alpha),\end{split}$ (51)

  * II.

If $\frac{\sqrt{2}}{2}<\alpha\leq 1$, then

$p(n,\alpha)\leq\frac{1}{2}(2\alpha)^{-n},\quad\text{and}\quad
p(n,\alpha)\sim\frac{1}{2}(2\alpha)^{-n}$ (52)

(with equality for $\alpha=1$).

Proof For the coefficient in (47), (42) implies that

$\frac{\alpha}{2B(\frac{n-1}{2},\frac{1}{2})}\leq\frac{\alpha\sqrt{n}}{2\sqrt{2\pi}},\quad\text{and}\quad\frac{\alpha}{2B(\frac{n-1}{2},\frac{1}{2})}\sim\frac{\alpha\sqrt{n}}{2\sqrt{2\pi}}.$
(53)

The first integral
$I_{1}(n):=\int_{0}^{1}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}t^{n}dt$ in (47) can
be written in the form (48) with
$h(t)=\frac{1}{2}\log(1-\alpha^{2}t^{2})+\log(t)$, $n:=n-3$, $\phi(t)=t^{3}$.
If $\frac{\sqrt{2}}{2}<\alpha\leq 1$, $h(t)$ attains maximum on $(0,1]$ at
point $t=c:=\frac{1}{\sqrt{2}a}$, $h(c)=-\log(2\alpha)$, $h^{\prime}(c)=0$,
$h^{\prime\prime}(c)=-8\alpha^{2}$, $\phi(c)=(\sqrt{2}\alpha)^{-3}$, and (49)
implies that

$I_{1}(n)\sim(\sqrt{2}\alpha)^{-3}e^{(n-3)(-\log(2\alpha))}\sqrt{\frac{2\pi}{8(n-3)\alpha^{2}}}\sim\sqrt{\frac{2\pi}{n\alpha^{2}}}(2\alpha)^{-n}.$
(54)

If $0<\alpha<\frac{\sqrt{2}}{2}$, $h(t)$ attains maximum on $(0,1]$ at point
$t=1$, $h(1)=\frac{1}{2}\log(1-\alpha^{2})$,
$h^{\prime}(1)=\frac{1-2\alpha^{2}}{1-\alpha^{2}}$, and inequalities $h(t)\leq
h(1)+h^{\prime}(1)(t-1),\,0<t\leq 1$, $\phi(t)=t^{3}\leq 1,\,0<t\leq 1$ imply
that

$\begin{split}I_{1}(t)\leq&\int_{0}^{1}\exp\left[(n-3)(h(1)+h^{\prime}(1)(t-1))\right]dt=\\\
&\frac{(1-\alpha^{2})^{\frac{n-1}{2}}}{(1-2\alpha^{2})(n-3)}\left(1-\exp\left(-\frac{(1-2\alpha^{2})(n-3)}{1-\alpha^{2}}\right)\right)\leq\\\
&\frac{(1-\alpha^{2})^{\frac{n-1}{2}}}{(1-2\alpha^{2})(n-3)},\end{split}$ (55)

and (50) implies that

$I_{1}(t)\sim\frac{(1-\alpha^{2})^{\frac{n-1}{2}}}{(1-2\alpha^{2})(n-3)}.$
(56)

The second integral
$I_{2}(n):=\int_{1}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}(2-t^{-n})$
in (47) can be estimated similarly. Inequalities
$\frac{1}{2}\log(1-\alpha^{2}t^{2})\leq\frac{1}{2}\log(1-\alpha^{2})-\frac{\alpha^{2}}{1-\alpha^{2}}(t-1)$
and $-\log(t)\geq-(t-1)$ imply that

$\begin{split}&I_{2}(t)\leq\\\
&\int_{1}^{1/\alpha}\\!\\!\\!\exp\left[(n\\!-\\!3)\left(\frac{\log(1-\alpha^{2})}{2}-\frac{\alpha^{2}(t-1)}{1-\alpha^{2}}\right)\right]\left(2-e^{-n(t-1)}\right)dt=\\\
&(1\\!-\\!\alpha^{2})^{\frac{n-1}{2}}\left(\frac{2}{\alpha^{2}(n\\!-\\!3)}\\!-\\!\frac{1}{n\\!-\\!3\alpha^{2}}\\!+\\!\frac{\exp\left(\\!-\frac{n-3\alpha^{2}}{\alpha+\alpha^{2}}\right)}{n-3\alpha^{2}}\\!-\\!\frac{\exp\left(\\!-\frac{\alpha(n-3)}{1+\alpha}\right)}{\alpha^{2}(n-3)}\right)\\!\leq\\\
&(1-\alpha^{2})^{\frac{n-1}{2}}\left(\frac{2}{\alpha^{2}(n-3)}-\frac{1}{n-3\alpha^{2}}\right)\leq(1-\alpha^{2})^{\frac{n-1}{2}}\frac{(2-\alpha^{2})n}{\alpha^{2}(n-3)^{2}},\end{split}$
(57)

where the second inequality follows from the facts that
$n-3\alpha^{2}\geq\alpha^{2}(n-3)$ and
$\exp\left(-\frac{n-3\alpha^{2}}{\alpha+\alpha^{2}}\right)\leq\exp\left(-\frac{\alpha(n-3)}{1+\alpha}\right)$.
Moreover, (50) implies that the first inequality in (57) is asymptotically
tight, and the asymptotic tightness of the second and third inequalities in
(57) is straightforward, hence

$I_{2}(t)\sim(1-\alpha^{2})^{\frac{n-1}{2}}\frac{(2-\alpha^{2})n}{\alpha^{2}(n-3)^{2}}.$
(58)

If $0<\alpha<\frac{\sqrt{2}}{2}$, the combination of (53), (55), and (57)
yields

$\begin{split}&p(n,\alpha)\leq\\\
&\;\;\;\frac{\alpha\sqrt{n}}{2\sqrt{2\pi}}\frac{(1-\alpha^{2})^{\frac{n-1}{2}}n}{(n-3)^{2}}\left(\frac{1}{1-2\alpha^{2}}\frac{n-3}{n}+\frac{2-\alpha^{2}}{\alpha^{2}}\right)\leq
q(n,\alpha),\end{split}$

where the second inequality follows from substituting $1$ instead of
$\frac{n-3}{n}$ and simplifying. The $p(n,\alpha)\sim q(n,\alpha)$ part of
(51) follow from (53), (56), and (58).

The inequality in (52) follows from (17). For $\frac{\sqrt{2}}{2}<\alpha\leq
1$, the $\sim$ part of (52) follows from (53), (54), and (58). $\Box$

We conjecture that factor $\frac{n^{3/2}}{(n-3)^{2}}$ in (51) can be improved
to a simpler factor $\sqrt{n}$, which would allow to remove the condition
$n>3$, but this improvement is negligible for large $n$, and the $\sim$ part
of (51) implies that asymptotically non-negligible improvement is impossible,
and bound (51) is essentially the best possible if
$0<\alpha<\frac{\sqrt{2}}{2}$. Similarly, bound (52) is essentially the best
possible if $\frac{\sqrt{2}}{2}<\alpha\leq 1$.

Theorem 15 and Proposition 7 imply the following corollary.

###### Corollary 6

Let $\alpha\in\left(0,\frac{1}{\sqrt{2}}\right)$, $n>3$, and let
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be the set of $M$ i.i.d
points from uniform distribution in a ball. For any $\delta>0$, if

$M\leq\sqrt[4]{2\pi}\sqrt{\delta\alpha(1-2\alpha^{2})}\frac{n-3}{n^{3/4}}\left(\frac{1}{1-\alpha^{2}}\right)^{\frac{n+3}{4}},$
(59)

then the expected number of $\alpha$-inseparable pairs in $F$ is less than
$\delta$. In particular, (59) implies that $F$ is $\alpha$-Fisher separable
with probability greater than $1-\delta$.

Proposition 7 implies that the bound for $M$ in Corollary 6 is asymptotically
tight, and has the advantage of being a simple explicit formula. For
$\alpha\geq\frac{1}{\sqrt{2}}$, (52) implies that an asymptotically tight
bound is given in Theorem 2.

###### Example 10

Let $\delta=0.01$. Table 7 shows the upper bounds on $M$ in Corollary 6 for
$\alpha=0.5,0.6$ and $0.7$ in various dimensions $n$.

Table 7:  The upper bound of $M$ (59) that guarantees $\alpha$-Fisher separability with probability $p>0.99$ of $M$ i.i.d. points sampled from uniform distribution in a ball, for various $\alpha$ and dimensions. | $\alpha=0.5$ | $\alpha=0.6$ | $\alpha=0.7$
---|---|---|---
$n=10$ | $0.25$ | $0.34$ | $0.2$
$n=50$ | $8.9$ | $60$ | $350$
$n=100$ | $400$ | $19,491$ | $1.9\cdot 10^{6}$
$n=200$ | $642,645$ | $1.6\cdot 10^{9}$ | $4.8\cdot 10^{13}$
$n=500$ | $1.9\cdot 10^{15}$ | $7.1\cdot 10^{23}$ | $5.2\cdot 10^{35}$
$n=1000$ | $9.4\cdot 10^{30}$ | $1.4\cdot 10^{48}$ | $2.2\cdot 10^{72}$

For example, for $n=200$, we see that $642,645$ points from the uniform
distribution in the unit ball are Fisher-separable at level $\alpha=0.5$ with
probability greater than $99\%$. For comparison, with the same parameters, the
bound (7) in Theorem 2 reduces to $M<0.14$. The optimal bound in Theorem 15
gives $M<661,243$.

The results of this section can be straightforwardly extended to the case when
the points in ${\mathbb{R}}^{n}$ are selected from the uniform distribution in
a spherical layer, that is, from the distribution (35) with

$\rho(r)=\begin{cases}\frac{1}{1-R},\quad R\leq r\leq 1,\\\
0,\quad\quad\text{otherwise},\end{cases}$

where $R\in(0,1)$ is a parameter. Then $h(n,t)$ in (45) is given by

$h(n,t)=\begin{cases}0,\quad\quad\quad\quad\quad\quad t\leq R\\\
\frac{t^{-n}(R^{n}-t^{n})^{2}}{2(1-R^{n})^{2}},\quad\quad\,\,\,\,\,R<t\leq
1,\\\ 1-\frac{t^{n}(R^{n}-t^{-n})^{2}}{2(1-R^{n})^{2}},\quad\,\,1\leq
t<1/R,\\\ 1,\quad\quad\quad\quad\quad\quad 1/R<t.\end{cases}$ (60)

With Theorem 14, this implies that if $M$ i.i.d. points are selected from this
distribution, then the expected number of $\alpha$-inseparable pairs is less
than $\delta$ if and only if

$M<\frac{1}{2}+\sqrt{\frac{1}{4}+\frac{\delta}{p(n,\alpha)}},$

where $p(n,\alpha)$ is given by (46) with $h(n,t)$ given by (60).

Some (weaker) estimates for spherical layer were received earlier by Sidorov &
Zolotykh [2020].

###  5.4 Multivariate exponential distribution

By multivariate exponential distribution in ${\mathbb{R}}^{n}$ we will mean
rotation invariant distribution such that $\rho(||{\boldsymbol{x}}||)$ in (35)
is equal to $\exp(-||{\boldsymbol{x}}||)$. In this case, the distribution of
$||{\boldsymbol{x}}||$ is the standard Gamma distribution with $n$ degrees of
freedom, and, for i.i.d. ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$, ratio
$\frac{{\boldsymbol{x}}}{{\boldsymbol{y}}}$ follows beta prime distribution,
that is,

${\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]=I_{\frac{t}{1+t}}(n,n),$

where $I_{z}(a,b)$ is the regularized incomplete beta function defined in
(37). Hence, Theorem 14 implies the following result.

###### Theorem 16

Let $\alpha\in(0,1]$, and let points
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ be i.i.d points from exponential
distribution in ${\mathbb{R}}^{n}$. For any $\delta>0$, the expected number of
$\alpha$-inseparable pairs from set
$F=\left\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\right\\}$ is less than
$\delta$ if and only if

$\begin{split}&M<\frac{1}{2}+\sqrt{\frac{1}{4}+\frac{\delta}{p(n,\alpha)}},\\\
&\mbox{where
}p(n,\alpha)=\frac{\alpha}{B(\frac{n-1}{2},\frac{1}{2})}\int_{0}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}I_{\frac{t}{1+t}}(n,n)dt.\end{split}$
(61)

In particular, (61) implies that $F$ is $\alpha$-Fisher separable with
probability greater than $1-\delta$.

###### Example 11

Let $\delta=0.01$. Table 8 shows the upper bounds on $M$ in Theorem 16 for
$\alpha=0.6,0.8$ and $1$ in various dimensions $n$.

Table 8:  The upper bounds on $M$ (61) that guarantees $\alpha$-Fisher separability of $M$ i.i.d. points from exponential distribution with probability $p>0.99$ for various $\alpha$ and dimensions. | $\alpha=0.6$ | $\alpha=0.8$ | $\alpha=1$
---|---|---|---
$n=10$ | $0.65$ | $0.81$ | $1.06$
$n=50$ | $7.6$ | $43$ | $249$
$n=100$ | $218$ | $6,662$ | $203,805$
$n=200$ | $154,501$ | $1.3\cdot 10^{8}$ | $1.1\cdot 10^{11}$
$n=500$ | $4.1\cdot 10^{13}$ | $7.6\cdot 10^{20}$ | $1.6\cdot 10^{28}$
$n=1000$ | $3.8\cdot 10^{27}$ | $1.1\cdot 10^{42}$ | $4.8\cdot 10^{56}$

For example, for $n=100$, we see that over $200,000$ points from the
multivariate exponential distribution are Fisher-separable at level $\alpha=1$
with probability greater than $99\%$. In dimension $n=200$, over $150,000$
points from the same distribution become Fisher-separable at level
$\alpha=0.6$.

The growth of factor $I_{\frac{t}{1+t}}(n,n)$ in (61) is described by the
following proposition.

###### Proposition 8

For any $t>0$ and $n\geq 1$,

$I_{\frac{t}{1+t}}(n,n)=\begin{cases}\frac{1}{2}I_{\frac{4t}{(1+t)^{2}}}(n,\frac{1}{2}),\quad
0<t\leq 1,\\\ 1-\frac{1}{2}I_{\frac{4t}{(1+t)^{2}}}(n,\frac{1}{2}),1\leq
t.\end{cases}$ (62)

In particular,

$I_{\frac{t}{1+t}}(n,n)\leq\frac{1}{2\sqrt{\pi
n}}\frac{1+t}{1-t}\left(\frac{4t}{(1+t)^{2}}\right)^{n},\quad 0<t<1,$ (63)

and this upper bound is asymptotically tight if $t$ is fixed and $n\to\infty$.

Proof If $0<t\leq 1$, then $z=\frac{t}{1+t}\leq\frac{1}{2}$, and

$\begin{split}B_{z}(n,n)=&\int_{0}^{z}u^{n-1}(1-u)^{n-1}du=\\\
&\int_{0}^{4z(1-z)}(s/4)^{n-1}\frac{ds}{4\sqrt{1-s}}=4^{-n}B_{4z(1-z)}\left(n,\frac{1}{2}\right),\end{split}$

where the second inequality is the change of variables $s=4u(1-u)$. Next,

$\begin{split}B(n,n)=&\int_{0}^{1}u^{n-1}(1-n)^{n-1}dt=\\\
&2\int_{0}^{1/2}u^{n-1}(1-n)^{n-1}dt=2B_{\frac{1}{2}}(n,n)=4^{-n}B\left(n,\frac{1}{2}\right),\end{split}$

hence

$I_{z}(n,n)=\frac{B_{z}(n,n)}{B(n,n)}=\frac{4^{-n}B_{4z(1-z)}\left(n,\frac{1}{2}\right)}{4^{-n}B\left(n,\frac{1}{2}\right)}=I_{4z(1-z)}\left(n,\frac{1}{2}\right),$

which with $z=\frac{t}{1+t}$ implies the first line of (62). The second line
follows from the first one and the identity $I_{z}(a,b)=1-I_{1-x}(b,a)$.

For $0<t<1$, (40) with $a=n$, $b=1/2$, and $z=\frac{4t}{(1+t)^{2}}$ implies
that

$\begin{split}&I_{\frac{t}{1+t}}(n,n)=\frac{1}{2}I_{\frac{4t}{(1+t)^{2}}}(n,\frac{1}{2})\leq\\\
&\;\;\;\;\;\left(\frac{4t}{(1+t)^{2}}\right)^{n}\left(1-\frac{4t}{(1+t)^{2}}\right)^{-1/2}\frac{n^{-1/2}}{2\Gamma(1/2)},\end{split}$

which simplifies to the right-hand side of (63). $\Box$

The next proposition establishes asymptotic growth of $p(n,\alpha)$ in (61) as
$n\to\infty$.

###### Proposition 9

Let $p(n,\alpha)$ be given by (61). Then

$\begin{split}&p(n,\alpha)\sim\\\
&\frac{\sqrt{1+5\alpha^{2}+(1+\alpha^{2})\sqrt{1+8\alpha^{2}}}}{2\alpha\sqrt{\pi
n}\sqrt[4]{1+8\alpha^{2}}}\left(\frac{4\sqrt{2}\alpha(\sqrt{1+8\alpha^{2}}-1)}{(\sqrt{1+8\alpha^{2}}+4\alpha^{2}-1)^{3/2}}\right)^{n}.\end{split}$
(64)

Proof Proposition 8 together with obvious bound $I_{\frac{t}{1+t}}(n,n)\leq 1$
implies that the integral in (61) is bounded by

$I_{n}:=\int_{0}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}I_{\frac{t}{1+t}}(n,n)dt\leq
J_{n}+L_{n},$ (65)

where

$\begin{split}&J_{n}:=\int_{0}^{1}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}\min\left\\{\frac{1}{2\sqrt{\pi
n}}\frac{1+t}{1-t}\left(\frac{4t}{(1+t)^{2}}\right)^{n},1\right\\}dt,\\\
&L_{n}:=\int_{1}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}dt.\end{split}$

Because for $n\geq 3$ we have $J_{n}\leq 1$ and $L_{n}\leq\frac{1}{\alpha}-1$,
and (63) is asymptotically tight, (65) is also asymptotically tight by
dominated convergence theorem.

Integral $J_{n}$ can be written in the form (48) with

$\phi_{n}(t):=(1-\alpha^{2}t^{2})^{-3/2}\min\left\\{\frac{1}{2\sqrt{\pi
n}}\frac{1+t}{1-t},\left(\frac{(1+t)^{2}}{4t}\right)^{n}\right\\}$

and

$h(t):=\log\left(\sqrt{1-\alpha^{2}t^{2}}\frac{4t}{(1+t)^{2}}\right).$

Function $h(t)$ attains maximum on $(0,1)$ at

$t_{0}=t_{0}(a):=\frac{\sqrt{1+8a^{2}}-1}{4a^{2}}$

and by (49)

$\begin{split}J_{n}\sim&\phi_{n}(t_{0})\sqrt{\frac{2\pi}{n|h^{\prime\prime}(t_{0})|}}e^{nh(t_{0})}\sim\\\
&(1-\alpha^{2}t_{0}^{2})^{-3/2}\frac{1}{n}\frac{1+t_{0}}{1-t_{0}}\sqrt{\frac{1}{2|h^{\prime\prime}(t_{0})|}}e^{nh(t_{0})},\end{split}$

where the second $\sim$ follows from the fact that $\frac{1}{2\sqrt{\pi
n}}\frac{1+t_{0}}{1-t_{0}}<\left(\frac{(1+t_{0})^{2}}{4t_{0}}\right)^{n}$ for
large $n$.

Similarly, by (50)

$L_{n}\sim\frac{1-\alpha^{2}}{n\alpha^{2}}\left(\sqrt{1-\alpha^{2}}\right)^{(n-3)}.$

Because $e^{h(t_{0})}>\sqrt{1-\alpha^{2}}$ for all $0<\alpha\leq 1$,
$I_{n}\sim J_{n}+L_{n}\sim J_{n}$ as $n\to\infty$. This together with (61) and
(53) implies that

$p(n,\alpha)\sim\frac{\alpha\sqrt{n}}{\sqrt{2\pi}}(1-\alpha^{2}t_{0}^{2})^{-3/2}\frac{1}{n}\frac{1+t_{0}}{1-t_{0}}\sqrt{\frac{1}{2|h^{\prime\prime}(t_{0})|}}e^{nh(t_{0})},$

which simplifies to (64). $\Box$

For $\alpha=1$, Theorem 16 and Proposition 9 imply the following corollary.

###### Corollary 7

Let points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ are i.i.d points from
exponential distribution in ${\mathbb{R}}^{n}$. For any $\delta>0$, if

$M<\sqrt{\frac{\delta}{p(n,1)}}\sim\sqrt{\delta}\sqrt[4]{\pi
n}\left(\frac{\sqrt[4]{27}}{2}\right)^{n},$

then the expected number of $1$-inseparable pairs in set
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is less than $\delta$.
In particular, set $F$ is $1$-Fisher separable with probability greater than
$1-\delta$.

In particular,

$b(1)=\log\left(\frac{\sqrt[4]{27}}{2}\right)=0.1308...,$

where $b(\alpha)$ is defined in (19). For comparison, for uniform distribution
in a ball $b(1)=\frac{1}{2}\log 2=0.3465...$, while for standard normal
distribution $b(1)=\frac{1}{4}\log 2=0.1732...$.

###  5.5 General log-concave spherically invariant distribution

This section derives separation theorems for arbitrary spherically invariant
distribution. We start with the following easy result.

###### Theorem 17

Let $\delta>0$, $\alpha\in(1/2,1]$, and let
$\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from a spherically invariant log-concave distribution in
${\mathbb{R}}^{n}$. If

$M<\sqrt{\frac{\delta}{2}}\exp\left(n\frac{(2\alpha-1)^{2}}{8(2\alpha+1)^{2}}\right),$
(66)

then the expected number of $\alpha$-inseparable pairs in set
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is less than $\delta$.
In particular, set $F$ is $\alpha$-Fisher separable with probability greater
than $1-\delta$.

Proof Let ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$ be two i.i.d points from
the given distribution. Inequality (4) can be rewritten as

$\left\|{\boldsymbol{x}}-\frac{{\boldsymbol{y}}}{2\alpha}\right\|\leq\left\|\frac{{\boldsymbol{y}}}{2\alpha}\right\|,$

that is, ${\boldsymbol{x}}$ belongs to a ball of radius
$\left\|\frac{{\boldsymbol{y}}}{2\alpha}\right\|$. For every fixed $t>0$, this
may happen if either

  * (i)

$||{\boldsymbol{y}}||>t$, or

  * (ii)

${\boldsymbol{x}}$ belongs to a ball of radius at most $\frac{t}{2\alpha}$.

We will prove that, for $t=\frac{4\alpha}{2\alpha+1}\mu$, where
$\mu={\mathbb{E}}[||{\boldsymbol{x}}||]={\mathbb{E}}[||{\boldsymbol{y}}||]$,
both these possibilities can happen with probability at most
$e^{-n\frac{(2\alpha-1)^{2}}{4(2\alpha+1)^{2}}}$. With (16), this will imply
(66).

As observed by Bobkov [2010, p. 328], if random variable ${\boldsymbol{x}}$
has density given by (35) with log-concave $\rho$, then $||{\boldsymbol{x}}||$
has log-concave distribution of order $n$ (that is, has density of the form
$q(r)=r^{n-1}\rho(r)$ for log-concave $\rho$). According to Bobkov [2010,
Corollary 3.2], this implies that, for any $h\in[0.1]$,

${\mathbb{P}}[||{\boldsymbol{x}}||-\mu\geq h\mu]\leq e^{-nh^{2}/4}$ (67)

and

${\mathbb{P}}[\mu-||{\boldsymbol{x}}||\geq h\mu]\leq e^{-nh^{2}/4}.$ (68)

With $h=\frac{2\alpha-1}{2\alpha+1}$, (67) implies that probability of (i) is
at most $e^{-n\frac{(2\alpha-1)^{2}}{4(2\alpha+1)^{2}}}$, while (68) implies
that

${\mathbb{P}}\left[||{\boldsymbol{x}}||\leq\frac{2}{2\alpha+1}\mu\right]\leq
e^{-n\frac{(2\alpha-1)^{2}}{4(2\alpha+1)^{2}}}.$

In other words, the probability that ${\boldsymbol{x}}$ belongs to a ball $B$
of radius $\frac{t}{2\alpha}$ centred at origin is at most
$e^{-n\frac{(2\alpha-1)^{2}}{4(2\alpha+1)^{2}}}$. However, because the density
$\hat{\rho}$ is spherically invariant and log-concave, we have
$\hat{\rho}(x)\geq\hat{\rho}(y)$ for every $x\in B$ and $y\not\in B$, hence
shifting the ball cannot increase the probability for a point to belong to it.
$\Box$

The bound (66) in Theorem 17 is simple and explicit. For example, for
$\alpha=1$ it reduces to

$M<\sqrt{\frac{\delta}{2}}\exp\left(\frac{n}{72}\right).$ (69)

However, the bound is far from being optimal, and the Theorem is not
applicable for $\alpha\leq\frac{1}{2}$. We next prove a separation theorem
with more complicated but better bound. It also applies to a broader class of
distributions, because it does not requires for $\rho$ in (35) to be non-
increasing.

###### Theorem 18

Let $\delta>0$, $\alpha\in(0,1]$, and let
$F=\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{M}\\}$ be a set of $M$ i.i.d.
random points from a distribution in ${\mathbb{R}}^{n}$ given by (35) with
log-concave $\rho$. If

$M<\sqrt{\delta}f(n,\alpha)^{-1/2},$ (70)

where $f(n,\alpha)$ is an explicit function defined in formulas (71)-(73)
below, then the expected number of $\alpha$-inseparable pairs in set
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is less than $\delta$.
In particular, (70) implies that set $F$ is $\alpha$-Fisher separable with
probability greater than $1-\delta$.

Proof Let ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$ be any i.i.d. points from
the given distribution. Let us derive an upper bound for
${\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]$ for any $t\in(0,1/\alpha)$. Let $q(.)$ be the density for absolute
value distribution. We have

$\begin{split}{\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]=&\int_{0}^{\infty}q(x)dx\int_{x/t}^{\infty}q(y)dy=\\\
&\int_{0}^{\infty}q(x)dx\cdot{\mathbb{P}}\left[||{\boldsymbol{y}}||\geq\frac{x}{t}\right].\end{split}$

We claim that

${\mathbb{P}}\left[||{\boldsymbol{y}}||\geq\frac{x}{t}\right]\leq\psi_{n,t}(x):=\begin{cases}1,\quad
x\leq t,\\\ \exp\left(-\frac{n(x-t)^{2}}{4t^{2}}\right),\quad t\leq x\leq
2t\\\ \exp\left(-\frac{nx}{8t}\right),\quad 2t\leq x.\end{cases}$ (71)

Indeed, the first line in (71) is trivial. If $t\leq x\leq 2t$, then, applying
(67) with $\mu=1$ and $h=\frac{x-t}{t}$, we get the second line in (71).
Further, equation (3.9) in the cited work [Bobkov, 2010] states that

${\mathbb{P}}\left[||{\boldsymbol{y}}||\geq
h\mu\right]\leq\exp\left(-\frac{nh}{8}\right),\quad h\geq 2.$

Applying this with $\mu=1$ and $h=\frac{x}{t}$, we get the third line in (71).
With (71),

$\begin{split}{\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]\leq&\int_{0}^{\infty}q(x)\psi_{n,t}(x)dx=\\\
&\int_{0}^{\infty}{\mathbb{P}}[||{\boldsymbol{x}}||\leq
x](-\psi^{\prime}_{n,t}(x))dx,\end{split}$

where the last equality is integration by parts. Because $\psi_{n,t}(x)$ is
non-increasing, $-\psi^{\prime}_{n,t}(x)$ is non-negative, and
${\mathbb{P}}[||{\boldsymbol{x}}||\leq x]$ can be bounded by

${\mathbb{P}}[||{\boldsymbol{x}}||\leq x]\leq
g_{n}(x):=\begin{cases}\exp\left(-\frac{n(1-x)^{2}}{4}\right),\quad x\leq
1,\\\ 1,\quad x\geq 1,\end{cases}$ (72)

where the first line in (72) follows from (68) with $\mu=1$ and $h=1-x$.
Hence,

${\mathbb{P}}\left[\frac{||{\boldsymbol{x}}||}{||{\boldsymbol{y}}||}\leq
t\right]\leq\phi(t,n):=\int_{0}^{\infty}g_{n}(x)(-\psi^{\prime}_{n,t}(x))dx.$

Applying this bound to (44), we get

$p\leq
f(n,\alpha):=\frac{\alpha}{B(\frac{n-1}{2},\frac{1}{2})}\int_{0}^{1/\alpha}(1-\alpha^{2}t^{2})^{\frac{n-3}{2}}\phi(t,n)dt,$
(73)

and (70) follows from (16). $\Box$

The function $f(n,\alpha)$ in (70) is complicated but explicit and, for any
specific values of $n$ and $\alpha$, can be easily computed in any package
like Mathematica. In particular, we verified in Mathematica that

$\frac{-\log f(n,1)}{n}\geq 0.14,\quad 1\ \leq n\leq 4000.$

This together with Theorem 18 implies the following Corollary.

###### Corollary 8

Let $\delta>0$, and let $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$
be a set of $M$ i.i.d. random points from a distribution in ${\mathbb{R}}^{n}$
given by (35) with log-concave $\rho$. If $1\leq n\leq 4000$ and

$M<\sqrt{\delta}\exp\left(0.07n\right)$ (74)

then the expected number of $1$-inseparable pairs in set $F$ is less than
$\delta$. In particular, (74) implies that set $F$ is $1$-Fisher separable
with probability greater than $1-\delta$.

If $n>4000$, then we can use (69) and get the bound much higher than needed
for any practical purposes. However, for smaller $n$, Corollary 8 is a
significant improvement comparing to (69).

###### Example 12

Let $\alpha=1$ and $\delta=0.01$.

  * (a)

If $n=4001$, then (69) reduces to $M<96,158,590,065,160,622,896,817$;

  * (b)

If $n=400$, then (69) reduces to $M\leq 18$, while (74) reduces to $M\leq
144,625,706,429$;

  * (c)

If $n=200$, (74) still gives a reasonable bound $M\leq 120,260$.

###### Example 13

Let $\alpha=1$ and $\delta=0.01$. Table 9 shows the upper bounds on $M$ in
Corollary 8 in various dimensions $n$.

Table 9:  The upper bounds on $M$ in Corollary 8 in various dimensions $n$ for $\alpha=1$ and $\delta=0.01$. $n$ | $M\leq$
---|---
$10$ | $0.2$
$50$ | $3.3$
$100$ | $109$
$200$ | $120,260$
$500$ | $1.5\cdot 10^{14}$
$1000$ | $2.5\cdot 10^{29}$

Corollary 7 demonstrates that constant $0.07$ in Corollary 8 is within a
factor less than $2$ from being optimal.

##  6 Improved bounds for product distributions in the unit cube

###  6.1 The general case

In this section we assume the following.

  * (a)

all points in a finite set $F$ are chosen independently;

  * (b)

points in $F$ are not necessary identically distributed, but have the same
mean $\boldsymbol{\mu}=(\mu_{1},\dots,\mu_{n})\in{\mathbb{R}}^{n}$;

  * (c)

for each $\boldsymbol{x}=(x_{1},\dots,x_{n})\in F$, components
$x_{1},\dots,x_{n}$ are independent and have $[0,1]$ support;

  * (d)

there are no point $\boldsymbol{x}\in F$ such that
${\mathbb{P}}[\boldsymbol{x}=\boldsymbol{\mu}]=1$.

From (c), $F$ is a subset of the unit cube $U_{n}=[0,1]^{n}$. From (b),
$E[x_{i}]=\mu_{i}$ for all $i=1,\dots,n$ and for all $\boldsymbol{x}\in F$.
Let

$\sigma_{0}^{2}=\min_{\boldsymbol{x}\in
F}\left(\frac{1}{n}\sum_{i=1}^{n}Var[x_{i}]\right),$

that is, the minimal value of average variance of the components. From (d),
$\sigma_{0}^{2}>0$.

Fix any point $\boldsymbol{c}=(c_{1},\dots,c_{n})\in U_{n}$, and any pair
$\boldsymbol{x},\boldsymbol{y}\in F$. Let

$z_{i}=(x_{i}-c_{i})(y_{i}-c_{i})-\alpha(x_{i}-c_{i})^{2},\quad i=1,\dots,n.$
(75)

Inequality (13) reduces to

${\mathbb{P}}\left[\sum_{i=1}^{n}z_{i}\geq 0\right]\leq f(n,\alpha).$

From (a) and (c) it follows that all random variables $z_{i}$ are independent.
Next,

$E[z_{i}]=E[(x_{i}-c_{i})(y_{i}-c_{i})]-\alpha E[(x_{i}-c_{i})^{2}].$

By independence,
$E[(x_{i}-c_{i})(y_{i}-c_{i})]=E[(x_{i}-c_{i})]E[(y_{i}-c_{i})]=(\mu_{i}-c_{i})^{2}$,
and $E[z_{i}]=(\mu_{i}-c_{i})^{2}-\alpha
E[(x_{i}-c_{i})^{2}]=(1-\alpha)(\mu_{i}-c_{i})^{2}-\alpha Var[x_{i}-c_{i}].$
Hence,

$E\left[\sum_{i=1}^{n}z_{i}\right]=(1-\alpha)\sum_{i=1}^{n}(\mu_{i}-c_{i})^{2}-\alpha\sum_{i=1}^{n}Var[x_{i}]\leq$
$\leq(1-\alpha)\sum_{i=1}^{n}(\mu_{i}-c_{i})^{2}-n\alpha\sigma_{0}^{2}=-nt,$

where

$t:=\alpha\sigma_{0}^{2}-(1-\alpha)\frac{1}{n}\sum_{i=1}^{n}(\mu_{i}-c_{i})^{2}.$
(76)

Note that $t$ is guaranteed to be positive if either (i) $\alpha$ is
sufficiently close to $1$, or (ii) $\boldsymbol{c}=\boldsymbol{\mu}$.

The following Proposition established bounds on $z_{i}$.

###### Proposition 10

Let $c^{\prime}_{i}:=\max\\{c_{i},1-c_{i}\\}$ for all $i$, and
$f(c):=-c+c^{2}(1-\alpha)$.

  * (i)

if $\alpha\geq 0.5$, then

$-c^{\prime}_{i}+(c^{\prime}_{i})^{2}(1-\alpha)\leq
z_{i}\leq\frac{(c^{\prime}_{i})^{2}}{4\alpha}.$

In particular, $-\alpha\leq z_{i}\leq\frac{1}{4\alpha}$ for all $i$;

  * (ii)

if $\alpha\leq 0.5$, then

$\min\\{f(c_{i}),f(1-c_{i})\\}\leq z_{i}\leq(1-\alpha)(c^{\prime}_{i})^{2}.$

In particular, $-\frac{1}{4(1-\alpha)}\leq z_{i}\leq 1-\alpha$ for all $i$;

  * (iii)

if $c_{i}=\frac{1}{2}$ for all $i$, then
$-\frac{1}{2}+\frac{1}{4}(1-\alpha)\leq z_{i}\leq\frac{1}{16\alpha}$ for all
$i$ if $\alpha\geq 0.5$ and $-\frac{1}{2}+\frac{1}{4}(1-\alpha)\leq
z_{i}\leq\frac{1}{4}(1-\alpha)$ for all $i$ if $\alpha\leq 0.5$.

Proof For each fixed $c_{i}$ and $y_{i}$, $z_{i}$ in (75) is maximized if
$x_{i}=\frac{y_{i}-c_{i}}{2\alpha}+c_{i}$, resulting in
$z_{i}=\frac{(y_{i}-c_{i})^{2}}{4\alpha}$. The last expression is maximized if
$y_{i}$ is either $0$ or $1$, with maximum equal to
$\frac{(c^{\prime}_{i})^{2}}{4\alpha}$. This bound is tight if $\alpha\geq
0.5$. If $\alpha<0.5$, then critical point $\frac{y_{i}-c_{i}}{2\alpha}+c_{i}$
lies outside of $[0,1]$ and (75) is maximized if $x_{i}$ is either $0$ or $1$,
resulting in bound $(1-\alpha)(c^{\prime}_{i})^{2}$.

Similarly, $z_{i}$ in (75) is minimized when either $x_{i}=1$ and $y_{i}=0$ or
vice versa, resulting in bound $\min\\{f(c_{i}),f(1-c_{i})\\}\leq z_{i}$.
Because $f(c)\geq-\frac{1}{4(1-\alpha)}$ for all $c$, bound
$-\frac{1}{4(1-\alpha)}\leq z_{i}$ follows. If $\alpha\geq 0.5$, then $f$ is
monotone decreasing on $[0,1]$, hence
$\min\\{f(c_{i}),f(1-c_{i})\\}=f(c^{\prime}_{i})=-c^{\prime}_{i}+(c^{\prime}_{i})^{2}(1-\alpha)\geq
f(1)=-\alpha$. $\Box$

Let $S_{n}=\sum_{i=1}^{n}z_{i}$. By Hoeffding’s inequality [Hoeffding, 1963],
[Boucheron, 2013, Theorem 2.8],

${\mathbb{P}}[S_{n}\geq 0]\leq{\mathbb{P}}[S_{n}-E[S_{n}]\geq
nt]\leq\exp\left(-\frac{2n^{2}t^{2}}{\sum\limits_{i=1}^{n}(b_{i}-a_{i})^{2}}\right),$

provided that $t>0$, where $[a_{i},b_{i}]$ is the support of random variable
$z_{i}$. Applying Proposition 10 to bound $b_{i}-a_{i}$, we get the following
result.

###### Theorem 19

Assume that (a)-(d) hold. Let $\delta>0$, $\alpha\in(0,1]$, and let
$\boldsymbol{c}$ be an arbitrary point inside unit cube $[0,1]^{n}$ such that
$t$ in (76) is positive. Let $c^{\prime}_{i}:=\max\\{c_{i},1-c_{i}\\}$ and
$g(c):=\min\\{-c+c^{2}(1-\alpha),-(1-c)+(1-c)^{2}(1-\alpha)\\}$. If
$\alpha\geq 0.5$ and

$M<\sqrt{\delta}\exp\left(\frac{n^{2}t^{2}}{\sum_{i=1}^{n}\left(c^{\prime}_{i}-(c^{\prime}_{i})^{2}(1-\alpha)+\frac{(c^{\prime}_{i})^{2}}{4\alpha}\right)^{2}}\right),$

or $\alpha\leq 0.5$ and

$M<\sqrt{\delta}\exp\left(\frac{n^{2}t^{2}}{\sum_{i=1}^{n}\left((1-\alpha)(c^{\prime}_{i})^{2}-g(c_{i})\right)^{2}}\right),$

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(\alpha,\boldsymbol{c})$-Fisher separable with probability greater than
$1-\delta$.

For $\alpha=1$, we get the following corollary

###### Corollary 9

Assume that (a)-(d) hold. Let $\delta>0$, and let $\boldsymbol{c}$ be an
arbitrary point inside unit cube $[0,1]^{n}$. If

$M<\sqrt{\delta}\exp\left(\frac{16}{25}n\sigma_{0}^{4}\right),$ (77)

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(1,\boldsymbol{c})$-Fisher separable with probability greater than
$1-\delta$.

###### Example 14

With $\delta=0.01$, $n=500$, and $\sigma_{0}=0.5$, (same values as in Example
6) (77) reduces to $M<48,516,519$.

By selecting $\boldsymbol{c}$ being the center of the cube, we can improve the
bound further.

###### Corollary 10

Assume that (a)-(d) hold. Let $\delta>0$, and let
$\boldsymbol{c}=(\frac{1}{2},\dots,\frac{1}{2})$ be the center of unit cube
$[0,1]^{n}$. If

$M<\sqrt{\delta}\exp\left(\frac{256}{81}n\sigma_{0}^{4}\right),$ (78)

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(1,\boldsymbol{c})$-Fisher separable with probability greater than
$1-\delta$.

In contrast to (77), bound (78) may be practical in dimension $n=100$.

###### Example 15

If $\delta=0.01$ and $n=100$, then, even with maximal possible
$\sigma_{0}=0.5$, (77) reduces to $M<5.5$. In contrast, (78) with these
parameters gives $M<37,901,503$.

In lager dimensions, bound (78) may be practical for (slightly) lower
$\sigma_{0}$.

###### Example 16

If $\delta=0.01$, and $\sigma_{0}=\frac{1}{2\sqrt{3}}$ (standard deviation of
uniform distribution on $[0,1]$), then, even with $n=1000$, (77) reduces to
$M<8.5$. In contrast, (78) with these parameters gives $M<340,283,178$.

If $\alpha<1$, it is convenient to apply Theorem 19 with
$\boldsymbol{c}=\boldsymbol{\mu}$. In this case $t$ in (76) is guaranteed to
be positive, and bounds in Proposition 10 (i),(ii) imply the following result.

###### Corollary 11

Assume that (a)-(d) hold. Let $\delta>0$, $\alpha\in(0,1]$. If

$M<\sqrt{\delta}\exp\left(\frac{16\alpha^{4}}{(1+4\alpha^{2})^{2}}n\sigma_{0}^{4}\right),\quad\alpha\geq
0.5,$

or

$M<\sqrt{\delta}\exp\left(\frac{16(1-\alpha)^{2}\alpha^{2}}{(1+4(1-\alpha)^{2})^{2}}n\sigma_{0}^{4}\right),\quad\alpha\leq
0.5,$

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(\alpha,\boldsymbol{\mu})$-Fisher separable with probability greater than
$1-\delta$.

###### Example 17

With $\delta=0.01$, $n=500$, and $\sigma_{0}=0.5$, and $\alpha=0.9$, Corollary
11 is applicable if $M<8,411,607$.

###  6.2 The mean-centered distributions

In this section we consider a special case when
$\boldsymbol{\mu}=(\frac{1}{2},\dots,\frac{1}{2})$ is the center of the unit
cube. In this case, Theorem 19 with Proposition 10 (iii) implies that set $F$
is $(\alpha,\boldsymbol{\mu})$-Fisher separable with probability greater than
$1-\delta$ provided that

$M<\sqrt{\delta}\exp\left(\frac{256\alpha^{4}}{(1+2\alpha)^{4}}n\sigma_{0}^{4}\right),\quad\alpha\geq
0.5,$ (79)

or

$M<\sqrt{\delta}\exp\left(4\alpha^{2}n\sigma_{0}^{4}\right),\quad\alpha\leq
0.5.$

With $\alpha=1$, (79) reduces to (78). It is practical if $\sigma_{0}$ is
close to its maximal value $0.5$, but, because of factor $\sigma_{0}^{4}$,
quickly becomes useless if $\sigma_{0}$ decreases.

###### Example 18

If $\delta=0.01$, and $\sigma_{0}=0.2$, then, even with $n=1000$, (78) reduces
to $M<15.7$.

The theorem below uses Bernstein inequality to derive an alternative bound
with better dependence of $\sigma_{0}$.

###### Theorem 20

Assume that (a)-(d) hold, and assume that
$\boldsymbol{\mu}=(\frac{1}{2},\dots,\frac{1}{2})$ is the center of unit cube
$[0,1]^{n}$. For any $\delta>0$, $\alpha\in(0,1]$, if

$M<\sqrt{\delta}\exp\left(\frac{12\alpha^{2}}{12\alpha^{2}+13}n\sigma^{2}_{0}\right),\quad\alpha\geq
0.5,$

or

$M<\sqrt{\delta}\exp\left(\frac{3\alpha^{2}}{2\alpha^{2}+\alpha+3}n\sigma^{2}_{0}\right),\quad\alpha\leq
0.5,$

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(\alpha,\boldsymbol{\mu})$-Fisher separable with probability greater than
$1-\delta$.

Proof Bernstein inequality [Boucheron, 2013, p. 36] states that, if
$S_{n}=\sum_{i=1}^{n}z_{i}$ is the sum of independent random variables with
finite variance such that $z_{i}\leq b$ for some $b>0$ with probability $1$
for all $i=1,2,\dots,n$, then, for any $T>0$,

${\mathbb{P}}[S_{n}-E[S_{n}]\geq
T]\leq\exp\left(-\frac{T^{2}}{2(v+bT/3)}\right),$ (80)

where $v=\sum_{i=1}^{n}E[z_{i}^{2}]$. With $z_{i}$ given by (75),
$c_{i}=\mu_{i}=1/2$, and notation $\bar{x}_{i}=x_{i}-1/2$,
$\bar{y}_{i}=y_{i}-1/2$,

$E[z_{i}]=E[\bar{x}_{i}]E[\bar{y}_{i}]-\alpha E[\bar{x}_{i}^{2}]=-\alpha
E[\bar{x}_{i}^{2}].$

Let $\sigma_{i}^{2}=E[\bar{x}_{i}^{2}]$ be the variance of $x_{i}$, and
$\sigma^{2}_{x}=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{2}$ be the average
variance of the components of $\boldsymbol{x}$. Then
$E[S_{n}]=\sum_{i=1}^{n}E[z_{i}]=-n\alpha\sigma^{2}_{x}$. Also,

$E[z_{i}^{2}]=E[\bar{x}_{i}^{2}]E[\bar{y}_{i}^{2}]-2\alpha
E[\bar{x}_{i}^{3}]E[\bar{y}_{i}]+\alpha^{2}E[\bar{x}_{i}^{4}].$

Because $\bar{y}_{i}$ has support $[-1/2,1/2]$, $E[\bar{y}_{i}]=0$, and
$f(y)=y^{2}$ is a convex function, $E[\bar{y}_{i}^{2}]$ is maximal if
$\bar{y}_{i}$ takes values $\pm 1/2$ with equal chances, and
$E[\bar{y}_{i}^{2}]\leq 1/4$. Next, denoting $u_{i}=\bar{x}_{i}^{2}$, we note
that $E[u_{i}]=\sigma_{i}^{2}$, support of $u_{i}$ is $[0,1/4]$, hence
$E[u_{i}^{2}]$ is maximal if $u_{i}$ takes values $0$ and $1/4$ with
probabilities $1-4\sigma_{i}^{2}$ and $4\sigma_{i}^{2}$, respectively. Hence,
$E[\bar{x}_{i}^{4}]=E[u_{i}^{2}]\leq(1/4)^{2}4\sigma_{i}^{2}=\sigma_{i}^{2}/4$.
This implies that
$E[z_{i}^{2}]\leq\sigma_{i}^{2}(1/4)+\alpha^{2}(\sigma_{i}^{2}/4)=(1+\alpha^{2})\sigma_{i}^{2}/4$.
Hence,
$v=\sum_{i=1}^{n}E[z_{i}^{2}]\leq\frac{1+\alpha^{2}}{4}\sum_{i=1}^{n}\sigma_{i}^{2}=\frac{1+\alpha^{2}}{4}n\sigma^{2}_{x}$.

By Proposition 10(iii), $z_{i}\leq b$ for all $i$, where
$b=\frac{1}{16\alpha}$ if $\alpha\geq 0.5$ and $b=\frac{1}{4}(1-\alpha)$ if
$\alpha\leq 0.5$.

Hence, for $\alpha\geq 0.5$, (80) implies that

${\mathbb{P}}[S_{n}\geq 0]={\mathbb{P}}[S_{n}-E[S_{n}]\geq
n\alpha\sigma^{2}_{x}]\leq$
$\leq\exp\left(-\frac{(n\alpha\sigma^{2}_{x})^{2}}{2((1+\alpha^{2})n\sigma^{2}_{x}/4+n\alpha\sigma^{2}_{x}/48\alpha)}\right)=$
$=\exp\left(\frac{-24\alpha^{2}}{12\alpha^{2}+13}n\sigma^{2}_{x}\right)\leq\exp\left(\frac{-24\alpha^{2}}{12\alpha^{2}+13}n\sigma^{2}_{0}\right).$

For $\alpha\geq 0.5$, similar calculation gives

${\mathbb{P}}[S_{n}\geq
0]\leq\exp\left(\frac{-6\alpha^{2}}{2\alpha^{2}+\alpha+3}n\sigma^{2}_{0}\right)$

Combining these bounds with (16), we obtain the desired result. $\Box$

For $\alpha=1$, this gives the following corollary.

###### Corollary 12

Assume that (a)-(d) hold, and assume that
$\boldsymbol{\mu}=(\frac{1}{2},\dots,\frac{1}{2})$ is the center of unit cube
$[0,1]^{n}$. For any $\delta>0$, if

$M<\sqrt{\delta}\exp\left(\frac{12}{25}n\sigma^{2}_{0}\right)$ (81)

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(1,\boldsymbol{\mu})$-Fisher separable with probability greater than
$1-\delta$.

This bound is better than (78), provided that
$\frac{12}{25}n\sigma^{2}_{0}>\frac{256}{81}n\sigma_{0}^{4}$, or
$\sigma_{0}<\frac{9\sqrt{3}}{40}\approx 0.39$.

###### Example 19

If $\delta=0.01$, $\sigma_{0}=0.2$, and $n=1000$ (the same parameters as in
Example 18) (81) reduces to $M<21,799,877$.

How close these bounds to being optimal? If each point in $F$ is distributed
uniformly among vertices of the cube, then $2$ points $\boldsymbol{x}$ and
$\boldsymbol{y}$ are not Fisher separable if and only if they coincide, which
may happen with probability $2^{-n}$. Hence, Fisher separability of a set of
$M$ points holds with probability $1-\delta$ for

$M\approx\sqrt{\frac{\delta}{2^{-n}}}=\sqrt{\delta}\exp\left(\frac{\log
2}{2}n\right)\approx\sqrt{\delta}\exp(0.35n).$

In this example, $\sigma_{0}=0.5$, and (78) gives bound
$\sqrt{\delta}\exp\left(\frac{16}{81}n\right)\approx\sqrt{\delta}\exp(0.2n)$.
Note that the coefficients in these estimates differ less than by the factor
of $2$.

Corollary 12 follows from two-point bound (13) with
$f(n,\alpha)=\exp\left(-\frac{24}{25}n\sigma_{0}^{2}\right)$. Can we
significantly improve the constant here, or the dependence from $\sigma_{0}$?
Consider two points $\boldsymbol{x}$ and $\boldsymbol{y}$, such that all
components $x_{i}$ of $\boldsymbol{x}$ take values $0,1/2,1$ with
probabilities $2\sigma_{0}^{2}$, $1-4\sigma_{0}^{2}$, $2\sigma_{0}^{2}$,
respectively, and all components $y_{i}$ of $\boldsymbol{y}$ take values $0,1$
with equal chances. Then $z_{i}$ given by (75) take values $-1/2$ and $0$ with
probabilities $2\sigma_{0}^{2}$ and $1-2\sigma_{0}^{2}$, respectively, hence
$\boldsymbol{x}$ and $\boldsymbol{y}$ are not Fisher separable with
probability $p_{n}=(1-2\sigma_{0}^{2})^{n}$. For small $\sigma_{0}$,
$p_{n}\approx\exp(-2n\sigma_{0}^{2})$, hence the quadratic dependence on
$\sigma_{0}$ cannot be improved, and the coefficient $\frac{24}{25}$ cannot be
improved to any value higher than $2$.

###  6.3 Better bounds if the product distribution is known

The results in Sections 6.1 and 6.2 are valid for the whole family of product
distributions satisfying certain conditions. This Section studies the case
when the data distribution is explicitly given. In this case, we can deduce
improved estimates from Chernoff’s inequality. Our first result is for general
product distributions, not necessary bounded in the unit cube.

###### Theorem 21

Let points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ be i.i.d points from
an arbitrary but explicitly given product distribution $G$ in
${\mathbb{R}}^{n}$. For any $\delta>0$, let

$M<\sqrt{\delta}\exp\left(\gamma_{n}\right),$ (82)

where

$\gamma_{n}=\frac{1}{2}\sup\limits_{\lambda\geq 0}\left(-\sum_{i=1}^{n}\log
E\left[e^{\lambda(x_{i}y_{i}-\alpha x_{i}^{2})}\right]\right),$

where $x_{i}$ and $y_{i}$ are independent random variables distributed as
$i$-th component of $G$. Then set
$F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(\alpha,\boldsymbol{0})$-Fisher separable with probability greater than
$1-\delta$.

Proof With $\boldsymbol{c}=\boldsymbol{0}$, (75) simplifies to

$z_{i}=x_{i}y_{i}-\alpha x_{i}^{2},\quad i=1,\dots,n,$

where $x_{i}$ and $y_{i}$ are independent and distributed as $i$-th component
of $G$. Points $\boldsymbol{x}$ and $\boldsymbol{y}$ are not Fisher separable
if $S\geq 0$, where $S=\sum_{i=1}^{n}z_{i}$.

Chernoff’s inequality [Boucheron, 2013, p. 21] states that, for any random
variable $S$, and any real number $t$,

${\mathbb{P}}[S\geq t]\leq\exp[-\psi^{*}_{S}(t)],$

where

$\psi^{*}_{S}(t)=\sup\limits_{\lambda\geq 0}(\lambda t-\psi_{S}(\lambda)),$

where $\psi_{S}(\lambda)=\log(E[e^{\lambda S}])$. If $S=\sum_{i=1}^{n}z_{i}$
for independent random variables $z_{i}$,

$e^{\psi_{S}(\lambda)}=E[e^{\lambda\sum_{i=1}^{n}z_{i}}]=E\left[\prod_{i=1}^{n}e^{\lambda
z_{i}}\right]=\prod_{i=1}^{n}E[e^{\lambda z_{i}}],$

hence

$\psi_{S}(\lambda)=\log\left(\prod_{i=1}^{n}E[e^{\lambda
z_{i}}]\right)=\sum_{i=1}^{n}\log E\left[e^{\lambda(x_{i}y_{i}-\alpha
x_{i}^{2})}\right],$

and $\psi^{*}_{S}(0)=2\gamma_{n}$. Hence, Chernoff’s inequality with $t=0$
implies that

${\mathbb{P}}[S\geq 0]\leq\exp[-\psi^{*}_{S}(0)]=\exp[-2\gamma_{n}],$

and (82) follows from (16). $\Box$

###### Corollary 13

If all components of $G$ in Theorem 21 have the same distribution, then
estimate (82) simplifies to

$M<\sqrt{\delta}\exp\left(\gamma n\right),$ (83)

where

$\gamma=\frac{1}{2}\sup\limits_{\lambda\geq 0}\left(-\log
E\left[e^{\lambda(xy-\alpha x^{2})}\right]\right),$

where $x$ and $y$ are independent random variables distributed as a component
of $G$. In particular, if the component distribution has density $f$, then

$\gamma=\frac{1}{2}\sup\limits_{\lambda\geq
0}\left(-\log\left[\int_{{\mathbb{R}}^{2}}e^{\lambda(xy-\alpha
x^{2})}f(x)f(y)dxdy\right]\right).$

It follows from the proof of Theorem 21 and Cramer’s theorem [Pham, 2007,
Theorem 2.1] that the exponent $\gamma$ in (83) is the best possible. However,
estimate (83) maybe non-optimal in lower order terms. Below we give a formula
for the asymptotically best possible upper bound for $M$ in Corollary 13.

Let $\lambda^{*}$ be the (unique) minimizer of $E\left[e^{\lambda(xy-\alpha
x^{2})}\right]$, and let

$c^{*}:=\left.\frac{d}{d\lambda}\left(\frac{E\left[(xy-\alpha
x^{2})e^{\lambda(xy-\alpha x^{2})}\right]}{E\left[e^{\lambda(xy-\alpha
x^{2})}\right]}\right)\right|_{\lambda=\lambda^{*}}$

The exact asymptotic growth of the probability ${\mathbb{P}}[S\geq 0]$ in
Theorem 21 is given by [Petrov, 1965, Theorem 1]

${\mathbb{P}}[S\geq 0]=\frac{\exp[-2\gamma
n]}{\lambda^{*}\sqrt{c^{*}}\sqrt{2\pi n}}(1+o(1)),$

hence the exact asymptotic estimate for $M$ in Corollary 13 is

$M<\sqrt{\delta}\sqrt{\lambda^{*}}\sqrt[4]{2\pi c^{*}n}\exp\left(\gamma
n\right)(1+o(1)).$

We can see that estimate (83) differs from the optimal one by
$\sqrt{\lambda^{*}}\sqrt[4]{2\pi c^{*}n}$ term. However, the advantages of
estimate (83) is simplicity and the absence of $(1+o(1))$ term.

We now apply Corollary 13 to some special cases. First, Corollary 13
specialised to standard normal distribution implies Theorem 12. As another
example, we apply Corollary 13 to the uniform distribution in a cube.

###### Corollary 14

Let $\alpha=1$ and points $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}$ are
i.i.d points from uniform distribution in a cube with center
$\boldsymbol{\mu}$. For any $\delta>0$, if

$M<\sqrt{\delta}\exp\left(\gamma n\right),$ (84)

where

$\gamma=\frac{1}{2}\sup\limits_{\lambda\geq
0}\left(-\log\left[\int_{-\frac{1}{2}}^{\frac{1}{2}}\int_{-\frac{1}{2}}^{\frac{1}{2}}e^{\lambda(xy-x^{2})}dxdy\right]\right)=0.23319...$

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(1,\boldsymbol{\mu})$-Fisher separable with probability greater than
$1-\delta$.

For the unit cube, $\sigma^{2}_{0}=\frac{1}{12}$, and Corollary 12 implies
$(1,\boldsymbol{\mu})$-Fisher separability with probability greater than
$1-\delta$ provided that

$M<\sqrt{\delta}\exp\left(\frac{n}{25}\right)$ (85)

We can see that (84) is a substantial improvement over (85). This is because
(84) works for uniform distribution only, while (85) works for _any_ product
distribution in the unit cube with $\sigma^{2}_{0}=\frac{1}{12}$.

###### Example 20

Let $\alpha=1$ and $\delta=0.01$. Table 10 shows the upper bounds on $M$ in
Corollary 14 in various dimensions $n$.

Table 10:  The upper bounds on $M$ (85) in Corollary 14 in various dimensions $n$ for $\alpha=1$ and $\delta=0.01$. $n$ | $M\leq$
---|---
$10$ | $1.02$
$50$ | $11,578$
$100$ | $1.3\cdot 10^{9}$
$200$ | $1.7\cdot 10^{19}$
$500$ | $4.3\cdot 10^{49}$
$1000$ | $1.8\cdot 10^{100}$

For example, for $n=100$, we see that over a billion points from the uniform
distribution in the unit cube are $1$-Fisher-separable with probability
greater than $99\%$ (compare to the earlier weaker estimates by Gorban and
Tyukin [2017] and Sidorov & Zolotykh [2020]).

##  7 Fisher separability for dependent data from product distribution

The key assumption in Section 6 is that all points in set $F$ are chosen
independently. This section establishes a sufficient condition for Fisher
separability with high probability in a datasets with dependent data points,
as soon as the corresponding conditional distributions are product
distributions in the unit cube $U_{n}=[0,1]^{n}$.

Formally, we assume the following.

  * (*)

For any $\boldsymbol{x}\in F$ and $\boldsymbol{y}\in F$, and any
$\boldsymbol{y}_{0}\in U_{n}$, the conditional distribution of
$\boldsymbol{x}$ given $\boldsymbol{y}=\boldsymbol{y}_{0}$ is a product
distribution with support in $U_{n}$.

For every $\boldsymbol{x}\in F,\boldsymbol{y}\in F,\boldsymbol{y}_{0}\in
U_{n}$ and index $i\in{1,2,\dots,n}$, let
$\sigma_{i}^{2}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{y}_{0})$ be the
variance of the conditional distribution of the $i$-th component of
$\boldsymbol{x}$ given $\boldsymbol{y}=\boldsymbol{y}_{0}$. Let

$\sigma_{0}^{2}=\min_{\boldsymbol{x}\in F,\boldsymbol{y}\in
F,\boldsymbol{y}_{0}\in
U_{n}}\left(\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{2}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{y}_{0})\right)$

be the minimal value of average variance of the components of such conditional
distribution. Also, let $\boldsymbol{c}^{*}=(1/2,\dots,1/2)$ be the center of
$U_{n}$.

###### Theorem 22

Assume that (*) holds. For any $\delta>0$, $\alpha\in(0,1]$, if

$\sigma^{2}_{0}>\frac{1}{16\alpha^{2}}$

and

$M<\sqrt{\delta}\exp\left(\frac{256\alpha^{4}}{(1+2\alpha)^{4}}\left(\sigma^{2}_{0}-\frac{1}{16\alpha^{2}}\right)^{2}n\right)$

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(\alpha,\boldsymbol{c}^{*})$-Fisher separable with probability greater than
$1-\delta$.

Proof By (16), the statement of the theorem follows from (13) with
$\boldsymbol{c}=\boldsymbol{c}^{*}$ and

$f(n,\alpha)=\exp\left(-2\left(\frac{4\alpha}{2\alpha+1}\right)^{4}\left(\sigma^{2}_{0}-\frac{1}{16\alpha^{2}}\right)^{2}n\right).$

We will show that for any $\boldsymbol{x}\in F,\boldsymbol{y}\in F$, and
$\boldsymbol{y}_{0}\in U_{n}$

${\mathbb{P}}[\alpha(\boldsymbol{x}-\boldsymbol{c}^{*},\boldsymbol{x}-\boldsymbol{c}^{*})\leq(\boldsymbol{x}-\boldsymbol{c}^{*},\boldsymbol{y}-\boldsymbol{c}^{*})\,|\,\boldsymbol{y}=\boldsymbol{y}_{0}]\leq
f(n,\alpha),$ (86)

which would imply (13) and finish the proof. The set of all
$\boldsymbol{x}\in{\mathbb{R}}^{n}$ which does not satisfy the inequality
$\alpha(\boldsymbol{x}-\boldsymbol{c}^{*},\boldsymbol{x}-\boldsymbol{c}^{*})\leq(\boldsymbol{x}-\boldsymbol{c}^{*},\boldsymbol{y}-\boldsymbol{c}^{*})$
is the ball with center
$\boldsymbol{c}=\boldsymbol{c}^{*}+(\boldsymbol{y}_{0}-\boldsymbol{c}^{*})/2\alpha$
and radius $r=||\boldsymbol{y}_{0}-\boldsymbol{c}^{*}||/2\alpha$, see Gorban
et al. [2018]. Because $\boldsymbol{y}_{0}\in U_{n}$,
$r^{2}=||\boldsymbol{y}_{0}-\boldsymbol{c}^{*}||^{2}/4\alpha^{2}\leq
n(1/2)^{2}/4\alpha^{2}=n/16\alpha^{2}$, and (86) would follow from

${\mathbb{P}}\left[(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{x}-\boldsymbol{c})\leq\frac{n}{16\alpha^{2}}\,|\,\boldsymbol{y}=\boldsymbol{y}_{0}\right]\leq
f(n,\alpha).$ (87)

Let $x_{i}$ be the random variable whose distribution is the conditional
distribution of the $i$-th component of $\boldsymbol{x}$ given
$\boldsymbol{y}=\boldsymbol{y}_{0}$. Let $z_{i}=-(x_{i}-c_{i})^{2}$, where
$c_{i}$ is the $i$-th component of $\boldsymbol{c}$. Then

$E[z_{i}]=-E[(x_{i}-c_{i})^{2}]\leq-E[(x_{i}-E[x_{i}])^{2}]=-\sigma_{i}^{2}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{y}_{0}),$

and

$\sum_{i=1}^{n}E[z_{i}]\leq-\sum_{i=1}^{n}\sigma_{i}^{2}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{y}_{0})\leq-n\sigma_{0}^{2}.$

Hence,

${\mathbb{P}}\left[(\boldsymbol{x}-\boldsymbol{c},\boldsymbol{x}-\boldsymbol{c})\leq\frac{n}{16\alpha^{2}}\,|\,\boldsymbol{y}=\boldsymbol{y}_{0}\right]={\mathbb{P}}\left[\sum_{i=1}^{n}z_{i}\geq-\frac{n}{16\alpha^{2}}\right]$
$\leq{\mathbb{P}}\left[\sum_{i=1}^{n}(z_{i}-E[z_{i}])\geq-\frac{n}{16\alpha^{2}}+n\sigma_{0}^{2}\right].$

In fact, $c_{i}=1/2+(y^{0}_{i}-1/2)/2\alpha$, where $y^{0}_{i}$ is the $i$-th
component of $\boldsymbol{y}_{0}$. Because $0\leq y^{0}_{i}\leq 1$, we get
$1/2-1/4\alpha\leq c_{i}\leq 1/2+1/4\alpha$, hence $-(1/2+1/4\alpha)^{2}\leq
z_{i}\leq 0$. By Hoeffding’s inequality [Boucheron, 2013, Theorem 2.8],

${\mathbb{P}}\left[\sum_{i=1}^{n}(z_{i}-E[z_{i}])\geq
t\right]\leq\exp\left(-\frac{2t^{2}}{n(1/2+1/4\alpha)^{4}}\right).$

With $t=-\frac{n}{16\alpha^{2}}+n\sigma_{0}^{2}$, this proves (87). $\Box$

We remark that because $\sigma_{0}\leq 0.5$, the bound
$\sigma^{2}_{0}>\frac{1}{16\alpha^{2}}$ in Theorem 22 may hold only if
$\alpha>1/2$.

For $\alpha=1$, we have the following corollary.

###### Corollary 15

Assume that (*) holds. For any $\delta>0$, if

$\sigma^{2}_{0}>\frac{1}{16}$

and

$M<\sqrt{\delta}\exp\left(\frac{256}{81}\left(\sigma^{2}_{0}-\frac{1}{16}\right)^{2}n\right)$
(88)

then set $F=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ is
$(1,\boldsymbol{c}^{*})$-Fisher separable with probability greater than
$1-\delta$.

###### Example 21

Let $\alpha=1$ and $\delta=0.01$. Table 11 shows the upper bounds on $M$ in
Corollary 15 for $\sigma_{0}=0.4,0.45$, and $0.5$ in various dimensions $n$.

Table 11:  The upper bounds on $M$ in Corollary 15 for $\alpha=1$ and $\delta=0.01$, various $\sigma_{0}$ and dimensions. | $\sigma_{0}=0.4$ | $\sigma_{0}=0.45$ | $\sigma_{0}=0.5$
---|---|---|---
$n=10$ | $0.13$ | $0.18$ | $0.3$
$n=50$ | $0.44$ | $2.21$ | $25$
$n=100$ | $2$ | $49$ | $6,691$
$n=200$ | $40$ | $24,017$ | $4.4\cdot 10^{8}$
$n=500$ | $334,248$ | $2.8\cdot 10^{12}$ | $1.3\cdot 10^{23}$
$n=1000$ | $1.1\cdot 10^{12}$ | $8\cdot 10^{25}$ | $1.7\cdot 10^{47}$

For example, for $n=500$ and $\sigma_{0}=0.4$, we see that over $300,000$
points are Fisher-separable with probability greater than $99\%$.

Corollary 15 is not applicable if $\sigma^{2}_{0}\leq 1/16$. However, this is
unavoidable. Indeed, let set $F$ contain points $\boldsymbol{x}$ and
$\boldsymbol{y}$ such that $\boldsymbol{y}$ is uniformly distributed among the
vertices of the unit cube, and $\boldsymbol{x}$ is uniformly distributed among
the vertices of the (twice smaller) cube with main diagonal connecting
$\boldsymbol{c}^{*}$ and $\boldsymbol{y}$. Then the variance of the components
of $\boldsymbol{x}$ is $1/16$, but $\boldsymbol{x}$ and $\boldsymbol{y}$ are