# Duration problem: basic concept and some extensions

Zdzisław Porosiński  Wrocław University of Technology
Wybrzeże Wyspiańskiego 27
50-370 Wrocław, Poland<EMAIL_ADDRESS>,  Marek Skarupski
Wrocław University of Technology
Wybrzeże Wyspiańskiego 27,
50-370 Wrocław, Poland<EMAIL_ADDRESS>and  Krzysztof Szajowski
Wrocław University of Technology
Wybrzeże Wyspiańskiego 27
50-370 Wrocław, Poland<EMAIL_ADDRESS>
###### Abstract.

We consider a sequence of independent random variables with the known
distribution observed sequentially. The observation $n$ is assumed to be a
value of one order statistics such as $s:n$-th, where $1\leq s\leq n$. It the
instances following the $n$th observation it may remain of the $s:m$ or it
will be the value of the order statistics $r:m$ (of $m>n$ observations).
Changing the rank of the observation, along with expanding a set of
observations there is a random phenomenon that is difficult to predict. From
practical reasons it is of great interest. Among others, we pose the question
of the moment in which the observation appears and whose rank will not change
significantly until the end of sampling of a certain size. We also attempt to
answer which observation should be kept to have the “good quality observation”
as long as possible. This last question was analysed by Ferguson, Hardwick and
Tamaki (1991) in the abstract form which they called the _problem of
duration_.

This article gives a systematical presentation of the known duration models
and a new modifications. We collect results from different papers on the
duration of the extremal observation in the no-information (denoted as rank
based) case and the full-information case. In the case of non-extremal
observation duration models the most appealing are various settings related to
the two extremal order statistics. In the no-information case it will be the
maximizing duration of owning the relatively best or the second best object.
The idea was formulated and the problem was solved by Szajowski and Tamaki
(2006). The full-information duration problem with special requirement was
presented by Kurushima and Ano (2010).

###### Key words and phrases:

optimal stopping, duration problem, secretary problem

###### 2010 Mathematics Subject Classification:

60G40, 62L15

##  1\. Introduction

It was Ferguson, Hardwick and Tamaki [6] who formulated the duration problem
as the optimal prediction the relative extremal observation keeping the
leading position for the highest period. The basic formulation was for the
classical no-information secretary problem. It is a sequential selection
problem which is a variation of the classical secretary problem (CSP) treated,
for example, by Gilbert and Mosteller [9]. The aim of the CSP is to examine
items ranked from $1$ to $N$ by the random selection without replacement, one
at a time, and to win wchich means to stop at any item whose overall
(absolute) rank belongs to the given set of ranks (in the basic version this
set contains the rank $1$ only), given only the relative ranks of the items
drawn so far. Since the articles by Gardner [8] the secretary problem has been
extended and generalized in many different directions. Excellent reviews of
the development of this colourful problem and its extensions have been given
by Rose [19], Freeman [7] and Samuels [20]. The deepest analysis of the
assumptions and their consequences was made by Ferguson [6].

###  1.1. Duration problems for the no-information case.

The basic form of the duration problem can be described as follows. A set of
$N$ rankable objects appears as in CSP. As each object appears, we must decide
whether to select or reject it on the basis of the relative ranks of the
objects. The payoff is the length of time we are in possession regarding a
relatively best object. Thus we will only select the relatively best object,
receiving a payoff of one as we do so and an additional one for each new
observation as long as the selected object remains relatively best.

Ferguson, Hardwick and Tamaki [6] considered various duration models in quite
some detail. Moreover, they mention that they had discussed the duration
problem also for a random number of arrivals in continuous time. The solution
is indeed easy if the arrival process is the Pascal process, since then (see
Bruss and Rogers [4, Theorem 2]), the corresponding record arrival process is
Poisson. The latter gives then also access to Poisson embedding (Bruss and
Rogers [3]) displaying an interesting duality. However, Ferguson et al. [6]
confined themselves throughout their study to the duration problem for the
relatively best items. In this paper, we attempt to extend the problems to
choose and keep the items having the relatively high leading position for the
long period. As a simple example we refer to a relatively best or the second
best object as a candidate. The focus is the case where each time we receive a
unit payoff as long as either of the chosen objects remains a candidate.
Obviously only candidates can be chosen, the objective being to maximize the
expected payoff. This problem can be viewed from another perspective as
follows. Let us observe at moment $i$ the relatively second candidate and let
us denote $T(i)$ the time of the first candidate after time $i$ (_i.e._ the
relatively best or the second best item) if there is one, and $N+1$ if there
is none. If we observe at $i$ the relatively best item then $T(i)$ is the
moment when new item appears, which changes the relative rank of $i$th item to
the non-candidate rank. The time $T(i)-i$ is called duration of the candidate
selected at time $i$. The objective is to find a stopping time $\tau^{*}$ such
that

(1)
$v_{N}=E\left[\frac{T(\tau^{*})-\tau^{*}}{N}\right]=\sup\limits_{\tau\in{\mathfrak{M}}^{N}}E\left[\frac{T(\tau)-\tau}{N}\right],$

where ${\mathfrak{M}}^{N}$ denotes the set of all stopping times.

###  1.2. Duration problems for the full-information case.

The second group of models in [6] are those related to the full-information
best choice problem. We observe sequentially i.i.d. random variables from the
known distribution. Without the loss of generality we can assume that they
come from the uniform distribution on the interval $[0,1]$. Suppose that we
want to maximize the time in which the selected object maintains its quality
(e.g. being the relatively best one). In many cases we see that the reward is
related with the win probability. A typical optimal stopping problem in full
information case was first studied by Gilbert and Mosteller [9]. The
comparison of results was derived by Gnedin [10].

The paper is organized as follows. In Section 2 the solution of the problems
formulated in the section 1.1 is presented. A Markov chain optimal stopping
problem equivalent to the duration problem and the optimal strategy will be
formulated in Section 2.1 and derived in Section 2.2. This section is based
mainly on the suggestion from [5] and the results by [22] and [21]. In Section
2.3 the problem of stopping on the relatively best or second best is shown.
The discounted no-information duration problem is described in in Section 2.4.
In the Section 3 we consider full information duration problem (FIDP) in
finite horizon with and without recall possibility. The duration problem is
transformed to the optimal stopping problem for the Markov process similar to
this applied by Bojdecki [2] and Prosiński and Szajowski [16] (see Section
3.1). In Section 3.2 we present results related to the best-choice duration
problem (BCDP) with and without recall possibility. In section 3.3 we switch
into random horizon full information duration problem (RHFIDP). In Section 3.4
there is a description of the full information duration problem with the
unbounded horizon. We extend FIDP into duration of owning the relatively best
or second best object in Section 3.6. We show some results for the unbounded
horizon. Various directions of the extensions based on the main idea of the
duration problem are the subject of the conclusion section.

##  2\. Markov model for no-information duration problems

The models which are considered in this study are the so called no information
models where the decision to select an object is based only on the relative
ranks of the objects observed so far. Let ${\mathbb{S}}=\\{1,2,\ldots,N\\}$ be
the set of ranks of items $\\{x_{1},x_{2},\ldots,x_{N}\\}$ and
$\\{X_{1},X_{2},\ldots,X_{N}\\}$ their permutation. We observe sequentially
the permutation of items from the set ${\mathbb{S}}$. The mathematical model
of such an experiment is the probability space $(\Omega,{\mathcal{F}},{\bf
P})$. The elementary events are permutations of the elements from
${\mathbb{S}}$ and the probability measure ${\bf P}$ is the uniform
distribution on $\Omega$. The observation of random variables $Y_{k}$,
$k=1,2,\ldots,N$, generate the sequence of $\sigma$-fields
${\mathcal{F}}_{k}=\sigma\\{Y_{1},Y_{2},\ldots,Y_{k}\\}$, $k=1,2,\ldots,N$.
The random variables $Y_{k}$ are independent and ${\bf
P}\\{Y_{k}=i\\}=\frac{1}{k}$.

We assume that all permutations are equally likely. If $X_{k}$ is the rank of
$k$-th candidate we define

(2) $Y_{kj}=\\#\\{1\leq i\leq j:X_{i}\leq X_{k}\\}$

the running rank of $k$-th object at the moment $j\geq k$. The random variable
$Y_{k}=Y_{kk}$ is called relative rank of $k$-th candidate with respect of the
items investigated to the moment $k$. Let $A\subset{\mathbb{S}}$.
Subsequently, the appearance of the next candidate after $i$ is the moment
$S_{A}(i)=\inf\\{k>i:Y_{k}\in A\\}$ and the maturity $T_{r}(i)=\inf\\{k\geq
i:{\bf P}\\{X_{k}\in A|Y_{ik}=r\\}=0\\}$ of the candidate with the relative
rank $r$ at moment $i$ is defined. The maturity can be represented in the
equivalent manner as $T_{r}(i)=\inf\\{k\geq i:Y_{i}=r,\ Y_{k}\in A,\
Y_{ik}\notin A\\}$.

######  Remark 1.

If $A=\\{1,2,\ldots,s\\}$ and

(3a) $\displaystyle S_{A}(i)$ $\displaystyle=\inf\\{k>i:Y_{k}\in A\\}$ then
$T_{s}(i)=S_{A}(i)$, and for any $r\in A$ (3b) $\displaystyle T_{r}(i)$
$\displaystyle=\inf\\{k\geq i:Y_{ik}\not\in A\\}.$

For $r<s$ the duration of the candidate with rank $r$ at the moment $i$ is
dependent on the items appearing between $i$ and $k$. Changing the rank of a
candidate when a new candidate approaches, does not always mean that one
ceased to be a candidate.

Denote by ${\mathfrak{M}}^{N}$ the set of all Markov moments $\tau$ with
respect to $\sigma$-fields $\\{{\mathcal{F}}_{k}\\}_{k=1}^{N}$. The decision
maker observes the stream of relative ranks. When $Y_{i}\in
A=\\{1,2,\ldots,s\\}$ it is the potential candidate for the absolutely $r$th
item, $r\in A$. Sometimes it is enough to keep such a candidate for a period
of time to get profit which is proportional to the shell file of a candidate
(the second kind of duration of the candidate). The random variable $T(i)$ is
defined as the moment when the keeping candidate stops to be the candidate
(the maturity of the candidate). Let us consider the possibility of recall
force to think about the rejected candidates. We define
$\delta_{r}(i)=\sup_{1\leq j\leq i}\\{Y_{j}=r\\}$ _the actual position of the
relative $r$ at the moment $i$_. $\delta_{r}(i)$ is the random variable
measurable with respect to ${\mathcal{F}}_{i}$. The recall option means the
possibility of returning to the last candidate who has the relative rank
$r^{\star}=\mbox{arg}\max_{\\{s\in A\\}}\delta_{s}(i)$ or to the candidate
with the given rank, e.g $r=1$. The present history at $i$ and $Y_{k,s}$ for
$k\in\\{i,\ldots,N\\}$, $s=i,i+1,\ldots,N$ allows to define the maturity
$T(i)$ for various models. In the next part examples of various definitions of
maturity will be shown, and therefore different definitions of duration will
be presented.

###  2.1. The optimal stopping problem for the embedded Markov chain

####  2.1.1. Embedded Markov chain.

Let $a=\max(A)$. The function $\varphi(k,r)$ defined in (15) is equal to $0$
for $r>a$ and non-negative for $r\leq a$. It means that it is rational to
choose an item for keeping at the moment $k$ when the state $(k,r)$ such that
$r\leq a$. Define $W_{0}=(1,Y_{1})=(1,1)$,
$\gamma_{t}=\inf\\{r>\gamma_{t-1}:Y_{r}\leq\min(a,r)\\}$
($\inf\emptyset=\infty$) and $W_{t}=(\gamma_{t},Y_{\gamma_{t}})$. If
$\gamma_{t}=\infty$ then define $W_{t}=(\infty,\infty)$. $W_{t}$ is the Markov
chain with the state space ${\mathbb{E}}=\\{(s,r):s\in\\{1,2,\ldots,N\\},r\in
A\\}\cup\\{(\infty,\infty)\\}$ and the following transition probabilities (see
[22])

(4) $\begin{split}p(r,s)&={\bf P}\\{W_{t+1}=(s,l_{s})|W_{t}=(r,l_{r})\\}\\\
&=\begin{cases}\frac{1}{s},&\text{ if $r<a$, $s=r+1$},\\\
\frac{(r)_{a}}{(s)_{a+1}},&\text{ if $a\leq r<s$},\\\ 0,&\text{ if $r\geq s$
or $r<a$, $s\neq r+1$,}\end{cases}\end{split}$

