Sharp estimate on the supremum of a class of sums of small i.i.d. random variables.

Péter Major Alféd Rényi Mathematical Institute of the Hungarian Academy of Science e-mail address: major.peter@renyi.mta.hu

Summary. We take a class of functions F with polynomial covering numbers on a measurable space (X, X) together with a sequence of independent, identically distributed X-space valued random variables ξ_{1}, …, ξ_{n}, and give a good estimate on the tail distri-

bution of sup_{f∈F} ∑_{j=1}^{n} f(ξ_{j}) if the expected values E|f(ξ_{1})| are very small for all f ∈ F. In

a subsequent paper [5] we give a sharp bound for the supremum of normalized sums of i.i.d. random variables in a more general case. But the proof of that estimate is based on the results in this work.

1. Introduction.

This work is part of a more general investigation about the supremum of (normalized) sums of bounded, independent and identically distributed random variables if the class of random variables whose sums we investigate have some nice properties. It turned out that it is useful to investigate first the case when the expectations of the absolute values of these random variables are very small, and this is the subject of the present paper. In paper [5] we shall get good estimates in the general case when the expectations of these absolute values may be relatively large with the help of the main result in this paper.

First I recall the notion of uniform covering numbers and classes of functions with polynomial covering numbers, since they play an important role in our investigation. Then I formulate the main result of this paper, and make some comments that may help in understanding its content.

Definition of uniform covering numbers with respect to L_{1}-norm. Let a measurable space (X, X) be given together with a class of measurable, real valued functions F on this space. The uniform covering number of this class of functions at level ε, ε > 0, with respect to the L_{1}-norm is sup_{ν} N (ε, F, L_{1}(ν)), where the supremum is taken

for all probability measures ν on the space (X, X), and N (ε, F, L_{1}(ν)) is the smallest integer m for which there exist some functions f_{j} ∈ F, 1 ≤ j ≤ m, such that

min_{1≤j≤m} ∫ |f − f_{j}| dν ≤ ε for all f ∈ F.

Definition of a class of functions with polynomially increasing covering numbers. We say that a class of functions F has polynomially increasing covering numbers with parameter D and exponent L if the inequality

sup_{ν} N (ε, F, L_{1}(ν)) ≤ Dε^{−L}  (1.1)

holds for all 0 < ε ≤ 1 with the number sup_{ν} N (ε, F, L_{1}(ν)) introduced in the previous

definition.

The main result of this work is the following Theorem 1.

Theorem 1. Let F be a finite or countable class of functions on a measurable space (X, X) which has polynomially increasing covering numbers with some parameter D ≥ 1 and exponent L ≥ 1, and sup_{x∈X} |f(x)| ≤ 1 for all f ∈ F. Let ξ_{1}, …, ξ_{n}, n ≥ 2, be a

sequence of independent and identically distributed random variables with values in the space (X, X) with a distribution μ, and assume that the inequality ∫ |f(x)|μ( dx) ≤ ρ holds for all f ∈ F with a number 0 < ρ ≤ n^{−200}. Put S_{n}(f) = S_{n}(f)(ξ_{1}, …, ξ_{n}) =

∑_{j=1}^{n} f(ξ_{j}) for all f ∈ F. The inequality

P (sup_{f∈F} |S_{n}(f)| ≥ u) ≤ Dρ^{Cu} for all u > 41L  (1.2)

holds with some universal constant 1 > C > 0. We can choose e.g. C = \frac{1}{50}.

I introduce an example that may help in understanding better the content of Theorem 1. In particular, it gives some hints why a condition of the type u > C̄L had to be imposed in formula (1.2). (We imposed this condition with C̄ = 41.)

Let us take a set X = {x_{1}, …, x_{N}} with a large number N together with the uniform distribution μ on it, i.e. let μ(x_{j}) = \frac{1}{N} for all 1 ≤ j ≤ N, and define the following class of function F on X. Fix a positive integer L, and let the class of functions F consist of the indicator functions of all subsets of X containing no more than L points. Let us fix a number n, and choose for all numbers j = 1, …, n a point of the set X choosing each point with the same probability \frac{1}{N} independently of each other. Let ξ_{j} denote the element of X we chose at the j-th time. In such a way we defined a sequence of independent random variables ξ_{1}, …, ξ_{n} on X with distribution μ, and a class of functions F consisting of non-negative functions bounded by 1 such that

∫ f(x)μ( dx) ≤ \frac{L}{N} for all f ∈ F. Let us introduce the random sums S_{n}(f) = ∑_{j=1}^{n} f(ξ_{j})

for all f ∈ F. We shall estimate first the probability P_{n} = P (sup_{f∈F} S_{n}(f) ≥ n) and

then the probability P_{u,n} = P (sup_{f∈F} S_{n}(f) ≥ u) for u ≤ n.

It is not difficult to see that P_{n} = 1 if n ≤ L, and P_{n} ≤ \binom{N}{L}(\frac{L}{N})^{n} ≤ C^{L}ρ^{n−L} with ρ = \frac{L}{N} if n > L, where C is a universal constant. The number C can be chosen as a constant for which the inequality p^{p} ≤ C^{p}p! holds for all positive integers p. We can choose for instance C = 4. In the proof of the above estimate we may exploit that X has \binom{N}{L} subsets containing exactly L points, and the event sup_{f∈F} S_{n}(f) ≥ n may occur only if there is a subset of X of cardinality L which contains all points ξ_{j}, 1 ≤ j ≤ n. Also the estimate P_{u,n} ≤ \binom{n}{u}P_{u} ≤ C^{L}n^{u}ρ^{u−L} holds, because the event sup_{f∈F} S_{n}(f) ≥ u

can only occur if there are some indices 1 ≤ j_{1} < j_{2} < ⋯ < j_{u} ≤ n such that all points ξ_{j_{s}}, 1 ≤ s ≤ u, are contained in a subset of X of cardinality L. The probability of such an event is P_{u} for all sequences 1 ≤ j_{1} < j_{2} < ⋯ < j_{u} ≤ n, and there are \binom{n}{u} such sequences.

We show that if N ≥ n^{201} and n ≥ 41L, then the above model satisfies the conditions of Theorem 1, and compare the bound we got for P_{u,n} in our previous calculation with the estimate of Theorem 1 in this example. We shall apply Theorem 1 for the class of functions F consisting of the indicator functions of all subsets containing at most L points of a set X. To apply Theorem 1 I show that the above defined F is a class of functions with polynomially increasing covering numbers with exponent L and an appropriate parameter D. Then we can apply the estimate of Theorem 1 for the probability P_{u,n}. To check the above stated property of F I recall the definition of Vapnik–Červonenkis classes together with a classical result about their properties.

Definition of Vapnik–Červonenkis classes. Let a set X be given, and let us select a class D of subsets of this set X. We call D a Vapnik–Červonenkis class if there exist two real numbers B and K such that for all positive integers n and subsets S(n) = {x_{1}, …, x_{n}} ⊂ X of cardinality n of the set X the collection of sets of the form S(n)∩D, D ∈ D, contains no more than Bn^{K} subsets of S(n). We call B the parameter and K the exponent of this Vapnik–Červonenkis class.

It is not difficult to see that the subsets of a set X containing at most L points constitute a Vapnik–Červonenkis class with exponent K = L and an appropriate parameter B. (Some calculation shows that we can choose B = \frac{1.5}{L!}.) I recall a classical result (see e.g. [7] Chapter 2, 25 Approximation Lemma) by which the indicator functions of the sets in a Vapnik–Červonenkis class constitute a class of functions with polynomially increasing covering numbers. (Actually the work [7] uses a slightly different terminology, and it presents a more general result.) In the book [7] it is proved that if the parameter and exponent of a Vapnik–Červonenkis class are B and K, then the class of functions consisting of its indicator functions has polynomially increasing covering numbers with parameter D = max(B^{2}, n_{0}) and exponent L = 2K with an appropriate constant n_{0} = n_{0}(K). Moreover, it is not difficult to see by slightly modifying the proof that this exponent can be chosen as L = (1 + ε)K and an appropriate parameter D = D(K, L, ε) for arbitrary ε > 0. Actually there are some improved versions of this result that supply slightly better estimates for this parameter and exponent (see [2] or [8] Theorem 2.6.4), but this improvement does not play an important role in our considerations.

