# Ordinal Optimisation and the Offline Multiple Noisy Secretary Problem

Robert Chin &Jonathan E. Rowe &Iman Shames
&Chris Manzie
&Dragan Nešić Department of Electrical and Electronic Engineering, The
University of Melbourne, Australia & School of Computer Science, University of
Birmingham, United Kingdom. Email<EMAIL_ADDRESS>of
Computer Science, University of Birmingham, United Kingdom & The Alan Turing
Institute, United KingdomCollege of Engineering & Computer Science, Australian
National University, AustraliaDepartment of Electrical and Electronic
Engineering, The University of Melbourne, AustraliaDepartment of Electrical
and Electronic Engineering, The University of Melbourne, Australia

###### Abstract

We study the success probability for a variant of the secretary problem, with
noisy observations and multiple offline selection. Our formulation emulates,
and is motivated by, problems involving noisy selection arising in the
disciplines of stochastic simulation and simulation-based optimisation. In
addition, we employ the philosophy of ordinal optimisation - involving an
ordinal selection rule, and a percentile notion of goal softening for the
success probability. As a result, it is shown that the success probability
only depends on the underlying copula of the problem. Other general properties
for the success probability are also presented. Specialising to the case of
Gaussian copulas, we also derive an analytic lower bound for the success
probability, which may then be inverted to find sufficiently large sample
sizes that guarantee a high success probability arbitrarily close to one.

_Keywords_ Ordinal optimization $\cdot$ Secretary problem $\cdot$ Copulas

##  1 Introduction

Numerous problems studied in operations research are themed around the
objective of ‘picking the best’ from a finite number of alternatives, under
uncertainty. The branch of ranking and selection problems [1] typically
considers finding the population with the best mean from a collected sample.
Online (i.e. sequential) variations of ranking and selection have also
appeared, e.g. [2], which are also closely related to the pure exploration
(best-arm identification) setting in multi-armed bandits [3]. Common
motivators for this line of work include stochastic search/simulation [4] and
the design of clinical trials [5].

On the other hand, the secretary problem (also known as the "best choice"
problem) is an optimal stopping problem that is commonly framed in the context
of selecting the best candidate for a job, when the quality of interviewed
candidates are observed sequentially in random order [6]. The well-known
asymptotically optimal solution for maximising the probability of best
selection features the reciprocal of Euler’s number (approximately 0.37) as a
stopping rule [7, Equation (2a-10)]. Variations of the secretary problem are
abundant in the literature, for instance when multiple candidates may be
selected [8], or when observations of candidate quality are corrupted by noise
[9].

Ordinal optimisation (OO) is another paradigm, originally introduced in [10],
that is proposed for softening difficult problems in stochastic search and
optimisation, motivated by the simulation-based design of discrete-event
dynamical systems. It is offered as a complementary approach to conventional
optimisation techniques whenever there is ‘little hope’ of finding the global
optimum solution, and its operation rests on two underlying principles: 1) by
selecting the subset according to order, the selection is more ‘robust’ to
noise; and 2) by goal softening (i.e. increasing the degree of sub-
optimality), chances of success can be improved.

In the offline (i.e. non-sequential) formulation of OO [11, Chapter II], the
technique boils down to "randomly sample many candidate solutions, simulate
their performances, and pick the best observed". This is also known as the
horse-race selection rule, which is formally proven to be optimal under the
setup considered in [12, Theorem 3.1]. The outcome provided by OO is a high
probability guarantee that one or more out of a selected subset of candidate
solutions is an acceptable sub-optimal solution. It is interesting to note
that the same philosphy of "sample many candidate solutions and pick the best
observed" also independently manifests itself in a corner of the
probabilistically robust control literature [13], justified by rigorous sample
complexity analysis. A research area with roots from OO is the optimal
computing budget allocation (OCBA) framework, which addresses the problem of
efficient sequential allocation of simulation resources [14]. This work on
OCBA can also be regarded as an early precursor to results in online ranking
and selection, and pure exploration bandits [15, §33.5].

In this paper, we investigate a secretary-like problem that is motivated by
simulation-based optimisation. Specifically, we consider contexts where noisy
offline simulations are relatively cheap/plentiful compared to ‘true’
evaluations of performance, which are relatively expensive/limited. This may
be represented, for example, by the learning of a robotic controller that is
primarily outsourced to a computer simulation prior to physical deployment,
under the sim-to-real methodology [16]. To this end, we introduce the
framework of an offline noisy secretary problem, and regard the probability of
success as the probability in which at least one selected candidate performs
acceptably well. In addition, we employ in our formulation the two
cornerstones championed by OO: an ordinal horse-race selection rule with fixed
selection size for multiple secretaries, and goal softening as another degree
of freedom to control the probability of success.

We study the properties of the success probability in general settings. In
particular, our formulation leads to a success probability which only depends
on the bivariate copula of the underlying distributions. Note that while
copula modelling has been previously applied in stochastic simulation [17], it
was used for a different purpose (namely, to model the time-series of
simulation inputs). By keeping to the motivational context that the allowable
number of offline evaluations is plentiful, we also address the inversion
problem, that is to determine a sufficiently large sample size of candidates,
so that for fixed selection size, a prescribed high probability of success is
guaranteed.

The paper is structured as follows. In Section 2, we setup the technical
premise of the paper, and define the success probability for the offline
multiple noisy secretary problem. The inversion problem is also to be stated
formally. In Section 3, we provide an explicit integral expression for the
success probability that only depends on the underlying copula, and use this
to illustrate various properties of the success probability for general copula
models. In Section 4, the success probability is specialised to the case of
Gaussian copula models, in which we provide an analytic lower bound for the
success probability. This analytic lower bound is then used to address the
inversion problem, where we demonstrate finding sufficiently large sample
sizes to guarantee a high probability of success. Concluding remarks are given
and future work is proposed in Section 5.

##  2 Preliminaries

###  2.1 Notation

The set $\mathbb{R}$ denotes the real numbers, and $\mathbb{N}$ denotes the
set of natural numbers. The logarithm $\log\left(\cdot\right)$ is taken to
mean the natural logarithm, while $\cot\left(\cdot\right)$ and
$\sinh\left(\cdot\right)$ are the cotangent and hyperbolic sine functions
respecrively. The floor and ceiling operators are given by
$\left\lfloor\cdot\right\rfloor$ and $\left\lceil\cdot\right\rceil$
respectively. Whenever the symbols $\leq$ and $<$ are used between vectors,
they refer to element-wise inequalities. The standard Gaussian probability
density function (PDF), cumulative distribution function (CDF), inverse CDF
(i.e. quantile function) and $Q$-function (complementary CDF) are canonically
represented using $\phi\left(\cdot\right)$, $\Phi\left(\cdot\right)$,
$\Phi^{-1}\left(\cdot\right)$, $Q\left(\cdot\right)$ respectively. We write
$\mathbf{X}\sim\mathcal{N}\left(\boldsymbol{\mu},C\right)$ to denote that
$\mathbf{X}$ is Gaussian distributed with mean $\boldsymbol{\mu}$ and
covariance $C$. The probability of an event is measured by
$\operatorname{Pr}\left(\cdot\right)$ with respect to a probability space that
is clear from context. The abbreviation i.i.d. stands for mutually independent
and identically distributed. The symbol $\mathbb{E}$ denotes mathematical
expectation. We use $\mathbb{I}_{\left\\{\cdot\right\\}}$ to denote an
indicator variable. The notation $\left[X\middle|Y=y\right]$ is understood to
mean a random variable that is equal in law to the conditional distribution of
$X$ given $Y=y$. Following the notation of [18], stochastic dominance is
denoted by $\underset{\mathrm{st}}{\preceq}$ and the symbol
$\underset{\mathrm{st}}{=}$ between random elements denotes equality in law.
The $k$th order statistic of a i.i.d. sample of size $n$ from parent
distribution $Z$ will be denoted by $Z_{k:n}$.

###  2.2 Setup

Let the pair $\left(Z,X\right)$ have a continuous distribution with joint CDF
$F_{Z,X}\left(z,x\right)$ and respective marginal CDFs $F_{Z}\left(z\right)$,
$F_{X}\left(x\right)$. Consider $n$ i.i.d. copies $\left(Z_{i},X_{i}\right)$
drawn from the distribution of $\left(Z,X\right)$. The variables
$Z_{1},\dots,Z_{n}$ (i.e. noisily observed candidate qualities) are ordered
from best to worst, denoted by $Z_{1:n}\leq\dots\leq Z_{n:n}$. The best $m$
(with $m\leq n$) are selected, given by $Z_{1:n},\dots,Z_{m:n}$, with
respectively attached $X$-values (i.e. actual candidate qualities) denoted as
$X_{\left\langle 1\right\rangle},\dots,X_{\left\langle m\right\rangle}$. More
explicitly, the pairs $\left(Z_{1:n},X_{\left\langle
1\right\rangle}\right),\dots,\left(Z_{m:n},X_{\left\langle
m\right\rangle}\right)$ have been chosen. For this offline multiple noisy
secretary problem, we define the corresponding success probability as follows.

######  Definition 2.1 (Success probability).

The success probability $p_{\mathrm{success}}$ is the probability that at
least one of $X_{\left\langle 1\right\rangle},\dots,X_{\left\langle
m\right\rangle}$ is in the best $100\alpha$ percentile of the population of
$X$, and denoted

$\displaystyle p_{\mathrm{success}}^{F_{Z,X}}\left(n,m,\alpha\right)$
$\displaystyle:=\operatorname{Pr}\left(\bigcup_{i=1}^{m}\left\\{X_{\left\langle
i\right\rangle}\leq x_{\alpha}^{*}\right\\}\right)$ (2.1)
$\displaystyle=\operatorname{Pr}\left(\min_{i\in\left\\{1,\dots,m\right\\}}X_{\left\langle
i\right\rangle}\leq x_{\alpha}^{*}\right),$ (2.2)

where $x_{\alpha}^{*}$ with $\alpha\in\left(0,1\right]$ is such that
$\operatorname{Pr}\left(X\leq x_{\alpha}^{*}\right)=\alpha$.

This is an offline variant of the secretary problem, because the selection is
made after all the $Z_{1},\dots,Z_{n}$ are observed. Also, the classical
secretary problem is trivial if selections can be made offline, so one purpose
of having noisy observations is to ‘un-trivialise’ the problem. Painting this
setup in a simulation-based optimisation context, we could for example take
each $Z_{i}$ as the empirical average
$Z_{i}=\frac{1}{T}\sum_{t=1}^{T}J\left(\theta_{i},W_{t}\right)$ over $T$
simulation replications, where $J\left(\theta_{i},W_{t}\right)$ is a system
performance function of a randomly generated design parameter $\theta_{i}$,
and the $W_{t}$ are stochastic simulation input variables. Naturally, $Z_{i}$
is then a noisy estimate of the actual expectation
$X_{i}=\mathbb{E}_{W}\left[J\left(\theta_{i},W\right)\middle|\theta_{i}\right]$.
In essence, simulating a candidate solution is akin to conducting an
‘interview’ for it. Hence Definition 2.1 is compatible, provided the random
variables are continuous.

