PHYSICAL REVIEW E 100, 032110 (2019)

Robust random search with scale-free stochastic resettingŁukasz Kuśmierz

and Taro Toyoizumi

Laboratory for Neural Computation and Adaptation, RIKEN Center for Brain Science, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan(Received 30 December 2018; revised manuscript received 16 April 2019; published 5 September 2019)
A new model of search based on stochastic resetting is introduced, wherein rate of resets depends explicitly
on time elapsed since the beginning of the process. It is shown that rate inversely proportional to time leads
to paradoxical diffusion which mixes self-similarity and linear growth of the mean-square displacement withnonlocality and non-Gaussian propagator. It is argued that such resetting protocol offers a general and efficient
search-boosting method that does not need to be optimized with respect to the scale of the underlying search
problem (e.g., distance to the goal) and is not very sensitive to other search parameters. Both subdiffusive
and superdiffusive regimes of the mean-squared displacement scaling are demonstrated with more general ratefunctions.
DOI: 10.1103/PhysRevE.100.032110

I. INTRODUCTION

Any search is intrinsically governed by randomness: theneed to perform it underscores the ignorance of the searching
agent and its inability to predict the outcome. In particular,
the agent may not know in advance how much time, on
average, it will take to find a target and how much variability
in search time is expected due the randomness. How can theefficiency of a search strategy be boosted without acquiringsuch information beforehand? It may happen that the longer
the search lasts, the more unfavorable random instance theagent is experiencing, and thus the longer the expected remaining time to find the target. It is then true that restarting
the process anew may be beneficial, as it lowers the expectedcompletion time. It has been shown that this is indeed the caseif the coefficient of variation of completion times is larger
than 1 [1]. This conditions holds if the completion timesof a search process are drawn from the hyperexponential or
power-law distributions. Such situation arises, for instance,in the one-dimensional, unbiased Brownian motion with asingle target. The possibility of arbitrarily long excursions far
from the target manifests itself in large fluctuations and theassociated power-law distribution of the first passage times.
In the engineering community such mechanism was studied in the context of computer software systems [2–5] andnonconvex optimization methods [6–9]. More recently, Evans
and Majumdar introduced a model with time-homogeneous
stochastic resetting (i.e., with exponentially distributed waiting times between the resets) in tandem with diffusion [10].
They showed that one-dimensional [10] and multidimensional[11] diffusion with resets exhibit finite mean first passage
times (MFPTs) which can be optimized with respect to resetting rate r. Moreover, resets lead to nonequilibrium steadystates with a combination of local and nonlocal currents[10,12,13]. The simplicity and nontrivial behavior of thesesystems has sparked the interest of the physics community,with a considerable amount of research focusing on modifying
the model to include nontrivial boundary conditions [14–16],
external potentials [17], anomalous transport [12,18–24],
2470-0045/2019/100(3)/032110(8)drift [21,25], delays following the resets [1,26–28], and nonexponential distributions of waiting times between resets[13,29,30]. Resets were also studied in the context of stochastic energetics [31], enzymatic reactions [32], fluctuating interfaces [33], and power-law distributions in nonequilibrium
systems [34].
Nonexponential waiting times between the resets can begenerated by time-dependent resetting rates [29,30]. In models introduced in these previous works, rate depends on thetime elapsed since the last reset. Here we introduce a newmodel with resetting rate r(t ) that depends on the time elapsed
since the start of the process. Such nonstationary resetting
protocol, while preserving the Markovian character of the
dynamics, introduces time-inhomogeneity. As we will show,
this dramatically affects the behavior of the process. If r(t )decays with time, then the process does not converge to
any steady state, with the mean-square displacement (MSD)
growing indefinitely. Moreover, r(t ) that is inversely proportional to time provides an efficient and robust mechanism
to boost the time efficiency of a search. It has previously
been shown that deterministic resetting is the optimal way ofminimizing search time via resets [35]. However, similarly
to stochastic resetting with a constant rate, such resetting
has to be optimized assuming full knowledge of details of agiven search problem. In contrast, the resetting mechanism
we propose does not have to be adapted to the timescale ofthe search problem.
II. DIFFUSION WITH TIME-DEPENDENT RESETTING

We start from one-dimensional diffusion as the underlying
search process, which will help build the intuition. Later
we present a more general framework. Since the processof diffusion with memoryless resetting is Markovian, it isfully characterized by the initial position distribution and the
propagator ρ(x, t|xi , ti ), which denotes the probability density
function of x at time t of a particle that at time ti < t was
at xi . The particle diffuses till a resetting event that brings it
instantaneously back to the resetting position x0 (equal to the032110-1©2019 American Physical SocietyŁUKASZ KUŚMIERZ AND TARO TOYOIZUMIPHYSICAL REVIEW E 100, 032110 (2019)

position of the particle at time t = 0) [36]. The particle thencontinues to diffuse until the next reset. The corresponding
propagator solves the following partial differential equation:102∂t ρ(x, t|xi , ti ) = D∂xx
ρ(x, t|xi , ti ) − r(t )ρ(x, t|xi , ti )+ r(t )δ(x − x0 ),where ∂z denotes the partial derivative with respect to z and
D is the diffusion coefficient. Such process has been analyzed
extensively in the case of a constant rate r(t ) = r, with thecorresponding resets described by the homogeneous Poisson
point process. It has been shown [10] that this process, inthe absence of targets, attains a nonequilibrium steady state.
If a single target, represented by an absorbing boundary, isplaced at the origin, then there exists an optimal rate r ∗ ∝ x0−2
at which the MFPT is minimized.
A. Scale-free resetting

In this work we mainly focus our attention on the special
case ofr(t ) =

α
.
t

(2)

The only parameter α is dimensionless—this form of resetting
does not introduce any timescale. For this reason, we refer to
Eq. (2) as a scale-free resetting. Resets described by Eq. (2)are generated by the inhomogeneous Poisson point processwith an average intensity (expected number of events) withina time period (t0 , t1 ] given by
N (t0 , t1 ) = α ln

t1
.
t0

(3)

Note that our choice of r(t ) features a singularity at t = 0,
which translates into diverging intensity with t0 → 0. Any
practical applications of scale-free resetting have to introduce
a short-term cutoff to avoid resetting with infinite frequency.
However, all our theoretical predictions without an explicit
account of the cutoff are still valid at times much longer thanthe cutoff.
As evident from Eq. (1), the process Eq. (1) with Eq. (2)preserves the self-similarity of the pure Brownian motion, i.e.,
the rescaling x → cx and t → c2t does not change any observables (see Fig. 1). We can therefore expect that the meansquare displacement (MSD) scales linearly with time. Indeed,straightforward calculations [multiply Eq. (1) by (x − x0 )2 ,integrate over x and solve the resulting ordinary differential
equation] lead to
 ∞
2Dt
. (4)
(x(t ) − x0 )2  =dxx 2 ρ(x, t|x0 , 0) =1+α−∞Although the self-similarity and associated linear timedependence of the MSD bear a strong resemblance to freediffusion, resets vastly modify other statistics. For instance,
the Fourier transform of the propagator reads
ρ(k, t|x0 , 0) = αeikx0 t −α e−Dk t
2

-1

(1)

 t
0

dτ τ α−1 eDk τ .
2

(5)

0

0.2

0.4

0.6

0.8

1

0

20

40

60

80

100

10

0

-10

FIG. 1. Sample trajectories (colored, thin lines) and percentile
lines (thick, black lines) of diffusion with scale-free resetting with
α = 10. A comparison of short (top) and long (bottom) timescales
illustrates the self-similarity of the process. The presented percentile
lines xq (t ) are such that together only 10% of the sample trajectories
have x(t ) > xq (t ) (upper branch) or x(t ) < xq (t ) (lower branch).

This propagator is clearly non-Gaussian and has a cusp atx = x0 . It takes a particularly simple form for α = 1:
−Dk 2 tikx0 1 − eρ(k, t|x0 , 0) = e
.
Dk 2t

(6)

Similar non-Gaussian displacement distributions with acusp, accompanied by a linear time dependence of the MSD
have been observed in several systems of diffusing colloidal particles [37,38]. Such systems have recently attracted
considerable attention among theoreticians, who since thenhave developed multiple models with fluctuating diffusivity[37,39–42]. Scale-free resetting provides an alternative mechanism behind such behavior.
B. Generalizations of the resetting rate function

In addition to the presented applications to search problems, a generalization of the proposed resetting mechanism
can be applied to model anomalous transport phenomena. The
MSD of Eq. (1) with r(t ) = α/t μ is given by the formula


α 1−μ
2
t
(x(t ) − x0 )  = 2D exp −
1−μ


 t
α
τ 1−μ ,
(7)dτ exp×
1−μ0which for μ < 1 exhibits a smooth transition between diffusive behavior with the MSD ≈ 2Dt for tτα and subdifτα , where
fusive behavior with the MSD ≈ 2Dt μ /α for tτα = α −1/(1−μ) is the timescale introduced by the power-law
resetting. In the opposite case of μ > 1 the long-term behavior
is diffusive, whereas at short times an apparent superdiffusivity with the MSD ≈ 2Dτ μ /α is observed. By assumingr(t ) ∝ (log t )−1 one can also model an ultra-slow diffusion
with the MSD ∝ log t, a behavior previously uncovered in
the strongly non-Markovian random walks with preferential
relocations to places visited in the past [43].

032110-2

ROBUST RANDOM SEARCH WITH SCALE-FREE …

PHYSICAL REVIEW E 100, 032110 (2019)

One could involve heavy-tails jump distributions leading
to a competition between superdiffusivity of the Lévy flights
and subdiffusive tendency from resets, similar to the competition observed in the continuous-time random walk scheme[44–46]. Many different variants of a combination of anomalous transport with constant-rate stochastic resetting werepreviously studied [12,18–21,24] and were shown to exhibit
nontrivial features, including first and second order transitionsof the optimal search [18,19,21,47] and a nonmonotonic
behavior of the MSD [24]. For this reason, we expect that a
combination of scale-free resets with independent constantrate resets may lead to thought-provoking phenomena.
III. COMPLETION TIMES

