Does it matter how you sample a population?

Question

I have a well-mixed vat containing an infinite number of marbles. There is an infinite amount of marbles in the vat, but they only come in some unknown but finite number of varieties: $$\mathcal{V} = \{v_{1},v_{2},v_{3},...,v_{k}\}$$ $k$ is unknown, and for $i\neq j$, drawing a $v_i$-type marble might be more likely than drawing a $v_j$-type marble.

In an experiment, a machine samples the vat using some unknown procedure. The machine reports a set $X$ describing $q\leq k$ varieties of marbles from its sample: $$ X \subseteq \mathcal{V}; \quad |X|=q$$

Trials of this experiment are repeated ($q$ is fixed across trials) and we get a sequence of subsets of $\mathcal{V}$, $(X_1,X_2,\dots)$.

The only other things we know are:

• trials are independent and identical
• the machine reports the top $q$ most frequently occurring varieties in its sample

We don't know precisely how the machine samples marbles. It could pick a large number of marbles, then report the $q$ most frequent. Alternatively, it could keep picking up marbles until there are $q$ varieties. There are other things it could do too.

Will the distribution of our trials $(X_1,X_2,\dots)$ be affected by the machine's sampling procedure?

Answer 1

A simple way to verify that the method matters is to choose particular probabilities for types of marbles, and calculate the chance of each subset according to some methods. This can't prove that the method doesn't matter, though.

Suppose there are $3$ types and the chances of each type are $1/2$, $1/4$, and $1/4$, respectively. Suppose you are choosing $2$ types of marbles.

Suppose after choosing a marble, you ignore the rest of the kind. The chance you get $\lbrace v_2,v_3\rbrace$ is $2*1/4*1/3 = 1/6$.

Suppose you reject pairs with repeated types. The chance of $\lbrace v_2,v_3\rbrace$ is $$\frac{2*1/4*1/4}{2*1/4*1/4 + 2*1/2*1/4 + 2*1/2*1/4} = \frac{1/8}{1/8 + 1/4 + 1/4} = 1/5.$$

Since these are different, the method the machine uses matters. Rejecting pairs with repeated types tends to weight the pairs with common types less.

Two of the methods you mention are equivalent. Ignoring the rest of its kind after picking a marble is the same as picking until you have $q$ different types.