Abstract
The BK inequality (van den Berg and Kesten in J Appl Probab 22:556–569, 1985) says that, for product measures on {0, 1}n, the probability that two increasing events A and B ‘occur disjointly’ is at most the product of the two individual probabilities. The conjecture in van den Berg and Kesten (1985) that this holds for all events was proved by Reimer (Combin Probab Comput 9:27–32, 2000). Several other problems in this area remained open. For instance, although it is easy to see that non-product measures cannot satisfy the above inequality for all events, there are several such measures which, intuitively, should satisfy the inequality for all increasing events. One of the most natural candidates is the measure assigning equal probabilities to all configurations with exactly k 1’s (and probability 0 to all other configurations). The main contribution of this paper is a proof for these measures. We also point out how our result extends to weighted versions of these measures, and to products of such measures.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Borcea J., Brändén P., Liggett T.M.: Negative dependence and the geometry of polynomials. J. Am. Math. Soc. 22, 521–567 (2009)
Borgs, C., Chayes, J.T., Randall, D.: The van den Berg-Kesten-Reimer inequality: a review. In: Bramson, M., Durrett, R. (eds.) Perplexing Problems in Probability (Festschrift in honor of Harry Kesten), pp. 159–175 (1999)
Brändén P.: Polynomials with the half-plane property and matroid theory. Adv. Math. 216, 302–320 (2007)
Brändén, P., Jonasson, J.: Negative dependence in sampling. Preprint. http://www.math.chalmers.se/jonasson/recent.html (2011)
Dubhashi D., Jonasson J., Ranjan D.: Positive influence and negative dependence. Combin. Probab. Comput. 16, 29–41 (2007)
Dubhashi D., Ranjan D.: Balls and bins: a study in negative dependence. Random Struct. Alg. 13, 99–124 (1998)
Grimmett, G.R.: Percolative problems. In: Grimmett, G.R. (ed.) Probability and Phase Transition, pp. 69–86. Kluwer, Dordrecht (1994)
Grimmett G.R.: Percolation, 2nd edn. Springer, Berlin (1999)
Grimmett, G.R.: Probability on graphs. In: IMS Textbooks. Cambridge University Press (2010)
Kahn J., Neiman M.: Negative correlation and log-concavity. Random Struct. Alg. 37, 367–388 (2010)
Markström K.: Closure properties and negatively associated measures violating the van den Berg-Kesten inequality. Elect. Comm. Probab. 15, 449–456 (2009)
Pemantle R.: Towards a theory of negative dependence. J. Math. Phys. 41, 1371–1390 (2000)
Reimer D.: Proof of the Van den Berg-Kesten conjecture. Combin. Probab. Comput. 9, 27–32 (2000)
Talagrand, M.: Some remarks on the Berg-Kesten inequality. In: Probability in Banach Spaces, vol. 9, pp. 293–297. Birkhäuser, Boston (1994)
van den Berg J., Kesten H.: Inequalities with applications to percolation and reliability. J. Appl. Probab. 22, 556–569 (1985)
van den Berg J., Fiebig U.: On a combinatorial conjecture concerning disjoint occurrences of events. Ann. Probab. 15, 354–374 (1987)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
van den Berg, J., Jonasson, J. A BK inequality for randomly drawn subsets of fixed size. Probab. Theory Relat. Fields 154, 835–844 (2012). https://doi.org/10.1007/s00440-011-0386-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-011-0386-z