Let \(n\) be a positive integer. Let \(S\) be the set of integers between \(1\) and \(n\). Consider the following process: We remove a number from \(S\) at random and write it down. We repeat this until \(S\) is empty. The result is a permutation of the integers from \(1\) to \(n\). Let \(X\) denote this permutation. Is \(X\) uniformly distributed?
Explanation of Answer
The permutation \(X\) that results from the described process is uniformly distributed among all possible permutations of the set \(S\). In this context, a uniformly distributed permutation means that each possible permutation of the set \(S\) is equally likely to occur.
When you remove the first number from \(S\), any of the \(n\) integers has an equal chance \(\frac{1}{n}\) of being chosen.
When you remove the second number, any of the remaining \(n-1\) numbers has an equal chance \(\frac{1}{n-1}\) of being chosen.
This process continues until the last number, which has a \(\frac{1}{1}\) chance of being chosen when it’s the only number left.
The probability of obtaining any specific permutation \(X\) is the product of the probabilities of selecting each element in its specific position in the permutation. This probability is \(\frac{1}{n} \times \frac{1}{n-1} \times \cdots \times \frac{1}{2} \times \frac{1}{1}\), which simplifies to \(\frac{1}{n!}\).
Since there are \(n!\) (n factorial) possible permutations of the set \(S\) and each permutation has a probability of \(\frac{1}{n!}\) of being selected, the process generates a uniformly distributed permutation of the set \(S\). This means that each of the \(n!\) permutations is equally likely to be the result \(X\) of the described process.
Suppose we are attending a college which has 3000 students. We wish to choose a subset of size 100 from the student body. Let \(X\) represent the subset, chosen using the following possible strategies. For which strategies would it be appropriate to assign the uniform distribution to \(X\)? If it is appropriate, what probability should we assign to each outcome?
(a) Take the first 100 students who enter the cafeteria to eat lunch.
(b) Ask the Registrar to sort the students by their Social Security number, and then take the first 100 in the resulting list.
(c) Ask the Registrar for a set of cards, with each card containing the name of exactly one student, and with each student appearing on exactly one card. Throw the cards out of a third-story window, then walk outside and pick up the first 100 cards that you find.Explanation of Answer
To determine whether it’s appropriate to assign the uniform distribution to \(X\) in each scenario, we need to assess if every subset of 100 students has an equal chance of being chosen. If it is appropriate, then each subset of size 100 out of 3000 students should have the same probability of selection.
This method is likely not uniform because the selection is influenced
by the time students choose to eat, which can be affected by their
schedules, habits, or preferences. Some students might have classes
during lunch hours or prefer to eat at different times, reducing their
chances of being included in the subset.
Uniform distribution assignment: Not appropriate.
This method could be considered uniform if the Social Security
numbers are randomly distributed across students, which they typically
are. Since the sorting criterion (Social Security number) is independent
of any student’s likelihood of being chosen, each student has an equal
chance of being in any position in the list and thus an equal chance of
being in the first 100.
Uniform distribution assignment: Appropriate.
Probability assignment: If uniform, each subset of 100 students
out of 3000 should have a probability of \(\frac{1}{\binom{3000}{100}}\). \[
\frac{1}{\binom{3000}{100}} \approx 9.6055 \times 10^{-190}
\]
This method seems to introduce randomness, assuming that the way the
cards scatter is random and picking them up doesn’t introduce any bias.
Each card (and thus each student) should have an equal chance of being
in any position in the scattered arrangement and being among the first
100 picked up.
Uniform distribution assignment: Potentially appropriate, but
this could depend on the specifics of how the cards are thrown and
collected. If truly random, it’s appropriate.
Probability assignment: If uniform, each subset of 100 students
out of 3000 should have a probability of \(\frac{1}{\binom{3000}{100}}\). \[
\frac{1}{\binom{3000}{100}} \approx 9.6055 \times 10^{-190}
\]
In summary, strategies (b) and (c) could be appropriate for the uniform distribution assignment under certain conditions, with each outcome having a probability of \(\frac{1}{\binom{3000}{100}}\). Strategy (a) is not suitable for a uniform distribution assignment due to the likely time-based biases in the selection process.