Probability of A is a subset of B if Hash(A) is a subset of Hash(B).

Question

There is an infinite countable set $S$. From it we have two subsets of $A$ and $B$. The $Hash$ function translates $S$ into $Hash(S)$ - a finite set of hashes, and, accordingly translates $A$ into $Hash(A)$ and $B$ into $Hash(B)$.

Question: Is it possible and how to count the probability $P(A \subseteq B | Hash(A) \subseteq Hash(B))$ given $|A|, |B|, |Hash(S)|$?

Here is what I've tried:

$X = A \subseteq B$

$Y = Hash(A) \subseteq Hash(B)$

$P(X|Y) = P(Y|X)P(X)/P(Y)$

$P(Y|X) = 1$ (as I understand)

Probability of hash of one element of $A$ is equal to hash of one element of $B$ is $1/|Hash(S)|$.

Probability of hash of one element of $A$ is equal to hash of at least one element of $B$ is $1 - (1 - 1/|Hash(S)|)^{|B|}$.

Probability of hash of any element of A is equal to hash of at least one element of B is $(1 - (1 - 1/|Hash(S)|)^{|B|})^{|A|}$.

$P(Y) = (1 - (1 - 1/|Hash(S)|)^{|B|})^{|A|}$

$P(X) = P(A \subseteq B)$ - here I stuck

If assume that $S$ is finite and add $|S|$ as given parameter - then got same for $A$ and $B$:

Probability of one element of A is equal to one element of B is $1/|S|$.

Probability of one element of A is equal to at least one element of B is $1 - (1 - 1/|S|)^{|B|}$.

Probability of any element of A is equal to at least one element of B is $(1 - (1 - 1/|S|)^{|B|})^{|A|}$.

$P(X) = (1 - (1 - 1/|S|)^{|B|})^{|A|}$

$P(A \subseteq B | Hash(A) \subseteq Hash(B)) = (1 - (1 - 1/|S|)^{|B|})^{|A|} / (1 - (1 - 1/|Hash(S)|)^{|B|})^{|A|}$

So could anybody please check if this is correct?

Answer 1

It really depends on $Hash=H$. Consider $S=\{0,1,2,3\}, H(S)=\{0,1\}, |A|=1, |B|=2$. So $P(A \subseteq B)=\frac{1}{2}$. Without loss of generality, there are two possibilities: $|H^{-1}(0)|=1,2$.

In the case $|H^{-1}(0)|=2$, we can consider $H(x)=x \mod2$. Again, there are two cases:

• $|H(B)|=2$ (it happens $4$ times when $B=\{0,1\}, \{0,3\}, \{1,2\}, \{2,3\}$). Then $P(Y|\ |H(B)|=2) = 1$ and $P(|H(B)|=2)=\frac{4}{6}$.
• $|H(B)|=1$ (it happens $2$ times when $B=\{0,2\}, \{1,3\}$). Then $P(Y|\ |H(B)|=1) = \frac{1}{2}$ and $P(|H(B)|=1)=\frac{2}{6}$.

So

$$P(Y) = P(Y, |H(B)|=2) + P(Y, |H(B)|=1) = \\ P(Y|\ |H(B)|=2)\cdot P(|H(B)|=2) + P(Y|\ |H(B)|=1)\cdot P(|H(B)|=1) = \\1 \cdot \frac{4}{6} + \frac{1}{2}\cdot \frac{2}{6} = \frac{5}{6}$$

In the case $|H^{-1}(0)|=1$, we can consider $H(x)=0$ if $x=0$, $H(x)=1$ otherwise. Again, there are two cases:

• $|H(B)|=2$ (it happens $3$ times when $B=\{0,1\}, \{0,2\}, \{0,3\}$). Then $P(Y|\ |H(B)|=2) = 1$ and $P(|H(B)|=2)=\frac{3}{6}$.
• $|H(B)|=1$ (it happens $3$ times when $B=\{1,2\}, \{1,3\}, \{2,3\}$). Then $P(Y|\ |H(B)|=1) = \frac{3}{4}$ and $P(|H(B)|=1)=\frac{3}{6}$.

So $P(Y) = \ldots = \frac{7}{8}$.