# Untangling Gaussian Mixtures

Eva Fluck  Department of Computer Science, RWTH Aachen University,
<EMAIL_ADDRESS>Sandra Kiefer  Department of Computer Science,
University of Oxford<EMAIL_ADDRESS>Christoph Standke  Department
of Computer Science, RWTH Aachen University<EMAIL_ADDRESS>
###### Abstract

Tangles were originally introduced as a concept to formalize regions of high
connectivity in graphs. In recent years, they have also been discovered as a
link between structural graph theory and data science: when interpreting
similarity in data sets as connectivity between points, finding clusters in
the data essentially amounts to finding tangles in the underlying graphs.

This paper further explores the potential of tangles in data sets as a means
for a formal study of clusters. Real-world data often follow a normal
distribution. Accounting for this, we develop a quantitative theory of tangles
in data sets drawn from Gaussian mixtures. To this end, we equip the data with
a graph structure that models similarity between the points and allows us to
apply tangle theory to the data. We provide explicit conditions under which
tangles associated with the marginal Gaussian distributions exist
asymptotically almost surely. This can be considered as a sufficient formal
criterion for the separabability of clusters in the data.

##  1 Introduction

Cluster analysis [9, 10, 11, 28] can be summarized as the task of grouping
data points based on some similarity measurement. There are two central
paradigms for clustering algorithms: some, like $k$-means and $k$-median,
focus on _similarity_ and group together data points that are sufficiently
close to each other, whereas for example the spectral clustering approach
rather uses _dissimilarity_ to split the data into sufficiently different
groups. Either way, hard clustering, i.e. clustering that partitions the data
into disjoint subsets, has its limits when it comes to real-world data. These
data sets typically have some inherent fuzziness and clusters that are most
adequate to represent them may be wide-spread and might even overlap. All in
all, in real-world data, we cannot always expect a clear answer to the
question whether two points should be grouped together or considered
different, and soft-clustering approaches are necessary. The most common such
approach is to assign values to the data points that denote the degree of
membership to each cluster. For an overview, see e.g. [12].

Connectivity is a central concept for studying the structure of complex graphs
and more general relational structures [16, 17, 24, 37]. It finds its way into
cluster analysis when we consider “similar” data points as adjacent or
connected (see e.g. [39]). Here, the similarity is usually measured via the
distance of the data points in $\mathbb{R}^{d}$. When we equip a set of data
points with a suitable graph structure that reflects their proximity,
analyzing similarity of data points becomes a problem of studying the graph
connectivity. We can hence borrow also graph-theoretic concepts to analyse the
data set. As it turns out, the notion of a graph _tangle_ captures exactly the
kind of ambiguity described above: it is a precise formal definition of
potentially fuzzy but sufficiently distinct clusters in graphs.

Tangles in graphs were first introduced in [37]. They offer a perspective on
connectivity that differs from the classical view: instead of focusing on the
highly connected regions, they deal with thin parts, i.e., the bottlenecks in
the graph. A highly connected region is never located exactly at a bottleneck;
it must lie (mostly) on one of the sides defined by a cut along the
bottleneck. A tangle is a set of consistent orientations of all the
bottlenecks, where the orientation is towards the side of the bottleneck on
which the major part of the associated highly connected region lies. So a
tangle provides “signposts” towards a particular highly connected region and
assigns one such signpost to each low-order cut. We identify highly connected
regions by looking at the signposts. That is, we consider the regions
different whenever there is at least one signpost that points into opposite
directions in the two tangles. This notion of being sufficiently different is
somewhat along the lines of the dissimilarity paradigm, but in a less strict
sense than clusters. In fact, the definition via consistent orientations of
bottlenecks is robust precisely because it avoids references to an explicit
point set.

The authors of [37] show a powerful duality result, which links tangles
closely to branch decompositions of graphs. Furthermore, they give a tree
decomposition of a graph into its maximal tangles, which was turned into a
canonical one in [6]. The original tangle concept was extended to directed
graphs [30, 36] and tangle-tree decompositions were also found in that setting
[25]. In related work, variations of the tangle concept that consider
different ways to measure connectivity in graphs [1, 4] and in matroids [24]
have been explored, see also [27]. The insight that one can define tangles
completely without an underlying graph structure was carried further and led
to the study of _abstract separation systems_ [13, 15, 18, 20], where
separations play the role of the previously mentioned cuts. Even in this very
general setting, duality theorems which relate tangles to tree decompositions
have been derived [18].

With Data Science and Machine Learning emerging as central research fields in
modern computer science, tangles have caught attention also in the context of
clustering. The first transfer of the concept to real-world data happened in
digital-image analysis [19], where tangles were used to describe clusters in
image data in order to find interesting image parts. As Diestel puts it in
[14], “tangles offer a new paradigm for clustering in large data sets”.
Informally speaking, unlike clusters, tangles come equipped with an _order_ ,
a narrowness threshold that defines how small a cut through the data must be
for the corresponding region to be considered a bottleneck. This means that a
parameter of the tangle is the “width of the bottlenecks” at the signposts
that constitute the tangle, and this way, the order is an indicator for the
unambiguity of the highly-connected region or the cluster associated with the
tangle. Vice versa, branch decompositions serve as witnesses for the absence
of tangles above a certain order and may thereby be considered indicators that
clusters above a certain quality threshold do not exist within the data.
Additionally, the order of the tangles captures hierarchical structure of the
data: by decreasing the threshold, some of the previously considered cuts are
not classified as small anymore, so the new bottlenecks are a subset of the
previous ones and thus, several of the previously distinct dense regions may
be united into a single one. It is worth mentioning here that also the tangle-
tree decomposition has its correspondence in the realm of clustering, as it
yields a canonical decomposition of the data set into clusters, see [16].

Tangles can also help when it comes to interpreting clusters. In some
scenarios, separations of the data have semantics (for example, if one
separates discrete data by type) and the orientations of those can then give
an explanation of the similarities between clustered data points. For more
background on interpretable classification and interpretable clustering, we
refer the reader to [5, 35].

So far, the connection between tangles and clustering is largely based on
intuition, as the numerous figurative expressions used in this introduction
indicate. Towards grasping the link formally, [22] establishes an explicit
connection between tangles and hierarchical clustering, which can be
generalized to a one-to-one correspondence between a certain type of
connectivity functions together with its tangles and hierarchical clustering
[23]. Furthermore, the authors of [32] introduce an algorithmic framework to
compute a clustering based on tangles.

(a)

(b)

Figure 1: Data drawn from two Gaussians with their hidden labels in red and
blue. The dashed line represents a possible low-order cut and the purple
circles are candidates for highly connected regions. (a) A
$\delta$-neighborhood graph on the data, that is, two data points are adjacent
if their distance is at most $\delta$. (b) The fully connected graph with the
edge weights dependent on the distance of the data points represented in the
opacity.

#### Our contribution

This paper embarks on a project to make the connection between tangles and
clusters more robust, formal, and quantitative, without depending on
particular clustering algorithms or paradigms.

Real-world data frequently follow a normal distribution, and clustering
algorithms are often tested against data drawn from Gaussian mixtures [7, 39].
We develop a quantitative theory of tangles in data sets obtained from
sampling from Gaussian mixtures, i.e., we assume that the data points are
drawn from various Gaussian distributions. Our goal is to identify
incomparable tangles, that is, pairs of tangles that orient at least one
separation (cut) of the underlying graph differently or rather where none is
just a restriction of the other. Our theory allows us to draw conclusions of
the kind “With high probability, there exist incomparable tangles in the data”
as well as concrete lower bounds on these probabilities. Each tangle will
correspond to a marginal distribution of the Gaussian mixture, i.e., to one
Gaussian distribution contributing to the mixture, so we can interpret a high
probability for the existence of incomparable tangles as a formalization of
the distinguishability or separability of the marginals.

In a set of data points drawn from a Gaussian mixture, a reasonable clustering
algorithm would typically determine clusters that closely correspond to the
hidden labels, i.e., it will assign most points correctly to the marginal
distribution they have been drawn from [26]. However, as described above, the
goal of this work is not to split the data up into partition classes or to
actually determine hidden labels. We rather study ways to quantify the
existence of clusters (or tangles) in the data set, which could in a next step
be interpreted as a quality measure for the reliability of a prediction of the
hidden labels. To this end, we take up two standard ways to represent the data
as a weighted graph, the $\delta$-neighborhood graph (Figure 1) and the fully
connected graph (Figure 1). In both graphs, similarity of data points is
represented in edges and weights on those. We thus use these edge weights as
our connectivity measure for candidate bottlenecks to define the tangles.

Consider the following question: given a mixture of Gaussian distributions,
what is the probability that incomparable tangles associated with the
marginals exist when $n$ data points are drawn? By carefully employing
classical tools from probability theory, our analysis provides explicit
conditions such that, asymptotically almost surely, the tangles exist. In the
$\delta$-neighborhood graph, we further improve our lower bound on the
probability: with (explicit) stronger assumptions, we deduce that the
probability for the existence of incomparable tangles tends to $1$
exponentially fast in the number of data points.

Our theorems are applicable to any mixture of Gaussian distributions. But in
order to be so versatile, their preconditions are quite technical and it is
not trivial to see what choices of parameters and sets fulfill them. We
analyze the preconditions of our theorems for specific sets of parameters to
showcase what a “good choice” may be as well as to compute the explicit
probability bounds in different settings.

We perform a detailed analysis for the mixture of two $1$-dimensional
Gaussians. Here (see Figure 2 – 2), we find that the means of the marginal
distributions need not be far apart in order to satisfy the conditions for the
applicability of our guarantees. Furthermore, the obtained lower probability
bounds for the existence of incomparable tangles are close to $1$ even for
small data sets. This excludes large hidden constants and shows that our
bounds are not only asymptotically high. For the general situation, as soon as
the dimension is larger than $1$ and we have at least three marginal
Gaussians, the means of the distributions are not necessarily aligned.
Accounting for this, we study examples of Gaussian mixtures whose marginals
cannot be separated well by a hyperplane.

Our work differs from [32], which also studies tangles in mixtures of two
Gaussians, in that we consider all possible separations of the data set
instead of restricting them. By studying specific well-behaved separations and
imposing restrictions on the data sets, the authors of [32] manage to provide
theoretical guarantees that the tangles are in 1-to-1 correspondence with the
marginal distributions of the mixture. Moreover, while the results in [32]
treat the special case of two Gaussians, our theorems may appear intimidating
and therefore cumbersome to handle at first sight, but they apply to the
general setting of any mixture of Gaussian distributions with arbitrary
parameters.

#### Outline

Our paper is structured as follows. Section 2 of this paper provides an
introduction to tangles on weighted graphs and some useful tools from
probability theory. Section 3 is dedicated to our model assumptions and the
two graph structures we assign to the data sets. In Section 4, we present our
results for the $\delta$-neighborhood graph and outline in Section 5 to which
extent they translate to the fully connected graph. We conclude with a
discussion of possible follow-up projects in Section 6.

##  2 Preliminaries

For $n\in\mathbb{N}_{>0}$, we let $[n]\coloneqq\\{1,\ldots,n\\}$. For a finite
set $U$, we write $\binom{U}{n}$ to denote all $n$-element subsets of $U$ and
$2^{U}$ to denote the set of all subsets. For $S\subseteq U$, we let
${S}^{\mathsf{c}}\coloneqq U\setminus S$.

###  2.1 Graphs and tangles

This subsection is supposed to serve the reader as a light introduction to the
realm of connectivity functions and tangles. For more background on the topic,
we refer to [27].

A _weighted graph_ is a triple $G=(V,E,w)$ where the pair $(V,E)$ is an
undirected graph with vertex set $V$ and edge set $E\subseteq\binom{V}{2}$,
and $w\colon E\to\mathbb{R}_{>0}$ is a function that assigns _weights_ to the
edges. For $u,v\in V$ with $\\{u,v\\}\in E$, we let $w(u,v)\coloneqq
w(\\{u,v\\})$. In the remainder of this paper, all graphs are assumed to be
weighted. If $E=\binom{V}{2}$, the graph $G$ is a _clique_. For $W\subseteq
V$, we denote by $G[W]$ the (weighted) subgraph of $G$ induced by the vertices
in $W$. For $S,T\subseteq V$, we let $E(S,T)\coloneqq\\{\\{u,v\\}\in E\mid
u\in S,v\in T\\}$. Furthermore, we set $E(S)\coloneqq E(S,S)$.

For a finite set $U$, we call $\kappa\colon 2^{U}\rightarrow\mathbb{R}$ a
_connectivity function_ if all of the following hold.

  * •

$\kappa$ is _symmetric_ , i.e., for all $S\subseteq U$, it holds that
$\kappa(S)=\kappa({S}^{\mathsf{c}})$.

  * •

$\kappa$ is _normalized_ , i.e., $\kappa(\emptyset)=\kappa(U)=0$.

  * •

$\kappa$ is _submodular_ , i.e., $\kappa(S)+\kappa(T)\geq\kappa(S\cap
T)+\kappa(S\cup T)$ holds for all $S,T\subseteq U$.

A prominent example for a connectivity function is the edge connectivity on
graphs. Intuitively, it measures how strongly a vertex set is connected to its
complement. On a graph where all edges have weight $1$, the edge connectivity
of a vertex set equals the order of a minimal edge separation, i.e., the
minimum number of edges that need to be removed to separate the vertex set and
its complement.

######  Example 1 (see [27]).

Let $G=(V,E,w)$ be a weighted graph. For $S\subseteq V$, we define the _edge-
connectivity function_ $\kappa_{G}\colon 2^{V}\rightarrow\mathbb{R}$ via

$\kappa_{G}(S)\coloneqq\sum_{\\{u,v\\}\in E(S,{S}^{\mathsf{c}})}w(u,v).$

Using connectivity functions, we can describe highly connected regions in
structures formally. In the following, to do so, we introduce tangles based on
connectivity functions. Every tangle corresponds to one highly connected
region and vice versa. To have a robust notion of high connectedness, instead
of describing the region pointwise, the tangle just provides directions
towards the region in an unambiguous way. More precisely, for every set with a
low value of the connectivity function (i.e., a “low connectivity” to its
complement), the tangle contains either the set or its complement, which can
be interpreted as determining on which side of the induced separation between
the set and its complement the main part of the considered highly connected
region lies.

