Метод условных вероятностей

В математике для доказательства существования математических объектов с некоторыми комбинаторными свойствами используется вероятностный метод, в котором показывается, что случайный объект, выбранный из некоторой вероятностной выборки, имеет требуемое свойство с положительной вероятностью. Следовательно, эти доказательства существования неконструктивны — они не описывают явно метод построения или вычисления таких объектов.

Метод условных вероятностей преобразует такое доказательство во «вполне точном смысле» в эффективный детерминированный алгоритм, который гарантирует обнаружение объекта с желаемыми свойствами. То есть метод дерандомизирует доказательство. Основная идея — заменить каждый случайный выбор в случайном эксперименте детерминированным выбором таким образом, чтобы сохранить условное математическое ожидание неудачи, обусловленной выбором, меньшим 1.

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

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

Обзор

Рагхаван даёт такое описание метода:

Сначала мы показываем существование доказуемо хорошего приближённого решения, использующего вероятностный метод... [Мы затем] показываем, что доказательство вероятностного существования можно преобразовать, в очень точном смысле, в детерминированный аппроксимационный алгоритм.

(Рагхаван обсуждает метод в контексте вероятностного округления, но метод работает с вероятностным методом общего вида.)

Метод условных математических ожиданий

Чтобы применить метод к вероятностному доказательству, случайно выбранный объект в исходном доказательстве должен допускать выбор путём случайных экспериментов, состоящих из последовательности «малых» случайных выборов.

Имеется тривиальный пример для иллюстрации принципа.

Лемма: Можно открыть (скрытые) три монеты так, что число решек будет не меньше 2.

Вероятностное доказательство. Если три монеты бросать случайно, математическое ожидание числа решек равно 1,5. Таким образом, должно быть решение (способ открытия монет), так что число решёток будет не меньше 1,5. Поскольку число решек является целым числом, в таком решении имеется по меньшей мере 2 решки. Q.E.D.

В этом примере случайный эксперимент заключается в подбрасывании трёх симметричных монет. Эксперимент проиллюстрирован деревом на рисунке. Имеется восемь результатов, каждый соответствует листу в дереве. Испытание в случайном эксперименте соответствует выбору случайного перехода от корня (верхнего узла дерева, где монеты не открыты) до листа. Успешные решения — это те, в которых по меньшей мере две монеты выпали решками. Внутренние узлы дерева соответствуют частично определённым решениям, в которых открыты 0, 1, 2 и так далее монет.

Чтобы применить метод условных вероятностей, фокусируются на условной вероятности неудачи, задаваемой последовательным выбором, осуществляемым при переходе эксперимента от шага к шагу. На диаграмме каждый узел помечен этой условной вероятностью. (Например, если открыта только первая монета, и результат эксперимента — решка, это соответствует второму наследнику корня. Для этого промежуточного состояния вероятность неудачи равна 0,25.)

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

условное математическое ожидание неуспеха, определяемое текущим состоянием, меньше 1.

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

Условие инвариантности первоначально (в корне) выполняется, поскольку исходное доказательство показывает, что (безусловная) вероятность неудачи меньше 1. Условная вероятность в любом внутреннем узле является средним арифметическим условных вероятностей наследников узла. Это свойство важно, поскольку из него следует, что любой внутренний узел с условной вероятностью, меньшей 1, имеет по меньшей мере одного наследника, условная вероятность которого меньше 1. Таким образом, в любом внутреннем узле можно всегда выбрать некоторого наследника, чтобы при переходе к нему условие инвариантности сохранялось. Поскольку условие инвариантности сохраняется до самого конца, когда эксперимент достигает листа и все выборы определены, решение, полученное таким способом, должно быть успешным.

Эффективность

В типичном приложении метода целью является возможность реализовать итоговый детерминированный процесс с помощью достаточно эффективного алгоритма (слово «эффективный» обычно означает алгоритм, время работы которого зависит полиномиально от размера входа), даже если число возможных решений огромно (растёт экспоненциально). Например, рассмотрим задачу с открыванием монет при больших n.

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

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

