19
$\begingroup$

I looked up on the web, but couldn't find anything helpful.

I'm basically looking for a way to measure how 'evenly' a value is distributed. As in, an 'evenly' distributed distribution like X: enter image description here

and an 'unevenly' distributed distribution Y of roughly the same mean and standard deviation: enter image description here

But is there any evenness measure m, such that m(X) > m(Y)? If there isn't, what would be the best way to create a measure like this?

(Images screenshot from Khan Academy)

$\endgroup$
9
  • 1
    $\begingroup$ What about skew? $\endgroup$ Commented Nov 4, 2014 at 19:07
  • 1
    $\begingroup$ Entropy is nice for discrete distributions having the same support. But I don't know whether it is nice for continuous distributions. $\endgroup$ Commented Nov 4, 2014 at 19:55
  • $\begingroup$ Are you sure that dot plot is what you want? I don't think you really mean to ask about uniformity. This sounds like a question about "clumpiness" or "degree of clustering" or even multimodality. $\endgroup$ Commented Nov 4, 2014 at 20:29
  • $\begingroup$ @StéphaneLaurent - I was recommended entropy by a few others as well. Could you please take the time and elaborate a bit on it? $\endgroup$
    – Ketan
    Commented Nov 4, 2014 at 20:38
  • 1
    $\begingroup$ You need to more clearly define what you mean by "evenly distributed". My literal minded brain say that data such 1,4,7,10,13,... are perfectly evenly distributed. But you might mean something entirely different. $\endgroup$ Commented Nov 12, 2014 at 4:43

6 Answers 6

23
$\begingroup$

A standard, powerful, well-understood, theoretically well-established, and frequently implemented measure of "evenness" is the Ripley K function and its close relative, the L function. Although these are typically used to evaluate two-dimensional spatial point configurations, the analysis needed to adapt them to one dimension (which usually is not given in references) is simple.


Theory

The K function estimates the mean proportion of points within a distance $d$ of a typical point. For a uniform distribution on the interval $[0,1]$, the true proportion can be computed and (asymptotically in the sample size) equals $1 - (1-d)^2$. The appropriate one-dimensional version of the L function subtracts this value from K to show deviations from uniformity. We might therefore consider normalizing any batch of data to have a unit range and examining its L function for deviations around zero.


Worked Examples

To illustrate, I have simulated $999$ independent samples of size $64$ from a uniform distribution and plotted their (normalized) L functions for shorter distances (from $0$ to $1/3$), thereby creating an envelope to estimate the sampling distribution of the L function. (Plotted points well within this envelope cannot be significantly distinguished from uniformity.) Over this I have plotted the L functions for samples of the same size from a U-shaped distribution, a mixture distribution with four obvious components, and a standard Normal distribution. The histograms of these samples (and of their parent distributions) are shown for reference, using line symbols to match those of the L functions.

Figure

The sharp separated spikes of the U-shaped distribution (dashed red line, leftmost histogram) create clusters of closely spaced values. This is reflected by a very large slope in the L function at $0$. The L function then decreases, eventually becoming negative to reflect the gaps at intermediate distances.

The sample from the normal distribution (solid blue line, rightmost histogram) is fairly close to uniformly distributed. Accordingly, its L function does not depart from $0$ quickly. However, by distances of $0.10$ or so, it has risen sufficiently above the envelope to signal a slight tendency to cluster. The continued rise across intermediate distances indicates the clustering is diffuse and widespread (not confined to some isolated peaks).

The initial large slope for the sample from the mixture distribution (middle histogram) reveals clustering at small distances (less than $0.15$). By dropping to negative levels, it signals separation at intermediate distances. Comparing this to the U-shaped distribution's L function is revealing: the slopes at $0$, the amounts by which these curves rise above $0$, and the rates at which they eventually descend back to $0$ all provide information about the nature of the clustering present in the data. Any of these characteristics could be chosen as a single measure of "evenness" to suit a particular application.

These examples show how an L-function can be examined to evaluate departures of the data from uniformity ("evenness") and how quantitative information about the scale and nature of the departures can be extracted from it.

