Greedy algorithms and Zipf laws

Author: 

Moran, J
Bouchaud, J

Publication Date: 

9 April 2018

Journal: 

Journal of Statistical Mechanics: Theory and Experiment

Last Updated: 

2021-03-17T21:44:15.133+00:00

Issue: 

4

Volume: 

2018

DOI: 

10.1088/1742-5468/aab50a

page: 

043402-043402

abstract: 

We consider a simple model of firm/city/etc growth based on a multi-item criterion: whenever entity B fares better than 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 . The resulting stationary distribution of sizes is generically a Zipf-law provided M  >  K/2. When , no selection occurs and the size distribution remains thin-tailed. In the special case M  =  K, one needs to regularize the problem by introducing a small 'default' probability phgr. We find that the stationary distribution has a power-law tail that becomes a Zipf-law when . The approach to the stationary state can also be characterized, with strong similarities with a simple 'aging' model considered by Barrat and Mézard.

Symplectic id: 

1145383

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article