A noisy secretary problem was also studied by [9], but instead considered the
probability that the best out of $X_{1},\dots,X_{n}$ was selected. It was
demonstrated that, even in the offline setting, there exist distributions
whereby this probability tends to zero as $n\to\infty$. In this paper, the
role of $\alpha$ is for goal-softening, i.e. controlling degree of sub-
optimality as defined by a threshold of the best $100\alpha$ percentile of
$X$. The results for our formulation imply that $\alpha$ can be controlled to
make $p_{\mathrm{success}}$ arbitrarily close to one, while
$p_{\mathrm{success}}>0$ always when $\alpha\in\left(0,1\right]$.

We also focus attention on the problem of inverting the success probability,
i.e. finding a sample size $n$ so that $p_{\mathrm{success}}$ is sufficiently
high.

######  Problem 2.1 (High probability inversion).

Prescribe $\delta\in\left(0,1\right]$, and fix $m\in\mathbb{N}$,
$\alpha\in\left(0,1\right]$. Given the distribution for $\left(Z,X\right)$:

  1. (a)

does there exist a finite $n$ which yields
$p_{\mathrm{success}}^{F_{Z,X}}\left(n,m,\alpha\right)\geq 1-\delta$?

  2. (b)

If so, find such an $n$.

In the context of simulation-based optimisation, $n$ represents the quantity
of simulations performed offline. Thus Problem 2.1 could be phrased as "find
the number of offline simulations, so that at least one candidate actually
performs acceptably well, with high probability".

###  2.3 Dependence Modelling

Since $Z$ is a noisily corrupted version of $X$, a reasonable condition that
might be desired on $\left(Z,X\right)$ is some notion of positive dependence,
i.e. roughly speaking, low (high) $Z$ is predictive of low (high) $X$. One
such formal notion of positive dependence is called stochastically increasing
positive dependence (SIPD), defined as follows [19, §2.8.2].

######  Definition 2.2 (Stochastically increasing positive dependence).

The random variable $X$ is said to be stochastically increasing positive
dependent in $Z$ if

$\operatorname{Pr}\left(X>x\middle|Z=z\right)\leq\operatorname{Pr}\left(X>x\middle|Z=z^{\prime}\right)$
(2.3)

for all $z,z^{\prime}$ in the support of $Z$, such that $z\leq z^{\prime}$.

The SIPD condition may be satisfied, for instance, under a particular additive
noise causal representation. Additive noise is the same type of noise
considered in [9] and areas of stochastic simulation such as [10, 20]. Further
elaboration is provided in Appendix A.

Due to their utility in modelling dependence structure and flexibility to
describe wide classes of distributions, copulas will be convenient for
modelling the pair $\left(Z,X\right)$.

######  Definition 2.3 (Bivariate copula).

A bivariate copula is a bivariate distribution, with both marginal
distributions being the $\operatorname{Uniform}\left(0,1\right)$ distribution.

Through the probability integral transform, which says that both
$F_{Z}\left(Z\right)$ and $F_{X}\left(X\right)$ are
$\operatorname{Uniform}\left(0,1\right)$ distributed [21, Theorem 1], every
multivariate distribution can be represented with just its marginal
distributions and a copula. Moreover, Sklar’s theorem [19, Theorem 1.1]
asserts that if the distribution is continuous, then the choice of copula in
this representation is unique. If the continuous pair $\left(Z,X\right)$ is
represented with copula $\mathcal{C}_{Z,X}$, then we say that
$\left(Z,X\right)$ ‘has’ copula $\mathcal{C}_{Z,X}$ and write the joint copula
CDF as

$\mathcal{C}_{Z,X}\left(z,x\right):=\operatorname{Pr}\left(F_{Z}\left(Z\right)\leq
z,F_{X}\left(X\right)\leq x\right).$ (2.4)

In addition, the conditional copula CDF of $X$ given $Z$ is denoted by

$\mathcal{C}_{X|Z}\left(x\middle|z\right):=\operatorname{Pr}\left(F_{X}\left(X\right)\leq
x\middle|F_{Z}\left(Z\right)=z\right).$ (2.5)

##  3 Properties of Success Probability

In this section, we present several properties of the success probability when
$\left(Z,X\right)$ has a general copula model. Our first result gives an
expression to compute the success probability by evaluating an $m$-dimensional
integral.

######  Theorem 3.1 (Integral expression for success probability).

We have

$p_{\mathrm{success}}^{F_{Z,X}}\left(n,m,\alpha\right)=\dfrac{n!}{\left(n-m\right)!}\int_{0}^{1}\int_{0}^{z_{m}}\dots\int_{0}^{z_{2}}\left[1-\prod_{j=1}^{m}\left(1-\mathcal{C}_{X|Z}\left(\alpha\middle|z_{j}\right)\right)\right]\\\
\times\left(1-z_{m}\right)^{n-m}\mathrm{d}z_{1}\dots\mathrm{d}z_{m-1}\mathrm{d}z_{m}.$
(3.1)

The proof may be found in Appendix C. Theorem 3.1 reveals that when
calculating the success probability given $n$, $m$ and $\alpha$, only the
copula of $\left(Z,X\right)$ matters. Or alternatively, we can without loss of
generality assume that $\left(Z,X\right)$ is a copula distribution, and write
$p_{\mathrm{success}}^{F_{Z,X}}=p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$.
Therefore, we see why the "ordinal" term from OO can be a fitting qualifier -
the success probability will be invariant to univariate monotonic (i.e.
strictly increasing) transformations of $Z$ and $X$, because this does not
modify the underlying copula.

The $m$-dimensional integral in (3.1) is analytically intractable, except for
simple special cases exemplified as follows. For the bivariate Clayton copula
[19, §4.6.1] with parameter $\varrho=1$ (denoted
$\operatorname{Clay}\left(\varrho\right)$), and $n=3$, $m=1$, $\alpha=1/2$, we
have

$p_{\mathrm{success}}^{\operatorname{Clay}\left(1\right)}\left(3,1,\dfrac{1}{2}\right)=3\int_{0}^{1}\dfrac{\left(1-z\right)^{2}}{\left(z+1\right)^{2}}\mathrm{d}z=9-12\log
2\approx 0.6822.$ (3.2)

Or using $\operatorname{Clay}\left(2\right)$ instead, we have

$p_{\mathrm{success}}^{\operatorname{Clay}\left(2\right)}\left(3,1,\dfrac{1}{2}\right)=3\int_{0}^{1}\dfrac{\left(1-z\right)^{2}}{\left(3z^{2}+1\right)^{3/2}}\mathrm{d}z=\dfrac{\sinh^{-1}\left(\sqrt{3}\right)}{\sqrt{3}}\approx
0.7603.$ (3.3)

Note that it is also possible to consider an alternative selection rule -
which is to instead select all the candidates below the threshold
$z_{m/n}^{*}$, where $z_{m/n}^{*}$ is the $100m/n$ percentile of $Z$. This
selection rule gives a randomised selection size equal to $m$ in expectation,
and it can be shown that the analogous success probability is the somewhat
more ‘elegant-looking’ expression of
$1-\left(1-C_{Z,X}\left(m/n,\alpha\right)\right)^{n}$. In comparison to a
fixed selection size however, this randomised selection size suffers from
three issues: 1) if the marginal distribution of $Z$ is not known in practice,
then this selection rule is non-operational; 2) a randomised selection size
yields a strictly smaller asymptotic success probability; and 3) in
applications (e.g. simulation-based optimisation), it may be undesirable to
have the selection size be randomised, especially as the selection size is
able to be zero with non-zero probability, and has an asymptotic variance of
$m$. Further details are provided in Appendix B.

Under a SIPD regularity condition, we can also confirm that the horse-race
selection rule (i.e. selecting the best $m$ observed) is indeed the optimal
choice.

######  Proposition 3.1 (Optimality of horse-race selection).

If $X$ is SIPD in $Z$, then the selection of the first $m$ order statistics
maximises the success probability in Definition 2.1, compared to any other
selection of size $m$ from the sample.

The success probability can also be shown to be non-decreasing in each of its
arguments.

######  Proposition 3.2 (Monotonicity of success probability).

The success probability $p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$ satisfies
the following monotonicity properties.

  1. (a)

(Monotonicity in $n$) If $X$ is SIPD in $Z$, then for any $n\in\mathbb{N}$ and
fixed $\bar{m}\in\left\\{1,\dots,n\right\\}$ and fixed
$\bar{\alpha}\in\left(0,1\right]$, we have

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,\bar{m},\bar{\alpha}\right)\leq
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n+1,\bar{m},\bar{\alpha}\right).$
(3.4)

  2. (b)

(Monotonicity in $m$) For fixed $\bar{n}\in\mathbb{N}$, fixed
$\bar{\alpha}\in\left(0,1\right]$ and any $m\in\left\\{1,\dots,n-1\right\\}$,
we have

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(\bar{n},m,\bar{\alpha}\right)\leq
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(\bar{n},m+1,\bar{\alpha}\right).$
(3.5)

  3. (c)

(Monotonicity in $\alpha$) For fixed $\bar{n}\in\mathbb{N}$, fixed
$\bar{m}\in\left\\{1,\dots,\bar{n}\right\\}$ and any
$\alpha,\alpha^{\prime}\in\left(0,1\right]$ such that
$\alpha\leq\alpha^{\prime}$, we have

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(\bar{n},\bar{m},\alpha\right)\leq
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(\bar{n},\bar{m},\alpha^{\prime}\right).$
(3.6)

For any copula satisfying the SIPD condition, we also have the following
general upper and lower bounds.

######  Proposition 3.3 (General bounds for success probability).

If $X$ is SIPD in $Z$, the success probability
$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$ satisfies

$1-\left(1-\alpha\right)^{m}\leq
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)\leq
1-\left(1-\alpha\right)^{n}.$ (3.7)

These bounds are tight, as some of the following limiting cases show.

######  Proposition 3.4 (Limiting forms of success probability).

If $X$ is SIPD in $Z$, the success probability
$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$ satisfies the following.

  1. (a)

When $m=n$:

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,n,\alpha\right)=1-\left(1-\alpha\right)^{n}.$
(3.8)

  2. (b)

When $\alpha=1$:

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,1\right)=1.$ (3.9)

  3. (c)

When $\alpha\to 0^{+}$:

$\lim_{\alpha\to
0^{+}}p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=0.$
(3.10)

  4. (d)

If $Z$ and $X$ are comonotonic (i.e. perfect positive dependence, such that
$F_{Z}\left(Z\right)=F_{X}\left(X\right)$ for every realisation of
$\left(Z,X\right)$), then

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=1-\left(1-\alpha\right)^{n}.$
(3.11)

  5. (e)

If $Z$ and $X$ are independent, then

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=1-\left(1-\alpha\right)^{m}.$
(3.12)

  6. (f)

When $m\to\infty$ and $n\to\infty$ in any way such that $m\leq n$:

