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 (9)

• Power-law distributions in empirical data
• First Passage Under Restart
• First order transition for the optimal search time of Lévy flights with resetting
• Experimental realization of diffusion with stochastic resetting
• Stochastic Search with Poisson and Deterministic Resetting
• Monotonous continuous-time random walks with drift and stochastic reset events
• Diffusion with resetting in a logarithmic potential
• Mean-performance of sharp restart I: Statistical roadmap
• Stochastic resetting antiviral therapies prevents drug resistance development

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