### Sidebar

seminars:comb:abstract.201004bro

# Negative Dependence of Srinivasan's Subset Sampling Processes

## Abstract for the Combinatorics Seminar 2010 April 27

Suppose we want a random k-element subset of {1,2,…,n}, chosen with probabilities such that the probability of its containing i is a predetermined number pi (we say the process has “prescribed marginals”). Srinivasan's sampling processes (SSPs) are random processes which satisfy these requirements. Dubhashi, Jonasson, and Ranjan study the ways in which choosing a set that contains some elements may reduce the probability that it contains some other elements (this ill-defined phenomenon is called “negative dependence”). In particular, they prove that linear SSPs have conditional negative association (which is one candidate for a precise definition of negative dependence), by using a theorem of Feder and Mihail and a coupling argument.

We consider a broader class of SSPs that we call “tournament SSPs” (TSSPs). These have a tree-like structure. We prove that they also 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. (“Conditioned” means one computes probabilities assuming certain restrictions on the outcomes.) 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.

This is joint work with Jamie Radcliffe (University of Nebraska - Lincoln) and Jon Cutler (Montclair State).