• Использование условного математического ожидания: Многие вероятностные доказательства работают следующим образом: в них явно определяется случайная переменная Q, показывается, что (i) математическое ожидание Q не превосходит (или не меньше) некоторого порогового значения, и что (ii) в любом решении, где Q не превосходит (не меньше) порового значения, решение успешно. Тогда из (i) следует, что существует решение, в котором Q не превышает порога, а из этого и (ii) следует, что существует успешное решение. (В примере выше Q равно числу решек, и это значение должно быть не меньше порога 1,5. Во многих приложениях Q является числом «плохих» событий (не обязательно независимых), случающихся в данном решении, где каждое плохое событие соответствует одному пути, по которому эксперимент может быть неуспешным, а математическое ожидание числа плохих событий меньше 1.)

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

• Использование пессимистического оценщика: В некоторых случаях вместо точного условного математического ожидания значения Q можно использовать достаточно близкую границу, называемую пессимистичным оценщиком. Пессимистический оценщик — это функция текущего состояния. Оценщик должен быть верхней (или нижней) границей условного математического ожидания Q заданного текущего состояния, и он должен иметь невозрастающее (или неубывающее) математическое ожидание на каждом случайном шаге эксперимента. Как правило, хороший пессимистический оценщик может быть получен путём аккуратной разборки логики исходного доказательства.

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

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

Лемма о максимальном разрезе

Если задан любой неориентированный граф G = (V, E), задача о максимальном разрезе заключается в раскраске каждой вершины графа в один из двух цветов (скажем, чёрного и белого) так, чтобы максимизировать число рёбер, конечные вершины которых имеют разные цвета. (Будем говорить о таких рёбрах как о разрезе.)

Лемма о максимальном разрезе (Max-Cut): В любом графе G = (V, E) по меньшей мере |E|/2 рёбер можно вырезать.

Вероятностное доказательство. Выкрашиваем каждую вершину в чёрный или белый цвет согласно бросаниям симметричной монеты. Для любого ребра e из E вероятность, что ребро выбирается для разреза, равна 1/2. Тогда, согласно линейности математического ожидания, математическое ожидание числа рёбер разреза равно |E|/2. Таким образом, существует раскраска, которая вырезает по меньшей мере |E|/2 рёбер. Q.E.D.

Метод условных вероятностей с условными математическими ожиданиями

Чтобы применить метод условных вероятностей, сначала моделируют случайный эксперимент как цепь малых случайных шагов. В этом случае естественно рассматривать каждый шаг как выбор цвета конкретной вершины (так что имеется |V| шагов).

Затем случайный выбор на каждом шаге заменяется детерминированным выбором, сохраняющим условную вероятность неудачи, определяемой раскраской вершин, меньшей 1. (Здесь неудача означает, что разрез состоит из менее чем |E|/2 рёбер.)

В этом случае условную вероятность неудачи вычислить непросто. В действительности, исходное доказательство не вычисляет вероятность неудачи явно. Вместо этого доказательство показывает, что математическое ожидание числа рёбер разреза не меньше |E|/2.

Пусть случайная переменная Q равна числу рёбер разреза. Чтобы сохранить условную вероятность неудачи меньше 1, достаточно сохранять условное математическое ожидание Q на уровне или выше порога |E|/2. (Пока условное математическое ожидание Q не меньше |E|/2, должно существовать достижимое решение, в котором Q не менее |E|/2, так что условная вероятность достижения такого решения положительна.) Чтобы сохранять условное математическое ожидание Q на уровне |E|/2 или выше, алгоритм на каждом шаге будет раскрашивать вершину так, чтобы максимизировать результирующее условное математическое ожидание величины Q. Этого достаточно, поскольку должен существовать наследник узла, условное математическое ожидание которого не меньше условного математического ожидания текущего состояния (а потому не меньше |E|/2).

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

числу рёбер, конечные вершины которых выкрашены в разные цвета

+ (1/2)*(число рёбер с по меньшей мере одной невыкрашенной вершиной).

Алгоритм

