Лас-Вегас и Монте-Карло: задуматься или ошибиться

Если ты отнесёшь знакомый рандомизированный алгоритм к одному из двух видов, превратишь один вид в другой и скажешь, когда обратное превращение невозможно, - листай до «Теперь сам».

Как думаешь, сколько ячеек нужно посмотреть

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

Ответь себе до чтения: сколько ячеек в худшем случае посмотрит алгоритм без случайности и сколько в среднем - алгоритм, который тычет в случайные места? Первому противник подсунет нули ровно там, куда он смотрит сначала: 500 001 ячейка. Второму подсунуть нечего - он сам не знает, куда посмотрит, - и ему хватает в среднем двух проб. Но «в среднем» скрывает вопрос: а сколько в худшем?

На что это похоже

Два способа искать ключи перед выходом из дома. Первый: искать, пока не найдёшь. Ключи будут найдены наверняка, но на встречу можно опоздать на неизвестное время. Второй: искать ровно пять минут и уйти. На встречу успеешь точно, но, возможно, без ключей.

Ни один способ не лучше другого сам по себе. Первый выбирают, когда без ключей идти бессмысленно, второй - когда опоздание хуже.

Механизм: что именно случайно и как одно меняют на другое

Алгоритм Лас-Вегас всегда возвращает верный ответ; случайной величиной является время его работы. Гарантия формулируется как ожидаемое время на любом входе.

Алгоритм Монте-Карло работает время, ограниченное заранее; случайной величиной является правильность ответа. Гарантия формулируется как вероятность ошибки на любом входе. Ошибка бывает односторонней - один из двух ответов всегда верен - и двусторонней.

И там, и там слова «на любом входе» - главное: вероятность берётся по монеткам алгоритма, а не по входам. Плохого входа нет, бывает неудачный бросок.

Знакомые алгоритмы курса раскладываются так:

Лас-Вегас: ответ верен всегда            Монте-Карло: время ограничено всегда
быстрая сортировка, случайный опорный     тест Миллера-Рабина          (односторонняя)
быстрый выбор k-го элемента               Рабин-Карп без перепроверки  (односторонняя)
декартово дерево, список с пропусками     проверка произведения матриц (односторонняя, урок 4)
хеш-таблица со случайной функцией         минимальный разрез по Каргеру (урок 5)   
Рабин-Карп с посимвольной перепроверкой   оценка по выборке            (двусторонняя)

Рабин-Карп стоит в обоих столбцах: совпадение хешей можно перепроверить посимвольно, и тогда ответ всегда верен, а время зависит от числа ложных срабатываний; можно не перепроверять - тогда время твёрдое, а ответ изредка ложный.

Из Лас-Вегаса в Монте-Карло. Пусть ожидаемое время не больше T - это число берут из анализа алгоритма, как 1,39 · n · log₂ n для быстрой сортировки. Останавливаем алгоритм через 2T шагов и отвечаем «не знаю» или что угодно. По неравенству Маркова он не успеет с вероятностью не больше 1/2; k независимых попыток не успеют все с вероятностью не больше 1/2ᵏ.

Из Монте-Карло в Лас-Вегас. Нужна проверка: быстрый способ убедиться, что ответ верен. Тогда алгоритм запускают, проверяют ответ и при неудаче запускают заново. Если один запуск успешен с вероятностью p, до успеха в среднем 1/p запусков - геометрическое распределение из первой главы. Проверка есть не всегда: найденный разрез нельзя дёшево проверить на минимальность, и алгоритм из урока 5 остаётся алгоритмом Монте-Карло.

Правило

Алгоритм Лас-Вегас: ответ всегда верен, время случайно. Алгоритм Монте-Карло: время ограничено, ответ верен с вероятностью не меньше заданной. Обрыв алгоритма Лас-Вегас на 2T шагах при ожидаемом времени T даёт алгоритм Монте-Карло с вероятностью отказа не больше 1/2. Алгоритм Монте-Карло с вероятностью успеха p и проверкой ответа за время V даёт алгоритм Лас-Вегас с ожидаемым временем (время запуска + V) / p.

Разбор: поиск единицы двумя способами

Массив из тысячи ячеек, единицы на нечётных местах. las_vegas пробует случайные ячейки до первой единицы и возвращает её номер и число проб. monte_karlo делает не больше трёх проб и при неудаче возвращает −1.

import random

def las_vegas(a):
    prob = 0
    while True:
        prob = prob + 1
        i = random.randrange(len(a))
        if a[i] == 1:
            return [i, prob]

def monte_karlo(a, popytok):
    for p in range(popytok):
        i = random.randrange(len(a))
        if a[i] == 1:
            return i
    return -1

random.seed(31)
a = [0, 1] * 500
opytov = 4000
vsego_prob = 0
hudshee = 0
otkazov = 0
for opyt in range(opytov):
    otvet = las_vegas(a)
    vsego_prob = vsego_prob + otvet[1]
    hudshee = max(hudshee, otvet[1])
    if monte_karlo(a, 3) == -1:
        otkazov = otkazov + 1
