# Choosing restart strategy at partial knowledge of process statistics

Ilia Nikitin and Sergey Belan<EMAIL_ADDRESS>Landau Institute for
Theoretical Physics, Russian Academy of Sciences, 1-A Akademika Semenova av.,
142432 Chernogolovka, Russia  National Research University Higher School of
Economics, Faculty of Physics, Myasnitskaya 20, 101000 Moscow, Russia

###### Abstract

Optimization of a random processes by restart is a subject of active
theoretical research in statistical physics and has long found practical
application in computer science. Meanwhile, one of the key issues remains
largely unsolved: when should we restart a process whose detailed statistics
are unknown to ensure that our intervention will improve performance?
Addressing this query here we propose several constructive criteria for the
effectiveness of various protocols of non-instantaneous restart in the mean
completion time problem and in the success probability problem. Being
expressed in terms of a small number of easily estimated statistical
characteristics of the original process, these criteria allow informed restart
decision based on partial information.

##  I Introduction

Restart as a method of accelerating randomized tasks was first proposed in the
early 90s in computer science. Namely, the authors of Refs. [1, 2] showed that
applying a restart to a probabilistic algorithm whose completion time
represents highly fluctuating random variable leads to smaller tail
probabilities and to smaller expected completion time. Beyond computer
science, optimization via restart is the subject of active research by the
statistical physics community. The starting point for these studies was the
work of Evans and Majumdar [3], who found that stochastic (Poisson) restart
reduces the mean first-passage time of Brownian motion. Also, this area of
research received an additional impetus for development due to the works [4,
5, 6] devoted to the kinetics of enzymatic reactions, where the restart
corresponds to dissociation of the intermediate enzyme-substrate complex.
Theoretical analysis presented in this studies demonstrated that an increase
in the dissociation rate constant could potentially speed up enzymatic
turnover.

Thus, essentially the same mathematical model arises in different research
fields. Regardless of the specific context, one of the critical tasks is the
following: how to find a restart strategy that is guaranteed to reduce the
expected completion time of the stochastic process of interest? The general
renewal formalism developed by Pal and Reuveni [7] allows to predict whether
the implementation of a particular restart protocol will be effective for a
given stochastic process. Moreover, as proved in [2, 8, 7], a strictly regular
(periodic) strategy, implying that the random process is restarted every
$\tau_{\ast}$ units of time, is universally optimal. The value of the optimal
period $\tau_{\ast}$ is problem-specific and can be determined once we know
the probability density of the random completion time of the original process.

In practice, however, the statistics of the optimized process can be poorly
specified or even completely unknown [2, 9, 4, 10, 8, 11, 12]. Trying to
address this issue, the authors of [2] have developed a restart protocol,
nowadays known as Luby strategy, which has the following remarkable property:
regardless of the statistical details of the original process, the average
completion time of this process subject to the Luby strategy exceeds the
expectation of completion time provided by the optimal periodic protocol by no
more than a logarithmic factor.

While ingenious and elegant, Luby’s strategy suffers from two serious
drawbacks. First, it only applies to processes with discrete completion times.
In the case of continuous time, as was recently shown by Lorentz [8], such a
universal strategy simply does not exist. Secondly, and even more importantly,
even for discrete-time processes, applying the Luby strategy, we can only be
sure that the resulting mean completion time will not be too bad compared to
the optimal value achieved by the best periodic strategy. In other words,
there is no guarantee that Luby strategy will not degrade performance as
compared to the restart-free case [8].

Thus, two extremes are well understood: if the complete statistics of the
process duration is available, then it is straightforward to find the optimal
restart strategy, while in the absence of information about the process
statistical properties it would be better do not use restart at all, since
this is the only way to avoid unintentional decrease in performance. In the
recent paper [13], which addresses an intermediate scenario of partially known
statistics, Eliazar and Reuveni formulated the constructive criteria for the
effectiveness of restarts, expressed through simple statistical
characteristics of a randomized task. Unlike previously known existence
results, constructive criteria serve not just as indicators of the restart
effectiveness, but also offer a strategy that is guaranteed to reduce the
average completion time.

The results presented in [13], however, are obtained under the assumption of
instantaneous restart events, while in real-life settings a restart is
accompanied by some time delays. Say, in the context of single molecule enzyme
kinetics, some time is required to enzyme which unbinds from substrate to find
a new one in the surrounding solution [4, 6, 14]. Similarly, the restart of a
computer program typically involves a time overhead. Also, models with non-
instantaneous restarts provide more realistic pictures of colloidal particle
diffusion with resetting [15]. To the best of our knowledge, the existing
literature lacks constructive criteria of restart efficiency for models with
non-momentary restarts. In addition, the criteria proposed in [13] refer only
to the case of a periodic restart. The constructive criteria, if any, for
other types of restart strategies remains unknown.

Finally, let us note that the potential of restart is not limited to
optimization of the mean completion time. In particular, implementation of
restart can also improve the probability of getting a desired outcome when a
processes has several alternative completion scenarios [16]. constructive
criteria for the problem of optimizing the splitting probabilities have not
yet been formulated as far as we know.

In this paper, we fill aforementioned gaps by constructing a set of
constructive efficiency criteria for regular and stochastic non-instantaneous
restarts in both the mean completion time problem, and in the success
probability problem.

##  II Optimization of the mean completion time

Consider a stochastic process whose random duration time $T$ has a probability
density $P(T)$. The restart protocol ${\cal R}$ is characterized by a
(possibly infinite) sequence of of inter-restarts time intervals
$\tau_{1},\tau_{2},\dots$. If the process is completed prior to the first
restart event, the story ends there. Otherwise, the current attempt is
aborted, and the process starts from scratch. Similarly, next attempt may
either complete prior to the second restart or not, with the same rules. This
procedure repeats until the process finally reaches completion. We will also
assume that initialization of the process and each restart are accompanied by
some random time delay $t$ which is independent of $T$.

In the absence of restart, the random waiting time for the process completion
is given by the sum $T+t$. The restart protocol is considered effective if
$\langle T_{{\cal R}}\rangle<\langle T\rangle+\langle t\rangle$, where
$T_{{\cal R}}$ is a random waiting time of the process completion in the
presence of the protocol ${\cal R}$, and angular brackets denote averaging
over the statistics of the original process and possibly over the statistics
of the inter-restarts intervals (in the case of a stochastic protocol). It is
convenient to define dimensionless effectiveness of restart as

$\eta_{{\cal R}}=1-\frac{\langle T_{{\cal R}}\rangle}{\langle T\rangle+\langle
t\rangle}.$ (1)

Clearly, the effective protocols obey $0<\eta_{{\cal R}}\leq 1$.

In the simplest case of a strictly regular schedule, implying that the restart
events are equally spaced in time, i.e., $\tau_{k}=\tau$ for all $k=1,2,...$,
the expected completion time can be expressed as

$\langle T_{\tau}\rangle=\frac{\langle
T\rangle+\tau-\langle|T-\tau|\rangle+2\langle t\rangle}{2Pr[T\leq\tau]},$ (2)

where $\langle|T-\tau|\rangle$ is the mean absolute deviation (MAD) of the
random variable $T$ from the value of $\tau$. Equation (2) was first derived
in Ref. [13] in particular case of zero time penalty $t=0$.

Another important scenario is the Poisson restart, where inter-restarts
intervals are mutually independent and identically distributed with
exponential probability density $\rho(\tau)=re^{-r\tau}$. Here $r$ represents
the restart rate. The average completion time in the presence of a Poisson
restart is given by (see [6])

$\langle T_{r}\rangle=\frac{1-\tilde{P}(r)+r\langle t\rangle}{r\tilde{P}(r)},$
(3)

