Interactive demo · Probability and Statistical Inference · Chapter 7

Glivenko–Cantelli: the largest gap goes to zero

The law of large numbers says that F̂n(x) → F(x) at each fixed x. The Glivenko–Cantelli theorem says more: the largest gap Dn = supx|F̂n(x) − F(x)| goes to 0 almost surely, for every F. Follow Dn along one or many sample paths up to n = 10,000. On the log–log scale the paths fall with slope −1/2: Dn is of order 1/√n, the DKW inequality bounds how often a path can sit above εn at a given n, and √n Dn settles to Kolmogorov's distribution, the same for every continuous F.

Distribution F

Number of paths

Sample size n (shown)

DKW envelope α

Try these

Path k is X1, X2, ..., X10000 = F−1(U1), F−1(U2), ... from its own seeded generator, and Dn is computed from the first n values at 54 sample sizes between 1 and 10,000. Every distribution sees the same uniforms. The typical size is the median of Kolmogorov's law over √n, 0.828/√n; the dotted curve is √(log log n / (2n)), the size of the largest gaps over the whole path (Chung's law of the iterated logarithm).

In the lecture notes