
September 29th, 2012, 01:06 AM
#1
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/(ni).
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/(ni) taking in ranks too?

September 30th, 2012, 03:37 AM
#2
Re: Hiring a person from n persons  Rank and Probablity
Originally Posted by siddharthm87
I am unable to understand the concept here.
How did you arrive at 1/(ni)? 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.
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 outrank everyone before her is 1/i.
Last edited by nuzzle; October 1st, 2012 at 06:23 AM.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
