javascript - 抛硬币 1000 次时，如何计算连续 8 次得到相同结果的概率是多少？

Question

我尝试使用此代码:

function calc (n, c) {
  let a = 0
  const omega = Math.pow(2, n)

  let search1 = ''
  let search2 = ''

  for (let i = 0; i < c; i++) {
    search1 += '0'
  }
  for (let i = 0; i < c; i++) {
    search2 += '1'
  }

  for (let i = 0; i < omega; i++) {
    if (i.toString(2).includes(search1) || i.toString(2).includes(search2)) {
      a++
    }
  }

  const prob = a * 100 / omega
  console.log({ a: a, omega: omega, prob: prob.toFixed(2) })
}

calc(1000, 8)

哪个有效，但是当涉及到大数字时速度很慢。如何优化我的代码以使其更快？或者也许存在一个数学解决方案，根本不需要编码？我只想知道这个问题的解决方案。

Answer 1

第一个 蒙特卡罗模拟回答:
您可以通过对伯努利分布进行一些统计推断来找到此模拟的置信区间，我不会在这里做。

function doesItHappen(l,r){
    var lastValue = null;
    var lastN = 0;
    for(var i = 0; i < l; i++){
        var currentValue = Math.random() > 0.5 ? 1 : 0;
        if(lastValue === currentValue) {
            lastN++;
        } else {
            lastValue = currentValue;
            lastN = 1;
        }
        if(lastN === r) return true;
    }
    return false;
}

function rep(n,l,r){
    var t = 0;
    for(var i = 0; i < n; i++) {
        if(doesItHappen(l,r)) t++;
    }
    return t/n;
}
console.log(rep(100000,1000,8))

最后是实际的 数学 回答
我在网上找不到这个问题的解决方案，所以我想出了自己的方法来计算 o(n) 时间和空间复杂度，您甚至可以通过丢弃较旧的 valueStore 对象来将其降低到 o(1) 空间复杂度比你想要的连续序列的长度。关键是要认识到你必须在当前长度之前计算所有组合，类似于斐波那契数列。

function calculateProbability(l,r) {
  var valueStore = [
    { // Initialize it
      totalNumberOfCombinations: 2,
      numberOfCombinationsWithSequence: 0
    }
  ];
  function getValues(index) {
    // combinations with the sequence in it
      // There are two ways a consecutive sequence of r length can occur, it either occured in the previous combination and we flipped a new heads or tails(doesn't matter)
      // Or this flip resulted in a new consecutive sequence of r length occuring (let's say theres k combinations of this)
      // Heres the genius, k must end in a sequence of heads or tails so theres 2 possible endings, the beginnings of k cannot contain the sequence of r consecutive flips
      // If this previous combination ends in a head then the new sequence is all tails and vice versa
      // So k = the combinations of flips without the consective flips before the current sequence
      // k = the totalNumberOfCombinations 8 flips ago - numberOfCombinationsWithSequence 8 flips ago
    if (index === r - 1) {
      // All heads or all tails
      var numberOfCombinationsWithSequence = 2;
    } else if(index < r) {
      var numberOfCombinationsWithSequence = 0;
    } else {
      var numberOfCombinationsWithSequence = valueStore[index - 1].numberOfCombinationsWithSequence * 2 + (valueStore[index - r].totalNumberOfCombinations - valueStore[index - r].numberOfCombinationsWithSequence)
    }
    return {
      // total possible combinations
      // this is just the previous number of combinations but times 2 since we flip again
      totalNumberOfCombinations: valueStore[index - 1].totalNumberOfCombinations * 2,
      numberOfCombinationsWithSequence: numberOfCombinationsWithSequence
    }
  }

  for(var i = 1; i < l; i++) {
    var values = getValues(i);
    valueStore.push(values);
  }

  return valueStore[valueStore.length - 1].numberOfCombinationsWithSequence / valueStore[valueStore.length - 1].totalNumberOfCombinations;
}
console.log(calculateProbability(1000,8));

100% 准确的答案是 0.9817098435878764 或 98.17%