In Quest of the Best !!

Jerry, a cute looking mouse, extremely intelligent(Stupid at times !! ) is eating cheese.. He hears some crackling noise ou

t and goes out to check. He reads a note that says,

“ Dear Jerry,

Please take care of Tuffy over the Thanksgiving holiday. P.S : he loves to eat! “ :P

Jerry being a little lazy frowns over the idea of spending a nice holiday with Tuffy. A little later, “A Nanny!!” ,he exclaims to himself and thinks “I can always hire a nanny as long as I have enough cheese to pay her ;)”. But Jerry is a perfectionist. He wants to hire ‘The Best’ nanny for his dear nephew and was quite excited about the idea. But on what basis would he know who the Best was? He had an answer for that too. He said “Whoever has scored the highest marks in ‘Mouse-keeping’ school will acquire this post”. By the way, you have to know this, Jerry loves bossing around. Ah...ha…you guessed it right!! That is another reason why he wanted to ‘hire’ someone :P

Much to Jerry’s delight, he saw a bunch of them waiting for the post. Soon he murmured to himself, “Dude it is not going to be easy to choose the best”. He planned to do the following:

(Are you wondering "Is Jerry not smart enough to find out the highest-scorer among the lot?". Well, let me tell you. Jerry has no clue about anyone's marks. Only when a person enters the room for interview process, he gets to know the score and either he has to be hired or fired with no other option left. Also assuming that ‘Mouse-keeping’ school doesn’t give out the highest –scorer)

• Ask them to maintain a queue and let everyone in one by one in the order A,B,C and so on.

• Blindly hire ‘A ‘and ‘pay’ some cheese.

• Look at ‘B’. In case if ‘B’ has a score better than the previously chosen one i.e. ‘A’, then he fires ‘A’ (along with which, the paid cheese is gone :P) and hires ‘B’. Not to forget, he has to pay cheese to ‘B’ for hiring.

He plans to do this until he interviews everyone in order to find the best among the lot.

“Oh dear God!! Won’t I run out of cheese if I do that? What if I feel restless in the middle of the whole process?? ” . Yes…finally...he realizes how much he loves cheese and how lazy he is!! So he contacts his good old mathematician friend Mr.X to help him out with this problem.

Mr.X thinks over the problem a little and speaks to Jerry. The conversation goes like this.

Mr. X : I can help you if you are ready to compromise a little.

Jerry : Oh ! I don’t mind as long as it finds me The Best nanny and I get a larger share of the cheese.

Mr.X : Ok I can’t promise you that I will find the best Nanny, but I promise you to save large amount of your cheese and get you a Nanny closest to the Best.

Jerry : Nice. Alright then, give out the solution.

Mr.X : Given members, find the best among 1 to by hiring and firing process. Let us call her . Hire $\beta$. Find the first person among $k+1$ to $n$ who beats $\beta$ with her score, say $B1$. There you are!! She is the nanny you want to hire.

Jerry (with a weird look) : Really?? You think this is gonna work?? And how do I know $k$?

Mr.X : Well ,$ k$ = number of people attending the interview($n$) /exponential constant ($e$)

Jerry : Oh great !! I will try that out.

Hurray !! he verifies that the method actually works !! He hires $B1$ and she really does take very well care of tuffy .

As usual, happy Ending of the story. :) :) :)

But wait a minute, what exactly happened behind the scene? How was he so sure that this will work out? Any miracle? By the way,Who is this Mr.X?

Mr.X is none other than the ‘Probability’ !!!!!

Let us see how probability finds us a solution for this !! Summarizing the method :

1. A $k$ is found. This $k$ is the point at which you can AFFORD to feel restless.

2. What is the use of this $k$?

Hire the best person $\beta$ in the range 1 to $k$ by ‘hiring and firing’ process. Find the person in the range $k+1$ to $n$ who beats $\beta$. Let us call it $B1$. There are high chances of $B1$ being the Actual best. If this works, then u save a lot of money, time and yet you get a best or closest to best. But how?? Perplexed??

Points to be noted is that ‘best’ i.e. $Bi$ has to occur after $k$ and most of the times it does !! So proceeding with this is worth a try. But the question is how to find a $k$ so that this method works?

