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

Начнем наш сегодняшний путь с задачи

Три айтишника — Маша, Вася и Петя — пошли в поход. После ужина они решают, кто будет мыть посуду. Петя дежурит один, а Маша с Васей — вдвоём. Значит, нужно выбрать Петю с вероятностью, а Машу с Васей — с вероятностью

Под рукой — только честная монетка. Как с её помощью устроить такой жребий?

Возникает вопрос: можно ли выбрать дежурного побыстрее?

Существует ли алгоритм, для которого ожидаемое число бросков меньше, чем для базового?

Оказывается, ответ да: существует простой, но неочевидный метод, позволяющий смоделировать событие с вероятностью — и в среднем требует не больше двух бросков. Он называется алгоритмом Кнута–Яо

Версия этого текста со всеми формальными определениями и техническими деталями будет выложена в моем телеграм канале Кроссворд Тьюринга

Подписывайтесь!)

В этой статье мы пройдём весь путь к этому алгоритму. Начнём с базового алгоритма, научимся оценивать, сколько бросков он требует в среднем, и найдём границу, быстрее которой работать невозможно. А затем построим тот алгоритм, который этой границы достигает — оптимальный для вероятности

После этого мы обобщим идею: научимся моделировать любую вероятность, а в финале — и любое дискретное распределение. Появится важное понятие, называемое энтропией, которое описывает, сколько бросков нужно для генерации распределения

А в самом конце — как всегда, красивая задача

Но прежде всего — разберёмся, откуда в базовом алгоритме появляется

Задача. Игрок бросает пару монет, пока на одной из них не выпадет орёл. Сколько в среднем продлится эта игра?

Будем считать, что ход — это бросок пары монет. Обозначим за ожидаемое количество ходов в игре. Посмотрим, из чего оно складывается:

• Первый ход совершается всегда — его вклад в равен

• Второй происходит только тогда, когда на обеих монетах выпали решки. Это случается в игр, то есть его вклад в равен

• Каждый последующий ход происходит в раза реже и даёт вклад в раза меньше, чем предыдущий.

Тогда:

Как считать сумму геометрической прогрессии

Число — площадь гусеницы (фигуры на картинке). Она состоит из жёлтого квадрата и хвоста. Но хвост — та же гусеница, уменьшенная вдвое по обеим координатам и в раза по площади

Тоже самое можно получить и с помощью теории вероятностей: первый шаг происходит всегда, а дальше — с вероятностью игра начинается заново
Таким образом:

Упражнение. Найдите ожидаемое время работы этих двух алгоритмов

Такие схемы устроены одинаково: на каждом шаге бросается одно и то же число монет, и в зависимости от выпавшего набора принимается решение или перебрасываем

Назовём такие алгоритмы пошаговыми

Нет смысла бросать одну монету за раз. Если бросать дважды — возможен только базовый алгоритм. Остальные схемы требуют не меньше трёх бросков уже на первом шаге, а значит работают медленнее, чем 8/3. Получается, базовый алгоритм — самый быстрый среди пошаговых

Может быть, базовый алгоритм оптимален? Чтобы ответить, нужно не просто сравнивать схемы между собой, а оценить снизу ожидаемое число бросков. То есть найти границу, быстрее которой не может работать никакой алгоритм, даже самый изощрённый. Сейчас мы это сделаем

Представим, что кто-то придумал хитрый алгоритм, совсем не похожий на базовый. Он может действовать как угодно — принимать решение по длине серий, по чётности, по позициям орлов. Верно одно: он выбирает Петю с вероятностью , а Машу с Васей — с вероятностью . Мы не знаем, как он устроен, но хотим оценить ожидаемое число бросков

Обозначим за вероятность того, что, действуя по алгоритму, нам придётся бросить монетку хотя бы раз. Тогда, как и в прошлом разделе:

Докажем, что вероятность не может быть слишком малой

Утверждение. Для любого выполняется неравенство

Доказательство оценки

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

• Если бы алгоритм гарантированно завершался после броска, исходы делились бы в отношении — но не делится на три

• Значит, для какого-то исхода алгоритм продолжит работу, следовательно, с вероятностью не меньше придётся бросить раз

Получается, ожидаемое число бросков можно оценить так:

Эту сумму можно найти, используя уже знакомое вычисление :

Упражнение. Пусть для некоторого алгоритма . Сколько есть исходов для бросков, после которых он остановится?

Возникает естественный вопрос:

Можно ли достичь этой границы?

Существует ли алгоритм, для которого среднее число бросков равно ?
В следующем разделе мы разберёмся, как этого добиться

Мы хотим построить алгоритм, в котором ожидаемое число бросков равно . Мы знаем, что это возможно только если после любого числа бросков один результат ведёт к продолжению, а остальные — к завершению

Запишем этот единственный результат как слово из букв (решка) и (орёл). Например, значит, что после решки, орла и двух решек алгоритм всё ещё работает

Назовём эти слова незавершёнными

Незавершённые слова продолжают друг друга. Если — незавершённое, то и тоже. То есть каждое следующее незавершённое слово получается из предыдущего приписыванием буквы в конец

Например, алгоритм может продолжаться на таких словах:

Все они — начальные отрезки одной бесконечной последовательности

Назовём её управляющей последовательностью алгоритма

Алгоритм продолжает работу после n бросков тогда и только тогда, когда результат этих бросков совпадает с первыми n буквами управляющей последовательности

Теперь легко описать алгоритмы с ожидаемым числом бросков

Утверждение. Алгоритм в среднем требует броска, если он работает до тех пор, пока результат совпадает с некой последовательностью — и завершает работу при первом отклонении

