Sharp tail distribution estimates for the supremum of a class of sums of i.i.d. random variables

Péter Major Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences

Summary. We take a class of functions F with polynomially increasing covering numbers on a measurable space (X, X) together with a sequence of i.i.d. X-valued random

variables ξ_{1}, …, ξ_{n}, and give a good estimate on the tail behaviour of sup_{f∈F} ∑_{j=1}^{n} f(ξ_{j}) if

the relations sup_{x∈X} |f(x)| ≤ 1, Ef(ξ_{1}) = 0 and Ef(ξ_{1})^{2} < σ^{2} hold with some 0 ≤ σ ≤ 1

for all f ∈ F. Roughly speaking this estimate states that under some natural conditions the above supremum is not much larger than the largest element taking part in it. The proof heavily depends on the main result of paper [6]. We also present an example that shows that our results are sharp, and compare them with results of earlier papers.

Introduction.

The main result of this paper is an estimate about the tail-distribution of the supremum of sums of i.i.d. random variables presented in Theorem 1 together with an extension of it that provides an estimate for this tail-distribution in some cases not covered in Theorem 1. At first glance these results may look rather complicated, but as I try to explain in Section 2 they yield sharp estimates under natural conditions. They express such a fact that under some natural conditions we can get an almost as good bound for the supremum of an appropriately defined class of random sums as for one term taking part in this supremum. Before presenting these results I recall the definition of uniform covering numbers and classes of functions with polynomially increasing covering numbers, since they appear in the formulation of our results. Here I define the notion of uniform covering numbers, unlike to [6], with respect to all L_{p}-norms, p ≥ 1, because in some arguments I shall apply it for p = 2 and not for p = 1.

Definition of uniform covering numbers with respect to L_{p}-norms. 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_{p}-norm, 1 ≤ p < ∞, is sup_{ν} N (ε, F, L_{p}(ν)),

where the supremum is taken for all probability measures ν on the space (X, X), and N (ε, F, L_{p}(ν)) 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}|^{p} dν ≤ ε^{p} 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 with parameter p = 1.

Theorem 1 yields the following estimate.

Theorem 1. Let a sequence of independent, identically distributed random variables ξ_{1}, …, ξ_{n}, n ≥ 2, be given with values in a measurable space (X, X) with some distribution μ together with a countable class of functions F on the same space (X, X) which has polynomially increasing covering numbers with parameter D ≥ 1 and exponent L ≥ 1. Let the class of functions F satisfy also the relations sup_{x∈X} |f(x)| ≤ 1, ∫ f(x)μ( dx) = 0,

and ∫ f^{2}(x)μ( dx) ≤ σ^{2} with some number 0 ≤ σ^{2} ≤ 1 for all f ∈ F. Define the nor-

malized random sums S_{n}(f) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f(ξ_{j}) for all f ∈ F. There are some universal

constants C_{j} > 0, 1 ≤ j ≤ 5, (such that also the inequality C_{2} < 1 holds), for which the inequality

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ C_{1}e^{−C_{2}\sqrt{n}v log(v/\sqrt{n}σ^{2})} for all v ≥ u(σ)  (1.2)

holds if one of the following conditions is satisfied.

(a) σ^{2} ≤ \frac{1}{n^{400}} , and u(σ) = \frac{C_{3}}{\sqrt{n}}(L + \frac{log D}{log n}),

(b) \frac{1}{n^{400}} < σ^{2} ≤ \frac{log n}{8n}, and u(σ) = \frac{C_{4}}{\sqrt{n}} (L_{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} + log D),

(c) \frac{log n}{8n} < σ^{2} ≤ 1, and u(σ) = \frac{C_{5}}{\sqrt{n}}(nσ^{2} + L log n + log D).

I complete the result of Theorem 1 with an extension which almost agrees with

Theorem 4.1 in [5]. It yields an estimate for P (sup_{f∈F} |S_{n}(f)| ≥ v) in cases not covered

in Theorem 1. In case (c) it enlarges the set of levels v for which a good estimate can be given for the probability at the left-hand side of (1.2). I discuss this result to give a more complete solution of the problem discussed in Theorem 1. Besides, it may be interesting to understand what kind of tools are applied in its proof.

Extension of Theorem 1. Let us consider, similarly to Theorem 1, a sequence of independent, identically distributed random variables ξ_{1}, …, ξ_{n}, n ≥ 2, with values in a measurable space (X, X) with some distribution μ together with a countable class of functions F on the same space (X, X), which has polynomially increasing covering numbers with parameter D ≥ 1 and exponent L ≥ 1, and such that sup_{x∈X} |f(x)| ≤ 1,

∫ f(x)μ( dx) = 0, and ∫ f^{2}(x)μ( dx) ≤ σ^{2} with some number 0 ≤ σ^{2} ≤ 1 for all f ∈ F. The supremum of the normalized sums S_{n}(f), f ∈ F, introduced in Theorem 1 satisfies the inequality

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ C exp \{−α\frac{v^{2}}{σ^{2}} \}  (1.3)

with appropriate (universal) constants α > 0, C > 0 and C_{6} > 0 if \frac{log n}{8n} < σ^{2} ≤ 1, and \sqrt{n}σ^{2} ≥ v ≥ ū(σ), where ū(σ) is defined as

ū(σ) = C_{6}σ (L^{3/4} log^{1/2} \frac{2}{σ} + (log D)^{1/2}) .

The value \frac{log n}{8n} determining the boundary between cases (b) and (c) in Theorem 1 could be replaced by α\frac{log n}{n} with an arbitrary number 0 < α < 1. To see this one has to check that the formula defining u(σ) in cases (b) and (c) give a value of the same order if σ^{2} ∼ α\frac{log n}{n} with 0 < α < 1. I chose the parameter α = \frac{1}{8} because some calculations were simpler with such a choice. Let me remark that a similar statement holds for the value of boundary n^{−200} between cases (a) and (b). This could have been replaced by n^{−β} with any β > 1.

In Section 2 I try to explain why the above results are natural. I present an example which shows that Theorem 1 and its Extension are sharp. There are models satisfying the conditions of these results for which these results would not hold any longer if we replaced the functions u(σ) = u(σ, n) or ū(σ) by a much smaller function. More explicitly, they would become invalid if we replaced the function u(σ, n) by a function v(σ, n) such that lim_{n→∞} \frac{v(n,σ)}{u(n,σ)} = 0, or ū(σ) by a function v̄(σ) such that lim_{σ→0} \frac{v̄(σ)}{ū(σ)} = 0.

(Because of the condition ū(σ) ≤ v ≤ \sqrt{n}σ^{2} in the Extension of Theorem 1 the value of ū(σ) for small values σ is interesting only in the case of large sample size n.) In Section 3 I present the proof of Theorem 1 and its Extension. In Section 4 I discuss the content of these results in more detail. I explain the main problems and ideas behind them, and I also make a comparison with the results of earlier works.

2. Discussion on the conditions of these results.

We defined with the help of a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n} on a measurable space (X, X) and a class of functions F with polynomially increasing covering numbers on the same space (X, X) the random sums S_{n}(f) for all f ∈ F, and wanted

to give a good estimate on the tail distribution P_{n}(v) = P (sup_{f∈F} |S_{n}(f)| > v) of the

supremum of these random sums at all levels v > 0 if the conditions sup_{x∈X} |f(x)| ≤ 1,

Ef(ξ_{1}) = 0 and Ef^{2}(ξ_{1}) ≤ σ^{2} hold with some number 0 ≤ σ ≤ 1 for all functions f ∈ F. In particular, we were interested in the dependence of this estimate on the number σ. In this section I discuss the sharpness of our results, and present an example that indicates that the estimates given in Theorem 1 and in its Extension are sharp.

Although I gave an estimate for the supremum of a class of random sums defined with the help of a class of functions F which has polynomially increasing covering numbers with arbitrary exponent L and parameter D, I was mainly interested in the special case when these parameters L and D are bounded, more precisely when they have a bound not depending on the parameter σ. In this case the functions u(σ) and ū(σ) in Theorem 1 and in its Extension have a simpler form. Namely, we can choose u(σ) = \frac{C_{3}}{\sqrt{n}} in case (a), u(σ) = \frac{C_{4}}{\sqrt{n}} _{\frac{log n}{log \frac{log n}{nσ^{2}}}} in case (b), u(σ) = C_{5}\sqrt{n}σ^{2} in case (c), and

ū(σ) = C_{6}σ log^{1/2} \frac{2}{σ}. In this section I present an example that indicates that our results are sharp in this case. I shall call the estimates in these results sharp, because only the value of the universal constants appearing in them can be improved. I do not try to find the optimal value of these constants, but I want to present such an example where these estimates cannot be improved in any other respect. In particular, I shall show that the estimates in this example do not hold any longer if we replace the coefficients C_{j} in the definition of the quantities u(σ) and ū(σ) with very small positive constant, because after such a replacement the probabilities P_{n}(v) would be very close to one at level v = u(σ) or v = ū(σ) at large sample size n. I shall consider the following example.

Example. Take a sequence of independent, uniformly distributed random variables ξ_{1}, …, ξ_{n} on the unit interval [0, 1], fix a number 0 ≤ σ^{2} ≤ 1, and define a class of functions F_{σ} and F̄_{σ} with functions defined on the unit interval [0, 1] in the following way. F_{σ} = \{f_{1}, …, f_{k}\}, and F̄ = \{f̄_{1}, …, f̄_{k}\} with k = k(σ) = [\frac{1}{σ^{2}} ], where [·] denotes integer part, and f̄_{j}(x) = f̄_{j}(x|σ) = 1 if x ∈ [(j − 1)σ^{2}, jσ^{2}), f̄_{j}(x) = f̄_{j}(x|σ) = 0 if x ∉ [(j − 1)σ^{2}, jσ^{2}), 1 ≤ j ≤ k, and f_{j}(x) = f_{j}(x|σ) = f̄_{j}(x) − σ^{2}, 1 ≤ j ≤ n.

It can be seen that F_{σ} satisfies the conditions of Theorem 1 with Ef(ξ_{j}) ≤ σ^{2} for all f ∈ F_{σ}. In particular, it has polynomially increasing covering numbers with such a parameter D and exponent L that can be bounded by numbers not depending on σ^{2}. This can be seen directly, but it is also a consequence of some classical results by which the indicator functions of a Vapnik–Červonenkis class of sets constitute a class of functions with polynomially increasing covering numbers. (See e.g. Theorem 5.2 in [5]). I shall show that the sequence of random variables ξ_{1}, …, ξ_{n} and class of functions F in the above example have the following property.

An estimate on the function P_{n}(v) in the models of the above Example. A number C̄ > 0 can be chosen in such a way that for all δ > 0 there is an index n_{0}(δ) such that for all sample sizes n ≥ n_{0}(δ) and numbers 0 ≤ σ ≤ 1 the inequality

P_{n}(û(σ)) = P ( sup_{f∈F_{σ}} |S_{n}(f)| ≥ û(σ)) ≥ 1 − δ,  (2.1)

holds with û(σ) = \frac{C̄}{\sqrt{n}} in case (a), i.e. if σ^{2} ≤ n^{−400}, û(σ) = \frac{C̄}{\sqrt{n}} _{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} in case (b),

i.e. if n^{−400} < σ^{2} ≤ \frac{log n}{8n}, and û(σ) = C̄σ log^{1/2} \frac{2}{σ} in case (c) i.e. if \frac{log n}{8n} ≤ σ^{2} ≤ 1.

In Theorem 1 and in its Extension we gave a good estimate for P_{n}(v) if v ≥ u(σ) in cases (a) and (b), and v ≥ ū(σ) in case (c), while in formula (2.1) I claimed that there are such models satisfying the conditions of these results for which no good estimate holds for P_{n}(û(σ)), if we define the function û(σ) by replacing the coefficients C_{j} by a sufficiently small constant C̄ in their definition. Let me recall that here we restricted our attention to the case when the exponent L and parameter D of the polynomially increasing covering numbers of the class of functions F_{σ} we considered are bounded by a constant not depending on the parameter σ. Actually, in the case (c) we have to explain the estimate on P_{n}(v) in more detail. In this case we have to compare the estimates given by Theorem 1 and its Extension.

It may happen that \sqrt{n}σ^{2} ≥ ū(σ), and in this case the estimate (1.3) of the Extension of Theorem 1 is an empty statement. I claim that in this case we can replace the condition v ≥ u(σ) by the condition v ≥ ū(σ) in case (c) of Theorem 1 with an appropriate constant C_{6} in the definition of ū(σ), and Theorem 1 remains valid after such a modification. To show this it is enough to check that u(σ) and ū(σ) have the same order of magnitude in this case, i.e. there are universal constants C′ > 0 and C′′ > 0 such that C′ū(σ) ≤ u(σ) ≤ C′′ū(σ).

We have ū(σ) ≤ \sqrt{n}σ^{2} = \frac{1}{C_{5}} u(σ) in this case, which implies the first inequality. On the other hand, σ^{2} ≥ \frac{log n}{8n} in case (c), hence as some calculation shows ū(σ) = C_{6}σ log^{1/2} \frac{2}{σ} ≥ const. \sqrt{n}σ^{2}. This implies the second inequality.

If \sqrt{n}σ^{2} ≥ ū(σ), and the estimate (1.3) is not an empty statement, then we can give a good estimate for P_{n}(v) for all v ≥ ū(σ), i.e. also if u(σ) ≥ v ≥ \sqrt{n}σ^{2}, in a case which was covered neither in Theorem 1 nor in its Extension. In this case we have C_{6}\sqrt{n}σ^{2} ≥ v, and we can write the following inequality by means of relation (1.3) with the choice v = \sqrt{n}σ^{2}.

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ P (sup_{f∈F} |S_{n}(f)| ≥ \sqrt{n}σ^{2}) ≤ Ce^{−αnσ^{2}} ≤ Ce^{−ᾱv^{2}/σ^{2}},

with some ᾱ > 0, i.e. relation (1.3) holds (with a possible different parameter ᾱ > 0) for all u(σ) ≥ v ≥ ū(σ).

To understand the content of Theorem 1 and its Extension together with the estimate on the function P_{n}(v) in the models of the Example formulated above it may be useful to recall a result called the concentration inequality for the supremum of sums of i.i.d. random variables. (See e.g. [11]). It states that there is a concentration point of the tail distribution of the supremum of sums of i.i.d. random variables. This concentration point has the property that the supremum is strongly concentrated in a small neighbourhood of it. I do not formulate this result in a more precise and detailed form, because we need it here only for the sake of some orientation. The problem with its application is that this result determines the concentration point only in an implicit way, as the expected value of the supremum we are investigating, and we cannot calculate it explicitly in the general case. On the other hand, the concentration inequality implies that we can get a good, non-trivial estimate for the tail distribution of the supremum of sums of i.i.d. random variables only at levels higher than their concentration point. (Otherwise we cannot give a better estimate for the tail distribution than the trivial upper bound 1.) The number u(σ) defined in Theorem 1 is an upper bound for the concentration point in cases (a) and (b), while the number ū(σ) defined the Extension of Theorem 1 is an upper bound for it in the case (c). On the other hand, the number û(σ) introduced in formula (2.1) is a lower bound for the concentration point in the models introduced in the Example. So in this case we have determined the concentration point up to a (universal) multiplying constant.

Thus the functions u(σ) and ū(σ) can be considered as good upper bounds on the concentration point of the supremum of the random sums S_{n}(f), f ∈ F, if the conditions of Theorem 1 and its Extension are satisfied. In formulas (1.2) and (1.3) we also gave an estimate on the function P_{n}(v), i.e. on the tail distribution of the supremum we are investigating for v ≥ u(σ) or v ≥ ū(σ). We can say that this estimate is also sharp, we cannot get a better bound (if we disregard the value of the universal constants C_{1}, C_{2}) in formula (1.2) and C and α in formula (1.3) even if we took a single normalized sum S_{n}(f) whose terms f(ξ_{j}) have variance Ef(ξ_{j})^{2} = σ^{2}.

Indeed, if we disregard the value of the universal constants appearing in our estimates, then we can say that formula (1.2) yields such an estimate for the tail distribution P_{n}(v) as Bennett’s inequality yields for the tail distribution of a single term S_{n}(f) if the terms in this normalized sum have variance σ^{2}. At least this is the case if we consider the estimate of Bennett’s inequality at level v ≥ 2\sqrt{n}σ^{2}. (This follows e.g. from formula (3.3) in this paper. Here we recalled Bennett’s inequality, and formula (3.3) is a part of it.) On the other hand, we considered in Theorem 1 only such levels v where this condition is satisfied, since u(σ) ≥ 2\sqrt{n}σ in all cases of Theorem 1. Moreover, there are examples that show that inequality (3.3) is sharp, we cannot get a better estimate without some additional restrictions. (See Example 3.3 in [5]). In inequality (1.3) we gave a Gaussian type upper bound, and this is also a sharp estimate if we disregard the value of the absolute constants in it.

To complete this section we still have to show that the model introduced in the Example satisfies formula (2.1). This will be done in the following proof.

The proof of the estimate on the function P_{n}(v) formulated about the models in the Example of this Section. In the proof of relation (2.1) we introduce the following notation. Define the empirical distribution function F_{n}(x) of the random variables ξ_{1}, …, ξ_{n}, i.e. put

F_{n}(x) = \frac{1}{n}\{the number of indices j, 1 ≤ j ≤ n, such that ξ_{j} < x\}

for all 0 < x ≤ 1, and take its normalization G_{n}(x) = \sqrt{n}(F_{n}(x) − x), 0 < x ≤ 1. Observe that

{ sup_{f∈F_{σ}} |S_{n}(f)| ≥ û(σ)} = { max_{1≤j≤k(σ)} |G_{n}(jσ^{2}) − G_{n}((j − 1)σ^{2})| ≥ û(σ)} . (2.2)

