# Order Statistics and Benford's Law

Authors: Steven J. Miller; Mark J. Nigrini
Journal: International Journal of Mathematics and Mathematical Sciences
 (2008)

---

## Abstract

Fix a baseB>1 and let ζ have the standard exponential
distribution; the distribution of digits of ζ base B is
known to be very close to Benford's law. If there exists a C such
that the distribution of digits of C times the elements of some set is the same as that of ζ, we say that set exhibits
shifted exponential behavior base B. Let X1,…,XN be i.i.d.r.v. If the Xi's are Unif, then as N→∞ the distribution
of the digits of the differences between adjacent order statistics
converges to shifted exponential behavior. If instead Xi's  come from a compactly supported distribution with uniformly bounded first and second derivatives and a second-order Taylor series expansion at each point, then the distribution of digits of any Nδ consecutive differences and all N−1 normalized
differences of the order statistics exhibit shifted exponential behavior.
We derive conditions on the probability density which determine
whether or not the distribution of the digits of all the
unnormalized differences converges to Benford's law, shifted exponential behavior, or oscillates between the two, and show that the Pareto distribution leads to oscillating behavior.


---

## Body

## 1. Introduction

Benford's law gives the expected frequencies of the
digits in many tabulated data. It was first observed by Newcomb in the 1880s,
who noticed that pages of numbers starting with a1 in logarithm tables were significantly more
worn than those starting with a 9.
In 1938 Benford [1] observed the same digit bias in a variety of
phenomena. From his observations, he
postulated that in many datasets, more numbers began with a 1 than with a 9;
his investigations  (with 20,229 observations) supported his belief. See [2, 3] for a description and history, and [4] for an extensive bibliography.For any baseB>1,
we may uniquely write a positive x∈ℝ as x=MB(x)⋅Bk,
where k∈ℤ and MB(x) (called the mantissa) is in [1,B).
A sequence of positive numbers {an} is Benford baseB if the probability of observing a mantissa of an base B of at most s is logBs.
More precisely, for s∈[1,B],
we have(1.1)limN→∞#{n≤N:1≤MB(αn)≤s}N=logBs. Benford behavior for
continuous functions is defined analogously. (If the functions are not
positive, we study the distribution of the digits of the absolute value of the
function.) Thus, working base 10 we find the probability of observing a first   the
probability of observing a first digit of d is log10(d+1)−log10(d),
implying that about 30% of the time the first digit is a 1.We can prove many mathematical systems
follow Benford's law, ranging from recurrence
relations [5] to n! [6] to iterates of power, exponential and
rational maps, as well as Newton's method [7–9]; to chains of random
variables and hierarchical Bayesian models [10]; to values of L-functions near the critical line; to
characteristic polynomials of random matrix ensembles and iterates of the 3x+1-Map [11, 12]; as well as to products of
random variables [13]. We also see Benford's law in a variety of natural
systems, such as atomic physics [14], biology [15], and geology [16].
Applications of Benford's law range from rounding errors in computer
calculations (see [17, page 255]) to detecting tax (see [18, 19]) and voter
fraud (see [20]).This work is motivated by two observations (see Remark1.9 for more
details). First, since Benford's seminal paper, many investigations have shown
that amalgamating data from different sources leads to Benford behavior;
second, many standard probability distributions are close to Benford behavior.
We investigate the distribution of digits of differences of adjacent ordered
random variables. For any δ<1,
if we study at most Nδ consecutive differences of a dataset of size N,
the resulting distribution of leading digits depends very weakly on the
underlying distribution of the data, and closely approximates Benford's law. We
then investigate whether or not studying all the differences leads to Benford
behavior; this question is inspired by the first observation above, and has led
to new tests for data integrity (see [21]). These tests are quick and
easy-to-apply, and have successfully detected problems with some datasets, thus
providing a practical application of our main results.Proving our results requires analyzing the
distribution of digits of independent random variables drawn from the standard
exponential, and quantifying how close the distribution of digits of a random
variable with the standard exponential distribution is to Benford's law.
Leemis et al. [22] have observed that the standard exponential
is quite close to Benford's law; this was proved by Engel and Leuenberger [23],
who showed that the maximum difference in the cumulative distribution function
from Benford's law (base 10) is at least .029 and at most .03. We provide
an alternate proof of this result in the appendix using a different technique,
as well as showing that there is no base B such that the standard exponential
distribution is Benford base B (Corollary A.2).Both proofs apply Fourier analysis to periodic
functions. In [23, equation (5)], the main step is interchanging an integration and a
limit. Our proof is based on applying Poisson summation to the derivative of
the cumulative distribution function of the logarithms modulo 1, FB.
Benford's law is equivalent to FB(b)=b,
which by calculus is the same as FB′(b)=1 and FB(0)=0.
Thus, studying the deviation of FB′(b) from 1 is a natural way to investigate the deviations
from Benford behavior. We hope the details of these calculations may be of use
to others in investigating related problems (Poisson summation has been
fruitfully used by Kontorovich and Miller [11] and Jang et al. [10] in proving many systems are Benford's; see also [24]).


### 1.1. Definitions

A sequence{an}n=1∞⊂[0,1] is equidistributed if(1.2)limN→∞#{n:n≤N,an∈[a,b]}N=b−a∀[a,b]⊂[0,1].Similarly, a continuous random
variable on [0,∞),
whose probability density function is p,
is equidistributed modulo 1 if(1.3)limT→∞∫0Tχa,b(x)p(x)dx∫0Tp(x)dx=b−a,for any [a,b]⊂[0,1],
where χa,b(x)=1 for xmod1∈[a,b] and 0 otherwise.A positive sequence (or values of a function) is
Benford baseB if and only if its base B logarithms are equidistributed modulo 1;
this equivalence is at the heart of many investigations of Benford's law (see
[6, 25] for a proof).We use the following notations for the various error
terms.(1)
Letℰ(x) denote an error of at most x in absolute value; thus f(b)=g(b)+ℰ(x) means |f(b)−g(b)|≤x.(2)
Big-Oh notation: forg(x) a nonnegative function, we say f(x)=O(g(x)) if there exist an x0 and a C>0 such that, for all x≥x0, |f(x)|≤Cg(x).The following theorem is the starting point for
investigating the distribution of digits of order statistics.Theorem 1.1.
Letζ have the standard (unit) exponential
distribution(1.4)Prob(ζ∈[α,β])=∫αβe−tdt,[α,β]∈[0,∞).For b∈[0,1],
let FB(b) be the cumulative distribution function of logBζmod1;
thus FB(b):=Prob(logBζmod1∈[0,b]).
Then, for all M≥2,(1.5)FB′(b)=1+2∑m=1∞Re(e−2πimbΓ(1+2πimlogB))=1+2∑m=1M−1Re(e−2πimbΓ(1+2πimlogB))+ℰ(42πc1(B)e−(π2−c2(B))M/logB),where c1(B),c2(B) are  constants such that for  all m≥M≥2,
one has (1.6)e2π2m/logB−e−2π2m/logB≥e2π2m/logBc12(B),mlogB≤e2c2(B)m/logB,1−e(π2−c2(B))M/logB≥12.For B∈[e,10], take c1(B)=2 and c2(B)=1/5,
which give(1.7)Prob(logζmod1∈[a,b])=b−a+2rπ⋅sin(π(b+a)+θ)⋅sin(π(b−a))+ℰ(6.32⋅10−7),with r≈0.000324986, θ≈1.32427186,
and(1.8)Prob(log10ζmod1∈[a,b])=b−a+2r1πsin(π(b+a)−θ1)⋅sin(π(b−a))−r2πsin(2π(b+a)+θ2)⋅sin(2π(b−a))+ℰ(8.5⋅10−5)with(1.9)r1≈0.0569573,θ1≈0.8055888,r2≈0.0011080,θ2≈0.1384410.The above theorem was proved in [23]; we provide an
alternate proof in Appendix A. As remarked earlier, our technique consists of
applying Poisson summation to the derivative of the cumulative distribution
function of the logarithms modulo 1;
it is then very natural and easy to compare deviations from the resulting
distribution and the uniform distribution (if a dataset satisfies Benford's
law, then the distribution of its logarithms is uniform). Our series expansions
are obtained by applying properties of the Gamma function.Definition 1.2 (Definition exponential behavior, shifted exponential behavior).
Letζ have the standard exponential distribution,
and fix a base B.
If the distribution of the digits of a set is the same as the distribution of
the digits of ζ,
then one says that the set exhibits exponential
behavior (base B). If there is a constant C>0 such that the distribution of digits of all
elements multiplied by C is exponential behavior, then
one says that the system exhibits shifted
exponential behavior (with shift of logBCmod1).We briefly describe the reasons behind this notation.
One important property of Benford's law is that it is invariant under
rescaling; many authors have used this property to characterize Benford
behavior. Thus, if a dataset is Benford baseB,
and we fix a positive number C,
so is the dataset obtained by multiplying each element by C.
This is clear if, instead of looking at the distribution of the digits, we
study the distribution of the base B logarithms modulo 1.
Benford's law is equivalent to the logarithms modulo 1 being uniformly distributed (see, e.g., [6, 25]); the effect of multiplying all entries by a fixed constant simply
translates the uniform distribution modulo 1,
which is again the uniform distribution.The situation is different for exponential behavior.
Multiplying all elements by a fixed constantC (where C≠Bk for some k∈ℤ) does not preserve exponential behavior;
however, the effect is easy-to-describe. Again looking at the logarithms,
exponential behavior is equivalent to the base B logarithms modulo 1 having a specific distribution which is almost
equal to the uniform distribution (at least if the base B is not too large). Multiplying by a fixed
constant C≠Bk shifts the logarithm distribution by logBCmod1.


