The probability that $m$ is the largest number drawn

combinatoricsprobability

A box contains $n$ identical balls numbered $1$ through $n$. Suppose $k$ balls are drawn in succession.

(a) What is the probability that m is the largest number drawn?

(b) What is the probability that the largest number drawn is less than or equal to $m$?

I don't know how to solve this problem? Could you help me? For (a), I only know that the denominator will be $\binom{n}{k}$. How to find the numerator for both cases?

Best Answer

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).