Невероятные события: может ли выпасть 400 орлов из 1000 бросков?

В недавней статье про Закон больших чисел мы оценивали вероятность больших отклонений с помощью неравенства Чебышёва. Для тысячи бросков монетки оно даёт границу 2,5% для отклонения в 100 и более орлов. Мне стало интересно, насколько это близко к правде. Я написал симуляцию и проверил — сначала на сотне прогонов, потом на тысяче, потом на ста тысячах. Ни одного такого исхода. Реальная вероятность оказалась меньше 5 ⋅ 10 ⁹ — катастрофически меньше, чем 2,5% из оценки Чебышёва. Именно это стало поводом для написания статьи. Мы хотим понять, как связано число испытаний, отклонение и вероятность. Если зафиксировать отклонение, какова вероятность его превышения? Если зафиксировать вероятность, каким должно быть допустимое отклонение? И, наконец, если заданы и вероятность, и отклонение, то сколько испытаний нужно провести, чтобы с заданной вероятностью уложиться в эти рамки? В этой статье мы начнём с эксперимента и дойдём до строгой экспоненциальной оценки, которая работает для любого числа испытаний. По дороге докажем оценку Чернова и выведем частный случай неравенства Хёффдинга и разберём, как они устроены. Такие оценки широко используются в прикладной математике . Нам важно заранее знать, сколько испытаний провести, чтобы с частота с заданной точностью приблизилась к истинной вероятности события. Разница между прогнозами, которые дают неравенство Чебышёва и экспоненциальные оценки, может быть колоссальной! К неравенству Хёффдинга

https://habr.com/ru/articles/935676/

#математика #теория_вероятностей #статистика #закон_больших_чисел #центральная_предельная_теорема #случайность #интуиция #монте_карло #математическое_ожидание #доверительный_интервал

Жребий брошен: оптимальная генерация распределений и алгоритм Кнута-Яо

Задача Три айтишника — Маша, Вася и Петя — пошли в поход. После ужина они решают, кто будет мыть посуду. Петя дежурит один, а Маша с Васей — вдвоём. Значит, нужно выбрать Петю с вероятностью ⅓, а Машу с Васей — с вероятностью ⅔. Под рукой — только честная монетка. Как с её помощью устроить такой жребий? Когда мы обсуждали эту задачу со студентами, они предложили такой способ. Бросим монету дважды: если выпали два орла — дежурит Петя; если один орёл и одна решка — Маша с Васей; если две решки — перебрасываем Чтобы выбрать дежурного так, в среднем уходит 8⁄3 броска (чуть позже мы это докажем). Можно ли сделать это быстрее? Существует ли алгоритм, для которого ожидаемое число бросков меньше? Оказывается, можно придумать простой, но неочевидный метод, позволяющий смоделировать событие с вероятностью ⅓ — и в среднем требует не больше двух бросков . Он называется алгоритмом Кнута–Яо В этой статье мы пройдём весь путь к этому алгоритму. Начнём с базовых методов, поймем, сколько бросков они требуют в среднем, и найдём границу, быстрее которой не может работать никакой алгоритм. А затем построим тот, который этой границы достигает — оптимальный для вероятности ⅓ В финале мы обобщим эту идею: научимся моделировать любую вероятность p от 0 до 1 — и любое дискретное распределение. Заодно познакомимся с важным понятием, называемым энтропией А в самом конце, как всегда — красивая задача

https://habr.com/ru/articles/924076/

#математика #теория_вероятностей #случайность #модель #математическое_ожидание #монетка #жребий #сэмплирование #кнут #энтропия

Алгоритм генерации волн врагов в рогалике

Привет! Недавно в ранний доступ в Steam вышла наша игра Clayers: Prologue . Это рогалик в глиняном стиле, где нужно подбирать и смешивать цвета, чтобы убивать врагов. В этой статье разберём наш подход к генерации волн с учётом сложности противников.

https://habr.com/ru/articles/880924/

#рогалик #генерация #волны #алгоритм #формулы #математическое_ожидание #godot