Probability Function over a fixed number of instances

Question

I need to build a Boolean probability test that can be run periodically with increasing chances of returning true.

The increase in probability of returning a positive test is to be determined by variable (nMax) representing the expected number of tests to return a combined result of 95%+ chance of returning true.

For example: for nMax = 1000

n = [1] has 'almost zero' percent chance of returning true
n = [2] has 'slightly more than almost zero' percent chance of returning true
....
n = [1000] still only has a 'small' chance of returning true but the combined result of n[1] -> n[1000] is now > .95

I've had several unsuccessful attempts attempting to use probabilistic log scales but none seem particularly promising. Thoughts very welcome.

function test(n, nMax){
  let test = Math.random()
  if (Math.random() > (1/(n/nMax))){
    return true
  } else {
    return false
  }
}

function runUntilTrue(){
  let i = 1;
  let result = false;
  while (result == false){
    result = test(i, 100)
    i++
  }
  console.log(i + " tests until true was returned true")
}

runUntilTrue()

Answer 1

There are an infinite number of solutions to fit your constraints. A simple one is to require that each run has the same probability to be successful. Let's call this probability 𝑝.

We must satisfy that the probability of getting success in the first nMax runs is 0.95. In other words, the probability of not getting success in the first nMax runs is 0.05.

Not getting success in the first run, has a probability of 1 − 𝑝. Not getting success in both the first and second run, has a probability of (1 − 𝑝)². Not getting success in any of the first nMax runs, has a probability of (1 − 𝑝)^nMax

Let's solve this:

      (1 − 𝑝)^nMax = 0.05

so:

      𝑝 = 1 − 0.05^1/nMax

Implementation

function neededRuns(nMax, cumulProb=0.95) {
    const p = 1 - (1 - cumulProb) ** (1/nMax);
    
    let n = 1;
    while (Math.random() >= p) n++;
    return n;
}

// Test
const nMax = 100;
const cumulProb = 0.95;
const numAttempts = 100;

let numExceeding = 0;
for (let attempt = 0; attempt < numAttempts; attempt++) {
    let runCount = neededRuns(nMax, cumulProb); 
    console.log(runCount);
    if (runCount > nMax) numExceeding++;
}

console.log(`${numExceeding}/${numAttempts} attemps needed more than ${nMax} runs.`);  

Strictly increasing series

In case you want the individual probabilities to be strictly increasing, then you could for instance apply a similar strategy, but artificially lower the probability a tiny bit, and recalculate the mean probability for nMax-1, and repeat.

You could use an iterator for that:

function * iterProbability(nMax, cumulProb=0.95) {
    let failProb = 1 - cumulProb;
    let p, prevP;
    while (nMax) {
        prevP = p;
        p = 1 - failProb ** (1/nMax);
        nMax--;
        p *= 0.99 ** nMax; // reduce p a bit
        yield p;
        failProb /= 1 - p;  // take this p into account for next iteration
    }
    // After nMax probabilities, 
    //   continue with the same factor of reduction of failure probability
    let coeff = (1 - p) / (1 - prevP);
    while (true) { // ...for ever.
        p = 1 - (1 - p) * coeff;
        yield p;
    }
}

function neededRuns(nMax, cumulProb=0.95) {
    let n = 0;
    for (let p of iterProbability(nMax, cumulProb)) {
        n++;
        if (Math.random() < p) return n;
    }
}

// Test
const nMax = 100;
const cumulProb = 0.95;
const numAttempts = 100;

let numExceeding = 0;
for (let attempt = 0; attempt < numAttempts; attempt++) {
    let runCount = neededRuns(nMax, cumulProb); 
    console.log(runCount);
    if (runCount > nMax) numExceeding++;
}

console.log(`${numExceeding}/${numAttempts} attemps needed more than ${nMax} runs.`);
// Be aware that Stack Snippets clip the console ouput.