Similarity of Symbol Frequency Distributions with Heavy Tails

Quantifying the similarity between symbolic sequences is a traditional problem in information theory which requires comparing the frequencies of symbols in different sequences. In numerous modern applications, ranging from DNA over music to texts, the distribution of symbol frequencies is characterized by heavy-tailed distributions (e.g., Zipf’s law). The large number of low-frequency symbols in these distributions poses major difficulties to the estimation of the similarity between sequences; e.g., they hinder an accurate finite-size estimation of entropies. Here, we show analytically how the systematic (bias) and statistical (fluctuations) errors in these estimations depend on the sample size $N$ and on the exponent $\gamma$ of the heavy-tailed distribution. Our results are valid for the Shannon entropy ($\alpha =1$), its corresponding similarity measures (e.g., the Jensen-Shanon divergence), and also for measures based on the generalized entropy of order $\alpha$. For small $\alpha$’s, including $\alpha =1$, the errors decay slower than the $1/N$ decay observed in short-tailed distributions. For $\alpha$ larger than a critical value ${\alpha }^{*}=1+1/\gamma \le 2$, the $1/N$ decay is recovered. We show the practical significance of our results by quantifying the evolution of the English language over the last two centuries using a complete $\alpha$ spectrum of measures. We find that frequent words change more slowly than less frequent words and that $\alpha =2$ provides the most robust measure to quantify language change.

Popular Summary

How similar are two examples of music or text from different authors or disciplines? How fast is the vocabulary of a language changing over time? How can one distinguish between coding and noncoding regions in DNA? The problem underlying all of these questions is how to quantify the similarity between sequences of symbols (e.g., notes in music, words in texts, or base pairs in DNA) and determine the likelihood that two sequences derive from the same parent population. In this work, we address this problem for the important and particularly difficult case in which the frequencies of symbols show heavy-tailed distributions, as encountered in many social, biological, and natural systems (e.g., the famous Zipf’s law that states that the frequencies of words are inversely proportional to their rank in a frequency table).

Information-theoretic measures provide a natural framework for comparing symbolic sequences. Motivated by the wide variation of symbol frequencies in heavy-tailed distributions—for example, “and” is 10,000 times more frequent in the English language than “genetic”—we analytically show how estimating the similarity between two sequences is prone to errors whose magnitudes depend on the sample size $N$. Our primary finding is that, for heavy-tailed distributions, (i) the error decay is often much slower than $1/N$, illustrating the difficulty in obtaining accurate estimates even for large sample sizes, and (ii) there is a critical value of the order of the entropy ${\alpha }^{*}\le 2$ for which the normal $1/N$ dependence is recovered. We emphasize the importance of these findings in the example of quantifying how fast the English vocabulary has changed within the last 200 years, showing that these finite-size effects have to be taken into account even for very large databases ($N\gtrsim 1,000,000,000$ words).

Our results have a direct impact on computer science (e.g., authorship attribution or document classification) and also extend beyond the analysis of natural language because heavy-tailed distributions are ubiquitous in other complex systems.

Figure 1

The English vocabulary in different years. Rank-frequency distribution $p(r)$ of individual years $t$ for $t=1850$, 1900, and 1950 of the Google-ngram database [10], multiplied by a factor of 1, 2, and 4, respectively, for better visual comparison. The inset shows the original untransformed data (same axis), highlighting that the rank-frequency distributions are almost indistinguishable. Individual words (e.g., “and,” “see,” “ship,” and “genetic”) show changes in rank and frequency (symbols), where words with larger ranks (i.e., smaller frequencies) show larger change.

Figure 2

Illustration of our toy model, where $\mathit{p}$ (left diagram) and $\mathit{q}$ (right diagram) have the same rank-frequency distribution but differ in the probability for individual symbols. In this example, $\mathit{p}$ and $\mathit{q}$ are the same ($p_i=q_i$) for $i\in \{A,C,D,E,F,G,H\}$, while the symbol $i=B$ in $\mathit{p}$ is replaced by $i=B^{†}$ in $\mathit{q}$ with $p_{i=B}=q_{i=B^{†}}$ and $p_{i=B^{†}}=q_{i=B}=0$.

