Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
На примере хорошей задачки по теории вероятностей мы сравним что круче - аналитические решения или моделирование. Вначале я хотел написать только аналитическую часть и попросить заинтересованных читателей запрограммировать симуляцию задачи. Но нехорошо перекладывать на других свои дела, поэтому, в меру способностей, постарался сделать и вторую часть. Попутно знакомясь с Питончиком. Если что-то в коде получилось коряво, милости просим наставить на путь истинный.
Задачка такая:
В ящике 4 белых 10 черных шаров. Из него наудачу вынимают шар, фиксируют его цвет и возвращают шар назад в ящик. Назовем «белым пулом» любую максимальную цепочку подряд вынутых белых шаров. Найти математическое ожидание количества «белых пулов» при извлечении из ящика 20 шаров.
Аналитический подход
Чтобы решить такую задачку, нужно прочувствовать ее изнутри - представить себя белым шаром, черным шаром, всеми шарами сразу вместе... Картинка поможет настроиться на нужный лад и не подглядывать в решение, если захотелось порешать сначала самому.
Внимание, мой вариант решения. Возможны арифметические ошибки, но ответ похож на правду и будет проверен моделированием.
Мне кажется задачка нетривиальная. По крайне мере, все виденные мной на просторах интернета попытки решения были весьма плачевны. Люди получали в ответе математическое ожидание числа белых пулов, большее чем их максимально возможное число...
Первый шаг, который я сделал - интуитивно почувствовал, что нужно использовать индуктивный подход, начав с небольшого числа извлеченных шаров. Хорошо бы еще формализовать задачу. Сделать это проще всего перейдя к рассмотрению двоичных последовательностей (см. также предыдущий пост про слоистые среды). Ноль у меня будет обозначать черный шар, единичка - белый. Тогда, например, в последовательности 1-0-1-0-111-0-11-0-1-000 будет 5 белых пулов с длиной от 1 до 3. Изолированная с двух сторон нулями единичка - уже белый пул! Поэтому при вытаскивании 20 шаров максимальное число пулов будет равно 10 (чередование нулей и единиц). Соответственно ответ, который хитрый студент найдет в гугле = 100/7, будет весьма далек от правды.
Идем дальше. При извлечении 2х шаров нам нужно рассмотреть 4 варианта: 0=00, 1=01, 2=10, 3=11. Соответственно, при извлечении 3х шаров нужно рассматривать двоичные последовательности задающие числа от 0 до 7, и т.д.
В случае последовательности из 2х шаров матожидание числа белых пулов найти просто. У нас есть ноль пулов, и три раза по одному пулу. А дальше мы делаем твист, который может сбить с толку. Обозначим это матожидание как <N(2)>, но вычислять его не будем - вдруг и не понадобиться потом!
Если взять большее число испытаний, то возникает сложность с одновременным подсчетом числа пулов и соответствующих вероятностей. Понятно, что для каждой двоичной последовательности вероятности появления нулей и единиц нужно перемножить. Но их нужно как-то подсчитать. К счастью, в задаче есть повторяющаяся структура. При увеличении числа испытаний сначала все двоичные последовательности повторяются, потом слева появляется дополнительная единичка и снова все повторяется.
Логично попробовать вывести рекуррентную формулу для матожидания <N(n)>. Сделать это можно так — при n испытаниях вы должны выписать двоичные представления чисел от 0 до
Обозначим
Следующий шаг уже вполне предсказуем. Наша стратегия заключается в том, чтобы не выводить формулы для числа пулов и числа единичек! Используем аналог ленивых вычислений - ленивую аналитику. Запишем матожидание числа пулов
Тоже самое сделаем для матожидания при увеличенном на 1 числе испытаний
Теперь нужно в формуле для <N(n+1)> попытаться выделить <N(n)>. Для этого нужно понять как работает число пулов, при добавлении еще одного двоичного разряда. Если число i по прежнему может быть представлено n разрядами, то добавление нового двоичного разряда просто соответствует приписыванию 0 слева. Число белых пулов и число единичек не меняется
Дальше в двоичном разложении слева появляется изолированная единичка, что увеличивает число белых пулов и число единиц на, простите, единицу
И в оставшемся диапазоне, левая единичка сливается с предыдущей единичкой, в итоге
Теперь все это добро надо подставить в формулу для математического ожидания длины белых пулов при n+1 испытаниях. После некоторых алгебраических преобразований (где и могут быть ошибки, в основном, из-за манипуляций с верхними пределами суммирования) у меня получилось, что
Это уже замечательно! Число белых пулов вычислять не надо. Но есть сумма, в которую входит выражение для числа единиц. Для оставшейся суммы я не придумал ничего лучше, чем снова найти рекуррентное соотношение
Теперь если мы увеличим число испытаний на единичку, число слагаемых вырастет в два раза. Первая половина суммы не поменяется, а у вторая половина будет точно такая же как первая, только с дополнительным множителем за счет добавления одной единички
Получилась геометрическая прогрессия!
Теперь можно выписать искомое рекуррентное соотношение без наших вспомогательных функций p и u:
Это арифметическая прогрессия! Значит
И, окончательно, <N(20)>=200/49~4, то есть в среднем мы ожидаем 4 белых пула. Ответ похож на правду, если учесть что число возможных пулов от 0 до 10.
Моделирование.
Давайте теперь решим задачу с помощью моделирования! Надо запустить генератор двоичных последовательностей длиной в 20 символов с вероятностью появления нулей и единичек из задачи. Я просто сделал ящик=последовательность с 10 нулями и 4 единичками и случайным образом вытаскиваю 20 раз по одному элементу. Появление и исчезновение белого пула я подсчитываю по изменению следующего элемента. При этом каждый пул кроме, возможно, последнего, будет учтен два раза.
import random
box = [1,1,1,1,0,0,0,0,0,0,0,0,0,0]
def poolnumber():
unitcount=0
poolcount=0
pooldelim=0
for i in range(1, 21):
ball=random.choice(box)
#print(ball)
unitcount=unitcount+ball
if ball!= pooldelim:
poolcount+=1
pooldelim=ball
res=round(poolcount/2)
#print(unitcount)
#print(round(poolcount/2))
return resНу а теперь много раз вызовем функцию подсчета пулов и найдем среднее
totalpoolnumber=0
size=5000
for i in range(1, size):
totalpoolnumber=totalpoolnumber+poolnumber()
print(totalpoolnumber/size)
print(200/49)Удивительно, но вероятные арифметические ошибки в аналитической части не случились! И 500 и 20000 испытаний дают 4.0xxx - близкий ответ к аналитическому решению! Однако, насколько проще и быстрее реализовать модель! К тому же, можно уже полученную модель применить для решения более сложных задач - искать, например, среднюю длину белого пула, или среднюю длину пула максимальной длины. Так что, хоть я и занимаюсь "точно решаемыми" задачами, но должен признаться - использование программирования и моделирования является мощным и универсальным инструментом.
PS: Моделирование сначала давало заниженный ответ, близкий к 3.8. И только знание точного ответа, хотя я в нем и засомневался, позволило мне найти ошибку - шарик я вытаскивал не 20 раз, а всего 19. Когда это поправил, сразу добился замечательного согласия теории и эксперимента! И в защиту аналитического метода решения, скажу, что ответ у нас получился для любого числа испытаний - мы нашли, что среднее число белых пулов растет с числом вытащенных шаров линейно. В принципе, этого и следует ожидать от аналитического подхода - попадание в общие свойства решения.