$\lim_{m,n\to\infty}p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=1.$
(3.13)

  7. (g)

When $m$ is finite and $n\to\infty$:

$\lim_{n\to\infty}p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=1-\left(1-\mathcal{C}_{X|Z}\left(\alpha\middle|0\right)\right)^{m}.$
(3.14)

Due to the specification of Problem 2.1, we are primarily interested in the
regime of large $n$ and relatively small fixed $m$. Sadly, the property in
Proposition 3.43.14 indicates that in general, for finite $m$ we have
$\lim_{n\to\infty}p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)<1$,
whenever $\mathcal{C}_{X|Z}\left(\alpha\middle|0\right)<1$. For example, the
bivariate Frank copula [19, §4.5.1] with parameter $\varpi>0$ has boundary
conditional CDF

$\mathcal{C}_{X|Z}^{\mathrm{Frank}}\left(\alpha\middle|0;\varpi\right)=\dfrac{1-e^{-\varpi\alpha}}{1-e^{-\varpi}}<1.$
(3.15)

Thus to address Problem 2.1(a) in general, we can only attain a high success
probability with a combination of sufficiently large $n$ and $m$. However,
there do exist classes of copulas where
$\lim_{n\to\infty}p_{\mathrm{success}}\left(n,m,\alpha\right)=1$ for all
finite $m\geq 1$. In these cases, it is possible to address Problem 2.1(b),
i.e. for a prescribed high probability $1-\delta$ (with any
$\delta\in\left(0,1\right]$ and $m$, $\alpha$ fixed), to find an $n^{*}$ such
that $p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n^{*},m,\alpha\right)\geq
1-\delta$. A naive approach would be to increment $n$ and numerically evaluate
$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$ using the $m$-dimensional integral
(3.1) until such an $n^{*}$ is found. In the next section, we study one such
class of copula which satisfies this property, and explore an alternative
approach for finding $n^{*}$ using an analytic lower bound for
$p_{\mathrm{success}}$.

##  4 Gaussian Copula Success Probability

The naive approach to address Problem 2.1(b) is by numerically evaluating the
$m$-dimensional integral iteratively (discussed at the end of Section 3).
However, several numerical issues pervade this approach.

  * •

Firstly, $m$-dimensional integrals will become hard to compute (even
numerically) for sufficiently large $m$.

  * •

Secondly, even by taking $m=1$ (which lower bounds the success probability for
$m\geq 1$ due to Proposition 3.23.5), we do not know the vicinity of the order
of magnitude for $n$ to begin evaluating
$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$. For example, we could begin
evaluating $p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$ by incrementing $n$
starting from $n=100$, but it would actually require $n\approx 10^{9}$ before
$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\geq 1-\delta$, resulting in an
excessive number of evaluations.

  * •

Lastly, even if we did know (or can narrow down) the vicinity of the order of
magnitude for $n$, it may not be possible to obtain an accurate numerical
evaluation of $p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$ for very large $n$,
since the factor $\left(1-z_{m}\right)^{n-m}n!/\left(n-m\right)!$ related to
the probability density in (3.1) tends towards a degenerate distribution
concentrated over zero as $n\to\infty$, for fixed $m$.

In this section, we address the above issues by specialising the success
probability to the case when $\left(Z,X\right)$ has a bivariate Gaussian
copula. This allows us to develop an analytic lower bound for the success
probability, which may be inverted to directly address Problem 2.1(b). The
bivariate Gaussian copula is defined as follows.

######  Definition 4.1 (Bivariate Gaussian copula).

Let $\left(Z,X\right)$ be a bivariate standard Gaussian vector with
correlation $\rho\in\left[-1,1\right]$, i.e.

$\begin{bmatrix}Z\\\ X\end{bmatrix}\sim\mathcal{N}\left(\begin{bmatrix}0\\\
0\end{bmatrix},\begin{bmatrix}1&\rho\\\ \rho&1\end{bmatrix}\right).$ (4.1)

Then the bivariate Gaussian copula with correlation $\rho$, denoted
$\mathcal{NC}\left(\rho\right)$, is the distribution of
$\left(\Phi\left(Z\right),\Phi\left(X\right)\right)$.

The class of multivariate distributions with Gaussian copulas are referred to
as non-paranormal distributions [22], and alternatively as meta-Gaussian
distributions [23]. A bivariate Gaussian copula is entirely specified by the
correlation parameter $\rho$, which also neatly summarises the dependence
within the distribution. Thus, we denote the success probability with a
Gaussian copula as
$p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n,m,\alpha\right)$.
The bivariate Gaussian copula is known to satisfy the stronger condition of
positive likelihood ratio dependence for $\rho>0$ [19, §4.3.1], which implies
SIPD of $X$ in $Z$ [24, Theorem 5.2.19]. Thus all the properties in Section 3
hold for $p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}$. It is also
known that the boundary CDF for the bivariate Gausssian is
$\mathcal{C}_{X|Z}^{\mathcal{N}}\left(\cdot\middle|0;\rho\right)=1$ for all
$\rho>0$ [19, §4.3.1], so by Proposition 3.43.14, we immediately have

$\lim_{n\to\infty}p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n,m,\alpha\right)=1$
(4.2)

when $\rho>0$, for any $m\geq 1$. The Gaussian copula model for
$\left(Z,X\right)$ also admits an additive independent Gaussian noise
representation (see Appendix A).

###  4.1 Analytic Lower Bound for Success Probability

Under a Gaussian copula model for $\left(Z,X\right)$ with positive correlation
$\rho>0$, we can derive the following analytic lower bound on the success
probability.

######  Theorem 4.1 (Success probability analytic lower bound).

Given some $\omega\in\left(0,\frac{\pi}{2}\right)$, let

$\mathfrak{c}_{1}=\dfrac{1}{2}-\dfrac{\omega}{\pi},\quad\mathfrak{c}_{2}=\dfrac{\cot{\omega}}{\pi-2\omega}$
(4.3)

and

$\displaystyle\mu_{n}=-\sqrt{\dfrac{\log\left(n\mathfrak{c}_{1}\right)}{\mathfrak{c}_{2}}}$
(4.4) $\displaystyle\sigma_{n}^{2}=\dfrac{-\log\log
2}{2\mathfrak{c}_{2}\left(\log\left(n\mathfrak{c}_{1}\right)-\log\log
2\right)}.$ (4.5)

Then for any $\omega\in\left(0,\frac{\pi}{2}\right)$, there exists an
$\widetilde{n}\left(\omega\right)\in\mathbb{N}$ such that for all
$n\geq\widetilde{n}\left(\omega\right)$, $m\in\left\\{1,\dots,n\right\\}$,
$\rho\in\left(0,1\right]$, and $\alpha\in\left(0,1\right]$, we have

$p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n,m,\alpha\right)\geq
p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n,1,\alpha\right)\geq\Phi\left(\dfrac{\Phi^{-1}\left(\alpha\right)-\rho\mu_{n}}{\sqrt{1-\rho^{2}+\rho^{2}\sigma_{n}^{2}}}\right).$
(4.6)

The proof of this result is found in Appendix C. Furthermore, given any
$n\in\mathbb{N}$, $m\in\left\\{1,\dots,n\right\\}$, $\rho\in\left(0,1\right]$,
and $\alpha\in\left(0,1\right]$, we can optimise the bound with respect to
$\omega$ by

$p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n,m,\alpha\right)\geq
p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n,1,\alpha\right)\geq\sup_{\omega\in\Omega_{n}}\Phi\left(\dfrac{\Phi^{-1}\left(\alpha\right)-\rho\mu_{n}\left(\omega\right)}{\sqrt{1-\rho^{2}+\rho^{2}\left[\sigma_{n}\left(\omega\right)\right]^{2}}}\right),$
(4.7)

where $\Omega_{n}\subset\left(0,\frac{\pi}{2}\right)$ is the set of all
$\omega$ such that $n\geq\widetilde{n}\left(\omega\right)$, while
$\mu_{n}\left(\omega\right)$, $\left[\sigma_{n}\left(\omega\right)\right]^{2}$
are (4.4), (4.5) respectively but with dependence on $\omega$ explicitly
denoted. For a given $\omega$, it is also worthwhile to consider the smallest
integer $\widetilde{n}\left(\omega\right)$ such that (4.6) is valid. It is
clear that we must have $n^{*}\left(\omega\right)>1/\mathfrak{c}_{1}$,
otherwise it possibly allows for $\log\left(n\mathfrak{c}_{1}\right)<0$ in
(4.4) and (4.5). Given $n$ and $\omega$, one can numerically certify whether
$n\geq\widetilde{n}\left(\omega\right)$, using sufficient conditions from the
proof of Theorem 4.6. We have empirically observed that
$\widetilde{n}\left(\omega\right)$ can be quite small; we are usually able to
accept $\widetilde{n}\left(\omega\right)=\left\lceil
1/\mathfrak{c}_{1}\right\rceil$. Using this certification, the optimised lower
bound (4.7) can also be implemented via a numerical procedure, noting that we
need only conduct search over a univariate bounded interval. Further
discussion and pseudocode for these implementations can be found in Appendix
D.

Throughout Figures 1(a)-1(d), we plot the optimised lower bound (4.7) from
Theorem 4.6, with baseline values $m=1$, $\alpha=0.05$, $\rho=0.4$ and
$n=100$, while varying s single quantity. In Figure 1(a), this is compared
against a numerical evaluation of the success probability using (3.1).
However, since the density in the integrand concentrates over zero as $n$
increases, numerical integration becomes inaccurate for large $n$ (as
discussed at the beginning of this section). In Figure 1(b), we instead plot
the lower bound over a semi-log horizontal axis scale for large $n$, to
illustrate the convergence of the success probability to one. These plots
demonstrate that the behaviour of the lower bound is reasonably close to the
actual probability. As the lower bound has been derived with $m=1$ while the
bound itself does not change with $m$, this means the bound is least
conservative for $m=1$, and will generally become more conservative as $m$
grows. For instance with $\alpha=0.05$ and $m=32$, the lower bound from
Proposition 3.7 yields $p_{\mathrm{success}}^{\mathcal{N}}\geq 0.806$ for any
$n\geq 32$, already surpassing the lower bound with $n=10^{9}$ from Figure
1(a). However, the bound (4.6) is still useful in the regime of small $m$ and
large $n$, e.g. for addressing Problem 2.1(b).

(a) Comparison of the optimised lower bound in (4.7) to numerical integration
via Theorem 3.1, as $n$ is varied. In addition, this figure demonstrates
monotonicity in $n$ from Proposition 3.23.4.

(b) Comparison of the lower bound (4.7) when $n$ is varied over a semi-log
horizontal axis scale. In addition, this figure demonstrates convergence to
one in $n$ from (4.2).

(c) Comparison of the optimised lower bound in (4.7) to numerical integration
via Theorem 3.1, as $\rho$ is varied.