The above argument shows that the class of functions F considered in the above example has polynomially increasing covering numbers with exponent 2L and an appropriate parameter D. Its exponent can be chosen even as (1 + ε)L with an appropriate parameter D(ε) for all ε > 0. This means in particular that Theorem 1 can be applied to estimate the probability P_{u,n} if the numbers L, N and n are appropriately chosen.

It can be proved that both Theorem 1 and our previous argument provide an estimate of the form P_{u,n} ≤ ρ^{αu} with a universal constant 0 < α < 1, only the parameter α is different in these two estimates. (Observe that ρ = \frac{L}{N} ≥ ∫ f(x)μ( dx) for all f ∈ F in this example.). To see that we proved such an estimate for P_{u,n} which implies the inequality P_{u,n} ≤ ρ^{αu} under the conditions of Theorem 1 observe that ρ^{u−L} ≤ ρ^{40u/41}, and n^{u} ≤ ρ^{−u/200}. Moreover, it can be seen that if we are not interested in the value of the universal parameter α, then this estimate is sharp. I also remark that we can give a useful estimate for P_{u,n} in this example (and not only the trivial bound P_{u,n} ≤ 1) only if u > L.

The main content of Theorem 1 is that a similar picture arises if the supremum of the sums we consider is defined with the help of an arbitrary class of functions with polynomially increasing covering numbers. Namely, Theorem 1 states that if F is a class of functions with polynomially increasing covering numbers with some exponent L and parameter D that satisfies some natural conditions, then there are universal constants

0 < α < 1, C_{1} > 1 and C_{2} > 0 such that P (sup_{f∈F} S_{n}(f) > u) ≤ Dρ^{−αu} if n ≥ C_{1}L and

ρ ≤ n^{−C_{2}}. Here we applied the notations of Theorem 1. We also gave an explicit value for these universal parameters in Theorem 1, but we did not try to find a really good choice. It might be interesting to show on the basis of the calculation of the present paper that we can choose C_{1} = 1 + ε or α = 1 − ε with arbitrary small ε > 0 if the remaining universal constants are appropriately chosen.

As the above considered example shows the estimate of Theorem 1 holds only if u ≥ CL with a number C ≥ 1. The other condition of Theorem 1 by which ρ ≤ n^{−C_{2}} with a sufficiently large number C_{2} > 0 can be weakened. Actually this is the topic of paper [5] which is a continuation of the present work. In paper [5] I shall consider such classes of functions F with polynomially increasing covering numbers for which the parameter ρ considered in Theorem 1 can be relatively large. On the other hand, in [5] we shall consider only such classes of functions F whose elements have the ‘normalizing property’ ∫ f(x)μ( dx) = 0 for all f ∈ F. In the present work we did not impose such a normalization condition, because in the case ρ ≤ n^{−α} with some α > 1 the lack of normalization has a negligible effect.

Theorem 1 will be proved with the help of Theorem 1A formulated below. After its formulation I shall explain that Theorem 1A can be considered as a special case of Theorem 1.

Theorem 1A. Let X = {x_{1}, …, x_{N}} be a finite set of N elements, and let X be the σ-algebra consisting of all subsets of X. Let μ denote the uniform distribution on X, i.e. let μ(A) = \frac{|A|}{N} for all sets A ⊂ X, where |A| denotes the cardinality of the set A. Let F be a class of functions with polynomially increasing covering numbers with some parameter D ≥ 1 and exponent L ≥ 1 on the measurable space (X, X) such that 0 ≤ f(x) ≤ 1 for all x ∈ X and f ∈ F, and ∫ f(x)μ( dx) ≤ \frac{ρ}{2} for all f ∈ F with some ρ > 0 which satisfies the inequality ρ ≤ min(\frac{1}{1000}, L^{−20}).

For the sake of a simpler argument we shall assume that the number N has the special form N = 2^{k}N_{0} with some integer k ≥ 0 and a number N_{0} that satisfies the inequality \frac{1}{16}ρ^{−3/2} < N_{0} ≤ \frac{1}{8}ρ^{−3/2}. (Actually we could choose an arbitrary number N ≥ \frac{1}{16}ρ^{−3/2} in Theorem 1A, but this special choice of N makes our argument simpler.)

Introduce for all numbers p = 1, 2, … the p-fold direct product X^{p} of the space X together with the p-fold product measure μ_{p} of the uniform distribution μ on X, i.e. let each sequence x^{(p)} = (x_{s_{1}}, …, x_{s_{p}}), x_{s_{j}} ∈ X, 1 ≤ j ≤ p, have the weight μ_{p}(x^{(p)}) = \frac{1}{N^{p}} with respect to the measure μ_{p}.

Given a function f ∈ F and a positive integer p let us define the set B_{p}(f) ⊂ X^{p} for all p ≥ 2 by the formula

B_{p}(f) = {x^{(p)} = (x_{s_{1}}, …, x_{s_{p}}): x^{(p)} ∈ X^{p}, f(x_{s_{j}}) = 1 for all 1 ≤ j ≤ p}, (1.3)

and put

B_{p} = B_{p}(F) = ⋃_{f∈F} B_{p}(f).  (1.4)

If p ≥ 2L and p ≤ ρ^{−1/100}, then there exist some universal constants C_{1} > 0 and 1 > C_{2} > 0 such that

μ_{p}(B_{p}) = μ_{p}(B_{p}(F)) ≤ C_{1}Dρ^{C_{2}p}.  (1.5)

We can choose for instance C_{1} = 2 and C_{2} = \frac{1}{4}.

In Theorem 1A we considered a special case of the problem discussed in Theorem 1. We took a space of the form X = {x_{1}, …, x_{N}} with the uniform distribution μ on it, and considered a class of functions with polynomially increasing covering numbers and some additional special properties. If we apply Theorem 1 with the choice p = n, then the event B_{p}(F) defined in (1.4) agrees with the event sup_{f∈F} S_{n}(f) ≥ n, and

formula (1.5) implies the estimate (1.2) with the special choice u = n for the system X, F, μ considered in Theorem 1A.

It may be worth mentioning that in Theorem 1A we considered a class of functions F which contains functions f with the property 0 ≤ f ≤ 1, while the event B_{p}(F) whose probability we have estimated depended only on the sets where these functions f take value 1. Hence the event B_{p}(F) would not change if we replaced all functions f ∈ F by the smaller functions f · I_{{f=1}}, where I_{{f=1}} denotes the indicator function of the set {x: f(x) = 1}. Nevertheless, it was useful to formulate the result in the form as we did, because by replacing the functions f by f · I_{{f=1}} we may get such a class of functions which has not polynomially increasing covering numbers. We shall prove Theorem 1 with the help of Theorem 1A formulated in the present form.

In Section 2 I make some remarks and discuss some examples which may explain the motivation behind the investigation of this paper. Theorem 1A will be proved by means an appropriate induction procedure in Section 3. Theorem 1 will be proved in Section 4 with the help of Theorem 1A and a good approximation.

2. A discussion of the results in this paper.

To understand the results of this work it may be useful to consider the following problem. Let us have a finite set X = {x_{1}, …, x_{N}} with large cardinality N and a class F of subsets of X which is a Vapnik–Ĉervonenkis class with some parameter B ≥ 1 and exponent K ≥ 1, and such that all sets A ∈ F contain no more than ρN points, where ρ is a relatively small number, say ρ ≤ min(\frac{1}{2000}, (2K)^{−30}). Let us choose n points from the set X randomly and independently from each other so that at each step we choose every point of X with the same probability \frac{1}{N}. Let n ≥ αK with an appropriately chosen sufficiently large but fixed universal constant α. Give a good estimate on the probability that one of the sets A ∈ F contains each one of the n selected points.

This probability is very small, and it can be well bounded by means of Theorem 1A. Indeed, if we define the class of functions F̃ which contains the indicator functions of the sets in F, then F̃ is a class of functions with polynomially increasing covering numbers which satisfies the conditions of Theorem 1A, and the probability we want to estimate equals the probability of the event B_{p}(F̃) defined in (1.4) with p = n. Hence Theorem 1A gives the estimate C_{1}Bρ^{C_{2}n} with some universal constants C_{1} > 0 and C_{2} > 0 for the probability we want to estimate.

