Empirical Discrepancies and Subadditive Processes

If Xi,i=1,2,⋯Xi,i=1,2,⋯ are independent and identically distributed vector valued random variables with distribution F, and S is a class of subsets of Rd, then necessary and sufficient conditions are given for the almost sure convergence of (1/n)Dsn = supA∈S |(1/n) ∑ 1A(Xi)−F(A)| to zero. The criteria are defined by combinatorial entropies which are given as the time constants of certain subadditive processes. These time constants are estimated, and convergence results for (1/n)DnS obtained, for the classes of algebraic regions, convex sets, and lower layers. These results include the solution to a problem posed by W. Stute.