Informative Goodness-of-Fit for Multivariate Distributions Sara Algeri1

1 School of Statistics, University of Minnesota,
0461 Church St SE, Minneapolis, MN 55455, USA.
Email<EMAIL_ADDRESS>

###### Abstract

This article introduces an informative goodness-of-fit (iGOF) approach to
study multivariate distributions. When the null model is rejected, iGOF allows
us to identify the underlying sources of mismodeling and naturally equips
practitioners with additional insights on the nature of the deviations from
the true distribution. The informative character of the procedure is achieved
by exploiting smooth tests and random fields theory to facilitate the analysis
of multivariate data. Simulation studies show that iGOF enjoys high power for
different types of alternatives. The methods presented here directly address
the problem of background mismodeling arising in physics and astronomy. It is
in these areas that the motivation of this work is rooted.

Multivariate goodness-of-fit, Rosenblatt transform, smooth tests, background
mismodeling.

##  1 Introduction

_Scientific motivations._ When searching for the signals of new particles, or
when aiming to detect new astronomical objects, a common difficulty arising in
the analysis of the data collected by the detectors is the impossibility of
correctly specifying the background distribution. In physics and astronomy, we
typically refer with “background” or “noise” to the signal of all the
astrophysical sources which are not those we aim to discover. Unfortunately,
since many sources contribute to the background, its distribution is
particularly difficult to model (e.g., Priel et al., 2017; Dauncey et al.,
2015; Algeri et al., 2018).

Moreover, if the model postulated by the scientists is rejected, it is often
difficult to identify the invalidating causes. As a result, this aspect is
typically addressed by conducting a suite of exploratory analyses to
adequately constrain the parameters involved, followed by a validity check for
a newly postulated distribution. Given the complexity of the models
investigated through physics experiments, however, this may result in a
substantial investment of resources (e.g., Balázs et al., 2017); even more so
when having to choose between tens of plausible theoretical models (e.g.,
Scott, 2018).

_Statistical formulation of the problem._ In statistical terms, these
difficulties translate into two main questions arising in the statistical
analysis of multivariate data. Specifically, given a random vector
$\bm{X}=(X_{1},\dots,X_{p})$, we may wonder:

  * Q1.

_is the distribution of $\bm{X}$ correctly specified and, if not, in what way
the true data distribution diverges from that hypothesized under the null
hypothesis?_

  * Q2.

_How can we improve our postulated model?_ _Or in other words, can we provide
a data-driven correction of for it?_

As noted by Pearson (1938), smooth tests, originally introduced by Neyman
(1937), naturally allow us to capture and model the departure of $f$ from $g$
and thus, they offer the framework to directly address Q1 and Q2.

In order to provide a high level overview on smooth tests, let $f$ be the true
(unknown) probability density function (pdf) of a random variable
$X\in\mathbb{R}$, $g$ is the hypothesized density and $G$ the respective
cumulative density function (cdf). For example, in the above-mentioned problem
of background mismodeling, $f$ represents the true background distribution and
$g$ is the background model postulated by the scientists. A smooth model for
the true probability law $f$ can be specified as

$f(x)=g(x)d\bigl{(}G(x)\bigl{)}=g(x)\biggl{\\{}1+\sum_{j\geq
1}\theta_{j}T_{j}\bigl{[}G(x)\bigl{]}\biggl{\\}},$ (1)

where $d(G(x))=\frac{f(x)}{g(x)}$ is the likelihood ratio and the term in the
curly brackets is an orthonormal expansion for $d$. A smooth test (e.g.,
Neyman, 1937; Barton, 1953; Ledwina, 1994) consists of testing if any of the
coefficients $\theta_{j}$ in (1) is different from zero. Finally, by
estimating $d\bigl{(}G(x)\bigl{)}$ and constructing adequate confidence bands,
it is possible to visualize the nature of the departure of $f$ from $g$.

Despite their usefulness, smooth tests are mainly limited to the univariate
setting. In light of this, the main methodological task of this work is to
extend this framework to allow for the analysis of multivariate data.

_Main results and organization._ The theoretical framework is presented in
Section 2. There, we define a suitable expansion of the likelihood ratio
through orthonormal functions on the unit cube. As shown in Sections 3 and 4,
such representation substantially simplifies the subsequent stages of
estimation, model selection and (post-selection) inference. In Section 5, we
discuss a simple ANOVA-like testing strategy to identify possible sources of
mismodeling. Power studies are conducted via simulations in both Sections 4
and 5. As noted above, this work finds its main motivations in the context of
astrophysical searches. Therefore, in Section 6 we illustrate how iGOF can be
used to address the problem of mismodeling of the cosmic background
considering a realistic simulation from the Fermi Large Area Telescope (Atwood
et al., 2009). Despite this article mainly focuses on the analysis of
continuous data, extensions to the discrete setting are discussed in Section
7. Section 8 collects a summary of the results and a discussion of the
limitations of iGOF. Technical proofs and codes are provided in the
Supplementary Material. A summary of the main notation used throughout the
paper is available in the Appendix.

##  2 Theoretical framework

###  2.1 Transformations of the likelihood ratio on the unit cube

Suppose $F$ is the true distribution function of a random vector
$\textbf{X}\in\mathcal{X}\subseteq\mathbb{R}^{p}$ and denote with $G$ its
hypothesized distribution. $F$ and $G$ are assumed to be continuous with
densities $f$ and $g$. Furthermore, assume that $f(\bm{x})=0$ whenever
$g(\bm{x})=0$. For every $\bm{x}=(x_{1},\dots,x_{p})\in\mathcal{X}$, the
hypothesized density $g$ is such that

$g(\bm{x})=\prod_{d=1}^{p}g_{d}(x_{d}|{\bm{x}}_{<d}),$

where $\bm{x}_{<d}=(x_{1},\dots,x_{d-1})$ and $g_{1},\dots,g_{p}$ are suitable
densities with associated cdfs and quantile functions $G_{d}$ and $Q_{d}$, for
all $d=1,\dots,p$. The likelihood ratio between $F$ and $G$ can be specified
as

$d(\bm{u})=\frac{f\bigl{(}\bm{Q}(\bm{u})\bigl{)}}{g\bigl{(}\bm{Q}(\bm{u})\bigl{)}},\quad\bm{u}\in[0,1]^{p}$
(2)

where
$\bm{u}=(u_{1},\dots,u_{p})=\bigl{(}G_{1}(x_{1}),\dots,G_{p}(x_{p}|{\bm{x}}_{<p})\bigl{)}=\bm{G}_{R}(\bm{x})$
is the Rosenblatt transformation (Rosenblatt, 1952)111Notice that, in general,
$\bm{G}_{R}(\bm{x})\not\equiv G(\bm{x})$ as the Rosenblatt’s transform
$\bm{G}_{R}(\bm{x})\in[0,1]^{d}$ whereas the cdf $G(\bm{x})\in[0,1]$..
Whereas, $\bm{Q}(\bm{u})=\bigl{(}Q_{1}(u_{1}),\dots,Q_{p}(u_{p})\bigl{)}$, for
all $d=1,\dots,p$.

In the bivariate setting, for instance, let $G_{1}\equiv G_{X_{1}}$ and
$G_{2}\equiv G_{X_{2}|X_{1}}$, i.e., the hypothesized marginal cdf of $X_{1}$
and the hypothesized conditional cdf of $X_{2}|X_{1}$, respectively. Hence,
(2) specifies as

$d(u_{1},u_{2})=\frac{f_{X_{1}X_{2}}\bigl{(}Q_{1}(u_{1}),Q_{2}(u_{2})\bigl{)}}{g_{X_{1}X_{2}}\bigl{(}Q_{1}(u_{1}),Q_{2}(u_{2})\bigl{)}}.$

######  Remark 2.1.

As a plausible alternative to Rosenblatt’s transform, one could choose each
$G_{d}\equiv G_{X_{d}}$, which corresponds to assuming independence among the
components of $\bm{X}$. In this setting, (2) is the copula density (e.g.,
Nelsen, 2007) of $\bm{X}$ under $G$. Despite this choice could simplify
substantially the computations, it would not allow to test models where the
components of $\bm{X}$ are assumed to be dependent. Moreover, it is worth
pointing out that there are situations where such transformation cannot be
specified (e.g., Section 6).

To provide a sufficiently detailed representation of the substructures
characterizing the distribution of $\bm{X}$ (see Q1 in Section 1), a natural
approach is that of expressing (2) by means of a suitable orthonormal basis in
$L^{2}[0,1]^{p}$.

For instance, let $T_{j_{d}}(u_{d})$ be the $j_{d}^{th}$ normalized shifted
Legendre polynomial evaluated at $u_{d}=G_{d}(x_{d}|\bm{x}_{<d})$, with
$T_{0}(u_{d})=1$, $T_{1}(u_{d})=\sqrt{12}(u_{d}-0.5)$, etc. (e.g., Section
LABEL:Ex1app, Supplementary Material). Each $\\{T_{j_{d}}(u_{d})\\}_{j_{d}\geq
0}$ forms a basis in $L^{2}[0,1]$. Hence, we can exploit a well known result
in Hilbert space theory (e.g., Proposition 2 Reed and Simon, 1980, p.50) which
asserts that given two orthonormal bases $\\{\psi_{j}\\}$, $\\{\phi_{k}\\}$
for the Hilbert spaces $\mathcal{H}_{1}$, $\mathcal{H}_{2}$, then
$\\{\psi_{j}\otimes\phi_{k}\\}$ is an orthonormal basis for
$\mathcal{H}_{1}\otimes\mathcal{H}_{2}$. It follows that the tensor product
basis $\\{T_{j_{1},\dots,j_{p}}(\bm{u})\\}_{j_{1}\dots j_{p}\geq 0}$ of
functions

$T_{j_{1}\dots j_{p}}(\bm{u})=\prod_{d=1}^{p}T_{j_{d}}(u_{d})$ (3)

forms an orthonormal basis on $L^{2}[0,1]^{p}$, the Hilbert space of square
integrable function over the $p$-dimensional unit cube.

Notice that despite any orthonormal basis in $[0,1]$ could be used to
construct a tensor product basis in $[0,1]^{p}$, here we focus on the
normalized shifted Legendre polynomials. This choice is justified by the fact
that the latter are special cases of the so called LP-score functions
(Mukhopadhyay and Wang, 2020, e.g.,). As discussed in Section 7, the LP score
functions allow for extensions to the discrete setting.

Finally, under the assumption $d(\bm{u})\in L^{2}[0,1]^{p}$, we can write

$d(\bm{u})=\sum_{j_{1}\geq 0,\dots,j_{p}\geq 0}\theta_{j_{1}\dots
j_{p}}T_{j_{1}\dots j_{p}}(\bm{u}),\qquad\text{ $\bm{u}\in[0,1]^{p}$}$ (4)

with $\theta_{j_{1}\dots j_{p}}=\int_{[0,1]^{p}}T_{j_{1}\dots
j_{p}}(\bm{u})d(\bm{u})\text{d}\bm{u}$. The expansion in (4) follows from
Theorem II.6 in Reed and Simon (1980) and it is equivalent to say that the sum
on the right-hand side converges to $d(\bm{u})$ in $L^{2}[0,1]^{p}$.

######  Remark 2.2.

An anonymous referee correctly pointed out that the likelihood ratio can also
be expanded through an orthonormal expansion on the original domain
$\mathcal{X}$, bypassing the need of Rosenblatt’s transform. In our context,
however, the Rosenblatt transform is particularly useful for two main reasons.
First of all, one can show (Proposition 3.1 to follow) that $d(\bm{u})$
corresponds to the density of $\bm{U}=\bm{G}_{R}(\bm{X})$. This fact will
simplify substantially the estimation process (Section 3). Second, by
transforming the data on the compact compact domain $[0,1]^{p}$ we will be
able to exploit exploit results from random fields theory to perform inference
(Section 4).

##  3 Estimation

The summations in (4) are taken up to infinity. However, to make the expansion
operational, it is necessary to truncate the series in (4) at integers values
$m_{1},\dots,m_{p}$. That is because, effectively, the coefficients
$\theta_{j_{1}\dots j_{p}}$ need to be estimated and, consequently, the more
terms are included in (4), the larger the variance of the resulting estimator
of $d(\bm{u})$ (see Section 4.2 for a more detailed discussion on model
selection).

For the sake of simplifying the notation in this section and those to follow,
denote with $\mathcal{K}$ the set

$\mathcal{K}:=\biggl{\\{}\\{j_{1}\dots j_{p}\\},\text{ with
}j_{d}=0,\dots,m_{d},\text{ for all }d=1,\dots,p,\text{ and
}\sum_{d=1}^{p}j_{d}\neq 0\biggl{\\}}$ (5)

