# On fluctuations of complexity measures for the FIND algorithm

Jasper Ischebeck  Institute of Mathematics, Goethe University Frankfurt,
Frankfurt a.M., Germany<EMAIL_ADDRESS>and  Ralph Neininger
Institute of Mathematics, Goethe University Frankfurt, Frankfurt a.M., Germany
<EMAIL_ADDRESS>
###### Abstract.

The FIND algorithm (also called Quickselect) is a fundamental algorithm to
select ranks or quantiles within a set of data. It was shown by Grübel and
Rösler that the number of key comparisons required by Find as a process of the
quantiles $\alpha\in[0,1]$ in a natural probabilistic model converges after
normalization in distribution within the càdlàg space $D[0,1]$ endowed with
the Skorokhod metric. We show that the process of the residuals in the latter
convergence after normalization converges in distribution to a mixture of
Gaussian processes in $D[0,1]$ and identify the limit’s conditional covariance
functions. A similar result holds for the related algorithm QuickVal. Our
method extends to other cost measures such as the number of swaps (key
exchanges) required by Find or cost measures which are based on key
comparisons but take into account that the cost of a comparison between two
keys may depend on their values, an example being the number of bit
comparisons needed to compare keys given by their bit expansions.

###### 2020 Mathematics Subject Classification:

60F17, 68Q25, 68P10, 60C05

##  1\. Introduction

In 1961, Hoare [11] introduced the algorithm FIND, also called Quickselect, to
select a key (an element) of a given rank from a linearly ordered finite set
of data. We assume that the data are distinct real numbers. To be definite a
simple version of the FIND algorithm is given as follows: $\mathrm{FIND}(S,k)$
has as input a set $S=\\{s_{1},\ldots,s_{n}\\}$ of distinct real numbers of
size $n$ and an integer $1\leq k\leq n$. The algorithm $\mathrm{FIND}$
operates recursively as follows: If $n=1$ we have $k=1$ and $\mathrm{FIND}$
returns the single element of $S$. If $n\geq 2$ and
$S=\\{s_{1},\ldots,s_{n}\\}$ the algorithm first chooses an elements from $S$,
say $s_{j}$, called pivot, and generates the sets

$\displaystyle
S_{<}:=\\{s_{i}\,|\,s_{i}<s_{j},i\in\\{1,\ldots,n\\}\setminus\\{j\\}\\},\quad
S_{\geq}:=\\{s_{i}\,|\,s_{i}\geq
s_{j},i\in\\{1,\ldots,n\\}\setminus\\{j\\}\\}.$

If $k=|S_{<}|+1$, the algorithm returns $s_{j}$. If $k\leq|S_{<}|$,
recursively $\mathrm{FIND}(S_{<},k)$ is applied. If $k\geq|S_{<}|+2$,
recursively $\mathrm{FIND}(S_{\geq},k-|S_{<}|-1)$ is applied. Note that
$\mathrm{FIND}(S,k)$ returns the element of rank $k$ from $S$. There are
various variants of the algorithm, in particular regarding how the pivot
element is chosen and how $S$ is partitioned into the subsets $S_{<}$ and
$S_{\geq}$.

In a standard probabilistic model one assumes that the data are ordered, i.e.
given as a vector $(s_{1},\ldots,s_{n})$, and are randomly permuted, all
permutations being equally likely. This can be achieved assuming that the data
are given as $(U_{1},\ldots,U_{n})$ where $(U_{j})_{j\in{\mathbb{N}}}$ is a
sequence of i.i.d. random variables with distribution $\mathrm{unif}[0,1]$,
the uniform distribution over the unit interval $[0,1]$. This is the
probabilistic model considered below. Note that the randomness is within the
data, while the algorithm is deterministic.

Various cost measures have been considered for $\mathrm{FIND}$, mainly the
number of key comparisons required which we analyze in detail below. At the
end of this extended abstract we state related results for the number of swaps
(key exchanges) required and for cost measures which are based on key
comparisons, where the cost of a comparison may depend on the values of the
keys $s_{i}$, $s_{j}$, the number of bit comparisons required to decide
whether $s_{i}<s_{j}$ or not being a prominent example.

For analysis purposes a related process, called $\mathrm{QuickVal}$, has been
considered, see [18, 8]. Informally, $\mathrm{QuickVal}$ for an
$\alpha\in[0,1]$ mimics $\mathrm{FIND}$ to select (or to try to select) the
value $\alpha$ from the set of data, which, in our probabilistic model for
large $n$, comes close to $\mathrm{FIND}$ selecting rank $\lfloor\alpha
n\rfloor$. To be definite, $\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$
compares the $U_{i}$ with $U_{1}$ to generate sublists

$\displaystyle S_{<}:=(U_{j_{1}},\ldots,U_{j_{m-1}}),\quad
S_{\geq}:=(U_{j_{m+1}},\ldots,U_{j_{n}}),$

with $U_{j_{i}}<U_{1}$ for $i=1,\ldots,{m-1}$ and $2\leq j_{1}<\cdots<j_{m-1}$
and $U_{j_{i}}\geq U_{1}$ for $i=m+1,\ldots,n$ and $2\leq
j_{m+1}<\cdots<j_{n}$. Hence, $m-1\in\\{0,\ldots,n-1\\}$ is the number of the
$U_{i}$, $2\leq i\leq n$, being smaller than $U_{1}$. The algorithm
recursively calls $\mathrm{QuickVal}(S_{<},\alpha)$ if $\alpha<U_{1}$ and
$|S_{<}|>0$. If $\alpha\geq U_{1}$ and $|S_{\geq}|>0$ recursively
$\mathrm{QuickVal}(S_{\geq},\alpha-U_{1})$ is called. The number of key
comparisons required by $\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ is
denoted by $S_{\alpha,n}$.

To describe the processes $(S_{\alpha,n})_{\alpha\in[0,1]}$ and their limit
(after scaling) conveniently we also consider the binary search tree
constructed from the the data $(U_{i})_{i\in{\mathbb{N}}}$. Part of the
following definitions are depicted in Figure 1. The data are inserted into the
rooted infinite binary tree, where we denote its nodes by the elements of
$\\{0,1\\}^{\ast}:=\cup_{n=0}^{\infty}\\{0,1\\}^{n}$ as follows. Its root is
denoted by the empty word $\epsilon$ and for each node
$\phi\in\\{0,1\\}^{\ast}$ we denote by $\phi 0$ and $\phi 1$ (the word $\phi$
appended with a $0$ resp. $1$) its left and right child respectively. Moreover
$\lvert\phi\rvert$ denotes the length of the word $\phi$, which is the depth
of the corresponding node in the tree. To construct the binary search tree for
$(U_{1},\ldots,U_{n})$ the first key $U_{1}$ is inserted into the root and
occupies the root. Then, successively the following keys are inserted, where
each key traverses the already occupied nodes starting at the root as follows:
Whenever the key traversing is less than the occupying key at a node it moves
on to the left child of that node, otherwise to its right child. The first
empty node found is occupied by the key.

To describe the costs of the algorithms we organize, using notation of Fill
and Nakama [8], the sub-intervals
$([L_{\phi},R_{\phi}))_{\phi\in\\{0,1\\}^{\ast}}$ implicitly generated
starting with $[0,1)=:[L_{\epsilon},R_{\epsilon})$ and recursively setting

$\displaystyle\tau_{\phi}$
$\displaystyle:=\inf\\{i\in{\mathbb{N}}\,|\,L_{\phi}<U_{i}<R_{\phi}\\},$ (1)
$\displaystyle L_{\phi 0}$ $\displaystyle:=L_{\phi},\quad R_{\phi
1}:=R_{\phi},\quad L_{\phi 1}:=R_{\phi 0}:=U_{\tau_{\phi}},\quad
I_{\phi}:=R_{\phi}-L_{\phi}.$

Now, if a sublist starting with pivot $U_{\tau_{\phi}}$ has to be split by
$\mathrm{QuickVal}$, the keys which are inserted in the subtree rooted at
$U_{\tau_{\phi}}$ need to be compared with $U_{\tau_{\phi}}$. Hence, we get a
contribution of key comparisons of

(2) $S_{\phi,n}=\sum_{\tau_{\phi}<k\leq
n}\mathbf{1}_{[L_{\phi},R_{\phi})}(U_{k}).$

Now, for $\alpha\in[0,1]$, $\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$
generates and splits sublists encoded by $\phi(\alpha,k)$ for $k=0,1,\ldots$
for which we obtain by $\phi(\alpha,0)=\epsilon$ and

(3) $\phi(\alpha,k+1)=\begin{cases}\phi(\alpha,k)0,&\mbox{if
}\alpha<U_{\tau_{\phi(\alpha,k)}},\\\ \phi(\alpha,k)1,&\mbox{if }\alpha\geq
U_{\tau_{\phi(\alpha,k)}}.\end{cases}$

When using the variables defined in (1) or (2), we abbreviate the notation
$\phi(\alpha,k)$ by $\alpha,k$, such as writing
$I_{\alpha,k}:=I_{\phi(\alpha,k)}$ or $S_{\alpha,k,n}:=S_{\phi(\alpha,k),n}$.

$U_{\tau_{\epsilon}}$$U_{\tau_{0}}$$U_{\tau_{\alpha,1}}$$U_{\tau_{\alpha,2}}$…$U_{\tau_{10}}$$\alpha\geq
U_{\tau_{\epsilon}}$$\alpha<U_{\tau_{\alpha,1}}$ Figure 1. Part of the binary
search tree. The pivots of sublists split by
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ for some $\alpha\in[0,1]$ are
on the path indicated. Note that we have
$\tau_{\epsilon}=\tau_{\phi(\alpha,0)}=\tau_{\alpha,0}=1$ and in this example
$\alpha\geq U_{1}$ and $\alpha<U_{\tau_{\alpha,1}}$ so that
$\phi(\alpha,2)=10\in\\{0,1\\}^{2}$.

The number of key comparisons required by
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ is then given by the (finite)
sum

$\displaystyle S_{\alpha,n}=\sum_{k=1}^{\infty}S_{\alpha,k,n}.$

Fill and Nakama [8, Theorem 3.2] showed (considering more general complexity
measures) that for each $\alpha\in[0,1]$ almost surely

(4) $\displaystyle\frac{1}{n}S_{\alpha,n}\to
S_{\alpha}:=\sum_{k=0}^{\infty}I_{\alpha,k},\quad(n\to\infty).$

The latter convergence also holds in $L_{p}$, see Fill and Matterer [7,
Proposition 6.1].

We take the point of view that such an almost sure asymptotic result may be
considered a strong law of large numbers (SLLN). The subject of the present
extended abstract is to study the fluctuations in such SLLN, sometimes called
a central limit analogue. We study these fluctuations as processes in the
metric space $(D[0,1],d_{\mathrm{SK}})$ of càdlàg functions endowed with the
Skorokhod metric; see Billingsley [2] for background on weak convergence of
probability measures on metric spaces in general and on
$(D[0,1],d_{\mathrm{SK}})$ in particular. Note that, by definition,
$(S_{\alpha,n})_{\alpha\in[0,1]}$ and $(S_{\alpha})_{\alpha\in[0,1]}$ have
càdlàg paths almost surely. As the normalized process of fluctuations we
define

(5) $\displaystyle
G_{n}:=(G_{\alpha,n})_{\alpha\in[0,1]}:=\left(\frac{S_{\alpha,n}-nS_{\alpha}}{\sqrt{n}}\right)_{\mathrlap{\alpha\in[0,1]}}.$