(d) Comparison of the optimised lower bound in (4.7) to numerical integration
via Theorem 3.1, as $\alpha$ is varied. In addition, this figure demonstrates
monotonicity in $\alpha$ from Proposition 3.23.6.

Figure 1: Numerical results for the lower bound.

###  4.2 Inversion of Analytic Lower Bound

We now use the analytic lower bound in (4.6) of Theorem 4.6 to address Problem
2.1(b), in the case that $\left(Z,X\right)$ has a Gaussian copula. Putting
this into the contexts discussed earlier, we may address questions of the
nature "how many job candidates should the hiring manager interview", or "how
many simulations should be conducted offline" in order to guarantee a
prescribed high success probability. Observe that the analytic lower bound in
(4.6) tends to one, as $n\to\infty$. So to address Problem 2.1(b) using the
lower bound (given $\alpha$, $\rho$ and $\delta$), we aim to invert for $n$ in
terms of $\omega$ with the expression

$\Phi\left(\dfrac{\Phi^{-1}\left(\alpha\right)-\rho\mu_{n}}{\sqrt{1-\rho^{2}+\rho^{2}\sigma_{n}^{2}}}\right)=1-\delta.$
(4.8)

Putting the definitions of $\mu_{n}$ and $\sigma_{n}$ from (4.4) and (4.5)
respectively, this equation can be rearranged into a quartic equation in
$\mathsf{x}=\sqrt{\log\left(n\mathfrak{c}_{1}\right)}$, of the form

$\mathfrak{a}_{4}\mathsf{x}^{4}+\mathfrak{a}_{3}\mathsf{x}^{3}+\mathfrak{a}_{2}\mathsf{x}^{2}+\mathfrak{a}_{1}\mathsf{x}+\mathfrak{a}_{0}=0,$
(4.9)

where

$\displaystyle\mathfrak{a}_{4}$ $\displaystyle=-\dfrac{2\rho^{2}}{\log\log 2}$
(4.10) $\displaystyle\mathfrak{a}_{3}$
$\displaystyle=-\dfrac{4\Phi^{-1}\left(\alpha\right)\rho\sqrt{\mathfrak{c}_{2}}}{\log\log
2}$ (4.11) $\displaystyle\mathfrak{a}_{2}$
$\displaystyle=2\rho^{2}-\dfrac{2\mathfrak{c}_{2}\left(\left[\Phi^{-1}\left(\alpha\right)\right]^{2}-\left[\Phi^{-1}\left(1-\delta\right)\right]^{2}+\rho^{2}\left[\Phi^{-1}\left(1-\delta\right)\right]^{2}\right)}{\log\log
2}$ (4.12) $\displaystyle\mathfrak{a}_{1}$
$\displaystyle=4\sqrt{\mathfrak{c}_{2}}\Phi^{-1}\left(\alpha\right)\rho$
(4.13) $\displaystyle\mathfrak{a}_{0}$
$\displaystyle=2\mathfrak{c}_{2}\left(\left[\Phi^{-1}\left(\alpha\right)\right]^{2}-\left[\Phi^{-1}\left(1-\delta\right)\right]^{2}+\rho^{2}\left[\Phi^{-1}\left(1-\delta\right)\right]^{2}\right)-\rho^{2}\left[\Phi^{-1}\left(1-\delta\right)\right]^{2}.$
(4.14)

Therefore we take the solution for $n$ corresponding to
$\mathsf{x}=\sqrt{\log\left(n\mathfrak{c}_{1}\right)}$ as the greatest real
root of the quartic equation. Let this solution for $n$ in terms of $\omega$
be denoted $n^{*}\left(\omega\right)$. According to the monotonicity and
convergence properties from Proposition 3.23.4 and (4.2) respectively, then
provided $n^{*}\left(\omega\right)\geq\widetilde{n}\left(\omega\right)$, we
guarantee

$p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n^{*}\left(\omega\right),m,\alpha\right)\geq
1-\delta,$ (4.15)

since $n^{*}\left(\omega\right)$ upper bounds the smallest $n$ needed such
that $p_{\mathrm{success}}\geq 1-\delta$. Moreover, in a similar way to (4.7),
one can numerically optimise with respect to $\omega$ to find the smallest
$n^{*}\left(\omega\right)$ that guarantees a high probability of success.
Pseudocode implementing this (which also takes into account the requirement
$n^{*}\left(\omega\right)\geq\widetilde{n}\left(\omega\right)$) can be found
in Algorithm 3 of Appendix D.

Table 1: Computed values of $n$ which guarantees $p_{\mathrm{success}}^{\mathcal{NC}\left(\rho\right)}\left(n^{*}\left(\omega\right),m,\alpha\right)\geq 1-\delta$, with fixed $\alpha=0.01$ and valid for any $m\geq 1$. | $\delta=0.01$ | $\delta=0.05$ | $\delta=0.1$
---|---|---|---
$\rho=0.01$ | $8.144\times 10^{47007}$ | $5.427\times 10^{34246}$ | $8.943\times 10^{28267}$
$\rho=0.3$ | $3.289\times 10^{51}$ | $1.619\times 10^{38}$ | $8.775\times 10^{31}$
$\rho=0.6$ | $8.703\times 10^{11}$ | $1.988\times 10^{9}$ | $1.078\times 10^{8}$
$\rho=0.9$ | $16744$ | $4338$ | $2188$
$\rho=0.99$ | $893$ | $505$ | $372$

Table 1 lists computed values of $n^{*}$ numerically optimised with respect to
$\omega$, using the aforementioned approach. The table is valid for all $m\geq
1$ (however are values are least conservative when $m=1$), for fixed
$\alpha=0.01$ and a variety of values for $\rho$ and $\delta$. The values for
$n$ trend downwards as $\rho$ increases, which is intuitive (as fewer samples
might be required if noisy observations are strongly correlated with the
actual values). Of particular note, the case with extremely small correlation
$\rho=0.01$ requires $n$ to be at an impractical order of magnitude, namely
$10^{47007}$ when $\delta=0.01$. This highlights the utility of the analytic
lower bound in Theorem 4.6, which allows for a computationally cheap procedure
to find a sufficiently high $n$. If Problem 2.1(b) were attempted to be solved
by evaluating expression (3.1), then large $n$ such as in the order of
$10^{47007}$ would have rendered the evaluation of such probabilities to be
intractable.

Also, Table 1 illustrates the value of having a strong positive dependence in
$\rho$, since it reduces the sample size required to reach a prescribed high
probability of success. For instance with $\delta=0.1$, increasing from
$\rho=0.01$ to $\rho=0.6$ reduces the order of magnitude required for $n^{*}$
from $10^{28267}$ to a more practical $10^{8}$. As one may have reasonably
guessed, increasing the strength of correlation between $Z$ and $X$ (which is
in effect, decreasing the amount of noise in the interview/simulation of
candidates) has a favourable effect on the success probability.

##  5 Conclusion

Motivated by methods in simulation-based optimisation, we studied the success
probability for an offline multiple noisy secretary problem. As a consequence
of applying an ordinal optimisation selection rule with a notion of goal
softening, the success probability was found to depend only on the underlying
copula. One key condition for the copula was that of stochastically increasing
positive dependence, which is sufficient to ensure that $p_{\mathrm{success}}$
is non-decreasing in $n$. An analytic lower bound for $p_{\mathrm{success}}$
was developed in the case of the Gaussian copula model, and Figures 1(a)-1(d)
illustrate that this lower bound is close to the true success probability. The
lower bound may also be inverted to compute sufficiently large values of $n$
which guarantees success probabilities arbitrarily close to one. This is
demonstrated in numerical examples by successfully finding such values of $n$,
even in regimes which require extremely high orders of magnitude for $n$,
whereby numerical integration would not be successful.

The following directions are proposed for future work. In order to address
Problem 2.1(b) for a non-Gaussian copula, invertible analytic lower bounds for
other classes of copulae could be investigated. It may also be interesting to
study how strength of dependence affects $p_{\mathrm{success}}$ for wider
classes of copulas (analogous to the role of $\rho$ in the Gaussian copula),
and how the success probability could be estimated, whenever the copula is not
specified exactly in practice. Another direction would be to consider a
relaxed problem where $\left(Z,X\right)$ is allowed to have a discrete
distribution. The present approach may then need to be modified, since the
underlying copula for $\left(Z,X\right)$ would no longer be unique.

## References

  * [1] E. J. Dudewicz, “Ranking (ordering) and selection: An overview of how to select the best,” Technometrics, vol. 22, no. 1, p. 113, 1980.
  * [2] Y. Peng, E. K. P. Chong, C.-H. Chen, and M. C. Fu, “Ranking and selection as stochastic control,” IEEE Transactions on Automatic Control, vol. 63, no. 8, pp. 2359–2373, 2018.
  * [3] S. Bubeck, R. Munos, and G. Stoltz, “Pure exploration in multi-armed bandits problems,” in International Conference on Algorithmic Learning Theory, pp. 23–37, Springer Berlin Heidelberg, 2009.
  * [4] M. C. Fu, ed., Handbook of Simulation Optimization.  Springer, 2014.
  * [5] C. Shen, Z. Wang, S. Villar, and M. V. D. Schaar, “Learning for dose allocation in adaptive clinical trials with safety constraints,” in International Conference on Machine Learning, 2020.
  * [6] F. T. Bruss, “A unified approach to a class of best choice problems with an unknown number of options,” The Annals of Probability, vol. 12, no. 3, 1984\.
  * [7] J. P. Gilbert and F. Mosteller, “Recognizing the maximum of a sequence,” Journal of the American Statistical Association, vol. 61, no. 313, pp. 35–73, 1966.
  * [8] J. Preater, “On multiple choice secretary problems,” Mathematics of Operations Research, vol. 19, no. 3, pp. 597–602, 1994.
  * [9] A. M. Krieger and E. Samuel-Cahn, “The noisy secretary problem and some results on extreme concomitant variables,” Journal of Applied Probability, vol. 49, no. 3, pp. 821–837, 2012.
  * [10] Y. C. Ho, R. S. Sreenivas, and P. Vakili, “Ordinal optimization of DEDS,” Discrete Event Dynamic Systems, vol. 2, no. 1, pp. 61–88, 1992.
  * [11] Y.-C. Ho, Q.-C. Zhao, and Q.-S. Jia, Ordinal Optimization: Soft Optimization for Hard Problems.  Springer, 2007.
  * [12] M. Yang and L. Lee, “Ordinal optimization with subset selection rule,” Journal of Optimization Theory and Applications, vol. 113, no. 3, pp. 597–620, 2002.
  * [13] M. Vidyasagar, “Randomized algorithms for robust controller synthesis using statistical learning theory,” Automatica, vol. 37, no. 10, pp. 1515–1528, 2001.
  * [14] H.-C. Chen, C.-H. Chen, and E. Yucesan, “Computing efforts allocation for ordinal optimization and discrete event simulation,” IEEE Transactions on Automatic Control, vol. 45, no. 5, pp. 960–964, 2000.
  * [15] T. Lattimore and C. Szepesvári, Bandit Algorithms.  Cambridge University Press, 2020.
  * [16] X. B. Peng, M. Andrychowicz, W. Zaremba, and P. Abbeel, “Sim-to-real transfer of robotic control with dynamics randomization,” in IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2018.
  * [17] B. Biller, “Copula-based multivariate input models for stochastic simulation,” Operations Research, vol. 57, no. 4, pp. 878–892, 2009.
  * [18] M. Shaked and J. G. Shanthikumar, Stochastic Orders.  Springer, 2007.
  * [19] H. Joe, Dependence Modeling with Copulas.  CRC Press, 2014.
  * [20] W. Xie, B. L. Nelson, and R. R. Barton, “A bayesian framework for quantifying uncertainty in stochastic simulation,” Operations Research, vol. 62, no. 6, pp. 1439–1452, 2014.
  * [21] J. E. Angus, “The probability integral transform and related results,” SIAM Review, vol. 36, no. 4, pp. 652–654, 1994.
  * [22] H. Liu, F. Han, M. Yuan, J. Lafferty, and L. Wasserman, “High-dimensional semiparametric gaussian copula graphical models,” The Annals of Statistics, vol. 40, no. 4, pp. 2293–2326, 2012.
  * [23] B. Storvik, G. Storvik, and R. Fjortoft, “On the combination of multisensor data using meta-gaussian distributions,” IEEE Transactions on Geoscience and Remote Sensing, vol. 47, no. 7, pp. 2372–2379, 2009.
  * [24] R. B. Nelsen, An Introduction to Copulas.  Springer, 1st ed., 1999.
  * [25] S. L. Morgan and C. Winship, Counterfactuals and Causal Inference: Methods and Principles for Social Research.  Cambridge University Press, 2nd ed., 2015.
  * [26] M. Harder, Exchangeability of Copulas.  PhD thesis, Ulm University, 2016.
  * [27] H. A. David and H. N. Nagaraja, Order Statistics.  John Wiley, 2005.
  * [28] M.-W. Wu, Y. Li, M. Gurusamy, and P.-Y. Kam, “A tight lower bound on the gaussian Q-function with a simple inversion algorithm, and an application to coherent optical communications,” IEEE Communications Letters, vol. 22, no. 7, pp. 1358–1361, 2018.
  * [29] M. Chiani, D. Dardari, and M. Simon, “New exponential bounds and approximations for the computation of error probability in fading channels,” IEEE Transactions on Wireless Communications, vol. 24, no. 5, pp. 840–845, 2003.
  * [30] B. C. Arnold, N. Balakrishnan, and H. N. Nagaraja, A First Course in Order Statistics.  SIAM, 2008.
  * [31] C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning.  MIT Press, 2006.
  * [32] V. Krishnamurthy, Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing.  Cambridge University Press, 2016.

