The mathematical principle of Hiring Problem

2018-05-04

Problem’s Describe

Hiring Problem,it is also known as the Secretary Problem,we use the wikipedia definiton to define it.

The basic form of the problem is the follwinng:imagine an administrator who wants to hire the best secretary out of rankable applicants for a position.The applicants are interviewd one by one in random order.A decision about each particular appliant is to be made immediately after the interview.Once rejectd,an applicant cannot be recalled.During the interview,the administrator can rank the applicant among all interviewd so farm,but is unaware of the quailty of yet unseen applicants.

The question is about the optimal strategy to maximize the probability of selecting the best applicant.

If the decison can be deferred to the end,this can be solved by the simple maximum selection algotithm of traking the running maximum,and selecting the overall maximum at the end.The difficulty is that the decision must be made immediately.

The mathematical principle–Optimal Stopping Theory

The probability of win using is:

Our idea is we choose r which we can use the first element better than it,than we think the element is best chioce.So,now we have a question,if the turly best element is before K,we can not find the best,the probability is 0,if not,we have:

Now we can make:

Let ,and we can get .

Now we find the max value of this function,we have:

So,now we know the ,and the probability that we find the max of is .

Dynamic programming

I will give its solution in next paper.i am tried now,zZZ.

References:

1,Chapter 2. FINITE HORIZON PROBLEMS.

2,Secretary problem

3,SUM THE ODDS TO ONE AND STOP

4,实用马尔可夫决策过程

回到首页

所有文章