Optimal Stochastic Restart Renders Fluctuations in First Passage Times Universal

Stochastic restart may drastically reduce the expected run time of a computer algorithm, expedite the completion of a complex search process, or increase the turnover rate of an enzymatic reaction. These diverse first-passage-time (FPT) processes seem to have very little in common but it is actually quite the other way around. Here we show that the relative standard deviation associated with the FPT of an optimally restarted process, i.e., one that is restarted at a constant (nonzero) rate which brings the mean FPT to a minimum, is always unity. We interpret, further generalize, and discuss this finding and the implications arising from it.

Figure 1

(a) An illustration of diffusion mediated search at time $t=0$. (b) The mean FPT to target as a function of the restart rate for different values of $D/L^2$. The higher this ratio is the higher the value of the optimal restart rate $r^{*}$ which brings $⟨T_r⟩$ to a minimum (see positions marked with full circles). Inset. The relative standard deviation in the FPT as a function of the restart rate (normalized by the optimal restart rate).

Figure 2

An illustration of a generic process subject to stochastic restart.

Figure 3

The mean (solid lines) and standard deviation (dashed lines) in the FPT of a restarted process as a function of the restart rate. Plots are made using Eq. (7) for three different time distributions of the underlying process subject to restart: (i) Fréchet distribution $Pr(T\le t)=e^{-t^{-\alpha }}(t>0)$, with $\alpha =1$; (ii) Log-normal distribution $Pr(T\le t)={\int }_0^t{[x\sigma \sqrt{2\pi }]}^{-1}\exp [-(\ln (x)-\mu {)}^2/2{\sigma }^2]dx(t>0)$, with $\mu =1$ and $\sigma =1.2$; (iii) Log-logistic distribution $Pr(T\le t)={[1+{(t/\alpha )}^{-\beta }]}^{-1}(t>0)$, with $\alpha =3.4$ and $\beta =1.45$. Equation (4) asserts that $\sigma (T_r)$ will cut $⟨T_r⟩$ at the exact point at which the latter attains its minimum.

Figure 4

The distribution of $T_{r^{*}}/⟨T_{r^{*}}⟩$ is nonuniversal. Consider a generalization of diffusion with stochastic restart. Letting $\tilde{T}(s)=e^{{-(\tau s)}^{\alpha }}$ we note that for $\tau =L^2/D$ and $\alpha =1/2$ we have the Laplace transform of the Lévy-Smirnov distribution discussed above, and in general for $0<\alpha <1$ the Laplace transform of the one sided Lévy distribution [35]. In Ref. [49] we showed that the optimal restart rate for this distribution is given by $r^{*}=(z^{*}{)}^{1/\alpha }/\tau$, where $z^{*}$ is the solution to $\alpha z=1-e^{-z}$. This now allows us to compute $⟨T_{r^{*}}⟩$ and plot $⟨e^{-s{T}_{r^{*}}/⟨T_{r^{*}}⟩}⟩$ for different values of $\alpha$ while fixing $\tau =1$ for convenience. It is clearly visible that while all curves fall on top of each other, and on top of ${(1+s)}^{-1}$, for $s\ll 1$ their behavior for $s\gg 1$ depends on the value of $\alpha$.

Figure 5

The mean and standard deviation of $T_r$ for three different cases of diffusion mediated search with stochastic restart and time overheads. In all three cases $\tilde{T}(s)=e^{-\sqrt{s}}$ ($L^2/D=1$), $⟨T_{\mathrm{on}}⟩=1$, and $⟨T_r⟩$ is hence one and the same. The standard deviations ${\sigma }_i(T_r)$ are, however, quite distinct since here we chose ${\sigma }_i^2(T_{\mathrm{on}})=i-1$ for $i=1$, 2, 3. These values could, for example, be associated with sharp (deterministic), exponential, and Gamma distributed delays (in this order). Note that in all three cases ${\sigma }_i(T_{r^{*}})=\sqrt{{⟨T_{r^{*}}⟩}^2+[{\sigma }_i^2(T_{\mathrm{on}})-{⟨T_{\mathrm{on}}⟩}^2]/\tilde{T}(r^{*})}$ in accord with Eq. (10).