# Large deviations for subcomplex counts and Betti numbers in multi-parameter
simplicial complexes

Gennady Samorodnitsky  School of Operations Research and Information
Engineering
Cornell University
NY, 14853, USA<EMAIL_ADDRESS>and  Takashi Owada  Department of Statistics
Purdue University
IN, 47907, USA<EMAIL_ADDRESS>
###### Abstract.

We consider the multi-parameter random simplicial complex as a higher
dimensional extension of the classical Erdös-Rényi graph. We investigate
appearance of “unusual” topological structures in the complex from the point
of view of large deviations. We first study upper tail large deviation
probabilities for subcomplex counts, deriving the order of magnitude of such
probabilities at the logarithmic scale precision. The obtained results are
then applied to analyze large deviations for the number of simplices at the
critical dimension and below. Finally, these results are also used to deduce
large deviation estimates for Betti numbers of the complex in the critical
dimension.

###### Key words and phrases:

Large deviations, multi-parameter simplicial complex, Betti number

###### 2010 Mathematics Subject Classification:

Primary 60F17. Secondary 55U05, 60C05, 60F15.

Samorodnitsky’s research is partially supported by the NSF grant DMS-2015242
at Cornell University. Owada’s research is partially supported by the NSF
grant, DMS-1811428 at Purdue University.

##  1\. Introduction

One can view a simplicial complex as a network with connections potentially
involving more than 2 vertices at a time. Given a set $V$ of vertices, an
undirected graph allows for the existence of only edges of the type
$(v_{1},v_{2})$ for $v_{1},v_{2}$ in $V$, while potentially higher-dimensional
“edges” would have the form $(v_{1},\ldots,v_{k})$ with $k\geq 2$ for
$v_{1},\ldots,v_{k}$ in $V$. If $k>2$, this is a hyperedge, which is not
allowed in a graph but is allowed in a hypergraph. A simplicial complex is a
special kind of a hypergraph, in which a subset of hyperdge is itself a
hyperedge. That is, if $(v_{1},\ldots,v_{k})$ with $k>2$ is a hyperedge, then
so is the collection of $k-1$ vertices obtained by removing from
$(v_{1},\ldots,v_{k})$ any one of its $k$ vertices. When describing a
simiplical complex, one typically says that $(v_{1},\ldots,v_{k})$ forms a
$(k-1)$-dimensional simplex (henceforth we call it a $(k-1)$-simplex), and not
a hyperedge.

In a random simplicial complex, the simplices of different dimensions are
added according to a randomized rule. Some of the models of random simplicial
complexes are extensions of the classical Erdös-Rényi random graph, in which
potential edges between two vertices are formed with probability $p$,
independently of other potential edges. Possible rules of constructing a
random simplicial complex include the _flag complex_ (also known as the clique
complex), in which a potential $k$-simplex is formed whenever a set of $k+1$
vertices constitutes a clique in the Erdös-Rényi graph (see e.g., Kahle
(2009)). _The Linial-Meshulam-Wallach complex_ of a fixed maximal dimension
$k$ is a random simplicial complex, in which all of the $(k-1)$-simplices are
present with probability $1$, while the potential $k$-simplices are included
with probability $p$, independently of other $k$-simplices (Linial and
Meshulam (2006); Meshulam and Wallach (2009)). The most general model in this
direction is _the Costa-Farber multi-parameter simplicial complex_ , for which
potential simplices are added inductively in their dimensions; for every
$k=1,2,\dots$, each potential $k$-simplex is included with probability
$p_{k}$, independently of other simplices, only when all of its $(k-1)$-faces
are present (see Costa and Farber (2016, 2017)).

The randomness of the simplicial complexes induces randomness on the
topological structure of the complex and its topological invariants, such as
_the Betti numbers_ and _the Euler characteristic_. The distributions of
topological invariants have been a subject of recent interest for various
models of random simplicial complexes. This includes the existence of a
dominating dimension and central limit theorems for the Euler characteristic;
see e.g. Kahle and Meckes (2013); Thoppe et al. (2016); Fowler (2019);
Kanazawa (2022). Functional limit theorems for a dynamic version of the multi-
parameter model have been established in Owada et al. (2021).

However, the previous work describes only the “usual” topological structure of
random simplicial complexes, in the sense of the “average” behavior and likely
deviations from the “average” behavior of the topological invariants. In
contrast, the primary focus of this paper is in the situations when the
topological structure of the complex is less usual, in the sense of a
topological invariant being far away from the average. Such events are, by
definition, rare but may have an oversized impact on the function of the
network, and they are typically referred to as large deviations events. Such
events are often related to situations when certain subcomplexes appear
significantly more or significantly less than expected. Understanding the
probabilities of such events is sometimes described as the upper (or lower)
tail large deviations problem for a subcomplex count.

Within the context of the Erdös-Rényi random graphs, large deviation problems
for subgraph counts have attracted much attention over the last decade in,
among many others, Chatterjee and Varadhan (2011); Chatterjee and Dembo
(2016); Bhattacharya et al. (2017); Lubetzky and Zhao (2017); Eldan (2018);
Yan (2020); Cook and Dembo (2020). In particular, Chatterjee (2017) gives a
comprehensive presentation, covering various large deviation problems for the
random graph of different degrees of denseness. Moreover, Janson et al. (2004)
developed a general framework for the upper tail large deviation problems for
subgraph counts in the random graph. The combinatorial part of this approach
is based on a result in Alon (1981), and an extension to uniform subhypergraph
counts in a random hypergraph setup is provided in Dudek et al. (2010).

The present work receives much inspiration from Janson et al. (2004) and
addresses the upper tail large deviation problems for subcomplex counts in the
multi-parameter random simplicial complex. Due to its high-dimensional
topological structure, this problem is more involved than the analogous
problems for random graphs. Although some of the results available for the
Erdös-Rényi random graph have not yet been fully extended to the multi-
parameter random simplicial complex, the results we obtain are useful for
understanding certain rare events in the latter complex. For instance, we are
able to describe the upper tail large deviations for the Betti numbers at the
dominating dimensions.

This paper is organized as follows. In Section 2, we present a formal
definition of the multi-parameter random simplicial complex. In Section 3, we
address general upper tail large deviation problem for subcomplex counts.
Section 4 specializes to the large deviation problem for the number of
simplices at the dominating dimension and below, under the setup of Owada et
al. (2021). Finally, Section 5 discusses the upper tail large deviations for
Betti numbers at the dominating dimension.

##  2\. The multi-parameter random simplical complex and the subcomplex count
problem

In this section we formally construct the multi-parameter random simplical
complex introduced in Costa and Farber (2016, 2017). This complex is a model
of an abstract simplicial complex on the alphabet $[n]=\\{1,\ldots,n\\}$,
parametrized by ${\bf p}={\bf p}(n)=(p_{1},\ldots,p_{n-1})\in[0,1]^{n-1}$ . A
simplex (or a face, or a word) in this complex is a nonempty collection of
letters in the alphabet, and the dimension of a simplex is equal to the number
of letters in the word minus 1. The $i$th skeleton of a complex is the
subcomplex consisting of all faces of dimension $i$ or less. The multi-
parameter random simplicial complex is built recursively, starting with the
$[n]$ as the 0th skeleton. For $i=1,\ldots,n-1$, once the $(i-1)$st skeleton
has been constructed, each of the potential $i$-simplices whose boundary is in
that $(i-1)$st skeleton, is added to the complex with probability $p_{i}$,
independently of other potential $i$-simplices. We denote the obtained random
complex by $K\big{(}n;{\bf p}(n)\big{)}=K(n;p_{1},\ldots,p_{n-1})$.

We are interested in the subcomplex counting problem for the multi-parameter
random simplicial complex. Given two simplicial complexes, $F_{1}$ and
$F_{2}$, an ordered copy of $F_{1}$ in $F_{2}$ is an injective simplicial map
from the vertex set of $F_{1}$ to the vertex set of $F_{2}$. In particular,
this map has the property that the vertices of every simplex in $F_{1}$ are
mapped into the vertices of a simplex in $F_{2}$ of the same dimension.
Similarly, an unordered copy of $F_{1}$ in $F_{2}$ is a subcomplex $F_{3}$ of
$F_{2}$, which is isomorphic to $F_{1}$; that is, there is a bijective mapping
between the vertex set of $F_{1}$ and the vertex set of $F_{3}$, such that a
set of vertices forms a simplex in $F_{1}$ if and only if the corresponding
vertex set under this mapping forms a simplex in $F_{3}$. If
$n_{o}(F_{2},F_{1})$ and $n(F_{2},F_{1})$ are the numbers of ordered and
unordered copies of $F_{1}$ in $F_{2}$ correspondingly, then it is clear that
$n_{o}(F_{2},F_{1})/n(F_{2},F_{1})=\\#({\rm Aut}(F_{1}))$, the number of
automorphisms of $F_{1}$ consisting of all permutations of the vertices of
$F_{1}$ preserving the complex.

Let $F$ be a fixed simplicial complex of dimension $k\geq 1$. For $n>k$ and
probabilities ${\bf p}(n)$, we denote by $N_{n}(F)$ and $N_{o,n}(F)$ the
(random) numbers of unordered and ordered copies of $F$ in the multi-parameter
simplicial complex $K(n;p_{1},\ldots,p_{n-1})$, correspondingly. Note that
$p_{i}$ with $i>k$ do not affect $N_{n}(F)$ and $N_{o,n}(F)$, so we may assume
that $p_{i}=0$ for $i>k$ and simply write the complex as
$K(n;p_{1},\ldots,p_{k})$. If we denote for $i=0,1,\ldots,k$,

(2.1) $\displaystyle F_{i}=$ the set of $i$-simplices in $F$, $\displaystyle
s_{i}(F)=$ $\displaystyle\ \text{the number of $i$-simplices in $F$},$

then

(2.2)
$\displaystyle\mu_{o,n}(F):=\mathbb{E}[N_{o,n}(F)]=(n)_{s_{0}(F)}\prod_{i=1}^{k}p_{i}^{s_{i}(F)},$
$\displaystyle\mu_{n}(F):=\mathbb{E}[N_{n}(F)]=\mu_{o,n}(F)/\\#({\rm
Aut}(F)),$

where $(n)_{s_{0}(F)}:=n(n-1)\cdots\bigl{(}n-s_{0}(F)+1\bigr{)}$.

As $n\to\infty$, the copies of $F$ can potentially be found in many (nearly)
independent parts of the multi-parameter simplicial complex
$K(n;p_{1},\ldots,p_{k})$, so one expects that for large $n$ enough,
$N_{n}(F)$ and $N_{o,n}(F)$ do not deviate “too much” from their corresponding
means. Therefore, the upper tail large deviation probabilities

(2.3) $\mathbb{P}\bigl{(}N_{o,n}(F)\geq(1+\varepsilon)\mu_{o,n}(F)\bigr{)},\ \
\varepsilon>0,$

and the lower tail large deviation probabilities

(2.4) $\mathbb{P}\bigl{(}N_{o,n}(F)\leq(1-\varepsilon)\mu_{o,n}(F)\bigr{)},\ \
0<\varepsilon<1,$

are expected to be exponentially small for large $n$ enough. Our subject of
interest is to investigate exactly how small these probabilities are. In this
paper we focus only on the upper tail large deviations in (2.3). An analysis
of the lower tail large deviations in (2.4) is postponed to a future
publication.

##  3\. Upper tail large deviations

Our approach to understanding the upper tail large deviations for subcomplex
counts is inspired by Janson et al. (2004). If $G$ is a fixed simplicial
complex of dimension $k\geq 1$, we denote by $N(m_{0},m_{1},\ldots,m_{k};G)$
the maximum of $n(F,G)$ taken over all simplicial complexes $F$ with
$s_{i}(F)\leq m_{i}$, $i=0,1,\ldots,k$. Clearly,
$N(m_{0},m_{1},\ldots,m_{k};G)=0$ unless $s_{i}(G)\leq m_{i}$,
$i=0,1,\ldots,k$.

The number $N(m_{0},m_{1},\ldots,m_{k};G)$ is often referred to as the
_extremal parameter_ and is related to a certain linear optimization problem
that we now describe. Using the notation in (2.1), we consider the linear
program

(3.1) $\displaystyle\max\sum_{v\in G_{0}}x_{v}$ subject to $\displaystyle
0\leq\sum_{v\in\sigma_{i}}x_{v}\leq\log m_{i},\ \sigma_{i}\in G_{i},\
i=0,1,\ldots,k.$

Denote by $\gamma=\gamma(m_{0},m_{1},\ldots,m_{k};G)$ the optimal value of
this problem.

######  Proposition 3.1.

Assume that $s_{i}(G)\leq m_{i}$, $i=0,1,\ldots,k$. Then, there are finite
positive constants $c(G),C(G)$ that depend only on $G$, such that

(3.2) $c(G)e^{\gamma(m_{0},m_{1},\ldots,m_{k};G)}\leq
N(m_{0},m_{1},\ldots,m_{k};G)\leq C(G)e^{\gamma(m_{0},m_{1},\ldots,m_{k};G)}.$

###### Proof.