By a classical results of probability theory, the normalized empirical distribution functions converge weakly to the Brownian bridge as n → ∞. In our next considerations it will be also interesting that the modulus of continuity of a Brownian bridge, (which actually agrees with the modulus of continuity of a Wiener process) can be also calculated, (see e.g. [8]). By a similar, but simpler calculation we can estimate the probability of the event we get by replacing the normalized empirical distribution function G_{n}(·) by a Brownian bridge in the right-hand side expression of (2.2). This is actually done with the choice û(σ) = C̄σ log^{1/2} \frac{2}{σ} in the fourth chapter of [5] (page 27), and it is shown that this probability is almost one for large parameters n for all σ > 0 if the coefficient C̄ of û(σ) is chosen sufficiently small. (Actually we have to choose C̄ < \sqrt{2}.) Let us call this estimate the Gaussian version of formula (2.1). At a heuristic level this result together with formula (2.2) and the weak convergence of the normalized empirical processes G_{n}(·) to a Brownian bridge suggests that formula (2.1) should hold with û(σ) = C̄σ log^{1/2} \frac{2}{σ} and a small coefficient C̄ > 0.

This heuristic argument is nevertheless misleading, since the weak convergence of the empirical processes G_{n}(·) to the Brownian bridge in itself does not allow to carry out a limiting procedure that leads to formula (2.1). On the other hand, a stronger version of the weak convergence of the normalized empirical processes (see [4]) yields a useful result in this direction. This result states that a normalized empirical process G_{n}(x) and a Brownian bridge B(x), 0 ≤ x ≤ 1, can be constructed in such a way that sup_{0≤x≤1} |B(x)−G_{n}(x)| ≤ K \frac{log n}{\sqrt{n}} for all n ≥ 2 and sufficiently large K > 0 with probability

almost 1. This result together with the Gaussian version of formula (2.1) imply the validity of formula (2.1) if σ^{2} ≥ B \frac{log n}{2n} with a sufficiently large B > 0. Indeed, in this case û(σ) ≥ 2K \frac{log n}{\sqrt{n}}, hence the Gaussian version of formula of (2.1) together with the result of [4] imply that

P ( max_{1≤j≤k(σ)} |G_{n}(jσ^{2}) − G_{n}((j − 1)σ^{2})| ≥ \frac{û(σ)}{2}) ≥ 1 − δ

if σ^{2} ≥ B \frac{log n}{n}, and n ≥ n_{0}(δ), hence inequality (2.1) holds in this case if we choose C̄ > 0 sufficiently small in the definition of û(σ). Moreover, this relation also holds for all σ^{2} ≥ \frac{log n}{8n}, i.e. in the case (c) if we choose û(σ) = C̄σ log^{1/2} \frac{2}{σ} with a sufficiently small Ĉ > 0. To see this it is enough to observe that if max_{1≤j≤k(σ)} |G_{n}(jσ^{2})−G_{n}((j−1)σ^{2})| ≤ û(σ), then

for any positive integers A we have max_{1≤j≤k(\sqrt{A}σ)} |G_{n}(j(Aσ))−G_{n}((j −1)(Aσ))| ≤ Aû(σ),

and that the corresponding result holds if σ^{2} ≥ B \frac{log n}{8n}.

In cases (a) and (b) the above Gaussian approximation argument does not work. Moreover, inequality (2.1) holds only with a different function û(σ) in these cases. In case (b) we shall prove formula (2.1) by means of a Poissonian approximation method described below. It can be considered as a more detailed elaboration of the argument in Example 4.3 of [5].

In this argument first we consider the following problem. Take a Poisson process Z_{n}(t), 0 ≤ t ≤ 1, with parameter n, (i.e. let EZ_{n}(t) = nt for all 0 ≤ t ≤ 1) in the interval [0, 1]. Fix some number 0 ≤ σ^{2} ≤ \frac{1}{7} \frac{log n}{n}, and define with its help the number û(σ) = û(σ, n) = \frac{3}{4\sqrt{n}} _{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} and the random variables V̄_{j} = V̄_{j}^{(n)}(σ) = Z_{n}(jσ^{2})−Z_{n}((j−1)σ^{2})

for 1 ≤ j ≤ k with k = k(σ) = [\frac{1}{σ^{2}} ]. (Here we defined û(σ) similarly to the quantity introduced with the same notation at the formulation of inequality (2.1) in the case (b). We only made small modifications. Namely, we considered σ^{2} in the interval [0, \frac{log n}{7n}] instead of the interval [\frac{1}{n^{200}} , \frac{log n}{8n}], and we fixed the value C̄ = \frac{3}{4} in the definition of û(σ).) We shall show that for all δ > 0 there is some threshold index n_{0}(δ) such that the inequality

P ( max_{1≤j≤k(σ)} V̄_{j}^{(n)}(σ) ≥ \sqrt{n}û(σ, n)) ≥ 1 − δ if n ≥ n_{0}(δ)  (2.3)

holds for all 0 ≤ σ^{2} ≤ \frac{1}{7} \frac{log n}{n}.

To prove this inequality let us first observe that

P ( max_{1≤j≤k(σ)} V̄_{j}^{(n)}(σ) ≥ \sqrt{n}û(σ, n)) ≥ P (V̄_{j}^{(n)}(σ) = \sqrt{n}û(σ, n) for some 1 ≤ j ≤ k)
= 1 − P (V̄_{1}^{(n)}(σ) ≠ \sqrt{n}û(σ, n))^{k},

and

P (V̄_{1}^{(n)}(σ) ≠ \sqrt{n}û(σ, n)) = 1 − P (V̄_{1}^{(n)}(σ) = \sqrt{n}û(σ, n))

= 1 − \frac{(nσ^{2})^{\sqrt{n}û(σ,n)}}{(\sqrt{n}û(σ, n))!} e^{−nσ^{2}} ≤ 1 − (\frac{nσ^{2}}{\sqrt{n}û(σ, n)})^{\sqrt{n}û(n,σ)} e^{−nσ^{2}}.

Since we have k = [\frac{1}{σ^{2}} ] we can bound the left-hand side of (2.3) from below as

P ( max_{1≤j≤k(σ)} V̄_{j}^{(n)}(σ)\sqrt{n}û(σ, n))

≥ 1 − [1 − (\frac{nσ^{2}}{\sqrt{n}û(σ, n)})^{\sqrt{n}û(n,σ)} e^{−nσ^{2}}]^{1/σ^{2}} ≥ 1 − e^{−T}

with T = \frac{1}{σ^{2}} (\frac{nσ^{2}}{\sqrt{n}û(σ,n)})^{\sqrt{n}û(n,σ)} e^{−nσ^{2}}. Hence to prove (2.3) it is enough to show that

(\frac{nσ^{2}}{\sqrt{n}û(σ, n)})^{\sqrt{n}û(n,σ)} ≥ σ^{2}e^{nσ^{2}} log \frac{1}{δ} if n ≥ n_{0}(δ).  (2.4))

The right-hand side of (2.4) can be bounded from above as

σ^{2}e^{nσ^{2}} log \frac{1}{δ} = \frac{log \frac{1}{δ}}{n} (nσ^{2})e^{nσ^{2}} ≤ \frac{log \frac{1}{δ}}{n} (\frac{1}{7} log n) e^{(log n)/7} ≤ n^{−5/6}

if n ≥ n_{0}(δ), since nσ^{2} ≤ \frac{1}{7} log n, and log \frac{1}{δ} ≤ n^{1/100} for n ≥ n_{0}(δ). Hence we prove (2.4) if we show that

\frac{\sqrt{n}û(n, σ)}{nσ^{2}} log (\frac{\sqrt{n}û(σ, n)}{nσ^{2}}) ≤ \frac{5}{6} \frac{log n}{nσ^{2}}.

By applying the definition of û(n, σ) and introducing the quantity z = \frac{3}{4} \frac{log n}{nσ^{2}} we can rewrite the last inequality as \frac{z}{log( \frac{4z}{3} )} log(\frac{z}{log( \frac{4z}{3} )}) ≤ \frac{10}{9}z, or since z ≥ \frac{21}{4} in the case we

are investigating it can be rewritten as \frac{1}{9} log \frac{4z}{3} ≥ − log log \frac{4z}{3} − log \frac{4}{3} if z ≥ \frac{21}{4}, and this relation clearly holds. Thus we proved (2.3).

We shall prove relation (2.1) in the case (b) by means of formula (2.3) for a Poisson process with parameter \frac{99}{100}n instead of n and a simple coupling argument between an empirical process and a Poisson process. Namely, we make the following coupling. Let us consider a sequence of independent random variables ξ_{1}, ξ_{2} … with uniform distribution on the unit interval [0, 1] together with a Poissonian random variable η = η_{n} with parameter \frac{99}{100}n independent of the random variables ξ_{j}, j = 1, 2, …, and take the first η_{n} terms of the random variables ξ_{j}, i.e. the sequence ξ_{1}, ξ_{2}, …, ξ_{η_{n}} with the random stopping index η_{n}. In such a way we constructed a Poisson process with parameter \frac{99}{100}n, which is smaller than the (non-normalized) empirical distribution of the sequence ξ_{1}, …, ξ_{n} in the following sense. For large parameter n with probability almost 1 all intervals [a, b] ⊂ [0, 1] contain more points from the sequence ξ_{1}, …, ξ_{n} than from the above constructed Poisson process. This is a simple consequence of the fact that P (η_{n} > n) → 0 as n → ∞.

The above coupling construction and formula (2.3) (with a Poisson process with parameter \frac{99}{100}) imply that

P ( sup_{f̄∈F̄_{σ}} \sqrt{n}S_{n}(f̄) ≥ \sqrt{\frac{99}{100}n}û (σ, \frac{99}{100}n)) ≥ 1 − δ if n ≥ n_{0}(δ)

