Author |
Topic: Disjoint Sets (Read 3949 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Disjoint Sets
« on: Dec 22nd, 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| > Na 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 26th, 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 < 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.
|
| « Last Edit: Dec 26th, 2013, 10:43am by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print