We first prove the lower bound in (3.2). Let $\bigl{(}x_{v}^{*},\,v\in
G_{0}\bigr{)}$ be an optimal solution to the linear program (3.1). We
construct a simplicial complex $F$ as follows. Let $c>0$ be a small constant
described in the sequel. We start with a family of disjoint sets
$(V_{v})_{v\in G_{0}}$, where $V_{v}$ consists of $n_{v}:=\lceil
ce^{x_{v}^{*}}\rceil$ points for each $v\in G_{0}$. Define the vertices of $F$
to be the points in the union $\bigcup_{v\in G_{0}}V_{v}$, i.e., we take
$F_{0}=\bigcup_{v\in G_{0}}V_{v}$. Next, for every $j\in\\{1,\dots,k\\}$ and
distinct vertices $v_{1},\dots,v_{j+1}\in G_{0}$, a point set
$(w_{1},\dots,w_{j+1})\in\prod_{i=1}^{j+1}V_{v_{i}}$ forms a $j$-simplex in
$F$ if and only if the vertices $v_{i},\,i=1,\ldots,j+1$, form a $j$-simplex
in $G$.

We claim that if we choose a sufficiently small constant $c>0$ that depends
only on $G$, then it can be assured that

$s_{j}(F)\leq m_{j},\ \ j=0,1,\ldots,k.$

For this purpose, we use the constraints in (3.1). Consider first $s_{0}(F)$.
Suppose first that $s_{0}(G)<m_{0}$; then,

$\displaystyle s_{0}(F)=\sum_{v\in G_{0}}\lceil
ce^{x_{v}^{*}}\rceil\leq\sum_{v\in G_{0}}\bigl{(}ce^{x_{v}^{*}}+1\bigr{)}\leq
s_{0}(G)(cm_{0}+1)\leq m_{0},$

if we choose $c$ to satisfy

$c\leq\frac{1}{s_{0}(G)(1+s_{0}(G))}.$

Suppose next that $s_{0}(G)=m_{0}$. In this case, $e^{x_{v}^{*}}\leq s_{0}(G)$
for each $v\in G_{0}$, so choosing $c\leq 1/s_{0}(G)$ leads to

$s_{0}(F)=\sum_{v\in G_{0}}\lceil ce^{x_{v}^{*}}\rceil=s_{0}(G)=m_{0}.$

Similarly, for any $j=1,\ldots,k$, if $s_{j}(G)<m_{j}$, then

$\displaystyle s_{j}(F)=$ $\displaystyle\sum_{(v_{1},\ldots,v_{j+1})\in
G_{j}}\prod_{i=1}^{j+1}\lceil
ce^{x_{v_{i}}^{*}}\rceil\leq\sum_{(v_{1},\ldots,v_{j+1})\in
G_{j}}\prod_{i=1}^{j+1}\bigl{(}ce^{x_{v_{i}}^{*}}+1\bigr{)}$ $\displaystyle=$
$\displaystyle\sum_{(v_{1},\ldots,v_{j+1})\in
G_{j}}\bigg{(}1+\sum_{i=1}^{j+1}\sum_{A\subset\\{1,\ldots,j+1\\},\\#(A)=i}c^{i}\exp\Big{\\{}\sum_{\ell\in
A}x_{v_{\ell}^{*}}\Big{\\}}\bigg{)}$ $\displaystyle\leq$
$\displaystyle\sum_{(v_{1},\ldots,v_{j+1})\in
G_{j}}\bigg{(}1+\sum_{i=1}^{j+1}c^{i}{j+1\choose i}m_{j}\bigg{)}$
$\displaystyle=$ $\displaystyle
s_{j}(G)\Big{(}1+m_{j}\bigl{(}(1+c)^{j+1}-1\bigr{)}\Big{)}.$

Thus, if we choose $c$ to satisfy

$c\leq\left[\left(\frac{1}{s_{j}(G)(1+s_{j}(G))}+1\right)^{1/(j+1)}-1\right],$

it then holds that $s_{j}(F)\leq m_{j}$, as required. On the other hand, if
$s_{j}(G)=m_{j}$, then for $(v_{1},\dots,v_{j+1})\in G_{j}$, we have
$e^{x_{v_{i}}^{*}}\leq s_{j}(G)$, $i=1,\dots,j+1$; so choosing $c\leq
1/s_{j}(G)$ again leads to

$s_{j}(F)=\sum_{(v_{1},\dots,v_{j+1})\in G_{j}}\prod_{i=1}^{j+1}\lceil
ce^{x_{v_{i}}^{*}}\rceil=s_{j}(G)=m_{j}.$

For the simplicial complex $F$ constructed above, the number of ordered copies
of $G$ in $F$ is at least

$\prod_{v\in G_{0}}n_{v}\geq c^{s_{0}(G)}\exp\Big{\\{}\sum_{v\in
G_{0}}x_{v}^{*}\Big{\\}}=c^{s_{0}(G)}e^{\gamma}.$

We thus conclude that

$N(m_{0},m_{1},\ldots,m_{k};G)\geq N(F,G)\geq\frac{c^{s_{0}(G)}}{\\#({\rm
Aut}(G))}e^{\gamma},$

establishing the lower bound in (3.2).

In order to prove the upper bound in (3.2), we start with the dual problem to
the optimization problem (3.1). It is the linear program

(3.3) $\displaystyle\min\left[\sum_{v\in G_{0}}y_{v}\log
m_{0}+\sum_{i=1}^{k}\sum_{\sigma_{i}\in G_{i}}z^{(i)}_{\sigma_{i}}\log
m_{i}\right]$ subject to $\displaystyle
y_{v}+\sum_{i=1}^{k}\sum_{\sigma_{i}\in G_{i}\atop
v\in\sigma_{i}}z^{(i)}_{\sigma_{i}}\geq 1\ \ \text{for any $v\in G_{0}$,}$
$\displaystyle y_{v}\geq 0,\ z^{(i)}_{\sigma_{i}}\geq 0\ \ \text{for all $v\in
G_{0}$ and $\sigma_{i}\in G_{i},\ i=1,\ldots,k$.}$

The optimal value of the dual problem (3.3) equals
$\gamma=\gamma(m_{0},m_{1},\ldots,m_{k};G)$; that is, it has the same optimal
value as the original linear program in (3.1). For later use, let
$(y_{v}^{*}),\bigl{(}z_{\sigma_{i}}^{(i*)}\bigr{)}$ be an optimal solution to
the dual problem in (3.3), so that

(3.4) $\gamma=\sum_{v\in G_{0}}y_{v}^{*}\log
m_{0}+\sum_{i=1}^{k}\sum_{\sigma_{i}\in G_{i}}z_{\sigma_{i}}^{(i*)}\log
m_{i}.$

Now, let us fix a simplicial complex $F$ of dimension $k$, satisfying
$s_{i}(F)\leq m_{i},\,i=0,1,\ldots,k$. Then, the upper bound in (3.2) is
obtained as an immediate consequence of the bound

(3.5) $n_{o}(F,G)\leq C(G)e^{\gamma}$

for some constant $C(G)$ that does not depend on $F$. For the proof of (3.5),
we consider a partition

(3.6) $F_{0}=\bigcup_{v\in G_{0}}V_{v}$

of the vertex set of $F$ into subsets indexed by the vertices of $G$. Denote
by $\mathcal{H}=\mathcal{H}(F,G)$ the collection of all ordered copies of $G$
in $F$, so that $\\#(\mathcal{H}(F,G))=n_{o}(F,G)$. Further, let
$\mathcal{W}=\mathcal{W}(F,G)$ be a subset of $\mathcal{H}$, such that each
$v\in G_{0}$ is mapped into one of the vertices in $V_{v}$.

We create a random partition (3.6) as follows. To each vertex $w\in F_{0}$,
assign randomly and independently a vertex $U(w)\in G_{0}$. Now, let

$V_{v}=\bigl{\\{}w\in F_{0}:\,U(w)=v\bigr{\\}},\ v\in G_{0}$

(some sets $V_{v}$ may be empty). In this setting, $\mathcal{W}$ is a _random_
subset of $\mathcal{H}$, so that

$\displaystyle\mathbb{E}\bigl{[}\\#(\mathcal{W})\bigr{]}=\sum_{\varphi\in\mathcal{H}}\mathbb{P}(\varphi\in\mathcal{W})=\sum_{\varphi\in\mathcal{H}}\mathbb{P}\Big{(}U\big{(}\varphi(v)\big{)}=v\
\ \text{for each $v\in G_{0}$}\Big{)}=s_{0}(G)^{-s_{0}(G)}n_{o}(F,G).$

This indicates that there exists a _nonrandom_ partition (3.6) of the vertex
set of $F$, for which

(3.7) $\\#(\mathcal{W})\geq s_{0}(G)^{-s_{0}(G)}n_{0}(F,G).$

Fixing a collection $\mathcal{W}$ that satisfies (3.7), we define
$\mathcal{W}_{0}:=\bigl{\\{}H_{0}:\,H\in\mathcal{W}\bigr{\\}}$ to be the
collection of ordered vertex sets of complexes in $\mathcal{W}$, so that
$\\#(\mathcal{W}_{0})=\\#(\mathcal{W})$. For a subset $U\subseteq F_{0}$,
define the trace of $\mathcal{W}_{0}$ on $U$ by

${\rm Tr}(\mathcal{W}_{0},U)=\bigl{\\{}H_{0}\cap
U:\,H_{0}\in\mathcal{W}_{0}\bigr{\\}}.$

We choose a large positive integer $t$ and define

$l_{0}(v)=\lceil ty_{v}^{*}\rceil,\,v\in G_{0},\ \ l_{i}(\sigma_{i})=\lceil
tz_{\sigma_{i}}^{(i*)}\rceil,\,\sigma_{i}\in G_{i},\,i=1,\ldots,k,$

where $y_{v}^{*}$ and $z_{\sigma_{i}}^{(i*)}$ are given in (3.4). Referring to
the partition (3.6) of $F_{0}$ constructed above that satisfies (3.7), we now
construct a family $U_{1},\ldots,U_{s}$ of subsets of $F_{0}$ as follows. Take
each set $V_{v}$ in (3.6) exactly $l_{0}(v)$ times for every $v\in G_{0}$.
Next, for each $\sigma_{i}=\\{v_{1},\ldots,v_{i+1}\\}\in G_{i}$,
$i=1,\ldots,k$, take the union $V_{v_{1}}\cup\ldots\cup V_{v_{i+1}}$ exactly
$l_{i}(\sigma_{i})$ times. Finally, we enumerate these subsets as
$U_{1},\dots,U_{s}$, where

$s=\sum_{v\in G_{0}}l_{0}(v)+\sum_{i=1}^{k}\sum_{\sigma_{i}\in
G_{i}}l_{i}(\sigma_{i}).$

Then, for every $v\in G_{0}$, each of the vertices in $V_{v}$ appears exactly
$l_{0}(v)+\sum_{i=1}^{k}\sum_{\sigma_{i}\in
G_{i},\,v\in\sigma_{i}}l_{i}(\sigma_{i})$ times in the sets
$U_{1},\dots,U_{s}$. By the constraint of the dual problem (3.3),

$\displaystyle l_{0}(v)+\sum_{i=1}^{k}\sum_{\sigma_{i}\in G_{i}\atop
v\in\sigma_{i}}l_{i}(\sigma_{i})\geq
t\bigg{(}y_{v}^{*}+\sum_{i=1}^{k}\sum_{\sigma_{i}\in G_{i}\atop
v\in\sigma_{i}}z^{(i*)}_{\sigma_{i}}\bigg{)}\geq t.$

This implies that every vertex in $F$ appears at least $t$ times in the sets
$U_{1},\ldots,U_{s}$. By Lemma 1.2 in Friedgut and Kahn (1998),

(3.8)
$\displaystyle\bigl{(}\\#(\mathcal{W})\bigr{)}^{t}=\bigl{(}\\#(\mathcal{W}_{0})\bigr{)}^{t}\leq\prod_{m=1}^{s}\\#\bigl{(}{\rm
Tr}(\mathcal{W}_{0},U_{m})\bigr{)}$ $\displaystyle=$ $\displaystyle\prod_{v\in
G_{0}}\left[\\#\bigl{(}{\rm
Tr}(\mathcal{W}_{0},V_{v})\bigr{)}\right]^{l_{0}(v)}\prod_{j=1}^{k}\prod_{\sigma_{j}=\\{v_{1},\ldots,v_{j+1}\\}\in
G_{j}}\left[\\#\bigl{(}{\rm Tr}(\mathcal{W}_{0},V_{v_{1}}\cup\ldots\cup
V_{v_{j+1}})\bigr{)}\right]^{l_{j}(\sigma_{j})}.$

By the definition of $\mathcal{W}$, each $H_{0}\in\mathcal{W}_{0}$ has at most
one element in $V_{v}$ for each $v\in G_{0}$, so

(3.9) $\\#\bigl{(}{\rm Tr}(\mathcal{W}_{0},V_{v})\bigr{)}\leq\\#(V_{v})\leq
s_{0}(F)\leq m_{0}.$

Similarly, for each $\sigma_{j}=\\{v_{1},\ldots,v_{j+1}\\}\in G_{j}$, the
intersection of $H_{0}\in\mathcal{W}_{0}$ and $\bigcup_{i=1}^{j+1}V_{v_{i}}$
either forms a $j$-simplex in $F$ or becomes an empty set. Therefore,

(3.10) $\\#\bigl{(}{\rm Tr}(\mathcal{W}_{0},V_{v_{1}}\cup\ldots\cup
V_{v_{j+1}})\bigr{)}\leq s_{j}(F)\leq m_{j},\ j=1,\ldots,k.$