with the class of functions F̄_{σ} introduced before the formulation (2.1) and the function û(σ, n) defined in the estimate about the models of the Example in case (b). To complete the proof of (2.1) in the case (b) it is enough to check that the above relation remains valid if the class of functions F̄_{σ} is replaced by the class of functions F_{σ} and the term \sqrt{\frac{99}{100}n}û(σ, \frac{99}{100}n) is replaced by û(σ, n) = \frac{C̄}{\sqrt{n}} _{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} with some appropriate C̄ > 0.

Since the functions f ∈ F are of the form f(x) = f̄(x)−σ^{2} with some f̄ ∈ F, the identity \sqrt{n}S_{n}(f) = \sqrt{n}S_{n}(f̄)−nσ^{2} holds, and to prove the desired relation it is enough to check that

\sqrt{\frac{99}{100}} \frac{3}{4} \frac{log n}{log( \frac{log n}{\frac{99}{100} nσ^{2}} )} − nσ^{2} ≥ \sqrt{\frac{99}{100}} \frac{3}{4} \frac{log n}{log(\frac{log n}{nσ^{2}})} − nσ^{2} ≥ C̄ \frac{log n}{log(\frac{log n}{nσ^{2}})}

with some appropriate C̄ > 0 if 8nσ^{2} ≤ log n. The first inequality clearly holds, and the second inequality is equivalent to the relation

\sqrt{\frac{99}{100}} \frac{3}{4} \frac{\frac{log n}{nσ^{2}}}{log(\frac{log n}{nσ^{2}})} ≥ α

with some α > 1. But this relation clearly holds if 8nσ^{2} ≤ log n. Thus we have proved (2.1) also in case (b).

In the case (a) the proof of (2.1) is very simple. It is enough to observe that the sample points ξ_{j} fall into one of the intervals [(j−1)σ^{2}, jσ^{2}), 1 ≤ j ≤ k, (we disregard the event that they fall into the last interval [kσ^{2}, 1) which has negligibly small probability), hence

P ( sup_{f̄∈F̄_{σ}} \sqrt{n}S_{n}(f̄) ≥ 1) ≥ 1 − δ if n ≥ n_{0}(δ),

and since σ^{2} is very small for large n relation (2.1) holds in case (a) with C̄ = 1 − ε for any ε > 0.

I finish this section with some remarks on the paper [2], about whose existence I learned only after finishing this work. Theorem 4 in Section 2 of that paper contains an almost sure limit theorem on the appropriately normalized supremum of the increase of the empirical distribution functions F_{n}, n = 1, 2, …, of a sequence of i.i.d. random variables in small intervals if these i.i.d. random variables are uniformly distributed in the interval [0, 1]. Here we take the supremum of F_{n} for all subintervals of [0, 1] whose length is smaller than a prescribed number a_{n}. Actually paper [2] contains a more general result, but its application about the growth of the empirical distribution functions in small intervals seems to be its most interesting application. I do not give a precise formulation of Theorem 4 in [2], I omit its rather technical conditions. In particular, I do not describe what kind of conditions the number a_{n} must satisfy in this theorem. I only want to make some comments about its relation to the result about the model in our Example.

If we look carefully at the result of [2], then we can understand that it gives an improved version of the statement about the properties of the model discussed in the Example of this section in case (b). It enables us to define such a function û(σ) in this case for which even the relation

P ((1 − ε)û(σ) ≤ sup_{f∈F_{σ}} |S_{n}(f)| ≤ (1 + ε)û(σ)) → 1

holds for all ε > 0 if n → ∞, and σ = σ(n) satisfies the relation n^{−400} ≤ σ^{2} ≤ \frac{log n}{8n}. This means that in this case we can determine the value of the concentration point precisely and not only up to a multiplicative constant. Actually a precise explanation of this statement demands the elaboration of some technical details, but I omit this.

Finally I remark that our approach to the problem studied in this section is essentially different from that of [2]. In that paper the results are proved by means of some deep inequalities contained in earlier results, while here I tried to explain that they can be proved by means of a good Poissonian coupling. This may explain the situation better, and this approach seems to be appropriate also for the proof of the results in [2].

3. Proof of Theorem 1 and its extension.

Proof of Theorem 1. In the case (a) inequality (1.2) is a simple consequence of Theorem 1 in [6]. We can apply this result by writing σ instead of ρ in its formulation, since (∫ |f(x)|μ( dx))^{2} ≤ ∫ f^{2}(x)μ( dx) ≤ σ^{2} by the Cauchy–Schwarz inequality. Hence under the conditions of Theorem 1 the inequality ∫ |f(x)|μ( dx) ≤ ρ holds for all f ∈ F with ρ = σ, and by Theorem 1 of [6]

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ De^{− \frac{1}{25} \sqrt{n}v log(σ^{−2})} if v ≥ \frac{C̄}{\sqrt{n}}L and σ^{2} ≤ \frac{1}{n^{400}}  (3.1)

with an appropriate C̄ > 0. (Here we apply a division by \sqrt{n} in the definition of S_{n}(f), which was not done in [6], and this causes some difference in the formulas.)

I claim that we can drop the coefficient D at the right-hand side of (3.1) if we replace the coefficient \frac{1}{25} by \frac{1}{50} in the exponent, we choose such a constant C̄ in (3.1) for which C̄ ≥ \frac{1}{8}, and exploit that by condition (a) v ≥ u(σ) ≥ \frac{C̄}{\sqrt{n}}(L + \frac{log D}{log n}). To show

this it is enough to check that D ≤ e^{\sqrt{n}v log(σ^{−2})/50} in this case. This relation holds, since \frac{log D}{log n} ≤ 8\sqrt{n}v, and log(σ^{−2}) ≥ 400 log n, thus D = exp\{\frac{1}{400}(\frac{log D}{log n})(400 log n)\} ≤ exp\{\frac{1}{50} \sqrt{n}v log(σ^{−2})\}, as I claimed.

Next I show that formula (3.1) or its previous modification remains valid if we replace log(σ^{−2}) by log(\frac{v}{\sqrt{n}σ^{2}} ) in the exponent of its right-hand side. In the proof of this statement we can restrict our attention to the case v ≤ \sqrt{n}, since otherwise the probability at the left-hand side of (3.1) equals zero. In this case the inequality σ^{−2} ≥ \frac{v}{\sqrt{n}σ^{2}} holds, and this allows the above replacement. The above modifications of formula (3.1) imply inequality (1.2) in case (a).

Remark. If we are not interested in the value of the (universal) constants in (1.2), then in the case (a) this inequality has the same strength if we replace the term log(v/\sqrt{n}σ^{2}) by log(σ^{−2}) in it. To see this, observe that beside the inequality σ^{−2} ≥ \frac{v}{\sqrt{n}σ^{2}} (if v ≤ \sqrt{n}), the inequality \frac{v}{\sqrt{n}σ^{2}} ≥ \frac{1}{nσ^{2}} ≥ σ^{−2+1/200} also holds in case (a) because of the inequalities v ≥ u(σ) ≥ n^{−1/2} and n^{−200} ≥ σ^{2}. The original form of (1.2) has the advantage that it simultaneously holds in all cases (a), (b) and (c).

The proof of Theorem 1 in cases (b) and (c). We exploit that the class of functions F satisfies (1.1). We use this relation with the choice ε = n^{−400} and the measure μ instead of sup_{ν}. We may find in such a way m ≤ Dn^{400L} functions f_{j} ∈ F, 1 ≤ j ≤ m, such that

min_{1≤j≤m} ∫ |f_{j}(x) − f(x)|μ( dx) ≤ n^{−400} for all f ∈ F. This means that F = ⋃_{j=1}^{n} D_{j} with

D_{j} = {f: f ∈ F, ∫ |f_{j}(x) − f(x)|μ( dx) ≤ n^{−400}} ,

and as a consequence

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ ∑_{j=1}^{m} P (|S_{n}(f_{j})| ≥ \frac{v}{2} ) + ∑_{j=1}^{m} P ( sup_{f∈D_{j}} |S_{n}(f − f_{j})| ≥ \frac{v}{2} ) (3.2)

for all v > 0. We shall estimate both terms at the right-hand side of (3.2) if v ≥ u(σ), the first term by means of Bennett’s inequality, more precisely by a consequence of it formulated below, and the second term by means of the already proved case (a) of Theorem 1. We shall apply the following version of Bennett’s inequality, see [5].

Bennett’s inequality. Let X_{1}, …, X_{n} be independent and identically distributed random variables such that P (|X_{1}| ≤ 1) = 1, EX_{1} = 0 and EX_{1}^{2} ≤ σ^{2} with some 0 ≤ σ ≤ 1.

Put S_{n} = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} X_{j}. Then

P (S_{n} > v) ≤ exp \{−nσ^{2} [(1 + \frac{v}{\sqrt{n}σ^{2}} ) log (1 + \frac{v}{\sqrt{n}σ^{2}} ) − \frac{v}{\sqrt{n}σ^{2}} ]\}

for all v > 0. As a consequence, for all ε > 0 there exists some B = B(ε) > 0 such that