Theorem 1 can be useful in the solution of the following generalized version of the previous problem. Let us consider the same class of functions F as before, and choose randomly n points from the set X independently of each other by the uniform distribution, and let us assume this time that ρ ≤ n^{−1/200}. Let us bound the probability of the event that one of the sets A ∈ F contains at least αK elements from the randomly chosen n points, where α is a sufficiently large fixed number, and K is the exponent of the Vapnik–Červonenkis class F. This probability can be estimated similarly to the previous case, only we have to apply Theorem 1 instead of Theorem 1A. We get the estimate Bρ^{αCK} with a universal constant C.

Similar problems can be solved with the help of results which give a good bound on the probability at the left-hand side of formula (1.2) if F is a class of functions with polynomially increasing kernel functions, and the inequality ∫ f(x)μ( dx) ≤ ρ holds for all functions f ∈ F with a small number ρ. (The measure μ in this formula is the distribution of the random variables which take part in the definition of the quantity S_{n}(f) appearing in Theorem 1.) I know some results in the literature in this direction, but they do not provide a good estimate in the previous problems. In particular, they do not show that the above considered probabilities are very small even in such cases when we consider relatively short sequences of selected points in the first problem or we are looking for such a set A ∈ F in the second problem which contains only relatively few elements from the random sequence we have selected. (We may get good estimates if the sequence we consider has a length n ≥ αK or we are looking for a set A ∈ F containing at least αK points of our sequence. Here α > 0 is a universal constant, and K is the exponent of the Vapnik–Červonenkis class.) The earlier results I know about do not give a good estimate in these problems, because they provide a sharp estimate in formula (1.2) of Theorem 1 only if the parameter ρ in it is relatively large.

In this paper I gave a good estimate in Theorem 1 if the parameter ρ in it is very small, namely if the inequality ρ ≤ n^{−200} holds. I am also interested in the question what can be told if this condition is dropped. This is the subject of my paper [5]. I also discuss some examples in that paper which show that its estimates are sharp, and I compare them with the results of some earlier works. The proofs in [5] are based on Theorem 1 of this work. But since the arguments of the two papers are essentially different I decided to handle them separately.

I wrote that the parameter ρ in Theorem 1 must be small. But actually the condition ρ ≤ n^{−200} imposed on it provides a relatively large bound. In the proof of the generalized version of Theorem 1 in paper [5] I shall adapt one of the main ideas in the Vapnik–Červonenkis theory. I try to reduce the estimation of the probability we are interested in to the estimation of the probability of relatively few events that can be simply bounded. Relatively few events means in this context that their number is only a polynomially, and not e.g. an exponentially increasing function of the sample size n. I shall be able to carry out such a program, since the parameter ρ in Theorem 1 is bounded by a (negative) power of the sample size n. This is the reason why it is important that we can apply Theorem 1 with relatively large parameters ρ.

I finish this section by some comments on the terminology of this paper. I applied the notion of classes of functions with polynomially increasing covering numbers. I introduced the same notion in my work [4] under the name ‘L_{1}-dense classes of functions’. I changed this name to make reference to the closely related notion of uniform covering numbers which was introduced in the literature at several places, see e.g. [1], [6] or [8]. I used the terminology Vapnik–Červonenkis classes in a non-standard way. Usually one calls a class C of subsets of a set X a Vapnik–Červonenkis class of dimension d if d is the largest integer such that for all subsets D of X containing d elements its intersections with the sets of C contain all subsets of D. (See e.g. [1].) An important combinatorial result called the Sauer lemma implies that a Vapnik–Červonenkis class of dimension d is a Vapnik–Červonenkis class with exponent K = d and parameter B = (\frac{e}{d})^{d} by our terminology. (On the other hand, if a class of sets is a Vapnik–Červonenkis class with exponent K and parameter B by our terminology, then it is a Vapnik–Červonenkis class of dimension d < d̄, if d̄ is such a number for which Bd̄^{K} < 2d̄.) Hence we may also speak of Vapnik–Červonenkis classes with given exponent and parameter. I prefer this terminology, because it expresses the most important property of Vapnik–Červonenkis classes, and it indicates the similarity of this notion with the notion of classes of functions with polynomially increasing covering numbers.

3. The proof of Theorem 1A.

Theorem 1A will be proved by means of induction with respect to the parameter k (appearing in the definition of the size N of the set X). The first result of this section, Lemma 3.1, formulates a result similar to Theorem 1A in the special case when the set X, where the functions f are defined contains relatively few points. We need it to start our induction procedure.

Lemma 3.1. Let us fix a number ρ, 0 < ρ < 1, and a set X = {x_{1}, …, x_{N_{0}}}, with N_{0} ≤ \frac{1}{8}ρ^{−3/2} points together with a class of functions F defined on X which satisfies the following weakened version of the property having polynomially increasing covering numbers with some parameter D ≥ 1 and exponent L ≥ 1. N (ε, F, L_{1}(μ)) ≤ Dε^{−L} for all 0 < ε ≤ 1, where μ is the uniform distribution on X, and N (ε, F, L_{1}(μ)) was introduced in the definition of uniform covering numbers. Let us also assume that ∫ f(x) dμ(x) ≤ ρ and f(x) ≥ 0 for all f ∈ F and x ∈ X. Let us consider an integer p ≥ 2L, and the set B_{p} = B_{p}(F) ⊂ X^{p} introduced in formula (1.4) together with the uniform measure μ_{p} on the p-fold product X^{p} of the space X. The inequality

μ_{p}(B_{p}) ≤ Dρ^{p/4}  (3.1)

holds.

Proof of Lemma 3.1. Let us choose a set of functions f_{1}, …, f_{s}, f_{j} ∈ F for all 1 ≤ j ≤ s, with cardinality s ≤ D(2N_{0})^{L} such that for all f ∈ F there is a function f_{j}, 1 ≤ j ≤ s, for which the inequality ∫ |f(x) − f_{j}(x)|μ( dx) ≤ \frac{1}{2N_{0}} holds. If ∫ |f(x) − f_{j}(x)|μ( dx) ≤ \frac{1}{2N_{0}} , then |f(x) − f_{j}(x)| ≤ \frac{1}{2} for all x ∈ X. This follows from the inequality \frac{1}{N_{0}} |f(x) − f_{j}(x)| ≤ ∫ |f(x) − f_{j}(x)|μ( dx) ≤ \frac{1}{2N_{0}} for all x ∈ X. As a consequence, \{x: f(x) = 1\} ⊂ \{x: f_{j}(x) ≥ \frac{1}{2}\} for such a pair of functions f and f_{j}, and

B_{p} = B_{p}(F) = ⋃_{f∈F} B_{p}(f) ⊂ ⋃_{j=1}^{s} \{(x_{t_{1}}, …, x_{t_{p}}): f_{j}(x_{t_{k}}) ≥ \frac{1}{2} for all 1 ≤ k ≤ p\} .

Besides, we have for each j, 1 ≤ j ≤ s,

μ_{p} \{(x_{t_{1}}, …, x_{t_{p}}): f_{j}(x_{t_{k}}) ≥ \frac{1}{2} for all 1 ≤ k ≤ p\}

= (μ \{x_{t}: f_{j}(x_{t}) ≥ \frac{1}{2}\})^{p} ≤ (2ρ)^{p}.

Hence the relations p ≥ 2L and N_{0} ≤ \frac{1}{8}ρ^{−3/2} imply that

μ_{p}(B_{p}) ≤ s(2ρ)^{p} ≤ D(2N_{0})^{p/2}(2ρ)^{p} ≤ Dρ^{p/4}.

Lemma 3.1 is proved.

In our inductive proof we also need a result presented in Lemma 3.2. It is a version of the following heuristic statement.

Let us consider a class of functions F on a finite set X with polynomially increasing covering numbers which consists of non-negative functions bounded by 1, and take the supremum of the integrals ∫ f(x)μ( dx) of all functions f ∈ F with respect to the uniform distribution μ on X. Let the cardinality of the set X be 2N, where the number N is of the form N = A2^{k} with some positive integers A and k, and let the above supremum of integrals be bounded by a number ρ_{k+1}. Then there is a number ρ_{k} slightly larger than ρ_{k+1} with the following property. For most subsets Y ⊂ X with cardinality N the supremum of the integrals of the restrictions of the functions f ∈ F to the set Y with respect to the uniform distribution on Y can be bounded by ρ_{k}.

