0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Asaf Karagila Mar 14 at 20:56
  • $\begingroup$ 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) $\endgroup$ – Vladislav Mar 14 at 20:59
  • $\begingroup$ @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\}$ $\endgroup$ – user10714010 Mar 14 at 21:12
  • $\begingroup$ @Vladislav $A'_k$ is usually much much smaller than $A'$ $\endgroup$ – user10714010 Mar 14 at 21:13
  • $\begingroup$ So it is not $k$th smallest number but a set of first $k$ smallest numbers, is it? $\endgroup$ – Vladislav Mar 14 at 21:18

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.