Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems

Preface
Contents
1 What Is This Book About?
	1.1 Philosophy
	1.2 What Is Chaining?
	1.3 The Kolmogorov Conditions
	1.4 Chaining in a Metric Space: Dudley\'s Bound
	1.5 Overall Plan of the Book
	1.6 Does This Book Contain any Ideas?
	1.7 Overview by Chapters
		1.7.1 Gaussian Processes and the Generic Chaining
		1.7.2 Trees and Other Measures of Size
		1.7.3 Matching Theorems
		1.7.4 Warming Up with p-Stable Processes
		1.7.5 Bernoulli Processes
		1.7.6 Random Fourier Series and Trigonometric Sums
		1.7.7 Partition Scheme for Families of Distances
		1.7.8 Peaky Parts of Functions
		1.7.9 Proof of the Bernoulli Conjecture
		1.7.10 Random Series of Functions
		1.7.11 Infinitely Divisible Processes
		1.7.12 Unfulfilled Dreams
		1.7.13 Empirical Processes
		1.7.14 Gaussian Chaos
		1.7.15 Convergence of Orthogonal Series: Majorizing Measures
		1.7.16 Shor\'s Matching Theorem
		1.7.17 The Ultimate Matching Theorem in Dimension Three
		1.7.18 Applications to Banach Space Theory
Part I The Generic Chaining
	2 Gaussian Processes and the Generic Chaining
		2.1 Overview
		2.2 Measuring the Size of the Supremum
		2.3 The Union Bound and Other Basic Facts
		2.4 The Generic Chaining
		2.5 Entropy Numbers
		2.6 Rolling Up Our Sleeves: Chaining in the Simplex
		2.7 Admissible Sequences of Partitions
		2.8 Functionals
		2.9 Partitioning Schemes
		2.10 Gaussian Processes: The Majorizing Measure Theorem
		2.11 Gaussian Processes as Subsets of a Hilbert Space
		2.12 Dreams
		2.13 A First Look at Ellipsoids
		2.14 Rolling Up Our Sleeves: Chaining on Ellipsoids
		2.15 Continuity of Gaussian Processes
		2.16 Notes and Comments
	3 Trees and Other Measures of Size
		3.1 Trees
			3.1.1 Separated Trees
			3.1.2 Organized Trees
			3.1.3 Majorizing Measures
		3.2 Rolling Up Our Sleeves: Trees in Ellipsoids
		3.3 Fernique\'s Functional
			3.3.1 Fernique\'s Functional
			3.3.2 Fernique\'s Convexity Argument
			3.3.3 From Majorizing Measures to Sequencesof Partitions
		3.4 Witnessing Measures
		3.5 An Inequality of Fernique
	4 Matching Theorems
		4.1 The Ellipsoid Theorem
		4.2 Partitioning Scheme II
		4.3 Matchings
		4.4 Discrepancy Bounds
		4.5 The Ajtai-Komlós-Tusnády Matching Theorem
			4.5.1 The Long and Instructive Way
			4.5.2 The Short and Magic Way
		4.6 Lower Bound for the Ajtai-Komlós-Tusnády Theorem
		4.7 The Leighton-Shor Grid Matching Theorem
		4.8 Lower Bound for the Leighton-Shor Theorem
		4.9 For the Expert Only
		4.10 Notes and Comments
