Universal performance bounds of restart

Abstract

As has long been known to computer scientists, the performance of probabilistic algorithms characterized by relatively large runtime fluctuations can be improved by applying a restart, i.e., episodic interruption of a randomized computational procedure followed by initialization of its new statistically independent realization. A similar effect of restart-induced process acceleration could potentially be possible in the context of enzymatic reactions, where dissociation of the enzyme-substrate intermediate corresponds to restarting the catalytic step of the reaction. To date, a significant number of analytical results have been obtained in physics and computer science regarding the effect of restart on the completion time statistics in various model problems, however, the fundamental limits of restart efficiency remain unknown. Here we derive a range of universal statistical inequalities that offer constraints on the effect that restart could impose on the completion time of a generic stochastic process. The corresponding bounds are expressed via simple statistical metrics of the original process such as harmonic mean $h$, median value $m$ and mode $M$, and, thus, are remarkably practical. We test our analytical predictions with multiple numerical examples, discuss implications arising from them and important avenues of future work.

arXiv comment12 pages, 2 figures

References in corpus (41)

• Diffusion with Stochastic Resetting
• Stochastic Resetting and Applications
• Diffusion with Optimal Resetting
• First Passage Under Restart
• First order transition for the optimal search time of Lévy flights with resetting
• Optimal stochastic restart renders fluctuations in first passage times universal
• Experimental realization of diffusion with stochastic resetting
• Diffusion under time-dependent resetting
• Run and tumble particle under resetting: a renewal approach
• Diffusion with resetting in arbitrary spatial dimension
• Diffusion with stochastic resetting at power-law times
• Non-equilibrium steady states of stochastic processes with intermittent resetting
• The Michaelis-Menten reaction scheme as a unified approach towards the optimal restart problem
• Optimal first arrival times in Lévy flights with resetting
• Boosting search by rare events
• Restart could optimize the probability of success in a Bernoulli trial
• Resetting processes with non-instanteneous return
• Effects of refractory period on stochastic resetting
• The inspection paradox in stochastic resetting
• First passage of a particle in a potential under stochastic resetting: a vanishing transition of optimal resetting rate
• Péclet number governs transition to acceleratory restart in drift-diffusion
• Single-molecule theory of enzymatic inhibition predicts the emergence of inhibitor-activator duality
• Diffusion with resetting in a logarithmic potential
• Landau theory of restart transitions
• Effect of Partial Absorption on Diffusion with Resetting
• Diffusion with stochastic resetting is invariant to return speed
• Run-and-Tumble particles in Two-dimensions under Stochastic Resetting
• First passage under restart for discrete space and time: application to one dimensional confined lattice random walks
• Random acceleration process under stochastic resetting
• First passage in the presence of stochastic resetting and a potential barrier
• Brownian motion under non-instantaneous resetting in higher dimensions
• Robust random search with scale-free stochastic resetting
• First passage of a diffusing particle under stochastic resetting in bounded domains with spherical symmetry
• Median and Mode in First Passage under Restart
• Mean-performance of Sharp Restart II: Inequality Roadmap
• Role of dimensions in first passage of a diffusing particle under stochastic resetting and attractive bias
• Searching for clusters of targets under stochastic resetting
• Diversity of Sharp Restart
• SUNNY-CP and the MiniZinc Challenge
• Entropy of Sharp Restart
• The one-dimensional telegraphic process with noninstantaneous stochastic resetting

Cited by in corpus (3)

• Stochastic Resetting for Enhanced Sampling
• Optimal conditions for first passage of jump processes with resetting
• First passage time in space-dependent stochastic resetting