A different fussy suitor from those I've met before
September 16, 2012 8:28 PM Subscribe
I'm working through an explanation/derivation of the secretary problem that I've never seen before. I know the eventual answer, and I understand most of the steps, but explain this to me like I'm an idiot:
(This is for a class, but not a for-credit homework problem. I was intrigued enough to ask because it's a different way of working through a problem I already know pretty well.)
posted by supercres to grab bag (8 answers total)
I'm giving a short setup (see this
for the full formulation). n candidates, A1 through An. A1 is the best, An is the worst. They're interviewed in a random order. The first group of candidates (the ones that won't be selected) is G1; G1 has r randomly-selected candidates in it. M is the rank of the best candidate in G1.
Here's the step that I don't understand, and hasn't been in explanations of the problem I've seen before: get an expression for the probability that M is equal to k (that is, that the overall kth best candidate is the best one in G1), in terms of k, n, and r.
I know that the probability that any given candidate is in G1 is r/n, but the probability that Ak is the best in G1 is giving me fits.
I know, based on the fact that I know the solution to the problem, that it has a summation in it. But thinking through it, I can only come up with it in terms of binomial coefficients. I'm sure I'm overlooking something dumb. Help!