Abstract
A maximal inequality seeks to estimate the expected maximum of a collection of random variables, $\mathbb{E}\max_i X_i$, based on the properties of the individual $X_i$. While the union bound provides tight estimates for independent variables, it often becomes overly pessimistic when strong dependencies are present. This paper demonstrates that for non-negative random variables, pairwise independence is sufficient to ensure that the maximal inequality behaves similarly to its independent counterpart. We further show that this condition can be relaxed to negative dependence or even quantified violations of negative dependence.
Introduction
In machine learning theory and empirical process theory, a recurring challenge is bounding the "worst-case" outcome of a set of random variables $X_1, \dots, X_n$. Specifically, we are interested in the expected maximum $\mathbb{E} \max_i X_i$. When these variables are independent, the union bound and related concentration inequalities provide sharp upper bounds. However, in many practical applications, variables exhibit significant correlation.
If variables are perfectly dependent (e.g., $X_1 = X_2 = \dots = X_n$), the maximum is simply the expectation of a single variable. In contrast, a naive application of the union bound would suggest the maximum grows with $n$. To bridge this gap, this research explores "decoupling"—the process of bounding the maximum of a dependent set of variables using the maximum of its "independent version" (a set $\tilde{X}_1, \dots, \tilde{X}_n$ with the same marginal distributions but no correlation).
Theoretical Framework
The Bernoulli Case
The analysis begins with the simplest case: Bernoulli (0 or 1) random variables. Using the Paley-Zygmund inequality, it can be shown that if a set of Bernoulli variables is pairwise independent, the probability that at least one variable equals 1 is at least half the probability that would be observed if the variables were fully independent. This provides the foundational constant for the subsequent lower bounds.
The Layer Cake Representation
To extend results from binary outcomes to general non-negative real-valued variables, the paper employs the Layer Cake representation: $$\mathbb{E}[X] = \int_0^\infty \mathbb{P}(X > t) dt$$ By expressing the expectation as an integral of tail probabilities, the results derived for Bernoulli trials (which represent the probability of exceeding a threshold $t$) can be integrated to cover continuous expectations.
Key Results
The paper establishes two primary bounds that "sandwich" the behavior of the maximum of dependent variables relative to their independent counterparts.
1. The Upper Bound
For any collection of non-negative integrable random variables, the expected maximum is bounded by: $$\mathbb{E} \max X_i \leq \frac{e}{e-1} \mathbb{E} \max \tilde{X}_i$$ This result, building on work by Pinelis, shows that the dependent maximum is never more than approximately $1.58$ times the independent maximum, regardless of the dependency structure.
2. The Lower Bound
If the variables are at least pairwise independent, a new lower bound is established: $$\mathbb{E} \max X_i \geq \frac{1}{2} \mathbb{E} \max \tilde{X}_i$$ This confirms that pairwise independence is a powerful enough condition to keep the expected maximum within a factor of 2 of the fully independent case.
Relaxing Independence
The requirement of pairwise independence is not a hard limit. The paper demonstrates that these bounds remain valid under negative pairwise covariance, where variables are less likely to be large simultaneously than they would be under independence. Furthermore, the author introduces a framework to quantify violations of negative covariance, allowing for generalized bounds even when some positive correlation exists.
Discussion and Future Work
Optimal Constants
While the lower bound constant is proven to be $1/2$, the author conjectures that this is conservative. Based on the symmetry of the problem, the true optimal constant may be $\frac{e}{2(e-1)} \approx 0.79$. Proving this tighter bound remains an open theoretical challenge.
Connections to Prophet Inequalities
There is a notable conceptual link between these maximal inequalities and "prophet inequalities" in optimal stopping theory. Both fields address the gap between different levels of information or dependency when selecting the best outcome from a sequence of random variables.
Limitations
The current results are restricted to non-negative variables. Extending these decoupling techniques to variables that can take negative values—such as those found in Gaussian processes—is a significant direction for future research. Additionally, exploring specific dependency structures like Markov chains could yield even more refined bounds.
Summary updated