Author 
Topic: Disjoint Sets (Read 3958 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Disjoint Sets
« on: Dec 22^{nd}, 2013, 12:19am » 
Quote Modify

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?


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500

Comments...


IP Logged 
Regards, Michael Dagg



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Disjoint Sets
« Reply #2 on: Dec 26^{th}, 2013, 10:43am » 
Quote Modify

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 < 1a). 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.

« Last Edit: Dec 26^{th}, 2013, 10:43am by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