Алгоритм раскрашивает каждую вершину с целью максимизировать результирующее значение условного математического ожидания. Это гарантирует сохранение условного математического ожидания на уровне |E|/2 или выше, и это гарантирует сохранение условного математического ожидания неуспеха меньше 1, что, в свою очередь, гарантирует успешный результат. Алгоритм можно упростить до следующего:

 1. Для каждой вершины u из V (в любом порядке):
 2.   Рассмотрим уже раскрашенные соседние u вершины.
 3.       Если среди этих вершин больше чёрных, выкрашиваем u в белый цвет.
 4.   В противном случае выкрашиваем u в чёрный цвет.

Согласно построению этот детерминированный алгоритм гарантирует отсечение по меньшей мере половины рёбер заданного графа. (Это делает алгоритм 0.5-аппроксимиционным алгоритмом для Max-cut.)

Пример использования пессимистические оценки

Следующий пример демонстрирует использование пессимистических оценок.

Теорема Турана

Одна из формулировок теоремы Турана следующая:

Любой граф G = (V, E) содержит независимое множество размера, не меньшего |V|/(D+1), где D = 2|E|/|V|— средняя степень графа.

Вероятностное доказательство теоремы Турана

Рассмотрим следующий случайный процесс для построения независимого множества S:

 1. Устанавливаем множество S пустым.
 2. Для каждой вершины u из V в случайном порядке:
 3.    Если ни один из соседей вершины u не содержится в S, добавляем u в S
 4. Возвращаем S.

Ясно, что процесс даёт независимое множество. Любая вершина u, которая была рассмотрена до всех её соседей, будет добавлена в S. Таким образом, если d(u) означает степень u, вероятность, что u добавляется в S, будет не меньше 1/(d(u)+1). Согласно линейности математического ожидания, ожидаемый размер S не меньше

$\sum _{u\in V}{\frac {1}{d(u)+1}}~\geq ~{\frac {|V|}{D+1}}.$

(Неравенство выше следует из того, что функция 1/(x+1) выпукла по x, так что при минимизации левой части выражения под знаком суммы дают значения 2|E|, если каждое d(u) = D = 2|E|/|V|.) Q.E.D.

Метод условных вероятностей, использующий пессимистические оценки

В этом случае случайный процесс имеет |V| шагов. Каждый шаг рассматривает некоторую ещё нерассмотренную вершину u и добавляет её в S, если ни одна из соседних вершин ещё не добавлена. Пусть случайная переменная Q равна числу вершин, добавленных в S. Доказательство показывает, что E[Q] ≥ |V|/(D+1).

Мы заменим каждый случайный шаг детерминированным шагом, который сохраняет условное математическое ожидание величины Q выше |V|/(D+1). Это обеспечит успешный результат, то есть результат, в котором независимое множество S имеет размер, не меньший |V|/(D+1), что соответствует границе в теореме Турана.

Если первый шаг выполнен, пусть S^(t) означает вершины, добавленные до этого. Пусть R^(t) означает нерассмотренные вершины, не имеющие соседей в S^(t). После выполнения первого шага последующие рассуждения в исходном доказательстве, что любая вершина w из R^(t), имеющая условную вероятность, не меньшую 1/(d(w)+1), добавляется в S, означают, что условное математическое ожидание величины Q не меньше

$|S^{(t)}|~+~\sum _{w\in R^{(t)}}{\frac {1}{d(w)+1}}.$

Пусть Q^(t) означает вышеупомянутое математическое ожидание, которое называется пессимистическим оценщиком для условного математического ожидания.

Доказательство показывает, что пессимистический оценщик первоначально не меньше величины |V|/(D+1). (То есть, Q⁽⁰⁾ ≥ |V|/(D+1).) Алгоритм делает каждый выбор, избегая уменьшения пессимистического оценщика, то есть, так что Q^(t+1) ≥ Q^(t) для каждого t. Поскольку пессимистический оценщик является нижней границей условного математического ожидания, это обеспечит, что условное математическое ожидание будет всегда выше |V|/(D+1), что, в свою очередь, обеспечит, что условное математическое ожидание неудачи находится ниже 1.

