Как рассчитать вероятность получения одного и того же результата 8 раз подряд при подбрасывании монеты 1000 раз?

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) времени и пространства сложности, вы даже можете получить его вниз o (1) сложность пространства, отбрасывая объекты 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%

Answer 2

как насчет симуляции?

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)