Author 
Topic: Set P contains n elements (Read 13223 times) 

navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender:
Posts: 28


Set P contains n elements
« on: Apr 12^{th}, 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 12^{th}, 2019, 9:44am by navdeep1771 » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2861


Re: Set P contains n elements
« Reply #1 on: Apr 17^{th}, 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 2^{n} subsets of P, I get: p=n!/{m!*2^(2n)}*SUM_{k=m}^{n}2^(nk)/{(nk)!*(km)!} Reasoning: hidden:  For A to have k elements, with m<=k<=n, there are ^{n}C_{k} such sets A. For each such A, there are ^{k}C_{m} 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 nk elements of P can be in or out freely, giving 2^{nk} 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: ^{n}C_{k}*^{k}C_{m}*2^{nk} =n!/{k!(nk)!}*k!/{m!(km)!}*2^{nk} =2^{nk}*n!/{m!(km)!(nk)!} So the total number of pairs of sets A and B with an intersection of size exactly m is: SUM_{k=m}^{n}[2^{nk}n!/{m!(km)!(nk)!}] =n!/m!SUM_{k=m}^{n}2^{nk}/{(km)!(nk)!} And there are 2^{n} possibilities for each of A and B independently, giving 2^{2n} equally likely possible pairs of A and B, and a final probability of: n!/{m!*2^(2n)}*SUM_{k=m}^{n}2^(nk)/{(nk)!*(km)!} 

« Last Edit: Apr 17^{th}, 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 17^{th}, 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 17^{th}, 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 17^{th}, 2019, 10:50am » 
Quote Modify

My result is C(n, m) * 3^{(nm)} / 4^{n} 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 nm elements with the 3 remaining colors in one of 3^{(nm)} ways. And then you divide by 4^{n} 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/4^{7} ~= 0.0115

« Last Edit: Apr 17^{th}, 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 17^{th}, 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!/(nm)! )


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 17^{th}, 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^(nm).

« Last Edit: Apr 17^{th}, 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 17^{th}, 2019, 10:19pm » 
Quote Modify

It also looks quite simple to extend this to k sets C(n, m) * (2^{k} 1)^{(nm)} / 2^{k*n}

« Last Edit: Apr 17^{th}, 2019, 10:20pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2861


Re: Set P contains n elements
« Reply #7 on: Apr 18^{th}, 2019, 5:26am » 
Quote Modify

on Apr 17^{th}, 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 (nk)'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 