print(round(vsego_prob / opytov, 3), hudshee, round(otkazov / opytov, 4))

2.001 14 0.1325

Лас-Вегас: в среднем 2,001 пробы, как и обещает 1/p при p = 1/2. Но в худшем из четырёх тысяч запусков проб было 14, и верхней границы у этого числа нет: с вероятностью 1/2⁴⁰ их будет больше сорока.

Монте-Карло с тремя пробами отказал в 13,25% запусков при расчётных 1/2³ = 12,5%. Его время - не больше трёх проб. А ошибка у него односторонняя: если номер возвращён, там точно единица. Отказ −1 не доказывает, что единиц нет.

По существу функции отличаются одним - условием цикла. Это и есть переход между видами: while True против for с пределом.

Разбор: оценка числа π и граница метода

Второй смысл слова. Метод Монте-Карло - оценить величину, которую трудно посчитать, как долю случайных проб, попавших в цель. Четверть круга радиуса 1 занимает долю π/4 единичного квадрата. Бросаем в квадрат случайные точки и считаем долю попавших в круг.

import math
import random

random.seed(314)
for tochek in [100, 1000, 10000, 40000]:
    vnutri = 0
    for i in range(tochek):
        x = random.random()
        y = random.random()
        if x * x + y * y <= 1:
            vnutri = vnutri + 1
    ocenka = 4 * vnutri / tochek
    garantiya = 4 * math.sqrt(math.log(2 / 0.05) / (2 * tochek))
    print(tochek, round(ocenka, 4), round(abs(ocenka - math.pi), 4), round(garantiya, 4))

100 3.32 0.1784 0.5432
1000 3.092 0.0496 0.1718
10000 3.1292 0.0124 0.0543
40000 3.1403 0.0013 0.0272

Столбцы: число точек, оценка, её ошибка и ошибка, которую граница Хёфдинга из прошлой главы допускает с вероятностью 5%. В программе math.sqrt(x) - квадратный корень, math.pi - число π. Последний столбец получен из n ≥ ln(2/δ) / (2ε²), решённого относительно ε, и умножен на 4, потому что оценка - это доля, умноженная на 4. Ошибка убывает как корень из числа точек: в четыреста раз больше точек дали в двадцать раз более узкую гарантию. Это двусторонний алгоритм Монте-Карло: время задано, ответ приближённый с известной надёжностью.

Граница метода - редкие события. Пусть цель занимает одну миллионную квадрата. Тогда из сорока тысяч точек в неё, скорее всего, не попадёт ни одна, и оценка будет «ноль» - с огромной относительной ошибкой. У оценки доли p по n пробам стандартное отклонение около √(p/n); чтобы оно составляло 10% от самой доли, нужно порядка 100/p проб. Когда p мало, пробы делают не равномерно, а там, где цель вероятнее, и поправляют ответ на это смещение.

Что ломается без этого

Ответ Монте-Карло принимают за истину. «Тест сказал: простое» - это «простое с вероятностью ошибки не больше 1/4ᵏ». Пока k достаточно велико, разницей пренебрегают, но при k = 2 она равна шести процентам.

Алгоритм Лас-Вегас ставят туда, где есть предел времени. Обработчик, который обязан ответить за 50 мс, не может вызывать цикл «пока не повезёт» без предела: среднее время ничего не обещает одному вызову.

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

Превращение в Лас-Вегас без проверки. «Запустим десять раз и возьмём лучший ответ» не делает алгоритм точным, если нечем убедиться, что лучший из десяти - верный.

Зачем это в работе

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

Выбор между видами - инженерное решение. Проверка дубликатов файлов по хешу - Монте-Карло; побайтовое сравнение совпавших - Лас-Вегас, с повторным чтением каждой совпавшей пары. Системы резервного копирования обычно выбирают первое с хешем в 256 бит: при любом достижимом числе файлов вероятность его коллизии несравнимо меньше вероятности сбоя оборудования.

И оценка выборкой - рабочий инструмент там, где точный счёт невозможен: доля строк, подходящих под условие запроса, в планировщике базы данных; интеграл в трассировке лучей; вероятность отказа системы, посчитанная прогоном модели.

Теперь сам

1. Алгоритм возвращает верный ответ всегда и работает в среднем 4 секунды. К какому виду он относится и что можно сказать о вероятности, что он проработает больше 40 секунд?
2. Алгоритм Монте-Карло находит решение с вероятностью 0,2, запуск занимает 3 мс, проверка решения - 1 мс. Каково ожидаемое время алгоритма Лас-Вегас, построенного из него?
3. Проверка «есть ли подстрока» по Рабину-Карпу без посимвольной перепроверки ответила «нет». Может ли ответ быть неверным?
4. Долю медленных запросов оценивают по выборке из 10 000. Во сколько раз нужно увеличить выборку, чтобы гарантированная ошибка стала втрое меньше?
5. Почему алгоритм поиска минимального разреза нельзя превратить в алгоритм Лас-Вегас так же, как поиск единицы?