(One can indeed plot the entire L function, extending to the full normalized distance of $1$, to assess large-scale departures from uniformity. Ordinarily, though, assessing the behavior of the data at smaller distances is of greater importance.)


Software

R code to generate this figure follows. It starts by defining functions to compute K and L. It creates a capability to simulate from a mixture distribution. Then it generates the simulated data and makes the plots.

Ripley.K <- function(x, scale) {
  # Arguments:
  # x is an array of data.
  # scale (not actually used) is an option to rescale the data.
  #
  # Return value:
  # A function that calculates Ripley's K for any value between 0 and 1 (or `scale`).
  #
  x.pairs <- outer(x, x, function(a,b) abs(a-b))  # All pairwise distances
  x.pairs <- x.pairs[lower.tri(x.pairs)]          # Distances between distinct pairs
  if(missing(scale)) scale <- diff(range(x.pairs))# Rescale distances to [0,1]
  x.pairs <- x.pairs / scale
  #
  # The built-in `ecdf` function returns the proportion of values in `x.pairs` that
  # are less than or equal to its argument.
  #
  return (ecdf(x.pairs))
}
#
# The one-dimensional L function.
# It merely subtracts 1 - (1-y)^2 from `Ripley.K(x)(y)`.  
# Its argument `x` is an array of data values.
#
Ripley.L <- function(x) {function(y) Ripley.K(x)(y) - 1 + (1-y)^2}
#-------------------------------------------------------------------------------#
set.seed(17)
#
# Create mixtures of random variables.
#
rmixture <- function(n, p=1, f=list(runif), factor=10) {
  q <- ceiling(factor * abs(p) * n / sum(abs(p)))
  x <- as.vector(unlist(mapply(function(y,f) f(y), q, f)))
  sample(x, n)
}
dmixture <- function(x, p=1, f=list(dunif)) {
  z <- matrix(unlist(sapply(f, function(g) g(x))), ncol=length(f))
  z %*% (abs(p) / sum(abs(p)))
}
p <- rep(1, 4)
fg <- lapply(p, function(q) {
  v <- runif(1,0,30)
  list(function(n) rnorm(n,v), function(x) dnorm(x,v), v)
  })
f <- lapply(fg, function(u) u[[1]]) # For random sampling
g <- lapply(fg, function(u) u[[2]]) # The distribution functions
v <- sapply(fg, function(u) u[[3]]) # The parameters (for reference)
#-------------------------------------------------------------------------------#
#
# Study the L function.
#
n <- 64                # Sample size
alpha <- beta <- 0.2   # Beta distribution parameters

layout(matrix(c(rep(1,3), 3, 4, 2), 2, 3, byrow=TRUE), heights=c(0.6, 0.4))
#
# Display the L functions over an envelope for the uniform distribution.
#
plot(c(0,1/3), c(-1/8,1/6), type="n", 
     xlab="Normalized Distance", ylab="Total Proportion",
     main="Ripley L Functions")
invisible(replicate(999, {
  plot(Ripley.L(x.unif <- runif(n)), col="#00000010", add=TRUE)
}))
abline(h=0, lwd=2, col="White")
#
# Each of these lines generates a random set of `n` data according to a specified
# distribution, calls `Ripley.L`, and plots its values.
#
plot(Ripley.L(x.norm <- rnorm(n)), col="Blue", lwd=2, add=TRUE)
plot(Ripley.L(x.beta <- rbeta(n, alpha, beta)), col="Red", lwd=2, lty=2, add=TRUE)
plot(Ripley.L(x.mixture <- rmixture(n, p, f)), col="Green", lwd=2, lty=3, add=TRUE)
#
# Display the histograms.
#
n.breaks <- 24
h <- hist(x.norm, main="Normal Sample", breaks=n.breaks, xlab="Value")
curve(dnorm(x)*n*mean(diff(h$breaks)), add=TRUE, lwd=2, col="Blue")
h <- hist(x.beta, main=paste0("Beta(", alpha, ",", beta, ") Sample"), 
          breaks=n.breaks, xlab="Value")
