Hiring a person from n persons - Rank and Probablity
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Hiring a person from n persons - Rank and Probablity

#### Hybrid View

1. Junior Member
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. Elite Member
Join Date
May 2009
Posts
2,413

## 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/(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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•