Combinatorics, Probability and Computing



Paper

Positive Influence and Negative Dependence


DEVDATT DUBHASHI a1 1 , JOHAN JONASSON a2 2 and DESH RANJAN a3 3 4
a1 Department of Computing Science, Chalmers University of Technology, SE 412 96 Göteborg, Sweden (e-mail: dubhasi@cs.chalmers.se)
a2 Department of Mathematics, Chalmers University of Technoloy, SE 412 96 Göteborg, Sweden (e-mail: jonasson@math.chalmers.se)
a3 Department of Computer Science, New Mexico State University, Las Cruces, New Mexico 88003, USA (e-mail: dranjan@cs.nmsu.edu)

Article author query
dubhashi d   [Google Scholar] 
jonasson j   [Google Scholar] 
ranjan d   [Google Scholar] 
 

Abstract

We study negative dependence properties of a sampling process due to Srinivasan to produce distributions on level sets with given marginals. We give a simple proof that the distribution satisfies negative association. We also show that under a linear match schedule it satisfies the stronger condition of conditional negative association via a non-trivial application of the Feder–Mihail theorem. This method involves the notion of a variable of positive influence. We give some results and related counter-examples which might shed some light on its role in a theory of negative dependence.

(Received June 30 2004)
(Revised July 6 2005)



Footnotes

1 Work done partly while the author was visiting BRICS.

2 Work supported by the Swedish Research Council.

3 Work done partly while the author was visiting the Max–Planck–Institut für Informatik and BRICS.

4 Work partially supported by the ESPRIT Basic Research Actions Program of the EC under contract No. 7141 (project ALCOM II).