# A correlation inequality for random points in a hypercube with some
implications

Royi Jacobovic and Or Zuk  Department of Statistics and Data Science
The Hebrew University of Jerusalem
Mt. Scopus, 9190501, Jerusalem, Israel
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Let $\prec$ be the product order on $\mathbb{R}^{k}$ and assume that
$X_{1},X_{2},\ldots,X_{n}$ ($n\geq 3$) are i.i.d. random vectors distributed
uniformly in the unit hypercube $[0,1]^{k}$. Let $S$ be the (random) set of
vectors in $\mathbb{R}^{k}$ that $\prec$-dominate all vectors in
$\\{X_{3},..,X_{n}\\}$, and let $W$ be the set of vectors that are not
$\prec$-dominated by any vector in $\\{X_{3},..,X_{n}\\}$. The main result of
this work is the correlation inequality

$P(X_{2}\in W|X_{1}\in W)\leq P(X_{2}\in W|X_{1}\in S)\,.$

For every $1\leq i\leq n$ let $E_{i,n}$ be the event that $X_{i}$ is not
$\prec$-dominated by any of the other vectors in $\\{X_{1},\ldots,X_{n}\\}$.
The main inequality yields an elementary proof for the result that the events
$E_{1,n}$ and $E_{2,n}$ are asymptotically independent as $n\to\infty$.
Furthermore, we derive a related combinatorial formula for the variance of the
sum $\sum_{i=1}^{n}\textbf{1}_{E_{i,n}}$, i.e. the number of maxima under the
product order $\prec$, and show that certain linear functionals of partial
sums of $\\{\textbf{1}_{E_{i,n}};1\leq i\leq n\\}$ are asymptotically normal
as $n\to\infty$.

##  1 Introduction

For every positive integer $l\in\mathbb{N}$, denote
$[l]\equiv\\{1,2,\ldots.l\\}$ and let $\prec$ be the product order on
$\mathbb{R}^{k}$, i.e., for any two real vectors
$x=(x_{1},x_{2},\ldots,x_{k})$ and $y=(y_{1},y_{2},\ldots,y_{k})$,

$x\prec y\Leftrightarrow\left(x_{i}\leq y_{i}\ ,\ \forall i\in[k]\right)\,.$
(1)

In addition, $\not\prec$ is the negation of $\prec$.

Let $X_{1},X_{2},\ldots,X_{n}$ ($n\geq 3$) be i.i.d. random vectors
distributed uniformly on $[0,1]^{k}$ and define two random sets:

$W\equiv\left\\{x\in\mathbb{R}^{k};x\not\prec X_{i},\forall 3\leq i\leq
n\right\\}\ \ ,\ \ S\equiv\left\\{x\in\mathbb{R}^{k};X_{i}\prec x,\forall
3\leq i\leq n\right\\}$ (2)

The main result of this work is the following correlation inequality

$P(X_{2}\in W|X_{1}\in W)\leq P(X_{2}\in W|X_{1}\in S)\,.$ (3)

Observe that $S\subset W$ with probability one, hence the conditioning on
$X_{1}$ on the right-hand side above is more restrictive than the conditioning
on the left-hand side.

For each $i\in[n]$ the vector $X_{i}$ is said to be a maximum of
$\textbf{X}_{n}\equiv\\{X_{1},X_{2},\ldots,X_{n}\\}$ if and only if no other
vector in $\textbf{X}_{n}$ $\prec$-dominates $X_{i}$. Since the product order
$\prec$ is a partial order, the set of maxima of $\textbf{X}_{n}$ might
include more than one element. Define the events

$E_{i,n}\equiv\\{X_{i}\text{ is a maximum of $\textbf{X}_{n}$}\\}\ \ ,\ \
1\leq i\leq n\,.$ (4)

Then, the inequality (3) is used in order to provide an elementary proof for
the result that $E_{1,n}$ and $E_{2,n}$ are asymptotically independent as
$n\to\infty$. This asymptotic independence result is applied in order to
derive a central limit theorem (CLT) for certain linear functionals of partial
sums of $\\{\textbf{1}_{E_{i,n}};i\in[n]\\}$.

The rest of this work is organized as follows: Section 2 is about the
correlation inequality (3). In particular, it includes the proof as well as a
discussion about a conjectured extension of (3). Section 3 contains the
asymptotic independence and the CLT statements along with their proofs.

###  1.1 Related literature

Correlation inequalities are inequalities satisfied by a correlation function
in a probabilistic model. Several well-known correlation inequalities arise in
diverse fields of probability theory: In models originating from statistical
mechanics [1, 2] and percolation theory [3]. For the Gaussian case, an
inequality was suggested in [4], with some applications, e.g., [5, 6].
Additional correlation inequalities appear in [7, 8, 9, 10]. For example,
consider the FKG inequality [11] which has several generalizations and
applications in probability, e.g., [12, 13, 14, 15, 16, 17, 18].

Of particular relevance to the current work are correlation inequalities
related to linear extensions of finite partially ordered sets. In this
settings, there is a set with $\ell$ elements
$\\{U_{1},U_{2},\ldots,U_{\ell}\\}$ which is equipped with a partial order
$\prec_{1}$. With a bit abuse of notation, we may represent $\prec_{1}$ as the
set of all $(i,j)\in[\ell]\times[\ell]$ such that $U_{i}\prec_{1}U_{j}$. Let
$\prec_{2}$ be a random linear extension of $\prec_{1}$ which is distributed
uniformly over the set of all linear extensions of $\prec_{1}$. In this
probability space, for every $I\subseteq[\ell]\times[\ell]$, define an
ordering event $E_{I}\equiv\\{U_{i}\prec_{2}U_{j},\forall(i,j)\in I\\}$.
Several inequalities were proposed for co-occurrence of ordering events, i.e.,
$P(E_{A}|E_{B})\geq P(E_{A})$ for some choices of
$A,B\subseteq[\ell]\times[\ell]$. Equivalently, we can assume $n$ i.i.d.
continuous uniform random variables $U_{1},U_{2},\ldots,U_{n}\sim U(0,1)$.
Denote for every $I\subseteq[\ell]\times[\ell]$ the event
$\widetilde{E}_{I}\equiv\left\\{U_{i}<U_{j},\forall(i,j)\in I\right\\}$. Then,
the inequality is expressed as
$P(\widetilde{E}_{A}|\widetilde{E}_{B}\cap\widetilde{E}_{\prec_{1}})\geq
P(\widetilde{E}_{A}|\widetilde{E}_{\prec_{1}})$. For example, consider the XYZ
inequality [15, 19], which is related to the FKG inequality and can be phrased
as follows:

###### Theorem 1

(XYZ-inequality) Let $\prec_{1}$ be a subset of $[\ell]\times[\ell]$ which is
representing a partial order. Then:

$P(U_{1}<U_{2}|\widetilde{E}_{\prec_{1}})\leq
P(U_{1}<U_{2}|\widetilde{E}_{\prec_{1}}\cap\\{U_{1}<U_{3}\\}).$ (5)

While Eq. (5) seems intuitive, several natural generalizations of it do not
hold in general (see [15, 20, 21]). For example, taking
$\prec_{1}\equiv\\{(1,3)\\}$ and replacing $B=\\{(1,3)\\}$ by
$B=\\{(1,3),(3,4)\\}$ leads to a false statement. Other inequalities were
proposed in [22, 21], where $[\ell]$ is partitioned into two disjoint subsets
$N_{1},N_{2}$ such that $A$ and $B$ contain only pairs $(i,j)\in N_{1}\times
N_{2}$, and either the restriction of $\prec_{1}$ to each of $N_{1}$ and
$N_{2}$ is a (full) linear order, or $\prec=\prec_{1,1}\bigcup\prec_{1,2}$
such that for each $i=1,2$, $\prec_{1,i}$ is a partial order of $N_{i}$.

Additional details on related inequalities and counter-examples are available
in [23]. Another intriguing result is that although Theorem 1 implies that
$P(U_{1}<U_{2}<U_{3})\leq P(U_{1}<U_{2})P(U_{2}<U_{3})$, it was shown in [24]
that it may not hold that $P(U_{1}<U_{2}<U_{3}<U_{4})\leq
P(U_{1}<U_{2}<U_{3})P(U_{3}<U_{4})$. In the above inequalities, $A$ and $B$
are themselves subsets of $[\ell]\times[\ell]$ which are representing partial
orders. The main result of the current work (3) goes beyond such inequalities,
as it refers to more complex ordering events that cannot be represented as
partial order events, but only as intersections of unions of pairwise ordering
events.