Lemma 3.2. Let us define two sequences of numbers

N_{k} = 2^{k}N_{0}, and ρ_{k} = ρ ∏_{j=0}^{k−1} (1 + \frac{3}{N_{j}^{1/8}} )^{−1} ,  k = 1, 2, …, ρ_{0} = ρ, (3.2)

with the help of some starting numbers N_{0} and ρ which satisfy the relations ρ ≤ min(\frac{1}{1000}, L^{−20}) and \frac{1}{16}ρ^{−3/2} < N_{0} ≤ \frac{1}{8}ρ^{−3/2}. Let us fix an integer k ≥ 0, and a set X = {x_{1}, …, x_{2N_{k}}} with N_{k+1} = 2N_{k} = N_{0}2^{k+1} elements, and consider a class of functions F defined on the set X which has polynomially increasing covering numbers with parameter D ≥ 1 and exponent L ≥ 1 and satisfies the inequality 0 ≤ f(x) ≤ 1

for all points x ∈ X and functions f ∈ F. Put R_{k+1}(f) = ∑_{j=1}^{N_{k+1}} f(x_{j}), and assume that

the class of functions F also satisfies the condition R_{k+1}(f) ≤ N_{k+1}ρ_{k+1} for all f ∈ F. Let us define the quantity R_{Y} (f) = ∑_{x_{j}∈Y} f(x_{j}) for all functions f ∈ F and sets Y ⊂ X.

The following Statement (a) holds.

(a) The number of sets Y ⊂ X such that |Y | = N_{k}, and sup_{f∈F} R_{Y} (f) ≥ N_{k}ρ_{k} is less

than \binom{2N_{k}}{N_{k}}D exp \{−\frac{1}{100}2^{k/20}ρ^{−1/20}\}.

Proof of lemma 3.2. Let us fix a partition of X = {x_{1}, …, x_{2N_{k}}} to two point subsets {x_{j_{1}}, x_{j_{2}}}, …, {x_{j_{2N_{k}−1}}, x_{j_{2N_{k}}} } together with a sequence of i.i.d. random variables ε_{1}, …, ε_{N_{k}} with distribution P (ε_{l} = 1) = P (ε_{l} = −1) = \frac{1}{2} for all 1 ≤ l ≤ N_{k}. Let us define with their help the ‘randomized sum’

U_{k}(f) = ∑_{l=1}^{N_{k}} ε_{l} (f(x_{j_{2l−1}}) − f(x_{j_{2l}}))  (3.3)

for all f ∈ F.

Let us observe that for all f ∈ F the inequality

P (U_{k}(f) > 2z) ≤ exp \{−\frac{2z^{2}}{∑_{l=1}^{N_{k}}(f(x_{j_{2l−1}}) − f(x_{j_{2l}}))^{2}} \} ≤ e^{−z^{2}/2N_{k}ρ_{k+1}}  (3.4)

holds for all z > 0 by the Hoeffding inequality (see e.g. [7] Appendix B) and the inequality

∑_{l=1}^{N_{k}}(f(x_{j_{2l−1}}) − f(x_{j_{2l}}))^{2} ≤ 2 ∑_{j=1}^{2N_{k}} f(x_{j})^{2} ≤ 2R_{k+1}(f) ≤ 4N_{k}ρ_{k+1}.  (3.5)

(In formula (3.5) we exploit the condition 0 ≤ f(x) ≤ 1 which implies that f(x_{j})^{2} ≤ f(x_{j}).)

Define the (random) set

V_{k} = V_{k}(ε_{1}, …, ε_{N_{k}}) = ⋃_{l: ε_{l}=1}{x_{j_{2l−1}}} ∪ ⋃_{l: ε_{l}=−1}{x_{j_{2l}}}.

With such a notation we can write

{ω: ∑_{s∈V_{k}(ε_{1}(ω),...,ε_{N_{k}} (ω))} f(x_{s}) > N_{k}ρ_{k+1} + z}

⊂ \{ω: ∑_{s∈V_{k}(ε_{1}(ω),...,ε_{N_{k}} (ω))} f(x_{s}) > \frac{R_{k+1}(f)}{2} + z\} = \{ω: U_{k}(f)(ω) > 2z\}.

Hence

P ({ω: ∑_{s∈V_{k}(ε_{1}(ω),...,ε_{N_{k}} (ω))} f(x_{s}) > N_{k}ρ_{k+1} + z}) ≤ e^{−z^{2}/2N_{k}ρ_{k+1}}  (3.6)

for all z > 0 by relation (3.4).

I claim that relation (3.6) implies the following Statement (b).

(b) For all f ∈ F and z > 0 the number of sets V ⊂ X such that |V | = N_{k}, and

∑_{x∈V} f(x) ≥ N_{k}ρ_{k+1} + z is less than or equal to \binom{2N_{k}}{N_{k}}e^{−z^{2}/2N_{k}ρ_{k+1}}.

Indeed, it follows from relation (3.6) that for a fixed partition of the set X to two point subsets the number of those subsets V ⊂ X which contain exactly one point from each element of this partition, (and as a consequence contain exactly N_{k} points), and ∑_{s∈V} f(x_{s}) > N_{k}ρ_{k+1} + z is less than or equal to 2^{N_{k}}e^{−z^{2}/2N_{k}ρ_{k+1}}. We get an upper

bound for the quantity considered in statement (b) by summing up the number of sets V with these properties for all partitions of X to two point subsets, and taking into account how many times we counted each set V in this procedure. The number of the partitions of X to two point subsets equals (2N_{k} − 1)(2N_{k} − 3) ⋯ 3 · 1 = \frac{(2N_{k})!}{2^{N_{k}} N_{k}!}, and

each partition provides at most 2^{N_{k}}e^{−z^{2}/2Nρ_{k+1}} sets V with the desired properties. All sets V were counted N_{k}!-times in this calculation. (The multiciplicity by which a set V, |V | = N_{k}, was counted in the above calculation agrees with the number of those partitions of X to two point subsets which have the property that all of their elements contain a fixed element of V.) These considerations imply Statement (b).

Given a number 0 ≤ u < 1 there exist s ≤ Du^{−L} functions f_{1}, …, f_{s} in F such that for all f ∈ F and sets Y ⊂ X one of the functions f_{j}, 1 ≤ j ≤ s, satisfies the inequality ∑_{x∈Y} |f_{j}(x) − f(x)| ≤ ∑_{x∈X} |f_{j}(x) − f(x)| ≤ uN_{k+1}. We get this relation by

exploiting that F is a class of functions which has polynomially increasing covering numbers with parameter D and exponent L if we apply inequality (1.1) to estimate N (ε, F, L_{1}(μ)) with the uniform distribution μ on X instead of sup_{ν} N (ε, F, L_{1}(ν)).

This has the consequence that if ∑_{x∈Y} f(x) ≥ N_{k}ρ_{k+1} + z + 2uN_{k} for some Y ⊂ X and

f ∈ F, then there exists some index 1 ≤ j ≤ s such that ∑_{x∈Y} f_{j}(x) ≥ N_{k}ρ_{k+1} + z with

the same set Y ⊂ X. Hence Statement (b) implies that the number of sets Y such that |Y | = N_{k} and ∑_{x∈Y} f(x) ≥ N_{k}ρ_{k+1} + z + 2uN_{k} with some f ∈ F is less than or equal to

s · e^{−z^{2}/2N_{k}ρ_{k+1}} \binom{2N_{k}}{N_{k}} = Du^{−L}e^{−z^{2}/2N_{k}ρ_{k+1}} \binom{2N_{k}}{N_{k}}.

Put z = N_{k}ρ_{k+1} · N_{k}^{−1/8} and u = \frac{z}{N_{k}}. With such a choice we get that the number

of sets Y ⊂ X such that |Y | = N_{k} and sup_{f∈F} R_{Y} (f) ≥ N_{k}ρ_{k+1}(1 + 3N_{k}^{−1/8}) = N_{k}ρ_{k} is

less than

D (\frac{N_{k}^{1/8}}{ρ_{k+1}} )^{L} e^{−N_{k}^{3/4}ρ_{k+1}/2}\binom{2N_{k}}{N_{k}} = \binom{2N_{k}}{N_{k}}D (\frac{2^{k/8}N_{0}^{1/8}}{ρ_{k+1}} )^{L} e^{−2^{3k/4}N_{0}^{3/4}ρ_{k+1}/2}. (3.7)

