Greedy algorithms and Zipf laws
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
IOP Publishing
2018
|
| _version_ | 1797084148438925312 |
|---|---|
| author | Moran, J Bouchaud, J-P |
| author_facet | Moran, J Bouchaud, J-P |
| author_sort | Moran, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:51:18Z |
| format | Journal article |
| id | oxford-uuid:9a2c7f8f-cfee-4d0f-a1e1-1dbb7d4a0fd1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:51:18Z |
| publishDate | 2018 |
| publisher | IOP Publishing |
| record_format | dspace |
| spelling | oxford-uuid:9a2c7f8f-cfee-4d0f-a1e1-1dbb7d4a0fd12022-03-27T00:19:36ZGreedy algorithms and Zipf lawsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:9a2c7f8f-cfee-4d0f-a1e1-1dbb7d4a0fd1EnglishSymplectic ElementsIOP Publishing2018Moran, JBouchaud, J-PWe 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. |
| spellingShingle | Moran, J Bouchaud, J-P Greedy algorithms and Zipf laws |
| title | Greedy algorithms and Zipf laws |
| title_full | Greedy algorithms and Zipf laws |
| title_fullStr | Greedy algorithms and Zipf laws |
| title_full_unstemmed | Greedy algorithms and Zipf laws |
| title_short | Greedy algorithms and Zipf laws |
| title_sort | greedy algorithms and zipf laws |
| work_keys_str_mv | AT moranj greedyalgorithmsandzipflaws AT bouchaudjp greedyalgorithmsandzipflaws |