### 1.2. Results for Differences of Orders Statistics

We consider a simple case first, and show how the more
general case follows. LetX1,…,XN be independent identically distributed from
the uniform distribution on [0,L].
We consider L fixed and study the limit as N→∞.
Let X1:N,…,XN:N be the Xi's in increasing order. The Xi:N are called the order statistics, and satisfy 0≤X1:N≤X2:N≤⋯≤XN:N≤L.
We investigate the distribution of the leading digits of the differences
between adjacent Xi:N's, Xi+1:N−Xi:N.
For convenience, we periodically continue the data and set Xi+N:N=Xi:N+L.
As we have N differences in an interval of size L,
the average value  of  Xi+1:N−Xi:N is of size L/N, and it is sometimes
easier to study the normalized differences(1.10)Zi;N=Xi+1:N−Xi:NL/N.As the Xi's are drawn from a uniform distribution, it
is a standard result that as N→∞,
the Zi;N's are independent random variables, each
having the standard exponential distribution. Thus, as N→∞,
the probability that Zi;N∈[a,b] tends to ∫abe−tdt (see [26, 27] for proofs).For uniformly distributed random variables, if we know
the distribution oflogBZi;Nmod1,
then we can immediately determine the distribution of the digits of the Xi+1:N−Xi:N base B because(1.11)logBZi;N=logB(Xi+1:N−Xi:NL/N)=logB(Xi+1:N−Xi:N)−logB(LN).AsZi;N are independent with the standard exponential
distribution as N→∞;
if Xi are independent uniformly distributed, the
behavior of the digits of the differences Xi+1:N−Xi:N is an immediate consequence of Theorem
1.1.
Theorem 1.3 (Shifted exponential behavior of differences of independent uniformly distributed random variables).
LetX1,…,XN be independently distributed from the uniform
distribution on [0,L],
and let X1:N,…,XN:N be Xi's in an increasing order. As N→∞,
the distribution of the digits (base B) of the differences Xi+1:N−Xi:N converges to shifted exponential behavior,
with a shift of logB(L/N)mod1.A similar result holds for other
distributions.Theorem 1.4 (Shifted exponential behavior of subsets of differences of independent random variables).
LetX1,…,XN be independent, identically distributed random
variables whose density f(x) has a second-order Taylor series at each point
with first and second derivatives uniformly bounded, and let the Xi:N's be the Xi's in increasing order. Fix a δ∈(0,1).
Then, as N→∞ the distribution of the digits (base B) of Nδ consecutive differences Xi+1:N−Xi:N converges to shifted exponential behavior,
provided that Xi:N's are from a region where f(x) is nonzero.The key ingredient in this generalization is that the
techniques, which show that the differences between uniformly distributed
random variables become independent exponentially distributed random variables,
can be modified to handle more general distributions.We restricted ourselves to a subset of all consecutive
spacings because the normalization factor changes throughout the domain. The
shift in the shifted exponential behavior depends on which set ofNδ differences we study, coming from the
variations in the normalizing factors. Within a bin of Nδ differences, the normalization factor is
basically constant, and we may approximate our density with a uniform
distribution. It is possible for these variations to cancel and yield Benford
behavior for the digits of all the unnormalized differences. Such a result is
consistent with the belief that amalgamation of data from many different
distributions becomes Benford; however, this is not always the case (see Remark 1.6). From
Theorems 1.1 and 1.4, we
obtain the following theorem.
Theorem 1.5 (Benford behavior for all the differences of independent random variables).
LetX1,…,XN be independent identically distributed random
variables whose density f(x) is compactly supported and has a second-order
Taylor series at each point with first and second derivatives uniformly bounded.
Let the Xi:N's be the Xi's in an increasing order F(x) be the cumulative distribution function for f(x),
and fix a δ∈(0,1).
Let I(ϵ,δ,N)=[ϵN1−δ,N1−δ−ϵN1−δ].
For each fixed ϵ∈(0,1/2),
assume that
(i)
f(F−1(kNδ−1) is not too small for k∈I(ϵ,δ,N)(1.12)limN→∞maxk∈I(ϵ,δ,N)min(N−(ϵ+δ/2),Nδ−1)f(F−1(kNδ−1))=0,(ii)
logBf(F−1(kNδ−1)mod1 is equidistributed: for all [α,β]⊂[0,1](1.13)limN→∞#{k∈I(ϵ,δ,N):logBf(F−1(kNδ−1))mod1∈[α,β]}Nδ=β−α.
Then, if ϵ>max(0,1/3−δ/2) and ϵ<δ/2,
the distribution of the digits of the N−1 differences Xi+1:N−Xi:N converges to Benford's law (base B) as N→∞.Remark 1.6.
The conditions
of Theorem1.5 are usually not satisfied. We are unaware of any situation where (1.13) holds; we have
included Theorem 1.5 to give a sufficient condition of what is required
to have Benford's law satisfied exactly, and not just approximately. In Lemma 3.3, we show with: Example 3.3 shows that the conditions fail for the Pareto distribution,
and the limiting behavior oscillates between Benford and a sum of shifted
exponential behavior. (If several datasets each
exhibit shifted exponential behavior but with distinct shifts, then the
amalgamated dataset is closer to Benford's law than any of the original
datasets. This is apparent by studying the logarithms modulo 1.
The differences between these densities and Benford's law will look like Figure 1(b) (except, of course, that different shifts will result in shifting the plot
modulo 1). The key observation is that the unequal
shifts mean that we do not have reinforcements from
the peaks of modulo 1 densities being aligned, and thus the
amalgamation will decrease the maximum deviations.) The arguments generalize to
many densities whose cumulative distribution functions have tractable
closed-form expressions (e.g., exponential, Weibull, or f(x)=e−exex).All 499 999 differences of adjacent order statistics
from 500 000 independent random variables from the Pareto distribution with
minimum value and variance1.
(a) Observed digits of scaled differences of adjacent random variables
versus Benford's law; (b) scaled observed minus Benford's law (cumulative
distribution of base 10 logarithms).
(a)(b)The situation is very different if instead we study
normalized differences:(1.14)Z˜i:N=Xi+1:N−Xi:N1/Nf(Xi:N),note if f(x)=1/L is the uniform distribution on [0,L],
(1.14)
reduces to (1.10).
Theorem 1.7 (Shifted exponential behavior for all the normalized differences of independent random variables).
Assume the
probability distributionf satisfies the conditions of Theorem 1.5 and (1.12) and Z˜i;N is as in (1.14). Then, as N→∞,
the distribution of the digits of Z˜i:N converges to shifted exponential behavior.Remark 1.8.
Appropriately
scaled, the distribution of the digits of the differences is universal, and is
the exponential behavior of Theorem1.1. Thus, Theorem 1.7  implies that the
natural quantity to study is the normalized differences of the order
statistics, not the differences (see also Remark 3.5). With additional
work, we could study densities with unbounded support and show that, through
truncation, we can get arbitrarily close to shifted exponential behavior.Remark 1.9.
The main
motivation for this work is the need for improved ways of assessing the
authenticity and integrity of scientific and corporate data. Benford's law has
been successfully applied to detecting income tax, corporate, and voter fraud
(see [18–20]); in [21], we use these results to derive new statistical
tests to examine data authenticity and integrity. Early applications of these
tests to financial data showed that it could detect errors in data downloads,
rounded data, and inaccurate ordering of data. These attributes are not easily
observable from an analysis of descriptive statistics, and detecting these
errors can help managers avoid costly decisions based on erroneous data.The paper is organized as follows. We prove Theorem1.1 in Appendix A by using Poisson summation to analyze FB′(b).
Theorem 1.3 follows from the results of the order statistics of independent uniform
variables. The proof of Theorem 1.4 is similar, and given in Section 2. In Section 3,
we prove Theorems 1.5 and 1.7.


## 1.1. Definitions

A sequence{an}n=1∞⊂[0,1] is equidistributed if(1.2)limN→∞#{n:n≤N,an∈[a,b]}N=b−a∀[a,b]⊂[0,1].Similarly, a continuous random
variable on [0,∞),
whose probability density function is p,
is equidistributed modulo 1 if(1.3)limT→∞∫0Tχa,b(x)p(x)dx∫0Tp(x)dx=b−a,for any [a,b]⊂[0,1],
where χa,b(x)=1 for xmod1∈[a,b] and 0 otherwise.A positive sequence (or values of a function) is
Benford baseB if and only if its base B logarithms are equidistributed modulo 1;
this equivalence is at the heart of many investigations of Benford's law (see
[6, 25] for a proof).We use the following notations for the various error
terms.(1)
Letℰ(x) denote an error of at most x in absolute value; thus f(b)=g(b)+ℰ(x) means |f(b)−g(b)|≤x.(2)
Big-Oh notation: forg(x) a nonnegative function, we say f(x)=O(g(x)) if there exist an x0 and a C>0 such that, for all x≥x0, |f(x)|≤Cg(x).The following theorem is the starting point for
investigating the distribution of digits of order statistics.Theorem 1.1.
Letζ have the standard (unit) exponential
distribution(1.4)Prob(ζ∈[α,β])=∫αβe−tdt,[α,β]∈[0,∞).For b∈[0,1],
let FB(b) be the cumulative distribution function of logBζmod1;
thus FB(b):=Prob(logBζmod1∈[0,b]).
Then, for all M≥2,(1.5)FB′(b)=1+2∑m=1∞Re(e−2πimbΓ(1+2πimlogB))=1+2∑m=1M−1Re(e−2πimbΓ(1+2πimlogB))+ℰ(42πc1(B)e−(π2−c2(B))M/logB),where c1(B),c2(B) are  constants such that for  all m≥M≥2,
one has (1.6)e2π2m/logB−e−2π2m/logB≥e2π2m/logBc12(B),mlogB≤e2c2(B)m/logB,1−e(π2−c2(B))M/logB≥12.For B∈[e,10], take c1(B)=2 and c2(B)=1/5,
which give(1.7)Prob(logζmod1∈[a,b])=b−a+2rπ⋅sin(π(b+a)+θ)⋅sin(π(b−a))+ℰ(6.32⋅10−7),with r≈0.000324986, θ≈1.32427186,
and(1.8)Prob(log10ζmod1∈[a,b])=b−a+2r1πsin(π(b+a)−θ1)⋅sin(π(b−a))−r2πsin(2π(b+a)+θ2)⋅sin(2π(b−a))+ℰ(8.5⋅10−5)with(1.9)r1≈0.0569573,θ1≈0.8055888,r2≈0.0011080,θ2≈0.1384410.The above theorem was proved in [23]; we provide an
alternate proof in Appendix A. As remarked earlier, our technique consists of
applying Poisson summation to the derivative of the cumulative distribution
function of the logarithms modulo 1;
it is then very natural and easy to compare deviations from the resulting
distribution and the uniform distribution (if a dataset satisfies Benford's
law, then the distribution of its logarithms is uniform). Our series expansions
are obtained by applying properties of the Gamma function.Definition 1.2 (Definition exponential behavior, shifted exponential behavior).
Letζ have the standard exponential distribution,
and fix a base B.
If the distribution of the digits of a set is the same as the distribution of
the digits of ζ,
then one says that the set exhibits exponential
behavior (base B). If there is a constant C>0 such that the distribution of digits of all
elements multiplied by C is exponential behavior, then
one says that the system exhibits shifted
exponential behavior (with shift of logBCmod1).We briefly describe the reasons behind this notation.
One important property of Benford's law is that it is invariant under
rescaling; many authors have used this property to characterize Benford
behavior. Thus, if a dataset is Benford baseB,
and we fix a positive number C,
so is the dataset obtained by multiplying each element by C.
This is clear if, instead of looking at the distribution of the digits, we
study the distribution of the base B logarithms modulo 1.
Benford's law is equivalent to the logarithms modulo 1 being uniformly distributed (see, e.g., [6, 25]); the effect of multiplying all entries by a fixed constant simply
translates the uniform distribution modulo 1,
which is again the uniform distribution.The situation is different for exponential behavior.
Multiplying all elements by a fixed constantC (where C≠Bk for some k∈ℤ) does not preserve exponential behavior;
however, the effect is easy-to-describe. Again looking at the logarithms,
exponential behavior is equivalent to the base B logarithms modulo 1 having a specific distribution which is almost
equal to the uniform distribution (at least if the base B is not too large). Multiplying by a fixed
constant C≠Bk shifts the logarithm distribution by logBCmod1.