Part II Some Dreams Come True
	5 Warming Up with p-Stable Processes
		5.1  p-Stable Processes as Conditionally Gaussian Processes
		5.2 A Lower Bound for p-Stable Processes
		5.3 Philosophy
		5.4 Simplification Through Abstraction
		5.5 1-Stable Processes
		5.6 Where Do We Stand?
	6 Bernoulli Processes
		6.1 Bernoulli r.v.s
		6.2 Boundedness of Bernoulli Processes
		6.3 Concentration of Measure
		6.4 Sudakov Minoration
		6.5 Comparison Principle
		6.6 Control in ∞ Norm
		6.7 Peaky Parts of Functions
		6.8 Discrepancy Bounds for Empirical Processes
		6.9 Notes and Comments
	7 Random Fourier Series and Trigonometric Sums
		7.1 Translation-Invariant Distances
		7.2 Basics
			7.2.1 Simplification Through Abstraction
			7.2.2 Setting
			7.2.3 Upper Bounds in the Bernoulli Case
			7.2.4 Lower Bounds in the Gaussian Case
		7.3 Random Distances
			7.3.1 Basic Principles
			7.3.2 A General Upper Bound
			7.3.3 A Side Story
		7.4 The Marcus-Pisier Theorem
			7.4.1 The Marcus-Pisier Theorem
			7.4.2 Applications of the Marcus-Pisier Theorem
		7.5 Statement of Main Results
			7.5.1 General Setting
			7.5.2 Families of Distances
			7.5.3 Lower Bounds
			7.5.4 Upper Bounds
			7.5.5 Highlighting the Magic of Theorem 7.5.5
			7.5.6 Combining Upper and Lower Bounds
			7.5.7 An Example: Tails in u-p
			7.5.8 The Decomposition Theorem
			7.5.9 Convergence
		7.6 A Primer on Random Sets
		7.7 Proofs, Lower Bounds
		7.8 Proofs, Upper Bounds
			7.8.1 Road Map
			7.8.2 A Key Step
			7.8.3 Road Map: An Overview of DecompositionTheorems
			7.8.4  Decomposition Theorem in the Bernoulli Case
			7.8.5 Upper Bounds in the Bernoulli Case
			7.8.6 The Main Upper Bound
			7.8.7 Sums with Few Non-zero Terms
		7.9 Proof of the Decomposition Theorem
			7.9.1 Constructing Decompositions
			7.9.2 Proof of Proposition 7.9.1
		7.10 Proofs, Convergence
		7.11 Further Proofs
			7.11.1 Alternate Proof of Proposition 7.5.13
			7.11.2 Proof of Theorem 7.5.18
		7.12 Explicit Computations
		7.13 Vector-Valued Series: A Theorem of Fernique
		7.14 Notes and Comments
	8 Partitioning Scheme and Families of Distances
		8.1 The Partitioning Scheme
		8.2 Tail Inequalities
		8.3 The Structure of Certain Canonical Processes
	9 Peaky Part of Functions
		9.1 Road Map
		9.2 Peaky Part of Functions, II
		9.3 Philosophy
		9.4 Chaining for Bernoulli Processes
		9.5 Notes and Comments
	10 Proof of the Bernoulli Conjecture
		10.1 Latała\'s Principle
		10.2 Philosophy, I
		10.3 Chopping Maps and Functionals
			10.3.1 Chopping Maps
			10.3.2 Basic Facts
			10.3.3 Functionals
		10.4 Philosophy, II
		10.5 Latała\'s Step
		10.6 Philosophy, III
		10.7 A Decomposition Lemma
		10.8 Building the Partitions
		10.9 Philosophy, IV
		10.10 The Key Inequality
		10.11 Philosophy, V
		10.12 Proof of the Latała-Bednorz Theorem
		10.13 Philosophy, VI
		10.14 A Geometric Characterization of b(T)
		10.15 Lower Bounds from Measures
		10.16 Notes and Comments
	11 Random Series of Functions
		11.1 Road Map
		11.2 Random Series of Functions: General Setting
		11.3 Organization of the Chapter
		11.4 The Main Lemma
		11.5 Construction of the Majorizing Measure Using Convexity
		11.6 From Majorizing Measures to Partitions
		11.7 The General Lower Bound
		11.8 The Giné-Zinn Inequalities
		11.9 Proof of the Decomposition Theorem for EmpiricalProcesses
		11.10 The Decomposition Theorem for Random Series
		11.11 Selector Processes and Why They Matter
		11.12 Proving the Generalized Bernoulli Conjecture
		11.13 Notes and Comments
	12 Infinitely Divisible Processes
		12.1 Poisson r.v.s and Poisson Point Processes
		12.2 A Shortcut to Infinitely Divisible Processes
		12.3 Overview of Results
			12.3.1 The Main Lower Bound
			12.3.2 The Decomposition Theorem for Infinitely Divisible Processes
			12.3.3 Upper Bounds Through Bracketing
			12.3.4 Harmonizable Infinitely Divisible Processes
			12.3.5 Example: Harmonizable p-Stable Processes
		12.4 Proofs: The Bracketing Theorem
		12.5 Proofs: The Decomposition Theorem for Infinitely Divisible Processes
		12.6 Notes and Comments
	13 Unfulfilled Dreams
		13.1 Positive Selector Processes
		13.2 Explicitly Small Events
		13.3 My Lifetime Favorite Problem
		13.4 Classes of Sets
