We have insisted in the foregoing that the experiment of drawing a sample from an urn should always be performed in such a manner that one may speak of the first ball drawn, the second ball drawn, etc. Now it is clear that sampling need not be done in this way. Especially if one is sampling without replacement, the balls in the sample may be extracted from the urn not one at a time but all at once. For example, as in a bridge game, one may extract 13 cards from a deck of cards and examine them after all have been received and rearranged. If \(n\) balls are extracted all at once from an urn containing \(M\) balls, numbered 1 to \(M\) , the outcome of the experiment is a subset \(\left\{z_{1}, z_{2}, \ldots, z_{n}\right\}\) of the numbers 1 to \(M\) , rather than an \(n\) -tuple \(\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) whose components are numbers 1 to \(M\) .

We are thus led to define the notions of ordered and unordered samples. A sample is said to be ordered if attention is paid to the order in which the numbers (on the balls in the sample) appear. A sample is said to be unordered if attention is paid only to the numbers that appear in the sample but not to the order in which they appear. The sample description space of the random experiment of drawing (with or without replacement) an ordered sample of size \(n\) from an urn containing \(M\) balls numbered 1 to \(M\) consists of \(n\) -tuples \(\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) , in which each component \(z_{j}\) is a number 1 to \(M\) . The sample description space \(S\) of the random experiment of drawing (with or without) replacement an unordered sample of size \(n\) from an urn containing \(M\) balls numbered 1 to \(M\) consists of sets \(\left\{z_{1}, z_{2}, \ldots, z_{n}\right\}\) of size \(n\) , in which each member \(z_{j}\) is a number 1 to \(M\) .

We next compute the size of \(S\) . In the case of unordered samples, drawn without replacement, it is clear that \(N[S]=\left(\begin{array}{c}M \\ n\end{array}\right)\) , since the number of unordered samples of size \(n\) is the same as the number of subsets of size \(n\) of the set \(\{1,2, \ldots, M\}\) . In the case of unordered samples drawn with replacement, one may show (see theoretical exercise 5.2 ) that \(N[S]=\) \(\left(\begin{array}{c}M+n-1 \\ n\end{array}\right)\) .

In section 3 the problem of the number of successes in a sample was considered under the assumption that the sample was ordered. Suppose now that an unordered sample of size \(n\) is drawn from an urn containing \(M\) balls, of which \(M_{W}\) are white. Let us find, for \(k=0,1, \ldots, n\) , the probability of the event \(A_{k}\) that the sample will contain exactly \(k\) white balls. We consider first the case of sampling without replacement. Then \(N[S]=\left(\begin{array}{c}M \\ n\end{array}\right)\) . Next, \(N\left[A_{k}\right]=\left(\begin{array}{c}M_{W} \\ k\end{array}\right)\left(\begin{array}{c}M-M_{W} \\ n-k\end{array}\right)\) , since any description \(\left\{z_{1}, z_{2}, \ldots, z_{n}\right\}\) in \(A_{k}\) contains \(k\) white balls, which can be chosen in \(\left(\begin{array}{c}M_{W} \\ k\end{array}\right)\) ways, and \((n-k)\) nonwhite balls, which can be chosen in \(\left(\begin{array}{c}M-M_{W} \\ n-k\end{array}\right)\) ways. Consequently, in the case of unordered samples drawn without replacement \[P\left[A_{k}\right]=\frac{\left(\begin{array}{c} M_{W} \tag{5.1} \\ k \end{array}\right)\left(\begin{array}{c} M-M_{W} \\ n-k \end{array}\right)}{\left(\begin{array}{c} M \\ n \end{array}\right)}.\] 

It is readily verified that the value of \(P\left[A_{k}\right]\) , given by the model of unordered samples, agrees with the value of \(P\left[A_{k}\right]\) , given by the model of ordered samples, in the case of sampling without replacement. However, in the case of sampling with replacement the probability that an unordered sample of size \(n\) , drawn from an urn containing \(M\) balls, of which \(M_{W}\) are white, will contain exactly \(k\) white balls is equal to \[P\left[A_{k}\right]=\frac{\left(\begin{array}{c} M_{W}+k-1 \tag{5.2} \\ k \end{array}\right)\left(\begin{array}{c} M-M_{W}+n-k-1 \\ n-k \end{array}\right)}{\left(\begin{array}{c} M+n-1 \\ n \end{array}\right)},\] 