of cardinality $|\mathcal{K}|=M=\prod_{d=1}^{p}(m_{d}+1)-1$. That is,
$\mathcal{K}$ contains all the $p-$tuples $\\{j_{1}\dots j_{p}\\}$ of indexes
$j_{d}=0,\dots,m_{d}$, $d=1,\dots,p$ apart from the $p-$tuple $\\{0\dots
0\\}$. Let $\bm{\theta}$ be the $M\times 1$ vector of components
${\theta}_{k}$, with $k\in\mathcal{K}$. Similarly, denote with
$\bm{T}(\bm{u})$ the $M\times 1$ vector of elements $T_{k}(\bm{u})$,
$k\in\mathcal{K}$.

Consider $\bm{x}_{1},\dots,\bm{x}_{n}$, a sample of $n$ i.i.d. observations
from $\bm{X}$, and let $\bm{U}=\bm{G}_{R}(\bm{X})$ be the respective
Rosenblatt transformation. Denote with $\bm{u}_{1},\dots,\bm{u}_{n}$ the
sample of elements $\bm{u}_{i}=\bm{G}_{R}(\bm{x}_{i}).$ The parameter
${\bm{\theta}}$ can be estimated by means of the vector
$\widehat{\bm{\theta}}$ of components

$\widehat{\theta}_{k}=\frac{1}{n}\sum_{i=1}^{n}T_{k}(\bm{u}_{i})\quad\text{
for all $k\in\mathcal{K}$ },$ (6)

The mean and covariance matrix of $\widehat{\bm{\theta}}$ and an estimator of
$d(\bm{u})$ are given in Proposition 3.1.

######  Proposition 3.1.

The likelihood ratio $d\bigl{(}\bm{u}\bigl{)}$ is the density of the random
vector $\bm{U}$ and

$E[\widehat{\bm{\theta}}]=\bm{\theta}\quad\text{and}\quad\text{Cov}(\widehat{\bm{\theta}})=\bm{\Sigma}$
(7)

where $\bm{\Sigma}$ has diagonal elements
$\frac{\sigma^{2}_{k}}{n}=\frac{1}{n}V\bigl{[}T_{k}(\bm{U})\bigl{]}$ and non-
diagonal elements
$\frac{\sigma_{k,h}}{n}=\frac{1}{n}\text{Cov}\bigl{[}T_{k}(\bm{U}),T_{h}(\bm{U})\bigl{]}$,
with $k,h\in\mathcal{K}$. Furthermore, if $F\equiv G$, the equalities in (7)
reduce to

$E[\widehat{\bm{\theta}}]=\bm{0}\quad\text{and}\quad\text{Cov}(\widehat{\bm{\theta}})=\frac{1}{n}\bm{I}_{M},$
(8)

where $\bm{0}$ is the $M\times 1$ zero vector and $\bm{I}_{M}$ is the $M\times
M$ identity matrix.

Finally, an estimator of $d(\bm{u})$ is

$\displaystyle\widehat{d}(\bm{u})$
$\displaystyle=1+\widehat{\bm{\theta}}^{\prime}\bm{T}(\bm{u}),$ (9)

and has variance
$V\Bigl{[}\widehat{d}(\bm{u})\Bigl{]}=\bm{T}(\bm{u})^{\prime}\bm{\Sigma}\bm{T}(\bm{u})$.

It is worth pointing out that, when the likelihood ratio is formulated as a
density, it is often referred to as _comparison density_ (e.g., Parzen, 2004).

|
---|---
Figure 1: True (left panel) and estimated (right panel) likelihood ratio for
Example I. The estimate on the right has been obtained via (9) with $m_{1}=4$
and $m_{2}=3$. The components of the $\widehat{\bm{\theta}}$ vector have been
selected via the AIC criterion in (19).

Combining (1), (2) and (9) an estimate of $f$ is

$\displaystyle\widehat{f}(\bm{x})=g(\bm{x})\widehat{d}\bigl{(}\bm{G}_{R}(\bm{x})\bigl{)}=g(\bm{x})\bigl{[}1+\widehat{\bm{\theta}}^{\prime}\bm{T}\bigl{(}\bm{G}_{R}(\bm{x})\bigl{)}\bigl{]}$
(10)

Notice that the estimator $\widehat{f}$ incorporates the information carried
by the hypothesized model $g$; whereas, the estimator in the square brackets
provides a data-driven correction for it. Furthermore, define the integrated
squared bias (ISB) of $\widehat{d}(\bm{u})$ to be

$ISB=\int_{[0,1]^{p}}\Bigl{(}E[\widehat{d}(\bm{u})]-d(\bm{u})\Bigl{)}^{2}\text{d}\bm{u}.$
(11)

From Proposition 3.2 it follows that the closer $g$ is to $f$ in terms of
squared normalized distance the lower the ISB of $\widehat{d}(\bm{u})$.

######  Proposition 3.2.

The integrated squared bias of the estimator in (9) is

$\bigintsss_{[0,1]^{p}}\biggl{(}\frac{f\bigl{(}Q(\bm{u})\bigl{)}-g\bigl{(}Q(\bm{u})\bigl{)}}{g\bigl{(}Q(\bm{u})\bigl{)}}\biggl{)}^{2}\text{d}\bm{u}-\bm{\theta}^{\prime}\bm{1},$
(12)

where $\bm{1}$ is the $M\times 1$ unit vector.

The estimate in (10) is essentially that of a smooth model (e.g., Rayner and
Best, 1990), that is, a smoothed version of the true underlying probability
function. Similarly to the smooth model proposed by Barton (1953) in the
univariate setting, the estimator in (10) may lead to estimate that are not
_bona-fide_ , i.e, they may be negative and/or they may not integrate/sum up
to one. In this manuscript we focus on (10) mostly for the sake of
mathematical convenience in deriving the inferential results of Section 4.
Nonetheless, bona-fide estimators can be constructed similarly to the
univariate case as described in Algeri and Zhang (2020).

_Example I._ In direct searches for dark matter, the dominant background
sources are neutron recoils which may produce signals mimicking those expected
from dark matter candidates (e.g., Westerdale, 2016). As a toy example,
suppose we are interested in assessing the validity of a given distribution
for the nuclear recoil background specified over the energy region
$\mathcal{X}=[5,20]KeVnr\times[0,17]KeVnr$. Each observations in $\mathcal{X}$
corresponds to the scintillation of photons ($X_{1}$) and ionization electrons
($X_{2}$) (e.g., Aprile et al., 2017). The hypothesized background
distribution, $G_{X_{1}X_{1}}$, is that of a truncated bivariate normal with
mean vector $(12,8)$, variances $8$ and $12$ and covariance $2$. Moreover,
suppose that one additional background source is present. The latter is also a
bivariate normal with the same mean vector, variances $4$ and $20$ and
covariance $5$. Thus, the true model, $F_{X_{1}X_{1}}$, involves a mixture of
two, overlapping truncated bivariate Gaussians with mixture parameter $0.15$.
In order to estimate the likelihood ratio, set $G_{1}=G_{X_{1}}(x_{1})$ and
$G_{2}=G_{X_{2}|X_{1}}$. The estimated likelihood ratio, obtained over a
sample of $n=5,000$, is shown in the right panel of Figure 1, whereas the left
panel shows the true likelihood ratio. A closed form expression for the
estimate shown on the right panel is given in equation LABEL:LR1 in the
Supplementary Material.

While the estimate obtained recovers the main departures from uniformity, the
contours highlight that the estimator is rather noisy. Therefore, it is
important to investigate the properties of (9) to assess the significance of
the deviations observed.

##  4 Inference and model selection

###  4.1 Pre-selection inference

A smooth test for $H_{0}:G\equiv F$ versus $H_{1}:G\not\equiv F$ consists in
reformulating the problem as a test for uniformity of $\bm{U}$. Specifically,
(2) implies that $F\equiv G$ whenever $d(\bm{u})=1$, and thus

$\begin{split}H_{0}:d(\bm{u})=1\quad\text{$\forall\bm{u}\in[0,1]^{p}$}\quad\text{versus}\quad
H_{1}:\exists\bm{u}\in[0,1]^{p}\text{ s.t. }d(\bm{u})\neq 1.\end{split}$ (13)

It is easy to see that $d(\bm{u})=1$ for all $\bm{u}\in[0,1]^{p}$, when all
${\theta}_{k}$, $k\in\mathcal{K}$, are identically equal to zero. Hence, in
practice, we test

$H_{0}:\bm{\theta}=\bm{0}\qquad\text{vs}\qquad H_{1}:\bm{\theta}\neq\bm{0}.$
(14)

Notice that $H_{0}$ in (13) implies $H_{0}$ in (14), but the opposite is not
true in general. Whereas, $H_{1}$ in (14) does imply $H_{1}$ in (13).

With a little abuse of nomenclature, in this section and those to follow, we
will refer to $G$ as the “null model”. Furthermore, we will refer to $H_{0}$
in (13) when generically saying “under $H_{0}$”. However, most of the results
presented here, only require validity of the milder $H_{0}$ in (14).

To conduct our inference, we consider the so-called _deviance_ test
statistics, i.e.,

$D=n\widehat{\bm{\theta}}^{\prime}\widehat{\bm{\theta}}.$ (15)

Its asymptotic null distribution is given in Theorem 4.1.

######  Theorem 4.1.

If $H_{0}$ is true, then

$\sqrt{n}\widehat{\bm{\theta}}\xrightarrow{d}N(\bm{0},\bm{I}),\quad\text{as
$n\rightarrow\infty$}$ (16)

where $N(\bm{0},\bm{I})$ denotes a standard multivariate normal distribution.
Furthermore,

$D\xrightarrow{d}\chi^{2}_{M},\quad\text{as $n\rightarrow\infty$},$ (17)

where $M$ is the length of $\widehat{\bm{\theta}}$.

Corollary 4.2 follows directly from Theorem 4.1.

######  Corollary 4.2.

Denote with $\\{\widehat{d}(\bm{u})\\}$ the random field indexed by
$\bm{u}\in[0,1]^{p}$ with components as in (9). Moreover, assume that
$\widehat{\theta}_{k}=o(n^{-1/2})$ for all $k\not\in\mathcal{K}$. If $H_{0}$
is true,

$\Biggl{\\{}\frac{\widehat{d}(\bm{u})-1}{\sqrt{\frac{1}{n}\bm{T}(\bm{u})^{\prime}\bm{T}(\bm{u})}}\Biggl{\\}}\xrightarrow{d}\bm{Z}(\bm{u}),\quad\text{as
$n\rightarrow\infty$,}$ (18)

where $\bm{Z}(\bm{u})$ denotes a Gaussian random field with mean zero, unit
variance and covariance function
$\text{Cov}\Bigl{(}\bm{Z}(\bm{u}),\bm{Z}(\bm{u}^{\dagger})\Bigl{)}=\frac{\bm{T}(\bm{u})^{\prime}\bm{T}(\bm{u}^{\dagger})}{\sqrt{\bm{T}(\bm{u})^{\prime}\bm{T}(\bm{u})\bm{T}(\bm{u}^{\dagger})^{\prime}\bm{T}(\bm{u}^{\dagger})}}.$

At this stage, constructing inference on the basis of Theorem 4.1 and
Corollary 4.2 would be tempting. However, to guarantee the validity of our
results we must take into account that, when estimating the likelihood ratio
in (9), a model selection procedure is likely to be implemented.
Unfortunately, when a model is selected by a pool of possibilities, such
process introduces an additional source of variability and thus the resulting
inference is automatically affected (e.g., Berk et al., 2013). Section 4.2
addresses this aspect directly.

###  4.2 Post-selection inference

The estimate of the likelihood ratio considered so far involves up to $M$
functions $T_{k}(\bm{u})$. Nonetheless, it is possible that not all of these
$M$ terms are needed to capture the departures of $G$ from $F$ and indeed, it
is often convenient to remove some of them in order to avoid unnecessary
sources of noise. Various criteria have been proposed in literature for
density estimation and smooth models (e.g., Mukhopadhyay, 2017; Algeri, 2020)
and which can be easily extended to the multivariate setting. Here, we focus
on the approach of Mukhopadhyay (2017) and which specifies as follows.

Let $\widehat{\theta}_{(k)}$ be the $k^{th}$ largest $\widehat{\theta}_{k}$
estimate in order of magnitude, i.e.,
$\widehat{\theta}_{(1)}^{2}\geq\widehat{\theta}_{(2)}^{2}\geq\dots\geq\widehat{\theta}_{(M)}^{2}$.
Select the $K$ largest coefficients which maximize either