Part III Practicing
	14 Empirical Processes, II
		14.1 Bracketing
		14.2 The Class of Squares of a Given Class
		14.3 When Not to Use Chaining
	15 Gaussian Chaos
		15.1 Order 2 Gaussian Chaos
			15.1.1 Basic Facts
			15.1.2 When T Is Small for the Distance d∞
			15.1.3 Covering Numbers
			15.1.4 Another Way to Bound S(T)
			15.1.5 Yet Another Way to Bound S(T)
		15.2 Tails of Multiple-Order Gaussian Chaos
		15.3 Notes and Comments
	16 Convergence of Orthogonal Series: Majorizing Measures
		16.1 A Kind of Prologue: Chaining in a Metric Space and Pisier\'s Bound
		16.2 Introduction to Orthogonal Series: Paszkiewicz\'s Theorem
		16.3 Recovering the Classical Results
		16.4 Approach to Paszkiewicz\'s Theorem: Bednorz\'s Theorem
		16.5 Chaining, I
		16.6 Proof of Bednorz\'s Theorem
		16.7 Permutations
		16.8 Chaining, II
		16.9 Chaining, III
		16.10 Notes and Comments
	17 Shor\'s Matching Theorem
		17.1 Introduction
		17.2 The Discrepancy Theorem
		17.3 Lethal Weakness of the Approach
	18 The Ultimate Matching Theorem in Dimension 3
		18.1 Introduction
		18.2 Regularization of φ
		18.3 Discretization
		18.4 Discrepancy Bound
		18.5 Geometry
		18.6 Probability, I
		18.7 Haar Basis Expansion
		18.8 Probability, II
		18.9 Final Effort
	19 Applications to Banach Space Theory
		19.1 Cotype of Operators
			19.1.1 Basic Definitions
			19.1.2  Operators from ∞N
			19.1.3 Computing the Cotype-2 Constant with Few Vectors
		19.2 Unconditionality
			19.2.1 Classifying the Elements of B1
			19.2.2 Subsets of B1
			19.2.3 1-Unconditional Sequences and Gaussian Measures
		19.3 Probabilistic Constructions
			19.3.1 Restriction of Operators
			19.3.2 The Λ(p)-Problem
		19.4 Sidon Sets
A Discrepancy for Convex Sets
	A.1 Introduction
	A.2 Elements of Proof of the Upper Bound
	A.3 The Lower Bound
B Some Deterministic Arguments
	B.1 Hall\'s Matching Theorem
	B.2 Proof of Lemma 4.7.11
	B.3 The Shor-Leighton Grid Matching Theorem
	B.4 End of Proof of Theorem 17.2.1
	B.5 Proof of Proposition 17.3.1
	B.6 Proof of Proposition 17.2.4
C Classical View of Infinitely Divisible Processes
	C.1 Infinitely Divisible Random Variables
	C.2 Infinitely Divisible Processes
	C.3 Representation
	C.4 p-Stable Processes
D Reading Suggestions
	D.1 Partition Schemes
	D.2 Geometry of Metric Spaces
	D.3 Cover Times
	D.4 Matchings
	D.5 Super-concentration in the Sense of S. Chatterjee
	D.6 High-Dimensional Statistics
E Research Directions
	E.1 The Latała-Bednorz Theorem
	E.2 The Ultimate Matching Conjecture
	E.3 My Favorite Lifetime Problem
	E.4 From a Set to Its Convex Hull
F Solutions of Selected Exercises
G Comparison with the First Edition
Bibliography
Index