Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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:
and an 'unevenly' distributed distribution Y of roughly the same mean and standard deviation:
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)
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.
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.
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.
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.)
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")
Ripley.L.
$\endgroup$
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).
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".
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.
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.
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$.
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$.
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.
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.
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$.
Conversely, for the "uneven" distribution $Y$, interval sizes are either small (within clumps) or large (across clumps), leading to high variance.
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].
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.
The corresponding interval variances are:
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.
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.
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.
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.
