91

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.

Michael Hardy
  • 11,922
  • 11
  • 81
  • 119
Terry Tao
  • 108,865
  • 31
  • 432
  • 517
  • 7
    There's a paper called Zipf's Law for Cities: An Explanation with the following abstract.

    Zipf's law is a very tight constraint on the class of admissible models of local growth. It says that for most countries the size distribution of cities strikingly fits a power law: the number of cities with populations greater than S is proportional to 1/S. Suppose that, at least in the upper tail, all cities follow some proportional growth process (this appears to be verified empirically). This automatically leads their distribution to converge to Zipf's law.

    I can't access the paper itself though.

     – gowers Sep 18 '10 at 17:59
  • 2
    "From gene families and genera to incomes and internet file sizes: Why power laws are so common in nature":http://llacolen.ciencias.uchile.cl/~vmunoz/download/papers/rh02.pdf taken from Brian Hayes's article "Fat Tails": americanscientist.org/issues/pub/fat-tails. Not sure if this gives ways of generating Zipf's law with exponent 1, but maybe a random variable with exponential increasing value coupled with an exponentially decreasing probability capped for a particular N? – dorkusmonkey Sep 18 '10 at 19:39
  • Good question. It's been a while since I've looked at Zipf's book and I vaguely seem to recall that it was about a large number of different subjects, but maybe I was just missing his point. But I seem to recall that he found that word frequencies in English follow Zipf's law out to about the thousandth word and then suddenly drop off faster. I think the same maybe apply to numbers of postings by usenet posters. – Michael Hardy Sep 21 '10 at 00:19
  • http://arxiv.org/abs/1301.0427 – Steve Huntsman Jan 25 '13 at 14:55
  • 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) – Suvrit Sep 19 '10 at 07:34
  • Is there any linkage between this question and research on Riemann Hypothesis? – XL _At_Here_There Jul 19 '14 at 08:03
  • 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 resourc –  Jan 18 '11 at 22:37

8 Answers8

45

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.

Dick Palais
  • 15,150
  • 10
    "Zipf’s law is not a deep law in natural language as one might first have thought. It is very much related the particular representation one chooses" --From Li, W. "Random Texts Exhibit Zipf’s-Law-Like Word Frequency Distribution." IEEE Trans. on Info. Th. 38, 1842 (1992). – Steve Huntsman Sep 18 '10 at 18:50
19

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.

Steve Huntsman
  • 15,258
16

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

Did
  • 5,701
James Martin
  • 3,787
15

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.

vidyarthi
  • 2,027
Manjunath Krishnapur
  • 303
  • This also has a parameterized version, the $(\alpha,\theta)$-Chinese restaurant process, which will lead to different distributions on partitions. It's a nice answer for the question though because the random permutation case is by far the most natural element of the family of distributions. – Louigi Addario-Berry Sep 19 '10 at 11:47
  • How does this actually work though? If you take a realisation of the process $(N_1, N_2, ...)$, you'll get something that looks like (1,2,0,2,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0....) or whatever. That doesn't seem like a "process that obeys Zipf's law". I guess you could do something like take $n$ independent random permutations of $[n]$, and look at the collection of all the 1-cycles, all the 2-cycles, etc... but then it's maybe more artificial. – James Martin Sep 20 '10 at 00:10
  • That's right, it does seem a little unsatisfactory. In expectation we do have the 1/k behaviour, though. – Manjunath Krishnapur Sep 20 '10 at 08:32
6

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

S Palmer
  • 61
5

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

anon
  • 89
3

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.

The Amplitwist
  • 1,446
Alex Chinco
  • 31
2

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.

Pietro Majer
  • 56,550
  • 4
  • 116
  • 260