Then we have the following result:

######  Theorem 1.

Let $S_{\alpha,n}$ be the number of key comparisons required by
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ and
$(S_{\alpha})_{\alpha\in[0,1]}$ as in (4). Then for the fluctuation process
$G_{n}$ defined in (5) we have

$\displaystyle G_{n}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}G_{\infty}\;\mbox{ in
}(D[0,1],d_{\mathrm{SK}})\qquad(n\to\infty),$

where $G_{\infty}$ is a mixture of centered Gaussian processes with random
covariance function given by

(6)
$\Sigma_{\infty,\alpha,\beta}:=\sum_{k=0}^{J}\sum_{j=0}^{\infty}I_{\alpha,j\vee
k}+\mathbf{1}_{\\{\alpha\neq\beta\\}}(J+1)\sum_{j=J+1}^{\infty}(I_{\beta,j})-S_{\alpha}S_{\beta},\quad\alpha,\beta\in[0,1],$

where
$J=J(\alpha,\beta):=\max\\{k\in{\mathbb{N}}_{0}\,|\,\tau_{\alpha,k}=\tau_{\beta,k}\\}\in{\mathbb{N}}_{0}\cup\\{\infty\\}$.

######  Remark 2.

In his PhD thesis, Matterer [14, Theorem 6.4] showed the convergence of the
one-dimensional marginals for the functional limit law in Theorem 1.

######  Remark 3.

An alternative representation of the random covariance function in (6) is as
follows: With an independent random variable $V$ uniformly distributed over
$[0,1]$, we have

(7)
$\displaystyle\Sigma_{\infty,\alpha,\beta}={\mathrm{Cov}}\big{(}J(V,\alpha),J(V,\beta)\>\big{|}\>\mathcal{F}_{\infty}\big{)},$

with the $\sigma$-algebra

(8)
$\displaystyle\mathcal{F}_{\infty}:=\sigma\big{\\{}I_{\phi}\mid\phi\in\\{0,1\\}^{\ast}\big{\\}}.$

######  Remark 4.

A related functional limit law for the complexity of Radix Selection, an
algorithm to select ranks based on the bit expansions of the data, with a
limiting Gaussian process with a covariance function related to (7) can be
found in [12, Theorem 1.2]. See [17, Theorem 1.1] for another related
functional limit law.

The analysis of $\mathrm{QuickVal}$ is usually considered an intermediate step
to analyze the original $\mathrm{FIND}$ algorithm. Grübel and Rösler [9]
already pointed out that a version of $\mathrm{FIND}$ such as stated above
with $C^{\ast}_{n}(k)$ denoting the number of key comparisons for finding rank
$k$ within $(U_{1},\ldots,U_{n})$ does not lead to convergence within
$(D[0,1],d_{\mathrm{SK}})$ after the normalization
$\alpha\mapsto\frac{1}{n}C^{\ast}_{n}(\lfloor\alpha n\rfloor+1)$, where here
and below the convention $C^{\ast}_{n}(n+1):=C^{\ast}_{n}(n)$ is used. To
overcome this problem they propose a version that does not stop in case a
pivot turns out to be the rank to be selected by including the pivot in the
list $S_{<}$ and proceeding until a list of size $1$ is generated. Moreover,
their pivots are chosen uniformly at random. The number of key comparisons
$C^{\prime}_{n}(k)$ for Grübel and Rösler’s $\mathrm{FIND}$-version has the
property that

(9) $\displaystyle\left(\frac{1}{n}C^{\prime}_{n}\big{(}\lfloor\alpha
n\rfloor+1\big{)}\right)_{\alpha\in[0,1]}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}(S_{\alpha})_{\alpha\in[0,1]},\quad\mbox{ in
}(D[0,1],d_{\mathrm{SK}}),$

see [9, Theorem 4]. Without using random pivots we may also obtain right-
continuous limits by just recursively calling $\mathrm{FIND}(S_{\geq},0)$ in
case the pivot turns out to be the rank sought. We denote the number of key
comparisons for this version by $C_{n}(k)$, which is close to Grübel and
Rösler’s $\mathrm{FIND}$-version and also satisfies (9).

The convergence in (9) could only be stated weakly (not almost surely) since
Grübel und Rösler’s $\mathrm{FIND}$-version due to randomization within the
algorithm does not have a natural embedding on a probability space. Note that
the formulation of the $\mathrm{QuickVal}$ complexity does have such an
embedding which, e.g., makes the almost sure convergence in (4) possible.
However, it is easy to see that we have the distributional equality

(10) $\big{(}C_{n}\big{(}\lvert\\{U_{i}\leq\alpha:1\leq i\leq
n\\}\rvert\big{)}\big{)}_{\alpha\in[0,1]}\stackrel{{\scriptstyle
d}}{{=}}(S_{\alpha,n})_{\alpha\in[0,1]}.$

This allows to naturally couple the complexities on one probability space,
which we call its _natural coupling_. See [7, page 807] for a related
discussion of natural couplings.

To transfer Theorem 1 to $\mathrm{FIND}$ we need to align jumps to come up
with a suitable fluctuation process. The conventions $C_{n}(0):=C_{n}(1)$ and
$C_{n}(n+1):=C_{n}(n)$ are used.

######  Corollary 5.

Let $C_{n}(k)$ be the number of key comparisons required to select rank $1\leq
k\leq n$ within a set of $n$ data by $\mathrm{FIND}$ with the natural coupling
(10). Let $\Lambda_{n}:[0,1]\to[0,1]$, $n\in{\mathbb{N}}$, be any (random)
monotone increasing bijective function such that $\Lambda_{n}(\frac{k}{n+1})$
is equal to the element of rank $k$ within $\\{U_{1},\dots,U_{n}\\}$. Then we
have

$\displaystyle\left(\frac{C_{n}(\lfloor
t(n+1)\rfloor)-nS_{\Lambda_{n}(t)}}{\sqrt{n}}\right)_{t\in[0,1]}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}G_{\infty}\;\mbox{ in }(D[0,1],d_{\mathrm{SK}}),$

where $G_{\infty}$ is the process defined in Theorem 1.

The extended abstract is organized as follows: In Section 2 we introduce a
novel perturbation argument which is the basis of our analysis. Section 3
contains a criterion for weak convergence of probability measures on
$(D[0,1],d_{\mathrm{SK}})$, which is applied in Section 4 to proof Theorem 1
and Corollary 5. In Section 5 further functional fluctuation results are
stated for the number of swaps (key exchanges) required by $\mathrm{QuickVal}$
(depending on the specific algorithm used to partition $S$ into the sublists
$S_{<}$ and $S_{\geq}$) as well as functional fluctuation results for cost
measures which are based on key comparisons, where the cost of a comparison
may depend on the values of the keys.

##  2\. Perturbation of the data

$\mathrm{QuickVal}$ splits an interval $[L_{\phi},R_{\phi})$ by the first
value falling into $[L_{\phi},R_{\phi})$ denoted by $U_{\tau_{\phi}}$.
Obviously, this implies dependencies between the data $U_{i}$ and the lengths
$I_{\phi}$ of the intervals $[L_{\phi},R_{\phi})$. In the present section we
construct a perturbed sequence $(\widetilde{U}_{i})_{i\in{\mathbb{N}}}$ to the
data $(U_{i})_{i\in{\mathbb{N}}}$ such that we gain independence of
$(\widetilde{U}_{i})_{i\in{\mathbb{N}}}$ from the $\sigma$-algebra
$\mathcal{F}_{\infty}$ of the interval lengths defined in (8). In particular,
we aim that conditional on $\mathcal{F}_{\infty}$ the number of data
$(\widetilde{U}_{1},\ldots,\widetilde{U}_{n})$ falling into an interval
$[L_{\phi},R_{\phi})$ is binomial $B(n,I_{\phi})$ distributed, see Lemma 7
below.

Every value $U_{i}$, $i\in{\mathbb{N}}$, falls successively into subintervals
generated by $\mathrm{QuickVal}$ until becoming a pivot element. These
subintervals correspond to the path between the root of the corresponding
binary search tree and the node where $U_{i}$ is inserted. Let
$\phi_{i}\in\\{0,1\\}^{\ast}$ denote the node where $U_{i}$ is inserted.
Hence, we have $\tau_{\phi_{i}}=i$ and $U_{i}=L_{\phi_{i}}+I_{\phi_{i}0}$.

Let $(V_{i})_{i\in{\mathbb{N}}}$ be a sequence of i.i.d. $\mathrm{unif}[0,1]$
random variables being independent of $(U_{i})_{i\in{\mathbb{N}}}$. We define

(11) $\widetilde{U}_{i}:=L_{\phi_{i}}+I_{\phi_{i}}V_{i}.$

######  Lemma 6.

The sequence $(\widetilde{U}_{i})_{i\in{\mathbb{N}}}$ defined in (11) consists
of i.i.d. $\mathrm{unif}[0,1]$ distributed random variables and is independent
of $\mathcal{F}_{\infty}$.

###### Proof.

It suffices to show that $\widetilde{U}_{i}$ conditional on
$\mathcal{F}_{\infty}$ and $\widetilde{U}_{1},\dots,\widetilde{U}_{i-1}$ is
uniformly distributed on $[0,1]$ for all $i\in{\mathbb{N}}$. We use
infinitesimal notation to denote this claim by

${\mathbb{P}}\left(\widetilde{U}_{i}\in\mathrm{d}u\,\Big{|}\,\mathcal{F}_{\infty},\widetilde{U}_{1},\dots,\widetilde{U}_{i-1}\right)=\mathbf{1}_{[0,1]}(u)\mathrm{d}u,\quad
i\in{\mathbb{N}}.$

For each $i\in{\mathbb{N}}$ the random variables $\widetilde{U}_{i}$ and
$U_{i}$ fall into the same interval $[L_{\phi_{i}},R_{\phi_{i}})$, hence
$\phi_{1},\ldots,\phi_{i-1}$ are determined by
$\widetilde{U}_{1},\dots,\widetilde{U}_{i-1}$. Let us additionally condition
on $\phi_{i}$, then, by definition,

$\displaystyle{\mathbb{P}}\left(\widetilde{U}_{i}\in\mathrm{d}u\,\Big{|}\,\mathcal{F}_{\infty},\widetilde{U}_{1},\dots,\widetilde{U}_{i-1},\phi_{i}\right)=\frac{1}{I_{\phi_{i}}}\mathbf{1}_{[L_{\phi_{i}},R_{\phi_{i}})}(u)\mathrm{d}u.$

Note that $\phi_{i}$ denotes one of the $i$ external nodes of the binary
search tree with internal nodes denoted by $\phi_{1},\ldots,\phi_{i-1}$. We
denote by $\mathrm{Ext}_{i-1}$ the set of the labels of these external nodes.
Hence, conditional on $\mathcal{F}_{\infty},\phi_{1},\dots,\phi_{i-1}$ the
label $\phi_{i}$ is chosen from $\mathrm{Ext}_{i-1}$ with probability given by
the length of the corresponding interval, i.e.,
${\mathbb{P}}\left(\phi_{i}=\phi\,|\,\mathcal{F}_{\infty},\phi_{1},\dots,\phi_{i-1}\right)=I_{\phi}$
for all $\phi\in\mathrm{Ext}_{i-1}$. Thus, by the law of total probability we
obtain

