What is the probability that $m$ is the largest number drawn?

Solution 1:

I think your issue is a language one. I will attempt to rephrase a specific case of the question in a different way so we can really see what the meaning of $n,m,k$ are.

(a)

Suppose we have the first ten letters of the alphabet: $\{A,B,C,D,E,F,G,H,I,J\}$ and we select three of them uniformly at random without replacement. What is the probability that the "largest" (with regard to alphabetical order) letter that we chose is an $F$?

As there are ten letters and we are choosing three of them, there are $\binom{10}{3}$ different selections that can be made. This will be our denominator.

As for the numerator, if we suppose that our largest letter chosen was an $F$ that means in particular that an $F$ was chosen and there are two more additional letters left to choose and those two additional letters must be smaller than $F$ otherwise $F$ wouldn't have been the largest letter chosen. That is, we look at how many ways there are to choose two letters from $\{A,B,C,D,E\}$ to fill out the remainder of our set of chosen letters. There are $\binom{5}{2}$ ways to do this.

This gives us a probability of $\dfrac{\binom{5}{2}}{\binom{10}{3}}$

It should hopefully be clear why the above example is the exact same as the problem of finding the probability that the largest number chosen was $m$ when $k$ balls are chosen out of $n$ available. In the above example we had $n=10$ balls available, we selected $k=3$ balls, and the largest ball was meant to be $m=6$. The same logic applied above shows that the probability that the maximum is $m$ is $\dfrac{\binom{m-1}{k-1}}{\binom{n}{m}}$

It is worth noting that $\binom{m}{k}-\binom{m-1}{k}=\binom{m-1}{k-1}$ so this answer matches both that of @lulu and @greedoid.

(b)

Suppose we have the first ten letters of the alphabet: $\{A,B,C,D,E,F,G,H,I,J\}$ and we select three of them uniformly at random without replacement. What is the probability that all letters chosen are from $\{A,B,C,D,E,F\}$? That is to say, all letters chosen appear before $F$ in the dictionary or are $F$ themselves.

Again, there are $\binom{10}{3}$ ways to select three letters from our set of ten. This is again our denominator.

Choosing our three letters, we don't care what they are so long as they all come from the set $\{A,B,C,D,E,F\}$. There are six letters in this set and choosing three of them can be done in $\binom{6}{3}$ ways.

This gives a probability of $\dfrac{\binom{6}{3}}{\binom{10}{3}}$

Again, this should be a clear metaphor for the original problem where $n=10,m=6,k=3$. For arbitrary values of $n,m,k$ you will find using the same logic as above that the probability is $\dfrac{\binom{m}{k}}{\binom{n}{k}}$

It is worth pointing out that $\sum\limits_{i=k}^m\binom{i-1}{k-1}=\binom{m}{k}$ via the "hockeystick identity" and so this answer matches both that of @greedoid and that of @lulu.

"The part I get stuck is $\binom{m}{k}$. If it is $\binom{m}{k}$, then we are choosing $k$ balls from $m$ balls, right? But then $m$ is the largest number drawn balls, $k$ must be $= m$?"

Yes, $\binom{m}{k}$ represents the number of ways of choosing $k$ objects from $m$ objects. We are in the second problem as I have phrased it choosing $k$ balls from those balls numbered $\{1,2,3,4,\dots,m\}$. There is no requirement for $k$ to be equal to $m$ however. We merely want the largest appearing label to be less than or equal to $m$ (or equal to $m$ in the case of part (a)), we are not requiring that the number of balls selected be equal to $m$. That was why I chose to use letters in my metaphors. We wanted all letters chosen to be appearing at or before $F$ in the alphabet. When we were choosing three letters, the number $k=3$ is largely unrelated to the letter $F$ (the $m=6$'th letter of the alphabet).

Solution 2:

a) So we have to take $k-1$ balls with numbers $\leq m-1$. $$ P={{m-1\choose k-1}\over {n\choose k}}$$

b) Largest choosen number must be between $k$ and $m$ so $$P = {1\over {n\choose k}} \sum _{i=k}^m{i-1\choose k-1}$$

Solution 3:

Let us start with $b$.

For each $m$, with $1≤m≤n$ we want to count the number of ways to choose $k$ numbers $≤m$. By definition, this is $\binom mk$. As there are $\binom nk$ unrestricted ways to choose the numbers, we see that $$\text {Prob}(\max ≤m)=\frac {\binom mk}{\binom nk}$$

Of course, given such a choice, the max might well be $<m$. To get the probability that the max is exactly $m$ we subtract. Thus: $$\text {Prob}(\max =m)=\text {Prob}(\max ≤ m)-\text {Prob}(\max ≤m-1)= \frac {\binom mk}{\binom nk}-\frac {\binom {m-1}k}{\binom nk}$$