Motivation

Zipf's law is the empirical observation that when a set of measured values is sorted in decreasing order, the value of the $n$-th entry is often approximately inversely proportional to $n$. Its best-known instance is word frequency in natural language: in the Brown Corpus the most frequent word, "the", accounts for nearly $7\%$ of all word occurrences, the second, "of", for slightly over $3.5\%$, and so on. The same rank–size relation has been reported for city populations (Auerbach 1913), firm sizes (Axtell 2001), and many other data sets; it is named after the linguist George Kingsley Zipf (1932, 1935, 1949) and remains a central concept of quantitative linguistics (Piantadosi 2014).

In mathematical statistics the law is formalized as the Zipf distribution, a family of discrete probability distributions whose rank–frequency relation is an inverse power law, together with its relatives: the zeta distribution (Lotka's law), the Zipf–Mandelbrot law and the Yule–Simon distribution. Several generative explanations — random typing (Miller 1957, Li 1992) and preferential attachment — produce power laws by provable mechanisms.

Timeline of the results formalized here:

• 1913–1932 — Auerbach (city sizes), Estoup (1916), Dewey (1923), Condon (1928) and Zipf (1932) observe the inverse rank–frequency relation.
• 1957 — Miller: a power law emerges in randomly generated texts (doi:10.2307/1419346).
• 1992 — Li: in random texts with equiprobable letters, word frequency follows Zipf's macro-trend (doi:10.1109/18.165464).

Setting

For a real exponent $s$ and an integer $N \ge 1$, the generalized harmonic number is

$$H_{N,s} = \sum_{k=1}^{N}\frac{1}{k^s}, \qquad H_N = H_{N,1}.$$

The Zipf distribution on $N$ elements with exponent $s$ assigns to the element of rank $k \in\{1,\dots,N\}$ the probability

$$f(k;N,s) = \frac{1}{H_{N,s}}\,\frac{1}{k^{s}} .$$

The classical Zipf law is $s=1$. The source lists the parameter range $s\ge0$, $N\in\{1,2,3,\dots\}$.

The Riemann zeta function is $\zeta(s)=\sum_{k\ge1}k^{-s}$ for $s>1$. The Hurwitz zeta function is $\zeta(s,a)=\sum_{n\ge0}(n+a)^{-s}$. The Zipf–Mandelbrot law on ranks $k=1,2,\dots$ with shift $q$ and exponent $s$ is $f(k;q,s)=\frac{1}{C}\frac{1}{(k+q)^s}$ with $C=\zeta(s,q+1)$. The Yule–Simon distribution with parameter $\rho>0$ is $f(k;\rho)=\rho\,B(k,\rho+1)=\rho\,\Gamma(k)\Gamma(\rho+1)/\Gamma(k+\rho+1)$, $k = 1, 2, \dots$.

Formalization targets

Goal — the infinite-item extension

For $s \ge 0$:

$$\sum_{k\ge1}\frac1{k^s}<\infty \iff s>1;\qquad s>1 \implies H_{N,s}\xrightarrow[N\to\infty]{}\zeta(s);\qquad s\le1 \implies H_{N,s}\xrightarrow[N\to\infty]{}\infty .$$

That is, the generalized Zipf distribution extends to infinitely many items exactly when $s>1$, in which case the normalizing constant becomes Riemann's zeta function.

Milestones

1. Normalization: $\sum_{k=1}^N f(k;N,s)=1$.
2. CDF: $\sum_{k=1}^n f(k;N,s)=H_{n,s}/H_{N,s}$ for $n\le N$.
3. Mean: $\sum_{k} k\,f(k;N,s)=H_{N,s-1}/H_{N,s}$.
4. Variance: $\frac{H_{N,s-2}}{H_{N,s}}-\frac{H_{N,s-1}^2}{H_{N,s}^2}$.
5. Entropy: $\frac{s}{H_{N,s}}\sum_{k=1}^N\frac{\ln k}{k^s}+\ln H_{N,s}$.
6. Mode: rank $1$ is a most probable element (for $s \ge 0$).
7. Ratio: $f(1;N,s)/f(n;N,s)=n^s$ — "the most common word occurs about $n$ times the $n$-th most common one" when $s = 1$.
8. Log–log linearity: $\ln f(k;N,s) = -s\ln k-\ln H_{N,s}$, an affine function of $\ln k$ with slope $-s$.
9. Zipf–Mandelbrot: with $C=\zeta(s,q+1)$ the law is a probability distribution ($s>1$, $q\ge0$).
10. Yule–Simon tail: $f(k;\rho)\sim C/k^{\rho+1}$ for some constant $C>0$.
11. Random typing (Li): word probability is bounded above and below by a power of the rank.
12. Benford connection: the leading digits of a Zipf ($s=1$) random rank follow Benford's law as $N\to\infty$.

Significance

The goal pins down exactly when "Zipf's law with infinitely many items" makes sense, and identifies the resulting distribution (the zeta distribution) with Riemann's zeta function. The milestones are the infobox facts that statisticians use when fitting Zipf models (CDF, mean, variance, entropy, mode), the log–log diagnostic used to test data against the law, two of the related laws the source lists (Zipf–Mandelbrot, Yule–Simon), one of the generative explanations (random typing), and the stated link to Benford's law.

The results are classical; the work is formalizing them. Most milestones are finite algebra about $H_{N,s}$; the goal, the Yule–Simon tail, the random-typing bound and the Benford connection need analysis.

Difficulty

The finite identities are routine once the support conventions are fixed. The analytic content is concentrated in four places. The goal needs the $p$-series test and the identification of the limit with Mathlib's complex riemannZeta, which is defined by analytic continuation rather than by the series. The Yule–Simon tail needs the asymptotics $\Gamma(k)/\Gamma(k+a)\sim k^{-a}$. The random-typing bound requires controlling the rank of a word through the number of strictly shorter words, uniformly over every rank order compatible with the probabilities. The Benford connection requires comparing the harmonic sums over each block of integers with a fixed leading digit with $\ln(1+1/d)$, with an error that is negligible against $H_N\sim\ln N$.

Formalization scope

• $H_{N,s}$ uses a real exponent (Real.rpow); $H_{0,s}=0$.
• zipfPMF N s k is defined for every natural $k$ and is $0$ outside the support $\{1,\dots,N\}$. Statements that need a nonempty support assume $N\ge1$.
• The goal states convergence to the complex number riemannZeta s of the real partial sums viewed as complex numbers, and divergence as Tendsto … atTop atTop. The source's parameter range $s\ge0$ is kept as a hypothesis.
• The Hurwitz zeta function is defined by its series (value $0$ when the series diverges); the Zipf–Mandelbrot law is the infinite-item version on ranks $k\ge1$, with $q\ge0$.
• The Yule–Simon distribution is defined through the Gamma function; the tail statement asserts existence of a positive constant, matching the source's "[constant]".
• Random typing is formalized in Li's equiprobable model: $m\ge2$ letters each typed with probability $q>0$, a space with probability $1-mq>0$, and a word $w$ has probability $q^{|w|}(1-mq)$. "Sorted by rank" means any bijection $e$ from $\mathbb N$ onto the nonempty words along which the probability is non-increasing; the conclusion is a two-sided power-law bound with exponent $\log_m(1/q)$.
• The Benford connection uses the leading decimal digit of the rank $k$, with $k$ drawn from the Zipf distribution with $s=1$.
• Not formalized: the empirical claims (word, city, income data), the atlas-model result, Belevitch's Taylor-series argument, the parabolic fractal distribution and the Pareto exchange of variables; their statements in the source are not precise enough to formalize faithfully.

Selected references

• G. K. Zipf, Human Behavior and the Principle of Least Effort, Addison-Wesley, 1949. https://archive.org/details/in.ernet.dli.2015.90211
• E. U. Condon, Statistics of vocabulary, Science 67 (1928), 300. https://doi.org/10.1126/science.67.1733.300
• G. A. Miller, Some effects of intermittent silence, American Journal of Psychology 70 (1957), 311–314. https://doi.org/10.2307/1419346
• W. Li, Random texts exhibit Zipf's-law-like word frequency distribution, IEEE Trans. Inform. Theory 38 (1992), 1842–1845. https://doi.org/10.1109/18.165464
• B. Conrad, M. Mitzenmacher, Power laws for monkeys typing randomly: the case of unequal probabilities, IEEE Trans. Inform. Theory 50 (2004), 1403–1414. https://doi.org/10.1109/TIT.2004.830752
• R. L. Axtell, Zipf distribution of U.S. firm sizes, Science 293 (2001), 1818–1820. https://doi.org/10.1126/science.1062081
• M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics 46 (2005), 323–351. https://arxiv.org/abs/cond-mat/0412004
• S. T. Piantadosi, Zipf's word frequency law in natural language: a critical review and future directions, Psychon. Bull. Rev. 21 (2014), 1112–1130. https://doi.org/10.3758/s13423-014-0585-6
• Wikipedia, Zipf's law. https://en.wikipedia.org/wiki/Zipf%27s_law