Вероятностный метод, дерандомизация и принцип Яо

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

Как думаешь, всегда ли есть разрез в половину рёбер

Дан произвольный граф со ста рёбрами. Его вершины нужно разбить на две группы так, чтобы как можно больше рёбер шло из одной группы в другую.

Ответь себе до чтения: в любом ли графе можно добиться, чтобы между группами шло хотя бы 50 рёбер? Или противник построит граф, в котором лучшее разбиение режет только 30? В любом. Доказательство занимает одну строку и не предъявляет разбиения - оно показывает, что его не может не быть.

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

Средний рост в классе - 150 сантиметров. Отсюда без единого измерения следует, что в классе есть ученик ростом не ниже 150 и есть ученик ростом не выше 150. Все сразу не могут быть ниже среднего.

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

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

Вероятностный метод. Случайная величина не может быть всегда строго меньше своего ожидания. Значит, если E[X] = μ, то хотя бы на одном исходе X ≥ μ - и хотя бы на одном X ≤ μ.

Применим к разрезу. Каждую вершину независимо отправим в левую или правую группу монеткой. Ребро попадает в разрез, когда его концы в разных группах: вероятность 1/2. Индикатор на каждое ребро, линейность:

E[размер разреза] = m · 1/2 = m/2

Раз в среднем по всем разбиениям получается m/2, существует разбиение, которое режет не меньше m/2 рёбер.

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

условное ожидание = (рёбра, оба конца расставлены и стоят по разные стороны)
                  + 1/2 · (рёбра, у которых хотя бы один конец ещё не расставлен)

В начале оно равно m/2. Берём очередную вершину v. Если бы мы бросили монетку, условное ожидание после броска в среднем осталось бы прежним - значит, хотя бы один из двух вариантов его не уменьшает. Какой именно, видно сразу: рёбра от v к ещё не расставленным соседям при любом выборе дают по 1/2, а рёбра к расставленным соседям режутся, если v стоит напротив. Поэтому v ставят напротив большинства своих уже расставленных соседей.

Условное ожидание ни на одном шаге не уменьшилось, в начале было m/2, а в конце монеток не осталось и оно равно настоящему размеру разреза. Получился жадный алгоритм с гарантией m/2.

Принцип Яо. Рандомизированный алгоритм - это случайный выбор одного из детерминированных: зафиксируй все монетки заранее, и останется обычный алгоритм. Пусть нужно доказать, что никакой рандомизированный алгоритм не справится с задачей дешевле некоторой цены. Перебирать все способы бросать монетки невозможно. Принцип Яо предлагает другую работу: придумать распределение входов и показать, что любой детерминированный алгоритм на случайном входе из этого распределения в среднем платит не меньше c. Тогда у любого рандомизированного алгоритма найдётся вход, на котором его ожидаемая цена не меньше c.

Довод - то же «не все ниже среднего», применённое дважды. Если бы рандомизированный алгоритм на каждом входе платил в среднем меньше c, то и в среднем по входам из распределения он платил бы меньше c. Но он - смесь детерминированных, и значит, какой-то из них в среднем по входам платит меньше c. А таких нет.

Правило

Если E[X] = μ, существует исход с X ≥ μ и исход с X ≤ μ. В любом графе с m рёбрами есть разрез размера не меньше m/2, и жадный алгоритм «ставь вершину напротив большинства уже расставленных соседей» его находит. Принцип Яо: наибольшая по входам ожидаемая цена любого рандомизированного алгоритма не меньше, чем наименьшая по детерминированным алгоритмам средняя цена на любом заранее выбранном распределении входов.

Разбор: двести случайных разбиений и одно жадное

Случайный граф на 30 вершинах со 100 рёбрами. Первая часть программы бросает двести случайных разбиений и печатает средний, наименьший и наибольший разрез. Вторая расставляет вершины жадно.

import random

random.seed(37)
n = 30
m = 100
ryobra = []
while len(ryobra) < m:
    a = random.randrange(n)
    b = random.randrange(n)
    if a != b and [a, b] not in ryobra and [b, a] not in ryobra:
        ryobra.append([a, b])

def razrez(storona):
    k = 0
    for rebro in ryobra:
        if storona[rebro[0]] != storona[rebro[1]]:
            k = k + 1
    return k

opytov = 200
vsego = 0
luchshij = 0
hudshij = m
for opyt in range(opytov):
    storona = []
    for v in range(n):
        storona.append(random.randint(0, 1))
    r = razrez(storona)
    vsego = vsego + r
    luchshij = max(luchshij, r)
    hudshij = min(hudshij, r)
print(vsego / opytov, hudshij, luchshij)

sosedi = []
for v in range(n):
    sosedi.append([])
for rebro in ryobra:
    sosedi[rebro[0]].append(rebro[1])
    sosedi[rebro[1]].append(rebro[0])

