Tail-behavior roadmap for sharp restart

Abstract

Many tasks are accomplished via random processes. The completion time of such a task can be profoundly affected by restart: the occasional resetting of the task's underlying random process. Consequently, determining when restart will impede or expedite task completion is a subject of major importance. In recent years researchers explored this subject extensively, with main focus set on average behavior, i.e. on mean completion times. On the one hand, the mean approach asserts the centrality of "sharp restart" -- resetting with deterministic (fixed) timers. On the other hand, a significant drawback of the mean approach is that it provides no insight regarding tail behavior, i.e. the occurrence likelihood of extreme completion times. Addressing sharp restart, and shifting the focus from means to extremes, this paper establishes a comprehensive tail-behavior analysis of completion times. Employing the reliability-engineering notion of hazard rate, the analysis yields a set of universal results that determine -- from a tail-behavior perspective -- when sharp restart will impede or expedite task completion. The universal results are formulated in terms of explicit and highly applicable hazard-rate criteria. With the novel results at hand, a universal average-&-tail classification manual for sharp restart is devised. The manual specifies general scenarios in which -- rather counter-intuitively -- sharp restart has an opposite effect on average behavior and on tail behavior: decreasing mean completion times while dramatically increasing the likelihood of extreme completion times; and, conversely, increasing mean completion times while dramatically decreasing the likelihood of extreme completion times.

References in corpus (37)

• Power-law distributions in empirical data
• Power laws, Pareto distributions and Zipf's law
• Diffusion with Stochastic Resetting
• Stochastic Resetting and Applications
• First Passage Under Restart
• Biological Evolution and Statistical Physics
• First order transition for the optimal search time of Lévy flights with resetting
• Experimental realization of diffusion with stochastic resetting
• Diffusion under time-dependent resetting
• Stochastic resetting in backtrack recovery by RNA polymerases
• Diffusion with stochastic resetting at power-law times
• The Michaelis-Menten reaction scheme as a unified approach towards the optimal restart problem
• Optimal first arrival times in Lévy flights with resetting
• Optimal diffusive search: nonequilibrium resetting versus equilibrium dynamics
• Boosting search by rare events
• Stochastic Search with Poisson and Deterministic Resetting
• Search with home returns provides advantage under high uncertainty
• Monotonous continuous-time random walks with drift and stochastic reset events
• Resetting processes with non-instanteneous return
• Effects of refractory period on stochastic resetting
• Scaled Brownian motion with renewal 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
• Random Walks in Logarithmic and Power-Law Potentials, Nonuniversal Persistence, and Vortex Dynamics in the Two-Dimensional XY Model
• Diffusion with resetting in a logarithmic potential
• Landau theory of restart transitions
• First passage under restart with branching
• Non-renewal resetting of scaled Brownian motion
• On subdiffusive continuous time random walks with stochastic resetting
• Stochastic processes subject to a reset-and-residence mechanism: transport properties and first arrival statistics
• Heavy tails in the distribution of time-to-solution for classical and quantum annealing
• Mean-performance of sharp restart I: Statistical roadmap
• Stochastic resetting antiviral therapies prevents drug resistance development
• Robust random search with scale-free stochastic resetting
• Reaction-diffusion with stochastic decay rates
• Median and Mode in First Passage under Restart

Cited by in corpus (10)

• The inspection paradox in stochastic resetting
• Restart expedites quantum walk hitting times
• Stochastic resetting by a random amplitude
• Mitigating long queues and waiting times with service resetting
• Instability in the quantum restart problem
• Diversity of Sharp Restart
• Resonances of recurrence time of monitored quantum walks
• Entropy of Sharp Restart
• Accelerated first detection in discrete-time quantum walks using sharp restarts
• Arcsine laws for Brownian motion with Poissonian resetting