5

There are two sets, $A=\{a_1, \dots, a_n\}$ and $B=\{b_1, \dots, b_m\}$, for some $m$ and $n$.

The elements $a_1, \dots, a_n$ and $b_1, \dots, b_m$ are all $x$-bit binary strings, and they are all uniformly sampled from $X$, which is defined as the set of all $x$-bit binary strings.

Let $I_{n,m}$ be the value $|A\cap B|$. Obviously, $I_{n,m}$ is a random variable.

So, how can I calculate $E[I_{n,m}]$?

Note that $A$ and $B$ are multisets. Besides, given $x=3$, if $A$ and $B$ happen to have two $111$'s and three $111$'s, respectively ($\{111,111\}\subseteq A$ and $\{111,111,111\}\subseteq B$), then they only contribute $1$ to $I_{n,m}$.

user4478
  • 329
  • You’re written $A$ and $B$ as sets, implying that $a_i\ne a_j$ for $i\ne j$ and hence that you’re sampling without replacement. Is this correct? Or are they really $n$- and $m$-tuples, respectively, sample with replacement from $X$? – Brian M. Scott Jan 21 '13 at 19:37
  • They are sampled with replacement. – user4478 Jan 21 '13 at 19:39
  • Suppose that an $x$-bit string occurs twice in $A$ and three times in $B$; how much does that string contribute to $I_{n,m}$? If you’re treating $A$ and $B$ as multisets, I’d expect it to contribute $2$; if, on the other hand, you’re treating them as sets, so that $|A|$ may be strictly less than $m$, then I’d expect it to contribute $1$. – Brian M. Scott Jan 21 '13 at 19:43

1 Answers1

3

Added, in response to OP's clarification: If $A$ and $B$ are multisets, but $A \cap B$ is a set, then for the purposes of counting the size of $A \cap B$ we can treat $A$ and $B$ as if they are sets. For example, having $1 \in A \cap B$ is equivalent to having $1$ at least once in $A$ and $1$ at least once in $B$. This is tantamount to treating $A$ and $B$ as sets.

There are $2^x$ $x$-bit binary strings. Since you're choosing with replacement, for any $x$-bit binary string $k$ the probability that $k \not\in A$ is $(1 - \frac{1}{2^x})^n$, so the probability that $k \in A$ is $1 - (1 - \frac{1}{2^x})^n$. Similarly, the probability that $k \in B$ is $1 - (1 - \frac{1}{2^x})^m$. Thus the probability that $k \in A \cap B$ is $$\left(1 - q^n \right)\left(1 - q^m\right) = 1 - q^n - q^m + q^{m+n},$$ where $q = 1 - \frac{1}{2^x}$.

Let $I_k = 1$ if $k \in A \cap B$ and $0$ otherwise. Then $$E[I_{n,m}] = \sum_k E[I_k] = \sum_k P(k \in A \cap B) = 2^x (1 - q^n - q^m + q^{m+n}).$$

Mike Spivey
  • 55,550
  • So you’re treating $A$ and $B$ as sets sensu stricto. That probably is the intent, but I hope that the OP clarifies this. – Brian M. Scott Jan 21 '13 at 20:03
  • @BrianM.Scott: Yes, I am. If $A$ and $B$ are multisets, as you ask about in your comment, then the answer would be different. – Mike Spivey Jan 21 '13 at 20:05
  • @BrianM.Scott I am not sure, but it seems that the answer here is calculated based on "multiset + count different times" case. Am I right? – user4478 Jan 21 '13 at 20:08
  • @MikeSpivey Oh, I am wrong. It seems that your answer is based on the assumption that $A$ and $B$ are sets, instead of multisets. – user4478 Jan 21 '13 at 20:10
  • @user4478: Yes, I'm assuming $A$ and $B$ are sets. Is that your intent? – Mike Spivey Jan 21 '13 at 20:10
  • @MikeSpivey It's my bad, I didn't clarify my question; $A$ and $B$ should be multisets. However, if $A$ happens to have two $111$'s and $B$ happens to have three $111$'s (x=3 here), then they contribute 1 to $I_{n,m}$ only. – user4478 Jan 21 '13 at 20:13
  • @user4478: So $A$ and $B$ are multisets, but $A \cap B$ is a regular set? If that's the case, then my answer still holds. – Mike Spivey Jan 21 '13 at 20:15
  • @MikeSpivey Still working? Let me do some calculation. Thank you! :) – user4478 Jan 21 '13 at 20:19