curve(dbeta(x, alpha, beta)*n*mean(diff(h$breaks)), add=TRUE, lwd=2, lty=2, col="Red")
h <- hist(x.mixture, main="Mixture Sample", breaks=n.breaks, xlab="Value")
curve(dmixture(x, p, g)*n*mean(diff(h$breaks)), add=TRUE, lwd=2, lty=3, col="Green")
$\endgroup$
6
  • 1
    $\begingroup$ I work mostly in Numpy, and at times in SciPy. Do you have any idea if this measure is available in any stats python library? Searching for it doesn't return anything relevant. $\endgroup$
    – Ketan
    Commented Nov 5, 2014 at 20:18
  • $\begingroup$ The L function probably is not available, because it is usually coded for two or more dimensions. The algorithm is simple, as you can see from the implementation here: compute the empirical cumulative distribution function of the distances between all distinct pairs of data and then adjust as shown in Ripley.L. $\endgroup$
    – whuber
    Commented Nov 5, 2014 at 20:23
  • $\begingroup$ Is the measure variance agnostic or variance dependent? $\endgroup$
    – Ketan
    Commented Nov 6, 2014 at 11:20
  • 1
    $\begingroup$ The basic procedure I described here normalizes the data to make the range correspond to the interval $[0,1]$. As such it is "variance agnostic." However, that makes it sensitive to outliers. (This issue can be a severe problem in higher dimensions.) One can overcome that limitation by normalizing, say, to a quantile range (such as the IQR) and making a suitable adjustment in the $1-(1-d)^2$ correction for the L function. This would make the resulting L-function nonparametric and robust, which I think addresses the concern behind your comment. $\endgroup$
    – whuber
    Commented Nov 6, 2014 at 14:39
  • $\begingroup$ You said "This issue can be a severe problem in higher dimensions". It has been adapted for univariate arrays, right? I'm not entirely sure if I understood everything well. Could you please write Ripley.L in any other language or in pseudocode? Or you could just comment the existing code a bit or at least format Ripley.L to multiple lines to enhance its readability. Lack of any proper documentation at statsmodels.sourceforge.net/stable/generated/…, isn't helping me much anyway. $\endgroup$
    – Ketan
    Commented Nov 6, 2014 at 19:26
6
$\begingroup$

I assume that you want to measure how close is the distribution to the uniform.

You can look on the distance between cumulative distribution function of uniform distribution and the empirical cumulative distribution function of the sample.

Let's assume that the variable is defined on the set $\{1,2,3,4,5\}$. Then the uniform distribution have the cdf $F_u(x)$ given by

$$F_u(x) = \sum_{i=1}^{[x]} 1/5 .$$

Now, assume that your sample $X$ is $1,3,5$. Then the empirical distribution of $X$ is

$$ F_X(1) = 1/3, F_X(2) = 1/3, F_X(3) = 2/3, F_X(4) = 2/3, F_X(5) = 1 $$

And let sample $Y$ be $1,1,5$. Then the empirical distribution of $Y$ is

$$ F_Y(1) = 2/3, F_Y(2) = 2/3, F_Y(3) = 2/3, F_Y(4) = 2/3, F_Y(5) = 1 $$

Now, as a measure of distance between distributions let's take the sum of distances at each point, i.e.

$$ d(F,G) = \sum_{i=1}^5 | F(x) - G(x)|. $$

You can easily find out that $d(F_u,F_X) < d(F_u,F_Y) $.

In more complicated cases you need to revise the norm used above, but the main idea remains the same. If you need testing procedure, it may be good to use norms for which tests are developped (the ones that @TomMinka pointed out).

$\endgroup$
9
  • $\begingroup$ Some other popular measures of distance to a distribution are the Kolmogorov–Smirnov test and Anderson–Darling test. $\endgroup$
    – Tom Minka
    Commented Nov 4, 2014 at 19:41
  • $\begingroup$ Hi. Thanks for the answer. Kindly revisit the updated question for disambiguation, and let me know if your answer applies to it. If it does. I'll have to verify it. $\endgroup$
    – Ketan
    Commented Nov 4, 2014 at 19:46
  • $\begingroup$ Yes, my answer applies to it, as long as 'even' means 'uniform'. $\endgroup$ Commented Nov 4, 2014 at 19:47
  • $\begingroup$ Okay. Could you kindly elaborate on the answer a little. $\endgroup$
    – Ketan
    Commented Nov 4, 2014 at 19:49
  • $\begingroup$ @TomMinka thanks, definitly norms these norms are even better, since there is a testing procedure developped. $\endgroup$ Commented Nov 4, 2014 at 19:50
