###### Abstract

A general framework is introduced to estimate how much external information
has been infused into a search algorithm, the so-called active information.
This is rephrased as a test of fine-tuning, where tuning corresponds to the
amount of pre-specified knowledge that the algorithm makes use of in order to
reach a certain target. A function $f$ quantifies specificity for each
possible outcome $x$ of a search, so that the target of the algorithm is a set
of highly specified states, whereas fine-tuning occurs if it is much more
likely for the algorithm to reach the target than by chance. The distribution
of a random outcome $X$ of the algorithm involves a parameter $\theta$ that
quantifies how much background information that has been infused. A simple
choice of this parameter is to use $\theta f$ in order to exponentially tilt
the distribution of the outcome of the search algorithm under the null
distribution of no tuning, so that an exponential family of distributions is
obtained. Such algorithms are obtained by iterating a Metropolis-Hastings type
of Markov chain, and this makes it possible to compute the their active
information under equilibrium and non-equilibrium of the Markov chain, with or
without stopping when the targeted set of fine-tuned states has been reached.
Other choices of tuning parameters $\theta$ are discussed as well.
Nonparametric and parametric estimators of active information and tests of
fine-tuning are developed when repeated and independent outcomes of the
algorithm are available. The theory is illustrated with examples from
cosmology, student learning, reinforcement learning, a Moran type model of
population genetics, and evolutionary programming.

###### keywords:

Active information; exponential tilting; fine-tuning; functional information;
large deviations; Markov chains; Metropolis-Hastings; Moran model; statistical
estimation and testing

1 1 0 https://doi.org/ Assessing, testing and estimating the amount of fine-
tuning by means of active information Fine-tuning and active information
Daniel Andrés Díaz-Pachón 1 and Ola Hössjer 2,* Daniel Andrés Díaz-Pachón and
Ola Hössjer Díaz-Pachón, D. A.; Hössjer, O. Correspondence<EMAIL_ADDRESS>Tel.: +46-706721218 (O.H.)

##  1 Introduction

When Gödel published his incompleteness theorems (Gödel, 1931), there was a
commotion in the mathematical world from which it has neither yet recovered
nor fully assimilated the consequences Hofstadter (1999). Hilbert’s program to
base mathematics on a finite set of axioms had earlier been pursued by Alfred
North Whitehead and Bertrand Russell Whitehad and Russell (1927). But this
approach turned out to be wrong when Gödel proved that no finite set of axioms
in a formal system can prove all its true statements, including its own
consistency. In similar but lesser scale, when David Wolpert and William
MacReady published their No Free Lunch Theorems (NFLTs, Wolpert and MacReady
(1995, 1997)), there was disquiet in the community because these results imply
that there is no one-size-fit-all algorithm that can do well in all searches
Wolpert (2021), so that a “theory of everything” is not possible in machine
learning. Wolpert and MacReady concluded that it was necessary to incorporate
“problem-specific knowledge into the behavior of the algorithm” Wolpert and
MacReady (1997). Thus active information (actinfo) was introduced in order to
measure the amount of information carried by such problem-specific knowledge
Dembski and Marks II (2009a, b). More specifically, the NFLTs say that no
search works better on average than a blind search, i.e., a search according
to a uniform distribution. Accordingly, actinfo is defined as

$\displaystyle I^{+}=\log\frac{P(A)}{P_{0}(A)},$ (1)

where $A\subset\Omega$ is the non-empty target of the search algorithm, a
subset of the finite sample space $\Omega$, and $P_{0}$ is a uniform
probability measure ($P_{0}(A)=|A|/|\Omega|$). $P$ must be seen here as the
probability measure induced by the problem-specific knowledge of the
researcher, whereas $P_{0}$ is the underlying distribution assumed in the
NFLTs. It corresponds to absence of problem specific knowledge, in accordance
with Bernoulli’s Principle of Insufficient Reason (PoIR). An equivalent
characterization of actinfo is the reduction of functional information

$I^{+}=I_{f_{0}}-I_{f}=-\log P_{0}(A)-(-\log P(A))$ (2)

between algorithms that do not and do make use background knowledge. The name
functional information was introduced by Szostak and collaborators Hazen et
al. (2007); Szostak (2003). It refers to applications where $A$ corresponds to
all outcomes of an algorithm that are functional according to some criterion.
Then $I_{f_{0}}$ and $I_{f}$ are the self-information (measured in nats) of
the event that an algorithm $X$ produces a functional outcome, given that it
was generated under $P_{0}$ and $P$, respectively.

Suppose we do not know whether problem specific knowledge has been used or not
when the random search $X\in\Omega$ was generated. This corresponds to a
hypothesis testing problem

$\begin{array}[]{ll}H_{0}:X\sim P_{0},\\\ H_{1}:X\sim P,\end{array}$ (3)

where data is generated from distributions $P_{0}$ and $P$ under the null and
alternative hypotheses $H_{0}$ and $H_{1}$, respectively. It follows from (1)
that $I^{+}$ is the log likelihood ratio when testing $H_{0}$ against $H_{1}$,
if data is censored so that only $X\in A$ is known.

When the sample space $\Omega$ is finite or a bounded subset of a Euclidean
space, the PoIR can be motivated by the fact that the uniform distribution
maximizes Shannon entropy, since thereby it maximizes ignorance about the
outcome of $X$. However, the uniform distribution is not a feasible choice of
$P_{0}$ for unbounded samples spaces. For this reason actinfo has been
generalized to deal with unbounded spaces Díaz-Pachón and Marks II (2020), by
choosing $P_{0}$ to maximize Shannon entropy under side constraints $\xi$,
such as existence of various moments. This gives rise to a family of null
distributions $P_{0}=P_{0\xi}$, with a $\xi$ a nuisance parameter that has to
be estimated or controlled for in order to estimate or give bounds for the
active information.

Actinfo has also been used for mode detection in unsupervised learning, among
other applications Díaz-Pachón et al. (2019); Liu et al. (2022). Based on
previous work by Montañez Montañez (2017, 2018), actinfo has been used in the
past for hypothesis testing Díaz-Pachón et al. (2020). More specifically,
Díaz-Pachón et al. (2020) regards $P$ as a random measure so that $I^{+}$ is
random as well, and finds expressions for the tail probability of $I^{+}$.

###  1.1 Fine-tuning

Fine-tuning (FT) was introduced by Carter in physics and cosmology Carter
(1974). According to FT, the constants in the laws of nature and/or the
boundary conditions in the standard models of physics must belong to intervals
of low probability in order for life to exist. Since its inception, FT has
generated a great deal of fascination, seen in multiple divulgation books
(e.g., Barrow and Tipler (1988); Davies (1982); Lewis and Barnes (2016); Rees
(2000)) and scientific articles (e.g., Adams (2019); Barnes (2012); Tegmark
and Rees (1998); Tegmark et al. (2006)). For a given constant of nature $X$,
the connection between FT and active information can be described in three
steps:

  1. (i)

Establishing the life-permitting interval (LPI) $A$ that allows the existence
of life for the constant, with $\Omega=(0,\infty)={\mathbb{R}}^{+}$ or
$\Omega={\mathbb{R}}$ the range of values this constant could possibly take,
including those that do not permit life.

  2. (ii)

Determining the probability $P_{0}(A)$ of such a LPI. If $P_{0}=P_{0\xi}$
contains unknown parameters $\xi$, find an upper bound

$P_{0\text{max}}(A)=\max_{\xi}P_{0\xi}(A)$ (4)

of $P_{0}(A)$.

  3. (iii)

Suppose $H_{1}$ corresponds to an agent who uses background knowledge of what
is required for life to exist in order to bring about a constant of nature $X$
that with certainty permits life ($P(A)=1$). The active information
$I^{+}=I_{f_{0}}=-\log P_{0}(A)$ is then a measure of how much background
knowledge this agent infused. Following Díaz-Pachón et al. (2021, 2022), we
conclude that $X$ is finely tuned when the lower bound $-\log
P_{0\text{max}}(A)$ of $I^{+}=I_{f_{0}}$ is large enough. That is, FT
corresponds to infusing a high degree of background knowledge into a problem.

Fine-tuning has also been used in biology. Dingjan and Futerman explored it
for cell membranes Dingjan and Futerman (2021a, b), whereas Thorvaldsen and
Hössjer Thorvaldsen and Hössjer (2020) formalized it for a large class of
biological models. According the Thorvaldsen and Hössjer (2020), a system is
fine-tuned if it (a) has an independent specification, and (b) is very
unlikely to occur by chance.

###  1.2 The present article

In this article actinfo will not only be used in the algorithmic sense. It
will also be employed for testing the presence of and estimating the degree of
fine-tuning (FT) of a search algorithm or agent who brings about $X$. To this
end, we will introduce a specificity function $f$, which quantifies, in terms
of $f(x)$, how specified an outcome $x\in\Omega$ is. The target $A$, on the
other hand, is the set of highly specified states, that is, all states with a
degree of specificity that exceeds a given threshold. Then $I^{+}$ in (1) is a
test statistic for testing whether an algorithm has a much larger probability
of reaching the set of highly specified states or not, compared to a random
search. This is a test of FT, since reaching the target corresponds to
specificity (a), whereas reaching it with much higher probability than
expected by chance corresponds to (b).

To calculate $I^{+}$, the distributions $P_{0}$ and $P$ of the random search
algorithm under $H_{0}$ and $H_{1}$, respectively, need to be defined. As
mentioned above, the null distribution $P_{0}$ is typically chosen according
to some criterion, such as a maximizer of entropy, possibly with some extra
constraints on moments for unbounded $\Omega$, which was the strategy
implemented in Díaz-Pachón et al. (2021, 2022). Another possibility is to
choose $P_{0}$ as the equilibrium distribution of a Markov chain that models
the dynamics of the system under the null hypothesis, for instance an
evolutionary process with no external input. In general $P_{0}=P_{0\xi t}$
involves a number of nuisance parameters $\xi$, and sometimes also the time
point $t$ when an algorithm, that does not make use of external information,
stops. The choice of $P=P_{\theta\xi t}$ is problem specific, and it possibly
involves the nuisance parameters $\xi$ of the null distribution, the time
point $t$ when the algorithm stops, as well as tuning parameters $\theta$ that
correspond to infusing background knowledge into the search problem.
Therefore, in its most general form, the actinfo (1) is a function
$I^{+}=I^{+}(\theta,\xi,t)$ of the tuning parameters $\theta$, the nuisance
parameters $\xi$, and the time point $t$.

This general framework has many applications, based on different choices of
$f$, $A$, $P_{0}$, and $P$. For some models, $f$ is a binary function that
quantifies functionality, so that $A$ is the set of objects of a certain type
(e.g., proteins, protein complexes or cellular networks) that are functional
among the set $\Omega$ of all such objects. Another possibility is to choose
$A$ as the set of populations whose (expected) fitness exceeds a given
threshold. In this setting $P_{0\xi t}(A)$ corresponds to the probability that
a randomly chosen object or population would reach target $A$ of high fitness
at time $t$, given that no background knowledge of the specificity function
$f$ is used to generate $X$. The functional information $I_{f_{0}}=-\log
P_{0\xi t}(A)$ corresponds to the amount of external information that an
algorithm infuses, given that it brings about $X$ so that $A$ happens with
certainty ($P(A)=1$) within time $t$. In this case the object or population is
finely tuned when $I_{f_{0}}$ is large enough. More generally, we say that an
evolutionary algorithm that generates $X\sim P=P_{\theta\xi t}$ after $t$ time
steps is finely tuned when $I^{+}(\theta,\xi,t)$ is large enough. Typically,
$\theta$ involves selection parameters that determine to which extent a
population evolves towards higher fitness.

The unified treatment of search problems and FT of this paper, is organized as
follows: Section 2 introduces the specification function $f$ and the set $A$
of highly specified states. Section 3 introduces a class of probability
distributions $P=P_{\theta}$ for which the specificity function $f$ is used to
exponentially tilt the null distribution $P_{0}$, so that outcomes with high
specificity are more likely to occur, and with a scalar tuning parameter
$\theta$ of $P_{\theta}$ that corresponds to the amount of exponential
tilting. A proof is presented that it is possible to obtain a Metropolis-
Hastings type Markov chain in discrete time $t=0,1,2,\ldots$, whose outcome
$X=X_{t}$ at time $t$ has the aforementioned exponentially tilted distribution
under equilibrium, that is, when $t$ is large. The corresponding actinfo
$I^{+}(\theta,t)$ is shown to increase monotonically with $t$ towards an
equilibrium limit. The actinfo of a search algorithm $X=X_{t\wedge T}$ that
stops at time $T$, when the targeted set $A$ of highly specified states has
been reached, is also shown to increase more rapidly. Section 4 introduces
various nonparametric and parametric estimators of actinfo, and corresponding
tests of FT, when $n$ repeated and independent outputs of the search algorithm
are available. In particular, large deviations theory is used to prove that
the significance levels of these tests, i.e. the probability to detect FT
under $H_{0}$, goes to zero at an exponential rate when the sample size $n$
increases. Section 5 presents a number of examples from cosmology, student
learning, reinforcement learning, and population genetics, that illustrate our
approach. A discussion in Section 6 follows, whereas proofs and further
details about the models, are presented in Section 7.

##  2 Specificity and target

Consider a function $f:\Omega\to\mathbb{R}$, and assume that the objective of
the search algorithm, or the agent that brings about $X$, is to find regions
in $\Omega$ where $f$ is large. The rationale for this is an independent
specification, where a more specified state $x\in\Omega$ corresponds to a
larger $f(x)$. It is further assumed that the target set in (1) has the form

$\displaystyle A=\\{x\in\Omega;\,f(x)\geq f(x_{0})\\}.$ (5)

This implies that the purpose of the search algorithm or the agent is to bring
about an $X$ that is highly specified. We will refer to $f$ as a specificity
function of the agent or an objective function of the search algorithm. For
instance, in cosmological FT, $x$ is the value of a particular constant of
nature and the specificity function equals