storona = [-1] * n
for v in range(n):
    sleva = 0
    sprava = 0
    for u in sosedi[v]:
        if storona[u] == 0:
            sleva = sleva + 1
        if storona[u] == 1:
            sprava = sprava + 1
    if sleva <= sprava:
        storona[v] = 0
    else:
        storona[v] = 1
print(razrez(storona))

50.745 38 63
66

Средний разрез по двумстам случайным разбиениям - 50,7, как и обещает m/2 = 50. Отдельные разбиения дали от 38 до 63: случайное разбиение может оказаться и хуже половины. Жадная расстановка без единой монетки дала 66.

Гарантия жадного алгоритма - 50, а получилось 66: оценка m/2 верна для худшего графа. Она же показывает, что жадный алгоритм - приближённый с коэффициентом 1/2: наибольший разрез не больше m, а найденный не меньше m/2. Найти сам наибольший разрез - задача, для которой быстрого алгоритма не известно.

Разбор: где случайность не помогает и где метод не даёт объекта

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

По принципу Яо достаточно выбрать распределение входов. Возьмём самое естественное: единица стоит в любой из n ячеек с равной вероятностью. Детерминированный алгоритм - это фиксированный порядок, в котором он открывает ячейки. Какой бы порядок он ни выбрал, единица с равной вероятностью окажется первой, второй, …, последней в этом порядке:

средняя цена любого порядка = (1 + 2 + … + n) / n = (n + 1) / 2

Значит, у любого рандомизированного алгоритма есть вход, на котором он в среднем открывает не меньше (n + 1) / 2 ячеек. Случайность даёт здесь выигрыш не больше чем вдвое по сравнению с худшим случаем n и порядка роста не меняет. Разница с прежней задачей - в доле хороших ячеек: там их была половина, здесь одна из n.

Теперь граница самого вероятностного метода. Он доказывает, что объект существует, и не обязан его давать. Для разреза повезло: условное ожидание считается по простой формуле, и доказательство превратилось в алгоритм. Так бывает не всегда. Известный пример - графы, в которых нет ни большой группы попарно соединённых вершин, ни большой группы попарно несоединённых. Что такие графы существуют, доказано вероятностным методом в 1947 году: случайный граф подходит почти наверняка. Явно построить граф с такими же параметрами не удавалось десятилетиями: случайный граф годится, но проверить это для конкретного графа - само по себе трудная задача.

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

Из существования делают вывод «почти любой подойдёт». Ожидание m/2 не значит, что случайное разбиение обычно даёт m/2 или больше: в разборе были разбиения с 38 рёбрами. Для утверждения о типичном объекте нужна хвостовая оценка, а не одно ожидание.

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

Нижнюю оценку доказывают для одного алгоритма. «Мой рандомизированный алгоритм на этом входе медленный» ничего не говорит об остальных. Принцип Яо затем и нужен, чтобы высказаться сразу обо всех.

Распределение входов подбирают под алгоритм. В принципе Яо распределение фиксируется раньше алгоритма и должно быть плохим для каждого детерминированного, а не для одного выбранного.

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

Вероятностный метод уже работал в этом курсе, без названия. Идеальное хеширование из раздела про хеш-таблицы: если n ключей кладут в n² ячеек случайной функцией из универсального семейства, ожидаемое число коллизий меньше 1/2. Значит, функция без коллизий существует, и больше того - по неравенству Маркова случайная функция подходит с вероятностью больше 1/2. Отсюда алгоритм «пробуй случайные функции, пока не найдёшь», в среднем две попытки.

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

Принцип Яо - основной способ доказывать пределы. Нижняя граница log₂ n! сравнений для сортировки переносится на рандомизированные сортировки именно им: на случайной перестановке любая детерминированная сортировка в среднем делает не меньше log₂ n! сравнений, а значит, монетки не дадут сортировать сравнениями быстрее n · log n даже в среднем.

Теперь сам

1. Вершины графа с m рёбрами красят в три цвета случайно и независимо. Ребро «правильное», если его концы разного цвета. Что вероятностный метод говорит о существовании раскраски?
2. Формула состоит из m скобок, в каждой - три разные переменные или их отрицания, соединённые «или». Переменным дают случайные значения. Сколько скобок в среднем истинно и что из этого следует?
3. Жадный алгоритм ставит вершину v; три её соседа уже стоят слева, один справа, ещё два не расставлены. Куда поставить v и сколько рёбер при этом наверняка попадёт в разрез?
4. n ключей кладут в n² ячеек, ожидаемое число коллизий меньше 1/2. Оцени вероятность того, что коллизий нет.
5. Почему из принципа Яо следует, что случайные пробы не ускорят поиск единственной единицы, но из него не следует то же самое для массива, наполовину состоящего из единиц?