${\mathbb{P}}\left(\widetilde{U}_{i}\in\mathrm{d}u\,\Big{|}\,\mathcal{F}_{\infty},\widetilde{U}_{1},\dots,\widetilde{U}_{i-1}\right)=\sum_{\phi\in\mathrm{Ext}_{i-1}}I_{\phi}\frac{1}{I_{\phi}}\mathbf{1}_{[L_{\phi},R_{\phi})}(u)\mathrm{d}u=\mathbf{1}_{[0,1]}(u)\mathrm{d}u.$

This implies the assertion. ∎

The $\widetilde{U}_{i}$ are now coupled with the $U_{i}$ but independent of
the $I_{\phi}$. To compare with the number of key comparisons required by
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ we define

$\widetilde{S}_{\alpha,k,n}:=\sum_{i=1}^{n}\mathbf{1}_{[L_{\alpha,k},R_{\alpha,k})}(\widetilde{U}_{i}).$

######  Lemma 7.

Conditional on $I_{\alpha,k}$ we have that $\widetilde{S}_{\alpha,k,n}$ has
the binomial B$(n,I_{\alpha,k})$ distribution. Moreover, for all
$\alpha\in[0,1]$, $n\in{\mathbb{N}}$ and $0\leq k\leq n$ we have

(12) $S_{\alpha,k,n}\leq(\widetilde{S}_{\alpha,k,n}-1)^{+}\leq
S_{\alpha,k,n}+k-1.$

###### Proof.

The conditional distribution of $\widetilde{S}_{\alpha,k,n}$ follows from
Lemma 6. Recall that $S_{\alpha,k,n}$ is defined as
$\sum_{i=\tau_{\alpha,k}}^{n}\mathbf{1}\\{L_{\alpha,k-1}\leq
U_{i}<R_{\alpha,k-1}\\}$. By definition, $U_{i}$ and $\widetilde{U}_{i}$ are
in the interval $[L_{\phi_{i}},R_{\phi_{i}})$ for all $i\in{\mathbb{N}}$. If
$U_{i}\in(L_{\alpha,k},R_{\alpha,k})$, then $U_{i}$ appears as a pivot after
the $k$-th pivot. Hence, its interval $[L_{\phi_{i}},R_{\phi_{i}})$ and thus
also $\widetilde{U}_{i}$ are contained in $(L_{\alpha,k},R_{\alpha,k})$. The
$k$-th pivot $U_{\tau_{\alpha,k}}$ itself does not contribute to
$S_{\alpha,k,n}$, which implies the left inequality stated in the present
lemma.

For the right inequality, assume for some $i\in{\mathbb{N}}$ that the
perturbed value $\widetilde{U}_{i}$ is in $(L_{\alpha,k},R_{\alpha,k})$, but
$U_{i}$ is not. Then the corresponding interval $(L_{\phi_{i}},R_{\phi_{i}})$
must contain $(L_{\alpha,k},R_{\alpha,k})$, thus making $U_{i}$ a pivot that
appears before the $k$-th pivot. Since there are only $k$ such pivots, the
right inequality follows. ∎

##  3\. On Weak Convergence in $D[0,1]$

To prove the convergence in distribution in Theorem 1 within the space
$(D[0,1],d_{\mathrm{SK}})$ we use the following Proposition 8. It can be
proved by classical tools of weak convergence theory based on a study of the
modulus of continuity and the Arzelà–Ascoli theorem in form of a general
theorem of Billingsley [2, Theorem 13.2].

######  Proposition 8.

Let $X_{1},X_{2},\dots$ be a sequence of random variables in
$(D[0,1],d_{SK})$. Suppose that for every $K\in{\mathbb{N}}$, there exist
random càdlàg step functions $X^{K}_{1},X^{K}_{2},\dots$ with all jumps
contained in $\\{U_{\phi}\mid\phi\in\\{0,1\\}^{\ast},\lvert\phi\rvert<K\\}$.
If

  1. (i)

for all $r\in{\mathbb{N}}$ and $\alpha_{1},\dots,\alpha_{r}\in[0,1]$, the
marginals $\mathcal{L}(X_{n}(\alpha_{1}),\dots,X_{n}(\alpha_{r}))$ converge
weakly to some distribution $\mu_{\alpha_{1},\dots,\alpha_{r}}$,

  2. (ii)

for all $\varepsilon>0$,

(13)
$\lim_{K\to\infty}\limsup_{n\to\infty}{\mathbb{P}}\left(\big{\lVert}X_{n}-X^{K}_{n}\big{\rVert}_{\infty}>\varepsilon\right)\to
0,$

then $(X_{n})_{n\in{\mathbb{N}}}$ converges in distribution to a random
variable $X$ on $(D[0,1],d_{SK})$, and for all $r\in{\mathbb{N}}$ and
$\alpha_{1},\dots,\alpha_{r}\in[0,1]$ we have

(14)
$\mathcal{L}(X(\alpha_{1}),\dots,X(\alpha_{r}))=\mu_{\alpha_{1},\dots,\alpha_{r}}.$

##  4\. Proof of Theorem 1

To split the contributions to the process $G_{n}$ into costs resulting from
above and below a level $K\in{\mathbb{N}}$ we define

(15) $\displaystyle
G_{\alpha,k,n}:=\frac{S_{\alpha,k,n}-nI_{\alpha,k}}{\sqrt{n}}$

as the normalized fluctuations of the contribution at level $k$, and set

(16) $\displaystyle G^{\leq K}_{\alpha,n}:=\sum_{k=0}^{K}G_{\alpha,k,n},\qquad
G^{\leq K}_{n}:=\big{(}G^{\leq K}_{\alpha,n}\big{)}_{\alpha\in[0,1]},\qquad
G^{>K}_{\alpha,n}:=\sum_{k=K+1}^{\infty}G_{\alpha,k,n}.$

Hence, $G_{\alpha,n}=G^{\leq K}_{\alpha,n}+G^{>K}_{\alpha,n}$. Analogously,
for the perturbed values $\widetilde{S}_{k,n}$ we define

(17) $\displaystyle
W_{\alpha,k,n}:=\frac{\widetilde{S}_{\alpha,k,n}-nI_{\alpha,k}}{\sqrt{n}},\qquad
W^{\leq K}_{\alpha,n}:=\sum_{k=0}^{K}W_{\alpha,k,n}\qquad W^{\leq
K}_{n}:=\big{(}W^{\leq K}_{\alpha,n}\big{)}_{\alpha\in[0,1]}.$

######  Lemma 9.

For all $K\in{\mathbb{N}}$ we have convergence in distribution of $(G^{\leq
K}_{n})_{n\in{\mathbb{N}}}$ towards a mixture $G^{\leq K}_{\infty}=(G^{\leq
K}_{\alpha,\infty})_{\alpha\in[0,1]}$ of centered Gaussian processes within
$\|\cdot\|_{\infty}$. Conditional on $\mathcal{F}_{\infty}$, the limit
$G^{\leq K}_{\infty}$ is a centered Gaussian process with covariance function
given, for $\alpha,\beta\in[0,1]$ by

(18) $\displaystyle{\mathrm{Cov}}\big{(}G^{\leq K}_{\alpha,\infty},G^{\leq
K}_{\beta,\infty}\mid\mathcal{F}_{\infty}\big{)}=\sum_{k=0}^{K\wedge
J}\sum_{j=0}^{K}I_{\alpha,j\vee k}+\big{(}1+(K\wedge
J)\big{)}\sum_{j=J+1}^{K}I_{\beta,j}-S_{\alpha}^{\leq K}S_{\beta}^{\leq K},$

where $J=J(\alpha,\beta)$ is as in Theorem 1 and $S_{\alpha}^{\leq
K}:=\sum_{k=0}^{K}I_{\alpha,k}$. The stated convergence in distribution also
holds conditionally in $\mathcal{F}_{\infty}$, i.e., we have almost surely
that $\mathcal{L}(G^{\leq K}_{n}\mid\mathcal{F}_{\infty})$ converges weakly
towards $\mathcal{L}(G^{\leq K}_{\infty}\mid\mathcal{F}_{\infty})$.

###### Proof.

First note that by Lemma 7 we have $\left\lVert G^{\leq K}_{n}-W^{\leq
K}_{n}\right\rVert_{\infty}<K^{2}/\sqrt{n}$, so it suffices to show the lemma
for $W^{\leq K}_{n}$. Conditional on $\mathcal{F}_{\infty}$, the value of
$W^{\leq K}_{\alpha,n}$ is given by

(19) $W^{\leq
K}_{\alpha,n}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\sum_{k=0}^{K}\mathbf{1}\\{L_{\alpha,k}\leq\widetilde{U}_{i}<R_{\alpha,k}\\}-(R_{\alpha,k}-L_{\alpha,k}),$

thus the $2^{k}$ different values of the process $W^{\leq K}_{n}$ can be
expressed as the sum of $n$ centered, bounded i.i.d. random vectors, scaled by
$1/\sqrt{n}$. By the multivariate central limit theorem, these converge
towards a multivariate, centered normal variable. As the positions of the
jumps, still conditional on $\mathcal{F}_{\infty}$, are fixed, we have
convergence of $W^{\leq K}_{n}$ and thus also of $G^{\leq K}_{n}$ towards a
Gaussian process. Define
$X_{\alpha,k}:=\mathbf{1}\\{L_{\alpha,k-1}\leq\widetilde{U}_{1}<R_{\alpha,k-1}\\}$.
The covariance function then is given by

$\displaystyle{\mathrm{Cov}}\big{(}G^{\leq K}_{\alpha,\infty},G^{\leq
K}_{\beta,\infty}\mid\mathcal{F}_{\infty}\big{)}$
$\displaystyle={\mathrm{Cov}}\bigg{(}\sum_{k=0}^{K}X_{\alpha,k},\sum_{j=0}^{K}X_{\beta,j}\>\bigg{|}\>\mathcal{F}_{\infty}\bigg{)}$
$\displaystyle=\sum_{k=0}^{K}\sum_{j=0}^{K}\mathbb{E}\left[X_{\alpha,k}X_{\beta,j}\,\Big{|}\,\mathcal{F}_{\infty}\right]-S^{\leq
K}_{\alpha}S^{\leq K}_{\beta}$ (20) $\displaystyle=\sum_{k=0}^{K\wedge
J}\sum_{j=0}^{K}I_{\alpha,k\vee j}+\big{(}1+(K\wedge
J)\big{)}\sum_{j=J+1}^{K}I_{\beta,j}-S_{\alpha}^{\leq K}S_{\beta}^{\leq K}.$

The assertion follows. ∎

To see that the covariance functions in (4) converge towards the covariance
function of $G_{\infty}$ stated in Theorem 1 we restate a Lemma of Grübel and
Rösler [9, Lemma 1] that the maximal length of the intervals at a level is
decreasing geometrically with increasing levels. It is obtained observing that
$\mathbb{E}\left[\sum_{\lvert\phi\rvert=k}I_{\phi}^{2}\right]=(2/3)^{k}$ and
states:

######  Lemma 10.

There exists an a.s. finite random variable $K_{1}$ such that for all $k\geq
K_{1}$:

(21) $\max_{\alpha\in[0,1]}I_{\alpha,k}\leq k\left(\frac{2}{3}\right)^{k/2}.$

Lemma 10 implies that the covariance functions of $G^{\leq K}_{\infty}$ from
(18) converge a.s. to the covariance function of $G_{\infty}$ from (6).