Another strand of relevant literature is about the number of maxima in a model
with $n$ random points distributed uniformly in the unit hypercube
$[0,1]^{k}$. This model is related to several problems in analysis of linear
programming [25] and of maxima-finding algorithms [26, 27, 28, 29, 30].
Furthermore, it also appears in the context of game theory [31] and in the
analysis of random forest algorithms [32, 33]. Theoretical results regarding
this model appear in, e.g., [34, 35, 36, 37, 38]. In particular, as to be
explained in Section 3.1, the asymptotic independence of $E_{1,n}$ and
$E_{2,n}$ as $n\to\infty$ might be derived as a consequence of the results in
this literature. Remarkably, [35] includes a result regarding asymptotic
normality with the corresponding Berry-Essen bound of the number of maxima
$\sum\limits_{i=1}^{n}\textbf{1}_{E_{i,n}}$. In the current paper, we derive
different asymptotic normality results, for certain linear functionals of
partial sums of $\\{\textbf{1}_{E_{i,n}};i\in[n]\\}$. The derivation will
follow via an application of some limit theorems for triangular arrays of row-
wise exchangeable random variables [39].

For simplicity, we present our results for the case where all coordinates have
a continuous uniform marginal distribution. Since all events of interest can
be expressed in terms of the ranks of the corresponding random variables, the
major results of the current work still hold when the marginal $U(0,1)$
distribution is replaced by any continuous distribution. For a recent study
about the effect of discrete marginal distributions implying non-zero
probability for ties, see [40].

##  2 A correlation inequality

For every $i,j\in[n]$ denote $B_{ij}\equiv\\{X_{i}\prec X_{j}\\}$ and
$\overline{B_{ij}}\equiv\\{X_{i}\not\prec X_{j}\\}$. Then, Eq. (3) can be
rephrased as follows:

###### Theorem 2

$P\left(\bigcap_{j=3}^{n}\overline{B_{2j}}\bigg{|}\bigcap_{j=3}^{n}\overline{B_{1j}}\right)\leq
P\left(\bigcap_{j=3}^{n}\overline{B_{2j}}\bigg{|}\bigcap_{j=3}^{n}B_{j1}\right)\,.$
(6)

Proof: Let $x_{1},x_{2}\in\mathbb{[}0,1]^{k}$ be the values of $X_{1},X_{2}$
respectively, and denote $x_{[2]}\equiv[x_{1},x_{2}]$ such that for every
$i=1,2$, $x_{i}=(x_{i1},x_{i2},\ldots,x_{ik})$. It will be shown that for
every fixed $x_{1},x_{2}\in[0,1]^{k}$

$P(\bigcap_{j=3}^{n}\\{\overline{B_{2j}}\cap\overline{B_{1j}}\\}|x_{[2]})P(\bigcap_{j=3}^{n}B_{j1}|x_{[2]})\leq
P(\bigcap_{j=3}^{n}\\{\overline{B_{2j}}\cap
B_{j1}\\}|x_{[2]})P(\bigcap_{j=3}^{n}\overline{B_{1j}}|x_{[2]})$ (7)

and the theorem will follow by integration over $x_{[2]}$. Due to the
conditioning on $x_{[2]}$, we can write the above inequality as

$\prod_{j=3}^{n}P(\\{\overline{B_{2j}}\cap\overline{B_{1j}}\\}|x_{[2]})P(B_{j1}|x_{[2]})\leq\prod_{j=3}^{n}P(\\{\overline{B_{2j}}\cap
B_{j1}\\}|x_{[2]})P(\overline{B_{1j}}|x_{[2]})$ (8)

and by symmetry

$\Big{[}P(\\{\overline{B_{23}}\cap\overline{B_{13}}\\}|x_{[2]})P(B_{31}|x_{[2]})\Big{]}^{n-2}\leq\Big{[}P(\\{\overline{B_{23}}\cap
B_{31}\\}|x_{[2]})P(\overline{B_{13}}|x_{[2]})\Big{]}^{n-2}.$ (9)

Hence, it is enough to prove:

$P(\\{\overline{B_{23}}\cap\overline{B_{13}}\\}|x_{[2]})P(B_{31}|x_{[2]})\leq
P(\\{\overline{B_{23}}\cap B_{31}\\}|x_{[2]})P(\overline{B_{13}}|x_{[2]}).$
(10)

In order to compute the probabilities of each of the events above, observe
that:

$\displaystyle P(B_{31}|x_{[2]})$ $\displaystyle=\prod_{i=1}^{k}x_{1i}\>,$
(11) $\displaystyle P(\overline{B_{13}}|x_{[2]})$
$\displaystyle=1-\prod_{i=1}^{k}(1-x_{1i})\>,$ $\displaystyle
P(\overline{B_{23}}\cap\overline{B_{13}}|x_{[2]})$
$\displaystyle=1-P(B_{23}\cup B_{13}|x_{[2]})$
$\displaystyle=1-P(B_{23}|x_{[2]})-P(B_{13}|x_{[2]})+P(B_{23}\cap
B_{13}|x_{[2]})$
$\displaystyle=1-\prod_{i=1}^{k}(1-x_{1i})-\prod_{i=1}^{k}(1-x_{2i})+\prod_{i=1}^{k}(1-\max\\{x_{1i},x_{2i}\\})\>,$
$\displaystyle P(\overline{B_{23}}\cap B_{31}|x_{[2]})$
$\displaystyle=P(B_{31}|x_{[2]})-P(B_{23}\cap B_{31}|x_{[2]})$
$\displaystyle=\prod_{i=1}^{k}x_{1i}-\textbf{1}_{\\{x_{2}\prec
x_{1}\\}}\prod_{i=1}^{k}(x_{1i}-x_{2i}).$

Thus, an insertion of the probabilities from Eq. (2) into Eq. (10) yields that
it is remained to prove:

$\displaystyle\Big{[}\prod_{i=1}^{k}x_{1i}-\textbf{1}_{\\{x_{2}\prec
x_{1}\\}}\prod_{i=1}^{k}(x_{1i}-x_{2i})\Big{]}\Big{[}1-\prod_{i=1}^{k}(1-x_{1i})\Big{]}\geq$
$\displaystyle\Big{[}1-\prod_{i=1}^{k}(1-x_{1i})-\prod_{i=1}^{k}(1-x_{2i})+\prod_{i=1}^{k}(1-\max\\{x_{1i},x_{2i}\\})\Big{]}\prod_{i=1}^{k}x_{1i}.$
(12)

Then, subtraction of the common terms from both sides implies that the
following inequality has to be proven:

$\textbf{1}_{\\{x_{2}\prec
x_{1}\\}}\prod_{i=1}^{k}(x_{1i}-x_{2i})\Big{[}1-\prod_{i=1}^{k}(1-x_{1i})\Big{]}\leq\Big{[}\prod_{i=1}^{k}(1-x_{2i})-\prod_{i=1}^{k}\big{(}1-\max\\{x_{1i},x_{2i}\\}\big{)}\Big{]}\prod_{i=1}^{k}x_{1i}.$
(13)

When $x_{2}\not\prec x_{1}$, the left-hand side is zero, and the inequality
holds because the right-hand side is always non-negative. When $x_{2}\prec
x_{1}$, it is left to show that:

$G(x_{2};x_{1})\equiv\Big{[}\prod_{i=1}^{k}(1-x_{2i})-\prod_{i=1}^{k}(1-x_{1i})\Big{]}\prod_{i=1}^{k}x_{1i}-\prod_{i=1}^{k}(x_{1i}-x_{2i})\Big{[}1-\prod_{i=1}^{k}(1-x_{1i})\Big{]}\geq
0.$ (14)

In particular, $x_{2}\prec x_{1}$ implies that
$x_{2}\in\bigtimes\limits_{i=1}^{k}[0,x_{1i}]$. We proceed by first showing
that $G(x_{2};x_{1})\geq 0$ on the boundary of the box
$\bigtimes\limits_{i=1}^{k}[0,x_{1i}]$, and will later show that
$G(x_{2};x_{1})\geq 0$ also in the interior. First, if $x_{2i}=x_{1i}$ for
some $i\in[k]$, then

$G(x_{2};x_{1})=\Big{[}\prod_{i=1}^{k}(1-x_{2i})-\prod_{i=1}^{k}(1-x_{1i})\Big{]}\prod_{i=1}^{k}x_{1i}\geq
0.$ (15)

Next, if $\textbf{0}_{k}$ is the zero-vector in $\mathbb{R}^{k}$, then

$G(\bm{0_{k}};x_{1})=\Big{[}1-\prod_{i=1}^{k}(1-x_{1i})\Big{]}\prod_{i=1}^{k}x_{1i}-\prod_{i=1}^{k}x_{1i}\Big{[}1-\prod_{i=1}^{k}(1-x_{1i})\Big{]}=0.$
(16)

For every $i\in[k]$ let
$x_{2[-i]}\equiv(x_{21},..,x_{2(i-1)},x_{2(i+1)},..,x_{2k})$ and define the
real-valued function

$G_{x_{2[-i]},x_{1}}(y)\equiv
G\big{(}(x_{21},..,x_{2i-1},y,x_{2i+1},..,x_{2k});x_{1}\big{)}\ \ ,\ \
y\in\mathbb{R}.$ (17)

Then, Eq. (14) implies that $G_{x_{2[-i]},x_{1}}(\cdot)$ is a linear function
of $y$. Therefore, its minimum in a closed interval is obtained at the
boundary, i.e., for every $x_{1}\in[0,1]^{k}$,
$x_{2[-i]}\in\bigtimes\limits_{j=1,j\neq i}^{k}[0,x_{1j}]$ and
$y\in[0,x_{1i}]$ deduce that

