Mean-performance of sharp restart: II. Inequality roadmap

DOI10.1088/1751-8121/AC16C5zbMATH Open1505.82030arXiv2102.13154OpenAlexW3210794412WikidataQ122420462 ScholiaQ122420462MaRDI QIDQ5877427FDOQ5877427

Iddo I. Eliazar, Shlomi Reuveni

Publication date: 13 February 2023

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

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.

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

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

zbMATH Keywords

restartfirst-passage timesinequality indicesLorenz curvesresetting

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Selfsimilarity of diffusions’ first passage times
• Diversity of sharp restart
• Entropy of sharp restart
• 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)