For the costs from levels $k>K$ we find:

######  Proposition 11.

For all $\varepsilon,\eta>0$ there are constants $K,N\in{\mathbb{N}}$ such
that for all $n\geq N$

(22) ${\mathbb{P}}\left(\lVert
G^{>K}_{n}\rVert_{\infty}>\eta\right)<\varepsilon.$

We postpone the proof of the latter proposition and first use Proposition 11
and Lemma 9 to show convergence of the finite-dimensional distributions,
denoted fdd-convergence.

######  Lemma 12.

We have fdd-convergence of $G_{n}$ towards $G_{\infty}$.

###### Proof.

For any $K$, we can split $G_{n}=G^{\leq K}_{n}+G^{>K}_{n}$. By Lemma 9, we
have

$\displaystyle G^{\leq
K}_{n}\stackrel{{\scriptstyle\mathrm{fdd}}}{{\longrightarrow}}G^{\leq
K}_{\infty}\qquad(n\to\infty).$

Furthermore, because the covariance functions of the $G^{\leq K}_{\infty}$
converge a.s., we obtain

$\displaystyle G^{\leq
K}_{\infty}\stackrel{{\scriptstyle\mathrm{fdd}}}{{\longrightarrow}}\
G_{\infty}\qquad(K\to\infty)$

by Lévy’s continuity theorem. Hence, for all
$\alpha_{1},\dots,\alpha_{\ell}\in[0,1]$ and all
$t_{1},\dots,t_{\ell}\in\mathbb{R}$ we find a sequence
$(K_{n})_{n\in{\mathbb{N}}}$ in ${\mathbb{N}}$ such that

${\mathbb{P}}\left(G^{\leq K_{n}}_{\alpha_{1},n}<t_{1},\dots,G^{\leq
K_{n}}_{\alpha_{\ell},n}<t_{\ell}\right)\longrightarrow{\mathbb{P}}\left(G_{\alpha_{1},\infty}<t_{1},\dots,G_{\alpha_{\ell},\infty}<t_{\ell}\right)\quad(n\to\infty).$

Now, since $\lVert G^{>K_{n}}_{n}\rVert_{\infty}\to 0$ in probability by
Proposition 11 the claim of Lemma 12 follows by Slutzky’s theorem. ∎

To prepare for the proof of Proposition 11, we show that the fluctuations on
each level are also at least geometrically decreasing. Recall $K_{1}$ from
Lemma 10.

######  Lemma 13.

There exists a constant $a>1$ such that for all $k,n\in{\mathbb{N}}$

${\mathbb{P}}\left(\max_{\alpha\in[0,1]}\lvert
W_{\alpha,k,n}\rvert>a^{-k},\,K_{1}\leq k\right)\leq b(k)+c(k,n)$

with $b(k),c(k,n)\geq 0$ such that

(23) $\sum_{k=1}^{\infty}b(k)<\infty\quad\mbox{ and
}\quad\sum_{k=1}^{\lfloor(9/2)\log n\rfloor}c(k,n)\to 0\quad(n\to\infty).$

For the proof of Lemma 13 we require the following Chernoff bound:

######  Lemma 14.

Let $S_{n}$ be binomial $B(n,p)$ distributed for some $p\in[0,1]$ and
$n\in{\mathbb{N}}$ and let $\mu:=\mathbb{E}[S_{n}]$, $\varepsilon\geq 0$. Then

${\mathbb{P}}\left(S_{n}\notin\big{(}(1-\varepsilon)\mu,(1+\varepsilon)\mu\big{)}\right)\leq
2\exp\left(-\frac{\varepsilon^{2}\mu}{2+\varepsilon}\right).$

###### Proof.

Combine upper and lower bound in McDiarmid [15, Theorem 2.3]. ∎

###### Proof of Corollary 13.

Fix some $\alpha\in[0,1]$. Conditionally on $I_{k,\alpha}$, the costs
$\widetilde{S}_{\alpha,k,n}$ are $B(n,I_{k,\alpha})$-distributed by Lemma 6.
The Chernoff bound in Lemma 14 implies

$\displaystyle{\mathbb{P}}\left(\lvert
W_{\alpha,k,n}\rvert>a^{-k}\,\Big{|}\,I_{\alpha,k}\right)$
$\displaystyle={\mathbb{P}}\left(\big{\lvert}\widetilde{S}_{\alpha,k,n}-nI_{\alpha,k}\big{\rvert}>\sqrt{n}a^{-k}\,\Big{|}\,I_{\alpha,k}\right)$
$\displaystyle\leq
2\exp\left(-\frac{na^{-2k}}{nI_{\alpha,k}(2+\sqrt{n}a^{-k}/(nI_{\alpha,k}))}\right)$
(24)
$\displaystyle=2\exp\left(-\left(2a^{2k}I_{\alpha,k}+a^{k}/\sqrt{n}\right)^{-1}\right).$

For the two summands in the exponent in (24) we have the following behavior:
Summand $2a^{2k}I_{k,\alpha}$ is falling geometrically with $k$ for
sufficiently small $a>1$. Summand $a^{k}/\sqrt{n}$ is falling with $n$, but
growing with $k$. To separate these two contributions, note that
$\exp({x^{-1}})\geq\frac{1}{m!}x^{-m}$ and thus $\exp({-x^{-1}})\leq m!x^{m}$
for all $m\in{\mathbb{N}}$ and $x\geq 0$. Choosing $m=7$, we obtain

$\displaystyle{\mathbb{P}}\left(\lvert
W_{\alpha,k,n}\rvert>a^{-k}\,\Big{|}\,I_{\alpha,k}\right)$ $\displaystyle\leq
2\cdot 7!\left(2a^{2k}I_{\alpha,k}+a^{k}/\sqrt{n}\right)^{7}$
$\displaystyle\leq 2^{14}7!a^{14k}I_{\alpha,k}^{7}+2^{7}7!a^{7k}n^{-7/2}$

by convexity of $x\mapsto x^{7}$. Note that the $2^{k}$ intervals at level $k$
have lengths $I_{\alpha,k}$ summing to $1$. Hence,

$\displaystyle{\mathbb{P}}\left(\max_{\alpha\in[0,1]}\lvert
W_{\alpha,k,n}\rvert>a^{-k}\,\Big{|}\,I_{\alpha,k}\right)$ $\displaystyle\leq
2^{14}7!a^{14k}\max_{\alpha\in[0,1]}I_{\alpha,k}^{6}+2^{7}7!(2a^{7})^{k}n^{-7/2}.$

When furthermore $K_{1}\leq k$, by Lemma 10 the length $I_{\alpha,k}$ is
bounded by $k\frac{2}{3}^{k/2}$, hence

${\mathbb{P}}\left(\max_{\alpha\in[0,1]}\lvert
W_{\alpha,k,n}\rvert>a^{-k},\,K_{1}\leq k\right)\leq
2^{14}7!ka^{14k}\left(\frac{2}{3}\right)^{3k}+2^{7}7!(2a^{7})^{k}n^{-7/2}.$

Define the first summand on the right hand side of the latter inequality by
$b(k)$ and the second summand by $c(k,n)$. For all $1<a<(3/2)^{3/14}$ the
$b(k)$ form a convergent series. To also show the second statement in (23)
note that

$\sum_{k=1}^{\lfloor(9/2)\log
n\rfloor}c(k,n)=\mathrm{O}\left(\left(2a^{7}\right)^{(9/2)\log
n}n^{-7/2}\right)=\mathrm{O}\left(n^{(9/2)\log 2+(9/2)\cdot 7\log
a-7/2}\right).$

The latter $\mathrm{O}$-term converges to $0$ for $(63/2)\log a<7/2-(9/2)\log
2\approx 0.381\dots$, thus we may choose $a$ as required. ∎

We are now prepared for the proof of Proposition 11.

###### Proof of Proposition 11.

Let $\varepsilon,\eta>0$. To $K_{1}$ from Lemma 10 and $a$ and $b(k)$ from
Lemma 13 we choose $K$ sufficiently large such that

(25)
$\displaystyle{\mathbb{P}}(K_{1}>K)\leq\frac{\varepsilon}{4},\qquad\sum_{k=K}^{\infty}a^{-k}\leq\frac{\eta}{4}\qquad\mbox{and}\qquad\sum_{k=K}^{\infty}b(k)\leq\frac{\varepsilon}{4}.$

Let $H_{n}$ be the maximum amount of steps needed by
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ for any $\alpha$. Thus,
$H_{n}$ is also the height of the binary search tree built from
$U_{1},\dots,U_{n}$. Devroye [4] showed that the height has expectation
$\mathbb{E}[H_{n}]=\gamma\log n+o(\log n)$ with $\gamma=4.311\ldots$ Reed [16]
further showed that $\mathrm{Var}(H_{n})=\mathrm{O}(1)$. Hence, we can choose
$N$ sufficiently large such that

(26) $\displaystyle{\mathbb{P}}\left(H_{n}>\lfloor(9/2)\log
n\rfloor\right)<\frac{\varepsilon}{4},\qquad\sum_{k=1}^{\lfloor(9/2)\log
n\rfloor}c(k,n)\leq\frac{\varepsilon}{4},\qquad\text{and}\qquad\frac{\left((9/2)\log
n\right)^{2}}{\sqrt{n}}\leq\frac{\eta}{4}$

for all $n\geq N$. Subsequently we use the decomposition

$\displaystyle G^{>K}_{\alpha,n}=\sum_{k=K+1}^{\lfloor(9/2)\log
n\rfloor}\frac{S_{\alpha,k,n}-nI_{\alpha,k}}{\sqrt{n}}+\sum_{\lfloor(9/2)\log
n\rfloor+1}^{\infty}\frac{S_{\alpha,k,n}-nI_{\alpha,k}}{\sqrt{n}}=:\Gamma_{n}+G^{>\lfloor(9/2)\log
n\rfloor}_{\alpha,n}$

and consider the event

$\displaystyle A_{n}:=\\{K_{1}>K\\}\cup\\{H_{n}>\lfloor(9/2)\log n\rfloor\\}.$

We have ${\mathbb{P}}(A_{n})<\varepsilon/2$ for all $n\geq N$. Note that on
$A_{n}^{c}$ (the complement of $A_{n}$) we have $S_{\alpha,k,n}=0$ for all
$k>\lfloor(9/2)\log n\rfloor$ and also the bound on $I_{\alpha,k}$ from Lemma
10 applies, hence

$\displaystyle\left|G^{>\lfloor(9/2)\log n\rfloor}_{\alpha,n}\right|$
$\displaystyle\leq\sum_{\lfloor(9/2)\log
n\rfloor+1}^{\infty}\sqrt{n}I_{\alpha,k}\leq\sum_{\lfloor(9/2)\log
n\rfloor+1}^{\infty}\sqrt{n}k\left(\frac{2}{3}\right)^{k/2}$
$\displaystyle=\mathrm{O}\left(n^{1/2-(9/4)\log(3/2)}\log
n\right)=\mathrm{o}(1)$

since $(9/4)\log(3/2)=0.912\ldots$ Hence, we can enlarge $N$ so that on
$A_{n}^{c}$ we have $\big{\lvert}G^{>\lfloor(9/2)\log
n\rfloor}_{\alpha,n}\big{\rvert}<\eta/2$ for all $n\geq N$. This implies the
bound