$G_{x_{2[-i]},x_{1}}(y)\geq\min\left\\{G_{x_{2[-i]},x_{1}}(0),G_{x_{2[-i]},x_{1}}(x_{1i})\right\\}.$
(18)

In particular, Eqs. (15) and (16) yield that

$G_{\bm{0_{k-1}},x_{1}}(y)\geq\min\big{(}G_{\bm{0_{k-1}},x_{1}}(0),G_{\bm{0_{k-1}},x_{1}}(x_{1i})\big{)}=0$
(19)

for every $y\in[0,x_{1i}]$. Thus, $G(x_{2};x_{1})\geq 0$ for every vector
$x_{2}\in\bigtimes\limits_{i=1}^{k}[0,x_{1i}]$ with at least $k-1$ zero
coordinates. We next continue by induction. Let
$x_{2[-i]}\in\bigtimes\limits_{i=1}^{k}[0,x_{1i}]$ be a vector with $k-2$ zero
coordinates. Then, since $G_{x_{2[-i]},x_{1}}(0)$ is obtained by evaluating
$G$ at a vector with $k-1$ zero coordinates, deduce that

$G_{x_{2[-i]},x_{1}}(y)\geq\min\big{(}G_{x_{2[-i]},x_{1}}(0),G_{x_{2[-i]},x_{1}}(x_{1i})\big{)}\geq
0$ (20)

for every $y\in[0,x_{1i}]$. Proceeding by induction, we get that
$G_{x_{2[-i]},x_{1}}(x)\geq 0$ whenever $x_{2i}=0$ for some $i\in[k]$. As a
result deduce that $G(x_{2};x_{1})\geq 0$ for any $x_{2}$ lying at the
boundary of the box $\bigtimes\limits_{i=1}^{k}[0,x_{1i}]$. Next, for any
$x_{2[-i]}\in\bigtimes\limits_{j=1,j\neq i}^{k}[0,x_{1j}]$ and any
$y\in[0,x_{1i}]$ we have:

$G_{x_{2[-i]},x_{1}}(y)\geq\min\big{(}G_{x_{2[-i]},x_{1}}(0),G_{x_{2[-i]},x_{1}}(x_{1i})\big{)}\geq
0.$ (21)

Therefore, $G(x_{2};x_{1})\geq 0$ for every
$x_{2}\in\bigtimes\limits_{i=1}^{k}[0,x_{1i}]$ which completes the proof.

###  2.1 Conjecture

It is natural to consider generalizations the main result presented in Theorem
2. This theorem and several other correlation inequalities can be represented
as special cases of the following settings:

###### Problem 1

Consider $n$ i.i.d. uniform random variables $U_{1},U_{2},\ldots,U_{\ell}\sim
U(0,1)$. For every $(i,j)\in[\ell]\times[\ell]$ denote
$E_{ij}\equiv\\{U_{i}<U_{j}\\}$. Find the most general conditions on $T,S\geq
1$, $F_{1},F_{2}..,F_{T},H_{1},H_{2}..,H_{S}\subset[\ell]\times[\ell]$ under
which the following inequality is correct:

$P(\bigcap_{t=1}^{T}\bigcup_{(i,j)\in
F_{t}}E_{ij}|\bigcap_{s=1}^{S}\bigcup_{(i,j)\in H_{s}}E_{ij})\leq
P(\bigcap_{t=1}^{T}\bigcup_{(i,j)\in
F_{t}}E_{ij}|\bigcap_{s=1}^{S}\bigcap_{(i,j)\in H_{s}}E_{ij})\,.$ (22)

###### Remark 1

The inequality in Problem 1 is a generalization of the XYZ-inequality. For a
partial order with $q$ pairwise order relations
$\prec=\\{(a_{i},b_{i}),\>i\in[q]\\}$ take $S=q+1$ with
$H_{i}=\\{(a_{i},b_{j})\\}$ for $i\in[q]$ and
$H_{S}=\\{(a_{1},b_{1}),(1,3)\\}$. Take also $T=1,F_{1}=\\{(1,2)\\}$. Then Eq.
(22) reduces to Eq. (5) with $\ell=n$.

###### Remark 2

The inequality (22) is also a generalization of Theorem 2. Let $\ell=n\cdot k$
and for each $i\in[n]$ define
$X_{i}\equiv(U_{(i-1)k+1},U_{(i-1)k+2},\ldots,U_{ik})$. Then,

$B_{ij}=\left\\{X_{i}\prec
X_{j}\right\\}=\bigcap\limits_{r=1}^{k}\\{U_{(i-1)k+r}\leq U_{(j-1)k+r}\\}\ \
,\ \ \forall(i,j)\in[n]\times[n]\,,$ (23)

i.e., (6) is a special case of (22) with $T=S=n-2$ and

$\displaystyle
F_{t}=\big{\\{}\left(k+1,(t+1)k+1\right),(k+2,(t+1)k+2),\ldots,(2k,(t+2)k)\big{\\}}\
\ ,\ \ \forall t\in[n-2]\,,$ $\displaystyle
H_{s}=\big{\\{}\left(1,(s+1)k+1\right),\left(2,(s+1)k+2\right),\ldots,\left(k,(s+2)k\right)\big{\\}}\
\ ,\ \ \forall s\in[n-2]\,.$ (24)

###### Remark 3

Several of the counter-examples discussed in Section 1.1 and the references
therein can be phrased as violating the inequality (22). For example, take
$n=4$ with $T=S=2$ and the following sets:

$\displaystyle F_{1}$ $\displaystyle=\\{(1,4)\\}\>;\>F_{2}=\\{(1,4),(2,4)\\},$
$\displaystyle H_{1}$ $\displaystyle=\\{(1,3)\\}\>;\>H_{2}=\\{(1,3),(2,3)\\}.$
(25)

Then the inequality (22) reduces to (for some similar related examples, see
[15]):

$P(U_{1}<U_{4}|U_{1}<U_{3})\leq P(U_{1}<U_{4}|U_{1},U_{2}<U_{3}).$ (26)

By symmetry, there are $12$ permutations (out of $24$) over
$U_{1},U_{2},U_{3},U_{4}$ satisfying $U_{1}<U_{3}$,and $8$ permutations
satisfying $U_{1}<U_{3},U_{4}$, and similarly $8$ permutations satisfying
$U_{1},U_{2}<U_{3}$. Therefore, the left hand side of the above inequality is
$\frac{8}{12}$. To get the numerator of the right hand side, we need to count
the permutations satisfying $U_{1},U_{2}<U_{3}$ and $U_{1}<U_{4}$. There are
five such permutations:
$\\{(1,2,3,4),(1,2,4,3),(2,1,3,4),(2,1,4,3),(1,4,2,3)\\}$, hence the right
hand side is $\frac{5}{8}<\frac{8}{12}$ and the inequality fails.

Remark 3 implies that the inequality (22) is not true in general. However,
Remark 1 and Remark 2 imply that the inequality (22) may hold under certain
restrictions on the sets $F_{t},H_{s}$ and their relationships. This motivates
finding the most general conditions under which the inequality (22) is
correct. We suspect that Theorem 2 might be extended to the following more
general case:

###### Conjecture 1

Assume that $U_{1},..,U_{k},U_{k+1},..,U_{2k},U_{2k+1},...,U_{n}\sim U(0,1)$
are i.i.d. uniform random variables. Let
$F_{1},..,F_{T}\subset[k]\times\\{2k+1,..,n\\}$ and
$H_{1},..,H_{T}\subset\\{k+1,..,2k\\}\times\\{2k+1,..,n\\}$ for $T\geq 1$,
with $|F_{t}|=|H_{t}|=m\leq k,\>\forall t\in[T]$. Suppose that
$\sum\limits_{j=1}^{m}\textbf{1}_{\\{(i,j)\in F_{t}\\}}\leq 1,\>\forall
i\in[k],t\in[T]$ and similarly $\sum\limits_{j=1}^{m}\textbf{1}_{\\{(i,j)\in
H_{t}\\}}\leq 1,\>\forall i\in\\{k+1,..,2k\\},t\in[T]$. Then, the inequality
(22) holds.

Conjecture 1 was checked numerically and verified for all subsets up to $n\leq
12,m\leq 4,T\leq 3$. Three restrictions are imposed on the $F_{t},H_{t}$ sets
in the above conjecture: First, the r.v.s $U_{i}$ are divided into three sets,
where variables from the first (second) set can be only the first indices in
pairs appearing in $F_{t}$ ($H_{t}$), and variables from the third set appear
as the second indices in all pairs in $F_{t},H_{t}$. Second, in each $F_{t}$
or $H_{t}$ every variable from the first or second set can appear at most
once. Finally, the sizes of all sets $F_{t},H_{t}$ are fixed at $m$. All three
conditions are necessary. For example, if we allow sets $H_{t}$ of different
sizes, a counter-example is given by:

$\displaystyle F_{1}$ $\displaystyle=\\{(1,5)\\}\>;\>F_{2}=\\{(1,6)\\},$
$\displaystyle H_{1}$ $\displaystyle=\\{(3,5)\\}\>;\>H_{2}=\\{(3,7),(4,8)\\}.$
(27)