Substituting the bounds in (3.9) and (3.10) back into (3.8), we have, as
$t\to\infty$,

(3.11) $\displaystyle\\#(\mathcal{W})\leq$ $\displaystyle\prod_{v\in
G_{0}}m_{0}^{l_{0}(v)/t}\prod_{j=1}^{k}\prod_{\sigma_{j}=\\{v_{1},\ldots,v_{j+1}\\}\in
G_{j}}m_{j}^{l_{j}(\sigma_{j})/t}$ $\displaystyle\to$
$\displaystyle\prod_{v\in
G_{0}}m_{0}^{y_{v}^{*}}\prod_{j=1}^{k}\prod_{\sigma_{j}=\\{v_{1},\ldots,v_{j+1}\\}\in
G_{j}}m_{j}^{z^{(j*)}_{\sigma_{j}}}=e^{\gamma},$

where the last equality follows from (3.4). Combining (3.7) and (3.11), we
have

$n_{0}(F,G)\leq s_{0}(G)^{s_{0}(G)}e^{\gamma},$

which establishes the bound (3.5), as desired. ∎

The following lemma is a useful consequence of Proposition 3.1. It is a
higher-dimensional version of Lemma 2.1 in Janson et al. (2004).

######  Lemma 3.2.

Let $H$ be a $k$-dimensional subcomplex of $G$ with $s_{k}(H)>0$. Then, there
exists a constant $C_{H}\in(1,\infty)$ such that if $0\leq m_{1}<m_{2}\leq
m_{0}^{k+1}/s_{k}(G)$,

$\displaystyle N\bigl{(}m_{0},m_{1}s_{1}(G),\ldots,m_{1}s_{k}(G);H\bigr{)}\leq
C_{H}\Big{(}\frac{m_{1}}{m_{2}}\Big{)}^{1/(k+1)}N\bigl{(}m_{0},m_{2}s_{1}(G),\ldots,m_{2}s_{k}(G);H\bigr{)}.$

###### Proof.

It is enough to consider the case $m_{1}>0$. By Proposition 3.1,

(3.12) $\displaystyle
N\bigl{(}m_{0},m_{1}s_{1}(G),\ldots,m_{1}s_{k}(G);H\bigr{)}\leq
C_{1}(H)e^{\gamma_{1}}$

for some $C_{1}(H)\in(1,\infty)$, where

$\displaystyle\gamma_{1}=\max\sum_{v\in H_{0}}x_{v}$ subject to $\displaystyle
0\leq x_{v}\leq\log m_{0},\ v\in H_{0},$
$\displaystyle\sum_{v\in\sigma_{i}}x_{v}\leq\log s_{i}(G)+\log m_{1},\
\sigma_{i}\in H_{i},\,i=1,\ldots,k.$

Let $(x_{v}^{*},\,v\in H_{0})$ be an optimal solution for this problem.
Consider all $v\in H_{0}$ that belong to a $k$-simplex in $H$, and choose
among them a vertex $\tilde{v}\in H_{0}$ with the smallest value of
$x_{v}^{*}$; that is,

$x_{\tilde{v}}^{*}=\min_{\sigma_{k}\in H_{k},\,v\in\sigma_{k}}x_{v}^{*}.$

By the feasibility of $(x_{v}^{*})$, we have

(3.13) $x_{\tilde{v}}^{*}\leq\frac{1}{k+1}\log s_{k}(G)+\frac{1}{k+1}\log
m_{1}.$

Define for $v\in H_{0}$,

$x_{v}^{**}=x_{v}^{*}\ \text{for $v\not=\tilde{v}$},\ \
x_{\tilde{v}}^{**}=x_{\tilde{v}}^{*}+\frac{1}{k+1}\log\frac{m_{2}}{m_{1}}.$

Then for $\sigma_{i}\in H_{i},\,i=1,\ldots,k$, we have

$\displaystyle\sum_{v\in\sigma_{i}}x_{v}^{**}$
$\displaystyle=\sum_{v\in\sigma_{i}}x_{v}^{*}+\frac{1}{k+1}\log\frac{m_{2}}{m_{1}}$
$\displaystyle\leq\log s_{i}(G)+\log
m_{1}+\frac{1}{k+1}\log\frac{m_{2}}{m_{1}}\leq\log s_{i}(G)+\log m_{2},$

while, by (3.13),

$\displaystyle x_{\tilde{v}}^{**}\leq$ $\displaystyle\frac{1}{k+1}\log
s_{k}(G)+\frac{1}{k+1}\log m_{1}+\frac{1}{k+1}\log\frac{m_{2}}{m_{1}}$
$\displaystyle=$ $\displaystyle\frac{1}{k+1}\log s_{k}(G)+\frac{1}{k+1}\log
m_{2}\leq\log m_{0}.$

We thus conclude that $(x_{v}^{**})$ is a feasible solution to the linear
program

$\displaystyle\gamma_{2}=\max\sum_{v\in H_{0}}x_{v}$ subject to $\displaystyle
0\leq x_{v}\leq\log m_{0},\ v\in H_{0},$
$\displaystyle\sum_{v\in\sigma_{i}}x_{v}\leq\log s_{i}(G)+\log m_{2},\
\sigma_{i}\in H_{i},\,i=1,\ldots,k.$

Therefore,

$\gamma_{2}\geq\sum_{v\in
H_{0}}x_{v}^{**}=\gamma_{1}+\frac{1}{k+1}\log\frac{m_{2}}{m_{1}}.$

Appealing once again to Proposition 3.1, as well as (3.12), we have for some
constant $C_{2}(H)\in(0,1)$,

$\displaystyle N\bigl{(}m_{0},m_{2}s_{1}(G),\ldots,m_{2}s_{k}(G);H\bigr{)}\geq
C_{2}(H)e^{\gamma_{2}}\geq
C_{2}(H)\left(\frac{m_{2}}{m_{1}}\right)^{1/(k+1)}e^{\gamma_{1}}$
$\displaystyle\quad\geq\frac{C_{2}(H)}{C_{1}(H)}\left(\frac{m_{2}}{m_{1}}\right)^{1/(k+1)}N\bigl{(}m_{0},m_{1}s_{1}(G),\ldots,m_{1}s_{k}(G);H\bigr{)},$

as required. ∎

For numbers $0\leq p_{i}\leq 1,\,i=1,\ldots,k$, and a simplicial complex $G$
of dimension $k$, denote

$\Psi_{G,n}:=n^{s_{0}(G)}\prod_{i=1}^{k}p_{i}^{s_{i}(G)}\sim\mu_{o,n}(G),\
n\to\infty,$

and define

$\displaystyle M^{*}_{G,n}(p_{1},\ldots,p_{k}):=\max\biggl{\\{}$
$\displaystyle 1\leq m\leq\frac{{n\choose
k+1}}{s_{k}(G)}:N\bigl{(}n,ms_{1}(G),\ldots,ms_{k}(G);H\bigr{)}\leq\Psi_{H,n}$
$\displaystyle\qquad\qquad\qquad\text{for every non-empty subcomplex $H$ of
$G$}\biggr{\\}}.$

The following theorem is the main result of this section. It is an extension
of Theorem 1.2 of Janson et al. (2004) to the multi-parameter random
simplicial complexes. Its statement uses the notation $K_{k,n}$ for the
complete complex of dimension $k$ of $n$ vertices (i.e. a complex on $n$
vertices containing all possible simplices of dimensions $k$ and smaller).

######  Theorem 3.3.

For every $\varepsilon>0$, there exists $C(\varepsilon,G)>0$ so that for all
$n\geq 1$,

(3.14)
$\mathbb{P}\bigl{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\bigr{)}\leq\exp\Bigl{\\{}-C(\varepsilon,G)M^{*}_{G,n}(p_{1},\ldots,p_{k})\Bigr{\\}}.$

Moreover, if $(1+\varepsilon)\mu_{o,n}(G)\leq N\bigl{(}K_{k,n},G\bigr{)}$,
there exists $B(\varepsilon,G)>0$, such that for all $n\geq 2k+1$,

(3.15)
$\displaystyle\mathbb{P}\bigl{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\bigr{)}\geq\frac{1}{4}\left(\prod_{j=1}^{k}p_{j}\right)^{B(\varepsilon,G)M^{*}_{G,n}(p_{1},\ldots,p_{k})}.$

######  Remark 3.4.

Theorem 3.3 identifies the order of magnitude of the upper tail large
deviation probability at the logarithmic scale precision. The logarithmic
order of magnitude differs between the upper bound (3.14) and the lower bound
(3.15) by a factor of $\log\big{(}\prod_{j=1}^{k}p_{j}\big{)}$. We note that
under a common setup $p_{i}=n^{-\alpha_{i}}$ for some
$\alpha_{i}\in[0,\infty]$, $i\geq 1$, as in Section 4 below, the factor
$\log\big{(}\prod_{j=1}^{k}p_{j}\big{)}$ is logarithmic in $n$. In contrast,
the main term $M^{*}_{G,n}(p_{1},\ldots,p_{k})$ typically grows polynomially,
determining largely the order of magnitude of the large deviation probability.

Note also that the condition $(1+\varepsilon)\mu_{o,n}(G)\leq
N\bigl{(}K_{k,n},G\bigr{)}$ is rarely restrictive. In fact, it is equivalent
to $(1+\varepsilon)\prod_{j=1}^{k}p_{j}^{s_{j}(G)}\leq 1$; this, however,
trivially holds whenever $p_{j}\to 0$ as $n\to\infty$ for some $j$.

###### Proof.

We start with proving the upper bound in (3.14). Let $G_{1},\ldots,G_{M}$ be
the ordered copies of $G$ in $K_{k,n}$ where
$M=(n)_{s_{0}(G)}=n(n-1)\cdots\bigl{(}n-s_{0}(G)+1\bigr{)}$. Clearly,

$N_{o,n}(G)=\sum_{j=1}^{M}I_{j},$

where

$I_{j}={\mathbbm{1}}\bigl{\\{}G_{j}\text{ is a subcomplex of
}K(n;p_{1},\ldots,p_{k})\bigr{\\}},\ \ j=1,\ldots,M.$

Therefore, for each $m=1,2\ldots$, we have

(3.16) $\displaystyle\mathbb{E}[N_{o,n}(G)^{m}]=\sum_{1\leq
i_{1},\ldots,i_{m}\leq M}\mathbb{E}\bigl{[}I_{i_{1}}\cdots
I_{i_{m}}\bigr{]}=\sum_{1\leq i_{1},\ldots,i_{m}\leq
M}\prod_{j=1}^{k}p_{j}^{s_{j}(G_{i_{1}}\cup\cdots\cup G_{i_{m}})},$

with $s_{j}(\cdot)$ as in (2.1). For a fixed ${\bf
i}^{(m-1)}=(i_{1},\ldots,i_{m-1})\in\\{1,\dots,M\\}^{m-1}$, denote $F_{{\bf
i}^{(m-1)}}=G_{i_{1}}\cup\cdots\cup G_{i_{m-1}}$. Then (3.16) becomes

$\displaystyle\mathbb{E}[N_{o,n}(G)^{m}]=\sum_{{\bf
i}^{(m-1)}}\prod_{j=1}^{k}p_{j}^{s_{j}(F_{{\bf
i}^{(m-1)}})}\sum_{i_{m}=1}^{M}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(F_{{\bf
i}^{(m-1)}}\cap G_{i_{m}})}.$

For every fixed ${\bf i}^{(m-1)}$, if $F_{{\bf i}^{(m-1)}}\cap G_{i_{m}}$
contains at least one simplex of positive dimension, then this intersection is
isomorphic to some subcomplex $H$ of $G$ of positive dimension. We thus
conclude that

$\displaystyle\mathbb{E}[N_{o,n}(G)^{m}]$ $\displaystyle\leq\sum_{{\bf
i}^{(m-1)}}\prod_{j=1}^{k}p_{j}^{s_{j}(F_{{\bf
i}^{(m-1)}})}\bigg{[}M\prod_{j=1}^{k}p_{j}^{s_{j}(G)}+\sum_{i_{m}:F_{{\bf
i}^{(m-1)}}\cap
G_{i_{m}}\neq\emptyset}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(F_{{\bf
i}^{(m-1)}}\cap G_{i_{m}})}\bigg{]}$ $\displaystyle=\sum_{{\bf
i}^{(m-1)}}\prod_{j=1}^{k}p_{j}^{s_{j}(F_{{\bf
i}^{(m-1)}})}\bigg{[}\mu_{o,n}(G)+\sum_{H\subseteq
G}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}\\#\big{\\{}i:F_{{\bf
i}^{(m-1)}}\cap G_{i}\cong H\big{\\}}\bigg{]},$

where $\mu_{o,n}(G)$ is given in (2.2), and the sum $\sum_{H\subseteq G}$ is
taken over all subcomplexes of $G$ with positive dimension, and $\cong$ means
isomorphism between simplicial complexes. For every subcomplex $H$ of $G$,
there are at most

$\displaystyle N\bigl{(}s_{0}(F_{{\bf i}^{(m-1)}}),s_{1}(F_{{\bf
i}^{(m-1)}}),\ldots,s_{k}(F_{{\bf i}^{(m-1)}});H\bigr{)}\leq
N\bigl{(}n,(m-1)s_{1}(G),\ldots,(m-1)s_{k}(G);H\bigr{)}$