$f(x)=1_{\\{x\in A\\}},$ (6)

where $1_{\\{\cdot\\}}$ is the indicator function. That is, $f$ has a binary
range, with $f(x)=1$ and 0 corresponding to whether $x$ permits a universe
with life or not. From this, $A$ is the LPI of this constant if $f(x_{0})=1$.
Moreover, $X$ is the value of this constant of nature for a randomly generated
universe, with a distribution that either incorporates external information
($H_{1}$) or not ($H_{0}$).

In the context of proteins, $x$ is taken to be an amino acid sequence, whereas
$f(x)$ in (6) quantifies whether the protein that the amino acid corresponds
to is functional (1) or not (0). For instance, $X$ could be the outcome of a
random evolutionary process, the goal of which is to generate a functioning
protein, and this process either makes use of external information ($H_{1}$)
or not ($H_{0}$). Several other applications are given in Section 5, including
a more refined biological example, where $x$ corresponds to a protein complex
or a molecular machine.

###  2.1 Interpretation of target

There are at least two ways of interpreting $x_{0}$, and hence also the target
set $A$. According to the first interpretation, $x_{0}$ is the outcome of
random variable $X^{\prime}\in\Omega$; that is, the outcome of a first search.
Suppose $X$ is another random variable that represents a second (possibly
future) search, independent of $X^{\prime}$. Then, if we condition on the
outcome $x_{0}$ of the first search, the actinfo $I^{+}$ in (1) is the log
likelihood ratio for the event that the second search variable $X$ is at least
as specified as the observed value $f(x_{0})$ of the first search.

There is no need to associate $x_{0}$ in (5) with a first search variable
$X^{\prime}$ though. Instead, some apriori information may be used to define
which values of $f$ represent a high amount of specificity. This gives rise to
the second interpretation of $x_{0}$, according to which $x_{0}$ is used for
defining outcomes with a high and low degree of specificity, using
$f_{0}=f(x_{0})$ as a cutoff. According to this interpretation, the two sets
$A$ in (5) and its complement

$\displaystyle A^{c}=\Omega\setminus A=\\{x;\,f(x)<f(x_{0})\\}$

represent a dichotomization of specificity, so that $A$ and $A^{c}$ consist of
all states with high and low specificity respectively. With this
interpretation of $x$, $I^{+}$ is the log likelihood ratio for testing FT
based on the search variable $X$. In particular, suppose that the specificity
function $f$ is bounded, i.e.

$\displaystyle f_{\text{max}}=\max_{x\in\Omega}f(x)<\infty.$ (7)

Then the most stringent definition of high specificity,

$\displaystyle f_{0}=f_{\text{max}},$ (8)

only regards outcomes with a maximal value of $f$ as highly specified, so that

$\displaystyle A=\Omega_{\text{max}}=\\{x\in\Omega;\,f(x)=f_{\text{max}}\\}.$
(9)

Note that (6) is a special case of (9).

##  3 Active information for exponentially tilted systems

Throughout Section 3, $\xi$ is assumed to be known and the null distribution
does not involve any time index $t$. Therefore, $P_{0}$ is known, whereas
$P=P_{\theta t}$ involves the tuning parameters $\theta$ and the time index
$t$. It will further be assumed in Sections 3.1-3.2 that the system is in
equilibrium, so that the time index $t$ can be dropped also under $H_{1}$
($P=P_{\theta}$).

###  3.1 Exponential tilting

Let $P_{\theta}$ be an exponentially tilted version of $P_{0}$ for some scalar
tuning parameter $\theta>0$, which will also be called tilting parameter.
Exponential tilting is often used for rare events simulation Asmussen and
Glynn (2007); Siegmund (1976). Here $f$ is used to define the tilted version
of $P_{0}$ as

$\displaystyle P_{\theta}(x)=\frac{e^{\theta f(x)}}{M(\theta)}P_{0}(x),$ (10)

with

$\displaystyle M(\theta)=\sum_{x\in\Omega}e^{\theta f(x)}P_{0}(x)$ (11)

a normalizing constant assuring that $P_{\theta}$ is a probability measure.
For finite sample spaces $\Omega$, we interpret $P_{0}(x)$ and $P_{\theta}(x)$
as probability masses, whereas for continuous sample spaces they are
probability densities, and the sum in (11) is replaced by an integral. The
larger the tilting parameter $\theta>0$, the more the probability mass of
$P_{\theta}$ concentrates on regions of large $f$. In particular,
$P_{\infty}$, the weak limit of $P_{\theta}$ as $\theta\to\infty$, is
supported on (9) whenever (7) holds.

The parametric family

$\displaystyle\mathcal{P}=\\{P_{\theta};\,\theta\geq 0\\}$ (12)

of distributions is an exponential family (Lehmann and Casella, 1998, Section
1.5), and each $P_{\theta}\in\mathcal{P}$ gives rise to a separate version of
actinfo. This is summarized in the following proposition:

######  Proposition 1.

Suppose the target set $A$ is defined as in (5) for some $x_{0}\in\Omega$ such
that $P_{0}(A)>0$. Then $P_{\theta}(A)$ is a strictly increasing function of
$\theta\geq 0$ with $P_{\infty}(A)=1$. Consequently, the actinfo

$\displaystyle I^{+}(\theta)=\log\frac{P_{\theta}(A)}{P_{0}(A)}$ (13)

is a strictly increasing function of $\theta\geq 0$, with $I^{+}(0)=0$ and
$I^{+}(\infty)=I_{f0}=-\log P_{0}(A)$.

The intuitive interpretation of Proposition 1 is that the larger $\theta$ is,
the more problem specific knowledge is infused into $P_{\theta}$ in terms of
shifting probability mass towards regions in $\Omega$ where $f$, the
specificity function, is large.

###  3.2 Metropolis-Hastings systems with exponential tilting equilibrium

Inspired by Markov Chain Monte Carlo methods Robert and Casella (2010),
consider a Markov chain $X_{0},X_{1},\ldots\in\Omega$ for which $P_{\theta}$
is the equilibrium distribution. Consequently, if $P=P_{\theta}$ (that is,
under the alternative hypothesis $H_{1}$ in (2) when $\theta>0$), $X=X_{t}$
may be interpreted as the outcome of an algorithm after $t$ iterations,
provided $t$ is so large that equilibrium has been reached. The assumption is
made that this algorithm knows $f$ and tries to explore the whole state space
$\Omega$. If the Markov chain has an equilibrium distribution (10), this
corresponds to an algorithm that favors jumps towards regions of large $f$
when $\theta>0$, more so the higher the value of $\theta$ is. In more detail,
the transition kernel of the chain is an instance of the well-known
Metropolis-Hastings (MH) algorithm Hastings (1970); Metropolis et al. (1953),
which is closely related to simulated annealing Kirkpatrick et al. (1983).
This kernel has a probability or density

$\displaystyle\pi_{\theta}(x,y)=r_{\theta}(x)\delta(x,y)+\alpha_{\theta}(x,y)q(x,y)$
(14)

for jumps from $x$ to $y$, where $\delta(x,\cdot)$ is a point mass at
$x\in\Omega$, $q(x,\cdot)$ is a proposal distribution of jumps from a current
position $x$ of the Markov chain,

$\displaystyle\alpha_{\theta}(x,y)=\min\left[1,\frac{e^{\theta
f(y)}P_{0}(y)q(y,x)}{e^{\theta f(x)}P_{0}(x)q(x,y)}\right]$ (15)

is the probability of accepting a proposed move from $x$ to $y$, whereas

$\displaystyle r_{\theta}(x)=1-\sum_{y\in\Omega}\alpha_{\theta}(x,y)q(x,y)$
(16)

is the probability that the Markov chain rejects a proposed move away from $x$
(for continuous sample spaces $q(x,\cdot)$ is a probability density and then
the sum in (16) is replaced by an integral). The transition of the Markov
chain from $X_{t}=x$ to the next state $X_{t+1}$ is described in two steps as
follows. First a candidate $Y\sim q(x,\cdot)$ is proposed. Then in the second
step this candidate is either accepted with probability
$\alpha_{\theta}(x,Y)$, so that $X_{t+1}=Y$, or it is rejected with
probability $1-\alpha_{\theta}(x,Y)$, so that $X_{t+1}=X_{t}$. It is well
known that $P_{\theta}$ is the equilibrium distribution of this Markov chain
whenever it is irreducible; that is, provided the proposal distribution $q$ is
defined in such a way that moving between any pair of states in $\Omega$ in a
finite number of steps is possible (Ross, 2003, pp. 243-245).

In particular, if $q$ is symmetric and $P_{0}$ is uniform, then a proposed
upward move with $f(Y)>f(x)$ and $P_{\theta}(Y)>P_{\theta}(x)$ is always
accepted, whereas a proposed downward move with $f(Y)<f(x)$ is accepted with
probability $P_{\theta}(Y)/P_{\theta}(x)$. The Markov chain only makes local
jumps if $q(x,\cdot)$ puts all its probability mass in a small neighborhood of
$x$, for any $x\in\Omega$. At the other extreme is a chain with the global
proposal distribution $q(x,\cdot)\sim P_{\theta}$ for any $x\in\Omega$; all
proposed jumps of this chain are then accepted ($\alpha(x,y)=1$), and
$\\{X_{t}\\}_{t=1}^{\infty}$ is a sequence of independent and identically
distributed (i.i.d.) random variables with $X_{t}\sim P_{\theta}$.

###  3.3 Active information for Metropolis-Hastings systems in non-equilibrium

Suppose for simplicity that the sample space $\Omega$ is finite, and that the
states in $\Omega$ are listed in some order. Let

$\displaystyle\textbf{P}_{0}=(P_{0}(x);\,x\in\Omega)$ (17)

be a row vector of length $|\Omega|$ with all the null distribution
probabilities, and let

$\displaystyle\mathbf{\Pi}_{\theta}=\left(\pi_{\theta}(x,y);x,y\in\Omega\right)$
(18)

be a square matrix of order $|\Omega|$ that defines the transition kernel of
the Markov chain $\\{X_{t}\\}_{t=0}^{\infty}$ of Section 3.2. If $X_{0}\sim
P_{0}$, then by the Kolmogorov-Chapman equation $X_{t}\sim P_{\theta t}$,
where

$\displaystyle(P_{\theta t}(x);x\in\Omega)=\mathbf{P}_{\theta
t}=\mathbf{P}_{0}\mathbf{\Pi}_{\theta}^{t}.$ (19)

Hence, if $P=P_{\theta t}$, then $X=X_{t}$ corresponds to observing the Markov
chain at time $t$, under the alternative hypothesis $H_{1}$ in (3). Some basic
properties of the corresponding actinfo are summarized in the following
proposition:

######  Proposition 2.

Suppose $X=X_{t}$ is obtained by iterating $t$ times a Markov chain with
initial distribution (17) and transition kernel (18). The actinfo then equals

$I^{+}(\theta,t)=\log\frac{P_{\theta
t}(A)}{P_{0}(A)}=\log\frac{\mathbf{P}_{0}\mathbf{\Pi}_{\theta}^{t}\mathbf{v}}{\mathbf{P}_{0}\mathbf{v}},$
(20)

where $\mathbf{v}$ is a column vector of length $|\Omega|$ with ones in
positions $x\in A$ and zeros in positions $x\in A^{c}$. In particular,
$I^{+}(\theta,0)=0$ and

$\lim_{t\to\infty}I^{+}(\theta,t)=I^{+}(\theta).$ (21)

Therefore, $I^{+}(\theta,t)>0$ corresponds to knowledge of $f$ being used to
generate $t$ jumps of the Markov chain, under the alternative hypothesis
$H_{1}$ in (3).

###  3.4 Active information for Metropolis-Hastings systems with stopping

In Section 3.3, $P\sim P_{\theta t}$ was obtained by starting a random search
with null distribution $P_{0}$, and then iterating the Markov chain of Section
3.2 $t$ times. However, knowledge of $f$ can be utilized even more and stop
the Markov chain if the target $A$ in (5) is reached before time $t$. This can
be formalized by introducing the stopping time

$\displaystyle T=\min\\{t\geq 0;\,X_{t}\in A\\}$ (22)

and letting

$\displaystyle P_{\theta ts}(x)=P(X_{t\wedge T}=x)$ (23)

be the probability distribution of the stopped Markov chain $X_{t\wedge T}$,
with the last index $s$ in (23) being an acronym for stopping. In particular,

$\displaystyle P_{\theta ts}(A)=\sum_{x\in A}P_{\theta ts}(x)=P(T\leq t)$ (24)

is the probability of reaching the target $A$ for the first time after $t$
iterations or earlier. The theory of phase-type distributions can then be used
to compute the target probability $P_{\theta ts}(A)$ in (23) Asmussen et al.
(1996); Neuts (1981). To this end, clump all states $x\in A$ into one
absorbing state, and decompose the transition kernel in (18) according to

$\displaystyle\mathbf{\Pi}_{\theta}=\left(\begin{array}[]{cc}\mathbf{\Pi}_{\theta}^{\text{na}}&\mathbf{\Pi}^{\text{na,a}}_{\theta}\\\
\mathbf{0}&1\end{array}\right),$ (27)

where $\mathbf{\Pi}^{\text{na}}_{\theta}$ is a square matrix of order
$|A^{c}|$ containing the transition probabilities between all non-absorbing
states in $A^{c}$, whereas $\mathbf{\Pi}^{\text{na,a}}_{\theta}$ is a column
vector of length $|A^{c}|$ with transition probabilities $\pi(x,A)$ from all
the non-absorbing states $x\in A^{c}$ into the absorbing state $A$. Moreover,
$\mathbf{P}_{0}^{\text{na}}=\left(P_{0}(x);\,x\in A^{c}\right)$ is a row
vector of length $|A^{c}|$ that is the restriction of the start-distribution
$\mathbf{P}_{0}$ in (17) to all non-absorbing states. Then

$\displaystyle P_{\theta
ts}(A)=1-\mathbf{P}_{0}^{\text{na}}(\mathbf{\Pi}^{\text{na}}_{\theta})^{t}\mathbf{1},$
(28)