2
$\begingroup$

If I understand your question correctly, the "most even" distribution for you would be one where the random variable takes every observed value once—uniform in a sense. If there are "clusters" of observations at the same value, that would be uneven. Assuming we are talking discrete observations, perhaps you could look at both the average difference between the probability mass points, the maximum difference or maybe how many observations have a difference from the "average" over a certain threshold.

If it were truly uniform in the observations, all PM points should have equal value, and the difference between max and min is 0. The closer the average difference is to 0, the more "even" the bulk of the observations are, the lower the maximum difference and the fewer "peaks" there are also goes to show how "even" the empirical observations are.

Update Of course, you can use a chi-square test for uniformity or compare the empirical distribution function with a uniform, but in those cases, you will be penalized by any large "gaps" in observations, even though the distributions of observations are still "even".

$\endgroup$
1
  • $\begingroup$ For a given set of possible values, I want to basically model how 'rare' or 'peculiar' it would be have a particular value from that set of values. In lack of any other options, I'm trying to measure how evenly or uniformly distributed the values are. The more even the distribution, the less chance there is to have any peculiar value from the set. Whereas, if for example all the data lies in the extremes of a distribution, any value can be something worthy to be considered as 'peculiar'. I hope you get it? $\endgroup$
    – Ketan
    Commented Nov 4, 2014 at 20:47
2
$\begingroup$

Clumpiness detection

Ripley's L function, as noted and nicely illustrated by @whuber, will generate an indicator of "clumpiness" (i.e. amount of clustering) in the distribution for a given target distance (or normalized distance). The same is true for the discrepancy metric outlined in Martin Roberts' answer, which is spiritually similar to Ripley's L function but computes the maximum difference from uniformity observed within a given interval, instead of a proportion for a given distance. A nice practical example of using Ripley's family of functions to detect "clumps" in a 2D scenario is given in this article by Kiskowski et al.

Issues

In both Ripley's L function and discrepancy, some target distance/interval needs to be specified. If you need a summary statistic for "clumpiness" (i.e. how even/uneven your distribution is independently of a specific distance/interval), you can examine Ripley's L function, as proposed by @whuber, and derive different statistics, but it is not obvious how to go about it.

Side note

Given a distance value $d$, the Ripley's K function $K(d)$ returns the fraction of observed distances below $d$, among all the pairwise distances in your data. Then Ripley's L is defined as $L(d)=K(d)-K_u(d)$, where $K_u(d)$ is the value of K(d) for a perfectly uniform distribution. In @whuber’s reply $K_u(d)=1 - (1-d)^2$. This is true for the continuous case, but only asymptotically true for the discrete case. The exact solution for the discrete case would be $\frac{M^2-(M-d)(M-d+1)-M}{M^2-M}$, where $M$ is the number of distinct observable positions. Note that here we are assuming that for the discrete case the range of positions is not normalized to $[0,1]$ and can be described as $[0,M)$. So, $M$ could also represent the resolution with which we observe positions. Here is a visual proof of the formula for the discrete case with $10$ distinct positions ($M=10$) and $d=3$.

Graphical derivation of Ripley's L function formula

There are $M^2=100$ pairwise distances. Those below $d=3$ are colored in blue. The number of white cells is $(M-d)(M-d+1)=56$. Therefore, the number of blue cells is $M^2-(M-d)(M-d+1)$=44. Note that it’s common practice to avoid considering the distance of an element with itself, so the $0$-valued cells on the diagonal are not going to be counted, giving us a number of distances below $d$ of $M^2-(M-d)(M-d+1)-M$ out of a total of $M^2-M$.


Binning-based approaches

Alternative metrics can be devised using a binning approach. By defining regularly spaced bins over the range of observations (or, if known, the domain of the sampled distribution), one can define the distribution of data points across the bins (either as absolute numbers or relative frequencies).

