Is there a natural random process that is rigorously known to produce Zipf's law? - MathOverflow

Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-18T16:24:22Z

Zipf's law 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.

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.

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.

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.

Answer by Dick Palais for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-18T18:09:42Z

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 :-)

(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:

http://www.infoplease.com/ipa/A0763098.html#axzz0zuwyduxq

However, for China, it is WAY off---not even close:

http://en.wikipedia.org/wiki/List_of_cities_in_the_People%27s_Republic_of_China_by_population

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.

Answer by Steve Huntsman for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-18T18:59:30Z

Following up Gowers' comment, a 1998 PRL article (arxiv version here) discusses the mechanism that appears to underlie Zipf's law statistics for cities:

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.

Answer by S. Sra for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-19T07:34:50Z

Sorry, this is supposed to be comment (but with reputation < 50, one cannot comment). Anyone care to enlighten whether the Pitman-Yor process is a "natural" process to explain Zipf's law (because it is useful for modeling data with power-law tails)

Answer by Manjunath Krishnapur for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-19T10:28:55Z

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.

Answer by Pietro Majer for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-19T11:43:35Z

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.. &c.

Answer by Alex Chinco for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-19T16:38:51Z

Xavier Gabaix has several papers (eg here and here) that look at the emergence of Zipf's law in city sizes as a natural phenomenon.

Answer by James Martin for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-20T23:09:31Z

Here's a simple birth model which leads to power law behaviour with exponent 1.

Start with a single individual of type 1.

Reproduction as follows:

(a) each individual produces "clone offspring" (a child of the same type as itself) at rate 1.

(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.

Let $N_k(t)$ be the number of individuals of type $k$ alive at time $t$.

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)$.

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.

Reordering the $N_k(t)$ into decreasing order still leaves essentially the same rate of decay.

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 $ ).

Answer by anon for Is there a natural random process that is rigorously known to produce Zipf's law?

2010-11-23T14:17:18Z

http://en.wikipedia.org/wiki/Chinese_restaurant_process

Answer by Aaron Sheldon for Is there a natural random process that is rigorously known to produce Zipf's law?

2011-01-18T22:37:51Z

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?

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?

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).