<p>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
<span class="math-container">$\mathcal{B}$</span>, sample a point in <span class="math-container">$\cup \mathcal{B}$</span>
uniformly at random.</p>
<p>Let <span class="math-container">$\cup \mathcal{A}$</span> denote collection of subsets over <span class="math-container">$n$</span> objects. Given a sub-collection <span class="math-container">$\mathcal{B}$</span>, (subcollection of <span class="math-container">$\mathcal{A}$</span>) sample a point from <span class="math-container">$\cup \mathcal{B}$</span> uniformly at random.</p>
<p>The simple algorithm is to first apply a random permutation to <span class="math-container">$n$</span> objects and then sort the sets we have in <span class="math-container">$\mathcal{A}$</span> (preprocessing) according to the random permutation. In the query processing phase we will find the minimum element among all elements of <span class="math-container">$\cup\mathcal{B}$</span> and return it.</p>
<p>Time complexity(query phase) is <span class="math-container">$\mathcal{O}(\mathcal{|B|})$</span> as we need to iterate over the all sets we have in <span class="math-container">$\mathcal{B}$</span>.</p>
<p>Is there exists a faster algorithm for the above problem?</p>
<p>Note that there will be two phase preprocessing and query phase. I am considering the time complexity of the query phase.</p>
<p>Refer me to papers or books which cover topics related to the problem described above.</p>

CC BY-SA 4.0
2022-09-09T09:59:17.583Z
(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?
usul
CC BY-SA 4.0
2022-09-09T10:10:27.477Z
@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.
Shi
CC BY-SA 4.0
2022-09-09T10:36:42.903Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-09-09T14:43:03.247Z
@Emil Jeřábek. It is union of $B$'s.
Shi
CC BY-SA 4.0
2022-09-09T18:13:22.910Z
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...
usul
CC BY-SA 4.0
2022-09-09T18:13:35.437Z
(i) There are theoretical data structures that (with some restrictions), given a collection of non-negative weights, allow constant-time updates to the weights and constant-time sampling (choosing a single weight at random with probability proportional to the weight).  Perhaps you can use these.  (ii) It's not clear from the post (as currently written) how B is given in the query phase, but surely if it's given, say, as a list of indices of sets in B, you can't do better than $O(|B|)$.
Neal Young
CC BY-SA 4.0
2022-09-10T08:18:25.043Z
@usul $\mathcal{B} = O(n^{\alpha} \log n)$ where $0<\alpha<1$
Shi
CC BY-SA 4.0
2022-09-10T08:21:11.707Z
@ Neal Young Thanks for the detailed comment. $\mathcal{B}$ will be given as a collection of arrays.
Shi
CC BY-SA 4.0
2022-09-13T18:06:07.540Z
@NealYoung can you give a pointer/link to such data structures?
kodlu
CC BY-SA 4.0
2022-09-13T18:52:54.820Z
See [15] and [10] as cited in the bibliography of https://dx.doi.org/10.1007/s00453-013-9771-6.  
[15] Matias, Y., Vitter, J.S., Ni, W.: Dynamic generation of discrete random variates. Theory Comput. Syst. 36(4), 329–358 (2003)
[10] 10. Hagerup, T., Mehlhorn, K., Munro, J.I.: Optimal algorithms for generating discrete random variables with changing distributions. In: Proceedings 20th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 700, pp. 253–264 (1993).
Neal Young
<reference-request><sample-complexity>
Faster algorithm for sampling unifromly at random
Shi
# Faster algorithm for sampling unifromly at random

(Asked by: username_0 on 2022-09-09)

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.

**Tags:** reference-request, sample-complexity

> **Comments:**
> **username_1**: (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?  
> **username_0**: @username_1 $\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.  
> **username_2**: 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.  
> **username_0**: @username_2. It is union of $B$'s.  
> **username_1**: 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...  
> **username_3**: (i) There are theoretical data structures that (with some restrictions), given a collection of non-negative weights, allow constant-time updates to the weights and constant-time sampling (choosing a single weight at random with probability proportional to the weight).  Perhaps you can use these.  (ii) It's not clear from the post (as currently written) how B is given in the query phase, but surely if it's given, say, as a list of indices of sets in B, you can't do better than $O(|B|)$.  
> **username_0**: @username_1 $\mathcal{B} = O(n^{\alpha} \log n)$ where $0<\alpha<1$  
> **username_0**: @ username_3 Thanks for the detailed comment. $\mathcal{B}$ will be given as a collection of arrays.  
> **username_4**: @NealYoung can you give a pointer/link to such data structures?  
> **username_3**: See [15] and [10] as cited in the bibliography of https://dx.doi.org/10.1007/s00453-013-9771-6.   [15] Matias, Y., Vitter, J.S., Ni, W.: Dynamic generation of discrete random variates. Theory Comput. Syst. 36(4), 329–358 (2003) [10] 10. Hagerup, T., Mehlhorn, K., Munro, J.I.: Optimal algorithms for generating discrete random variables with changing distributions. In: Proceedings 20th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 700, pp. 253–264 (1993).  

---

## 0 answers

