# How to sample so that there is equal inclusion probability for each member of the population?

Suppose we have a population where $a$ boys below 15 years are white, $b$ boys above 15 years are white, $c$ boys below 15 years are black and $d$ boys above 15 years are black. Describe a way to select $3$ boys from them so that each skin colour and each age group is represented, and the probability of inclusion of any individual in the sample is the same.

My thoughts: Number the boys as $1,2,...,a+b+c+d$. Draw a random number in $\{1,2,...,a+b+c+d\}$ and select three boys. If they satisfy the mentioned properties keep this triplet. Else reject this triplet and go for another random selection. Repeat until you get a triplet.

Does this make sense? This is similar to what we do in selecting a person with a coin. But does it work here?

• This is not clear. Rejection sampling may be one way to pick equally from the 4 groups, [white, above 15], [white, below 15], [black, above 15] and [black, below 15]. When sampling without replacement from a group you can start picking with replacement and reject the repeats continuing until you get the required sample size n. Typical n << N where N is the population size. There are other ways to do the randomization without rejection sampling. Jan 9, 2017 at 3:57
• In this case I don't see why you don't just pick an n<a, n< b, n<c and n<d and then sample n from each of the 4 groups. You would have a total of 4n samples with the same number in each group. Jan 9, 2017 at 4:00
• Instead of "the probability of inclusion of any individual in the sample is the same" do you mean "the probability of selecting any valid configuration is equal"? Jan 9, 2017 at 4:21
• The reference is Discrete Event Simulation by George S. Fishman Springer 2001. I am familiar with early versions of a similiar book. Jan 9, 2017 at 4:28
• I think @josliber comment about the meaning of your criteria is a sound one. I do not see how you can select so that each individual has the same chance of being picked. Consider for example $a=b=c=1$ and $d=10000$ Jan 9, 2017 at 11:28

This is an important and interesting question because it sheds light on the nature of sampling and on how badly it can go wrong when seemingly innocuous constraints are imposed.

This answer shows how to obtain a general expression for a solution (in which individuals within each group are indistinguishable). It then exhibits some necessary conditions the counts $$a,b,c,d$$ must satisfy in order for there to exist a solution at all. Finally, it illustrates the approach with an explicit solution for one example.

In a final section it discusses the rejection sampling scheme proposed in the question.

There are four disjoint categories of "units" in the population, which I will call $$A,$$ $$B,$$ $$C,$$ and $$D,$$ having counts $$a,$$ $$b,$$ $$c,$$ and $$d,$$ respectively. We wish to obtain samples of three distinct units in which at least one is from $$A\cup B$$ ("white boys"), at least one from $$C\cup D$$ ("black boys"), at least one from $$A\cup C$$ ("below 15 years"), and at least one from $$B\cup D$$ ("above 15 years").

In any sample $$\{x_1,x_2,x_3\}$$ order the units alphabetically by category and label that sample by the corresponding sequence of categories. The allowable labels are readily found: they are among

$$AAD, ABC, ABD, ACD, ADD, BBC, BCC, BCD.$$

(Some of these labels cannot appear when any of $$a,b,c,d$$ are less than $$2.$$ I will ignore this complication in all subsequent calculations.)

For instance, $$AAD$$ means the sample consists of two under-15 white boys and one over-15 black boy: all four categories are represented. By contrast, a sample with label $$BDD$$ would consist of one over-15 white boy and two over-15 black boys: there would be no representative of the under-15 category.

We have in effect partitioned the set of all allowable samples into eight types according to their labels. For simplicity, let's look for two-step solutions in which (1) a label $$\mathcal L$$ is selected with probability $$\pi_\mathcal{L}$$ and then (2) one of the possible samples with label $$\mathcal L$$ is selected randomly and equiprobably. This approach avoids distinguishing individuals within the four categories--a natural and useful simplification.

The task is to find a set of label-selection probabilities $$\{\pi_{AAD}, \pi_{ABC}, \ldots, \pi_{BCD}\}$$ that achieve equal inclusion probabilities for all units in the population. To do this, we will need to compute the inclusion probabilities for each label. As a matter of notation--I'm including it for clarity, but hope not to use it much in the sequel--write these conditional inclusion probabilities as

$$p(\mathcal C\mid {\mathcal L}) = \Pr\left(\text{a particular individual in category } \mathcal C \text{ is in the sample given label }\mathcal L \text{ is drawn}\right).$$

Consider:

• In any of the four labels with distinct categories, such as $$ABC,$$ the chance that any individual in category $$A$$ will be in the sample is $$1/a$$ (and likewise for individuals in the other categories in the label). This means $$p(A\mid {ABC})=\frac{1}{a};\quad p(B\mid {ABC})=\frac{1}{b};\quad p(C\mid {ABC})=\frac{1}{c}.$$

• In any of the remaining four labels like $$AAD$$ with just two distinct categories, there are two individuals from $$A$$ and one from $$D$$ in each sample. Thus, the chance of including a particular individual in $$A$$ is $$2/a$$ while the chance of including a particular individual in $$D$$ is $$1/d.$$ Thus $$p(A\mid {AAD})=\frac{2}{a};\quad p(D\mid {AAD})=\frac{1}{d}.$$

Then, for $$\mathcal C \in \{A,B,C,D\}$$ the law of conditional probability asserts that the inclusion probability of any given individual in $$\mathcal C,$$ written $$p(\mathcal C),$$ is

$$p(\mathcal C) = \sum_{\mathcal{L}\in\text{ Labels}} p(\mathcal C\mid {\mathcal L}) \pi_\mathcal{L}.\tag{1}$$