Figure 3

The spectrum ${\tilde{D}}_{\alpha }(\mathit{p},I^{*})$ for two different changes. The lines correspond to Eq. (9) with $p_i\propto i^{-1}$ with $i=1,2,\dots ,1000$ and two different sets of replaced symbols $I_1^{*}$, $I_2^{*}$. Right inset: $I_1^{*}=\{1\}$; i.e., only the symbol with the highest probability, $p_{i=1}\approx 0.13$, is changed. Left inset: $I_2^{*}=\{368,\dots ,1000\}$; i.e., the symbols with small probability are replaced. The choice of $I_2^{*}$ was made such that $\sum _{i\in I_2^{*}}{p}_i\approx p_{i=1}$ and therefore ${\tilde{D}}_{\alpha =1}(\mathit{p},I_1^{*})\approx {\tilde{D}}_{\alpha =1}(\mathit{p},I_2^{*})$.

Figure 4

Finite-size estimation of the normalized Jensen-Shannon divergence $\tilde{D}={\tilde{D}}_{\alpha =1}$. (a)–(c) Estimation of $\mathbb{E}[\tilde{D}(\widehat{\mathit{p}},\widehat{\mathit{q}})]$ between two sequences of size $N$ drawn from the same distribution [i.e., $D(\mathit{p},\mathit{q})=0$] using four different estimators of the entropy (see text) for three representative distributions: (a) Exponential (short-tailed) distribution $p_i\propto e^{-ai}$ for $i=0,1,\dots$ with $a=0.1$, (b) power-law (heavy-tailed) distribution $p_i\propto i^{-\gamma }$ for $i=1,2,\dots$ with $\gamma =3/2$, and (c) empirical Zipf distribution of word frequencies, i.e., rank-frequency distribution $p(r)$ from the complete Google-ngram data, $p_i=f(i=r)$ for $i=1,\dots ,4623568$, which is well described by a double power law [11]. (d)–(f) The same as (a)–(c) for the fluctuations $\mathbb{V}[\tilde{D}(\widehat{\mathit{p}},\widehat{\mathit{q}})]$. The dotted lines show the expected scalings from Table 2 for short-tailed distributions, i.e., $N^{-1}$ ($N^{-2}$), and power-law distributions, i.e., $N^{-1+1/\gamma }$ ($N^{-2+1/\gamma }$), for the bias (fluctuations). In (c), we show the expected scaling for the bias, $V_{\mathrm{emp}}(N)/N$, where $V_{\mathrm{emp}}(N)$ is the expected number of different symbols in a random sample of size $N$ from the empirical distribution [32]. Averages are taken over 1000 realizations.

Figure 5

Bias (a,b) and fluctuations (c,d) in the finite-size estimation of ${\tilde{D}}_{\alpha }$. Estimation of $\mathbb{E}[{\tilde{D}}_{\alpha }(\widehat{\mathit{p}},\widehat{\mathit{q}})]$ between two sequences, each of size $N$, drawn numerically from the same power-law distribution $p_i\propto i^{-\gamma }$ for $i=1,2,\dots ,V\to \infty$ with $\gamma =3/2$ using the plug-in estimator ($p_i\mapsto {\widehat{p}}_i$) for the entropies of order $\alpha$. (a) Scaling of the bias with $N$ for different $\alpha$. (b) Decrease of the bias in ${\tilde{D}}_{\alpha }$ when the sample size is doubled ($N\mapsto 2N$) for different values of $N$ as a function of $\alpha$. (c,d) The same as (a) and (b) for the fluctuations $\mathbb{V}[{\tilde{D}}_{\alpha }(\widehat{\mathit{p}},\widehat{\mathit{q}})]$. Red lines in all plots indicate the borders between the regimes, ${\alpha }_1^{\mathbb{E}}=1/\gamma =2/3$, ${\alpha }_2^{\mathbb{E}}=1+1/\gamma =5/3$ [for the bias in (a,b)] and ${\alpha }_1^{\mathbb{V}}=1/\gamma =2/3$, ${\alpha }_2^{\mathbb{V}}=1+1/(2\gamma )=4/3$ [for the fluctuations in (c,d)]. Dotted lines indicate the predictions based on Table 1 for $\alpha <{\alpha }_1^{\mathbb{E}}$, ${\alpha }_1^{\mathbb{V}}$ and $\alpha >{\alpha }_2^{\mathbb{E}}$, ${\alpha }_2^{\mathbb{V}}$ [in (a,c)] and all values of $\alpha$ [in (b,d)]. Averages are taken over 1000 realizations.