where $\tilde{P}(r)=\int_{0}^{\infty}dTP(T)e^{-rT}$ denotes the Laplace
transform of the probability density function $P(T)$.

In addition, we will consider the case of a gamma-protocol for which the
random intervals between restarts are independently sampled from the Gamma
distribution $\rho(\tau)=\frac{\beta^{k}}{\Gamma(k)}\tau^{k-1}e^{-\beta\tau}$
with rate parameter $\beta$ and shape parameter $k$. The expected completion
time of a process under gamma-restart with $k=2$ is given by

$\langle T_{\beta}\rangle=\frac{\beta\langle
t\rangle+2-2\tilde{P}(\beta)+\beta\partial_{\beta}\tilde{P}(\beta)}{\beta\tilde{P}(\beta)-\beta^{2}\partial_{\beta}\tilde{P}(\beta)}.$
(4)

Once full statistics of the original process encoded into the probability
density $P(T)$ is known, one can use Eqs. (2)-(4) to determine the values (if
any) of the control parameter (period $\tau$ or rates $r$, $\beta$) for which
the corresponding strategy is advantageous. Moreover, the most efficient
strategy is always periodic, and the optimal period can be found by minimizing
the right side of Eq. (2) with respect to $\tau$. Our goal is to formulate
constructive criteria of restart efficiency, allowing to choose guaranteed
beneficial restart protocol without knowledge of the full process statistics.
Several such criteria were proposed in [13] for the particular case of the
periodic restart with zero penalty $t=0$.

Let us outline the idea underlying our derivation of the desired criteria.
First of all, using various probabilistic inequalities, we obtain an upper
bound for the mean completion time $\langle T_{\tau}\rangle\leq{\cal T}$ of
the process under restart protocol ${\cal R}$, where the time scale ${\cal T}$
is expressed through the mean restart period ($\tau$, $r$ or $\beta$ depending
on the protocol) and some simple statistical characteristics of the original
process (e.g., statistical moments, median value, MADs, etc.). Then the
solution of the inequality ${\cal T}\leq\langle T\rangle+\langle t\rangle$
with respect to the mean period defines a set (possibly empty) of efficient
values for period. Further, by minimizing ${\cal T}$ on this set, one can find
the the period which provides the maximum guaranteed efficiency. Next, we
demonstrate concrete implementations of this simple idea.

###  II.1 Periodic restart

For any random variable $T$ one has
$\langle|T-\tau|\rangle\geq\langle|T-m|\rangle$, where $m$ is the median value
of $T$. Moreover, the equality is achieved for $\tau=m$. So, using Eq. (2) we
get the following estimate

$\langle T_{\tau}\rangle\leq\frac{\langle
T\rangle+\tau-\langle|T-m|\rangle+2\langle t\rangle}{2Pr[T\leq\tau]}.$ (5)

It follows from Eq. (5) that if the condition

$\displaystyle m+\langle t\rangle<\langle|T-m|\rangle,$ (6)

is satisfied, then the inequality $\langle T_{\tau}\rangle\leq\langle
T\rangle+\tau-\langle|T-m|\rangle+2\langle t\rangle<\langle T\rangle+\langle
t\rangle$ holds for any period belonging to the interval

$\displaystyle m\leq\tau<\langle|T-m|\rangle-\langle t\rangle.$ (7)

Moreover, the choice $\tau_{0}=m$ is optimal in the sense that regular restart
with period $\tau_{0}$ provides the highest guaranteed efficiency which is
given by

$\eta_{1}=\frac{\langle|T-m|\rangle-m-\langle t\rangle}{\langle
T\rangle+\langle t\rangle}.$ (8)

The described criteria generalizes result presented [13] to the case of a non-
zero duration of restart events.

Further, as shown in [17] for the articular case $t=0$, the inequality
$2m<\langle T\rangle$ represents a sufficient condition for the existence of
an effective periodic protocol. Here we turn this existence result into a
constructive criterion that holds in the presence of a restart penalty. By
virtue of Jensen’s inequality, one has $\langle|T-\tau|\rangle\geq\langle
T\rangle-\tau$, and, therefore, Eq. (2) allows to write the following estimate

$\langle T_{\tau}\rangle\leq\frac{\tau+\langle t\rangle}{Pr[T\leq\tau]}.$ (9)

From Eq. (9) we see that if the condition

$\displaystyle m<\frac{1}{2}\langle T\rangle-\frac{1}{2}\langle t\rangle$ (10)

is met, then regular restart with the period belonging to the interval

$\displaystyle m\leq\tau<\frac{1}{2}\langle T\rangle-\frac{1}{2}\langle
t\rangle,$ (11)

reduces the average completion time since in this case one get $\langle
T_{\tau}\rangle\leq 2\tau+2\langle t\rangle<\langle T\rangle+\langle
t\rangle$. The guaranteed efficiency is maximal at $\tau_{0}=m$ and is
estimated as

$\eta_{2}\geq 1-\frac{2(m+\langle t\rangle)}{\langle T\rangle+\langle
t\rangle}.$ (12)

###  II.2 Poisson restart

Periodic strategy is important due to its optimal property, which has already
been discussed above. Namelly, if you found a value $\tau_{\ast}\geq 0$
(probably $\tau_{\ast}=+\infty$) such that $\langle
T_{\tau_{\ast}}\rangle\leq\langle T_{\tau}\rangle$ for any $\tau\geq 0$, then
$\langle T_{\tau_{\ast}}\rangle\leq\langle T_{\cal R}\rangle$ for all ${\cal
R}$. However, as previous studies have shown [6], a periodic protocol with a
non-optimal period $\tau\neq\tau_{\ast}$ may be inferior to other restart
strategies. Since the optimal period $\tau_{\ast}$ of a regular restart does
not have to be equal to the median completion time of the initial process $m$,
the periodic strategies constructed above are generally not optimal. In
addition, the conditions of their applicability (see Eqs. (6) and (10)) are
not necessary for the existence of an effective protocol. In other words,
violation of the conditions $m+\langle t\rangle<\langle|T-m|\rangle$ and
$m<\frac{1}{2}\langle T\rangle-\frac{1}{2}\langle t\rangle$ for a given
stochastic process does not mean that an effective restart protocol can not be
constructed.

Given above arguments, it is interesting to develop efficient policies of non-
periodic restart. Particularly attractive in this respect is the Poisson
strategy, which has been widely studied before, see e.g. [3, 4, 5, 6, 18, 19].
A simple sufficient condition for the efficiency of the Poisson restart [18]
reads

$\displaystyle\langle T^{2}\rangle>2\langle T\rangle(\langle T\rangle+\langle
t\rangle).$ (13)

Note, however, that the latter inequality represent existence result: it
serves as an indicator of the existence of an effective Poisson strategy
without presenting it. Moreover, the logic underlying derivation of sufficient
condition determined by Eq. (13) suggests that knowing the first two
statistical moments of the random completion time is not enough to choose at
effective restart rate. Namely, the pair $\langle T\rangle$ and $\langle
T^{2}\rangle$ determines only the slope of $\langle T_{r}\rangle$ in its
dependence on $r$ at the point $r=0$, saying nothing about its behavior for
non-zero values of $r$.

A constructive condition for the effectiveness of the Poisson restart can be
formulated if we add information about the third-order moment. Based on the
knowledge of $\langle T\rangle$, $\langle T^{2}\rangle$ and $\langle
T^{3}\rangle$, one can estimate the the Laplace transform of $P(T)$ as [20]

$\tilde{P}(r)\geq 1-r\langle T\rangle+\frac{r^{2}\langle
T^{2}\rangle^{2}}{r\langle T^{3}\rangle+2\langle T^{2}\rangle}.$ (14)