######  Definition 2.

Let $U$ be a finite set and $\kappa$ a connectivity function on $U$. A
_$\kappa$ -tangle_ of order $k\geq 0$ is a set $\mathcal{T}\subseteq 2^{U}$
such that all of the following hold.111This definition differs slightly from
the early works on tangles. We orient all separations within the tangle
towards the “large side”, whereas the original definition in [37] orients
separations towards the “small side”. In the clustering setting, our
orientation is more natural. Still, both definitions of the orientation yield
equivalent theories.

T.0

$\kappa(S)<k$ for all $S\in\mathcal{T}$.

T.1

For all $S\subseteq U$ with $\kappa(S)<k$, either $S\in\mathcal{T}$ or
${S}^{\mathsf{c}}\in\mathcal{T}$ holds.

T.2

For all $S_{1},S_{2},S_{3}\in\mathcal{T}$, it holds that $S_{1}\cap S_{2}\cap
S_{3}\neq\emptyset$.

T.3

For all $x\in U$, it holds that $\\{x\\}\notin\mathcal{T}$.

If $\kappa$ is clear from the context, we drop it and we call $\mathcal{T}$ a
tangle. We denote the order of $\mathcal{T}$ by
$\operatorname{ord}(\mathcal{T})$.

Conditions (T.0) and (T.1) ensure that a tangle orients all and only the
separations of low order. The intuition behind requiring non-empty
intersection in condition (T.2) is to ensure that the orientations induced by
the tangle are consistent, that is, all point towards a unique highly
connected region. The number $3$ might seem arbitrary here, but it turns out
that it is necessary and sufficient to give a rich theory (see also [17, 27]).
Finally, condition (T.3) means that singletons are not considered to be highly
connected regions.

We call two tangles $\mathcal{T}_{1}$, $\mathcal{T}_{2}$ _incomparable_ if
there is an $S\subset U$ with $S\in\mathcal{T}_{1}$ and
${S}^{\mathsf{c}}\in\mathcal{T}_{2}$. That is, the tangles are incomparable if
there is some separation that is oriented differently by them. If
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ are not incomparable, we have
$\mathcal{T}_{1}\subseteq\mathcal{T}_{2}$ or
$\mathcal{T}_{1}\supseteq\mathcal{T}_{2}$.

As we are going to see, every clique in a graph induces a tangle. We will use
this fact to prove the existence of tangles in sets of data points obtained
from Gaussian mixtures.

######  Notation 3.

Let $G=(V,E,w)$ be a weighted graph and suppose $W\subseteq V$. If
$E(W)=\emptyset$, set $w_{W}\coloneqq 1$. Otherwise, let
$w_{W}\coloneqq\min\\{w(u,v)\mid\\{u,v\\}\in E(W)\\}$. We set

$\mathcal{T}_{G}(W)\coloneqq\left\\{S\subseteq V\ \bigg{|}\
\kappa_{G}(S)<\frac{2\cdot\lvert W\rvert^{2}}{9}\cdot w_{W}\text{ and }\lvert
S\cap W\rvert>\lvert W\setminus S\rvert\right\\}\ .$

The following lemma provides sufficient conditions for $\mathcal{T}_{G}(W)$ to
be a tangle. Note that the factor $\frac{2}{9}$ is necessary to ensure a non-
empty intersection of all triples of sets contained in the tangle.

######  Lemma 4.

Let $G=(V,E,w)$ be a weighted graph. Let $W\subseteq V$ such that $\lvert
W\rvert\geq 2$ and $G[W]$ is a clique. For
$w_{W}\coloneqq\min\\{w(u,v)\mid\\{u,v\\}\in E(W)\\}$, it holds that
$\mathcal{T}_{G}(W)$ is a $\kappa_{G}$-tangle of order $\frac{2}{9}\cdot\lvert
W\rvert^{2}\cdot w_{W}$.

###### Proof.

Let $k\coloneqq|W|$ and $K\coloneqq G[W]$. (T.0) and (T.3) hold trivially by
the definition of $\mathcal{T}_{G}(W)$. (T.1) holds, since for every vertex
set $S$ that contains exactly half of all vertices of $W$, we have
$\kappa_{G}(S)\geq\kappa_{K}(S\cap W)\geq(\frac{k}{2})^{2}\cdot
w_{W}>\frac{2k^{2}}{9}\cdot w_{W}$. To see that (T.2) holds, we show that
$\kappa_{G}(S)<\frac{2k^{2}}{9}\cdot w_{W}$ implies that $S$ or
${S}^{\mathsf{c}}$ contains more than $\frac{2}{3}$ of all vertices in $W$. We
again use that for every $S\subseteq V$, it holds that
$\kappa_{G}(S)>\kappa_{K}(S\cap W)$, thus we only need to compute
$\kappa_{K}(S\cap W)$. Assume there is some $S\subset V$ such that
$\kappa_{K}(S\cap W)<\frac{2k^{2}}{9}w_{W}$ and $\frac{1}{2}\lvert
W\rvert<\lvert S\cap W\rvert\leq\frac{2}{3}\lvert W\rvert$. We compute
$\kappa_{K}(S\cap W)\geq\lvert S\cap W\rvert\cdot\lvert W\setminus
S\rvert\cdot w_{W}=\lvert S\cap W\rvert\cdot(k-\lvert S\cap W\rvert)\cdot
w_{W}$ and see that the right-hand side becomes minimal when $\lvert S\cap
W\rvert=\lfloor\frac{2}{3}k\rfloor$. For this minimum, we obtain the bound
$\kappa_{K}(S\cap W)\geq\frac{2k^{2}}{9}w_{W}$. However, this contradicts the
assumption $\kappa_{K}(S\cap W)<\frac{2k^{2}}{9}w_{W}$. Thus, we can tighten
the restriction $\lvert S\cap W\rvert>\lvert W\setminus S\rvert$ to $\lvert
S\cap W\rvert>\frac{2}{3}k$. Then (T.2) holds trivially. ∎

###  2.2 Probability theory

We give a brief introduction to the main concepts and notation we use from
probability theory. For more background, we refer the reader to [31]. As
usual, we assume our data to be a subset of some real vector space
$\mathbb{R}^{d}$, which we equip with the Euclidean norm $\lVert\cdot\rVert$
as well as the corresponding (standard) topology and Borel $\sigma$-algebra,
whose elements we call _Borel sets_. For $\boldsymbol{x}\in\mathbb{R}^{d}$ and
$\delta\geq 0$, we define
$B_{\delta}[\boldsymbol{x}]\coloneqq\\{\boldsymbol{x^{\prime}}\mid\boldsymbol{x^{\prime}}\in\mathbb{R}^{d},\lVert\boldsymbol{x^{\prime}}-\boldsymbol{x}\rVert\leq\delta\\}$.
For a Borel set $S\subseteq\mathbb{R}^{d}$, we denote its complement
$\mathbb{R}^{d}\setminus S$ by ${S}^{\mathsf{c}}$ and its indicator function
by $\mathds{1}_{S}$. We also set
$B_{\delta}[S]\coloneqq\bigcup_{\boldsymbol{x}\in
S}B_{\delta}[\boldsymbol{x}]$.222The set $B_{\delta}[S]$ is not necessarily a
Borel set. However, it is Lebesgue-measurable as a continuous image of the
Borel set $S\times B_{\delta}(\boldsymbol{0})$, which suffices for our
purposes. The probability spaces we consider consist of some $\mathbb{R}^{d}$,
its Borel $\sigma$-algebra and a probability distribution $\mathbb{D}$.
Instead of $\mathbb{D}(\\{D\in\mathbb{R}^{d}\colon D\text{ has property
}E\\})$, we write $\Pr_{D\sim\mathbb{D}}(E)$ or simply $\Pr(E)$.

All random variables that we consider are real-valued. For a random variable
$X$, we denote its expected value by $\operatorname*{\mathbb{E}}(X)$ and its
variance by $\operatorname*{Var}(X)$. The covariance of variables $X$ and $Y$
is denoted by $\operatorname{Cov}(X,Y)$. Random variables $X_{1},\ldots,X_{n}$
are called _independent_ if, for all
$A_{1},\ldots,A_{n}\in\mathcal{B}(\mathbb{R}^{d})$, it holds that
$\Pr(\bigwedge_{i=1}^{n}(X_{i}\in A_{i}))=\prod_{i=1}^{n}\Pr(X_{i}\in A_{i})$.

We often use the inequality $\Pr(A\wedge B)\geq\Pr(A)+\Pr(B)-1$, which is
equivalent to the well-known _union bound_.

Recall that the _Gaussian distribution_ $\mathcal{N}(\mu,\sigma^{2})$ with
mean $\mu\in\mathbb{R}$ and standard deviation $\sigma>0$ as parameters is a
distribution on $\mathbb{R}$ with density
$\varphi(x\mid\mu,\sigma^{2})=\frac{1}{\sigma\sqrt{2\pi}}\exp\Big{(}{-\frac{(x-\mu)^{2}}{2\sigma^{2}}}\Big{)}$.
Its distribution function is denoted by $\Phi_{\mu,\sigma^{2}}$. For
$\boldsymbol{\mu}=(\mu_{1},\ldots,\mu_{d})\in\mathbb{R}^{d}$ and $\sigma>0$,
the $d$-dimensional _spherical Gaussian distribution_
$\mathcal{N}^{d}_{\text{sp}}(\boldsymbol{\mu},\sigma^{2})$ with mean
$\boldsymbol{\mu}$ and standard deviation $\sigma$ is the distribution of the
random vector $(X_{1},\ldots,X_{d})$ whose coordinates are independent and the
$i$-th coordinate is $\mathcal{N}(\mu_{i},\sigma^{2})$-distributed.

We recall the Bienaymé-Chebyshev inequality.

######  Theorem 5 (Bienaymé-Chebyshev’s inequality [3, 8]).

Let $X$ be a random variable with finite expected value and variance. Then,
for each $t>0$, it holds that

$\Pr\big{(}\lvert X-\operatorname*{\mathbb{E}}(X)\rvert\geq
t\big{)}\leq\frac{\operatorname*{Var}(X)}{t^{2}}.$

The next inequalities study the distribution of a sum of independent random
variables. We use the following special case of the well-known Hoeffding’s
inequality [29].

######  Theorem 6 (Hoeffding’s Inequality [29]).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that for each
$i\in[n]$, there exist real numbers $a_{i}$ and $b_{i}$ with $a_{i}\leq
X_{i}\leq b_{i}$. Let $\bar{X}\coloneqq\frac{1}{n}\sum_{i=1}^{n}X_{i}$. If
$\mathbb{E}(\bar{X})<0$, then

$\Pr\left(\sum_{i=1}^{n}X_{i}<0\right)>1-\exp\left(-\frac{2n^{2}\mathbb{E}(\bar{X})^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

The following theorem is a quantitative version of the central limit theorem.

######  Theorem 7 (Berry-Esseen’s Inequality ([2, 21])).

Let $X_{1},\ldots,X_{n}$ be independent random variables, each with finite
expected value, finite variance and finite absolute third central moment
$\rho_{i}=\operatorname*{\mathbb{E}}(\lvert
X_{i}-\operatorname*{\mathbb{E}}(X_{i})\rvert^{3})$. For $x\in\mathbb{R}$, let

$F_{n}(x)\coloneqq\Pr\left(\frac{\sum_{i=1}^{n}X_{i}-\sum\operatorname*{\mathbb{E}}(X_{i})}{\sqrt{\sum_{i=1}^{n}\operatorname*{Var}(X_{i})}}\leq
x\right).$

Then there is a constant $C\in\mathbb{R}$ such that $\smash{\lvert
F_{n}(x)-\Phi_{0,1}(x)\rvert\leq\frac{C\cdot\sum_{i=1}^{n}\rho_{i}}{\left(\sum_{i=1}^{n}\operatorname*{Var}(X_{i})\right)^{\frac{3}{2}}}}\
.$

The currently best value for the constant in the theorem is $C=0.5591$ [38].

##  3 The data model

We assume that the data points are drawn from two or more spherical Gaussian
distributions (which we call the _marginals_ or _marginal distributions_) with
given parameters.333The task of learning these parameters from a set of data
is very well studied, see e.g. [33] or [34]. In most of the considered cases,
we will have two distributions with equal standard deviations. Let $d$ be the
dimension of the marginal distributions. Then the data points will be
represented by $d$-dimensional vectors. To make explicit reference to them, it
will be convenient to consider these vectors as labeled with indices
$1,\dots,n$. Therefore, we assume our data encoded as a $(d\times
n)$-dimensional matrix $D$ whose $i$-th column is the data point
$\boldsymbol{x}_{i}$. Accordingly, we also consider $D$ as a transposed tuple
of vectors and write $D=(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n})$.

In the general situation, we cannot assume to draw the same number of data
points from each of the participating Gaussian distributions. Instead, we
assume that, for each marginal, the number of data points drawn from it is
given as a parameter.444The most common alternative model is drawing the data
from a Gaussian mixture with given weights (see, e.g., [28, Chapter 8]). This
is mathematically easier to handle due to the independence of the data points.
Our results thus translate to this setting. However, the data will have a
slightly higher variance, which leads to stronger requirements for our
theorems to be applicable. To this end, we introduce a _hidden labeling_ ,
which assigns to each matrix column the distribution that the corresponding
data point is drawn from. To consider variable total numbers of data points,
we fix the ratios of points drawn from each distribution.

######  Definition 8.

Let $m\in\mathbb{N}$ and $r_{1},\ldots,r_{m}\in\mathbb{Q}_{>0}$ and suppose
that $r_{1}+\ldots+r_{m}=1$. A natural number $n$ is called _compatible with
$(r_{1},\ldots,r_{m})$_ if all $r_{k}\cdot n$ are in $\mathbb{N}$. In that
case, we set $n_{k}\coloneqq r_{k}\cdot n$. A _hidden labeling for
$(r_{1},\dots,r_{m},n)$_ is a function $\ell\colon[n]\to[m]$ such that, for
each $k\in[m]$, there are exactly $n_{k}$ indices $i\in[n]$ that are mapped to
$k$.

If we write $r_{k}=\frac{p_{k}}{q_{k}}$ with coprime natural numbers $p_{k}$
and $q_{k}$, then $n$ is compatible with $(r_{1},\ldots,r_{m})$ if and only if
it is divisible by all the $q_{k}$. If $r_{1},\ldots,r_{m}$ are clear from the
context, we drop them and simply speak about _compatible_ $n$ and $\ell$.

######  Definition 9.

Suppose $d,m\in\mathbb{N}$ and $r_{1},\ldots,r_{m}\in\mathbb{Q}_{>0}$ with
$r_{1}+\ldots+r_{m}=1$ and let $n$ be compatible with $(r_{1},\ldots,r_{m})$.
Let $\ell\colon[n]\rightarrow[m]$ be a hidden labeling for
$(r_{1},\dots,r_{m},n)$. Furthermore, let
$(\boldsymbol{\mu}_{1},\sigma_{1}),\ldots,(\boldsymbol{\mu}_{m},\sigma_{m})$
be such that for each $k\in[m]$, it holds that
$\boldsymbol{\mu}_{k}\in\mathbb{R}^{d}$ and $\sigma_{k}>0$. Let
$(X_{i})_{i\in[n]}$ be a collection of independent $d$-dimensional random
variables such that
$X_{i}\sim\mathcal{N}^{d}_{\text{sp}}(\boldsymbol{\mu}_{\ell(i)},\sigma_{\ell(i)}^{2})$.
The _data distribution defined by
$((r_{k},\boldsymbol{\mu}_{k},\sigma_{k})_{k\in[m]},n,\ell)$_ is the joint
distribution of the $X_{i}$ and denoted by
$\mathbb{D}[(r_{k},\boldsymbol{\mu}_{k},\sigma_{k})_{k\in[m]},n,\ell]$.

Note that the induced data distribution is a distribution over the real vector
space of $(d\times n)$-dimensional matrices whose colums correspond to
$d$-dimensional data points.

######  Notation 10.

In the setting of Definition 9, we let $f_{k}$ be the density of the $k$-th
Gaussian distribution; that is,
$f_{k}(\boldsymbol{x})=\varphi(\boldsymbol{x}\mid\boldsymbol{\mu}_{k},\sigma_{k}^{2})$.
The induced measure is denoted by $\nu_{k}$, so for every Borel set
$A\subseteq\mathbb{R}^{d}$, we have
$\nu_{k}(A)=\int_{A}f_{k}(\boldsymbol{x})d\boldsymbol{x}$. We set
$\bar{f}\coloneqq\sum r_{k}f_{k}$ and $\bar{\nu}\coloneqq\sum r_{k}\nu_{k}$.

Note that in the described setting, for all compatible $n$ and $\ell$, it
holds that $\frac{1}{n}\sum_{i=1}^{n}f_{\ell(i)}=\bar{f}$.

To analyze the data points, we define an underlying graph structure, which
captures the similarity between the data points. More precisely, we interpret
the data points as the vertices and consider two different ways to define
(weighted) adjacency, both of which take the Euclidean distance between
vertices into account.

######  Definition 11.

Let $n,d\in\mathbb{N}_{>0}$ and suppose
$w\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}_{\geq 0}$ is symmetric
and $D=(\boldsymbol{x}_{i})_{i\in[n]}\in\mathbb{R}^{d\times n}$. Then $G(D,w)$
denotes the weighted graph with vertex set $[n]$, edge set
$\big{\\{}\\{i,j\\}\mid w(\boldsymbol{x}_{i},\boldsymbol{x}_{j})>0\big{\\}}$
and weights $w^{\prime}(i,j)=w(\boldsymbol{x}_{i},\boldsymbol{x}_{j})$.

