Functional van den Berg-Kesten-Reimer Inequalities and their Duals, with Applications

arXiv1508.07267MaRDI QIDQ6264936

Yosef Rinott, Larry Goldstein

Publication date: 28 August 2015

Abstract: The BKR inequality conjectured by van den Berg and Kesten in [11], and proved by Reimer in [8], states that for $A$ and $B$ events on $S$, a finite product of finite sets $S_i,i=1,ldots,n$, and $P$ any product measure on $S$, ${\displaystyle }$ P(A Box B) le P(A)P(B),${\displaystyle }$ where the set $ABoxB$ consists of the elementary events which lie in both $A$ and $B$ for `disjoint reasons.' Precisely, with $$ and $$, for $$ letting $$, the set $ABoxB$ consists of all $$ for which there exist disjoint subsets $K$ and $L$ of $$ for which $$ and $$. The BKR inequality is extended to the following functional version on a general finite product measure space $(S,mathbbS)$ with product probability measure $P$, ${\displaystyle }$Eleft{ max_{stackrel{K cap L = emptyset}{K subset {�f n}, L subset {�f n}}} underline{f}_K({�f X})underline{g}_L({�f X}) ight} leq Eleft{f({�f X}) ight},Eleft{g({�f X}) ight},${\displaystyle }$ where $f$ and $g$ are non-negative measurable functions, $$ and $$ The original BKR inequality is recovered by taking $$ and $$, and applying the fact that in general $$. Related formulations, and functional versions of the dual inequality on events by Kahn, Saks, and Smyth [6], are also considered. Applications include order statistics, assignment problems, and paths in random graphs.

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15)

This page was built for publication: Functional van den Berg-Kesten-Reimer Inequalities and their Duals, with Applications