$\text{BIC}(K)=\sum_{(k)=1}^{K}\widehat{\theta}^{2}_{(k)}-\frac{K\log
n}{n}\quad\text{or}\quad\text{AIC}(K)=\sum_{(k)=1}^{R}\widehat{\theta}^{2}_{(k)}-\frac{2K}{n}.$
(19)

Notice that, as defined in (5), each $k$ is a $p-$tuple of indexes $j_{1}\dots
j_{p}$, whereas $(k)$ is the integer value corresponding to the order of
magnitude of the respective coefficient $\widehat{\theta}_{k}$. Hence, the
summations in (19) and those to follow are taken over $(k)=1,\dots,K$, that is
the $K$ $p-$tuples of indexes $j_{1}\dots j_{p}$ with the $K^{th}$ largest
estimates $\widehat{\theta}_{k}$.

An estimate of $d(\bm{u})$, is then selected via (19) from the family of
estimators

$\widehat{d}_{(K)}(\bm{u})=1+\sum_{(k)=1}^{K}\widehat{\theta}^{2}_{(k)}T_{(k)}(\bm{u}),\quad\text{K=1,\ldots,M}$
(20)

where the subscript $(K)$ is used to emphasize that the estimator in (20)
includes only the $K^{th}$ largest $\widehat{\theta}_{k}$ estimated
coefficients. Clearly, the choice of BIC or AIC is arbitrary and, from a
practical standpoint, the BIC tends to lead to smoother estimates than the
AIC.

The selection rules in (19) compare $M$ possible models assuming that each
$m_{d}$, for $d=1,\dots,D$ was fixed before the researcher looked at the data.
Valid post-selection inference can then be constructed as in Theorem 4.1 and
Corollary 4.3. The respective proofs are provided in the Supplementary
material.

######  Corollary 4.3.

Denote with $\widehat{d}_{(K*)}$ the estimator of $d(\bm{u})$ selected via
(19), and let $D_{(K^{*})}=\sum_{(k)=1}^{K^{*}}\widehat{\theta}^{2}_{(k)}$ be
the respective deviance statistics. As $n\rightarrow\infty$, a valid post-
selection bound for the p-value to test (13) is

$\text{p-value}_{adj}=P(\chi^{2}_{M}>D_{\text{obs}}),$ (21)

where $D_{\text{obs}}$ is the value of $D_{(K^{*})}$ observed.

Where the bound in (21), follows from the fact that the estimators in (20) are
nested, for all $K=1,\dots,M-1$, and thus each $D_{(K)}$ is stochastically
lower or equal than $D_{(M)}$. Hence, for all $K=1,\dots,M-1$,
$P(D_{(K)}>D_{\text{obs}})$ is smaller than $P(D_{(M)}>D_{\text{obs}})$.

In order to grasp further insights on the deviations of $G$ from $F$, it is
worth constructing adequate confidence bands. This can be done, while
accounting for post-selection adjustments, as in Corollary 4.4.

######  Corollary 4.4.

Denote with $\widehat{d}_{(K*)}$ the estimator of $d(\bm{u})$ selected via
(19), and denote with $SE_{0}\bigl{[}\widehat{d}_{(K^{*})}(\bm{u})\bigl{]}$
its standard error under $H_{0}$. Valid (post-selection adjusted)
$(1-\alpha)\%$ confidence regions, under $H_{0}$ in (13), are

$\biggl{[}1-c_{\alpha/2}SE_{0}\bigl{[}\widehat{d}_{(K^{*})}(\bm{u})\bigl{]},1+c_{\alpha/2}SE_{0}\bigl{[}\widehat{d}_{(K^{*})}(\bm{u})\bigl{]}\biggl{]}\qquad\text{for
all $\bm{u}\in[0,1]^{p}$}$ (22)

with $c_{\alpha/2}$ such that

$P\Biggl{(}\sup_{\bm{u}}\biggl{\\{}\frac{\widehat{d}_{(M)}(\bm{u})-1}{SE_{0}\bigl{[}\widehat{d}_{(M)}(\bm{u})\bigl{]}}\biggl{\\}}>c_{\alpha/2}\Biggl{|}H_{0}\Biggl{)}=\frac{\alpha}{2}.$
(23)

Intuitively, $\widehat{d}_{(M)}$ is the least smooth among all the estimators
considered; hence, we expect that the random field resulting from
$\widehat{d}_{(M)}$ has the largest probability of crossing the fixed level
$c_{\alpha/2}$.

From a theoretical perspective, a highly non-trivial aspect in the
construction of (22) is the estimation of the quantile $c_{\alpha/2}$.
Probabilities such (23) are known in literature as _excursion probabilities_
(e.g., Adler, 2000) and which cannot be expressed in closed form. A possible
solution for constructing the confidence bands in (22), is that of proceeding
by estimating $SE_{0}\bigl{[}\widehat{d}_{(K^{*})}(\bm{u})\bigl{]}$ and
$c_{\alpha/2}$ via Monte Carlo simulations (see Algeri and Zhang, 2020,
Algorithm 1). Unfortunately, in the most crucial (astro)physical searches the
level of significance required to claim a new discovery is typically in the
order of $\alpha=10^{-7}$ (e.g., Lyons, 2013), and thus Monte Carlo
simulations may be computationally prohibitive. This is further aggravated
when dealing with complex models for which even a single Monte Carlo replicate
can be highly expensive in terms of both computational and time resources.

As a valid alternative, for continuous $F$ and $G$, accurate approximations
for (23) under mild smoothness conditions exist (e.g., Taylor and Worsley,
2008). In our setting, smoothness follows from the fact that the random field
in (18) and the respective limit can be written as a linear combination of the
functions
$\frac{T_{k}(\bm{u})}{\sqrt{\sum_{k\in\mathcal{K}}T^{2}_{k}(\bm{u})}}$ (see
proof of Corollary 4.2 in the Supplementary Material) which are composition of
Legendre polynomials, and thus, admit infinite partial derivatives.

An approximation for the left-hand side of (23) is

$\bigl{(}1-\Phi(c_{\alpha/2})\bigl{)}+\mathcal{L}_{1}\frac{e^{-\frac{c_{\alpha/2}^{2}}{2}}}{\pi}+\mathcal{L}_{2}\frac{e^{-\frac{c_{\alpha/2}^{2}}{2}}}{\sqrt{2}\pi^{3/2}}+O\biggl{(}\exp\Bigl{(}-\frac{\gamma
c_{\alpha/2}^{2}}{2}\Bigl{)}\biggl{)},\quad\text{as $n\rightarrow\infty$,}$
(24)

for some $\gamma>1$ (Taylor et al., 2005). In (24), $\mathcal{L}_{1}$ and
$\mathcal{L}_{2}$ are constant known as Lipischitz-Killing curvatures and are
typically estimated numerically (e.g., Algeri and van Dyk, 2020). Notice that
the error rate in (24) decreases exponentially fast, as
$\alpha\rightarrow\infty$. Therefore, this solution is particularly amenable
to overcome the issues arising when dealing with stringent significance
requirements.

---
Figure 2: Simulated and approximated confidence regions for Example I. The left panel corresponds to the (post-selection) confidence regions and deviance p-value obtained via a simulation of size $B=10,000$. The right panel shows to the (post-selection adjusted) confidence regions and deviance p-value computed as in (21) and (22). Darker shades correspond to significant deviations of the estimated likelihood ratio above one. Lighter shades correspond to significant deviations below one.  | $n=500$ | $n=1000$ | n=2000 | $n=5000$ | $n=7000$ | $n=10,000$
---|---|---|---|---|---|---
Type I error | 0.0540 | 0.0500 | 0.0499 | 0.0482 | 0.0508 | 0.04930
($\pm$ SE) | ($\pm$ 0.0023) | ($\pm$ 0.0022) | ($\pm$ 0.0022) | ($\pm$ 0.0021) | ($\pm$ 0.0022) | ($\pm$ 0.0022)
Power | 0.2157 | 0.4456 | 0.8063 | 0.9995 | 1.0000 | 1.0000
($\pm$ SE) | ($\pm$ 0.0041) | ($\pm$ 0.0050) | ($\pm$ 0.0040) | ($\pm$ 0.0002) | ($\pm$ 0.0000) | ($\pm$ 0.0000)
Table 1: Simulated probability of type I error and power for Example I
considering different sample sizes. The nominal level is chosen to be
$\alpha=0.05$. Each simulation involves $B=10,000$ replicates.

As one may expect, the simplicity of the post-selection adjustments in (21)
and (22) comes with a price. Specifically, they can be rather conservative for
increasing values of $M$. However, as shown below for Example I and in the
sections to follow, (21) still leads to high power even if the sample size is
only moderately large. Similarly, (22) can be quite accurate and match closely
the confidence regions obtained by simulating directly the distribution of
(18), while repeating the selection process at each replicate.

_Example I (continued)._ The estimate of the likelihood ratio in the right
panel of Figure 1 has been obtained by setting $m_{1}=4$ and $m_{2}=3$ and
selecting the terms of the respective tensor basis via the AIC rule in (19).
The AIC procedure selects $9$ terms out of $M=19$. The post-selection adjusted
p-value and $95\%$ confidence regions are shown in the right panel of Figure
2. The confidence contours are constructed by setting equal to one all the
values of $\widehat{d}$ contained within the bands in (22). Whereas the
quantile $c_{\alpha}$ has been calculated by solving

$\bigl{(}1-\Phi(c_{\alpha/2})\bigl{)}+\mathcal{L}_{1}\frac{e^{-\frac{c_{\alpha/2}^{2}}{2}}}{\pi}+\mathcal{L}_{2}\frac{e^{-\frac{c_{\alpha/2}^{2}}{2}}}{\sqrt{2}\pi^{3/2}}-\frac{\alpha}{2}=0$
(25)

and estimating $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ by means of the R
package TOHM (Algeri, 2019) as described in Algeri and van Dyk (2020). This
approach led to $c_{\alpha}=3.5568$. The confidence contours suggest that the
most prominent deviations occur in correspondence of the regions
$[10,12]\times[0,5]$ and $[12,15]\times[12,17]$. Here, the estimator of
$d(\bm{u})$ shows significant deviations above one and thus we conclude that
the postulated model underestimates the truth over these areas. The presence
of significant departures of $G_{X_{1}X_{2}}$ from $F_{X_{1}X_{2}}$ are
confirmed by the deviance test (adjusted p-value $\sim 3.97\cdot 10^{-11}$).
The left panel of Figure 2 shows the confidence regions and deviance p-value
obtained by means of a Monte Carlo simulation involving $B=10,000$ replicates.
The selection procedure has been implemented at each replicate. While more
conservative, the confidence regions computed via (22) and (25), approximate
reasonably well those obtained via simulation.

Finally, we investigate the probability of type I error and the power of the
deviance test based on (21). Table 5 reports the results obtained considering
a suite of five simulations, each of size $B=10,000$, conducted using five
different sample sizes. For all $n$ considered, the probability of type I
error observed is approximately the same than the nominal level $\alpha=0.05$.
Whereas, the power increases rapidly with $n$. For the smallest samples sizes
considered, i.e., $n=500$ and $n=1000$, the power is rather low ($\sim 22\%$
and $\sim 45\%$, respectively). However, it has to be noted that, in our
example, the mixture parameter is $0.15$; therefore the deviations from the
postulated model effectively account for only $\sim 75$ and $\sim 150$ data
points when $n=500$ and $n=1000$, respectively.

In principle the plots in Figures 1, 2, and those to follow, could also be
visualized in the quantile domain. The latter is to be preferred when working
with long tailed distribution where one may expect that only a few
observations have been detected over large regions of the $\bm{X}$ domain. In
those situations, the quantile representation would allow to magnify the
differences observed over the the most “data-abundant” regions. An more
detailed discussion of this aspect, and adequate graphical comparisons can be
found in (Algeri, 2020).

##  5 iGOF-diagnostic analysis

The constructs introduced so far allow us to assess the validity of the
postulated model, obtain an estimate of the likelihood ratio test to visualize
where and how departures of $g$ from $f$ occur, and construct a data driven
correction for the initial model $g$ (equation 10). Unfortunately, however, a
visual inspection is only possible when $p\leq 3$. Nevertheless, when $p>3$,
more insights on the sources of mismodeling affecting $G$ can be obtained by
conducting an ANOVA-like analysis where random sub-vectors of $\bm{X}$ are
tested individually, from the largest to the smallest.