P (S_{n} > v) ≤ exp \{−(1 − ε)\sqrt{n}v log \frac{v}{\sqrt{n}σ^{2}} \} if v > B\sqrt{n}σ^{2},

and there exists some positive constant K > 0 such that

P (S_{n} > v) ≤ exp \{−K\sqrt{n}v log \frac{v}{\sqrt{n}σ^{2}} \} if v > 2\sqrt{n}σ^{2}.  (3.3)

The above result is a special case of Theorem 3.2 in [5] in the case when we restrict our attention to sums of independent and identically distributed random variables. It has a slightly different form, because in the definition of S_{n} we considered normalized sums (with a multiplication by n^{−1/2}). Here we need only the inequality formulated in (3.3) which helps to estimate the probabilities appearing in the first sum at the right-hand side of (3.2). To apply (3.3) in the estimation of these terms we have to show that if the constants C_{4} and C_{5} are chosen sufficiently large in Theorem 1, then u(σ) > 2\sqrt{n}σ^{2} in cases (b) and (c).

In case (b) it is enough to show that \sqrt{n}u(σ) ≥ C_{4}_{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} ≥ 2nσ^{2}, and even

C_{4}_{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} ≥ 20nσ^{2}, or in an equivalent form \frac{C_{4}}{20} \frac{log n}{nσ^{2}} ≥ log(\frac{log n}{nσ^{2}}). (Observe that

\frac{log n}{nσ^{2}} ≥ 8, hence log(\frac{log n}{nσ^{2}}) > 0 in case (b).) This statement holds, since z = \frac{log n}{nσ^{2}} ≥ 8 in case (b), and \frac{C_{4}}{20} z ≥ log z if z ≥ 8, and C_{4} is sufficiently large.

In case (c), clearly u(σ) ≥ \frac{C_{5}}{\sqrt{n}}nσ^{2} ≥ 20\sqrt{n}σ^{2} for sufficiently large constant C_{5}. These relations together with formula (3.3) imply that in cases (b) and (c)

P (|S_{n}(f_{j})| ≥ \frac{v}{2} ) ≤ 2 exp \{−K\sqrt{n}v log \frac{v}{\sqrt{n}σ^{2}} \} if v ≥ u(σ)  (3.4)

with an appropriate K > 0 for all 1 ≤ j ≤ m. (In formula (3.4) we have exploited that log(\frac{\frac{v}{2}}{\sqrt{n}σ^{2}} ) ≥ \frac{1}{2} log(\frac{v}{\sqrt{n}σ^{2}} ) since \frac{v}{\sqrt{n}σ^{2}} ≥ 20, and as a consequence log(\frac{v}{\sqrt{n}σ^{2}} ) ≥ 2 log 2.)

Let us define, with the help of the class of functions D_{j} the class of functions D′_{j} = \{h: h = \frac{f−f_{j}}{2} , f ∈ D_{j}\} for all 1 ≤ j ≤ m. It is not difficult to see that

sup_{x∈X} |h(x)| ≤ 1, ∫ h^{2}(x)μ( dx) ≤ ∫ |h(x)|μ( dx) ≤ n^{−400} for all h ∈ D′_{j}, and D′_{j} is a class

of functions which has polynomially increasing covering numbers with parameter D and exponent L, 1 ≤ j ≤ m. I claim that

P ( sup_{f∈D_{j}} |S_{n}(f − f_{j})| ≥ \frac{v}{2} ) = P ( sup_{h∈D′_{j}} |S_{n}(h_{j})| ≥ \frac{v}{4} )
≤ e^{−C_{2}\sqrt{n}v log(vn^{195})} if v ≥ u(σ)  (3.5)

for all 1 ≤ j ≤ n in both cases (b) and (c). We shall get this estimate by applying Theorem 1 in the already proved case (a) with the choice of parameter σ^{2} = n^{−400}. To apply this result we have to check that \frac{v}{4} ≥ \frac{u(σ)}{4} ≥ u(n^{−200}) = \frac{C_{3}}{\sqrt{n}}(L + \frac{log D}{log n}) if the constants C_{4} and C_{5} are sufficiently large. These statements hold, since in case (b) \frac{log n}{log \frac{log n}{nσ^{2}}} ≥ \frac{log n}{log(n^{399} log n)} ≥ \frac{1}{400}, hence u(σ) ≥ \frac{C_{4}}{\sqrt{n}}(\frac{L}{200} + log D) ≥ 4u(n^{−200}) if C_{4} is

chosen sufficiently large, and an analogous but simpler argument supplies this relation in case (c) if C_{5} is chosen sufficiently large.

It is not difficult to see that the right-hand side both of (3.4) and (3.5) can be bounded from above by C_{1}e^{−C̄_{2}\sqrt{n}v log(v/\sqrt{n}σ^{2})} with some appropriate constants C_{1} > 0 and C̄_{2} > 0. Hence relations (3.2), (3.4) and (3.5) together with the inequality m ≤ Dn^{400L} imply that

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ C_{1}Dn^{400L}e^{−C̄_{2}\sqrt{n}v log(v/\sqrt{n}σ^{2})} if v ≥ u(σ)  (3.6)

in both cases (b) and (c). Hence to complete the proof of Theorem 1 (with the choice C_{2} = \frac{C̄_{2}}{2} ) it is enough to show that

e^{− \frac{C̄_{2}}{2} \sqrt{n}v log(v/\sqrt{n}σ^{2})} ≤ e^{− \frac{C̄_{2}}{2} \sqrt{n}u(σ) log(u(σ)/\sqrt{n}σ^{2})} ≤ D^{−1}n^{−400L} if v ≥ u(σ) (3.7)

in cases (b) and (c) if the constants C_{4} and C_{5} are chosen sufficiently large.

It is enough to prove the second inequality in formula (3.7), since its proof also implies that the expressions in the exponent of this formula have negative value, and they are decreasing functions for v ≥ u(σ). The second inequality in (3.7) clearly holds in case (c), since \frac{C̄_{2}}{2} \sqrt{n}u(σ) ≥ 400L log n+log D, and log \frac{u(σ)}{\sqrt{n}σ^{2}} ≥ 1 in this case. In case (b)

relation (3.7) can be reduced to the inequalities C̄_{2}\sqrt{n}u(σ) log(\frac{u(σ)}{\sqrt{n}σ^{2}} ) ≥ 800L log n, and

C̄_{2}\sqrt{n}u(σ) log(\frac{\sqrt{n}(σ)}{nσ^{2}}) ≥ 4 log D. To prove the second inequality observe that in case (b)

C̄_{2}\sqrt{n}u(σ) ≥ C_{4}C̄_{2} log D ≥ 4 log D, and log (\frac{\sqrt{n}u(σ)}{nσ^{2}}) ≥ 1.

The second of these inequalities follows from the relation

\frac{\sqrt{n}u(σ)}{nσ^{2}} ≥ C_{4} \frac{\frac{log n}{nσ^{2}}}{log(\frac{log n}{nσ^{2}})} ≥ 3,

which holds because of the relation \frac{log n}{nσ^{2}} ≥ 8 in case (b).

The remaining inequality can be rewritten as C̄_{2} \frac{\sqrt{n}u(σ)}{nσ^{2}} log(\frac{\sqrt{n}u(σ)}{nσ^{2}}) ≥ 800L\frac{log n}{nσ^{2}}. To prove it observe that because of the definition of the function u(σ) in case (b) we can write C̄_{2} \frac{\sqrt{n}u(σ)}{nσ^{2}} ≥ 1600L\frac{log n}{nσ^{2}} _{\frac{1}{log( \frac{log n}{nσ^{2}} )}}. I also claim that log(\frac{\sqrt{n}u(σ)}{nσ^{2}}) ≥ \frac{1}{2}(\frac{log n}{nσ^{2}}). By

multiplying the last two inequalities we get the desired inequality, and this completes the proof of Theorem 1.

To prove the above formulated inequality introduce the notation z = \frac{log n}{nσ^{2}} and û(σ) = \frac{1}{\sqrt{n}} _{\frac{log n}{log( \frac{log n}{nσ^{2}} )}}. By exploiting the definition of u(σ) in case (b) we can write

with the help of this notation that log(\frac{\sqrt{n}u(σ)}{nσ^{2}}) ≥ log(\frac{\sqrt{n}û(σ)}{nσ^{2}}) = log z − log log z ≥ \frac{1}{2} log z = \frac{1}{2}(\frac{log n}{nσ^{2}}). In this calculation we have exploited that in case (b) z ≥ 8, hence log z − log log z ≥ \frac{1}{2} log z. Theorem 1 is proved.

The extension of Theorem 1 is a slight generalization of Theorem 4.1 in [5], and its proof is based on the same ideas. The original proof in [5] is made by means of two results, formulated in Propositions 6.1 and 6.2 of that work. Here I present a slightly improved version of Proposition 6.2 in Theorem 3.1, which is, as I show, a simple consequence of Theorem 1. Then I formulate Theorem 3.2 which is a (simplified) version of Proposition 6.1 in [5]. I show that the Extension of Theorem 1 can be proved with the help of these results by slightly modifying (and simplifying) the proof of Theorem 4.1 in [5]. In Section 4 I shall discuss the role of Theorems 3.1 and 3.2 together with the idea behind them in more detail.

First I formulate Theorem 3.1.

