I was trying to simulate the Secretary problem in JS, expecting to get a value of 1/e (~37%), but what I am getting is much less (~10%), and it was changing, increasing people would decrease it.
This is what I tried, I think the error might be the let x=new Array(people).fill(0).map(e=>Math.random())
. I was expecting 37%, but got ~10%
JavaScript
x
30
30
1
//number of people, and also number of results
2
let people=100
3
//multiple trials to smooth data
4
let trials=1000;
5
6
let results=new Array(people).fill(0);
7
// creates a percent, i/people, for each initial group that is "turned down"
8
for (var i=0;i<people;i++) {
9
// runs a few times to smooth data
10
for (var j=0;j<trials;j++) {
11
//x is new random set of people, values in [0,1]
12
let x=new Array(people).fill(0).map(e=>Math.random());
13
//"rejected set"
14
let min=Math.max(x.splice(0,i));
15
//select the first person better than the "rejected" set
16
let select=0;
17
let selected=false
18
for (var k of x) {
19
if (k>=min && !selected) {
20
select=k;
21
selected=true;
22
}
23
}
24
//increase results by selected or last person
25
results[i]+=select!=0?select:x[x.length-1];
26
}
27
}
28
//strategy to get highest average score
29
console.log("Best strategy: "+(results.indexOf(Math.max(results))/people*100)+"%");
30
I also plotted some of the data on desmos here.
Advertisement
Answer
I don’t understand how you count the number of successful trials to compute the probability. Try to replace the counting logic as follows.
JavaScript
1
12
12
1
for (var k of x) {
2
if (k > min && !selected) {
3
select = k;
4
selected = true;
5
} else if (k > select && selected) {
6
selected = false;
7
break;
8
}
9
}
10
//increase results by selected or last person
11
results[i]+= selected
12
Basically, your trial is successful only when the first higher than min
value is the total maximum. This gives values close to 1/e*100
for me.