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

В математике и информатике метод условных вероятностей ^{[1] [2]} представляет собой систематический метод преобразования неконструктивных вероятностных доказательств существования в эффективные детерминированные алгоритмы , которые явно конструируют желаемый объект. ^[3]

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

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

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

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

Обзор

Рагхаван ^[2] дает такое описание:

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

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

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

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

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

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

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

В этом примере случайный эксперимент состоит из подбрасывания трех честных монет. Эксперимент проиллюстрирован корневым деревом на соседней диаграмме. Существует восемь результатов, каждый из которых соответствует листу в дереве. Попытка случайного эксперимента соответствует случайному блужданию от корня (верхний узел в дереве, где не было подброшено ни одной монеты) к листу. Успешными результатами являются те, в которых по крайней мере две монеты выпали решкой. Внутренние узлы в дереве соответствуют частично определенным результатам, где только 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 ) задача максимального разреза состоит в том, чтобы раскрасить каждую вершину графа в один из двух цветов (скажем, черный или белый) так, чтобы максимизировать количество ребер, конечные точки которых имеют разные цвета. (Допустим, что такое ребро разрезано .)

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 |.) ЧТЭК

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

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

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

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

${\displaystyle |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 , где u минимизирует . ${\displaystyle \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.

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

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

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

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

${\displaystyle \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 ,

${\displaystyle \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 в оставшемся графе.

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

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

Ссылки

1. Спенсер, Джоэл Х. (1987), Десять лекций по вероятностному методу, SIAM, ISBN 978-0-89871-325-1
2. Raghavan, Prabhakar (1988), «Вероятностное построение детерминированных алгоритмов: аппроксимация программ упаковки целых чисел», Журнал компьютерных и системных наук , 37 (2): 130–143, doi : 10.1016/0022-0000(88)90003-7
3. Вероятностный метод — метод условных вероятностей, запись в блоге Нила Э. Янга, дата обращения 19/04/2012 и 14/09/2023.

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

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

• Alon, Noga ; Spencer, Joel (2008). Вероятностный метод. Wiley-Interscience Series in Discrete Mathematics and Optimization (Третье изд.). Hoboken, NJ: John Wiley and Sons. стр. 250 и далее. ISBN 978-0-470-17020-5. МР  2437651.(страницы, указанные во 2-м издании, ISBN 9780471653981 ) 

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

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

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

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