Functional BRK Inequalities, and their Duals, with Applications

Larry Goldstein
Yosef Rinott

The inequality conjectured by van den Berg and Kesten in [9], and proved by Reimerin [6], states that for A and B events on S, a product of finitely many finite sets, and P any product measure on S, P(AοB) ≤ P(A)P(B), where AοB are the elementary events which lie in both A and B for `disjoint reasons.' This inequality on events is the special case, for indicator functions, of the inequalityhaving the following formulation. Let X be a random vector with n independent components, each in some space Si (such asℜd), and set S = ∏ni=1Si. Say that the function f : S →ℜdepends on K ⊂ {1,...,n} if f(x) = f(y) whenever xi = yi for all i ∈ K. Then for any given finite or countable collections of non-negative real valued functions {fα}α∈A, {gβ}β∈B on S which depend on Kα and Lβ respectively,E{supKα∩Lβ=∅ fα(X) gβ(X)} ≤ E{sup fα(X)} E{sup gβ(X)}. Related formulations, and functional versions of the dual inequality on events by Kahn,Saks, and Smyth [4], are also considered. Applications include order statistics, assignment problems, and paths in random graphs.

November, 2004
Published in: 
Journal of Theoretical Probability 20, 275-293 (2007)