Suppose you have data from a discrete power law with exponent α. That is, the probability of an outcome *n* is proportional to *n*^{-α}. How can you recover α?

A naive approach would be to gloss over the fact that you have discrete data and use the MLE (maximum likelihood estimator) for continuous data. That does a very poor job [1]. The discrete case needs its own estimator.

To illustrate this, we start by generating 5,000 samples from a discrete power law with exponent 3.

The continuous MLE is very simple to implement:

Unfortunately, it gives an estimate of 6.87 for alpha, though we know it should be around 3.

The MLE for the discrete power law distribution satisfies

Here ζ is the Riemann zeta function, and *x**i* are the samples. Note that the left size of the equation is the derivative of log ζ, or what is sometimes called the logarithmic derivative.

There are three minor obstacles to finding the estimator using Python. First, SciPy doesn’t implement the Riemann zeta function ζ(*x*) per se. It implements a generalization, the Hurwitz zeta function, ζ(*x*, *q*). Here we just need to set *q* to 1 to get the Riemann zeta function.

Second, SciPy doesn’t implement the derivative of zeta. We don’t need much accuracy, so it’s easy enough to implement our own. See an earlier post for an explanation of the implementation below.

Finally, we don’t have an explicit equation for our estimator. But we can easily solve for it using the bisection algorithm. (Bisect is slow but reliable. We’re not in a hurry, so we might as use something reliable.)

We have assumed that our data follow a power law immediately from *n* = 1. In practice, power laws generally fit better after the first few elements. The code above works for the more general case if you set `xmin`

to be the point at which power law behavior kicks in.

The bisection method above searches for a value of the power law exponent between 1.01 and 10, which is somewhat arbitrary. However, power law exponents are very often between 2 and 3 and seldom too far outside that range.

The code gives an estimate of α equal to 2.969, very near the true value of 3, and much better than the naive estimate of 6.87.

Of course in real applications you don’t know the correct result before you begin, so you use something like a confidence interval to give you an idea how much uncertainty remains in your estimate.

The following equation [2] gives a value of σ from a normal approximation to the distribution of our estimator.

So an approximate 95% confidence interval would be the point estimate +/- 2σ.

Here we use a finite difference approximation for the second derivative of zeta, an extension of the idea used above for the first derivative. We don’t need high accuracy approximations of the derivatives since statistical error will be larger than the approximation error.

In the example above, we have α = 2.969 and σ = 0.0334, so a 95% confidence interval would be [2.902, 3.036].

* * *

[1] Using the continuous MLE with discrete data is not so bad when the minimum output *x*_{min}is moderately large. But here, where *x*_{min} = 1 it’s terrible.

[2] Equation 3.6 from Power-law distributions in empirical data by Aaron Clauset, Cosma Rohilla Shalzi, and M. E. J. Newman.

*This article originally appeared here. Republished with permission. Submit your copyright complaints here.*

download minecraft free1 month agoWay cool! Some extremely valid points! I appreciate you writing this

post and the rest of the site is also very good.

gamefly free trial3 weeks agoHi, I think your blog might be having browser compatibility issues.

When I look at your blog in Safari, it looks fine but when opening

in Internet Explorer, it has some overlapping.

I just wanted to give you a quick heads up! Other then that, great blog!