PaperlayerView exact revision on arXiv

Source-linked AI summary

Zipf's law unzipped

Seung Ki Baek, Sebastian Bernhardsson, Petter Minnhagen

arXiv:1104.1789v1physics.soc-phcs.SI

TL;DR

The paper asks why Zipf-like power laws describe seemingly unrelated phenomena. It models them as random group divisions and uses information theory to predict group-size distributions. Its conclusion is that the largest group and overall system size are linked to the power-law index, unlike what the discussed growth models explain.

  • Problem

    The paper asks why Zipf’s law describes data from seemingly unrelated phenomena, beyond identifying fits or estimating exponents.

    Source: §1 · p. 2

  • Method

    Random Group Formation models elements as balls divided into groups and uses information theory to predict the group-size distribution, incorporating the largest group’s size.

    Source: §1 · p. 2, §3 · p. 8

  • Results

    The paper concludes that the largest group determines the small-k power-law index, which varies systematically with system size, relationships the discussed growth models do not explain.

    Source: §6 · p. 18

  • Takeaways & Limitations

    Because RGF makes explicit predictions, its validity is open to further tests.

    Source: §6 · p. 18

    The paper’s critique notes that growth models can encode system-specific history and leave the relation among growth, steady state, and maximum entropy flexible.

    Source: §5 · pp. 14, 17

Abstract

from arXiv · show

Why does Zipf's law give a good description of data from seemingly completely unrelated phenomena? Here it is argued that the reason is that they can all be described as outcomes of a ubiquitous random group division: the elements can be citizens of a country and the groups family names, or the elements can be all the words making up a novel and the groups the unique words, or the elements could be inhabitants and the groups the cities in a country, and so on. A Random Group Formation (RGF) is presented from which a Bayesian estimate is obtained based on minimal information: it provides the best prediction for the number of groups with $k$ elements, given the total number of elements, groups, and the number of elements in the largest group. For each specification of these three values, the RGF predicts a unique group distribution $N(k)\propto \exp(-bk)/k^{\gamma}$, where the power-law index $\gamma$ is a unique function of the same three values. The universality of the result is made possible by the fact that no system specific assumptions are made about the mechanism responsible for the group division. The direct relation between $\gamma$ and the total number of elements, groups, and the number of elements in the largest group, is calculated. The predictive power of the RGF model is demonstrated by direct comparison with data from a variety of systems. It is shown that $\gamma$ usually takes values in the interval $1\leq\gamma\leq 2$ and that the value for a given phenomena depends in a systematic way on the total size of the data set. The results are put in the context of earlier discussions on Zipf's and Gibrat's laws, $N(k)\propto k^{-2}$ and the connection between growth models and RGF is elucidated.

1. Introduction

The paper asks why power-law distributions recur across unrelated phenomena and proposes group division as their shared abstract feature. It uses information theory to predict group-size distributions without relying on system-specific mechanisms.

1. Introduction

  • Power-law distributions across diverse phenomena have a long history, including income distributions, city sizes, and word frequencies associated with Zipf’s law.The passage traces early findings to Pareto, Auerbach, and Zipf, while noting Estroup’s earlier word-frequency finding.Source: §1 · p. 2
  • Rather than testing which mathematical form best fits data or estimating an exponent, the paper focuses on why Zipf’s law describes seemingly unrelated phenomena.Source: §1 · p. 2
  • The paper frames the shared explanation as a global abstract model whose characteristics are decided by shared information, following the Simon–Mandelbrot debate.Simon proposed an abstract urn scheme, while Mandelbrot argued for information and entropy rather than a growth model.Source: §1 · p. 2
  • The proposed common feature is division into groups, modeled as numbered balls assigned to boxes and used to predict box-size distributions through maximum mutual information.Examples include people grouped by cities or family names, and words grouped by their occurrences in a novel.Source: §1 · p. 2
  • The paper previews comparisons with empirical data, an explanation of systematic exponent changes, and a discussion of RGF alongside Gibrat’s growth model and the k^-2 distribution.It also previews the claim that k^-2 is an equilibrium rather than a growth feature.Source: §1 · pp. 2–3

2. What do we want to explain?

The paper asks why seemingly unrelated group-size data share broad, fat-tailed distributions. Across cities, family names, and novel word frequencies, the tails are common but their detailed shapes differ, and Zipf’s law does not fully describe them.

2. What do we want to explain?

  • The six cases include city sizes, family-name frequencies, and novel word frequencies, making their shared broadness difficult to attribute to one system-specific process.The paper frames the alternatives as accidental, system-specific similarity or a shared system-independent stochastic process, and pursues the latter.Source: §2 · pp. 4–7
  • US and Korean family-name frequencies and word frequencies in Hardy and Melville novels all show fat-tailed distributions.The Korean family-name distribution falls off more slowly than the US family-name distribution in the log-log plot.Source: Figure 3 · p. 4, Figure 4 · p. 4, §2 · p. 5
  • Across six datasets, all distributions have fat tails, but their detailed shapes differ and Zipf’s law is not a complete mathematical description.Only the French commune data follow Zipf’s law over a limited interval at smaller k.Source: §2 · p. 6