A. General analysis

Instead of assuming that the underlying search process is
described by a simple, one-dimensional diffusion, we firstconsider any random search process. Let a nonnegative random variable T0 be the completion times of the original process without resetting. Similarly, let Tα denote the completion
times of the same process modified by introducing scale-freeresets of the form Eq. (2). Our goal is to calculate statistics ofTα given known statistics of T0 . In particular, we will be interested in the mean completion time (MCT), denoted as Tα . For
any absolute-time-dependent rate function r(t ), one can link
the survival probability of the model with resets Sα (t ) withthe survival probability of the underlying reset-free process
S0 (t ) by means of the following renewal equation [48]: t
Sα (t ) = S0 (t )(0, t ) +dτ r(τ ) Sα (τ ) S0 (t − τ )(τ, t ),
where

(8)

  t1(t0 , t1 ) = exp −dτ r(τ )Combining the general expression Eq. (8) with Eqs. (10) and(2) we arrive at the equationα t
Sα (t ) = αdτ τ α−1 Sα (τ ) S0 (t − τ ).
(11)
t 0
To solve Eq. (11) we introduce an auxillary function,

In the previous section we have shown how time-dependent
resetting affects the time evolution and shape of the displacement distribution. Another striking consequence of scale-freeresetting can be observed in the statistics of the first passage
times. As we show in the following, in contrast to free diffusion on infinite line, diffusion with scale-free resetting can finda target in a finite MFPT. Moreover, due to the self-similarity,
we can expect that the MFPT is proportional to x02 , where x0
denotes the initial position with respect to the target.
This observation prompted us to explore more general scenarios of search under scale-free resetting beyond diffusion on
infinite line. Since the following calculations apply to generalsearch times that may not be generated as the first passage
times of some stochastic process, we hereafter use the termcompletion times. We show that scale-free resetting is robust,i.e., the optimal form of the scale-free resetting (as prescribedby the parameter α) does not depend on the timescale. Thus,
the protocol can be optimized in a parsimonious manner,without knowing how much time on average the underlying
search takes.

0either there are no resets until time t, which happens withprobability (0, t ), or there are resets in this time period withthe last reset at time τ . The integral appears here because τ
can be anywhere between 0 and t. In the case of scale-freeresetting Eq. (2), the no-reset probability is given by
 α
t0
.
(10)
α (t0 , t1 ) =
t1

(9)

t0

is the probability of no resets in the interval of time (t0 , t1 ].
Equation (8) splits the survival probability into two cases:gα (t ) ≡ t α−1 Sα (t ),which solves a simpler integral equation,α tgα (t ) =dτ gα (τ ) S0 (t − τ ).
t 0

(12)

(13)

By denoting L{ f (t )} ≡ f˜(s) as the Laplace transform of f (t ),the corresponding Laplace-transformed equation reads∂s g̃α (s) = −α S̃0 (s) g̃α (s).

(14)

In the following we will assume that the probability of finding
the target in no-time is equal to zero. In this case the corresponding survival probability can be written in the form [49]S̃0 (s) =1 − ρ̃0 (s)
,
s

(15)

where ρ0 (t ) is the probability density function of thecompletion time of the process without resetting, andlims→∞ ρ̃0 (s) = 0. We can easily solve the differential
Eq. (14), leading to ∞ρ̃0 (u),(16)g̃α (s) = Cα s−α exp −αduuswhere Cα is a constant yet to be determined.
We now show how to recover S̃α (s) from g̃α (s). We employ
the identity ∞du(u − s)β e−st = (β + 1)t −1−β e−st ,(17)swhich holds for β > −1 [50]. From Eq. (17) we deduce that ∞1du(u − s)β f˜(s).
L{t −β−1 f (t )} =(18)
(β + 1) s
We can apply Eq. (18) in Eq. (12) by replacing β with α − 1and noticing that L{t f (t )} = −∂s f˜(s) [51], which leads to ∞1
du(u − s)α−1 ∂u g̃α (u).
(19)
S̃α (s) = −(α) s
In the last step we plug Eq. (16) into Eq. (19). The initialcondition

032110-3

lim Sα (t ) = lim s S̃α (s) = 1

t→0

s→∞

(20)

ŁUKASZ KUŚMIERZ AND TARO TOYOIZUMIPHYSICAL REVIEW E 100, 032110 (2019)

allows us to calculate Cα = (α). The final result reads ∞ 
u − s α−1 1 − ρ̃0 (u)duS̃α (s) = α
u
u2
s


 ∞
ρ̃0 (v).
(21)
× exp −αdvvuEquation (21) allows us to calculate any statistics of thecompletion times, at least in principle. In particular, the MCT
is simply given by S̃α (0), i.e.,


 ∞
 ∞
1 − ρ̃0 (u)ρ̃0 (v). (22)Tα = αduexp −αdv
u2v
0uB. Special cases

Here we present two special cases of the search process T0 ,which illustrates basic features of the scale-free resetting.

where
E1 (x) =,(23)

where τdiff ≡ x02 /D. Importantly, ρ0 (t ) ∼ t −3/2 for large t andthus the MCT is infinite. Plugging Eq. (23) into the general expression for the MCT (22) leads to a rather complicated integral, which can nevertheless be easily integrated numerically.
Numerical simulations confirm our theoretical prediction (cf.
Fig. 2) and show that the MCT attains its minimum value ofTα∗ /τdiff ≈ 1.97 at α ∗ ≈ 3.5. Moreover, as expected from thedimensionality analysis, the MCT scales quadratically with
the initial distance to the target.
We can learn a lot about the distribution of Tα by directly
analyzing the auxiliary function Eq. (16), which in the case ofdiffusion takes the form
√


(24)
g̃α (s) = (α + 1)s−α exp −2αE1 sτdiff ,
3

3

2.5

2.5

2

2

1.5

1.5

1

1

0.5

0.5

0
-1

0

1

2

3

0
-2

e−t
t

(25)

is a version of the exponential integral. For x > 0 it can be
expressed as∞

E1 (x) = −γ − ln x −(−x)k,k · k!
k=1(26)

where γ ≈ 0.5772 stands for the Euler-Mascheroni constant.
Thus the solution Eq. (24) has the following representation:√∞(− sτdiff )kαg̃α (s) = (α + 1)τdiff exp 2αγ + 2α.
k · k!
k=1(27)
By letting s = 0 in Eq. (27) we arrive at a simple formula forthe αth (fractional) moment,αTα α = α lim g̃α (s) = (α + 1)e2αγ τdiff.

In the first example we consider one-dimensional diffusion
Eq. (1) with a single target (trap). The probability density
function of the completion times (here corresponding to thefirst passage times) for α = 0 (no resets) is well-known and in
the Laplace space reads [49]ρ̃0 (s) = edtx

1. One-dimensional diffusion with a single trap√− sτdiff

 ∞

s→0

(28)

For α = 1 we obtain a simple expression for the MCT,T1 (x0 ) = e2γ τdiff ≈ 3.17x02 /D.

(29)

As expected, the MCT scales quadratically with the distance to the target. Small s expansion of (27) shows thatgα (t ) ∼ t −3/2 for large t, which together with Eq. (12) implies
that the tail of the survival probability behaves likeSα (t ) ∼ t −1/2−α .

(30)

ν

Therefore, the fractional moments Tα  are finite if and only
if ν < α + 1/2. In particular, the MCT is finite for α > 1/2;
see Fig. 2.
2. Random search with failure

As we show in Sec. III C, the optimal choice of α does notdepend on the search-problem timescale. However, this choice
may be sensitive to other features of ρ0 . In the second example
we explore the resilience of the scale-free resetting to search
failures. Let the search problem be described by the densityρ0 (t ) = pδ(t − τ0 ),(31)

where p  1 is the probability of a successful search. The
trivial case p = 1 corresponds to deterministic completiontime, whereas for p < 1 the density is unnormalized as there isnonzero probability 1 − p that the search ends with a failure;i.e., the completion time is infinite. We plugρ̃0 (s) = pe−sτ0(32)into Eq. (16) and arrive at
-1

0

1

g̃α (s) = (α + 1)s−α exp[−α pE1 (sτ0 )],

2

(33)

and thus via the expansion Eq. (26),
FIG. 2. The MCT of diffusion with scale-free resetting as a function of α (left) and the MCT of diffusion with constant-rate resetting
as a function of r (right). The gray vertical line denotes the asymptote
at α = 21 . Dots denote simulation results which were obtained bymeans of the Euler-Maruyama stochastic integration method with abias reduction technique that modifies the stopping rule close to thetarget [52] with D = 1, integration time step t = 10−3 , and numberof samples M = 106 . Notice log-log scale.

Sα (t ) ∼ t −α p ,(34)

for p < 1 and large t. We conclude that the MCT is finite if
and only if p = 1 or α > 1/p; see Fig. 3. Moreover, the MCT
is again proportional to timescale τ0 :
 ∞1 − pe−s −α pE1 (s)Tα (p) = τ0 α
ds
e
.
(35)
s2
0

032110-4

ROBUST RANDOM SEARCH WITH SCALE-FREE …
10

10

8

8

6

6

4

0

2

4

6

8

that minimizes h(α) at the same time minimizes the Tα (τ0 )ν 
for any nonzero value of τ0 .
This result is quite remarkable: the scale-free resetting provides a parsimonious search boosting technique that does not
employ any knowledge about the timescale of the underlying
search problem.

4

p = 0.5
p = 0.7
p = 0.92

PHYSICAL REVIEW E 100, 032110 (2019)

D. Comparison with other resetting protocols

2
10

0

1

2

1. Resetting protocols

3

FIG. 3. The MCT of the failure model Eq. (31) with scale-freeresetting as a function of α, Eq. (35) (left) and with constant-rateresetting as a function of r, Eq. (42) (right). Gray vertical lines denote
asymptotes given by α∞ = 1/p.