Theorem 3.1. Let us have a probability measure μ on a measurable space (X, X) together with a sequence of independent and μ distributed random variables ξ_{1}, …, ξ_{n}, n ≥ 2, and a countable class F of functions f = f(x) on (X, X) which has polynomially increasing covering numbers with some parameter D ≥ 1 and exponent L ≥ 1. Let this class of functions F also satisfy the relations sup_{x∈X} |f(x)| ≤ 1, ∫ f(x)μ( dx) = 0 and

∫ f^{2}(x)μ( dx) ≤ σ^{2} for all f ∈ F with some 0 < σ ≤ 1 that satisfies the inequality nσ^{2} > L log n + log D. Then there exists a threshold index A_{0} such that the normalized random sums S_{n}(f), f ∈ F, introduced in Theorem 1 satisfy the inequality

P (sup_{f∈F} |S_{n}(f)| ≥ An^{1/2}σ^{2}) ≤ e^{−Anσ^{2}} if A ≥ A_{0}.  (3.8)

I show that the estimate (3.8) in Theorem 3.1 is a weakened version of formula (1.2) of Theorem 1. First I show that the probability at the left-hand side of (3.8) can be estimated by means of Theorem 1 in case (c) with the choice v = An^{1/2}σ^{2} if A ≥ A_{0} with a sufficiently large threshold index A_{0} > 0. We have to check that nσ^{2} ≥ \frac{1}{8} log n, and v ≥ u(σ) (with the function u(σ) defined in case (c) of Theorem 1) if A_{0} is chosen sufficiently large. These inequalities hold, since under the conditions of Theorem 3.1 nσ^{2} ≥ L log n ≥ \frac{1}{8} log n, and for v ≥ A_{0}n^{1/2}σ^{2} we can write v ≥ \frac{A_{0}}{\sqrt{n}}nσ^{2} ≥ \frac{A_{0}}{2\sqrt{n}}nσ^{2} + \frac{A_{0}}{2\sqrt{n}}(L log n + log D) ≥ \frac{C_{5}}{\sqrt{n}}(nσ^{2} + L log n + log D) = u(σ).

Thus we can apply formula (1.2) with v = An^{1/2}σ^{2} to estimate the left-hand side of (3.8), and we get the upper bound

C_{1}e^{−C_{2}\sqrt{n}v log(v/\sqrt{n}σ^{2})} = C_{1}e^{−C_{2}Anσ^{2} log A} ≤ e^{−Anσ^{2}}

for A ≥ A_{0} if the (universal) constant A_{0} is chosen sufficiently large. Thus we proved Theorem 3.1 which provides a slightly better estimate than Proposition 6.2 in [5].

In the proof of the Extension of Theorem 1 I shall also apply following Theorem 3.2 which is a simple modified version of Proposition 6.1 in [5].

Theorem 3.2. Let us have a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n}, n ≥ 2, on a measurable space (X, X) with some distribution μ and a class of functions F on the space (X, X) that satisfies the inequality N (ε, F, L_{2}(μ)) ≤ D̄ε^{−L} with some numbers D̄ ≥ 1 and L ≥ 1 for all 0 < ε ≤ 1. Let us also assume that this class of functions F also has the properties sup_{x∈X} |f(x)| ≤ 1, ∫ f(x)μ( dx) = 0 and ∫ f^{2}(x)μ( dx) ≤ σ^{2} with a prescribed

number 0 < σ ≤ 1 for all f ∈ F. Take the normalized sums S_{n}(f) = \frac{1}{\sqrt{n}} ∑_{l=1}^{n} f(ξ_{l}) for

all f ∈ F, and let us fix a number Ā ≥ 1.

There exists a number M = M(Ā) > 0 such that with these parameters Ā and M = M(Ā) ≥ 1 the following relations hold. For all numbers v > 0 such that nσ^{2} ≥ (\frac{v}{σ} )^{2} ≥ M(L log \frac{2}{σ} +log D̄) define the number σ̄_{0} = σ̄_{0}(v) = \frac{1}{8\sqrt{n}} \frac{v}{Āσ}. Then for all numbers σ̄_{0} ≤ σ̄ ≤ σ a collection of functions Fσ̄ = {f_{1}, …, f_{m}} ⊂ F with m ≤ D̄2^{2L}σ̄^{−L} elements can be chosen in such a way that the union of the sets D_{j} = {f: f ∈ F, ∫ |f − f_{j}|^{2} dμ ≤ σ̄^{2}},

1 ≤ j ≤ m, cover the set of functions F, i.e. ⋃_{j=1}^{m} D_{j} = F, and the normalized random

sums S_{n}(f), f ∈ Fσ̄, n ≥ 2, satisfy the inequality

P ( sup_{f∈Fσ̄} |S_{n}(f)| ≥ \frac{v}{Ā}) ≤ 4 exp \{−α (\frac{v}{10Āσ} )^{2}\}  (3.9)

with an appropriate constant α and with the previously chosen parameter Ā. (In formula (3.9) we have assumed that the number v appearing in it satisfies the condition nσ^{2} ≥ (\frac{v}{σ})^{2} ≥ M(L log \frac{2}{σ} + log D̄).)

Remark. Theorem 3.2 is an empty statement if the inequality nσ^{2} ≥ (\frac{v}{σ})^{2} ≥ M(L log \frac{2}{σ} + log D̄) has no solution. This result can be considered as a consequence of Proposition 6.1 in [5], although it contains some statements which are proved but not explicitly stated in [5]. In that work inequality (3.9) is proved in the special case when σ̄ = 4^{k}σ with some non-negative integer k, and σ̄ ≥ σ̄_{0}, and in that case the set Fσ̄ can be chosen with smaller cardinality m ≤ D̄σ̄^{−L}. It is not difficult to deduce Theorem 3.2 from this result. Actually Theorem 3.2 contains the result one can prove with the help of the classical chaining method under the conditions of the Extension of Theorem 1. It is a classical method which works in ‘regular Gaussian’ or ‘almost Gaussian’ models, see [5].

In the proof of the Extension of Theorem 1 let us first check that under its conditions also the conditions of Theorem 3.2 hold with D̄ = D2^{L}. In particular, all numbers v satisfying the conditions of the Extension of Theorem 1 satisfy also the condition nσ^{2} ≥ (\frac{v}{σ} )^{2} ≥ M(L log \frac{2}{σ} + log D̄) of Theorem 3.2 if we choose the constant C_{6} in the definition of ū(σ) (in dependence of the value M(Ā)) sufficiently large. The inequality N (ε, F, L_{2}(μ)) ≤ D̄ε^{−L} with D̄ = 2^{L}D under the conditions of this Extension follows from the inequality N (ε, F, L_{2}(μ)) ≤ N (\frac{ε}{2}, F, L_{1}(μ)) if F consists of functions whose absolute value is bounded by 1. This relation is a consequence of the observation that ∫ |f − g|^{2} dμ ≤ 2 ∫ |f − g| dμ if sup |f(x)| ≤ 1 and sup |g(x)| ≤ 1.

We still have to check that nσ^{2} ≥ (\frac{v}{σ} )^{2} ≥ M(L log \frac{2}{σ} + log D̄) under the conditions ū(σ) ≤ v ≤ \sqrt{n}σ^{2}. But this is a simple consequence of the definition of ū(σ) if the constant C_{6} is chosen sufficiently large in it. Actually at this point we could replace the number L^{3/4} by L^{1/2} in the definition of ū(σ).

We shall prove the Extension of Theorem 1 with the help of Theorem 3.2 with the choice of σ̄^{2} = \frac{v}{Ā\sqrt{n}}, where Ā = max(2, A_{0}) and Theorem 3.1 with σ = σ̄. First we have to check that this number σ̄ satisfies the conditions σ̄_{0} = \frac{1}{8\sqrt{n}} \frac{v}{Aσ} ≤ σ̄ ≤ σ (to apply Theorem 3.2) and nσ̄^{2} ≥ L log n + log D (to apply Theorem 3.1) (if the number M(Ā) is sufficiently big). We shall also show that nσ̄^{2} ≥ L log \frac{1}{σ̄} + log(2^{3L}D).

The inequality σ̄_{0} ≤ σ̄ ≤ σ can be rewritten as \frac{v^{2}}{64\sqrt{n}Āσ^{2}} = Ā\sqrt{n}σ̄_{0}^{2} ≤ v ≤ Ā\sqrt{n}σ^{2}. Both of these inequalities hold if v ≤ Ā\sqrt{n}σ^{2}, or in an equivalent form (\frac{v}{σ})^{2} ≤ Ā^{2}nσ^{2}. This inequality holds under the conditions of Theorem 3.2, since we chose a number Ā ≥ 1.

To prove the second inequality let us observe that nσ̄^{2} ≥ nσ̄_{0}^{2} = \frac{1}{64} \frac{v^{2}}{Ā^{2}σ^{2}} ≥ \frac{M}{64Ā^{2}} (L log \frac{2}{σ} + log(2^{L}D)). This calculation implies the desired inequality in the case σ ≤ n^{−1/3} if the constant M = M(Ā) is chosen sufficiently large, since in this case log \frac{2}{σ} ≥ \frac{1}{3} log n. In the case n^{−1/3} ≤ σ ≤ 1 we exploit that in the Extension of Theorem 1 we restricted our attention to the case when the number u satisfies the more restrictive condition v ≥ ū(σ) = C_{6}σ(L^{3/4} log^{1/2} \frac{2}{σ} + (log D)^{1/2}). In this case we can