Without loss of generality, let $\bm{X}_{q}=(X_{1},\dots,X_{q})$ be the random
collecting the first $q<p$ components of $\bm{X}$. Denote with $F_{q}$ the
true cdf of $\bm{X}_{q}$ and let $G_{q}$ be its postulated cdf. Moreover,
assume that the density of $G_{q}$ can be specified as

$g_{q}\bigl{(}\bm{x}_{q}\bigl{)}=\prod_{d=1}^{q}g_{d}\bigl{(}x_{d}|\bm{x}_{<d}\bigl{)}\quad\text{for
all $d=1,\dots,q$.}$ (26)

Similarly to (2) and (4), we can then express the likelihood ratio of
$\bm{X}_{q}$ on the $q$ dimensional unit cube via

$d(\bm{u}_{q})=\frac{f_{q}\bigl{(}\bm{Q}_{q}(\bm{u}_{q})\bigl{)}}{g_{q}\bigl{(}\bm{Q}_{q}(\bm{u}_{q})\bigl{)}}=\sum_{j_{1}\geq
0,\dots,j_{q}\geq 0}\theta_{j_{1}\dots j_{q}}T_{j_{1}\dots
j_{q}}(\bm{u}_{q}),\quad\bm{u_{q}}\in[0,1]^{q}$ (27)

where
$\bm{u}_{q}=\bigl{(}G_{1}(x_{1}),\dots,G_{q}(x_{q}|\bm{x}_{<q})\bigl{)}$, and
thus $\bm{u}_{q}$ is a sub-vector of $\bm{u}=\bm{G}_{R}(\bm{x})$. Whereas,
similarly to (3), one can write the tensor basis functions $T_{j_{1}\dots
j_{q}}$ as

$T_{j_{1}\dots
j_{q}}(\bm{u}_{q})=\prod_{d=1}^{q}T_{j_{d}}(u_{d})=\prod_{d=1}^{p}T_{j_{d}}(u_{d})\quad\text{
with }j_{d}=0,\text{ for all }d=q+1.$ (28)

The last equality follows from the fact that
$T_{0}\bigl{(}G(x_{d}|\bm{x}_{<d})\bigl{)}=1$ for all $d=1,\dots,p$, and thus
each $T_{j_{1}\dots j_{q}}(\bm{u}_{q})=T_{j_{1}\dots j_{q}0\dots 0}(\bm{u})$.
Consequently, the $\theta_{j_{1}\dots j_{q}}$ coefficients are equal to the
theta $\theta_{j_{1}\dots j_{p}}$ whenever $j_{d}=0$, for all $d=q+1$. As a
result, we can easily perform inference for $\bm{X}_{q}$ by means of the
estimators $\widehat{\theta}_{k}$ in (6), without the need of an entirely new
estimation procedure.

Specifically, denote with $\mathcal{K}_{q}$ and $\mathcal{K}^{*}$ the subsets
of $\mathcal{K}$ in (5)

$\displaystyle\mathcal{K}_{q}$ $\displaystyle:=\biggl{\\{}k=\\{j_{1}\dots
j_{p}\\}\in\mathcal{K}\text{ with }j_{d}=0,\text{ for all
}d=q+1,\dots,p\biggl{\\}}$ (29) $\displaystyle\mathcal{K}^{*}$
$\displaystyle:=\biggl{\\{}k=\\{j_{1}\dots j_{p}\\}\in\mathcal{K}\text{ with
}(k)\leq K^{*}\biggl{\\}}$ (30)

of cardinality $|\mathcal{K}_{q}|=M_{q}=\prod_{d=1}^{q}(m_{d}+1)-1$ and
$|\mathcal{K}^{*}|=K^{*}$. Recall that $K^{*}$ is the value minimizing either
the AIC or BIC in (19), and thus, $\mathcal{K}^{*}$ collects all the $p-$tuple
of indexes in $\mathcal{K}$ which have been ultimately selected when
constructing the estimator $\widehat{d}_{(K^{*})}$ and the deviance statistics
$D_{(K^{*})}$ in Corollaries 4.3 and 4.4. To test

$H_{0}:G_{q}=F_{q}\quad\text{versus}\quad H_{1}:G_{q}\neq F_{q}$ (31)

we may consider the test statistics
$D_{q}=n\sum_{k\in\mathcal{K}_{q}}\widehat{\theta}^{2}_{k}$ and proceed as in
Theorem 4.1. Whereas, valid post-selection inference can be obtained as in
Theorem 5.1.

######  Theorem 5.1.

As $n\rightarrow\infty$, a valid post-selection bound for the p-value to test
(31) is

$\text{p-value}_{q,adj}=P(\chi^{2}_{M_{q}}>D_{obs}),$ (32)

where $D_{obs}$ being the value of the test statistics

$D^{*}_{q}=n\sum_{k\in\mathcal{K}_{q}\cap\mathcal{K}^{*}}\widehat{\theta}^{2}_{k}$
(33)

observed, $\mathcal{K}_{q}$ and $\mathcal{K}^{*}$ as in (29) and (30) and
$\widehat{\theta}_{k}$ as in (6).

Theorem 5.1 follows directly from (27) and (28) and, in virtue of the
orthogonality of the $T_{k}$ functions and condition (26).

######  Remark 5.2.

Because of condition (26), Theorem 5.1 holds only for random sub-vectors of
$\bm{X}$ whose Rosenblatt transform $u_{q}$ includes all the conditioning,
from the higher to the lower, necessary to recover
$g_{q}\bigl{(}\bm{x}_{q}\bigl{)}$. To some extent, this condition can be seen
as the iGOF counterpart of the marginality principle advocated by Nelder
(1977) in the context of ANOVA, and which consists in taking into account of
the hierarchy of the main effects and interactions in a given model.

Similarly to the ANOVA, Theorem 5.1 allows us to construct an iGOF-diagnostic
table to identify the source of mismodeling for a given random vector $\bm{X}$
and its components. Below we show how this can be done in practice for the
case of a $7$-dimensional random vector.

_Example II._ We consider a sample of $n=5000$ observations from a random
vector $\bm{X}=(X_{1},\dots,X_{7})$ with components distributed as summarized
in the second column of Table 2. Table 3 collects the results obtained by
applying Theorem 5.1 to test the validity of the models specified for
different sub-vectors of $\bm{X}$. The overall deviance test is reported in
the first row and correctly reject the null model.

Variable |  True ($F$) |  Hypothesized ($G$) | Correct
---|---|---|---
$X_{6}|X_{1},X_{2},X_{5}$ | Laplace$\Bigl{[}e^{0.03x_{1}+0.02x_{2}+0.01x_{2}^{2}+0.02x_{5}},1\Bigl{]}$ | Laplace$\Big{[}e^{0.03x_{1}+0.02x_{2}+0.02x_{5}},1\Bigl{]}$ | No
$X_{1},X_{2},X_{5}$ | $N\left[\left(\begin{array}[]{c}10\\\ 15\\\ 11\end{array}\right),\left(\begin{array}[]{ccc}4&0.5&0\\\ 0.5&3&1\\\ 0&1&5\end{array}\right)\right]$ | $N\left[\left(\begin{array}[]{c}10\\\ 15\\\ 11\end{array}\right),\left(\begin{array}[]{ccc}4&0.5&0\\\ 0.5&3&1\\\ 0&1&5\end{array}\right)\right]$ | Yes
$X_{4}|X_{3}$ | Exponential$\Bigl{(}\frac{1}{x_{3}}\Bigl{)}$ | Exponential$\Bigl{(}\frac{1}{x_{3}}\Bigl{)}$ | Yes
$X_{3}$ | Exponential$(1)$ | Exponential$(0.9)$ | No
$X_{7}$ | $T_{3}$ | Cauchy$(0,1)$ | No
Table 2: True and postulated model for Example II. The last column highlights
where mismodeling occurs.

Similarly, the test in the second row, rejects the hypotheses that the vector
$(X_{1},X_{2},X_{5},X_{6})$ is modelled correctly, and fails to rejects the
model for $(X_{1},X_{2},X_{5})$. This aspect is particularly important as it
highlights that the mismodeling occurs only with respect to the conditional
distribution of $X_{6}|X_{1},X_{2},X_{5}$. The tests in the fourth and fifth
row show that the vector $(X_{3},X_{4})$ has been mismodeled and one source of
mismodeling is the marginal of $X_{3}$. Ultimately, the test for $X_{7}$ also
correctly rejects the null hypothesis of Cauchy distribution. Table 4 collects
the results of a simulation obtained by repeating the diagnostic analysis in
Table 3 through a simulation of $B=10,000$ replicates, while considering
different sample sizes. Even when the sample size considered is only $500$,
the most prominent deviations are captured with probability one, whereas, the
model for $(X_{1},X_{2},X_{5})$ is never rejected. More issues arise in
diagnosing mismodeling of $X_{3}$ and, consequently, $(X_{3},X_{4})$ for
smaller samples. For instance, even when $n=1000$ the power of the procedure
in detecting departures of $G_{X_{3}}$ from $F_{X_{3}}$ is only $\sim 56\%$
and $\sim 3\%$ for $(X_{3},X_{4})$. It has to be noted, however, that
detecting mismodeling of $X_{3}$ is a particularly challenging task. As shown
in Figure 3, the postulated and the true pdf of $X_{3}$ are very close one-
another; this minor differences are further “diluted” when considering the
joint distribution of $(X_{3},X_{4})$, since $X_{4}|X_{3}$ is correctly
specified. Nevertheless, such minor deviations are detected with high power
for larger sample sizes.

$\bm{X}_{q}$ | df | (Adjusted)
---|---|---
|  | p-value
$\bm{X}$ | 16383 | $<10^{-130}$
$(X_{1},X_{2},X_{5},X_{6})$ | 256 | $<10^{-130}$
$(X_{1},X_{2},X_{5})$ | 63 | $1$
$(X_{3},X_{4})$ | 15 | $8.467\cdot 10^{-08}$
$X_{3}$ | 3 | $1.525\cdot 10^{-13}$
$X_{7}$ | 3 | $2.599\cdot 10^{-122}$

Table 3: iGOF-diagnostic table. The third column reports the (post-selection
adjusted) deviance p-values in (32) with $\bm{X}_{q}$ specified as in the
first column. The second column corresponds to the degrees of freedom used in
the calculation of the p-value, namely, $M_{q}$.

Figure 3: Comparing the postulated (red dashed line) and the true model (green
solid line) of $X_{3}$.

$\bm{X}_{q}$ | Sample size ($n$)
---|---
| $500$ | $1000$ | $2000$ | $3000$ | $5000$ | $10,000$
$\bm{X}$ | 1 | 1 | 1 | 1 | 1 | 1
$(X_{1},X_{2},X_{5},X_{6})$ | 1 | 1 | 1 | 1 | 1 | 1
$(X_{1},X_{2},X_{5})$ | 0 | 0 | 0 | 0 | 0 | 0
$(X_{3},X_{4})$ | 0.0069 | 0.0342 | 0.2384 | 0.5939 | 0.9615 | 1
| ($\pm$0.0008) | ($\pm$0.0018) | ($\pm$0.0049) | ($\pm$0.0049) | ($\pm$ 0.0019) |
$X_{3}$ | 0.2360 | 0.5560 | 0.9153 | 0.9868 | 0.9999 | 1
| ($\pm$0.0043) | ($\pm$0.0050) | ($\pm$0.0028) | ($\pm$0.0011) | ($\pm$ 0.0001) |
$X_{7}$ | 1 | 1 | 1 | 1 | 1 | 1
Table 4: Performance of the iGOF-diagnostic analysis for different sample
sizes. For values different from zero and one the Monte Carlo errors $(\pm
SE)$ are also reported. The significance level considered is $\alpha=0.05$.
---
Figure 4: Simulated and approximated confidence regions for the Fermi LAT
simulation. The left panel corresponds to the (post-selection) confidence
regions and deviance p-value obtained via a simulation of size $B=10,000$. The
right panel shows to the (post-selection adjusted) confidence regions and
deviance p-value computed as in (21) and (22). Darker shades correspond to
significant deviations of the estimated likelihood ratio above one. Lighter
shades correspond to significant deviations below one.

##  6 A diagnosis of background mismodeling

When conducting searches for new phenomena, mismodeling of the background
distribution can dramatically compromise the sensitivity of the experiment.
Specifically, overestimating the background can increase the chances of false
negatives. Whereas, underestimating the background may lead to claiming false
discoveries. To illustrate how iGOF can be used to understand if and how the
postulated background model have been misspecified, we consider a simulated
observation by the Fermi Large Area Telescope (LAT) Atwood et al. (2009)
obtained with the _gtobssim_
package222http://fermi.gsfc.nasa.gov/ssc/data/analysis/software and previously
published in Algeri and van Dyk (2020). The simulation includes a realistic
representations of the instrumental noise of the detector and present
backgrounds.

