The problem is as follows
We want to create a new NBA team, we want to keep the tallest candidate. Let's suppose we have n candidates in a random order. So if we have candidate 2 who is taller than candidate 3, so candidate 3 is not hired. Oppositely, if candidate 3 is taller than candidate 2, so candidate 3 is higher. etc.
What is the probability to hire exactly 2 candidates ?
For me, I see 3 cases. Let's suppose that each candidate has a rank : ($1$ to $n$, where $n$ is the tallest)
- The tallest candidate is the first one, so nobody else will be hired
- The first candidate has a rank $i <= n-1$, so between the first candidate and the $j$'th candidate (where $j$ is the tallest candidate), we should have candidates which size smaller than $n-i$, and then, the tallest candidate ($j$) and finally the rest.
The final answer is $Pr\{T_i\}=\frac{1}{n}\frac{1}{n-i}$, where $T_i$ is the probability for hiring twice if your first candidate has rank $i$, but I don't understand how to get it.
For me, first, you should have the probability to have any candidate except the tallest one as first candidate, which is $\frac{n-1}{n}$. Then I'm a little bit stuck (and I don't know whether my reasoning is correct or not) because I would like to compute the probability to have any candidates with lower rank than i and then, the tallest one and finally the rest.
How should I proceed ?
Bonus : What is the probability to hire exactly m candidates, where $m <= n$
Best Answer
To solve the problem, let the random variable $X_i$ be equal to 1 if the $i$th candidate is the largest among the first $i$ candidates. Then $P(X_i=1)=1/i$ and $P(X_i=0)=1-1/i$ for all $i$ . Since $X_1=1$, the probability that $\sum_{k=1}^{n}X_k=2$ is equal to the probability that exactly one of the $X_2,\ldots,X_n$ is equal to 1 and the others are zero. This probability is easily calculated, using the (nontrivial) fact that the $X_i$ are independent. For example,for $n=3$, the probability has the value 1/3+1/6=1/2. In general, the probability mass function of $X_1+\cdots+X_n$ can be calculated from its generating function, which is given by the product of the terms $1-1/i+z/i$ for $i=1,\ldots,n$. Using computer algebra, you can expand this product into a polynomial of degree $n$. The coefficient of $z^m$ in this polynomial gives you the probability that exactly $m$ of the $n$ candidates will be chosen.