javascript - 固定数量实例上的概率函数

Question

我需要建立一个布尔概率测试，它可以定期运行，增加返回真值的机会。

返回阳性测试的概率的增加将由变量 (nMax) 确定，该变量表示预期的测试次数，以返回 95%+ 机会返回真实的组合结果。

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

我曾多次尝试使用概率对数标度，但均未成功，但似乎没有一个特别有希望。很受欢迎的想法。

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()

标签： javascriptalgorithmprobability

Answer 1

有无数种解决方案可以满足您的约束。一个简单的方法是要求每次运行具有相同的成功概率。我们称这个概率为 。

我们必须满足在第一次 nMax 运行中获得成功的概率是 0.95。换句话说，在第一次 nMax 运行中没有成功的概率是 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.