##  Appendix A Additive Noise Representations

Consider the following causal mechanism (depicted in Figure 2(a)) for
generating $\left(Z,X\right)$: by first generating $Z$, and then generating
$X$ given $Z=z$ though

$X=z+Y,$ (A.1)

where $Y$ is independent of $Z$. An alternative additive causal representation
is the reverse (depicted in Figure 2(b)): first $X$ is generated, and then $Z$
is generated given $X=x$ through

$Z=x+Y,$ (A.2)

where $Y$ is independent of $X$.

$X$$Z$$Y$ (a) Causal additive noise representation for $X$.

$Z$$X$$Y$ (b) Causal additive noise representation for $Z$.

Figure 2: Causal graphs [25, §3.2.2] for additive noise representations.

######  Proposition A.1 (Additive noise implies SIPD).

If either of the following conditions hold:

  * •

$\left(Z,X\right)$ is generated via the causal representation (A.1), or

  * •

$\left(Z,X\right)$ is generated via the causal representation (A.2), and
moreover the copula of $\left(Z,X\right)$ is exchangeable (i.e. its
distribution function $\mathcal{C}_{Z,X}\left(z,x\right)$ is permutation
symmetric),

then $X$ is SIPD in $Z$.

###### Proof.

For the first causal additive representation, as $Z$ and $Y$ are independent,
we have equality in law

$\left[X\middle|Z=z\right]\underset{\mathrm{st}}{=}z+Y.$ (A.3)

Thus

$\displaystyle\operatorname{Pr}\left(X>x\middle|Z=z\right)$
$\displaystyle=\operatorname{Pr}\left(Z+Y>x\middle|Z=z\right)$ (A.4)
$\displaystyle=\operatorname{Pr}\left(Y>x-z\middle|Z=z\right)$ (A.5)
$\displaystyle\leq\operatorname{Pr}\left(Y>x-z^{\prime}\middle|Z=z^{\prime}\right)$
(A.6) $\displaystyle=\operatorname{Pr}\left(X>x\middle|Z=z^{\prime}\right).$
(A.7)

for all $z^{\prime}\geq z$ in the support of $Z$. As for the second causal
additive representation, assume without loss of generality that
$\left(Z,X\right)$ is a copula, and denote
$\mathcal{C}_{Z,X}\left(z,x\right)=\operatorname{Pr}\left(Z\leq z,X\leq
x\right)$. By analogous arguments to the first causal additive representation,
we have

$\operatorname{Pr}\left(Z>z\middle|X=x\right)\leq\operatorname{Pr}\left(Z>z\middle|X=x^{\prime}\right)$
(A.8)

for all $z,x,x^{\prime}\in\left(0,1\right)$ such that $x\leq x^{\prime}$. Due
to exchangeability,
$\mathcal{C}_{Z,X}\left(z,x\right)=\mathcal{C}_{Z,X}\left(x,z\right)$ and we
have the copula conditional CDF (computed via [19, §2.1.3]) as

$\displaystyle\operatorname{Pr}\left(Z>z\middle|X=x\right)$
$\displaystyle=\dfrac{\partial\mathcal{C}_{Z,X}\left(z,x\right)}{\partial x}$
(A.9)
$\displaystyle=\dfrac{\partial\mathcal{C}_{Z,X}\left(x,z\right)}{\partial x}$
(A.10) $\displaystyle=\operatorname{Pr}\left(X>z\middle|Z=x\right).$ (A.11)

Performing the same for the right-hand side of (A.8), we get

$\operatorname{Pr}\left(X>z\middle|Z=x\right)\leq\operatorname{Pr}\left(X>z\middle|Z=x^{\prime}\right)$
(A.12)

for all $z,x,x^{\prime}\in\left(0,1\right)$ such that $x\leq x^{\prime}$,
which is the required condition for (2.3). ∎

Note that many classes of parametric copulas (with one or two parameters) are
exchangeable [19, §2.15], as are all members of the Archimedean family of
copulas [26], so the SIPD condition is satisfied for a variety of models with
additive noise.

###  A.1 Additive Noise Representation for Gaussian Copulas

Suppose observations $Z$ are generated by additive Gaussian noise to Gaussian
$X$ in the way of (A.2). Specifically, let

$Z=X+Y,$ (A.13)

where $X\sim\mathcal{N}\left(0,1\right)$ and
$Y\sim\mathcal{N}\left(0,\xi^{2}\right)$ independent of $X$. The variable
$\xi^{2}$ may be interpreted here as the noise-to-signal ratio. Note that
$\left(Z,X\right)$ is then bivariate Gaussian with correlation
$\rho=\left(1+\xi^{2}\right)^{-1/2}$ and naturally, a bivariate Gaussian has a
bivariate Gaussian copula. Hence this representation corresponds with the
Gaussian copula success probability
$p_{\mathrm{success}}^{\mathcal{NC}\left(1/\sqrt{1+\xi^{2}}\right)}\left(n,m,\alpha\right)$,
in terms of the noise-to-signal ratio.

##  Appendix B Randomised Selection Size

Consider the alternative selection rule: to select all the candidates below
the threshold $z_{m/n}^{*}$, where $z_{m/n}^{*}$ is the $100m/n$ percentile of
$Z$. This selection rule gives a randomised selection size that is binomial
distributed with parameters $n$ and $m/n$, and hence has an expectation of
$m$, and asymptotic variance of
$\lim_{n\to\infty}n\left(m/n\right)\left(1-m/n\right)=m$. The success
probability with this alternative selection rule, defined in the analogous way
to (2.1), is equal to $1-\left(1-C_{Z,X}\left(m/n,\alpha\right)\right)^{n}$,
which is explained as follows. Note that there will be a success if at least
one of the candidates satisfies both $Z_{i}\leq z_{m/n}^{*}$ and $X_{i}\leq
x_{\alpha}^{*}$; the former is the condition that it is selected the first
place, and the latter is the condition it actually performs acceptably well.
Thus, the failure probability is the probability that none of the samples
satisfies both $Z_{i}\leq z_{m/n}^{*}$ and $X_{i}\leq x_{\alpha}^{*}$. Since

$c:=C_{Z,X}\left(m/n,\alpha\right)=\operatorname{Pr}\left(X\leq
x_{\alpha}^{*},Z\leq z_{m/n}^{*}\right),$ (B.1)

then the failure probability is $\left(1-c\right)^{n}$, and so the success
probability is $1-\left(1-c\right)^{n}$. We compute the limit of this success
probability as $n\to\infty$ for fixed $m$. Assume without loss of generality
that $\left(Z,X\right)$ is a copula. Then we have

$\displaystyle\lim_{n\to\infty}\left[1-\left(1-c\right)^{n}\right]$
$\displaystyle=\lim_{n\to\infty}\left[1-\left(1-\operatorname{Pr}\left(X\leq
x_{\alpha}^{*}\middle|Z\leq z_{m/n}^{*}\right)\operatorname{Pr}\left(Z\leq
z_{m/n}^{*}\right)\right)^{n}\right]$ (B.2)
$\displaystyle=1-\lim_{n\to\infty}\left[\left(1-\dfrac{\operatorname{Pr}\left(X\leq
x_{\alpha}^{*}\middle|Z\leq z_{m/n}^{*}\right)m}{n}\right)^{n}\right]$ (B.3)
$\displaystyle=1-\exp\left(-m\lim_{n\to\infty}\operatorname{Pr}\left(X\leq
x_{\alpha}^{*}\middle|Z\leq z_{m/n}^{*}\right)\right)$ (B.4)
$\displaystyle=1-\exp\left(-mC_{X|Z}\left(\alpha\middle|0\right)\right),$
(B.5)

which depends on the copula conditional boundary CDF
$C_{X|Z}\left(\alpha\middle|0\right)\leq 1$, thus

$1-\exp\left(-mC_{X|Z}\left(\alpha\middle|0\right)\right)\leq 1-e^{-m}$ (B.6)

which is always strictly less than one for finite $m$. On the other hand, the
fixed size selection rule has the limiting success probability from
Proposition 3.43.14 of

$\lim_{n\to\infty}p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=1-\left(1-C_{X|Z}\left(\alpha\middle|0\right)\right)^{m},$
(B.7)