This example illustrates the fact that, while robust to thetimescale, scale-free resetting may be sensitive to other features of the search problem. In particular, the higher the
probability of the search failure, the larger resetting intensity
α is necessary to assure a finite value of the MCT. We discuss
this issue in more detail in Sec. III D 3.
C. Linear scale-dependence

We have seen that in two simple special cases the MCT
is proportional to the timescale of the underlying search
problem. Here we show that this is always the case and that
this observation generalizes to higher moments. Given thecompletion time of a process without resets T0 , we definea rescaled completion time as τ0 T0 . As in Sec. III B 2, theparameter τ0 denotes the timescale of the search problem,and may be related to its different features, e.g., in the caseof diffusion τ0 is proportional to x02 /D. The corresponding
probability density functions are related asρ̃0 (s, τ0 ) = exp(−sτ0 T0 )T0 = ρ̃0 (τ0 s, 1),(36)

whereas the survival probabilities
S̃0 (s, τ0 ) = τ0 S̃0 (τ0 s, 1).

(37)

Let Tα (τ0 ) denote the completion time of a process withscale-free resetting with the underlying reset-free completion
times given by τ0 T0 . We substitute variables v → v/τ0 andu → u/τ0 in Eq. (21) and obtain S̃α (s, τ0 ) = τ0 S̃α (τ0 s, 1),
which leads to the conclusion thatTα (τ0 ) ∼ τ0 Tα (1),(38)

where ∼ denotes the equality of distributions. For all finite
fractional moments
Tα (τ0 )ν  ∝ τ0ν ,To understand merits and limitations of the proposed scalefree resetting, it is instructive to compare it to other resetting
protocols, i.e., predefined schemes of introducing resets into
the system. We focus solely on (possibly nonstationary) feedforward protocols that are independent from the state of thesystem [53].
Due to its simplicity, constant-rate resetting [i.e., r(t ) = r]is particularly popular in the literature. Diffusion with such
resetting has been studied extensively and its optimal MCT isgiven by Tconst (x0 , r ∗ ) ≈ 1.54x02 /D with the optimal resetting
rater ∗ ∝ x0−2 [54].
Another protocol that is of interest to us is a periodic,
deterministic resetting. Following Refs. [1,35] we call thisresetting sharp. Sharp resetting is important, as it was shown
to form the dominant strategy in the stationary setting [35].
2. Fluctuating or unknown environment

Although the constant resetting can work better than
the scale-free resetting [Tconst (x0 , r ∗ ) < Tα∗ (x0 )], the optimal
scale-free search parameter α ∗ does not involve any knowledge about the distance to the target. In contrast, the optimal
constant rate r ∗ depends strongly on x0 ; see Fig. 2. Hence,
optimizing r may be hard, or even impossible, if the positionof the target is unknown.
Consider a scenario of a single, immobile target placed
at a random position and assume the location of the target
does not change between the resets, but is drawn independently for separate trials [19,55,56]. This is equivalent to theresetting (and initial) position being drawn from a distribution
ρX (x0 ), i.e., the MCTs of the scale-free and constant resetting
processes in this case can be calculated as Tα (x0 )x0 ∼ρX andTconst (x0 )x0 ∼ρX , respectively. The distribution ρX may represent the real variability of the environment or the ignorance ofthe searching agent.
As an important special case, let us take the Laplace
distribution ρX (x0 ) = exp (−|x0 |/λ)/(2λ), which maximizes
entropy for a given average distance to the target λ = |x0 |.
In this case, the MCT of diffusion with constant resetting rater reads
λTconst (x0 , r)x0 ∼ρX = √,Dr − rλ(39)

and thus the mean value scales linearly Tα (τ0 ) ∝ τ0 : scalefree restarts of the form Eq. (2) yield the MCT that is
proportional to timescale of the underlying search problem,
which explains why in the case of diffusion Tα ∝ x02 . As aconsequence of Eq. (39), the optimal value of α, as defined byany moment, is robust to changes of τ0 . To see this, we canrewrite Eq. (39) in the form Tα (τ0 )ν  = τ0ν h(α), where thefunction h(α) does not depend on τ0 . Clearly, the value of α(40)with the minimum value of 4λ2 /D at 1/r ∗ = 4λ2 /D. In
contrast, since the variance of the Laplace distribution is equalto 2λ2 , the MCT of diffusion with scale-free resetting is givenby032110-5Tα (x0 )x0 ∼ρX = f (α)

2λ2
,
D

(41)

ŁUKASZ KUŚMIERZ AND TARO TOYOIZUMIPHYSICAL REVIEW E 100, 032110 (2019)

