Is sampling without replacement well-defined on an infinite set?

Question

In a finite set, the concept of sampling with or without replacement is both well-defined. But is it the case for an infinite set?

In other words, if X is finite, then

Choosing 5 things at the same time from `X`

and

Choosing 5 things sequentially from `X`

are different.

For one, the former is combination and the latter is permutation.

But are they any different if X is infinite?

Answer 1

For a continuous distribution (including uniform on an interval), the probability that a sample size two with replacement has identical values is $0$, so there is no substantial difference. For a discrete distribution, you cannot have an infinite population to sample from with a uniform distribution, preventing this being realistic.

So the interesting case is sampling without replacement from a discrete infinite population with a non-uniform distribution. Here is an example:

Suppose you have to choose two distinct positive integers, where the weight for choosing $n\in \mathbb Z^+$ is said to be proportional to $2^{-n}$, and you want the probability that you choose $m$ and $n$ in no particular order

1. One approach (which I call a Wallenius approach) is to say that you choose successively, reweighting after the first pick to exclude the already picked integer, making the probability $$2^{-m}\times \dfrac{2^{-n}}{1-2^{-m}}+2^{-n}\times \dfrac{2^{-m}}{1-2^{-n}} = 2^{-m-n}\left( \frac{1}{1-2^{-m}}+\frac{1}{1-2^{-n}}\right)$$

2. Another approach (which I call a naive approach) is to say that the combined probabilities are proportional to $2^{-m-n}$ but need to add up to $1$, making the probability $$\dfrac{ 2^{-m-n}}{\sum_{j=1}^\infty \sum_{k=j+1}^\infty 2^{-j-k}} = 3 \times 2^{-m-n}$$

3. A third approach (which I call a Fisher approach) is to say that each integer may be picked with probabilities $2^{-n}$ or not picked with probability $1-2^{-n}$, and you condition on exactly two integers being picked, making the probability $$\dfrac{ \prod_{l\not \in \{m,n\}} 2^{-m}2^{-n}(1-2^{-l})}{\sum_{j=1}^\infty \sum_{k=j+1}^\infty \prod_{l\not \in \{j,k\}} 2^{-j}2^{-k}(1-2^{-l})}=\dfrac{ \frac{2^{-m-n}}{(1-2^{-m})(1-2^{-n})}}{\sum_{j=1}^\infty \sum_{k=j+1}^\infty \frac{2^{-j-k}}{(1-2^{-j})(1-2^{-k})}} \\ \approx \frac{1.38491631755}{(2^{m}-1)(2^{n}-1)}$$

4. A fourth approach (which I call marginal) would be to observe that if the probability of choosing distinct $m$ and $n$ is $$2^{2-m-n} \text{ when one of } m \text{ and } n \text{ is }1 \\ 0 \text{ when neither of } m \text{ and } n \text{ is }1 $$ then the marginal probability of picking $n$ is $2^{1-n}$ and this is proportional to $2^{-n}$; clearly you have probability $1$ that $1$ is one of the two numbers picked

The sequential Wallenius approach is closer in concept to permutations and is perhaps the easiest to contemplate physically, while the other three are closer to combinations. The different approaches give different probabilities for various events for the same weights, as shown in the table below, though it would be possible to use different weights for the different approaches which could give more similar actual distributions

                                        Wallenius naive   Fisher  marginal
Probability choosing 1 and 2             0.4167   0.375   0.4616   0.5     
Probability choosing 1 and 3             0.1964   0.1875  0.1978   0.25     
Probability choosing 2 and 3             0.0774   0.0938  0.0659   0     
Probability choosing 1 and another       0.8033   0.75    0.8402   1     
Probability choosing 2 and another       0.5683   0.5625  0.5878   0.5     
Probability choosing 3 and another       0.3080   0.3281  0.2896   0.25     

Answer 2

One key thing you don't seem to be considering is that "choosing" from a set, finite or infinite, at random requires a probability distribution. Precisely how are you choosing from your set? In the finite case you can say something like "uniformly at random", but that is not a valid distribution on an infinite set.

Once you pick a distribution, sampling with replacement is definitely fine. But what about sampling without replacement? You would have to tell me how the distribution evolves. In the finite case, you can say something like "it's still uniform", but in the infinite case it may not be clear what kind of distribution you inherit from removing one element.

And the picture truly gets worse if the set isn't countably infinite, or if the distribution isn't discrete. So to answer your question, it really doesn't make sense to talk about sampling at all, replacement or not, until you start fixing distributions.