The region of interest corresponds to a disc in the sky of $30^{\circ}$ radius
and centered at ($195$ RA, $28$ DEC), where RA and DEC are the coordinates in
the sky. Here we assume that, despite the cosmic background is known to follow
a uniform distribution over the search area, it is unclear if the instrumental
error is effectively negligible, or if it has a prominent effect on the
underlying distribution. Therefore, we set $G_{X_{1}X_{2}}$ to be the cdf of a
uniform distribution with support
$\mathcal{X}_{1}\times\mathcal{X}_{2}=[165,195]\times[28-\sqrt{30^{2}-(x-195)^{2}},28+\sqrt{30^{2}-(x-195)^{2}}]$
and we proceed by estimating the likelihood ratio via (9) over a sample of
$n=68658$ observations. Specifically, we set $m_{1}=m_{2}=4$ and we select the
components of $\widehat{\bm{\theta}}$ via the BIC criterion in (19). The
resulting estimate is

$\widehat{d}\bigl{(}G_{1}(x_{1}),G_{2}(x_{2}|x_{1})\bigl{)}=1+0.022T_{1}\bigl{(}G_{1}(x_{1})\bigl{)}-0.043T_{1}\bigl{(}G_{2}(x_{2}|x_{1})\bigl{)}+0.041T_{2}\bigl{(}G_{2}(x_{2}|x_{1})\bigl{)}.$
(34)

In order to assess the significance of the deviations captured by (34), we
compute both the confidence regions and deviance p-values via (22) and (21).
The results are reported in the right panel of Figure 4, whereas the left
panel shows the confidence regions and deviance p-value obtained via
simulation. Similarly to what we have observed for Example I (see Figure 2),
despite the approximate confidence bands are more conservative, they still
allow to capture the main departures from uniformity. Indeed, in both cases,
we can see that the prominent deviations of the true underlying model from the
postulated uniform distribution occur in proximity of low values of $X_{2}$.
Whereas, at the center-left of the search area, the uniform model
significantly underestimates the model inclusive of the instrumental error.
Finally, it follows from (10) that an updated model background distribution
which accounts for these deviations can be constructed as in (10) by simply
multiplying the uniform pdf by the estimated likelihood ratio in (34).

##  7 Extensions to the discrete case

The methods discussed so far focus on the case where $F$ and $G$ are
continuous. However, extensions to the discrete setting can be derived by
rewriting the expansion in (4) through an orthonormal set of functions
suitable to model discrete data. This can be done, for instance, by means of
the so-called “LP333In the _LP_ acronym, the letter _L_ typically denotes
nonparametric methods based on quantiles, whereas _P_ stands for polynomials
(Mukhopadhyay and Wang, 2020, Supp S1). score functions”, recently introduced
(e.g., Mukhopadhyay and Wang, 2020) and which can be seen as a generalization
of the Legendre polynomials valid in both the continuous and discrete setting.

Specifically, when $p=1$, a complete orthonormal basis of LP score functions
in $L^{2}(G)$ can be specified by letting the first component to be
$T_{0}\bigl{[}G(x)\bigl{]}=1$. Subsequent components
$\\{T_{j}\bigl{[}G(x)\bigl{]}\\}_{j>0}$ are obtained by Gram-Schimidt
orthonormalization of powers of

$T_{1}\bigl{[}G(x)\bigl{]}=\frac{G_{\text{mid}}(x)-E[G_{\text{mid}}(x)]}{\sqrt{V(G_{\text{mid}}(x))}}=\frac{G(x)-0.5p_{G}(x)-0.5}{\sqrt{[1-\sum_{x\in\mathcal{X}}p_{G}^{3}(x)]/12}},$
(35)

where $G_{\text{mid}}(x)=G(x)-0.5p_{G}(x)$ is the _mid-distribution function_
, which it has been shown in Parzen (2004) to have mean $0.5$ and variance
$[1-\sum_{x\in\mathcal{X}}p_{G}^{3}(x)]/12$, with $\mathcal{X}$ being the set
of distinct points in the support of $X$ and $p_{G}(x)=P(X=x)$ if $X\sim G$.
Therefore, $T_{1}\bigl{[}G(x)\bigl{]}$ is the standardized mid-distribution
and orthonormality of the $T_{j}\bigl{[}G(x)]$ functions in $L^{2}(G)$ follows
by the first equality in (35) and by Gram-Schmidt process.

Notice that, for continuous $X$, $G_{\text{mid}}(x)=G(x)$ and
$\sum_{x\in\mathcal{X}}p_{G}^{3}(x)=0$, consequently, the LP score functions
reduce to normalized shifted Legendre polynomials. The latter are effectively
the result of a Gram-Schmidt orthonormalization applied to powers of $G(x)$.
Whereas, the LP score functions are obtained by orthonormalizing powers of the
standardized mid-distribution function with respect to the measure $G$.

Recall that, in our context, the cdfs $G_{d}$, $d=1,\dots,p$ are the
conditional and marginal distribution functions specified in the Rosenblatt’s
transform $\bm{G}_{R}(\bm{x})$. Hence, an orthonormal basis in
$L^{2}\bigl{(}G_{d})$ is
$\Bigl{\\{}T_{j_{d}}\bigl{[}G_{d}(\cdot|\cdot)\bigl{]}\Bigl{\\}}_{j_{d}\geq
0}$ with $T_{0}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}=1$ and subsequent
components

$\displaystyle\quad T_{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}$
$\displaystyle=\frac{\text{\r{T}}_{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}}{\bigl{|}\bigl{|}\text{\r{T}}_{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}\bigl{|}\bigl{|}_{G_{d}}},\quad\text{for
all $j_{p}\geq 1$, where}$ (36)
$\displaystyle\text{\r{T}}_{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}$
$\displaystyle=T^{j_{d}}_{1}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}$ (37)
$\displaystyle-\sum_{k=1}^{{j_{p}}-1}\bigl{<}T^{{j_{d}}}_{1}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]},T_{k}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}\bigl{>}_{G_{d}}T_{k}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]},$
(38)
$\displaystyle\bigl{<}T_{1}^{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]},$
$\displaystyle
T_{k_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}\bigl{>}_{G_{d}}=$ (39)
$\displaystyle\int
T_{1}^{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}T_{k_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}\text{d}G_{d}(x_{d}|\bm{x}_{<d})$
(40)

and $||\cdot||_{G_{d}}=\sqrt{<\cdot,\cdot>_{G_{d}}}$.

When $p>1$ a suitable tensor basis in $L^{2}(G)$ can then be constructed as in
Proposition 3. $\\{T_{j_{1},\dots,j_{p}}(\bm{u})\\}_{j_{1}\dots j_{p}\geq 0}$.
Orthonormality of the $T_{j_{1},\dots,j_{p}}(\bm{u})$ score functions can be
verified directly as shown in Section LABEL:LPbasis of the Supplementary
Material.

##  8 Discussion

This work proposes an informative approach to goodness-of-fit which connects
exploratory and confirmatory data analysis to study multivariate
distributions. By transforming the likelihood ratio on the unit cube,
confidence regions can be constructed as in Corollary 4.4 to identify regions
of the supportwhere significant deviations occurs. While this approach is
practical only for problems in at most three dimensions, in more dimensions a
detailed diagnosis of mismodeling can be achieved by means of the iGOF-
diagnostic analysis proposed in Section 5. These tools can be used to directly
address Q1 in Section 1. For instance, given the panacea of theories available
on the nature of dark matter, experimentalists aiming to detect it often face
the dilemma of selecting which of the tens of theoretical models (mainly non-
nested) available should be tested (e.g., Scott, 2018). If one was to test it
using the procedure discussed in this paper, even when a given model is
rejected, it is possible to gain further insight on the shape of the departure
of the true data distribution and the null model and ultimately use such
information to “rule out” other models which would be inconsistent with such
deviation.

Moreover, as we aimed for when formulating Q2 in Section 1, the true
probability function of the data can be estimated semi-parametrically via
(10), while assessing the validity of the model postulated by the scientists.
Interestingly, the resulting estimate incorporates the knowledge carried by
the hypothesized model and thus, it provides a data-driven update for it in
the direction of the true distribution of the data.

Despite the usefulness of the methods presented here in applied settings, and
in the physical sciences in particular (e.g., Section 6), they are not exempt
from limitations. For instance, several problems in physics and astronomy,
often involve no more than 8 or 10 dimensions and/or can be reduced to 2D
planes (e.g., Aprile et al., 2017). In this context, choosing $m_{d}$ equal to
$3$ or $4$ for all $d=1,\dots,p$, is often sufficient to avoid overfitting
and, eventually, lack of power by implementing adequate model selection
strategies and for sufficiently large samples (see Sections 4 and 5). In more
dimensions, however, the method suffers from the curse of dimensionality (e.g.
Friedman et al., 2001), as the size of the LP tensor basis increases
exponentially fast with $p$. In this context, a regularized solution could be
particularly valuable (see for instance Signoretto et al., 2014) when
analyzing, for instance, data coming from large astronomical surveys such as
the Large Synoptic Survey Telescope (LSST) survey (e.g., Tyson, 2002).

Furthermore, the unitary representation of the likelihood ratio in (2) relies
on the Rosenblatt transform and which can lead to different configurations of
$\bm{U}$ and, potentially, different estimators. Despite this aspect would
require adequate treatment on its own, it is worth noting that this problem is
essentially the same arising in the context of vine copulas (e.g., Nagler et
al., 2017) and for which adequate model selection procedures exists (e.g.,
Panagiotelis et al., 2017; Dissmann et al., 2013).

Finally, the inferential procedures presented here extend classical smooth
tests to the multivariate setting and allow us to visualize graphically the
departure of $F$ from $G$ and study their substructures. Despite this article
focuses on simple null hypothesis, that is, the postulated model is assumed to
be fully specified, classical results on smooth tests (e.g., Thas, 2010, Sec
4.2.2.3 and 5.2.2.3 ) can be used to show to derive asymptotic tests in the
parametric setting. Unfortunately, however, the asymptotic approximations are
known to be rather slow in the parametric case. Therefore, in practical
applications, when $G$ depends on unknown parameters it is recommended to
perform inference by means of the parametric bootstrap and which has been
shown by Babu and Rao (2004) to be consistent also in the multivariate
setting.

Appendix

Symbol | Description
---|---
$\bm{X}=(X_{1},\dots,X_{p})$ | Random vector of components
| $X_{d},d=1,\dots,p$
$\mathcal{X}$ | Support of $\bm{X}$
$F,f$ | True cdf and density of $\bm{X}$
$G,g$ | Postulated cdf and density of $\bm{X}$
$G_{d},Q_{d},g_{d}$ | Conditional cdf, quantile
| function and density of $X_{d}$
$\bm{U}=\bm{G}_{R}(\bm{X})$ | Rosenblatt’s transform of $\bm{X}$
$\bm{Q}(\bm{X})=\bm{U}$ | Inverse of the Rosenblatt’s
| transform
$\bm{x}=(x_{1},\dots,x_{p})=\bm{Q}(\bm{u})$ | Realization of $\bm{X}$
| with components $x_{d}=Q_{d}(u_{d})$
$\bm{u}=(u_{1},\dots,u_{p})=\bm{G}_{R}(\bm{x})$ | Realization of $\bm{U}$, with
| components $u_{d}=G_{d}(x_{d}|\bm{x}_{<d})$
$\bm{x}_{<d}=(x_{1},\dots,x_{d-1})$ | First $d-1$ components of $\bm{x}$
$\bm{u}_{<d}=(u_{1},\dots,u_{d-1})$ | First $d-1$ components of $\bm{u}$
$d(\bm{u}),\widehat{d}(\bm{u})$ | Likelihood ratio and its estimate
$T_{j_{d}}\bigl{[}G_{d}(x_{d}|\bm{x}_{<d})\bigl{]}=T_{j_{d}}(u_{d})$ |  $j_{d}^{th}$ normalized shifted Legendre
| polynomial in $L^{2}(G_{d})$ and $[0,1]$
$T_{k}\bigl{[}\bm{G}_{R}(\bm{x})\bigl{]}=T_{k}(\bm{u})$ | Tensor product of $T_{j_{d}}$ functions
| with $k\in\mathcal{K}$, in $L^{2}(G)$ and $[0,1]^{p}$
$\mathcal{K}$ | sets of $p-$tuple $\\{j_{1}\dots j_{p}\\}$,
|  $\sum_{d}j_{d}\neq 0$, $j_{d}=0,\dots,m_{d}$
$|\mathcal{K}|=M$ | Cardinality of $\mathcal{K}$
$\bm{T}(\bm{u})=\bm{T}\bigl{[}\bm{G}_{R}(\bm{x})\bigl{]}$ |  $M\times 1$ vector of components
| $T_{k}(\bm{u})=T_{k}\bigl{[}\bm{G}_{R}(\bm{x})\bigl{]}$
$\bm{\theta}$ |  $M\times 1$ vector collecting the
| coefficients $\theta_{k}$
$\widehat{\bm{\theta}}$ |  $M\times 1$ vector collecting the
| estimates $\widehat{\theta}_{k}$
$D$ | Deviance statistics
Table 5: A summary of the main notation used throughout the paper.