where f (α) = Tα (x0 )/τdiff is the same prefactor as in thecase of constant x0 (Fig. 2) with the minimum f (α ∗ ) ≈ 1.97
at α ∗ ≈ 3.5—in this case the scale-free resetting leads to a(slightly) better efficiency than the constant resetting. More
importantly, in that case the optimal choice of α does notdepend on λ, to which the optimal constant rate is quitesensitive. Indeed, if the chosen constant rate is larger thanr = D/λ2 , the MCT diverges; see Eq. (40).
More broadly, the MCT of constant resetting search diverges for any distribution of x0 that has tails heavier than
exponential, in particular for any power-law distribution. In
contrast, the MCT of diffusion with scale-free resetting remains finite for any distribution of x0 with finite variance andthe choice of the optimal parameter α does not depend on any
aspect of the distribution of x0 ,The optimal parameters of the constant-rate resetting protocol
depend both on scale and failure probability; see Fig. 3. On
the one hand, in contrast to the scale-free resetting protocol,
the MCT is in this case finite for any p. On the other hand, fora given value of the resetting rate, the completion time is very
sensitive to τ0 .
To sum up, sharp resetting is the most efficient resetting
protocol in a well-known, static environment (search problem). However, such a protocol is highly sensitive to thetimescale of the search problem and may easily fail in the caseof an imperfect knowledge or fluctuating environment. If thesefluctuations (or ignorance) are not too large and the averagetimescale is known, then constant-rate stochastic resets areadvantageous. Otherwise, scale-free resets may be of great
advantage, since they are robust to the timescale of the search
problem.

3. Trade-off

4. Generalizations

Our results suggest that resetting protocols entail a natural
trade-off between sensitivity of the protocol outcomes to two
distinct features of the completion times of the underlying
search problem: its timescale and the shape of its tail. It isconvenient, in this context, to analyze the survival probabilityof the completion times. The tail of the survival probability
captures both probability of large fluctuations and the failure
probability, i.e., in the case of a nonzero failure probability,
the survival probability does not decay to zero.
The scale-free resetting is robust to the timescale. However,
the timescale robustness does not come without a price: dueto the ever-growing intervals between succeeding resets, thisprotocol is rather sensitive to the tail of the distribution. In
the case of a one-dimensional diffusive search, the survival
probability of the completion times has a power-law tail∼t −1/2 . The scale-free resetting to some extent tempers thetail, leading to a finite value of the MCT for α > 21 . However,the fluctuations of the completion times are still large, withthe survival probability ∼t −1/2−α . Thus, the variance diverges
for α  23 . Similarly, the scale-free resetting is sensitive tothe failure probability: as shown above, to retain a finite
MCT, α has to be larger than 1/p, where 1 − p is the failure
probability; see Fig. 3.
At the other extreme is the sharp resetting protocol. Indeed,
the optimal sharp resetting shows shorter MCTs and lower
relative fluctuations than any stochastic resetting in a known
search environment [35]. Additionally, it is easy to show thatthe optimal sharp protocol does not depend on the failure
probability p. However, sharp resets are at the same time
extremely sensitive to the timescale of the search process. In
the case of diffusion they lead to divergent MCTs for any
Laplace distribution of x0 [55].
Within the framework of the discussed trade-off, constantrate resetting is placed in between sharp resetting and scalefree resetting. In the case of diffusion, fluctuations of the completion times are strongly reduced by this kind of resetting—all moments are finite for any r [1,35]. In the simple case of
constant time failure model Eq. (31) its MCT reads

The constant-rate and scale-free resetting protocols are
special cases of the general family of resetting protocols of
the form r(t ) = α/t μ , introduced in Section II B. As shown
therein, supplementing diffusion with such a resetting protocol with μ < 1 gives rise to the subdiffusive behavior. Thus,
this protocol introduces a timescale and, for a fixed α, its
MCT scales superlinearly with τ0 . It is therefore not robust, as
the optimal α depends on τ0 . Nonetheless, this protocol may
still be efficient in some search problems. Since in the limitof μ → 0 the standard constant-resetting case is recovered,in search problems with large variability one can expectthat the fluctuations of the completion times are smaller for
lower values of μ. Thus, the subdiffusive protocol may prove
useful in the context of balancing the trade-off discussed inSec. III D 3. The rich family of models with absolute-timedependent stochastic resetting and the associated trade-off
will be the subject of a separate study.


1 erτ0−1 .
Tconst =rp(42)

IV. CONCLUSIONSWe envision multiple applications of scale-free resetting,especially in optimization problems. For instance, it seems
natural to ask about its relation to simulated annealing [57],and its applicability in evolutionary algorithms [6,7], deeplearning via gradient methods [8,58], and biologically plausible learning techniques with three factors [59,60]. The
robustness of the scale-free resetting protocol should offer
additional benefits in the nonstationary setup of curriculum
learning [61] and could potentially offer an explanation as
to why aging [62,63] may be useful in learning. Of course
the practical optimization problems are high-dimensional andthus the general renewal framework Eq. (8) should prove
useful in the construction and analysis of the practical algorithms. Another interesting avenue of possible applications
are models of evidence accumulation and decision making[64,65], as recently it was shown that stationary resets canmodify splitting probabilities [66]. Restarts in this context
may be interpreted as useful forgetting [67,68].
A number of open problems are left for future studies. To assess the efficiency of the proposed scheme, one
could compare it to diffusion in time-dependent, scale-free