where $\mathbf{1}$ is a column vector of $|A^{c}|$ ones.

The actinfo $I^{+}_{s}$ of a search procedure with stopping is thus defined:

######  Proposition 3.

Suppose $X=X_{t}$ is obtained by iterating a Markov chain with initial
distribution (17) and transition kernel (18) (for some $\theta\geq 0$) at most
$t$ times, and stopping whenever the set $A$ is reached. Then the actinfo is
given by

$\displaystyle I^{+}_{s}(\theta,t)=\log\frac{P_{\theta
ts}(A)}{P_{0}(A)}=\log\frac{1-\mathbf{P}_{0}^{\text{na}}(\mathbf{\Pi}^{\text{na}}_{\theta})^{t}\mathbf{1}}{\mathbf{P}_{0}\mathbf{v}},$
(29)

with $\mathbf{P}_{0}$ and $\mathbf{v}$ as in Proposition 2, whereas
$\mathbf{P}_{0}^{\text{na}}$, $\mathbf{\Pi}_{\theta}^{\text{na}}$, and
$\mathbf{1}$ are defined below (27) and (28). This actinfo satisfies

$\displaystyle I^{+}_{s}(\theta,t)\geq I^{+}(\theta,t)$ (30)

and $I_{s}^{+}(\theta,t)$ is a non-decreasing function of $t$ such that

$\displaystyle\lim_{t\to\infty}I_{s}^{+}(\theta,t)=I_{f0}$ (31)

and

$\displaystyle\sum_{t=0}^{\infty}\left(1-P_{0}(A)e^{I^{+}_{s}(\theta,t)}\right)=E(T).$
(32)

Inequality (30) states that, for a search procedure with $t$ iterations,
knowledge about $f$ that is used for stopping the Markov chain in (18) will
increase the actinfo, regardless of whether knowledge about $f$ was used
($\theta>0$) or not ($\theta=0$) when iterating the Markov chain. Equation
(31) is a consequence of the fact that the target $A$ is reached eventually
with probability 1, so that the actinfo of a search procedure with stopping
equals the functional information $I_{f0}=-\log P_{0}(A)$ after many
iterations of the Markov chain. Moreover, equation (32) tells that the rate at
which $P_{0}(A)e^{I^{+}_{s}(\theta,t)}$ approaches 1 is determined by the
expected waiting time $E(T)$ of reaching the target.

From Proposition 3, actinfo for a system with stopping is closely related to
the phase-type distribution of the waiting time $T$ until the target is
reached. This has been studied in Hössjer et al. (2021), in the context of
gene expression of a number of genes, with $x$ the collection of regulatory
regions of all these genes.

##  4 Estimating active information and testing fine-tuning

Suppose the random search algorithm is repeated independently, under the same
conditions, $n$ times. For instance, suppose $\\{X_{it}\\}_{t=0}^{\infty}$
correspond to independent realizations $i=1,\ldots,n$ of a search algorithm.
The outomes of these independent searches are either $X_{i}=X_{it}$ or
$X_{i}=X_{i,t\wedge T_{i}}$, for $i=1,\ldots,n$, depending on whether the
search algorithm is stopped at a fixed time point $t$ or at random time points
$\\{T_{i}\\}_{i=1}^{n}$. In either case, an output of i.i.d random variables

$X_{1},\ldots,X_{n}\sim Q$ (33)

is obtained. These repeated outcomes of the search algorithm will be used to
test for and estimate the degree of fine-tuning. The methodology depends on
whether the null distribution $P_{0}$ is known or involves unknown nuisance
parameters.

###  4.1 Null distribution known

Suppose the null distribution $P_{0}$ is known. The sample in (33) is then
used for testing between the two hypotheses

$\displaystyle\begin{array}[]{ll}H_{0}:&Q=P_{0},\\\
H_{1}:&Q\in{\mathcal{P}}_{1},\end{array}$ (36)

with

${\mathcal{P}}_{1}=\\{P;\,P(A)\geq p_{\text{min}}\\}$ (37)

the set of distributions that correspond to fine-tuning. Suppose an estimate
$\hat{Q}(A)$ of the probability that $X\in A$ is computed from data (33), with
an associated empirical actinfo

$\displaystyle\hat{I}^{+}=\hat{I}^{+}_{n}=\log\frac{\hat{Q}(A)}{P_{0}(A)}.$
(38)

If $\hat{Q}(A)$ is a consistent estimator of $Q(A)$, then for large sample
sizes $\hat{I}^{+}$ will be close to

$\displaystyle I_{Q}^{+}=\log\frac{Q(A)}{P_{0}(A)},$ (39)

which equals 0 under $H_{0}$ and $I^{+}=I^{+}_{P}$ under $H_{1}$, for some
particular $P\in{\mathcal{P}}_{1}$. To test $H_{0}$ against $H_{1}$,

$\displaystyle\text{reject }H_{0}\text{ when }\hat{I}^{+}\geq I_{\text{min}},$
(40)

where $I_{\text{min}}$ is a pre-specified lower bound on the range of values
of the actinfo that correspond to FT.

####  4.1.1 Nonparametric estimator and test

From Section 3, $P=P_{\theta}$, $P=P_{\theta t}$ or $P=P_{\theta ts}$ involves
the tilting parameter $\theta$, and possibly also the number of iterations $t$
of the algorithm and a stopping time $T$. In this section, no other assumption
than $P\in{\mathcal{P}}_{1}$ is made on $P$, and a nonparametric version of
the empirical actinfo is used. The fraction

$\displaystyle\hat{Q}(A)=\frac{1}{n}\sum_{i=1}^{n}1_{\\{X_{i}\in A\\}}$ (41)

of random searches that fall into $A$ is used as an estimate of $Q(A)$.
Therefore, (41) only requires knowledge of the set $A$, not of the function
$f$.

The following result establishes asymptotic normality of the nonparametric
version of the estimator $\hat{I}^{+}$ in (38). Moreover, large deviations
Varadhan (1984) are used to show that the significance level of the
nonparametric version of the FT test (40) goes to zero exponentially fast with
$n$:

######  Proposition 4.

Suppose the empirical actinfo $\hat{I}_{n}^{+}$ in (38) is computed non-
parametrically, using (41) as an estimate of the target probability $Q(A)$.
Then $\hat{I}_{n}^{+}$ is an asymptotically normal estimator of $I^{+}_{Q}$ in
(39), in the sense that

$\displaystyle\sqrt{n}(\hat{I}^{+}_{n}-I^{+}_{Q})\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,V)\text{ as }n\to\infty,$ (42)

where $\stackrel{{\scriptstyle\cal L}}{{\longrightarrow}}$ refers to
convergence in distribution, and

$\displaystyle V=\frac{1-Q(A)}{Q(A)}$ (43)

is the variance of the limiting normal distribution. The significance level of
the test (40) for fine-tuning, with threshold $I_{\text{min}}$, satisfies

$\displaystyle\lim_{n\to\infty}-\frac{\log\left(P_{H_{0}}(\hat{I}_{n}^{+}\geq
I_{\text{min}})\right)}{n}=C,$ (44)

where

$\displaystyle
C=p_{\text{min}}\log\frac{p_{\text{min}}}{P_{0}(A)}+(1-p_{\text{min}})\log\frac{1-p_{\text{min}}}{1-P_{0}(A)}$
(45)

is the Kullback-Leibler divergence between Bernoulli distributions with
success probabilities $p_{\text{min}}=P_{0}(A)\exp(I_{\text{min}})$ and
$P_{0}(A)$ respectively.

######  Remark 1.

The conclusion of Proposition 4 is that the probability of observing actinfo
that corresponds to fine-tuning by chance decays at rate $e^{-Cn}$ when the
sample size $n$ gets large.

####  4.1.2 Parametric estimator and test

Suppose there is a priori knowledge that $P$ is close to the parametric
exponential family $\mathcal{P}$ of distributions in (10)-(12) for some value
$\theta>0$ of the tilting parameter. A parametric test of actinfo is naturally
defined. For this, compute first the maximum likelihood estimate

$\displaystyle\hat{\theta}=\hat{\theta}_{n}=\arg\max_{\theta\geq
0}\sum_{i=1}^{n}\log P_{\theta}(X_{i})$ (46)

of $\theta$, and use it to define a parametric estimate

$\displaystyle\hat{Q}(A)=P_{\hat{\theta}}(A)$ (47)

of the target probability $Q(A)$ that is inserted into (38) to define a
parametric version of the empirical actinfo $\hat{I}^{+}$. As opposed to (41),
the estimate (47) requires full knowledge of $f$.

To analyze the properties of the estimator (38) and test (40), introduce

$\displaystyle\theta^{\ast}=\arg\min_{\theta\geq
0}D_{KL}(Q~{}\|~{}P_{\theta}),$ (48)

where

$\displaystyle
D_{KL}(Q~{}\|~{}P_{\theta})=\sum_{x\in\Omega}Q(x)\log\frac{Q(x)}{P_{\theta}(x)}$
(49)

is the Kullback-Leibler divergence between $Q$ and $P_{\theta}$. From (48),
$P_{\theta^{\ast}}$ is the distribution in $\mathcal{P}$ that best
approximates $Q$. In particular, $\theta^{\ast}=\theta$ if $Q\in\mathcal{P}$
and $Q=P_{\theta}$ for some $\theta\geq 0$.

The following proposition shows that $\hat{I}^{+}$ is an asymptotically normal
estimator of $I^{+}(\theta^{\ast})$ in (13), which differs from $I_{Q}^{+}$ in
(39) whenever $Q\notin\mathcal{P}$. Moreover, the proposition also provides
large sample properties of the significance level of the test for actinfo:

######  Proposition 5.

Suppose the empirical actinfo $\hat{I}_{n}^{+}$ in (38) is computed
parametrically, using an estimate (47) of the target probability $Q(A)$. Then
$\hat{I}_{n}^{+}$ is an asymptotically normal estimator of
$I^{+}(\theta^{\ast})$, in the sense that

$\displaystyle\sqrt{n}\left(\hat{I}^{+}_{n}-I^{+}(\theta^{\ast})\right)\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,V)\text{ as }n\to\infty,$ (50)

where the variance of the limiting normal distribution is given by

$\displaystyle V=\frac{\text{Cov}^{2}_{P_{\theta^{\ast}}}\left[f(X)I(f(X)\geq
f_{0})\right]\text{Var}_{Q}\left[f(X)\right]}{P_{\theta^{\ast}}^{2}(A)\text{Var}^{\,\,2}_{P_{\theta^{\ast}}}[f(X)]}.$
(51)

Moreover, the significance level of the parametric test for fine-tuning, based
on (40) and (47), satisfies

$\displaystyle\lim_{n\to\infty}-\frac{\log\left[P_{H_{0}}\left(\hat{I}_{n}^{+}\geq
I_{\text{min}}\right)\right]}{n}=C,$ (52)

for

$\displaystyle C=\sup_{\phi>0}\left\\{\phi E_{P_{\text{min}}}[f(X)]-\log
M(\phi)\right\\},$ (53)

where $P_{\text{min}}=P_{\theta_{\text{min}}}$,
$\theta_{\text{min}}<\theta^{\ast}$ is the solution of
$P_{\theta_{\text{min}}}(A)=p_{\text{min}}=P_{0}(A)\exp(I_{\text{min}})$,
$M(\phi)$ is given by (11), whereas $p_{\text{min}}$ is defined in (37).

####  4.1.3 Comparison between nonparametric and parametric estimates of
actinfo

The two versions of empirical actinfo are complementary. The nonparametric
version is preferable in the sense that it makes less assumptions about the
distribution $P$ of the random algorithm under $H_{1}$, and in particular it
is a consistent estimator of $I_{Q}^{+}$ in (39). The parametric version of
$\hat{I}^{+}$, on the other hand, is preferable when $nQ(A)$ is small, since
it makes use of all data in order to estimate $Q(A)$, although it is not a
consistent estimator of $I_{Q}^{+}$ when $Q\notin\mathcal{P}$. The asymptotic
variances in (43) and (51), as well as the rates of exponential significance
level decrease in (45) and (53), agree when $Q=P_{\theta^{\ast}}$ and
$f(x)=f_{0}1_{\\{x\in A\\}}$, which is a special case of (8).

###  4.2 Null distribution unknown

Suppose the null distribution $P_{0}=P_{0\xi}$ involves an unknown nuisance
parameter $\xi\in\Xi$. The objective is then to test the two hypotheses

$\displaystyle\begin{array}[]{ll}H_{0}:&Q\in{\mathcal{P}}_{0},\\\
H_{1}:&Q\in{\mathcal{P}}_{1},\end{array}$ (56)

where the set of distribution under the null and alternative hypotheses equals

${\mathcal{P}}_{0}=\\{P_{0\xi};\,\xi\in\Xi\\}$ (57)

and (37) respectively.

####  4.2.1 One sample available

The actinfo

$I_{Q}^{+}=I_{Q}^{+}(\xi)=\log\frac{Q(A)}{P_{0\xi}(A)}$ (58)

cannot be consistently estimated if only one sample (33) is available. The
best that can be done is to estimate a lower bound

$\hat{I}^{+}=\hat{I}_{n}^{+}=\log\frac{\hat{Q}(A)}{P_{0\text{max}}(A)}$ (59)

of $I^{+}$, with $P_{0\text{max}}(A)$ defined in (4) and $\hat{Q}(A)$ an
estimate of $Q(A)$. This estimator will have an asymptotic bias

$B=I^{+}_{Q}(\xi^{\ast})-I_{Q}^{+}=\log\frac{P_{0\xi}(A)}{P_{0\text{max}}(A)}\leq
0,$ (60)

with $\xi^{\ast}$ the nuisance parameter that maxizes $P_{0\xi}(A)$ Hössjer et
al. (2022a). For the numerator of (59) either the nonparametric estimate of
$Q(A)$ in (41) can be used, or a parametric class

