wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Disjoint Sets
        
(Message started by: Barukh on Dec 22^nd, 2013, 12:19am)

Title: Disjoint Sets
Post by Barukh on Dec 22^nd, 2013, 12:19am

Consider a set of N different values.

By randomly choosing elements from N, two subsets – A and B – are formed, so that |A|*|B| = N, and |A|, |B| > N^a for some constant a (e.g. their sizes depend on N).

What is the probability that A and B are disjoint, when N is big?

Title: Re: Disjoint Sets
Post by Michael Dagg on Dec 26^th, 2013, 8:58am

Comments...

Title: Re: Disjoint Sets
Post by Michael Dagg on Dec 26^th, 2013, 10:43am

I've thought of another way to see that the limiting
probability of 1/e is reasonable. Choose a random set A of
legal size (i.e. of size N^\alpha, where a < \alpha < 1-a). Then begin
constructing B by choosing random elements from S. At each choice,
the probability of choosing a member of A is N^(\alpha - 1). If we keep
track of the number of choices X that are members of A, then X is
Poisson distributed with parameters n = N^(1-\alpha) and p = N^(\alpha - 1).

Therefore, the probability of choosing no member of A is e^(-np) = 1/e. The only
reason this isn't exact is that when constructing B, we might choose an
element more than once. One can show that the expected number of elements
of S that are chosen more than once is quite small, so this shouldn't affect
the limiting probability.