Home > Software design >  Unexpected values when simulating the Secretary problem
Unexpected values when simulating the Secretary problem

Time:11-13

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%

//number of people, and also number of results
let people=100
//multiple trials to smooth data
let trials=1000;

let results=new Array(people).fill(0);
// creates a percent, i/people, for each initial group that is "turned down"
for (var i=0;i<people;i  ) {
    // runs a few times to smooth data
    for (var j=0;j<trials;j  ) {
        //x is new random set of people, values in [0,1]
        let x=new Array(people).fill(0).map(e=>Math.random()); 
        //"rejected set"
        let min=Math.max(...x.splice(0,i));
        //select the first person better than the "rejected" set
        let select=0;
        let selected=false
        for (var k of x) {
            if (k>=min && !selected) {
                select=k;
                selected=true;
            }
        }
        //increase results by selected or last person
        results[i] =select!=0?select:x[x.length-1];
    }
}
//strategy to get highest average score
console.log("Best strategy: " (results.indexOf(Math.max(...results))/people*100) "%");

I also plotted some of the data on desmos here.

CodePudding user response:

I don't understand how you count the number of successful trials to compute the probability. Try to replace the counting logic as follows.

        for (var k of x) {
            if (k > min && !selected) {
                select = k;
                selected = true;
            } else if (k > select && selected) {
                selected = false;
                break;
            }
        }
        //increase results by selected or last person
        results[i] = selected

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.

  • Related