which does not agree with the value of \(P\left[A_{k}\right]\) , given by the model of ordered samples.

Example 5B . Distributing balls among urns (the occupancy problem) . Suppose that we are given \(M\) urns, numbered 1 to \(M\) , among which we are to distribute \(n\) balls, where \(n. What is the probability that each of the urns numbered 1 to \(n\) will contain exactly 1 ball?

 

Solution

Let \(A\) be the event that each of the urns numbered 1 to \(n\) will contain exactly 1 ball. In order to determine the probability space on which the event \(A\) is defined, we must first make assumptions regarding (i) the distinguishability of the balls and (ii) the manner in which the distribution of balls is to be carried out.

 

If the balls are regarded as being distinguishable (by being labeled with the numbers 1 to \(n\) ), then to describe the results of distributing \(n\) balls among the \(N\) urns one may write an \(n\) -tuple \(\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) , whose \(j\) th component \(z_{j}\) designates the number of the urn in which ball \(j\) was deposited. If the balls are regarded as being all alike, and therefore indistinguishable, then to describe the results of distributing \(n\) balls among the \(N\) urns one may write a set \(\left\{z_{1}, z_{2}, \ldots, z_{n}\right\}\) of size \(n\) , in which each member \(z_{j}\) represents the number of an urn into which a ball has been deposited. Thus ordered and unordered samples correspond in the occupancy problem to distributing distinguishable and indistinguishable balls, respectively. 

Next, in distributing the balls, one may or may not impose an exclusion rule to the effect that in distributing the balls one ball at most may be put into any urn. It is clear that imposing an exclusion rule is equivalent to choosing the urn numbers (sampling) without replacement, since an urn may be chosen once at most. If an exclusion rule is not imposed, so that in any urn one may deposit as many balls as one pleases, then one is choosing the urn numbers (sampling) with replacement.

Let us now return to the problem of computing \(P[A]\) . The size of the sample description space is given in Table 5A for each of the various possible cases. Next, let us determine the size of \(A\) . Whether or not an exclusion rule is imposed, we obtain \(N[A]=n\) ! if the balls are distinguishable and \(N[A]=1\) if the balls are indistinguishable. Consequently, if the balls are distinguishable and distributed without exclusion, \[P[A]=\frac{n !}{M^{n}}; \tag{5.3}\] if the balls are indistinguishable and distributed without exclusion, \[P[A]=\frac{1}{\left(\begin{array}{c} M+n-1 \tag{5.4} \\ n \end{array}\right)};\] if the balls are distributed with exclusion, it makes no difference whether the balls are considered distinguishable or indistinguishable, since \[P[A]=\frac{n !}{(M)_{n}}=\frac{1}{\left(\begin{array}{c} M \tag{5.5} \\ n \end{array}\right)}.\] 

Each of the different probability models for occupancy problems, described in the foregoing, find application in statistical physics . Suppose one seeks to determine the equilibrium state of a physical system composed of a very large number \(n\) of “particles” of the same nature: electrons, protons, photons, mesons, neutrons, etc. For simplicity, assume that there are \(M\) microscopic states in which each of the particles can be (for example, there are \(M\) energy levels that a particle can occupy). To describe the macroscopic state of the system, suppose that it suffices to state the \(M\) tuple \(\left(n_{1}, n_{2}, \ldots, n_{M}\right)\) whose \(j\) th component \(n_{j}\) is the number of “particles” in the \(j\) th microscopic state. The equilibrium state of the system of particles is defined as that macroscopic state \(\left(n_{1}, n_{2}, \ldots, n_{M}\right)\) with the highest probability of occurring. To compute the probability of any given macroscopic state, an assumption must be made as to whether or not the particles obey the Pauli exclusion principle (which states that there cannot be more than one particle in any of the microscopic states). If the indistinguishable particles are assumed to obey the exclusion principle, then they are said to possess Fermi-Dirac statistics. If the indistinguishable particles are not required to obey the exclusion principle, then they are said to possess Bose-Einstein statistics. If the particles are assumed to be distinguishable and do not obey the exclusion principle, then they are said to possess Maxwell-Boltzmann statistics. Although physical particles cannot be considered distinguishable, Maxwell-Boltzmann statistics are correct as approximations in certain circumstances to Bose-Einstein and Fermi-Dirac statistics.

The probability of various events defined on the general occupancy and sampling problems are summarized in Table 6A .

Partitioned Samples . If we examine certain card games, we may notice still another type of sampling. We may extract \(n\) distinguishable balls (or cards) from an urn (or deck of cards), which can then be divided into a number of subsets (in a bridge game, into four hands). More precisely, we may specify a positive integer \(r\) and nonnegative integers \(k_{1}, k_{2}, \ldots, k_{r}\) , such that \(k_{1}+k_{2}+\cdots+k_{r}=n\) . We then divide the sample of size \(n\) into \(r\) subsets; a first subset of size \(k_{1}\) , a second subset of size \(k_{2}, \ldots\) , an \(r\) th subset of size \(k_{r}\) . For example, in the game of bridge there are four hands (subsets), each of size 13, called East, North, West, and South (instead of first, second, third, and fourth subsets). The outcome of a sample taken in this way is an r-tuple of subsets , \[\left(\left\{z_{1}, \ldots, z_{k_{1}}\right\},\left\{z_{k_{1}+1}, \ldots, z_{k_{1}+k_{2}}\right\}, \ldots,\left\{z_{k_{1}+\cdots+k_{r-1}+1}, \ldots, z_{k_{1}+\cdots+k_{r}}\right\}\right) \tag{5.6}\] whose first component is the first subset, second component is the second subset, …, \(r\) th component is the \(r\) th subset. We call a sample of the form of (5.6) a partitioned sample , with partitioning scheme \(\left(r: k_{1}\right.\) , \(\left.k_{2}, \ldots, k_{r}\right)\) .

We next derive formulas for the number of ways in which partitioned samples may be drawn.

In the case of sampling without replacement from an urn containing \(M\) balls, numbered 1 to \(M\) , the number of possible partitioned samples of size \(n\) , with partitioning scheme \(\left(r ; k_{1}, k_{2}, \ldots, k_{r}\right)\) , is equal to \begin{align} \left(\begin{array}{c} M \\ k_{1} \end{array}\right)\left(\begin{array}{c} M-k_{1} \\ k_{2} \end{array}\right) \cdots\left(\begin{array}{c} M-k_{1}-\cdots-k_{r-1} \\ k_{r} \end{array}\right)= & \tag{5.7} \\ & \left(\begin{array}{c} M \\ k_{1} k_{2} \cdots k_{r} M-n \end{array}\right) . \end{align} 

Since there are \(\left(\begin{array}{l}M \\ k_{1}\end{array}\right)\) possible subsets of \(k_{1}\) balls, \(\left(\begin{array}{c}M-k_{1} \\ k_{2}\end{array}\right)\) possible subsets of \(k_{2}\) balls (there are \(M-k_{1}\) balls available from which to select the \(k_{2}\) balls to go into the second subset), it follows that there are \(\left(\begin{array}{c}M-k_{1}-\cdots-k_{r-1} \\ k_{r}\end{array}\right)\) ways in which to select the \(r\) th subset.

In the case of sampling with replacement from an urn containing \(M\) balls, numbered 1 to \(M\) , the number of possible partitioned samples of size \(n\) , with partitioning scheme \(\left(r ; k_{1}, k_{2}, \ldots, k_{r}\right)\) , is equal to \[\left(\begin{array}{c} M+k_{1}-1 \tag{5.8} \\ k_{1} \end{array}\right)\left(\begin{array}{c} M+k_{2}-1 \\ k_{2} \end{array}\right) \ldots\left(\begin{array}{c} M+k_{r}-1 \\ k_{r} \end{array}\right).\] 

The next example illustrates the theory of partitioned samples and provides a technique whereby card games such as bridge may be analyzed.

The interested reader may desire to consider for himself the theory of partitions that are unordered, rather than ordered, arrays of subsets.

Theoretical Exercises

Exercises