Expected number of elements in an intersection

Probability Level 4

Let P n P_{n} be the set of all subsets of the set [ n ] = { 1 , 2 , … , n } . [n] = \{1,2,\ldots, n\}. If two distinct elements of P 5 P_{5} are chosen at random, the expected number of elements (of [ n ] [n] ) that they have in common can be expressed as a b \frac{a}{b} where a a and b b are coprime positive integers. What is the value of a + b ? a + b?

Details and assumptions

As an explicit example, P 2 = { ∅ , { 1 } , { 2 } , { 1 , 2 } } P_2 = \left\{ \emptyset, \{1\}, \{2\}, \{1, 2\} \right\} . { 1 } \{1\} and { 1 , 2 } \{1,2\} are 2 elements of P 2 P_2 , which have 1 element in common.


The answer is 137.

View wiki
Calvin Lin by Calvin Lin

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

First, let's call the randomly chosen element of P 5 P_5 be the set A and set B.

The probability that an element x is in both A and B can be computed by multiplying the probability that x is in A and probability that x is in B.

The probability that x is in A is 1 2 \frac{1}{2} since of the 32 elements of P 5 P_5 16 contains x. While the probability that x is in B provided it is in A is 15 31 \frac{15}{31} since of the 32 elements of P 5 P_5 , one of them is A which is already chosen.

Therefore the probability that x is in both A and B is, 1 2 × 15 31 = 15 62 \frac{1}{2} \times \frac{15}{31} = \frac{15}{62}

And since we we have five elements for [n]

The Expected number of same elements of set A and set B is

Probabilitu × \times n = 15 62 × 5 = 75 62 = \frac{15}{62} \times 5 = \frac{75}{62}

Since 75 and 62 are positive coprimes then a + b = 75 + 62 = 137 a+b = 75 + 62 = 137

12 Helpful 0 Interesting 0 Brilliant 0 Confused

The linearity of expectation is an extremely useful property. There is no need to list out all the pairs and slowly count the number of intersections, which is the brute force approach used by the rest of the solutions.

Calvin Lin Staff - 7 years ago
Zi Song Yeoh
May 20, 2014

Call a subset of P 5 P_{5} a n n -set if there are n n elements in that subset.

Sets                         Total number of intersecting elements            Number of pairs

  1. 5 5 -set and 5 5 -set       0                                                                           0

  2. 5 5 -set and 4 4 -set       20                                                                         5

  3. 5 5 -set and 3 3 -set.      30                                                                        10

  4. 5 5 -set and 2 2 -set.      20                                                                        10

  5. 5 5 -set and 1 1 -set.      5                                                                           5

  6. 5 5 -set and 0 0 -set.      0                                                                           1

  7. 4 4 -set and 4 4 -set.     30                                                                           10

  8. 4 4 -set and 3 3 -set.     120                                                                           50

  9. 4 4 -set and 2 2 -set.       80                                                                           50

  10. 4 4 -set and 1 1 -set.    20                                                                         25

  11. 4 4 -set and 0 0 -set.    0.                                                                          5

  12. 3 3 -set and 3 3 -set.    75                                                                           45

  13. 3 3 -set and 2 2 -set.    120                                                                           100

  14. 3 3 -set and 1 1 -set.    30                                                                        50

  15. 3 3 -set and 0 0 -set.    0.                                                                         10

  16. 2 2 -set and 2 2 -set.     45                                                                           45

  17. 2 2 -set and 1 1 -set.    20                                                                         50

  18. 2 2 -set and 0 0 -set.    0.                                                                         10

  19. 1 1 -set and 1 1 -set.    0.                                                                         10

  20. 1 1 -set and 0 0 -set     0.                                                                          5

  21. 0 0 -set and 0 0 -set.    0.                                                                          0

  22. Total.                600                                                                            496 Thus,

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Calvin Lin Staff
May 13, 2014

Let x , y x, y be the two chosen elements of P 5 . P_{5}. Let X i X_i be the random variable that is 1 when i i is contained in both x x and y y and 0 otherwise. The expected number of elements in both x x and y y will thus be E ( ∑ i = 1 5 X i ) = ∑ i = 1 5 E ( X i ) . E(\sum\limits_{i=1}^{5} X_i) = \sum\limits_{i=1}^{5} E(X_i).

We seek to calculate E ( X i ) . E(X_i). The probability that i ∈ x i \in x is 1 2 . \frac{1}{2}. Given that i ∈ x , i \in x, the probability that i ∈ y i \in y is 1 2 ⋅ 2 5 − 1 − 1 2 5 − 1 , \frac{1}{2} \cdot \frac{2^{5-1} - 1}{2^{5}-1}, so E ( X i ) = 15 62 . E(X_i) = \frac{15}{62}. This is independent of which i i is chosen, so the expected number of elements in both sets is 5 ( 15 62 ) = 75 62 . 5 \left(\frac{15}{62}\right) = \frac{75}{62}. Thus a + b = 75 + 62 = 137. a + b = 75 + 62 = 137.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...