Hiring a person from n persons - Rank and Probablity
I am studying algorithms from CLRS book.I am trying to understand the difference between
- probability of hiring ith person from n persons
- probability of hiring ith person from n persons based on ranks.Each person will be allotted a rank after interviewing and if his rank is greater than the rank of the previously hired person, he gets recruited too
calculating the probability we know the answer for the first one is 1/(n-i).
The answer for the second is 1/i in the CLRS book. I am unable to understand the concept here.How is it 1/i?Can it also be 1/(n-i) taking in ranks too?
Re: Hiring a person from n persons - Rank and Probablity
How did you arrive at 1/(n-i)? It dosn't look like a proper probability to me. Say n=10, then the probability for the 10:th person would be 1/0. That's infinity and probabilities are supposed to lie between 0 and 1.
Originally Posted by siddharthm87
I don't think the idea here is to consider situations with or without ranking. Instead the concept of rank is introduced as a way to impose a total ordering. Otherwise it cannot be determined which one of any two persons is more qualified and that's a necessary precondition for all algorithms discussed in relation to the hiring problem.
Say there are N ranked people. If you select i of them at random anyone in that group can have highest rank with equal probability 1/i. And specifically if N people are standing in line at random the i:th person of the first i persons will have highest rank with 1/i probability. So the probability that the i:th person in line will out-rank everyone before her is 1/i.