固定数量实例的概率函数

Question

我需要构建一个布尔概率测试，它可以运行周期性地增加 return 为真的机会。

return 阳性测试概率的增加由表示预期测试次数的变量 (nMax) 确定 return 95%+ 机会的综合结果 return是真的。

例如：对于 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

我曾多次尝试使用概率对数尺度，但都没有成功，但 none 似乎特别有前途。非常欢迎的想法。

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

有无数种解决方案可以满足您的限制条件。一个简单的就是要求每个运行有相同的概率成功。我们称此概率为 .

我们必须满足在前 nMax 运行s 中获得成功的概率是 0.95。也就是说，第一个nMax运行s没有成功的概率是0.05.

第一个运行没有成功的概率为 1 - 。在第一个和第二个运行中均未成功的概率为 (1 − )²。在前 nMax 运行秒内没有成功，概率为 (1 − )^nMax

让我们解决这个问题：

(1 − )^nMax = 0.05

所以：

= 1 − 0.05^1/nMax

实施

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.`);

严格递增级数

如果你希望个体概率严格增加，那么你可以应用类似的策略，但人为地稍微降低概率，然后重新计算 nMax-1 的平均概率，然后重复。

您可以为此使用迭代器：

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.

固定数量实例的概率函数

Probability Function over a fixed number of instances

javascript

algorithm

probability

实施

严格递增级数