10
$\begingroup$

I'm attempting to find out whether some highly skewed data are drawn from a power law distribution, following the popular paper by Clauset, Shalizi and Newman, 2009.

Clauset et al. use the Kolmogorov-Smirnov (KS) statistic to measure the goodness-of-fit of the data to the hypothesised power law distribution. However, in an old paper on the Whitworth distribution by Nancy Geller, she mentions that once observations are ranked, they are no longer independently and identically distributed and therefore the KS test becomes invalid.

My question: Does this mean that the KS test is also invalid when considering any power law where a quantity x is scaled according to its rank (i.e. Zipf's law)? Or, is it still valid since Clauset et al. did a simulation test and, in Fig. 4 (p. 673), it appears as though the KS test performs fine anyway?

Apologies if this is a silly question and please feel free to point me in the right direction if I've missed something more basic here.

References

Clauset, A., C. R. Shalizi, and M. E. J. Newman. 2009. “Power-Law Distributions in Empirical Data.” SIAM Review 51 (4): 661–703. doi:10.1137/070710111

Geller, N.L. 1979, "A Test of Significance for the Whitworth Distribution", Journal of the American Society for Information Science, vol. 30, no. 4, pp. 229.

$\endgroup$
3
  • 1
    $\begingroup$ Could you (or whoever) expand on what "scaled according to its rank" means? Does this mean that every observation is rescaled with a different scale factor depending on its rank, or... $\endgroup$
    – jbowman
    Sep 14, 2021 at 3:34
  • $\begingroup$ Possibly bad wording, but all I meant by that is a situation where you have a set of observed quantities and each observation is placed on a rank scale from largest to smallest. i.e. a rank-frequency or rank-size distribution. $\endgroup$
    – JaydenM-C
    Sep 15, 2021 at 4:56
  • 1
    $\begingroup$ Do you have the initial values, or are the ranks all that are left? Ranking all by itself doesn't break the K-S test, which compares the empirical CDF to the theoretical one; the calculation of the empirical CDF necessarily involves finding the smallest observation, then the next smallest, etc. $\endgroup$
    – jbowman
    Sep 15, 2021 at 14:06

2 Answers 2

8
+50
$\begingroup$

The issue raised in the Geller paper is not about the ranking of the data, but rather that the Kolmogorov-Smirnov test has different critical values when the parameters of the distribution you are comparing against must be computed from data.

For an example, consider two problems: say we have some data $\mathbf{X}=(X_1,\dots,X_n)$, and we want to test (1) whether this is distributed Exp$(1)$ or (2) whether this is exponentially distributed at all. Let $F_\lambda$ denote the Exp$(\lambda)$ cdf and let $\mathbb{F}(x)=\frac1n\sum_{i=1}^n \mathbb{1}_{(-\infty,x]}(X_i)$ denote the empirical cdf. Then, to handle testing problem (1), we can use the Kolmogorov-Smirnov statistic $$ \text{KS}=\sup_x\,\lvert\mathbb{F}(x)-F_1(x)\rvert. $$ There's no issue there.

Consider now (2). It's harder to test this; what cdf should take the role of $F_1$ when we don't know the parameter of the exponential distribution? Well, one strategy is to guess the best parameter $\lambda$, say by the MLE $\hat\lambda$ and compare against $F_{\hat\lambda}$: $$ \text{KS}'=\sup_x\,\lvert\mathbb{F}(x)-F_{\hat\lambda}(x)\rvert. $$ But now, this will change the distribution of the K-S statistic, and a correction must be made. Geller refers to some work by Durbin describing appropriate critical values for $\text{KS}'$ obtained from its asymptotic distribution.

Okay, so, we can see the issue for the power law paper: Clauset et al. want to estimate parameters and do a KS test. So, they have the same problem, they are not comparing against a fixed cdf but rather one that is estimated from data.

They get around this by simulating the $p$ value, rather than relying on any asymptotic results. Their procedure is as follows. Let $\mathbf{X}=(X_1,\dots,X_n)$ again be your data.

  1. Estimate the parameters $\hat\theta$ of the power law distribution from your data.
  2. Draw many simulated datasets $\mathbf{X}'_{b}$, $b=1,\dots,B$ from the power law distribution with parameters $\hat\theta$.
  3. For each $b=1,\dots,B$, estimate the parameters of the power law from the simulated dataset $\mathbf{X}'_{b}$, giving a new estimate $\hat\theta'_b$.
  4. Now, compute the KS statistic for the original dataset: $$ \text{KS}=\sup_x\,\lvert\mathbb{F}(x)-G_{\hat\theta}(x)\rvert, $$ where $G_\theta$ is the cdf of the power law with parameters $\theta$. (Actually, in the paper it is a little more subtle, since they also model parts of the data before it enters its power law tail; I'm simplifying to get at the gist, but $G$ should be the cdf from their fitted model.)
  5. For each simulated dataset $b=1,\dots,B$, compute $$ \text{KS}'_b=\sup_x\,\lvert\mathbb{F}'_b(x)-G_{\hat\theta'_b}(x)\rvert, $$ where $\mathbb{F}'_b$ is the empirical cdf of $\mathbf{X}'_b$.
  6. Now let $\hat{p}$ be the fraction of simulated datasets $b$ for which $\text{KS}'_b>\text{KS}$.

This is an elaboration of the procedure described on page 677 in the paper. Simulation based tests like this don't rely on any asymptotic results about the underlying statistic, so this procedure is another way of dealing with the problem (like Durbin did for the exponential -- one could also have done the same simulation procedure there, drawing simulated Exp$(\hat\lambda)$ replicates). Clauset et al. address the issue pointed out in this question and by Geller in footnote 7 at the bottom of page 677, but the point is: simulation means we don't need to worry.

I'll end with a general note: simulating $p$ values is a common way to test goodness of fit without having to do a bunch of math. The idea is, if you have some statistic, you can just see if it looks weird compared to the distribution of that statistic under your model. You just approximate that distribution by sampling from your model. It could be K-S statistic or really anything. If it looks weird, you can be like, hey my model is wrong, the empirical statistic is not what the model would like to produce. I like to plot the empirical statistic on top of the histogram of simulated ones rather than compute a $p$ value but to each their own.

$\endgroup$
2
  • $\begingroup$ (+1) This is a very thorough answer. I'm not going to award the bounty just yet because I want to draw attention to this answer, and give other folks the opportunity to post their own. This should net you several more upvotes in the meantime. $\endgroup$
    – Sycorax
    Sep 15, 2021 at 14:54
  • $\begingroup$ haha, thanks Sycorax $\endgroup$ Sep 15, 2021 at 14:54
4
$\begingroup$

TL;DR

However, in an old paper on the Whitworth distribution by Nancy Geller, she mentions that once observations are ranked, they are no longer independently and identically distributed and therefore the KS test becomes invalid.

Clauset et al. are using the KS statistic and not the KS test. Geller states that you can not use the KS test, but not that you can not use the KS statistic. So there is no contradiction.

In addition, it seems that Geller is referring to another problem than the mere ranking of observations. The problem with that case of the Whitworth distribution is because of the correlation between variables.

Clauset, Shalizi, and Newman, 2009

Clauset et al. use the Kolmogorov-Smirnov (KS) statistic to measure the goodness-of-fit of the data to the hypothesized power-law distribution.

The KS statistic is indeed used by Clauser et al., but this is not the same as a KS test (which means comparing it with the Kolmogorov distribution). It is only the KS test which would be wrong.

The KS statistic is used in two ways:

  • They use the KS statistic as a distance measure for fitting

    Our estimate $\hat{x}_{min}$ is then the value of ${x}_{min}$ that minimizes $D$

  • They use the KS statistic as a distance measure to test goodness of fit, by using bootstrapping. This bootstrapping circumvents the problem with the KS distribution for the KS statistic being wrong (which is the issue that Geller mentions). Instead of using the KS distribution as the distribution for the KS statistic under the null hypothesis, one estimates an empirical distribution for this statistic by simulations.

    This distance is compared with distance measurements for comparable synthetic data sets drawn from the same model, and the $p$-value is defined to be the fraction of the synthetic distances that are larger than the empirical distance.

Geller, 1979

Geller is concerned with a test of whether a certain sample follows a Whitworth distribution.

  • The model for this distribution is randomly breaking a stick of length 1 into $n$ pieces, by randomly selecting $n-1$ points on the stick using a uniform distribution.

  • Alternative construction.

    Geller mentions that the distribution for the piece of the stick follows some sort of exponential distribution. Let there be $n$ iid $Y_i \sim Exp(1)$ then the lengths of the sticks are distributed as $X_i = Y_i /\sum_{j=1}^n Y_j$

    This can be seen intuitively by the following equivalent construction of the broken stick:

    You could make a similar stick broken into $n$ pieces by considering a Poisson process in which the distance between events is exponentially distributed. You compose the $n$ pieces by drawing their lengths from an exponential distribution and composing the entire stick by putting the pieces together. This stick has a variable length, but you could scale all the pieces by the total length of the pieces such that the stick becomes of length 1. Because the sticks are related to a Poisson process the breakpoints are uniformly distributed. So you get a stick broken into $n$ pieces where the breakpoints are distributed according to a uniform distribution.


The problem with "once observations are ranked, they are no longer independently and identically distributed"

I am not sure what actually is supposed to be meant by testing the hypothesis of a Whitworth distribution with the KS test in connection with the idea that the ranking causes the problems. But, I can make the following from it:

  • Using a KS test The Whitworth distribution is a joint distribution (in fact the stick-breaking is a special case of a Dirichlet distribution with $\alpha_i = 1$ for each $i$) and related to the entire sample whose components are sampled at once. It is not like the stick lengths (or whatever variable/process replaces the stick-breaking) are each independently sampled according to the marginal distribution (which would be a beta distribution).

    Possibly the idea of naively applying the KS test is that the ranked sticks are to be compared with their marginal distribution. That would indeed be not correct.

    The single stick lengths $X_i$ are distributed according to a Beta distribution with parameters $1$ and $n-1$. But, because of the correlation between the $X_i$, you are not supposed to arrange the stick lengths and compare the experimental CDF with the CDF of the beta distribution.

  • The ranking causing problems. The reason why you can not apply the KS test in that way is that the lengths of the sticks are correlated. It is not so much because of the ranking. If you would draw independently from the beta distribution and order the sample then this would be fine.

    So the problem is not in the ranking, but in the individuals from the sample not being generated as independent draws. (if you break a big piece from the stick, then the next ones will be smaller)

The trick by Geller is the realization that testing the goodness of fit for the correlated lengths $X_i$ is similar to testing the goodness of fit for the uncorrelated variables $Y_i$ but with a KS statistic based on an exponential distribution whose rate parameter is estimated/fitted by the sum of the entire sample.

For this situation where the KS statistic is not applied to a single apriori-defined distribution, but instead to a distribution whose parameters are fitted (that rate parameter in the exponential distribution), they refer to the work by Durbin.

In the work by Clauset et al the goodness of fit is also performed after fitting some parameters. The standard KS test would not be good in their case either (like in the case of Geller). But as mentioned before, they are not doing the standard KS test and they use a bootstrapping method instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.