1
$\begingroup$

Let $M$ be a collection of elements given in the form of the array such that membership of any element can be done in $O(1)$ time. Which means elements of array $M$ are $\{1,2,\cdots,n\}$ such that $1$ is stored at $M[1]$ and $2$ at $M[2]$ and so on. The goal is to sample an element from the array $M$.

Note that we have to design an algorithm multiple times (say $k$ times) in such a way that in each repetition we get a different element as a result.

Sampling means the probability of picking any element from $M$ is $\frac{1}{|M|}$.

My idea is as follows: create another array $F:=[\frac{1}{|M|},\frac{1}{|M|},\cdots,\frac{1}{|M|}]$, which means assigning equal weights to each element.

There are several existing algorithms now which can sample an element from $M$ in expected time $O(1)$ (Say Algorithm 1 Algorithm).

If I run the same algorithm 1 again then the same element may get picked so I have to update something in the array $F$ this update should be in $O(1)$ time.

I am looking for an algorithm that gives $O(k)$ time for $k$ repetitions other than constructing array $F$.

How to modify the above algorithm such that next time I get a different answer?

EDIT: For any $a\in \{1,2,...,n\}, $Pr[Output_1=a] = $\frac{1}{|M|}$ and Pr[Output_i=a|Output_i-1 =a_i-1,...,Output_1=a_1]. Output_i denotes the output of the algorithm in the $i$th iteration and Pr denotes the probability.

$\endgroup$
6
  • 2
    $\begingroup$ I fail to see how establishing an array of weights explicitly changes (or defines) sampling a subset of size $k$. $\endgroup$
    – greybeard
    Sep 15, 2022 at 5:34
  • $\begingroup$ 1. I don't understand what you mean by "given in the form of the array such that membership of any element can be done in O(1) time." Can you explain that in another way? If you have an array of elements, testing whether a particular value is an element of the array takes O(n) time. 2. Might there be repeats in the elements of the array? 3. What do you mean by "Note that..."? Do you mean the goal is to randomly choose k elements, without replacement? Please edit the question so it is clearer about all of these points. $\endgroup$
    – D.W.
    Sep 15, 2022 at 6:14
  • $\begingroup$ There are no duplicate elements in the given array $M$. $\endgroup$
    – Rma
    Sep 15, 2022 at 7:11
  • $\begingroup$ So your question is how to sample k elements from n elements without replacement? stackoverflow.com/questions/311703/… $\endgroup$
    – qwr
    Sep 15, 2022 at 7:20
  • $\begingroup$ @greybeard I did this as I will apply the algorithm given in the pdf. $\endgroup$
    – Rma
    Sep 15, 2022 at 7:20

1 Answer 1

1
$\begingroup$
return M[(i - 1) % n + 1]

for $i=1,2, \cdots k$ does the trick.

$\endgroup$
6
  • $\begingroup$ Thanks but how to prove its correctness $\endgroup$
    – Rma
    Sep 19, 2022 at 8:13
  • $\begingroup$ @Rma: how could it be wrong ? $\endgroup$
    – user16034
    Sep 19, 2022 at 8:23
  • $\begingroup$ for i=1 it is fine but how to prove probability that for i=2,3,..,k is also equally like as written in the edit part of the question. $\endgroup$
    – Rma
    Sep 19, 2022 at 10:31
  • $\begingroup$ Well, systematic sampling does not ensure that the elements have the same chance of being drawn. But if you draw $k$ elements from a single set of $n$, does it matter ? $\endgroup$
    – user16034
    Sep 19, 2022 at 10:52
  • $\begingroup$ I will pick the k elements one by one. Suppose that it matters that the elements have the same chance of being drawn then? $\endgroup$
    – Rma
    Sep 19, 2022 at 11:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.