
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 27th, 2017, 10:31 PM  #1 
Newbie Joined: Oct 2017 From: Hanoi Posts: 4 Thanks: 1  The P of the # of two random sets
I found this question a satisfying challenge, so I hope I got it right! "Let X be a set containing n elements. If two subsets A and B are picked at random, what would be the probability that they are both the same size?" So, basically what is the probability that the cardinality of the two sets (which I indicate with #) is the same, so P(#A=#B), if that is the correct notation. I assumed that the empty set was considered a subset of X because not including it made my brain hurt. So, the probability space is made up of all the subsets of X of any length from 1 to n, bearing in mind that the empty set has a cardinality of 0, but I am counting it as one of the sets that might be randomly picked. By brute force I figured the total number of sets, irrespective of cardinality, by taking examples: n=3 empty set, {1}, {2}, {3}, {12}, {13}, {23}, {123} Total, 8 sets n=2 empty set, {1}, {2}, {12} Total, 4 sets n=1 empty set, {1} Total, 2 sets n=0 empty set Total, 1 set So it is plain to see that total sets will always equal 2^n, and number of possible pairs of sets, irrespective of length, would be 2^n choose 2. So that is my denominator. Now what we need to know is, for each cardinality, starting with n, then n1, then n2 on to 0, how many subsets of n have that card? So, for n=3, number of sets #3=1, #2=3, #1=3, #0=1. More brute force for n=2, n=4, etc., makes it clear we are dealing with Pascal's Triangle and all of them lovely binomial coefficients. Each of these coefficients is represented by n choose k for k=0 to k=n. So the number of pairs of sets with the same cardinality that might possibly be picked is the sum of the possible pairs from each of the binomial coefficients of an ndegree polynomial, so the sum of (n choose k) choose 2. So that is the (sum from k=0 to n of (n choose k) choose 2))/ (2^n choose 2). If that makes sense. Can't we use Latex on this interface? Okay. Now I'm too tired to think. 
October 28th, 2017, 09:20 AM  #2 
Senior Member Joined: Sep 2015 From: USA Posts: 2,100 Thanks: 1093 
you're close but not quite right. the actual answer is $\dfrac{\displaystyle \sum_{k=0}^n~\dbinom{n}{k}^2}{2^{2n}}$ see if you can puzzle out why. Remember you have two independent sets to choose from, each of size $n$ 

Tags 
random, sets 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Open sets and closed sets  Luiz  Topology  3  July 15th, 2015 05:31 AM 
Open Sets and Closed Sets  fienefie  Real Analysis  6  February 24th, 2015 02:14 PM 
Theory and Problems of Probability, Random Variables, and Random Processes  messaoud2010  Probability and Statistics  1  July 18th, 2014 11:26 AM 
minor sets sets problem  Jamsisos  Advanced Statistics  1  June 21st, 2012 01:11 PM 
Add the variances of 2 sets of independent random variables?  SummerWinterXYZ  Advanced Statistics  2  March 11th, 2012 07:06 PM 