Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T18:30:48.906Z Has data issue: false hasContentIssue false
  • English
  • Français

Negative Dependence and Srinivasan's Sampling Process

Published online by Cambridge University Press:  22 February 2011

JOSH BROWN KRAMER ,
JONATHAN CUTLER  and
A. J. RADCLIFFE
JOSH BROWN KRAMER
Affiliation:
Department of Mathematics and Computer Science Department, Illinois Wesleyan University, Bloomington, IL, USA (e-mail: [email protected])
JONATHAN CUTLER
Affiliation:
Department of Mathematical Sciences, Montclair State University, Montclair, NJ, USA (e-mail: [email protected])
A. J. RADCLIFFE
Affiliation:
Department of Mathematics, University of Nebraska–Lincoln, Lincoln, NE, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Dubhashi, Jonasson and Ranjan Dubhashi, Jonasson and Ranjan (2007) study the negative dependence properties of Srinivasan's sampling processes (SSPs), random processes which sample sets of a fixed size with prescribed marginals. In particular they prove that linear SSPs have conditional negative association, by using the Feder–Mihail theorem and a coupling argument. We consider a broader class of SSPs that we call tournament SSPs (TSSPs). These have a tree-like structure and we prove that they have conditional negative association. Our approach is completely different from that of Dubhashi, Jonasson and Ranjan. We give an abstract characterization of TSSPs, and use this to deduce that certain conditioned TSSPs are themselves TSSPs. We show that TSSPs have negative association, and hence conditional negative association. We also give an example of an SSP that does not have negative association.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 3 , May 2011 , pp. 347 - 361
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Dubhashi, D., Jonasson, J. and Ranjan, D. (2007) Positive influence and negative dependence. Combin. Probab. Comput. 16 29–41.CrossRefGoogle Scholar
[2]Dubhashi, D. and Ranjan, D. (1998) Balls and bins: A study in negative dependence. Random Struct. Alg. 13 99–124.3.0.CO;2-M>CrossRefGoogle Scholar
[3]Feder, T. and Mihail, M. (1992) Balanced matroids. In STOC '92: Proc. 24th Annual ACM Symposium on Theory of Computing (New York), ACM, pp. 26–38.CrossRefGoogle Scholar
[4]Grimmett, G. R. and Winkler, S. N. (2004) Negative association in uniform forests and connected graphs. Random Struct. Alg. 24 444–460.CrossRefGoogle Scholar
[5]Joag-Dev, K. and Proschan, F. (1983) Negative association of random variables, with applications. Ann. Statist. 11 286–295.CrossRefGoogle Scholar
[6]Pemantle, R. (2000) Towards a theory of negative dependence. J. Math. Phys. 41 1371–1390.CrossRefGoogle Scholar
[7]Reimer, D. (2000) Proof of the van den Berg–Kesten conjecture. Combin. Probab. Comput. 9 27–32.Google Scholar
[8]Semple, C. and Welsh, D. (2008) Negative correlation in graphs and matroids. Combin. Probab. Comput. 17 423–435.CrossRefGoogle Scholar
[9]Srinivasan, A. (2001) Distributions on level-sets with applications to approximation algorithms. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas 2001), IEEE Computer Society Press, pp. 588–597.CrossRefGoogle Scholar
[10]van den Berg, J. and Kesten, H. (1985) Inequalities with applications to percolation and reliability. J. Appl. Probab. 22 556–569.CrossRefGoogle Scholar