which can achieve one for finite $m$, provided
$C_{X|Z}\left(\alpha\middle|0\right)=1$. Furthermore, this is shown to be
asymptotically strictly greater than that for the randomised selection size.
Let $c_{\alpha}:=C_{X|Z}\left(\alpha\middle|0\right)$, and use the fact that
$\log\left(1-c_{\alpha}\right)\leq-c_{\alpha}$ for all $c_{\alpha}\geq 0$
(refer to Lemma C.2) so that

$1-e^{-mc_{\alpha}}\leq 1-\left(1-c_{\alpha}\right)^{m},$ (B.8)

with equality if and only if $c_{\alpha}=0$, i.e. both sides are equal to
zero. However the lower bound in Proposition 3.7 implies a strictly positive
success probability, so it must be that

$1-e^{-mc_{\alpha}}<1-\left(1-c_{\alpha}\right)^{m}.$ (B.9)

##  Appendix C Proofs of Main Results

###  C.1 Proof of Theorem 3.1

Observe that

$\min\left\\{X_{\left\langle 1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq x_{\alpha}^{*}$ (C.1)

if and only if

$\min\left\\{F_{X}\left(X_{\left\langle
1\right\rangle}\right),\dots,F_{X}\left(X_{\left\langle
m\right\rangle}\right)\right\\}\leq\alpha.$ (C.2)

Moreover, the ordering of
$F_{Z}\left(Z_{1}\right),\dots,F_{Z}\left(Z_{n}\right)$ compared to
$Z_{1},\dots,Z_{n}$ is unchanged. Therefore using the probability integral
transform, we can assume without loss of generality that $\left(Z,X\right)$ is
a copula distribution, so that $Z$ and $X$ are each
$\operatorname{Uniform}\left(0,1\right)$ distributed. With the law of total
probability, write

$p_{\mathrm{success}}^{F_{Z,X}}\left(n,m,\alpha\right)=\int_{0}^{1}\dots\int_{0}^{1}\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\alpha\middle|Z_{1:n}=z_{1},\dots,Z_{m:n}=z_{m}\right)\\\
\times
f_{Z_{1:n},\dots,Z_{m:n}}\left(z_{1},\dots,z_{m}\right)\mathrm{d}z_{1}\dots\mathrm{d}z_{m},$
(C.3)

where

$f_{Z_{1:n},\dots,Z_{m:n}}\left(z_{1},\dots,z_{m}\right)=\dfrac{n!}{\left(n-m\right)!}\left(1-z_{m}\right)^{n-m}\mathbb{I}_{\left\\{z_{1}\leq\dots\leq
z_{m}\right\\}}$ (C.4)

is the joint PDF of the first $m$ order statistics of the i.i.d.
$\operatorname{Uniform}\left(0,1\right)$ sample
$\left(Z_{1},\dots,Z_{n}\right)$, for which the form may be deduced via [27,
§2.2]. Further note that since each pair $\left(Z_{i},X_{i}\right)$ is sampled
independently, then each $X_{\left\langle j\right\rangle}$ is conditionally
independent of all the variables

$\left(X_{\left\langle 1\right\rangle},\dots,X_{\left\langle
j-1\right\rangle},X_{\left\langle j+1\right\rangle},\dots,X_{\left\langle
m\right\rangle},Z_{1:n},\dots,Z_{\left(j-1\right):n},Z_{\left(j+1\right):n},\dots,Z_{m:n}\right),$
(C.5)

given $Z_{j:m}$. Denote the event
$\mathcal{Z}=\left\\{Z_{1:n}=z_{1},\dots,Z_{m:n}=z_{m}\right\\}$ for brevity.
Then

$\displaystyle\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\alpha\middle|\mathcal{Z}\right)$
$\displaystyle=1-\operatorname{Pr}\left(X_{\left\langle
1\right\rangle}>\alpha,\dots,X_{\left\langle
m\right\rangle}>\alpha\middle|\mathcal{Z}\right)$ (C.6)
$\displaystyle=1-\prod_{j=1}^{m}\operatorname{Pr}\left(X_{\left\langle
j\right\rangle}>\alpha\middle|Z_{j:n}=z_{j}\right)$ (C.7)
$\displaystyle=1-\prod_{j=1}^{m}\operatorname{Pr}\left(X>\alpha\middle|Z=z_{j}\right)$
(C.8)
$\displaystyle=1-\prod_{j=1}^{m}\left(1-\operatorname{Pr}\left(X\leq\alpha\middle|Z=z_{j}\right)\right)$
(C.9)
$\displaystyle=1-\prod_{j=1}^{m}\left(1-\mathcal{C}_{X|Z}\left(\alpha\middle|z_{j}\right)\right).$
(C.10)

Plugging (C.4) and (C.10) into (C.3), we have the result claimed. ∎

###  C.2 Proof of Proposition 3.1

Starting from (C.3) and applying (C.10), we have

$\displaystyle
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)$
$\displaystyle=\begin{multlined}\int_{0}^{1}\dots\int_{0}^{1}\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\alpha\middle|Z_{1:n}=z_{1},\dots,Z_{m:n}=z_{m}\right)\\\
\times
f_{Z_{1:n},\dots,Z_{m:n}}\left(z_{1},\dots,z_{m}\right)\mathrm{d}z_{1}\dots\mathrm{d}z_{m}\end{multlined}\int_{0}^{1}\dots\int_{0}^{1}\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\alpha\middle|Z_{1:n}=z_{1},\dots,Z_{m:n}=z_{m}\right)\\\
\times
f_{Z_{1:n},\dots,Z_{m:n}}\left(z_{1},\dots,z_{m}\right)\mathrm{d}z_{1}\dots\mathrm{d}z_{m}$
(C.13)
$\displaystyle=1-\mathbb{E}_{Z_{1:n},\dots,Z_{m:n}}\left[\prod_{j=1}^{m}\operatorname{Pr}\left(X>\alpha\middle|Z=Z_{j:n}\right)\right].$
(C.14)

Consider some arbitrary ordered selection of size $m$ from
$\left(Z_{1},\dots,Z_{n}\right)$, denoted
$\left(Z_{1}^{\prime},\dots,Z_{m}^{\prime}\right)$. Then we have multivariate
stochastic dominance [18, §6.B.1]

$\left(Z_{1:n},\dots,Z_{m:n}\right)\underset{\mathrm{st}}{\preceq}\left(Z_{1}^{\prime},\dots,Z_{m}^{\prime}\right),$
(C.15)

since

$Z_{1:n}\leq Z_{1}^{\prime},\quad Z_{2:n}\leq Z_{2}^{\prime},\quad\dots,\quad
Z_{m:n}\leq Z_{m}^{\prime}$ (C.16)

for every realisation of $\left(Z_{1},\dots,Z_{n}\right)$, so [18, Theorem
6.B.1] holds. Applying the SIPD condition,
$\prod_{j=1}^{m}\operatorname{Pr}\left(X>\alpha\middle|Z=z_{j}\right)$ is a
non-decreasing function in $\left(z_{1},\dots,z_{m}\right)$, so by the
definition of stochastic dominance [18, §6.B.1], we have

$\mathbb{E}_{Z_{1:n},\dots,Z_{m:n}}\left[\prod_{j=1}^{m}\operatorname{Pr}\left(X>\alpha\middle|Z=Z_{j:n}\right)\right]\leq\mathbb{E}_{Z_{1}^{\prime},\dots,Z_{m}^{\prime}}\left[\prod_{j=1}^{m}\operatorname{Pr}\left(X>\alpha\middle|Z=Z_{j}^{\prime}\right)\right].$
(C.17)

Hence the success probability is maximised when
$\left(Z_{1}^{\prime},\dots,Z_{m}^{\prime}\right)$ is chosen as the first $m$
order statistics. ∎

###  C.3 Proof of Proposition 3.2

For the proof of Proposition 3.2, we require the following lemma.

######  Lemma C.1.

Let $\mathbf{Z}_{\left[m\right]:n}:=\left(Z_{1:n},\dots,Z_{m:n}\right)$ denote
the joint first $m$ order statistics of an i.i.d. sample of size $n$ from
parent distribution $Z$. Then

$\mathbf{Z}_{\left[m\right]:\left(n+1\right)}\underset{\mathrm{st}}{\preceq}\mathbf{Z}_{\left[m\right]:n}.$
(C.18)

###### Proof.

Consider the following construction on the same probability space. Form an
i.i.d. sample of size $n+1$ from $Z$ and take the first $m$ order statistics.
This will be equal in law to $\mathbf{Z}_{\left[m\right]:\left(n+1\right)}$.
Now delete one element uniformly at random, and re-compute the first $m$ order
statistics. This will be equal in law to $\mathbf{Z}_{\left[m\right]:n}$.
Moreover, for every realisation (denoted in lowercase), we have

$\left(z_{1:\left(n+1\right)},\dots,z_{m:\left(n+1\right)}\right)\leq\left(z_{1:n},\dots,z_{m:n}\right).$
(C.19)

Therefore from the characterisation of stochastic dominance in [18, Theorem
6.B.1], (C.18) holds. ∎

For 3.4, it follows from Lemma C.18, via the same technique and analogous
arguments as in the proof of Proposition 3.1.

For 3.5, since

$\min\left\\{X_{\left\langle 1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle m+1\right\rangle}\right\\},$ (C.20)

then

$\displaystyle
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)$
$\displaystyle=\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\alpha\right)$ (C.21)
$\displaystyle\leq\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m+1\right\rangle}\right\\}\leq\alpha\right)$ (C.22)
$\displaystyle=p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m+1,\alpha\right).$
(C.23)

For 3.6, by De Morgan’s laws (i.e. complement of the union is the intersection
of the complements), put the definition of
$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)$ in terms of

$p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)=1-\operatorname{Pr}\left(\bigcap_{i=1}^{m}\left\\{X_{\left\langle
i\right\rangle}>x_{\alpha}^{*}\right\\}\right).$ (C.24)

Then apply the properties that $x_{\alpha}^{*}$ is non-decreasing in $\alpha$
and $\operatorname{Pr}\left(\bigcap_{i=1}^{m}\left\\{X_{\left\langle
i\right\rangle}>x_{\alpha}^{*}\right\\}\right)$ is non-increasing in
$x_{\alpha}^{*}$. ∎

###  C.4 Proof of Proposition 3.7

For the lower bound, consider the success probability where the selection of
size $m$ is uniformly random without replacement from
$\left(Z_{1},\dots,Z_{n}\right)$. This selection is identical in law to
$\left(Z_{1},\dots,Z_{m}\right)$, which are i.i.d. Then the success
probability can be computed by

$\displaystyle\operatorname{Pr}\left(\min\left\\{X_{1},\dots,X_{m}\right\\}\leq
x_{\alpha^{*}}\right)$
$\displaystyle=1-\prod_{j=1}^{m}\operatorname{Pr}\left(X_{j}>x_{\alpha}^{*}\right)$
(C.25) $\displaystyle=1-\left(1-\alpha\right)^{m}.$ (C.26)

Based on similar arguments provided from the proof of Proposition 3.1, it
follows that this lower bounds $p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}$.

For the upper bound, we can use the fact

