Skip to main content

Power Laws

Module 3: Modelling with Randomness

NoteReading
  • Compulsory: Clauset et al. (2009), Sections 1 to 3 and Box 1.
  • Recommended: Newman (2005). The tests of Sections 4 and 5 of the first paper are the subject of Fitting Power Laws Properly.

A distribution has a fat (heavy) tail when large values are much more likely than under a Gaussian. The simplest example is the power law. This page follows Newman (2005) and Clauset et al. (2009).

Definition

A continuous power law has density

\[ p(x) = \frac{\alpha - 1}{x_{\min}} \left( \frac{x}{x_{\min}} \right)^{-\alpha}, \qquad x \ge x_{\min}, \tag{1}\]

with \(\alpha > 1\) so that it can be normalized. Its complementary cumulative distribution function (CCDF) is also a power law, with exponent one less:

\[ P(X \ge x) = \left( \frac{x}{x_{\min}} \right)^{-(\alpha - 1)} . \tag{2}\]

The mean is finite only if \(\alpha > 2\) and the variance only if \(\alpha > 3\) (Newman 2005). For \(1 < \alpha \le 3\) the sample variance never settles, however much data you collect.

Pareto, Zipf and the same law

Pareto’s law is a statement about the CCDF: the fraction of people with wealth above \(x\) decays as a power of \(x\). Zipf’s law is a statement about ranks: the \(r\)-th most frequent word appears with frequency proportional to \(r^{-s}\). A rank plot is the CCDF with the axes swapped, so both are power laws for the same data (Newman 2005).

Log-log plots and their pitfalls

On log-log axes Equation 1 is a straight line with slope \(-\alpha\). That suggests fitting a line by least squares. Clauset et al. (2009) show that this is a poor estimator:

  • A histogram with linear bins has very few counts in the tail, and its logarithm is noisy and biased. For 10000 continuous samples with \(\alpha = 2.5\) and \(x_{\min} = 1\), Clauset et al. (2009) obtain \(1.39 \pm 0.05\) from a least-squares fit to a histogram with constant-width bins and \(1.19 \pm 0.02\) with logarithmic bins, against \(2.50 \pm 0.02\) from maximum likelihood (their Table 3.1).
  • The least-squares fit has no valid error estimate. The noise in the logarithm of a count is not Gaussian, and for a fit to a cumulative distribution neighbouring points are strongly correlated. The error bar of a biased fit therefore gives no warning that the estimate is wrong.
  • A straight-looking stretch does not prove a power law, and a high \(r^2\) is no evidence either. Clauset et al. (2009) show small samples from a power law, a log-normal and an exponential distribution that all look roughly straight on log-log axes (their Fig. 4.1a).

A least-squares fit to the CCDF built without binning (a rank-frequency plot) does much better than a histogram fit. For the same continuous data it gives \(2.4869 \pm 0.0003\). The paper still recommends maximum likelihood, because the least-squares error bars are not valid and the CCDF fit is biased for integer data (2.570 against a true value of 2.5). Plot the CCDF, which needs no binning, and estimate \(\alpha\) by maximum likelihood.

Figure 1: The same 5000 samples of a power law with \(\alpha = 2.5\) and \(x_{\min} = 1\). Left: histogram with linear bins on log-log axes. Right: empirical CCDF, with the exact CCDF \(x^{-1.5}\) as a dashed line.

The maximum likelihood estimator

Given \(n\) observations \(x_i \ge x_{\min}\), the maximum likelihood estimate of \(\alpha\) is

\[ \hat{\alpha} = 1 + n \left[ \sum_{i=1}^{n} \ln \frac{x_i}{x_{\min}} \right]^{-1}, \qquad \sigma_{\hat{\alpha}} = \frac{\hat{\alpha} - 1}{\sqrt{n}}, \tag{3}\]

(Newman 2005; Clauset et al. 2009). The estimator is unbiased only asymptotically. Its bias decays as \(1/n\), and the authors give \(n \gtrsim 50\) as a rule of thumb for an estimate accurate to about 1 %. In practice \(x_{\min}\) is unknown, and it matters. If it is too low, the fit includes data that do not follow the power law and \(\hat{\alpha}\) is biased. If it is too high, data are thrown away and the error grows. Clauset et al. (2009) choose \(x_{\min}\) by minimizing the Kolmogorov-Smirnov distance between the data above \(x_{\min}\) and the fitted law. They then test the fit with a bootstrap p-value and compare the power law with alternative distributions (their Box 1). Fitting Power Laws Properly implements this procedure. You meet the same estimator again as the Hill estimator in the lab. For integer data the estimator has to change: the paper gives an approximation that replaces \(x_{\min}\) by \(x_{\min} - 1/2\) inside the logarithm, accurate to about 1 % for \(x_{\min} \gtrsim 6\).

alpha_hat, err = mle_power_law_exponent(x, xmin=1.0)
print(f"MLE: alpha = {alpha_hat:.3f} +/- {err:.3f}  (true 2.5)")
MLE: alpha = 2.503 +/- 0.021  (true 2.5)
NoteExercise

Estimate \(\alpha\) by a least-squares line through the log-log histogram of the left panel (use only bins with counts). Repeat for 200 independent samples of size 5000 and compare the mean and spread of the least-squares and MLE estimates.

rng = np.random.default_rng(3)
ls, ml = [], []
for _ in range(200):
    s = sample_pareto(5000, 2.5, 1.0, rng)
    c, e = np.histogram(s, bins=200)
    m = 0.5 * (e[1:] + e[:-1])
    keep = c > 0
    ls.append(-np.polyfit(np.log(m[keep]), np.log(c[keep]), 1)[0])
    ml.append(mle_power_law_exponent(s, 1.0)[0])
print(f"least squares: {np.mean(ls):.3f} +/- {np.std(ls):.3f}")
print(f"MLE:           {np.mean(ml):.3f} +/- {np.std(ml):.3f}")
least squares: 1.599 +/- 0.171
MLE:           2.499 +/- 0.020

The least-squares estimate is strongly biased (about 1.6 with a spread of 0.17 in this run) because the sparse tail bins, many with a single count, flatten the line. The MLE is centred on 2.50 with a spread of 0.02, close to \((\alpha - 1)/\sqrt{n} \approx 0.021\).

References

Clauset, Aaron, Cosma Rohilla Shalizi, and M. E. J. Newman. 2009. “Power-Law Distributions in Empirical Data.” SIAM Review 51 (4): 661–703. https://doi.org/10.1137/070710111.
Newman, M. E. J. 2005. “Power Laws, Pareto Distributions and Zipf’s Law.” Contemporary Physics 46 (5): 323–51. https://doi.org/10.1080/00107510500052444.