The BK inequality for pivotal sampling a.k.a. the Srinivasan samplig process

Johan Jonasson (Chalmers University of Technology)

Abstract


The pivotal sampling algorithm, a.k.a. the Srinivasan sampling process, is a simply described recursive algorithm for sampling from a finite population a fixed number of items such that each item is included in the sample with a prescribed desired inclusion probability.The algorithm has attracted quite some interest in recent years due to the fact that despite its simplicity, it has been shown to satisfy strong properties of negative dependence, e.g. conditional negative association.In this paper it is shown that (tree-ordered) pivotal/Srinivasan sampling also satisfies the BK inequality.This is done via a mapping from increasing sets of samples to sets of match sequencesand an application of the van den Berg-Kesten-Reimer inequality.The result is one of only very few non-trivial situations where the BK inequality is known to hold.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-6

Publication Date: May 16, 2013

DOI: 10.1214/ECP.v18-2045

References

  • J. van den Berg and A. Gandolfi (2012), BK-type inequalities and generalized random-cluster representations. Available at http://arxiv.org/pdf/1203.3665v1.pdf
  • van den Berg, J. Sharpness of the percolation transition in the two-dimensional contact process. Ann. Appl. Probab. 21 (2011), no. 1, 374--395. MR2778387 http://arxiv.org/pdf/1105.3862.pdf
  • van den Berg, J.; Kesten, H. Inequalities with applications to percolation and reliability. J. Appl. Probab. 22 (1985), no. 3, 556--569. MR0799280
  • Borcea, Julius; Brändén, Petter; Liggett, Thomas M. Negative dependence and the geometry of polynomials. J. Amer. Math. Soc. 22 (2009), no. 2, 521--567. MR2476782
  • Jonasson, Johan. Mixing time bounds for overlapping cycles shuffles. Electron. J. Probab. 16 (2011), no. 46, 1281--1295. MR2827459
  • Dubhashi, Devdatt; Jonasson, Johan; Ranjan, Desh. Positive influence and negative dependence. Combin. Probab. Comput. 16 (2007), no. 1, 29--41. MR2286510
  • Dubhashi, Devdatt; Ranjan, Desh. Balls and bins: a study in negative dependence. Random Structures Algorithms 13 (1998), no. 2, 99--124. MR1642566
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Markström, Klas. Closure properties and negatively associated measures violating the van den Berg-Kesten inequality. Electron. Commun. Probab. 15 (2010), 449--456. MR2726091
  • Pemantle, Robin. Towards a theory of negative dependence. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. J. Math. Phys. 41 (2000), no. 3, 1371--1390. MR1757964
  • Reimer, David. Proof of the van den Berg-Kesten conjecture. Combin. Probab. Comput. 9 (2000), no. 1, 27--32. MR1751301
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.