It follows from the definition of ρ_{k} that \frac{1}{2}ρ ≤ ρ_{k+1} ≤ ρ, and we also have L ≤ ρ^{−1/20} because of the condition imposed on the number ρ. These relations together with the condition \frac{1}{16}ρ^{−3/2} < N_{0} ≤ \frac{1}{8}ρ^{−3/2} of Lemma 3.2 enable us to bound the expression in (3.7) from above by

\binom{2N_{k}}{N_{k}}D (C_{1}2^{k/8}ρ^{−19/16})^{ρ^{−1/20}} e^{−C_{2}2^{3k/4}ρ^{−1/8}} ≤ \binom{2N_{k}}{N_{k}}D exp \{−C_{3}2^{k/20}ρ^{−1/20}\}

with appropriate constants C_{1}, C_{2} and C_{3}. One can choose e.g. C_{3} = \frac{1}{100}, and this implies Statement (a). (In the last step of this estimation we have exploited that for a small number ρ > 0 and all positive integers k the term e^{−C_{2}2^{3k/4}ρ^{−1/8}} is much smaller than the reciprocal of (C_{1}2^{k/8}ρ^{−19/16})^{ρ^{−1/20}} which is of order

exp \{−const. ρ^{−1/20}(log k + log \frac{1}{ρ})\}.) Lemma 3.2 is proved.

Remark. It may be worth remarking that the most important part of Lemma 3.2, relation (3.4) or its consequence (3.6) can be considered as a weakened version of Lemma 3 in [3], and even its proof is based on the ideas worked out there. In formula (3.4) a random sum denoted by U_{k}(f) was estimated by means of the Hoeffding inequality. To get this estimate we had to bound the variance of the random variable U_{k}(f), and this was done in formula (3.5). In Lemma 3 of [3] a similar random sum was investigated, but in that case a good asymptotic formula and not only an upper bound was proved for the tail distribution of the random sum. In the proof of that result a sharp version of the central limit theorem was applied instead of the Hoeffding inequality, and we needed a good asymptotic formula and not only a good upper bound for the variance of the random sum we investigated. The proof of the good asymptotic formula for this variance was the hardest part in the proof of Lemma 3 in [3].

Proof of Theorem 1A. Let us fix some numbers N_{0}, ρ and L which satisfy the conditions of Lemma 3.2. Take an integer k ≥ 0, define the numbers N_{k} and ρ_{k} by formula (3.2), consider a space X = {x_{1}, …, x_{N_{k}}} with N_{k} elements and a class of functions F on it which has polynomially increasing covering numbers with parameter D ≥ 1 and exponent L ≥ 1, and it has the properties that if f ∈ F, then 0 ≤ f(x) ≤ 1 for all x ∈ X, and ∫ f(x)μ( dx) ≤ ρ_{k} with the uniform distribution μ on X. Fix an integer p such that p ≥ 2L, p ≤ ρ^{−1/100}, and let us also consider the sets B_{p}(f), f ∈ F, and B_{p} = B_{p}(F) introduced in formulas (1.3) and (1.4). They consist of sequences x^{(p)} = (x_{s_{1}}, …, x_{s_{p}}) ∈ X^{p} with some nice properties. Let V (p, ρ, N_{0}, k) = V_{D,L}(p, ρ, N_{0}, k) denote the supremum of the cardinality of the sets B_{p}(F) if the supremum is taken for all possible sets X and class of functions F with the above properties (with parameters N_{k} and ρ_{k}).

I claim that

V (p, ρ, N_{0}, k) ≤ C_{k}DN_{k}^{p}ρ^{p/4} for all k = 0, 1, 2, …  (3.8)

with

C_{k} = ∏_{j=0}^{k}(1 + 2^{−j}ρ).  (3.9)

Relation (3.8) will be proved by means of induction with respect to k. Its validity for k = 0 follows from Lemma 3.1. Let us assume that it holds for some k, take a set X with cardinality N_{k+1} = 2N_{k} together with a class of functions F which satisfies the above conditions with the parameters D, L, p, ρ_{k+1} and N_{k+1}, and let us give a good bound on the cardinality of the set B_{p}(F) defined in (1.3) and (1.4) in this case. To calculate the number of sequences x^{(p)} = (x_{s_{1}}, …, x_{s_{p}}) ∈ X^{p} which belong to the set B_{p}(F) let us take all sets Y ⊂ X with cardinality |Y | = N_{k}, let us bound the number of those sequences x^{(p)} ∈ B_{p}(F) for which also the property x^{(p)} ∈ Y^{p} holds, and let us sum up these numbers for all sets Y ⊂ X such that |Y | = N_{k}. Then take into account how many times we counted a sequence x^{(p)} in this summation. I claim that we get the following estimate in such a way:

|B_{p}(F)| ≤ DN_{k}^{p} \begin{matrix}( & {2N_{k} \atop N_{k}} & ) \\ ( & {2N_{k}−p \atop N_{k}−p} & ) \end{matrix} (C_{k}ρ^{p/4} + exp \{−\frac{1}{100}2^{k/20}ρ^{−1/20}\})  (3.10)

with the coefficient C_{k} defined in (3.9).

To prove relation (3.10) let us first observe that if F is a class of functions on the set X which has polynomially increasing covering numbers with parameter D and exponent L, and we restrict the domain where the functions of F are defined to a smaller set Y ⊂ X then the class of functions we obtain in such a way remains a class of functions which has polynomially increasing covering numbers with the same parameter D and exponent L. Hence if we fix a set Y with cardinality |Y | = N_{k} for which the property sup_{f∈F} R_{Y} (f) ≤ N_{k}ρ_{k} holds (with the quantity R_{Y} (f) introduced in

the formulation of Lemma 3.2), then the number of those sequences x^{(p)} for which x^{(p)} ∈ B_{p}(F) ∩ Y^{p} can be bounded by our induction hypothesis by C_{k}N_{k}^{p}Dρ^{p/4}. We shall bound the number of the sequences x^{(p)} ∈ B_{p}(F) ∩ Y^{p} for the remaining sets Y with cardinality |Y | = N_{k} by the trivial upper bound N_{k}^{p}, but the number of such sets Y is less than \binom{2N_{k}}{N_{k}}D exp \{−\frac{1}{100}2^{k/20}ρ^{−1/20}\} by Lemma 3.2. This yields the upper bound C_{k}N_{k}^{p}Dρ^{p/4}\binom{2N_{k}}{N_{k}} + N_{k}^{p}\binom{2N_{k}}{N_{k}}D exp \{−\frac{1}{100}2^{k/20}ρ^{−1/20}\} for the sum we get by summing up the number of sequences x^{(p)} ∈ Y^{p} ∩ B_{p}(F) for all subsets with |Y | = N_{k} elements. To prove (3.10) we still have to take into account how many times we counted the sequences x^{(p)} ∈ B_{p}(F) in this summation. If all coordinates of a sequence x^{(p)} ∈ B_{p}(F) are different, then we counted it \binom{2N_{k}−p}{N_{k}−p}-times, because to find a set Y, |Y | = N_{k}, containing the elements of this sequence x^{(p)} we have to extend these points with N_{k} −p new points from the remaining 2N_{k} − p points of X. If some coordinates of a sequence x^{(p)} may agree, then we might have counted this sequence with greater multiplicity. The above considerations imply (3.10).

To prove relation (3.8) with the help of (3.10) let us observe that under the conditions of Theorem 1A (in particular, we have \frac{1}{N_{0}} ≤ 16ρ^{3/2}, p^{2} ≤ ρ^{−1/50} ≤ \frac{1}{16}ρ^{−1/6}, 2N_{k} − p ≥ N_{k} = 2^{k}N_{0} for all k = 0, 1, 2, … with a sufficiently small ρ > 0)

N_{k}^{p} \begin{matrix}( & {2N_{k} \atop N_{k}} & ) \\ ( & {2N_{k}−p \atop N_{k}−p} & ) \end{matrix} = N_{k}^{p} \begin{matrix}( & {2N_{k} \atop N_{k}} & ) \\ ( & {2N_{k}−p \atop N_{k}} & ) \end{matrix} = N_{k}^{p} \frac{2N_{k}(2N_{k} − 1) ⋯ (2N_{k} − p + 1)}{N_{k}(N_{k} − 1) ⋯ (N_{k} − p + 1)}

