Source-linked AI summary
First Passage Under Restart
Arnab Pal, Shlomi Reuveni
TL;DR
The paper develops a generic treatment of first-passage processes under stochastic restart, deriving relations that hold for arbitrary restart-time distributions and broad first-passage-time origins. It shows that the framework extends results to sharp restart times regardless of optimality and to any restart-time distribution.
Problem
Existing first-passage analyses must account for processes and restart mechanisms with potentially arbitrary distributions and origins.
Method
The paper uses indicator variables, renewal-process residual-time averages, and expectations over first-passage and restart times to derive general relations.
Results
The derived relations hold for every stochastic restart time regardless of its distribution and generalize earlier results to sharp restart times regardless of optimality.
Takeaways & Limitations
First-passage behavior under restart can be analyzed through relations that remain valid across restart-time distributions and restart optimality.
Takeaways & Limitations
The derivations assume independence between the restart variables and the first-passage time, and one result additionally assumes σ(T) / ⟨T⟩ > 1.
Abstract
from arXiv · showhide
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.
Supplementary
The supplementary material is dated 16 December 2016.
- 16 December 2016 is the supplementary material’s date.
First Passage Under Restart
The paper is authored by Arnab Pal and Shlomi Reuveni, with affiliations at Technion and Harvard Medical School.
- Arnab Pal and Shlomi Reuveni are the paper’s authors.
- Pal is affiliated with the Schulich Faculty of Chemistry at Technion–Israel Institute of Technology in Haifa.
- Reuveni is affiliated with the Department of Systems Biology at Harvard Medical School in Boston.
1 Derivation of Eq. (4) in main text
The supplementary derivation uses conditional expectations and an optimal sharp restart time to establish a result that applies to every stochastic restart time, regardless of its distribution.
- The derivation uses the law of total expectation to analyze stochastic restart strategies.
- An optimal sharp restart time is defined as a deterministic time t* satisfying the stated inequality for all t > 0.
- The resulting comparison holds for every stochastic restart time and regardless of its distribution.
2 Derivation of Eq. (5) in main text
The supplementary derivation obtains Eq. (5) by decomposing restarted completion times and using an independent identically distributed copy of the restarted process; it then specializes the result to exponential restart.
- The derivation of Eq. (5) begins by expanding the restarted completion-time expression and rearranging the resulting relation.
- The restarted process is represented using an independent and identically distributed copy that is independent of both R and T.
- For exponentially distributed restart time R, the density is substituted into Eq. (5) to recover the main-text result.
3 Derivation of Eq. (7) in main text
The derivation of Eq. (7) uses Laplace-transform moment expansions and derivatives at s → 0 to recover the second-moment relation for the minimum of completion and restart times.
- Result: Differentiating the transform relations and rearranging terms recovers Eq. (7) in the main text.The text states that the resulting expression coincides with Eq. (7).
- Derivation: The second moment of min(T,R) decomposes according to whether completion or restart occurs first.⟨min(T, R)^2⟩ is expressed using conditional second moments weighted by Pr(T < R) and Pr(R ≤ T).
- Derivation: Laplace-transform moment expansions provide an alternative derivation of Eq. (7).The derivation recalls the moment expansion, differentiates the relevant transform, and takes the limit s → 0.
4 Derivation of Eq. (8) in main text
The derivation expands the Laplace transform of the completion-time distribution at low restart rate and shows that sufficiently weak constant-rate restart lowers the mean FPT when relative fluctuations exceed unity.
- Result: When σ(T) / ⟨T⟩ > 1 and r is sufficiently small, constant-rate restart lowers the mean first passage time.The derivation explicitly imposes the relative-fluctuation condition and the small-rate regime.
- Derivation: Low-rate expansion of ˜T(r) determines the behavior of the restarted mean FPT as r → 0.The expansion is substituted into the restarted-process expression to obtain the limiting behavior.
- Scope: The result assumes no particular origin or distribution for T beyond σ(T) / ⟨T⟩ > 1.T may itself arise from a process already subject to restart, although the text discusses a boundary for optimal sharp restart.
5 Details of distributions in Fig. 5
The figure plots distributions including the Lévy-Smirnov distribution, identified as the first-passage-time distribution of diffusion-mediated search.
- Distributions: The plotted distributions include the Lévy-Smirnov distribution.It is identified as the FPT distribution of diffusion mediated search.
- Distributions: The Lévy-Smirnov distribution represents the first-passage-time distribution of diffusion-mediated search.
6 Derivation and probabilistic interpretation of Eq. (9) in main text
The derivation of Eq. (9) compares completion and restart through residual waiting times and event probabilities. Its probabilistic interpretation explains how an infinitesimal external restart rate can increase, reduce, or leave the mean FPT unchanged.
- Probabilistic interpretation: Introducing an infinitesimal external restart eventually restarts the process at a random point in time, after which the expected completion time is approximately ⟨T_R⟩.This expected time is compared with completion without exogenous restart.
- Probabilistic interpretation: The resulting change in mean FPT depends on relative fluctuations: weak restart lowers it when σ(T_R) / ⟨T_R⟩ > 1 and otherwise increases or leaves it unchanged.This interpretation is stated for a process already subject to restart.
- Derivation: For a process observed at a random time, the relevant waiting time is the mean residual time until restart or completion.For renewal processes, this residual time generally differs from the initial mean min(T,R).
- Derivation: The probability that restart occurs from a randomly observed, aged process is weighted by the restart residual-time contribution.The text contrasts this with the immediate-after-start probability Pr(R ≤ T).
- Probabilistic interpretation: The fraction of the time axis ending in restart is Pr(T < R)⟨T_min⟩ + Pr(R ≤ T)⟨R_min⟩.This expression is identified as the exact relative fraction of time spans ending with endogenous restart rather than completion.
- Result: A low restart rate increases or leaves unchanged the mean FPT whenever the residual-time inequality in Eq. (9) holds.The derivation substitutes the expressions for ⟨T_res⟩ and ⟨T_R⟩ and rearranges to recover Eq. (9).
7 Numerical exploration of Eq. (9) in the main text
Numerical examples test Eq. (9) across several first-passage and restart-time distributions. The results support its validity for sharp and non-sharp restart, independently of restart-time optimality.
- Sharp restart examples: For sharp restart, Eq. (9) generalizes Eq. (8) regardless of whether the restart time is optimal.The relation holds for ⟨min(T,R)⟩ for every t ≥ 0.
- Sharp restart examples: Eq. (9) is numerically demonstrated for the three cases considered in Fig. 5: Lévy-Smirnov, Fréchet, and Log-Logistic.Figure S1 revisits the Fig. 5 examples with sharp restart.
- Non-sharp restart distributions: Eq. (9) is also tested with Uniform, Gamma, and Weibull restart-time distributions, and holds in all three cases regardless of the optimality of ⟨R⟩.Figure S2 examines restart distributions other than the sharp, including Gamma, Uniform, and Weibull forms.