First Passage under Restart

First passage under restart has recently emerged as a conceptual framework suitable for the description of a wide range of phenomena, but the endless variety of ways in which restart mechanisms and first passage processes mix and match hindered the identification of unifying principles and general truths. Hope that these exist came from a recently discovered universality displayed by processes under optimal, constant rate, restart—but extensions and generalizations proved challenging as they marry arbitrarily complex processes and restart mechanisms. To address this challenge, we develop a generic approach to first passage under restart. Key features of diffusion under restart—the ultimate poster boy for this wide and diverse class of problems—are then shown to be completely universal.

Figure 1

(Top) Bad weather could force a team of searchers to temporarily cease their efforts and return to base. By the time search is renewed the target may have relocated and search must thus start from scratch. (Middle) A computer algorithm operates as a black box which randomly scans a tree of possibilities in search of a solution. Chance may send the algorithm down the wrong path, but programmed restart could help rescue the search. (Bottom) A molecule that was previously prepared at an excited state decays to a low energy state. A pulse of laser could bring the molecule back to its excited state and restart a chemical or physical reaction. This time, the desired product may be formed.

Figure 2

A few examples of restart time distributions (left) and the restart rates they induce (right). Below $\delta (x)$ is the Dirac delta function, $\mathrm{\Gamma }(x)$ is the Gamma function, and $⟨R⟩=1$ in all plots. (i) Sharp (deterministic) restart $f_R(t)=\delta (t-⟨R⟩)$. Restart rate jumps abruptly from zero to infinity at $t=⟨R⟩$. (ii) Exponentially distributed restart $f_R(t)={⟨R⟩}^{-1}{e}^{-t/⟨R⟩}$. Restart rate is constant: $r(t)=1/⟨R⟩$, (iii) and (iv) Weibull distributed restart $f_R(t)=k/\lambda {(t/\lambda )}^{k-1}{e}^{-{(t/\lambda )}^k}$. Restart rate is given by $r(t)=k{t}^{k-1}/{\lambda }^k$ and could monotonically decrease (e.g., $k=1/2$, $\lambda =⟨R⟩/2$) or increase [e.g., $k=3/2$, $\lambda =⟨R⟩/\mathrm{\Gamma }(5/3)$] with time.

Figure 3

Mean FPT for diffusion mediated search with restart versus the mean restart time, for various restart time distributions taken from Fig. 2.

Figure 4

Two approaches to first passage under restart.

Figure 5

The mean (solid lines) and standard deviation (dashed lines) of the restarted FPT $T_t$ versus the sharp restart time $t$, for various distributions of the underlying FPT $T$ (see SM for details [44]).