Suppose we have $K$ elements to form sets with unique elements (null set not included). For example, for $K = 2$, we can have three sets possible sets as $\lbrace 1 \rbrace$, $\lbrace 2 \rbrace$, and $\lbrace 1, 2 \rbrace$. So for any $K \in \mathbb{Z}^{+}$, there are total $2^K -1$ possible sets.

Now a person, say Adam, wishes to choose one of these $2^K -1$ sets at random, i.e., each set is chosen with probability $\frac{1}{2^K -1}$. Then, other person, say Bob, chooses his set from these $2^K -1$ sets at random.

What is the probability that the set chosen by Bob has $n$ (with $n \in \lbrace 0, 1, 2, \dotsc, K\rbrace$) elements in common with Adam's chosen set? For example, for $K = 3$, let us say Adam chooses the set $\lbrace 2, 3 \rbrace$ and Bob chooses $\lbrace 1, 2, 3 \rbrace$. Then their chosen sets have $n = 2$ elements common. If Bob chooses $\lbrace 1, 3 \rbrace$, their chosen sets have $n = 1$ element common.

My attempt: I tried to represent the sets as binary sequences of length $K$. I set $k$th position to $1$ if the element $k$ is present in the chosen set, otherwise to $0$. For example, for $K = 3$ where Adam chooses the set $\lbrace 2, 3 \rbrace$ and Bob chooses $\lbrace 1, 3 \rbrace$ , it is equivalent to say that Adam has chosen the binary sequence ($011$) and Bob has chosen ($101$). But I am unable to calculate the probability for any general values of $K \in \mathbb{Z}^{+}$ and $n$.


1 Answer 1


Well, first we choose the overlap. Since the overlap is $n$, there are $\binom{k}{n}$ ways to do so. Now for each of the remaining elements, either Adam owns it, Bob owns it, or neither owns it. Three choices each, so $3^{k-n}$ ways to do this. Thus in total the answer is $$\binom{k}{n}3^{k-n}$$ ways, or a chance of $$\frac{\binom{k}{n}3^{k-n}}{(2^k-1)^2}$$ as long as $n\neq0$. For $n=0$, there is one possibility that needs to be ruled out, that of a zero-element set being chosen. We simply count how many ways there are for this to happen ($2^{k+1}-1$) and subtract from the total number of ways, thus giving us a probability of $$\frac{3^k-2^{k+1}+1}{(2^k-1)^2}$$


You must log in to answer this question.

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