3

Условия задачи следующие:

Есть монетка, выпадающая орлом с вероятностью P (0 < P < 1). Какова вероятность того, что в серии из N бросков будет как минимум одна подсерия из M орлов подряд?

Задача весьма нетривиальна, мне удалось нагуглить вариант решения на английском, но не вполне удалось понять, что там написано и даже как можно было бы закодить результат приведенный там.

Желательно, чтобы решение можно было хоть как-то объяснить человеку с достаточно неглубокими познаниями тервера, типа меня (учили нас неплохо, но это было слишком давно и практически не применялось в жизни).

В целом, достаточно будет упрощенного варианта решения при p~0.5 и N>>M (N много больше M).

К примеру, численное моделирование ситуации (P=0.5):

Series of 20000 trials was made 20000 times

Longest streak of 9 successes count 1 times
Longest streak of 10 successes count 148 times
Longest streak of 11 successes count 1569 times
Longest streak of 12 successes count 4090 times
Longest streak of 13 successes count 4870 times
Longest streak of 14 successes count 3995 times
Longest streak of 15 successes count 2531 times
Longest streak of 16 successes count 1358 times
Longest streak of 17 successes count 732 times
Longest streak of 18 successes count 367 times
Longest streak of 19 successes count 182 times
Longest streak of 20 successes count 81 times
Longest streak of 21 successes count 44 times
Longest streak of 22 successes count 15 times
Longest streak of 23 successes count 10 times
Longest streak of 24 successes count 4 times
Longest streak of 25 successes count 1 times
Longest streak of 26 successes count 1 times
Longest streak of 28 successes count 1 times

streaks of 18 successes coint 1359 times
streaks of 19 successes coint 638 times
streaks of 20 successes coint 296 times
streaks of 21 successes coint 139 times
streaks of 22 successes coint 63 times
streaks of 23 successes coint 31 times
streaks of 24 successes coint 14 times
streaks of 25 successes coint 7 times
streaks of 26 successes coint 4 times
streaks of 27 successes coint 2 times
streaks of 28 successes coint 1 times
3
  • 1
    Это из комбинаторики, если честно не помню как решать но могу подсказать ссылку на лекцию, где все доходчиво рассказано 20 фев 2016 в 8:09
  • Рассказать не могу, так что просто комментируя - "Конкретная математика", глава 8. Там про монеты много, но конкретно такой задачи нет, хотя задача 41 - оценка количества бросков монет до появления серии из n орлов. Может, натолкнет на какие-то идеи?
    – Harry
    20 фев 2016 в 8:17
  • @AlexsandrTer, спасибо, посмотрю, отпишусь.
    – andy.37
    20 фев 2016 в 11:54

1 ответ 1

1
  • Единица - орёл, ноль - решка
  • p - вероятность выпадения единиц
  • ok(n, m) - вероятность наличия подпоследовательности
  • no(n, m) - вероятность отсутствия подпоследовательности

Далее:

  • i+1 - позиция, с которой начинается искомая последовательность единиц
  • i <= n-m, иначе не поместится последовательность единиц
  • Если i = -1, то префикса нет.

Далее рассматриваем 0 <= i <= n-m:

  • В позиции i находится 0, его вероятность 1-p
  • Вероятность получения части до позиции i равна no(i-1, m)

  • Вероятность получения самой последовательности p^m

Суммируем:

2^p * (1 + .5 * sum { i=0 to n-m } of no(i-1, m))
2^p * (1 + .5 * sum { i=0 to n-m } of (1 - ok(i-1, m)))
2
  • Ага, спасибо, буду разбираться. К похожему рекурсивному алгоритму я тоже пришел.
    – andy.37
    20 фев 2016 в 14:32
  • @andy.37, можно попытаться посчитать сумму. Либо раскрыть no не в разность, а подставить формулу туда.
    – Qwertiy
    20 фев 2016 в 17:04

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.