## Supplementary Material

The folder _Codes_and_data_ collects the data used in Section 6 and the codes
used for the analyses in Figures 1, 2, and 4. The interested reader is
directed to the supplementary file _Codes_description.pdf_ for a more detailed
description of all the codes and files available. The file
_Supplement_iGOF.pdf_ collects the technical proofs and additional results
related to Example I.

## Acknowledgments

The author thanks sincerely Estate V. Khmaladze, G. Jogesh Babu and two
anonymous referees for the useful discussions and comments. Their valuable
feedback has led to a substantial improvement of the quality and clarity of
the manuscript.

## References

  * Adler (2000) Adler, R. J. (2000).  On excursion sets, tube formulas and maxima of random fields.  Annals of Applied Probability, pages 1–74.
  * Algeri (2019) Algeri, S. (2019).  TOHM: Testing One Hypothesis Multiple Times.  R package version 1.3.
  * Algeri (2020) Algeri, S. (2020).  Detecting new signals under background mismodeling.  Phys. Rev. D, 101:015003.
  * Algeri et al. (2018) Algeri, S. et al. (2018).  Statistical challenges in the search for dark matter.  arXiv:1807.09273.
  * Algeri and van Dyk (2020) Algeri, S. and van Dyk, D. A. (2020).  Testing one hypothesis multiple times: the multidimensional case.  Journal of Computational and Graphical Statistics, 29(2):358–371.
  * Algeri and Zhang (2020) Algeri, S. and Zhang, X. (2020).  Exhaustive goodness-of-fit via smoothed inference and graphics.  arXiv preprint arXiv:2005.13011.
  * Aprile et al. (2017) Aprile, E., Aalbers, J., Agostini, F., Alfonsi, M., Amaro, F., Anthony, M., Arneodo, F., Barrow, P., Baudis, L., Bauermeister, B., et al. (2017).  First dark matter search results from the xenon1t experiment.  Physical review letters, 119(18):181301.
  * Atwood et al. (2009) Atwood et al., W. B. (2009).  The large area telescope on the fermi gamma-ray space telescope mission.  The Astrophysical Journal, 697(2):1071.
  * Babu and Rao (2004) Babu, G. J. and Rao, C. R. (2004).  Goodness-of-fit tests when parameters are estimated.  Sankhya, 66(1):63–74.
  * Balázs et al. (2017) Balázs, C. et al. (2017).  Colliderbit: a gambit module for the calculation of high-energy collider observables and likelihoods.  The European Physical Journal C, 77(11):795.
  * Barton (1953) Barton, D. E. (1953).  On neyman’s smooth test of goodness of fit and its power with respect to a particular system of alternatives.  Scandinavian Actuarial Journal, 1953(sup1):24–63.
  * Berk et al. (2013) Berk, R., Brown, L., Buja, A., Zhang, K., Zhao, L., et al. (2013).  Valid post-selection inference.  The Annals of Statistics, 41(2):802–837.
  * Dauncey et al. (2015) Dauncey, P., Kenzie, M., Wardle, N., and Davies, G. (2015).  Handling uncertainties in background shapes: the discrete profiling method.  Journal of Instrumentation, 10(04):P04015.
  * Dissmann et al. (2013) Dissmann, J., Brechmann, E. C., Czado, C., and Kurowicka, D. (2013).  Selecting and estimating regular vine copulae and application to financial returns.  Computational Statistics & Data Analysis, 59:52–69.
  * Friedman et al. (2001) Friedman, J., Hastie, T., and Tibshirani, R. (2001).  The elements of statistical learning, volume 1.  Springer series in statistics New York.
  * Ledwina (1994) Ledwina, T. (1994).  Data-driven version of neyman’s smooth test of fit.  Journal of the American Statistical Association, 89(427):1000–1005.
  * Lyons (2013) Lyons, L. (2013).  Discovering the Significance of 5 sigma.  arXiv:1310.1284.
  * Mukhopadhyay (2017) Mukhopadhyay, S. (2017).  Large-scale mode identification and data-driven sciences.  Electronic Journal of Statistics, 11(1):215–240.
  * Mukhopadhyay and Wang (2020) Mukhopadhyay, S. and Wang, K. (2020).  Nonparametric high-dimensional k-sample comparison.  Biometrika (to appear).
  * Nagler et al. (2017) Nagler, T., Schellhase, C., and Czado, C. (2017).  Nonparametric estimation of simplified vine copula models: comparison of methods.  Dependence Modeling, 5(1):99–120.
  * Nelder (1977) Nelder, J. (1977).  A reformulation of linear models.  Journal of the Royal Statistical Society: Series A (General), 140(1):48–63.
  * Nelsen (2007) Nelsen, R. B. (2007).  An introduction to copulas.  Springer Science & Business Media.
  * Neyman (1937) Neyman, J. (1937).  Smooth test for goodness of fit.  Scandinavian Actuarial Journal, 1937(3-4):149–199.
  * Panagiotelis et al. (2017) Panagiotelis, A., Czado, C., Joe, H., and Stöber, J. (2017).  Model selection for discrete regular vine copulas.  Computational Statistics & Data Analysis, 106:138–152.
  * Parzen (2004) Parzen, E. (2004).  Quantile probability and statistical data modeling.  Statistical Science, 19(4):652–662.
  * Pearson (1938) Pearson, E. S. (1938).  The probability integral transformation for testing goodness of fit and combining independent tests of significance.  Biometrika, 30(1/2):134–148.
  * Priel et al. (2017) Priel, N., Rauch, L., Landsman, H., Manfredini, A., and Budnik, R. (2017).  A model independent safeguard against background mismodeling for statistical inference.  Journal of Cosmology and Astroparticle Physics, 2017(05):013.
  * Rayner and Best (1990) Rayner, J. C. W. and Best, D. J. (1990).  Smooth tests of goodness of fit: an overview.  International Statistical Review/Revue Internationale de Statistique, pages 9–17.
  * Reed and Simon (1980) Reed, M. and Simon, B. (1980).  Methods of modern mathematical physics i: functional analysis.
  * Rosenblatt (1952) Rosenblatt, M. (1952).  Remarks on a multivariate transformation.  The annals of mathematical statistics, 23(3):470–472.
  * Scott (2018) Scott, P. (2018).  Dark matter model comparison.  BIRS Workshop on Dark matter model comparison, DM-Stat: Statistical Challenges in the Search for Dark Matter.
  * Signoretto et al. (2014) Signoretto, M., Dinh, Q. T., De Lathauwer, L., and Suykens, J. A. (2014).  Learning with tensors: a framework based on convex optimization and spectral regularization.  Machine Learning, 94(3):303–351.
  * Taylor et al. (2005) Taylor, J., Takemura, A., Adler, R. J., et al. (2005).  Validity of the expected euler characteristic heuristic.  The Annals of Probability, 33(4):1362–1396.
  * Taylor and Worsley (2008) Taylor, J. E. and Worsley, K. J. (2008).  Random fields of multivariate test statistics, with applications to shape analysis.  Ann. Statist., 36(1):1–27.
  * Thas (2010) Thas, O. (2010).  Comparing distributions.  Springer.
  * Tyson (2002) Tyson, J. A. (2002).  Large synoptic survey telescope: overview.  In Survey and Other Telescope Technologies and Discoveries, volume 4836, pages 10–20. International Society for Optics and Photonics.
  * Westerdale (2016) Westerdale, S. (2016).  A study of nuclear recoil backgrounds in dark matter detectors.  PhD thesis, Princeton University.


is trivial if $T_{1}+T_{2}$ is compact. Otherwise, for each
$\varepsilon\in(0,1)$, we can find operators $U\in\mathscr{B}(C_{0}(K),c_{0})$
and $V\in\mathscr{B}(c_{0},C_{0}(K))$ such that

$I_{c_{0}}-U(T_{1}+T_{2})V\in\mathscr{K}(c_{0})$ (7.9)

and

$\frac{1}{\lVert U\rVert\,\lVert
V\rVert}\geqslant(1-\varepsilon)\nu(T_{1}+T_{2}+\mathscr{K}(C_{0}(K))).$

Set $R_{i}=UT_{i}V\in\mathscr{B}(c_{0})$ for $i=1,2$. By (7.9), at least one
of these operators is non-compact, say $R_{1}$ (relabelling them if
necessary). Therefore we can apply Corollary 7.6 to find a constant
$\xi_{1}>0$ and a closed subspace $W_{1}$ of $c_{0}$ such that $W_{1}$ is
isomorphic to $c_{0}$,

$(1+\varepsilon)\xi_{1}\lVert w\rVert\geqslant\lVert
R_{1}w\rVert\geqslant(1-\varepsilon)\xi_{1}\lVert w\rVert\qquad(w\in W_{1})$
(7.10)

and $I_{c_{0}}=U_{1}R_{1}V_{1}$ for some operators
$U_{1},V_{1}\in\mathscr{B}(c_{0})$ with $\lVert U_{1}\rVert\,\lVert
V_{1}\rVert\leqslant\frac{(1+\varepsilon)^{2}}{(1-\varepsilon)\xi_{1}}$.

Now we split in two cases, beginning with the case where the restriction of
$R_{2}$ to $W_{1}$ is non-compact. Since $W_{1}$ is isomorphic to $c_{0}$, we
can apply Corollary 7.6 once more, this time to the operator $R_{2}|_{W_{1}}$,
to find a constant $\xi_{2}>0$ and a closed, infinite-dimensional subspace
$W_{2}$ of $W_{1}$ such that

$(1+\varepsilon)\xi_{2}\lVert w\rVert\geqslant\lVert
R_{2}w\rVert\geqslant(1-\varepsilon)\xi_{2}\lVert w\rVert\qquad(w\in W_{2})$
(7.11)

and $I_{c_{0}}=U_{2}R_{2}V_{2}$ for some operators
$U_{2},V_{2}\in\mathscr{B}(c_{0})$ with $\lVert U_{2}\rVert\,\lVert
V_{2}\rVert\leqslant\frac{(1+\varepsilon)^{2}}{(1-\varepsilon)\xi_{2}}$.

Then, for $i\in\\{1,2\\}$, we have
$I_{c_{0}}=U_{i}R_{i}V_{i}=(U_{i}U)T_{i}(VV_{i})$, so

$\displaystyle\nu(T_{i}+\mathscr{K}(C_{0}(K)))$
$\displaystyle\geqslant\frac{1}{\lVert U_{i}\rVert\,\lVert U\rVert\,\lVert
V\rVert\,\lVert
V_{i}\rVert}\geqslant\frac{(1-\varepsilon)^{2}\xi_{i}}{(1+\varepsilon)^{2}}\nu(T_{1}+T_{2}+\mathscr{K}(C_{0}(K))).$
(7.12)

The left-hand inequalities in (7.10)–(7.11) and the fact that $W_{2}\subseteq
W_{1}$ imply that

$(1+\varepsilon)(\xi_{1}+\xi_{2})\geqslant\lVert(R_{1}+R_{2})|_{W_{2}}\rVert\geqslant\lVert(R_{1}+R_{2})|_{W_{2}}\rVert_{e}=\lVert
I_{c_{0}}|_{W_{2}}\rVert_{e}=1,$ (7.13)

where the penultimate equality follows from (7.9). Adding up the estimates
(7.12) for $i=1$ and $i=2$ and substituting the lower bound on
$\xi_{1}+\xi_{2}$ from (7.13) into this sum, we obtain

$\nu(T_{1}+\mathscr{K}(C_{0}(K)))+\nu(T_{2}+\mathscr{K}(C_{0}(K)))\geqslant\frac{(1-\varepsilon)^{2}}{(1+\varepsilon)^{3}}\nu(T_{1}+T_{2}+\mathscr{K}(C_{0}(K))).$
(7.14)

We claim that this inequality also holds true in the case where
$R_{2}|_{W_{1}}$ is compact. Indeed, the estimate (7.12) remains valid for
$i=1$, while we can modify (7.13) in the following way:

$(1+\varepsilon)\xi_{1}\geqslant\lVert R_{1}|_{W_{1}}\rVert\geqslant\lVert
R_{1}|_{W_{1}}\rVert_{e}=\lVert(R_{1}+R_{2})|_{W_{1}}\rVert_{e}=\lVert
I_{c_{0}}|_{W_{1}}\rVert_{e}=1.$

Now (7.14) follows by using the trivial lower bound $0$ on
$\nu(T_{2}+\mathscr{K}(C_{0}(K)))$.

Since (7.14) holds true for arbitrary $\varepsilon\in(0,1)$, we conclude that
$\nu$ is subadditive.

Submultiplicativity. The inequality

$\nu(T_{2}T_{1}+\mathscr{K}(C_{0}(K)))\leqslant\nu(T_{2}+\mathscr{K}(C_{0}(K)))\nu(T_{1}+\mathscr{K}(C_{0}(K)))$

is trivial if $T_{2}T_{1}$ is compact. Otherwise, for each
$\varepsilon\in(0,1)$, we can find operators $U\in\mathscr{B}(C_{0}(K),c_{0})$
and $V\in\mathscr{B}(c_{0},C_{0}(K))$ such that

$I_{c_{0}}-UT_{2}T_{1}V\in\mathscr{K}(c_{0})\qquad\text{and}\qquad\frac{1}{\lVert
U\rVert\,\lVert
V\rVert}\geqslant(1-\varepsilon)\nu(T_{2}T_{1}+\mathscr{K}(C_{0}(K))).$ (7.15)

Applying Corollary 7.6 and Lemma 7.8 twice, we obtain constants
$\xi_{1},\xi_{2}>0$, closed subspaces $W_{1}\subseteq V[c_{0}]$ and
$W_{2}\subseteq T_{1}[W_{1}]$ and operators
$U_{1},U_{2}\in\mathscr{B}(C_{0}(K),c_{0})$ and
$V_{1},V_{2}\in\mathscr{B}(c_{0},C_{0}(K))$ such that $T_{1}[W_{1}]$ and
$T_{2}[W_{2}]$ are isomorphic to $c_{0}$ and

$(1+\varepsilon)\xi_{i}\lVert w\rVert\geqslant\lVert
T_{i}w\rVert\geqslant(1-\varepsilon)\xi_{i}\lVert w\rVert,\quad
U_{i}T_{i}V_{i}=I_{c_{0}},\quad\lVert U_{i}\rVert\,\lVert
V_{i}\rVert\leqslant\frac{(1+\varepsilon)^{2}}{(1-\varepsilon)\xi_{i}}$ (7.16)

for $w\in W_{i}$ and $i\in\\{1,2\\}$. (To explain this construction in detail,
for $i=1$ we apply Corollary 7.6 to the operator $T_{1}|_{V[c_{0}]}$; this is
justified because Lemma 7.8 and the first part of (7.15) show that the domain
$V[c_{0}]$ is isomorphic to $c_{0}$ and $T_{1}|_{V[c_{0}]}$ is non-compact.
Next, for $i=2$, we apply Corollary 7.6 to the operator
$T_{2}|_{T_{1}[W_{1}]}$; by construction its domain $T_{1}[W_{1}]$ is
isomorphic to $c_{0}$, and since $T_{1}[W_{1}]\subseteq T_{1}V[c_{0}]$, we can
apply Lemma 7.8 and (7.15) once more to deduce that $T_{2}|_{T_{1}[W_{1}]}$ is
non-compact.)

The second and third identity in (7.16) show that

$\nu(T_{2}+\mathscr{K}(C_{0}(K)))\nu(T_{1}+\mathscr{K}(C_{0}(K)))\geqslant\frac{1}{\lVert
U_{2}\rVert\,\lVert V_{2}\rVert\,\lVert U_{1}\rVert\,\lVert
V_{1}\rVert}\geqslant\frac{(1-\varepsilon)^{2}\xi_{1}\xi_{2}}{(1+\varepsilon)^{4}}.$
(7.17)

Set $W_{0}=V^{-1}[T_{1}^{-1}[W_{2}]\cap W_{1}]$. This is a closed subspace of
$c_{0}$ such that

$V[W_{0}]=T_{1}^{-1}[W_{2}]\cap W_{1}\qquad\text{and}\qquad
T_{1}V[W_{0}]=W_{2}.$

The latter identity implies that $W_{0}$ is infinite-dimensional. Combining
this with the first part of (7.15) and the left-hand inequality in (7.16), we
find

$1=\lVert I_{c_{0}}|_{W_{0}}\rVert_{e}=\lVert
UT_{2}T_{1}V|_{W_{0}}\rVert_{e}\leqslant\lVert U\rVert\,\lVert
T_{2}|_{W_{2}}\rVert\,\lVert T_{1}|_{W_{1}}\rVert\,\lVert
V\rVert\leqslant(1+\varepsilon)^{2}\xi_{1}\xi_{2}\lVert U\rVert\,\lVert
V\rVert.$

This produces a lower bound on $\xi_{1}\xi_{2}$, which we can substitute into
(7.17) to obtain

$\displaystyle\nu(T_{2}+\mathscr{K}(C_{0}(K)))\nu(T_{1}+\mathscr{K}(C_{0}(K)))$
$\displaystyle\geqslant\frac{(1-\varepsilon)^{2}}{(1+\varepsilon)^{6}\lVert
U\rVert\,\lVert V\rVert}$
$\displaystyle\geqslant\frac{(1-\varepsilon)^{3}}{(1+\varepsilon)^{6}}\nu(T_{2}T_{1}+\mathscr{K}(C_{0}(K))).$

Since this inequality holds true for arbitrary $\varepsilon\in(0,1)$, we
conclude that $\nu$ is submultiplicative.

Finally, the inequality (7.3) follows from the fact that if
$I_{c_{0}}-UTV\in\mathscr{K}(c_{0})$, then

$1=\lVert I_{c_{0}}\rVert_{e}=\lVert UTV\rVert_{e}\leqslant\lVert
U\rVert\,\lVert T\rVert_{e}\,\lVert V\rVert.\qed$

###### Proof of Theorem 7.1.

We can apply Theorem 3.1 because the unit ball of $C_{0}(K)^{*}$ is weak*
sequentially compact by Theorem 6.2; it shows that conditions (a) and (b) are
equivalent.

We shall now complete the proof by verifying that conditions (b)–(e) are
equivalent. Lemma 2.13 shows that (b) implies (c), which trivially implies
(d).

(d)$\Rightarrow$(e). Suppose that
$\mathscr{B}(C_{0}(K))/\mathscr{K}(C_{0}(K))$ is incompressible, and consider
the identity map $\iota$ on $\mathscr{B}(C_{0}(K))/\mathscr{K}(C_{0}(K))$,
which is obviously an algebra isomorphism. Proposition 7.2 shows that $\iota$
is continuous if we endow its domain with the essential norm and its codomain
with the algebra norm $\nu$ given by (7.2). Therefore the hypothesis implies
that $\iota$ is bounded below; that is, we can find a constant $\eta>0$ such
that

$\nu(T+\mathscr{K}(C_{0}(K)))\geqslant\eta\lVert
T\rVert_{e}\qquad(T\in\mathscr{B}(C_{0}(K))).$ (7.18)

(e)$\Rightarrow$(b). Suppose that $\eta>0$ is a constant for which (7.18) is
satisfied, and note that $\eta\leqslant 1$ by (7.3). We claim that (b) is
satisfied for any constant $C>1/\eta$. Indeed, let $T\in\mathscr{B}(C_{0}(K))$
be a non-compact operator with $\lVert T\rVert_{e}=1$, and take
$\xi\in(1/C,\eta)$. Then we have
$\nu(T+\mathscr{K}(C_{0}(K)))\geqslant\eta>\xi$, so the definition (7.2) of
$\nu$ implies that there are operators $U_{1}\in\mathscr{B}(C_{0}(K),c_{0})$
and $V_{1}\in\mathscr{B}(c_{0},C_{0}(K))$ such that

$I_{c_{0}}-U_{1}TV_{1}\in\mathscr{K}(c_{0})\qquad\text{and}\qquad\frac{1}{\lVert
U_{1}\rVert\,\lVert V_{1}\rVert}>\xi.$

Since $C\xi>1$, Lemma 2.15 shows that $U_{2}(U_{1}TV_{1})V_{2}=I_{c_{0}}$ for
some operators $U_{2},V_{2}\in\mathscr{B}(c_{0})$ with $\lVert
U_{2}\rVert\,\lVert V_{2}\rVert<C\xi$. Hence the operators $U=U_{2}U_{1}$ and
$V=V_{1}V_{2}$ have the required properties. ∎

### Acknowledgements

This paper is part of the first-named author’s PhD at Lancaster University. He
acknowledges with thanks the funding from the EPSRC (grant number
EP/R513076/1) that has supported his studies.

We are grateful to Bill Johnson (Texas A&M) for sharing an early draft of the
manuscript [25] with us, and to Hans-Olav Tylli (Helsinki) for pointing out
Example 2.18.

## References

  * [1] S. A. Argyros and R. G. Haydon, A hereditarily indecomposable $\mathscr{L}_{\infty}$-space that solves the scalar-plus-compact problem, _Acta Math._ 206 (2011), 1–54.
  * [2] M. Arnott and N. J. Laustsen, Classifying the closed ideals of bounded operators on two families of non-separable classical Banach spaces, _J. Math. Anal. Appl._ (2021), 125105.
  * [3] K. Astala and H.-O. Tylli, On the bounded compact approximation property and measures of noncompactness, _J. Funct. Anal._ 70 (1987), 388–401.
  * [4] B. A. Barnes, Algebraic elements of a Banach algebra modulo an ideal, _Pacific J. Math._ 117 (1985), 219–231.
  * [5] M. Cambern, On mappings of sequence spaces, _Studia Math._ 30 (1968), 73–77.
  * [6] S. R. Caradus, W. E. Pfaffenberger and B. Yood, _Calkin algebras and algebras of operators on Banach spaces,_ Marcel Dekker, 1974.
  * [7] H. G. Dales, A discontinuous homomorphism from $C(X)$, _Amer. J. Math._ 101 (1979), 647–734.
  * [8] H. G. Dales, _Banach algebras and automatic continuity_ , London Math. Soc. Monogr. Ser. 24, Clarendon Press, Oxford, 2000.
  * [9] H. G. Dales and W. H. Woodin, _An introduction to independence for analysts,_ London Math. Soc. Lecture Note Ser. 115, Cambridge University Press, 1987.
  * [10] M. Daws, Closed ideals in the Banach algebra of operators on classical non-separable spaces, _Math. Proc. Cambr. Philos. Soc._ 140 (2006), 317–332.
  * [11] J. Diestel, _Sequences and series in Banach spaces_ , Graduate Texts in Math. 92, Springer-Verlag, 1983.
  * [12] P. N. Dowling, N. Randrianantoanina and B. Turett, Remarks on James’s distortion theorems II, _Bull. Austral. Math. Soc._ 59 (1999), 515–522.
  * [13] M. Eidelheit, On isomorphisms of rings of linear operators, _Studia Math._ 9 (1940), 97–105.
  * [14] J. R. Esterle, Injection de semi-groupes divisibles dans des algèbres de convolution et construction d’homomorphismes discontinus de $\mathcal{C}(K)$, _Proc. London Math. Soc._ 36 (1978), 59–85.
  * [15] D. Freeman, Th. Schlumprecht and A. Zsák, Banach spaces for which the space of operators has $2^{\mathfrak{c}}$ closed ideals, _Forum Math., Sigma_ 9 (2021), 1–20.
  * [16] E. M. Galego and A. Plichko, On Banach spaces containing complemented and uncomplemented subspaces isomorphic to $c_{0}$, _Ext. Math._ 18 (2003), 315–319.
  * [17] I. C. Gohberg, A. S. Markus and I. A. Feldman, Normally solvable operators and ideals associated with them, _Amer. Math. Soc. Translat._ 61 (1967), 63–84, Russian original in _Bul. Akad. Štiince RSS Moldoven_ 10 (76) (1960), 51–70.
  * [18] M. González, E. Saksman and H.-O. Tylli, Representing non-weakly compact operators, _Studia Math._ 113 (1995), 265–282.
  * [19] B. Gramsch, Eine Idealstruktur Banachscher Operatoralgebren, _J. Reine Angew. Math._ 225 (1967), 97–115.
  * [20] J. Hagler and W. B. Johnson, On Banach spaces whose dual balls are not weak* sequentially compact, _Israel J. Math._ 28 (1977), 325–330.
  * [21] P. Hájek, V. Montesinos Santalucía, J. Vanderwerff and V. Zizler, _Biorthogonal systems in Banach spaces,_ CMS Books in Math./Ouvrages de Math. de la SMC 26, Springer-Verlag, New York, 2008.
  * [22] B. Horváth and T. Kania, Surjective homomorphisms from algebras of operators on long sequence spaces are automatically injective, _Quart. J. Math._ 72 (2021), 1167–1189.
  * [23] R. C. James, Uniformly non-square Banach spaces, _Ann. of Math._ 80 (1964), 542–550.
  * [24] B. E. Johnson, Continuity of homomorphisms of algebras of operators, _J. London Math. Soc._ 42 (1967), 537–541.
  * [25] W. B. Johnson, T. Kania and G. Schechtman, Closed ideals of operators on and complemented subspaces of Banach spaces of functions with countable support, _Proc. Amer. Math. Soc._ 144 (2016), 4471–4485.
  * [26] W. B. Johnson and N. C. Phillips, Manuscript in preparation.
  * [27] T. Kania and T. Kochanek, The ideal of weakly compactly generated operators acting on a Banach space, _J. Op. Th._ 71 (2014), 455–477.
  * [28] T. Kania and N. J. Laustsen, Ideal structure of the algebra of bounded operators acting on a Banach space, _Indiana Univ. Math. J._ 66 (2017), 1019–1043.
  * [29] P. Koszmider, On decompositions of Banach spaces of continuous functions on Mrówka’s spaces, _Proc. Amer. Math. Soc._ 133 (2005), 2137–2146.
  * [30] P. Koszmider and N. J. Laustsen, A Banach space induced by an almost disjoint family, admitting only few operators and decompositions, _Adv. Math._ 381 (2021), 107613.
  * [31] N. J. Laustsen, R. J. Loy and C. J. Read, The lattice of closed ideals in the Banach algebra of operators on certain Banach spaces, _J. Funct. Anal._ 214 (2004), 106–131.
  * [32] N. J. Laustsen, Th. Schlumprecht and A. Zsák, The lattice of closed ideals in the Banach algebra of operators on a certain dual Banach space, _J. Op. Th._ 56 (2006), 391–402.
  * [33] N. J. Laustsen and R. Skillicorn, Extensions and the weak Calkin algebra of Read’s Banach space admitting discontinuous derivations, _Studia Math._ 236 (2017), 51–62.
  * [34] J. Lindenstrauss and L. Tzafriri, _Classical Banach spaces,_ Vol. I, Ergeb. Math. Grenzgeb. 92, Springer-Verlag, Berlin–New York, 1977.
  * [35] H. P. Lotz, N. T. Peck and H. Porta, Semi-embeddings of Banach spaces, _Proc. Edinb. Math. Soc._ 22 (1979), 233–240.
  * [36] E. Luft, The two-sided closed ideals of the algebra of bounded linear operators of a Hilbert space, _Czech. Math. J._ 18 (1968), 595–605.
  * [37] M. J. Meyer, On a topological property of certain Calkin algebras, _Bull. London Math. Soc._ 24 (1992), 591–598.
  * [38] M. J. Meyer, Lower bounds for norms on certain algebras, _Illinois J. Math._ 39 (1995), 567–575.
  * [39] P. Motakis, Separable spaces of continuous functions as Calkin algebras, _J. Amer. Math. Soc._ (2023), https://doi.org/10.1090/jams/1024
  * [40] P. Motakis, D. Puglisi and D. Zisimopoulou, A hierarchy of separable commutative Calkin algebras, _Indiana Univ. Math. J._ 65 (2016), 39–67.
  * [41] I. Namioka and R. R. Phelps, Banach spaces which are Asplund spaces, _Duke Math. J._ 42 (1975), 735–750.
  * [42] T. W. Palmer, _Banach algebras and the general theory of ∗-algebras,_ Vol. I, Cambridge University Press, 1994.
  * [43] A. Pełczyński, On strictly singular and strictly cosingular operators. I. Strictly singular and strictly cosingular operators in $C(S)$-spaces. _Bull. Acad. Pol. Sci._ 13 (1965), 31–37.
  * [44] A. Pietsch, _Operator ideals,_ North Holland, 1980.
  * [45] C. J. Read, Discontinuous derivations on the algebra of bounded operators on a Banach space, _J. London Math. Soc._ 40 (1989), 305–326.
  * [46] H. P. Rosenthal, On relatively disjoint families of measures, with some applications to Banach space theory, _Studia Math._ 37 (1970), 13–36.
  * [47] W. Rudin, Continuous functions on compact spaces without perfect subsets, _Proc. Amer. Math. Soc._ 8 (1957), 39–42.
  * [48] M. Tarbard, Hereditarily indecomposable, separable $\mathscr{L}_{\infty}$ Banach spaces with $\ell_{1}$ dual having few but not very few operators, _J. London Math. Soc._ 85 (2012), 737–764.
  * [49] H.-O. Tylli, The essential norm of an operator is not self-dual, _Israel J. Math._ 91 (1995), 93–110.
  * [50] H.-O. Tylli, Exotic algebra norms on quotient algebras of the bounded linear operators, _Proceedings of the $3^{\text{rd}}$ International Conference on Topological Algebra and Applications, Oulu 2–6 July, 2001,_ (editors: M. Filali and J. Arhippainen), Oulu University Press, Oulu (2004), 210–224.
  * [51] G. K. Ware, _Uniqueness of norm properties of Calkin algebras,_ PhD thesis, Australian National University, 2014; available online at https://openresearch-repository.anu.edu.au/handle/1885/14510
  * [52] B. Yood, Homomorphisms on normed algebras, _Pacific J. Math._ 8 (1958), 373–381.


Department of Computer Science, ETH Zürich,
<EMAIL_ADDRESS>Institute for Machine Learning,
ETH Zürich<EMAIL_ADDRESS>Ivan Baburin and Ryan
Cotterell <ccs2012> <concept> <concept_id>10003752.10003766</concept_id>
<concept_desc>Theory of computation Formal languages and automata
theory</concept_desc> <concept_significance>300</concept_significance>
</concept> </ccs2012> [300]Theory of computation Formal languages and automata
theory John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# Blow-up in Non-Deterministic Automata

Ivan Baburin  Ryan Cotterell

###### Abstract

In this paper we examine the difficulty of finding an equivalent deterministic
automaton when confronted with a non-deterministic one. While for some
automata the exponential blow-up in their number of states is unavoidable, we
show that in general, any approximation of state complexity with polynomial
precision remains ${{\mathsf{PSPACE}}}$-hard. The same is true when using the
subset construction to determinize the NFA, meaning that it is
${{\mathsf{PSPACE}}}$-hard to predict whether subset construction will produce
an exponential “blow-up” in the number of states or not. To give an
explanation for its behaviour, we propose the notion of subset complexity,
which serves as an upper bound on the size of subset construction. Due to it
simple and intuitive nature it allows to identify large classes of automata
which can have limited non-determinism and completely avoid the “blow-up”.
Subset complexity also remains invariant under NFA reversal and allows to
predict how the introduction or removal of transitions from the NFA will
affect its size.

###### keywords:

Non-Deterministic Automata, Subset construction, Determinization, Complexity

##  1 Introduction

Among the very first results in automata theory was the equivalence between
non-deterministic automata (NFAs) and deterministic automata (DFAs). The
original proof by Rabin and Scott [RabinPowerset] presented the powerset
construction: a general algorithm for converting arbitrary NFAs into DFAs. A
major downside of powerset construction (and its improved version, the subset
construction) was the fact that it could produce an exponential blow-up of up
to $2^{{|{{Q}}|}}$ states during this conversion. It was later shown by Moore
[moore1971bounds] that this was unavoidable: he gave a $n$-state NFA
construction known today as the Moore’s automaton (see Figure 1) with the
property that the minimal equivalent DFA requires exactly $2^{n}$ states, i.e.
exhibiting a “blow-up”. Since then, a lot of other types of automata and
subregular languages have been shown to exhibit a similar “blow-up” behaviour
[brualdi1991combinatorial], but the question of why and when it happens
remained open.

On the other hand there have been many approaches to model the non-determinism
in finite state automata. Some of the more prominent ones include ambiguity
[ambiguous-NFA], tree width [HromkovicTree], size of syntactic semigroup,
number of atoms, reversal complexity, star complexity [complexity-survey],
and, more recently the NFA width [width-NFA]. Since determinization plays a
key role in answering many questions about NFA properties, several other
determinization algorithms besides subset construction have been developed:
for example Brzozowski’s algorithm [brzozowski] which applies subset
construction two times to directly produce a minimal DFA. An overview for some
other minimization (and determinization) algorithms can be found in [automata-
minimization]. While determinization remains important, due to accompanying
difficulties there are now a handful of approaches answering NFA related
questions without an explicit determinization. Some examples of such
algorithms include the “hacking universality” algorithm [hacking-universality]
for NFA equivalence and the antichain algorithm for NFA universality
[antichain-algorithms].

$q_{1}$$q_{2}$$q_{3}$$q_{4}$$\ldots$$q_{n}$$b$$a$$a,b$$a,b$$a,b$$a,b$$a$$a$
Figure 1: Moore’s non-deterministic automaton
${{{{\mathcal{A}}}_{\textsc{moore}}}}$ with $n$ states which for $n\geq 2$
requires at least $2^{n}$ states in its deterministic analogue

In this paper we return back to the roots of the problem and try to answer the
question on when the determinization can be performed efficiently, i.e. avoids
the exponential “blow-up” and how to predict it. Furthermore, we will resort
to the subset construction as our go-to determinization algorithm since it is
the most common determinization algorithm and widely used in many automata
libraries [allauzen2007openfst]. Optimality of subset construction was studied
in [brzozowski-full] which characterized all trim automata for which the
subset construction results in a minimal DFA. As we see it, there are two ways
to approach the “blow-up” problem:

  * •

Try to find an efficient algorithm which could tell us whether the minimal DFA
is large, or whether the subset construction explodes

  * •

Find some characterization for automata with no “blow-up”

We investigate the first point in LABEL:sec:difficulties and show that it is
${{\mathsf{PSPACE}}}$-hard to answer any of those questions, even if we relax
our demands to a fairly coarse grained approximation. A summary of our
findings can be found in Table 1. On the second point [delta-NFAs] provides a
characterization for a simple class of NFAs (called $\delta$NFAs) for which
determinization is ${{\mathsf{NP}}}$-hard, even though the minimal
deterministic automaton for any $\delta$NFA only has a quadratic number of
states. In LABEL:sec:subset-complexity we take a slightly different approach
and introduce a very simple measure which we call “subset complexity” serving
as an upper bound for the run of a subset construction. Subset complexity has
no explicit relation to any language properties of the NFA and is purely based
on its transition structure. In LABEL:sec:computational we discuss how to
efficiently bound the subset complexity when confronted with NFA, and in
LABEL:sec:examples provide some examples where subset complexity can explain
the “blow-up” particularly well. LABEL:sec:open-questions states some open
questions.

Table 1: Complexity results on estimating the size of minimal DFA and the size
of the output from subset construction. The entries in gray indicate priorly
known results, while the ones in black correspond to our contributions. The
difficulty of decision problems translates into the difficulty of computing
exact values.

(r,1cm,0.9cm)[5pt]c|c|cc|c|c& Exact size Approximation
Minimal DFA ${{\mathsf{PSPACE}}}$-complete ${{\mathsf{PSPACE}}}$-complete
Subset construction ${{\mathsf{PSPACE}}}$-complete
${{\mathsf{PSPACE}}}$-complete

##  2 Background: Automata and Semigroups

We start by briefly reciting core definitions for finite-state automata in the
context of language recognition, determinism and their complexity, as well as
the duality between automata and finite semigroups.

######  Definition 2.1.

A

The symbol ${{\varepsilon}}$ represents an empty symbol, and thus a transition
with label ${{\varepsilon}}$ (or in short ${{\varepsilon}}$-transition) can
always be performed without the need for any additional input.

######  Definition 2.2.

A

We say that a word ${{\boldsymbol{y}}}\in{{{{\Sigma}}^{*}}}$ is

######  Definition 4.

recognized by the FSA ${{\mathcal{A}}}$ if there exists a path from some
starting state ${{q}}\in{{I}}$ to some final state ${{q}}^{\prime}\in{{F}}$
with yield ${{\boldsymbol{y}}}$. Moreover, we denote with
${{\mathcal{L}({{\mathcal{A}}})}}$ the