Пусть u — вершина, рассматриваемая алгоритмом на шаге (t+1).

Если u уже имеет соседа в множестве S, то u не добавляется в S и (после проверки Q^(t)), пессимистический оценщик остаётся неизменным. Если u не имеет соседей в множестве S, то u добавляется в S.

Если u выбирается случайно из оставшихся вершин, ожидаемый рост пессимистического оценщика неотрицателен. [Вычисление. Обусловленная выбором вершины из R^(t) вероятность, что данный член 1/(d(w)+1) выпадает из суммы пессимистичного оценщика, не превосходит (d(w)+1)/|R^(t)|, так что ожидаемое уменьшение каждого члена в сумме не превосходит 1/|R^(t)|. В сумме имеется R^(t) членов. Таким образом, ожидаемое уменьшение суммы не превосходит 1. Между тем размер S увеличивается на 1.]

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

Алгоритм максимизации пессимистической оценки

Алгоритм, приведённый ниже, выбирает каждую вершину u с целью максимизировать результирующий пессимистический оценщик. Согласно вышеприведённым рассуждениям это предотвращает пессимистический оценщик от убывания и гарантирует успешный выход.

Ниже N^(t)(u) означает соседей вершины u в R^(t) (то есть соседей вершины u, которые не входят в S и не имеют соседей в S).

1. Устанавливаем S пустым.
2. Пока есть нерассмотренная вершина u, не имеющая соседей в S:
3.    Добавляем вершину u в S, которая минимизирует $\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}$.
4. Возвращаем S.

Алгоритмы, не максимизирующие пессимистическую оценку

Чтобы метод условных вероятностей работал, достаточно, чтобы алгоритм не уменьшал пессимистическую оценку (или не увеличивал, по ситуации). Алгоритм не обязательно максимизирует (или минимизирует) пессимистическую оценку. Это даёт некоторую свободу в разработке алгоритме.

1. Устанавливаем S пустым.
2. Пока существует вершина u в графе без соседей в S:
3. Добавляем такую вершину u в S, если u минимизирует d(u) (начальную степень вершины u).
4. Возвращаем S.

1. Устанавливаем S пустым.
2. Пока оставшийся граф не пуст:
3.    Добавляем вершину u в S, если u имеет минимальную степень в оставшемся графе.
4.    Удаляем u и всех соседей вершины в графе.
5. Возвращаем S.

Каждый алгоритм анализируется с тем же пессимистическим оценщиком, что и ранее. На каждом шаге алгоритма суммарное увеличение пессимистического оценщика равно

$1-\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}},$

где N^(t)(u) означает соседей вершины u в оставшемся графе (то есть в R^(t)).

В первом алгоритме увеличение неотрицательно ввиду выбора u,

$\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d(u)+1){\frac {1}{d(u)+1}}=1$,

где d(u) — степень вершины u в исходном графе.

Во втором алгоритме увеличение неотрицательно ввиду выбора u,

$\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d'(u)+1){\frac {1}{d'(u)+1}}=1$,

где d′(u) — степень вершин u в оставшемся графе.

См. также

• Вероятностный метод
• Дерандомизация

Литература для дальнейшего чтения

• Noga Alon, Joel Spencer. The probabilistic method. — Third. — Hoboken, NJ: John Wiley and Sons, 2008. — С. 250 et seq. (in 2nd edition, ISBN 9780471653981). — (Wiley-Interscience Series in Discrete Mathematics and Optimization). — ISBN 978-0-470-17020-5.

• Rajeev Motwani, Prabhakar Raghavan. Randomized algorithms. — Cambridge University Press. — С. 120-. — ISBN 978-0-521-47465-8.
• Vijay Vazirani. Approximation algorithms. — Springer Verlag. — С. 130-. — ISBN 978-3-540-65367-7.

Ссылки

• The probabilistic method — method of conditional probabilities, blog entry by Neal E. Young, accessed 19/04/2012.