Exact enumeration of all consistent partial orders yield:

$\displaystyle
P\Big{(}U_{1}<U_{5},U_{6}|\\{U_{3}<U_{5}\\}\cap\big{\\{}\\{U_{3}<U_{7}\\}\cup\\{U_{4}<U_{8}\\}\big{\\}}\Big{)}=\frac{861}{2100}=0.41>$
$\displaystyle
P\Big{(}U_{1}<U_{5},U_{6}|\\{U_{3}<U_{5}\\}\cap\\{U_{3}<U_{7}\\}\cap\\{U_{4}<U_{8}\\}\Big{)}=\frac{336}{840}=0.4.$
(28)

####  2.1.1 Computations

We have developed a computational pipeline for checking whether an inequality
of the form (22) holds for specific cases, by exhaustive counting of all of
the permutations induced by the partial ordering events specified by
$F_{t},H_{s}$. When $T=S=1$, the problem reduces to counting linear extensions
of a partial order induced by the $E_{ij}$ events.

For a general partial order, it was shown in [41] that counting the number of
linear extensions is $\\#P$-complete. When $T>1$, exact counting of the number
of total orders consistent with the restrictions imposed by the $F_{t},H_{s}$
sets is even harder. For some specific cases the computation might be easier -
for example, the number of linear extensions of a partial order given by a
chain over $m\leq n$ variables (e.g. $U_{1}<U_{3}<U_{7}$ for $m=3<n=7$), is
$\frac{n!}{m!}$ by symmetry.

There are known polynomial randomized approximation algorithms for the general
case [42]. However, these algorithms only yield an approximate answer, hence
to verify whether the inequality (22) holds for specific cases, we may need to
run them to until the error in estimating event probabilities is smaller than
$\frac{1}{n!}$, or alternatively use them as a first filtering step, and turn
to exact exhaustive computation when the randomized approach provides evidence
for a violation of the inequality.

The above techniques are implemented in a python code for checking whether the
inequality (22) holds for a particular set collection
$\\{F_{1},..,F_{T};H_{1},..,H_{S}\\}$, and for finding putative counter-
example by either sampling such sets collections, or by an exhaustive
enumeration over the possible sets $F_{t},H_{s}$ of given sizes. The code can
be used for small values of $n$, and is available at
https://github.com/orzuk/Pareto. For example, the following command verifies
the counter-example (27),
$>>>$ check_CNF_DNF_inequality(9, [[(1, 4)], [(1, 4), (2, 4)]] , [[(1, 3)],
[(1, 3), (2, 3)]])
(False, 861, 336, 2100, 840)

The next command was used to verify Conjecture 1 for $n\leq 12,m\leq 4,T\leq
3$ by enumerating all $\sim\\!10^{6}$ possible subset collections up to these
sizes, running for $\sim\\!35$ hours on a standard laptop PC, and failing to
find a counter-example among them:
$>>>$ find_enumerate_counter_example_DNF_CNF_inequality(n = 12, num_edges = 4,
num_sets = 3)
False

While more efficient algorithms and code are available for counting linear
extensions of partial orders, for either the general case or special partial
orders (see e.g. [43, 44, 45, 46]), they can be applied directly only for the
case $T=S=1$. Addressing the more general case requires developing new
algorithms for efficient counting or enumeration of the total orders
consistent with intersections of unions of pairwise ordering events - such
algorithms may be used in in order to provide evidence for proposed putative
inequalities or find novel counter-examples for small value of $n$, and may be
of independent interest in combinatorial applications. These computational
improvements, as well as deriving and proving rigorously generalizations of
Theorem 2 such as Conjecture 1, are left for future work.

##  3 Some related results

###  3.1 Asymptotic independence

One possible application of Theorem 2 is given by the next theorem:

###### Theorem 3

For every $n\geq 1$, let

$p_{n}\equiv P(E_{1,n})\ \ ,\ \ e_{n}\equiv P(E_{1,n}\cap E_{2,n})\,.$ (29)

  1. 1.

For every $k\geq 1$

$e_{n}=\sum\limits_{\begin{subarray}{c}a,b,c,d\in\mathbb{Z}_{+}:\\\
a+b+c+d=n-2\end{subarray}}(-1)^{a+b}\binom{n-2}{a\>b\>c\>d}\frac{(a+b+2c+2)^{k}-(b+c+1)^{k}-(a+c+1)^{k}}{(a+c+1)^{k}(b+c+1)^{k}(a+b+c+2)^{k}}\,.$
(30)

  2. 2.

If $k>1$, then

$e_{n}\sim p^{2}_{k,n}\sim\left[\frac{\log^{k-1}(n)}{n(k-1)!}\right]^{2}\ \
\text{as}\ \ n\to\infty$ (31)

and hence

$\rho_{k,n}\equiv\text{Corr}(\textbf{1}_{E_{1,n}},\textbf{1}_{E_{2,n}})=o\left[\frac{\log^{k-1}(n)}{n}\right]\
\ \text{as}\ \ n\to\infty\,.$ (32)

###### Remark 4

In the current analysis $k$ is a fixed parameter of the model. In particular,
it is a parameter of the events $E_{1,n},E_{2,n},\ldots,E_{n,n}$ and
correspondingly it appears in the expressions of $p_{n}$ and $e_{n}$. At the
same time, $k$ remains constant all over the analysis to follow. Consequently,
for brevity, it is suppressed in the notations: $E_{i,n}$, $p_{n}$ and
$e_{n}$.

The first part of Theorem 3 includes a combinatorial expression for $e_{n}$
which is, to the best of our knowledge, a new one. Theorem 2 is applied in
order to provide an elementary proof for the second part of Theorem 3.
Importantly, an alternative proof for the second part of Theorem 3 stems from
existing results. Specifically, it is well-known (see, e.g., Theorems 3 and 4
in [31]) that

$p_{n}=\sum_{u=1}^{n}\binom{n-1}{u-1}\frac{(-1)^{u-1}}{u^{k}}$ (33)

and

$p_{n}\sim\frac{\log^{k-1}(n)}{n(k-1)!}\ \ \text{as}\ \ n\to\infty\,.$ (34)

The main result of [34] implies that there exists a constant $C_{k}>0$ such
that for every $k>1$

$\text{Var}\left(\sum_{i=1}^{n}\textbf{1}_{E_{i,n}}\right)\sim
C_{k}\log^{k-1}(n)\ \ \text{as}\ \ n\to\infty\,.$ (35)

Thus, because

$\displaystyle\text{Var}\left(\sum_{i=1}^{n}\textbf{1}_{E_{i,n}}\right)$
$\displaystyle=\sum_{i=1}^{n}\text{Var}\left(\textbf{1}_{E_{i,n}}\right)+2\sum_{i=1}^{n}\sum_{j=i+1}^{n}\text{Cov}(\textbf{1}_{E_{i,n}},\textbf{1}_{E_{j,n}})$
(36)
$\displaystyle=n\text{Var}(Z_{1})+n(n-1)\left\\{\mathbb{E}\left(\textbf{1}_{E_{1,n}}\textbf{1}_{E_{2,n}}\right)-\left[\mathbb{E}\left(\textbf{1}_{E_{1,n}}\right)\right]^{2}\right\\}$
$\displaystyle=np_{n}(1-p_{n})+n(n-1)(e_{n}-p_{n}^{2})\,,$

it is possible to deduce that

$\lim_{n\to\infty}\frac{e_{n}}{p_{n}^{2}}=1+\lim_{n\to\infty}\frac{\text{Var}(\sum_{i=1}^{n}\textbf{1}_{E_{i,n}})}{(np_{n})^{2}}-\lim_{n\to\infty}\frac{1}{np_{n}}=1\,.$
(37)

###  3.2 A limit theorem

In this part, we consider a sequence of models: For each $n\in\mathbb{N}$
assume that $X_{1}^{n},X_{2}^{n},\ldots,X_{m_{n}}^{n}$ are i.i.d. random
vectors distributed uniformly in the unit hypercube $[0,1]^{k}$. For every
$n\in\mathbb{N}$ and $i\in[m_{n}]$ denote the event

$E_{i,n}\equiv\big{\\{}X_{i}\text{ is a maximum of
$\\{X_{1}^{n},X_{2}^{n},\ldots,X_{m_{n}}^{n}\\}$}\big{\\}}\,,$ (38)

and the corresponding indicator $Z_{ni}\equiv\textbf{1}_{E_{i,n}}$. Since $k$
remains fixed we keep suppressing it in the notations. An implication of
Theorem 3 is addressed in the following theorem:

###### Theorem 4

  1. 1.

If $m_{n}=n$ for every $n\in\mathbb{N}$, then for every $k\in\mathbb{N}$:

$\frac{1}{np_{n}}\sum_{i=1}^{n}Z_{i}^{k,n}\rightarrow 1\ \ \text{as}\ \
n\to\infty\ \ \text{in}\ \ L^{2}(P)\,.$ (39)

  2. 2.

Let $(m_{n})_{n=1}^{\infty}$ be a sequence of positive integers such that
$\lim\limits_{n\to\infty}\frac{n}{m_{n}}=\gamma\in(0,1)$ and assume that
$k>1$. For any $n\geq 1$ and $i\in[m_{n}]$ denote

$U_{ni}\equiv\frac{Z_{ni}-p_{m_{n}}}{\sqrt{p_{m_{n}}(1-p_{m_{n}})}}\,.$ (40)

Then,

$\sqrt{n}\left(\frac{1}{n}\sum_{i=1}^{n}U_{ni}-\frac{1}{m_{n}}\sum_{i=1}^{m_{n}}U_{ni}\right)\xrightarrow{d}\mathcal{N}(0,1-\gamma)\
\ \text{as }n\to\infty\,.$ (41)

  3. 3.

For any $k>1$, there exists a sequence $(m_{n})_{n=1}^{\infty}$ of positive
integers such that

$n\ll m_{n}\ll n\log^{k}n,$ (42)

and:

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}U_{ni}\xrightarrow{d}\mathcal{N}(0,1)\ \
\text{as }n\to\infty\,.$ (43)

###### Remark 5

The set of maxima of a set of vectors is usually called the Pareto-front of
that set. Thus, the first part of Theorem 4 is an $L^{2}(P)$ version of a law
of large numbers for the size of the Pareto-front. The second part of Theorem
4 might be interpreted as a CLT for the difference between the normalized size
of the Pareto-front and a normalized size of a partial Pareto-front. The third
part provides a CLT for the size of a certain fraction of the Pareto-front.

###### Remark 6

The second and third parts of Theorem 4 show a CLT for partial sums of the
indicator variables $Z_{ni}=\textbf{1}_{E_{i,n}}$. Importantly, they cannot be
deduced directly from the CLT given in [35] for the entire sum
$\sum\limits_{i=1}^{n}\textbf{1}_{E_{i,n}}$ (with $m_{n}=n$ for every
$n\in\mathbb{N}$). It is also unclear if they can be used in order to deduce
the CLT given in [35].

###  3.3 Proofs

####  3.3.1 Proof of Theorem 3

###### Lemma 1

Let $W_{1},..,W_{n}$ be exchangeable random variables such that
$W_{1}\sim\text{Ber}(p)$ for some $p\in(0,1)$ and denote
$W\equiv\sum\limits_{j=1}^{n}W_{j}$. Then,

$\mathbb{E}(W|W_{1}=1)\geq np.$ (44)

Proof: Since $W_{1},W_{2},\ldots,W_{n}$ are exchangeable, then Bayes’ theorem
with the Cauchy-Schwartz inequality yields that

$\displaystyle\mathbb{E}(W|W_{1}=1)$
$\displaystyle=\sum_{i=0}^{n}P(W=i|W_{1}=1)i$
$\displaystyle=\sum_{i=0}^{n}\frac{P(W=i)}{P(W_{1}=1)}P(W_{1}=1|W=i)i$
$\displaystyle=\frac{1}{p}\sum_{i=0}^{n}P(W=i)i^{2}$
$\displaystyle=n\frac{\mathbb{E}(W^{2})}{\mathbb{E}(W)}\geq\frac{[\mathbb{E}(W)]^{2}}{\mathbb{E}(W)}=\mathbb{E}(W)=np.$
(45)

#### Proof (Theorem 3):

  1. 1.

For every $i\in[n]$ and $j\in[k]$ let $X_{ij}$ be the $j$-th coordinate of the
vector $X_{i}$. In addition, let $x_{1},x_{2}\in[0,1]^{k}$ such that for every
$i=1,2$, $x_{i}=(x_{i1},x_{i2},\ldots,x_{ik})$. Then, conditioning on the
values of $X_{1}$ and $X_{2}$ yields that

$\displaystyle e_{n}$
$\displaystyle=\int_{[0,1]^{2k}}\textbf{1}_{\\{x_{1}\not\prec
x_{2},x_{2}\not\prec
x_{1}\\}}P\left(\bigcap_{i=3}^{n}\bigcap_{m=1}^{2}\bigcup_{j=1}^{k}\\{X_{ij}>x_{mj}\\}\right)dx_{1}dx_{2}$
$\displaystyle=\int_{[0,1]^{2k}}\textbf{1}_{\\{x_{1}\not\prec
x_{2},x_{2}\not\prec
x_{1}\\}}\left[P\left(\bigcap_{m=1}^{2}\bigcup_{j=1}^{k}\\{X_{3j}>x_{mj}\\}\right)\right]^{n-2}dx_{1}dx_{2}\,.$
(46)

The probabilities that appear inside the integral above are as follows:

$\displaystyle
P\left(\bigcap_{m=1}^{2}\bigcup_{j=1}^{k}\\{X_{3j}>x_{mj}\\}\right)$
$\displaystyle=1-P\left(\bigcap_{j=1}^{k}\\{X_{3j}<x_{1j}\\}\right)-P\left(\bigcap_{j=1}^{k}\\{X_{3j}<x_{2j}\\}\right)$
$\displaystyle+P\left(\bigcap_{j=1}^{k}\big{\\{}X_{3j}<\min\\{x_{1j},x_{2j}\\}\big{\\}}\right)$
$\displaystyle=1-\prod_{j=1}^{k}x_{1j}-\prod_{j=1}^{k}x_{2j}+\prod_{j=1}^{k}\min\\{x_{1j},x_{2j}\\}\,.$
(47)

Thus, using the multinomial theorem deduce that

$\displaystyle e_{n}$
$\displaystyle=\int_{[0,1]^{2k}}\Big{(}1-\prod_{j=1}^{k}\textbf{1}_{\\{x_{1j}<x_{2j}\\}}-\prod_{j=1}^{k}\textbf{1}_{\\{x_{1j}>x_{2j}\\}}\Big{)}$
$\displaystyle\Big{(}1-\prod_{j=1}^{k}x_{1j}-\prod_{j=1}^{k}x_{2j}+\prod_{j=1}^{k}\min\\{x_{1j},x_{2j}\\}\Big{)}^{n-2}dx_{1}dx_{2}$
$\displaystyle=\int_{[0,1]^{2k}}\Big{(}1-\prod_{j=1}^{k}\textbf{1}_{\\{x_{1j}<x_{2j}\\}}-\prod_{j=1}^{k}\textbf{1}_{\\{x_{1j}>x_{2j}\\}}\Big{)}$
$\displaystyle\sum\limits_{\begin{subarray}{c}a,b,c,d\in\mathbb{Z}_{+}:\\\
a+b+c+d=n-2\end{subarray}}(-1)^{a+b}\binom{n-2}{a\>b\>c\>d}\left(\prod_{j=1}^{k}x_{1j}\right)^{a}\left(\prod_{j=1}^{k}x_{2j}\right)^{b}\left(\prod_{j=1}^{k}\min\\{x_{1j},x_{2j}\\}\right)^{c}dx_{1}dx_{2}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}a,b,c,d\in\mathbb{Z}_{+}:\\\
a+b+c+d=n-2\end{subarray}}(-1)^{a+b}\binom{n-2}{a\>b\>c\>d}\Bigg{[}\prod_{j=1}^{k}\int_{0}^{1}\int_{0}^{1}x_{1j}^{a}x_{2j}^{b}\big{(}\min\\{x_{1j},x_{2j}\\}\big{)}^{c}dx_{1j}dx_{2j}$
$\displaystyle-\prod_{j=1}^{k}\int_{0}^{1}\int_{0}^{x_{2j}}x_{1j}^{a}x_{2j}^{b}\big{(}\min\\{x_{1j},x_{2j}\\}\big{)}^{c}dx_{1j}dx_{2j}$
$\displaystyle-\prod_{j=1}^{k}\int_{0}^{1}\int_{0}^{x_{1j}}x_{1j}^{a}x_{2j}^{b}\big{(}\min\\{x_{1j},x_{2j}\\}\big{)}^{c}dx_{2j}dx_{1j}\Bigg{]}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}a,b,c,d\in\mathbb{Z}_{+}:\\\
a+b+c+d=n-2\end{subarray}}(-1)^{a+b}\binom{n-2}{a\>b\>c\>d}\Bigg{[}\left(\frac{a+b+2c+2}{(a+c+1)(b+c+1)(a+b+c+2)}\right)^{k}$
$\displaystyle-\left(\frac{1}{(a+c+1)(a+b+c+2)}\right)^{k}-\left(\frac{1}{(b+c+1)(a+b+c+2)}\right)^{k}\Bigg{]}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}a,b,c,d\in\mathbb{Z}_{+}:\\\
a+b+c+d=n-2\end{subarray}}(-1)^{a+b}\binom{n-2}{a\>b\>c\>d}\frac{(a+b+2c+2)^{k}-(b+c+1)^{k}-(a+c+1)^{k}}{(a+c+1)^{k}(b+c+1)^{k}(a+b+c+2)^{k}}\
.$ (48)

  2. 2.

The proof of Eq. (31) will follow from the next squeezing argument.

    1. (a)

