Probability to draw a group of balls which contains a specific ball

Question

A bin holds n balls, labeled with the numbers $1, 2, . . . , n$. Exactly $m$ balls are being sampled uniformly at random from the bin. Let $M$ be the maximum number that was drawn.

1. Compute the distribution of $M$, when the samples are being made without replacement.

My answer:

We need to calculate $P(M=k)$

I have 2 answers which result in 2 different values.

1. We must draw the $k$'th ball ($1$ way to do it) and then we need to choose the rest of the balls ($\binom{k-1}{m-1}$). There are $\binom{n}{m}$ ways to choose $m$ balls from $n$ balls:

$$\frac{1\cdot\binom{k-1}{m-1}}{\binom{n}{m}}$$

2. We must draw the $k$'th ball $\frac{1}{n}$ and then we need to choose the rest of the balls $\binom{k-1}{m-1}$. The probability to choose each of these balls is:

$$ \frac{1}{n-1}\cdot\frac{1}{n-2}\cdots\frac{1}{n-m} $$

So the final result is:

$$ \frac{1}{n}\cdot\binom{k-1}{m-1}\cdot\frac{1}{n-1}\cdot\frac{1}{n-2}\cdots\frac{1}{n-m} = $$

$$ \frac{1}{n}\cdot\binom{k-1}{m-1}\cdot\frac{(n-m-1)!}{n!} $$

---

My question - Each result is different. Which is the correct one and why is the other not correct?

Answer 1

The first method is the correct one, but method number 2 can be fixed. I will try to point out the errors and fix them:

• The product $$\frac1{n-1}\cdot\frac1{n-2}\cdots\frac1{n-m}$$ should have stopped at $n-m+1$ instead, since otherwise you would draw $m+1$ balls as a total.

• The fraction $1/n$ should be included as part of $n!$ in the denominator in the last line, since the other fractions only have $n-1,n-2$ etc.

• Finally you should multiply the whole thing by the $m!$ different orders in which those $m$ balls could be drawn.

After doing this, the two actually agree since they both become: $$ \binom{k-1}{m-1}\cdot\frac{(n-m)!\cdot m!}{n!} $$ if you look carefully.

---

Note that method 1 considers combinations where order does not matter, whereas method 2 thinks through probabilities for each specific sequence of events and hence permutations where order does matter. That is what prompted the correction of a factor $m!$ in the method 2 approach. In method 1 that factor $m!$ is just already an element of the formula for the orderless $\binom{n}{m}$.

Answer 2

I would say $$P(M = k)=P(M \le k)-P(M \le k-1) =\dfrac{k \choose m}{n \choose m}-\dfrac{k-1 \choose m}{n \choose m} = \dfrac{m{k \choose m}}{k{n \choose m}}=\dfrac{{k-1 \choose m-1}}{{n \choose m}}$$ so the first option in the question

The second option is too small and does not add up to $1$