The goal is to come up the simple data structure for sampling a uniform point from a collection of sets, i.e., given a sub-collection $\mathcal{B}$, sample a point in $\cup \mathcal{B}$ uniformly at random.

Let $\cup \mathcal{A}$ denote collection of subsets over $n$ objects. Given a sub-collection $\mathcal{B}$, (subcollection of $\mathcal{A}$) sample a point from $\cup \mathcal{B}$ uniformly at random.

The simple algorithm is to first apply a random permutation to $n$ objects and then sort the sets we have in $\mathcal{A}$ (preprocessing) according to the random permutation. In the query processing phase we will find the minimum element among all elements of $\cup\mathcal{B}$ and return it.

Time complexity(query phase) is $\mathcal{O}(\mathcal{|B|})$ as we need to iterate over the all sets we have in $\mathcal{B}$.

Is there exists a faster algorithm for the above problem?

Note that there will be two phase preprocessing and query phase. I am considering the time complexity of the query phase.

Refer me to papers or books which cover topics related to the problem described above.

  • 1
    $\begingroup$ (1) what do you mean by sample a point from B? Do you mean pick one of the subsets in B, or do you mean pick one of the elements of one of the subsets of B? If the latter, do you mean sample an element uniformly from the union of subsets in B? (2) How are A and B represented? $\endgroup$
    – usul
    Sep 9, 2022 at 9:59
  • $\begingroup$ @usul $\mathcal{A}$ is given as a list but in the preprocessing phase one can create any data structure and $\mathcal{B}$ will be given in the query phase. $\endgroup$
    – Shi
    Sep 9, 2022 at 10:10
  • $\begingroup$ The edit is unclear. What exactly is the distribution? A uniformly picked element of a uniformly chosen set from B gives a different distribution from a uniformly picked element of the union of the Bs. $\endgroup$ Sep 9, 2022 at 10:36
  • $\begingroup$ @Emil Jeřábek. It is union of $B$'s. $\endgroup$
    – Shi
    Sep 9, 2022 at 14:43
  • 1
    $\begingroup$ I think the problem is clear to me now. Seems very hard to improve on $O(|\mathcal{B}|)$ as you have to at least do some sort of processing for each element of $\mathcal{B}$, e.g. know how large it is... $\endgroup$
    – usul
    Sep 9, 2022 at 18:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.