${\mathcal{P}}=\\{P_{\theta\xi};\,\theta\in\Theta,\xi\in\Xi\\}$

of distributions can be used that involves a tuning parameter vector $\theta$
and a vector of nuisance parameters $\xi$. If $Q$ is thought to be close to
${\cal P}$, the parametric estimate

$\hat{Q}(A)=P_{\hat{\theta}\hat{\xi}}(A)$ (61)

of $Q(A)$ is used that generalizes (47), with

$(\hat{\theta},\hat{\xi})=\arg\max_{\theta,\xi}\sum_{i=1}^{n}\log
P_{\theta\xi}(X_{i}).$ (62)

When the sample size $n$ tends to infinity, the estimator (62) will converge
to

$(\theta^{\ast},\xi^{\ast})=\arg\min_{\theta,\xi}D_{KL}(Q~{}\|~{}P_{\theta\xi}).$
(63)

The following result is an extension of Propositions 4-5, when nuisance
parameters $\xi$ are added and a general type of tuning parameter $\theta$
(not necessarily a scalar tilting parameter) is used:

######  Proposition 6.

Suppose the null distribution $P_{0}=P_{0\xi}$ involves an unknown parameter
$\xi$ and the actinfo $I_{Q}^{+}$ in (58) is estimated by $\hat{I}_{n}^{+}$ in
(59), using an estimator $\hat{Q}(A)$ of the target probability $Q(A)$ that is
either nonparametric (41) or parametric (61). Given these assumptions,
$\hat{I}_{n}^{+}$ is an asymptotically normal estimator, in the sense that

$\sqrt{n}(\hat{I}^{+}_{n}-I_{Q}^{+}-B)\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,V)\text{ as }n\to\infty.$ (64)

The asymptotic bias $B$ in (64) is defined in (60) whereas the asymptotic
variance $V$ is defined in (43) for the nonparametric estimator of
$I_{Q}^{+}$, whereas

$\begin{array}[]{rcl}V&=&E[\psi_{\theta^{\ast}\xi^{\ast}}(X)|X\in
A]E[\psi_{\theta^{\ast}\xi^{\ast}}^{\prime}(X)]^{-1}E[\psi^{T}_{\theta^{\ast}\xi^{\ast}}(X)\psi_{\theta^{\ast}\xi^{\ast}}(X)]\\\
&\cdot&E[(\psi_{\theta^{\ast}\xi^{\ast}}^{\prime})^{T}(X)]^{-1}E[\psi_{\theta^{\ast}\xi^{\ast}}(X)|X\in
A]^{T}\end{array}$ (65)

for the parametric estimator of $I_{Q}^{+}$, with $\psi_{\theta\xi}(x)=d\log
P_{\theta\xi}(x)/d(\theta,\xi)$, $(\theta^{\ast},\xi^{\ast})$ defined as in
(63), and $T$ refering to matrix transposition. Moreover, the significance
level of the test (40) of FT, with threshold $I_{\text{min}}$, satisfies

$\displaystyle\lim_{n\to\infty}-\frac{\log\left[P_{0\xi}\left(\hat{I}_{n}^{+}\geq
I_{\text{min}}\right)\right]}{n}=C,$ (66)

with

$C=p_{\text{min}}e^{-B}\log\frac{p_{\text{min}}e^{-B}}{P_{0\xi}(A)}+(1-p_{\text{min}}e^{-B})\log\frac{1-p_{\text{min}}e^{-B}}{1-P_{0\xi}(A)}$
(67)

for the nonparametric version of the test, with
$p_{\text{min}}=P_{0\xi}(A)\exp(I_{\text{min}})$. For the parametric versions
of the FT-test, and in the special case when $\theta$ is a scalar exponential
tilting parameter, $C$ is given by (53), with
$P_{\text{min}}=P_{\theta_{\mbox{\tiny min}}\xi}$, and $\theta_{\text{min}}$
the solution of $P_{\theta_{\mbox{\tiny min}}\xi}(A)=p_{\text{min}}e^{-B}$.

######  Remark 2.

The negative bias term $B$ makes the test of FT in Proposition 6 more
conservative than the tests in Propositions 4-5. This can be seen, for
instance, by comparing the two large deviation rates $C$ in (45) and (67). The
rate in (67) is larger, since $p_{\text{min}}$ is multiplied by a term
$e^{-B}$. This corresponds to the fact that to falsely reject $H_{0}$ in
Proposition 6 is more difficult.

####  4.2.2 Two samples available

In addition to the first sample (33), suppose a second sample

$X_{01},\ldots,X_{0n_{0}}\sim P_{0\xi}$ (68)

of $n_{0}$ i.i.d. observations under the null distribution is available. A
consistent estimator

$\hat{I}^{+}=\hat{I}^{+}_{nn_{0}}=\log\frac{\hat{Q}(A)}{P_{0\hat{\xi}}(A)}$
(69)

of $I_{Q}^{+}$ in (58) is then available, with

$\hat{\xi}=\arg\max_{\xi}\sum_{i=1}^{n_{0}}\log P_{0\xi}(X_{0i}).$ (70)

The following result provides asymptotic properties of the estimator (69) of
actinfo, and the corresponding test (40) of FT with threshold
$I_{\text{min}}$:

######  Proposition 7.

Suppose the null distribution $P_{0}=P_{0\xi}$ involves an unknown nuisance
parameter $\xi$, and that the active information $I_{Q}^{+}$ in (58) is
estimated by $\hat{I}_{nn_{0}}^{+}$ in (69), making use of two samples (33)
and (68), of sizes $n$ and $n_{0}$, from $Q$ and $P_{0\xi}$ respectively.
Assume further that the estimator $\hat{Q}(A)$ of $Q(A)$ is either
nonparametric (41) or parametric (61). If $n,n_{0}\to\infty$ in such a way
that

$\frac{n}{n_{0}}\to\lambda>0,$ (71)

then

$\sqrt{n}(\hat{I}^{+}_{nn_{0}}-I_{Q}^{+})\,\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,V_{1}+\lambda V_{2}),$ (72)

where

$V_{2}=E[\psi_{\xi}(X)|X\in
A]E[\psi_{\xi}^{T}(X)\psi_{\xi}(X)]^{-1}E[\psi_{\xi}(X)|X\in A]^{T},$ (73)

and $\psi_{\xi}(x)=d\log P_{0\xi}(x)/d\xi$. If the nonparametric estimator of
$Q(A)$ is used, then $V_{1}$ equals $V$ in (43), whereas if the parametric
estimator $Q(A)$ is used, then $V_{1}$ equals $V$ in (65). The significance
level of the test (40) of FT, with threshold $I_{\text{min}}$, satisfies the
same type of large deviation result (66) as in Proposition 6, for the
nonparametric and parametric versions of the test (in the latter case assuming
that $\theta$ is a scalar tilting parameter), but in the definitions of the
nonparametric and parametric large deviation rates $C$, the bias term $B=0$.

##  5 Examples

######  Example 1 (Cosmology Díaz-Pachón et al. (2021, 2022)).

Suppose there is a positive constant of nature $X\in\Omega={\mathbb{R}}^{+}$,
a life-permitting interval $A\subset\Omega$, and a specificity function (6)
that equals 1 inside $A=(a,b)$ and zero elsewhere. The maximum entropy
distribution under a first moment constraint $\xi=E(X)$ is exponential with
expected value. Consequently,

$P_{0\xi}(A)=\frac{1}{\xi}\int_{a}^{b}e^{-x/\xi}dx.$

The null and alternative hypotheses for the fine-tuning test are given in
(56), where under $H_{1}$ the agent brings about a life-permitting value of
$X$ with probability 1 ($P(A)=1$). Only one universe is observed, with a value
$X=X_{1}$ of the constant. Therefore, there is a sample (33) of size $n=1$,
whereas no null sample (68) is available. Since $X_{1}\in A$ is life-
permitting, $\hat{Q}(A)=1$. The estimate (59) of actinfo then simplifies to

$\hat{I}^{+}=\log\frac{1}{P_{0\text{max}}(A)}=-\log P_{0\text{max}}(A).$ (74)

Let $x=(a+b)/2$ be the midpoint of the LPI and suppose that half of its
relative size $\epsilon=(b-a)/(2x)$ is small. The probability in (74) is then
approximated by

$P_{0\text{max}}(A)\approx(b-a)\max_{\xi>0}\frac{e^{-x/\xi}}{\xi}\approx
2\epsilon e^{-1}.$

From (74) the estimated actinfo

$\hat{I}^{+}\approx 1-\log(\epsilon)-\log(2)$

is a monotone decreasing function of $\epsilon$.

######  Example 2 (Evaluation of student test scores Hössjer et al. (2022b)).

Suppose a number of students perform a test. Let
$x=(z,y)=(z_{1},\ldots,z_{d-1},y)\in{\mathbb{R}}^{d}$ summarize the
chararcteristics of a student with covariates $z$ that are used to predict the
outcome $y$ of the test. The specificity function $f(x)=x_{d}=y$ equals the
student’s test score, and (5) corresponds to the set of students that pass the
test, with a minimally allowed score of $f_{0}$. The population of students
follows a $(d-1)$-dimensional multivariate normal distribution $Z\sim
N(\mbox{\boldmath$m$},\mbox{\boldmath$\Sigma$})$, where
$\mbox{\boldmath$m$}=(m_{1},\ldots,m_{d-1})$ and
$\mbox{\boldmath$\Sigma$}=(\sigma_{jk})_{j,k=1}^{d-1}$ are known. The
conditional distribution of the response follows a multiple linear regression
model

$Y|Z=z\sim
N\left(\xi_{0}+\sum_{j=1}^{d-1}\xi_{j}z_{j}+t(\theta_{0}+\sum_{j=1}^{d-1}\theta_{j}z_{j}),\sigma^{2}\right),$

for a student with covariate vector $z$ who prepared for the test for a period
of length $t$. The nuiscance parameter vector
$\xi=(\xi_{0},\ldots,\xi_{d-1},\sigma^{2})$ involves the error variance and
the regression parameters for students who did not train for the test, whereas
the tuning parameter vector $\theta=(\theta_{0},\ldots,\theta_{d-1})$ involves
the regression parameters that correspond to the effect of preparing for the
test. The unconditional distribution of the response is normal, $Y\sim
N(\mu,V)$, with

$\begin{array}[]{rcl}\mu&=&\mu(\theta,\xi,t)=(\xi_{0}+t\theta_{0})+\sum_{j=1}^{d-1}(\xi_{j}+t\theta_{j})m_{j},\\\
V&=&V(\theta,\xi,t)=\sigma^{2}+\sum_{j,k=1}^{d-1}(\xi_{j}+t\theta_{j})(\xi_{k}+t\theta_{k})\sigma_{jk}.\end{array}$

Therefore, the probability, for a randomly chosen student, that studied for
the test for a period of length $t$, to pass is

$P(A)=P_{\theta\xi t}(A)=P(Y\geq
f_{0})=1-\Phi\left(\frac{f_{0}-\mu}{\sqrt{V}}\right),$ (75)

where $\Phi$ is the cumulative distribution function of a standard normal
distribution. The null distribution $P_{0}=P_{0\xi}$ corresponds to putting
$t=0$ in (75). Thus the actinfo