ways to choose an unordered copy of $H$ in $F_{{\bf i}^{(m-1)}}$. To bound the
number of ordered copies of $G$ in $K_{k,n}$ whose intersection with $F_{{\bf
i}^{(m-1)}}$ is isomorphic to $H$ (i.e., $\\#\\{i:F_{{\bf i}^{(m-1)}}\cap
G_{i}\cong H\\}$), notice that each choice of an unordered copy of $H$ in
$F_{{\bf i}^{(m-1)}}$ determines $s_{0}(H)$ vertices in the copy of $G$; thus,
the number of ways to select the remaining vertices of the copy of $G$ is at
most
$\big{(}n-s_{0}(H)\big{)}_{s_{0}(G)-s_{0}(H)}=(n)_{s_{0}(G)}/(n)_{s_{0}(H)}$.
Finally, the vertices of the copy of $G$ can be numbered in at most
$s_{0}(G)!$ ways. From these observations, we conclude that

$\displaystyle\\#\big{\\{}i:F_{{\bf i}^{(m-1)}}\cap G_{i}\cong H\big{\\}}\leq
N\bigl{(}n,(m-1)s_{1}(G),\ldots,(m-1)s_{k}(G);H\bigr{)}\frac{(n)_{s_{0}(G)}}{(n)_{s_{0}(H)}}\,s_{0}(G)!.$

Now (2.2) gives us

$\displaystyle\mathbb{E}[N_{o,n}(G)^{m}]\leq$ $\displaystyle\sum_{{\bf
i}^{(m-1)}}\prod_{j=1}^{k}p_{j}^{s_{j}(F_{{\bf i}^{(m-1)}})}$
$\displaystyle\times\mu_{o,n}(G)\bigg{[}1+s_{0}(G)!\sum_{H\subseteq
G}\frac{N\bigl{(}n,(m-1)s_{1}(G),\ldots,(m-1)s_{k}(G);H\bigr{)}}{\mu_{o,n}(H)}\bigg{]}.$

Using (3.16) with $m$ replaced by $m-1$ results in

$\mathbb{E}[N_{o,n}(G)^{m}]\leq\mathbb{E}[N_{o,n}(G)^{m-1}]\mu_{o,n}(G)\bigg{[}1+s_{0}(G)!\sum_{H\subseteq
G}\frac{N\bigl{(}n,(m-1)s_{1}(G),\ldots,(m-1)s_{k}(G);H\bigr{)}}{\mu_{o,n}(H)}\bigg{]}.$

By the monotonicity of the function $N$ in all of its arguments, an inductive
argument gives us the bound

(3.17)
$\mathbb{E}[N_{o,n}(G)^{m}]\leq\mu_{o,n}(G)^{m}\Biggl{[}1+s_{0}(G)!\sum_{H\subseteq
G}\frac{N\bigl{(}n,(m-1)s_{1}(G),\ldots,(m-1)s_{k}(G);H\bigr{)}}{\mu_{o,n}(H)}\Biggr{]}^{m-1},$

for every $m\geq 1$.

For $\theta\in(0,1)$ to be determined in the sequel, we take $m=\lceil\theta
M^{*}_{G,n}(p_{1},\ldots,p_{k})\rceil=:\lceil\theta M_{G,n}^{*}\rceil$. Note
that by Lemma 3.2,

$\displaystyle N\bigl{(}n,(m-1)s_{1}(G),\ldots,(m-1)s_{k}(G);H\bigr{)}$
$\displaystyle\leq$ $\displaystyle N\bigl{(}n,\theta
M_{G,n}^{*}s_{1}(G),\ldots,\theta M_{G,n}^{*}s_{k}(G);H\bigr{)}$
$\displaystyle\leq$ $\displaystyle
C_{H}\theta^{1/(k+1)}N\bigl{(}n,M_{G,n}^{*}s_{1}(G),\ldots,M_{G,n}^{*}s_{k}(G);H\bigr{)}\leq\theta^{1/(k+1)}C_{H}\Psi_{H,n}.$

Therefore, using (3.17) with $m=\lceil\theta M_{G,n}^{*}\rceil$ and Markov’s
inequality, we obtain for $\varepsilon>0$,

$\displaystyle\mathbb{P}\bigl{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\bigr{)}$
$\displaystyle\leq(1+\varepsilon)^{-\theta
M_{G,n}^{*}}\bigg{[}1+\theta^{1/(k+1)}s_{0}(G)!\sum_{H\subseteq
G}\frac{C_{H}\Psi_{H,n}}{\mu_{o,n}(H)}\bigg{]}^{\theta M_{G,n}^{*}}$
$\displaystyle=(1+\varepsilon)^{-\theta
M_{G,n}^{*}}\bigg{[}1+\theta^{1/(k+1)}s_{0}(G)!\sum_{H\subseteq
G}\frac{C_{H}n^{s_{0}(H)}}{n(n-1)\cdots\bigl{(}n-s_{0}(H)+1\bigr{)}}\bigg{]}^{\theta
M_{G,n}^{*}}$
$\displaystyle\leq\bigg{[}(1+\varepsilon)^{-1}\Big{(}1+\theta^{1/(k+1)}s_{0}(G)^{s_{0}(G)}\sum_{H\subseteq
G}C_{H}\Big{)}\bigg{]}^{\theta M_{G,n}^{*}}.$

Choosing

$0<\theta<\min\bigg{\\{}1,\bigg{(}\frac{\varepsilon}{s_{0}(G)^{s_{0}(G)}\sum_{H\subseteq
G}C_{H}}\bigg{)}^{k+1}\bigg{\\}}$

establishes (3.14).

Our proof of (3.15) is also inspired by an argument in Janson et al. (2004).
Suppose there exist $a_{i}>0,\,i=1,\ldots,k$, $m\geq 1$, and a subcomplex $H$
of $G$, such that

(3.18) $N\bigl{(}n,a_{1}m,\ldots,a_{k}m;H\bigr{)}\geq
2(1+\varepsilon)\Psi_{H,n}.$

This implies that there is a complex $F$ on at most $n$ nodes with
$s_{i}(F)\leq a_{i}m,\,i=1,\ldots,k$, such that

(3.19) $n(F,H)\geq 2(1+\varepsilon)\Psi_{H,n}\geq
2(1+\varepsilon)\mu_{o,n}(H).$

Our first goal is to show that under the assumption (3.18),

(3.20)
$\mathbb{P}\big{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\big{)}\geq\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)+a_{j}m}.$

Given a subcomplex $H$ of $G$ satisfying (3.18), we see that each of the
ordered copies of $G$ in $K_{k,n}$ has a unique corresponding ordered copy of
$H$ in $K_{k,n}$; if the latter is also in $F$, we refer to that ordered copy
of $G$ as being $F$-rooted. Since there are $n_{o}(F,H)=\\#({\rm
Aut}(H))n(F,H)$ ordered copies of $H$ in $F$, the number of $F$-rooted ordered
copies of $G$ in $K_{k,n}$ is

$J:=n_{o}(F,H)\bigl{(}n-s_{0}(H)\bigr{)}_{s_{0}(G)-s_{0}(H)}.$

Denote these ordered copies of $G$ in $K_{k,n}$ by $G_{1},\ldots,G_{J}$. Since
$\\#({\rm Aut}(H))\geq 1$, it follows from (3.19) that

(3.21) $\displaystyle J\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}\geq
2(1+\varepsilon)\mu_{o,n}(H)\bigl{(}n-s_{0}(H)\bigr{)}_{s_{0}(G)-s_{0}(H)}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}=2(1+\varepsilon)\mu_{o,n}(G).$

Let $K_{F}(n;p_{1},\ldots,p_{k})$ be the multi-parameter simplicial complex
$K(n;p_{1},\ldots,p_{k})$ conditioned on $F\subseteq K(n;p_{1},\ldots,p_{k})$.
For $i=1,\ldots,J$, let $Z_{i}$ be the indicator function of the event that
$G_{i}$ is a subcomplex of $K_{F}(n;p_{1},\ldots,p_{k})$. Then,

(3.22) $\mathbb{P}(Z_{i}=1)=\prod_{j=1}^{k}p_{j}^{s_{j}(G_{i}\setminus
F)}\geq\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}.$

Since the rightmost term in (3.22) is independent of $i$, the lower bound in
Lemma 3.3 of Janson et al. (2004) gives us

$\displaystyle\mathbb{P}\bigg{(}N_{o,n}(G)\geq\frac{J}{2}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}\Bigg{|}F\subseteq
K(n;p_{1},\ldots,p_{k})\bigg{)}$ $\displaystyle\geq$
$\displaystyle\mathbb{P}\bigg{(}\sum_{i=1}^{J}Z_{i}\geq\frac{J}{2}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}\bigg{)}\geq\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}\geq\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)}.$

Therefore, by (3.21),

$\displaystyle\mathbb{P}\big{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\big{)}\geq\mathbb{P}\Big{(}N_{o,n}(G)\geq\frac{J}{2}\prod_{j=1}^{k}p_{j}^{s_{j}(G)-s_{j}(H)}\Big{)}$
$\displaystyle\geq$
$\displaystyle\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)}\mathbb{P}\big{(}F\subseteq
K(n;p_{1},\ldots,p_{k})\big{)}$ $\displaystyle=$
$\displaystyle\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)}\prod_{j=1}^{k}p_{j}^{s_{j}(F)}\geq\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)+a_{j}m},$

establishing (3.20), as desired.

Now, we are ready to prove the lower bound in (3.15). Suppose first that

(3.23) $2\big{(}2(1+\varepsilon)C_{H}\big{)}^{k+1}M_{G,n}^{*}\leq
s_{k}(G)^{-1}{n\choose k+1},$

where $C_{H}>1$ is the constant in Lemma 3.2, that is increased, without loss
of generality, to be the nearest positive integer. Then, $M_{G,n}^{*}<\lfloor
s_{k}(G)^{-1}{n\choose k+1}\rfloor$, so there is a subcomplex $H$ of $G$ such
that

$N\Bigl{(}n,\bigl{(}M_{G,n}^{*}+1\bigr{)}s_{1}(G),\ldots,\bigl{(}M_{G,n}^{*}+1\bigr{)}s_{k}(G);H\Bigr{)}>\Psi_{H,n}.$

Therefore, by Lemma 3.2,

$\displaystyle 2(1+\varepsilon)\Psi_{H,n}<$ $\displaystyle
2(1+\varepsilon)N\Bigl{(}n,\bigl{(}M_{G,n}^{*}+1\bigr{)}s_{1}(G),\ldots,\bigl{(}M_{G,n}^{*}+1\bigr{)}s_{k}(G);H\Bigr{)}$
$\displaystyle\leq$ $\displaystyle
2(1+\varepsilon)N\Bigl{(}n,2M_{G,n}^{*}s_{1}(G),\ldots,2M_{G,n}^{*}s_{k}(G);H\Bigr{)}$
$\displaystyle\leq$ $\displaystyle
N\Bigl{(}n,2(2(1+\varepsilon)C_{H})^{k+1}M_{G,n}^{*}s_{1}(G),\ldots,2(2(1+\varepsilon)C_{H})^{k+1}M_{G,n}^{*}s_{k}(G);H\Bigr{)}.$

Since the condition (3.18) is now satisfied with $a_{i}=s_{i}(G)$,
$i=1,\dots,k$, and $m=2\big{(}2(1+\varepsilon)C_{H}\big{)}^{k+1}M_{G,n}^{*}$,
we conclude by (3.20) that

(3.24)
$\displaystyle\mathbb{P}\big{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\big{)}\geq\frac{1}{4}\prod_{j=1}^{k}p_{j}^{s_{j}(G)+2(2(1+\varepsilon)C_{H})^{k+1}M_{G,n}^{*}s_{j}(G)}\geq\frac{1}{4}\bigg{(}\prod_{j=1}^{k}p_{j}\bigg{)}^{B_{1}(\varepsilon,G)M_{G,n}^{*}},$

where

$B_{1}(\varepsilon,G)=\max_{j=1,\ldots,k}s_{j}(G)\Bigl{[}1+2\bigl{(}2(1+\varepsilon)\max_{H\subseteq
G}C_{H}\bigr{)}^{k+1}\Bigr{]}.$

Next, we need to consider the case when (3.23) does not hold. In this case, it
follows from the assumption $(1+\varepsilon)\mu_{o,n}(G)\leq N(K_{k,n},G)$
that, for $n\geq 2k+1$,

(3.25)
$\displaystyle\mathbb{P}\big{(}N_{o,n}(G)\geq(1+\varepsilon)\mu_{o,n}(G)\big{)}\geq\mathbb{P}\big{(}N_{o,n}(G)\geq
N\bigl{(}K_{k,n},G\bigr{)}\big{)}$ $\displaystyle\geq$
$\displaystyle\mathbb{P}\Bigl{(}K(n;p_{1},\ldots,p_{k})=K_{k,n}\Bigr{)}=\prod_{j=1}^{k}p_{j}^{n\choose
j+1}\geq\prod_{j=1}^{k}p_{j}^{n\choose
k+1}\geq\bigg{(}\prod_{j=1}^{k}p_{j}\bigg{)}^{B_{2}(\varepsilon,G)M_{G,n}^{*}},$

where

