My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum

Thanks Tree1Thanks
  • 1 Post By romsek
LinkBack Thread Tools Display Modes
October 27th, 2017, 10:31 PM   #1
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.
Omne Bonum is offline  
October 28th, 2017, 09:20 AM   #2
Senior Member
romsek's Avatar
Joined: Sep 2015
From: USA

Posts: 1,979
Thanks: 1027

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
romsek is online now  

  My Math Forum > High School Math Forum > Probability and Statistics

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

Copyright © 2018 My Math Forum. All rights reserved.