0
$\begingroup$

I'm a bit embarrassed to ask this here, but I'm not very good at statistics and curious about the right answer.

If I pick $m$ elements out of $n$ randomly ($m<n$), the right way to do it is to shuffle my $n$ elements and take the first $m$.

But if I do it "wrong" by just picking a random element out of the $n$ for $m$ times, putting back always, how many unique elements can I expect to get after $m$ draws?

Writing this down makes it really sound like a high school question. And that is probably what it is.

The first draw is always unique. The second draw has a chance of $1/n$ to be unique, the next one $2/n$ and so on.

But given $n$ and $m$, is there a closed formula for picking $m$ times from $n$ – how many unique picks do I expect?

$\endgroup$

1 Answer 1

1
$\begingroup$

First you say, "If I pick $m$ elements out of $n$ randomly $(m < n),$ the right way to do it is to shuffle my $n$ elements and take the first $m.$ That amounts to sampling without replacement. Using that method, there is no way to get the same element more than once. With that method are ${n \choose m} = \frac{n!}{m!(n-m)!}$ different samples of size $m$. If you have $n = 3$ elements A, B, and C, and you are choosing $n = 2,$ then the possible samples are:

AB AC BC

If you keep track of the order then there are six ordered samples without replacement:

AB AC BC BA, CA, CB

Then you say, "But if I do it 'wrong by just picking a random element out of the $n$ for $m$ times, putting back always, how many unique elements can I expect to get after $m$ draws?" Now your are sampling with replacement, but there is also an implied order. (Pick the first, replace; pick the second, replace; and so on.) As you say, there is a possibility of choosing the same element more than once. There are $n^m$ possible ordered samples when choosing with replacement. In our example,

AA  AB  AC
BA  BB  BC
CA  CB  CC

Your main question has to do with the chances of picking the same element more than once, when sampling with replacement. This is essentially the famous 'birthday problem': You have 25 people is a room, each with an equal chance of having been born on any of 365 days (ignore leap years). What is the probability of getting a birthday match? The probability of no match is:

$$P(\text{No Match}) = \frac{365}{365}\frac{364}{365}\frac{363}{365} \cdots \frac{365-(25-1)}{365} = \prod_{i=0}^{24}\left(1 - \frac{i}{365}\right) = \frac{{}_{365}P_{25}}{365^{25}} = 0.4313.$$

So there is more than a 50:50 chance of a least one birthday match among the people in the room. Here the symbol ${}_{365}P_{25}$ is called the 'permutations of 365 objects taken 25 at a time' ${}_{n}P_{m} = \frac{n!}{(n-m)!}.$ ('Permutations' are ordered samples.)

There are several dozen posts on this site dealing with the birthday problem and variations of it. You can search among them for whatever details interest you.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .