Author |
Topic: Set P contains n elements (Read 13479 times) |
|
navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender: 
Posts: 28
|
 |
Set P contains n elements
« on: Apr 12th, 2019, 9:43am » |
 Quote  Modify
|
A set P contains n elements. A subset A of set P is chosen at random. Set P is reconstructed by replacing the elements of A. Another subset B is chosen at random. Find the probability that A[intersection]B has exactly m(m<n) elements common.
|
| « Last Edit: Apr 12th, 2019, 9:44am by navdeep1771 » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2874
|
|
Re: Set P contains n elements
« Reply #1 on: Apr 17th, 2019, 6:15am » |
Quote Modify
|
I don't have a closed form, but, if p is the probability that |A[intersection]B|=m where A and B are uniformly and independently chosen from the 2n subsets of P, I get: p=n!/{m!*2^(2n)}*SUMk=mn2^(n-k)/{(n-k)!*(k-m)!}
Reasoning:
| hidden: |
For A to have k elements, with m<=k<=n, there are nCk such sets A.
For each such A, there are kCm subsets of size m that could be overlaps.
For each such overlap, the inclusion or exclusion of the k elements of A in B are fixed, while the remaining n-k elements of P can be in or out freely, giving 2n-k possible Bs for each possible overlap.
Combining it all gives the number of pairs of sets A and B with an intersection of size exactly m and set A having size exactly k as:
nCk*kCm*2n-k
=n!/{k!(n-k)!}*k!/{m!(k-m)!}*2n-k
=2n-k*n!/{m!(k-m)!(n-k)!}
So the total number of pairs of sets A and B with an intersection of size exactly m is:
SUMk=mn[2n-kn!/{m!(k-m)!(n-k)!}]
=n!/m!SUMk=mn2n-k/{(k-m)!(n-k)!}
And there are 2n possibilities for each of A and B independently, giving 22n equally likely possible pairs of A and B, and a final probability of:
n!/{m!*2^(2n)}*SUMk=mn2^(n-k)/{(n-k)!*(k-m)!}
|
|
| « Last Edit: Apr 17th, 2019, 6:16am by rmsgrey » |
IP Logged |
|
|
|
navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender:
Posts: 28
|
|
Re: Set P contains n elements
« Reply #2 on: Apr 17th, 2019, 10:39am » |
Quote Modify
|
I am struggling to write math. That YABBC tags don't work. Neither I can post an image, as it requires some minimum no. of posts. Well I can't understand what's the operation between "n" and "2" in your SUM. It would be better if you can post it in an image where the answer is crisp clear. Let's check for some values, suppose n = 7 and m = 5. What do you got?
|
| « Last Edit: Apr 17th, 2019, 10:46am by navdeep1771 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Set P contains n elements
« Reply #3 on: Apr 17th, 2019, 10:50am » |
Quote Modify
|
My result is C(n, m) * 3(n-m) / 4n
I'm approaching it as: color each item with one of 4 colors (say, red, yellow, blue and green), and then count that a given color (say, red) occurs m times.
So there's C(n, m) ways to pick m red elements, then color the other n-m elements with the 3 remaining colors in one of 3(n-m) ways. And then you divide by 4n for the probability
The analogy is the red and yellow elements are in set A, and red and blue elements are in set B, green ones are in neither
for n=7, m=5 I get 189/47 ~= 0.0115
|
| « Last Edit: Apr 17th, 2019, 11:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Set P contains n elements
« Reply #4 on: Apr 17th, 2019, 11:29am » |
Quote Modify
|
NB wolframalpha happily simplifies rmsgrey's result to the same as mine. (Albeit with C(n, m) expanded to n!/m!/(n-m)! )
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender:
Posts: 28
|
|
Re: Set P contains n elements
« Reply #5 on: Apr 17th, 2019, 8:45pm » |
Quote Modify
|
That's correct. The strategy towr used is very similar to that I know i.e. by Venn Diagram. There are n elements in set P. Construct 2 sets A and B in set P having some intersection part. So now total there are 4 ways to send n elements in Set P which are:
Set A only, Set B only, Intersection of Set A and B, and neither in Set A nor in Set B. So total = 4^n.
Favorable : Selecting any m elements from n and then sending those m elements into the intersection partof Set A and Set B. Which is C(n,m)*3^(n-m).
|
| « Last Edit: Apr 17th, 2019, 10:03pm by navdeep1771 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Set P contains n elements
« Reply #6 on: Apr 17th, 2019, 10:19pm » |
Quote Modify
|
It also looks quite simple to extend this to k sets
C(n, m) * (2k -1)(n-m) / 2k*n
|
| « Last Edit: Apr 17th, 2019, 10:20pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Set P contains n elements
« Reply #7 on: Apr 18th, 2019, 5:26am » |
Quote Modify
|
on Apr 17th, 2019, 10:39am, navdeep1771 wrote:| I am struggling to write math. That YABBC tags don't work. Neither I can post an image, as it requires some minimum no. of posts. Well I can't understand what's the operation between "n" and "2" in your SUM. It would be better if you can post it in an image where the answer is crisp clear. Let's check for some values, suppose n = 7 and m = 5. What do you got? |
|
n was the upper limit of the sum, so "sum from k=m to n of {(two raised to the (n-k)'th power) divided by ...}
In Towr's analogy, I'm breaking the total cases based on the number of yellow items, and then summing those cases.
I would like to point out that towr's extended formula also applies to situations where there are k independently chosen subsets, and you want there to be precisely m that are both in the intersection of any subset of those k sets and outside the union of the remaining sets. For example, if you had sets A, B, C, D, E and F, the formula, with k=6, would give the correct value for the probability of there being precisely m elements that are both in A, B and C, and outside D, E and F.
A simple proof can be found by considering that D can be replaced by its complement, ~D, and similarly E by ~E, F by ~F, without changing the probabilities, and A&B&C&~D&~E&~F then becomes A&B&C&D&E&F - the common intersection of all 6 subsets.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print