I got into a debate with someone in class over an experiment that was claimed to be randomized.

The experiment was such that there is a bucket of distinct objects, and objects were being "randomly" (but independently) selected from the bucket. There are $N$ objects in the bucket, and $M$ random selections are made. The experiment was conducted such that $M>>N$, but $M$ is finite.

It was claimed that this experiment (choosing objects $M$ times) was conducted "randomly," and also that the experiment GUARANTEED that all $N$ objects would be chosen at least once. I think that "randomly" and "GUARANTEED" are mutually exclusive in this instance.

I made the argument that if the experiment guarantees that all $N$ objects would be chosen at least once, then the selections are not conducted randomly. To guarantee that all $N$ objects are selected, with a finite $M$ (albeit being much larger than $N$) would remove the randomness in my opinion? Am I right, or is it possible for this to still be random while guaranteeing all objects are selected at least once?

Note that I am not asking what is the probability of selecting all $N$ samples by making $M$ selections, where $M>>N$. I understand the probability here is close to 1. For the probability to be equal to 1, then $M\rightarrow\infty$.

  • $\begingroup$ You can select $M=N$ times randomly from $N$ objects and still guarantee each has been selected: just mix the objects up thoroughly and withdraw them from their population one at a time without replacement. This (standard) example shows that "random" and "guarantee" are not necessarily mutually exclusive properties. $\endgroup$ – whuber Mar 31 '19 at 15:27

There’s a distinction between asking what you’ve picked after $M$ draws, vs conditioning on the event that you’ve picked all $N$ objects after $N$ draws. The latter event is still random, for example, the total number of times each object was chosen will again be random.

| cite | improve this answer | |
  • $\begingroup$ Sorry, I don't think I understand. They claimed the experiment GUARANTEED that each of the $N$ objects would be drawn at least once, but that the selections were performed "randomly." I don't see how an experiment that was making $M$ draws can "guarantee" that all $N$ objects are selected at least once? $\endgroup$ – anonuser01 Mar 31 '19 at 2:40
  • 1
    $\begingroup$ If the selections are independent and random, then definitely there’s no guarantee (with probability 1), that each object will be picked at least once. $\endgroup$ – Alex R. Mar 31 '19 at 2:42
  • $\begingroup$ Yeah I agree, and that was the point that I was trying to make in the OP as well as during my class debate. The person seemed to suggest that because $M>>N$, this is what "guaranteed" each object was picked at least once. I think he might have used his empirical observations (which showed that each object was drawn at least once for all the experiments they conducted) to make a generalization that the probability is 1. In reality, the probability is probably close to 1, given that $M>>N$, so he may have just been lazy with words. $\endgroup$ – anonuser01 Mar 31 '19 at 2:51
  • $\begingroup$ Right. There is on the other hand a concept of “waiting time” (or stopping time) in this case which is the first time at which you collect at least one of each object. This time is finite with probability 1. $\endgroup$ – Alex R. Mar 31 '19 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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