In the first model, we maintain all distances. We define a weighted graph,
which assigns to the edge between a pair of vertices a weight that is
monotonous in their distance and upper-bounded by $1$ with equality if and
only if the distance between the data points is $0$.

######  Example 12.

For $c>0$ and
$\hat{w}_{c}(\boldsymbol{x},\boldsymbol{y})\coloneqq\exp\left(\frac{-\lVert\boldsymbol{x}-\boldsymbol{y}\rVert^{2}}{2c^{2}}\right)$,
the graph $G(D,\hat{w}_{c})$ is a _fully connected graph_. In the context of
this work, we will only have $c=\sigma$, where $\sigma$ is the standard
deviation of the Gaussian distribution at hand (see also [39]). Accordingly,
we drop $c$ and will simply speak about _the_ fully connected graph. See also
Figure 1.

Instead of maintaining all distances between pairs of vertices, we can also
define a threshold for adjacency and forget the distances between vertices
that are further apart.

######  Example 13.

For $\delta>0$ and
$w_{\delta}(\boldsymbol{x},\boldsymbol{y})\coloneqq\begin{cases}1,\text{ if
}\lVert\boldsymbol{x}-\boldsymbol{y}\rVert\leq\delta\\\ 0,\text{
otherwise}\end{cases},$ the graph $G(D,w_{\delta})$ is a _$\delta$
-neighborhood graph_. See also Figure 1.

Both of these models are standard in the clustering context [39]555Besides the
graph models considered here, the article [39] lists a third one. There, a
vertex is adjacent to its $k$ nearest neighbors. However, the model is not
suitable for our context, because the existence of an edge between two
vertices does not only depend on the positions of the corresponding data
points.. Since every graph vertex represents a point in $\mathbb{R}^{d}$, we
can interpret separations of $\mathbb{R}^{d}$ as separations of the vertex set
in the $\delta$-neighborhood graph and the fully connected graph. This
motivates the following notation and will ultimately allow us to bound
probabilities for events on the graphs by using bounds on probabilities in
$\mathbb{R}^{d}$ associated with the data distributions we consider.

######  Notation 14.

For $d,n\in\mathbb{N}_{>0}$, $A\subseteq\mathbb{R}^{d}$ and a $(d\times
n)$-dimensional data matrix $D$, we set
$V_{A}(D)\coloneqq\\{i\in[n]\mid\boldsymbol{x}_{i}\in A\\}$. If $D$ is clear
from the context, we only write $V_{A}$.

Note that, if $A\subseteq\mathbb{R}^{d}$ is a Borel set and $\mathbb{D}$ is a
probability distribution on $\mathbb{R}^{d\times n}$, then the size of $V_{A}$
(denoted by $\lvert V_{A}\rvert$) is a random variable.

The following lemma gives tool insights about the dependence of
$\mathbb{E}(|V_{A}|)$ and $\operatorname*{Var}(|V_{A}|)$ on $n$. We use those
in the next section to obtain the desired probability bounds.

######  Lemma 15.

Assume $d,m\in\mathbb{N}_{>0}$ and let
$(r_{1},\boldsymbol{\mu}_{1},\sigma_{1}),\ldots,(r_{m},\boldsymbol{\mu}_{m},\sigma_{m})$
be as in Definition 9. Let $A\subseteq\mathbb{R}^{d}$ be a Borel set and
suppose $w\in\\{w_{\delta},\hat{w}_{c}\\}$. Then, for compatible $n$ and
$\ell$ and
$\mathbb{D}\coloneqq\mathbb{D}[(r_{k},\boldsymbol{\mu}_{k},\sigma_{k})_{k\in[m]},n,\ell]$,
the following statements hold.

  1. 1.

$\operatorname*{\mathbb{E}}_{D\sim\mathbb{D}}(\lvert
V_{A}\rvert)=n\cdot\bar{\nu}(A)$.

  2. 2.

$\operatorname*{Var}_{D\sim\mathbb{D}}(\lvert
V_{A}\rvert)=n\cdot\sum_{k=1}^{m}r_{k}\nu_{k}(A)(1-\nu_{k}(A))$.

  3. 3.

$\operatorname*{\mathbb{E}}_{D\sim\mathbb{D}}(\lvert
V_{A}\rvert^{2})=n^{2}\cdot\bar{\nu}(A)^{2}+n\cdot\sum_{k=1}^{m}r_{k}\nu_{k}(A)(1-\nu_{k}(A)).$

  4. 4.

$\operatorname*{Var}_{D\sim\mathbb{D}}(\lvert V_{A}\rvert^{2})=O(n^{3})$.

  5. 5.

There is a $c\geq 0$ such that

$\operatorname*{\mathbb{E}}_{D\sim\mathbb{D}}\big{(}\kappa_{G(D,w)}(V_{A})\big{)}=n^{2}\cdot\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})\bar{f}(\boldsymbol{x})\bar{f}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}-n\cdot
c.$

  6. 6.

$\operatorname*{Var}_{D\sim\mathbb{D}}(\kappa_{G(D,w)}(V_{A}))=O(n^{3})$.

  7. 7.

$\Pr\limits_{D\sim\mathbb{D}}\left(\lvert V_{A}\rvert\geq
2\right)=1-\left(1+\sum\limits_{k=1}^{m}\frac{n_{k}\cdot\nu_{k}(A)}{1-\nu_{k}(A)}\right)\cdot\prod\limits_{k=1}^{m}\big{(}1-\nu_{k}(A)\big{)}^{n_{k}}$

###### Proof.

For better readability, we write $\operatorname*{\mathbb{E}}$,
$\operatorname*{Var}$, $\operatorname{Cov}$, and $\kappa$ instead of
$\operatorname*{\mathbb{E}}_{D\sim\mathbb{D}}$,
$\operatorname*{Var}_{D\sim\mathbb{D}}$,
$\operatorname{Cov}_{D\sim\mathbb{D}}$, and $\kappa_{G(D,w)}$ throughout this
proof.

To prove Parts 1 and 2, we observe that

$\operatorname*{\mathbb{E}}(\lvert
V_{A}\rvert)=\operatorname*{\mathbb{E}}\left(\sum_{i=1}^{n}\mathds{1}_{A}(X_{i})\right)=\sum_{i=1}^{n}\operatorname*{\mathbb{E}}(\mathds{1}_{A}(X_{i}))=\sum_{i=1}^{n}\nu_{\ell(i)}(A)=n\cdot\bar{\nu}(A)$

and, since the $X_{i}$ are independent,

$\displaystyle\operatorname*{Var}(\lvert V_{A}\rvert)$
$\displaystyle=\operatorname*{Var}\left(\sum_{i=1}^{n}\mathds{1}_{A}(X_{i})\right)=\sum_{i=1}^{n}\operatorname*{Var}(\mathds{1}_{A}(X_{i}))$
$\displaystyle=\sum_{i=1}^{n}\nu_{\ell(i)}(A)(1-\nu_{\ell(i)}(A))=\sum_{k=1}^{m}n_{k}\nu_{k}(A)(1-\nu_{k}(A))$
$\displaystyle=n\cdot\sum_{k=1}^{m}r_{k}\nu_{k}(A)(1-\nu_{k}(A)).$

Now Part 3 immediately follows from the well-known equality
$\operatorname*{\mathbb{E}}(\lvert
V_{A}\rvert^{2})=\operatorname*{\mathbb{E}}(\lvert
V_{A}\rvert)^{2}+\operatorname*{Var}(\lvert V_{A}\rvert)$.

For Part 4, we expand $\lvert
V_{A}\rvert^{2}=(\sum_{i=1}^{n}\mathds{1}_{A}(X_{i}))^{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}\mathds{1}_{A}(X_{i})\cdot\mathds{1}_{A}(X_{j})$
and conclude

$\operatorname*{Var}(\lvert
V_{A}\rvert^{2})=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{i^{\prime}=1}^{n}\sum_{j^{\prime}=1}^{n}\operatorname{Cov}\big{(}\mathds{1}_{A}(X_{i})\cdot\mathds{1}_{A}(X_{j}),\mathds{1}_{A}(X_{i^{\prime}})\cdot\mathds{1}_{A}(X_{j^{\prime}})\big{)}.$
(1)

If $i,j,i^{\prime},j^{\prime}$ are pairwise distinct, then the random
variables $X_{i},X_{j},X_{i^{\prime}}$ and $X_{j^{\prime}}$ are independent
and hence
$\operatorname{Cov}(\mathds{1}_{A}(X_{i})\cdot\mathds{1}_{A}(X_{j}),\mathds{1}_{A}(X_{i^{\prime}})\cdot\mathds{1}_{A}(X_{j^{\prime}}))=0$.
This implies that $n(n-1)(n-2)(n-3)$ of the $n^{4}$ summands in Equation 1 are
equal to $0$. Since every other summand is also at most $1$, this shows the
claim.

For proving Parts 5 and 6, we set $Y_{i,j}\coloneqq
w(X_{i},X_{j})\cdot\mathds{1}_{A}(X_{i})\cdot\mathds{1}_{{A}^{\mathsf{c}}}(X_{j})$,
which yields $Y_{i,i}=0$ whenever $i=j$ and otherwise, for $i\neq j$,

$\operatorname*{\mathbb{E}}(Y_{i,j})=\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{\ell(i)}(\boldsymbol{x})f_{\ell(j)}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}\
.$

Since $\kappa(V_{A})=\sum_{i=1}^{n}\sum_{j=1}^{n}Y_{i,j},$ we conclude

$\displaystyle\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})\bar{f}(\boldsymbol{x})\bar{f}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})\bigg{(}\frac{1}{n}\sum_{i=1}^{n}f_{\ell(i)}(\boldsymbol{x})\bigg{)}\bigg{(}\frac{1}{n}\sum_{j=1}^{n}f_{\ell(j)}(\boldsymbol{y})\bigg{)}\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})\bigg{(}\sum_{i=1}^{n}\sum_{j=1}^{n}f_{\ell(i)}(\boldsymbol{x})f_{\ell(j)}(\boldsymbol{y})\bigg{)}\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{\ell(i)}(\boldsymbol{x})f_{\ell(j)}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}^{n}\int\limits_{A}\int\limits_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{\ell(i)}(\boldsymbol{x})f_{\ell(j)}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle+\frac{1}{n^{2}}\mspace{-2.0mu}\sum_{i=1}^{n}\int\limits_{A}\int\limits_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{\ell(i)}(\boldsymbol{x})f_{\ell(i)}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname*{\mathbb{E}}(Y_{i,j})+\frac{1}{n^{2}}\sum_{k=1}^{m}n_{k}\cdot\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{k}(\boldsymbol{x})f_{k}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\operatorname*{\mathbb{E}}(\kappa(V_{A}))+\frac{1}{n}\bigg{(}\sum_{k=1}^{m}r_{k}\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{k}(\boldsymbol{x})f_{k}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}\bigg{)}\
.$

