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

Question

Zipf's law is the empirical observation that in many real-life populations of $n$ objects, the $k^\text{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 1

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 2

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 3

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 4

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($\frac{1}{2}$), Poisson($\frac1{3}$)... hence probably even if $N_i$ are ranked in order, their sizes would be like $1, \frac1{2}, \frac1{3}$ etc.

Answer 5

There's a recent paper on the arXiv by Schwab et al. that looks to contain a nice derivation of Zipf's law, which arises in random systems affected by a hidden variable (something like common inputs to a neural network): http://arxiv.org/abs/1310.0448

Answer 6

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

Answer 7

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

Answer 8

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.