$B_{2}(\varepsilon,G)=2\bigl{(}2(1+\varepsilon)\max_{H\subseteq
G}C_{H}\bigr{)}^{k+1}s_{k}(G).$

Now, (3.15) follows from (3.24) and (3.25) . ∎

##  4\. Simplices at the critical dimension and below

Distributional limit theorems for the multi-parameter simplicial complex
$K(n;{\bf p})$ were obtained in Owada et al. (2021). These results are
obtained under the assumption

(4.1) $p_{i}=n^{-\alpha_{i}},\ i\geq 1,$

for $\alpha_{i}\in[0,\infty]$, $i\geq 1$. In this section we retain this
assumption and, instead of distributional results, we investigate large
deviation probabilities for the number of certain simplices in $K(n;{\bf p})$.
We will use the general results obtained in the previous section.

We are particularly interested in counting the simplices at or below the
_critical dimension_ of the model. In other words, we consider the simplices
of dimension $k\geq 1$, satisfying

(4.2) $\sum_{i=1}^{k}{k\choose i}\alpha_{i}<1,\ \ \text{ and }\ \
q:=\min\\{i\geq 1:\alpha_{i}>0\\}\leq k;$

this introduces a minor unimportant abuse of notation by conflating the
dimension of the simplex with the largest dimension of an entire complex.
Counting the simplices at the critical dimension is particularly important
since their numbers largely determine the behaviour of the Euler
characteristic of $K(n;{\bf p})$; Thoppe et al. (2016); Owada et al. (2021).

Let $\sigma_{k}$ be a simplex of dimension $k$ satisfying (4.2). The following
proposition, a part of which requires an extra assumption on the parameters,
describes the size of a crucial ingredient in the logarithmic order of
magnitude of the upper tail large deviations probability:
$\mathbb{P}\bigl{(}N_{o,n}(\sigma_{k})>(1+\varepsilon)\mu_{o,n}(\sigma_{k})\bigr{)}$
for $\varepsilon>0$. Notice that the extra assumption (4.3) below will be used
only for proving a lower bound in (4.4).

######  Proposition 4.1.

Suppose that (4.2) holds. In the case of $q<k$, suppose also that for any
$k_{0}=q+1,\ldots,k$,

(4.3)
$\frac{k-q}{k+1}\binom{k+1}{q+1}\alpha_{q}+\sum_{j=q+1}^{k_{0}}{k+1\choose
j+1}\alpha_{j}<k_{0}-q.$

Then, for large enough $n$,

(4.4) $C_{k}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}}\leq
M_{\sigma_{k},n}^{*}\bigl{(}n^{-\alpha_{1}},\ldots,n^{-\alpha_{k}}\bigr{)}\leq
C_{k}n^{q+1-\binom{k}{q}\alpha_{q}}$

for some $C_{k}\geq 1$. In particular, for $\varepsilon>0$ and all large
enough $n$,

(4.5)
$\exp\Bigl{\\{}-C_{k}^{\prime}(\varepsilon)n^{q+1-\binom{k}{q}\alpha_{q}}\log
n\Bigr{\\}}\leq\mathbb{P}\bigl{(}N_{o,n}(\sigma_{k})\geq(1+\varepsilon)\mu_{o,n}(\sigma_{k})\bigr{)}\leq\exp\Bigl{\\{}-C_{k}^{\prime\prime}(\varepsilon)n^{q+1-\binom{k}{q}\alpha_{q}}\Bigr{\\}}$

for some positive constants
$C_{k}^{\prime}(\varepsilon),\,C_{k}^{\prime\prime}(\varepsilon)$.

######  Remark 4.2.

Proposition 4.1 indicates that, at least under an extra condition, it is the
skeleton of dimension $q$, the lowest non-trivial dimension of the complex,
that plays a crucial role in determining the rate of decay of the upper large
deviation probabilities at the critical dimension and below it. The reason
appears to be the fact that “flipping” of a $q$-simplex from “on” to “off” or
vice verse affects the topology of the complex more than does any flipping in
other dimensions. The same phenomenon has already been observed in the central
limit theorem for the simplex counts at the critical dimension; see
Proposition 3.6 in Owada et al. (2021).

######  Remark 4.3.

Suppose $q=1$ in (4.2). Then, if $k=1$, the statement of Proposition 4.1
follows from Corollary 1.7 in Janson et al. (2004). For $k=2$, it is easy to
see that condition (4.3) follows from the subcriticality condition (4.2), but
that is no longer the case for $k\geq 3$. However, if $k=3$, one can still
directly compute the value of
$M_{\sigma_{3},n}^{*}(n^{-\alpha_{1}},n^{-\alpha_{2}},n^{-\alpha_{3}})$ and
verify the inequalities in (4.4), without using condition (4.3). To summarize,
the claim of Proposition 4.1 holds at least for $k\in\\{1,2,3\\}$, under the
assumption (4.2) only. We do not know if one can deduce the same conclusion
for $k\geq 4$.

###### Proof.

Since (4.5) follows from (4.4) and Theorem 3.3, we only need to prove the
bounds in (4.4). We start with the upper bound. Recall that

$M_{\sigma_{k},n}^{*}\bigl{(}n^{-\alpha_{1}},\ldots,n^{-\alpha_{k}}\bigr{)}=\min_{H:\text{
subcomplex of $\sigma_{k}$}}K_{H},$

where for a subcomplex $H$ of $\sigma_{k}$,

(4.6) $\displaystyle K_{H}=\max\biggl{\\{}m\leq{n\choose
k+1}:N\left(n,m{k+1\choose
2},m\binom{k+1}{3},\ldots,m\binom{k+1}{k},m;H\right)\leq\Psi_{H,n}\biggr{\\}}.$

Therefore, to prove the upper bound in (4.4) we only need to detect a specific
subcomplex $H$ of $\sigma_{k}$, such that

(4.7) $K_{H}\leq C_{k}n^{q+1-\binom{k}{q}\alpha_{q}}.$

Let us take $H$ to be the $q$-skeleton of $\sigma_{k}$. For this $H$, in the
obvious notation,

(4.8) $K_{H}=\max\biggl{\\{}m\leq{n\choose k+1}:N\left(n,m{k+1\choose
2},\dots,m\binom{k+1}{q+1};H\right)\leq n^{k+1-{k+1\choose
q+1}\alpha_{q}}\biggr{\\}}.$

By Proposition 3.1,

(4.9) $a_{k}e^{\gamma}\leq N\left(n,m{k+1\choose
2},\dots,m\binom{k+1}{q+1};H\right)\leq b_{k}e^{\gamma}$

for some $a_{k},b_{k}>0$, where

(4.10) $\displaystyle\gamma=\max\sum_{v=1}^{k+1}x_{v}$ subject to
$\displaystyle 0\leq x_{v}\leq\log n,\ v=1,\ldots,k+1,$
$\displaystyle\sum_{v\in\sigma_{i}}x_{v}\leq\log\bigg{\\{}m\binom{k+1}{i+1}\bigg{\\}},\
\ \sigma_{i}\in H_{i},\,i=1,\dots,q.$

First, suppose $\binom{k+1}{q+1}m>n^{q+1}$, in which case, we have
$\binom{k+1}{j+1}m>n^{j+1}$, $j=1,\dots,q$. Then, $x_{v}=\log n$,
$v=1,\dots,k+1$, is easily seen to be an optimal solution to (4.10). It then
follows from (4.9) that

(4.11) $N\left(n,m{k+1\choose 2},\dots,m\binom{k+1}{q+1};H\right)\geq
a_{k}n^{k+1}.$

However, as $\alpha_{q}>0$, there is no $m\in{\mathbb{N}}$ that satisfies
(4.11) and the inequality in (4.8).

Therefore, we only need to consider the case $\binom{k+1}{q+1}m\leq n^{q+1}$.
Then, one can see that

$x_{v}=\frac{1}{q+1}\log\bigg{\\{}m\binom{k+1}{q+1}\bigg{\\}},\ \
v=1,\dots,k+1,$

is an optimal solution to the linear program (4.10), so that

$\gamma=\frac{k+1}{q+1}\log\bigg{\\{}m\binom{k+1}{q+1}\bigg{\\}}.$

Therefore, by (4.9),

$b_{k}^{-\frac{q+1}{k+1}}\binom{k+1}{q+1}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}}\leq
K_{H}\leq
a_{k}^{-\frac{q+1}{k+1}}\binom{k+1}{q+1}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}},$

and (4.7) follows.

We now prove the lower bound in (4.4). For this purpose we need to prove that
for every subcomplex $H$ of $\sigma_{k}$,

(4.12) $K_{H}\geq C_{k}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}}.$

Consider first a subcomplex $H$ of dimension $1,\dots,q-1$. In this case, it
is clear that $\Psi_{H,n}=n^{k+1}$, and thus, $K_{H}=\binom{n}{k+1}$ and
(4.12) trivially holds. Consider next a subcomplex $H$ of dimension $q$. Let
$\bar{H}$ be a $(q+1)$-uniform hypergraph on $k+1$ vertices with its
hyperedges identified as a $q$-simplex in $H$. Given another hypergraph
$\bar{F}$, define $\bar{n}(\bar{F},\bar{H})$ to be the number of unordered
copies (as a hypergraph) of $\bar{H}$ in $\bar{F}$. Define also

$\bar{N}\left(n,m\binom{k+1}{q+1};\bar{H}\right):=\max\bigg{\\{}\bar{n}(\bar{F},\bar{H}):v_{\bar{F}}\leq
n,\ e_{\bar{F}}\leq m\binom{k+1}{q+1}\bigg{\\}},$

where $v_{\bar{F}}$ is the number of vertices in $\bar{F}$ and $e_{\bar{F}}$
the number of hyperedges in $\bar{F}$. Then, by construction, we have

$\bar{N}\left(n,m\binom{k+1}{q+1};\bar{H}\right)\geq
N\left(n,m\binom{k+1}{2},\dots,m\binom{k+1}{q+1};H\right).$

By virtue of this inequality together with $v_{\bar{H}}=k+1$ and
$e_{\bar{H}}=s_{q}(H)$,

(4.13) $\displaystyle K_{H}$
$\displaystyle=\max\bigg{\\{}m\leq\binom{n}{k+1}:N\left(n,m\binom{k+1}{2},\dots,m\binom{k+1}{q+1};H\right)\leq
n^{k+1-s_{q}(H)\alpha_{q}}\bigg{\\}}$
$\displaystyle\geq\max\bigg{\\{}m\leq\binom{n}{k+1}:\bar{N}\left(n,m\binom{k+1}{q+1};\bar{H}\right)\leq
n^{v_{\bar{H}}}p_{q}^{e_{\bar{H}}}\bigg{\\}}.$

Observe that $\bar{H}$ is seen to be a subhypergraph of a
$\binom{k}{q}$-regular, $(q+1)$-uniform hypergraph. Moreover, by (4.2),

$p_{q}=n^{-\alpha_{q}}\geq
n^{-\binom{k}{q}^{-1}}>n^{-(q+1)\binom{k}{q}^{-1}}.$

Hence, Proposition 4.3 in Dudek et al. (2010) implies that the last quantity
in (4.13) is at least

$Cn^{q+1}p_{q}^{\binom{k}{q}}=Cn^{q+1-\binom{q}{k}\alpha_{q}},$

for some constant $C$, as desired for (4.12).

Now, it remains to establish (4.12) for subcomplexes $H$ of dimension
$k_{0}=q+1,\ldots,k$. By (4.6), we need to show that there exists $C_{k}>0$
such that for any subcomplex $H$ of $\sigma_{k}$ on $k+1$ vertices, and all
$n$ large enough,

$\displaystyle N\left(n,\lceil
C_{k}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}}\rceil{k+1\choose 2},\ldots,\lceil
C_{k}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}}\rceil{k+1\choose
k_{0}+1};H\right)\leq n^{k+1-\sum_{j=q}^{k_{0}}s_{j}(H)\alpha_{j}}.$

It follows from Proposition 3.1, together with the dual formulation (3.3),
that for a given subcomplex $H$ and $n$ large enough, it is sufficient to
exhibit non-negative numbers $y_{v},\,v=1,\ldots,k+1$ and
$z_{\sigma_{i}}^{(i)},\,\sigma_{i}\in H_{i},\,i=1,\ldots,k_{0}$, such that

(4.14) $y_{v}+\sum_{i=1}^{k_{0}}\sum_{\sigma_{i}\in H_{i}\atop
v\in\sigma_{i}}z^{(i)}_{\sigma_{i}}\geq 1\ \ \text{for any $v=1,\ldots,k+1$},$

and

(4.15) $\displaystyle\sum_{v=1}^{k+1}y_{v}\log
n+\sum_{i=1}^{k_{0}}\sum_{\sigma_{i}\in
H_{i}}z^{(i)}_{\sigma_{i}}\log\left(\lceil
C_{k}^{-1}n^{q+1-\binom{k}{q}\alpha_{q}}\rceil{k+1\choose i+1}\right)$
$\displaystyle\leq$
$\displaystyle\Big{(}k+1-\sum_{j=q}^{k_{0}}s_{j}(H)\alpha_{j}\Big{)}\log n+B,$

where $B$ is a $k$-dependent constant. It is clear that if we can choose these
numbers in such a way that