Можно выбрать любую управляющую последовательность (они ничем не отличаются друг от друга). Алгоритм особенно прост, если она состоит из одних решек: бросаем монетку до первого орла и принимаем решение

Упражнение. Покажите, что ожидаемое число бросков до первого орла равно , не используя бесконечную сумму

Именно на основе такой управляющей последовательности — из одних решек — мы сейчас построим алгоритм, решающий исходную задачу

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

Алгоритм завершается, если на -м броске впервые выпал орёл, а до этого были только решки. Вероятность такого исхода равна

После завершения алгоритма мы с определенностью понимаем, кто идет дежурить. Таким образом все исходы делятся на две группы, и вероятность дежурства Пети складывается из вероятностей исходов первой группы, а Маши с Васей — из вероятностей исходов второй

Получается, мы должны распределить числа на две суммы так, чтобы первая равнялась , а вторая —

Каждое из чисел в ряду в два раза меньше предыдущего, поэтому сумма чисел на чётных местах () в два раза меньше суммы чисел на нечётных (). Получается, что они составляют и всей суммы соответственно

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

Таким образом, получаем простой и естественный алгоритм

Алгоритм. Бросаем монетку до первого орла. Если он выпал на чётном броске — дежурит Петя, иначе — Маша и Вася

Так мы завершили путь к оптимальному алгоритму: начали с наивного решения, вывели формулу для среднего числа бросков, нашли границу, быстрее которой никакой алгоритм работать не может — и построили алгоритм, который эту границу достигает

Алгоритм, который мы построили, точно реализует вероятность — и делает это с минимально возможным числом бросков. Теперь хочется понять:

Можно ли тем же способом смоделировать любую вероятность?

Мы построили алгоритм, который отправляет Петю дежурить с вероятностью , и делает это в среднем за два броска. Оказывается, то же самое можно сделать для любой вероятности от до

Как и раньше, будем бросать монетку до первого орла. Алгоритм завершается, если на -м броске впервые выпал орёл, а до этого были только решки. Этот исход даёт вклад в вероятность, и мы хотим выбрать такие исходы, чтобы сумма вероятностей была равна . Как это сделать

Напомним, что такое двоичная запись числа. Последовательности нулей и единиц можно сопоставить числу от до . Например:

В таком случае называют двоичной записью числа

Утверждение. У любого числа от 0 до 1 есть двоичная запись (возможно, бесконечная)

Почему двоичная запись всегда существует

Построим последовательность нулей и единиц пошагово:

• Разобьём отрезок пополам. Если лежит в левой половине, пишем , если в правой (или посередине) —

• Выберем ту половину, в которой оказалась точка, и теперь вместо отрезка работаем с ней — снова делим пополам, находим , и так далее

Покажем, что эта последовательность действительно задаёт число Рассмотрим её начальный участок:

Это левая граница отрезка, полученного на шаге . Тогда:

Значит, приближается к , и последовательность задаёт число :

Теперь понятно, как обобщить алгоритм для любой вероятности

Этот алгоритм можно сформулировать и иначе — возможно, чуть проще — если использовать двоичную запись как управляющую последовательность алгоритма

Алгоритм Кнута–Яо, вторая версия. Бросаем монету до первого отклонения от управляющей последовательности. Если это орёл — дежурит Петя, если решка — Маша и Вася

Как увидеть, что алгоритм дает нужную вероятность?

Каждому набору бросков сопоставим число от 0 до 1. Для этого заменим орлы на 0, решки на 1, и получим двоичную запись числа

Например, слову соответствует число

Алгоритм Кнута–Яо сравнивает случайное число с : если , дежурит Петя; если — Маша с Васей. Это можно определить в момент первого отклонения двоичных записей и

Понятно, что Петя будет дежурить с вероятностью

Алгоритм Кнута–Яо оптимален

• Если не представимо в виде , ожидаемое время работы равно , а доказательство работает так же, как для

• Если же , ситуация немного меняется: алгоритм Кнута–Яо завершится не позже, чем через бросков. Он остаётся оптимальным — и даже работает быстрее.

Подробнее про последний случай можно прочесть в Telegram-канале Кроссворд Тьюринга

Алгоритм Кнута–Яо позволяет смоделировать событие с любой вероятностью от 0 до 1. Но что делать, если исходов несколько? Например, нужно выбрать один из трёх вариантов с заданными вероятностями ? Или один из десяти?

Принцип остаётся тем же. Представим отрезок от 0 до 1, разбитый на участки длиной и . Начинаем бросать монетку и постепенно выписывать двоичную запись случайной точки на отрезке. В тот момент, когда становится ясно, в какой из частей эта точка неизбежно попадёт, алгоритм завершает работу — и мы выбираем соответствующий исход

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

Существует важный числовой инвариант распределения, называемый энтропией — мера его неопределённости. Для трёх вероятностей энтропия вычисляется по формуле:

Вероятно, никакой алгоритм не может работать быстрее, чем энтропия распределения. С другой стороны, несложно показать, что ожидаемое время работы алгоритма Кнута–Яо не превосходит энтропию плюс два:

Та же оценка верна и для произвольного числа исходов. Таким образом, алгоритм Кнута-Яо оптимален с точностью до константы

На этом мы завершим историю, начавшуюся с простой задачи про монетку

Ссылки

Вот некоторые полезные ссылки

• Питер Кэмерон A fair coin

• Григорий Мезон, Александр Перепечко Как из монетки сделать кубик, или Любой жребий за два броска («КВАНТИК» №3, 2021 )

• Видео версия статьи Мерзона и Перепечко

Задача

А тем, кто добрался до этого места, предлагаю такую задачку

Асимметричная монетка выпадает орлом с вероятностью и решкой с вероятностью . Как двум людям вытянуть честный жребий с её помощью?