Functional BKR Inequalities, and their Duals, with Applications

Larry Goldstein () and Yosef Rinott
Additional contact information
Larry Goldstein: University of Southern California
Yosef Rinott: Hebrew University of Jerusalem

Journal of Theoretical Probability, 2007, vol. 20, issue 2, 275-293

Abstract: Abstract The inequality conjectured by van den Berg and Kesten (J. Appl. Probab. 22, 556–569, 1985), and proved by Reimer (Comb. Probab. Comput. 9, 27–32, 2000), states that for A and B events on S, a finite product of finite sets, and P any product measure on S, $$P(A\Box B)\le P(A)P(B),$$ where the set A□B consists of 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 inequality having the following formulation. Let X be a random vector with n independent components, each in some space S i (such as R d ), and set S=∏ i=1 n S i . Say that the function f:S→R depends on K⊆{1,…,n} if f(x)=f(y) whenever x i =y i for all i∈K. Then for any given finite or countable collections of non-negative real valued functions $\{f_{\alpha}\}_{\alpha \in \mathcal{A}},\,\{g_{\beta}\}_{\beta \in \mathcal{B}}$ on S, depending on $K_{\alpha},\alpha \in \mathcal{A}$ and L β ,β∈ℬ respectively, $$E\Bigl\{\sup_{K_{\alpha}\cap L_{\beta}=\emptyset}f_{\alpha}(\mathbf{X})g_{\beta}(\mathbf{X})\Bigr\}\leq E\Bigl\{\sup_{\alpha}f_{\alpha}(\mathbf{X})\Bigr\}E\Bigl\{\sup_{\beta}g_{\beta}(\mathbf{X})\Bigr\}.$$ Related formulations, and functional versions of the dual inequality on events by Kahn, Saks, and Smyth (15th Annual IEEE Conference on Computational Complexity 98–103, IEEE Computer Soc., Los Alamitos, CA, 2000), are also considered. Applications include order statistics, assignment problems, and paths in random graphs.

Keywords: Graphs and paths; Positive dependence; Order statistics (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-007-0068-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:20:y:2007:i:2:d:10.1007_s10959-007-0068-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-007-0068-z

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().