The entropy of this distribution can then be computed as follows:

$-\sum_{i=1}^{b}f(x_i)·log_2(f(x_i))$

where $b$ is the number of bins and $f(x_i)$ the relative frequency of observations in bin $i$ (i.e. counts in bin $i$ over total counts).

In other words, we are splitting our range into bins and then asking how uniform (high entropy) or non-uniform (low entropy) our counts of observations in each bin are. Using the same binning approach, other measures of inequality, like the Gini coefficient, can be used. A practical example of this approach, using both entropy and Gini coefficient, can be found in this article by Mascolo et al.

Issues

Binning-based approaches directly generate a summary statistic (the overall positional entropy, or Gini coefficient). They do not require that we specify a distance/interval at which we want to evaluate "clumpiness", but they require that we define a bin size, which will affect the counts and the resulting statistic. Therefore, bin size indirectly defines the scale at which one wants to detect clustering, similarly to the choice of $d$ for Ripley’s functions. Binning also introduces artifacts by arbitrarily chunking the sequence at regular intervals, which could potentially result in missing a clump that sits across two bins. A simple way to make results less dependent on the binning frame is to use two sets of bins with an offset of half the bin size, as described here by Mascolo et al.

If you are interested in the statistical significance of the observed unevenness of your distribution, keep in mind that this method (as the others) is sensitive to the number of datapoints. Getting low entropy values by chance is easier for small samples. As the sample size increases, the expected value of the entropy approaches the theoretical maximum $-\sum_{i=1}^{b}1/b·log_2(1/b)=-log_2(1/b)=log_2(b)$ where $b$ is the number of bins. Therefore, remember to control for sample size when comparing experiments. So far there’s no exact solution to the problem of finding the expected value of entropy, given the sample size and the number of bins.


Interval variance

If you want to obtain a summary statistic that indicates the evenness/unevenness of a one-dimensional distribution, as outlined in the question, and that does not require you to specify a given distance/interval/bin size at which to analyze clumpiness, an easy solution is to use the variance of the intervals.

That is, we take our observations, sort them, and compute the distance among each consecutive observation (i.e. the length of the interval between two consecutive data points).

Given a sample $x_1,\ldots,x_N\in{X}$ of size $N$ for a given distribution, we define the interval series $i_{x_2-x_1},\ldots,i_{x_{N}-x_{N-1}}\in{I}$, of length $N-1$.

Intuitively, for the "even" distribution $X$ introduced by @Ketan in their question, all the intervals are exactly the same and their variance is therefore $0$.

Original question illustration: uniform

Conversely, for the "uneven" distribution $Y$, interval sizes are either small (within clumps) or large (across clumps), leading to high variance.

Original question illustration: uniform

Shown below are five $N=64$ samples from a uniform distribution in $[-5,+5]$ [top], and five $N=64$ samples for a "clumped" distribution in the same domain (with four uniformly distributed clumps centered at $-4 [\pm0.5]$, $-2 [\pm0.75]$, $1.5 [\pm0.25]$ and $3.75 [\pm0.5]$) [bottom].

Uniform and clumped distribution samples

The corresponding interval histograms are shown below. Notice that samples from clumped distributions (5 rightmost bars in each bin) have many more small intervals (from within clumps) than the uniform samples (5 leftmost bars in each bin). The samples from clumped distributions also have several (inter-clump) large interval values that are completely absent in the uniform samples.

Intervals distribution

The corresponding interval variances are:

  • Uniform distribution samples: $0.025\pm0.005$
  • Clumped distribution samples: $0.137\pm0.009$

which recapitulate our intuition that "clumped" distributions should have larger interval variance.

A practical example of this measure is illustrated in this article by Philip and Freeland.

Issues

A finite random sample from a uniform distribution will not be perfectly even, regardless of the measure of evenness/unevenness/clumpiness chosen. As sample size increases, the expected value of the interval variance approaches 0, just like the Gini coefficient and the value of the Ripley’s L function, while entropy reaches its theoretical maximum $log(b)$. But if the sample size is not large enough, the expected value can be far from that.

