# Given arbitrary set if each member map randomly to a different set injectively, is the k smallest number of the new set representative of the old set?

Given arbitrary set if each member map randomly to a different set injectively, is the k smallest number of the new set representative of the old set in a way that preserve set intersection property probabilistically?

Or more precisely if I have set $$A$$ and set $$B$$ and I randomly map each element in set $$A$$ to set $$A'$$ and $$B$$ to $$B'$$ injectively $$\mathbb{Z_n} \Rightarrow \mathbb{Z_n}$$ for which n is bounded number $$\in \mathbb{Z}$$

For $$A'$$ and $$B'$$ I take the smallest $$k$$ numbers and put it in $$A'_k$$ and $$B'_k$$

ie. If $$A' = \{1,2,3,4\}$$ and $$B' = \{2,4,5,6,8,10\}$$ $$A'_2 = \{1,2\}$$ and $$B'_2 = \{2,4\}$$ . Essentially $$A_k$$ is the set of kth smallest element in $$A$$

If I intersect $$A_k$$ and $$B_k$$ can I say that the probability of finding intersection between $$A_k$$ and $$B_k$$ is a fair representation of the probability of finding intersection between $$A$$ and $$B$$

The motivation of the problem is that there is an cardinality estimation algorithm called the KMV that uses the $$k_{th}$$ smallest element to estimate the number of distinct element in a set and it also allows the estimation of distinct element between the intersection of 2 KMV . I understand how KMV is capable of estimating the cardinality of a set, but I don't quite understand how KMV preserve intersection operation statistically

• It's unclear to me why you'd use ASCII and $\rm\LaTeX$ in such a weird and inconsistent mixture, and also what are $A_k$ and $B_k$. – Asaf Karagila Mar 14 at 20:56
• What is the point of $A_k$ and $B_k$? It seems like they always have the only element ($k$th number of $A'$ and $B'$ respectively) – Vladislav Mar 14 at 20:59
• @AsafKaragila bad habit from asking question in stackoverflow, should be fixed, $A_k$ is the $k_{th}$ smallest element in $A$ for example $A = \{1, 2,3\}$ $A_2 = \{ 1, 2\}$ – user10714010 Mar 14 at 21:12
• @Vladislav $A'_k$ is usually much much smaller than $A'$ – user10714010 Mar 14 at 21:13
• So it is not $k$th smallest number but a set of first $k$ smallest numbers, is it? – Vladislav Mar 14 at 21:18