$Bi$ : Probability of best occurring in ith p

osition i.e. $\frac{1}{n}$

$Wi$ : Probability of $\beta$ occurring in right position $\frac{k}{i}$

$\beta$ can occur in any one of the k positions. k has to occur before i.

Hence for the method to be a success, both these conditions needs to be satisfied. As both the events are independent, the probabilities have to be multiplied. Hence, by the product rule, the probability of this happening is $B_i.W_i$

$i$ has to occur after $k$, i.e. anywhere between $k+1$ to $n$

$\sum_{i=k+1}^{n}\; W_i B_i$

$\sum_{i=k+1}^{n}\frac{k}{i-1} \frac{1}{n}$

$\frac{k}{n}\sum_{i=k}^{n}\; \frac{1}{i}$

We know tat ,

$\ln n= 1\: + \frac{1}{2}\: + \frac{1}{3}\: + \frac{1}{4}+\cdots +\frac{1}{n}$

$f(k) = \frac{k}{n}\;\left ( \ln n - ln k \right )$

(Click on the image to get a clear view)

A tangent is drawn at the peak. As the slope is 0, f'(k) is equated to 0 in order to find the value of k.

f '(k) = 0

f '(k)=$ \frac{ln n}{n} -\frac{1}{n}\;\left ( k.\:\frac{1}{k}\;+\; ln\:k \right )$

$\frac{ln n}{n} - \frac{1}{n} - \frac{ln k}{n} = 0$

$\frac{1}{n} \left(ln \frac{n}{k} - 1 \right) = 0$

$\left(ln \frac{n}{k} - 1 \right) = 0 $

$ln \frac{n}{k} = 1$

$\frac{n}{k} = e $

$k = \frac{n}{e}$

Wow is that it?? At $k = \frac{n}{e}$, there is a high probability of beta being very close to ‘Best’ which is our aim. You can afford to stop your interviewing process at ‘k’ and also not compromise with your principle of finding the ‘Best’.

If there are n candidates for interview, you can stop the process at n/e and still find the Best with high probability.

Not convinced?? Let us work out the problem given :

(A python generated output :P you can trust this :P )

Work out this on your own and tally the answers given. This way, you will get more acquainted with the method.

Let us say there are 100 candidates for the interview (assuming that there is only one ‘Best’). Their marks are as follows.(These marks are 'random'ly generated by python)

Lets follow Jerry's method i.e. hiring and firing process...That way, the total number of hiring is 5. But once you reach '100' you dunno if that is the best or not. You end up interviewing everyone with the hope that you can find someone better than the one you have already found.

The main aim of the method proposed is to avoid the interviewing process for everyone and yet find a best one. Basically what it means to tell is that you can afford to get restless at $k$

According to the method proposed,

1.K=n/e =100/2.714 =36 (represented by the red line)

2.Number of hirings before k = 4

3.The Obtained Best within k = $\beta$ = 98

4. The ‘Best’ chosen after k = 100 !!!! Which is the actual Best !!

*************************************************************************************

Consider this case where you a $B1$ closest to $Bi$

1. K=n/e =100/2.714 =36 (represented by the red line)

2. Number of hirings before k = 6

3. The Obtained Best within k = $\beta$ = 91

4. The ‘Best’ chosen after k = 98 (represented with yellow)!!!! Which is closest to the actual Best (represented with yellow)!!

*************************************************************************************

Worst Case: If the Actual Best occurs within the range 1 to k, then the method fails and you

1. K=n/e =100/2.714 =36 (represented by the red line)

2. Number of hirings before k = 6

3. The Obtained Best within k = $\beta$ = 100 (Disaster :P)

4. The ‘Best’ chosen after k = 17 (represented with blue)!!!! If none of the values beat $\beta$ then by default the last value is chosen to show that you have traversed the complete list.

*************************************************************************************

Probability at its 'Best' ;) Hope you have your eyebrows raised ;) If not, you need to go through it once again ;)

FYI : The class of algorithms where input is fed in serial fashion and you don't have the prior knowledge about the entire input at the time of processing are called Online Algorithms. Also, this problem is the same as 'The Secretary Problem'. You can google and take a look at it :) :)

Shruthi R Nayak