When comparing results to an ideal perfectly uniform sample, you should be aware that these metrics are biased. With the binning-based approaches one can increase bin size, while with Ripley’s functions one can increase the value of $d$. But there is no way to control for that with the variance of the intervals. Keep that in mind if you plan to apply it to small samples, which are very prone to picking up noise in the form of natural variance among the intervals of uniformly distributed points.

$\endgroup$
1
$\begingroup$

The measure you are looking for is formally called discrepancy.

The one-dimensional version is as follows:

Let $I=[a,b)$ denote the half-open interval and consider a finite sequence $x_1,\ldots,x_N\in{I}$.

For a subset $J\subset{I}$, let $A(J,N)$ denote the number of elements of this sequence inside $J$.

That is, $$ A(J,N)=\left|\{x_1,\ldots,x_N\}\cap{J}\right|, $$ and let $V(J)$ denote the volume of $J$.

The discrepancy of the sequence $x_1,\ldots,x_N$ is defined as $$ > D_N=\sup_{J}{\left|A(J,N)-V(J)\cdot{N}\right|}, $$ where the supremum is taken over all half-open subintervals $J=\prod_{j=1}{[0,t_j)}$, with $0\leq{t_j}\leq1$.

The discrepancy thus compares the actual number of points in a given volume with the expected number of points in that volume, assuming the sequence $x_1,\ldots,x_N$ is uniformly distributed in $I$.

Low discrepancy sequences are often called quasirandom sequences.

A basic overview of low discrepancy sequences can be found here, and my blog post "The unreasonable effectiveness of quasirandom sequences" compares various methods when applied to Numerical Integration, mapping points to the surface of a sphere, and quasiperiodic tiling.

$\endgroup$
0
$\begingroup$

It sounds like you are interested in the pairwise differences of randomly observed values in a particular sequence, as in the case of modeling growth or trend. There are a number of ways to do so in time series analyses. A very basic approach is just a simple linear model regressing the sequence values upon their index values. In the first case, your linear model would give you a singular regression coefficient of 1 (predictive $R^2 = 1$). In the later case, this would be a coefficient of 1.51 and an $R^2$ of 0.78.

$\endgroup$
6
  • $\begingroup$ I don't know if I understood clearly enough what you meant, but I simply need to understand how 'evenly' something is distributed in a distribution. Variance is not that useful given that one can get the same variance and mean for two very differently distributed distributions. $\endgroup$
    – Ketan
    Commented Nov 4, 2014 at 19:26
  • $\begingroup$ @Ketan, you changed your question substantially. Either way, I am not clear what that might be. In any regard, it's clear that my answer is not addressing what you are interested in based on the most recent version of your question. $\endgroup$
    – AdamO
    Commented Nov 4, 2014 at 20:05
  • $\begingroup$ For a given set of possible values, I want to basically model how 'rare' or 'peculiar' it would be have a particular value from that set of values. In lack of any other options, I'm trying to measure how evenly or uniformly distributed the values are. The more even the distribution, the less chance there is to have any peculiar value from the set. Whereas, if for example all the data lies in the extremes of a distribution, any value can be something worthy to be considered as 'peculiar'. I hope you get it? $\endgroup$
    – Ketan
    Commented Nov 4, 2014 at 20:48
  • $\begingroup$ No, sorry still not following. Just to verify, are you familiar with the formal definition of "uniformly" distributed data? A "normal" distribution, for example, is not uniform. Both are symmetric. You seem to allude to whether symmetry might be of interest, but then you seem to say that the probability of sampling "rare" values is of interest. For instance, a Cauchy distribution is symmetric, but is known to be an example of a distribution that will generate outliers as a probability model. $\endgroup$
    – AdamO
    Commented Nov 4, 2014 at 20:58
  • $\begingroup$ Let me put it this way: Each set is simply the set of all values of a particular attribute in a dataset. I basically want to quantify each attribute by how 'stable' its values are, for which I've been using simple variance till now. But last night, I realized that exactly same variance and mean is possible for 2 attributes, even though one could be 'even', and other having most of the values in 2 extremes. Hence now I want an additional measure to measure if the values can be found evenly, or do they reside more in the extremes. $\endgroup$
    – Ketan
    Commented Nov 5, 2014 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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