Coding a secretary problem (Monte Carlo) - problems with python code

Question

Trying to code the secretary problem in python by doing a Monte Carlo simulation (without using e). The essence of the problem is here: https://en.wikipedia.org/wiki/Secretary_problem

Described as :Imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant. Taken from: https://www.geeksforgeeks.org/secretary-problem-optimal-stopping-problem/

Table that I'm checking my code against:

Here is my python code so far:

n = 7; # of applicants
m = 10000; # of repeats
plot = np.zeros(1);
        
for i in range (2,m): #multiple runs
    array = np.random.randint(1,1000,n); 
    for j in range(2,n): #over range of array 
        test = 0;
        if array[j] > array[1] and array[j] == array.max():
            plot=plot+1
            test = 1;
            break
        if array[j]> array[1]:
            test = 2;
            break

print(plot/m)
print(array)
print("j = ",j)
print("test = ",test)

I am doing something wrong with my code here that I'm unable to replicate the table. In the above code I've tried to do 7 = number of applicants and take the best applicant after '2'.

The plot/m should output the percentage in column three given the number of applicants and 'take the best after'.

Answered! As below.

Additional code:

import numpy as np
import matplotlib.pyplot as plt
import time
plt.style.use('seaborn-whitegrid')

n = 150  #total number of applicants
nplot = np.empty([1,1])
#take = 3 #not necessary, turned into J below: 

for k in range(2,n):
    m = 10000 #number of repeats 
    plot = np.empty([1,1]);
    
     
    for j in range(1,k):    
        passed = 0
        for i in range (0,m): #multiple runs
            array = np.random.rand(k);
            picked = np.argmax(array[j:]>max(array[0:j])) + j
            best = np.argmax(array)
            if best == picked:
                passed = passed+1
        #print(passed/m)
        plot = np.append(plot,[passed/m])
    #print(plot)
    plot = plot[1:];
    x = range(1,k);
    y = plot
    #print("N = ",k)
    print("Check ",plot.argmax()," if you have ",k," applicants", round(100* plot.max(),2),"% chance of finding the best applicant")
    nplot =np.append(nplot,plot.max())
# Plot: 
nplot = nplot[1:];
x = range(2,n);
y = nplot
plt.plot(x, y, 'o', color='black');
plt.xlabel("Number of Applicants")
plt.ylabel("Probability of Best Applicant")

user_2116486 · Answer

Here is something that seems to do the job and is a bit simpler. Comments:

Use argmax to determine who is the best secretary, or to pick the first that has a better grade than another group
Draw from a real-valued function to reduce the odds of having 2 secretaries having the same grade.

Hence:

import numpy as np

n = 7
take = 2
m = 100000
passed = 0
        
for i in range (0,m): #multiple runs
    array = np.random.rand(n);
    picked = np.argmax(array[take:]>max(array[0:take])) + take
    best = np.argmax(array)
    if best == picked:
        passed = passed+1

print(passed/m)

Coding a secretary problem (Monte Carlo) - problems with python code

1 Answers