$\displaystyle{\mathbb{P}}\left(\lvert G^{>K}_{\alpha,n}\rvert>\eta\right)$
$\displaystyle\leq{\mathbb{P}}(A_{n})+{\mathbb{P}}\left(\left\\{\lvert
G^{>K}_{\alpha,n}\rvert>\eta\right\\}\cap A_{n}^{c}\right)$ (27)
$\displaystyle\leq\frac{\varepsilon}{2}+{\mathbb{P}}\left(\left\\{\lvert\Gamma_{n}\rvert>\frac{\eta}{2}\right\\}\cap
A_{n}^{c}\right)+{\mathbb{P}}\left(\left\\{\big{\lvert}G^{>\lfloor(9/2)\log
n\rfloor}_{\alpha,n}\big{\rvert}>\frac{\eta}{2}\right\\}\cap
A_{n}^{c}\right).$

Note that the third summand in (27) is $0$. Hence, it remains to bound the
second summand in (27). To this end note that

$\displaystyle\lvert\Gamma_{n}\rvert$
$\displaystyle\leq\sup_{\alpha\in[0,1]}\sum_{k=K+1}^{\lfloor(9/2)\log
n\rfloor}\left({\left\lvert\frac{\widetilde{S}_{\alpha,k,n}-nI_{\alpha,k}}{\sqrt{n}}\right\rvert+\left\lvert\frac{S_{\alpha,k,n}-\widetilde{S}_{\alpha,k,n}}{\sqrt{n}}\right\rvert}\right)$
(28) $\displaystyle\leq\Bigg{(}\sum_{k=K+1}^{\lfloor(9/2)\log
n\rfloor}\max_{\alpha\in[0,1]}\lvert
W_{\alpha,k,n}\rvert\Bigg{)}+\frac{\lfloor(9/2)\log n\rfloor^{2}}{\sqrt{n}},$

where Lemma 7 is used. The third relation in (26) assures that the second term
in (28) is smaller than $\eta/4$. In view of the second relation in (25) and
(28), we have

$\displaystyle\left\\{\left\lvert\Gamma_{n}\right\rvert>\frac{\eta}{2}\right\\}\cap
A_{n}^{c}\subset\bigcup_{k=K}^{\lfloor(9/2)\log
n\rfloor}\left\\{\max_{\alpha\in[0,1]}\lvert
W_{\alpha,k,n}\rvert>a^{-k},\,K_{1}\leq k\right\\}.$

Thus, Lemma 13 together with (25) and (26) imply that the second summand in
(27) is bounded by $\varepsilon/2$. This implies the assertion. ∎

###### Proof of Theorem 1.

We apply Lemma 8 to $G_{n}$ and $G_{n}^{\leq K}$. The first condition, fdd
convergence, is Lemma 12, the second condition is Proposition 11. ∎

We now transfer the fluctuation result for $\mathrm{QuickVal}$ in Theorem 1 to
the original Find process in Corollary 5.

###### Proof of Corollary 5.

Let $\widetilde{F}_{n}$ be the inverse of $\Lambda_{n}$ in the statement of
Corollary 5. By definition of $\Lambda_{n}$, the value of the element
$U_{(k)}$ of rank $k$ within $U_{1},\dots,U_{n}$ is given by $\frac{k}{n+1}$,
so

(29)
$\big{\lfloor}(n+1)\widetilde{F}_{n}(\alpha)\big{\rfloor}=\big{\lvert}\left\\{U_{i}\leq\alpha\mid
1\leq i\leq n\right\\}\big{\rvert}$

for all $\alpha\in[0,1)$. Thus,
$C_{n}\big{(}\big{\lfloor}(n+1)\widetilde{F}_{n}(\alpha)\big{\rfloor}\big{)}=S_{\alpha,n}$
a.s. for all $\alpha\in[0,1]$, see (10). For $\alpha=1$ note that
$\widetilde{F}_{n}(\alpha)=1$ and $C_{n}(n+1)=C_{n}(n)$ by definition. The
Skorokhod distance $d_{\mathrm{SK}}$ is then bounded by

$\displaystyle d_{\mathrm{SK}}\left(G_{n},\left(\frac{C_{n}(\lfloor
t(n+1)\rfloor)-nS_{\Lambda_{n}(t)}}{\sqrt{n}}\right)_{t\in[0,1]}\right)$
$\displaystyle=d_{\mathrm{SK}}\left(G_{n},\left(\frac{S_{\Lambda_{n}(t),n}-nS_{\Lambda_{n}(t)}}{\sqrt{n}}\right)_{t\in[0,1]}\right)$
$\displaystyle=d_{\mathrm{SK}}\left(G_{n},(G_{\Lambda_{n}(t),n})_{t\in[0,1]}\right)$
$\displaystyle\leq\lVert\widetilde{F}_{n}-\mathrm{id}\rVert_{\infty}.$

By (29), $\widetilde{F}_{n}$ is close to the empirical distribution function
and thus converges a.s. uniformly to the identity $\mathrm{id}$ by the
Glivenko–Cantelli theorem. The statement of Corollary 5 then follows from
Slutzky’s theorem. ∎

##  5\. Further cost measures

In this section we sketch results analogous to Theorem 1 for other cost
measures than the number of key comparisons. We consider the number of swaps
required by $\mathrm{QuickVal}$ which however depends on the implementation of
the procedure to partition the input $(U_{1},\ldots,U_{n})$ into the sublists
$S_{<}$ and $S_{\geq}$. We consider two such procedures, the one originally
proposed by Hoare [10] and one that is attributed to Lomuto, see [1, 3, 13].
Our results are stated in Subsection 5.1.

As a further cost measure we consider the model where the costs to compare two
keys may depend on their values, e.g., the number of bit comparisons required
to compare them when they are given by their binary expansions. The total cost
for all key comparisons required by
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ or
$\mathrm{FIND}((U_{1},\ldots,U_{n}),k)$ is no longer determined by the fact
that the ranks of $(U_{1},\ldots,U_{n})$ form an uniformly random permutation.
Here, the distribution of the $U_{i}$ matters. We only consider the uniform
distribution as in the previous sections and hope to report on other
distributions in the full paper version of this extended abstract. Our results
are stated in Subsection 5.2. A probabilistic analysis for the number of bit
comparisons of the related $\mathrm{Quicksort}$ algorithms was given in [6,
5].

###  5.1. Number of swaps

Usually, QuickSelect is implemented in-place, meaning that it only requires
the memory for the list $S$ of values and a bounded amount of additional
memory. This is achieved by swapping values within $S$ so that the elements of
$S_{<}$ and $S_{\geq}$ are contained in contiguous parts of the list. Such a
procedure is called partition. There are various procedures of partition.

The original procedure by Hoare [10] searches the list $S$ from both ends at
once: It repeatedly finds the index $i=\min\\{2\leq i\leq n\mid
U_{i}>U_{1}\\}$ of the leftmost element bigger than the pivot and the index
$j:=\max\\{2\leq j\leq n\mid U_{j}<U_{1}\\}$ of the rightmost element smaller
than the pivot. If $i<j$, it swaps $U_{i}$ and $U_{j}$. Else the algorithm
terminates.

A simpler, but less efficient implementation is the so-called Lomuto partition
scheme [1, 3, 13] that only searches from one end of $S$. It keeps track of
the amount $i$ of elements at the start of the list it has already swapped. In
every step, it finds the index $j:=\max\\{2\leq j\leq n\mid U_{j}<U_{1}\\}$ of
the rightmost element smaller than the pivot. If $i+1<j$, it swaps $U_{i+1}$
and $U_{j}$ and increases $i$ by one. Otherwise the algorithm terminates.

Both partition schemes only compare elements to the pivot, so the model of
randomness is preserved within the sublists $S_{<}$ and $S_{\geq}$. However,
their original order is not preserved, so QuickSelect run on
$U_{1},\dots,U_{n}$ will usually not select the same pivots as QuickSelect on
$U_{1},\dots,U_{n+1}$. For convenience, we assume that the pivot to split a
sublist $S^{\prime}$ of $S$ is the element of $S^{\prime}$ that came first in
the original list $S$. We call this choice of the pivots a _suitable
embedding_.

####  5.1.1. Hoare’s partition

For Hoare’s partition, via a hypergeometric distribution the expected number
of swaps in step $k$ given $\mathcal{F}_{\infty}$ is approximately
$nI_{\alpha,k+1}(I_{\alpha}-I_{\alpha,k})/I_{\alpha,k}$, which leads to the
limit process $L=(L_{\alpha})_{\alpha\in[0,1]}$ given by

$L_{\alpha}:=\sum_{k=0}^{\infty}\frac{I_{\alpha,k+1}(I_{\alpha}-I_{\alpha,k})}{I_{\alpha,k}},\quad\alpha\in[0,1].$

It is now possible to study the fluctuations by their contributions from the
individual levels and combine them as for the number of key comparisons above.
Since we are still in the range of the central limit theorem we again obtain a
mixture of centered Gaussian processes. To be explicit, first denote by
$Z_{\phi}$ the limit of the $G_{\alpha,k,n}$ as $n\to\infty$ where
$\phi=\phi(\alpha,k)\in\\{0,1\\}^{k}$. Further, denote by
$\\{Y_{\phi}\,|\,\phi\in\\{0,1\\}^{\ast}\\}$ a set of i.i.d.
$\mathcal{N}(0,1)$ random variables being independent of
$\\{Z_{\phi}\,|\,\phi\in\\{0,1\\}^{\ast}\\}$ and of $\mathcal{F}_{\infty}$.
Then the limiting process
$G^{\mathrm{swap}}=(G^{\mathrm{swap}}_{\alpha})_{\alpha\in[0,1]}$ is given by

(30)
$G^{\mathrm{swap}}_{\alpha}:=\;\sum_{\mathclap{\phi\in\\{\phi(k,\alpha)\,|\,k\in{\mathbb{N}}_{0}\\}}}\quad
Y_{\phi}\frac{I_{\phi 0}I_{\phi 1}}{I_{\phi}^{3/2}}+Z_{\phi 0}\frac{I_{\phi
1}}{I_{\phi}}+Z_{\phi 1}\frac{I_{\phi 0}}{I_{\phi}}-Z_{\phi}\frac{I_{\phi
0}I_{\phi 1}}{I_{\phi}},\quad\alpha\in[0,1].$

Then we have the following result for key exchanges corresponding to Theorem
1.

######  Theorem 15.

Let $K_{\alpha,n}$ be the number of key exchanges required by
$\mathrm{QuickVal}((U_{1},\dots,U_{n}),\alpha)$ with Hoare’s partition
algorithm in a suitable embedding. Then, as $n\to\infty$, we have

$\displaystyle\left(\frac{K_{\alpha,n}-nL_{\alpha}}{\sqrt{n}}\right)_{\alpha\in[0,1]}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}G^{\mathrm{swap}}\quad\mbox{in
}(D[0,1],d_{\mathrm{SK}}).$

####  5.1.2. Lomuto’s partition

The Lomuto partition is simpler to implement and much easier to analyze. The
Lomuto partition swaps every element smaller than the pivot, so the amount of
swaps at some path $\phi\in\\{0,1\\}^{*}$ is given by $S_{\phi 0}+1$. With the
$Z_{\phi}$ introduced in Subsection 5.1.1 we find that
$(Z_{\phi})_{\phi\in\\{0,1\\}^{\ast}}$ is a mixture of centered Gaussian
processes with conditional covariance function given by

