抛硬币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 simulate(throws, streak, runs) {
  let win = "".padStart(streak, "1")
  let win2 = "".padStart(streak, "0")
  let hits = 0
  for (let n = 0; n < runs; n++) {
    let res = "";
    for (let i = 0; i < throws; i++) {
      let val = Math.round(Math.random())
      res += val
    }
    if (res.includes(win) || res.includes(win2)) {
      hits++
    }
  }
  console.log({
    hits,
    runs,
    prob: ((hits / runs) * 100).toFixed(2)
  })
}

simulate(1000, 8, 10000)

Answer 2

先做一个Monte Carlo模拟回答：你可以通过对伯努利分布做一些统计推断来找到这个模拟的置信区间，我不会在这里做。

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) 时间和 space 复杂度，你甚至可以将它降低到 o(1) space 通过丢弃比您想要的连续序列长度更早的 valueStore 对象来实现复杂性。关键是要认识到你必须计算当前长度之前的所有组合，类似于斐波那契数列。

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%

抛硬币1000次，连续8次出现相同结果的概率是多少？

How to calculate what is probability of getting same result 8 times in a row, when flipping coin 1000 times?

javascript

math

probability