with $p(\infty,\infty)=1$, $p(r,\infty)=1-a\sum_{s=r+1}^{N}p(r,s)$, where
$(s)_{a}=s(s-1)(s-2)\ldots(s-a+1)$, $(s)_{0}=1$. We denote $T\varphi(k,r)={\bf
E}_{(k,r)}\varphi(W_{1})$ the mean operator for the function
$g:{\mathbb{E}}\rightarrow\Re$. Let
${\mathcal{G}}_{t}=\sigma\\{W_{1},W_{2},\ldots,W_{t}\\}$ and
$\tilde{{\mathfrak{M}}}^{N}$ be the set of stopping times with respect to
$\\{{\mathcal{G}}_{t}\\}_{t=1}^{N}$. Since $\gamma_{t}$ is increasing, then we
can define
$\tilde{{\mathfrak{M}}}^{N}_{r+1}=\\{\sigma\in\tilde{{\mathfrak{M}}}^{N}:\gamma_{\sigma}>r\\}$.

Let ${\bf P}_{(k,r)}(\cdot)$ be the probability measure related to the Markov
chain $W_{t}$, with the trajectory starting in the state $(k,r)$ and ${\bf
E}_{(k,r)}(\cdot)$ the expected value with respect to ${\bf
P}_{(k,r)}(\cdot)$. From (4) we can see that the transition probabilities do
not depend on relative ranks, but only on the moments $k$ where the items with
the relative rank $r\leq\min(a,k)$ appear. Based on the following lemma we can
solve the problem (1) with the gain function (14) using the embedded Markov
chain $(W_{t},{\mathcal{G}}_{t},{\bf P}_{(1,1)})_{t=0}^{N}$.

######  Lemma 2.

(see [22])

(5) ${\bf E}w_{N}(k+1,Y_{k+1})={\bf E}_{(k,r)}w_{N}(W_{1})\mbox{ for every
$r\leq\min(a,k)$.}$

####  2.1.2. The optimal stopping problem.

Let $T(i)=\zeta_{i}T_{1}(i)$ and $\xi_{i}$ is an additional restriction (the
requirement on the chosen item). The aim is to find
$\tau^{\star}\in{\mathfrak{M}}^{N}$ such that:

(6) ${\bf
E}\left[\frac{T(\tau^{\star})-\tau^{\star}}{N}\xi_{\tau^{\star}}\right]=\sup_{\tau{\mathfrak{M}}^{N}}{\bf
E}\left[\frac{T(\tau)-\tau}{N}\xi_{\tau}\right].$

Let us observe that for any $\tau\in{\mathfrak{M}}^{N}$

$\displaystyle{\bf E}\left[\frac{T(\tau)-\tau}{N}\xi_{\tau}\right]$
$\displaystyle=$ $\displaystyle\sum_{r=1}^{N}\int_{\\{\tau=r\\}}{\bf
E}\\{\frac{T_{r}-r}{N}\xi_{r}|Y_{r}\\}d{\bf P}={\bf E}\varphi(\tau,Y_{\tau}).$

####  2.1.3. Recursive algorithm

Let ${\mathfrak{M}}^{N}_{r}=\\{\tau\in{\mathfrak{M}}^{N}:r\leq\tau\leq N\\}$
and $\tilde{w}_{N}(r)=\sup_{\tau\in{\mathfrak{M}}^{N}_{r}}{\bf
E}\varphi(\tau,Y_{\tau})$. The following algorithm allows to construct the
value of the problem $v_{N}=w_{N}(1,1)$.

(7) $\tilde{w}_{N}(N)={\bf E}\varphi(N,Y_{N})$

Let

(8) $w_{N}(N,r)&=\left\\{\begin{array}[]{ll}1,&\mbox{ if $r\in A$},\\\
0,&\mbox{ otherwise,}\end{array}\right.\\\ w_{N}(k,r)=\max\\{\varphi(k,r),{\bf
E}w_{N}(r+1,Y_{r+1})\\},\\\ \tilde{w}_{N}(k)={\bf
E}w_{N}(k,Y_{k})=\frac{1}{k}\sum_{r=1}^{k}w_{N}(k,r).$

We have then $v_{N}=\tilde{w}_{N}(1)$. The optimal stopping time $\tau^{*}$ is
defined as follows: one has to stop at the first moment $k$ when $Y_{k}=r$,
unless $w_{N}(k,r)>\varphi(k,r)$. We can define the stopping set as
$\Gamma=\\{(k,r):\varphi(k,r)\geq\tilde{w}_{N}(k)\\}$.

###  2.2. Classical no-information BC duration problem

It is not difficult to formalize the duration problem for BC as with recall as
without recall and also when the additional requirement concerning the
absolute rank of the selected object is added. In order to present the problem
of the duration time for BCP considered in [6] we assume that $A=\\{1\\}$,
$\zeta_{n}(\omega)={\mathbb{I}}_{\\{Y_{n}\in A\\}}(\omega)$ and
$\zeta_{n}^{\star}(\omega)={\mathbb{I}}_{\\{X_{n}\in A\\}}(\omega)$.

####  2.2.1. Finite horizon duration problem of BCP without recall ([6, Sec.
2.2]).

Let $T(i)=\zeta_{i}T_{1}(i)$ and $\xi_{i}=1$. The aim is to find
$\tau^{\star}\in{\mathfrak{M}}^{N}$ such that:

(9) ${\bf
E}\left[\frac{T(\tau^{\star})-\tau^{\star})}{N}\xi_{\tau^{\star}}\right]=\sup_{\tau{\mathfrak{M}}^{N}}{\bf
E}\left[\frac{(T(\tau)-\tau)}{N}\xi_{\tau}\right].$

It is the first setting of the problem. In [6] the authors observed that the
pay-offs in the problem for the threshold rules are exactly there same as the
pay-offs for the threshold rule for the best choice secretary problem with an
unknown, random number of options that has the uniform distribution on
${\mathbb{S}}$ (see the results by Presman and Sonin [17], Rasmussen and
Robbins[18] and a general method of Samuels [20] showing the relation of the
random horizon problems to the problems with cost ). The single threshold
$r^{\star}_{N}$strategy is optimal having the asymptotic
$\lim_{N\rightarrow\infty}\frac{r^{\star}_{N}}{N}\cong\mbox{e}^{-2}$ and the
problem value $2\mbox{e}^{-2}$.

####  2.2.2. Finite horizon duration problem of BCP with recall ([6, Sec.
2.2]).

Let $T(i)=T_{1}(i)$ and $\xi_{i}=1$. The aim is to find
$\tau^{\star}\in{\mathfrak{M}}^{N}$ in the problem of (6) with this new
definition of the maturity moment. This second setting of the problem has the
solution which has a simple relation with the solution of BCP. Namely, if
$k_{N}^{\star}$ is the optimal threshold for BCP then the optimal threshold
for the duration problem of BCP with recall is $K_{N}=r_{N}^{\star}-1$ for
$N\geq 2$. It is also the optimal rule for the BCP with an unknown, random
number of options having the uniform distribution on ${\mathbb{S}}$ and
possible recall.

####  2.2.3. Duration problem without recall with choice of the best ([6, Sec.
2.3]).

Let us define the maturity moment as $T(i)=\zeta_{i}T_{1}(i)$ and
$\xi_{i}=\zeta_{i}^{\star}$. The positive pay-off is when $T(i)=N+1$ only. The
expected fraction of duration $v_{k}$ for the threshold strategy $k$ is equal
$v_{k}=\frac{N+1-k}{N}{\bf P}\\{T(k)=N+1\\}=\frac{N+1-k)k}{N^{2}}$ which is
unimodal with mode at $L_{N}=\left\lfloor\frac{N+1}{2}\right\rfloor$. Thus the
optimal rule is among the threshold rules with $k$ lower than $L_{N}$. The
asymptotic $\alpha=\lim_{N\rightarrow\infty}\frac{r^{\star}_{N}}{N}\cong
0.20388$ is the solution of the equation $-\log(x)-2+2x=0$. The limiting value
of the expected pay-off is $0.1618$.

####  2.2.4. Duration problem with recall and choice of the best ([6, Sec.
2.3]).

Let us define the maturity moment as $T(i)=T_{1}(i)$ and
$\xi_{i}=\zeta_{i}^{\star}$. The positive pay-off is when $T(i)=N+1$ only. The
optimal rule is the fixed sample size rule that stops at $L_{N}$. The
asymptotic optimal return is $0.25$.

###  2.3. The duration of the best or the second best

####  2.3.1. Distribution of a maturity moment.

Let $A=\\{1,2\\}$. The model without recall is considered. The maturity of the
candidate at $i$ is equal:

(10) $T(i)=\sum_{r=1}^{2}{\mathbb{I}}_{\\{Y_{\delta_{r}(i)}=r\\}}T_{r}(i),$

where $\delta_{r}(i)$, the position of the relatively $r$th at the moment $i$,
is equal $i$ for $r=1,2$. The conditional distribution of $T(i)$ is following:

:

$\mathbf{Y_{i}=2:}$ In this case $T(i)=k$ when
$Y_{i}=2,Y_{i+1}>2,Y_{i+2}>2,\ldots,Y_{k-1}>2,Y_{k}\in A$. We have for
$i<k\leq N$:

(11a) $\displaystyle{\bf P}\\{T(i)=k|Y_{i}=2\\}$
$\displaystyle=\frac{2(i-1)i}{(k-2)(k-1)k};$ (11b)
$\displaystyle\begin{split}{\bf
P}\\{T(i)=N+1|Y_{i}=2\\}&=1-\sum_{s=i+1}^{N}\frac{2(i-1)i}{(s-2)(s-1)s}\\\
&=\frac{i(i-1)}{N(N-1)}.\end{split}$

:

$\mathbf{Y_{i}=1;T(i)\leq N:}$ the random variable $T(i)=k$ if there exists
$s\in\\{i+1,\ldots,k-1\\}$ such that
$Y_{i}=1,Y_{i+1}>1,Y_{i+2}>1,\ldots,Y_{s-1}>1,Y_{s}=1,Y_{s+1}>2,\ldots,Y_{k-1}>2,Y_{k}\in
A$. We have for $i<k\leq N$

(12) ${\bf P}\\{T(i)=k|Y_{i}=1\\}&=\frac{2i(s-i+1)}{(k-2)(k-1)k}.$

:

$\mathbf{Y_{i}=1,T(i)=N+1,Y_{kN}=1\textrm{ or }2:}$ We have

(13) ${\bf
P}\\{T(i)=N+1,Y_{iN}=1|Y_{i}=1\\}&=1-\sum_{s=i+1}^{N}\frac{i}{(s-1)s}\\\
=\frac{i}{N};\\\ {\bf
P}\\{T(i)=N+1,Y_{iN}=2|Y_{i}=1\\}=\sum_{s=i+1}^{N}\frac{i}{(s-1)s}\\\
(1-\sum_{k=s+1}^{N}\frac{2(s-1)s}{(k-2)(k-1)k})\\\ =\frac{i(N-i)}{N(N-1)}\\\
{\bf P}\\{T(i)=N+1|Y_{i}=1\\}=\frac{i}{N}+\frac{i(N-i)}{N(N-1)}\\\
=\frac{i(2N-i-1)}{N(N-1)}$

######  Remark 3.

The solution of the problem (1) with $T(i)$ given by (10) will be performed by
its change to the optimal stopping problem for the embedded Markov chain. In
the case without recall there are no additional restrictions and $\xi_{n}=1$
for $n=1,2\ldots,N$. However, there is the obvious and interesting problem of
taking into account the value of a candidate who is kept until moment $n$ (see
[11]). Especially, when the value of the candidate is changed over time.

######  Remark 4.

The possibility of recall requires an additional clarification. The natural
models are as follows:

(i):

the possibility of returning to the best so far candidate means
$T(i)=T_{1}(i)$;

(ii):

the possibility to return to the last candidate is defined as
$T(i)={\mathbb{I}}_{\\{Y_{\delta_{r^{\star}}(i)}=r^{\star}\\}}T_{r^{\star}}(i)$,
where $r^{\star}=\mathop{\mathrm{arg\,max}}\displaylimits_{\\{s\in
A\\}}\delta_{s}(i)$.

Both approaches require access to the history of the observed random variables
during the selection process, each at a different extent.

The duration problem which requires the selected object to be of the
prescribed absolute rank (which is not higher than $a$) and matching the
expectations also needs further investigation.

####  2.3.2. The optimal stopping problem for the best or the second best
duration problem.

In the following lemma the function $\varphi(\cdot)$ is calculated. The final
form of it is using the digamma function ($\digamma$-function) $\psi_{n}(z)$
(see Abramowitz and Stegun [1] p. 260). For $n=0$ we will use the denotation
$\psi(z)$. This function is defined as $n$th logarithmic derivative of the
Euler gamma function $\Gamma(z)$

$\displaystyle\psi_{n}(z)$ $\displaystyle=$
$\displaystyle\frac{d^{n+1}}{d\\!z^{n+1}}\ln\Gamma(z)=\frac{d^{n}}{d\\!z^{n}}\frac{\Gamma^{{}^{\prime}}(z)}{\Gamma(z)}.$

######  Lemma 5.

The payoff function $\varphi(k,r)$ has the form

