Return to Question

Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each, and $𝑀_1,…,𝑀_𝑘$ are sublists with the smallest $𝑋$ elements in each list. Let $𝐶_1$ contain some elements from the lists. Define more $𝐶$s by: if $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, let $𝐶_{𝑖+1}=𝐶_𝑖\cup𝐿_𝑖$; and otherwise let $𝐶_{𝑖+1}=𝐶_𝑖$. What size of $𝑋$ will ensure with probability at least $1−1/𝑛^2$ that: If $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, then $|𝐶_𝑖\cap𝐿_𝑖|<1.1𝑛/𝑟$; and otherwise, $|𝐶_𝑖\cap𝐿_𝑖|>0.9𝑛/𝑟$? I am looking to minimize the size of $X$.

Edit: Above simplified problem suggested by Matt F. in the comments below.

Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each. We use a fully independent hash function ℎ to compute a value for each element of each list. (We suppose the hash function returns a value uniformly at random from $[𝑛^2]$. Note also that two elements $x$, and $y$ where $x = y$ has $ℎ(𝑥)=ℎ(𝑦)$.) Let $𝑀_1,…,𝑀_𝑘$ be sublists with the smallest $𝑋$ elements by computed hash value in each list. Let $𝐶_1$ contain $L_1$. Define more $𝐶$s by: if $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, let $𝐶_{𝑖+1}=𝐶_𝑖\cup𝐿_𝑖$; and otherwise let $𝐶_{𝑖+1}=𝐶_𝑖$. What size of $𝑋$ will ensure with probability at least $1−1/𝑛^2$ that: If $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, then $|𝐶_𝑖\cap𝐿_𝑖|<1.1𝑛/𝑟$; and otherwise, $|𝐶_𝑖\cap𝐿_𝑖|>0.9𝑛/𝑟$? I am looking to minimize the size of $X$.

Edit: Above simplified problem suggested by Matt F. in the comments below.

Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each, and $𝑀_1,…,𝑀_𝑘$ are sublists with the smallest $𝑋$ elements in each list. Let $𝐶_1$ contain some elements from the lists. Define more $𝐶$s by: if $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, let $𝐶_{𝑖+1}=𝐶_𝑖\cup𝐿_𝑖$; and otherwise let $𝐶_{𝑖+1}=𝐶_𝑖$. What size of $𝑋$ will ensure with probability at least $1−1/𝑛^2$ that: If $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, then $|𝐶_𝑖\cap𝐿_𝑖|<1.1𝑛/𝑟$; and otherwise, $|𝐶_𝑖\cap𝐿_𝑖|>0.9𝑛/𝑟$? I am looking to minimize the size of $X$.

Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each, and $𝑀_1,…,𝑀_𝑘$ are sublists with the smallest $𝑋$ elements in each list. Let $𝐶_1$ contain some elements from the lists. Define more $𝐶$s by: if $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, let $𝐶_{𝑖+1}=𝐶_𝑖\cup𝐿_𝑖$; and otherwise let $𝐶_{𝑖+1}=𝐶_𝑖$. What size of $𝑋$ will ensure with probability at least $1−1/𝑛^2$ that: If $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, then $|𝐶_𝑖\cap𝐿_𝑖|<1.1𝑛/𝑟$; and otherwise, $|𝐶_𝑖\cap𝐿_𝑖|>0.9𝑛/𝑟$? I am looking to minimize the size of $X$.

Edit: Above simplified problem suggested by Matt F. in the comments below.

Suppose we are given some lists of elements $L_1, \dots, L_{\ell}$ where each list has $n$ elements. We use a fully independent hash function $h$ to compute a value for each element of each list. (We suppose the hash function returns a value uniformly at random from $[n^2]$. Note also that two elements $x$ and $y$ where $x = y$ has $h(x) = h(y)$.) We then use the $X$ elements corresponding to the $X$ smallest hash values of each list to do the following:

We have some set $C$ consisting of elements from the lists. We order the lists in an arbitrary order and process the lists in that order. Then, using the $X$ elements from each list, we add the elements in each list $L_i$ to $C$ if at most a $1/r$-fraction of $X$ elements are in $C$. The question is: how large does $X$ have to be if I want to ensure with probability at least $1 - \frac{1}{n^2}$ for some constant $c$ that each list $L_j$ added to $C$ has at most a $(1+\epsilon)(1/r)$-fraction of elements in $L_j$ that are in $C$ when it was added to $C$, and each list not added to $C$ has more than $(1-\epsilon)(1/r)$-fraction of elements in $C$ when it was processed. You can provide the constant $\epsilon$; any constant $0 < \epsilon < 1$ is fine.

Suppose we have a random variable $R_i$ for each list $L_i$ representing whether list $L_i$ has at most a $(1+\epsilon)(1/r)$-fraction of its elements in $C$ provided at most $(1/r)$-fraction of the elements in its $X$ elements is in $C$. The difficulty of the problem is that the $R_i$'s are not only correlated with each other but also depends on which lists are added into $C$.

Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each, and $𝑀_1,…,𝑀_𝑘$ are sublists with the smallest $𝑋$ elements in each list. Let $𝐶_1$ contain some elements from the lists. Define more $𝐶$s by: if $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, let $𝐶_{𝑖+1}=𝐶_𝑖\cup𝐿_𝑖$; and otherwise let $𝐶_{𝑖+1}=𝐶_𝑖$. What size of $𝑋$ will ensure with probability at least $1−1/𝑛^2$ that: If $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, then $|𝐶_𝑖\cap𝐿_𝑖|<1.1𝑛/𝑟$; and otherwise, $|𝐶_𝑖\cap𝐿_𝑖|>0.9𝑛/𝑟$? I am looking to minimize the size of $X$.