Setting
$c\coloneqq\sum_{k=1}^{m}r_{k}\int_{A}\int_{{A}^{\mathsf{c}}}w(\boldsymbol{x},\boldsymbol{y})f_{k}(\boldsymbol{x})f_{k}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$,
this yields Part 5.

Next, we expand

$\operatorname*{Var}(\kappa(V_{A}))=\operatorname*{Var}(\sum_{i=1}^{n}\sum_{j=1}^{n}Y_{i,j})=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{i^{\prime}=1}^{n}\sum_{j^{\prime}=1}^{n}\operatorname{Cov}(Y_{i,j},Y_{i^{\prime},j^{\prime}})$
(2)

and observe for pairwise distinct $i,j,i^{\prime},j^{\prime}$ that
$X_{i},X_{j},X_{i^{\prime}},X_{j^{\prime}}$ are independent, which in turn
yields the independence of $Y_{i,j}$ and $Y_{i^{\prime},j^{\prime}}$. Thus, we
get that $\operatorname{Cov}(Y_{i,j},Y_{i^{\prime},j^{\prime}})=0$. This
yields that there are $O(n^{3})$ non-zero summands in Equation 2 and it
remains to show that these can be bounded independently from $n$ and $\ell$.
Indeed, since the value of
$\operatorname{Cov}(Y_{i,j},Y_{i^{\prime},j^{\prime}})$ is determined by
$\ell(i),\ell(j),\ell(i^{\prime}),\ell(j^{\prime})$ and the information which
of the indices are equal, we can find a common upper bound on the covariances
that only depends on
$(r_{1},\boldsymbol{\mu}_{1},\sigma_{1}),\ldots,(r_{m},\boldsymbol{\mu}_{m},\sigma_{m})$,
$A$ and $w$. This yields Part 6.

Finally, to prove the formula for the probability of $\lvert V_{A}\rvert\geq
2$, we write

$\Pr_{D\sim\mathbb{D}}\big{(}\lvert V_{A}\rvert\geq
2\big{)}=1-\Pr_{D\sim\mathbb{D}}\big{(}\lvert
V_{A}\rvert=0\big{)}-\Pr_{D\sim\mathbb{D}}\big{(}\lvert V_{A}\rvert=1\big{)}$

and use the independence of the random variables $X_{i}$ to obtain

$\displaystyle\Pr_{D\sim\mathbb{D}}\big{(}\lvert
V_{A}\rvert=0\big{)}=\Pr_{D\sim\mathbb{D}}\Big{(}\bigwedge_{i=1}^{n}(X_{i}\notin
A)\Big{)}=\prod_{i=1}^{n}\Pr_{D\sim\mathbb{D}}\big{(}X_{i}\notin
A\big{)}=\prod_{i=1}^{n}(1-\nu_{\ell(i)}(A))$

and, since all $\nu_{k}(A)<1$,

$\displaystyle\Pr_{D\sim\mathbb{D}}\big{(}\lvert V_{A}\rvert=1\big{)}$
$\displaystyle=\sum_{i=1}^{n}\Pr_{D\sim\mathbb{D}}\Big{(}(X_{i}\in
A)\wedge\bigwedge_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{n}(X_{j}\notin A)\Big{)}$
$\displaystyle=\sum_{i=1}^{n}\Pr_{D\sim\mathbb{D}}(X_{i}\in
A)\cdot\prod_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{n}\Pr_{D\sim\mathbb{D}}(X_{j}\notin A)$
$\displaystyle=\sum_{i=1}^{n}\nu_{\ell(i)}(A)\cdot\prod_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{n}(1-\nu_{\ell(j)}(A))$
$\displaystyle=\sum_{i=1}^{n}\frac{\nu_{\ell(i)}(A)}{1-\nu_{\ell(i)}(A)}\cdot\prod_{j=1}^{n}(1-\nu_{\ell(j)}(A)).$

Together, this yields

$\displaystyle\Pr_{D\sim\mathbb{D}}\big{(}\lvert V_{A}\rvert\geq 2\big{)}$
$\displaystyle=1-\left(1+\sum_{i=1}^{n}\frac{\nu_{\ell(i)}(A)}{1-\nu_{\ell(i)}(A)}\right)\cdot\prod_{j=1}^{n}(1-\nu_{\ell(j)}(A))$
$\displaystyle=1-\left(1+\sum_{k=1}^{m}\frac{n_{k}\cdot\nu_{k}(A)}{1-\nu_{k}(A)}\right)\cdot\prod_{k=1}^{m}(1-\nu_{k}(A))^{n_{k}}\
,$

which shows Part 7. ∎

##  4 Results for the neighborhood graph

In this section, we study the tangles that occur in the $\delta$-neighborhood
graph, as defined in Example 13. We find that the unweighted structure of the
graph makes it possible to derive strong lower bounds on the probability that
incomparable tangles corresponding to the different marginal Gaussian
distributions exist. By Lemma 4, every non-trivial clique $G[W]$ induces a
$\kappa_{G}$-tangle. Every hyperball of radius at most $\frac{\delta}{2}$
induces a clique in the $\delta$-neighborhood graph. As our goal is to
identify tangles associated with the dense regions around the means, we
consider the $\frac{\delta}{2}$-neighborhood
$B_{\frac{\delta}{2}}[\boldsymbol{\mu}]$ of $\mu$ in the following. We bound
the probability that the induced cliques are non-trivial and that the tangles
corresponding to different means are indeed incomparable. To do so, we find
small separations that are oriented differently by the different tangles.

###  4.1 Probability bounds

To compute the probability bounds for the existence of incomparable tangles,
we first give a bound on the probability that, for a given separation, the
$\frac{\delta}{2}$-ball around the mean of a distribution induces a tangle
with a prescribed orientation of the separation.

To consider different geometric objects for the separation, we define it via a
Borel set $S$. In Section 4.2, we consider particular choices for $S$ that
fulfill the requirements to obtain the probability bounds presented in this
section. Often the local minima of the underlying joint distribution will
induce a good choice for the Borel set $S$, but, to actually compute the
probabilities, it can be useful to make different choices.

######  Theorem 16.

Suppose $\delta>0$, $d,m\in\mathbb{N}_{>0}$ and let
$(r_{1},\boldsymbol{\mu}_{1},\sigma_{1}),\ldots,(r_{m},\boldsymbol{\mu}_{m},\sigma_{m})$
be as in Definition 9. Choose a $k\in[m]$ and define $B\coloneqq
B_{\frac{\delta}{2}}[\boldsymbol{\mu_{k}}]$. Let $S\subseteq\mathbb{R}^{d}$ be
a Borel set.

If $\bar{\nu}(B\cap S)>\frac{1}{2}\bar{\nu}(B)$ and
$\frac{2}{9}\bar{\nu}(B)^{2}>\int_{S}\int_{{S}^{\mathsf{c}}}w_{\delta}(\boldsymbol{x},\boldsymbol{y})\bar{f}(\boldsymbol{x})\bar{f}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$,
then for compatible $n$ and $\ell$ and
$\mathbb{D}=\mathbb{D}[(r_{k},\boldsymbol{\mu}_{k},\sigma_{k})_{k\in[m]},n,\ell]$,
it holds that

$\Pr_{D\sim\mathbb{D}}\left(\mathcal{T}_{G(D,w_{\delta})}(V_{B})\text{ is a
tangle that contains }V_{S}\right)=1-O\left(\tfrac{1}{n}\right)\ .$

###### Proof.

For better readability, let $G\coloneqq G(D,w_{\delta})$ and
$\kappa\coloneqq\kappa_{G}$. Since $B$ is a ball with radius
$\frac{\delta}{2}$, every two data points in $B$ have distance at most
$\delta$, so $V_{B}$ induces a clique in $G$ with $w_{V_{B}}=1$ where
$w_{V_{B}}\coloneqq\min\\{w(u,v)\mid\\{u,v\\}\in E(V_{B})\\}$. Note that, by
Lemma 4, it holds that $\mathcal{T}_{G}(V_{B})$ is a tangle as soon as $\lvert
V_{B}\rvert\geq 2$. Furthermore, for the tangle to have the desired
orientation, i.e., for $V_{S}$ to be a member of $\mathcal{T}_{G}(V_{B})$, the
inequalities $\lvert V_{B}\cap V_{S}\rvert>\lvert V_{B}\setminus V_{S}\rvert$
and $\frac{2}{9}\lvert V_{B}\rvert^{2}>\kappa(V_{S})$ must hold.

In the following, we define four events which will ultimately enable us to
deduce a lower bound on the probability that the conditions

  1. 1.

$\lvert V_{B}\rvert\geq 2$,

  2. 2.

$\lvert V_{B}\cap V_{S}\rvert>\lvert V_{B}\setminus V_{S}\rvert$ and

  3. 3.

$\frac{2}{9}\lvert V_{B}\rvert^{2}>\kappa(V_{S})$

hold simultaneously. Note that the assumptions of the theorem ensure that
Inequalities (2) and (3) hold in expectation. Indeed,

$\displaystyle\operatorname*{\mathbb{E}}(\lvert V_{B}\cap V_{S}\rvert)$
$\displaystyle\overset{\text{L.\ref{lem:basic_computations_app}.\ref{enum:exp_size_app}}}{=}n\cdot\bar{\nu}(B\cap
S)>n\cdot(\bar{\nu}(B)-(\bar{\nu}(B\cap S))$
$\displaystyle=n\cdot\bar{\nu}(B\setminus
S)\overset{\text{L.\ref{lem:basic_computations_app}.\ref{enum:exp_size_app}}}{=}\operatorname*{\mathbb{E}}(\lvert
V_{B}\setminus V_{S}\rvert)$

and similarly, by Lemma 15, Parts 3 and 5, Inequality (3) holds in
expectation. Therefore, we can use the Bienaymé-Chebyshev inequality (Theorem
5) for each of the random variables $\lvert V_{B\cap S}\rvert$, $\lvert
V_{B\setminus S}\rvert$, $\lvert V_{B}\rvert^{2}$, and $\kappa(V_{S})$ to
derive probability bounds. Set

$\varepsilon_{1}\coloneqq\frac{1}{2}\cdot\big{(}\bar{\nu}(B\cap
S)-\bar{\nu}(B\setminus S)\big{)}\qquad\text{ and }\\\
\varepsilon_{2}\coloneqq\frac{1}{2}\cdot\left(\frac{2}{9}\bar{\nu}(B)^{2}-\int_{S}\int_{{S}^{\mathsf{c}}}w_{\delta}(\boldsymbol{x},\boldsymbol{y})\bar{f}(\boldsymbol{x})\bar{f}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}\right).$

With this, we are ready to define our events $E_{1},E_{2},E_{3},E_{4}$ and
deduce lower bounds on their probabilities.

$\displaystyle\Pr_{D\sim\mathbb{D}}\Big{(}\underbrace{\big{\lvert}\lvert
V_{B\cap S}\rvert-\operatorname*{\mathbb{E}}(\lvert V_{B\cap
S}\rvert)\big{\rvert}<\varepsilon_{1}\cdot n}_{\eqqcolon{}E_{1}}\Big{)}$
$\displaystyle>\mathrlap{1-\frac{\operatorname*{Var}(\lvert V_{B\cap
S}\rvert)}{\varepsilon_{1}^{2}n^{2}}}\phantom{1-\frac{\operatorname*{Var}(\kappa(V_{S}))}{\varepsilon_{2}^{2}n^{4}}}\overset{\text{L.\ref{lem:basic_computations_app}.\ref{enum:var_size_app}}}{=}1-O\left(\frac{1}{n}\right),$
$\displaystyle\Pr_{D\sim\mathbb{D}}\Big{(}\underbrace{\big{\lvert}\lvert
V_{B\setminus S}\rvert-\operatorname*{\mathbb{E}}(\lvert V_{B\setminus
S}\rvert)\big{\rvert}<\varepsilon_{1}\cdot n}_{\eqqcolon{}E_{2}}\Big{)}$
$\displaystyle>\mathrlap{1-\frac{\operatorname*{Var}(\lvert V_{B\setminus
S}\rvert)}{\varepsilon_{1}^{2}n^{2}}}\phantom{1-\frac{\operatorname*{Var}(\kappa(V_{S}))}{\varepsilon_{2}^{2}n^{4}}}\overset{\text{L.\ref{lem:basic_computations_app}.\ref{enum:var_size_app}}}{=}1-O\left(\frac{1}{n}\right),$
$\displaystyle\Pr_{D\sim\mathbb{D}}\Big{(}\underbrace{\big{\lvert}\lvert
V_{B}\rvert^{2}-\operatorname*{\mathbb{E}}(\lvert
V_{B}\rvert^{2})\big{\rvert}<\varepsilon_{2}\cdot
n^{2}}_{\eqqcolon{}E_{3}}\Big{)}$
$\displaystyle>\mathrlap{1-\frac{\operatorname*{Var}(\lvert
V_{B}\rvert^{2})}{\varepsilon_{2}^{2}n^{4}}}\phantom{1-\frac{\operatorname*{Var}(\kappa(V_{S}))}{\varepsilon_{2}^{2}n^{4}}}\overset{\text{L.\ref{lem:basic_computations_app}.\ref{enum:var_size_sq_app}}}{=}1-O\left(\frac{1}{n}\right),$
$\displaystyle\Pr\limits_{D\sim\mathbb{D}}\Big{(}\underbrace{\big{\lvert}\kappa(V_{S})-\operatorname*{\mathbb{E}}(\kappa(V_{S}))\big{\rvert}<\varepsilon_{2}\cdot
n^{2}}_{\eqqcolon{}E_{4}}\Big{)}$
$\displaystyle>1-\frac{\operatorname*{Var}(\kappa(V_{S}))}{\varepsilon_{2}^{2}n^{4}}\overset{\text{L.\ref{lem:basic_computations_app}.\ref{enum:var_kappa_app}}}{=}1-O\left(\frac{1}{n}\right).$

The union bound then yields

$\Pr_{D\sim\mathbb{D}}(E_{1}\wedge E_{2}\wedge E_{3}\wedge
E_{4})\geq\Pr_{D\sim\mathbb{D}}(E_{1})+\Pr_{D\sim\mathbb{D}}(E_{2})+\Pr_{D\sim\mathbb{D}}(E_{3})+\Pr_{D\sim\mathbb{D}}(E_{4})-3=1-O\left(\frac{1}{n}\right).$

