nach oben

2014 | Buch

Kapitel lesen Erstes Kapitel lesen

Upper and Lower Bounds for Stochastic Processes

Modern Methods and Classical Problems

verfasst von: Michel Talagrand

Verlag: Springer Berlin Heidelberg

Buchreihe : Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The book develops modern methods and in particular the "generic chaining" to bound stochastic processes. This methods allows in particular to get optimal bounds for Gaussian and Bernoulli processes. Applications are given to stable processes, infinitely divisible processes, matching theorems, the convergence of random Fourier series, of orthogonal series, and to functional analysis. The complete solution of a number of classical problems is given in complete detail, and an ambitious program for future research is laid out.

Inhaltsverzeichnis

Frontmatter

1. Philosophy and Overview of the Book

Abstract

Chapter 1 describes the philosophy of the book and some of its highlights. For us a stochastic process is a collection of random variables (r.v.s) (X _t)_t∈T, where T is an index set, and the goal of the book is to find upper bounds and lower bounds for the random quantity sup_t∈T X _t as a function of certain “geometric” characteristics. A fundamental example, which covers in particular the case of Gaussian processes is that of random series X _t=∑_k≥1 ξ _k f _k(t), where f _k are functions and ξ _k are independent r.v.s. The study of such series occupies a large part of this book.

Michel Talagrand

2. Gaussian Processes and the Generic Chaining

Abstract

Chapter 2 describes the “generic chaining” method, a kind of optimal organization of Kolmogorov’s chaining, which forms the core of the book. In its simplest form it allows to bound a stochastic process under a condition on the tails of its increments. The typical case is that of Gaussian processes. These satisfy the following “increment condition”: for u>0 and any s,t∈T, we have P(|X _s−X _t|≥u)≤2exp(−u ²/2d(s,t)²), where d ²(s,t)=E(X _s−X _t)². This simply expresses a (somewhat suboptimal) bound on the tail of the Gaussian r.v. X _s−X _t. The generic chaining bound involves certain “geometric” characteristics of the metric space (T,d) which in a sense measure the “size” of this space in a more precise manner than the classical Dudley’s integral. A fruitful formulation of the generic chaining bound involves sequences of partitions of the metric space, and we provide the basic tools to construct such partitions. We also give a number of concrete examples by analysing ellipsoids in Hilbert space, and showing that Dudley’s integral is already insufficient to study these.

Michel Talagrand

3. Random Fourier Series and Trigonometric Sums, I

Abstract

In Chapter 3 we investigate Gaussian processes in “the stationary case,” where e.g. the underlying space is a compact group and the distance is translation invariant. This is relevant to the study of random Fourier series, the basic example of which is X _t=∑_k≥1 ξ _kexp(2P iikt), where t∈[0,1] and the r.v.s ξ _k are independent. The fundamental case where ξ _k=a _k g _k for numbers a _k and independent Gaussian r.v.s (g _k) is of great historical importance. We prove some of the classical Marcus-Pisier results, which provide a complete solution in this case, and are also quite satisfactory in the more general case when the random coefficients (ξ _k) are square-integrable. We also explain a result of X. Fernique on vector-valued random Fourier series, which had an important part in the genesis of this book.

Michel Talagrand

4. Matching Theorems, I

Abstract

In Chapter 4 we demonstrate that the generic chaining (or of course some equivalent form of it) is already required to really understand the irregularities occurring in the distribution of N points (X _i)_i≤N independently and uniformly distributed in the unit square. These irregularities are measured by the “cost” of pairing (=matching) these points with N fixed points that are very uniformly spread, for two notions of cost. For each of them we prove that the expected cost of an optimal matching is bounded by \(L (\log N)^{\alpha}/\sqrt{N}\) for either α=1/2 or α=3/4. The factor \(1/\sqrt{N}\) is simply a scaling factor, but the fractional powers of log are indeed fascinating (and optimal). The connection with Chapter 2 is that one can often reduce the proof of a matching theorem to the proof of a suitable bound for a quantity of the type \(\sup_{f\in \mathcal{F}} | \sum_{i\leq N}(f(X_{i}) -\int f{\rm d} \lambda)|\) where \(\mathcal{F}\) is a class of functions on the unit square and λ is Lebesgue’s measure. That is, we have to bound a complicated random process. The main issue is to control in the appropriate sense the size of the class \(\mathcal{F}\). For this we parametrize this class of functions by a suitable ellipsoid of Hilbert space using Fourier transforms. This approach illustrates particularly well the benefits of an abstract point of view: we are able to trace the mysterious fractional powers of log back to the geometry of ellipsoids in Hilbert space.

