Suppose that we have a population \(D\) of \(m\) objects. The population could be a deck of cards, a set of people, an urn full of balls, or any number of other collections. In many cases, we simply label the objects from 1 to \(m\), so that \(D = \{1, 2, \ldots, m\}\). In other cases (such as the card experiment), it may be more natural to label the objects with vectors. In any case, \(D\) is usually a finite subset of \(\R^k\) for some \(k \in \N_+\).
The basic experiment consists of selecting \(n\) objects from the population \(D\) at random and recording the sequence of objects chosen. Thus, the outcome is \(\bs{X} = (X_1, X_2, \ldots, X_n)\) where \(X_i \in D\) is the \(i\)th object chosen.
From the multiplication rule of combinatorics,
With either type of sampling, we assume that the samples are equally likely and thus that the outcome variable \(\bs{X}\) is uniformly distributed on the appropriate sample space \(S\); this is the meaning of the phrase random sample: \[ \P(\bs{X} \in A) = \frac{\#(A)}{\#(S)}, \quad A \subseteq S \]
Suppose again that we select \(n\) objects at random from the population \(D\), either with or without replacement and record the ordered sample \(\bs{X} = (X_1, X_2, \ldots, X_n)\)
Any permutation of \(\bs{X}\) has the same distribution as \(\bs{X}\) itself, namely the uniform distribution on the appropriate sample set \(S\):
A sequence of random variables with this property is said to be exchangeable. Although this property is very simple to understand, both intuitively and mathematically, it is nonetheless very important. We will use the exchangeable property often in this chapter.
More generally, any sequence of \(k\) of the \(n\) outcome variables is uniformly distributed on the appropriate sample set:
In particular, for either sampling method, \(X_i\) is uniformly distributed on \(D\) for each \(i \in \{1, 2, \ldots, n\}\).
If the sampling is with replacement then \(\bs{X} = (X_1, X_2, \ldots, X_n)\) is a sequence of independent random variables.
Thus, when the sampling is with replacement, the sample variables form a random sample from the uniform distribution, in statistical terminology.
If the sampling is without replacement, then the conditional distribution of a sequence of \(k\) of the outcome variables, given the values of a sequence of \(j\) other outcome variables, is the uniform distribution on the set of permutations of size \(k\) chosen from the population when the \(j\) known values are removed (of course, \(j + k \le n\)).
In particular, \(X_i\) and \(X_j\) are dependent for any distinct \(i\) and \(j\) when the sampling is without replacement.
In many cases when the sampling is without replacement, the order in which the objects are chosen is not important; all that matters is the (unordered) set of objects: \[ \bs{W} = \{X_1, X_2, \ldots, X_n\} \] The random set \(\bs{W}\) takes values in the set of combinations of size \(n\) chosen from \(D\): \[ T = \left\{ \{x_1, x_2, \ldots, x_n\}: x_i \in D \text{ for each } i \text{ and } x_i \ne x_j \text{ for all } i \ne j \right\} \]
Recall that \(\#(T) = \binom{m}{n}\).
\(\bs{W}\) is uniformly distributed over \(T\): \[ \P(\bs{W} \in B) = \frac{\#(B)}{\#(T)} = \frac{\#(B)}{\binom{m}{n}}, \quad B \subseteq T \]
For any combination of size \(n\) from \(D\), there are \(n!\) permutations of size \(n\).
Suppose now that the sampling is with replacement, and we again denote the unordered outcome by \(\bs{W}\). In this case, \(\bs{W}\) takes values in the collection of multisets of size \(n\) from \(D\). (A multiset is like an ordinary set, except that repeated elements are allowed). \[ T = \left\{ \{x_1, x_2, \ldots, x_n\}: x_i \in D \text{ for each } i \right\} \]
Recall that \(\#(T) = \binom{m + n - 1}{n}\).
\(\bs{W}\) is not uniformly distributed on \(T\).
The following table summarizes the formulas for the number of samples of size \(n\) chosen from a population of \(m\) elements, based on the criteria of order and replacement.
| Replacement | Order | With | Without |
|---|---|---|
| With | \(m^n\) | \(\binom{m + n - 1}{n}\) |
| Without | \(m^{(n)}\) | \(\binom{m}{n}\) |
Suppose that a sample of size 2 is chosen from the population \(\{1, 2, 3, 4\}\). Explicitly list all samples in the following cases:
A dichotomous population consists of two types of objects.
Suppose that a batch of 100 components includes 10 that are defective. A random sample of 5 components is selected without replacement. Compute the probability that the sample contains at least one defective component.
0.4162
An urn contains 50 balls, 30 red and 20 green. A sample of 15 balls is chosen at random. Find the probability that the sample contains 10 red balls in each of the following cases:
In the ball and urn experiment select 50 balls with 30 red balls, and sample size 15. Run the experiment 100 times. Compute the relative frequency of the event that the sample has 10 red balls in each of the following cases, and compare with the respective probability in the previous exercise:
Suppose that a club has 100 members, 40 men and 60 women. A committee of 10 members is selected at random (and without replacement, of course).
Suppose that a small pond contains 500 fish, 50 of them tagged. A fisherman catches 10 fish. Find the probability that the catch contains at least 2 tagged fish.
0.2635
The basic distribution that arises from sampling without replacement from a dichotomous population is studied in the section on the hypergeometric distribution. More generally, a multi-type population consists of objects of \(k\) different types.
Suppose that a legislative body consists of 60 republicans, 40 democrats, and 20 independents. A committee of 10 members is chosen at random. Find the probability that at least one party is not represented on the committee.
0.1633. Use the inclusion-exclusion law.
The basic distribution that arises from sampling without replacement from a multi-type population is studied in the section on the multivariate hypergeometric distribution.
Recall that a standard card deck can be modeled by the product set \[ D = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \jack, \queen, \king\} \times \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\} \] where the first coordinate encodes the denomination or kind (ace, 2-10, jack, queen, king) and where the second coordinate encodes the suit (clubs, diamonds, hearts, spades). The general card experiment consists of drawing \(n\) cards at random and without replacement from the deck \(D\). Thus, the \(i\)th card is \(X_i = (Y_i, Z_i)\) where \(Y_i\) is the denomination and \(Z_i\) is the suit. The special case \(n = 5\) is the poker experiment and the special case \(n = 13\) is the bridge experiment. Note that with respect to the denominations or with respect to the suits, a deck of cards is a multi-type population as discussed above.
In the card experiment with \(n = 5\) cards (poker), there are
In the card experiment with \(n = 13\) cards (bridge), there are
In the card experiment, set \(n = 5\). Run the simulation 5 times and on each run, list all of the (ordered) sequences of cards that would give the same unordered hand as the one you observed.
In the card experiment,
In the card experiment, \(Y_i\) and \(Z_j\) are independent for any \(i\) and \(j\).
In the card experiment, \((Y_1, Y_2)\) and \((Z_1, Z_2)\) are dependent.
Suppose that a sequence of 5 cards is dealt. Find each of the following:
Run the card experiment 500 time. Compute the relative frequency corresponding to each probability in the previous exercise.
Find the probability that a bridge hand will contain no cards of denomination 10, jack, queen, king, or ace. Such a hand is called a Yarborough, in honor of the second Earl of Yarborough.
0.000547
Rolling \(n\) fair, six-sided dice is equivalent to choosing a random sample of size \(n\) with replacement from the population \(\{1, 2, 3, 4, 5, 6\}\). Generally, selecting a random sample of size \(n\) with replacement from \(D = \{1, 2, \ldots, m\}\) is equivalent to rolling \(n\) fair, \(m\)-sided dice.
In the game of poker dice, 5 standard, fair dice are thrown. Find each of the following:
Run the poker dice experiment 500 times. Compute the relative frequency of each event in the previous exercise and compare with the corresponding probability.
The game of poker dice is treated in more detail in the chapter on games of chance.
Supposes that we select \(n\) persons at random and record their birthdays. If we assume that birthdays are uniformly distributed throughout the year, and if we ignore leap years, then this experiment is equivalent to selecting a sample of size \(n\) with replacement from \(D = \{1, 2, \ldots, 365\}\). Similarly, we could record birth months or birth weeks.
Suppose that a probability class has 30 students. Find each of the following:
In the birthday experiment, set \(m = 365\) and \(n = 30\). Run the experiment 1000 times and compare the relative frequency of each event in the previous exercise to the corresponding probability.
The birthday problem is treated in more detail later in this chapter.
Suppose that we distribute \(n\) distinct balls into \(m\) distinct cells at random. This experiment also fits the basic model, where \(D\) is the population of cells and \(X_i\) is the cell containing the \(i\)th ball. Sampling with replacement means that a cell may contain more than one ball; sampling without replacement means that a cell may contain at most one ball.
Suppose that 5 balls are distributed into 10 cells (with no restrictions). Find each of the following:
Suppose that when we purchase a certain product (bubble gum, or cereal for example), we receive a coupon (a baseball card or small toy, for example), which is equally likely to be any one of \(m\) types. We can think of this experiment as sampling with replacement from the population of coupon types; \(X_i\) is the coupon that we receive on the \(i\)th purchase.
Suppose that a kid's meal at a fast food restaurant comes with a toy. The toy is equally likely to be any of 5 types. Suppose that a mom buys a kid's meal for each of her 3 kids. Find each of the following:
The coupon collector problem is studied in more detail later in this chapter.
Suppose that a person has \(n\) keys, only one of which opens a certain door. The person tries the keys at random. We will let \(N\) denote the trial number when the person finds the correct key.
Suppose that unsuccessful keys are discarded (the rational thing to do, of course). Then \(N\) has the uniform distribution on \(\{1, 2, \ldots, n\}\).
Suppose that unsuccessful keys are not discarded (perhaps the person has had a bit too much to drink). Then \(N\) has a geometric distribution on \(\N_+\).
It's very easy to simulate a random sample of size \(n\), with replacement from \(D = \{1, 2, \ldots, m\}\). Recall that the ceiling function \(\lceil x \rceil\) gives the smallest integer that is at least as large as \(x\).
Let \(\bs{U} = (U_1, U_2, \ldots, U_n)\) be a sequence of be a random numbers. Recall that these are independent random variables, each uniformly distributed on the interval \([0, 1]\) (the standard uniform distribution). Then \(X_i = \lceil m \, U_i \rceil\) for \(i \in \{1, 2, \ldots, n\}\) simulates a random sample, with replacement, from \(D\).
It's a bit harder to simulate a random sample of size \(n\), without replacement, since we need to remove each sample value before the next draw.
The following algorithm generates a random sample of size \(n\), without replacement, from \(D\).