Secretory Problem

When to give up? Exploration vs Exploitation

A lot of hard working students don’t end up being selected for the scholarships. I should know because i lost 3 years doing it.

Now i turn into a information theoretic game to find when should i have quit the whole process.

Assumption: Your best score will get you scholarship if you are one of the sufficiently prepared student.

Say, entrance exams are the games. We all agree they do behave as a game. If a student is well prepared as indicated by practice questions and exams, then getting their name in scholarship in list is basically a game of chance. This is not to say that it is not possible but given that we all have time and money constrains in our life, when is the right amount to quit. Thus, A player in this game is a sufficiently prepared, hard working student. for others, before playing this game one has to be efficiently prepared.

Now that we agree, getting your name on that list is a work of chance. Say, that you are prepared to give entrance exams 10 times but that will come at a cost of time and money. Out of 10 exams you give, say all these exams can be ranked from your best score to worst score , thus you can rank them from 1 to 10. We can agree on one thing that your best possible score has the highest chance of getting scholarship[which may not be necessarily true for all but our player is a smart, hardworking , well prepared one.].

Now, we give exams one by one and the score one get is random after some cutoff[for me it was 90]. We can all relate to the “fact” that some questions are actually random and they determine our fate.

So we don’t know which exam’s is gonna be the best score for us. so its ideal to assume that it is random. After we give each exams, we surely can rank which one was the best exams and which one was the worst.

The optimal solution is to give n/e exams before deciding to quit and quit after the n/e exams if the score on n/e + 1 is not better than the exams before.

def quit_candidate(n):
    '''Choose a exam to quit after.. from a list of n exam using 
    the optimal strategy. 1= best time to quit,n is worst time to quit'''

    exams = np.arange(1, n+1)
    np.random.shuffle(exams)
    
    stop = int(round(n/np.e)) 
    best_from_rejected = np.min(exams[:stop])
    rest = exams[stop:]
    
    try:
        return rest[rest < best_from_rejected][0]
    except IndexError:
        return exams[-1]
#Now let's see if it actually holds..by having  100,000 student give 100 exams

sim = np.array([quit_candidate(n=100) for i in range(100000)])

plt.figure(figsize=(10, 6))
plt.hist(sim, bins=100)
plt.xticks(np.arange(0, 101, 10))
plt.ylim(0, 40000)
plt.xlabel('Chosen candidate')
plt.ylabel('frequency')
plt.show()

img

We see most of the time we ended up quiting on the prime time[rank 1 is the prime time to quit]

best_candidate = []
for r in range(5, 101, 5):
    sim = np.array([quit_candidate(n=100, reject=r) for i in range(100000)])
    # np.histogram counts frequency of each candidate
    best_candidate.append(np.histogram(sim, bins=100)[0][0]/100000)

plt.figure(figsize=(10, 6))
plt.scatter(range(5, 101, 5), best_candidate)
plt.xlim(0, 100)
plt.xticks(np.arange(0, 101, 10))
plt.ylim(0, 0.4)
plt.xlabel('% of candidates rejected')
plt.ylabel('Probability of choosing best candidate')
plt.grid(True)
plt.axvline(100/np.e, ls='--', c='black')
plt.show()

img

Hence , if we decide to quit on the optimal time to quit is try giving 37% exams and quit if the score is lower than the lower score you got before.

so i was ready to give 8 exams and my score were [84,87,88,94,90,92]

37% of 8 = 3.

My score was improving after 3rd exam so i guess i was right to keep giving exams but the 5th exam my score went down i guess i should have quit then instead of giving one more exam. I lost another 3 month preparing for that.

:-by Kapil Khanal