It suffices now to show that $E_{1}\land E_{2}\land E_{3}\land E_{4}$ entails
the validity of Inequalities (1)-(3). Suppose that all of
$E_{1},E_{2},E_{3},E_{4}$ hold. Then for $n\geq\frac{2}{\varepsilon_{1}}$, we
have

$\displaystyle\lvert V_{B}\rvert$ $\displaystyle\geq\lvert V_{B\cap S}\rvert$
$\displaystyle=(\lvert V_{B\cap S}\rvert-\operatorname*{\mathbb{E}}(\lvert
V_{B\cap S}\rvert))+(\operatorname*{\mathbb{E}}(\lvert V_{B\cap
S}\rvert)-\operatorname*{\mathbb{E}}(\lvert V_{B\setminus
S}\rvert))+\operatorname*{\mathbb{E}}(\lvert V_{B\setminus S}\rvert)$
$\displaystyle\overset{\mathclap{E_{1}}}{{}>{}}{-}\varepsilon_{1}\cdot
n+2\varepsilon_{1}\cdot n+\operatorname*{\mathbb{E}}(\lvert V_{B\setminus
S}\rvert)$ $\displaystyle>\varepsilon_{1}\cdot n$ $\displaystyle\geq 2\ ,$

which shows Inequality (1). Moreover,

$\displaystyle\lvert V_{B}\cap V_{S}\rvert-\lvert V_{B}\setminus
V_{S}\rvert={}$ $\displaystyle\big{(}\lvert V_{B}\cap
V_{S}\rvert-\operatorname*{\mathbb{E}}(\lvert V_{B}\cap V_{S}\rvert)\big{)}$
$\displaystyle{}+\big{(}\operatorname*{\mathbb{E}}(\lvert V_{B}\cap
V_{S}\rvert)-\operatorname*{\mathbb{E}}(\lvert V_{B}\setminus
V_{S}\rvert)\big{)}$ $\displaystyle{}+\big{(}\operatorname*{\mathbb{E}}(\lvert
V_{B}\setminus V_{S}\rvert)-\lvert V_{B}\setminus V_{S}\rvert\big{)}$
$\displaystyle={}$ $\displaystyle\big{(}\lvert V_{B\cap
S}\rvert-\operatorname*{\mathbb{E}}(\lvert V_{B\cap
S}\rvert)\big{)}+n\cdot\big{(}\bar{\nu}(B\cap S)-\bar{\nu}(B\setminus
S)\big{)}$ $\displaystyle{}+\big{(}\operatorname*{\mathbb{E}}(\lvert
V_{B\setminus S}\rvert)-\lvert V_{B\setminus S}\rvert\big{)}$
$\displaystyle\overset{\mathclap{E_{1},E_{2}}}{{}>{}}$
$\displaystyle{-}\varepsilon_{1}\cdot n+2\varepsilon_{1}\cdot
n-\varepsilon_{1}\cdot n$ $\displaystyle={}$ $\displaystyle 0\ ,$

which proves Inequality (2). Finally, by Parts 3 and 5 of Lemma 15, there
exists a $c\geq 0$ such that

$\displaystyle\frac{2}{9}\lvert
V_{B}\rvert^{2}\mspace{-2.0mu}-\mspace{-2.0mu}\kappa(V_{S})=$ $\displaystyle\
\frac{2}{9}\big{(}\lvert
V_{B}\rvert^{2}\mspace{-1.0mu}-\mspace{-1.0mu}\operatorname*{\mathbb{E}}(\lvert
V_{B}\rvert^{2})\big{)}\mspace{-2.0mu}+\mspace{-2.0mu}\left(\mspace{-1.0mu}\frac{2}{9}\operatorname*{\mathbb{E}}(\lvert
V_{B}\rvert^{2})\mspace{-1.0mu}-\mspace{-1.0mu}\operatorname*{\mathbb{E}}(\kappa(V_{S}))\mspace{-2.0mu}\right)$
$\displaystyle{}+\big{(}\operatorname*{\mathbb{E}}(\kappa(V_{S}))\mspace{-1.0mu}-\mspace{-1.0mu}\kappa(V_{S})\big{)}$
$\displaystyle\overset{\mathclap{E_{3},E_{4}}}{{}>{}}$
$\displaystyle{-}\varepsilon_{2}\cdot n^{2}+2\varepsilon_{2}\cdot
n^{2}+\frac{2}{9}n\cdot\sum_{k=1}^{m}r_{k}\nu_{k}(B)(1-\nu_{k}(B))$
$\displaystyle{}+c\cdot n-\varepsilon_{2}\cdot n^{2}$ $\displaystyle>$
$\displaystyle\ 0\ ,$

which shows Inequality (3). Together, this proves that for
$n\geq\frac{2}{\varepsilon_{1}}$, the event $E_{1}\land E_{2}\land E_{3}\land
E_{4}$ implies that $\mathcal{T}_{G}(V_{B})$ is a tangle that contains
$V_{S}$. This completes the proof. ∎

######  Remark 17.

A small modification of the proof shows that the probability for $V_{S}$ to be
a member of $\mathcal{T}_{G(D,w_{\delta})}(V_{B})$ is in $O(\frac{1}{n})$ if
the second inequality holds with opposite sign; that is, if
$\frac{2}{9}\bar{\nu}(B)^{2}<\int_{S}\int_{{S}^{\mathsf{c}}}w_{\delta}(\boldsymbol{x},\boldsymbol{y})\bar{f}(\boldsymbol{x})\bar{f}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}$.
However, this does not imply that there is no suitable tangle containing
$V_{S}$, since a tangle of higher order containing
$\mathcal{T}_{G(D,w_{\delta})}(V_{B})$ as a subset and $V_{S}$ as a member
could still exist.

In fact, the proof arguments yield that, for every $\varepsilon>0$, the order
of the tangle is with probability $1-O\left(\tfrac{1}{n}\right)$ at least
$(1-\varepsilon)\cdot n^{2}\cdot\frac{2}{9}\bar{\nu}(B)^{2}$.

Theorem 16 can be used to show the existence of incomparable tangles
asymptotically almost surely. However, since the constants hidden in the
asymptotic expression for the bound are large, for small numbers of data
points, it only yields a trivial bound. Hence, we intend to make reasonably
stricter requirements for the data distribution that allow us to find a
probability bound with significantly faster convergence to $1$. As a first
step, we derive an upper bound on the size of a cut induced by a set
$S\subseteq\mathbb{R}^{d}$.

######  Lemma 18.

Suppose $\delta>0$, $d,n\in\mathbb{N}_{>0}$, $D\in\mathbb{R}^{d\times n}$ and
let $S\subseteq\mathbb{R}^{d}$ be a Borel set. We set $A\coloneqq
B_{\delta}[S]\cap B_{\delta}[{S}^{\mathsf{c}}]$. Then
$\kappa_{G(D,w_{\delta})}(V_{S})\leq\frac{1}{4}\lvert V_{A}\rvert^{2}$.

###### Proof.

Let $E$ be the edge set of $G(D,w_{\delta})$ and consider an edge
$\\{i,j\\}\in E(V_{S},V_{{S}^{\mathsf{c}}})$ with $i\in V_{S}$ and $j\in
V_{{S}^{\mathsf{c}}}$. By definition of the $\delta$-neighborhood graph
(Example 13), we know
$\lVert\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\rVert\leq\delta$. Hence
$\boldsymbol{x}_{i}\in B_{\delta}[\boldsymbol{x}_{j}]\cap S\subseteq
B_{\delta}[{S}^{\mathsf{c}}]\cap S$ and $\boldsymbol{x}_{j}\in
B_{\delta}[\boldsymbol{x}_{i}]\cap{S}^{\mathsf{c}}\subseteq
B_{\delta}[S]\cap{S}^{\mathsf{c}}$, which yields $(i,j)\in
V_{B_{\delta}[{S}^{\mathsf{c}}]\cap S}\times
V_{B_{\delta}[S]\cap{S}^{\mathsf{c}}}$. Since
$B_{\delta}[{S}^{\mathsf{c}}]\cap S$ and $B_{\delta}[S]\cap{S}^{\mathsf{c}}$
are disjoint with $(B_{\delta}[{S}^{\mathsf{c}}]\cap
S)\cup(B_{\delta}[S]\cap{S}^{\mathsf{c}})=A$, we can use the well-known
inequality $a\cdot b\leq\frac{1}{4}(a+b)^{2}$ for reals $a,b$ to conclude

$\kappa_{G(D,w_{\delta})}(V_{S})\leq\lvert V_{B_{\delta}[{S}^{\mathsf{c}}]\cap
S}\rvert\cdot\lvert
V_{B_{\delta}[S]\cap{S}^{\mathsf{c}}}\rvert\leq\frac{1}{4}\left(\lvert
V_{B_{\delta}[{S}^{\mathsf{c}}]\cap S}\rvert+\lvert
V_{B_{\delta}[S]\cap{S}^{\mathsf{c}}}\rvert\right)^{2}=\frac{1}{4}\lvert
V_{A}\rvert^{2}.$

∎

Using the lemma, we can answer the question whether a cut is oriented by the
considered tangle by checking if a sum of independent random variables is
negative. Then, Hoeffding’s and Berry-Esseen’s Inequalities (Theorems 6 and 7)
yield the following.

######  Theorem 19.

Suppose $\delta>0$, $d,m\in\mathbb{N}_{>0}$ and let
$(r_{1},\boldsymbol{\mu}_{1},\sigma_{1}),\ldots,(r_{m},\boldsymbol{\mu}_{m},\sigma_{m})$
be as in Definition 9. Choose a $k\in[m]$ and define $B\coloneqq
B_{\frac{\delta}{2}}[\boldsymbol{\mu_{k}}]$. Let $S$ be a Borel set with
$B\subseteq S$. We set $A\coloneqq B_{\delta}[S]\cap
B_{\delta}[{S}^{\mathsf{c}}]$ and suppose
$2\sqrt{2}\bar{\nu}(B)>3\bar{\nu}(A).$

Let $n$ and $\ell$ be compatible and
$\mathbb{D}=\mathbb{D}[(r_{k},\boldsymbol{\mu}_{k},\sigma_{k})_{k\in[m]},n,\ell]$.
For all $i\in[n]$, we define random variables
$Y_{i}\coloneqq(3\cdot\mathds{1}_{A}-2\sqrt{2}\cdot\mathds{1}_{B})(X_{i})$ and
set $\rho_{i}\coloneqq\operatorname*{\mathbb{E}}(\lvert
Y_{i}-\operatorname*{\mathbb{E}}(Y_{i})\rvert^{3})$. Then

$\displaystyle\Pr_{D\sim\mathbb{D}}\big{(}\mathcal{T}_{G(D,w_{\delta})}(V_{B})\text{
is a tangle that contains }V_{S}\big{)}$ $\displaystyle{}\geq{}\
\max\Bigg{\\{}1-\exp\left(-n\cdot\frac{2}{(2\sqrt{2}+3)^{2}}\cdot(3\bar{\nu}(A)-2\sqrt{2}\bar{\nu}(B)\big{)}^{2}\right),$
$\displaystyle\phantom{{}\geq{}\
\max\bigg{\\}}}\Phi_{0,1}\left(\frac{-\sum_{i=1}^{n}\operatorname*{\mathbb{E}}(Y_{i})}{\sqrt{\sum_{i=1}^{n}\operatorname*{Var}(Y_{i})}}\right)-\frac{C\cdot\sum_{i=1}^{n}\rho_{i}}{(\sum_{i=1}^{n}\operatorname*{Var}(Y_{i}))^{\frac{3}{2}}}\Bigg{\\}}$
$\displaystyle\phantom{{}\geq{}\
}-\left(1+\sum_{k=1}^{m}\frac{n_{k}\cdot\nu_{k}(B)}{1-\nu_{k}(B)}\right)\cdot\prod_{k=1}^{m}\big{(}1-\nu_{k}(B)\big{)}^{n_{k}}$

where $C$ is the constant from Theorem 7. As a consequence,

$\Pr_{D\sim\mathbb{D}}\big{(}\mathcal{T}_{G(D,w_{\delta})}(V_{B})\text{ is a
tangle that contains }V_{S}\big{)}=1-e^{-\Omega(n)}.$

###### Proof.

For better readability, let $G\coloneqq G(D,w_{\delta})$ and
$\operatorname*{\mathbb{E}}\coloneqq\operatorname*{\mathbb{E}}_{D\sim\mathbb{D}}$.
As we already observed in the proof of Theorem 16, the set $V_{B}$ induces a
clique in $G$ with $w_{V_{B}}=1$ and hence, by Lemma 4,
$\mathcal{T}_{G}(V_{B})$ is a tangle as soon as $\lvert V_{B}\rvert\geq 2$.
Since $B\subseteq S$, the set $V_{S}$ is a member of $\mathcal{T}_{G}(V_{B})$
as soon as $\frac{2}{9}\lvert V_{B}\rvert^{2}>\kappa_{G}(V_{S})$. By Lemma 18,
this is true if $\frac{2}{9}\lvert V_{B}\rvert^{2}>\frac{1}{4}\lvert
V_{A}\rvert^{2}$ or, equivalently, $2\sqrt{2}\lvert V_{B}\rvert>3\lvert
V_{A}\rvert$. Hence,

$\displaystyle\Pr_{D\sim\mathbb{D}}$ $\displaystyle(\mathcal{T}_{G}\text{ is a
tangle that contains }V_{S})$
$\displaystyle\geq\Pr_{D\sim\mathbb{D}}\left(2\sqrt{2}\lvert
V_{B}\rvert>3\lvert V_{A}\rvert\text{ and }\lvert V_{B}\rvert\geq 2\right)$
$\displaystyle=\Pr_{D\sim\mathbb{D}}\left(2\sqrt{2}\lvert V_{B}\rvert\geq
3\lvert V_{A}\rvert\text{ and }\lvert V_{B}\rvert\geq 2\right)$
$\displaystyle\geq\Pr_{D\sim\mathbb{D}}\left(3\lvert
V_{A}\rvert\mspace{-2.0mu}-\mspace{-2.0mu}2\sqrt{2}\lvert
V_{B}\rvert\mspace{-1.0mu}\leq\mspace{-1.0mu}0\right)\mspace{-2.0mu}+\mspace{-4.0mu}\Pr_{D\sim\mathbb{D}}(\lvert
V_{B}\rvert\mspace{-1.0mu}\geq\mspace{-1.0mu}2)\mspace{-2.0mu}-\mspace{-2.0mu}1\,$