$\min_{i\in\left\\{1,\dots,n\right\\}}X_{i}\leq\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle m\right\rangle}\right\\}$ (C.27)

to bound

$\displaystyle
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)$
$\displaystyle=\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle m\right\rangle}\right\\}\leq
x_{\alpha}^{*}\right)$ (C.28)
$\displaystyle\leq\operatorname{Pr}\left(\min_{i\in\left\\{1,\dots,n\right\\}}X_{i}\leq
x_{\alpha}^{*}\right)$ (C.29)
$\displaystyle=1-\prod_{i=1}^{n}\operatorname{Pr}\left(X_{i}>\alpha\right)$
(C.30) $\displaystyle=1-\left(1-\alpha\right)^{n}.$ (C.31)

∎

###  C.5 Proof of Proposition 3.4

For cases 3.8, 3.9, 3.10, the results are immediate from applying the general
upper and lower bounds in Proposition 3.7. For 3.11, assuming without loss of
generality that $\left(Z,X\right)$ is a copula and applying the property of
comotonicity, then

$\displaystyle
p_{\mathrm{success}}^{\mathcal{C}_{Z,X}}\left(n,m,\alpha\right)$
$\displaystyle=\operatorname{Pr}\left(\min\left\\{X_{\left\langle
1\right\rangle},\dots,X_{\left\langle
m\right\rangle}\right\\}\leq\alpha\right)$ (C.32)
$\displaystyle=\operatorname{Pr}\left(\min\left\\{Z_{1:n},\dots,Z_{m:n}\right\\}\leq\alpha\right)$
(C.33) $\displaystyle=\operatorname{Pr}\left(Z_{1:n}\leq\alpha\right)$ (C.34)
$\displaystyle=1-\prod_{i=1}^{n}\operatorname{Pr}\left(Z_{i}>\alpha\right)$
(C.35) $\displaystyle=1-\left(1-\alpha\right)^{n}.$ (C.36)

For 3.12, by independence of $Z$ and $X$ we have from (C.10):

$\displaystyle
1-\prod_{j=1}^{m}\left(1-\operatorname{Pr}\left(X\leq\alpha\middle|Z=z_{j}\right)\right)$
$\displaystyle=1-\prod_{j=1}^{m}\left(1-\operatorname{Pr}\left(X\leq\alpha\right)\right)$
(C.37) $\displaystyle=1-\left(1-\alpha\right)^{m}.$ (C.38)

This can be taken outside of the integral in (C.3) (where the integral
evaluates to one), so the result follows. Case 3.13 follows from the lower
bound in Proposition 3.7. Lastly for 3.14, as $n\to\infty$, the joint density
(C.4) converges to the Dirac delta function in argument $z_{m}$. Considering
the region of integration in the expression (3.1) where $0\leq
z_{1}\leq\dots\leq z_{m}$, we have that $z_{m}=0$ implies
$z_{1}=\dots=z_{m-1}=0$. Therefore

$\displaystyle\lim_{n\to\infty}p_{\mathrm{success}}\left(n,m,\alpha\right)$
$\displaystyle=1-\prod_{j=1}^{m}\left(1-\operatorname{Pr}\left(X\leq\alpha\middle|Z=0\right)\right)$
(C.39)
$\displaystyle=1-\left(1-\mathcal{C}_{X|Z}\left(\alpha\middle|0\right)\right)^{m}.$
(C.40)

∎

###  C.6 Proof of Theorem 4.6

For the proof of Theorem 4.6, we require the following lemmas.

######  Lemma C.2.

We have

$-p\log 4\leq\log\left(1-p\right)\leq-p,$ (C.41)

where the lower bound applies for all $p\in\left[0,\frac{1}{2}\right]$, and
the upper bound applies for all $p\geq 0$.

###### Proof.

The lower bound can be established over $p\in\left[0,\frac{1}{2}\right]$ via
concavity of $\log\left(1-p\right)$, i.e. line secants lie below the graph.
The upper bound can also be established over $p\geq 0$ via concavity. ∎

######  Lemma C.3.

For the Gaussian $Q$-function given by $Q\left(x\right)=1-\Phi\left(x\right)$,
we have

$\mathfrak{c}_{1}\exp\left(-\mathfrak{c}_{2}x^{2}\right)\leq
Q\left(x\right)\leq\frac{1}{2}\exp\left(-\dfrac{x^{2}}{2}\right)$ (C.42)

over $x\geq 0$, with

$\displaystyle\mathfrak{c}_{1}=\dfrac{1}{2}-\dfrac{\omega}{\pi}$ (C.43)
$\displaystyle\mathfrak{c}_{2}=\dfrac{\cot{\omega}}{\pi-2\omega}$ (C.44)

for any $\omega\in\left(0,\frac{\pi}{2}\right)$.

###### Proof.

The lower bound is due to [28, Equation (2)] and the upper bound is found in
[29, Equation (5)]. ∎

######  Lemma C.4.

Let $Z_{1:n}$ denote the first order statistic of an i.i.d. standard Gaussian
sample of size $n$. For any $\omega\in\left(0,\frac{\pi}{2}\right)$, let

$\displaystyle\mathfrak{c}_{1}=\dfrac{1}{2}-\dfrac{\omega}{\pi}$ (C.45)
$\displaystyle\mathfrak{c}_{2}=\dfrac{\cot{\omega}}{\pi-2\omega}.$ (C.46)

Consider $\widehat{Z}_{1:n}\sim\mathcal{N}\left(\mu_{n},\sigma_{n}^{2}\right)$
where

$\displaystyle\mu_{n}=-\sqrt{\dfrac{\log\left(n\mathfrak{c}_{1}\right)}{\mathfrak{c}_{2}}}$
(C.47) $\displaystyle\sigma_{n}^{2}=\dfrac{-\log\log
2}{2\mathfrak{c}_{2}\left(\log\left(n\mathfrak{c}_{1}\right)-\log\log
2\right)}.$ (C.48)

Then there exists some integer $\widetilde{n}\left(\omega\right)$ such that
for all $n\geq\widetilde{n}\left(\omega\right)$, we have
$Z_{1:n}\underset{\mathrm{st}}{\preceq}\widehat{Z}_{1:n}$, i.e.
$\widehat{Z}_{1:n}$ stochastically dominates $Z_{1:n}$.

###### Proof.

If $\widehat{Z}_{1:n}$ stochastically dominates $Z_{1:n}$, then by definition
$\operatorname{Pr}\left(\widehat{Z}_{1:n}\geq
z\right)\geq\operatorname{Pr}\left(Z_{1:n}\geq z\right)$ for all
$z\in\mathbb{R}$. Or in terms of the Gaussian $Q$-function
$Q\left(z\right)=1-\Phi\left(z\right)$, we require

$Q\left(z\right)^{n}\leq Q\left(\dfrac{z-\mu_{n}}{\sigma_{n}}\right)$ (C.49)

for all $z\in\mathbb{R}$, where the left-hand side follows from well-known
form of the distribution for the first order statistic [30, Equation
(2.2.11)]. The idea is to show that this bound holds over three different
intervals whose union is $\mathbb{R}$, being $\left(-\infty,\mu_{n}\right]$,
$\left[\mu_{n},0\right]$ and $\left[0,\infty\right)$. We begin with
$z\in\left(-\infty,\mu_{n}\right]$. Since $\mu_{n}\leq 0$, then via the lower
bound in Lemma C.3

$Q\left(z\right)^{n}\leq\left(1-\mathfrak{c}_{1}\exp\left(-\mathfrak{c}_{2}z^{2}\right)\right)^{n}.$
(C.50)

Since $0\leq\mathfrak{c}_{1}\exp\left(-\mathfrak{c}_{2}z^{2}\right)\leq 1/2$,
then putting $p=\mathfrak{c}_{1}\exp\left(-\mathfrak{c}_{2}z^{2}\right)$ in
the upper bound from Lemma C.2, we get

$\displaystyle Q\left(z\right)^{n}$
$\displaystyle\leq\exp\left(-n\mathfrak{c}_{1}\exp\left(-\mathfrak{c}_{2}z^{2}\right)\right)$
(C.51)
$\displaystyle=\exp\left(-\exp\left(-\left(\mathfrak{c}_{2}z^{2}-\log\left(n\mathfrak{c}_{1}\right)\right)\right)\right).$
(C.52)

Now using the upper bound in Lemma C.3, we have for $z\leq\mu_{n}$:

$1-\dfrac{1}{2}\exp\left(-\dfrac{\left(z-\mu_{n}\right)^{2}}{2\sigma_{n}^{2}}\right)\leq
Q\left(\dfrac{z-\mu_{n}}{\sigma_{n}}\right).$ (C.53)

The lower bound in Lemma C.2 implies $\exp\left(-p\log 4\right)\leq 1-p$.
Applying this with
$p=\frac{1}{2}\exp\left(-\frac{\left(z-\mu_{n}\right)^{2}}{2\sigma_{n}^{2}}\right)$
and after some manipulation, we arrive at

$Q\left(\dfrac{z-\mu_{n}}{\sigma_{n}}\right)\geq\exp\left(-\exp\left(-\left(\dfrac{\left(z-\mu_{n}\right)^{2}}{2\sigma_{n}^{2}}-\log\log
2\right)\right)\right).$ (C.54)

Thus a sufficient condition for $Q\left(z\right)^{n}\leq
Q\left(\frac{z-\mu_{n}}{\sigma_{n}}\right)$ over
$z\in\left(-\infty,\mu_{n}\right]$ is

$\exp\left(-\exp\left(-\left(\mathfrak{c}_{2}z^{2}-\log\left(n\mathfrak{c}_{1}\right)\right)\right)\right)\leq\exp\left(-\exp\left(-\left(\dfrac{\left(z-\mu_{n}\right)^{2}}{2\sigma_{n}^{2}}-\log\log
2\right)\right)\right)$ (C.55)

or equivalently,

$\left(\dfrac{1}{\sigma_{n}^{2}}-2\mathfrak{c}_{2}\right)z^{2}-2\dfrac{\mu_{n}}{\sigma_{n}^{2}}z+\dfrac{\mu_{n}^{2}}{\sigma_{n}^{2}}+2\log\left(n\mathfrak{c}_{1}\right)-2\log\log
2\geq 0.$ (C.56)

The roots of this quadratic are at

$z=\dfrac{\mu_{n}\pm\sqrt{\mu_{n}^{2}-\left(1-2\mathfrak{c}_{2}\sigma_{n}^{2}\right)\left(\mu_{n}^{2}+2\sigma_{n}^{2}\log\left(n\mathfrak{c}_{1}\right)-2\sigma_{n}^{2}\log\log
2\right)}}{1-2\mathfrak{c}_{2}\sigma_{n}^{2}}$ (C.57)

with discriminant $\Delta$ calculated by

