Mean-performance of sharp restart: II. Inequality roadmap

DOI10.1088/1751-8121/AC16C5MaRDI QIDQ5877427zbMATH OpenOpenAlexWikidataFDO

Authors Shlomi Reuveni, Iddo I. Eliazar

Publication date 13 February 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.13154

zbMATH Keywords

restartfirst-passage timesinequality indicesLorenz curvesresetting

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: Restarting a deterministic process always impedes its completion. However, it is known that restarting a random process can also lead to an opposite outcome -- expediting completion. Hence, the effect of restart is contingent on the underlying statistical heterogeneity of the process' completion times. To quantify this heterogeneity we bring a novel approach to restart: the methodology of inequality indices, which is widely applied in economics and in the social sciences to measure income and wealth disparity. Using this approach we establish an `inequality roadmap' for the mean-performance of sharp restart: a whole new set of universal inequality criteria that determine when restart with sharp timers (i.e. with fixed deterministic timers) decreases/increases mean completion. The criteria are based on a host of inequality indices including Bonferroni, Gini, Pietra, and other Lorenz-curve indices; each index captures a different angle of the restart-inequality interplay. Utilizing the fact that sharp restart can match the mean-performance of any general restart protocol, we prove -- with unprecedented precision and resolution -- the validity of the following statement: restart impedes/expedites mean completion when the underlying statistical heterogeneity is low/high.

Recommendations

• Mean-performance of sharp restart I: statistical roadmap
• RESTART distributions and an asymptotically exact random algorithm for solution of problems of discrete optimization
• Restart strategies in optimization: parallel and serial cases
• scientific article; zbMATH DE number 1142348
• scientific article; zbMATH DE number 4072264
• On the efficiency of RESTART for multidimensional state systems
• Methods to compare expensive stochastic optimization algorithms with random restarts
• On accuracy and efficiency of constrained reinitialization

Cites work

• scientific article; zbMATH DE number 3133146 (Why is no real title available?)
• scientific article; zbMATH DE number 3215084 (Why is no real title available?)
• A General Definition of the Lorenz Curve
• A guide to first-passage processes
• A proposal of poverty measures based on the Bonferroni inequality index
• A tour of inequality
• Average is over
• Beyond lognormal inequality: the Lorenz flow structure
• Bonferroni and Gini indices for various parametric families of distributions
• Call center service times are lognormal: a Fokker-Planck description
• Celebrating the Memory of Corrado Gini: a Personality Out of the Ordinary
• Diffusion under time-dependent resetting
• Diffusion with optimal resetting
• First-passage phenomena and their applications
• From Gini to Bonferroni to Tsallis: an inequality-indices trek
• Gini's scientific work: an evergreen
• Harnessing inequality
• Human behavior and lognormal distribution. A kinetic description
• Inequality spectra
• Investigating equality: the Rényi spectrum
• Mean-performance of sharp restart I: statistical roadmap
• Modeling Income Distributions and Lorenz Curves
• On the generalization and decomposition of the Bonferroni index
• Optimization and growth in first-passage resetting
• Parametric Lorenz Curves: Models and Applications
• Péclet number governs transition to acceleratory restart in drift-diffusion
• Statistical Analysis of a Telephone Call Center
• Stochastic movement subject to a reset-and-residence mechanism: transport properties and first arrival statistics
• Stochastic resetting and applications
• Stochastic search with Poisson and deterministic resetting
• The Gini methodology. A primer on a statistical methodology.
• The relationship between the absolute deviation from a quantile and Gini's mean difference

Cited in

(10)

• Arcsine laws for Brownian motion with Poissonian resetting
• Bernoulli trial under subsystem restarts: two competing searchers looking for a target
• Selfsimilarity of diffusions’ first passage times
• Diversity of sharp restart
• Entropy of sharp restart
• Beautiful Gini
• Restart strategies and Internet congestion
• Mean-performance of sharp restart I: statistical roadmap
• Tail-behavior roadmap for sharp restart
• The inspection paradox in stochastic resetting

This page was built for publication: Mean-performance of sharp restart: II. Inequality roadmap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5877427)