032110-6

ROBUST RANDOM SEARCH WITH SCALE-FREE …

PHYSICAL REVIEW E 100, 032110 (2019)potentials—such comparison in the case of static potentials
and resets seems to favor the latter [54,55]. Moreover, it
is important to find conditions under which scale-free resets can lower the expected completion time, similar to thesimple criterion in the case of constant-rate resets [1,32,69].
A related question is how the optimal α depends on thedetails of a search problem at hand. Another important issue
is the divergence of Eq. (2) at t = 0 which is infeasible
and in practice a short-time cutoff has to be introduced.

The optimal cut-off should depend on a cost associated withresets.

[1] S. Reuveni, Phys. Rev. Lett. 116, 170601 (2016).
[2] Y. Huang, C. Kintala, N. Kolettis, and N. D. Fulton, Software rejuvenation: Analysis, module, and applications, in Proceedingsof the International Symposium on Fault-Tolerant Computing(FTCS’95) (IEEE, Piscataway, NJ, 1995), p. 0381.
[3] T. Dohi, K. Goševa-Popstojanova, and K. Trivedi, Comput. J.
44, 473 (2001).
[4] A. P. Van Moorsel and K. Wolter, IEEE Trans. Software Eng.
547 (2006).
[5] H. Okamura and T. Dohi, J. Jpn. Ind. Manage. Assoc. 66, 416(2016).
[6] A. S. Fukunaga, Restart scheduling for genetic algorithms, inProceedings of the International Conference on Parallel Problem Solving from Nature (Springer, Berlin, 1998), pp. 357–366.
[7] T. Jansen, On the analysis of dynamic restart strategies forevolutionary algorithms, in Proceedings of the International
Conference on Parallel Problem Solving from Nature (Springer,
Berlin, 2002), pp. 33–43.
[8] M. A. Luersen and R. Le Riche, Comput. Struct. 82, 2251
(2004).
[9] I. Loshchilov and F. Hutter, in Proc. of the International Conference on Learning Representations, 2017 (Toulon, France, 2017),
arXiv:1608.03983.
[10] M. R. Evans and S. N. Majumdar, Phys. Rev. Lett. 106, 160601(2011).
[11] M. R. Evans and S. N. Majumdar, J. Phys. A: Math. Theor. 47,
285001 (2014).
[12] V. Méndez and D. Campos, Phys. Rev. E 93, 022106 (2016).
[13] S. Eule and J. J. Metzger, New J. Phys. 18, 033006 (2016).
[14] C. Christou and A. Schadschneider, J. Phys. A: Math. Theor.
48, 285003 (2015).
[15] A. Chatterjee, C. Christou, and A. Schadschneider, Phys. Rev.
E 97, 062106 (2018).
[16] A. Pal and V. Prasad, Phys. Rev. E 99, 032123 (2019).
[17] A. Pal, Phys. Rev. E 91, 012113 (2015).
[18] L. Kusmierz, S. N. Majumdar, S. Sabhapandit, and G. Schehr,
Phys. Rev. Lett. 113, 220602 (2014).
[19] Ł. Kuśmierz and E. Gudowska-Nowak, Phys. Rev. E 92, 052127(2015).
[20] V. P. Shkilev, Phys. Rev. E 96, 012126 (2017).
[21] M. Montero, A. Masó-Puigdellosas, and J. Villarroel, Eur. Phys.
J. 90, 176 (2017).
[22] A. S. Bodrova, A. V. Chechkin, and I. M. Sokolov, Phys. Rev.
E 100, 012120 (2019).
[23] A. S. Bodrova, A. V. Chechkin, and I. M. Sokolov, Phys. Rev.
E 100, 012119 (2019).