= N_{k+1}^{p} (1 + \frac{1}{2(N_{k} − 1)}) (1 + \frac{2}{2(N_{k} − 2)}) ⋯ (1 + \frac{p − 1}{2(N_{k} − p + 1)})

≤ N_{k+1}^{p} exp \{\frac{p^{2}}{2^{k+1}N_{0}} \} ≤ N_{k+1}^{p}e^{2^{−(k+1)}ρ^{4/3}} ≤ N_{k+1}^{p} (1 + \frac{1}{3}2^{−(k+1)}ρ) ,

and

exp \{−\frac{1}{100}2^{k/20}ρ^{−1/20}\} = ρ^{p/4} exp \{−\frac{1}{100}2^{k/20}ρ^{−1/20} + \frac{p}{4} log \frac{1}{ρ}\} ≤ C_{k} \frac{ρ^{p/4}}{3} 2^{−(k+1)}ρ

with the coefficient C_{k} defined in (3.9). These estimates together with (3.10) imply (3.8) for parameter k + 1.

It is not difficult to prove Theorem 1A with the help of relation (3.8). To do this let us observe that ρ_{k} ≥ \frac{ρ}{2} and C_{k} ≤ 2 for all k = 0, 1, 2, . . .. Hence taking a class of functions F on a set X with cardinality N_{k} with some k ≥ 0 which satisfies the conditions of Theorem 1A we can write (by exploiting that ∫ f(x)μ( dx) ≤ \frac{ρ}{2} ≤ ρ_{k}) the estimate

μ_{p}(B_{p}(F)) = N_{k}^{−p}|B_{p}(F)| ≤ N_{k}^{−p}V (ρ, p, N_{0}, k) ≤ 2Dρ^{−p/4}

by relation (3.8). Theorem 1A is proved.

4. The proof of Theorem 1.

First we prove a special case of Theorem 1 in Lemma 4.1. Here we take a class of functions F on a finite set X of cardinality 2^{k} with some integer k, and μ is the uniform distribution on X.

Lemma 4.1. Let us consider a finite set X = {x_{1}, …, x_{2^{k}}} with N = 2^{k} elements together with a class of functions F on X which has monotone increasing covering numbers with some parameter D ≥ 1 and exponent L ≥ 1, and it contains functions f ∈ F with the properties 0 ≤ f(x) ≤ 1 for all x ∈ X and ∫ f(x)μ( dx) ≤ ρ with some 0 < ρ < 1. Here μ denotes the uniform distribution on X. Let us take the n-fold direct product X^{n} of X with some number n ≥ 2, and define the function S_{n}(f)(x_{s_{1}}, …, x_{s_{n}}) =

∑_{j=1}^{n} f(x_{s_{j}}) for all (x_{s_{1}}, …, x_{s_{n}}) ∈ X^{n} and f ∈ F. Let us assume that ρ ≤ n^{−200}, and

N = 2^{k} ≥ ρ^{−3/2}. Then the set B_{n}(u) ⊂ X^{n} defined as

B_{n}(u) = {(x_{s_{1}}, …, x_{s_{n}}): sup_{f∈F} S_{n}(f)(x_{s_{1}}, …, x_{s_{n}}) > u}  (4.1)

satisfies the inequality

μ_{n}(B_{n}(u)) ≤ 2Dρ^{u/25} for all u ≥ 40L,  (4.2)

where μ_{n} denotes the uniform distribution on X^{n}.

Proof of Lemma 4.1 Let us define for all functions f ∈ F and integers j, 1 ≤ j ≤ R, where R is defined by the relation n < 2^{R} ≤ 2n, the functions f_{j}(x) = min(2^{−j}, f(x)) and f̄_{j}(x) = 2^{j}f_{j}(x), x ∈ X. Put F_{j} = {f_{j}: f ∈ F} and F̄_{j} = {f̄_{j}: f ∈ F}. One can simply check that if F is a class of functions which has polynomially increasing covering numbers with parameter D and exponent L, then F_{j} is a class of functions which has polynomially increasing covering numbers with parameter D and exponent L, while F̄_{j} is a class of functions which has polynomially increasing covering numbers with parameter D2^{jL} and exponent L. We can also state that ∫ f_{j}(x)μ( dx) ≤ ρ, and ∫ f̄_{j}(x)μ( dx) ≤ 2^{j}ρ for all f ∈ F.

Let us define for all f ∈ F and 1 ≤ j ≤ R the following function H_{j}(f) on X^{n}:

H_{j}(f)(x_{s_{1}}, …, x_{s_{n}}) = the number of such indices l for which f̄_{j}(x_{s_{l}}) = 1.

We can write

S_{n}(f)(x_{s_{1}}, …, x_{s_{n}}) ≤ ∑_{j=1}^{R} 2^{1−j}H_{j}(f)(x_{s_{1}}, …, x_{s_{n}}) + 1

for all f ∈ F. This formula implies the inequality

sup_{f∈F} S_{n}(f)(x_{s_{1}}, …, x_{s_{n}}) ≤ ∑_{j=1}^{R} 2^{1−j} sup_{f∈F} H_{j}(f)(x_{s_{1}}, …, x_{s_{n}}) + 1,

and the relation

{(x_{s_{1}}, …, x_{s_{n}}): sup_{f∈F} S_{n}(f)(x_{s_{1}}, …, x_{s_{n}}) > u}

⊂ ⋃_{j=1}^{R} \{(x_{s_{1}}, …, x_{s_{n}}): \frac{sup_{f∈F} H_{j}(f)(x_{s_{1}}, …, x_{s_{n}})}{2^{j−1}} > \frac{(u − 1)}{\sqrt{2} − 1}2^{−j/2}\} .

Hence

μ_{n}(B_{n}(u)) ≤ ∑_{j=1}^{R} μ_{n}(D_{n}(u, j))  (4.3)

for the sets B_{n}(u) defined in (4.1) and

D_{n}(u, j) = \{(x_{s_{1}}, …, x_{s_{n}}): sup_{f∈F} H_{j}(f)(x_{s_{1}}, …, x_{s_{n}}) > \frac{\sqrt{2} − 1}{2}(u − 1)2^{j/2}\} ,
, 1 ≤ j ≤ R.

We can prove Lemma 4.1 with the help of relation (4.3) if we give a good estimate on the measures μ_{n}(D_{n}(u, j)). This can be done with the help of Theorem 1A.

Indeed, the set D_{n}(u, j) consists of such sequences (x_{s_{1}}, …, x_{s_{n}}) ∈ X^{n} which have a subsequence (x_{s_{p_{1}}} , …, x_{s_{p_{t}}}) with t = t(j) = [\frac{\sqrt{2}−1}{2}(u − 1)2^{j/2}] + 1 elements, where [·] denotes integer part, with the property that there is a function f ∈ F such that the function f̄_{j}(·) defined with its help equals 1 in all coordinates of this subsequence. More explicitly,

D_{n}(u, j) =  ⋃_{{l_{1},...,l_{t}}⊂{1,...,n}} ( ⋃_{f∈F}{(x_{1}, …, x_{n}): f̄_{j}(x_{s_{l_{1}}} ) = 1, …, f̄_{j}(x_{s_{l_{t}}}) = 1}) (4.4)

with t = t(j) = [\frac{\sqrt{2}−1}{2}(u − 1)2^{j/2}] + 1.

The outside union in (4.4) consists of \binom{n}{t(j)} ≤ n^{t(j)} terms, and the cardinality of the sequences (x_{1}, …, x_{n}) in the inner union can be bounded by means of Theorem 1A for each term if it is applied with p = t(j), in the space X consisting of N = 2^{k} = N_{0}2k̄ points, for the class of functions F̄_{j} which is a class of functions which has polynomially increasing covering numbers with parameter D2^{jL} and exponent L. Moreover, the functions f̄_{j} ∈ F̄_{j} satisfy the inequality ∫ f̄_{j}(x)μ( dx) ≤ 2^{j}ρ. This means that under the conditions of Lemma 4.1 we can apply Theorem 1A for the class of functions F̄_{j} with parameter ρ̄ = 2^{j+1}ρ instead of ρ. (We have to check that all conditions of Theorem 1A hold. In particular, we can state that ρ̄ = 2^{j+1}ρ ≤ L^{−20}, since ρ ≤ n^{−200}, 2^{j} ≤ 2n, and since we estimate the probability in formula (4.2) only under the condition u ≥ 40L, and this probability is zero if u > n, hence we may assume that L ≤ \frac{n}{40}. We chose the term N_{0} in the application of Theorem 1A as N_{0} = 2^{k_{0}} with k_{0} defined by the relation \frac{1}{16}ρ^{−3/2} < 2^{k_{0}} ≤ \frac{1}{8}ρ^{−3/2}, and k̄ = k − k_{0}.)