${\mathrm{Cov}}\left(Z_{\phi},Z_{\psi}\mid\mathcal{F}_{\infty}\right)=I_{\phi\vee\psi}-I_{\phi}I_{\psi},\quad\phi,\psi\in\\{0,1\\}^{\ast},$

where $I_{\phi\vee\psi}$ is the length of the interval
$[L_{\phi},R_{\phi})\cap[L_{\psi},R_{\psi})$, thus $I_{\phi\vee\psi}$ is only
nonzero if one of $\psi$ and $\phi$ is a prefix of the other. Then the
limiting process $G^{\mathrm{Lo}}=(G^{\mathrm{Lo}}_{\alpha})_{\alpha\in[0,1]}$
is given by

$G^{\mathrm{Lo}}_{\alpha}=\sum_{k=0}^{\infty}Z_{\phi(\alpha,k)0},\quad\alpha\in[0,1].$

We can directly apply Lemma 13 and our proof for the number of key comparisons
can be straightforwardly transferred.

######  Theorem 16.

Let $K_{\alpha,n}^{\mathrm{Lo}}$ be the number of key exchanges required by
$\mathrm{QuickVal}((U_{1},\dots,U_{n}),\alpha)$ with Lomuto’s partition
procedure in a suitable embedding. Then, as $n\to\infty$, we have

$\displaystyle\left(\frac{K_{\alpha,n}^{\mathrm{Lo}}-n\sum_{k=0}^{\infty}I_{\phi(\alpha,k)0}}{\sqrt{n}}\right)_{\alpha\in[0,1]}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}G^{\mathrm{Lo}}\quad\mbox{in }(D[0,1],d_{\mathrm{SK}}).$

###  5.2. Number of bit comparisons

We now consider the model where the cost to compare two keys depends on their
values. These costs are described by a measurable _cost function_
$\beta:[0,1]^{2}\to[0,\infty)$, and we require that they have a polynomial
tail, that is: There are constants $c$, $\varepsilon>0$ such that for all
$u\in[0,1],x\in{\mathbb{N}}$ and for $V\sim\mathrm{unif}[0,1]$

${\mathbb{P}}\left(\beta(u,V)\geq x\right)\leq cx^{-1/\varepsilon}.$

This condition is called $(c,\varepsilon)$_-tameness_ , see Matterer [14], and
$\beta$ is called to be $\varepsilon$_-tame_ if it is $(c,\varepsilon)$-tame
for some $c>0$. Note that, e.g., $\beta$ counting the number of bit
comparisons is $\varepsilon$-tame for all $\varepsilon>0$. The costs of
$\mathrm{QuickVal}((U_{1},\ldots,U_{n}),\alpha)$ in this model are given by

$S^{\beta}_{\alpha,n}:=\sum_{k=0}^{\infty}\sum_{\tau_{\alpha,k}<i\leq
n}\mathbf{1}_{[L_{\alpha,k},R_{\alpha,k})}(U_{i})\beta(U_{\tau_{\alpha,k}},U_{i})$

and the limit is, with $V\sim\mathrm{unif}[0,1]$ being independent of the
$U_{1},\dots,U_{n}$, given as

$S^{\beta}_{\alpha,\infty}:=\sum_{k=0}^{\infty}\mathbb{E}\left[\mathbf{1}_{[L_{\alpha,k},R_{\alpha,k})}(V)\beta(U_{\tau_{\alpha,k}},V)\,\Big{|}\,\mathcal{F}_{\infty}\right]$

Matterer [14, Theorem 6.4 and Theorem 6.14] shows for
$\varepsilon<\frac{1}{2}$ that for fixed $\alpha\in[0,1]$ the resulting
residual

$G^{\beta}_{\alpha,n}:=\frac{S^{\beta}_{\alpha,n}-nS^{\beta}_{\alpha,\infty}}{\sqrt{n}}$

converges to a mixed centered Gaussian random variable
$G^{\beta}_{\alpha,\infty}$ in distribution and with all moments. It is
possible to combine them to a mixture of centered Gaussian processes

(31) $\displaystyle
G^{\beta}_{\infty}=(G^{\beta}_{\alpha,\infty})_{\alpha\in[0,1]},$

defined by the conditional covariance functions given, with
$X^{\beta}_{\alpha,k}:=\mathbf{1}_{[L_{\alpha,k},R_{\alpha,k})}(V)\cdot\beta(U_{\tau_{\alpha,k,n}},V)$,
by

(32)
${\mathrm{Cov}}\big{(}G^{\beta}_{\alpha,\infty},G^{\beta}_{\gamma,\infty}\mid\mathcal{F}_{\infty}\big{)}={\mathrm{Cov}}\left(\sum_{k=0}^{\infty}X^{\beta}_{\alpha,k},\sum_{k=0}^{\infty}X^{\beta}_{\gamma,k}\,\Big{|}\,\mathcal{F}_{\infty}\right),\quad\alpha,\gamma\in[0,1].$

It can be shown that the latter expression is a.s. well-defined. We have the
following result corresponding to Theorem 1.

######  Theorem 17.

Let $\beta$ be an $\varepsilon$-tame cost function with
$\varepsilon<\frac{1}{4}$. Then we have

$\displaystyle\left(\frac{S^{\beta}_{\alpha,n}-nS^{\beta}_{\alpha,\infty}}{\sqrt{n}}\right)_{\alpha\in[0,1]}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}G^{\beta}_{\infty}\quad\mbox{ in
}(D[0,1],d_{\mathrm{SK}}),$

where $G^{\beta}_{\infty}$ is the mixture of centered Gaussian processes
defined in (31).

