12
$\begingroup$

Let $$ S={1,2,...,n} $$ From the power set, $ P(S) $, of $S$, two subsets $A$, $B$ are chosen at random. If each subset is equally likely to be chosen, then, the probability that the sets $ A $ and $ B $ have no elements in common is....

Here are some of my tries:

Probability that two particular sets will be chosen is $ 2^{-2n} $. If from one set $\phi$ is chosen, no intersection, is guaranteed, if a Singelton is chosen from first set then

  1. if $ \phi $ is chosen from second set, then no intersection is guaranteed
  2. if some set with cardinality = 1 is chosen from second set then no intersection guaranteed for all $n$ sets except for 1 which is the same as first set.
  3. if some set with cardinality = 2 is chosen from second set then for no intersection guaranteed for all $^{n}C _2 $sets except for $n-1$ which contain the singleton in first set.
  4. if some set with cardinality = 3 is chosen from second set then for no intersection guaranteed for all $^ {n}C _2 $ sets except for???? I can't think further. I can't figure out a general term for $n$ cardinality.

So far, I have figured.

$ P(A\bigcap B = \phi) = 2^{-2n} [^{n}C_0 * 1 + ^{n}C_1(^{n}C_0 * 1 + ^{n}C_1 -1 + ^{n}C_2 -(n-1) ..... ) + ^{n}C_2(....) .......^{n}C_n(....) ] $

I have tried finding complement of the question (finding probability that they have at least something in common)

I have tried using de Morgans law, $ P(A\bigcap B = \phi) = P((A^c \bigcup B^c)^c) = \phi) $ but I can't figure it out.

I created a python program to find probability however computer cant calculate probabilities for $n >= 25$ and the result does not seem to have converged. At $ n = 25 $, probability is around $0.001$.

I have looked at other similar questions however they don't deal with subsets of superset but some simple subset of simple sets.

The probability that two randomly selected subsets of the set $\{1 , 2, 3, 4 , 5\}$ have exactly two elements in their intersection , is

$\endgroup$
5
  • $\begingroup$ Your program's results don't seem to converge to $0$ for large $n$? $\endgroup$
    – Brian Tung
    Aug 13, 2023 at 16:37
  • 1
    $\begingroup$ Hint. Encode each subset as a binary string of length $n$. Then the $k$th element in the superset is present in the intersection of the subsets, if the strings both have what in the $k$th position? $\endgroup$
    – Brian Tung
    Aug 13, 2023 at 16:39
  • 1
    $\begingroup$ Hint: two sets have empty intersection if and only if, for every $j\in S$, at most one of $A$ and $B$ contains $j$ ... and these events are independent for different $j$. (By the way, one should specify that $A$ and $B$ are chosen independently as well as uniformly.) $\endgroup$ Aug 13, 2023 at 16:52
  • $\begingroup$ This is bound to be a duplicate. $\endgroup$
    – user700480
    Aug 15, 2023 at 21:08
  • $\begingroup$ In some sense a choice of probability measure is required. There is not a unique probability distribution that can be defined over such an event space. $\endgroup$
    – Galen
    Aug 15, 2023 at 22:32

3 Answers 3

31
$\begingroup$

Construct the sets $A$ and $B$ by following this procedure: for each element of $S$, flip a fair coin to decide if it is a member of $A$, and flip again to decide, independently, if it is to be a member of $B$. The chance the element in question is not in $A\cap B$ is $3/4$, and the chance that none of the $n$ elements of $S$ are in $A\cap B$ is thus $(3/4)^n$.

$\endgroup$
1
  • 1
    $\begingroup$ This is a special case of using indicator functions. It might be nice to say a word about those if you know them. They are very useful for all kinds of probability problems. $\endgroup$
    – DRF
    Aug 15, 2023 at 9:42
9
$\begingroup$

Number of pairs is $2^{2n}$, and for the number of pairs $(A,B): A \cap B=\emptyset $, you just notice that, to obtain such a pair $(A,B)$, it’s the same as constructing a mapping from $S$ to $\{ x,y,z\}$ (mapping elements of $A$ to $x$, elements of $B$ to $y$, elements of the complement to $z$). So $3^{n}$ many.

$\endgroup$
5
$\begingroup$

Pick a subset $S_1 \subset S$, and suppose $\#S_1 = m$ is the number of elements in $S_1$. There are $n - m$ elements in $S\setminus S_1$, hence the probability of choosing a subset of $S_2 \subset S$ disjoint to $S_1$ is $$P(S_1 \cap S_2 = \emptyset | \#S_1 = m) = \frac{2^{n-m}}{2^n} = \frac{1}{2^{m}}.$$ Summing over all $m$-element subsets of $S$ yields $$P(S_1 \cap S_2 = \emptyset) = \frac{1}{2^n}\sum_{m=0}^n\left(\frac{1}{2}\right)^m\binom{n}{m} = \left(\frac{3}{4}\right)^n,$$ the final equality by the binomial theorem.

EDIT: It also depends on if "order matters." As noted by other commenters, there are $3^n$ tuples of disjoint subsets. However, order matters in these tuples, that is if $A\cap B = \emptyset$ then the pair of disjoint subsets $(A,B)$ and $(B,A)$ are considered distinct ways to pick the subsets. This may not be desirable behavior. In that event, clearly the solution $(\emptyset, \emptyset)$ is allowed, hence there are $3^n - 1$ disjoint tuples where we double count; halving that number and adding back the solution $(\emptyset, \emptyset)$ yields $$\frac{3^n-1}{2}+1 = \frac{3^n+1}{2}$$ tuples of disjoint subsets of $S$ where order does not matter. There are $$2^n + \binom{2^n}{2} = 2^{2n-1} + 2^{n-1}$$ tuples of the form $\{(a,a) : a\in 2^S\} \cup \{\{a,b\} : a,b\in 2^S\}$, since if we choose two subsets of $S$ at random we can pick the same subset twice or two distinct subsets. So in this interpretation the probability is $$\frac{3^n+1}{4^n +2^n}.$$

$\endgroup$
3
  • $\begingroup$ For $n=1$, the other answers give $\frac34$ while yours gives $\frac23$. It is easy to check by elementary means that the other answers are right in this case. $\endgroup$ Aug 15, 2023 at 11:31
  • $\begingroup$ As I mentioned it depends on how you wish to interpret the problem. For example, consider the singleton $\{1\}$ and its power set $\{\emptyset, \{1\}\}$. If order matters then indeed we have a 3/4 probability; $(\emptyset, \emptyset)$ and $(\emptyset, \{1\})$ and $(\{1\}, \emptyset)$ are all disjoint, and there are $4$ total pairs to choose from. But if you consider $(\emptyset, \{1\})$ and $(\{1\}, \emptyset)$ to be the same tuple, then there is only a 2/3 probability, which was the intended consequence. $\endgroup$
    – BBBBBB
    Aug 16, 2023 at 2:03
  • $\begingroup$ OK. I accept your argument that there was ambiguity in the question. One upvote for you (only), $\endgroup$ Aug 16, 2023 at 7:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .