Unordered Samples and Occupancy Problems

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 balls are extracted all at once from an urn containing balls, numbered 1 to , the outcome of the experiment is a subset of the numbers 1 to , rather than an -tuple whose components are numbers 1 to .

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 from an urn containing balls numbered 1 to consists of -tuples , in which each component is a number 1 to . The sample description space of the random experiment of drawing (with or without) replacement an unordered sample of size from an urn containing balls numbered 1 to consists of sets of size , in which each member is a number 1 to .

Example 5A . All possible unordered samples of size 3 from an urn containing four balls . In example 1A we listed all possible sample descriptions in the case of the random experiment of drawing, with or without replacement, an ordered sample of size 3 from an urn containing four balls. We now list all possible unordered samples. If the sampling is done without replacement, then the possible unordered samples of size 3 that can be drawn are

If the sampling is done with replacement, then the possible unordered samples of size 3 that can be drawn are

,	,	,
,	,	,
,	,	,
,	,
,	,
,	,
,
,
,
,

We next compute the size of . In the case of unordered samples, drawn without replacement, it is clear that , since the number of unordered samples of size is the same as the number of subsets of size of the set . In the case of unordered samples drawn with replacement, one may show (see theoretical exercise 5.2 ) that .

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 is drawn from an urn containing balls, of which are white. Let us find, for , the probability of the event that the sample will contain exactly white balls. We consider first the case of sampling without replacement. Then . Next, , since any description in contains white balls, which can be chosen in ways, and nonwhite balls, which can be chosen in ways. Consequently, in the case of unordered samples drawn without replacement

It is readily verified that the value of , given by the model of unordered samples, agrees with the value of , 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 , drawn from an urn containing balls, of which are white, will contain exactly white balls is equal to

which does not agree with the value of , given by the model of ordered samples.

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

Solution

Let be the event that each of the urns numbered 1 to will contain exactly 1 ball. In order to determine the probability space on which the event 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 ), then to describe the results of distributing balls among the urns one may write an -tuple , whose th component designates the number of the urn in which ball was deposited. If the balls are regarded as being all alike, and therefore indistinguishable, then to describe the results of distributing balls among the urns one may write a set of size , in which each member 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 . 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 . Whether or not an exclusion rule is imposed, we obtain ! if the balls are distinguishable and if the balls are indistinguishable. Consequently, if the balls are distinguishable and distributed without exclusion, if the balls are indistinguishable and distributed without exclusion, if the balls are distributed with exclusion, it makes no difference whether the balls are considered distinguishable or indistinguishable, since

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 of “particles” of the same nature: electrons, protons, photons, mesons, neutrons, etc. For simplicity, assume that there are microscopic states in which each of the particles can be (for example, there are energy levels that a particle can occupy). To describe the macroscopic state of the system, suppose that it suffices to state the tuple whose th component is the number of “particles” in the th microscopic state. The equilibrium state of the system of particles is defined as that macroscopic state 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 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 and nonnegative integers , such that . We then divide the sample of size into subsets; a first subset of size , a second subset of size , an th subset of size . 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 , whose first component is the first subset, second component is the second subset, …, th component is the th subset. We call a sample of the form of (5.6) a partitioned sample , with partitioning scheme , .

Example 5C . An example of partitioned samples . Consider again the experiment of drawing a sample of size 3 from an urn containing four balls, numbered 1 to 4. If the sampling is done without replacement, and the sample is partitioned, with partitioning scheme , then the possible samples that could have been drawn are

,	,	,
,	,	,
,	,	,

If the sampling is done with replacement, and the sample is partitioned, with partitioning scheme , then the possible samples that could have been drawn are

,	,	,
,	,	,
,	,	,
,	,	,
,	,	,
,	,	,
,	,	,
,	,	,
,	,	,
,	,	,

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 balls, numbered 1 to , the number of possible partitioned samples of size , with partitioning scheme , is equal to

Since there are possible subsets of balls, possible subsets of balls (there are balls available from which to select the balls to go into the second subset), it follows that there are ways in which to select the th subset.

In the case of sampling with replacement from an urn containing balls, numbered 1 to , the number of possible partitioned samples of size , with partitioning scheme , is equal to

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

Example 5D . An urn contains fifty-two balls, numbered 1 to 52. Let the balls be drawn one at a time and divided among four players in the following manner: for , balls drawn on trials numbered (for ) are given to player . Thus player 1 gets the balls drawn on the first, fifth,…, forty-ninth draws, player 2 gets the balls drawn on the second, sixth, …, fiftieth draws, and so on. Suppose that the balls numbered 1, 11, 31, and 41 are considered “lucky”. What is the probability that each player will have a “lucky” ball?

Solution

Dividing the fifty-two balls drawn among four players in the manner described is exactly the same process as drawing, without replacement, a partitioned sample of size 52, with partitioning scheme . The sample description space of the experiment being performed here consists of 4-tuples of mutually exclusive subsets, of size 13, of the numbers 1 to 52, in which (for ) the th subset represents the balls held by the th player. The size of the sample description space is the number of ways in which a sample of fifty-two balls, partitioned in the way we have described, may be drawn from an urn containing fifty-two distinguishable balls. Thus

We next calculate the size of the event that each of the four players will have exactly one “lucky” ball. First, consider a description in that has the following properties: player 1 has ball number 11, player 2 has ball number 41, player 3 has ball number 1, and player 4 has ball number 31. Each description has forty-eight members about which nothing has been specified; consequently there are descriptions, for in this many ways can the remaining forty-eight balls be distributed among the members of the description. Now the four “lucky” balls can be distributed among the four hands in 4! ways. Consequently,

and the probability that each player will possess exactly one “lucky” ball is given by the quotient of (5.10) and (5.9) .

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

Theoretical Exercises

5.1 . An urn contains balls, numbered 1 to . A sample of size is drawn without replacement, and the numbers on the balls are arranged in increasing order of their numbers: . Let be a number 1 to , and , a number 1 to . Show the probability that is

5.2 . The number of unordered samples with replacement . Let denote the number of unordered samples of size that one may draw, by sampling with replacement, from an urn containing distinguishable balls. Show that .

Hint: . To prove the assertion, make use of the principle of mathematical induction. Let be the proposition that, whatever . P(1) is clearly true, since there are unordered samples of size 1. To complete the proof, we must show that implies . The following formula is immediately obtained: for any , and :

To obtain this formula, let the balls be numbered 1 to . Let each unordered sample be arrangéd so that the numbers of the balls in the sample are in non-decreasing order (as in the example in the text involving unordered samples of size 3 from an urn containing 4 balls). Then there are samples of size whose first entry is samples of size whose first entry is 2, and so on, until there are whose first entry is . Now, by the induction hypothesis, . Consequently, . We thus determine that , so that is proved, and the asserted formula for is proved by mathematical induction.

5.3 . Show that the number of ways in which indistinguishable objects may be arranged in distinguishable cells is .

5.4 . Let . Show that the number of ways in which indistinguishable objects may be arranged in distinguishable cells so that no cell will be empty is . Hint: It suffices to find the number of ways in which indistinguishable objects may be arranged in distinguishable cells, since after placing 1 object in each cell the remaining objects may be arranged without restriction.

Exercises

5.1 . On an examination the following question was posed: From a point on the base of a certain mountain there are 5 paths leading to the top of the mountain. In how many ways can one make a round trip (from the base to the top and back again)? Explain why each of the following 4 answers was graded as being correct: (i) , (ii) , (iii) , (iv) .

5.2 . A certain young woman has 3 men friends. She is told by a fortune teller that she will be married twice and that both her husbands will come from this group of 3 men. How many possible marital histories can this woman have? Consider 4 cases. (May she marry the same man twice? Does the order in which she marries matter?)

5.3 . The legitimate theater in New York gives both afternoon and evening performances on Saturdays. A man comes to New York one Saturday to attend 2 performances (1 in the afternoon and 1 in the evening) of the living theater. There are 6 shows that he might consider attending. In how many ways can he choose 2 shows? Consider 4 cases.

Answer

5.4 . An urn contains 52 balls, numbered 1 to 52. Let the balls be drawn 1 at a time and divided among 4 people. Suppose that the balls numbered , and 41 are considered “lucky”. What is the probability that (i) each person will have a “lucky” ball, (ii) 1 person will have all 4 “lucky” balls?

5.5 . A bridge player announces that his hand (of 13 cards) contains (i) an ace (that is, at least 1 ace), (ii) the ace of hearts. What is the probability that it will contain another one?

Answer

(i) ; (ii) .

5.6 . What is the probability that in a division of a deck of cards into 4 bridge hands, 1 of the hands will contain (i) 13 cards of the same suit, (ii) 4 aces and 4 kings, (iii) 3 aces and 3 kings?

5.7 . Prove that the probability of South’s receiving exactly aces when a bridge deck is divided into 4 hands is the same as the probability that a hand of 13 cards drawn from a bridge deck will contain exactly aces.

5.8 . An urn contains 8 balls numbered 1 to 8. Four balls are drawn without replacement; suppose is the second smallest of the 4 numbers drawn. What is the probability that ?

5.9 . A red card is removed from a bridge deck of 52 cards; 13 cards are then drawn and found to be the same color. Show that the (conditional) probability that all will be black is equal to .

5.10 . A room contains 10 people who are wearing badges numbered 1 to 10. What is the probability that if 3 persons are selected at random (i) the largest (ii) the smallest badge number chosen will be 5?

5.11 . From a pack of 52 cards an even number of cards is drawn. Show that the probability that half of these cards will be red and half will be black is Hint . Show, and then use (with ), the facts that for any integer

Unordered and Partitioned Samples-Occupancy Problems

Theoretical Exercises

Exercises

Quick Links

Social Media