The problem we are interested in 1

Let ξ_{1}, …, ξ_{n} be a sequence of i.i.d. random variables with some distribution μ on a measurable space (X , X). Let a class of functions F consisting of countably many functions be given on the space (X , X) with the properties ∫ f (x)μ( dx) = 0, sup_{x∈X} |f (x)| ≤ 1 and ∫ f (x)^{2}μ( dx) ≤ σ^{2} with some 0 < σ ≤ 1 for all elements f ∈ F. Let F be a class of functions with polynomially increasing covering numbers with exponent L ≥ 1 and parameter D ≥ 1. (I recall the definition of this notion later.) Define the normalized sums S_{n}(f ) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f (ξ_{j}) for all f ∈ F, and give a good estimate on the tail distribution

P (sup_{f ∈F} S_{n}(f ) > v) for all numbers v > 0  (1)

of the supremum of these sums. This estimate may depend on σ, L and D.

An important result, called the concentration inequality, has the consequence that there is a level v_{0} such that for v < v_{0} the probability in formula (1) is almost 1, while for v > v_{0}, it begins to decrease rapidly. An important part of our problem is to give a good estimate on this level v_{0}.

There is a solution for a natural analogous version of our problem when we estimate the supremum of Gaussian random variables. This is done by means of a method called the chaining argument. A similar estimate can be proved under some restrictions in our model with the help of the so-called symmetrization argument. Our goal is to prove a good estimate in in the general case, which holds without these restrictions.

To discuss this problem first I recall the definition of classes of functions with polynomially incerasing functions together with their exponent L and parameter D. I do it in two steps on the next page.

First step of the definition.

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.

Second step of the definition.

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} holds for all 0 < ε ≤ 1 with the number sup_{ν} N (ε, F, L_{1}(ν)) introduced in the previous definition.

A useful example 4

First I present a simple example which may help to understand what kind of result we may expect.

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̄_{σ} as set of 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. Give a good estimate on P_{n}(v) = P(sup_{j} S_{n}(f_{j}) > v).

F satisfies the conditions in our problem. It is a class of functions with polynomially increasing functions with some exponent L and parameter D which do not depend on σ^{2}, and the parameter σ^{2} introduced in the model is an upper bound for all ∫ f_{j}(x)^{2}μ( dx).

Our first problem: Find a good estimate on the number v_{0} with the property that P_{n}(v) ≪ 1 only for v > v_{0}. Its solution:

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 − δ,

holds with 1.) û(σ) = \frac{C̄}{\sqrt{n}} if σ^{2} ≤ n^{−400},

2.) û(σ) = \frac{C̄}{\sqrt{n}} _{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} if n^{−400} < σ^{2} ≤ \frac{log n}{8n}, and

3.) û(σ) = C̄σ log^{1/2} \frac{2}{σ} if \frac{log n}{8n} ≤ σ^{2} ≤ 1.

This result says that v_{0} ≥ û(σ) for the number v_{0} with the above demanded property. Our results will show that this estimate is sharp. The above example helps us to understand what kind of result we can expect in the general case.

Next I explain the picture behind this result.

In case 3.) of this example σ^{2} is relatively large, and we get such an estimate for the best choice of û(σ) as in the Gaussian case.

In case 2.) we get the right choice for û(σ) not by a Gaussian but by a Poissonian approximation of our model.

In case 1.) σ^{2} is very small. We can make a trivial estimate by exploiting that given an arbitrary partition of our space, some element of this partitition contains a given sample point. In this case this is the right estimate for û(σ).

Next I formulate the Theorem, and its Extension, the main results of my paper. They say that in the general case we have the estimate that the above Example and some classical estimates on the tail distribution of sums of independent random variables suggest.

Theorem. Let a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n}, n ≥ 2, with values in (X , X) with some distribution μ and a countable class of functions F on the same space (X , X) with polynomially increasing covering numbers with exponent L ≥ 1 and parameter D ≥ 1 be given. Let the functions f ∈ F satisfy 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. The normalized sums S_{n}(f ), f ∈ F, satisfy 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(σ)

with some universal constants C_{j} > 0, 1 ≤ j ≤ 5, if one of the following conditions is satisfied. 1.) σ^{2} ≤ \frac{1}{n^{400}} , and u(σ) = \frac{C_{3}}{\sqrt{n}}(L + \frac{log D}{log n}),

2.) \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}} )}} + logD),

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

Extension of the Theorem. Let us consider, similarly to the Theorem, a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n}, n ≥ 2, with values in a space (X , X) with some distribution μ which satisfies the conditions of the Theorem. In the case \frac{log n}{8n} < σ^{2} ≤ 1 the supremum of the normalized sums S_{n}(f ), f ∈ F, satisfies the inequality

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

with appropriate (universal) constants α > 0, C > 0 and C_{6} > 0 if \sqrt{n}σ^{2} ≥ v ≥ ū(σ), where ū(σ) is defined as ū(σ) = C_{6}σ(L^{3/4} log^{1/2} \frac{2}{σ} + (logD)^{1/2}).

In cases 1.) and 2.) Theorem gives a good estimate for v ≥ u(σ) with an u(σ) suggested by the Example. It is a (non-Gaussian) estimate suggested by Bennett’s inequality. In case 3.) the Theorem and its Extension together give a good estimate. It holds for v ≥ ū(σ), as it is suggested by the Example. The Extension gives a good Gaussian estimate if ū(σ) ≤ v ≤ \sqrt{n}σ^{2}. Over this level we have a weaker estimate formulated in the Theorem.

The main ideas of the proof: I can simplify our problem with the help of my paper Sharp estimate on the supremum of a class of sums of small i.i.d. random variables by exploiting that we are working with a class of functions with polynomially increasing covering numbers. This enables us to reduce our problem to the case when we have finally many random sums S_{n}(f ) with some nice properties. The reduced problem can be solved by means of classical methods, like the Chaining argument and good estimates of sums of i.i.d. random variables.

The main point of the proof is that we can separate the regular and irregular contributions to the supremum we are investigating. The regular part can be well investigated by classical tools like the chaining argument. The real novelty in my research was to find a new method for the estimation of the irregular effects. This demanded the application of new arguments.

I put a more detailed version of this talk to the address

http://www.renyi.hu/˜ major/talks/supremum.html