write nσ̄^{2} = \frac{\sqrt{n}v}{A} ≥ \frac{\sqrt{n}ū(σ̄)}{A} ≥ ^{\frac{C_{6}\sqrt{n}σL^{3/4} log^{1/2} \frac{2}{σ}}{A}} ≥ L^{3/4}n^{1/6} if the constant C_{6} is sufficiently large, and nσ̄^{2} ≥ nσ̄_{0}^{2} = \frac{1}{64} \frac{v^{2}}{Ā^{2}σ^{2}} ≥ \frac{1}{64} \frac{ū(σ)^{2}}{Ā^{2}σ^{2}} ≥ C_{6}L^{3/2} log \frac{2}{σ} ≥ C_{6}L^{3/2}. The last two inequalities imply that in the case n^{−1/3}σ ≤ 1 we have nσ̄^{2} = (nσ̄^{2})^{2/3}(nσ̄^{2})^{1/3} ≥ C_{6}^{1/3}Ln^{1/9} ≥ 2L log n. On the other hand, the former results imply that nσ̄^{2} ≥ 2 log D, and as a consequence the desired inequality holds also in the case n^{−1/3} ≤ σ ≤ 1. The remaining inequality nσ̄^{2} ≥ L log \frac{1}{σ̄} + log(2^{3L}D) follows from the first estimate we proved about nσ̄^{2}.

To prove the Extension of Theorem 1 let us choose with the help of Theorem 3.2 a sequence of functions Fσ̄ = {f_{1}, …, f_{m}} ⊂ F and sets D_{j} = {f: f ∈ F, ∫ |f − f_{j}|^{2} dμ ≤

σ̄^{2}}, 1 ≤ j ≤ m, with m ≤ D̄2^{2L}σ̄^{−L} elements such that ⋃_{j=1}^{m} D_{j} = F.

Since we chose a number A ≥ 2 with the above notation we can write up the inequality

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ P ( sup_{f∈Fσ̄} |S_{n}(f)| ≥ \frac{v}{A}) + ∑_{j=1}^{m} P ( sup_{f∈D_{j}} |S_{n}(f − f_{j})| ≥ \frac{v}{2} )

if ū(σ) ≤ v ≤ \sqrt{n}σ^{2}, and the two terms at the right-hand side of this inequality can be estimated by means of Theorems 3.1 and 3.2.

We can write

P ( sup_{f∈Fσ̄} |S_{n}(f)| ≥ \frac{v}{Ā}) ≤ 4e^{−αv^{2}/100Ā^{2}σ^{2}}

by Theorem 3.2, and

∑_{j=1}^{m} P ( sup_{f∈D_{j}} |S_{n}(f − f_{j})| ≥ \frac{v}{2} ) ≤ me^{−nAσ̄^{2}}

by Theorem 3.1.

On the other hand,

me^{−nAσ̄^{2}} ≤ D2^{3L}σ̄^{−L}e^{−nAσ̄^{2}} ≤ e^{−nAσ̄^{2}/2} ≤ e^{−nAσ̄_{0}^{2}/2} = e^{−Av^{2}/64Āσ^{2}} ≤ e^{−v^{2}/64σ^{2}},

since

D2^{3L}σ̄^{−L}e^{−nAσ̄^{2}/2} ≤ D2^{3L}σ̄^{−L}e^{−nσ̄^{2}} ≤ 1

by the inequality nσ̄^{2} ≥ L log \frac{1}{σ̄} + log(D2^{3L}). The above inequalities imply that

P (sup_{f∈F} |S_{n}(f)| ≥ v) ≤ 4e^{−αv^{2}/100Ā^{2}σ^{2}} + e^{−v^{2}/64σ^{2}}

if ū(σ) ≤ v ≤ \sqrt{n}σ^{2}. Thus formula (1.3) and the Extension of Theorem 1 is proved.

I finish this paper with a discussion about its methods and results.

4. A discussion about the methods and results of this paper.

The problem of this paper, the estimation of the tail-distribution of the supremum

sup_{f∈F} S_{n}(f) of the normalized sums S_{n}(f) = \frac{1}{\sqrt{n}} ∑_{k=1}^{n} f(ξ_{k}) for a sequence of i.i.d. random

variables ξ_{1}, …, ξ_{n} and a class of functions F with some nice properties has a long history. Such a problem arises in a natural way in the study of the uniform central limit theorem for a class of normalized sums S_{n}(f), f ∈ F, with a nice class of functions F, see [3]. An important part of such a study is to prove the ‘tightness’ of the class of functions S_{n}(f), f ∈ F, by showing first that for a subclass F′ ⊂ F such that E(f −g)^{2} ≤ δ with a small number δ for any pairs f, g ∈ F′ the supremum sup_{f∈F′} S_{n}(f −g)

with a fixed g ∈ F is small with probability almost 1. There are some results that give a bound on the tail-distribution of such a supremum if δ = δ_{n}, and δ_{n} → 0 as n → ∞. But the estimates I know about in this direction do not provide a sharp estimate if δ_{n} → 0 very fast. My goal in this paper was to give a good estimate also in such cases, and to give a good bound on the tail distribution of sup_{f∈F′} S_{n}(f − g) in the general case

δ = δ_{n}.

Let us remark that for large indices n the random variables S_{n}(f) are asymptotically Gaussian. Hence it is natural to study first the natural Gaussian counterpart of the above problem to understand what kind of estimates hold in this modified problem, what kind of methods are useful in their study, and how they can be adapted to our original problem. The following problem can be considered as this natural Gaussian counterpart. Take a class of (jointly) Gaussian random variables η_{t}, Eη_{t} = 0, t ∈ T, with a (countable) parameter set T, and give a good estimate on the tail distribution of sup_{t∈T} η_{t} with the help

of the (pseudo) metric ρ(s, t), ρ^{2}(s, t) = E(η_{s} − η_{t})^{2}, s, t ∈ T. There is a good solution of this problem with the help of the so-called chaining argument. This is worked out in detail in [12], and this book contains the sharpest results in this direction. We get a good estimate if for all ε > 0 we can find a set {t_{1}, …, t_{M}} ⊂ T with relatively few M = M(ε) elements, whose ε-neighbourhood with respect to the metric ρ covers the whole space T. The estimate depends on this function M(ε). In particular, if M(ε) ≤ Dε^{−L} with some constants D > 1 and L > 1, and Eη_{t}^{2} ≤ σ^{2} ≤ 1 for all t ∈ T and ε > 0, then the estimate

P (sup_{t∈T} η_{t} > u) ≤ De^{−(u−u(σ))^{2}/2σ^{2}} holds for all u ≥ u(σ) with u(σ) = CL^{1/2}σ log^{1/2} \frac{2}{σ},

where C > 0 is a universal constant. The book [12] contains a sharper result which provides a good estimate in the general case. It is also mentioned in this book that a similar estimate holds for an arbitrary set of random variables ζ_{t}, t ∈ T, if they satisfy the ‘Gaussian type estimate’ P (|ζ_{t} − ζ_{s}| > u) ≤ Ce^{−αu^{2}/ρ^{2}(s,t)} with some fixed numbers C > 0 and α > 0 for all s, t ∈ T and u > 0. The question arises whether such an estimate holds also in our original problem about the supremum of normalized random sums S_{n}(f), f ∈ F, if they are defined with the help of a nice class of functions F.

Let us assume that sup |f(x)| ≤ 1, and ES_{n}(f) = 0 for all f ∈ F in the class of functions F we consider. Then we may try to apply the above indicated result with T = F and an appropriate metric ρ on it. Observe that E[S_{n}(f)−S_{n}(g)]^{2} = ∫ (f −g)^{2} dμ for all f, g ∈ F, where μ denotes the distribution of the random variables ξ_{j}. This means that we have to work with the metric ρ(f, g) defined as ρ^{2}(f, g) = ∫ (f − g)^{2} dμ in this case. The question arises whether the above formulated ‘Gaussian type estimate’ which provides a good estimate on the tail distribution of the supremum we are interested in holds in this case.

I discussed this problem in detail in the third chapter of my book [5]. The main point is that there are some classical results, like the Bernstein or Bennett inequality that give good estimates for the tail distribution of sums of bounded i.i.d. random variables, but they provide so good ‘Gaussian type estimates’ that we need only at not too high levels u. There are also examples that show that in certain cases we cannot get good ‘Gaussian type estimates’ at high levels u. This has the consequence that the chaining argument worked out to handle the Gaussian counterpart of our problem is not good enough to solve our problem. It enables us to reduce it to the special case, when the distance ρ(f, g) is very small for all f, g ∈ F, but it does not give more help. (How small this distance must be that depends on the sample size n.) The study of this reduced problem demands new ideas. Moreover, to get good estimates we have to introduce some new conditions about the behaviour of the class F, it is not enough to have good control on the metric ρ(f, g), f, g ∈ F, introduced above.