## 1.2. Results for Differences of Orders Statistics

We consider a simple case first, and show how the more
general case follows. LetX1,…,XN be independent identically distributed from
the uniform distribution on [0,L].
We consider L fixed and study the limit as N→∞.
Let X1:N,…,XN:N be the Xi's in increasing order. The Xi:N are called the order statistics, and satisfy 0≤X1:N≤X2:N≤⋯≤XN:N≤L.
We investigate the distribution of the leading digits of the differences
between adjacent Xi:N's, Xi+1:N−Xi:N.
For convenience, we periodically continue the data and set Xi+N:N=Xi:N+L.
As we have N differences in an interval of size L,
the average value  of  Xi+1:N−Xi:N is of size L/N, and it is sometimes
easier to study the normalized differences(1.10)Zi;N=Xi+1:N−Xi:NL/N.As the Xi's are drawn from a uniform distribution, it
is a standard result that as N→∞,
the Zi;N's are independent random variables, each
having the standard exponential distribution. Thus, as N→∞,
the probability that Zi;N∈[a,b] tends to ∫abe−tdt (see [26, 27] for proofs).For uniformly distributed random variables, if we know
the distribution oflogBZi;Nmod1,
then we can immediately determine the distribution of the digits of the Xi+1:N−Xi:N base B because(1.11)logBZi;N=logB(Xi+1:N−Xi:NL/N)=logB(Xi+1:N−Xi:N)−logB(LN).AsZi;N are independent with the standard exponential
distribution as N→∞;
if Xi are independent uniformly distributed, the
behavior of the digits of the differences Xi+1:N−Xi:N is an immediate consequence of Theorem
1.1.
Theorem 1.3 (Shifted exponential behavior of differences of independent uniformly distributed random variables).
LetX1,…,XN be independently distributed from the uniform
distribution on [0,L],
and let X1:N,…,XN:N be Xi's in an increasing order. As N→∞,
the distribution of the digits (base B) of the differences Xi+1:N−Xi:N converges to shifted exponential behavior,
with a shift of logB(L/N)mod1.A similar result holds for other
distributions.Theorem 1.4 (Shifted exponential behavior of subsets of differences of independent random variables).
LetX1,…,XN be independent, identically distributed random
variables whose density f(x) has a second-order Taylor series at each point
with first and second derivatives uniformly bounded, and let the Xi:N's be the Xi's in increasing order. Fix a δ∈(0,1).
Then, as N→∞ the distribution of the digits (base B) of Nδ consecutive differences Xi+1:N−Xi:N converges to shifted exponential behavior,
provided that Xi:N's are from a region where f(x) is nonzero.The key ingredient in this generalization is that the
techniques, which show that the differences between uniformly distributed
random variables become independent exponentially distributed random variables,
can be modified to handle more general distributions.We restricted ourselves to a subset of all consecutive
spacings because the normalization factor changes throughout the domain. The
shift in the shifted exponential behavior depends on which set ofNδ differences we study, coming from the
variations in the normalizing factors. Within a bin of Nδ differences, the normalization factor is
basically constant, and we may approximate our density with a uniform
distribution. It is possible for these variations to cancel and yield Benford
behavior for the digits of all the unnormalized differences. Such a result is
consistent with the belief that amalgamation of data from many different
distributions becomes Benford; however, this is not always the case (see Remark 1.6). From
Theorems 1.1 and 1.4, we
obtain the following theorem.
Theorem 1.5 (Benford behavior for all the differences of independent random variables).
LetX1,…,XN be independent identically distributed random
variables whose density f(x) is compactly supported and has a second-order
Taylor series at each point with first and second derivatives uniformly bounded.
Let the Xi:N's be the Xi's in an increasing order F(x) be the cumulative distribution function for f(x),
and fix a δ∈(0,1).
Let I(ϵ,δ,N)=[ϵN1−δ,N1−δ−ϵN1−δ].
For each fixed ϵ∈(0,1/2),
assume that
(i)
f(F−1(kNδ−1) is not too small for k∈I(ϵ,δ,N)(1.12)limN→∞maxk∈I(ϵ,δ,N)min(N−(ϵ+δ/2),Nδ−1)f(F−1(kNδ−1))=0,(ii)
logBf(F−1(kNδ−1)mod1 is equidistributed: for all [α,β]⊂[0,1](1.13)limN→∞#{k∈I(ϵ,δ,N):logBf(F−1(kNδ−1))mod1∈[α,β]}Nδ=β−α.
Then, if ϵ>max(0,1/3−δ/2) and ϵ<δ/2,
the distribution of the digits of the N−1 differences Xi+1:N−Xi:N converges to Benford's law (base B) as N→∞.Remark 1.6.
The conditions
of Theorem1.5 are usually not satisfied. We are unaware of any situation where (1.13) holds; we have
included Theorem 1.5 to give a sufficient condition of what is required
to have Benford's law satisfied exactly, and not just approximately. In Lemma 3.3, we show with: Example 3.3 shows that the conditions fail for the Pareto distribution,
and the limiting behavior oscillates between Benford and a sum of shifted
exponential behavior. (If several datasets each
exhibit shifted exponential behavior but with distinct shifts, then the
amalgamated dataset is closer to Benford's law than any of the original
datasets. This is apparent by studying the logarithms modulo 1.
The differences between these densities and Benford's law will look like Figure 1(b) (except, of course, that different shifts will result in shifting the plot
modulo 1). The key observation is that the unequal
shifts mean that we do not have reinforcements from
the peaks of modulo 1 densities being aligned, and thus the
amalgamation will decrease the maximum deviations.) The arguments generalize to
many densities whose cumulative distribution functions have tractable
closed-form expressions (e.g., exponential, Weibull, or f(x)=e−exex).All 499 999 differences of adjacent order statistics
from 500 000 independent random variables from the Pareto distribution with
minimum value and variance1.
(a) Observed digits of scaled differences of adjacent random variables
versus Benford's law; (b) scaled observed minus Benford's law (cumulative
distribution of base 10 logarithms).
(a)(b)The situation is very different if instead we study
normalized differences:(1.14)Z˜i:N=Xi+1:N−Xi:N1/Nf(Xi:N),note if f(x)=1/L is the uniform distribution on [0,L],
(1.14)
reduces to (1.10).
Theorem 1.7 (Shifted exponential behavior for all the normalized differences of independent random variables).
Assume the
probability distributionf satisfies the conditions of Theorem 1.5 and (1.12) and Z˜i;N is as in (1.14). Then, as N→∞,
the distribution of the digits of Z˜i:N converges to shifted exponential behavior.Remark 1.8.
Appropriately
scaled, the distribution of the digits of the differences is universal, and is
the exponential behavior of Theorem1.1. Thus, Theorem 1.7  implies that the
natural quantity to study is the normalized differences of the order
statistics, not the differences (see also Remark 3.5). With additional
work, we could study densities with unbounded support and show that, through
truncation, we can get arbitrarily close to shifted exponential behavior.Remark 1.9.
The main
motivation for this work is the need for improved ways of assessing the
authenticity and integrity of scientific and corporate data. Benford's law has
been successfully applied to detecting income tax, corporate, and voter fraud
(see [18–20]); in [21], we use these results to derive new statistical
tests to examine data authenticity and integrity. Early applications of these
tests to financial data showed that it could detect errors in data downloads,
rounded data, and inaccurate ordering of data. These attributes are not easily
observable from an analysis of descriptive statistics, and detecting these
errors can help managers avoid costly decisions based on erroneous data.The paper is organized as follows. We prove Theorem1.1 in Appendix A by using Poisson summation to analyze FB′(b).
Theorem 1.3 follows from the results of the order statistics of independent uniform
variables. The proof of Theorem 1.4 is similar, and given in Section 2. In Section 3,
we prove Theorems 1.5 and 1.7.


## 2. Proofs of Theorems1.3 and 1.4

Theorem1.3 is a consequence of the fact that the normalized
differences between the order statistics drawn from the uniform distribution
converge to being independent standard exponentials. The proof of Theorem 1.4 proceeds
similarly. Specifically, over a short enough region, any distribution with a
second-order Taylor series at each point with first and second derivatives
uniformly bounded is well approximated by a uniform distribution.To prove Theorem1.4, it suffices to show
that if X1,…,XN are drawn from a sufficiently nice
distribution, then for any fixed δ∈(0,1) the limiting behavior of the order statistics
of Nδ adjacent Xi's becomes Poissonian (i.e., the Nδ−1 normalized differences converge to being
independently distributed from the standard exponential). We prove this below
for compactly supported distributions f(x) that have a second-order Taylor series at each
point with the first and second derivatives uniformly bounded, and when the Nδ adjacent Xi's are from a region where f(x) is bounded away from zero.For eachN,
consider intervals [aN,bN] such that ∫aNbNf(x)dx=Nδ/N;
thus, the proportion of the total mass in such intervals is Nδ−1.
We fix such an interval for our arguments. For each i∈{1,…,N},
let(2.1)wi={1,ifXi∈[aN,bN]0,otherwise. Note wi is 1 with probability Nδ−1 and 0 with probability 1−Nδ−1; wi is a binary indicator random variable, telling
us whether or not Xi∈[aN,bN].
Thus,(2.2)𝔼[∑i=1Nwi]=Nδ,Var(∑i=1Nwi)=Nδ⋅(1−Nδ−1).Let MN be the number of Xi in [aN,bN],
and let βN be any nondecreasing sequence tending
to infinity (in the course of the proof, we will find
that we may take any sequence with βN=O(Nδ/2)). By (2.2) and the central
limit theorem (which we may use as wi's satisfy the Lyapunov condition), with
probability tending to 1,
we have(2.3)MN=Nδ+O(βNNδ/2).We assume that in the interval[aN,bN] there exist constants c and C such that whenever x∈[aN,bN], 0<c<f(x)<C<∞;
we assume that these constants hold for all regions investigated and for all N.
(If our distribution has unbounded support, for any ϵ>0,
we can truncate it on both sides so that the omitted probability is at most ϵ.
Our result is then trivially modified to be within ϵ of shifted exponential behavior.) Thus,(2.4)c⋅(bN−aN)≤∫aNbNf(x)dx=Nδ−1≤C(bN−aN),implying that bN−aN is of size Nδ−1.
If we assume that f(x) has at least a second-order Taylor expansion,
then(2.5)f(x)=f(aN)+f′(aN)(x−aN)+O((x−aN)2)=f(aN)+f′(aN)(x−aN)+O(N2δ−2).
As we assume
that the first and second derivatives are uniformly bounded, as
well as f being bounded away from zero in the intervals
under consideration, all Big-Oh constants below are independent of N. Thus,(2.6)bN−aN=Nδ−1f(aN)+O(N2δ−2).We now investigate the order statistics of theMN of the Xi's that lie in [aN,bN].
We know ∫aNbNf(x)dx=Nδ−1;
by setting gN(x)=f(x)N1−δ,
then gN(x) is the conditional density function for Xi,
given that Xi∈[aN,bN].
Thus, gN(x) integrates to 1, and for x∈[aN,bN],
we have(2.7)gN(x)=f(aN)⋅N1−δ+f′(aN)(x−aN)⋅N1−δ+O(Nδ−1).We have an interval of sizeNδ−1/f(aN)+O(N2δ−2),
and MN=Nδ+O(βNNδ/2) of the Xi lying in the interval (remember
that βN are any nondecreasing sequence tending to
infinity). Thus, with probability tending to 1, the average spacing between
adjacent ordered Xi is(2.8)Nδ−1/f(aN)+O(N2δ−2)MN=(f(aN)N)−1+N−1⋅O(βNN−δ/2+Nδ−1),in particular, we see that we
must choose βN=O(Nδ/2).
As δ∈(0,1),
if we fix a k such that Xk∈[aN,bN],
then we expect the next Xi to the right of Xk to be about t/Nf(aN) units away, where t is of size 1.
For a given Xk,
we can compute the conditional probability that the next Xi is between t/Nf(aN) and (t+Δt)/Nf(aN) units to the right. It is simply the
difference of the probability that all the other MN−1 of the Xi's in [aN,bN] are not in the interval [Xk,Xk+t/Nf(aN)] and the probability that all other Xi in [aN,bN] are not in the interval [Xk,Xk+(t+Δt)/Nf(aN)];
note that we are using the wrapped interval [aN,bN].Some care is required in these calculations. We have a
conditional probability as we assume thatXk∈[aN,bN] and that exactly MN of the Xi are in [aN,bN].
Thus, these probabilities depend on two random variables, namely, Xk and MN.
This is not a problem in practice, however (e.g., MN is tightly concentrated about its mean value).Recalling our expansion forgN(x) (and that bN−aN=Nδ−1/f(aN)+O(N2δ−2) and t is of size 1), after simple algebra, we find that with
probability tending to 1, for a given Xk and MN,
the first probability is(2.9)(1−∫XkXk+t/Nf(aN)gN(x)dx)MN−1.The above integral equals tNδ+O(N−1) (use the Taylor series expansion in (2.7) and note that the
interval [aN,bN] is of size O(Nδ−1)). Using (2.3),
it is easy to see that this is a.s. equal to(2.10)(1−t+O(Nδ−1+βNN−δ/2)MN)MN−1.We, therefore, find that as N→∞,
the probability that MN−1 of the Xi's (i≠k) are in [aN,bN]∖[Xk,Xk+t/Nf(aN)],
conditioned on Xk and MN,
converges to e−t.
(Some care is required, as the exceptional set in our a.s. statement can depend
on t.
This can be surmounted by taking expectations with respect to our conditional
probabilities and applying the dominated convergence theorem.)The calculation of the second probability, the
conditional probability that theMN−1 other Xi' that  are  [aN,bN]  not in the
interval [Xk,Xk+(t+Δt)/Nf(aN)],
given Xk and MN,
follows analogously by  replacing t with t+Δt in the previous argument. We thus find that
this probability is e−(t+Δt).
As(2.11)∫tt+Δte−udu=e−t−e−(t+Δt),we find that the density of the
difference between adjacent order statistics tends to the standard (unit)
exponential density; thus, the proof of Theorem 1.4 now follows from
Theorem 1.3.


## 3. Proofs of Theorems1.5 and 1.7

We generalize the notation from Section2. Let f(x) be any distribution with a second-order Taylor
series at each point with first and second derivatives uniformly bounded, and
let X1:N,…,XN:N be the order statistics. We fix a δ∈(0,1),
and for k∈{1,…,N1−δ},
we consider bins [ak;N,bk;N] such that(3.1)∫ak;Nbk;Nf(x)dx=NδN=Nδ−1,there are N1−δ such bins. By the central limit theorem (see
(2.3)), if Mk;N is the number of order statistics in [ak;N,bk;N],
then, provided that ϵ>max(0,1/3−δ/2) with probability tending to 1,
we have(3.2)Mk;N=Nδ+O(Nϵ+δ/2),of course we also require ϵ<δ/2,
as, otherwise, the error term is larger than the main term.Remark 3.1.
Before we
considered just one fixed interval; as we are studyingN1−δ intervals simultaneously, we need ϵ in the exponent so that with high probability,
all intervals have to first order Nδ order statistics. For the arguments below, it
would have sufficed to have an error of size O(Nδ−ϵ).
We thank the referee for pointing out that ϵ>1/3−δ/2,
and provide his argument in Appendix B.Similar to (2.8), the average spacing between adjacent order
statistics in [ak;N,bk;N] is(3.3)(f(ak;N)N)−1+N−1⋅O(N−(ϵ+δ/2)+Nδ−1).Note that (3.3) is the
generalization of (1.11); if f is the uniform distribution on [0,L],
then f(ak;N)=1/L.
By Theorem 1.4,
as N→∞,
the distribution of digits of the differences in each bin converges to shifted
exponential behavior; however, the variation in the average spacing between
bins leads to bin-dependent shifts in the shifted exponential behavior.Similar to (1.11), we can study the distribution of digits of the
differences of the normalized order statistics. If Xi:N and Xi+1:N are in [ak;N,bk;N],
then(3.4)Zi;N=Xi+1:N−Xi:N(f(ak;N)N)−1+N−1⋅O(N−(ϵ+δ/2)+Nδ−1),logBZi;N=logB(Xi+1:N−Xi:N)+logBN−logB(f(ak;N)−1+O(N−(ϵ+δ/2)+Nδ−1)).Note we are using the same normalization factor for all differences between adjacent order statistics in a
bin. Later, we show that we may replace f(ak;N) with f(Xi:N).
As we study all Xi+1:N−Xi:N in the bin [ak;N,bk;N],
it is useful to rewrite the above as(3.5)logB(Xi+1:N−Xi:N)=logBZi;N−logBN+logB(f(ak;N)−1+O(N−(ϵ+δ/2)+Nδ−1)).We have N1−δ bins, so k∈{1,…,N1−δ}.
As we only care about the limiting behavior, we may safely ignore the first and
last bins. We may, therefore, assume that each ak;N is finite, and ak+1;N=bk;N.
(Of course, we know that both quantities are finite as we assumed that our
distribution has compact support. We remove the last bins to simplify
generalizations to noncompactly supported distributions.)LetF(x) be the cumulative distribution function for f(x).
Then,(3.6)F(ak;N)=(k−1)NδN=(k−1)Nδ−1.For notational convenience, we
relabel the bins so that k∈{0,…,N1−δ−1};
thus F(ak;N)=kNδ−1.We now prove our theorems which determine when these
bin-dependent shifts cancel (yielding Benford behavior), or reinforce (yielding
sums of shifted exponential behavior).Proof of Theorem1.5.
There are
approximatelyNδ differences in each bin [ak;N,bk;N].
By Theorem 1.4,
the distribution of the digits of the differences in each bin converges to
shifted exponential behavior. As we assume that the first and second
derivatives of f are uniformly bounded, the Big-Oh constants in
Section 2 are independent of the bins. The shift in the shifted exponential
behavior in each bin is controlled by the last two terms on the right-hand side
of (3.5). The logBN shifts the shifted exponential behavior in
each bin equally. The bin-dependent shift is controlled by the final term(3.7)logB(f(ak;N)−1+O(N−(ϵ+δ/2)+Nδ−1))=−logBf(ak;N)+logB(1+min(N−(ϵ+δ/2),Nδ−1)f(ak;N)).
Thus, each of theN1−δ bins exhibits shifted exponential behavior,
with a bin-dependent shift composed of the two terms in (3.7). By (1.12), f(ak;N) are not small compared to min(N−(ϵ+δ/2),Nδ−1),
and hence the second term logB(1+(min(N−(ϵ+δ/2),Nδ−1)/f(ak;N))) is negligible. In particular, this factor
depends only very weakly on the bin, and tends to zero as N→∞.
Thus, the bin-dependent shift in the shifted
exponential behavior is approximately−logBf(ak;N)=−logBf(F−1(kNδ−1)).
If these shifts are equidistributed modulo 1,
then the deviations from Benford behavior cancel, and the shifted exponential
behavior of each bin becomes Benford behavior for all the differences.Remark 3.2.
Consider the
case when the density is a uniform distribution on some interval. Then, allf(F−1(kNδ−1)) are equal, and each bin has the same shift in
its shifted exponential behavior. These shifts, therefore, reinforce each
other, and the distribution of all the differences is also shifted exponential
behavior, with the same shift. This is observed in numerical experiments (see
Theorem 1.3 for
an alternate proof).We analyze the assumptions of Theorem1.5. The condition from
(1.12) is
easy-to-check, and is often satisfied. For example, if the probability density
is a finite union of monotonic pieces and is zero only finitely
often, then (1.12) holds. This is because for k∈I(ϵ,δ,N), F−1(kNδ−1)∈[F−1(ϵ),F−1(1−ϵ)],
and this is, therefore, independent of N (if f vanishes finitely often, we need to remove
small subintervals from I(ϵ,δ,N),
but the analysis proceeds similarly). The only difficulty is basically a
probability distribution with intervals of zero probability. Thus, (1.12) is a mild
assumption.If we choose any distributionother than a
uniform distribution, then f(x) is not constant; however, (1.13)
does not need to hold (i.e., logBf(ak;N)mod1 does not need to
be equidistributed as N→∞). For example, consider a Pareto distribution
with minimum value 1 and exponent a>0.
The density is(3.8)f(x)={ax−a−1ifx≥1,0otherwise. The Pareto distribution
is known to be useful in modelling natural phenomena, and for appropriate
choices of exponents, it yields approximately
Benford behavior (see [16]).Example 3.3.
Iff is a Pareto distribution with minimum value 1 and exponent a>0,
then f does not satisfy the second condition of
Theorem 1.5,
(1.13).
To see this, note that the cumulative distribution
function off is F(x)=1−x−a.
As we only care about the limiting behavior, we need only
to study k∈I(ϵ,δ,N)=[ϵN1−δ,N1−δ−ϵN1−δ].
Therefore, F(ak;N)=kNδ−1 implies that(3.9)ak;N=(1−kNδ−1)−1/a,f(ak;N)=a(1−kNδ−1)(a+1)/a.
The condition from (1.12) is satisfied,
namely,(3.10)limN→∞maxk∈I(ϵ,δ,N)min(N−(ϵ+δ/2),Nδ−1)f(ak;N)=limN→∞maxk∈I(ϵ,δ,N)min(N−(ϵ+δ/2),Nδ−1)a(kNδ−1)(a+1)/a=0,as k is of size N1−δ.
Letj=N1−δ−k∈I(ϵ,δ,N).
Then, the bin-dependent shifts are(3.11)logBf(ak;N)=a+1alogB(1−kNδ−1)+logBa=a+1alogB(jN1−δ)+logBa=logB(j(a+1)/a)+logB(aN(1−δ)(a+1)/a).Thus, for a Pareto distribution
with exponent a,
the distribution of all the differences becomes Benford if and only if j(a+1)/a is Benford. This follows from the fact that a
sequence is Benford if and only if its logarithms are equidistributed. For
fixed m, jm is not Benford (e.g., [6]), and thus
the condition from (1.13) fails.Remark 3.4.
We chose to
study a Pareto distribution because the distribution of digits of a random
variable drawn from a Pareto distribution converges to Benford behavior (base
10) asa→1;
however, the digits of the differences do not tend to Benford (or shifted
exponential) behavior. A similar analysis holds for many distributions with
good closed-form expressions for the cumulative distribution function. In
particular, if f is the density of an exponential or Weibull
distribution (or f(x)=e−exex), then f does not satisfy the second condition of
Theorem 1.5,
(1.13).Modifying the proof of Theorem1.5 yields our result on
the distribution of digits of the normalized differences.Proof of Theorem1.7.
Iff is the uniform distribution, there is nothing
to prove. For general f,
rescaling the differences eliminates the bin-dependent shifts. Let(3.12)Z˜i:N=Xi+1:N−Xi:N1/Nf(Xi:N).In Theorem 1.5, we use the same
scale factor for all differences in a bin (see (3.4)). As we assume
the first and second derivatives of f are uniformly bounded, (2.5) and (2.6) imply that for Xi:N∈[ak;N,bk;N],(3.13)f(Xi:N)=f(ak;N)+O(bk;N−ak;N)=f(ak;N)+O(Nδ−1f(ak;N)+N2δ−2),and the Big-Oh constants are
independent of k.
As we assume that f satisfies (1.12), the error term
is negligible.
Thus, our assumptions onf imply that f is basically constant on each bin, and we may
replace the local rescaling factor f(Xi:N) with the bin rescaling factor f(ak;N).
Thus, each bin of normalized differences has the same shift in its
shifted exponential behavior. Therefore all the shifts reinforce, and the
digits of all the normalized differences exhibit shifted exponential behavior
as N→∞.As an example of Theorem1.7, in Figure 1 we
consider 500,000 independent random variables drawn from the Pareto distribution
with exponent(3.14)a=4+19−3333+19+33333(we chose a to make the variance equal 1). We study the distribution of the digits of
the differences in base 10. The amplitude is about .018,
which is the amplitude of the shifted exponential behavior of Theorem  1.1 (see the equation in
[23, Theorem 2] or (1.5) of Theorem 1.1).Remark 3.5.
The universal
behavior of Theorem1.7 suggests that if we are interested in the behavior
of the digits of all the differences, the natural quantity to study is the normalized differences. For any distribution with uniformly bounded first and second
derivatives and a second-order Taylor series expansion at each point, we obtain
shifted exponential behavior.



---

*Source: 382948-2008-12-01.xml*