[24] Ł. Kuśmierz and E. Gudowska-Nowak, Phys. Rev. E 99, 052116(2019).
[25] S. Ray, D. Mondal, and S. Reuveni, J. Phys. A: Math. Theor.
52, 255002 (2019).
[26] M. R. Evans and S. N. Majumdar, J. Phys. A: Math. Gen. 52,
01LT01 (2018).
[27] A. Masó-Puigdellosas, D. Campos, and V. Méndez, J. Stat.
Mech.: Theory Exp. (2019) 033201.
[28] A. Pal, Ł. Kuśmierz, and S. Reuveni, arXiv:1906.06987 (2019).
[29] A. Nagar and S. Gupta, Phys. Rev. E 93, 060102(R) (2016).
[30] A. Pal, A. Kundu, and M. R. Evans, J. Phys. A: Math. Theor.
49, 225001 (2016).
[31] J. Fuchs, S. Goldt, and U. Seifert, EPL 113, 60009 (2016).
[32] T. Rotbart, S. Reuveni, and M. Urbakh, Phys. Rev. E 92,
060101(R) (2015).
[33] S. Gupta, S. N. Majumdar, and G. Schehr, Phys. Rev. Lett. 112,220601 (2014).
[34] S. C. Manrubia and D. H. Zanette, Phys. Rev. E 59, 4945
(1999).
[35] A. Pal and S. Reuveni, Phys. Rev. Lett. 118, 030603 (2017).
[36] We are assuming that the initial position corresponds to theresetting position. However, due to the singular behavior of
the function r(t ) at t = 0, the choice of the initial position isinconsequential: If it does not match the resetting position, thenthe probability mass is transferred to the resetting position in an
infinitesimal time.
[37] B. Wang, S. M. Anthony, S. C. Bae, and S. Granick, Proc. Natl.
Acad. Sci. USA 106, 15160 (2009).
[38] B. Wang, J. Kuo, S. C. Bae, and S. Granick, Nat. Mater. 11, 481(2012).
[39] S. Hapca, J. W. Crawford, and I. M. Young, J. R. Soc. Interface
6, 111 (2008).
[40] M. V. Chubynsky and G. W. Slater, Phys. Rev. Lett. 113,098302 (2014).
[41] A. V. Chechkin, F. Seno, R. Metzler, and I. M. Sokolov, Phys.
Rev. X 7, 021002 (2017).
[42] V. Sposini, A. V. Chechkin, F. Seno, G. Pagnini, and R. Metzler,
New J. Phys. 20, 043044 (2018).
[43] D. Boyer and C. Solis-Salas, Phys. Rev. Lett. 112, 240601(2014).
[44] E. W. Montroll and G. H. Weiss, J. Math. Phys. 6, 167 (1965).
[45] R. Metzler and J. Klafter, Phys. Rep. 339, 1 (2000).
[46] M. Magdziarz and A. Weron, Phy. Rev. E 75, 056702 (2007).
[47] D. Campos and V. Méndez, Phys. Rev. E 92, 062115 (2015).
[48] Note that multiple different renewal approaches to processes
with resetting have been proposed [1, 33, 35, 70]. Our approach

ACKNOWLEDGMENTS

We are indebted to Shun Ogawa for stimulating discussions. This work was supported by RIKEN Center for
Brain Science, Brain/MINDS from AMED under Grant No.
JP19dm020700 and JSPS KAKENHI Grant No. JP18H05432.

032110-7ŁUKASZ KUŚMIERZ AND TARO TOYOIZUMIPHYSICAL REVIEW E 100, 032110 (2019)is closely related to a discrete-time counterpart applied inRef. [18].
[49] S. Redner, A Guide to First-passage Processes (Cambridge
University Press, Cambridge, 2001).
[50] The integral operator in Eqs. (17) and (18) corresponds to the
Riemann-Liouville fractional integral. Similarly, the integral in
Eq. (19) can be expressed by means of the Caputo fractional
derivative.
[51] We could have also applied Eq. (18) directly with β = α − 2.
The resulting equation is simpler, but holds only for α > 1.
[52] R. Mannella, Phys. Lett. A 254, 257 (1999).
[53] In general resetting protocols may form a feedback loop that
depend on the state of the system (e.g., current position x in thecase of diffusion [71]).
[54] M. R. Evans, S. N. Majumdar, and K. Mallick, J. Phys. A: Math.
Theor. 46, 185001 (2013).
[55] Ł. Kuśmierz, M. Bier, and E. Gudowska-Nowak, J. Phys. A:
Math. Theor. 50, 185003 (2017).
[56] R. G. Pinsky, arXiv:1803.10463 (2018).
[57] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671(1983).
[58] Y. LeCun, Y. Bengio, and G. Hinton, Nature 521, 436(2015).

[59] N. Frémaux and W. Gerstner, Front. Neural Circ. 9, 85 (2016).
[60] Ł. Kuśmierz, T. Isomura, and T. Toyoizumi, Curr. Opin.
Neurobiol. 46, 170 (2017).
[61] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, Curriculum learning, in Proceedings of the 26th Annual International
Conference on Machine Learning (ACM, New York, NY, 2009),
pp. 41–48.
[62] J. Villain, J. Phys. C: Solid State Phys. 10, 1717 (1977).
[63] R. Metzler, J.-H. Jeon, A. G. Cherstvy, and E. Barkai, Phys.
Chem. Chem. Phys. 16, 24128 (2014).
[64] R. Bogacz, E. Brown, J. Moehlis, P. Holmes, and J. D. Cohen,
Psychol. Rev. 113, 700 (2006).
[65] S. Tajima, J. Drugowitsch, and A. Pouget, Nat. Commun. 7,12400 (2016).
[66] S. Belan, Phys. Rev. Lett. 120, 080601 (2018).
[67] J. T. Wixted, Annu. Rev. Psychol. 55, 235 (2004).
[68] O. Hardt, K. Nader, and L. Nadel, Trends Cognit. Sci. 17, 111(2013).
[69] S. Reuveni, M. Urbakh, and J. Klafter, Proc. Natl. Acad. Sci.
USA 4391 (2014).
[70] A. Chechkin and I. M. Sokolov, Phys. Rev. Lett. 121, 050601(2018).
[71] R. G. Pinsky, arXiv:1805.00320 (2018).

032110-8