Applying Lemma 1 to the indicator random variables
$\textbf{1}_{E_{1,n}},\textbf{1}_{E_{2,n}},\ldots,\textbf{1}_{E_{n,n}}$
implies that

$\mathbb{E}\left(\sum_{i=1}^{n}\textbf{1}_{E_{i,n}}\ \big{|}\
\textbf{1}_{E_{1,n}}=1\right)=1+(n-1)\frac{e_{n}}{p_{n}}\geq np_{n}.$ (49)

As a result deduce that

$\frac{e_{n}}{p^{2}_{k,n}}\geq\frac{n}{n-1}-\frac{1}{p_{n}(n-1)}\,.$ (50)

Thus, since $np_{n}\rightarrow\infty$ as $n\to\infty$, deduce that the lower
bound tends to one as $n\to\infty$.

    2. (b)

Next we prove that there exists an upper bound of $\frac{e_{n}}{p^{2}_{k,n}}$
which tends to one as $n\to\infty$. To this end, observe that

$\displaystyle e_{n}$
$\displaystyle=P\left(\bigcap_{i=1}^{2}\bigcap_{j\in[n]\setminus\\{i\\}}\overline{B_{ij}}\right)$
$\displaystyle\leq
P\left(\bigcap_{i=1}^{2}\bigcap_{j=3}^{n}\overline{B_{ij}}\right)$
$\displaystyle=P\left(\bigcap_{j=3}^{n}\overline{B_{1j}}\right)P\left(\bigcap_{j=3}^{n}\overline{B_{2j}}\
\big{|}\ \bigcap_{j=3}^{n}\overline{B_{1j}}\right)$ $\displaystyle\leq
p_{k,n-1}P\left(\bigcap_{j=3}^{n}\overline{B_{2j}}\ \big{|}\
\bigcap_{j=3}^{n}B_{j1}\right)$
$\displaystyle=p_{k,n-1}\left[1-P\left(\bigcup_{j=3}^{n}B_{2j}\ |\
\bigcap_{j=3}^{n}B_{j1}\right)\right]$
$\displaystyle=p_{k,n-1}\left[1+\sum_{u=2}^{n-2}\binom{n-2}{u-1}(-1)^{u-1}P\left(\bigcap_{j=3}^{u+1}B_{2j}\
\big{|}\ \bigcap_{j=3}^{n}B_{j1}\right)\right].$ (51)

The second inequality above follows from Theorem 2. The last two lines are due
to De-Morgan’s laws with an inclusion-exclusion principle. The next step is to
evaluate the probability
$P(\bigcap\limits_{j=3}^{u+1}B_{2j}|\bigcap\limits_{j=3}^{n}B_{j1})$ for
$u\geq 2$. The set $\\{X_{ij};i\in[n],j\in[k]\\}$ contains i.i.d. random
variables with a continuous distribution and hence symmetry considerations
yield that

$\displaystyle P\left(\bigcap_{j=3}^{u+1}B_{2j}\ \big{|}\
\bigcap_{j=3}^{n}B_{j1}\right)$
$\displaystyle=P\left(\bigcap_{j=3}^{u+1}\bigcap_{l=1}^{k}\\{X_{2l}\leq
X_{jl}\\}\ \big{|}\ \bigcap_{j=3}^{n}\bigcap_{l=1}^{k}\\{X_{jl}\leq
X_{1l}\\}\right)$ $\displaystyle=\left[P\left(\bigcap_{j=3}^{u+1}\\{X_{21}\leq
X_{j1}\\}\ \big{|}\ \bigcap_{j=3}^{n}\\{X_{j1}\leq
X_{11}\\}\right)\right]^{k}$
$\displaystyle=\left\\{\frac{P\left[\left(\bigcap\limits_{j=3}^{u+1}\\{X_{21}\leq
X_{j1}\\}\right)\cap\left(\bigcap\limits_{j=3}^{n}\\{X_{j1}\leq
X_{11}\\}\right)\right]}{P\left(\bigcap\limits_{j=3}^{n}\\{X_{j1}\leq
X_{11}\\}\right)}\right\\}^{k}$
$\displaystyle=\left(\frac{\frac{1}{n}\cdot\frac{1}{u}}{\frac{1}{n-1}}\cdot\right)^{k}$
$\displaystyle=\left(\frac{n-1}{nu}\right)^{k}\,.$ (52)

Plugging Eq. (52) into Eq. (51) and using Eq. (33) with the binomial theorem
gives,

$\displaystyle\frac{e_{n}}{p^{2}_{k,n}}$
$\displaystyle\leq\frac{p_{k,n-1}}{p^{2}_{k,n}}\left[1+\left(\frac{n-1}{n}\right)^{k}\sum_{u=2}^{n-2}\binom{n-2}{u-1}(-1)^{u-1}u^{-k}\right]$
$\displaystyle=\frac{p_{k,n-1}}{p^{2}_{k,n}}\left[1+\left(\frac{n-1}{n}\right)^{k}(p_{k,n-1}-1)\right]$
$\displaystyle=\left(\frac{n-1}{n}\right)^{k}\left(\frac{p_{k,n-1}}{p_{n}}\right)^{2}+\frac{1}{p_{n}}\left[1-\left(1-\frac{1}{n}\right)^{k}\right]\frac{p_{k,n-1}}{p_{n}}$
$\displaystyle=\left(\frac{n-1}{n}\right)^{k}\left(\frac{p_{k,n-1}}{p_{n}}\right)^{2}+\frac{p_{k,n-1}}{p_{n}}\cdot\frac{1}{np_{n}}\sum_{u=1}^{k}\binom{k}{u}\left(-\frac{1}{n}\right)^{u-1}\,.$

Finally, $np_{n}\rightarrow\infty$ and $p_{k,n-1}/p_{n}\rightarrow 1$ as
$n\to\infty$ imply that the upper bound above tends to one as $n\to\infty$.

Once we have established the proof of Eq. (31), it is possible to prove Eq.
(32). To this end, observe that

$\lim_{n\to\infty}\frac{e_{n}-p_{n}^{2}}{\left[\frac{\log^{k-1}(n)}{n(k-1)!}\right]^{2}}=1-1=0$
(53)

and hence

$e_{n}-p_{n}^{2}=o\left(\left[\frac{\log^{k-1}(n)}{n(k-1)!}\right]^{2}\right)\
\ \text{as}\ \ n\to\infty\,.$ (54)

Thus, since

$\rho_{k,n}=\frac{e_{n}-p_{n}^{2}}{p_{n}(1-p_{n})}\,,$ (55)

then Eq. (32) follows.

####  3.3.2 Proof of Theorem 4

###### Lemma 2

If $np_{m_{n}}\rightarrow\infty$ as $n\to\infty$, then:

$\frac{1}{n}\sum_{i=1}^{n}U_{ni}^{2}\rightarrow 1\ \ \text{as}\ \ n\to\infty\
\ \text{in}\ \ L^{2}(P)\,.$ (56)

Proof: By definition
$U_{ni}^{2}=\frac{(Z_{ni}-p_{m_{n}})^{2}}{p_{m_{n}}(1-p_{m_{n}})}$ with
$Z_{ni}\sim\text{Ber}(p_{m_{n}})$ and hence

$\displaystyle EU_{n1}^{4}$
$\displaystyle=E\left[\frac{\left(Z_{n1}-p_{m_{n}}\right)^{4}}{p_{m_{n}}^{2}\left(1-p_{m_{n}}\right)^{2}}\right]$
$\displaystyle=\frac{p_{m_{n}}\left(1-p_{m_{n}}\right)^{4}+\left(1-p_{m_{n}}\right)p_{m_{n}}^{4}}{p_{m_{n}}^{2}\left(1-p_{m_{n}}\right)^{2}}$
$\displaystyle=\frac{(1-p_{m_{n}})^{2}}{p_{m_{n}}}+\frac{p_{m_{n}}^{2}}{1-p_{m_{n}}}\
.$ (57)

Thus, the assumption that $\underset{n\to\infty}{\lim}np_{m_{n}}=\infty$
implies that

$\lim_{n\to\infty}\frac{EU^{4}_{n1}}{n}=\lim_{n\to\infty}\left[\frac{\left(1-p_{m_{n}}\right)^{2}}{np_{m_{n}}}+\frac{p_{m_{n}}^{2}}{n(1-p_{m_{n}})}\right]=0\
.$ (58)

Similarly,

$\displaystyle EU_{n1}^{2}U_{n2}^{2}$
$\displaystyle=E\left[\frac{\left(Z_{n1}-p_{m_{n}}\right)^{2}\left(Z_{n2}-p_{m_{n}}\right)^{2}}{p_{m_{n}}^{2}\left(1-p_{m_{n}}\right)^{2}}\right]$
$\displaystyle=\frac{E\left[\left(Z_{n1}\left(1-2p_{m_{n}}\right)+p_{m_{n}}^{2}\right)\left(Z_{n2}\left(1-2p_{m_{n}}\right)+p_{m_{n}}^{2}\right)\right]}{p_{m_{n}}^{2}\left(1-p_{m_{n}}\right)^{2}}$
$\displaystyle=\frac{\left(1-2p_{m_{n}}\right)^{2}e_{k,m_{n}}+2p_{m_{n}}^{3}\left(1-2p_{m_{n}}\right)+p_{m_{n}}^{4}}{p_{m_{n}}^{2}\left(1-p_{m_{n}}\right)^{2}}$
$\displaystyle=\left(\frac{1-2p_{m_{n}}}{1-p_{m_{n}}}\right)^{2}\frac{e_{k,m_{n}}}{p_{m_{n}}^{2}}+\frac{2p_{m_{n}}-3p_{m_{n}}^{2}}{\left(1-p_{m_{n}}\right)^{2}}\
.$ (59)