$\Delta=\sigma_{n}^{4}\left(4\mathfrak{c}_{2}\log\left(n\mathfrak{c}_{1}\right)-4\mathfrak{c}_{2}\log\log
2\right)+\sigma_{n}^{2}\left(2\mathfrak{c}_{2}\mu_{n}^{2}-2\log\left(n\mathfrak{c}_{1}\right)+2\log\log
2\right).$ (C.58)

Under the same choice of $\omega$, note
$2\mathfrak{c}_{2}\mu_{n}^{2}=2\log\left(n\mathfrak{c}_{1}\right)$ and the
discriminant becomes

$\Delta=\sigma_{n}^{4}\left(4\mathfrak{c}_{2}\log\left(n\mathfrak{c}_{1}\right)-4\mathfrak{c}_{2}\log\log
2\right)+\sigma_{n}^{2}\left(2\log\log 2\right).$ (C.59)

The quadratic inequality is satisfied everywhere if the discriminant is non-
positive, so put $\Delta=0$ and taking the positive solution for
$\sigma_{n}^{2}$, giving

$\sigma_{n}^{2}=\dfrac{-\log\log
2}{2\mathfrak{c}_{2}\left(\log\left(n\mathfrak{c}_{1}\right)-\log\log
2\right)}.$ (C.60)

Therefore the inequality is satisfied provided $n\mathfrak{c}_{1}>1$, which
occurs for sufficiently large $n$, since $\mathfrak{c}_{1}>0$. Next we show
that the stochastic dominance condition is satisfied for
$z\in\left[\mu_{n},0\right]$, under the proposed choice of $\mu_{n}$ and
$\sigma_{n}$ above. Over this interval, we can use the same upper bound on
$Q\left(z\right)^{n}$ as before, and now we have the lower bound

$Q\left(\dfrac{z-\mu_{n}}{\sigma_{n}}\right)\geq\exp\left(-\left(\mathfrak{c}_{2}\left(\dfrac{z-\mu_{n}}{\sigma_{n}}\right)^{2}-\log\mathfrak{c}_{1}\right)\right).$
(C.61)

Thus we want to show that

$n\mathfrak{c}_{1}\exp\left(-\mathfrak{c}_{2}z^{2}\right)\geq\mathfrak{c}_{2}\left(\dfrac{z-\mu_{n}}{\sigma_{n}}\right)^{2}-\log\mathfrak{c}_{1}.$
(C.62)

Fix $z$, and recognise that
$\frac{\mu_{n}^{2}}{\sigma_{n}^{2}}=O\left(\left(\log n\right)^{2}\right)$ in
the right-hand side, while the left-hand side is $O\left(n\right)$. Therefore

$O\left(n\right)\geq\left(\left(\log n\right)^{2}\right)$ (C.63)

since $O\left(e^{n}\right)\geq O\left(n^{2}\right)$. Lastly for the interval
$z\in\left[0,\infty\right)$, we use the upper bound in Lemma C.3 to give

$Q\left(z\right)^{n}\leq\dfrac{1}{2^{n}}\exp\left(-\dfrac{nz^{2}}{2}\right)$
(C.64)

and we can use the same lower bound as in the preceding interval. In the same
vein as above, we want to show

$\left(\dfrac{n}{2}-\dfrac{\mathfrak{c}_{2}}{\sigma_{n}^{2}}\right)z^{2}-\dfrac{2\mathfrak{c}_{2}\mu_{n}}{\sigma_{n}^{2}}+n\log
2+\dfrac{\mu_{n}^{2}}{\sigma_{n}^{2}}-\log\mathfrak{c}_{1}\geq 0.$ (C.65)

The discriminant of the quadratic is non-positive when

$\left(\dfrac{n}{2}-\dfrac{\mathfrak{c}_{2}}{\sigma_{n}^{2}}\right)\left(n\log
2+\dfrac{\mu_{n}^{2}}{\sigma_{n}^{2}}-\log\mathfrak{c}_{1}\right)\geq\dfrac{\mathfrak{c}_{2}^{2}\mu_{n}^{2}}{\sigma_{n}^{4}}.$
(C.66)

The left-hand side is $O\left(n^{2}\right)$ and the right-hand side is
$O\left(\left(\log n\right)^{3}\right)$, thus this inequality is also
satisfied for sufficiently large $n$.

∎

To establish the right inequality in (4.6), assume without loss in generality
that $\left(Z,X\right)$ are bivariate standard Gaussian with correlation
$\rho$, as in (4.1). By establishing
$Z_{1:n}\underset{\mathrm{st}}{\preceq}\widehat{Z}_{1:n}$ via Lemma C.4, then
via the same technique as in the proof of Proposition 3.1, we have

$\displaystyle
p_{\mathrm{success}}^{\mathcal{NC}\left(p\right)}\left(n,1,\alpha\right)$
$\displaystyle=\int_{-\infty}^{\infty}\operatorname{Pr}\left(X\leq\Phi^{-1}\left(\alpha\right)\middle|Z=z\right)f_{Z_{1:n}}\left(z\right)\mathrm{d}z$
(C.67)
$\displaystyle\geq\int_{-\infty}^{\infty}\operatorname{Pr}\left(X\leq\Phi^{-1}\left(\alpha\right)\middle|Z=z\right)f_{\widehat{Z}_{1:n}}\left(z\right)\mathrm{d}z,$
(C.68)

where $f_{Z_{1:n}}\left(\cdot\right)$ is the density of the first order
statistic of the standard Gaussian, and
$f_{\widehat{Z}_{1:n}}\left(\cdot\right)$ is the density of
$\mathcal{N}\left(\mu_{n},\sigma^{2}_{n}\right)$. Using well-known
conditioning formulae for Gaussians [31, Equation (A.6)], we also have

$\left[X\middle|Z=z\right]\sim\mathcal{N}\left(\rho z,1-\rho^{2}\right).$
(C.69)

Thus, the integral (C.68) may be computed analytically with well-known
marginalisation formulae for linear-Gaussian systems [32, Theorem 2.3.1]. In
particular, if
$\widehat{Z}_{1:n}\sim\mathcal{N}\left(\mu_{n},\sigma^{2}_{n}\right)$ and
$\left[X\middle|\widehat{Z}_{1:n}=z\right]\sim\mathcal{N}\left(\rho
z,1-\rho^{2}\right)$, then
$X\sim\mathcal{N}\left(\rho\mu_{n},1-\rho^{2}+\rho^{2}\sigma_{n}^{2}\right)$.
Hence

$\int_{-\infty}^{\infty}\operatorname{Pr}\left(X\leq\Phi^{-1}\left(\alpha\right)\middle|Z=z\right)f_{\widehat{Z}_{1:n}}\left(z\right)\mathrm{d}z=\Phi\left(\dfrac{\Phi^{-1}\left(\alpha\right)-\rho\mu_{n}}{\sqrt{1-\rho^{2}+\rho^{2}\sigma_{n}^{2}}}\right).$
(C.70)

The left inequality in (4.6) is a result of monotonicity in $m$ from
Proposition 3.23.5. ∎

##  Appendix D Algorithms

The optimised lower bound in (4.7) can be implemented numerically. This is
done by using sufficient conditions found in the proof of Lemma C.4 to check
whether $n\geq\widetilde{n}\left(\omega\right)$ for a given $n$ and $\omega$.
We are required to check whether the inequality (C.49) is satisfied over each
of the intervals $\left(\infty,\mu_{n}\right]$, $\left[\mu_{n},0\right]$ and
$\left[0,\infty\right)$. The inequality is satisfied over
$\left(\infty,\mu_{n}\right]$ by construction provided $n\mathfrak{c}_{1}>1$,
whereas (C.66) contains the sufficient condition for the interval
$\left[0,\infty\right)$. As for the bounded interval $\left[\mu_{n},0\right]$,
we can directly evaluate (up to the available numerical precision) whether
(C.49) is satisfied. Pseudocode to implement this numerical certificate is
provided in Algorithm 1. Using this certificate, we can implement the
optimised lower bound (4.7), with pseudocode for this found in Algorithm 2.

Algorithm 1 Numerical certification of sufficient conditions for
$n\geq\widetilde{n}\left(\omega\right)$ in Theorem 4.6

1:function NumericalCert($n$, $\omega$)

2:
$\mathfrak{c}_{1}\leftarrow\dfrac{1}{2}-\dfrac{\omega}{\pi},\quad\mathfrak{c}_{2}\leftarrow\dfrac{\cot{\omega}}{\pi-2\omega}$

3:
$\mu_{n}\leftarrow-\sqrt{\dfrac{\log\left(n\mathfrak{c}_{1}\right)}{\mathfrak{c}_{2}}},\quad\sigma_{n}^{2}\leftarrow\dfrac{-\log\log
2}{2\mathfrak{c}_{2}\left(\log\left(n\mathfrak{c}_{1}\right)-\log\log
2\right)}$

4: if $n\mathfrak{c}_{1}\leq 1$ then $\triangleright$ Check sufficient
condition for the interval $\left(\infty,\mu_{n}\right]$

5: return $\mathtt{False}$

6: else if (C.49) fails over $\left[\mu_{n},0\right]$ then $\triangleright$
Check sufficient condition for the interval $\left[\mu_{n},0\right]$

7: return $\mathtt{False}$

8: else if (C.66) fails then $\triangleright$ Check sufficient condition for
the interval $\left[0,\infty\right)$

9: return $\mathtt{False}$

10: else

11: return $\mathtt{True}$

Algorithm 2 Implementation of lower bounds in Theorem 4.6 and (4.7)

1:function LowerBound($n$, $\alpha$, $\rho$, $\omega$) $\triangleright$ Lower
bound in (4.6)

2: if NumericalCert($n$, $\omega$) then

3: return Right-hand side of (4.6)

4: else

5: return $0$

6:function OptimisedLowerBound($n$, $\alpha$, $\rho$) $\triangleright$
Optimised lower bound in (4.7)

7: $\epsilon\leftarrow$ machine epsilon

8: return
$\max_{\omega\in\left[\epsilon,\pi/2-\epsilon\right]}$LowerBound($n$,
$\alpha$, $\rho$, $\omega$)

Algorithm 3 implements an optimised $n^{*}$ to address Problem 2.1(b) for the
Gaussian copula success probability, as described in Section 4.2. The
procedure also calls the numerical certificate from Algorithm 1.

Algorithm 3 Implementation of optimised $n^{*}$ for solving Problem 2.1(b)
with Gaussian copula

1:function nStar($\alpha$, $\rho$, $\delta$, $\omega$)

2: Solve quartic (4.9) for greatest real root $\mathsf{x}$

3:
$n^{*}\leftarrow\left\lfloor\exp\left(\mathsf{x}^{2}-\log\mathfrak{c}_{1}\right)\right\rfloor$

4: if NumericalCert($n^{*}$, $\omega$) then

5: return $n^{*}$

6: else

7: return $\infty$

8:function nStarOptimised($\alpha$, $\rho$, $\delta$)

9: $\epsilon\leftarrow$ machine epsilon

10: return
$\min_{\omega\in\left[\epsilon,\pi/2-\epsilon\right]}$nStar($\alpha$, $\rho$,
$\delta$, $\omega$)