(4.16)
$\sum_{v=1}^{k+1}y_{v}+\Big{(}q+1-\binom{k}{q}\alpha_{q}\Big{)}\sum_{i=1}^{k_{0}}\sum_{\sigma_{i}\in
H_{i}}z^{(i)}_{\sigma_{i}}<k+1-\sum_{j=q}^{k_{0}}s_{j}(H)\alpha_{j},$

then (4.15) will be satisfied for large $n$, regardless of the constant
$C_{k}$ above. Specifically, we choose the numbers $(y_{v})$ and
$(z_{\sigma_{i}}^{(i)})$ as follows.

$\displaystyle y_{v}=1-\frac{s_{k_{0},v}}{s_{k_{0}}(H)},\ v=1,\ldots,k+1,$
$\displaystyle z^{(k_{0})}_{\sigma_{k_{0}}}=\frac{1}{s_{k_{0}}(H)},\ i=k_{0},\
\ \ z^{(i)}_{\sigma_{i}}=0,\,i\not=k_{0},$

where for a vertex $v$, $s_{k_{0},v}$ is the number of $k_{0}$-simplices in
$H$ to which $v$ belongs. It is elementary to check that these variables
satisfy the constraints in (4.14) as equalities. Moreover, it is evident that

$\sum_{i=1}^{k_{0}}\sum_{\sigma_{i}\in H_{i}}z^{(i)}_{\sigma_{i}}=1,$

while

$\displaystyle\sum_{v=1}^{k+1}y_{v}=k+1-\frac{1}{s_{k_{0}}(H)}\sum_{v=1}^{k+1}s_{k_{0},v}=k+1-(k_{0}+1)=k-k_{0},$

since every $k_{0}$-simplex contributes to exactly $k_{0}+1$ vertices.
Therefore, (4.16) reduces to

(4.17)
$k-k_{0}+q+1-\binom{k}{q}\alpha_{q}<k+1-\sum_{j=q}^{k_{0}}s_{j}(H)\alpha_{j}.$

Since

$s_{j}(H)\leq{k+1\choose j+1},\ \ \ j=q,\ldots,k_{0},$

(4.17) follows from (4.3). ∎

##  5\. The Betti number at the critical dimension

In this section we will use the results of Section 4 to derive large deviation
results for the Betti number at the critical dimension. We still assume that
the probabilities $(p_{i},\,i\geq 1)$ are given by (4.1). Recall that a
dimension $k^{*}\geq 1$ is called critical if

(5.1) $\sum_{i=1}^{k^{*}}{k^{*}\choose
i}\alpha_{i}<1<\sum_{i=1}^{k^{*}+1}{k^{*}+1\choose i}\alpha_{i},\ \ \text{ and
}\ \ q\leq k^{*};$

see Fowler (2019); Owada et al. (2021). We consider the Betti number
$\beta_{k^{*},n}$ at the critical dimension. By the Morse inequalities (see
e.g. Exercise 1, p. 61 in Munkres (1984)), for any dimension $j$,

(5.2)
$N_{n}(\sigma_{j})-N_{n}(\sigma_{j-1})-N_{n}(\sigma_{j+1})\leq\beta_{j,n}\leq
N_{n}(\sigma_{j}),$

where $N_{n}(\sigma_{j})$ is the number of $j$-simplices in the multi-
parameter simplicial complex. It follows from Proposition 3.1 in Owada et al.
(2021) that

(5.3)
$\mathbb{E}\bigl{[}N_{n}(\sigma_{j})\bigr{]}\sim\frac{n^{\tau_{j}}}{(j+1)!},\
\ \ n\to\infty,$

with

$\tau_{j}=j+1-\sum_{i=1}^{j}{j+1\choose i+1}\alpha_{i},\ \ j=1,2,\ldots,$

and the sequence $\tau_{1},\tau_{2},\ldots$ reaches its unique maximum at the
critical dimension $k^{*}$. It thus follows from (5.2) and (5.3) that

$\mathbb{E}\bigl{[}\beta_{k^{*},n}\bigr{]}\sim\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!},\
\ \ n\to\infty.$

The following theorem considers the upper tail large deviations for
$\beta_{k^{*},n}$. An extra condition is needed.

######  Theorem 5.1.

Under the conditions of Proposition 4.1, assume also that

(5.4)
$\sum_{i=q}^{k^{*}+1}\binom{k^{*}+1}{i}\alpha_{i}-1\geq\frac{q(k^{*}+2)!}{(q+1)!(k^{*}+1-q)!(k^{*}+1)}\,\alpha_{q}.$

Then for any $\varepsilon>0$, there exist positive constants
$C_{1}(\varepsilon),\,C_{2}(\varepsilon)>0$, such that

(5.5) $\exp\Big{\\{}-C_{1}(\varepsilon)n^{q+1-\binom{k^{*}}{q}\alpha_{q}}\log
n\Big{\\}}\leq\mathbb{P}\left(\beta_{k^{*},n}\geq(1+\varepsilon)\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!}\right)\leq\exp\Big{\\{}-C_{2}(\varepsilon)n^{q+1-\binom{k^{*}}{q}\alpha_{q}}\Big{\\}}$

for all $n$ large enough.

###### Proof.

Using (5.2) and Proposition 4.1, we have

$\displaystyle\mathbb{P}\left(\beta_{k^{*},n}\geq(1+\varepsilon)\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!}\right)\leq\mathbb{P}\left(N_{n}(\sigma_{k^{*}})\geq(1+\varepsilon)\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!}\right)\leq\exp\Bigl{\\{}-C(\varepsilon)n^{q+1-\binom{k^{*}}{q}\alpha_{q}}\Bigr{\\}},$

for some constant $C(\varepsilon)>0$. This proves the upper bound in (5.5).

To prove the lower bound, let $D$ be a positive constant to be determined in a
moment and take

$m=\Bigl{\lceil}(D(1+\varepsilon))^{1/(k^{*}+1)}n^{1-\frac{1}{q+1}\binom{k^{*}}{q}\alpha_{q}}\Bigr{\rceil}.$

Fix arbitrary $m$ vertices out of $n$ (say, the vertices numbered
$1,\ldots,m$). Let $A$ be the event for which all ${m\choose q+1}$ simplices
of dimension $q$ based on these $m$ vertices are present in $K(n;{\bf p})$.
Given a simplicial complex, its simplex is said to be _free_ if it is not in
the boundary of any simplex of a larger dimension in that complex. Define
$F_{k^{*},n}$ to be the number of free $k^{*}$-simplices in $K(n;{\bf p})$.
Then, conditionally on $A$, a set of $k^{*}+1$ vertices in $\\{1,\dots,m\\}$
forms a free $k^{*}$-simplex in $K(n;{\bf p})$ with probability

