Abstract:

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$\pm$$\pm$ˆˆA, g²²ˆˆB on S which depend on K$\pm$ and L² respectively,EsupK$\pm$ˆ\copyrightL²=ˆłdots} f$\pm$(X) g²(X) Esup f$\pm$(X) Esup 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.

Website