Michel Talagrand

5. Bernoulli Processes

Abstract

In Chapter 5 we investigate Bernoulli processes, where the individual random variables X _t are linear combinations of independent random signs. Random signs are obviously important r.v.s, and occur frequently in connection with “symmetrization procedures”, a very useful tool. Each Bernoulli process is associated with a Gaussian process in a canonical manner, when one replaces the random signs by independent standard Gaussian r.v.s. The Bernoulli process has better tails than the corresponding Gaussian process (it is “subgaussian”) and is bounded whenever the Gaussian process is bounded. There is however a completely different reason for which a Bernoulli process might be bounded, namely that the sum of the absolute values of the coefficients of the random signs remains bounded independently of the index t. A natural question is then to decide whether these two extreme situations are the only fundamental reasons why a Bernoulli process can be bounded, in the sense that a suitable “mixture” of them occurs in every bounded Bernoulli process. This was the “Bernoulli Conjecture”, which has been so brilliantly solved by W. Bednorz and R. Latała. The proof of their fundamental result occupies much of this chapter. Many of the previous ideas it builds upon will be further developed in subsequent chapters.

Michel Talagrand

6. Trees and the Art of Lower Bounds

Abstract

In Chapter 6 we describe different notions of trees, and show how one can measure the “size” of a metric space by the size of the largest trees it contains, in a way which is equivalent to the measures of size introduced in Chapter 2. Building a large tree in a metric space is an efficient method to bound its size from below. We apply this idea to prove that the upper bounds obtained in the matching problems of Chapter 4 are sharp: we prove lower bounds of the same order as these upper bounds.

Michel Talagrand

7. Random Fourier Series and Trigonometric Sums, II

Abstract

In Chapter 7 we return to the study of random Fourier series, but now without making any assumption of integrability on the random coefficients, which we simply assumed to be independent symmetric r.v.s. This chapter also develops one of the fundamental ideas of this work: many processes can be exactly controlled, not by using one or two distances, but by using an entire family of distances. With these tools, we are able to give in full generality necessary and sufficient conditions for convergence of random Fourier series. These conditions can be formulated in words by saying that convergence is equivalent to the finiteness of (a proper generalization of) a certain “entropy integral”. We then give examples of application of the abstract theorems to the case of ordinary random Fourier series.

Michel Talagrand

8. Processes Related to Gaussian Processes

Abstract

In Chapter 8 we transfer our understanding of Gaussian processes to processes that are, in various senses, related to Gaussian processes. We use that p-stable processes are conditionally Gaussian to provide lower bounds for such processes. Although these bounds are in general very far from being upper bounds, they are in a sense extremely accurate. In certain situations, where there is “stationarity”, they can be reversed. We obtain these bounds rather easily, even in the previously difficult case p=1.

Decoupled Gaussian chaoses are another class of conditionally Gaussian processes. There exists methods fundamentally different from chaining to control them (a situation which we do not expect to occur for processes defined as sums of a random series). Finally we study the tails of a single multiple order Gaussian chaos, and present a deep result of R. Latała which provides a rather complete description of these tails.

Michel Talagrand

9. Theory and Practice of Empirical Processes

Abstract

In Chapter 9 we investigate how to control the supremum of the empirical process over a class of functions. The fundamental theoretical question in this direction is whether there exists a “best possible” method to control this supremum at a given size of the random sample. We offer a natural candidate for such a “best possible” method, in the spirit of the Bednorz-Latała result of Chapter 5. Whether this natural method is actually optimal is a major open problem. To illustrate that meditating on these theoretical questions might help to solve practical problems, we present a somewhat streamlined proofs of two deep recent results.