We will prove with the help of the above relations the inequality

μ_{n}(D_{n}(u, j)) = \frac{|D_{n}(u, j)|}{N^{n}} ≤ 2n^{t(j)}D2^{jL}(2^{j+1}ρ)^{t(j)/4}
≤ 2D(8n^{5}ρ)^{t(j)/4} ≤ 2Dρ^{t(j)/5} ≤ Dρ^{ju/25}.  (4.5)

To get the first estimate in the second line of formula (4.5) observe that under the condition of Lemma 4.1 \frac{\sqrt{2}−1}{2}(u − 1) ≥ 4L, hence 2^{jL} ≤ 2^{j2^{−j/2}t(j)/4} ≤ 2^{t(j)/4}, and by the definition of the number R we have

(2^{j+1})^{t(j)/4} ≤ (2^{R+1})^{t(j)/4} ≤ (4n)^{t(j)/4}.

We imposed the condition n ≤ ρ^{−1/200}, and this implies the second inequality. Finally t(j) ≥ \frac{ju}{5}. (In the last inequality a j = 1 parameter is the worst case.) Relation (4.2) follows from (4.3) and (4.5). Lemma 4.1 is proved

Now we turn to the proof of the main result of this paper.

Proof of Theorem 1. We may assume that all functions f ∈ F are non-negative, i.e. 0 ≤ f(x) ≤ 1 for all f ∈ F and x ∈ X, because we can replace the function f by its absolute value |f|, and apply the result for this new class of functions which also satisfies the conditions of Theorem 1. Next I show that we also may assume that the class of functions F contains only finitely many functions, and it satisfies the same conditions as the original class of function F with the only difference that we assume that F is a class of functions which has polynomially increasing covering numbers with the same exponent L but with parameter 2^{L}D instead of D.

Indeed, if a number is an upper bound for the probability

P ( sup_{f∈F′} S_{n}(f) > u) for all finite subsets F′ ⊂ F, then it is also an upper bound for P (sup_{f∈F} S_{n}(f) > u). Besides, the conditions of Theorem 1 remain valid if F is replaced

by an arbitrary class of functions F′ ⊂ F with a small modification. Namely, we can state that F′ is a class of functions which has polynomially increasing covering numbers with exponent L but with a possibly different parameter D̄ = 2^{L}D. (We had to change the parameter D of a class of functions F′ ⊂ F with polynomially increasing covering numbers, because although we can choose a sequence of functions f_{1}, …, f_{m} with m ≤ Dε^{−L} elements which is an ε-dense set in F with respect to the L_{1}(ν) norm with a probability measure ν, and f_{j} ∈ F, but these functions may be not contained in F′. To overcome this difficulty we choose a sequence f_{1}, …, f_{m} with m ≤ 2^{L}Dε^{−L} elements such that min_{1≤j≤m} ∫ |f −f_{j}| dν ≤ \frac{ε}{2} for all functions f ∈ F′. We may also assume

that for all these functions f_{j} there is a function f ∈ F′ whose distance from f_{j} in the L_{1}(ν) norm is less than or equal to \frac{ε}{2}, since we can drop those functions f_{j} which do not have this property. Then we replace those functions f_{j} for which f_{j} ∉ F′ by a function f ∈ F′ such that ∫ |f − f_{j}| dν ≤ \frac{ε}{2}. In such a way we get an ε-dense subclass of F′ with m ≤ 2^{L}Dε^{−L} elements in the L_{1}(ν) norm.)

In the next step I show that we may restrict our attention to the case when the functions of the class of functions F (consisting of finitely many functions) take only finitely many values. For this goal first I split up the interval [0, 1] into n subintervals of the following form: B_{j} = (\frac{j−1}{n}, \frac{j}{n}], 2 ≤ j ≤ n, and B_{1} = [0, \frac{1}{n}]. (We defined the function B_{1} in a slightly different way in order to guarantee that the point zero is also contained in some set B_{j}.) Then given a class of function F on a set X that contains finitely many functions f_{1}, …, f_{R} we define the following sets A(s(1), …, s(R)) ⊂ X (depending on F):

A(s(1), …, s(R)) = {x: f_{j}(x) ∈ B_{s(j)}, for all 1 ≤ j ≤ R},

where 1 ≤ s(j) ≤ n for all 1 ≤ j ≤ R.

In such a way the sets A(s(1), …, s(R)) make up a partition of the set X. Actually, for the sake of a simpler argument we shall diminish a bit the set X, by defining it as the union of those sets A(s(1), …, s(R)) for which μ(A(s(1), …, s(R))) > 0 with the measure μ appearing in Theorem 1. This restriction will cause no problem in our later considerations.

We shall define new functions f̃_{j}(x), 1 ≤ j ≤ R, by means of the partition of X to the sets A(s(1), …, s(R)) by the formula

f̃_{j}(x) = \frac{∫_{A(s(1),...,s(R))} f_{j}(x)μ( dx)}{μ(A(s(1), …, s(R)))}, 1 ≤ j ≤ R, if x ∈ A(s(1), …, s(R)).

We have |f_{j}(x) − f̃_{j}(x)| ≤ \frac{1}{n} for all 1 ≤ j ≤ n and x ∈ X. Hence

| sup_{1≤j≤R}(S_{n}(f_{j}) − S_{n}(f̃_{j}))| ≤ 1,

for almost all sequences ξ_{1}(ω), …, ξ_{n}(ω), and as a consequence

P ( sup_{1≤j≤R} S_{n}(f_{j}) > u + 1) ≤ P ( sup_{1≤j≤R} S_{n}(f̃_{j}) > u)  (4.6)

Let us also observe that the class of functions F̃ = {f̃_{j}, 1 ≤ j ≤ R} also satisfies the conditions of Theorem 1, i.e. ∫ f̃_{j}(x)μ( dx) ≤ ρ for all 1 ≤ j ≤ R, and F̃ is a class of functions which has polynomially increasing covering numbers with parameter D̄ = 2^{L}D and exponent L. (The conditions on the numbers n and ρ clearly remain valid.)

The first relation follows from the identity ∫ f̃_{j}(x)μ( dx) = ∫ f_{j}(x)μ( dx) which holds because of the identities

∫_{A(s(1),...,s(R))} f̃_{j}(x)μ( dx) = ∫_{A(s(1),...,s(R))} f_{j}(x)μ( dx)

for all sets A(s(1), …, s(R)).

To prove that F̃ has polynomially increasing covering numbers with parameter 2^{L}D and exponent L let us introduce for all probability measures ν the probability measure ν̃ = ν̃(ν) which is defined by the property that for all (measurable) sets A(s(1), …, s(R)) and B ⊂ A(s(1), …, s(R)) the identity ν̃(B) = μ(B)\frac{ν(A(s(1),...,s(R)))}{μ(A(s(1),...,s(R)))} holds. Because of the special form of the functions f̃_{j} if a set of functions F̃_{ε,ν̃} ⊂ F̃ is an ε-dense subset of F̃ in the L_{1}(ν̃) norm, then it is also a ε-dense subset of F̃ in the L_{1}(ν) norm. (In the proof of this statement we exploit that

ν̃(A(s(1), …, s(R))) = ν(A(s(1), …, s(R)))

for all sets A(s(1), …, s(R)), and it depends only on the value of a measure ν on the sets A(s(1), …, s(R)) whether a set of functions {f_{1}, …, f_{m}} ⊂ F̃ is an ε-dense subset of F̃ in the L_{1}(ν) norm.)

