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

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

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

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

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

Источник: Википедия