Greedy algorithms and Zipf laws

DOI10.1088/1742-5468/AAB50AMaRDI QIDQ4964565zbMATH OpenOpenAlexWikidataFDO

Authors José Moran, Jean-Philippe Bouchaud

Publication date 2 March 2021

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Production models (90B30) Mathematical geography and demography (91D20)

Abstract: We consider a simple model of firm/city/etc. growth based on a multi-item criterion: whenever entity B fares better that entity A on a subset of $M$ items out of $K$, the agent originally in A moves to B. We solve the model analytically in the cases $K=1$ and $Koinfty$. The resulting stationary distribution of sizes is generically a Zipf-law provided $M>K/2$. When $MleqK/2$, no selection occurs and the size distribution remains thin-tailed. In the special case $M=K$, one needs to regularise the problem by introducing a small "default" probability $phi$. We find that the stationary distribution has a power-law tail that becomes a Zipf-law when $phio0$. The approach to the stationary state can also been characterized, with strong similarities with a simple "aging" model considered by Barrat & M'ezard.

Recommendations

• scientific article; zbMATH DE number 1146090
• Greedy in Approximation Algorithms
• A class of greedy algorithms and its relation to greedoids
• Some remarks on greedy algorithms
• scientific article; zbMATH DE number 1191608
• scientific article; zbMATH DE number 3970528
• The classification of greedy algorithms
• Greedy algorithms with prescribed coefficients
• Canonical greedy algorithms and dynamic programming

Cites work

• ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS
• On the emergence of scale-free production networks
• Zipf's Law for Cities: An Explanation

Cited in

(5)

• Theory of Zipf's law and beyond
• Zipf's law and maximum sustainable growth
• A THEORETICAL APPROACH FOR PARETO–ZIPF LAW
• Zipf's Law for Cities: An Explanation
• Limiting size index distributions for ball-bin models with Zipf-type frequencies

This page was built for publication: Greedy algorithms and Zipf laws

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