where the second step follows from the fact that $\sqrt{2}$ is irrational, and
the third step is a union bound. Expressing $\lvert V_{A}\rvert$ and $\lvert
V_{B}\rvert$ as a sum of the indicator variables now yields

$\displaystyle 3\lvert V_{A}\rvert-2\sqrt{2}\lvert V_{B}\rvert$
$\displaystyle=3\sum_{i=1}^{n}\cdot\mathds{1}_{A}(X_{i})-2\sqrt{2}\sum_{i=1}^{n}\cdot\mathds{1}_{B}(X_{i})$
$\displaystyle=\sum_{i=1}^{n}\left(3\cdot\mathds{1}_{A}-2\sqrt{2}\cdot\mathds{1}_{B}\right)(X_{i})=\sum_{i=1}^{n}Y_{i}\
.$

Together,

$\Pr\limits_{D\sim\mathbb{D}}\mspace{-3.0mu}\left(\mathcal{T}_{G(D,w_{\delta})}(V_{B})\text{
is a tangle that contains }V_{S}\right)\\\
\geq\Pr\limits_{D\sim\mathbb{D}}\mspace{-3.0mu}\left(\sum\limits_{i=1}^{n}Y_{i}\leq
0\mspace{-3.0mu}\right)+\Pr\limits_{D\sim\mathbb{D}}\left(\lvert
V_{B}\rvert\geq 2\right)-1\ .$

Concerning the bounds on the probability that $\sum_{i=1}^{n}Y_{i}\leq 0$, we
prove two bounds separately and then take the maximum. We first observe that
$Y_{1},\ldots,Y_{n}$ are independent random variables with $-2\sqrt{2}\leq
Y_{i}\leq 3$ for all $i\in[n]$. Furthermore, for
$\bar{Y}=\frac{1}{n}\sum_{i=1}^{n}Y_{i}$, we have

$\displaystyle\operatorname*{\mathbb{E}}\left(\bar{Y}\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\operatorname*{\mathbb{E}}\big{(}(3\cdot\mathds{1}_{A}-2\sqrt{2}\cdot\mathds{1}_{B})(X_{i})\big{)}=\frac{1}{n}\sum_{i=1}^{n}3\nu_{\ell(i)}(A)-2\sqrt{2}\nu_{\ell(i)}(B)$
$\displaystyle=3\bar{\nu}(A)-2\sqrt{2}\bar{\nu}(B)<0.$

Now the first bound follows from Theorem 6 with
$t=-\operatorname*{\mathbb{E}}(\bar{Y})$, since

$\displaystyle\Pr_{D\sim\mathbb{D}}\left(\sum_{i=1}^{n}Y_{i}\leq 0\right)$
$\displaystyle\geq
1-\Pr_{D\sim\mathbb{D}}(\bar{Y}-\operatorname*{\mathbb{E}}(\bar{Y})$
$\displaystyle\geq-\operatorname*{\mathbb{E}}(\bar{Y}))>1-\left(-\frac{2n^{2}\operatorname*{\mathbb{E}}(\bar{Y})^{2}}{\sum_{i=1}^{n}(3+2\sqrt{2})^{2}}\right)$
$\displaystyle=1-\exp\left(-n\cdot\frac{2}{(2\sqrt{2}+3)^{2}}\cdot(3\bar{\nu}(A)-2\sqrt{2}\bar{\nu}(B))^{2}\right)$

and the second bound follows from Theorem 7, since

$\displaystyle\Pr_{D\sim\mathbb{D}}\left(\sum_{i=1}^{n}Y_{i}\leq 0\right)$
$\displaystyle=\Pr_{D\sim\mathbb{D}}\left(\frac{\sum_{i=1}^{n}Y_{i}-\sum_{i=1}^{n}\operatorname*{\mathbb{E}}(Y_{i})}{\sqrt{\sum_{i=1}^{n}\operatorname*{Var}(Y_{i})}}\leq\frac{-\sum_{i=1}^{n}\operatorname*{\mathbb{E}}(Y_{i})}{\sqrt{\sum_{i=1}^{n}\operatorname*{Var}(Y_{i})}}\right)$
$\displaystyle\geq\Phi_{0,1}\left(\frac{-\sum_{i=1}^{n}\operatorname*{\mathbb{E}}(Y_{i})}{\sqrt{\sum_{i=1}^{n}\operatorname*{Var}(Y_{i})}}\right)-\frac{C\cdot\sum_{i=1}^{n}\rho_{i}}{(\sum_{i=1}^{n}\operatorname*{Var}(Y_{i}))^{\frac{3}{2}}}$

For the probability that $\lvert V_{B}\rvert\geq 2$, we can apply Lemma 15,
Part 7. Altogether, we obtain the desired lower bound.

To prove the lower asymptotic bound of $1-e^{-\Omega(n)}$, we first observe
that

$\left(1+\sum_{k=1}^{m}\frac{n_{k}\cdot\nu_{k}(B)}{1-\nu_{k}(B)}\right)\cdot\prod_{k=1}^{m}\big{(}1-\nu_{k}(B)\big{)}^{n_{k}}\\\
=\left(1+n\cdot\sum_{k=1}^{m}\frac{r_{k}\cdot\nu_{k}(B)}{1-\nu_{k}(B)}\right)\cdot\left(\prod_{k=1}^{m}\big{(}1-\nu_{k}(B)\big{)}^{r_{k}}\right)^{n}\mspace{-4.0mu},$

which shows that there are constants $c_{1},c_{2}>0$ and $c_{3}\in(0,1)$ such
that

$\displaystyle\Pr_{D\sim\mathbb{D}}$
$\displaystyle\big{(}\mathcal{T}_{G(D,w_{\delta})}(V_{B})\text{ is a tangle
that contains }V_{S}\big{)}$ $\displaystyle{}\geq{}$ $\displaystyle
1-\exp\left(-n\cdot\frac{2\cdot(3\bar{\nu}(A)-2\sqrt{2}\bar{\nu}(B)\big{)}^{2}}{(2\sqrt{2}+3)^{2}}\right)$
$\displaystyle-\left(1+\sum_{k=1}^{m}\frac{n_{k}\cdot\nu_{k}(B)}{1-\nu_{k}(B)}\right)\cdot\prod_{k=1}^{m}\big{(}1-\nu_{k}(B)\big{)}^{n_{k}}$
$\displaystyle{}={}$ $\displaystyle 1-e^{-c_{1}\cdot n}-(1+c_{2}\cdot n)\cdot
c_{3}^{n}=1-e^{-c_{1}\cdot n}-e^{\ln(1+c_{2}\cdot n)+\ln(c_{3})\cdot n}\ .$

Since $\ln(c_{3})<0$ and $\ln(1+c_{2}\cdot n)=o(n)$, this completes the proof.
∎

Note that the bound derived from Berry-Esseen’s Inequality (Theorem 7) only
yields an asymptotic bound of $1-O(\frac{1}{\sqrt{n}})$. However, when $n$ is
small, it often gives better results than the bound derived from Hoeffding’s
Inequality. Using the union bound with the event $A_{k}$ being
“$\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\frac{\delta}{2}}[\boldsymbol{\mu}_{k}]})$
is a tangle that contains $V_{S}$”, we can apply Theorems 16 and 19 to bound
the probability that the tangles we consider are incomparable.

######  Corollary 20.

Let $\delta>0$, $d,m\in\mathbb{N}_{>0}$ and let
$(r_{1},\boldsymbol{\mu}_{1},\sigma_{1}),\ldots,(r_{m},\boldsymbol{\mu}_{m},\sigma_{m})$
be as in Definition 9. Suppose that there are Borel sets $S_{k_{1},k_{2}}$ for
all $\\{k_{1},k_{2}\\}\in\binom{[m]}{2}$ with
$S_{k_{1},k_{2}}=S_{k_{2},k_{1}}^{c}$. If for each pair $(k_{1},k_{2})$, the
conditions of Theorem 16 with $k=k_{1}$ and $S=S_{k_{1},k_{2}}$ are fulfilled,
then

$\smash{\Pr_{D\sim\mathbb{D}}}\big{(}(\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\frac{\delta}{2}}[\boldsymbol{\mu}_{k}]}))_{k\in[m]}\text{
are pairwise incomparable tangles}\big{)}=1-O\left(\tfrac{1}{n}\right)$

for compatible $n$ and $\ell$ and
$\mathbb{D}=\mathbb{D}[(r_{k},\boldsymbol{\mu}_{k},\sigma_{k})_{k\in[m]},n,\ell]$.
If all $k_{1}$ and $S_{k_{1},k_{2}}$ meet the conditions of Theorem 19, then

$\smash{\Pr_{D\sim\mathbb{D}}}\big{(}(\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\frac{\delta}{2}}[\boldsymbol{\mu}_{k}]}))_{k\in[m]}\text{
are pairwise incomparable tangles}\big{)}=1-e^{-\Omega(n)}\ .$

###  4.2 Computational results

So far, we have seen theorems of the form “If some condition is met, there
will be incomparable tangles with at least probability $P$”. However, it is
not obvious to see for which parameters their conditions are fulfilled and
which bounds they yield. In this section, we provide an analysis of the
implications of our theorems for some explicit parameter sets, i.e., we study
the significance of the theoretically obtained bounds.

We begin our analysis with the case of two Gaussians, starting with an in-
depth study of the one-dimensional setting followed by the generalization to
higher dimensions. Then, we analyse a case of more than two marginals by
studying a mixture of three Gaussians whose means form an equilateral
triangle. We explore reasonable choices for the Borel set $S$ that defines the
candidate low-order cut such that the conditions for our probability bounds
are met also for Gaussian mixtures where the means of the marginals are close
to each other. Since the structural properties of the data only depend on the
ratio of the distances of the means and the standard deviation666The ratio
$s^{2}=\frac{\lambda^{2}}{\sigma^{2}}$ of the smallest distance of means and
the standard deviation is often called signal-to-noise ratio (SNR)., we can
normalize and restrict the following analysis to mixtures where all marginal
distributions have standard deviation 1 or, in the case of a mixture with
different standard deviations, we assume that at least one marginal has
standard deviation 1.

We start with the base case of two one-dimensional Gaussians with means $0$
and $\lambda$ and equal standard deviations $\sigma$ and equally many points
drawn from each. In this setting, we need $\lambda>2\sigma$ in order to have
more than one dense region in the data, because for $\lambda\leq 2\sigma$, the
mean density $\bar{f}$ only has one maximum at $\frac{\lambda}{2}$. As the
low-order cut used to distinguish the tangles, we choose the cut at
$\frac{\lambda}{2}$, so $S=\left(-\infty,\frac{\lambda}{2}\right]$. As shown
in Figure 2, Theorem 19 yields good lower bounds already for small data sets.

This setting can be generalized in three ways. First, we vary the fraction $r$
of data points drawn from one marginal distribution, i.e., we assume $rn$ data
points are drawn from the first marginal and $(1-r)n$ from the second
marginal. Here, the considered cut is at the local minimum of the average
density. The implied probability bounds and bounds on the distance of means
for this case are shown in Figures 2 and 2. Next, we vary the ratio $\alpha$
of the standard deviations, see Figure 2. Again, we separate the regions at
the local minimum of the mean distribution. In both of these first two
generalizations, we can compute the smallest distance of the means where the
conditions of Corollary 20 can be met via the following lemma.

######  Lemma 21.

Let $\lambda,\sigma,\alpha>\mspace{-2.0mu}0$ and
$r_{1}\mspace{-2.0mu}\in\mspace{-2.0mu}(0,1)$. Let $m\coloneqq 2$,
$\mu_{1}\coloneqq 0$, $\mu_{2}\coloneqq\lambda$, $\sigma_{1}\coloneqq\sigma$,
$\sigma_{2}\coloneqq\alpha\cdot\sigma$, $r_{2}\coloneqq 1-r_{1}$. Then with
$c\coloneqq\operatorname{argmin}_{0\leq x\leq\lambda}\bar{f}(x)$ and 10, the
following hold for compatible $n$ and $\ell$ and
$\mathbb{D}=\mathbb{D}[((r,0,\sigma),(1-r,\lambda,\alpha\sigma)),n,\ell]$.

  1. 1.

If $\frac{2}{3}\cdot\min\\{\bar{f}(0),\bar{f}(\lambda)\\}>\bar{f}(c)$, there
is a $\delta>0$ such that

$\smash{\Pr_{D\sim\mathbb{D}}}\left(\begin{matrix}\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\delta/2}[0]})\text{
and }\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\delta/2}[\lambda]})\\\ \text{ are
incomparable tangles}\end{matrix}\right)=1-O\left(\tfrac{1}{n}\right)\ .$

  2. 2.

If $\frac{\sqrt{2}}{3}\cdot\min\\{\bar{f}(0),\bar{f}(\lambda)\\}>\bar{f}(c)$,
there is a $\delta>0$ such that

$\smash{\Pr_{D\sim\mathbb{D}}}\left(\begin{matrix}\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\delta/2}[0]})\text{
and }\mathcal{T}_{G(D,w_{\delta})}(V_{B_{\delta/2}[\lambda]})\\\ \text{ are
incomparable tangles}\end{matrix}\right)=1-e^{-\Omega(n)}\ .$

(a)

(b)

(c)

(d)

Figure 2: Our computational results in the one-dimensional case.
We study the applicability of Theorem 19, where we choose $\delta$ to optimize
the probability bound. In the one-dimensional case, we assume that the means
of the marginal distributions have distance $\lambda$ and the standard
deviations are chosen to be $1$ and $\alpha$. From the first marginal
distribution we draw $rn$ many data points, from the second one, we draw
$(1-r)n$. (a) shows the probability bound dependent on $\lambda$ for different
$n$ in the base case. In (b), we vary the mixing parameters $r$ and plot the
probability bound dependent on $\lambda$ with $n=900$.
(c), (d) show plots of the smallest mean distance $\lambda$ such that the
conditions of Lemma 21 are met. In (c) we vary the mixing parameter $r$ and in
(d), we vary the ratio $\alpha$ between the standard deviations. Fixing
$r=1/2$ and $\alpha=1$, we obtain the bounds $\lambda>2.948$ and
$\lambda>3.397$, respectively.
Note that at some point the bound corresponding to Hoeffding’s Inequality
(Theorem 6) becomes larger than the bounds relating to Theorem 7.