## References

  * [1] Jon Bentley, _Programming pearls_ , Addison-Wesley, Reading, Mass., 2000.
  * [2] Patrick Billingsley, _Convergence of probability measures_ , Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons Inc., New York, 1999, A Wiley-Interscience Publication. MR MR1700749 (2000e:60008)
  * [3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, _Introduction to algorithms_ , third ed., MIT Press, Cambridge, MA, 2009. MR 2572804
  * [4] Luc Devroye, _A note on the height of binary search trees_ , J. ACM 33 (1986), no. 3, 489–498.
  * [5] James Allen Fill, _Distributional convergence for the number of symbol comparisons used by QuickSort_ , Ann. Appl. Probab. 23 (2013), no. 3, 1129–1147. MR 3076680
  * [6] James Allen Fill and Svante Janson, _The number of bit comparisons used by Quicksort: an average-case analysis_ , Electron. J. Probab. 17 (2012), no. 43, 22. MR 2928726
  * [7] James Allen Fill and Jason Matterer, _QuickSelect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find_ , Combin. Probab. Comput. 23 (2014), no. 5, 805–828. MR 3249225
  * [8] James Allen Fill and Takehiko Nakama, _Distributional convergence for the number of symbol comparisons used by quickselect_ , Advances in Applied Probability 45 (2013), no. 2, 425–450.
  * [9] Rudolf Grübel and Uwe Rösler, _Asymptotic distribution theory for Hoare’s selection algorithm_ , Adv. in Appl. Probab. 28 (1996), no. 1, 252–269. MR 1372338
  * [10] C. A. R. Hoare, _Algorithm 63: Partition_ , Commun. ACM 4 (1961), no. 7, 321.
  * [11] by same author, _Algorithm 65: Find_ , Commun. ACM 4 (1961), no. 7, 321–322.
  * [12] Kevin Leckey, Ralph Neininger, and Henning Sulzbach, _Process convergence for the complexity of radix selection on markov sources_ , Stochastic Processes and their Applications 129 (2019), no. 2, 507–538.
  * [13] Hosam M. Mahmoud, _Distributional analysis of swaps in quick select_ , Theoretical Computer Science 411 (2010), no. 16, 1763–1769.
  * [14] Jason Matterer, _Quickselect process and quickval residual convergence_ , Ph.D. thesis, The Johns Hopkins University, Baltimore, Maryland, 2015.
  * [15] Colin McDiarmid, _Concentration_ , Probabilistic Methods for Algorithmic Discrete Mathematics (Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed, eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, 1998, pp. 195–248.
  * [16] Bruce Reed, _The height of a random binary search tree_ , J. ACM 50 (2003), no. 3, 306–332.
  * [17] Henning Sulzbach, Ralph Neininger, and Michael Drmota, _A Gaussian limit process for optimal FIND algorithms_ , Electronic Journal of Probability 19 (2014), no. none, 1 – 28.
  * [18] Brigitte Vallée, Julien Clément, James Allen Fill, and Philippe Flajolet, _The number of symbol comparisons in QuickSort and QuickSelect_ , Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 5555, Springer, Berlin, 2009, pp. 750–763. MR 2544890


# Mind-to-Image: Projecting Visual Mental Imagination of the Brain from fMRI

Hugo Caselles-Dupré  Charles Mellerio  Paul Hérent  Alizée Lopez-Persem
Benoit Béranger  Mathieu Soularue  Pierre Fautrel  Gauthier Vernier  Matthieu
Cord

###### Abstract

The reconstruction of images observed by subjects from fMRI data collected
during visual stimuli has made significant strides in the past decade, thanks
to the availability of extensive fMRI datasets and advancements in generative
models for image generation. However, the application of visual reconstruction
has remained limited. Reconstructing visual imagination presents a greater
challenge, with potentially revolutionary applications ranging from aiding
individuals with disabilities to verifying witness accounts in court. The
primary hurdles in this field are the absence of data collection protocols for
visual imagery and the lack of datasets on the subject. Traditionally, fMRI-
to-image relies on data collected from subjects exposed to visual stimuli,
which poses issues for generating visual imagery based on the difference of
brain activity between visual stimulation and visual imagery. For the first
time, we have compiled a substantial dataset (around 6h of scans) on visual
imagery along with a proposed data collection protocol. We then train a
modified version of an fMRI-to-image model and demonstrate the feasibility of
reconstructing images from two modes of imagination: from memory and from pure
imagination. This marks an important step towards creating a technology that
allow direct reconstruction of visual imagery.

Machine Learning, ICML

##  1 Introduction

Figure 1: Overview of our method. Left: classic fMRI-to-Image approach where a
subject sees images in an MRI scanner, bold data are recorded then used to
train a model that convert brain data to match the seen images. Right: in our
approach we let the subject imagine previously seen images from a dataset of
surrealist images (face portraits and nature landscapes) which we create. The
brain data associated to the recollection of such images is gathered. It is
then used to train a model to reconstruct previously seen images from visual
imagination brain data. At inference time we collect brain data where the
subject completely imagines new images based on instructions and use the
trained model of the first step to generate the imagined images.

In the rapidly evolving field of neuroscience and artificial intelligence, the
quest to decode the complex mechanisms of the human brain has led to
groundbreaking developments, particularly in the area of functional magnetic
resonance imaging (fMRI). Among the myriad applications of fMRI, one of the
most intriguing has been the reconstruction of visual experiences. Traditional
methods have successfully reconstructed images based on fMRI BOLD (blood-
oxygen-level-dependent) data captured while subjects view specific images
(Chen et al., 2022, 2023; Scotti et al., 2023). This process involves
preprocessing the BOLD data to isolate voxels associated with the brain’s
visual areas, generating clip embeddings from these voxels, and then employing
image generation algorithms that utilize these embeddings to recreate the
observed images. Such methodologies have shown promising results, especially
when employing datasets like the NSD (Natural Scenes Dataset) (Allen et al.,
2022), a substantial 7T fMRI dataset designed to bridge cognitive neuroscience
and artificial intelligence. This dataset, featuring extensive scans from
eight subjects, has become a cornerstone for research in this domain.

The intersection of cognitive neuroscience and artificial intelligence holds
the potential not only to advance our understanding of brain mechanisms but
also to develop practical applications, such as real-time clinical tools and
brain-computer interfaces. These applications are predicated on the ability to
accurately interpret and reconstruct cognitive states and environmental inputs
from brain activity. However, despite the progress in visual reconstruction
from observed images, a significant challenge remains in the domain of visual
imagination. Visual imagination encompasses both the recall of previously seen
images (which we refer to as weak imagination in the paper) and the generation
of entirely new images within the mind’s eye (which we refer to as strong
imagination). The ability to decode and reconstruct these imagined visuals
offers promising possibilities for aiding individuals with disabilities,
enhancing creative processes, and even providing novel forms of evidence in
legal contexts.

While using models based on reconstruction of images based on visual stimuli
to generate images from imagination is theoretically possible, we believe that
we need novel approaches to tackle the issue of visualizing imagination in the
brain, particularly in data collection and model development. To this end, we
introduce a protocol inspired by the NSD dataset but tailored to capture the
nuances of visual imagination. Our approach distinguishes between weak and
strong imagination, developing specific protocols for each type of visual
imagery. We restrict our analysis on one theme of images: surrealism, and two
distinct modalities of images: portraits and landscapes. This is done by
collecting a dataset of surrealist face portraits and nature landscapes, using
real and generated images. This choice is not only methodological but also
thematic, aligning with the project’s broader artistic aspirations. The
intersection of art and science, particularly through the lens of surrealism
and its exploration of automatic processes, provides a rich context for our
research.

Leveraging the MindEye model (Scotti et al., 2023), a state-of-the-art fMRI-
to-image framework, we adapt its architecture to accommodate the broader
dimensional complexity inherent in visual imagination data. Our approach is
summarised in Fig.1. Our results, while preliminary, indicate the model’s
capability to distinguish between and accurately generate portraits and
landscapes based on the nature of the imagination. Although the fidelity of
the reconstructions to the imagined content varies, our findings underscore
the potential of this approach. With further refinement and expansion of the
dataset, this research could pave the way for more precise reconstructions of
visual imagination, opening new avenues for understanding and exploiting the
brain’s creative and cognitive processes.

##  2 Related work

In the domain of mental imagery, several studies have sought to decode and
reconstruct images from the brain’s visual cortex when subjects engage in
imagining specific scenes or objects. (Stokes et al., 2009) provided early
evidence of the brain’s capacity to activate shape-specific population codes
during mental imagery, highlighting the top-down influence of visual
imagination on neural activity in the visual cortex. (Reddy et al., 2010)
explored the decoding of category information during mental imagery, providing
an understanding on how different types of visual information are processed
and represented in the brain.

More recently, (Naselaris et al., 2015) developed a voxel-wise encoding model
capable of decoding mental images of remembered scenes, demonstrating the
relationship between memory, imagination, and visual perception. (VanRullen &
Reddy, 2019) employs a combination of variational auto-encoders (VAE) and
Generative Adversarial Networks (GAN) to perform robust pairwise decoding of
faces with a high degree of accuracy but also to classify gender and decode
which face was imagined by subjects. (Goebel et al., 2022) showed the
feasibility of reading imagined letter shapes from the mind’s eye using real-
time 7 Tesla fMRI, presenting a novel approach to understanding how specific
visual information can be decoded from brain activity.

These studies collectively underscore the potential of fMRI data in decoding
not just seen images but also those that are imagined or remembered.

##  3 fMRI data collection protocol for visual imagery

The development of a comprehensive data collection protocol is one the main
contributions of our study, aimed at capturing the complex neural correlates
of visual imagination. Drawing inspiration from the NSD paper (Allen et al.,
2022), our protocol is designed to explore two distinct facets of visual
imagination: weak imagination (imagination from memory) and strong imagination
(pure imagination). This dual approach enables us to study how the brain
navigates between recalling visual information and generating novel visual
constructs.

###  3.1 Image dataset used: Surrealism

We do not use the images from the COCO dataset (Lin et al., 2014) as it is
done in the NSD dataset. Because our research is also associated to an
artistic research, we decided to narrow the dataset to one theme (surrealism)
and two modes (face portraits and nature landscapes). This choice narrows the
visual space of the fMRI-to-Image model, which simplify the task and allows us
to have results without having to do 40 hours of scans as in the NSD dataset.

Thus, we created our own dataset of images for our experiments. The images
come from three sources: real images and generated images using Versatile
Diffusion (Xu et al., 2023) and Midjourney. The dataset comprises 1200 images.

This dataset is used in the weak imagination protocol, where the images are
recollected from memory and imagined. Then, the images are used to train the
fMRI-to-Image model. Finally, only brain data is given to the fMRI-to-Image
model to produce the reconstructions, both in the weak and strong imagination
cases.

###  3.2 Weak imagination: data collection protocol

The protocol for weak imagination aims at recording brain activity
corresponding to the recall of previously seen images. In this phase, subjects
are first shown an image for 3 seconds, followed by a 1-second rest period.
This sequence is repeated with three different images, each selected from our
curated set of 600 surrealist portraits and 600 surrealist landscapes. To
engage the brain’s imaginative capacities, the same images are then flashed
for 0.1 seconds, prompting the subject to imagine the image for 5 seconds
before resting for another second. This process is repeated over a span of 6
hours, encompassing a total of 1200 images. Out of the data collected, 100
data points (comprising brain activity and the corresponding image) are
earmarked for validation and evaluation, with the remainder serving as the
training set for our fMRI-to-image model. The evaluation focuses on the
model’s ability to generate images that not only match the correct modality
(face portrait or nature landscape) but also reflect the contents of the
original image.

###  3.3 Strong imagination: data collection protocol

For strong imagination, the process pivots towards the generation of entirely
new visual content based on verbal prompts. Subjects are instructed to imagine
a portrait or landscape evoking one of ten primal emotions (such as fear,
happiness, love, etc.). This task is designed to stimulate the pure
imagination process, encouraging the brain to construct novel visual imagery
without the reference of previously seen images. Each imagination session
lasts for 6 seconds, followed by a 1-second rest, cycling through combinations
of landscape/portrait and emotional prompts. This cycle is repeated 10 times.
Unlike the data collected for weak imagination, this dataset is solely used
during the model’s inference stage. The evaluation here is similar to the weak
imagination evaluation: quantitively assess if the model matches the correct
modality (face portrait or nature landscape) and qualitatively assess if the
contents of the generated image matches the visual imagery of the subject. To
ensure that we recall what the subject has imagined, the subject provides an
oral description of the visual contents of the imagined image.

###  3.4 Pre-processing of raw BOLD data and masking of the regions of
interest

After the raw BOLD (blood-oxygen-level-dependent) data is collected, we apply
a preprocessing routine to provide the model with data that decorrelates all
the noise that impair the following steps. We first co-register all BOLD data
with a T1 anatomical scan. Then, using a General Linear Model (GLM) with the
Glover hemodynamic response function (HRF) (implemented via the Nilearn
library (Abraham et al., 2014)), we extracted beta values associated with each
voxel for every distinct event, including both the displayed images and the
periods of imagination. This allwos us to isolate the specific brain activity
corresponding to each event, which is common practice for such tasks.

In the subsequent data pre-processing phase, we identify the brain regions
most instrumental to visual imagination and encoding, using a GLM model to
manually discern these areas of interest. Unlike the NSD dataset, which
predominantly focuses on visual areas, our study necessitated the creation of
a custom mask to encapsulate the regions identified as crucial in our specific
context of weak and strong imagination. This aforementioned mask was manually
curated based on the GLM analysis results, ensuring that only voxels
corresponding to our defined regions of interest were included in further
analyses. The delineation and analysis of these regions, and how they diverge
from the predominantly visual areas highlighted in the NSD study, is studied
in the results section.

Finally, we create our training, validation (weak imagination) and test
(strong imagination) datasets by flattening the pre-processed betas
corresponding the selected voxels and pair them with the images or prompts
related to their events.

##  4 Training the fMRI-to-Image model

We start from the state-of-the-art MindEye model which reconstructs images
viewed by subjects from fMRI data by combining two pipelines: a high-level
(semantic) pipeline and a low-level (perceptual) pipeline, both grounded in a
residual MLP backbone structure. The high-level pipeline maps fMRI voxels to
the CLIP Vision Transformer L/14 image space, capturing the semantics of the
image. In contrast, the low-level pipeline targets the perceptual fidelity of
reconstructed images by mapping voxels to a Variational Autoencoder’s (VAE)
image embedding space. They leverage contrastive and mean squared error (MSE)
losses for training of its projection and reconstruction capabilities.
Techniques such as MixCo are employed to improve classification and retrieval
performance by generating synthetic training data.

###  4.1 Adapting MindEye to larger masks for visual imagery

To accommodate the increased dimensionality inherent in our fMRI BOLD voxel
data, which covers extensive brain areas notably larger than only the visual
areas of the brain, we adapted MindEye’s architecture. This adjustment aimed
to manage the significant growth in input dimensions without exponentially
increasing the model’s parameter count. We thus simply refine the architecture
of the MLP so that the model efficiently processes the data while maintaining
high performance without overburdening computational resources.

###  4.2 Experiments

Our experimental procedures are as outlined below:

  * •

We first collect a dataset of weak and strong imagination using the protocol
defined in Sec.3, with a total of 6 hours of scans.

  * •

Then, we train our adapted fMRI-to-Image model using the dataset obtained from
the weak imagination data collection protocol. Then, this model is evaluated
using the validation set to assess its performance.

  * •

We finally freeze the parameters of the fMRI-to-Image model. This frozen model
is then employed to perform inference on the dataset derived from the strong
imagination data collection protocol, with the goal of visualising the purely
imagined images.

##  5 Results

We first analyze the most activate regions of the brain during visual
perception, weak imagination and strong imagination.

We then go over the results obtained for training reconstruction fMRI-to-Image
models for weak imagination before looking at strong imagination.

###  5.1 What happens in the brain during visualisation, weak and strong
imagination?

In this section we describe the brain regions involved during visual
perception, weak imagination, and strong imagination. This is done though the
visualisations presented in Fig.2.

Figure 2: Functional MRI results of the three conditions, respectively: simple
visual perception (A- in red), weak imagination (B- in pink) and strong
imagination (C- in blue) presented through a lower (top row) and right lateral
(bottom row) view. Activation maps were generated by comparing the “test” and
“rest” conditions, using the same statistical threshold for each test (T-score
=5).

The results of the first test (A) show that the brain regions mainly involved
in normal visual perception are, as expected, the primary and secondary visual
areas in the occipital lobe, the superior parietal lobule and the bottom of
the temporal lobe.

Weak imagination (B) involves occipital primary visual areas in a much weaker
way. Instead, there is an activation of the basal temporal associative visual
areas (fusiform gyrus) involved in mental imagery. The latter are partially
overlapped with brain areas involved in visual perception.

Strong imagination (C) involves even more brain areas distinct from visual
cortex, with a strong activation in prefrontal regions, involved in the
strategy of generating and controlling mental imagery. There is also an
incomplete overlap of activations between visual perception and imagination in
the temporal lobe, mainly limited to the fusiform gyrus, especially in the
right hemisphere, more specialized in the face processing (as this result was
obtained during the portrait imagination test).

These results justify the need for a specialised dataset for imagination
relative to visual perception, given that the regions most active during the
different tests are not quite the same.

###  5.2 Can we reconstruct images from weak imagination / memory?

We present curated results of the images generated by our model from weak
imagination in Fig.3.

Figure 3: Results for weak imagination on the validation dataset. Top row:
images from the validation set of our surrealism image dataset, which were
recollected from memory by the subject in the fMRI scanner. Bottom row:
reconstructed images from the fMRI-to-Image model based on the brain data
associated to the recollection of the images in the top row.

In the exploration of weak imagination, where subjects were prompted to recall
previously seen images, our results highlight the capacity of the model to
identify to the original class of the images. Specifically, if a subject
recalled a face portrait, the reconstructed image is almost always a face
portrait, and similarly for nature landscapes. This observation suggests a the
ability of the model to grasp the category of the imagined content accurately
within the BOLD data. To quantitatively assess this capability, we fine-tune a
pretrained ResNet50 model (He et al., 2016) to classify images as either face
portraits or nature landscapes using the images in our dataset. We apply this
classifier to the reconstructed images from the weak imagination tasks of the
validation set. We obtain a classification accuracy of 91% in correctly
identifying the reconstructed images as belonging to their original categories
of either portraits or landscapes. This level of accuracy demonstrates the
model’s ability in capturing the category information within the neural
activity during weak imagination.

While the model demonstrated a robust ability to regenerate the broad category
of the original images, the fidelity of content reconstruction within these
images presented a more varied outcome. Some reconstructions were close to the
remembered images. However, others diverged more significantly, indicating a
variability in the model’s ability to precisely capture and reconstruct the
nuanced details of each imagined scene. This variance in reconstruction
fidelity can be attributed, in part, to the limitations imposed by the
dataset’s size and the duration of the fMRI scanning sessions. With only 6
hours of scans and 1200 images constituting the dataset, the goal for training
a model from scratch to achieve perfect reconstruction is out of reach.
Nevertheless, these initial results are promising, suggesting a capacity for
accurate content reproduction. It is reasonable to anticipate that with an
expanded dataset, the fidelity of the reconstructed images to their original
counterparts would see significant improvement, enhancing both the precision
and consistency of the content reproduction in future iterations.

###  5.3 Can we reconstruct images from strong imagination / pure imagination?

We present curated results of the images generated by our model from strong
imagination in Fig.4.

Figure 4: Results from strong imagination. The subject is given an instruction
on the fMRI screen, such as ”Imagine a portrait representing optimism”. Then,
the subject purely imagines such image, giving an oral description. Then, the
associated brain data is fed to the fMRI-to-Image model to produce a
reconstruction, which is then evaluated compared to the oral description.

In the phase dedicated to strong imagination, we employed the previously
trained and then frozen fMRI-to-Image model to process BOLD data obtained
while subjects engaged in pure imagination tasks, such as imagining a portrait
or landscape embodying a concept like optimism. This procedure is effectively
transfer learning, leveraging a model trained exclusively on weak imagination
data to interpret and generate visual outputs from the distinct context of
strong imagination, without fine-tuning. In any case, we do not have tangible
images to serve as direct training data for strong imagination, since these
images exist solely within the mind of the subject. Hence we employ transfer
learning from the weak imagination process to generate from strong
imagination. Remarkably, the application of the fine-tuned ResNet50 classifier
to the generated images resulted in an 88% accuracy rate in categorizing the
images according to the instructions provided to the subjects. This accuracy
in category generation demonstrates the effectiveness of transfer learning
from weak to strong imagination, which represent our main contribution.

Determining the content accuracy of images generated from strong imagination
poses a unique challenge, as the ’ground truth’ images solely exist in the
subject’s mental imagery, inaccessible for direct comparison. To navigate
this, we based our evaluation on subjects’ descriptions of their imagined
scenes, collected during or following the scanning sessions. The variability
in the reconstructed content ranges from highly accurate renditions of
specific imagined elements, like a tree, dark-haired woman, or flowers, to
more abstract interpretations or plain errors. This also reflects the
subjective nature of this task. Given the reliance on subjective descriptions
and the inherent open-endedness of strong imagination, the results should be
interpreted with caution. While it’s challenging to draw definitive
conclusions about the model’s capacity for precise content reconstruction in
this context, the instances of recognisable elements emerging in the
reconstructions hint at the potential depths of accuracy achievable with
increased data volume and further model refinement.

##  6 Discussion

###  6.1 Ethical considerations

As we explore further into the capabilities of decoding and reconstructing
visual content from brain activity, we get closer to the boundaries of
personal thought and imagination, a concept known as ”mind privacy”. The
ability to visualise an individual’s mental imagery raises significant
questions about consent, mental autonomy, and the potential for misuse of such
technologies. On the one hand, such technology provides potential for good,
opening avenues for novel communication methods for those unable to speak or
write, enhancing creative expression, and deepening our understanding of the
human brain and its processes. On the other hand, it introduces the
possibility of invasive breaches of personal thought, where the most private
mental images and ideas could be exposed without consent. Navigating these
waters requires a careful, deliberate approach to ensure that the development
and application of these technologies are governed by ethical principles that
prioritise individual privacy and autonomy. Currently, the barriers to entry,
including the need for explicit consent and the use of expensive and
sophisticated MRI machinery, provide a layer of protection.

###  6.2 Future work

Future directions for this line of research include the acquisition of more
extensive data to improve the accuracy and specificity of content match in the
reconstructed images. A refined experimental protocol for both weak and strong
imagination tasks could lead to more nuanced insights into the brain’s imaging
processes, while improved evaluation methods for strong imagination would
enhance our understanding of the model’s effectiveness in capturing the depth
and detail of imagined content. Additionally, the question of whether MRI
technology can be replaced or complemented by EEG is promising. Recent studies
suggest the feasibility of reconstructing visual stimuli from brain activity
using EEG (Benchetrit et al., 2023), which offers a more accessible, and cost-
effective alternative to MRI.

##  7 Conclusion

In our work, we introduced and applied two novel data collection protocols:
weak and strong imagination. These protocols were designed to study visual
imagery and create training datasets for fMRI-to-Images models. We implemented
them during a 6-hour scanning session to create a comprehensive dataset. This
dataset then served as the basis for training our fMRI-to-image model.
Initially, the model was trained using data from the weak imagination
protocol, which involved reconstructing images that the subject had previously
seen. Subsequently, the same model, now frozen, was applied to data from the
strong imagination protocol, where the subject was asked to imagine new images
based on a written instruction. Our study demonstrates that the model
successfully distinguishes between broad categories such as portraits and
landscapes, effectively grasping the category of the content imagined by the
subject. Accurately capturing the detailed contents of these imagined images
was partly successful, but proved to be more challenging. This research
provides a promising path towards the generation of visual representations
directly from human thought.

## Acknowledgements

The author acknowledges the support of the French Agence Nationale de la
Recherche (ANR) under reference ANR-23-CE23-0023.

## References

  * Abraham et al. (2014) Abraham, A., Pedregosa, F., Eickenberg, M., Gervais, P., Mueller, A., Kossaifi, J., Gramfort, A., Thirion, B., and Varoquaux, G.  Machine learning for neuroimaging with scikit-learn.  _Frontiers in Neuroinformatics_ , 8:14, 2014.  doi: 10.3389/fninf.2014.00014.
  * Allen et al. (2022) Allen, E. J., St-Yves, G., Wu, Y., Breedlove, J. L., Prince, J. S., Dowdle, L. T., Nau, M., Caron, B., Pestilli, F., Charest, I., Hutchinson, J. B., Naselaris, T., and Kay, K.  A massive 7t fmri dataset to bridge cognitive neuroscience and artificial intelligence.  _Nature Neuroscience_ , 25:116–126, 2022.  doi: https://doi.org/10.1038/s41593-021-00997-w.
  * Benchetrit et al. (2023) Benchetrit, Y., Banville, H., and King, J.-R.  Brain decoding: toward real-time reconstruction of visual perception.  _arXiv preprint arXiv:2310.19812_ , 2023.
  * Chen et al. (2022) Chen, Z., Qing, J., Xiang, T., Yue, W. L., and Zhou, J. H.  Seeing beyond the brain: Conditional diffusion model with sparse masked modeling for vision decoding.  _arXiv preprint arXiv:2211.06956_ , 2022.  URL https://doi.org/10.48550/arXiv.2211.06956.
  * Chen et al. (2023) Chen, Z., Qing, J., and Zhou, J. H.  Cinematic mindscapes: High-quality video reconstruction from brain activity.  _arXiv preprint arXiv:2305.11675_ , 2023.  URL https://doi.org/10.48550/arXiv.2305.11675.
  * Goebel et al. (2022) Goebel, R., van Hoof, R., Bhat, S., Lührs, M., and Senden, M.  Reading imagined letter shapes from the mind’s eye using real-time 7 tesla fmri.  In _2022 10th International Winter Conference on Brain-Computer Interface (BCI)_ , pp. 1–3, 2022.  doi: 10.1109/BCI53720.2022.9735031.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Lin et al. (2014) Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., and Zitnick, C. L.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , pp. 740–755. Springer, 2014.
  * Naselaris et al. (2015) Naselaris, T., Olman, C. A., Stansbury, D. E., Ugurbil, K., and Gallant, J. L.  A voxel-wise encoding model for early visual areas decodes mental images of remembered scenes.  _NeuroImage_ , 105:215–228, 2015.  doi: 10.1016/j.neuroimage.2014.10.018.  URL https://www.sciencedirect.com/science/article/pii/S1053811914008428.
  * Reddy et al. (2010) Reddy, L., Tsuchiya, N., and Serre, T.  Reading the mind’s eye: Decoding category information during mental imagery.  _NeuroImage_ , 50(2):818–825, 2010.  doi: 10.1016/j.neuroimage.2009.11.084.  URL https://www.sciencedirect.com/science/article/pii/S1053811909012701.
  * Scotti et al. (2023) Scotti, P. S., Banerjee, A., Goode, J., Shabalin, S., Nguyen, A., Cohen, E., Dempster, A. J., Verlinde, N., Yundler, E., Weisberg, D., Norman, K. A., and Abraham, T. M.  Reconstructing the mind’s eye: fmri-to-image with contrastive learning and diffusion priors.  _arXiv preprint arXiv:2305.18274_ , 2023.  URL https://doi.org/10.48550/arXiv.2305.18274.
  * Stokes et al. (2009) Stokes, M., Thompson, R., Cusack, R., and Duncan, J.  Top-down activation of shape-specific population codes in visual cortex during mental imagery.  _Journal of Neuroscience_ , 29(5):1565–1572, 2009.  doi: 10.1523/JNEUROSCI.4657-08.2009.  URL https://www.jneurosci.org/content/29/5/1565.
  * VanRullen & Reddy (2019) VanRullen, R. and Reddy, L.  Reconstructing faces from fmri patterns using deep generative neural networks.  _Communications Biology_ , 2, 2019.  doi: https://doi.org/10.1038/s42003-019-0438-y.  URL https://www.nature.com/articles/s42003-019-0438-y.
  * Xu et al. (2023) Xu, X., Wang, Z., Zhang, E., Wang, K., and Shi, H.  Versatile diffusion: Text, images and variations all in one diffusion model.  _arXiv preprint arXiv:2211.08332_ , 2023.