Метод условных вероятностей - Method of conditional probabilities

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

В метод условных вероятностей (Спенсер 1987 ), (Рагхаван 1988 ) превращает такое доказательство в "очень точном смысле" в эффективное детерминированный алгоритм, тот, который гарантированно вычислит объект с желаемыми свойствами. То есть метод дерандомизирует доказательство. Основная идея состоит в том, чтобы заменить каждый случайный выбор в случайном эксперименте детерминированным выбором, чтобы сохранить условную вероятность отказа, учитывая выбранные до сих пор варианты, ниже 1.

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

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

Обзор

(Рагхаван 1988 ) дает это описание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В этом примере демонстрируется метод условных вероятностей с использованием условного ожидания.

Лемма Max-Cut

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

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

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

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

Чтобы применить метод условных вероятностей, сначала смоделируйте случайный эксперимент как последовательность небольших случайных шагов. В этом случае естественно рассматривать каждый шаг как выбор цвета для конкретной вершины (так что |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. Для каждой вершины ты в V (в любом порядке): 2. Рассмотрим уже раскрашенные соседние вершины ты. 3. Среди этих вершин, если черных больше, чем белых, то цвет ты белый. 4. В противном случае цвет ты чернить.

Благодаря своему происхождению, этот детерминированный алгоритм гарантированно сокращает по крайней мере половину ребер данного графа. (Это делает его 0.5-аппроксимационный алгоритм для Max-cut.)

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

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

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

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

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

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

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

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

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

(Из приведенного выше неравенства следует, что 1 / (Икс+1) является выпуклый в Икс, поэтому левая часть минимизируется при условии, что сумма степеней зафиксирована на 2 |E|, когда каждый d(ты) = D = 2|E|/|V|.) QED

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

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

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

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

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

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

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

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

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

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

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

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

Ниже, N(т)(ты) обозначает соседей ты в р(т) (то есть соседи ты которые ни в S ни соседа в S).

1. Инициализировать S быть пустым множеством 2. Пока существует еще не рассмотренная вершина ты без соседа в S: 3. Добавьте такую ​​вершину ты к S куда ты сводит к минимуму .4. Возвращаться S.

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

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

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

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

куда N(т)(ты) обозначает соседей ты в оставшемся графе (то есть в р(т)).

Для первого алгоритма чистое увеличение неотрицательно, потому что по выбору ты,

,

куда d(ты) - степень ты в исходном графике.

Для второго алгоритма чистое увеличение неотрицательно, потому что по выбору ты,

,

куда d ′(ты) - степень ты в оставшемся графике.

Смотрите также

Рекомендации

  • Спенсер, Джоэл Х. (1987), Десять лекций по вероятностному методу, СИАМ, ISBN  978-0-89871-325-1

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

внешняя ссылка