There are two main approaches to introduce appropriate new conditions which enable us to prove good estimates in the problem we are interested in. The first one can be found in the book of Talagrand [12]. He introduced a condition by which for all ε > 0 the class of functions F must have an ε-dense subset with relatively few elements not only with respect to the metric ρ but also with respect to the supremum norm. Theorems 1.2.7 and 2.7.2 in [12] are results in this spirit. Talagrand also proved some interesting and deep consequences of these results in Chapter 3 of [12]. There are however important problems where such an approach does not work. Such problems are e.g. the behaviour of the models considered in the Example of Section 2 or the problems considered in Section 2 of [6]. More generally such a problem appears if F consists of the indicator functions χ_{A} of different sets or if we consider their normalized versions f_{A}(x) = χ_{A}(x) − μ(A). (We may apply such a normalization to get functions whose integral with respect to the measure μ equals zero.) In such cases all functions of F are far from each other in the supremum norm, and as a consequence of it F has no dense subset with respect to the supremum norm with relatively few elements. To overcome this difficulty a different additional condition was introduced. This new condition demands that F must be a class of functions with polynomially increasing covering numbers. This approach proved to be useful in several interesting cases when the method of [12] does not work. There are some works, see e.g. [3], [10], [14] where it is shown that there are many classes of functions F with polynomially increasing covering numbers. The proof about their existence is closely related to the theory of Vapnik–Červonenkis classes.

The original technique for proving good estimates on the tail distribution of the supremum of the random sums S_{n}(f), f ∈ F, under the condition that the class of functions F has polynomially increasing covering numbers was the application of the so-called symmetrization argument. This technique is applied in several works, see e.g. [3], [5], [7], [9], [10], [13], and it works in several models when the method of [12] is not applicable. I do not describe this method, I only remark that I compared it with that of Talagrand in Chapter 18 of [5] at pp. 235–237. Here I also made a comparison between the applicability of these two methods.

Nevertheless, the symmetrization argument does not provide a sharp estimate if the bound σ^{2} ≥ sup_{f∈F} Ef^{2}(ξ_{j}) is too small. The main goal of the present paper to give a sharp

estimate also in this case. To understand our results better let us compare them with the results of some previous papers in the case when the class of functions F contains functions bounded by 1, and it has polynomially increasing covering numbers with bounded exponent L and parameter D, i.e. these numbers have a bound not depending on σ. Paper [14] gives the following upper bound for the value of the concentration point of the distribution of sup_{f∈F} S_{n}(f) in this case.

E^{∗} sup_{f∈F} S_{n}(f) ≤ CJ(σ, F, L_{2}) (1 + \frac{J(σ, F, L_{2})}{σ^{2}\sqrt{n}})

with a universal coefficient C, where

J(σ, F, L_{2}) = sup_{ν} ∫_{0}^{σ} \sqrt{1 + log N (ε, F, L_{2}(ν))} dε

with the uniform covering number sup_{ν} N (·, ·, ·) with respect to L_{2}-norms. (Here the

notation E^{∗} is applied, since the choice of a non-countable class of functions F is also allowed, and in this case the outer expectation E^{∗} is applied.)

Some calculation shows that in this case J(σ, F, L_{2}) ≍ σ\sqrt{log \frac{2}{σ}}, hence we get

the upper bound const. (σ\sqrt{log \frac{2}{σ}} + \begin{matrix}log & \frac{2}{σ} \\ √ & \overline{n} \end{matrix} ) for the value of the concentration point in

this case. This yields the upper bound Cσ\sqrt{log \frac{2}{σ}} if σ^{2} ≥ const.\frac{log n}{n} and C \begin{matrix}log & \frac{2}{σ} \\ √ & \overline{n} \end{matrix} if

σ^{2} ≤ const.\frac{log n}{n} for the value of the concentration point. This result is sharp in the first case, (see Theorem 1 and its Extension together with the Example in Section 2). But it is not sharp in the second case. Moreover, it can be improved in the following trivial way. If σ^{2} ≤ σ_{0}^{2} = \frac{log n}{n}, then we can apply the above estimate for σ_{0}^{2} instead

of σ^{2}, and this yields the upper bound \frac{log n}{\sqrt{n}} instead of the estimate \begin{matrix}log & \frac{2}{σ} \\ √ & \overline{n} \end{matrix} for the value of the concentration point. This means that the result of [14] could not yield a better estimate if σ^{2} ≪ σ_{0}^{2} than in the case σ^{2} = σ_{0}^{2}.

Massart’s paper [7] contains another result about the tail distribution of the supremum of S_{n}(f), f ∈ F. The proof in that paper is based on a modified version of the symmetrization argument. The result of [7] is rather complicated, but one can get an estimate for the value of the concentration point with its help. Here I shall consider the version of this result presented in Theorem 2.14.16 of the book [13]. We can get the bound for the value of the concentration point by calculating when the bound given for the tail distribution of the supremum given in this result becomes smaller than 1. Some calculation that I would omit would provide the right bound Cσ\sqrt{log \frac{2}{σ}}

if σ^{2} ≥ const.n^{−1/4} and a much weaker bound Cn^{−1/4} log^{1/2} \frac{2}{σ} for the value of the concentration point in the other case. It is also worth considering the estimate that Alexander’s method worked out in [1] supplies. It is based on the chaining argument, and it yields a good estimate, similarly to [14] if σ^{2} ≥ σ_{0}^{2} = \frac{log n}{n}, and a weak one in the other case.

Actually the proof of the result in [5] corresponding to the Extension of the Theorem 1 is based on Alexander’s idea in [1], and it yields a good estimate only for σ ≥ σ_{0}. The starting point in the present investigation was an attempt to find a refinement of this method which supplies a good estimate for the tail distribution of the supremum we are investigating if the number σ^{2} satisfying the inequality σ^{2} ≥ sup_{f∈F} Ef^{2}(ξ_{j}) can

be chosen in an arbitrary way. The original result was proved by means of an appropriate inductive hypothesis. To get an improved version of it we have to find a good reformulation of this inductive hypothesis that takes into account that in the case of small parameter σ^{2} we have a better estimate. This lead me to the investigation of the problem in paper [6]. Then it turned out that a direct application of the results in [6] enables us to work out a different method that yields a more general result with less effort. It may be interesting to compare this method with some standard techniques applied in the study of other probabilistic problems.

In the proof of limit theorems for sums of independent random variables or in the study of some similar problems a standard method is the application of the so-called truncation. The truncated random terms show nice ‘regular’ behaviour, since they are bounded. This enables us to study them with the help of classical methods. The contributions omitted by truncation contain the ‘irregular’ part of the random variables, and they cannot be handled by standard methods. But in nice cases it can be proved that they are negligible, hence we can prove the desired results.

Here we applied a similar approach to prove our estimates with the help of the result in [6]. We took some appropriately chosen functions f_{j} ∈ F, considered their small neighbourhoods with respect to the metric ρ defined in this section, and estimated the increase of S_{n}(f) in these neighbourhoods. More explicitly, we chose some appropriate functions f_{j} ∈ F and an appropriate small number σ > 0, and we estimated the tail distribution of sup_{f∈F, ρ(f,f_{j})≤σ} S_{n}(f − f_{j}). The tail distribution of these terms could be

well estimated by means of the result in [6]. They played a role similar to that part of random sums which were omitted at truncation in some analogous problems because of their large value. These terms are small by the results of [6]. On the other hand, they enable us to restrict our attention to such problems where we can make good estimations by means of some standard methods, like the application of classical estimates on the tail distribution of the single terms S_{n}(f) or the chaining argument. In the proof of Theorem 1 and its Extension actually such an approach was followed.

If we look carefully how we could work with the help of the result of [6] and how the symmetrization argument was applied in other works, then we can see that they played a similar role. It seems to me that the result of [6] can replace the symmetrization argument in most applications, moreover it supplies a more powerful tool.

References.

[1] K. S. Alexander, Probability inequalities for empirical processes and a law of the iterated logarithm. Annals of Probability 15 no. 4 1041–1067 (1984)

[2] P. Deheuvels, J. H. J. Einmahl, D. M. Mason, F. H. Ruymgaart, The almost sure behavior of maximal and minimal multivariate k_{n}-spacings. J. Multivariate Anal. 24, 155–176 (1988)

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

[4] J. Komlós, P. Major, G. Tusnády, An approximation of partial sums of independent rv.’s and the sample DF. I. Z. Wahrscheinlichkeitstheorie verw. Gebiete 32, 111–131 (1975)

[5] 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)

[6] P. Major, Sharp estimate on the supremum of a class of partial sums of small i.i.d. random variables, Stochastic Processes and their Applications (2015), http://dx.doi.org/10.1016/j.spa.2015.07.016

[7] P. Massart, Rates of convergence in the central limit theorem for empirical processes. Annales Institut Henri Poincaré 22, 381–423 (1986)

[8] H. P. McKean Jr., Stochastic integrals. Academic Press New York London (1969)

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

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

[11] M. Talagrand, New concentration inequalities in product spaces. Invent. Math. 126, 505–563 (1996)

[12] M. Talagrand, The generic chaining. Springer Monographs in Mathematics. Springer–Verlag, Berlin Heidelberg New York (2005)

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

[14] A. W. van der Wart, J. A. Wellner, A local maximal inequality under uniform entropy. Electronic Journal of Statistics 5, 192–203 (2011)