Using Theorem 3 and recalling that $p_{m_{n}}\rightarrow 0$ as $n\to\infty$,
deduce that

$\lim_{n\to\infty}EU_{n1}^{2}U_{n2}^{2}=\lim_{n\to\infty}\frac{e_{k,m_{n}}}{p_{m_{n}}^{2}}=1\
.$ (60)

In addition, standard calculations yield that

$\displaystyle\text{Var}\left(\frac{1}{n}\sum_{i=1}^{n}U^{2}_{ni}\right)$
$\displaystyle=\frac{\text{Var}(U^{2}_{n1})}{n}+\frac{n-1}{n}\text{Cov}\left(U_{n1}^{2},U_{n2}^{2}\right)$
(61)
$\displaystyle=\frac{EU^{4}_{n1}-1}{n}+\frac{n-1}{n}\left(EU_{n1}^{2}U_{n2}^{2}-1\right)$

and hence Eqs. (58), (60) imply that

$\text{Var}\left(\frac{1}{n}\sum_{i=1}^{n}U^{2}_{ni}\right)\rightarrow 0\ \
\text{as}\ \ n\to\infty\,.$ (62)

Finally, the result follows since for each $n\geq 1$,
$E[\frac{1}{n}\sum\limits_{i=1}^{n}U^{2}_{ni}]=1$.

#### Proof (Theorem 4):

  1. 1.

For $k=1$, the proof is immediate. Assume that $k>1$ and $m_{n}=n$ for every
$n\geq 1$. Then by Eq. (32), $n\rho_{k,m_{n}}=n\rho_{k,n}\rightarrow\infty$ as
$n\to\infty$. Therefore, Lemma 2 implies that

$\frac{1}{n}\sum_{i=1}^{n}U_{ni}^{2}\rightarrow 1\ \ \text{as}\ \ n\to\infty\
\ \text{in}\ \ L^{2}(P)\,.$ (63)

Since $Z_{ni}^{2}=Z_{ni}$ for each $i\in[n]$, then

$\frac{1}{n}\sum_{i=1}^{n}U_{ni}^{2}=\frac{(1-2p_{n})\frac{1}{n}\sum_{i=1}^{n}Z_{ni}+p_{n}^{2}}{p_{n}(1-p_{n})}\rightarrow
1\ \ \text{as}\ \ n\to\infty\ \ \text{in}\ \ L^{2}(P)$ (64)

and the result follows because $p_{n}\rightarrow 0$ as $n\to\infty$.

  2. 2.

$\left\\{U_{ni};n\geq 1,i\in[m_{n}]\right\\}$ is a triangular array and by
symmetry, for each $n\in\mathbb{N}$ the random variables
$U_{n1},U_{n2},\ldots,U_{nm_{n}}$ are exchangeable. Moreover, by construction
$EU_{ni}=0$ and $EU^{2}_{ni}=1$ for every $n\geq 1$, $i\in[n]$. Thus, in order
to complete the proof, it is left to verify that the pre-conditions of Theorem
2 in [39] are satisfied. To this end, recall that
$\frac{n}{m_{n}}\rightarrow\gamma\in(0,1)$ as $n\to\infty$ and observe that

$\lim_{n\to\infty}np_{m_{n}}=\lim_{n\to\infty}\frac{n}{m_{n}}\cdot\frac{\log^{k-1}(m_{n})}{(k-1)!}=\infty\,.$
(65)

    1. (a)

Eq. (32) yields that

$EU_{n1}U_{n2}=\rho_{k,m_{n}}\rightarrow 0\ \ \text{as}\ \ n\to\infty\,.$ (66)

    2. (b)

Since $p_{m_{n}}\rightarrow 0$ as $n\to\infty$, then $p_{m_{n}}<\frac{1}{2}$
for every sufficiently large $n\geq 1$. Therefore, using Eq. (65), deduce that
for every such $n$

$n^{-\frac{1}{2}}\max_{1\leq i\leq
m_{n}}|U_{ni}|\leq\frac{1-p_{m_{n}}}{\sqrt{n}\sqrt{p_{m_{n}}(1-p_{m_{n}})}}<\frac{1}{\sqrt{np_{m_{n}}}}\underset{n\to\infty}{\longrightarrow}0\,.$
(67)

    3. (c)

Due to Eq. (65), it is possible to apply Lemma 2 in order to deduce that

$\frac{1}{n}\sum_{i=1}^{n}U_{ni}^{2}\rightarrow 1\ \ \text{as}\ \ n\to\infty\
\ \text{in}\ \ L^{2}(P)\,.$ (68)

This convergence also yields convergence in probability and the last pre-
condition of Theorem 2 in [39] follows.

  3. 3.

Since $\rho_{k,n}=o\left(\frac{\log^{k-1}(n)}{n}\right)$, there exists a
positive decreasing function $g(n)$ such that:

(i)

$|\rho_{k,n}|\leq\frac{\log^{k-1}(n)}{n}g(n)$ for every $n\in\mathbb{N}$ large
enough.

(ii)

$g(n)\downarrow 0$ as $n\to\infty$.

(for example, take $g(n)\equiv\underset{n^{\prime}\geq
n}{\sup}\frac{|\rho_{k,n^{\prime}}|n^{\prime}}{\log^{k-1}(n^{\prime})}$).
Then, for each $n\in\mathbb{N}$, define

$m_{n}\equiv\min\left\\{m\in\mathbb{N}\ ;\
n<\frac{m}{\log^{k-1}(m)\max\big{(}\sqrt{g(m)},1/\sqrt{\log
m}\big{)}}\right\\}$ (69)

and note that $m_{n}<\infty$. The proof will follow by verifying that the
following four pre-conditions of Corollary 1 in [39] are satisfied.

    1. (a)

First, (69) and the definition of $g(n)$ imply that for $n$ large enough,

$\displaystyle n|\rho_{k,m_{n}}|$
$\displaystyle\leq\frac{m_{n}}{\max\big{(}\sqrt{g(m_{n})},1/\sqrt{\log(m_{n})}\big{)}\log^{k-1}(m_{n})}\cdot\frac{\log^{k-1}(m_{n})}{m_{n}}g(m_{n})$
$\displaystyle=\min\big{(}\sqrt{g(m_{n})},g(m_{n})\sqrt{\log(m_{n})}\big{)}\underset{n\to\infty}{\longrightarrow}0.$
(70)

    2. (b)

Next, the definition of $m_{n}$ yields that for every $n\geq 1$,

$n\geq\frac{m_{n}-1}{\log^{k-1}(m_{n}-1)\max\big{(}\sqrt{g(m_{n}-1)},1/\sqrt{\log(m_{n}-1)}\big{)}}\,.$
(71)

In addition, the first order approximation (34) implies that
$p_{m_{n}}>\frac{1}{2}\frac{\log^{k-1}(m_{n})}{(k-1)!m_{n}}$ for every
sufficiently large $n$. Combining the two inequalities gives as $n\to\infty$:

$\displaystyle np_{m_{n}}$
$\displaystyle>\frac{m_{n}-1}{\log^{k-1}(m_{n}-1)\max\big{(}\sqrt{g(m_{n}-1)},1/\sqrt{\log(m_{n}-1)}\big{)}}\cdot\frac{\log^{k-1}(m_{n})}{2(k-1)!m_{n}}$
$\displaystyle\sim\frac{1}{2(k-1)!\max\big{(}\sqrt{g(m_{n}-1)},1/\sqrt{\log(m_{n}-1)}\big{)}}\underset{n\to\infty}{\longrightarrow}\infty.$
(72)

Therefore, in similar to Eq. (67),

$n^{-\frac{1}{2}}\max_{1\leq i\leq
m_{n}}|U_{ni}|<\frac{1}{\sqrt{np_{m_{n}}}}\underset{n\to\infty}{\longrightarrow}0.$
(73)

    3. (c)

By Eq. (72), $np_{m_{n}}\underset{n\to\infty}{\longrightarrow}\infty$. Hence,
Lemma 2 yields that

$\frac{1}{n}\sum_{i=1}^{n}U_{ni}^{2}\rightarrow 1\ \ \text{as}\ \ n\to\infty\
\ \text{in}\ \ L^{2}(P)$ (74)

and this result implies convergence in probability.

    4. (d)

Finally,

$\frac{n}{m_{n}}<\min\left[\frac{1}{\sqrt{g(m_{n})}\log^{k-1}(m_{n})}\ ,\
\frac{1}{\log^{k-3/2}(m_{n})}\right]\underset{n\to\infty}{\longrightarrow}0.$
(75)

