4
$\begingroup$

Assume I have a set of 20 numbers. Each number in the set is unique. I am able to retrieve one number at a time from the set with the probability of retrieving any one member of the set being equal. How would I go about determining the probability that after ten random retrievals with replacement (i.e. a retrieval does not remove a number from the set) I would have 10 unique members?

Many thanks for your assistance.

2 Answers 2

9

We give three not very different arguments. The first two use counting, and the third works directly with probabilities.

Let us record the numbers that we get as a sequence of length $10$. So the sequence $(a_1, a_2, \dots, a_n)$ means that we got $a_1$ on the first pick, $a_2$ on the second pick, and so on.

There are $20^{10}$ such sequences, all equally likely, since we are replacing at each stage.

Suppose that we will be happy only if all the numbers are different.

Any of the $20$ numbers is fine for $a_1$. But for every choice of $a_1$, there are only $19$ values of $a_2$ that keep us hoping, for a total of $(20)(19)$ choices for $(a_1,a_2)$. But for every such choice of $(a_1,a_2)$, there are only $18$ values of $a_3$ that keep us hoping, for a total of $(20)(19)(18)$ choices for $(a_1,a_2,a_3)$. Continue.

We find that there are $(20)(19)(18)\cdots (12)(11)$ sequences of length $10$ that make us happy. Thus the required probability is $\frac{(20)(19)(18)\cdots (12)(11)}{20^{10}}.$

Another way: We count again the number of sequences of length $10$ that make us happy. Call a string of length $10$ good if all its entries are different. The numbers that appear in a good string can be chosen in $\dbinom{20}{10}$ ways. Here $\dbinom{n}{r}$ is the number of ways to choose $r$ objects from $n$ distinct objects. On scientific calculators, the label is ${}_nC_r$.

For every choice of the $10$ distinct numbers, these numbers can be lined up in a row in $10!$ ways. So there are $\dbinom{20}{10}10!$ good sequences of length $10$. The probability we will be happy is therefore $\frac{\binom{20}{10}10!}{20^{10}}.$

Still another way: We can work directly with probabilities. The probability that we are still hopeful after the second draw is $\dfrac{19}{20}$.

Given that we are still hopeful after the second draw, the probability we are hopeful after the third draw is $\dfrac{18}{20}$. So the probability that we are still hopeful after the third draw is $\dfrac{19}{20}\cdot\dfrac{18}{20}$.

Continue. The probability that we get $10$ distinct integers is $\frac{19}{20}\cdot\frac{18}{20}\cdot\frac{17}{20} \cdots\frac{12}{20}\cdot\frac{11}{20}.$ We can make the answer look nicer, at least to a mathematician, by putting a $\dfrac{20}{20}$ at the front.

5

The first selection will have $20$ possibilities, the next selection $19$ possibilities, and so on until the $10$-th selection has $11$ possibilities. The total number of ways of to choose a ball from these possibilities each time is $20\cdot19\cdots12\cdot11$. The total number of ways to choose $10$ balls at all is $20^{10}$. So you're looking at

$P=\frac{20!}{10! 20^{10}}\approx 0.0655.$