Next, assuming that the expression on the right side of (14) is positive, from
(3) and (14) we get the following estimate

$\langle T_{r}\rangle\leq\frac{r(\langle t\rangle+\langle T\rangle)(r\langle
T^{3}\rangle+2\langle T^{2}\rangle)-r{\langle T^{2}\rangle}^{2}}{(1-r\langle
T\rangle)(r\langle T^{3}\rangle+2\langle T^{2}\rangle)+r^{2}{\langle
T^{2}\rangle}^{2}}.$ (15)

Therefore, if $r$ satisfies the set of inequalities

$\left\\{\begin{array}[]{ll}\frac{r(\langle t\rangle+\langle
T\rangle)(r\langle T^{3}\rangle+2\langle T^{2}\rangle)-r{\langle
T^{2}\rangle}^{2}}{(1-r\langle T\rangle)(r\langle T^{3}\rangle+2\langle
T^{2}\rangle)+r^{2}{\langle T^{2}\rangle}^{2}}<\langle t\rangle+\langle
T\rangle,\\\ \\\ 1-r\langle T\rangle+\frac{r^{2}{\langle
T^{2}\rangle}^{2}}{r\langle T^{3}\rangle+2\langle T^{2}\rangle}>0,\\\ \\\
r>0.\end{array}\right.$ (16)

then Poisson restart at rate $r$ reduces the mean completion time. Solving
this system under the assumption that a sufficient condition defined by (13)
is met, we find an interval of effective rates

$\displaystyle 0<r<\frac{\langle T^{2}\rangle(\langle T^{2}\rangle-2\langle
T\rangle(\langle T\rangle+\langle t\rangle))}{(\langle T\rangle+\langle
t\rangle)(\langle T\rangle\langle T^{3}\rangle-\langle T^{2}\rangle^{2})}.$
(17)

Further, within the interval given by (17), the expression on the right side
of the inequality (15) attains its minimum value at the point $r^{m}_{opt}$
given by Eq. (55) in Appendix. As can be found from (17), (14) and (15), the
resulting efficiency is given by (56), see Appendix.

In the limit of negligible restart duration $t=0$, we obtain fairly compact
expressions for the optimal point

$r_{0}=\frac{\sqrt{2}\langle T^{2}\rangle^{3/2}-2\langle T\rangle\langle
T^{2}\rangle}{\langle T\rangle\langle T^{3}\rangle-\langle T^{2}\rangle^{2}}.$
(18)

while the corresponding estimate for the dimensionless effectiveness reads

$\displaystyle\eta_{3}\geq\frac{2\langle T^{2}\rangle\langle
T\rangle^{2}+\langle T^{2}\rangle^{2}-2\sqrt{2}\langle T\rangle\sqrt{\langle
T^{2}\rangle^{3}}}{\langle T\rangle\left(2\langle T\rangle\langle
T^{2}\rangle+\langle T^{3}\rangle-2\sqrt{2}\sqrt{\langle
T^{2}\rangle^{3}}\right)}.$ (19)

Note that the proposed method of constructing an effective Poisson strategy is
one of many possible. Alternatively, the Laplace transform of the probability
density $P(T)$ can be estimated as [20]

$\displaystyle\tilde{P}(r)\geq\sum_{k=0}^{2l-1}(-1)^{k}\frac{r^{k}\langle
T^{k}\rangle}{k!},$ (20)

where $l=1,2,...$. Let us evaluate the term $\tilde{P}(r)$ in the numerator of
right-hand side of the formula (3) using (20) with $l=2$, i.e.
$\tilde{P}(r)\geq 1-r\langle T\rangle+\frac{r^{2}}{2}\langle
T^{2}\rangle-\frac{r^{3}}{6}\langle T^{3}\rangle$. Next, to estimate the
Laplace transform $\tilde{P}(r)$ entering the denominator in the same
expression we use Eq. (20) with $l=1$: $\tilde{P}(r)\geq 1-r\langle T\rangle$.
Then, exploiting these estimates and assuming that $r<1/\langle T\rangle$ we
get from Eq. (3)

$\langle T_{r}\rangle\leq\frac{6\langle t\rangle+6\langle T\rangle-3r\langle
T^{2}\rangle+r^{2}\langle T^{3}\rangle}{6-6r\langle T\rangle},$ (21)

and, thus, the interval of effective rates is determined by the following set
of inequalities

$\left\\{\begin{array}[]{ll}\frac{6\langle t\rangle+6\langle
T\rangle-3r\langle T^{2}\rangle+r^{2}\langle T^{3}\rangle}{6-6r\langle
T\rangle}<\langle t\rangle+\langle T\rangle,\\\ \\\ r<\frac{1}{\langle
T\rangle},\\\ \\\ r>0.\end{array}\right.$ (22)

Assuming that the condition (13) is fulfilled, we readily find a solution

$\displaystyle 0<r<\frac{3(\langle T^{2}\rangle-2\langle T\rangle(\langle
T\rangle+\langle t\rangle))}{\langle T^{3}\rangle},$ (23)

which obviously differs from that given by Eq. (17) since its derivation is
based on different estimate on $\tilde{P}(r)$. Rate $r_{opt}^{c}$ determined
by Eq. (57) in Appendix minimizes the right side of the inequality (21) on the
interval (23), thus providing the highest guaranteed efficiency whose estimate
from below is given by Eq. (58).

Finally, using (14) to estimate Laplace transform in the numerator of the
right side of the formula (3) and the following from (14) the weaker
inequality $\tilde{P}(r)\geq 1-r\langle T\rangle$ to estimate the denominator,
we get a third way to build a win-win Poisson protocol. Assuming $r<1/\langle
T\rangle$, for the average completion time with this approach, we have

$\langle T_{r}\rangle<\frac{2(\langle t\rangle+\langle T\rangle)\langle
T^{2}\rangle+r\left[(\langle t\rangle+\langle T\rangle)\langle
T^{3}\rangle-\langle T^{2}\rangle^{2}\right]}{(1-r\langle
T\rangle)\left(r\langle T^{3}\rangle+2\langle T^{2}\rangle\right)}$ (24)

A set of guaranteed effective rates is determined by the solution of the
system of inequalities

$\left\\{\begin{array}[]{ll}\frac{2(\langle t\rangle+\langle T\rangle)\langle
T^{2}\rangle+r\left[(\langle t\rangle+\langle T\rangle)\langle
T^{3}\rangle-\langle T^{2}\rangle^{2}\right]}{(1-r\langle
T\rangle)\left(r\langle T^{3}\rangle+2\langle T^{2}\rangle\right)}<\langle
t\rangle+\langle T\rangle,\\\ \\\ r<\frac{1}{\langle T\rangle},\\\ \\\
r>0,\end{array}\right.$ (25)

solving which we get

$\displaystyle 0<r<\frac{\langle T^{2}\rangle\left[\langle
T^{2}\rangle-2\langle T\rangle(\langle t\rangle+\langle
T\rangle)\right]}{(\langle t\rangle+\langle T\rangle)\langle T\rangle\langle
T^{3}\rangle}.$ (26)

The optimal rate and the corresponding efficiency are determined by Eqs. (59)
and (60) in Appendix.

More generally, using the inequality (20) for $l>2$, as well as combining it
with (14), it is possible, in principle, to obtain an unlimited number of
other guaranteed effective Poisson strategies. Here we have given only the
simplest protocols that require knowledge of a minimum number of statistical
moments for their application.

###  II.3 Gamma strategy

Let us now analyze the stochastic gamma-protocol. From (4), we find that if
the condition

$\displaystyle\langle T^{3}\rangle\geq 3(\langle T\rangle+\langle
t\rangle)\langle T^{2}\rangle,$ (27)

is met then $\partial_{\beta}\langle T_{\beta}\rangle<0$ at $\beta=0$. So, the
inequality (27) represents a sufficient condition for the existence of an
effective gamma-strategy. However, the knowledge of the first three moments,
$\langle T\rangle$, $\langle T^{2}\rangle$ and $\langle T^{3}\rangle$, does
not allow us to choose a value of the parameter $\beta$ that reduces the mean
completion time for sure. A desired constructive criterion for the
effectiveness of the gamma-strategy can be formulated by adding information
about the fourth-order statistical moment $\langle T^{4}\rangle$.

To work out an upper estimate for the average completion time $\langle
T_{\beta}\rangle$ given by (4), it is useful to note that the derivative of
the Laplace transform $\partial_{\beta}\tilde{P}(\beta)$ can be represented as

$\displaystyle\partial_{\beta}\tilde{P}(\beta)=\partial_{\beta}\int_{0}^{\infty}dTP(T)e^{-\beta
T}=$ (28) $\displaystyle=-\int_{0}^{\infty}dTP(T)Te^{-\beta T}=-\langle
T\rangle\tilde{Q}(\beta).$ (29)

where $Q(T)=\frac{T}{\langle T\rangle}P(T)$. Being non-negative and normalized
by unity, $Q(T)$ can be treated as a probability density of some random
variable, and, therefore, its Laplace transform $\tilde{Q}(r)$ can be
evaluated from below using the inequality 20

$\displaystyle\tilde{Q}(\beta)\geq\sum_{k=0}^{2l-1}(-1)^{k}\frac{\beta^{k}\langle
T^{k}\rangle_{Q}}{k!},$ (30)

where $\langle
T^{n}\rangle_{Q}\equiv\int_{0}^{\infty}T^{n}Q(T)dT=\frac{\langle
T^{n+1}\rangle}{\langle T\rangle}$. From (28) and (30) we then find

$\partial_{\beta}\tilde{P}(\beta)\leq\sum_{k=0}^{2l-1}\frac{(-1)^{k+1}}{k!}\beta^{k}\langle
T^{k+1}\rangle$ (31)

Now let us estimate the term $\tilde{P}(\beta)$ in the numerator of Eq. (4)
via the inequality (20) at $l=2$. Also let us use (20) at $l=2$ to estimate
the term $\tilde{P}(\beta)$ in the denominator. Finally, the term
$\partial_{\beta}\tilde{P}(\beta)=-\langle T\rangle\tilde{Q}(\beta)$ can be
evaluated using (30) with $l=1$. Combining all these estimates we obtain

$\displaystyle\langle T_{\beta}\rangle\leq\frac{6\langle t\rangle+6\langle
T\rangle-\beta^{2}\langle T^{3}\rangle+{\beta^{3}}\langle
T^{4}\rangle}{6-3{\beta^{2}}\langle T^{2}\rangle-{\beta^{3}}\langle
T^{3}\rangle},$ (32)

which implies that $1-\frac{\beta^{2}}{2}\langle
T^{2}\rangle-\frac{\beta^{3}}{6}\langle T^{3}\rangle>0$. Then the effective
rates $\beta$ can be found from the requirement that the right-hand side of
Eq. (32) is less than mean completion time in the absence of restart $\langle
T\rangle+\langle t\rangle$. This yields the following interval

$\displaystyle 0<\beta<\frac{\langle T^{3}\rangle-3(\langle T\rangle+\langle
t\rangle)\langle T^{2}\rangle}{(\langle T\rangle+\langle t\rangle)\langle
T^{3}\rangle+\langle T^{4}\rangle}.$ (33)

As expected, this interval (33) is not empty if the existence conditions (27)
is met. The best rate providing maximum guaranteed efficiency can be found by
solving algebraic equation of the third degree.

Following the same logic, one can derive the effective gamma-strategy with an
arbitrary natural shape parameter $k$ of the probability density of inter-
restarts intervals
$\rho(\tau)=\frac{\beta^{k}}{\Gamma(k)}\tau^{k-1}e^{-\beta\tau}$. Note,
however, that the larger $k$ is, the greater the number of statistical moments
is required to determine the range of effective rates $\beta$.

Protocol | Applicability condition | Range for effective period/rate | Recommended period/rate | Efficiency
---|---|---|---|---
Regular1 | $m+\langle t\rangle<\langle|T-m|\rangle$ | $m\leq\tau<\langle|T-m|\rangle-\langle t\rangle$ | $\tau_{0}=m$ | $\eta_{1}=\frac{\langle|T-m|\rangle-m-\langle t\rangle}{\langle T\rangle+\langle t\rangle}$
Regular2 | $m<\frac{1}{2}\langle T\rangle-\frac{1}{2}\langle t\rangle$ | $m\leq\tau<\frac{1}{2}\langle T\rangle-\frac{1}{2}\langle t\rangle$ | $\tau_{0}=m$ | $\eta_{2}>1-\frac{2(m+\langle t\rangle)}{\langle T\rangle+\langle t\rangle}$
Poisson1 | $\langle T^{2}\rangle\geq 2\langle T\rangle(\langle T\rangle+\langle t\rangle)$ | $0<r<\frac{\langle T^{2}\rangle(\langle T^{2}\rangle-2\langle T\rangle(\langle T\rangle+\langle t\rangle))}{(\langle T\rangle+\langle t\rangle)(\langle T\rangle\langle T^{3}\rangle-\langle T^{2}\rangle^{2})}$ | see Eq. (55) | see Eq. (56)
Poisson2 | $\langle T^{2}\rangle\geq 2\langle T\rangle(\langle T\rangle+\langle t\rangle)$ | $0<r<\frac{3(\langle T^{2}\rangle-2\langle T\rangle(\langle T\rangle+\langle t\rangle))}{\langle T^{3}\rangle}$ | see Eq. (57) | see Eq. (58)
Poisson3 | $\langle T^{2}\rangle\geq 2\langle T\rangle(\langle T\rangle+\langle t\rangle)$ | $0<r<\frac{\langle T^{2}\rangle\left[\langle T^{2}\rangle-2\langle T\rangle(\langle t\rangle+\langle T\rangle)\right]}{(\langle t\rangle+\langle T\rangle)\langle T\rangle\langle T^{3}\rangle}$ | see Eq. (59) | see Eq. (60)
Gamma | $\langle T^{3}\rangle\geq 3(\langle T\rangle+\langle t\rangle)\langle T^{2}\rangle$ | $0<\beta<\frac{\langle T^{3}\rangle-3(\langle T\rangle+\langle t\rangle)\langle T^{2}\rangle}{(\langle T\rangle+\langle t\rangle)\langle T^{3}\rangle+\langle T^{4}\rangle}$ | numerically available | numerically available
Table 1: The table contains various restart protocols that are guaranteed to
reduce the average completion time of the process. For each strategy, the
table’s columns specify the following: the condition under which the
corresponding strategy is applicable; the resulting range for an effective
period (for periodic protocols) or rate (for Poisson or Gamma protocols); the
optimal period or rate providing the maximum guaranteed effectiveness; an
estimate for resulting maximum guaranteed efficiency.

##  III Optimization of success probability

So far, we have been talking about optimizing the average completion time of a
stochastic process. Meanwhile, restart can also be used to increase the
probability of observing a desired outcome of a random process with several
alternative completion scenarios [16]. Examples of such processes include
random search with multiple targets [21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31], random search with mortality [32, 33, 34, 35, 36, 37, 38, 39, 40],
chemical reactions with competing paths [41, 42, 43], folding of biopolymer
into one of several native states[44, 45, 46, 47, 48, 49]. In this section, we
provide constructive criteria of when restart increases chances that random
process ends in the desired way.

As a model consider a random process with two completion scenarios - ”success”
and ”failure”. The process is characterized by a random completion time $T$
having a probability density of $P(T)$. The latter can be represented as the
superposition $P(T)=P^{s}(T)+P^{f}(T)$, where $P^{s}(T)$ and $P^{f}(T)$ denote
the contribution of successful and unsuccessful trials, respectively. Note
that the normalization of the function $P^{s}(T)$ determines the ‘undisturbed’
probability of success of $p$: $p=\int_{0}^{\infty}P^{s}(T)dT$.

As previously, the restart protocol ${\cal R}$ is determined by a sequence of
time intervals $\tau_{1},\tau_{2},\dots$ which specifies the restart moments.
We will say that the protocol is effective if its implementation increases the
probability of success, i.e. $p_{{\cal R}}>p$. The corresponding restart
efficiency is defined as

$\displaystyle\chi=\frac{p_{{\cal R}}-p}{1-p}.$ (34)

For useful protocols we, thus, have $0<\chi\leq 1$.

If the process is restarted in strictly regular fashion with period $\tau$,
then the resulting probability of observing a successful outcome is equal to
[16]

$\displaystyle
p_{\tau}=\frac{\int_{0}^{\tau}P^{s}(T)dT}{\int_{0}^{\tau}P(T)dT}.$ (35)

The probability of success $p_{r}$ for the process under Poisson restart at
rate $r$ has the following form [16]

$p_{r}=\frac{\tilde{P}^{s}(r)}{\tilde{P}(r)},$ (36)

where $\tilde{P}^{s}(r)$ and $\tilde{P}(r)$ denote the Laplace transforms of,
respectively, $P^{s}(T)$ and $P(T)$ evaluated at $r$.

Finally, for the gamma-protocol with rate parameter $\beta$ and shape
parameter $k=1$ the resulting success probability is be given by the following
expression

$\displaystyle
p_{\beta}=\frac{\beta\partial_{\beta}\tilde{P}^{s}(\beta)-\tilde{P}^{s}(\beta)}{\beta\partial_{\beta}\tilde{P}(\beta)-\tilde{P}(\beta)}.$
(37)

Note that Eqs. (35-37) are valid in the presence of arbitrarily distributed
random penalty for restart as long as the penalty is uncorrelated with
outcome.

###  III.1 Regular strategy

Suppose the condition

$\displaystyle m_{s}<m,$ (38)

is met, where $m_{s}$ is the median completion time of successful attempts and
$m$ is the unconditional median completion time of the stochastic process of
interest. These metrics are defined by the relations
$p\int_{0}^{m_{s}}dTP^{s}(T)=1/2$ and $(1-p)\int_{0}^{m_{f}}dTP^{f}(T)=1/2$.
Then from (35) it is easy to see that the restart with a period $\tau$
belonging to the interval

$\displaystyle m_{s}<\tau<m,$ (39)

is effective for sure, since in this case the following estimate is valid

$\displaystyle
p_{\tau}=\frac{{p}+2\int_{m_{s}}^{\tau}dTP^{s}(T)}{{1}-2\int_{\tau}^{m}dTP(T)}>p.$
(40)

Unfortunately, the optimal period providing the greatest guaranteed efficiency
$\chi$ on the interval (39) cannot be expressed in terms of $m_{s}$ and $m$
but depends on the fine details of the probability density $P(T)$.

###  III.2 Poisson strategy

A simple sufficient condition for existence of effective Poisson restart
protocol found in [16] reads

$\displaystyle\langle T_{s}\rangle<\langle T\rangle,$ (41)

where $\langle T_{s}\rangle=p^{-1}\int_{0}^{\infty}dTP^{s}(T)T$ is the average
completion time of successful trials, while $\langle T\rangle$ is the
unconditional mean completion time. This criterion, however, does not say
anything about how to choose an efficient restart rate since knowledge of
linear statistical moments $\langle T_{s}\rangle$ and $\langle T\rangle$ alone
is not enough for these purposes. Below we show that adding information about
the second moment of the random completion time $\langle T^{2}\rangle$ allows
us to formulate a constructive criterion for the effectiveness of a Poisson
restart.

The probability of success given by Eq. (36) can be estimated from below as

$\displaystyle p_{r}\geq\frac{(1-r\langle T_{s}\rangle)(\langle T^{2}\rangle
r+\langle T\rangle)}{(\langle T^{2}\rangle-\langle T\rangle^{2})r+\langle
T\rangle}p,$ (42)

where we used the bound $P^{s}(r)\geq p\left(1-r\langle T_{s}\rangle\right)$,
which directly follows from (14), and the inequality [20]

$P(r)\leq 1-\frac{r\langle T\rangle^{2}}{r\langle T^{2}\rangle+\langle
T\rangle}.$ (43)

We see from (42) that if the existence condition (41) is met, then a Poisson
restart with a rate enclosed inside the interval

$\displaystyle 0<r<\frac{\langle T\rangle\left(\langle T\rangle-\langle
T_{s}\rangle\right)}{\langle T^{2}\rangle\langle T_{s}\rangle},$ (44)

increases the chances of success, i.e. $p_{r}>p$. As can be found by examining
the right side of the inequality (46) for an extremum, the point $r_{0}$ given
by Eq. (61) in Appendix provides the maximum guaranteed gain for the given
values of $\langle T_{s}\rangle$, $\langle T\rangle$ and $\langle
T^{2}\rangle$ provided the use of way of estimates described above. The
resulting efficiency is estimated from below as shown in Eq. (62).

Let us demonstrate another road to the range of efficient rates.
Alternatively, using the results of [50], we can evaluate the Laplace
transform from above as

$\displaystyle\tilde{P}(r)\leq 1-\frac{\langle T\rangle^{2}}{\langle
T^{2}\rangle}+\frac{\langle T\rangle^{2}}{\langle
T^{2}\rangle}e^{-\frac{\langle T^{2}\rangle}{\langle T\rangle}r},$ (45)

and then from Eq. (36) one gets

$\displaystyle p_{r}\geq\frac{\langle T^{2}\rangle(1-r\langle
T_{s}\rangle)}{\langle T^{2}\rangle-\langle T\rangle^{2}+\langle
T\rangle^{2}e^{-\frac{\langle T^{2}\rangle}{\langle T\rangle}r}}p.$ (46)

By requiring the expression on the right side of the last inequality to exceed
the undisturbed probability of success $p$, we find that if the condition
$\langle T_{s}\rangle<\langle T\rangle$ is satisfied, then all rates belonging
to the interval $0<r<r_{c}$, where $r_{c}$ represents the solution of the
transcendental equation $1-\frac{\langle T^{2}\rangle\langle
T_{s}\rangle}{\langle T\rangle^{2}}r-e^{-\frac{\langle T^{2}\rangle}{\langle
T\rangle}r}=0$, increase the chances of success. Interestingly, at $\langle
T\rangle-\langle T_{s}\rangle\ll\langle T\rangle$, one obtains the boundary
$r_{c}\approx 2\frac{\langle T\rangle-\langle T_{s}\rangle}{\langle
T^{2}\rangle}$ which twice exceeds the corresponding value dictated by Eq.
(44).

###  III.3 Gamma strategy

Finally, let us analyse the case of gamma-protocol. From (4), we see that if
the condition

$\displaystyle\langle T^{2}\rangle\geq\langle T^{2}_{s}\rangle,$ (47)

is met, then $\partial_{\beta}p_{\beta}>0$ at $\beta=0$ and, therefore, the
inequality (47) represents a sufficient condition for the existence of an
efficient gamma-strategy. Note, however, that the fixed pair $\langle
T^{2}\rangle$ and $\langle T^{2}_{s}\rangle$ determines only the slope of
$p_{\beta}$ in its dependence of $\beta$ at the point $\beta=0$, without
saying anything about its behavior for non-zero $\beta$. Let us show that a
efficient rates can be specified if the third-order moment $\langle
T^{3}\rangle$ is additionally known.

The success probability dictated by (37) can be estimated from below in
several different ways. Namely, first let us exploit inequality (20) at $l=1$
and $l=2$ for $\beta\partial_{\beta}\tilde{P}(\beta)$ and $\tilde{P}(\beta)$,
respectively. Next, let us estimate both terms in the denominator of Eq. (37)
via the inequality [20]

$\displaystyle\tilde{P}(\beta)\leq\sum_{k=0}^{2l}(-1)^{k}\frac{\beta^{k}\langle
T^{k}\rangle}{k!},$ (48)

at $l=1$. This yields

$\displaystyle p_{\beta}\geq\frac{6-3\langle T_{s}^{2}\rangle\beta^{2}-\langle
T_{s}^{3}\rangle\beta^{3}}{3(2-\langle T^{2}\rangle\beta^{2}+\langle
T^{3}\rangle\beta^{3})}p,$ (49)

where we assumed $1-\frac{\beta^{2}}{2}\langle
T^{2}\rangle+\frac{\beta^{3}}{2}\langle T^{3}\rangle\geq 0$. Then, requiring
that the corresponding bound is greater than the undisturbed probability of
success $p$, we obtain the interval

$\displaystyle 0<\beta<\frac{3(\langle T^{2}\rangle-\langle
T_{s}^{2}\rangle)}{3\langle T^{3}\rangle+\langle T_{s}^{3}\rangle},$ (50)

for rates which guarantee to increase the chances of success. The interval is
non-empty as long as the condition (47) is met.

Alternatively, one can use (20) with $l=1$ to bound $\tilde{P}(\beta)$ in the
numerator of (37), while leaving other estimates unchanged. This gives

$\displaystyle p_{\beta}\geq\frac{2-2\beta^{2}\langle
T_{s}^{2}\rangle}{2-\beta^{2}\langle T^{2}\rangle+\beta^{3}\langle
T^{3}\rangle}p.$ (51)

The same line of reasoning as described above the following interval of
efficient rates

$\displaystyle 0<\beta<\frac{\langle T^{2}\rangle-2\langle
T_{s}^{2}\rangle}{\langle T^{3}\rangle}.$ (52)

In contrast to the previous case, here we face a stronger applicability
condition $\langle T^{2}\rangle\geq 2\langle T^{2}_{s}\rangle$.

Similar result can be obtained if we estimate both terms entering numerator of
expression for $p_{\beta}$ using (20) with $l=1$, and exploit (43) to estimate
the term $-\partial_{\beta}\tilde{P}(\beta)=\langle T\rangle\tilde{Q}(\beta)$
in the denominator. For the probability of success we then find

$\displaystyle p_{\beta}\geq\frac{(2-2\beta^{2}\langle
T_{s}^{2}\rangle)(\langle T^{2}\rangle+\beta\langle T^{3}\rangle)}{2\langle
T^{2}\rangle-\beta^{2}\langle T^{2}\rangle^{2}+\beta^{3}\langle
T^{3}\rangle\langle T^{2}\rangle+2\beta\langle T^{3}\rangle}p.$ (53)

This estimate yields a narrower interval of effective rates

$\displaystyle{0<\beta<\frac{\langle T^{2}\rangle(\langle
T^{2}\rangle-2\langle T_{s}^{2}\rangle)}{\langle T^{3}\rangle(\langle
T^{2}\rangle+2\langle T^{2}_{s}\rangle)}},$ (54)

with the previous condition of applicability ${\langle T^{2}\rangle>2\langle
T_{s}^{2}\rangle}$.

To determine the best rates that provide the maximum guaranteed efficiency of
gamma restart at the intervals described above, and to calculate the resulting
efficiencies, one need to solve high-order algebraic equations, which is more
convenient to do by numerical methods.

Protocol | Applicability condition | Range for effective period/rate | Recommended period/rate | Efficiency
---|---|---|---|---
Regular | $m_{s}<m$ | $m_{s}<\tau<m$ | - | -
Poisson 1 | $\langle T_{s}\rangle<\langle T\rangle$ | $0<r<\frac{\langle T\rangle\left(\langle T\rangle-\langle T_{s}\rangle\right)}{\langle T^{2}\rangle\langle T_{s}\rangle}$ | see Eq. (61) | see Eq. (62)
Poisson 2 | $\langle T_{s}\rangle<\langle T\rangle$ | numerically available | numerically available | numerically available
Gamma 1 | $\langle T_{s}^{2}\rangle<\langle T^{2}\rangle$ | $0<\beta<\frac{3(\langle T^{2}\rangle-\langle T_{s}^{2}\rangle)}{3\langle T^{3}\rangle+\langle T_{s}^{3}\rangle}$ | numerically available | numerically available
Gamma 2 | $2\langle T_{s}^{2}\rangle<\langle T^{2}\rangle$ | $0<\beta<\frac{\langle T^{2}\rangle-2\langle T_{s}^{2}\rangle}{\langle T^{3}\rangle}$ | numerically available | numerically available
Gamma 3 | $2\langle T_{s}^{2}\rangle<\langle T^{2}\rangle$ | $0<\beta<\frac{\langle T^{2}\rangle(\langle T^{2}\rangle-2\langle T_{s}^{2}\rangle)}{\langle T^{3}\rangle(\langle T^{2}\rangle+2\langle T^{2}_{s}\rangle)}$ | numerically available | numerically available
Table 2: A table summarizing various restart protocols guaranteed to increase
the probability of success. For each strategy, the table’s columns specify the
following: the condition when the corresponding strategy works; the resulting
range for an effective period (for periodic protocols) or rate (for Poisson or
Gamma protocols); the optimal period or rate providing the maximum guaranteed
effectiveness; an estimate for resulting maximum guaranteed efficiency.

##  IV Conclusion

While very useful, the previously known sufficient conditions for the
existence of an efficient restart strategy (see [6, 16, 17]) do not specify
this strategy. Significant progress in solving the problem of choosing an
effective restart policy at partial knowledge of process statistics was
achieved in work [13], whose authors formulated relatively simple constructive
criteria for the effectiveness of periodic restarts. Overcoming limitations of
the previously known existence results, these criteria offer a specific
restart period that is guaranteed to reduce the average completion time of the
random process. Motivated by this progress, in this paper, we generalized one
of the criteria proposed in [13] to the case of a non-zero time penalty for
restart and also constructed several new criteria, some of which concern the
case of stochastic restart. In addition, we have offered the first examples of
constructive criterion of restart efficiency in context of the success
probability optimization. The results of the analysis are summarized in tables
(1) and (2).

It is important to note that all the criteria formulated here represent
sufficient but not necessary conditions. This means that there exist random
processes for which none of the applicability conditions given by Eqs.
(6),(10), (13), (27), (38), (41) and (47) is fulfilled, but an effective
strategy still exists. Thus, the protocols listed in the tables (1) and (2)
are complementary and, in practice, should be used together in order to
compensate for each other’s shortcomings at least partially.

###  IV.1 Acknowledgements

The work was supported by the Russian Science Foundation (RSF), project
$\\#$22-72-10052. The authors are grateful to V.V. Lebedev for useful
comments. I.S. Nikitin would like to thank A.M. Zubkov for referring to
relevant literature on statistical inequalities.

##  V Appendix

###  V.1 Optimization of the mean completion time

####  V.1.1 Poisson protocol

It is easy to show that within the interval given by (17), the expression on
the right side of the inequality (15) reaches its minimum value at the point

$r^{m}_{opt}=\frac{-2\langle T^{2}\rangle{\cal T}_{on}+\sqrt{2\langle
T^{2}\rangle^{3}\left[{\cal T}_{on}\langle T^{3}\rangle-\langle
T^{2}\rangle^{2}-2{\cal T}_{on}\langle T^{2}\rangle\langle
t\rangle\right]\left[\langle T^{3}\rangle\langle T\rangle-\langle
T^{2}\rangle^{2}\right]^{-1}}}{{\cal T}_{on}\langle T^{3}\rangle-\langle
T^{2}\rangle^{2}},$ (55)

where ${\cal T}_{on}=\langle T\rangle+\langle t\rangle$.

As can be easily shown from (17), (14) and (15), the resulting efficiency is
defined as

$\displaystyle\eta_{3}\geq 1-\frac{{\cal T}_{on}\langle T^{3}\rangle-\langle
T^{2}\rangle^{2}}{{\cal T}_{on}\left[\langle T^{3}\rangle-2\langle
T\rangle\langle T^{2}\rangle\right]-2{\cal T}_{on}r_{opt}^{m}\left[\langle
T\rangle\langle T^{3}\rangle-\langle T^{2}\rangle^{2}\right]}$ (56)

Rate $r_{opt}^{c}$ minimizes the right side of the inequality (21) on the
interval (23), thus providing the greatest guaranteed efficiency at the given
values of the first three points of the initial completion time

$\displaystyle r^{c}_{opt}=\frac{1}{\langle T\rangle}-\frac{\sqrt{\langle
T^{3}\rangle(\langle T^{3}\rangle-3\langle T^{2}\rangle\langle
T\rangle+6\langle T\rangle^{2}{\cal T}_{on}})}{\langle T\rangle\langle
T^{3}\rangle}$ (57)

Efficiency can be estimated from below as

$\displaystyle\eta_{4}\geq 1-\frac{3\langle T^{2}\rangle-2\langle T^{3}\rangle
r^{c}_{opt}}{6\langle T\rangle\left(\langle t\rangle+\langle T\rangle\right)}$
(58)

The optimal rate is given by

$\displaystyle r^{ms}_{opt}=\frac{-2{\cal T}_{on}\langle
T^{2}\rangle+\sqrt{2}\sqrt{\left(2{\cal T}_{on}\langle T\rangle\langle
T^{2}\rangle+{\cal T}_{on}\langle T^{3}\rangle-\langle
T^{2}\rangle^{2}\right)\langle T^{2}\rangle^{3}\left[\langle T\rangle\langle
T^{3}\rangle\right]^{-1}}}{{\cal T}_{on}\langle T^{3}\rangle-\langle
T^{2}\rangle^{2}}.$ (59)

Efficiency can be estimated from below as

$\displaystyle\eta_{5}\geq 1-\frac{\langle T^{3}\rangle\left(\langle
t\rangle+T\right)-\langle T^{2}\rangle^{2}}{\left(\langle t\rangle+\langle
T\rangle\right)\left(\langle T^{3}\rangle-2\langle
T\rangle\left(r^{ms}_{opt}\langle T^{3}\rangle+\langle
T^{2}\rangle\right)\right)}$ (60)

###  V.2 Optimization of splitting probabilities

####  V.2.1 Poisson strategy

It is easy to show by examining the right side of the inequality (46) at the
extremum, the point belonging to the specified interval

$\small r_{0}=\frac{-\langle T_{s}\rangle\langle T\rangle\langle
T^{2}\rangle+\sqrt{\langle T\rangle^{3}\langle T^{2}\rangle\langle
T_{s}\rangle(\langle T\rangle\langle
T_{s}\rangle+\sigma^{2})}}{\sigma^{2}\langle T^{2}\rangle\langle
T_{s}\rangle},$ (61)

where $\sigma^{2}=\langle T^{2}\rangle-\langle T\rangle^{2}$, provides the
maximum guaranteed gain for the given values of $\langle T_{s}\rangle$,
$\langle T\rangle$ and $\langle T^{2}\rangle$. The resulting efficiency is
estimated from below as

$\displaystyle\chi_{2}>$ $\displaystyle\frac{p}{1-p}\frac{\langle
T\rangle}{\sigma^{4}}\cdot\biggr{[}\left(\left(\langle T\rangle^{2}+\langle
T^{2}\rangle\right)\langle T_{s}\rangle-\langle
T\rangle\sigma^{2}\right)\biggr{.}\biggr{.}-2\sqrt{\langle T\rangle\langle
T^{2}\rangle\langle T_{s}\rangle\left(\langle T\rangle\langle
T_{s}\rangle+\sigma^{2}\right)}\Biggr{]}.$ (62)

## References

  * [1] H. Alt, L. Guibas, K. Mehlhorn, R. Karp, and A. Wigderson, “A method for obtaining randomized algorithms with small tail probabilities,” _Technical Report TR-91-057_ , 1991.
  * [2] M. Luby, A. Sinclair, and D. Zuckerman, “Optimal speedup of las vegas algorithms,” _Information Processing Letters_ , vol. 47, no. 4, p. 173, 1993.
  * [3] M. Evans and S. Majumdar, “Diffusion with stochastic resetting,” _Physical Review Letters_ , vol. 106, no. 16, p. 160601, 2011.
  * [4] S. Reuveni, M. Urbakh, and J. Klafter, “Role of substrate unbinding in michaelis–menten enzymatic reactions,” _Proceedings of the National Academy of Sciences_ , vol. 111, no. 12, p. 4391, 2014.
  * [5] T. Rotbart, S. Reuveni, and M. Urbakh, “Michaelis-menten reaction scheme as a unified approach towards the optimal restart problem,” _Physical Review E_ , vol. 92, no. 6, p. 060101, 2015.
  * [6] S. Reuveni, “Optimal stochastic restart renders fluctuations in first passage times universal,” _Physical Review Letters_ , vol. 116, no. 17, p. 170601, 2016.
  * [7] A. Pal and S. Reuveni, “First passage under restart,” _Physical Review Letters_ , vol. 118, no. 3, p. 030603, 2017.
  * [8] J. Lorenz, “Restart strategies in a continuous setting,” _Theory of Computing Systems_ , vol. 65, no. 8, p. 1143, 2021.
  * [9] M. Gagliolo and J. Schmidhuber, “Learning restart strategies,” _IJCAI_ , p. 792, 2007.
  * [10] J. Lorenz, “Runtime distributions and criteria for restarts.” _In International Conference on Current Trends in Theory and Practice of Informatics_ , p. 493, 2018.
  * [11] H. Wu and P. Beek, “On universal restart strategies for backtracking search,” _In International Conference on Principles and Practice of Constraint Programming_ , p. 681, 2007.
  * [12] M. Streeter, D. Golovin, and S. Smith, “Restart schedules for ensembles of problem instances,” _AAAI_ , p. 1204, 2007.
  * [13] I. Eliazar and S. Reuveni, “Mean-performance of sharp restart: Ii. inequality roadmap,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 54, no. 35, p. 355001, 2021.
  * [14] T. Robin, S. Reuveni, and M. Urbakh, “Single-molecule theory of enzymatic inhibition.” _Nature communications_ , vol. 9, no. 1, p. 1, 2018.
  * [15] O. Tal-Friedman, A. Pal, A. Sekhon, S. Reuveni, and Y. Roichman, “Experimental realization of diffusion with stochastic resetting,” _The journal of physical chemistry letters_ , vol. 11, no. 17, p. 7350, 2020.
  * [16] S. Belan, “Restart could optimize the probability of success in a bernoulli trial,” _Physical Review Letters_ , vol. 120, no. 8, p. 080601, 2018.
  * [17] D. Starkov and S. Belan, “Universal performance bounds of restart,” _Physical Review E_ , vol. 107, no. 6, p. L062101, 2023.
  * [18] A. Pal, S. Kostinski, and S. Reuveni, “The inspection paradox in stochastic resetting,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 55, no. 2, p. 021001, 2022.
  * [19] M. R. Evans, S. N. Majumdar, and G. Schehr, “Stochastic resetting and applications,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 53, no. 19, p. 193001, 2020.
  * [20] A. Zubkov, “Two-sided inequalities for laplace transforms,” _Theory of Probability & Its Applications_, vol. 43, no. 4, pp. 676–681, 1999.
  * [21] S. Condamin, O. Bénichou, and M. Moreau, “Random walks and brownian motion: A method of computation for first-passage times and related quantities in confined geometries,” _Physical Review E_ , vol. 75, no. 2, p. 021111, 2007.
  * [22] S. Condamin, V. Tejedor, and O. Bénichou, “Occupation times of random walks in confined geometries: From random trap model to diffusion-limited reactions,” _Physical Review E_ , vol. 76, no. 5, p. 050102, 2007.
  * [23] S. Condamin, V. Tejedor, R. Voituriez, O. Bénichou, and J. Klafter, “Probing microscopic origins of confined subdiffusion by first-passage observables,” _Proceedings of the National Academy of Sciences_ , vol. 105, no. 15, p. 5675, 2008.
  * [24] B. Meyer, E. Agliari, O. Bénichou, and R. Voituriez, “Exact calculations of first-passage quantities on recursive networks,” _Physical Review E_ , vol. 85, no. 2, p. 026113, 2012.
  * [25] T. Calandre, O. Bénichou, D. Grebenkov, and R. Voituriez, “Interfacial territory covered by surface-mediated diffusion,” _Physical Review E_ , vol. 85, no. 5, p. 051111, 2012.
  * [26] ——, “Splitting probabilities and interfacial territory covered by two-dimensional and three-dimensional surface-mediated diffusion,” _Physical Review E_ , vol. 89, no. 1, p. 012149, 2014.
  * [27] O. Bénichou and R. Voituriez, “Mean first-passage times in confined media: from markovian to non-markovian processes,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 48, no. 16, p. 163001, 2015.
  * [28] G. Cencetti, F. Bagnoli, F. Di Patti, and D. Fanelli, “The second will be first: competition on directed networks,” _Scientific Reports_ , vol. 6, no. 1, p. 1, 2016.
  * [29] P. Krapivsky and S. Redner, “Trapping and escape in a turbid medium,” _The Journal of Chemical Physics_ , vol. 147, no. 21, p. 214903, 2017.
  * [30] U. Dobramysl and D. Holcman, “Mixed analytical-stochastic simulation method for the recovery of a brownian gradient source from probability fluxes to small windows,” _Journal of computational physics_ , vol. 355, p. 22, 2018.
  * [31] A. Pal and V. Prasad, “First passage under stochastic resetting in an interval,” _Physical Review E_ , vol. 99, no. 3, p. 032123, 2019.
  * [32] I. Lohmar and J. Krug, “Diffusion-limited reactions and mortal random walkers in confined geometries,” _Journal of Statistical Physics_ , vol. 134, p. 307, 2009.
  * [33] E. Abad, S. Yuste, and K. Lindenberg, “Survival probability of an immobile target in a sea of evanescent diffusive or subdiffusive traps: A fractional equation approach,” _Physical Review E_ , vol. 86, no. 6, p. 061120, 2012.
  * [34] ——, “Elucidating the role of subdiffusion and evanescence in the target problem: Some recent results,” _Mathematical Modelling of Natural Phenomena_ , vol. 8, no. 2, p. 100, 2013.
  * [35] Exploration and trapping of mortal random walkers, “Yuste, sb. and abad, e. and lindenberg, k.” _Physical Review Letters_ , vol. 110, no. 22, p. 220603, 2013.
  * [36] E. Abad, S. Yuste, and K. Lindenberg, “Evanescent continuous-time random walks,” _Physical Review E_ , vol. 88, no. 6, p. 062110, 2013.
  * [37] E. Abad and J. Kozak, “Competing reaction processes on a lattice as a paradigm for catalyst deactivation,” _Physical Review E_ , vol. 91, no. 2, p. 022106, 2015.
  * [38] D. Campos, E. Abad, V. Méndez, S. Yuste, and K. Lindenberg, “Optimal search strategies of space-time coupled random walkers with finite lifetimes,” _Physical Review E_ , vol. 91, no. 5, p. 052115, 2015.
  * [39] B. Meerson and S. Redner, “Mortality, redundancy, and diversity in stochastic search,” _Physical Review Letters_ , vol. 114, no. 19, p. 198101, 2015.
  * [40] D. Grebenkov and J. Rupprecht, “The escape problem for mortal walkers,” _The Journal of Chemical Physics_ , vol. 146, no. 8, p. 084106, 2017.
  * [41] J. Rehbein and B. Carpenter, “Do we fully understand what controls chemical selectivity?” _Physical Chemistry Chemical Physics_ , vol. 13, no. 47, p. 20906, 2011.
  * [42] J. Rehbein and B. Wulff, “Chemistry in motion—off the mep,” _Tetrahedron letters_ , vol. 56, no. 50, p. 6931, 2015.
  * [43] A. Martín-Sómer, M. Yáñez, W. Hase, M. Gaigeot, and R. Spezia, “Post-transition state dynamics in gas phase reactivity: importance of bifurcations and rotational activation,” _Journal of Chemical Theory and Computation_ , vol. 12, no. 3, p. 974, 2016.
  * [44] S. Solomatin, M. Greenfeld, S. Chu, and D. Herschlag, “Multiple native states reveal persistent ruggedness of an rna folding landscape,” _Nature_ , vol. 463, no. 7281, p. 681, 2010.
  * [45] M. Marek, A. Johnson-Buck, and N. Walter, “The shape-shifting quasispecies of rna: one sequence, many functional folds,” _Physical Chemistry Chemical Physics_ , vol. 13, no. 24, p. 11524, 2011.
  * [46] C. Hyeon, J. Lee, J. Yoon, S. Hohng, and D. Thirumalai, “Hidden complexity in the isomerization dynamics of holliday junctions,” _Nature chemistry_ , vol. 4, no. 11, p. 907, 2012.
  * [47] B. Paudel and D. Rueda, “Molecular crowding accelerates ribozyme docking and catalysis,” _Journal of the American Chemical Society_ , vol. 136, no. 48, p. 16700, 2014.
  * [48] M. Hinczewski, C. Hyeon, and D. Thirumalai, “Directly measuring single-molecule heterogeneity using force spectroscopy,” _Proceedings of the National Academy of Sciences_ , vol. 113, no. 27, p. E3852, 2016.
  * [49] C. Pierse and O. Dudko, “Distinguishing signatures of multipathway conformational transitions,” _Physical Review Letters_ , vol. 118, no. 8, p. 088101, 2017.
  * [50] D. Brook, “Bounds for moment generating functions and for extinction probabilities,” _Journal of Applied Probability_ , vol. 3, no. 1, p. 171, 1966.