Since the above four conditions are satisfied, by Corollary 1 in [39], the
Gaussian limit in Eq. (43) holds. By condition (75) above, $n\ll m_{n}$.
Because $g(m)<1$ for $m$ large enough, we get from Eq. (69) that
$n>c\frac{m_{n}}{\log^{k-1}(m_{n})}$ for some $c>0$. Therefore, for $m_{n}$
large enough,

$n\log^{k-1}n>c\frac{m_{n}}{\log^{k-1}(m_{n})}\Big{[}\log c+\log
m_{n}-\log\big{(}\log^{k-1}(m_{n})\big{)}\Big{]}^{k-1}>c\frac{m_{n}\big{(}\frac{1}{2}\log(m_{n})\big{)}^{k-1}}{\log^{k-1}(m_{n})}=\frac{c}{2^{k-1}}m_{n}$
(76)

which gives $m_{n}<c^{\prime}n\log^{k-1}(n)$ for some $c^{\prime}>0$ and hence
$m_{n}\ll n\log^{k}(n)$, completing the proof of the theorem.

## References

  * [1] Robert B Griffiths.  Correlations in ising ferromagnets. i.  Journal of Mathematical Physics, 8(3):478–483, 1967.
  * [2] Jean Ginibre.  General formulation of griffiths’ inequalities.  Communications in Mathematical Physics, 16(4):310–328, 1970.
  * [3] Jacob Van Den Berg and Harry Kesten.  Inequalities with applications to percolation and reliability.  Journal of Applied Probability, 22(3):556–569, 1985.
  * [4] Loren D Pitt.  A Gaussian correlation inequality for symmetric convex sets.  The Annals of Probability, 5(3):470–474, 1977.
  * [5] Wenbo Li.  A Gaussian correlation inequality and its applications to small ball probabilities.  Electronic Communications in Probability, 4:111–118, 1999.
  * [6] Qi-Man Shao.  A Gaussian correlation inequality and its applications to the existence of small ball constant.  Stochastic Processes and their Applications, 107(2):269–287, 2003\.
  * [7] Samuel Karlin and Yosef Rinott.  Classes of orderings of measures and related correlation inequalities. i. multivariate totally positive distributions.  Journal of Multivariate Analysis, 10(4):467–498, 1980.
  * [8] Samuel Karlin and Yosef Rinott.  Classes of orderings of measures and related correlation inequalities ii. multivariate reverse rule distributions.  Journal of Multivariate Analysis, 10(4):499–516, 1980.
  * [9] Samuel Karlin and Yosef Rinott.  Total positivity properties of absolute value multinormal variables with applications to confidence interval estimates and related probabilistic inequalities.  The Annals of Statistics, 9(5):1035–1049, 1981.
  * [10] Yosef Rinott and Michael Saks.  Correlation inequalities and a conjecture for permanents.  Combinatorica, 13(3):269–277, 1993.
  * [11] Cees M Fortuin, Pieter W Kasteleyn, and Jean Ginibre.  Correlation inequalities on some partially ordered sets.  Communications in Mathematical Physics, 22(2):89–103, 1971.
  * [12] David Barbato.  FKG inequality for brownian motion and stochastic differential equations.  Electronic Communications in Probability, 10:7–16, 2005.
  * [13] Peter C Fishburn, Peter G Doyle, and Larry A Shepp.  The match set of a random permutation has the FKG property.  The Annals of Probability, 16(3):1194–1214, 1988.
  * [14] Günter Last and Mathew D Penrose.  Poisson process fock space representation, chaos expansion and covariance inequalities.  Probability theory and related fields, 150(3):663–690, 2011.
  * [15] Lawrence A Shepp.  The XYZ conjecture and the FKG inequality.  The Annals of Probability, pages 824–827, 1982.
  * [16] Vincent Tassion.  Crossing probabilities for voronoi percolation.  The Annals of Probability, 44(5):3385–3398, 2016.
  * [17] Augusto Teixeira.  Interlacement percolation on transient weighted graphs.  Electronic Journal of Probability, 14:1604–1627, 2009.
  * [18] J Van Den Berg and A Gandolfi.  LRU is better than FIFO under the independent reference model.  Journal of Applied Probability, 29(1):239–243, 1992.
  * [19] Peter C Fishburn.  A correlational inequality for linear extensions of a poset.  Order, 1(2):127–137, 1984.
  * [20] Ronald L Graham.  Applications of the FKG inequality and its relatives.  In Mathematical Programming The State of the Art, pages 115–131. Springer, 1983.
  * [21] Lawrence A Shepp.  The FKG inequality and some monotonicity properties of partial orders.  SIAM Journal on Algebraic Discrete Methods, 1(3):295–299, 1980\.
  * [22] Ronald L Graham, Andrew Chi-chih Yao, and Frances F Yao.  Some monotonicity properties of partial orders.  SIAM Journal on Algebraic Discrete Methods, 1(3):251–258, 1980\.
  * [23] Correlation inequalities. encyclopedia of mathematics.  http://encyclopediaofmath.org/index.php?title=Correlation_inequalities&oldid=46525.
  * [24] Graham R Brightwell.  Universal correlations in finite posets.  Order, 2(2):129–144, 1985.
  * [25] Charles Blair.  Random inequality constraint systems with few variables.  Mathematical Programming, 35(2):135–139, 1986.
  * [26] Wei-Mei Chen, Hsien-Kuei Hwang, and Tsung-Hsi Tsai.  Maxima-finding algorithms for multidimensional samples: A two-phase approach.  Computational Geometry, 45(1-2):33–53, 2012.
  * [27] Luc Devroye.  A note on the expected time for finding maxima by list algorithms.  Algorithmica, 23(2):97–108, 1999.
  * [28] Martin E Dyer and John Walker.  Dominance in multi-dimensional multiple-choice knapsack problems.  Asia-Pacific Journal of Operational Research, 15(2):159–168, 1998\.
  * [29] Mordecai J Golin.  A provably fast linear-expected-time maxima-finding algorithm.  Algorithmica, 11(6):501–524, 1994.
  * [30] Tsung-Hsi Tsai, Hsien-Kuei Hwang, and Wei-Mei Chen.  Efficient maxima-finding algorithms for random planar samples.  Discrete Mathematics & Theoretical Computer Science, 6, 2003.
  * [31] Barry O’Neill.  The number of outcomes in the pareto-optimal set of discrete bargaining games.  Mathematics of Operations Research, 6(4):571–578, 1981.
  * [32] Gérard Biau and Erwan Scornet.  A random forest guided tour.  Test, 25(2):197–227, 2016.
  * [33] Erwan Scornet, Gérard Biau, and Jean-Philippe Vert.  Consistency of random forests.  The Annals of Statistics, 43(4):1716–1741, 2015.
  * [34] Zhi-Dong Bai, Chern-Ching Chao, Hsien-Kuei Hwang, and Wen-Qi Liang.  On the variance of the number of maxima in random vectors and its applications.  The Annals of Applied Probability, 8(3):886–895, 1998.
  * [35] Zhi-Dong Bai, Luc Devroye, Hsien-Kuei Hwang, and Tsung-Hsi Tsai.  Maxima in hypercubes.  Random Structures & Algorithms, 27(3):290–309, 2005.
  * [36] Andrew D Barbour and A Xia.  The number of two-dimensional maxima.  Advances in Applied Probability, 33(4):727–750, 2001.
  * [37] Ole Barndorff-Nielsen and Milton Sobel.  On the distribution of the number of admissible points in a vector random sample.  Theory of Probability & Its Applications, 11(2):249–269, 1966\.
  * [38] Yuliy Baryshnikov.  Supporting-points processes and some of their applications.  Probability Theory and Related Fields, 117(2):163–182, 2000.
  * [39] Neville C Weber.  A martingale approach to central limit theorems for exchangeable random variables.  Journal of Applied Probability, 17(3):662–673, 1980.
  * [40] Royi Jacobovic and Or Zuk.  A phase transition for the probability of being a maximum among random vectors with general iid coordinates.  arXiv preprint arXiv:2112.15534, 2021.
  * [41] Graham Brightwell and Peter Winkler.  Counting linear extensions.  Order, 8(3):225–242, 1991.
  * [42] Martin Dyer, Alan Frieze, and Ravi Kannan.  A random polynomial-time algorithm for approximating the volume of convex bodies.  Journal of the ACM, 38(1):1–17, 1991.
  * [43] Gara Pruesse and Frank Ruskey.  Generating linear extensions fast.  SIAM Journal on Computing, 23(2):373–386, 1994.
  * [44] Kustaa Kangas, Teemu Hankala, Teppo Mikael Niinimäki, and Mikko Koivisto.  Counting linear extensions of sparse posets.  In IJCAI, pages 603–609, 2016.
  * [45] Kustaa Kangas, Mikko Koivisto, and Sami Salonen.  A faster tree-decomposition based algorithm for counting linear extensions.  Algorithmica, 82(8):2156–2173, 2020.
  * [46] Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto.  Counting linear extensions in practice: Mcmc versus exponential monte carlo.  In AAAI, volume 32, 2018.