###### Proof sketch.

We observe for $x\in\mathbb{R}$ and $\alpha>0$ that $\lim_{\delta\to
0}\frac{1}{\delta}\bar{\nu}([x-\alpha\cdot\delta,x+\alpha\cdot\delta])=2\alpha\cdot\bar{f}(x)$
and $\lim_{\delta\to
0}\frac{1}{\delta^{2}}\int_{c-\delta}^{c}\int_{c}^{x+\delta}\bar{f}(x)\bar{f}(y)\,dy\,dx=\frac{1}{2}\bar{f}(c)^{2}$.
Thus, by the assumptions, the conditions of Theorems 16 and 19, respectively,
hold in the limit for $\delta\to 0$. Since the conditions of the theorems are
strict inequalities, there must be a $\delta>0$ that satisfies them. ∎

Lastly, we vary the dimension of the data. For dimensions two and three,
Theorem 19 yields probability bounds similar to the one-dimensional case, see
Figure 4 and Figure 4. Since the exact values for
$\bar{\nu}(B_{\frac{\delta}{2}}[\boldsymbol{\mu_{i}}])$ become difficult to
compute in high dimensions, we approximate them by $\bar{\nu}(C)$, where $C$
is the largest hypercube contained in the hyperball as pictured in Figure 3.
We then compute the smallest distance of means $\lambda$ for which the
conditions of Theorem 19 are met, the results are shown in Figure 4. In
accordance with our intuition, they indicate that this approach works well for
low-dimensional data.

(a)

(b)

(c)

Figure 3: A schematic image of the higher-dimensional data distribution
models. We take marginals with equal $\sigma$ and draw equally many points
from each distribution. The red circles represent the means and the associated
hyperballs. In blue, we see the low-order cut, in light blue the area of
points that possibly contribute to the order of the cut. In (a) we have two
marginal distributions. The low-order cut is $S=\\{(x_{1},\ldots,x_{d})\mid
x_{1}\leq\frac{\lambda}{2}\\}$. The approximation of the hyperball as a
hypercube is shown in dark red. (b) and (c) show 3 distributions whose means
are positioned on an equilateral triangle. The cut along the Voronoi cell is
shown in (b), in (c) we see the cut along a cube centered at one of the means.

When we consider more than two Gaussians, the positions of the means become
crucial. If the means are aligned (as is always the case in one dimension),
they are naturally ordered and a cut separating consecutive means also
separates all smaller from all larger means. Also, all distributions around
non-adjacent means only contribute insignificantly to the cut. Hence, the
analysis is essentially like the one for a mixture of just two marginal
distributions.

However, if the means are not aligned, the best choice for the Borel set to
determine the low-order cut is no longer obvious. We demonstrate this with the
example of three two-dimensional Gaussians whose means form an equilateral
triangle. Here, there are several possible choices to define the cuts. Any
straight line separating one of the means from the others will be too close to
one dense region, resulting in a high-order cut. For this reason, we
investigate two alternative cuts: one along the _Voronoi cell_ , that is
$S_{i}=\\{\boldsymbol{x}\mid\lVert\boldsymbol{x}-\boldsymbol{\mu_{i}}\rVert\leq\lVert\boldsymbol{x}-\boldsymbol{\mu_{k}}\rVert\text{
for all }k\neq i\\}$, and one along a square centered at the mean, see Figure
3 and Figure 3. The cut along the Voronoi cell works well for Theorem 16 and
yields the existence of incomparable tangles asymptotically almost surely as
soon as $\lambda>4.1$. Notably, the square approach yields much better results
in the application of Theorem 19, as shown in Figure 4.

(a)

(b)

(c)

(d)

Figure 4: Our computations in higher dimensions.
First we consider a mixture of two types of distributions with mean distance
$\lambda$ (see Figure 3). We plot the probability bounds from Theorem 19
dependent on $\lambda$, where the dimension is two in (a) and three in (b).
In (c) we plot the smallest $\lambda$ such that the conditions of Theorem 16
are met and we get incomparable tangles a.a.s. dependent on the dimension,
using the described approximation.
In (d) we take three distributions whose means form an equilateral triangle
with side length $\lambda$ (see Figure 3). We plot the probability bound from
Theorem 19 for dimension 2 against the side length $\lambda$. The size of the
hypercube is chosen to maximize the resulting lower bound on the probability.
Again we see that at some point the bound corresponding to Hoeffding’s
Inequality (Theorem 6) becomes larger than the bounds relating to Theorem 7.

##  5 Results for the fully connected graph

We also investigate to which extent the theorems derived for the
$\delta$-neighborhood graph in Section 4.1 translate to the fully connected
graph. As the weight function, we take
$\hat{w}_{\sigma}(\boldsymbol{x},\boldsymbol{y})\coloneqq\exp\left(\frac{-\lVert\boldsymbol{x}-\boldsymbol{y}\rVert^{2}}{2\sigma^{2}}\right)$,
where $\sigma$ is the standard deviation of each of the marginal
distributions. Like before, we start by identifying incomparable tangles
induced by hyperballs around the means. Using Lemma 4, as soon as the
hyperball contains at least two data points, there is a tangle for this
region. The order of the tangle depends on the smallest weight among the
contained edges. Let the diameter of the hyperballs be $\Delta$. We observe
that the number of vertices within a hyperball grows with $\Delta$, whereas
the minimum edge weight decreases. This yields an interesting trade-off for
obtaining a good tangle order. Note that, in contrast to the
$\delta$-neighborhood graph, the choice of $\Delta$ does not influence the cut
order.

Again, we first deduce a general bound on the probability that, for a given
separation, the $\frac{\Delta}{2}$-ball around the mean of a distribution
induces a tangle with a prescribed orientation of the separation.

######  Theorem 22.

Let $d,m\in\mathbb{N}_{>0}$. Fix $\sigma>0$ and let
$(r_{1},\boldsymbol{\mu}_{1}),\ldots,(r_{m},\boldsymbol{\mu}_{m})$ as in
Definition 9. Choose $\Delta>0$, $k\in[m]$ and define $B\coloneqq
B_{\frac{\Delta}{2}}[\boldsymbol{\mu_{k}}]$. Let $S\subseteq\mathbb{R}^{d}$ be
a Borel set. If

$\bar{\nu}(B\cap S)>\tfrac{1}{2}\bar{\nu}(B)\text{ and
}\tfrac{2}{9}e^{-\frac{\Delta^{2}}{2\sigma^{2}}}\cdot\bar{\nu}(B)^{2}>\smash{\int_{S}}\smash{\int_{{S}^{\mathsf{c}}}}\hat{w}_{c}(\boldsymbol{x},\boldsymbol{y})\bar{f}(\boldsymbol{x})\bar{f}(\boldsymbol{y})\,d\boldsymbol{y}\,d\boldsymbol{x}\,,$

then for compatible $n$ and $\ell$ and
$\mathbb{D}=\mathbb{D}[(r_{k},\boldsymbol{\mu}_{k},\sigma)_{k\in[m]},n,\ell]$,
it holds that

$\smash{\Pr_{D\sim\mathbb{D}}}\left(\mathcal{T}_{G(D,\hat{w}_{\sigma})}(V_{B})\text{
is a tangle that contains }V_{S}\right)=1-O\left(\tfrac{1}{n}\right)\ .$

###### Proof.

We follow the proof of Theorem 16, but in contrast to the
$\delta$-neighborhood graph, $w_{V_{B}}$ is a random variable for the fully
connected graph. We observe however, that $w_{V_{B}}\geq
e^{\frac{-\Delta^{2}}{2\sigma^{2}}}$ as two points in $B$ have distance at
most $\Delta$. By comparing $\kappa_{G(D,\hat{w}_{\sigma})}(V_{S})$ with the
lower bound on $w_{V_{B}}$ instead of the actual value, the rest of the proof
is analogous to the one of Theorem 16. ∎

As in Section 4, we also want conditions to ensure a faster convergence of the
probabilities. Unfortunately, Lemma 18 does not easily translate to the fully
connected graph in general. Restricting ourselves to the one-dimensional
setting, we find the following suitable inequality.

######  Lemma 23.

Suppose $\sigma>0$, $n\in\mathbb{N}_{>0}$,
$D=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ and $c\in\mathbb{R}$. Then

$\kappa_{G(D,\hat{w}_{\sigma})}\big{(}V_{(-\infty,c]}\big{)}\leq\frac{1}{4}\left(\sum_{i=1}^{n}e^{\frac{-(x_{i}-c)^{2}}{2\sigma^{2}}}\right)^{2}\
.$

###### Proof.

Let $\\{i,j\\}$ be an edge that contributes to the cut, say $i\in
V_{(-\infty,c]}$ and $j\in V_{(c,\infty)}$. Then $x_{i}\leq c<x_{j}$ and hence
$x_{j}-c$ and $c-x_{i}$ are non-negative. This yields
$(x_{j}-x_{i})^{2}=(x_{j}-c+c-x_{i})^{2}\geq(x_{j}-c)^{2}+(c-x_{i})^{2}$ and
hence

$\hat{w}_{\sigma}(x_{i},x_{j})=e^{\frac{-(x_{i}-x_{j})^{2}}{2\sigma^{2}}}\leq
e^{\frac{-(x_{i}-c)^{2}-(c-x_{j})^{2}}{2\sigma^{2}}}=e^{\frac{-(x_{i}-c)^{2}}{2\sigma^{2}}}\cdot
e^{\frac{-(x_{j}-c)^{2}}{2\sigma^{2}}}.$

Using this insight and the inequality $a\cdot b\leq\frac{1}{4}(a+b)^{2}$ for
reals $a$ and $b$, we conclude

$\displaystyle\kappa_{G(D,\hat{w}_{\sigma})}\big{(}V_{(-\infty,c]}\big{)}$
$\displaystyle=\sum_{i\colon x_{i}\leq c}\ \sum_{j\colon
x_{j}>c}e^{\frac{-(x_{i}-x_{j})^{2}}{2\sigma^{2}}}\leq\sum_{i\colon x_{i}\leq
c}\ \sum_{j\colon x_{j}>c}e^{\frac{-(x_{i}-c)^{2}}{2\sigma^{2}}}\cdot
e^{\frac{-(x_{j}-c)^{2}}{2\sigma^{2}}}$ $\displaystyle=\left(\sum_{i\colon
x_{i}\leq
c}e^{\frac{-(x_{i}-c)^{2}}{2\sigma^{2}}}\right)\cdot\left(\sum_{j\colon
x_{j}>c}e^{\frac{-(x_{j}-c)^{2}}{2\sigma^{2}}}\right)$
$\displaystyle\leq\frac{1}{4}\left(\sum_{i\colon x_{i}\leq
c}e^{\frac{-(x_{i}-c)^{2}}{2\sigma^{2}}}+\sum_{j\colon
x_{j}>c}e^{\frac{-(x_{j}-c)^{2}}{2\sigma^{2}}}\right)^{2}$
$\displaystyle=\frac{1}{4}\left(\sum_{i=1}^{n}e^{\frac{-(x_{i}-c)^{2}}{2\sigma^{2}}}\right)^{2}$

as desired. ∎

We are now able to express the question whether a tangle orients a cut using a
sum of independent random variables. This enables us to apply Hoeffding’s
inequality Theorem 6 to get the desired stronger convergence.

######  Theorem 24.

Let $m\in\mathbb{N}_{>0}$. Fix $\sigma>0$ and let
$\mu_{1},\ldots,\mu_{k}\in\mathbb{R}$ and
$r_{1},\ldots,r_{k}\in\mathbb{R}_{>0}$ with $r_{1}+\ldots+r_{k}=1$. Choose
$\Delta>0$, $k\in[m]$ and define
$I\coloneqq[\mu_{k}-\frac{\Delta}{2},\mu_{k}+\frac{\Delta}{2}]$. Let $S$ be
either $(-\infty,c]$ or $(c,\infty)$ for some $c\in\mathbb{R}$ such that
$I\subseteq S$. If

$\frac{\sqrt{2}}{3}\cdot
e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\cdot\bar{\nu}(I)>\sum_{k=1}^{m}\frac{r_{k}}{2\sqrt{2}}\cdot
e^{\frac{-(\mu_{k}-c)^{2}}{4\sigma^{2}}}\ ,$

then, for all compatible $n$ and $\ell$ and
$\mathbb{D}=\mathbb{D}[(r_{k},\mu_{k},\sigma)_{k\in[m]},n,\ell]$,

$\displaystyle\Pr_{D\sim\mathbb{D}}\left(\mathcal{T}_{G(D,\hat{w}_{\sigma})}(V_{I})\text{
is a tangle that contains }V_{S}\right)$ $\displaystyle{}\geq{}\
1-\exp\left(-n\cdot\frac{2\cdot\left(\frac{\sqrt{2}}{3}\cdot
e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\cdot\bar{\nu}(I)-\sum_{k=1}^{m}\frac{r_{k}}{2\sqrt{2}}\cdot
e^{\frac{-(\mu_{k}-c)^{2}}{4\sigma^{2}}}\right)^{2}}{\left(\frac{1}{2}+\frac{\sqrt{2}}{3}\cdot
e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\right)^{2}}\right)$
$\displaystyle\phantom{{}\geq{}\
}-\left(1+\sum_{k=1}^{m}\frac{n_{k}\cdot\nu_{k}(I)}{1-\nu_{k}(I)}\right)\cdot\prod_{k=1}^{m}\big{(}1-\nu_{k}(I)\big{)}^{n_{k}}\
.$

In particular,

$\Pr_{D\sim\mathbb{D}}\left(\mathcal{T}_{G(D,\hat{w}_{\sigma})}(V_{I})\text{
is a tangle that contains }V_{S}\right)=1-e^{-\Omega(n)}\ .$

###### Proof.

