Maximal Inequalities via Concentration
Suppose each variable has a small tail probability. How large can the maximum of many of them be? A union bound already gives a useful answer for a finite collection, and exponential moments turn the number of variables into a logarithmic cost. We then approximate an infinite index set by a finite cover and estimate the error between nearby indices.
Let \(X_1,\ldots,X_n\) be i.i.d. with law \(P\). For a function \(f\), write \(Pf=\mathbb{E} f(X_1)\), \(P_nf=n^{-1}\sum_{i=1}^n f(X_i)\), and \(\mathbb G_nf=\sqrt n(P_n-P)f\). Rademacher variables are independent random signs, independent of the observations. See the empirical-process setup for measurability conventions.
1. Random variables
As we did in the discussion of concentration inequalities of random variables, consider a sequence of random variables \(X_1, \dots, X_n\), which neither need to be independent nor identically distributed. We are interested in the behaviour of the supremum of these random variables. For a start, consider the finite case, and suppose we know \(\mathbb{E} |X_i|^p < \infty\) for some \(p \geq 1\) and for all \(i\). Then, Hölder’s inequality tells us
A fixed moment bound can grow rapidly with the size of the collection. Exponential moments can give a smaller dependence on that size. To this end, we have seen Proposition 5 of the concentration-inequalities note, which allows us to understand the supremum of random variables when we have a property based on an increasing function available to us. The following result adapts Proposition 5 slightly.
Lemma 1 (Orlicz). For all \(i\), suppose \(\mathbf P\,\,\!\!(|X_i| > t) \leq K_i e^{-D_i t^p}\) for some \(K_i, D_i > 0\) and \(p \geq 1\). Let \(\psi_p (z) = e^{z^p} - 1\). Then,
where \(C_i = (\frac{1+K_i}{D_i})^{\frac1p}\). From this, we have
Proof. By direct calculations,
take the stated value of \(C_i\) so that \(D_i C_i^p-1=K_i\). To get the maximal bound, let \(C=\max_i C_i\). Jensen and monotonicity yield
Apply \(\psi_p^{-1}(n)=(\log(1+n))^{1/p}\). The exponential tail assumptions guarantee integrability, and no independence is used. ◻
Lemma 2. Let \(X_1, \dots, X_n\) be random variables satisfying the condition
for nonnegative constants \(a,b\) and all positive \(z\). Then,
Proof. Put \(L=\log(2n)\) and \(t(u)=2au+\sqrt{2bu}\). Direct expansion gives \(t(u)^2\ge2u(at(u)+b)\). The union bound therefore yields
Integrating this bound with the change of variables \(t=t(L+v)\),
Since \(L\ge\log2\), this is bounded by a universal constant times \(a\log(1+n)+\sqrt{b\log(1+n)}\). The cases \(a=0\) or \(b=0\) follow by the same calculation, and the zero-proxy case forces all variables to vanish almost surely. □
2. Stochastic processes
Separate from the ideas above, we can develop tools to understand the supremum of a random process. For a set \(T\), we can always write
for random variables \(\{X_t\}_{t \in T}\). Here, let’s say the set \(T\) is finite. Combining this union bound with the Chernoff bound gives control at a threshold determined by the log moment generating function and the logarithm of the size of the index set. The following discussion expands on Proposition 4 of the concentration-inequalities note, which should be seen as a special case of the following result.
Proposition 3 (Maximal inequality). Let \(T\) be finite and nonempty, and let the \(X_t\) be integrable. Suppose \(\psi:[0,\infty)\to[0,\infty)\) is finite and convex with \(\psi(0)=\psi'_+(0)=0\), and \(\log\mathbb{E}e^{\lambda X_t}\le\psi(\lambda)\) for every \(t\in T\) and \(\lambda\ge0\). Define
Then \(\mathbb{E}\max_{t\in T}X_t\le b(\log|T|)\). The function \(b\) is the generalized inverse \(\sup\{x\ge0:\psi^*(x)\le u\}\); no strict monotonicity of \(\psi^*\) is needed.
Proof. For any \(\lambda>0\), Jensen and the finite sum bound give
Taking the infimum proves the bound. For the inverse identity, observe that for \(x\ge0\),
Thus the sublevel set is exactly \([0,b(u)]\). If the conjugate is continuous and strictly increasing onto \([0,\infty)\), this generalized inverse agrees with its ordinary inverse. Degenerate proxies, such as \(\psi=0\), are also covered. □
Corollary 4. Under the assumptions of Proposition 3, for every \(\eta\ge0\),
If \(\psi^*(b(u))\ge u\) at \(u=\log|T|+\eta\), the strict inequality in the event may be replaced by a non-strict one.
Proof. Chernoff's inequality and the union bound give \(\Pr\{\max_tX_t\ge x\}\le\exp(\log|T|-\psi^*(x))\). If \(x>b(u)\), the inverse characterization gives \(\psi^*(x)>u\). Let \(x\downarrow b(u)\) to obtain the strict-tail statement. The additional condition permits direct substitution at the endpoint. Without it, the non-strict statement can fail: if every \(X_t=0\) and \(\psi=0\), then \(b(u)=0\) for all \(u\). □
Remark 5. For independent centered Gaussian variables with a common positive variance, the expected maximum has order the square root of the logarithm of the number of variables. Thus the logarithmic dependence in these bounds cannot be improved in general; independence alone does not imply sharpness for every family.
For the Gaussian order claim, write \(X_i=\sigma Z_i\) with independent standard normals. For \(u\geq1\), integrating the density over \([u,u+1/u]\) gives \(\mathbb P(Z_1>u)\geq c e^{-u^2/2}/u\) for an absolute \(c>0\). At \(u=\sqrt{\log n}\), independence yields \(\mathbb P(\max_iZ_i\leq u)\leq\exp\{-n\mathbb P(Z_1>u)\}\to0\). Also \((\max_iZ_i)_-\leq(Z_1)_-\), whose expectation is finite. Hence the expected maximum is bounded below by a constant times \(\sqrt{\log n}\) for large \(n\); the subgaussian maximal inequality gives the matching upper order. For Brownian motion, reflection gives \(\sup_{0\leq s\leq t}B_s\) the law of \(|B_t|\); integrating the normal density gives its mean \(\sqrt{2t/\pi}\).
In general, absent any assumptions, the maximal inequalities above present trivial bounds on the behaviour of the supremum of random variables. Furthermore, for general stochastic processes, calculating \(\mathbb{E} \sup_{t \in T} \: X_t\) is very nontrivial. In a special case, such as when \(\{X_t\}_{t \in T}\) is a standard Brownian motion, then the reflection principle tells us \(\mathbb{E} \sup_{0 \leq t \leq \overline t}X_t = \sqrt{\frac{2 \overline t}{\pi}}\) for every \(\overline t > 0\). So, we generally investigate the problem of bounding the expectation of the supremum of a stochastic process. To begin making some progress, we can appeal to a straightforward restriction on the collection \(\{X_t\}_{t \in T}\), called the Lipschitz property. We say a random process \(\{X_t\}_{t \in T}\) is Lipschitz for a metric \(d\) on \(T\) if there exists a random variable \(C\) such that
Choose a finite cover. The supremum is bounded by the largest value at its centers plus the Lipschitz error incurred when moving to a center. This gives the following inequality.
Lemma 6. Let \((T,d)\) be a nonempty totally bounded metric space, and let \(X_t\) be a process satisfying, on one event of probability one, \(|X_t-X_s|\leq C d(t,s)\) for all \(s,t\), where \(C\geq0\) and \(\mathbb EC<\infty\). Suppose \(\mathbb E e^{\lambda X_t}\leq e^{\lambda^2\sigma^2/2}\) for all real \(\lambda\) and all \(t\in T\), with \(\sigma\geq0\). In this lemma covering centers are required to belong to \(T\). Then
Proof. Fix a finite \(\eta\)-cover with centers \(t_1,\ldots,t_N\in T\). For every \(t\), choose a center at distance at most \(\eta\); the common Lipschitz event gives \(X_t\leq\max_jX_{t_j}+C\eta\), simultaneously in \(t\). Taking expectations and applying the finite subgaussian maximum bound proves the inequality for this \(\eta\). Take a smallest cover and then the infimum over \(\eta>0\). Total boundedness supplies a countable dense set; continuity of the Lipschitz paths makes the supremum equal almost surely to the supremum over this set, so it is measurable after completion. The same cover bound and any fixed coordinate show its integrability. ◻
We can then build on these tools if we wish to relax the requirement of the Lipschitz process. Specifically, in practical scenarios, the increments \(|X_t - X_s|\) are fluctuating for all pairs \(s,t\), with some (or most) being smaller than that in the worst-case scenario. A single global Lipschitz constant may overestimate most increments. Controlling increments at several distances leads to the chaining estimates developed later.