Michel Talagrand

10. Partition Scheme for Families of Distances

Abstract

In Chapter 10 we turn to other processes such that the description of the tails of their increments requires an entire sequence of parameters, and therefore a whole sequence of distances on the index space. As an application we consider the situation of “canonical processes”, where the r.v.s X _t are linear combinations of independent copies of symmetric r.v.s with density proportional to exp(−|x|^α) where α≥1 (and to considerably more general situations as discovered by R. Latała). The size of the process can then be completely described as a function of the geometry of the index space, a far reaching extension of the Gaussian case.

Michel Talagrand

11. Infinitely Divisible Processes

Abstract

In Chapter 11 we investigate infinitely divisible processes in a far more general setting than what mainstream probability theory has yet considered: we make no assumption of stationarity of increments of any kind and our processes are actually indexed by an abstract set. These processes are to Lévy processes what a general Gaussian process is to Brownian motion. Our main tool is a representation theorem due to J. Rosinski, which makes these processes appear as conditionally Bernoulli processes. For a large class of such processes we are able to prove lower bounds that extend those given in Chapter 8 for p-stable process. These lower bounds are not upper bounds in general, but we succeed in showing in a precise sense that they are upper bounds for “the part of boundness of the process which is due to cancellation”. Thus, whatever bound might be true for the “remainder of the process” owes nothing to cancellation.

Michel Talagrand

12. The Fundamental Conjectures

Abstract

In Chapter 12 we outlay a long range research program. We believe that it might well be true in considerable generality that “chaining explains all the part of the boundedness which is due to cancellation”. Even if this conjecture is true, there would remain to describe the “part of the boundedness which owes nothing to cancellation”, and for this part also we propose sweeping conjectures. At the heuristic level, the underlying idea of these conjectures is that ultimately, a bound for a stochastic process always arises from the use of the ‘union bound’ P(∪_n A _n)≤∑_n P(A _n) in a simple situation, and the use of basic principles such as linearity and positivity, or combinations of these.

Michel Talagrand

13. Convergence of Orthogonal Series; Majorizing Measures

Abstract

In Chapter 13 we turn to the old problem of characterizing the sequences (a _m) such that for each orthonormal sequence (φ _m) the series ∑_m≥1 a _m φ _m converges a.s., which has recently been solved by A. Paszkiewicz. Using a more abstract point of view, we present a very much simplified proof of his results (due essentially to W. Bednorz). This leads us to the question of discussing when a certain condition on the “increments” of a process implies its boundedness. When the increment condition is of “polynomial type”, this is more difficult than in the case of Gaussian processes, and requires the notion of “majorizing measure”. We present several elegant results of this theory, in their seemingly final form recently obtained by W. Bednorz.

Michel Talagrand

14. Matching Theorems, II: Shor’s Matching Theorem

Abstract

In Chapter 14 we return to matchings in dimension 2 and we prove a deep result of P. Shor. Unfortunately the best conceivable matching theorem, which would encompass this result as well as those of Chapter 4, and much more, remains as a challenging problem, “the ultimate matching conjecture”.

Michel Talagrand

15. The Ultimate Matching Theorem in Dimension ≥3

Abstract

In Chapter 15 we consider matchings in dimension ≥3. We are able to obtain the seemingly final result, a strong version of “the ultimate matching conjecture”. There are no more fractional powers of logN here, but in a random sample of N points uniformly distributed in [0,1]³, local irregularities occur at all scales between N ^−1/3 and (logN)^1/3 N ^−1/3, and our result can be seen as a precise global description of these irregularities.

Michel Talagrand

16. Applications to Banach Space Theory

Abstract

In Chapter 16 we give applications to various topics of Banach space theory, the most spectacular of which is a sharpened version of a celebrated result of Jean Bourgain on the Λ_p problem.

Michel Talagrand

Backmatter

Titel: Upper and Lower Bounds for Stochastic Processes
verfasst von: Michel Talagrand
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-54075-2
Print ISBN: 978-3-642-54074-5
DOI: https://doi.org/10.1007/978-3-642-54075-2