For better readability, let $G\coloneqq G(D,\hat{w}_{\sigma})$. As noticed
before, by Lemma 4, $\mathcal{T}_{G}(V_{I})$ is a tangle as soon as $\lvert
V_{I}\rvert\geq 2$. Therefore, we can first use a union bound to obtain

$\Pr_{D\sim\mathbb{D}}\left(\mathcal{T}_{G(D,\hat{w}_{\sigma})}(V_{I})\text{
is a tangle that contains }V_{S}\right)\\\
\geq\Pr_{D\sim\mathbb{D}}\big{(}V_{S}\in\mathcal{T}_{G}(V_{I})\big{)}+\Pr_{D\sim\mathbb{D}}\big{(}\lvert
V_{i}\rvert\geq 2\big{)}-1.$

Since $V_{I}\subseteq V_{S}$ by assumption, $V_{S}$ is a member of
$\mathcal{T}_{G}(V_{I})$ when $\frac{2}{9}w_{V_{I}}\lvert
V_{I}\rvert^{2}>\kappa_{G}(V_{S})$. We observe $w_{V_{I}}\geq
e^{\frac{-\Delta^{2}}{2\sigma^{2}}}$ as two points in $I$ have distance at
most $\Delta$. Setting

$Y_{i}\coloneqq\frac{1}{2}e^{\frac{-(X_{i}-c)^{2}}{2\sigma^{2}}}-\frac{\sqrt{2}}{3}e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\cdot\mathds{1}_{I}(X_{i})\
,$

we can use Lemma 23 to obtain

$\displaystyle\Pr(V_{S}\in\mathcal{T}_{G}(V_{I}))$
$\displaystyle=\Pr\left(\frac{2}{9}w_{V_{I}}\lvert
V_{I}\rvert^{2}>\kappa_{G}(V_{S})\right)$
$\displaystyle\geq\Pr\left(\frac{2}{9}e^{\frac{-\Delta^{2}}{2\sigma^{2}}}\cdot\lvert
V_{I}\rvert^{2}>\frac{1}{4}\left(\sum_{i=1}^{n}e^{\frac{-(X_{i}-c)^{2}}{2\sigma^{2}}}\right)^{2}\right)$
$\displaystyle=\Pr\left(\frac{\sqrt{2}}{3}e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\cdot\lvert
V_{I}\rvert>\frac{1}{2}\sum_{i=1}^{n}e^{\frac{-(X_{i}-c)^{2}}{2\sigma^{2}}}\right)$
$\displaystyle=\Pr\left(\sum_{i=1}^{n}\frac{1}{2}\cdot
e^{\frac{-(X_{i}-c)^{2}}{2\sigma^{2}}}-\frac{\sqrt{2}}{3}e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\cdot\mathds{1}_{I}(X_{i})<0\right)$
$\displaystyle=\Pr\left(\sum_{i=1}^{n}Y_{i}<0\right)\ .$

Since the $Y_{i}$ are independent and for all $i\in[n]$, it holds that
$\frac{\sqrt{2}}{3}e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\leq
Y_{i}\leq\frac{1}{2}$, we can apply Theorem 6. To obtain the expected value,
we then compute

$\operatorname*{\mathbb{E}}\left(e^{\frac{-(X_{i}-c)^{2}}{2\sigma^{2}}}\right)=\int_{\mathbb{R}}e^{\frac{-(x-c)^{2}}{2\sigma^{2}}}\cdot
e^{\frac{-(x-\mu_{\ell(i)})^{2}}{2\sigma^{2}}}\,dx=\frac{1}{\sqrt{2}}\cdot
e^{\frac{-(c-\mu_{\ell(i)})^{2}}{4\sigma^{2}}}\ .$

This yields

$\operatorname*{\mathbb{E}}(Y_{i})=\frac{1}{2\sqrt{2}}\cdot
e^{\frac{-(c-\mu_{\ell(i)})^{2}}{4\sigma^{2}}}-\frac{\sqrt{2}}{3}e^{\frac{-\Delta^{2}}{4\sigma^{2}}}\cdot\nu_{\ell(i)}(X_{i})\
.$

Now Theorem 6 together with Lemma 15, Part 7, gives the desired bound. ∎

Figure 5 shows our computational results for the fully connected graph in the
base case of two one-dimensional Gaussian distributions with means $0$ and
$\lambda$, equal standard deviation $\sigma$, and equally many points drawn
from each marginal. First we compute which distances of means $\lambda$ are
separable with Theorem 22, depending on the interval width $\Delta$, and find
that we must have $\lambda>4.27$.

The preconditions of Theorems 16 and 22 represent the condition that, in
expectation, the order of tangle must be larger than the edge connectivity of
$V_{S}$. Since every subset of data points induces a clique in the fully
connected graph, we bound the size of the interval around the mean that we
consider as a tangle-inducing clique in Lemma 4. Unlike in the case of the
$\delta$-neighborhood graph, this parameter does not influence the value of
the cut, but only influences the order of the tangle induced by the clique. As
it turns out, picking a too narrow interval yields too few points in the
clique and a too wide interval yields a too weak lower bound on the edge
weight of each edge: in both cases, we only obtain a tangle of low order via
Lemma 4. Figure 5 shows the tradeoff between the interval width and the
smallest separable distance of means.

Then we compute the lower bounds on the probability due to Theorem 24. We see
that the distances are higher and the probabilities lower as in the same
setting for the $\delta$-neighborhood graph.

(a)

(a)

Figure 5: Computational results for the fully connected graph. The smallest
distance of means $\lambda$ such that Theorem 22 can be applied, dependent on
the width $\Delta$ of the interval used to define the tangles is shown in (a).
Plot (b) shows the results of applying Theorem 24 for different sizes $n$ of
the data set. The interval width $\Delta$ is chosen to maximize the
probability bound.

##  6 Conclusion

In [22], a precise connection between tangles, a subject from structural graph
theory, and clustering, a central technique in data science, was established.
Our work aims at setting the foundation for an in-depth quantitative analysis
of tangles in data sets as a means to capture soft cluster assignments. To
this end, we have applied tangle theory to sets of data points that are drawn
from multiple Gaussian distributions. For the two standard graph models in
this context, we have found explicit conditions under which, asymptotically
almost surely, incomparable tangles that can be associated with the
participating Gaussian distributions exist. Here, we contribute two things.
First we give a probability bound with exponential convergence to $1$, which
has strong conditions on the distributions but provides a lower bound on the
tangle order. Secondly we provide a probability bound with slower convergence
to $1$, which has weaker assumptions on the data distributions and becomes
meaningful for large data sets.

Future projects shall continue the investigation of the potential of tangles
in data sets. For example, it would be interesting to study the fully
connected graph in more detail and possibly with other tools. More refined
bounds on the tangle order would lead to stronger probability bounds. As
another natural follow-up study, we leave as an open problem to improve on our
probability bounds (or the conditions on the data distributions) in higher
dimensions. To exploit the tangle potential in the Gaussian setting in more
depth, we suggest the theoretical analysis of multiple Gaussian distributions
whose means are in arbitrary position or whose standard deviations differ. In
a next step, the results could be applied to actually recover (with some
bounded error probability) the hidden labels. One can also go beyond Gaussian
mixtures and study other “well-clustered” data.

It can also be worthwhile to approach the problem via a study of branch
decompositions. The duality between tangle orders and orders of branch
decompositions ([37], also [27, Theorem 6.1]) will yield upper bounds on the
probability that tangles of high order exist, which may help in the search for
incomparable tangles.

Finally, regarding the benefit of the formalized connection between clustering
and tangles, there is not only a potential of tangles to yield theoretical
insights such as the presented ones about the existence and quality of
clusters in data sets. Indeed, exploring the connection further, the field of
structural graph theory might benefit from the broad research on fast
approximation algorithms for clustering, possibly yielding efficient
approximations for computing graph tangles or decompositions. However, note
that there may be tangles not stemming from clusters, so clustering algorithms
will not necessarily detect _all_ tangles in the data.

## References

  * [1] I. Adler, G. Gottlob, and M. Grohe.  Hypertree width and related hypergraph invariants.  European Journal of Combinatorics, 28(8):2167–2181, 2007.
  * [2] A. C. Berry.  The accuracy of the gaussian approximation to the sum of independent variates.  Transactions of the American Mathematical Society, 49(1):122–136, 1941.
  * [3] I.-J. Bienaymé.  Considérations à l’appui de la découverte de Laplace sur la loi de probabilité dans la méthode des moindres carrés.  Imprimerie de Mallet-Bachelier, 1853.
  * [4] L. Bozyk, O. Defrain, K. Okrasa, and M. Pilipczuk.  On objects dual to tree-cut decompositions.  CoRR, abs/2103.14667, 2021.
  * [5] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone.  Classification and Regression Trees.  Wadsworth, 1984.
  * [6] J. Carmesin, R. Diestel, M. Hamann, and F. Hundertmark.  Canonical tree-decompositions of finite graphs i. Existence and algorithms.  J. Comb. Theory, Ser. B, 116:1–24, 2016.
  * [7] K. Chaudhuri, S. Dasgupta, and A. Vattani.  Learning mixtures of gaussians using the k-means algorithm.  CoRR, abs/0912.0086, 2009.
  * [8] P. L. Chebyshev.  Des valeurs moyennes.  J. Math. Pures Appl, 12(2):177–184, 1867.
  * [9] V. Cohen-Addad, A. Gupta, A. Kumar, E. Lee, and J. Li.  Tight FPT approximations for k-median and k-means.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [10] V. Cohen-Addad, V. Kanade, F. Mallmann-Trenn, and C. Mathieu.  Hierarchical clustering: Objective functions and algorithms.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 378–397, 2018.
  * [11] S. Dasgupta.  A cost function for similarity-based hierarchical clustering.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 118–127, 2016.
  * [12] J. V. De Oliveira and W. Pedrycz.  Advances in fuzzy clustering and its applications.  John Wiley & Sons, 2007.
  * [13] R. Diestel.  Abstract separation systems.  Order, 35(1):157–170, 2018.
  * [14] R. Diestel.  Tangles: a new paradigm for clusters and types.  CoRR, abs/2006.01830, 2020.
  * [15] R. Diestel, J. Erde, and D. Weißauer.  Structural submodularity and tangles in abstract separation systems.  J. Combin. Theory Ser. A, 167:155–180, 2019.
  * [16] R. Diestel, F. Hundertmark, and S. Lemanczyk.  Profiles of separations: in graphs, matroids, and beyond.  Combinatorica, 39(1):37–75, 2019.
  * [17] R. Diestel and S. Oum.  Unifying duality theorems for width parameters in graphs and matroids (extended abstract).  In Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014. Revised Selected Papers, pages 1–14, 2014\.
  * [18] R. Diestel and S.-i. Oum.  Tangle-tree duality in abstract separation systems.  Adv. Math., 377:107470, 24, 2021.
  * [19] R. Diestel and G. Whittle.  Tangles and the Mona Lisa.  ArXiv, 2016.  arXiv:1603.06652 [math.CO].
  * [20] C. Elbracht, J. Kneip, and M. Teegen.  Trees of tangles in abstract separation systems.  J. Combin. Theory Ser. A, 180:105425, 27, 2021.
  * [21] C.-G. Esseen.  Fourier analysis of distribution functions. a mathematical study of the Laplace-Gaussian law.  Acta Mathematica, 77(1):1–125, 1945.
  * [22] E. Fluck.  Tangles and single linkage hierarchical clustering.  In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, volume 138 of LIPIcs, pages 38:1–38:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [23] E. Fluck.  Tangles and hierarchical clustering.  SIAM Journal on Discrete Mathematics, 38(1):75–92, 2024.
  * [24] J. Geelen, B. Gerards, and G. Whittle.  Tangles, tree-decompositions and grids in matroids.  Journal of Combinatorial Theory, Series B, 99(4):657–667, 2009\.
  * [25] A. C. Giannopoulou, K. Kawarabayashi, S. Kreutzer, and O. Kwon.  The canonical directed tree decomposition and its applications to the directed disjoint paths problem.  CoRR, abs/2009.13184, 2020.
  * [26] C. Giraud and N. Verzelen.  Partial recovery bounds for clustering with the relaxed k-means.  CoRR, abs/1807.07547, 2018.
  * [27] M. Grohe.  Tangled up in blue (a survey on connectivity, decompositions, and tangles).  ArXiv, 2016.  arXiv:1605.06704 [cs.DM].
  * [28] C. Hennig, M. Meila, F. Murtagh, and R. Rocci.  Handbook of cluster analysis.  CRC Press, 2015.
  * [29] W. Hoeffding.  Probability inequalities for sums of bounded random variables.  J. Amer. Statist. Assoc., 58:13–30, 1963.
  * [30] T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas.  Directed tree-width.  J. Comb. Theory, Ser. B, 82(1):138–154, 2001.
  * [31] A. Klenke.  Probability Theory: A Comprehensive Course.  Universitext. Springer-Verlag London, London, UK, 2nd edition, 2014.  Translation from the German language edition.
  * [32] S. Klepper, C. Elbracht, D. Fioravanti, J. Kneip, L. Rendsburg, M. Teegen, and U. von Luxburg.  Clustering with tangles: Algorithmic framework and theoretical guarantees.  J. Mach. Learn. Res., 24:190:1–190:56, 2023.
  * [33] A. Liu and A. Moitra.  Settling the robust learnability of mixtures of gaussians.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 518–531. ACM, 2021.
  * [34] A. Moitra and G. Valiant.  Settling the polynomial learnability of mixtures of gaussians.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 93–102. IEEE Computer Society, 2010.
  * [35] D. Pelleg and A. W. Moore.  Mixtures of rectangles: Interpretable soft clustering.  In C. E. Brodley and A. P. Danyluk, editors, Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28 - July 1, 2001, pages 401–408. Morgan Kaufmann, 2001.
  * [36] B. A. Reed.  Introducing directed tree width.  Electron. Notes Discret. Math., 3:222–229, 1999.
  * [37] N. Robertson and P. D. Seymour.  Graph minors. x. obstructions to tree-decomposition.  Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991\.
  * [38] I. S. Tyurin.  A refinement of the remainder in the Lyapunov theorem.  Theory of Probability & Its Applications, 56(4):693–696, 2012\.
  * [39] U. von Luxburg.  A tutorial on spectral clustering.  Statistics and Computing, 17(4):395–416, 2007.