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