$I^{+}=I^{+}(\theta,\xi,t)=\log\frac{1-\Phi\left((f_{0}-\mu(\theta,\xi,t)/\sqrt{V(\theta,\xi,t)}\right)}{1-\Phi\left((f_{0}-\mu(0,\xi,0)/\sqrt{V(0,\xi,0)}\right)}$
(76)

quantifies how much learning, during a period of length $t$, increases the
probability of passing the test. To compute an estimate $\hat{I}^{+}$ of
$I^{+}$ in (76), estimates $\hat{\xi}$ and $\hat{\theta}$ of $\xi$ and
$\theta$ are needed. This can be done by collecting two training samples, as
in (69). Another option is computing least squares estimates of the nuisance
and tuning parameters $(\xi,\theta)$ jointly, without bias, from one single
data set $\\{(t_{i},z_{i},y_{i})\\}_{i=1}^{n}$, provided that the time periods
$t_{i}$ vary, so that all parameters are identifiable.

######  Example 3 (Reinforcement learning (RI) Kaelbling et al. (1996)).

Consider an agent whose purpose is to maximize the reward $f(x)$ of a
trajectory $x$ that he to some extent will be able to control, for a time
period of length $t$. At each time point $u$ there are $m$ possible
environments ${\cal S}=\\{s_{1},\ldots,s_{m}\\}$ and $q$ possible actions
${\cal A}=\\{a_{1},\ldots,a_{q}\\}$ to take. The state space ${\cal X}={\cal
A}^{t}\times{\cal S}^{t+1}$ consists of all possible trajectories

$x=(a_{0},\ldots,a_{t-1},s_{0},\ldots,s_{t})$

of environments and actions, where $s_{u}$ is the environment and $a_{u}$ the
action taken at time $u$. A corresponding random trajectory is denoted with
capital letters

$X=(A_{0},\ldots,A_{t-1},S_{0},\ldots,S_{t}).$

If the environment of the system is $S_{u}=s$ at time $u$, and action
$A_{u}=a$ is taken, the probability of moving to environment $s^{\prime}$ is
$P_{a}(s,s^{\prime})=P(S_{u+1}=s^{\prime}|S_{u}=s,A_{u}=u)$, with an
instantaneous reward of $R_{a}(s,s^{\prime})$. If future rewards are
discounted by a factor $\gamma$, the total reward, over a time horizon of
length $t$, is

$f(x)=\sum_{u=0}^{t}R_{a_{u}}(s_{u},s_{u+1})\gamma^{u}.$

Let $f_{0}$ be a lower bound for a trajectory’s total discounted reward to be
acceptable, so that $A$ in (5) is the set of all acceptable trajectories. The
agent takes action according to some policy to make the expected total reward
of a trajectory as large as possible. To this end consider stationary
policies, where the action $A_{u}$ taken by the agent at each time point $u$
is only determined by the current environment $s_{u}$, according to some
matrix $\mbox{\boldmath$\Pi$}=(\pi(s,a);s\in{\cal S},a\in{\cal A})$ of
transition probabilities $\pi(s,a)=P(A_{u}=u|S_{u}=s)$. For a completely
random policy

$\pi(s,a)=\xi_{a};\quad a=1,\ldots,q,$

the action is not influenced by the current environment, and it is completely
specified by the vector $\xi=(\xi_{1},\ldots,\xi_{q})$ of nuisance parameters.
Thus $P_{0}(A)=P_{0\xi t}(f(X)\geq f_{0})$ is the probability that an ignorant
agent with policy determined by $\xi$, will have an acceptable trajectory. An
agent who knows the reward function $R_{a}$ and the dynamics $P_{a}$ of the
environment, will try to take this knowledge into account to formulate a
policy that makes the reward as large as possible. A deterministic policy
$\theta:{\cal S}\to{\cal A}$ is a function that to each environment takes a
unique action, so that

$\pi(s,a)=1_{\\{a=\theta(s)\\}}.$

Thus $P(A)=P_{\theta t}(f(X)\geq f_{0})$ is the probability that an agent with
deterministic policy $\theta$ obtains an acceptable trajectory. The active
information

$I^{+}=I^{+}(\theta,\xi,t)=\log\frac{P_{\theta}(\sum_{u=0}^{t}R_{A_{u}}(S_{u},S_{u+1})\gamma^{u}\geq
f_{0})}{P_{0\xi}(\sum_{u=0}^{t}R_{A_{u}}(S_{u},S_{u+1})\gamma^{u}\geq f_{0})}$
(77)

quantifies, on a logarithmic scale, how much more likely it is for an agent
with policy $\theta$ to obtain an acceptable trajectory, compared to an
ignorant agent with policy $\xi$. The values $\xi$ and $\theta$ are varied
during the exploration phase of RI, but they are assumed to be known during
the exploitation phase of RI. Suppose we want to compute the actinfo (77)
during the expoitation phase. Since $P_{0}(A)$ and $P(A)$ are typically
unknown, they have to be estimated by Monte Carlo. To this end, assume we have
two samples (33) and (68) of $n$ and $n_{0}$ trajectories available, from
$Q=P_{\theta t}$ and $Q=P_{0\xi t}$ respectively. Then $\hat{I}^{+}$ in (69)
can be used to estimate the actinfo (77).

######  Example 4 (Molecular machines and Moran models Thorvaldsen and Hössjer
(2020); Hössjer et al. (2021); Montañez (2018)).

Suppose $\Omega$ consists of all $2^{d}$ binary sequences
$x=(x_{1},\ldots,x_{d})$ of length $d$, with a null distribution $P_{0}(x)$
that will be chosen below. The specificity function $f$ is defined as

$\displaystyle f(x)=\left\\{\begin{array}[]{ll}a|x|,&x\neq(1,\ldots,1),\\\
1,&x=(1,\ldots,1),\end{array}\right.$ (80)

where $|x|=\sum_{i=1}^{d}x_{i}$ and $a\leq 1/d$ is a fixed parameter. We
regard $x$ as a molecular machine with $d$ parts, with $x_{i}=1$ or 0
depending on whether part $i$ functions or not. The specificity $f(x)$
quantifies how well the machine works, for instance its ability to regulate
activity in vitro or in vivo in a living cell. It is assumed that $f(x)$ is
determined by the number $|x|$ of functioning parts, with a maximal value
$f_{\text{max}}=f(1,\ldots,1)=1$. Using (8), the most stringent definition of
high specificity, it follows that $A=\\{(1,\ldots,1)\\}$ only contains one
element, a molecular machine for which all parts are in shape. The parameter
$a$ is crucial. If $0<a\leq 1/d$, it follows that a molecular machine works
better the more of the parts that are in shape. On the other hand, if $a<0$,
then a molecular machine with some parts in shape, but not all, functions
worse the more of the parts that are in shape, since all units must work in
order for the whole machine to function, and there is a cost $-a$ associated
with carrying each part that is in shape, as long as the whole system does not
function.

Each state $x$ is interpreted as a population of $N$ subjects, all having the
same variant $x$ of the molecular machine. With this interpretation, $X=X_{t}$
is the outcome of a random evolutionary process where all subjects of the
population, at any time point $t$, have the same state. But this state may
vary over time when all subjects of population simultaneously experience the
same change. The question of interest is whether this process can modify the
population so that all its members have a functioning molecular machine. A
transition of this process from $x$ is caused by a mutation with distribution
$q(x,\cdot)$, where $q(x,x)=0$. Suppose a mutation from $x$ to $y$ is
possible, i.e., $q(x,y)>0$. A mutation from $x$ to $y$ first occurs in one
individual and then it either (momentarily) dies out with probability
$1-\alpha_{\theta}(x,y)$ or it (momentarily) spreads to the whole population
(gets fixed) with probability

$\displaystyle\alpha_{\theta}(x,y)=C\cdot\left(\frac{e^{\theta
f(y)}P_{0}(y)q(y,x)}{e^{\theta f(x)}P_{0}(x)q(x,y)}\right)^{1/2},$ (81)

where

$\displaystyle C=\left(\max_{x,y}\frac{e^{\theta
f(y)}P_{0}(y)q(y,x)}{e^{\theta f(x)}P_{0}(x)q(x,y)}\right)^{-1/2}$ (82)

is a constant assuring that (81) never exceeds 1, and the maximum is taken
over all $x,y$ such that $x\neq y$ and both of $q(x,y)$ and $q(y,x)$ are
positive. The Markov chain with transition probabilities (14) and acceptance
probability (81) represents the dynamics of the evolutionary process.

As shown in Section 7, the equilibrium distribution of this Markov chain is
given by $P_{\theta}$ in (10). In particular, Propositions 2–3 remain valid
when the Markov chain (14) with acceptance probabilities (81) are used, rather
than (15). We will interpret

$\displaystyle s(x)=e^{\theta f(x)/N}$ (83)

as the selection coefficient or fitness of individuals with a molecular
machine of type $x$, that is, $s(x)$ is proportional to the fertility rate of
individuals of type $x$.

The MH-type Markov chain with acceptance probability (81)–(82) represents an
evolutionary process that closely resembles a Moran model with selection
Durrett (2008); Moran (1958a, b), which is frequently used for describing
evolutionary processes (see Section 7). The Moran model is a continuous time
Markov chain for a population with overlapping generations where individuals
die at the same rate, and are replaced by offspring of individuals in the
population proportionally to their selection coefficients $s(x)$. New types
arise when an offspring of parents of type $x$ mutate with probability
$\mu(x)$. If the mutation rate is small ($\mu(x)\ll N^{-1}$ for all
$x\in\Omega$), then to a good approximation the whole population will have the
same type at any point in time, a so called fixed state assumption.

Even though the Moran model is specified in continuous time, time can be
discretized as $t=0,1,2,\ldots$ by only recording the population when
individuals die. If individuals die at rate 1, then the next individual dies
at rate $N$, so that time is counted in units of $N^{-1}$ generations. The
fixed state assumption is motivated by assuming that newborn offspring with a
new mutation either dies out or spreads to the whole population (get fixed in
the population) right after birth. In this context, $q$ corresponds to the way
in which mutations change the type of the individual, whereas
$\alpha_{\theta}=\alpha_{\theta N}$ is the probability of fixation. If
$q(x,y)$ is the conditional probability that an offspring of a type $x$ parent
mutates to $y$, given that a mutation occurs, then the proposal kernel of the
Moran model is

$\displaystyle
q^{\text{Moran}}(x,y)=\left\\{\begin{array}[]{ll}\mu(x)q(x,y),&x\neq y,\\\
1-\mu(x),&x=y.\end{array}\right.$ (86)

As shown in Section 7, the acceptance (or fixation) probability of the Moran
model is

$\displaystyle\alpha^{\text{Moran}}_{\theta
N}(x,y)\approx\frac{1}{N}\left(1+\frac{\theta[f(y)-f(x)]}{2}\right)\approx\frac{1}{N}\left(\frac{e^{\theta
f(y)}}{e^{\theta f(x)}}\right)^{1/2}$ (87)

when $\theta[f(y)-f(x)]$ is small. From (86)-(87), the Moran model
approximates the Metropolis-Hastings kernel with acceptance probabilities
(81)-(82) with good accuracy when i) $\mu(x)\equiv\mu$, ii) $P_{0}$ is uniform
and iii) the proposal kernel $q$ is symmetric (i.e. $q(x,y)=q(y,x)$), although
the time scales of the two processes are different. More specifically, if
i)-iii) hold, a time-shifted version of the Moran model approximates the MH-
type model with acceptance probabilities (81)-(82), so that each time step of
the MH-type Markov chain corresponds to $C/\mu$ generations of a Moran model.
However, even under assumptions i)-iii) the stationary distribution of the
Moran model differs slightly from $P_{\theta}$.

The proposal kernel $q(x,y)$ is assumed to be local and satisfying