Hence it is enough to prove the existence of an ε-dense subset F̃_{ε,ν̃} of F̃ in the L_{1}(ν̃) norm with cardinality bounded by D̄ε^{−L} only with respect to such measures ν̃ which can be written in the form ν̃ = ν̃(ν) with some probability measure ν. In this case the relation we want to check follows from the fact that the original class of functions F has polynomially increasing covering numbers with parameter 2^{L}D and exponent L, and the inequality ∫ |f̃_{j} − f̃_{j′}|dν̃(ν) ≤ ∫ |f_{j} − f_{j′}|dν holds for all pairs f_{j}, f_{j′} ∈ F and probability measure ν. This inequality holds, since

∫_{A(s(1),...,s(R))} |f̃_{j}(x) − f̃_{j′}(x)| dν̃(ν)(x) ≤ ∫_{A(s(1),...,s(R))} |f_{j}(x) − f_{j′}(x)| dν(x)

for all sets A(s(1), …, s(R)).

Let us observe that for all k ≥ 1 we can define such a ‘discretized’ probability measure μ̄_{k} on the σ-algebra X_{k} with atoms A(s(1), …, s(R)) in the space X for which

|μ̄_{k}(A(s(1), …, s(R))) − μ(A(s(1), …, s(R)))| ≤ 2^{−k},

and the probability μ̄_{k} has the property that for all sets A(s(1), …, s(R))

μ̄_{k}(A(s(1), …, s(R))) = α(A(s(1), …, s(R)))2^{−k}  (4.7)

with a non-negative integer α(A(s(1), …, s(R))). (To find such a probability measure μ̄_{k} let us list the sets A(s(1), …, s(R)) as B_{1}, …, B_{Q}, and define the measure μ̄_{k} by

the relation ∑_{l=1}^{s} μ̄_{k}(B_{l}) = β_{s}2^{−k} if (β_{s} − 1)2^{k} < ∑_{l=1}^{s} μ_{k}(B_{l}) ≤ β_{s}2^{−k} with a positive

integer β_{s}. We assume this relation for all 1 ≤ s ≤ Q.)

Clearly,

P ( sup_{1≤j≤R} S_{n}(f̃_{j}) > u) = lim_{k→∞} Pμ̄_{k} ( sup_{1≤j≤R} S_{n}(f̃_{j}) > u)  (4.8)

for all u > 0, where Pμ̄_{k} means that we consider the probability of the same event as at the left-hand side of the identity, but this time we take i.i.d. random variables ξ_{1}, …, ξ_{n} with distribution μ̄_{k} (on the σ-algebra generated by the atoms A(s(1), …, s(R))) in the definition of the random variables S_{n}(f̃_{j}).

We shall bound the probabilities at the right-hand side in formula (4.8) for all large indices k by means of Lemma 4.1. This will be done with the help of the following construction. Take a space X̂ = X̂_{k} = {x_{1}, x_{2}, …, x_{2^{k}}} with 2^{k} elements and with the uniform distribution μ = μ^{(k)} on its points. Let us fix a partition of X̂ consisting of some sets Â(s(1), …, s(R)) with α(A(s(1), …, s(R))) elements. The number α(·) was introduced in (4.7). Let us define the functions f̂_{j}(x), 1 ≤ j ≤ R, x ∈ X̂, by the formula f̂_{j}(x) = \frac{s(j)}{n}, 1 ≤ j ≤ R, if x ∈ Â(s(1), …, s(R)). Take the n-fold direct product X̂^{n} of X̂ together with the uniform distribution μ_{n} = μ_{n}^{(k)} on it and the functions

S_{n}(f̂_{j})(x_{t_{1}}, …, x_{t_{n}}) = ∑_{l=1}^{n} f̂_{j}(x_{t_{l}}), 1 ≤ j ≤ R, if (x_{t_{1}}, …, x_{t_{n}}) ∈ X̂^{n} on the space X̂^{n}. I

claim that

Pμ̄_{k} ( sup_{1≤j≤R} S_{n}(f̃_{j}) > u) = μ_{n}^{(k)} ({(x_{t_{1}}, …, x_{t_{n}}): sup_{1≤j≤R} S_{n}(f̂_{j})(x_{t_{1}}, …, x_{t_{n}}) > u})
≤ 2D̄ρ^{u/25} if u > 8L.  (4.9)

The identity in formula (4.9) holds, since the joint distribution of the random vectors S_{n}(f_{j})(ξ_{1}, …, ξ_{n}), 1 ≤ j ≤ R, where ξ_{1}, …, ξ_{n} are independent random variables with distribution μ̄_{k} and of the random vectors S_{n}(f̂_{j})(x_{t_{1}}, …, x_{t_{n}}), 1 ≤ j ≤ R, where the distribution of (x_{t_{1}}, …, x_{t_{n}}) ∈ X̂^{n} is μ_{n}^{(k)}, agree. To prove the last inequality of (4.9) it is enough to check that for all sufficiently large numbers k the class of functions F̂ = {f̂_{1}, …, f̂_{R}} on the space X̂ = X̂_{k} satisfies the conditions of Lemma 4.1. Namely, F̂ has polynomially increasing covering numbers with parameter D̄ = 2^{L}D and exponent L, and ∫ f̂_{j}(x)μ( dx) ≤ ρ with a number ρ ≤ n^{−200} for all f̂_{j} ∈ F̂.

We should explain why F̂ is a class of functions on X̂ with polynomially increasing covering numbers. Let us observe that to prove this it is enough to find good covering numbers only for such probability measures ν̂ which have a constant density (with respect to the uniform distribution μ^{(k)}) on all sets Â(s(1), …, s(R)). This reduction of the probability measures can be done similarly as we proved that F̃ has polynomially increasing covering numbers with the help of the measures ν̃(ν). Given a measure ν̂ on X̂ with the above property let us correspond to it the measure ν̃ on X defined by the relation ν̃(A(s(1), …, s(R))) = ν̂(Â(s(1), …, s(R))) for all sets A(s(1), …, s(R)). Then we get that if a class of functions F̃_{ε,ν̃} = {f̃_{l_{1}}, …, f̃_{l_{s}}} is an is an ε-dense class of F̃ with respect to the L_{1}(ν̃) norm, then the class of function F̂_{ε,ν̂} = {f̂_{l_{1}}, …, f̂_{l_{s}}} is an is an ε-dense class with respect to the L_{1}(ν̂) norm. This implies that F̂ has such polynomially covering numbers as we demanded.

Then we get the inequality part of formula (4.9) from Lemma 4.1. Relation (1.2) follows from (4.9), (4.8) and (4.6). We still have to understand that in our estimation the coefficient 2D̄ = 2^{L+1}D in (4.9) can be replaced by D if we estimate the probability (1.2) only for u ≥ \frac{1}{4}(L + 1), and the term ρ^{u/25} in (4.9) is replaced by ρ^{u/50} when turning from (4.9) to formula (1.2). To see this observe that ρ^{u/25} ≤ ρ^{\frac{1}{4} (L+1)/50} · ρ^{u/50} ≤ n^{−(L+1)}ρ^{u/50} ≤ \frac{1}{2}2^{−L}ρ^{u/50} if u ≥ \frac{1}{4}L, ρ ≤ n^{−200}, and n ≥ 2. Theorem 1 is proved.

References.

[1] R. M. Dudley, Uniform Central Limit Theorems. Second Edition. Cambridge University Press, Cambridge (2014)

[2] D. Haussler, Sphere packing numbers of subsets of Boolean n–cube with bounded Vapnik–Chervonenkis dimension. Journal of Combinatorial Theory A 69, 217–232 (1995)

[3] J. Komlós, P. Major, G. Tusnády, An approximation of partial sums of independent rv.’s and the sample DF. II Z. Wahrscheinlichkeitstheorie verw. Gebiete 34, 33–58 (1976)

[4] P. Major, On the estimation of multiple random integrals and U-statistics Lecture Notes in Mathematics vol 2079 (Springer) Heidelberg New York Dordrecht London (2013)

[5] P. Major, On the tail behaviour of the distribution function of the supremum of a class of sums of i.i.d. random variables. Submitted to Stochastic Processes and their Applications.

[6] D. Pollard, A central limit theorem for empirical processes. Austral Math. Soc. (Series A). 235–248 33, (1982)

[7] D. Pollard, Convergence of Stochastic Processes. (Springer, New York, (1984)

[8] A. W. van der Vaart, J. A. Wellner, Weak Convergence and Empirical Processes. Springer, New York (1996)