(14)
$\varphi(k,r)=\left\\{\begin{array}[]{ll}\frac{k}{N^{2}}\left(1+k-N-2N\psi(k)+2N\psi(N)\right)&\mbox{
for $r=1$,}\\\ \frac{k(N-k+1)}{N^{2}}&\mbox{ for $r=2$,}\\\ 0&\mbox{
otherwise.}\end{array}\right.$

Proof. Based on the distribution of the random variable $T(k)$ and the
equality $\psi(p+1)-\psi(p)=\frac{1}{p}$ for the digamma function we get

(15) $\varphi(k,1)&={\bf E}\\{\frac{T(k)-k}{N}|Y_{k}=1\\}\\\
=\frac{k}{N^{2}}\left(1+k-N-2N(\psi(k)-\psi(N))\right)\\\ \varphi(k,2)={\bf
E}\\{\frac{T(k)-k}{N}|Y_{k}=2\\}=\frac{k(N-k+1)}{N^{2}}$

$\blacksquare$

####  2.3.3. Solution of the optimal shelf life problem for the best and the
second best.

First of all the form of $T\varphi(k,r)$ for $(k,r)\in{\mathbb{E}}$ will be
given.

######  Lemma 6.

The expected payoff of the function $\varphi(\cdot)$ with relation to the
embedded Markov chain $\\{W_{t}\\}$ has the following form:

(16)
$T\varphi(k,r)=\frac{(N-k)((2N-1)k+N-1)}{N^{2}(N-1)}+2\frac{k}{N^{2}}(\psi(N)-\psi(k)).$

Proof. The definition of the embedded Markov chain (4) and the payoff function
$\varphi(\cdot)$ in the lemma 5 give

$\displaystyle T\varphi(k,r)$ $\displaystyle=$
$\displaystyle\sum_{j=k+1}^{N}\sum_{r=1}^{2}p(k,j)\varphi(j,r)$
$\displaystyle=$
$\displaystyle\sum_{j=k+1}^{N}\frac{k(k-1)}{j(j-1)(j-2)}\Big{(}\frac{j(2N(\psi(N)-\psi(j))+N-j-1)}{N^{2}}$
$\displaystyle+\frac{j(N-j+1)}{N^{2}}\Big{)}$ $\displaystyle=$
$\displaystyle\sum_{j=k+1}^{N}\frac{k(k-1)}{j(j-1)(j-2)}\left(\frac{j(N-j-1)}{N^{2}}(j+N+\frac{2N}{j}-\frac{2N}{N-1})\right)$
$\displaystyle=$
$\displaystyle\frac{(N-k)((2N-1)k+N-1)}{N^{2}(N-1)}+2\frac{k}{N^{2}}(\psi(N)-\psi(k)).$

$\blacksquare$

Let us denote $A_{k}(r)=\\{(s,r):s>k\\}$.

######  Theorem 7.

There are constants $k_{1}^{\star}$ and $k_{2}^{\star}$ such that the optimal
stopping time for the problem (1) has the form

$\tau^{*}=\inf\\{t:W_{t}\in A_{k_{1}^{\star}}\cup A_{k_{2}^{\star}}\\}.$

The value function is

$\displaystyle\tilde{v}_{N}(k_{1}^{\star},k_{2}^{\star})$ $\displaystyle=$
$\displaystyle\frac{(N(3N-4)-3)+k_{1}^{\star}(N-3)\psi(k_{1}^{\star})}{(N-1)N}$
$\displaystyle\mbox{}\frac{+k_{1}^{\star}(2(N^{2}-1)(\psi_{1}(k_{2}^{\star}+1)}{(N-1)N}-\frac{\psi_{1}(k_{1}^{\star}+1)))}{(N-1)N}$
$\displaystyle\mbox{}+\frac{k_{1}^{\star}\left(2(N-1)\psi(N)+(5-3N)\psi(k_{2}^{\star})\right)}{(N-1)N}$
$\displaystyle\mbox{}-\frac{k_{1}^{\star}\left(3N^{3}+(2k_{2}^{\star}-3)N^{2}-2\left({k_{2}^{\star}}^{2}+k_{2}^{\star}+2\right)N+{k_{2}^{\star}}^{2}+k_{2}^{\star}\right)}{(N-1)N^{2}k_{2}^{\star}}$

Proof. The payoff function $\varphi(\cdot,r)$ for $r\in A$ is unimodal. It can
be seen following the analysis of the differences
$\varphi(k+1,1)-\varphi(k,1)$ which are decreasing when $k\leq N-1$. The
comparison of events related to $T(k)=j$ on $Y_{k}=1$ and $Y_{k}=2$ leads to
the conclusion that $\varphi(k,1)\geq\varphi(k,2)$ for
$k\in\\{1,2,\ldots,N\\}$. The value function $\tilde{w}_{(}k)$ is no-
increasing due to the fact of decreasing number of stopping times in
${\mathfrak{M}}^{N}_{k}$. At $k=N-1$ both payoff functions are greater than
$\tilde{w}_{N}(N-1)$. Let us assume $k_{2}^{\star}=\inf\\{1\leq k\leq
N:T\varphi(k,i)\leq\varphi(k,2)\\}-1$. We have for $k>k_{2}^{\star}$ and
$r=1,2$ that $w_{N}(k,r)=\varphi(k,r)$ and $\tilde{w}_{N}(k)=T\varphi(k,r)$.
Let us denote $k_{1}^{\star}=\inf\\{1\leq k\leq
k_{2}^{\star}:\tilde{w}_{N}(r)<\varphi(k,1)\\}$, where
$\tilde{w}_{N}(k)=\tilde{v}(k,k_{2}^{\star})$ and for $k<s$ we have

$\displaystyle\tilde{v}_{N}(k,s)$ $\displaystyle=$
$\displaystyle\sum_{j=k+1}^{s}\frac{k}{j(j-1)}\varphi(j,1)+\frac{k}{s}\tilde{w}_{N}(s)$
$\displaystyle=$ $\displaystyle\frac{(N(3N-4)-3)+k(N-3)\psi(k)}{(N-1)N}$
$\displaystyle\mbox{}+\frac{k\left(2(N-1)\psi(N)+(5-3N)\psi(s)\right)}{(N-1)N}$
$\displaystyle\mbox{}+\frac{k\left(2(N^{2}-1)\left(\psi_{1}(s+1)-\psi_{1}(k+1)\right)\right)}{(N-1)N}$
$\displaystyle\mbox{}-\frac{k\left(3N^{3}+(2s-3)N^{2}-2\left(s^{2}+s+2\right)N+s^{2}+s\right)}{(N-1)N^{2}s}.$

$\blacksquare$

###  2.4. Discounted no-information duration problem (DNIDP)

The discounted model for no-information duration problem was formulated by
Ferguson et a. [6]. Methods of discounting applied in their paper assume that
the horizon is infinite but the future payoffs are discounted by coefficient
$\beta\in(0,1)$ in such a way that an amount of $1$ received at the moment $k$
is worth $(1-\beta)\beta^{k-1}$ at moment $0$. If the $k$-th object is
relatively the best, and if the decision maker selects it, the payoff is equal
to the discounted maturity moment of the object chosen. The conditional
expected return is then

${\bf
E}(1-\beta)\beta^{T_{1}(k)-1}T_{1}(k)=\sum_{j=k+1}^{\infty}(1-\beta)\beta^{j-1}jp(k,j)=(1-\beta)k\sum_{j=k}^{\infty}\frac{\beta^{j}}{j}.$

Hence ${\bf
E}(1-\beta)\beta^{T_{1}(k)-1}T_{1}(k)=(1-\beta)\sum_{j=k}^{\infty}\beta^{j}{\bf
P}(T_{1}(k)>j)$ because ${\bf
P}(T_{1}(k)>j)=\sum_{s=j+1}^{\infty}\frac{k}{s(s-1)}=\frac{k}{j}$. The problem
is to find $\tau^{\star}$ such that

(17) ${\bf
E}(1-\beta)\beta^{T_{1}(\tau^{\star})-1}T_{1}(\tau^{\star})=\sup_{\\{\tau\in\mathfrak{S}\\}}{\bf
E}(1-\beta)\beta^{T_{1}(\tau)-1}T_{1}(\tau)$

The unimodality of the conditional expected return allows to formulate the
optimal stopping time maximizing the expected discounted duration in model
formulated in this way.

######  Theorem 8.

(Ferguson et al. [6] ) In the discounted duration problem (17), the optimal
rule has the threshold form defined by

(18) $r^{\star}(\beta)=\min\\{r\geq
1:\sum_{j=r+1}^{\infty}\frac{\beta^{j}}{j}\sum_{k=r+1}^{j}\frac{1}{k-1}\leq\sum_{j=r}^{\infty}\frac{\beta^{j}}{j}\\}.$

The solution of the problem is closely related to the BCP with the random,
geometric number of objects.

##  3\. Markov model for full information duration problem.

In full information duration problem our aim is to chose the object and hold
it as long as it is in its position, and we may base our choice of the
stopping time on the true values of the object.

We introduce a Markovian approach (cf. Bojdecki [2]). Let $N\in\mathbb{N}$ be
a fixed number and $\\{X_{n}\\}_{n=1}^{N}$ be a sequence of i.i.d random
variables uniformly distributed on the interval $[0,1]$. For $n=1,...,N$
define $\mathcal{F}_{n}=\sigma(X_{1},...,X_{n})$ and let $\mathcal{T}$ denote
a set of all stopping times with respect to the family
$\\{\mathcal{F}_{n}\\}_{n=1}^{N}$. Let $\mathcal{T}_{0}$ denote a set of all
stopping times $\tau\in\mathcal{T}$ such that

$X_{n}=\max\\{X_{1},...,X_{n}\\}\textrm{ on }\\{\tau=n\\},n=1,...,N.$

Define the moments with the highest number of the observed value, i.e.

$\tau_{1}=1,\quad\tau_{k}=\inf\\{n:\tau_{k-1}\leq n\leq
N,X_{n}=\max\\{X_{1},...,X_{n}\\}\\}\textrm{ for }k=1,...,N.$

We observe that the sequence $\tau_{1},\tau_{2},...\in\mathcal{T}_{0}$. Now
let us consider the following chain

$Y_{k}=(\tau_{k},X_{\tau_{k}})\textrm{ on
}\\{\tau_{k}<N+1\\},Y_{k}=(\tau_{N+1},\xi),$

where $\xi$ is a special absorbing state. It is easy to see that
$\\{Y_{k}\\}_{k=1}^{N+1}$ is a Markov chain with transition probabilities

(19) $\begin{split}p((n,x),(m,B))&=P(\tau_{k+1}=m,X_{m}\in
B|\tau_{k}=n,X_{n}=x)\\\ &=x^{m-n-1}\int_{B}dy,\end{split}$

$m>n$ and $0$ otherwise, with $B\subseteq(x,1]$.

###  3.1. Full information duration problem (FIDP) - the classical version.

In classical FIDP we stop at the relatively best object and hold it as long as
it is the relatively best one. Let $w(n,x)$ denote the expected payoff given
that the $n$-th object is the relatively best object of value $X_{n}=x$ and we
select it. It is easy to see that

(20) $w(n,x)=\sum_{m=n+1}^{N+1}p((n,x),(m,B))(m-n).$

In our problem we assume that $B=(x,1]$ and $B=\xi$ for $m=N+1$. Therefore
(20) has the form

(21)
$w(n,x)=\sum_{m=n+1}^{N+1}x^{m-n-1}=\sum_{m=0}^{N-n}x^{m}=\dfrac{1-x^{N-n+1}}{1-x}.$

Let us denote $s:=N-n+1$, and $\tilde{w}(x,s):=\frac{1-x^{s}}{1-x}$. This
notation we can understand as a stopping on $s$-th object from the end. Using
the backward induction method the optimal rule can be found. The optimal
expected return when there are $s$ objects yet there is to be observed knowing
that the present maximum value of the past observations is $x$ is defined by

(22) $v(x,s)=xv(x,s-1)+\int_{x}^{1}\max\\{\tilde{w}(y,s),v(y,s-1)\\}dy$

with the initial point $v(x,0)\equiv 0$. The following theorem gives the
optimal stopping rule.

######  Theorem 9.

(Ferguson, Hardwick, Tamaki [6]) In the FIDP it is optimal to select the
relatively best object of value $X_{s}=x$ at $s$ stages from the end if $x\geq
x_{s}$, where $x_{1}=0$ and for $s>1,x_{s}$ is the unique root of the equation

(23)
$\sum_{i=1}^{s}x^{i-1}=\sum_{i=1}^{s-1}x^{i-1}\sum_{j=1}^{s-i}\frac{1-x^{j}}{j}.$

Since this problem is monotone then one-step-look-ahead rule is optimal. We do
not write here a proof. This problem is related to the full information random
horizon best choice problem of Porosiński [15]. The optimal rules in this two
problems are the same. In [15] the author gives an asymptotic approximation
for the $x_{n}$ as $n\rightarrow\infty$. Substituting
$x_{n}:=1-\frac{z_{n}}{n}$ to (23) and keeping this equation stay zero $z_{n}$
must converge to some constant $z$, where $z$ satisfies the equation

(24) $\int_{0}^{z}e^{t}(1-\int_{0}^{t}\frac{1}{u}(1-e^{-u})du)dt=0.$

Using numerical methods it can be found that $z\approx 2.1198$. Therefore
$x_{n}\approx 1-\frac{2.1198}{n}$. Determining the value of the problem as

$V(n)=v(0,n)$

in [13] there is an approximated win probability given by

$\dfrac{V(n)}{n}\rightarrow C$

as $n\rightarrow\infty$, where $C$ is constant given by

$C=\int_{0}^{1}e^{-\frac{z}{u}}(\int_{0}^{u}(\dfrac{e^{\frac{zt}{u}}-1}{t}+\dfrac{e^{\frac{zt}{u}}}{1-t})dt-1)du$

using the numerical methods $C\approx 0.435171$. The payoff function in this
problem is almost the same as the payoff function in the full information best
choice problem with the random, uniformly discrete distributed on
$\\{1,...,n\\}$ horizon. The relation is that the payoff in FIDP is $n$ times
greater than in corresponding best choice problem (see: Gnedin [10]).

In the problem where recall is possible to find the optimal strategy we use
1-Step-Look-Ahead method. If we stop at $s$ stages from the end with an object
of value $x$, then our expected payoff is $\tilde{w}(x,s)$. Continuing one
step we expect to receive

$x\tilde{w}(x,s-1)+\int_{x}^{1}\tilde{w}(y,s-1)dy.$

After the simple calculation we get the optimal rule. The result is in the
following

######  Theorem 10.

(Ferguson, Hardwick, Tamaki [6]) In the FIDP with recall it is optimal to stop
at $s$ stages from the end if the largest of the values observed is at least
$x_{s}$, where $x_{s}\in[0,1]$ is the root of the following equation

(25) $\sum_{j=1}^{s-1}\dfrac{1-x^{j}}{j}=1.$

This is also the solution of the full information random horizon best choice
problem with recall. Substituting $x:=1-\frac{z}{n}$ to (23) and taking the
limit $n\rightarrow\infty$ we need to find the solution of the following
integral

(26) $\int_{0}^{1}\dfrac{1-e^{-zy}}{y}dy=1.$

Numerical methods give us $x_{n}\approx 1-\frac{1.345}{n}$.

###  3.2. Best choice duration problem (BCDP).

In BCDP we win the duration of owning the relatively best object only if it is
the best object overall.

Once again we introduce Markovian approach as in Section 2. In looking for the
best object we need to stop at the last stage before the process terminates.
Let $w(n,x)$ denote the expected payoff given that the $n$-th object is the
relatively best object of value $X_{n}=x$, we select it and it is the maximum
value overall. It can be observed that

(27) $w(n,x)=\sum_{m=n+1}^{N+1}p((n,x),(N+1,\xi))f(m,B).$

where $B=(x,1]$ and $B=\xi$ for $m=N+1$. Therefore (27) has the form

(28)
$w(n,x)=\sum_{m=n+1}^{N+1}x^{N-n}=x^{N-n}\sum_{m=n+1}^{N+1}=x^{N-n}(N-n+1).$

Let us denote $s:=N-n+1$, and $\tilde{w}(x,s):=sx^{s-1}$. Once again we can
think about this notation as a stopping at $s$th candidate from the end. In
this problem recursion (22) can be used. As a result we get the following

######  Theorem 11.

In the full information BCDP it is optimal to select the relatively best
object of the value $X_{s}=x$ at $s$ stages from the end if $x\geq x_{s}$,
where $x_{1}=0$ and $x_{s},s>1$ is the unique root of the equation

(29) $\sum_{j=1}^{s-1}x^{j-1}=sx^{s-1}.$

The value of the problem was found by Tamaki in [26]. It can be shown that the
optimal limiting payoff is given by

(30)
$v^{*}=\int_{0}^{1}\dfrac{1}{x}\left[\int_{0}^{x}e^{-\frac{c^{*}x}{1-y}}dy\right[dx-2\int_{0}^{1}ye^{-\frac{c^{*}}{y}}dy\approx
0.31096,$

where $c^{*}\approx 1.2564$ is a unique solution of the equation

$e^{c}=1+2c.$

With recall the optimal limiting payoff is given by

(31) $u^{*}=\dfrac{1-\log(2)}{2}+(\log(2))^{2}I(\log(2))\approx 0.33536,$

where $I(\cdot)$ is given by

$I(c)=\int_{1}^{\infty}\dfrac{e^{-ct}}{t}dt.$

###  3.3. Random Horizon Full information duration problem (RHFIDP).

Let us assume that the number of actually available objects $N$ is random.
This additional uncertainty in the FIDP will cause the necessity of a
clarification of the very concept of the duration. The random horizon duration
problem (RHDP) for the no-information case was investigated by Tamaki [24]. He
extended the research on RHDP for the full-information case in [25]. Let $N$
be assumed a bounded random variable, independent of the sequence
$X_{1},X_{2},\ldots,X_{n}$, and having a prior distribution
$\vec{p}=(p_{1},p_{2},\ldots,p_{n})$, where $p_{k}={\bf P}\\{N=k\\}$ are such
that $\sum_{k=1}^{n}p_{k}=1$ and $p_{n}>0$ for a known upper bound $n$. In
[25] the RHDP was distinguished into two models according to whether the final
stage of the planning horizon is $N$ or $n$. This distinction is related to
the last relative maximum. That is, if the chosen object is the last relative
maximum prior to $N$, we hold it until the stage $N$ in the first model,
whereas until the stage $n$ in the second model. The classical, finite
deterministic horizon FIDP occurs as a special case of the RHDP if $N$
degenerates to $n$. In this case there is no difference between these two
approaches. The performance measure is the proportional duration of holding
the candidate (the relative maximum of the observed sequence).

In this paper the extension to the unbounded random horizon FIDP will be
treated. For further consideration let us formulate first the main elements of
the Tamaki’s model with planning horizon $N$ investigated in [25]. For a given
prior $\vec{p}$ let $\pi_{k}={\bf P}\\{N\geq k\\}$. Let $(k,x)$ be the state,
where it is just observed, $k$-th observation to be a candidate having the
value $x$, i.e $X_{k}=\max\\{X_{1},\ldots,X_{k}\\}=x$, $1\leq k\leq n$,
$0<x<1$. Denote by $s_{k}(x)$ the payoff earned by stopping with the current
candidate in state $(k,x)$. It is the expected value of the proportional
duration $D_{k}(x)$ when the candidate is the state $(k,x)$ (see Lemma 2.1 in
[25]). Let $I_{j}(x)=\chi_{\\{\omega:X_{j}(\omega)<x\\}}(\omega)$ for $1\leq
j\leq n$, $0<x<1$. The proportional duration (see Appendix A of [25]) is

(32)
$D_{k}(x)=\frac{1}{n}\left[1+\sum_{i=k+1}^{N}\prod_{j=k+1}^{i}I_{j}(x)\right]$

and the payoff has the form:

(33) $s_{k}(x)=\frac{1}{n}\frac{1}{\pi_{k}x^{k}}\sum_{i=k}^{n}\pi_{i}x^{i}.$

Also let $c_{k}(x)$ denote the payoff earned by continuing observations in an
optimal manner. Then $v_{k}(x)=\max\\{s_{k}(x),c_{k}(x)\\}$ is the optimal
payoff provided that we start from the state $(k,x)$. If the decision maker
decides to proceed to the next stage after leaving the state $(k,x)$, the
$(k+1)$-th object can be observed only with probability ${\bf P}\\{N\geq
k+1|N\geq k\\}=\frac{\pi_{k+1}}{\pi_{k}}$ and it gives the state $(k+1,y)$ if
this new observation is a candidate with the value $y$, which is bigger than
$x$, while it pretends to leave the state $(k+1,x)$ if it is not a candidate.
It leads to the recursive equation:

(34)
$c_{k}(x)=\frac{\pi_{k+1}}{\pi_{k}}\left[xc_{k+1}(x)+\int_{x}^{1}v_{k+1}(y)dy\right],\text{
$1\leq k<n$,}$

with the boundary condition $c_{n}(x)\equiv 0$. The repeated use of (34)
yields

(35)
$c_{k}(x)=\sum_{i=k+1}^{n}\frac{\pi_{i}}{\pi_{k}}x^{i-k-1}\int_{x}^{1}s_{i}(y)dy.$

Since, for the given $k$, $s_{k}(x)$ is an increasing function of $x$ by (33)
while $c_{k}(x)$ is a non-increasing function in $x$ from its definition, then
there exists a sequence of thresholds
$\vec{a}^{\star}=(a_{1}^{\star},\ldots,a_{n}^{\star})$ such that, when in the
state $(k,x)$, the optimal rule stops with the current candidate iff $x\geq
a_{k}^{\star}$ i.e.
$\tau_{n}(\vec{(}a)^{\star})=\min\\{k:X_{k}=\max\\{X_{1},\ldots,X_{k}\\}\geq
a_{k}^{\star}\\}\wedge n$.

###  3.4.  The unbounded horizon full-information duration problem.

Let us consider the duration problem when the horizon $N$ is unbounded. The
equations (32) and (33) depend on the tail probabilities of the horizon
distribution. They allow to formulate the equation for the value function of
the problem in the form (34) with an additional requirement that the solution
$v_{k}(x)$ should be a continuous function of $x$ (a smooth fit condition).
The methods of solving such an equation are well known in MDP theory. The
special case of the horizon with the geometric distribution is worth be solved
due to many reasons. Let us observe that $s_{k}(x)$ is independent of $k$
because the duration of the candidate at the state $(k,x)$ is $s$ by two
exclusive ways:

  1. (1)

$N\geq k+s$ and $X_{k+1}<x$, $\ldots$, $X_{k+s}>x$;

  2. (2)

$N=k+s-1$ and $X_{k+1}<x$, $\ldots$, $X_{k+s}<x$.

It leads to

$\displaystyle s_{k}(x)$ $\displaystyle=$ $\displaystyle{\bf
E}[nD_{k}(x)]=\sum_{j=1}^{\infty}j[(1-x)x^{j-1}\frac{\pi_{k+j}}{\pi_{k}}+x^{j-1}\frac{\pi_{k+j-1}}{\pi_{k}}]$
$\displaystyle=$
$\displaystyle[(1-x)q+p]\sum_{j=1}^{\infty}j(qx)^{j-1}=[(1-x)q+p]\frac{1}{(1-qx)^{2}}$
$\displaystyle=$ $\displaystyle\frac{1}{1-qx}$

for the geometric distribution. There same result is given by (33) when the
geometric horizon is applied.

Given that the payoff function does not depend on $k$ and the lack of memory
properties of the geometric distribution also the payoff earned by continuing
observations in an optimal manner $c_{k}(x)=c(x)$ and the optimal payoff
$v_{k}(x)=v(x)$ provided that we start from state $(k,x)$ do not depend on
$k$. We have

(37) $c(x)=q[xc(x)+\int_{x}^{1}v(y)dy],$

which gives $c(x)=q(1-qx)^{-1}\int_{x}^{1}v(y)dy$. The optimal payoff

(38) $v(y)=\max\\{c(x),s(x)\\}=(1-qx)^{-1}\max\\{1,q\int_{x}^{1}v(y)dy\\}.$

For $x$ enough close to $1$ we have $v(x)=s(x)$. It means that the stopping
region contains $\\{(k,x):x\geq x_{0}\\}$, where $x_{0}$ fulfils the condition
$\int_{x_{0}}^{1}v(y)dy=\frac{1}{q}$. For $x\leq x_{0}$ the optimal payoff
fulfil eqution:

(39) $(1-qx)v(x)=a[\int_{x}^{x_{0}}v(y)dy+\int_{x_{0}}^{1}\frac{1}{1-qy}dy].$

It implies that $v(x)=\text{const}$ for $x\in(0,x_{0}]$. The continuity
condition forces $v(x_{0})=(1-qx_{0})^{-1}$. If such $x_{0}\in(0,1)$ exists
then by (39) we get $\ln\frac{1-q}{1-qx_{0}}=-1$. The function
$\varphi(t)=1+\ln\frac{p}{t}$ is well defined for $t\in(p,1)$. It is non-
increasing in this domain, $\varphi(p)=1$ and $\varphi(1)<0$ when
$p<\exp(-1)$.

######  Conclusion 1.

If $p\leq\exp(-1)$, then there is $x_{0}=\frac{1-ep}{q}\in(0,1)$ such that
$\\{(k,x):x\geq x_{0}\\}$ is the optimal stopping region for RHFIDP with the
geometric horizon. The expected optimal payoff is
$v^{\star}=\frac{x_{0}}{1-qx_{0}}-\frac{1}{q}\ln\frac{1-q}{1-qx_{0}}$.

If $p>\exp(-1)$ then the optimal stopping region for RHFIDP is the hole state
space. The decision maker should stop at the first observation obtaining the
expected payoff $v^{\star}=-\frac{1}{q}\ln(1-q)$.

######  Remark 12.

The definition of the duration depends on the context. In the seminal paper by
Ferguson et al. [6] there are various models. In most of them the maturity of
the accepted object is the moment when it stops to be the candidate. There are
other cases when the maturity is related to the approach of the horizon. In
the finite horizon case it is assumed that the duration is expanded by adding
$1$. When the horizon is random, as in this section, the same understanding of
the maturity is applied. However, in various applications such a definition of
the maturity should be corrected. If we buy obligation then it has an
additional value to the prescribed moment. If this maturity moment is random
we can consider the case when the random horizon is observed immediately or we
learn about the maturity by symptoms like an absence of new observations.

Assuming the maturity as an immediate close when the decision maker reaches
the last observation the expected payoff defined by (3.4) is changed to

$\displaystyle\tilde{s}_{k}(x)$ $\displaystyle=$ $\displaystyle{\bf
E}[n\tilde{\mathcal{D}}_{k}(x)]=\sum_{j=1}^{\infty}j[(1-x)x^{j-1}\frac{\pi_{k+j}}{\pi_{k}}+x^{j}\frac{\pi_{k+j}}{\pi_{k}}]$
$\displaystyle=$
$\displaystyle[(1-x)q+pqx]\sum_{j=1}^{\infty}j(qx)^{j-1}=[(1-x)q+pqx]\frac{1}{(1-qx)^{2}}$
$\displaystyle=$ $\displaystyle\frac{q}{1-qx}.$

The optimal strategy does not change with respect to the previous model but
the expected optimal payoff does.

###  3.5. Duration of owning relatively best or second best object.

This problem was firstly considered by Kurushima and Ano. The objective is to
maximize the time period of owning the relatively best and the relatively
second-best object. Here we consider the class of the stopping rule restricted
only to stop at the relatively best object. Let $U_{n}(x)$ denote the expected
duration of the relatively best object whose rank remains within the two when
the time to go is $n$ and the decision maker accepts the relatively best
applicant whose value $x$ is the maximum value among that of the applicants
arrived so far, that is $X_{n}=x$. $U_{n}(x)$ is given by

(41) $U_{n}(x)=2\sum_{k=1}^{n-1}x^{k-1}-nx^{n-1}.$

Let $G_{n}(x)$ define

(42) $G_{n}(x)=U_{n}(x)-\sum_{k=1}^{n-1}x^{k-1}\int_{x}^{1}U_{n-k}(y)dy.$

The 1-SLA calls for a stop in the region $B$ which is described as
$B=\\{(n,x):G_{n}(x)\geq 0\\}$, where $(n,x)$ is represented by the state when
the time to go is $n$ and the present applicant is the relatively best one
whose value $x$ is the maximum value among the applicants arrived so far. To
show that the 1-SLA stopping rule is optimal, it is sufficient to show the
next two statements:

  1. (1)

$G_{n}(x)\geq 0\Rightarrow G_{n-k}(x)\geq 0,k=1,2,\ldots$

  2. (2)

$G_{n}(x)\geq 0\Rightarrow G_{n}(y)\geq 0,y\geq x$.

The first statement is presented in the mentioned paper. The second remains as
an open problem. This problem is concluded by

######  Conjecture 1.

(see: [12]) For the full-information case of the duration problem where the
objective is to maximize the duration of owning the relatively best or the
second-best object, we assume that the class of the stopping rule is
restricted to that of stopping only at the relatively best object. Then, the
optimal stopping rule is to accept the first applicant who has the maximum
$X_{n}=x\geq s_{n}$ among the observed objects so far when the remaining time
is $n$, where $s_{1}=1$ and $s_{n},n\geq 2$ is the unique root of the equation

$3\sum_{k=1}^{n}x^{k-1}-2nx^{n-1}-2\sum_{k=1}^{n-1}x^{k-1}\sum_{j=1}^{n-k-1}\frac{1}{j}+2\sum_{k=1}^{n-1}x^{k}\sum_{j=1}^{k}\frac{1}{j}=0.$

###  3.6. Duration of owning relatively best or second best object for
unbounded horizon.

####  3.6.1. Applying geometrical horizon in Kurushima and Ano problem.

Our aim is to maximize the duration of owning the relatively best or the
second best object, where the class of stopping times is restricted to the
relatively best objects. We observe $N$ random variables from the known
distribution. We consider a special case where $N$ is a random variable
geometrically distributed, i.e.

(43) $P(N=k)=p_{k}=pq^{k-1},\quad 0<p<1;q=1-p.$

Let $w(n,x)$ denote the payoff for stopping at the $n$-th object whose value
is $x$.

(44) $w(n,x)={\bf
E}[T_{n}-n|X_{n}=x]=\frac{2q}{1-qx}-\frac{q(1-q)}{(1-qx)^{2}}.$

If we continue observations we expect to get a reward $Tw(n,x)$:

(45)
$\begin{split}Tw(n,x)&=\sum_{m=n+1}^{\infty}\int_{x}^{1}w(n,v)\dfrac{\pi_{m}}{\pi_{n}}x^{m-n-1}dv\\\
&=\dfrac{q}{1-qx}\Big{(}2\log\big{(}\frac{qx-1}{q-1}\big{)}+\frac{1-q}{1-qx}-1\Big{)}.\end{split}$

Denote $G(n,x):=w(n,x)-Tw(n,x)$. The 1-SLA rule is described by the following
set:

$B=\\{(n,x):G(n,x)\geq 0\\}.$

To prove the optimality of the 1-SLA rule it is necessary to show two things:
(i) $G(n,x)\geq 0\Rightarrow G(n+k,x)\geq 0,k=1,2,...$ and (ii) $G(n,x)\geq
0\Rightarrow G(n,y),y\geq x$. (i) is obvious, because payoffs do not depend on
$n$. Consider the function $g(x):=G(n,x)$. We will show that if $g(x)\geq x$
for some $x$ then it will be greater than $0$ for $y>x$. It is an equivalent
to the statement if for a given $x$ inequality

$3-2\dfrac{1-q}{1-qx}-\log\big{(}\frac{1-qx}{1-q}\big{)}^{2}\geq 0,$

holds then the same is for every $y>x$. Calculating a derivative of LHS we get

$-2q(1-q)\dfrac{1}{(1-qx)^{2}}+2q(1-qx)\dfrac{1}{(1-qx)^{2}}=\dfrac{2q^{2}(1-x)}{(1-qx)^{2}}.$

It is non-negative for every $x\leq 1$ and in point $x=1$ it has the value
$1$. If the inequality on LHS is true for the given $x$ then it is true for
$x<y<1$. We conclude that the 1-SLA rule is optimal. It is a threshold
strategy with threshold

(46) $\dfrac{\mu^{\star}p-1}{p-1},$

where $\mu^{\star}$ is a solution of the equality

$\mu^{2}e^{\frac{2}{\mu}}=e^{3},\mu>1.$

Numerically $\mu^{\star}\approx 3.3145.$ Note that if
$p\geq\frac{1}{\mu^{\star}}\approx 0.3017046$ the threshold is $0$ so the
1-SLA rule calls for a stop at the very first observation.

####  3.6.2. Stopping on the best and the second best object.

Assume that at the moment $n$ we are interested in choosing the relatively
best or second best object. We choose the object and hold it as long as it is
the relatively best or second best object. We observe sequentially
$X_{1},...,X_{N}$ i.i.d. $N$ is as in (43). Let $\zeta_{n}$ denote the largest
observation of sequence $X_{1},...,X_{n}$ and similarly $\eta_{n}$ denote the
second largest value of the sequence ($\zeta_{1}=X_{1},\zeta_{n}=X_{n:n}$ for
$n>1,\eta_{1}=0,\eta_{n}=X_{n-1:n}$ for $n>1$). Let $T_{n}$ be a random
variable that denotes the moment after the time $n$ when a better observation
occurs. Our aim is to find such a stopping time $\tau^{*}\in\mathcal{T}$ that

$P(\tau^{*}\leq N,T_{\tau^{*}}-\tau^{*},X_{\tau^{*}}=\zeta_{\tau^{*}}\textrm{
or }X_{\tau^{*}}=\eta_{\tau^{*}})$

is maximized, where $\mathcal{T}$ denotes a set of all stopping times with
respect to the family $\\{\mathcal{F}_{n}\\}_{n=1}^{\infty}$. Denote $R_{n}$
the rank of $n$th observation, i.e. a random variable:

$R_{n}=\begin{cases}1,X_{n}=\zeta_{n}\\\ 2,X_{n}=\eta_{n}.\end{cases}$

Let

$\begin{split}\tau_{1}&=1\\\ \tau_{k+1}&=\inf\\{n:\tau_{k}<n\leq
N,X_{n}\geq\eta_{\tau_{k}},k\in\mathbb{N}\\}.\end{split}$

Let us define a sequence

(47)
$\begin{split}Y_{k}&=(\tau_{k},\zeta_{\tau_{k}},\eta_{\tau_{k}},R_{\tau_{k}}),\quad\textrm{
if }\tau_{k}<\infty\\\ Y_{k}&=\delta,\quad\textrm{ if
}\tau_{k}=\infty,\end{split}$

where $\delta$ is the special absorbing state. It is easy to verify that (47)
is a Markov chain with respect to
$\mathcal{F}_{\tau_{k}}=\sigma(X_{1},...,X_{\tau_{k}},\mathbb{I}_{(N\geq
0)},...,\mathbb{I}_{(N\geq\tau_{k}-1)}),k=1,2....$ The transition
probabilities are:

(48)
$p((n,x,y,i),(m,[0,u],x,1))=\begin{cases}\dfrac{\pi_{m}}{\pi_{n}}y^{m-n-1}(u-x),u>x\\\
0,\textrm{ otherwise},\end{cases}$ (49)
$p((n,x,y,i),(m,x,[0,u],2))=\begin{cases}\dfrac{\pi_{m}}{\pi_{n}}y^{m-n-1}(u-y),y\leq
u\leq x\\\ 0,\textrm{ otherwise},\end{cases}$

for $m>n,i=1,2$, where $\pi_{k}=\sum_{j=k}^{\infty}p_{j}=q^{k-1}$. We derive
the payoff function. If we stop at the state $(n,x,y,1)$ then the duration of
the candidate is $k$ if:

  1. (1)

if there are two candidates of rank $1$: one at the time $n+1$ and the second
at some point between $n+1$ and $n+k-1$ inclusive and the time horizon is
longer than $n+k$

  2. (2)

if there is one candidate of rank $1$ between $n+1$ and $n+k-1$ inclusive and
the time horizon is $n+k$

  3. (3)

if there is no more better candidates and time horizon is $n+k$

If we stop at state $(n,x,y,2)$ then the duration of candidate is $k$ if:

  1. (1)

if there is one candidate of rank $1$ or $2$ at the time $n+k$ and the time
horizon is longer than $n+k$

  2. (2)

if there are no more better candidates and the time horizon is $n+k$

The payoff function is given by:

(50) $\begin{split}W((n,x,y,1))&={\bf
E}[T_{n}-n|X_{n}=x,R_{n}=1,\zeta_{n}=x,\eta_{n}=y]\\\
&=\frac{2q}{1-qx}-\frac{q(1-q)}{(1-qx)^{2}}\\\ W((n,x,y,2))&={\bf
E}[T_{n}-n|X_{n}=y,R_{n}=2,\zeta_{n}=x,\eta_{n}=y]\\\
&=\frac{q}{1-qy}\end{split}$

Note that both functions do not depend on $n$. This will not be mentioned
later. Let $T$ be an operator $Tf(x)=\int_{X}f(z)dP_{x}(z)$ for the bounded
function $f:X\rightarrow\mathbb{R}$. Then

(51)
$\begin{split}TW(x,y,i)&=\dfrac{q}{1-qy}\Big{(}\log\big{(}\frac{(1-qy)(1-qx)}{(1-q)^{2}}\big{)}+\frac{1-q}{1-qx}-1\Big{)}\quad
i=1,2.\end{split}$

We transform our equations in the following way:

$s:=\frac{1-q}{1-qx},\qquad t:=\frac{1-q}{1-qy},\qquad\alpha:=\frac{q}{1-q},$

and $\frac{1}{1+\alpha}\leq t\leq s\leq 1$, where $\alpha\in[0,\infty)$. Our
payoff function is now given by:

(52) $\begin{split}W(s,t,1)&=\alpha s(2-s)\\\ W(s,t,2)&=\alpha t\\\
TW(s,t,i)&=\alpha t\left(-\log(st)+s-1\right),\quad i=1,2.\end{split}$

Let us denote $F(s,t):=W(s,t,1)-TW(s,t,1)$ and $G(s,t):=W(s,t,2)-TW(s,t,2)$.
To find the stopping set we need to find the set that satisfies the optimality
equation. Let $B_{1}=\\{(s,t):F(s,t)\geq 0\\},B_{2}=\\{(s,t):G(s,t)\geq 0\\}$.

Note that the sign of the functions $F$ and $G$ does not depend on the
parameter $\alpha$. These sets are the same as in [16] (page 685). Using the
same methodology we obtain the optimal strategy: it allows us to stop only in
such a moment, when observed candidate is the largest so far and exceeds the
value $x^{\star}$. This value is independent of the value of the second
largest object. The problem is now transformed into the problem of stopping
only at the largest observations, as it was in Kurushima and Ano problem with
the geometrical horizon. Even if we observe the value of the second largest
object it does not affect the optimal strategy. We can reduce the problem to
observing only the relatively best objects.

##  4\. Conclusion and acknowledgements

We have presented different results regarding the duration problem. This is
the very first time, when all results from different papers are collected in
one place. The previous results were presented in a new form and thanks to
that it is easy to see connection between two problems. A very intriguing
issue seems to be the problem with random geometrically distributed horizon.
The geometric distribution has memoryless property and this is the reason why
the result is quite simple.

We are grateful to an anonymous referee for the several comments and
improvements of this paper.

## References

  * [1] M. Abramowitz and I. A. Stegun, editors.  Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables.  Dover, New York, 1972.
  * [2] T. Bojdecki.  Probability maximizing approach to optimal stopping and its application to a disorder problem.  Stochastics, 3:61–71, 1979.  Zbl 432.60051; MR 0546700;  doi: 10.1080/17442507908833137.
  * [3] F. Bruss and L. Rogers.  Embedding optimal selection problems in a Poisson process.  Stochastic Processes Appl., 38(2):267–278, 1991.  Zbl 0745.60040;  doi: 10.1016/0304-4149(91)90094-S.
  * [4] F. Bruss and L. Rogers.  Pascal processes and their characterization.  Stochastic Processes Appl., 37(2):331–338, 1991.  Zbl 0743.60043;  doi: 10.1016/0304-4149(91)90052-E.
  * [5] E. Dynkin and A. Yushkevich.  Theorems and Problems on Markov Processes.  Plenum, New York, 1969.
  * [6] T. Ferguson, J. Hardwich, and M. Tamaki.  Maximizing the duration of owning a relatively best object.  In T. S. Ferguson and S. M. Samuels, editors, Strategies for Sequential Search and Selection in Real Time, Proceedings of the AMS-IMS-SIAM Join Summer Research Conferences held Amherst, MA, June 21-27, 1990, volume 125 of Contemp. Math., pages 37–57. Amer. Math. Soc., Providence, RI, 1992.  MR 1160608; Zbl 0745.62079;  doi: 10.1090/conm/125/1160608.
  * [7] P. Freeman.  The secretary problem and its extensions: a review.  Int. Statist. Rev., 51:189–206, 1983.
  * [8] M. Gardner.  Mathematical games.  Scientific American, 202(1,3):150–156;172–182, 1960.
  * [9] J. Gilbert and F. Mosteller.  Recognizing the maximum of a sequence.  J. Am. Stat. Assoc., 61:35–73, 1966.
  * [10] A. V. Gnedin.  Objectives in the best-choice problems.  Sequential Anal., 24(2):177–188, 2005.
  * [11] A. V. Gnedin.  Optimal stopping with rank-dependent loss.  J. Appl. Probab., 44(4):996–1011, 2007.
  * [12] A. Kurushima and K. Ano.  Full-information duration problem and its generalizations.  Sūrikaisekikenkyūsho Kōkyūroku, (1682):50–54, 2010.  Mathematics of decision-making under uncertainty (Japanese) (Kyoto, 2002).
  * [13] V. Mazalov and M. Tamaki.  An explicit formula for the limiting optimal gain in the full information duration problem.  Sūrikaisekikenkyūsho Kōkyūroku, (1306):217–222, 2003.  Mathematics of decision-making under uncertainty (Japanese) (Kyoto, 2002).
  * [14] V. V. Mazalov and M. Tamaki.  Duration problem on trajectories.  Stochastics, 79(3-4):211–218, 2007.
  * [15] Z. Porosiński.  The full-information best choice problem with a random number of observations.  Stochastic Process. Appl., 24(2):293–307, 1987.
  * [16] Z. Porosiński and K. Szajowski.  On some selection problem.  In Proceedings of 14th IFIP Conference, pages 679–687, Leipzig, 1987.
  * [17] E. Presman and I. Sonin.  The best choice problem for a random number of objects.  Theory Prob. Appl., 17:657 – 668, 1972.
  * [18] W. Rasmussen and H. Robbins.  The candidate problem with unknown population size.  J. Appl. Probab., 12:692–701, 1975.
  * [19] J. Rose.  Twenty years of secretary problems: a survey of developments in the theory of optimal choice.  Management Studies, 1:53–64, 1982.
  * [20] S. Samuels.  Secretary problems.  In B. Ghosh and P. Sen, editors, Handbook of Sequential Analysis, pages 381–405. Marcel Decker, New York, 1991.
  * [21] A. Suchwałko and K. Szajowski.  Non standard, no information secretary problems.  Sci. Math. Japonicae, 56:443 – 456, 2002.
  * [22] K. Szajowski.  Optimal choice problem of a-th object.  Matem. Stos., 19:51–65, 1982.  in Polish.
  * [23] K. Szajowski and M. Tamaki.  Shelf Life of Candidates in the Generalized Secretary Problem.  ArXiv e-prints, page 10p., Feb. 2009.
  * [24] M. Tamaki.  Optimal stopping rule for the no-information duration problem with random horizon.  Adv. in Appl. Probab., 45(4):1028–1048, 2013.
  * [25] M. Tamaki.  Urn sampling distributions giving alternate correspondences between two optimal stopping problems.  Preprint, Faculty of Business Administration, Nagoya Campus, Hiraike 4-60-6, Nakamura, Nagoya, Aichi 453-8777, Japan, August 2013.
  * [26] M. Tamaki.  On the optimal stopping problems with monotone thresholds.  Sūrikaisekikenkyūsho Kōkyūroku, (1912):202–210, 2014.  Mathematics of decision-making under uncertainty (Japanese) (Kyoto, 2014).


11institutetext:  Department of Physics and INFN, University of Rome “Tor
Vergata”, Via della Ricerca Scientifica 1, 00133, Rome, Italy

First pacs description

# Data reconstruction for complex flows using AI: recent progress, obstacles,
and perspectives

Michele Buzzicotti<EMAIL_ADDRESS>
###### Abstract

In recent years the fluid mechanics community has been intensely focused on
pursuing solutions to its long-standing open problems by exploiting the new
machine learning, (ML), approaches. The exchange between ML and fluid
mechanics is bringing important paybacks in both directions. The first is
benefiting from new physics-inspired ML methods and a scientific playground to
perform quantitative benchmarks, whilst the latter has been open to a large
set of new tools inherently well suited to deal with big data, flexible in
scope, and capable of revealing unknown correlations. A special case is the
problem of modeling missing information of partially observable systems. The
aim of this paper is to review some of the ML algorithms that are playing an
important role in the current developments in this field, to uncover potential
avenues, and to discuss the open challenges for applications to fluid
mechanics.

###### pacs:

nn.mm.xx

##  1 INTRODUCTION

There is no doubt that our ability to produce, collect and analyze data is
rapidly increasing boosted by a positive feedback loop between technological
progress and new algorithms. Computer scientists, engineers, as well as
physicists and mathematicians, are pushing toward the new machine learning
(ML) era, which has already resulted in reforming standard data-analysis
paradigms. Breakthroughs have been achieved in numerous areas of computer
science, from computer vision (CV) [1, 2], up to natural language processing
[3, 4, 5] as well as in some scientific contexts as the protein folding
problem [6].

In complex flows as well, there have been numerous positive outcomes in nearly
all testing scenarios, varying from control problems as single and multi-
agents navigation in complex environments [7, 8, 9, 10, 11, 12, 13, 14, 15],
to turbulent control and drag reduction [16, 17, 18, 19, 20, 21], up to data
assimilation problems [22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33] to cite
few of them. However, applications in fluids are still in their infancy, and
the majority of cases are either conducted on highly idealized setups or only
showing preliminary results on more realistic conditions. The objective of
this paper is to examine some of the ML tools that have been applied with
promising results to reconstruct data from incomplete observations of complex
systems, including idealized turbulent [34, 35, 36, 37, 38, 39, 40, 41],
engineering [42, 43, 44, 45], and geophysical flows [33, 32], and to discuss
the possible future directions for quantitative advancements in fluid
mechanics.

Data reconstruction is the art of filling in missing information by
interpolating, denoising, or super-resolving a single realization, or a time
series, of data fitting a specific statistical distribution [46, 47]. ML
applications for data reconstruction are emerging in many areas, from computer
vision [48, 49, 50, 51], to medical imaging [52, 53, 54] up to seismic data
reconstruction [55, 56] and astrophysics [57, 58]. Also in geophysical fluid
dynamics works using ML to reconstruct missing data are rapidly growing [59,
60, 61, 62, 63, 64].

[width=1.]Fig1.pdf

Figure 1: Graphical illustration of different types of reconstructions. Panel
(i) the full state reconstruction from partial observations, gap fill. Panel
(ii) inverse problems, reconstruction of missing physical quantities coupled
to the observed ones. Panel (iii) Super-resolution, this is equivalent to a
gap reconstruction on the high Fourier space frequencies. Panel (iv) Dynamical
reconstruction, or modeling of missing physics on the observed scales.

For our focus on reconstructing complex flows it is possible to distinguish
four possible different questions, see Fig. 1: (i) full-state restoration,
with the aim to fill missing gaps in the real space state of a complex flow,
(ii) inferring missing fields, which can be derived as the inverse problem
solution where a physical observable that cannot be accessed/measured directly
can be inferred by measuring other quantities to which it is coupled, (iii)
super-resolution, which can be seen as the equivalent of point (i) but when
the gap to fill is on the high-wavenumbers of the Fourier domain, (iv)
dynamical modeling, which consists of reconstructing dynamically the effects
of missing scales on the evolution of the resolved ones [65, 66, 67, 68]. The
issue of designing a ML-inspired sub-grid closure for modeling computational
fluid dynamics is a subject per se and has been recently reviewed in [69, 70].
Here, our focus lies on the first three categories of problems under the
assumption that the amount of missing information to fill in is very large,
which renders the problem ill-posed. This means that multiple solutions can
fit within the same reconstruction [38, 43]. Under this assumption, already
defining what the optimal solution is, it is a question that can have
different answers depending on the specific target. For instance, as discussed
in [71, 72], the optimal reconstruction providing the minimum mean squared
error (MSE) is different from optimal solutions in terms of other statistical
quantities. In this review, we target reconstructions that maximize the
correlations with the observed data while respecting the statistical features
of the ground truth solution. The large-gap assumption is required when
dealing with the reconstruction of complex flows. For instance, let us
consider the full-state reconstruction problem of ocean surface currents. Even
though satellites have allowed us to get, for the first time, a global picture
of the ocean [73, 74], from mesoscale eddies up to western boundary currents,
over time scales relevant to climatological studies (decades), observing the
full dynamics of the ocean remains a gigantic task [75, 76], and requires
filling gaps of spatial scales between hundred km up to less than a meter and
time-frequency gaps spanning weeks up to turbulent and wave scales (of
seconds), which cannot be neglected to explain turbulent stirring, mixing, and
all vertical motions.

On top of applications, there are fundamental questions associated with
reconstructing complex flows. What type and quantity of information are
required to perform different reconstructions is one open theoretical
question, which can be investigated via a reverse engineering approach:
different inputs can be passed to the same model to assess the impact on the
reconstruction quality. Here, we discuss some of the ML algorithms that are
transforming the conventional paradigms of data analysis and that have the
potential to facilitate breakthroughs in the field of fluid dynamics.
Following a chronological order, we start with an introduction of ‘Variational
Auto-Encoders’, (VAEs), ‘Generative Adversarial Networks’, (GANs), and
‘denoising Diffusion probabilistic Models’, (DMs). After we discuss how to
combine pure Data-Driven methods with the physical knowledge at hand and we
provide possible future directions in this discipline.

##  2 DATA-DRIVEN METHODS

A typical approach to repair missing data in gappy fields, before the rise of
ML, was based on proper orthogonal decomposition (POD). POD is used to reduce
data dimensionality by identifying the dominant patterns in a dataset and
representing them using a smaller set of orthogonal basis functions, (POD
modes, i.e. eigenvectors of the correlation matrix) [77, 78, 79]. The same
approach have been extensively used also for filling of missing points in
geophysical data sets where it takes the name of Empirical Orthogonal Function
[80]. Extension of such techniques as the Gappy POD (GPOD) [81] or the
Extended POD (EPOD) [82] were derived to repair missing data with minimal MSE
solutions, showing results outperforming Kriging interpolation [83]. However,
POD-based approaches are limited when dealing with complex multi-scale and
non-Gaussian statistics as is the case of turbulent flows. As shown in [84],
where they implemented EPOD to reconstruct the bulk velocity of wall-bounded
turbulence from wall measurements, and in [71] where they used EPOD and GPOD
to fill missing data on velocity planes extracted from 3d rotating turbulent
flows, POD methods can only reconstruct the large-scale, Gaussian features of
the ground truth data.

A significant advancement in this regard was brought by the ML generative
models [85, 86, 87] aiming to generate new data that resembles ‘statistically’
the training dataset. Their success can be attributed to two factors. Firstly,
their architecture relies on multi-layer Convolutional Neural Networks (CNN)
[88, 89], which inherently possess the ability to emphasize long-range
correlations in data. Secondly, they are trained with loss functions that not
only account for MSE accuracy but also for statistical differences between the
generated and ground truth data. Fig. 2 gives a schematic illustration of the
three main generative models that are commonly utilized in ML.

[width=0.45]Fig2.pdf

Figure 2: Schematic representation of the three ML algorithms developed to
generate data accordingly with the probability distribution function described
by a training dataset. (Top) Variational Auto-Encoders, based on a
probabilistic encoder $q_{\phi}(z|x)$ and decoder $p_{\theta}(x|z)$. (Middle)
Generative Adversarial Networks, based on a generator $g_{\theta}(z)$ and a
discriminator $d_{\theta}(x)$. (Bottom) Diffusion Models, aiming to model the
reverse transition probability of a Markov Chain, through a network
$p_{\theta}(x_{t-1}|x_{t})$.

VAEs have been the first type of neural network trained to give in output new
samples, not belonging to the training dataset, which satisfies the same
statistical properties. In the first row of Fig. 2, a simple diagram depicts
the workflow of the VAE model. VAEs, like their predecessors, Auto-Encoders,
are based on an encoder-decoder structure. However, unlike Auto-Encoders, the
aim of VAEs is not to perform a dimensionality reduction by projecting the
input data, $x$, into a low-dimensional latent space, $z$. Instead, VAEs
define a probabilistic decoder, $p_{\theta}(x|z)$, which maps any input from
the latent space, sampled from a simple distribution, $p(z)$, typically a
multivariate Gaussian, into a sample in the output space that satisfies the
(generally unknown) statistical distribution characterizing the training
dataset. The probabilistic encoder, $q_{\phi}(z|x)$, plays a crucial role in
VAEs by facilitating the sampling of the latent space, $z$, during training to
accelerate decoder convergence. The encoder’s primary objective is to model
the posterior probability of the decoder, denoted as $p_{\theta}(z|x)$, which
corresponds to the likelihood of obtaining a particular sample in the latent
space $z$ when generating a specific input from the dataset $x$. The presence
of the probabilistic encoder assists the discriminator in exploring a smaller
and more relevant sub-manifold of the latent space, resulting in faster and
more stable training. VAE models operate on the basic assumption of learning a
mapping between a simple and fixed distribution into the data probability
distribution. Training the encoder entails minimizing the Kullback-Leibler
Divergence (KLD) between the selected latent space distribution, $p(z)$, and
the encoder’s output distribution, $q_{\phi}(z|x)$. This operation can
generally be computed analytically and requires adding a few extra terms to
the decoder loss function. As previously mentioned, the probabilistic decoder
of the VAE is trained by maximizing the log-likelihood of the generated data,
$\log p_{\theta}(x)$, where;

$p_{\theta}(x)=\int p_{\theta}(x|z)p(z)dz.$

Directly computing this loss function is intractable. However, a lower bound
can be defined, using a variational inference formulation, and calculated
under some approximations. The approximations are based on the assumption that
the decoder’s errors are Gaussian. By making this assumption, the maximization
of the log-likelihood can be rewritten as a minimization of the MSE. While
this approximation may be reasonable in some contexts, it is certainly
unsuitable for considering turbulent flows, which are well-known for their
highly non-Gaussian extreme fluctuations. As shown in the context of turbulent
flows on a rotating frame [71], the minimization of MSE alone results in
generating solutions that match the training data only at the large, more
energetic scales, while over-damping the smaller scales. Therefore, rather
than as generative methods, VAEs are mostly considered in the context of
reduced-order modeling to perform a probabilistic projection on low-
dimensional latent space, z, as studied in the context of 3d homogeneous and
isotropic turbulent (HIT) flows [34] and more recently on a 2d flow of a
simplified urban environment [90].
GANs are proposed to improve VAEs by relaxing the Gaussian errors assumption,
and by improving the evaluation of statistical features in generated data in
the loss [91, 92, 93]. In general, the functional form of the probability
distribution that characterizes the training dataset is unknown. To overcome
this issue, a second network, the discriminator, $d_{\theta^{\prime}}(x)$, is
used to evaluate the statistical properties of training and generated
datasets. The discriminator provides a loss function that the GAN generative
part, $g_{\theta}(z)$, can optimize during training. The discriminator
functions as a classifier and is trained to assign a probability of an input
being generated or extracted from a true dataset. On the other hand, the
generator maps a sample from a latent space into a sample in the data space,
similar to a VAE decoder. Its objective is to generate increasingly realistic
samples that can fool the discriminator, from which comes the name
‘adversarial’, where, as in a zero-sum game, a gain for one network gives an
equivalent loss to the other [94, 95]. For a fixed generator the analytical
expression for the optimal discriminator can be derived by maximizing the
adversarial loss [91], and results in;

$d^{*}(x)=\frac{p_{true}(x)}{p_{true}(x)+p_{gen}(x)},$

where $p_{true}$ and $p_{gen}$ represent the statistical distributions of the
true and generated datasets. Similarly, the optimal generator, denoted as
$g^{*}(z)$, can be derived as the network that minimizes the Jensen-Shannon
Divergence (JSD), a symmetric formulation of the KLD, between the true and
generated distributions [91]. GANs, have exhibited unparalleled potential in
producing turbulent datasets that display a remarkable level of statistical
similarity to their original counterparts. Both the original and generated
data exhibit identical deviations from Gaussianity up to the evaluation of
high-order statistical observables in several setups, as in super-resolving to
a $64\times$ larger 2d turbulent flows behind cylinders [96], and of 3d HIT
flows [97, 36], as well as in filling large gaps in rotating turbulence [38]
and 3d channel flows [43].

[width=0.49]Fig3.pdf

Figure 3: Workflow of a typical Variational Auto-Encoder (panel a) and of a
typical Generative Adversarial Network (panel b) designed to generate samples
$x_{g}$ conditioned on some observations $\hat{x}$. The blue boxes represent
the functions optimized during the training, the yellow boxes report the loss
functions and their connection with the different parts of the network. The
red boxes indicate where the stochastic sampling is happening along the
network propagation, while the green and brown circles represent respectively
the input and the conditioning of the networks. (panel c) Visualization of
typical fields analyzed by the networks with the aim of transforming
incomplete data into corresponding complete data.

Fig. 3 showcases the workflows of VAEs and GANs focusing on the applications
of these models to fill gaps by exploiting their generative capacities also
when constrained to fit some observations. In the three panels (a)-(b)-(c),
the sample $\hat{x}$ represents the gappy data and serves as a condition to
the model, the ground truth data (known only in the training stage) is denoted
as $x_{d}$, the model reconstruction is called $x_{g}$. In the VAEs the
condition $\hat{x}$ is passed to both the encoder and the decoder. During
training the encoder projects $x_{d}$ and $\hat{x}$ into the latent space by
defining the variance and the mean of a Gaussian distribution from which a
sample $z$ is extracted. The loss function is the same as in the case of pure
generation. In testing setup, the reconstruction the sampling on $z$ is done
from a standardized multivariate Gaussian while the decoder on top of the $z$
sample analyzes also the condition $\hat{x}$ [98, 99, 100]. Panel (b) displays
the GAN reconstruction setup, which distinguishes itself from the
unconstrained model in that the generator employs an encoder-decoder
architecture to map $\hat{x}$ to an intermediate space $z$ prior to generating
the filling data instead of performing a random sampling on the latent space.
The discriminator operates as usual, but now the overall generation loss is a
linear combination of the MSE between the ground truth and the reconstruction
data, in addition to the adversarial loss provided by the discriminator
prediction [48, 71, 72]. GAN generates realistic samples also when constrained
to match some observations. However, in the reconstruction case having
statistically consistent data leads to a larger MSE with respect to the ground
truth solutions. Indeed a tiny shift in space between the reconstruction and
the true solution brings larger MSE if the fields are both highly fluctuating
[71]. The principal limitation of GANs arises from their adversarial nature,
resulting in highly unstable training and slow convergence. It can happen that
one of the two players is dominated by the other and converges into a failure
solution.

Diffusion Models, Fig. 2 bottom panel, are an alternative technique to
generate. DMs transform a simple distribution into a more complex
distribution, resembling the training data while avoiding the need to
introduce a surrogate loss function, as seen in VAEs, and without relying on
adversarial training, as in GANs.

[width=.49]Fig4.pdf

Figure 4: (Panel a) Typical workflow of a Diffusion Model designed and trained
to generate data respecting the statistical distribution of a training
dataset. Framework applied to reconstruct the full state (reconstructed
output) from partial observations (masked input) using a pre-trained
generative, unconditioned Diffusion Model starting from a random noise
($x_{T}$) (panel b).

The workflow of DMs is illustrated in Fig. 4, for both the generation (a) and
the reconstruction (b) setups. DMs use a Markov chain to gradually convert one
distribution (latent space) into another (dataset), following the idea
developed in non-equilibrium statistical physics [101]. To learn the
parameterized Markov chain, DMs are trained using variational inference to
produce data samples that match the original data after repeating a finite
number of steps. The learning involves estimating small perturbations to a
diffusion process, problem, which is more tractable than explicitly describing
the full distribution within a single jump as potentially done in the other
generative models. Furthermore, since a diffusion process, $q(x_{t}|x_{t-1})$,
exists for any smooth target distribution, this method can capture data
distributions of arbitrary form [101]. If the forward diffusion process is a
Markov chain that gradually introduces Gaussian noise to the data until the
signal is destroyed, the model subsequently learns how to reverse the
diffusion process and generate desired data samples starting from pure
Gaussian noise realizations. Unlike VAEs or GANs, diffusion models involve a
latent variable $z$ with dimensionality identical to that of the original data
$x$. In Fig. 4 panel (b) discusses the approach proposed in [102] to employ
pre-trained unconditional DMs to condition the generation process on filling
some partial observations. The approach involves moving forward the gappy data
through the Markov chain by iteratively adding noise to the observations,
while simultaneously progressing backward from the noise distribution using
the reverse chain learned by the DM. To incorporate the observed data in the
generation process, the strategy is to repeatedly merge the forward-propagated
noisy observations with the reverse-propagated noisy signal. This allows the
reverse process to propagate data information within the gap and generate a
correlated reconstruction. DMs have produced state-of-the-art results in image
generation, see the famous example of ‘DALL-E 2’ [103], demonstrating their
ease of definition and effectiveness in training [104, 105, 106, 102, 107].
Attention [108] is another feature often implemented inside DMs architecture,
which is potentially crucial for large gap-filling. Indeed, attention is meant
to enhance the role of some parts of the input data while diminishing others,
showing good results at handling long-range spatial relations [109]. However,
DMs and attention, have not yet been extensively applied in the generation and
reconstruction of complex gappy flow data, but they have only been used to
super-resolve smooth bi-dimensional Kolmogorov flows [110]. Therefore, the
investigation of DMs and ‘attention’ capacity to generate high-quality samples
of complex flows is an ongoing field of research.

##  3 PHYSICS-INFORMED METHODS

Leveraging the observed data and the equation of motion, Physics-Informed
techniques, exploit spatio-temporal correlations to derive accurate
reconstruction of incomplete data. Kalman filters, variational approaches, and
nudging are examples of advanced tools that have proven effective in enhancing
initial conditions for weather forecasting problems since before ML [111, 112,
113].
Nudging is a physics-informed way to control the evolution of a flow via the
continuous insertion of observed data and the addition of a penalty term,
which tries to keep the flow trajectory close to that of the empirical subset
[114]. Nudging has been recently applied to reconstruct high resolution HIT
flow from sparse measurements [115] and to estimate physical unknown
parameters from turbulent data [116]. While physics-agnostic ML approaches are
focused solely on finding patterns in data, there is growing interest in
incorporating physical knowledge into ML algorithms, particularly in the field
of fluid mechanics where the underlying physical laws are well understood
[117]. The first objective is to impose constraints on the ML solutions to
ensure that they adhere to the known physical properties, the second objective
is to streamline the training by integrating relevant information directly
into the network architecture or training setup. There exist three methods for
incorporating physics into ML algorithms; (i) observational, (ii) inductive,
or (iii) learning biases. Observational biases may be introduced by selecting
training data to ensure that a specific aspect of physics is not only present
but also emphasized, ie, extreme events can be shown during training more
often than the frequency at which they occur. Inductive biases embed physical
constraints into the network architecture, as for example the CNNs embed
invariance along the groups of symmetries possessed by typical patterns
observed in images. Finally, learning biases operate in a ‘soft’ way by adding
additional terms to the loss function that penalize non-physical solutions
[118], such as those that do not satisfy equations of motion, violate mass or
energy conservation, and so forth. Physics-informed data-driven tools have
just begun to be highlighted as particularly promising in areas as numerical
weather prediction [119, 120, 121, 26]. Improving data-driven and physics-
informed methods synergy will undoubtedly be the focus of research in the
upcoming years.

##  4 PERSPECTIVES

Although ML techniques have been already implemented as standard tools in
computer science, fluid dynamics presents challenges that differ from those
tackled in many applications of machine learning, such as image recognition
and advertising, as stated in [122]. Fluid flows necessitate precise and
quantitative evaluations of the multi-scale and multi-frequency physical
mechanisms that they must adhere to. On top of this, while idealized flow
setups offer large datasets of high complexity, and quality, in real-life
flows, one needs to deal with very sparse and noisy data. The misalignment
between the idealized cases studied in the literature, and real applications
opens non-trivial problems connected with the generalizability and the
uncertainty quantification (UQ) of the pre-trained models [123, 124, 125,
126]. To overcome those issues, it is highly desirable to have in the future,
more open-access databases, such as JHTDB (https://turbulence.pha.jhu.edu) and
Smart-Turb (https://smart-turb.roma2.infn.it), and well-defined open
challenges, such as (https://github.com/ocean-data-challenges), that can bring
different communities closer, and that can drive ML applications to go beyond
theoretical exercises towards the quantitative improvement required to provide
advancements in fluid mechanics. Today’s challenges are connected with the
need of a quantitative AI, driven by several critical factors such as
validation, benchmarks on generalization, and UQ of ML solutions. Another
crucial aspect is the problem dimensionalization, which involves understanding
the correlation between the network’s architecture, deepness, structure, and
size, and the physical parameters, as Reynolds, Rayleigh, and time-to-
solution, among others. As discussed, already defining an evaluation metric to
quantify the solution quality is an issue in fluid mechanics that needs to be
carefully designed. Answering these questions is necessary, and
interdisciplinary collaborations between applied scientists and AI
specialists, are unavoidable for establishing best practices outperforming
today’s data assimilation techniques. Scientists are skilled at asking the
right questions and they are asked to define targets that can be applied to
real-world problems. AI specialists have a unique ability to ‘open the box’ of
complicated algorithms and unlock the potential of vast amounts of data.

Despite these challenges, scientific communities have not been deterred from
exploring the interactions between ML and complex flows. On the contrary, the
potential impact is attracting increasing attention, resulting in a
convergence of challenges and new approaches that we believe are likely to
continue transforming both fluid mechanics and machine learning research.

###### Acknowledgements.

MB acknowledges Prof. Luca Biferale for useful discussion and financial
support from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (Grant Agreement No. 882340).

## References

  * [1] Yeh R. A. et al. in proc. of IEEE (CVPR) 2017 pp. 5485–5493.
  * [2] Ulyanov D. et al. in proc. of IEEE (CVPR) 2018 pp. 9446–9454.
  * [3] Bowman S. R. et al. arXiv:1508.053262015.
  * [4] Chowdhary K. et al. Fund. of Artif. Intell.2020603.
  * [5] Wolf T. et al. in proc. of EMNLP 2020 2020 pp. 38–45.
  * [6] Jumper J. et al. Nature5962021583.
  * [7] Biferale L. et al. Chaos292019103138.
  * [8] Buzzicotti M. et al. in proc. of AIxIA 2020 (Springer) 2021 pp. 223–234.
  * [9] Reddy G. et al. Nature5622018236.
  * [10] Alageshan J. K. et al. Phys. Rev. E1012020043110.
  * [11] Verma S. et al. Proc. Natl. Acad. Sci.11520185849.
  * [12] Calascibetta C. et al. Eur Phys J E4620231.
  * [13] Loisy A. et al. Proc. R. Soc. A478202220220118.
  * [14] Heinonen R. A. et al. arXiv:2207.042772022.
  * [15] Loisy A. et al. arXiv:2302.007062023.
  * [16] Bucci M. et al. Proc. R. Soc. A475201920190351.
  * [17] Park J. et al. J. Fluid Mech.9042020A24.
  * [18] Ren F. et al. Journal of Hydrodynamics322020247.
  * [19] Buzzicotti M. et al. Phys. Rev. Lett.1242020084504.
  * [20] Huang X. et al. Defence Technology182022229.
  * [21] Guastoni L. et al. arXiv:2301.098892023.
  * [22] Carrassi A. et al. Wiley Interdiscip. Rev. Clim. Change92018e535.
  * [23] Reichstein M. et al. Nature5662019195.
  * [24] Corbetta A. et al. Sci. Adv.72021eaba7281.
  * [25] Schultz M. G. et al. Philos. Trans. R. Soc. A379202120200097.
  * [26] Willard J. et al. ACM Comput. Surv.5520221.
  * [27] Buzzicotti M. et al. Eur Phys J E452022102.
  * [28] Bolton T. et al. J. Adv. Model Earth Syst.112019376.
  * [29] Park J. et al. Remote Sens.1120191366.
  * [30] Stock A. et al. Remote Sens.1220203313.
  * [31] Lou R. et al. Multimed. Syst.20211.
  * [32] Pietropolli G. et al. in proc. of 21st EPIA (Springer) 2022 pp. 452–463.
  * [33] Buongiorno Nardelli B. et al. Remote Sens.1420221159.
  * [34] Mohan A. T. et al. J. Turbul.212020484.
  * [35] Woodward M. J. et al. 2021\.
  * [36] Kim H. et al. J. Fluid Mech.9102021A29.
  * [37] Fukami K. et al. J. Fluid Mech.9092021A9.
  * [38] Buzzicotti M. et al. Phys. Rev. F62021050503.
  * [39] Clark Di Leoni P. et al. arXiv:2210.048492022.
  * [40] Clark Di Leoni P. et al. arXiv:2301.077692023.
  * [41] Yousif M. Z. et al. Sci. Rep.1320232529.
  * [42] Nakamura T. et al. Phys. Fluids332021025116.
  * [43] Güemes A. et al. Phys. Fluids332021075121.
  * [44] Fukami K. et al. J. Fluids Eng.1442022121501.
  * [45] Eivazi H. et al. arXiv:2203.154022022.
  * [46] Asch M. et al. Data assimilation: methods, algorithms, and applications Vol. 11 (SIAM) 2016.
  * [47] Little R. J. et al. Statistical analysis with missing data Vol. 793 (John Wiley & Sons) 2019.
  * [48] Pathak D. et al. in proc. of IEEE (CVPR) 2016 pp. 2536–2544.
  * [49] Zhu J.-Y. et al. Adv Neural Inf Proc Syst302017.
  * [50] Belthangady C. et al. Nat. Methods1620191215.
  * [51] Zavrtanik V. et al. Pattern Recognit.1122021107706.
  * [52] Wang G. et al. IEEE Trans Med Imaging3720181289.
  * [53] Maier A. et al. Zeitschrift für Medizinische Physik29201986.
  * [54] Wang G. et al. Nat. Mach. Intell22020737.
  * [55] Chai X. et al. Sci. Rep.1020203302.
  * [56] Wang B. et al. Geophysics842019V11.
  * [57] Caldeira J. et al. Astronomy and Computing282019100307.
  * [58] Moriwaki K. et al. Mon. Not. R. Astron. Soc.: Lett.4962020L54.
  * [59] Sammartino M. et al. Remote Sens.1220204123.
  * [60] Di J. et al. Front. Mar. Sci.82021670683.
  * [61] Brajard J. et al. Philos. Trans. R. Soc. A379202120200086.
  * [62] Shrira V. I. et al. J. Fluid Mech.8872020A24.
  * [63] Fablet R. et al. ISPRS J. Photogramm.32021295.
  * [64] Dong C. et al. OLAR20222022.
  * [65] Meneveau C. et al. ARFM3220001.
  * [66] Buzzicotti M. et al. J. Turbul.192018167.
  * [67] Biferale L. et al. Phys. Rev. Lett.1232019014503.
  * [68] Buzzicotti M. et al. Phys. Rev. E1042021015302.
  * [69] Duraisamy K. et al. ARFM512019357.
  * [70] Vinuesa R. et al. Nat. Comput. Sci.22022358.
  * [71] Li T. et al. arXiv:2210.119212022.
  * [72] Li T. et al. arXiv:2301.075412023.
  * [73] Storer B. A. et al. Nat. Commun.1320225314.
  * [74] Buzzicotti M. et al. arXiv:2106.041572021.
  * [75] Pujol M.-I. et al. Ocean Science1220161067.
  * [76] Ballarotta M. et al. Ocean Science1520191091.
  * [77] Sirovich L. et al. Josa a41987519.
  * [78] Fukunaga K. Introduction to statistical pattern recognition (Elsevier) 2013.
  * [79] Hayase T. Fluid Dyn. Res.472015051201.
  * [80] Kondrashov D. et al. NPG132006151.
  * [81] Everson R. et al. JOSA A1219951657.
  * [82] Maurel S. et al. Flow Turbul Combust672001125.
  * [83] Gunes H. et al. J. Comput. Phys.2122006358.
  * [84] Guastoni L. et al. J. Fluid Mech.9282021A27.
  * [85] Hong Y. et al. ACM Comput. Surv.5220191.
  * [86] Bond-Taylor S. et al. IEEE Trans. Pattern Anal. Mach. Intell.2021.
  * [87] Gui J. et al. IEEE Trans Knowl Data Eng2021.
  * [88] O’Shea K. et al. arXiv:1511.084582015.
  * [89] Li Z. et al. IEEE Trans Neural Netw Learn2021.
  * [90] Eivazi H. et al. Expert Syst. Appl.2022022117038.
  * [91] Goodfellow I. et al. Adv Neural Inf Proc Syst272014.
  * [92] Wang K. et al. IEEE/CAA J. Autom. Sin.42017588.
  * [93] Heusel M. et al. Adv Neural Inf Proc Syst302017.
  * [94] Hofbauer et al. Evolutionary games and population dynamics (Cambridge university press) 1998.
  * [95] Borra F. et al. Phys. Rev. F72022023103.
  * [96] Deng Z. et al. Phys. Fluids312019125111.
  * [97] Subramaniam A. et al. arXiv:2003.019072020.
  * [98] Kingma D. P. et al. arXiv:1312.61142013.
  * [99] Salimans T. et al. in proc. of ICML (PMLR) 2015 pp. 1218–1226.
  * [100] Doersch C. arXiv:1606.059082016.
  * [101] Sohl-Dickstein J. et al. in proc. of ICML (PMLR) 2015 pp. 2256–2265.
  * [102] Lugmayr A. et al. in proc. of IEEE (CVPR 2022 pp. 11461–11471.
  * [103] Saharia C. et al. arXiv:2205.114872022.
  * [104] Ho J. et al. Adv Neural Inf Proc Syst3320206840.
  * [105] Nichol A. Q. et al. in proc. of ICML (PMLR) 2021 pp. 8162–8171.
  * [106] Dhariwal P. et al. Adv Neural Inf Proc Syst3420218780.
  * [107] Rombach R. et al. in proc. of IEEE (CVPR) 2022 pp. 10684–10695.
  * [108] Vaswani A. et al. Adv Neur Inf Proc Syst302017.
  * [109] Wang X. et al. in proc. of IEEE (CVPR) 2018 pp. 7794–7803.
  * [110] Shu D. et al. J. Comput. Phys.4782023111972.
  * [111] Kalnay E. Atmospheric modeling, data assimilation and predictability (Cambridge university press) 2003.
  * [112] Carrassi A. et al. Wiley Interdiscip. Rev. Clim. Change92018e535.
  * [113] Lakshmivarahan S. et al. Data Assimilation for Atmospheric, Oceanic and Hydrologic Applications (Vol. II)201327.
  * [114] Hoke J. E. et al. Mon Weather Rev10419761551.
  * [115] Clark Di Leoni P. et al. Phys. Rev. X102020011023.
  * [116] Buzzicotti M. et al. Phys. Fluids322020125116.
  * [117] Karniadakis G. E. et al. Nat. Rev. Phys.32021422.
  * [118] Raissi M. et al. J. Comput. Phys.3782019686.
  * [119] Zhao W. L. et al. Geophys. Res. Lett.46201914496.
  * [120] Alber M. et al. NPJ digital medicine22019115.
  * [121] Kashinath K. et al. Philos. Trans. R. Soc. A379202120200093.
  * [122] Brunton S. L. et al. ARFM522020477.
  * [123] Bucci M. et al. Eur Phys J E46202312.
  * [124] Abdar M. et al. Inf Fusion762021243.
  * [125] Hüllermeier E. et al. Mach. Learn.1102021457.
  * [126] Barth A. et al. Geosci. Model Dev.1320201609.