Figure 6

Measuring change in the usage of language on historical time scales. (a) ${\tilde{D}}_{\alpha }({\mathit{p}}_{t_1},{\mathit{p}}_{t_2})$ as a function of $\alpha$ for pairs of word-frequency distributions of the Google-ngram database obtained from the yearly corpora $t_1$ and $t_2$ with $(t_1,t_2)\in \{(1850,1900),(1900,1950),(1850,1950)\}$ (solid lines). The dotted lines with the same colors show the results of a null model in which samples of the same size as the ones in $t_1$ and $t_2$ are randomly drawn from the same distribution (obtained from combining the corpora in $t_1$ and $t_2$) mimicking a minimum distance that can be observed because of finite-size effects. The vertical lines show the three regimes $\alpha <1/\gamma$, $1/\gamma <\alpha <1+1/\gamma$, and $\alpha >1+1/\gamma$ in the convergence of ${\tilde{D}}_{\alpha }({\mathit{p}}_{t_1},{\mathit{p}}_{t_2})$ with $N$ (see Sec. 4), obtained using $\gamma =1.77$ [11]. Inset: Ratio ${\tilde{D}}_{\alpha }({\mathit{p}}_{t_{12}},{\mathit{p}}_{t_{12}})/{\tilde{D}}_{\alpha }({\mathit{p}}_{t_1},{\mathit{p}}_{t_2})$. (b) Average divergence as a function of $\mathrm{\Delta }t\equiv |t_2-t_1|$, calculated as ${\tilde{D}}_{\alpha }(\mathrm{\Delta }t)=(1/N_{\mathrm{\Delta }t})\sum _{t_1=1805}^{2000-\mathrm{\Delta }t}{\tilde{D}}_{\alpha }({\mathit{p}}_{t_1},{\mathit{p}}_{t_1+\mathrm{\Delta }t})$ for four different $\alpha$ (solid lines). Shaded areas represent the standard deviation associated with the average ${\tilde{D}}_{\alpha }(\mathrm{\Delta }t)$. Inset: $\sqrt{{\tilde{D}}_{\alpha }(\mathrm{\Delta }t)}$ as a function of $\mathrm{\Delta }t$, highlighting the approximate relationship ${\tilde{D}}_{\alpha }(\mathrm{\Delta }t)\sim \mathrm{\Delta }{t}^2$ for $\mathrm{\Delta }t\gg 1$.

Figure 7

JSD-$\alpha$ for sequences of different lengths. Measurement of ${\tilde{D}}_{\alpha }(\widehat{\mathit{p}},\widehat{\mathit{q}})$ between sequences $\widehat{\mathit{p}}$, $\widehat{\mathit{q}}$ of size ${N_p}^{\prime }={N_q}^{\prime }$ sampled randomly from the empirical distribution of the Google-ngram of the years $t\in \{1850,1950\}$ with different sizes, i.e., $\mathit{p}={\mathit{p}}_{t=1850}$ and $\mathit{q}={\mathit{p}}_{t=1950}$ with $N_p\ne N_q$, as a function of the sample size $N^{\prime }=N_p^{\prime }+N_q^{\prime }$ for different values of $\alpha$. The dotted (dashed) lines show ${\tilde{D}}_{\alpha }^{\pi }(\mathit{p},\mathit{q})$ between the full distributions $\mathit{p}$ and $\mathit{q}$ with equal (natural) weights, i.e., ${\pi }_p={\pi }_q=1/2$ [${\pi }_p=N_p/(N_p+N_q)\approx 0.22$ and ${\pi }_q=N_q/(N_p+N_q)\approx 0.78$ corresponding to the relative size of $\mathit{p}$ and $\mathit{q}$].