Is there a natural random process that is rigorously known to produce Zipf's law? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:48:00Z http://mathoverflow.net/feeds/question/39224 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law Is there a natural random process that is rigorously known to produce Zipf's law? Terry Tao 2010-09-18T16:24:22Z 2013-03-30T05:18:33Z <p><a href="http://en.wikipedia.org/wiki/Zipf%27s_law" rel="nofollow">Zipf's law</a> is the empirical observation that in many real-life populations of n objects, the $k^{th}$ largest object has size proportional to $1/k$, at least for $k$ significantly smaller than $n$ (and one also sometimes needs to assume $k$ somewhat larger than 1). It is a special case of a power law distribution (in which $1/k$ is replaced with $1/k^\alpha$ for some exponent $\alpha$), but the remarkable thing is that in many empirical cases (e.g. frequencies of words, or sizes of cities), the exponent is very close to 1.</p> <p>My question is: is there a "natural" random process (e.g. a birth-death process) that one can rigorously demonstrate (or at least conjecture) to generate populations of n non-negative quantities $X_1,\ldots,X_n$ (with n large but possibly variable) that obey Zipf's law on average with exponent 1? There are plenty of natural ways to generate processes that have power law tails (e.g. consider n positive quantities $X_1,\ldots,X_n$ evolving by iid copies of log-Brownian motion), but I don't see how to ensure the exponent is 1 without artificially setting the parameters to force this. </p> <p>Ideally, such processes should be at least somewhat plausible as models for an empirical situation in which Zipf's law is observed to hold, such as city sizes, but I would be happy with any non-artificial example of a process.</p> <p>One obstruction here is the exponent one property is not invariant with respect to taking powers: if $X_1,\ldots,X_n$ obeys Zipf's law with exponent one, then for any fixed $\beta>0$, $X_1^\beta,\ldots,X_n^\beta$ obeys the power law with a different exponent $\beta$. So whatever random process one would propose for Zipf's law must somehow be quite different from its powers.</p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39232#39232 Answer by Dick Palais for Is there a natural random process that is rigorously known to produce Zipf's law? Dick Palais 2010-09-18T18:09:42Z 2010-09-18T22:01:50Z <p>I'm not sure if this is an "answer" to your question, but I recall seeing somewhere that someone had shown that if you create a document by selecting the characters a...z plus a space character with uniform frequency then the "words" of such a document have a frequency distribution that follows Zipf's Law. (A little anecdote: when I was an undergraduate, I took a course on "Inductive Logic" given by Zipf. I recall being rather annoyed because he spent a lot of the time lecturing about "his" law and having us form groups that as part of our class work collected statistics to test it :-) </p> <p>(Added Remarks) I recalled that when we tested Zipf's Laws for city populations back then (more than 50 years ago !) the results were quite good---i.e., the population of the n-th city was pretty close to $1/n$ times the population of the first for many countries. I decided to see if that was still so. For the US it pretty much is:</p> <p><a href="http://www.infoplease.com/ipa/A0763098.html#axzz0zuwyduxq" rel="nofollow">http://www.infoplease.com/ipa/A0763098.html#axzz0zuwyduxq</a></p> <p>However, for China, it is WAY off---not even close:</p> <p><a href="http://en.wikipedia.org/wiki/List_of_cities_in_the_People%27s_Republic_of_China_by_population" rel="nofollow">http://en.wikipedia.org/wiki/List_of_cities_in_the_People%27s_Republic_of_China_by_population</a></p> <p>Of course the population of Chinese cities has been changing rapidly due to migrations into them from the countryside, and perhaps Zipf's Law pertains only to stable situations when things are in equilibrium.</p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39235#39235 Answer by Steve Huntsman for Is there a natural random process that is rigorously known to produce Zipf's law? Steve Huntsman 2010-09-18T18:59:30Z 2010-09-18T18:59:30Z <p>Following up Gowers' comment, a <a href="http://prl.aps.org/abstract/PRL/v80/i12/p2741_1" rel="nofollow">1998 PRL article</a> (arxiv version <a href="http://arxiv.org/abs/cond-mat/9801289" rel="nofollow">here</a>) discusses the mechanism that appears to underlie Zipf's law statistics for cities:</p> <blockquote> <p>We see that the interaction leading to the Zipf ’s law is, on one hand, the simplest possible (pairwise interaction). On the other it is a rather special one, since it is the “lowest order” of interaction which does not lead to the formation of a mega-city, which draws a good portion of the whole population.</p> </blockquote> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39281#39281 Answer by S. Sra for Is there a natural random process that is rigorously known to produce Zipf's law? S. Sra 2010-09-19T07:34:50Z 2010-09-19T07:34:50Z <p>Sorry, this is supposed to be comment (but with reputation &lt; 50, one cannot comment). Anyone care to enlighten whether the <a href="http://en.wikipedia.org/wiki/Pitman%E2%80%93Yor_process" rel="nofollow">Pitman-Yor process</a> is a "natural" process to explain Zipf's law (because it is useful for modeling data with power-law tails)</p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39290#39290 Answer by Manjunath Krishnapur for Is there a natural random process that is rigorously known to produce Zipf's law? Manjunath Krishnapur 2010-09-19T10:28:55Z 2010-09-19T10:28:55Z <p>Not sure if this model is natural enough, but if \pi is a random permutation of {1,2..n}, and N_i is the number of cycles of size i in \pi, then, (N_1, N_2...) are approximately independent Poisson(1), Poisson(1/2), Poisson(1/3)... hence probably even if N_i are ranked in order, their sizes would be like 1, 1/2, 1/3 etc.</p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39297#39297 Answer by Pietro Majer for Is there a natural random process that is rigorously known to produce Zipf's law? Pietro Majer 2010-09-19T11:43:35Z 2010-09-19T11:43:35Z <p>More a hint than a complete answer. A possible natural source for the appearance of a given law could be, getting it in the Nash equilibrium of some game. So one may e.g. look for the 2-players games that produce the Zipf's law as optimal strategy for one player, and then investigate whether there is any of these games that admits an interpretation as a natural model for biology/economy/social sciences.. &amp;c. </p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39314#39314 Answer by Alex Chinco for Is there a natural random process that is rigorously known to produce Zipf's law? Alex Chinco 2010-09-19T16:38:51Z 2010-09-19T16:38:51Z <p><a href="http://pages.stern.nyu.edu/~xgabaix/" rel="nofollow">Xavier Gabaix</a> has several papers (eg <a href="http://www.mitpressjournals.org/doi/abs/10.1162/003355399556133" rel="nofollow">here</a> and <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B7P64-4FFPH84-2F&amp;_user=142623&amp;_coverDate=12/31/2004&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1466283797&amp;_rerunOrigin=scholar.google&amp;_acct=C000000333&amp;_version=1&amp;_urlVersion=0&amp;_userid=142623&amp;md5=dfc67114398bfe4c3dcdf4b7529cb7b1&amp;searchtype=a" rel="nofollow">here</a>) that look at the emergence of Zipf's law in city sizes as a natural phenomenon.</p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/39448#39448 Answer by James Martin for Is there a natural random process that is rigorously known to produce Zipf's law? James Martin 2010-09-20T23:09:31Z 2011-09-27T12:37:35Z <p>Here's a simple birth model which leads to power law behaviour with exponent 1.</p> <p>Start with a single individual of type 1.</p> <p>Reproduction as follows:</p> <p>(a) each individual produces "clone offspring" (a child of the same type as itself) at rate 1. </p> <p>(b) in addition, each individual of type 1 produces "mutant offspring" (a child of a new type not yet seen before) at rate $\mu$, where $\mu$ is any positive constant. So the first mutant will be called type 2, the second type 3, etc. </p> <p>Let $N_k(t)$ be the number of individuals of type $k$ alive at time $t$. </p> <p>Once the first individual of type $k$ has been born, the type-$k$ family grows exponentially. Also, the first individual of type $k$ is born at time $\log k + O(1)$. </p> <p>From this it's quite easy to obtain that $N_k(t)$ behaves something like $e^t/k$. More precisely, for any $k$ the quantity $ke^{-t}N_k(t)$ converges as $t\to\infty$ with probability 1 to some random variable $W_k$, say, and the sequence of distributions of $W_k, k\geq 1$ is tight. </p> <p>Reordering the $N_k(t)$ into decreasing order still leaves essentially the same rate of decay. </p> <p>So for large $t$, $N_k(t), k \geq 1$ obeys Zipf's law (for a range of $k$ that depends suitably on $t$, say $k \ll e^t$ ). </p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/47100#47100 Answer by anon for Is there a natural random process that is rigorously known to produce Zipf's law? anon 2010-11-23T14:17:18Z 2010-11-23T14:17:18Z <p><a href="http://en.wikipedia.org/wiki/Chinese_restaurant_process" rel="nofollow">http://en.wikipedia.org/wiki/Chinese_restaurant_process</a></p> http://mathoverflow.net/questions/39224/is-there-a-natural-random-process-that-is-rigorously-known-to-produce-zipfs-law/52441#52441 Answer by Aaron Sheldon for Is there a natural random process that is rigorously known to produce Zipf's law? Aaron Sheldon 2011-01-18T22:37:51Z 2011-01-18T22:44:26Z <p>I wonder if there is a Zipf's Law equivalent of the Glivenko-Cantelli Theorem, where the condition of independence is replaced by requiring a sum of powers remain fixed, and the identical assumption is replaced by a marginal identical assumption?</p> <p>If $C=\sum_{i=1}^n X_i^\alpha$ and $X_i \sim P(X)$ then $\lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=1}^{n} I(X_i \leq x) \propto \ln(x)$ almost surely?</p> <p>I ask this because empirically Zipf's Law seems to occur when the sample violates independence, and is usually constrained by requiring a fixed sum (like fixed population size, wealth, or resource). </p>