1
$\begingroup$

This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, add it to the set, otherwise we will skip and reselect. This process will be repeated until required amount of samples are seccessfully selected.

Following is the JavaScript version of the algorithm (fell free to paste it into a browser console and try it):

function sample(arr, n) {
    if (n >= arr.length) return arr.slice(0);

    let set = new Set();
    while (set.size < n) {
        let index = Math.floor(Math.random() * arr.length);
        if (set.has(index)) continue;
        else set.add(index);
    }

    let result = [];

    for (let index of set) {
        result.push(arr[index]);
    }

    return result;
} 

Although is simple, it is difficult for me to find out the time complexity, and the possibility for each array items to be chosen. If the algorithm is practical, it should garentee every items has equally $k/N$ possibility to be selected, when we select $k$ items from an array with $N$ items. Unfortunately, I cannot prove this.

The time complexity is hard to handle with too, because the algorithm is based on random selecting, so it is possible that we happen to select the same item for many times, and as more and more items are selected, this possibility will increase, which makes the time complexity harder to compute.

$\endgroup$

1 Answer 1

1
$\begingroup$

Assume that $m$ items have already been chosen. The next one needs to be different, which occurs with probability $1-\dfrac mn$. So the expectation of the number of drawings is $\dfrac{n}{n-m}$ (geometric law). To reach the quorum of $k$ numbers, you will need

$$\sum_{m=0}^{k-1}\frac n{n-m}=n\left(H_{n}-H_{n-k}\right)\sim n\log\frac n{n-k}\\\sim k\ \text{ if }k\ll n$$ drawings on average, each corresponding to a search in the current set. To this, you add $k$ insertions.

You cannot do much better than assuming constant time for searches and insertions with a hash table.

$\endgroup$
2
  • $\begingroup$ Does re-select and reject items that has already been chosen effect the pobability, if it is not, why? $\endgroup$
    – Stephen.W
    Jun 28, 2022 at 21:04
  • $\begingroup$ @Stephen.W: why would it ? $\endgroup$
    – user16034
    Jun 29, 2022 at 7:04

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.