My Math Forum The P of the # of two random sets

 Probability and Statistics Basic Probability and Statistics Math Forum

 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 n-1, then n-2 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 n-degree 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$ Thanks from Omne Bonum

 Tags random, sets

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Luiz Topology 3 July 15th, 2015 05:31 AM fienefie Real Analysis 6 February 24th, 2015 02:14 PM messaoud2010 Probability and Statistics 1 July 18th, 2014 11:26 AM Jamsisos Advanced Statistics 1 June 21st, 2012 01:11 PM SummerWinterXYZ Advanced Statistics 2 March 11th, 2012 07:06 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top