$\displaystyle
q(x,y)=\left\\{\begin{array}[]{ll}b/[|x|+b(d-|x|)],&y=x+e_{j},x_{j}=0,\\\
1/[|x|+b(d-|x|)],&y=x+e_{j},x_{j}=1,\\\
0,&\text{otherwise},\end{array}\right.$ (91)

where $e_{j}=(0,\ldots,0,1,0,\ldots,0)$ is a row vector of length $d$ with a 1
in position $j\in\\{1,\ldots,d\\}$ and zeros elsewhere, whereas $x+e_{j}$
refers to component-wise addition modulo 2, corresponding to a switch of
component $j$ of $x$. A change of component $j$ from 0 to 1 is caused by a
beneficial mutation, whereas a change from 1 to 0 corresponds to a deleterious
mutation. Consequently, $b>0$ is the ratio between the rates at which
beneficial and deleterious mutations occur.

The kernel $q$ in (91) is symmetric only when beneficial and deleterious
mutations have the same rate ($b=1$). The more general case of asymmetric $q$
is handled differently by the MH-type algorithm and the Moran model. Whereas
the MH-type algorithm elevates the acceptance probability (81) of seldom-
proposed states $y$ (those $y$ for which $q(x,y)$ is small for many $x$), this
is not the case for the acceptance probability (87) of the Moran model. To
avoid that these states $y$ are reached too often by the MH-type algorithm,
the null distribution $P_{0}$ of no selection has to be chosen so that
$P_{0}(y)$ is small for rarely proposed states (whereas the Moran model needs
no such correction). Therefore $P_{0}$ in (81) will be chosen as the
stationary distribution of a transition kernel (14) for which $\theta=0$ and
all candidates are accepted ($\alpha_{0}(x,y)=1$). That is, if
$\tilde{\mathbf{\Pi}}_{0}$ refers to the transition matrix of such a Markov
chain, the initial distribution $\mathbf{P}_{0}$ in (17) is chosen as the
solution of

$\displaystyle\left\\{\begin{array}[]{ll}\mathbf{P}_{0}=\mathbf{P}_{0}\tilde{\mathbf{\Pi}}_{0},\\\
\sum_{x\in\Omega}P_{0}(x)=1.\end{array}\right.$ (94)

The null distribution $P_{0}=P_{0b}$ in (94) involves one single nuisance
parameter $\xi=b$. In the special case when beneficial and deleterious
mutations have the same rate ($b=1$), this procedure generates a uniform
distribution $P_{0}(x)\equiv 2^{-d}$. On the other hand, states $x$ with many
functioning parts will be harder to reach by the Markov process
$\tilde{\mathbf{\Pi}}_{0}$ when beneficial mutations occur less frequently
than deleterious ones ($0<b<1$), resulting in smaller values of $P_{0}(x)$.
The distribution under the alternative hypothesis, $P=P_{\tilde{\theta}bt}$,
involves the nuisance parameter $b$, the time point $t$ at which the state of
the population is recorded, and $\tilde{\theta}=(a,\theta)$, the two
parameters that determine how much background information the MH-type
evolutionary algorithm makes use of. For simplicity $a$ and $b$ are here
regarded as constants and we only include $\theta$ and $t$ in the notation.
This gives rise to an active information

$I^{+}(\theta,t)=\log\frac{P_{\theta}\left(X_{t}=(1,\ldots,1)\right)}{P_{0}\left(X_{t}=(1,\ldots,1)\right)}.$
(95)

The MH-type algorithm is studied for $d=5$, and illustrated in Figures 1-3.
Note that the functional information $I_{f0}$ is a decreasing function of $b$,
since it is more surprising to find a working molecular machine by chance when
the rate of beneficial mutations $b$ is small. Moreover, the active
information $I^{+}(\theta)=\lim_{t\to\infty}I^{+}(\theta,t)$ for the
equilibrium distribution of the Markov chain as well as the active
informations $I^{+}(\theta,t)$ and $I_{s}^{+}(\theta,t)$ for a system in non-
equilibrium, without and with stopping, are increasing functions of $\theta$,
and decreasing functions of $a$ and $b$. The smaller $a$ or $b$ is, the more
external information can be infused to increase the probability of reaching
the fine-tuned state of a working molecular machine $(1,\ldots,1)$. When $a$
is small, to leave this state once it is reached becomes more difficult, and
consequently $I_{s}^{+}(\theta,t)$ is only marginally larger than
$I(\theta,t)$.

Figure 1: Plot of $I^{+}(\theta)=\lim_{t\to\infty}I^{+}(\theta,t)$ in (95) as
a function of $\theta$ for a system of molecular machines with transition
kernel (81), proposal distribution (91), and null distribution (94). The
system has $d=5$ components, $b=1.0$, and $a=-0.2$ (dash-dotted), $a=0$
(solid) and $a=0.2$ (dashed). The horizontal dotted line corresponds to the
functional information $I_{f0}=3.47$. Figure 2: Plot of
$I^{+}(\theta)=\lim_{t\to\infty}I^{+}(\theta,t)$ in (95) as a function of
$\theta$ for a system of molecular machines with transition kernel (81),
proposal distribution (91), and null distribution (94). The system has $d=5$
components, $b=0.5$, and $a=-0.2$ (dash-dotted), $a=0$ (solid) and $a=0.2$
(dashed). The horizontal dotted line corresponds to the functional information
$I_{f0}=5.09$.

Figure 3: Plot of $I^{+}(\theta,t)$ in (95) (dashed) and $I^{+}_{s}(\theta,t)$
(solid) as a function of $t$ for a system of molecular machines with
transition kernel (81), proposal distribution (91), and null distribution
(94). The system has $d=5$ components and $\theta=2.5$. The upper (lower) row
corresponds to $b=1$ ($b=0.5$), whereas the left (right) column corresponds to
$a=0.2$ ($a=-0.2$). The horizontal lines in each figure illustrate
$I^{+}(\theta)$ (dash-dotted) and the functional information $I_{f0}$
(dotted).

######  Example 5 (Evolutionary programming algorithms).

Suppose $\Omega=\Omega_{\text{ind}}^{N}$ is a set of genetic variants from
some genomic region, $x=(x_{1},\ldots,x_{N})$, for the members of a population
of size $N$. That is, $x_{k}\in\Omega_{\text{ind}}$ is the variant of this
genomic region for individual $k$. If, for instance, the region codes for the
molecular machine of Example 4, we let
$x_{k}=(x_{k1},\ldots,x_{kd})\in\\{0,1\\}^{d}=\Omega_{\text{ind}}$, with
$x_{kj}=1$ or 0 depending on whether component $j$ of this machine works or
not for individual $k$. Let $g(x_{k})$ be the biological fitness, or expected
number of offspring, of $k$. In the context of molecular machines, the
logarithm of $g(x_{k})$ could be a function of the number of functioning parts
of a machine of type $x_{k}$. The specificity function of a population in
state $x$ is the average fitness

$f(x)=\frac{1}{N}\sum_{k=1}^{N}g(x_{k})$

of its individuals. The targeted set $A$ in (5) corresponds to all genetic
profiles with an average fitness at least $f_{0}$. This type of model is
frequently used in genetic programming as well as in other types of
evolutionary programming algorithms to mimic the evolution of $N$ individuals
over time Mitchell (1996); Vikhar (2016). Typically, the output $X=X_{t}$ of
the evolutionary algorithm is the last step of a simulation
$\\{X_{s}=(X_{s1},\ldots,X_{sN})\\}_{s=0}^{t}$ of the population over $t$
generations. Once the distributions $P_{0}=P_{0\xi t}$ and $P=P_{\theta\xi t}$
of $X$ are found under the null hypothesis $H_{0}$ and the alternative
hypothesis $H_{1}$, the actinfo $I^{+}$ can be computed, according to (1).
This actinfo quantifies, on a logarithmic scale, how much more likely it is
for the average fitness of the population to exceed $f_{0}$ at time $t$, for a
population with externally infused information ($H_{1}$) compared to an
evolutionary process where no such external information is used ($H_{0}$). For
instance, if a molecular machine needs all its parts in order to function
($g(x_{k})=1(|x_{k}|=d)$), then the actinfo at time $t$ equals

$I^{+}=I^{+}(\theta,\xi,t)=\log\frac{P_{\theta\xi}\left(|\\{k;\,1\leq k\leq
N,X_{tk}=(1,\ldots,1)\\}|\geq f_{0}N\right)}{P_{0\xi}\left(|\\{k;\,1\leq k\leq
N,X_{tk}=(1,\ldots,1)\\}|\geq f_{0}N\right)}.$ (96)

Since the state space $\Omega$ is very large, it is often complicated to find
explicit, analytical expressions for the actinfo $I^{+}$ in (96). Suppose the
nuisance parameters $\xi$ of the null distribution $P_{0}=P_{0\xi}$ are known.
This makes the framework of Section 4.1 applicable, running the evolutionary
algorithm $n$ times. That is, $n$ i.i.d. copies $\\{X_{is}\\}_{s=0}^{t}$ of
the population trajectory are generated up to time $t$ for $i=1,\ldots,n$.
Then $X_{i}=X_{it}=(X_{it1},\ldots,X_{itN})$, $i=1,\ldots,n$, are used for
computing an estimate $\hat{I}_{n}^{+}$ of the actinfo, and test for fine-
tuning, according to Section 4.1.

Recall the fixed state assumption of Example 4, whereby all individuals of the
population, at any time point, have the same state. Such an assumption is only
realistic when $N\mu\ll 1$, that is, when either the mutation rate $\mu$
and/or the population size $N$ is small. It corresponds to a scenario where
$P_{0}$ and $P$ put all their probability masses along the diagonal

$\displaystyle\Omega_{\text{diag}}=\\{x\in\Omega;\,x_{1}=\ldots=x_{N}\\}$ (97)

of $\Omega$. Since (97) is equivalent to the reduced state space
$\Omega_{\text{ind}}$, the fixed state assumption greatly simplifies the
analysis. For instance, it often makes it possible to find analytical
expressions for the actinfo $I^{+}$, rather than having to estimate it.

##  6 Discussion

In this article a general statistical framework is provided for using active
information to quantify the amount of pre-specified external knowledge an
algorithm makes use of, or equivalently, how tuned the algorithm is. The
theory is based on quantifying, for each state $x$, how specified it is by
means of a real-valued function $f(x)$. An algorithm with external information
either makes use of knowledge of $f$ directly, or at least it incorporates
knowledge that tends to move the output of the algorithm towards more
specified regions. The Metropolis-Hastings Markov chain incorporates knowledge
of $f$ directly, in terms of the acceptance probability of proposed moves. The
learning ability of this algorithm was analyzed by studying its active
information, with or without stopping, when the targeted set of highly
specified states is reached. When independent outcomes of an algorithm are
available, nonparametric and parametric estimators of the actinfo of the
algorithm were also developed, as well as nonparametric and parametric tests
of FT.

This work can be extended in different ways. A first extension is to find
conditions under which the actinfo $I^{+}(\theta,t)$ of a stochastic algorithm
based on a random start (according to the null distribution of a non-guided
algorithm) followed by $t$ iterations of the Metropolis-Hastings Markov chain
(without stopping) is a non-decreasing function of $t$. We conjecture that
this is typically the case but have not obtained any general conditions on the
distribution $q$ of proposed candidates for this result to hold.

A second extension is to widen the notion of specificity, so that not only the
functionality $f(x)$ but also the rarity $P_{0}(x)$ of the outcome $x$ under
the null distribution is taken into account. A class of such specificity
functions is

$\displaystyle g_{\theta}(x)=\theta f(x)-\log P_{0}(x),$ (98)

where $\theta>0$ is a parameter that controls the tradeoff between scenarios
where either functionality or rarity under the null is the most important
determinant of specificity. The case $\theta=0$ in (98) corresponds to
function having no impact, so that $g_{0}(x)$ reduces to Shannon’s self
information of $x$. The case $g_{1}(x)$ was proposed in Montañez (2018),
whereas $g_{\theta}(x)$ is solely determined by $f(x)$ in the limit when
$\theta$ gets large.

A third extension is to generalize the notion of actinfo to include not only
the probability of reaching a targeted set of highly specified states $A$
under $H_{0}$ and $H_{1}$, but also account for the conditional distribution
of the states within $A$, given that $A$ has been reached. This is related to
the way in which functional sequence complexity generalizes functional
information Abel and Trevors (2005); Durston and Chiu (2005, 2011); Durston et
al. (2007). Let $H(Q)=-\sum_{x}Q(x)\log[Q(x)]$ refer to the Shannon entropy of
a distribution $Q$, whereas $H(Q_{A})$ is the Shannon entropy of the
corresponding conditional distribution $Q_{A}(x)=Q(x|A)$, given that $A$ has
been reached. The functional sequence complexity

$\displaystyle\text{FSC}_{0}$ $\displaystyle=H(P_{0})-H(P_{0A})$
$\displaystyle=E_{P_{0}}\left\\{\log[P_{0}(X\mid A)]\mid X\in
A\right\\}-E_{P_{0}}\\{\log[P_{0}(X)]\\}$

is the reduction in entropy, under the null hypothesis $H_{0}$ of the highly
specified states in $A$, compared to the entropy under $H_{0}$ of all states
in $\Omega$. $\text{FSC}_{0}$ then reduces to the functional information
$I_{f0}$ when $P_{0}$ is uniform over $\Omega$. In a similar vein, the active
uncertainty reduction is introduced:

$\displaystyle\text{UR}^{+}$ $\displaystyle=\sum_{x\in A}P_{A}(x)\log
P(x)-\sum_{x\in A}P_{0A}(x)\log P_{0}(x)$ $\displaystyle=E_{P}[\log P(X)|X\in
A]-E_{P_{0}}[\log P_{0}(X)|X\in A].$

Then $\text{UR}^{+}=I^{+}$ when $P_{0A}$ and $P_{A}$ are uniformly distributed
on $A$. This happens, for instance, when $P_{0}$ has a uniform distribution on
$\Omega$ and $P=P_{\theta}$ for some $\theta>0$, and if (8) holds. The
properties of $\mbox{UR}^{+}$ deserve to be analyzed in more detail, for
instance investigate how it differs from the actinfo $I^{+}$.

A fourth extension would be to apply the concept of actinfo to other genetic
models. For instance, Example 4 is the first time that, to our knowledge,
actinfo is applied to the Moran model. In the past though, actinfo was used in
population genetics to study fixation times for the Wright-Fisher model of
population genetics, a model for which time is discrete and generations do not
overlap Díaz-Pachón and Marks II (2020).

##  7 Proofs

Proof of Proposition 1. Introduce

$\displaystyle J(\theta)$ $\displaystyle=\sum_{x\in
A^{c}}\exp\\{\theta[f(x)-f(x_{0})]\\}P_{0}(x),$ (99) $\displaystyle K(\theta)$
$\displaystyle=\sum_{x\in A}\exp\\{\theta[f(x)-f(x_{0})]\\}P_{0}(x),$

when $\Omega$ is finite, and replace the sums in (99) by integrals when
$\Omega$ is continuous. Then

$\displaystyle P_{\theta}(A)$ $\displaystyle=\exp[\theta
f(x_{0})]K(\theta)/\\{\exp(\theta f(x_{0}))[J(\theta)+K(\theta)]\\}$
$\displaystyle=K(\theta)/[J(\theta)+K(\theta)]$ (100)
$\displaystyle=1/[J(\theta)/K(\theta)+1].$

Since $P_{0}(A)<1$, it follows that $J(\theta)$ is a strictly decreasing
function of $\theta\geq 0$, whereas $K(\theta)$ is a non-decreasing function
of $\theta$. From this, it follows that $P_{\theta}(A)$ is a strictly
increasing function of $\theta$, and consequently
$I^{+}(\theta)=\log[P_{\theta}(A)/P_{0}(A)]$ is a strictly increasing function
of $\theta$ as well.

Moreover, $K(\theta)\geq P_{0}(A)>0$ for all $\theta\geq 0$, and $J(\theta)\to
0$ as $\theta\to\infty$ follows by dominated convergence. In conjunction with
(7) this implies $P_{\theta}(A)\to 1$ and $I^{+}(\theta)\to I_{f0}$ as
$\theta\to\infty$.

Proof of Proposition 2 Equation (20) follows from (17), (19) and the fact that

$\displaystyle P_{0}(A)$ $\displaystyle=\sum_{x\in
A}P_{0}(x)=\mathbf{P}_{0}\mathbf{v},$ $\displaystyle P_{\theta t}(A)$
$\displaystyle=\sum_{x\in A}P_{\theta t}(x)=\mathbf{P}_{\theta
t}\mathbf{v}=\mathbf{P}_{0}\mathbf{\Pi}_{\theta}^{t}\mathbf{v},$

since $\mathbf{v}$ is a column vector of length $|\Omega|$ with ones in
positions $x\in A$ and zeros in positions $x\in A^{c}$.

Equation (21) is equivalent to proving that

$\displaystyle P_{\theta t}(A)\to P_{\theta}(A)\text{ as }t\to\infty.$

But this follows from the fact that $P_{\theta}$ is the equilibrium
distribution of the Markov chain with transition kernel (18). That is, letting
$t\to\infty$ in (19) we find that

$\displaystyle\mathbf{P}_{\theta
t}=\mathbf{P}_{0}\mathbf{\Pi}_{\theta}^{t}\to\mathbf{P}_{\theta},$

and therefore

$P_{\theta t}(A)=\mathbf{P}_{\theta
t}\mathbf{v}\to\mathbf{P}_{\theta}\mathbf{v}=P_{\theta}(A),\text{ as
}t\to\infty.$

Proof of Proposition 3 Equation (30) follows from the definitions of
$I^{+}(\theta,t)$ and $I_{s}^{+}(\theta,t)$ in (20) and (29), and the fact
that

$P_{\theta t}(A)=P(X_{t}\in A)\leq P(X_{t\wedge T}\in A)=P_{\theta ts}(A),$

where the inequality is a consequence of the definition of $T$ in (22). Since

$P_{\theta ts}(A)=P(T\leq t)\leq P(T\leq t+1)=P_{\theta,t+1,s}(A),$

we have proved that $I_{s}^{+}(\theta,t)$ is non-decreasing in $t$. Equation
(31) follows from the definition of $I_{s}^{+}(\theta,t)$ and the fact that

$\lim_{t\to\infty}P_{\theta ts}(A)=P(T<\infty)=1.$ (101)

The last equality of (101) is a consequence of the fact that the Markov chain
with transition kernel $\mathbf{\Pi}_{\theta}$ is irreducible, so that any
state $x\in\Omega$ will be reached with probability 1. In particular, the
targeted set $A$ will be reached with probability 1. In order to verify (32),
we first deduce

$P(T>t)=1-P_{0}(A)e^{I^{+}_{s}(\theta,t)}$

from (24), and then we make use of the equality

$E(T)=\sum_{t=0}^{\infty}P(T>t).$

Proof of Proposition 4. Since $n\hat{Q}(A)\sim\text{Bin}(n,Q(A))$ has a
binomial distribution, it follows from the Central Limit Theorem that

$\sqrt{n}(\hat{Q}(A)-Q(A))\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,Q(A)[1-Q(A)]),$ (102)

as $n\to\infty$. Notice that $\hat{I}^{+}=g(\hat{Q}(A))$, where
$g(Q)=\log[Q/P_{0}(A)]$ and $g^{\prime}(Q)=1/Q$. Equation (42) follows from
the Delta Method (see, e.g., Theorem 8.12 of Lehmann and Casella (1998)) and
the fact that

$V=g^{\prime}(Q(A))^{2}\cdot Q(A)[1-Q(A)].$

In order to establish (44), to begin with, it follows from (38) and the
definition of $p_{\text{min}}$ that

$\displaystyle P_{H_{0}}(\hat{I}^{+}\geq I_{\text{min}})$
$\displaystyle=P_{H_{0}}(\hat{Q}(A)\geq p_{\text{min}})$
$\displaystyle=P_{H_{0}}\left(\frac{1}{n}\sum_{i=1}^{n}Y_{i}\geq
p_{\text{min}}\right),$

where $Y_{i}=I(X_{i}\in A)\sim\mbox{Be}(p_{0})$ are independent Bernoulli
variables under $H_{0}$ with success probability $p_{0}=P_{0}(A)$. It follows
from Large Deviations theory that (44) holds, with

$C=\sup_{\phi>0}[\phi p_{\text{min}}-\lambda(\phi)]$ (103)

the Legendre-Fenchel transformation, and

$\lambda(\phi)=\log E[\exp(\phi Y)]=\log[1+p_{0}(e^{\phi}-1)]$ (104)

the cumulant generating function of $Y$ (Kallenberg, 2021, pp. 529-533).
Inserting (104) into (103) it can be seen that the maximum in (103) is given
by (45).

Proof of Proposition 5. In order to verify (50), we will first show that the
estimator (46) of the tilting parameter $\theta$ is asymptotically normal

$\sqrt{n}(\hat{\theta}_{n}-\theta^{\ast})\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,U)\mbox{ as }n\to\infty,$ (105)

with asymptotic variance

$U=\frac{\text{Var}_{Q}[f(X)]}{\text{Var}^{\,\,2}_{P_{\theta^{\ast}}}[f(X)]}.$
(106)

To this end, let ′ refer to derivatives with respect to the tilting parameter
$\theta$. Define the score function

$\psi_{\theta}(x)=\frac{d\log
P_{\theta}(x)}{d\theta}=\frac{P_{\theta}^{\prime}(x)}{P_{\theta}(x)}$

and its derivative

$\psi_{\theta}^{\prime}(x)=\frac{d\psi_{\theta}(x)}{d\theta}.$

It is a standard result from the asymptotic theory of maximum likelihood
estimation and $M$-estimation (see, e.g., Chapter 6 of Lehmann and Casella
(1998)) that (105) holds with asymptotic variance

$U=\frac{\text{Var}_{Q}[\psi_{\theta^{\ast}}(X)]}{E^{2}_{Q}[\psi^{\prime}_{\theta^{\ast}}(X)]}.$
(107)

To simplify (107), notice that the score function can be written as

$\psi_{\theta}(x)=f(x)-\frac{M^{\prime}(\theta)}{M(\theta)}=f(x)-E_{P_{\theta}}[f(X)]$
(108)

for the exponential family of tilted distributions (10)-(11). From this it
follows that

$\psi^{\prime}_{\theta}(x)=\frac{M^{\prime\prime}(\theta)}{M(\theta)}-\left(\frac{M^{\prime}(\theta)}{M(\theta)}\right)^{2}=\text{Var}_{P_{\theta}}[f(X)]$

is a constant, not depending on $x$. Inserting the last two displayed
equations into (107), the formula in (106) for the asymptotic variance of
$\hat{\theta}$ is obtained. As a next step we notice that

$\hat{I}^{+}=g(\hat{\theta}),$ (109)

where

$g(\theta)=\log\frac{P_{\theta}(A)}{P_{0}(A)}=\log h(\theta)-\log P_{0}(A),$
(110)

and

$h(\theta)=P_{\theta}(A)=\frac{\sum_{x\in A}e^{\theta
f(x)}P_{0}(x)dx}{M(\theta)}$ (111)

follows from the definition of $P_{\theta}(x)$ in (10).

Differentiating (111) with respect to $\theta$, we find that

$\displaystyle\begin{aligned} h^{\prime}(\theta)&=\sum_{x\in A}f(x)e^{\theta
f(x)}P_{0}(x)dx/M(\theta)\\\ &-M^{\prime}(\theta)\sum_{x\in A}e^{\theta
f(x)}P_{0}(x)dx/M^{2}(\theta).\end{aligned}$ (112)

And it follows from the RHS of (112) that

$\displaystyle\begin{aligned}
h^{\prime}(\theta)&=E_{P_{\theta}}[f(X)I(f(X)\geq
f_{0})]-P_{\theta}(A)E_{P_{\theta}}[f(X)]\\\
&=\text{Cov}_{P_{\theta}}[f(X),I(f(X)\geq f_{0})].\end{aligned}$ (113)

Then we combine (110) and (112), and obtain

$g^{\prime}(\theta)=\frac{h^{\prime}(\theta)}{h(\theta)}=\frac{\text{Cov}_{P_{\theta}}[f(X),I(f(X)\geq
f_{0})]}{P_{\theta}(A)}.$ (114)

Finally we use the Delta Method to conclude that $\hat{I}^{+}$ is an
asymptotic normal estimator (42) of $I^{+}(\theta^{\ast})$, with asymptotic
variance $V=g^{\prime}(\theta^{\ast})^{2}U$, which, in view of (106) and
(114), agrees with (51).

In order to prove the large deviation result (52) for the parametric test of
FT, let $\theta_{\text{min}}$ be the value of the tilting parameter that
satisfies
$P_{\theta_{\text{min}}}(A)=p_{\text{min}}=P_{0}(A)\exp(I_{\text{min}})$. Then
notice that

$\displaystyle P_{H_{0}}(\hat{I}^{+}\geq I_{\text{min}})$
$\displaystyle=P_{H_{0}}(\hat{Q}(A)\geq p_{\text{min}})$
$\displaystyle=P_{H_{0}}(\hat{\theta}\geq\theta_{\text{min}})$
$\displaystyle=P_{H_{0}}(\sum_{i=1}^{n}\psi_{\theta_{\text{min}}}(X_{i})/n\geq
0)$ $\displaystyle=P_{H_{0}}\left(\sum_{i=1}^{n}f(X_{i})/n\geq
E_{p_{\text{min}}}[f(X)]\right),$

where in the third step we utilized that $\hat{\theta}\geq\theta_{\text{min}}$
is equivalent to the derivative of the log likelihood of data being non-
negative at $\theta_{\text{min}}$, and in the fourth step we made use of (108)
and introduced $p_{\text{min}}=P_{\theta_{\text{min}}}$. But this last line is
a large deviations probability. It then follows from large deviations theory
that (52) holds, with $C$ the Legendre-Fenchel transformation in (53).

Proof of Proposition 6. Since the bias corrected empirical actinfo

$\hat{I}_{n}^{+}-B=\log\frac{\hat{Q}(A)}{P_{0\xi}(A)}$ (115)

behaves like (38), with $P_{0}=P_{0\xi}$, the asymptotic normality result for
the nonparametric version of the estimator of $I_{Q}^{+}$ follows from
Proposition 4.

For the parametric version of the estimator of $I_{Q}^{+}$ we will (briefly)
generalize the asymptotic normality proof of Proposition 5. It follows from
(59) and (61) that

$\hat{I}_{n}^{+}=g(\hat{\theta},\hat{\xi}),$

where

$g(\theta,\xi)=\log\frac{P_{\theta\xi}(A)}{P_{0\text{max}}(A)}.$ (116)

Making use of the delta method, it follows that the asymptotic variance of the
parametric version of $\hat{I}_{n}^{+}$ equals

$V=g^{\prime}(\theta^{\ast},\xi^{\ast})\mbox{AsVar}(\hat{\theta},\hat{\xi})g^{\prime}(\theta^{\ast},\xi^{\ast})^{T},$
(117)

with the asymptotic variance of $(\hat{\theta},\hat{\xi})$ defined through

$\sqrt{n}\left((\hat{\theta},\hat{\xi})-(\theta^{\ast},\xi^{\ast})\right)\,\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,\mbox{AsVar}(\hat{\theta},\hat{\xi}))$

as $n\to\infty$. Since $(\hat{\theta},\hat{\xi})$ in (62) is an $M$-estimator,
it follows that its asymptotic variance equals

$\mbox{AsVar}(\hat{\theta},\hat{\xi})=E[\psi_{\theta^{\ast}\xi^{\ast}}^{\prime}(X)]^{-1}E[\psi^{T}_{\theta^{\ast}\xi^{\ast}}(X)\psi_{\theta^{\ast}\xi^{\ast}}(X)]E[(\psi_{\theta^{\ast}\xi^{\ast}}^{\prime})^{T}(X)]^{-1}.$
(118)

The gradient of (116) is

$g^{\prime}(\theta,\xi)=\frac{P_{\theta\xi}^{\prime}(A)}{P_{\theta\xi}(A)}=E[\psi_{\theta\xi}(X)|X\in
A],$ (119)

where $\psi_{\theta\xi}=P_{\theta\xi}^{\prime}(x)/P_{\theta\xi}(x)$ is the
likelihood score function for the combined parameter vector $(\theta,\xi)$.
Putting things together, the asympotic variance formula (65) for the
parametric version of $\hat{I}_{n}^{+}$ follows from (117)-(119).

The significance level of the FT test can be written as

$P_{0\xi}(\hat{I}_{n}^{+}\geq I_{\text{min}})=P_{0\xi}(\hat{I}_{n}^{+}-B\geq
I_{\text{min}}-B).$

Since $p_{\text{min}}=P_{0\xi}(A)\exp(I_{\text{min}})$, we have that

$I_{\text{min}}-B=\log\frac{p_{\text{min}}e^{-B}}{P_{0\xi}(A)}.$ (120)

From this and (115) it follows that the nonparametric test of FT behaves as
the corresponding nonparametric test of Proposition 4, with the null
probability $P_{0}(A)$ replaced by $P_{0\xi}(A)$, and $p_{\text{min}}$
replaced by $p_{\text{min}}e^{-B}$. Therefore, the large deviation result (67)
follows from (45). In a similar way, the large deviation result for the
parametric version of the FT-test (in the special case when $\theta$ is a
scalar exponential tilting parameter) follows from (115), (120) and
Proposition 5.

Proof of Proposition 7. Because of (58) and (69) we have that

$\sqrt{n}(\hat{I}_{nn_{0}}^{+}-I_{Q}^{+})=\sqrt{n}\log\frac{\hat{Q}(A)}{Q(A)}-\sqrt{\frac{n}{n_{0}}}\sqrt{n_{0}}\log\frac{P_{0\hat{\xi}}(A)}{P_{0\xi}(A)},$
(121)

where

$\sqrt{n}\log\frac{\hat{Q}(A)}{Q(A)}\,\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,V_{1})\mbox{ as }n\to\infty$ (122)

and

$\sqrt{n_{0}}\log\frac{P_{0\hat{\xi}}(A)}{P_{0\xi}(A)}\,\stackrel{{\scriptstyle\cal
L}}{{\longrightarrow}}N(0,V_{2})\mbox{ as }n_{0}\to\infty$ (123)

respectively. It follows from the proofs of Propositions 4-5 that the
asymptotic variance for $V_{1}$ in (122) is the same as $V$ in (43) and (65),
for the nonparametric and prametric versions of $\hat{Q}(A)$ respectively. The
asymptotic variance $V_{2}$ in (123) is given by (73). This is proved using
the delta method (similarly as for Proposition 6), making use of the fact that
$\hat{\xi}$ is the maximum likelihood estimator of $\xi$ with asymptotic
variance that is the inverse $E[\psi_{\xi}^{T}(X)\psi_{\xi}(X)]^{-1}$ of the
Fisher information matrix. The asymptotic normality result (72) then follows
from (121)-(123), the fact that $n/n_{0}\to\lambda$, and the independence of
the two samples.

The large deviations results are proved in a similar way as in Proposition 6,
replacing $P_{0\text{max}}(A)$ by $P_{0\hat{\xi}}(A)$. Using statistical
consistency $\hat{\xi}\,\stackrel{{\scriptstyle p}}{{\longrightarrow}}\xi$ as
$n_{0}\to\infty$, it follows that the large deviation rates $C$ of Proposition
7, for the nonparametric and parametric versions of the FT tests, are the same
as in Proposition 6, with bias term $B=0$.

Details from Example 4. In order to prove that the Metropolis-Hastings type
Markov chain (14) with acceptance probabilities (81) has equilibrium
distribution $P_{\theta}$, we first notice that for any pair of states $x\neq
y$, the flow of probability mass

$\displaystyle P_{\theta}(x)\pi_{\theta}(x,y)$
$\displaystyle=P_{\theta}(x)q(x,y)\alpha_{\theta}(x,y)$
$\displaystyle=\frac{P_{0}(x)e^{\theta f(x)}}{M(\theta)}q(x,y)\cdot
C\left[\frac{e^{\theta f(y)}P_{0}(y)q(y,x)}{e^{\theta
f(x)}P_{0}(x)q(x,y)}\right]^{1/2}$ $\displaystyle=C\frac{\left(e^{\theta
f(x)}P_{0}(x)q(x,y)e^{\theta f(y)}P_{0}(y)q(y,x)\right)^{1/2}}{M(\theta)}$
(124)

