wu :: forums « wu :: forums - Disjoint Sets » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 4:10am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: towr, william wu, Grimbal, Icarus, SMQ, Eigenray)    Disjoint Sets « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Disjoint Sets  (Read 3948 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
 Re: Disjoint Sets   ocfwu1.JPG « Reply #1 on: Dec 26th, 2013, 8:58am » Quote Modify

 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »