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

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

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

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

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

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

Обзор

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

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

Рагхаван обсуждает этот метод в контексте рандомизированного округления , но в целом он работает с вероятностным методом.

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

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

Вот тривиальный пример, иллюстрирующий этот принцип.

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

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

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

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

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

условная вероятность отказа при текущем состоянии меньше 1.

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

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

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

В типичном применении метода цель состоит в том, чтобы иметь возможность реализовать результирующий детерминированный процесс с помощью достаточно эффективного алгоритма (слово «эффективный» обычно означает алгоритм, который работает за полиномиальное время ), хотя обычно число возможных результатов огромен (экспоненциально велик). Например, рассмотрим задачу с подбрасыванием монеты, но расширенную до n подбрасываний для больших 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. Таким образом, в силу линейности ожидания ожидаемое количество разрезанных ребер равно | Е |/2. Таким образом, существует раскраска, разрезающая по крайней мере | E |/2 ребра. КЭД

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

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

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

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

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

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

количество ребер, конечные точки которых пока окрашены по-разному

+ (1/2)*( количество ребер, у которых хотя бы одна конечная точка еще не окрашена ).

Алгоритм

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

 1. For each vertex u in V (in any order):
 2.     Consider the already-colored neighboring vertices of u.
 3.         Among these vertices, if more are black than white, then color u white.
 4.     Otherwise, color u black.

Благодаря своему происхождению этот детерминированный алгоритм гарантированно обрежет не менее половины ребер данного графа. Это делает его алгоритмом приближения 0,5 для Max-cut .

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

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

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

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

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

Турана

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

 1. Initialize S to be the empty set.
 2. For each vertex u in V in random order:
 3.     If no neighbors of u are in S, add u to S
 4. Return 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| Е |/| V |.) КЭД

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

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

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

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

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

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

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

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

Если у u уже есть сосед в S , то u не добавляется к S и (путем проверки Q ^{( т )} ), пессимистическая оценка не меняется. Если u нет у соседа в S , то добавляется в S. u

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

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

оценки

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

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

1. Initialize S to be the empty set.
2. While there exists a not-yet-considered vertex u with no neighbor in S:
3.     Add such a vertex u to S where u minimizes $\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}$.
4. Return S.

которые не максимизируют

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

1. Initialize S to be the empty set.
2. While there exists a vertex u in the graph with no neighbor in S:
3.     Add such a vertex u to S, where u minimizes d(u) (the initial degree of u).
4. Return S.

1. Initialize S to be the empty set.
2. While the remaining graph is not empty:
3.     Add a vertex u to S, where u has minimum degree in the remaining graph.
4.     Delete u and all of its neighbors from the graph.
5. Return S.

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

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

где Н ^{( т )} ( u ) обозначает соседей u в оставшемся графе (то есть в R ^{( т )} ).

Для первого алгоритма чистое увеличение неотрицательно, поскольку по выбору 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 в оставшемся графе.

См. также

• Вероятностный метод
• Дерандомизация
• Рандомизированное округление

Дальнейшее чтение

Метод условного округления поясняется в нескольких учебниках:

• Алон, Нога ; Спенсер, Джоэл (2008). Вероятностный метод . Серия Wiley-Interscience по дискретной математике и оптимизации (Третье изд.). Хобокен, Нью-Джерси: Джон Уайли и сыновья. стр. 250 и след. ISBN  978-0-470-17020-5 . МР   2437651 . (цитируются страницы во 2-м издании, ISBN   9780471653981 )

• Мотвани, Раджив ; Рагхаван, Прабхакар (25 августа 1995 г.). Рандомизированные алгоритмы . Издательство Кембриджского университета . стр. 120–. ISBN  978-0-521-47465-8 .

• Вазирани, Виджай (5 декабря 2002 г.), Алгоритмы аппроксимации , Springer Verlag , стр. 130–, ISBN  978-3-540-65367-7

Внешние ссылки

• Вероятностный метод — метод условных вероятностей , запись в блоге Нила Э. Янга, по состоянию на 19.04.2012.