You have a set of N elements. You choose, at random, a subset of it. Then, indep

Question

You have a set of N elements. You choose, at random, a subset of it. Then, independently, you choose another subset of the original set of N elements. There are no limits on the size of either of the subsets, each can contain anywhere from zero to N elements. Neither size is specified. What is the probability, p, that the second subset is a subset of the first? An empty (zero elements) set is a subset of any set, and a set is obviously a subset of itself. Give a full solution with ample explanations

Explanation / Answer

Give a set with total N elements.

Now let us assume we pick a subset from this set of N elements. Let us name this subset as X and let us assume it has M elements.

Hence total number of subset that can be chosen = 2^M

Now let us assume there is another subset Y of the set of N elements. Now the probability that Y is a subset of X will be = 2^M / 2^N = 2 ^ (M-N).

This is the probability for one such subset X with M elements. Now probability of picking such subset from total of N elements will be = 2 ^ (-N) (N M)

Summing over all the probable M starting from M=0 to M=N, we will get following

= Sum (M=0 to M=N) : 2^ (M-N) * 2  ^ (-N) (N M) = (3/4) ^N

Hence the probability that second subset is subset of first>(3/4) ^N

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.