3. Random Group Formation

Random Group Formation models objects divided into categories using minimal information and an equal-probability assumption. It estimates a group-size distribution from the number of elements, groups, and the largest group, linking the distribution’s small-size power-law behavior to its largest-group cutoff.

3. Random Group Formation

  • RGF treats the data as objects divided into categories and uses equal probability for every address as its Bayesian starting assumption.The setup represents M numbered balls and N boxes, with a box of size k containing k slots.Source: §3 · p. 7
  • The model selects the most likely box-size distribution by minimizing information cost subject to the total-element and group-count constraints.The probability P(k) is treated as a distribution from which N box sizes are drawn.Source: §3 · pp. 7–8
  • An entropy reduction ΔS represents unknown preference-breaking processes and is estimated using the largest group size.Together with M and N, kmax yields a unique RGF prediction for P(k).Source: §3 · p. 8
  • For fixed γ, the RGF parameter relationship makes any three of M, N, kmax, and γ determine the fourth.The figure presents M and average group size on the axes and encodes kmax by color.Source: Figure 8 · p. 9
  • For fixed average group size, γ depends on the largest group size, so large-k behavior determines the distribution’s small-k power-law index.The paper also states that randomly removing elements increases γ.Source: Figure 10 · p. 9, §3 · p. 10
  • RGF distributions need not be power laws: the parameter relations determine whether they are convex, pure power-law, or slightly concave.A Gaussian or Poisson distribution has lower entropy than RGF for given M and N, corresponding to greater information cost.Source: §3 · p. 10

4. RGF predictions and properties

RGF predictions closely match six real datasets using only the total elements, number of groups, and largest-group size, rather than fitting a prescribed function. The predicted exponent γ varies systematically with the largest group and dataset size, including after text-size reduction.

4. RGF predictions and properties

  • RGF predictions closely match all six real datasets without fitting a prescribed functional form, using only M, N, and kmax.These are the total number of elements, groups, and elements in the largest group.Source: §4 · p. 10
  • γ spans 1.08 for Korean surnames to 1.98 for French communes, with values derived from Table 1 rather than fitted.Source: §4 · pp. 10–11
  • French communes’ γ≈1.98 reflects Marseille’s kmax≈8.5×10^5; matching US counties’ γ≈1.67 would require kmax≈2.5×10^5.The largest-group cutoff is essential alongside group count and total population.Source: §4 · p. 11
  • After random removal of 99% of Hardy’s words, γ rises from 1.66 to 1.97, as predicted by RGF (1.9655).The reduced data show small deviations; their entropy is 1.49064, versus 1.64776 for the RGF prediction.Source: Figure 11 · p. 12, §4 · p. 12
  • γ and b0 vary approximately linearly with 1/ln M; extrapolated γ is ≈1 for Hardy and ≈0.9 for Melville.This supports a systematic decrease in γ as dataset size increases, with limits close to the non-preferential value γ=1.Source: Figure 12 · p. 12, §4 · p. 13, Figure 13 · p. 13
  • For a novel, analyzing a short passage gives a result very similar to random word removal, because word-frequency classes are approximately position-independent.Source: §4 · p. 13

5. Relation to Growth Models

The section contrasts growth models with equilibrium group-size distributions, arguing that power laws can emerge from steady-state conditions rather than growth itself. It also identifies limitations of growth-based accounts, including poor fit to varied data and history dependence.

5. Relation to Growth Models

  • A maximum-entropy dynamical model moves balls between boxes while preventing any box from becoming empty, and its steady state is P(k) ∝ exp(−bk)/k.The dynamics are ergodic, so the long-run fraction of time a box has size k follows P(k).Source: §5 · p. 14
  • The Gibrat model produces a near-log-normal distribution, which does not match the cited word-frequency data or explain the observed fat tails.The discretized model is evaluated with α = 10/9, β = 9/10, and t = 10.Source: §5 · pp. 13–14
  • With a maximal size M, the ergodic single-box model has steady-state P(k) ∼ 1/k, matching the equal-address maximum-entropy solution when α · β = 1.In logarithmic scale, the process wanders without preference across values from ln 1 to ln M.Source: §5 · pp. 15–16
  • For α · β > 1 while α − β > 0, the steady-state exponent lies between 1 and 2; at α = β it is 2, and for β > α it exceeds 2.The α = β case is an equilibrium model with a well-defined non-growing average size.Source: §5 · p. 16
  • The 1/k^2 distribution is an equilibrium feature, not a consequence of stochastic growth; changing boundary conditions can produce other power-law exponents.The authors note that no general principle identifies which boundary-condition changes correspond to real datasets.Source: §5 · p. 16
  • The Simon model predicts exponents γ = 2.02 and γ = 2.04 for the Hardy and Melville texts, respectively, but fails to describe their word-frequency data.The authors conclude that it lacks the ubiquity needed to explain fat tails across the datasets considered.Source: §5 · p. 17
  • Simon’s history dependence conflicts with real texts: low-frequency words tend to occur late in Simon-generated books, while real-text frequency groups are roughly randomly spread.The authors argue this history dependence is too system-specific for a ubiquitous explanation.Source: §5 · p. 17

