Sample unique elements from an array containing repeated values

Question

I have a table containing elements in $[1,c]$. The elements may be repeated in the table. I want to sample $m$ unique elements from this table.

I can reduce this problem to weighted sampling without replacement. This would require me to a) count the number of times each element occurs - say element $i$ occurs $n_i$ times, b) generate random numbers $U_i^{1/n_i}, 1 \le i \le c$ , and c) pick elements corresponding to the top $m$ values (reference). Here $U_i \sim Unif([0,1])$.

If I want to do this without counting the frequency of all elements, can I use the following algorithm?

• Generate a uniform random number for each row in the table.

• Sort these numbers.

• Pick the top $m$ values such that their corresponding elements are unique.

Notice that instead of generating one uniform random number per element, this method generates $n_i$ random numbers for element $i$. Is the above algorithm equivalent to weighted sampling without replacement?

Answer 1

Suppose you have $c = 100$ balls with colors (coded as numbers 1 through 5) as follows: 40 Red(=1), 20 Blue(=2), 20 Green(=3), 10 Brown(=4), and 10 Purple(=5).

In R you can express the population of $c$ balls as follows:

pop = rep(1:5, c(40,20,20,10,10))

In R, you can choose a random sample from of size $m = 3$ from this population as follows:

draw = sample(pop, 3)

Three replications of the experiment look like this:

pop = rep(1:5, c(40,20,20,10,10))
draw = sample(pop, 3); draw
[1] 1 1 2
draw = sample(pop, 3); draw
[1] 1 3 2
draw = sample(pop, 3); draw
[1] 5 4 1

A simulation to approximate the probability of getting $m = 3$ bals of $m$ different colors, makes $B = 100\,000$ samples, and assesses the results.

set.seed(515)
pop = rep(1:5, c(40,20,20,10,10))
uniq = replicate(10^5, length(unique(sample(pop, 3))))
mean(uniq==3)
[1] 0.39415
2*sd(uniq==3)/sqrt(10^5)
[1] 0.003090619

table(uniq)/10^5
uniq
      1       2       3 
0.07675 0.52910 0.39415 

So the probability of getting three different colors is $0.394.\pm 0.003.$

The combinatorial paths to an exact solution that occur to me right now seem tediously intricate.

Note: The alternative code illustrated below always chooses three uniquely different colors---with regard to specified probabilities of available colors when each ball is chosen. (if 1 has already been chosen, then a lower-weighted ball must be chosen afterward.)

sample(1:5, 3, p=c(.4,.2,.2,.1,.1))
[1] 1 4 2
sample(1:5, 3, p=c(.4,.2,.2,.1,.1))
[1] 1 3 2
sample(1:5, 3, p=c(.4,.2,.2,.1,.1))
[1] 2 5 4
sample(1:5, 3, p=c(.4,.2,.2,.1,.1))
[1] 3 2 1