Since the sample size is $$3,$$ the population size is $$a+b+c+d,$$ and no sample includes any individual more than once, these probabilities must all be equal to $$3/(a+b+c+d).$$ The four conditions $$(1),$$ in conjunction with the axiomatic fact that probabilities sum to unity,

$$1 = \sum_{\mathcal{L}\in\text{ Labels}} \pi_\mathcal{L},$$

yield a set of five simultaneous (but slightly redundant) linear equations to be satisfied by the eight non-negative probabilities $$\pi_\mathcal{L}.$$ This is a linear program that is readily solved using many methods, such as the Simplex Method. It may have anywhere from no solutions through a four-dimensional polytope of solutions. This will become evident in the following example and discussion.

It turns out some general results can be obtained. One most general solution (in which the signs of the $$\pi_\mathcal{L}$$ are unconstrained) is

$$(a+b+c+d)\pmatrix{\pi_{BCD}\\ \pi_{AAD}\\ \pi_{ACD}\\ \pi_{CCB}} = \pmatrix{2(b+d)-(a+c)-(\pi_{ABD}+\pi_{ADD})\\ 2(a+b)-(c+d)-(\pi_{ABC}+\pi_{ABD}+\pi_{BBC})\\ 2(c+d)-(a+4b) + (\pi_{ABC}+\pi_{ABD} + 2\pi_{BBC} - \pi_{ADD}) \\ a+b+c-2d + (\pi_{ADD} - \pi_{ABC} - \pi_{BBC})}.\tag{2}$$

Since all the $$\pi_\mathcal{L}$$ are nonnegative, the first two equalities imply

$$2(b+d)\ge a+c;\quad 2(a+b) \ge c+d.\tag{3}$$

In words: no row sum may be more than twice the other row sum, and likewise for the column sums, in the two-by-two table of counts $$\pmatrix{a & b\\c & d}.$$

Thus, for this approach (where individuals within each category are not distinguished) to work, these constraints must hold. Otherwise it is impossible to obtain the desired sample.

To drive the results home, let's work a small example. Suppose $$(a,b,c,d)=(2,2,2,3).$$ The constraints $$(3)$$ are satisfied. Let's pick the solution $$(2)$$ determined by $$(\pi_{ABC}, \pi_{ABD}, \pi_{ADD}, \pi_{BCC}) = (0,0,0,0).$$ It is

$$(2+2+2+3)\pmatrix{\pi_{BCD}\\ \pi_{AAD}\\ \pi_{ACD}\\ \pi_{CCB}} = \pmatrix{2(2+3)-(2+2)\\ 2(2+2)-(2+3)\\ 2(2+3)-(2+4(2)) \\ 2+2+2-2(3)} = \pmatrix{6\\ 3\\ 0 \\ 0}.$$

Thus, this sampling scheme works by selecting the label $$BCD$$ with probability $$6/9=2/3$$ and otherwise selecting the label $$AAD$$ with probability $$1/3.$$

• When label $$BCD$$ is chosen, the expected number of occurrences of a given individual in $$A$$ is $$0;$$ of an individual in $$B$$ or $$C$$ is $$1/2;$$ and of an individual in $$D$$ is $$1/3.$$

• When label $$AAD$$ is chosen, the expected number of occurrences of a given individual in $$A$$ is $$1;$$ of an individual in $$B$$ or $$C$$ is $$0;$$ and of an individual in $$D$$ is $$1/3.$$

Applying $$(1)$$ we find all the chances are equal to $$1/3,$$ as intended.

It is noteworthy that in this sampling scheme, the only time that two individuals in the same group can appear in a sample is for group $$A.$$ In effect, although the individual selection probabilities are equal, the joint selection probabilities are radically different.

If you would like to explore this further, I offer another solution:

$$(\pi_{ABC}, \pi_{ABD}, \pi_{BCD}, \pi_{ACD}, \pi_{AAD}, \pi_{ADD}, \pi_{BBC}, \pi_{CCB}) = (1,4,6,4,2,7,3,3)/30.$$

In this solution all eight labels can appear and it is possible for two individuals within any of the four groups to be included simultaneously in the sample. For most practical problems it is probably wise to choose solutions that give positive probabilities of the widest possible sets of joint inclusions.

Finally, let's discuss the rejection sampling scheme described in the question. Consider our running example with $$(a,b,c,d)=(2,2,2,3).$$ From this population of $$a+b+c+d=9$$ individuals there are $$\binom{9}{3}=84$$ possible samples. Brute force enumeration shows that only $$57$$ of them are allowable. Within these $$57,$$ any given individual in $$A$$ appears $$22$$ times, any given individual in $$B$$ or $$C$$ appears $$19$$ times, and any given individual in $$D$$ appears only $$17$$ times. Because all allowable samples are equally likely to be chosen, the inclusion probabilities are $$22/57=1/3+1/19,$$ $$19/57=1/3,$$ and $$17/57=1/3-2/19.$$ They are unequal.

Intuitively, this imbalance makes sense. In an extreme case, where say $$(a,b,c,d)=(2,2,2,d)$$ with large $$d,$$ any allowable sample must contain at least one element of $$A,$$ $$B,$$ or $$C.$$ Although these are rare subsets of the population, these elements are over-represented in them, to the detriment of elements of $$d.$$ It's not hard to work out the exact probabilities, but since that's just an exercise in combinatorics and provides little additional insight, I will forgo the demonstration. Suffice it to say that as $$d$$ grows, the relative selection chances of individuals in group $$D$$ decrease to zero (they are proportional to $$1/d$$).

The moral is that you need to really understand the implications of even the mildest-seeming restrictions on your random samples before you can analyze them correctly. You cannot just assume the resulting sample will be random or even "representative" in any meaningful sense. For a practical example of why we ought to be concerned, see this question about creating samples for controlled drug trials.