CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Sep 2012
    Posts
    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/(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?

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Hiring a person from n persons - Rank and Probablity

    Quote Originally Posted by siddharthm87 View Post
    I am unable to understand the concept here.
    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.

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





Click Here to Expand Forum to Full Width

Featured