from $x$ to $y$ is symmetric with respect to $x$ and $y$. Therefore, the flow
$P_{\theta}(y)\pi_{\theta}(y,x)$ of probability mass in the opposite
direction, from $y$ to $x$, is the same as in (7). A Markov chain with this
property is called reversible (Popov, 2021, pp. 11-12). But it is well known
that $P_{\theta}$ is a stationary distribution if the Markov chain is
reversible with reversible measure $P_{\theta}$ (Grimmett and Stirzaker, 2001,
p. 238). If, additionally, the proposal distribution $q$ is such that it is
possible to move between any pair of states in a finite number of steps, it
follows that the Markov chain is irreducible and hence that $P_{\theta}$ is
its unique stationary distribution, which is also the equilibrium distribution
of the Markov chain (Grimmett and Stirzaker, 2001, p. 232).

Next we will motivate formula (87) for the acceptance probability of a Moran
model. Assume that the population evolves over time as a Moran model, and that
all individuals have type $x$. If one individual mutates from $x$ to $y$,
because of (83), the relative fitness between the $N-1$ individuals of type
$x$ and the newly mutated individual of type $y$ is

$s=\frac{e^{\theta f(y)/N}}{e^{\theta f(x)/N}}=e^{\theta[f(y)-f(x)]/N}.$ (125)

From the theory of Moran models (e.g., Hössjer et al. (2021); Komarova et al.
(2003)), it is well known that the fixation probability for the newly mutated
individual is

$\beta_{N}(s)=\left\\{\begin{array}[]{ll}(1-s^{-1})/(1-s^{-N}),&s\neq 1,\\\
1/N,&s=1.\end{array}\right.$ (126)

Inserting (125) into (126) we find (when $s\neq 1$, or equivalently when
$\Delta=\theta[f(y)-f(x)]\neq 0$), that

$\beta_{N}(s)=\frac{1-e^{-\Delta/N}}{1-e^{-\Delta}}\approx\frac{1}{N}\cdot\frac{\Delta}{1-e^{-\Delta}}\approx\frac{1}{N}\cdot(1+\frac{\Delta}{2}),$

which is equivalent to (87).

References

## References

  * Gödel (1931) Gödel, K.  Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I.  Monatshefte für Mathematik und Physik 1931, 38, 173–198.
  * Hofstadter (1999) Hofstadter, D.R.  Gödel, Escher, Bach: an Ethernal Golden Braid; Basic Books, 1999\.
  * Whitehad and Russell (1927) Whitehead, A.N.; Russell, B.  Principia Mathematica; Cambridge University Press, 1927.
  * Wolpert and MacReady (1995) Wolpert, D.H.; MacReady, W.G.  No Free Lunch Theorems for Search.  Technical Report SFI-TR-95-02-010, Santa Fe Institute, 1995.
  * Wolpert and MacReady (1997) Wolpert, D.H.; MacReady, W.G.  No Free Lunch Theorems for Optimization.  IEEE Transactions on Evolutionary Computation 1997, 1, 67–82.  https://doi.org/10.1109/4235.585893.
  * Wolpert (2021) Wolpert, D.H.  What is important about the No Free Lunch theorems? In Black Box Optimization, Machine Learning and No-Free Lunch Theorems; Pardalos, P.M.; Rasskazova, V.; Vrahatis, M.N., Eds.; Springer, 2021.
  * Dembski and Marks II (2009a) Dembski, W.A.; Marks II, R.J.  Bernoulli’s Principle of Insufficient Reason and Conservation of Information in Computer Search.  Proceedings of the 2009 IEEE International Conference on Systems, Man, and Cybernetics. San Antonio, TX 2009, pp. 2647–2652.  https://doi.org/10.1109/ICSMC.2009.5346119.
  * Dembski and Marks II (2009b) Dembski, W.A.; Marks II, R.J.  Conservation of Information in Search: Measuring the Cost of Success.  IEEE Transactions Systems, Man, and Cybernetics - Part A: Systems and Humans 2009, 5, 1051–1061.  https://doi.org/10.1109/TSMCA.2009.2025027.
  * Hazen et al. (2007) Hazen, R.M.; Griffin, P.L.; Carothers, J.M.; Szostak, J.W.  Functional information and the emergence of biocomplexity.  Proc Natl Acad Sci USA 2007, 104, 8574–8581.
  * Szostak (2003) Szostak, J.W.  Functional information: Molecular messages.  Nature 2003, 423, 689.  https://doi.org/10.1038/423689a.
  * Díaz-Pachón and Marks II (2020) Díaz-Pachón, D.A.; Marks II, R.J.  Generalized active information: Extensions to unbounded domains.  BIO-Complexity 2020, 2020, 1–6.  https://doi.org/10.5048/BIO-C.2020.3.
  * Díaz-Pachón et al. (2019) Díaz-Pachón, D.A.; Sáenz, J.P.; Rao, J.S.; Dazard, J.E.  Mode hunting through active information.  Applied Stochastic Models in Business and Industry 2019, 35, 376–393.  https://doi.org/10.1002/asmb.2430.
  * Liu et al. (2022) Liu, T.; Díaz-Pachón, D.A.; Rao, J.S.; Dazard, J.E.  High Dimensional Mode Hunting Using Pettiest Component Analysis.  IEEE Transactions on Pattern Analysis and Machine Intelligence 2022, Accepted.  https://doi.org/10.1109/TPAMI.2022.3195462.
  * Montañez (2017) Montañez, G.D.  The famine of forte: Few search problems greatly favor your algorithm.  2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC) 2017, pp. 477–482.  https://doi.org/10.1109/SMC.2017.8122651.
  * Montañez (2018) Montañez, G.D.  A Unified Model of Complex Specified Information.  BIO-Complexity 2018, 2018, 1–26.
  * Díaz-Pachón et al. (2020) Díaz-Pachón, D.A.; Sáenz, J.P.; Rao, J.S.  Hypothesis testing with active information.  Statistics & Probability Letters 2020, 161, 108742.  https://doi.org/10.1016/j.spl.2020.108742.
  * Carter (1974) Carter, B.  Large Number Coincidences and the Anthropic Principle in Cosmology. In Confrontation of Cosmological Theories with Observational Data; Longhair, M.S., Ed.; D. Reidel, 1974; pp. 291–298.
  * Barrow and Tipler (1988) Barrow, J.D.; Tipler, F.J.  The Anthropic Cosmological Principle; Oxford University Press, 1988\.
  * Davies (1982) Davies, P.  The Accidental Universe; Cambridge University Press, 1982.
  * Lewis and Barnes (2016) Lewis, G.F.; Barnes, L.A.  A Fortunate Universe: Life In a Finely Tuned Cosmos; Cambridge University Press, 2016.  https://doi.org/10.1017/9781316661413.
  * Rees (2000) Rees, M.J.  Just Six Numbers: The Deep Forces That Shape The Universe; Basic Books, 2000.
  * Adams (2019) Adams, F.C.  The degree of fine-tuning in our universe —and others.  Physics Reports 2019, 807, 1–111.  https://doi.org/10.1016/j.physrep.2019.02.001.
  * Barnes (2012) Barnes, L.A.  The Fine Tuning of the Universe for Intelligent Life.  Publications of the Astronomical Society of Australia 2012, 29, 529–564.  https://doi.org/10.1071/AS12015.
  * Tegmark and Rees (1998) Tegmark, M.; Rees, M.J.  Why is the cosmic microwave background fluctuation level $10^{-5}$.  The Astrophysical Journal 1998, 499, 526–532.
  * Tegmark et al. (2006) Tegmark, M.; Aguirre, A.; Rees, M.; Wilczek, F.  Dimensionless constants, cosmology, and other dark matters.  Physical Review D 2006, 73, 023505.  https://doi.org/10.1103/PhysRevD.73.023505.
  * Díaz-Pachón et al. (2021) Díaz-Pachón, D.A.; Hössjer, O.; Marks II, R.J.  Is Cosmological Tuning Fine or Coarse?  Journal of Cosmology and Astroparticle Physics 2021, 2021, 020.  https://doi.org/10.1088/1475-7516/2021/07/020.
  * Díaz-Pachón et al. (2022) Díaz-Pachón, D.A.; Hössjer, O.; Marks II, R.J.  Sometimes size does not matter.  Submitted 2022.
  * Dingjan and Futerman (2021a) Dingjan, T.; Futerman, A.H.  The fine-tuning of cell membrane lipid bilayers accentuates their compositional complexity.  BioEssays 2021, 43, e2100021.
  * Dingjan and Futerman (2021b) Dingjan, T.; Futerman, A.H.  The role of the ‘sphingoid motif’ in shaping the molecular interactions of sphingolipids in biomembranes.  Biochimica et Biophysica Acta (BBA) - Biomembranes 2021, 1863, 183701.
  * Thorvaldsen and Hössjer (2020) Thorvaldsen, S.; Hössjer, O.  Using statistical methods to model the fine-tuning of molecular machines and systems.  J Theor Biol 2020, 501, 110352.  https://doi.org/10.1016/j.jtbi.2020.110352.
  * Asmussen and Glynn (2007) Asmussen, S.; Glynn, P.W.  Stochastic Simulation: Algorithms and Analysis; Springer, 2007\.
  * Siegmund (1976) Siegmund, D.  Importance Sampling in the Monte Carlo Study of Sequential Tests.  Ann Stat 1976, 4, 673–684.
  * Lehmann and Casella (1998) Lehmann, E.L.; Casella, G.  Theory of Point Estimation, second ed.; Springer, 1998.
  * Robert and Casella (2010) Robert, C.P.; Casella, G.  Monte Carlo Statistical Methods; Springer, 2010.
  * Hastings (1970) Hastings, W.K.  Monte Carlo sampling methods using Markov chains and their applications.  Biometrika 1970, 57, 97–109.
  * Metropolis et al. (1953) Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.  Equation of State Calculations by Fast Computing Machines.  J Chem Phys 1953, 21, 1087–1092.
  * Kirkpatrick et al. (1983) Kirkpatrick, S.; C. D. Gelatt Jr..; Vecchi, M.P.  Optimization by Simulated Annealing.  Science 1983, 220, 671–680.
  * Ross (2003) Ross, S.  Introduction to Probability Models, 8th. ed.; Academic Press, 2003\.
  * Asmussen et al. (1996) Asmussen, R.; Nerman, O.; Olsson, M.  Fitting Phase-type Distributions via the EM Algorithm.  Scand J Stat 1996, 23, 419–441.
  * Neuts (1981) Neuts, M.F.  Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach; Johns Hopkins University Press, 1981.
  * Hössjer et al. (2021) Hössjer, O.; Bechly, G.; Gauger, A.  On the waiting time until coordinated mutations get fixed in regulatory sequences.  J Theor Biol 2021, 524, 110657.
  * Varadhan (1984) Varadhan, S.R.S.  Large Deviations and Applications; SIAM, 1984.
  * Hössjer et al. (2022a) Hössjer, O.; Díaz-Pachón, D.A.; Chen, Z.; Rao, J.S.  Active information, missing data, and prevalence estimation.  arXiv 2022.  https://doi.org/10.48550/arXiv.2206.05120.
  * Hössjer et al. (2022b) Hössjer, O.; Díaz-Pachón, D.A.; Rao, J.S.  Active Information, Learning, and Knowledge Acquisition.  PsyArXiv 2022.  https://doi.org/10.31234/osf.io/qt5kw.
  * Kaelbling et al. (1996) Kaelbling, L.P.; Littman, M.L.; Moore, A.W.  Reinforcement Learning: A Survey.  Journal of Artificial Intelligence Research 1996, 4, 237–285.
  * Durrett (2008) Durrett, R.  Probability Models for DNA Sequence Evolution; Springer, 2008\.
  * Moran (1958a) Moran, P.A.P.  Random processes in genetics.  Math Proc Camb Philos Soc 1958, 54, 60–71.
  * Moran (1958b) Moran, P.A.P.  A general theory of the distribution of gene frequencies - I. Overlapping generations.  Proc Roy Soc Lond B 1958, 149, 102–112.
  * Mitchell (1996) Mitchell, M.  An Introduction to Genetic Algorithms; MIT Press, 1996.
  * Vikhar (2016) Vikhar, P.A.  Evolutionary algorithms: A critical review and its future prospects.  2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC) 2016, pp. 261–265.
  * Abel and Trevors (2005) Abel, D.L.; Trevors, J.T.  Three subsets of sequence complexity and their relevance to biopolymeric information.  Theor Biol Med Model 2005, 2, 29.
  * Durston and Chiu (2005) Durston, K.K.; Chiu, D.K.Y.  A functional entropy model for biological sequences.  Dynamics of Continuous, Discrete & Impulsive Systems, Series B Supplement 2005.
  * Durston and Chiu (2011) Durston, K.K.; Chiu, D.K.Y.  Functional Sequence Complexity in Biopolymers. In The First Gene: The Birth of Programming, Messaging and Formal Control; Abel, D.L., Ed.; LongView Press, 2011; pp. 147–169.
  * Durston et al. (2007) Durston, K.K.; Chiu, D.K.Y.; Abel, D.L.; Trevors, J.T.  Measuring the functional sequence complexity of proteins.  Theor Biol Med Model 2007, 4, 47.
  * Díaz-Pachón and Marks II (2020) Díaz-Pachón, D.A.; Marks II, R.J.  Active Information Requirements for Fixation on the Wright-Fisher Model of Population Genetics.  BIO-Complexity 2020, 2020, 1–6.  https://doi.org/10.5048/BIO-C.2020.4.
  * Kallenberg (2021) Kallenberg, O.  Foundations of Modern Probability, 3rd. ed.; Vol. 2, Springer, 2021.
  * Popov (2021) Popov, S.  Two-Dimensional Random Walk: From Path Counting to Random Interlacements; Cambridge University Press, 2021.  https://doi.org/10.1017/9781108680134.
  * Grimmett and Stirzaker (2001) Grimmett, G.; Stirzaker, D.  Probability and Random Processes, 3rd. ed.; Oxford Univeristy Press, 2001.
  * Komarova et al. (2003) Komarova, N.L.; Sengupta, A.; Nowak, M.A.  Mutation-selection networks of cancer initiation: tumor suppressor genes and chromosomal instability.  J Theor Biol 2003, 223, 433–450.