nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Метод крутого Уокера, или о пользе кубиков

На троих мы сообразили, один из самых быстрых методов с помощью монетки сделать равновероятный выбор из 3 альтернатив таков:

Кидаем монетку 2 раза, это дает 4 равновероятных исхода, условно, 00, 01, 10 и 11.
00-идет первый студент,
01-идет второй,
10-идет третий,
11-перекидываем.

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

Возьмем куда более общую задачу. Есть выбор из K вариантов, каждый должен происходить с вероятностью pk, k=0..K-1. Пример распределения на рисунке, мы хотим выбрать один из цветов, хотя с тем же успехом можно выбирать целые числа или ветви исполнения.

В этот раз вместо монеты возьмем нечто покруче - rnd, он же random, он же генератор равномерно распределенных на [0;1) псевдослучайных чисел.

Классический метод, который сразу приходит в голову: делим отрезок [0;1] на части, каждая отвечает за свой вариант. Генерим случайную величину - по сути берем на отрезке произвольную точку. На какой цвет она попадет, тот и выбираем.

Но он не так уж и хорош. Нам придется делать цикл и проверять последовательно нахождение случайной величины внутри каждого интервала, пока не найдем нужный. Скажем, выпало 0.55, мы начинаем смотреть:
0.55>4/108=0.037, идем дальше,
0.55>12/108=0.111, идем дальше,
0.55>27/108=0.25, идем дальше,
0.55>43/108=0.398, идем дальше,
0.55<66/108=0.6111, значит, выбираем коричневый (единичку, если по маркировке резисторов).
Замучаемся! Конечно, сразу возникает идея применить двоичный поиск - зачем идти слева направо, если можно тыкнуться в центральный интервал, сравнить с ним и потом решать - идти вправо или влево. В таком случае выбор можно будет произвести за O(logK), что вообще-то неплохо, но есть метод куда более простой и эффективный!

Он называется методом Уокера (Walker) или методом псевдонимов (Alias Method), видимо, чтобы никто не догадался. На первый взгляд он выглядит как шаманство. Мы вводим две вспомогательные таблицы Pk (действительные числа) и Yk (целые числа) длиной по K - их нужно посчитать для заданного распределения только один раз. А дальше, процесс случайного выбора выглядит так:

Генерим случайную величину U с помощью rnd (Кнут называет их U от слова Uniform-равномерные). Затем умножаем на K, берем целую и дробную часть: M=[KU], V=KU-M. Очевидно, M принимает целые значения от 0 до K-1, а V – действительные на [0;1), причем имеет равномерное распределение.
И наконец, гвоздь программы, одна строка:

если V<PM, то выбираем M, иначе выбираем YM.
Понятно? По мне, так не очень. Сейчас объясним, откуда оно возникает и как построить таблицы. А помогут нам в этом разноцветные кубики.


Пусть у нас есть N разноцветных кубиков. Всего цветов K, они пронумерованы от 0 до K-1. Количество кубиков, имеющих цвет k, обозначаем как pk. Понятно, что p0+p1+…pK-1=N. И еще у нас есть K одинаковых коробок, в каждую из которых вмещается по N/K кубиков, для простоты считаем, что это натуральное число.

На рисунке ниже у нас 108 кубиков 6 различных цветов, есть 6 коробок, в каждую из которых уместится 18 кубиков.

Метод основан на утверждении, что ВСЕГДА, независимо от конкретных pk, эти кубики можно так упихать в коробки, что в каждой коробке будут находиться кубики не более, чем двух цветов.
Легче всего это доказать по индукции. Возьмем K=1: один цвет, одна коробка, все кубики в нее влезают, порядок.

Теперь, предполагая, что все выполняется для K-1, докажем, что будет выполняться и для K.
Всегда можно будет найти такой цвет k такой, что pk≤N/K и цвет m такой, что pm≥N/K. То есть, или их всех поровну, или одного цвета будет меньше, а значит другого будет больше, иначе быть не может. Берем одну пустую коробку и кладем в нее все кубики цвета k, там может остаться свободное место, в него кладем кубики цвета m, сколько влезет. Откладываем эту коробку в сторону. У нас остались кубики с K-1 разных цветов, их количество N1=N(K-1)/K и мы хотим распихать их в K1=K-1 коробку, по N1/K1 = N/K кубиков в каждую. Задача сведена к случаю K-1, доказательство по индукции завершено.

Усложним немножко задачу и окрасим сами коробки, каждая будет своего цвета. Каждый раз, выбирая цвет m, мы можем и коробку брать соответствующего цвета. Сейчас мы проделаем это на конкретном примере, а потом уже станет понятно, какой нам от этого прок.

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

Продолжим складывать те кубики, которых слишком много, туда, где их слишком мало и в конце концов каждый найдет свое место так, что на каждой строке будет не более 2 цветов:


А дальше все просто. Выбор цвета - это ни что иное, как выбор наугад одного из кубиков, его цвет мы и возьмем. Для начала выберем наугад одну из K коробок, с равной вероятностью. Далее нам достаточно знать, какую долю коробки занимают кубики ее родного цвета, и какого цвета кубики мы туда доложили. Первую величину назовем Pk, а вторую: Yk. Теперь смотрим еще раз на описания метода Уокера и все становится на свои места.

За дальнейшими разъяснениями можно обратиться на википедию - статья плахой, ссылки харощий!
На русском языке объяснение есть у Кнута, во 2-м томе, глава "Численные распределения". Понять, как построить таблицы и почему оно вообще будет работать как надо - оставляется читателю в качестве упражнения. К нему есть сжатый ответ, но берегитесь: в нем ошибка при доказательстве по индукции. Она несущественная, но может смутить: только начинаешь понимать, и тут на тебе, что-то очень странное.

По мне, так шикарнейший метод!
Tags: Монте-Карло для чайников, математика, моделирование
Subscribe

  • Хотел выпендриться

    Одно из замечаний к моему протоколу информационного обмена: ДОБАВЬ 16-битные заголовки к каждому сообщению! Нам могут прислать командное слово с…

  • Моделирование стыковки с помощью ВидеоИзмерителя

    "Нарисовал"-таки видеоролик, где мы начинаем с весьма неблагоприятных условий: вместо того, чтобы нас поставить ровно "напротив" стыковочного узла,…

  • Более тяжёлые тела падают быстрее!

    Увидел не так давно видео от Flammable Maths с таким заголовком, и подумал поначалу - он опять нас троллит. Это немецкий препод математики…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 2 comments