Pull to refresh

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

Level of difficultyMedium
Reading time8 min
Views2.2K

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

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

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

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

Если выпали два орла — дежурит Петя; если один орёл и одна решка — Маша с Васей; если две решки — перебрасываем

В итоге жребий будет честным: Петя будет дежурить ровно в трети игр

Сколько бросков потребуется, чтобы выбрать дежурного? Иногда достаточно двух, но бывает, что и десять — если очень не везёт

В среднем на это уходит 8⁄3 броска. Попробуйте посчитать сами а чуть позже мы сделаем это вместе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда:

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

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

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

Иллюстрация к вычислению
Иллюстрация к вычислению S
Две и две трети монетки по версии Chat GPT
Две и две трети монетки по версии Chat GPT

Ход состоит из двух бросков, а значит их ожидаемое число это

2S = 2 \frac{2}{3}

Можно придумать и другие похожие способы выбрать дежурного

Например, бросать три монеты за шаг: из восьми возможных троек два варианта отдать Пете, четыре — Маше и Васе, а оставшиеся два — перебрасывать. Можно использовать четыре монеты, выбрать 5 вариантов для Пети, 10 — для Маши и Васи

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

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

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

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

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

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

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

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

Утверждение. Для любого n выполняется неравенство p_n \ge \frac{1}{2^{n-1}}

Доказательство оценки
  • Заметим, что после n - 1 броска возможны 2^{n-1} различных исходов. Оценим, для скольких из них алгоритм точно продолжает работу

  • Если бы алгоритм гарантированно завершался после n - 1 броска, исходы делились бы в отношении 1:2 — но 2^{n-1} не делится на три

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получается, мы должны распределить числа (1/2, 1/4, 1/8, \ldots) на две суммы так, чтобы первая равнялась 1/3, а вторая — 2/3

Каждое из чисел в ряду в два раза меньше предыдущего, поэтому сумма чисел на чётных местах (1/4, 1/16, \ldots) в два раза меньше суммы чисел на нечётных (1/2,\ 1/8,\ \ldots). Получается, что они составляют 1/3 и 2/3 всей суммы соответственно

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

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

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

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

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

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

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

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

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

В таком случае 0.a_1a_2a_3\ldots называют двоичной записью числа X

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

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

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

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

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

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

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

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

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

Дональд Кнут, «отец анализа алгоритмов»
Дональд Кнут, «отец анализа алгоритмов»

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

Бросаем монету до первого орла. Пусть он выпал на n-м броске. Посмотрим на n-й знак в двоичной записи p. Если это 1 — дежурит Петя, 0 — Маша и Вася

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

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

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

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

Например, слову (\text{О}, \text{Р}, \text{Р}) соответствует число X = 0.011 = 3/8

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

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

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

  • Если p не представимо в виде k/2^m, ожидаемое время работы равно 2, а доказательство работает так же, как для 1/3

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

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

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

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

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

Клод Шеннон, один из авторов понятия энтропии
Клод Шеннон, один из авторов понятия энтропии

Что можно сказать про среднее число бросков в таком алгоритме? Оно зависит от формы распределения. Чем вероятности равномернее, тем больше бросков в среднем требуется; если один исход гораздо вероятнее других — алгоритм завершается быстрее

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

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

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

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

Ссылки

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

Задача

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

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

Tags:
Hubs:
+13
Comments12

Articles