(5.6) $\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}\Big{(}1-\prod_{i=q+1}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{m-(k^{*}+1)}\Big{(}1-\prod_{i=q}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{n-m}.$

Note that the probability (5.6) is independent of the choice of $k^{*}+1$
vertices in $\\{1,\dots,m\\}$. Since there are ${m\choose k^{*}+1}$ such
potential free $k^{*}$-simplices in $\\{1,\dots,m\\}$, it follows from Lemma
3.3 in Janson et al. (2004) that

$\displaystyle\mathbb{P}\bigg{(}F_{k^{*},n}\geq\frac{1}{2}{m\choose
k^{*}+1}\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}\Big{(}1-\prod_{i=q+1}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{m-(k^{*}+1)}\Big{(}1-\prod_{i=q}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{n-m}\,\bigg{|}\,A\bigg{)}$
$\displaystyle\geq\frac{1}{4}\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}\Big{(}1-\prod_{i=q+1}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{m-(k^{*}+1)}\Big{(}1-\prod_{i=q}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{n-m}.$

It follows from (5.4) and the criticality condition (5.1) that

$\displaystyle\Big{(}1-\prod_{i=q+1}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{m-(k^{*}+1)}\Big{(}1-\prod_{i=q}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{n-m}$
$\displaystyle\geq$
$\displaystyle\Big{(}1-n^{-\sum_{i=q+1}^{k^{*}+1}\binom{k^{*}+1}{i}\alpha_{i}}\Big{)}^{m}\Big{(}1-n^{-\sum_{i=q}^{k^{*}+1}\binom{k^{*}+1}{i}\alpha_{i}}\Big{)}^{n}$

is bounded away from $0$ (by some constant, say, $\rho$). Thus, choosing
$D>6/\rho$, one can obtain the following bound:

$\displaystyle\frac{1}{2}{m\choose
k^{*}+1}\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}\Big{(}1-\prod_{i=q+1}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{m-(k^{*}+1)}\Big{(}1-\prod_{i=q}^{k^{*}+1}p_{i}^{\binom{k^{*}+1}{i}}\Big{)}^{n-m}$
$\displaystyle\geq\frac{\rho
m^{k^{*}+1}}{3(k^{*}+1)!}\,\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}\geq\frac{D\rho(1+\varepsilon)}{3(k^{*}+1)!}\,n^{\tau_{k^{*}}}>2(1+\varepsilon)\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!}.$

Now, combining all of these results gives us

$\displaystyle\mathbb{P}\left(F_{k^{*},n}\geq
2(1+\varepsilon)\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!}\right)$
$\displaystyle\geq\frac{\rho}{4}\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}\mathbb{P}(A)=\frac{\rho}{4}\prod_{i=q+1}^{k^{*}}p_{i}^{{k^{*}+1\choose
i+1}}p_{q}^{\binom{m}{q+1}}$
$\displaystyle=\frac{\rho}{4}\exp\left\\{-\left(\sum_{i=q+1}^{k^{*}}{k^{*}+1\choose
i+1}\alpha_{i}+{m\choose q+1}\alpha_{q}\right)\log n\right\\}$
$\displaystyle\geq\frac{\rho}{4}\exp\left\\{-C(\varepsilon)n^{q+1-\binom{k^{*}}{q}\alpha_{q}}\log
n\right\\},$

for some constant $C(\varepsilon)>0$.

Note that the indicator function of each free $k^{*}$-simplex is an
independent $k^{*}$-dimensional cocycle. If we denote by $\gamma_{k^{*},n}$
the rank of the group of $k^{*}$-dimensional cocycles in $K(n;{\bf p})$, then
we have proved that for some constant $C(\varepsilon)>0$,

(5.7) $\mathbb{P}\left(\gamma_{k^{*},n}\geq
2(1+\varepsilon)\frac{n^{\tau_{k^{*}}}}{(k^{*}+1)!}\right)\geq\frac{\rho}{4}\exp\left\\{-C(\varepsilon)n^{q+1-\binom{k^{*}}{q}\alpha_{q}}\log
n\right\\}.$

In order to deduce the lower bound in (5.5) from (5.7), we only need to show
that the rank of the group of $k^{*}$-dimensional coboundaries in $K(n;{\bf
p})$ exceeds $(1+\varepsilon)n^{\tau_{k^{*}}}/(k^{*}+1)!$ only on an event
whose probability is of smaller order than the probability in (5.7). The rank
of the latter group does not exceed the rank of the group of
$(k^{*}-1)$-dimensional cochains in $K(n;{\bf p})$, which is, of course, equal
to the number $N_{n}(\sigma_{k^{*}-1})$ of $(k^{*}-1)$-simplices in $K(n;{\bf
p})$.

We know from Proposition 3.1 in Owada et al. (2021) that

$\mathbb{E}[N_{n}(\sigma_{k^{*}-1})]\sim\frac{n^{\tau_{k^{*}-1}}}{k^{*}!}=o\bigl{(}n^{\tau_{k^{*}}}\bigr{)},\
\ \ n\to\infty,$

by the criticality of the dimension $k^{*}$. It remains to notice that for any
$\varepsilon>0$,

$\displaystyle\mathbb{P}\bigl{(}N_{n}(\sigma_{k^{*}-1})\geq(1+\varepsilon)\mathbb{E}[N_{n}(\sigma_{k^{*}-1})]\bigr{)}\leq\exp\bigl{\\{}-Cn^{q+1-\binom{k^{*}-1}{q}\alpha_{q}}\bigr{\\}}$

by the upper bound in (4.5). The right-hand side above exhibits a smaller
order than the probability in (5.7), as required. ∎

## References

  * Alon (1981) N. Alon.  On the number of subgraphs of prescribed type of graphs with a given number of edges.  _Israel Journal of Mathematics_ , 38:116–130, 1981.
  * Bhattacharya et al. (2017) B. B. Bhattacharya, S. Ganguly, E. Lubetzky, and Y. Zhao.  Upper tails and independence polynomials in random graphs.  _Advances in Mathematics_ , 319:313–347, 2017.
  * Chatterjee (2017) S. Chatterjee.  _Large Deviations for Random Graphs_.  Springer, 2017.
  * Chatterjee and Dembo (2016) S. Chatterjee and A. Dembo.  Nonlinear large deviations.  _Advances in Mathematics_ , 299:396–450, 2016.
  * Chatterjee and Varadhan (2011) S. Chatterjee and S.R.S. Varadhan.  The large deviation principle for the Erdös-Rényi random graph.  _European Journal of Combinatorics_ , 32:1000–1017, 2011\.
  * Cook and Dembo (2020) N. Cook and A. Dembo.  Large deviations of subgraph counts for sparse Erdös–Rényi graphs.  _Advances in Mathematics_ , 373:107289, 2020.
  * Costa and Farber (2016) A. Costa and M. Farber.  Large random simplicial complexes, I.  _Journal of Topology and Analysis_ , 8, 2016.
  * Costa and Farber (2017) A. Costa and M. Farber.  Large random simplicial complexes, III the critical dimension.  _Journal of Knot Theory and Its Ramifications_ , 26, 2017.
  * Dudek et al. (2010) A. Dudek, J. Polcyn, and A. Ruciński.  Subhypergraph counts in extremal and random hypergraphs and the fractional $q$-independence.  _Journal of Combinatorial Optimization_ , 19:184–199, 2010\.
  * Eldan (2018) R. Eldan.  Gaussian-width gradient complexity, reverse log-sobolev inequalities and nonlinear large deviations.  _Geometric and Functional Analysis volume_ , 28:1548–1596, 2018.
  * Fowler (2019) C. F. Fowler.  Homology of multi-parameter random simplicial complexes.  _Discrete & Computational Geometry_, 62:87–127, 2019\.
  * Friedgut and Kahn (1998) E. Friedgut and J. Kahn.  On the number of copies of one hypergraph in another.  _Israel Journal of Mathematics_ , 105:251–256, 1998.
  * Janson et al. (2004) S. Janson, K. Oleszkiewicz, and A. Ruciński.  Upper tails for subgraph counts in random graphs.  _Israel Journal of Mathematics_ , 142:61–92, 2004.
  * Kahle (2009) M. Kahle.  Topology of random clique complexes.  _Discrete Mathematics_ , 309:1658–1671, 2009.
  * Kahle and Meckes (2013) M. Kahle and E. Meckes.  Limit theorems for Betti numbers of random simplicial complexes.  _Homology, Homotopy and Applications_ , 15:343–374, 2013\.
  * Kanazawa (2022) S. Kanazawa.  Law of large numbers for betti numbers of homogeneous and spatially independent random simplicial complexes.  _Random Structures & Algorithms_, 60:68–105, 2022.
  * Linial and Meshulam (2006) N. Linial and R. Meshulam.  Homological connectivity of random 2-complexes.  _Combinatorica_ , 26:475–487, 2006.
  * Lubetzky and Zhao (2017) E. Lubetzky and Y. Zhao.  On the variational problem for upper tails in sparse random graphs.  _Random Structures & Algorithms_, 50:420–436, 2017.
  * Meshulam and Wallach (2009) R. Meshulam and N. Wallach.  Homological connectivity of random $k$-dimensional complexes.  _Random Structures & Algorithms_, 34:408–417, 2009.
  * Munkres (1984) J. R. Munkres.  _Elements of Algebraic Topology_.  Addison-Wesley Publishing Company, Menlo Park, CA, 1984.
  * Owada et al. (2021) T. Owada, G. Samorodnitsky, and G. Thoppe.  Limit theorems for topological invariants of the dynamic multi-parameter simplicial complex.  _Stochastic Processes and Their Applications_ , 138:56–95, 2021.
  * Thoppe et al. (2016) G. C. Thoppe, D. Yogeshwaran, and R. J. Adler.  On the evolution of topology in dynamic clique complexes.  _Advances in Applied Probability_ , 48:989–1014, 2016.
  * Yan (2020) J. Yan.  Nonlinear large deviations: beyond the hypercube.  _The Annals of Applied Probability_ , 30:812–846, 2020\.


# Improve Cost Efficiency of Active Learning over Noisy Dataset

Zan-Kai Chong _Independent Researcher_ Malaysia<EMAIL_ADDRESS>Hiroyuki
Ohsaki _School of Science and Technology
Kwansei Gakuin University_ Japan<EMAIL_ADDRESS>Bryan Ng _School of
Engineering & Computer Science
Victoria University of Wellington_ New Zealand<EMAIL_ADDRESS>
###### Abstract

Active learning is a learning strategy whereby the machine learning algorithm
actively identifies and labels data points to optimize its learning. This
strategy is particularly effective in domains where an abundance of unlabeled
data exists, but the cost of labeling these data points is prohibitively
expensive. In this paper, we consider cases of binary classification, where
acquiring a positive instance incurs a significantly higher cost compared to
that of negative instances. For example, in the financial industry, such as in
money-lending businesses, a defaulted loan constitutes a positive event
leading to substantial financial loss. To address this issue, we propose a
shifted normal distribution sampling function that samples from a wider range
than typical uncertainty sampling. Our simulation underscores that our
proposed sampling function limits both noisy and positive label selection,
delivering between 20% and 32% improved cost efficiency over different test
datasets.

##  I Introduction

Active learning is a specialized form of machine learning that aims to
optimize the learning process by intelligently selecting the data points that
are most beneficial for model training [1, 2, 3]. Unlike traditional
supervised learning, which uses all available labeled examples, active
learning focuses using data points where the model is most uncertain and hence
stands to gain the most information. This approach is especially valuable in
scenarios where labeled data is scarce or expensive to obtain, such as in
medical imaging, natural language processing, or robotics.

Building on this foundational concept, uncertainty sampling emerged as one of
the earliest and most influential techniques in active learning. Initially
popularized by Lewis [4], this approach showed promise in enhancing the
performance of text classification models. The method was later expanded upon
by Schohn and Cohn [5], who applied it to Support Vector Machine (SVM)
classification, further solidifying its role as a potent tool for model
improvement. Over the years, uncertainty sampling has been extensively
researched and applied in various domains, featuring prominently in studies by
[6, 7, 8, 9, 10]. While much of the work in this area has been empirical or
heuristic, there has also been significant theoretical exploration, with
contributions from researchers like [11, 12].

While uncertainty sampling has earned its reputation as a cornerstone in the
active learning landscape, it is by no means the only strategy in use. Other
approaches, such as query-by-committee [13], expected model change [14],
expected error reduction [15], and expected variance reduction [16], offer
alternative ways to implement active learning effectively. These various
methodologies further extend the adaptability and applicability of active
learning, ensuring it remains a vibrant field of study. For a more in-depth
understanding of active learning, interested readers can refer to the survey
paper such as [3, 17], and the more recent [18].

Despite the advantages of sampling efficiency, active learning presents
several challenges. First, there’s the cold start issue, wherein the
effectiveness of uncertainty sampling relies heavily on the initial model’s
accuracy in capturing the overview of existing data distribution. A poorly
fitted initial model reduces the efficacy of both subsequent queries and
overall model performance. Second, real-world datasets often contain noise or
may have features that are not adequately representative, making the regions
of uncertainty potentially less valuable for querying. Third, labeling costs
can vary between positive and negative instances; for instance, in the
financial services industry, identifying a loan/mortgage default is
substantially more costly than pinpointing a reliable paymaster. For a more
comprehensive discussion on the practical challenges of active learning, refer
to [18].

Recent active learning research has made significant advances, particularly in
the field of deep learning. For example, [19] addresses the cold start issue
in deep learning models by establishing different querying strategies for high
and low budget regimes. [20] operates under the assumption of an abundance of
pre-labeled instances, which may contain noise. They employ a high-quality
model to identify and remove dubious or noisy labels, turning to an oracle for
final verification and adjustment.

In this paper, we assume that the dataset contains both labeled and unlabeled
data, with no free weakly-labeled data, unlike what is commonly found in deep
learning-related studies. We assume that overlapping features contribute to
dataset labeling noise and present ambiguity for the classification model. To
address these issues, we introduce a broader sampling spectrum to prevent the
model from over-sampling noisy regions. Furthermore, we propose a metric for
cost efficiency that considers the distinct labeling costs for positive
instances.

The remainder of this paper is organized as follows: Section 2 introduces the
foundational algorithms of random sampling and uncertainty sampling, which
serve as benchmarks for our proposed method. In Section 3, we elucidate our
proposed sampling function through mathematical modeling and algorithmic
description. Section 4 presents simulation results, comparing random sampling,
uncertainty sampling, and our proposed dsampling function. Finally, Section 5
offers conclusions drawn from our work.

##  II Random Sampling and Uncertainty Sampling

This section introduces random sampling and uncertainty sampling, which serve
as benchmarks for the simulation. Then, the general sampling algorithm is
presented.

###  II-A Random Sampling

Random sampling (or random samples) is a fundamental concept in the field of
machine learning and statistical analysis, where it serves as a primary data
selection method. It operates under the premise of providing every instance an
equal chance of being selected, thereby mitigating the risk of bias and
promoting diversity within the chosen sample [21].

The strength of random sampling lies in its simplicity and representativeness.
As it doesn’t rely on any additional information or complicated selection
mechanisms, it is easily implemented, even in scenarios where preliminary data
understanding is limited. Due to the randomness in selection, the sample often
captures the overall distribution of the population well, contributing to the
generalizability of the learned model.

However, random sampling is not without its weaknesses. In situations where
the distribution of labels is imbalanced, or certain classes of data are less
prevalent, random sampling overlooks these under represented labels.
Consequently, the learned model suffers from performance issues when
predicting less common classes [22]. Moreover, as random sampling does not
consider the informativeness or relevance of instances, it might lead to the
selection of redundant or non-informative instances, causing a potential waste
of computational resources.

Despite these drawbacks, random sampling remains a common and crucial sampling
strategy in machine learning projects due to its inherent simplicity and the
fair representation it provides. Various studies have employed random sampling
as a baseline or comparative method in research on active learning,
reinforcement learning, and other machine learning disciplines.

###  II-B Uncertainty Sampling

Uncertainty sampling is a data selection strategy in active learning, where
instances about which the model is most uncertain are chosen for labelling.
Essentially, it seeks to label instances for which the current predictive
model has the lowest confidence, thereby focusing on the most informative
samples to improve the model’s learning efficiency [4].

One of the principal advantages of uncertainty sampling lies in its potential
to maximize the learning outcomes from a limited pool of labeled instances. By
focusing on samples that the model finds hard to classify, it aids in refining
the decision boundary and enhancing overall model performance, leading to more
efficient use of computational resources compared to random sampling.

Despite these advantages, uncertainty sampling has its limitations. Primarily,
it runs the risk of gravitating towards complex or noisy instances, as these
are the samples where the model often experiences the most uncertainty. This
bias can lead to model overfitting, as the learning may focus excessively on
outliers or irregular instances.

###  II-C General Sampling Algorithm

The abovementioned random sampling and uncertainty sampling can be elaborated
with the following general algorithm.

  * •

Step 1 - Initialization: Start with an initial classification model that has
been trained on a labeled dataset (known data pool, $L$. Additionally, prepare
an unlabeled dataset (unknown data pool, $U$). Define stopping criteria such
as a predetermined number of queries, denoted by $N$. Each query is indexed by
and integer $q$, where $q\leq N$

  * •

Step 2 - Instance Selection: In this step, select instances from $U$ using
either random sampling or uncertainty sampling, based on the strategy chosen
for the simulation. For random sampling, randomly select $N$ instances from
$U$ without consideration of the model’s output. For uncertainty sampling, use
the existing model to predict the class probabilities for each instance in
$U$. Select instances based on measures of uncertainty, for example least
confidence, margin sampling, or entropy. After querying their true labels,
move the $N$ selected instances from $U$ to $L$.

  * •

Step 3 - Model Refinement: Using the updated labeled dataset $L$, retrain the
classification model. If the stopping criteria are not met, return to Step 2
and continue the process.

##  III Sampling over Uncertainty and Noise Regions

The assumptions and the mathematical model of the proposed sampling function
are stated and discussed in the following sections.

###  III-A Assumptions and Setup

As mentioned above, we use two distinct pools of data: one labeled and another
unlabeled. The initial size of the labeled data pool is modest, while the
unlabeled data pool is significantly larger. We also assume that the
distribution of the overall population remains constant throughout the
querying process. Our study focuses on a binary classification problem with
labels categorized as 0 and 1 or True or False.

It is important to note that the simulations involve assessing the actual
model performance, using the mean values of the Area Under the Curve (AUC) and
the F1 score, derived from _three_ distinct test data sets. These performance
outcomes are for referencing purposes only and are available solely to the
observers during the simulation. They do not in any way influence the results
of the different algorithms tested.

Finally, we assume that the active learning process concludes after a
predetermined number of queries.

###  III-B Shifted Normal Sampling: Inspired by the Uncertainty Region and
Noisy Region

Suppose we have the final model of an active learning process and its
associated prediction probability, denoted as $p_{i}^{\text{final}}$, for a
binary classification dataset. Here, $i$ is the index of the unlabeled
instances and it may be omitted for brevity.

By using $p^{\text{final}}$, we map all unlabelled instances to the range
$[0,1]\in\mathbb{R}$, where $\mathbb{{R}}$is the set of real numbers. Within
this range, instances with high predicted probablility are unambiguously
associated with their respective labels of 0 and 1\. In contrast, those around
$p^{{}_{\text{final}}}=0.5$ oscillate between the labels as the query
progresses. This ambiguity is attributed to their location in an overlap
region, which we term as _noise_ here, as illustrated in Fig. 1. Let the
integer $q$ denote the $q$-th query to the set $U$ (see Section III-D). Then
the region where $p^{q}\approx 0.5$ serves as the uncertainty region for
interim models to query. In contrast, the area around $p^{\text{final}}=0.5$
is considered the noise region, as it is uncertainly classified the final
model.

Figure 1: Optimal probability distributions for positive and negative events,
exhibiting minimal overlap area, and shifted normal samping function.

Now, assume that we are using uncertainty sampling in querying instances of
predicted probabilities $p^{q}$ close to the uncertainty region, i.e., in the
range of $(0.5-\delta,0.5+\delta)$, for a small value $\delta$ at $q$-th
query, where $\delta\in\mathbb{R}+$ and $\delta$ closes to 0 . Here, the
$p^{q=1}=0.5$ from the initial model might significantly differ from
$p^{\text{final}}=0.5$. Yet, as queries continue, we anticipate a gradual
refinement in the interim models, drawing instances closer and closer to
$p_{\text{final}}=0.5$. Let $\varphi(q)$ be the actual sampling distribution
of the interim model with reference to the final model, i.e.,

$\varphi(q)=\left\\{p_{i}^{\text{final}}:\forall
i,p_{i}^{q}\in\left[0.5-\delta,0.5+\delta\right]\right\\}.$ (1)

We expect $\varphi(q)$ to follow a normal distribution, represented as
$\varphi\sim\text{N}(0.5,\sigma)$, where $\sigma$ shrinks as $q$ increases.

The essence of uncertainty sampling is to query within the uncertainty region,
which overlaps with the noise region as queries progress. While initially
minimal, this overlap can increase as interim models are refined, further
pushing $\varphi(q)$ towards the noise region. We argue that narrow sampling
spectrum over the noise region is the cause of performance fluctuations in the
interim models. To address this issue, rather than sampling within the range
$[0.5-\delta,0.5+\delta]$, we opt for a wider normal distribution, denoted as
$\text{N}(0.5,\sigma)$. This allows us to shift the selection of instances
closer to $p^{q}=0.5$, while controlling the sampling spread via the standard
deviation $\sigma$.

The details of the algorithm will be elaborated in Section III-D.

###  III-C Imbalance Labelling Cost

We assume that the model performance metric such as AUC, F1, etc, is measured
and denoted as $\lambda(q)$, where higher $\lambda(q)$ represents better
performance and $0\leq\lambda(q)\leq 1;\lambda(q)\in\mathbb{{R}}$, for the
$q$-th query. . To tune the performance measurement of the sampling algorithm
in terms of its responsiveness to varying proportions of positive instances,
we introduce a metric designated as _cost efficiency_ , i.e.,

$\eta(q)=\frac{\lambda(q)}{\zeta(q)\,C},$ (2)

where $\eta\in\mathbb{{R}}$ , $\eta\geq 0$ and $\zeta(q):\zeta(q)\geq 0$
represent the proportion of positive instances within the known dataset.

Here, $C$ is the cost associated with a single positive instance relative to a
negative instance and $C\geq 1$. When the costs for both positive and negative
instances are identical, $C$ is 1. Conversely, if the cost of a positive
instance is three times the cost of a negative instance, $C$ is 3. For the
ensuing simulation, we adopt $C=1$ as our standard value. Overall, a higher
value of $\eta$ corresponds to increased efficiency.

As mentioned earlier, we assume that the labeling costs for positive events
are significantly higher than those for negative events in this case.
Consequently, we adjust the normal sampling distribution slightly to the left,
i.e., $\text{N}(0.45,\sigma)$, such that the sampling is slightly biased
towards negative events (Fig. 1). This adjustment will yield relatively fewer
positive labels in $\zeta(q)$, thereby improving $\eta(q)$.

This metric will be used in simulation results in Section IV.

###  III-D Normal Sampling Algorithm

We illustrate the algorithm of the proposed sampling function as follows.

####  III-D1 Step 1 - Initialization

Commence with a pre-existing classification model, accompanied by a labelled
dataset (the known data pool, $L$), and an unlabelled dataset (the unknown
data pool, $U$). Define a set of stopping criteria, such as a predefined
number of queries, denoted as $N$.

####  III-D2 Step 2 - Instance Selection

This step is analogous to uncertainty sampling, wherein instances are selected
based on predicted probabilities from all instances in $U$. However, diverging
from uncertainty sampling, instances are selected with predicted probabilities
in accordance with a normal distribution. In our simulation, we will use a
beta function, i.e., $\text{Beta}\left(\alpha,\beta\right)$ to approximate the
normal distribution, where $\alpha$ and $\beta$ are adjusted such that peak
values occur at $p=0.45$. Correspondingly, most instances are sampled near to
$p=0.45$, without disregarding instances from other ranges. Then, queried
instances will be incorporated into $L$.

####  III-D3 Step 3 - Model Refinement

A new model is built using $L$. If the stopping criteria have not been met,
the process will be repeated from Step 2.

##  IV Simulation Results

This section investigates the performance of random sampling, uncertainty
sampling and shifted normal sampling through simulation. The discussion
commences with a description of the simulation setup, followed by an overview
of the artificial datasets that we used. Finally, the simulation results are
delineated.

###  IV-A Simulation Overview

In this paper, we created synthetic classification datasets using Scikit-learn
[23]. The datasets comprise four feature columns, and each dataset has
different levels of noise. Due to page limits, we present results for two sets
of noise parameters in our simulations. The results shown are representative
of our extensive simulation over different simulation parameters.

Our primary focus was on binary classification, assuming a large data pool
with an equal number of positive and negative events. For the purpose of our
study, we divided the datasets randomly into three sections. The first, a
labeled data pool, contained 10 instances. The second, an unknown data pool,
held 1000 instances. Lastly, we had three test data pools, each containing
1000 instances. These test data were used to evaluate the performance of our
model after each query. The parameter _class_sep_ regulates the separation
between the label classes. A smaller value reduces the separation and makes
classification harder.

In line with the approach outlined in Section III-D, we adapted the sampling
algorithm during Step 2 to meet our simulation objective, choosing from random
sampling, uncertainty sampling, or shifted normal sampling. Each query
necessitated the selection of two instances from $U$ to be annotated,
revealing their true labels. This process was repeated across a total of 20
queries. Unless otherwise specified, all the presented graphs are the results
of 30 rounds of simulations and are plotted with 99% confidence intervals
(CI).

The models were built using the Generalized Linear Model (GLM) from H2O [24],
set to the optimal parameters and with no further feature engineering. It is
important to note that the ability of GLM to accurately identify positive
events can vary depending on the characteristics of the dataset.

###  IV-B Results

Fig. 2 shows the performance for a classification dataset, set with the
parameter _class_sep_ =0.5 for overlap dataset, where its bivariate pairwise
distribution is illustrated in Fig. 2(a). Fig. 2(b) charts the AUC, revealing
an increasing trend as the number of queries increases with better refined
interim models. In particular, we note that shifted normal sampling and random
sampling exhibit similar AUC values, while uncertainty sampling underperforms
on average. Then, Fig. 2(c) sheds light on their corresponding positive event
ratio at 99% CI. We observe both random sampling and uncertainty sampling stay
around $\zeta^{\left(\text{random}\right)}=0.53$ and
$\zeta^{\left(\text{uncertainty}\right)}=0.50$ whereas shifted normal sampling
converge approximately at $\zeta^{\left(\text{normal}\right)}=0.43$ at $q=20$.
It is worth noting that although shifted normal sampling has similar AUC
performance as random sampling, the former has lower positive event ratio
comparatively, results in better cost efficiency, i.e., achieving
$\eta^{\left(\text{normal}\right)}=1.88$ for shifted normal sampling — about
20% improvement as compared to uncertainty sampling
$\eta^{\left(\text{uncertainty}\right)}=1.60$ and random sampling
$\eta^{\left(\text{random}\right)}=1.54$ at final query.

(a)  (b)  (c)  (d)

Figure 2: Illustration of the classification dataset with parameter
_class_sep_ =0.5 indicating overlap dataset. The sub-figures represent (a)
bivariate distribution, (b) model performance measured in AUC, (c) ratio of
positive events, and (d) cost efficiency across each query.

Simulations on classification datasets with _class_sep_ =1.0 show minor
overlap, as in Fig. 3. Generally, all three sampling functions exhibits
competitive AUC performance with the their respective mean positive event
ratios all within the 99% CI. Since shifted normal sampling has the lowest
positive event ratio, the correponding cost efficiency stays highest, i.e.
$\eta^{\left(\text{normal}\right)}=2.44$, about 32% improvement as compared to
$\eta^{\left(\text{random}\right)}=1.78$ and
$\eta^{\left(\text{uncertainty}\right)}=1.92$ at final query.

(a)  (b)  (c)  (d)

Figure 3: Representation of the classification dataset for parameter
_class_sep_ =1.0. (a) bivariate distribution, (b) AUC, (c) positive event
ratio and (d) cost efficiency.

##  V Conclusion

This study aimed to examine the effectiveness of various sampling
algorithms—namely random sampling, uncertainty sampling, and the proposed
shifted normal sampling, in the context of noisy binary classification
datasets. We considered cost efficiency, particularly in scenarios where
labelling positive instances is more costly than negative instances. Our
findings reveal that shifted normal sampling strikes a robust balance between
AUC performance and improves cost efficiency up to 32%.

## References

  * [1] P. Ren, Y. Xiao, X. Chang, P.-Y. Huang, Z. Li, B. B. Gupta, X. Chen, and X. Wang, “A survey of deep active learning,” _ACM computing surveys (CSUR)_ , vol. 54, no. 9, pp. 1–40, 2021.
  * [2] S. Budd, E. C. Robinson, and B. Kainz, “A survey on active learning and human-in-the-loop deep learning for medical image analysis,” _Medical Image Analysis_ , vol. 71, p. 102062, 2021.
  * [3] B. Settles, “Active learning literature survey,” 2009.
  * [4] D. Lewis and W. Gale, “A sequential algorithmfor training text classifiers,” in _SIGIR’94: Proceedings of the Seventeenth Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, organised by Dublin City University_ , 1994, pp. 3–12.
  * [5] G. Schohn and D. Cohn, “Less is more: Active learning with support vector machines,” in _Proceedings of the Seventeenth International Conference on Machine Learning_ , 2000, pp. 839–846.
  * [6] Y. Yang, Z. Ma, F. Nie, X. Chang, and A. G. Hauptmann, “Multi-class active learning by uncertainty sampling with diversity maximization,” _International Journal of Computer Vision_ , vol. 113, pp. 113–127, 2015\.
  * [7] J. Zhu, H. Wang, T. Yao, and B. K. Tsou, “Active learning with sampling by uncertainty and density for word sense disambiguation and text classification,” in _22nd International Conference on Computational Linguistics, Coling 2008_ , 2008, pp. 1137–1144.
  * [8] E. Lughofer and M. Pratama, “Online active learning in data stream regression using uncertainty sampling based on evolving generalized fuzzy models,” _IEEE Transactions on fuzzy systems_ , vol. 26, no. 1, pp. 292–309, 2017\.
  * [9] Y. Yang and M. Loog, “Active learning using uncertainty information,” in _2016 23rd International Conference on Pattern Recognition (ICPR)_. IEEE, 2016, pp. 2646–2651.
  * [10] G. Wang, J.-N. Hwang, C. Rose, and F. Wallace, “Uncertainty sampling based active learning with diversity constraint by sparse selection,” in _2017 IEEE 19th International Workshop on Multimedia Signal Processing (MMSP)_. IEEE, 2017, pp. 1–6.
  * [11] S. Mussmann and P. S. Liang, “Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [12] A. Raj and F. Bach, “Convergence of uncertainty sampling for active learning,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 18 310–18 331.
  * [13] H. S. Seung, M. Opper, and H. Sompolinsky, “Query by committee,” in _Proceedings of the fifth annual workshop on Computational learning theory_ , 1992, pp. 287–294.
  * [14] B. Settles, M. Craven, and S. Ray, “Multiple-instance active learning,” _Advances in neural information processing systems_ , vol. 20, 2007.
  * [15] N. Roy and A. McCallum, “Toward optimal active learning through monte carlo estimation of error reduction,” _ICML, Williamstown_ , vol. 2, pp. 441–448, 2001.
  * [16] R. Wang, C.-Y. Chow, and S. Kwong, “Ambiguity-based multiclass active learning,” _IEEE Transactions on Fuzzy Systems_ , vol. 24, no. 1, pp. 242–248, 2015.
  * [17] H. Hino, “Active learning: Problem settings and recent developments,” _arXiv preprint arXiv:2012.04225_ , 2020.
  * [18] A. Tharwat and W. Schenck, “A survey on active learning: State-of-the-art, practical challenges and research directions,” _Mathematics_ , vol. 11, no. 4, p. 820, 2023.
  * [19] G. Hacohen, A. Dekel, and D. Weinshall, “Active learning on a budget: Opposite strategies suit high and low budgets,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 8175–8195.
  * [20] T. Younesian, Z. Zhao, A. Ghiassi, R. Birke, and L. Y. Chen, “Qactor: Active learning on noisy labels,” in _Asian Conference on Machine Learning_. PMLR, 2021, pp. 548–563.
  * [21] M. J. Kearns and U. Vazirani, _An introduction to computational learning theory_. MIT press, 1994.
  * [22] H. Kaur, H. S. Pannu, and A. K. Malhi, “A systematic review on imbalanced data challenges in machine learning: Applications and solutions,” _ACM Computing Surveys (CSUR)_ , vol. 52, no. 4, pp. 1–36, 2019.
  * [23] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python,” _Journal of Machine Learning Research_ , vol. 12, pp. 2825–2830, 2011.
  * [24] E. LeDell and S. Poirier, “H2O AutoML: Scalable automatic machine learning,” _7th ICML Workshop on Automated Machine Learning (AutoML)_ , July 2020.