wu :: forums
« wu :: forums - Disjoint Sets »

Welcome, Guest. Please Login or Register.
Nov 26th, 2021, 4:15pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, Grimbal, towr, SMQ, william wu, Eigenray)
   Disjoint Sets
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Disjoint Sets  (Read 3898 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Disjoint Sets  
« on: Dec 22nd, 2013, 12:19am »
Quote Quote Modify 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: male
Posts: 500
Re: Disjoint Sets   ocfwu1.JPG
« Reply #1 on: Dec 26th, 2013, 8:58am »
Quote Quote Modify Modify

Comments...
IP Logged


Regards,
Michael Dagg
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Disjoint Sets  
« Reply #2 on: Dec 26th, 2013, 10:43am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board