6. Summary

The paper proposes Random Group Formation (RGF) as a system-independent explanation for fat-tailed group-size distributions. Across six datasets spanning population, surname, and word-frequency distributions, RGF fits well, while the authors identify the largest group and system size as key constraints on the power-law index.

6. Summary

  • RGF describes six large datasets across population, surname, and word-frequency distributions well, and the power-law index changes systematically with system size.The six datasets comprise two examples of each of the three system types.Source: §6 · p. 17
  • The authors argue that growth models typically give exponents larger than 2, miss the coupling between largest-group size and exponent, and usually produce size-independent exponents.They also identify system-specific memory effects as a problem for models such as Simon’s.Source: §6 · p. 18
  • The largest group determines the power-law index that approximately describes the distribution for small k, and that index also depends systematically on system size.For example, a short novel has a different power-law index from a much longer novel.Source: §6 · p. 18
  • The authors acknowledge that the observed agreements could be accidental or that another ubiquitous explanation could account for the same constraints.Any alternative account would need to explain both the largest-group link and systematic size dependence.Source: §6 · p. 18
  • Because RGF makes explicit predictions, its validity can be tested further.The authors describe their evidence for RGF as convincing.Source: §6 · p. 18

Appendix A. Minimum information cost and maximum entropy

The appendix relates maximum entropy to mutual information when one variable’s distribution is known in advance. It defines an information cost for the equal-address RGF and interprets that cost as the extra information needed to locate a ball within groups of a known size.

Appendix A. Minimum information cost and maximum entropy

  • When x and y are independent, their joint entropy reduces to the sum of their individual entropies.The appendix contrasts this with dependent variables, whose joint distribution does not factor into p(x)p(y).Source: Appendix A · p. 19
  • When p(y) is known a priori, maximizing mutual information is equivalent to minimizing the constrained entropy H[p(y), p(x)].The appendix names this constrained entropy the information cost Icost[p(x)].Source: Appendix A · p. 20
  • The equal-address RGF takes the prior probability for each of the M addresses to be equal.The appendix gives the prior as p_i = 1/M.Source: Appendix A · p. 20
  • For a ball known to lie in groups of size k, ln kN(k) is the information needed to identify its specific address.The average information cost for localizing a ball with known k is Icost = Σ_k P(k) ln kN(k).Source: Appendix A · p. 20

Appendix B. Self-consistent Equations

The RGF curve is obtained by minimizing the total information cost, with its constants fixed by three self-consistent conditions. The largest-group condition uses a specified average maximum box size, while the smallest-box size links the exponent and cutoff.

Appendix B. Self-consistent Equations

  • Minimizing G[P(k)] yields the RGF curve, with γ=1/(1−c3), b=c2/(1−c3), and A=exp{−(1+[c1/(1−c3)]}.The constants are determined by simultaneously satisfying three conditions.Source: Appendix B · pp. 20–21
  • The smallest-box size k0 may be 1 or any arbitrary value, and γ and b are interdependent through a relation set by k0.k0 is defined as the size of the smallest box.Source: Appendix B · p. 21
  • The third condition fixes the average largest-box size; a threshold kc is chosen so one box is expected in [kc, M], then the average box size over that interval is calculated.The resulting conditions are solved self-consistently by trialing γ, deriving b from (B.4), and repeating until (B.5) is satisfied within the chosen precision.Source: Appendix B · p. 21

Appendix C. Random Book Transformation

The Random Book Transformation changes word-frequency distributions as book size changes. The 1/k form is invariant, while distributions with γ>1 become less broad under size reduction and tend toward a limiting form with exponent 2.

Appendix C. Random Book Transformation

  • The exponential cutoff increases linearly with n=M/m, with size dependence approximately Pm(k)∝exp(−kb0/m).Here b0 is a constant.Source: Appendix C · p. 22
  • P(k)∝1/k is invariant under the transformation, while distributions with γ>1 become less broad as size decreases.The transformed distribution approaches P∞(k)∝1/[k(k−1)], which has exponent γ=2 for k values not too small.Source: Appendix C · p. 22
  • In the reverse direction, the discussion suggests that an infinitely large book approaches P0(k)∝1/k, with some support from the data analysis.The passage frames this as an expectation and says the data provide some support.Source: Appendix C · p. 22
Loading 1104.1789v1…