| dbo:abstract
|
- In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects. The method of conditional probabilities, converts such a proof, in a "very precise sense", into an efficient deterministic algorithm, one that is guaranteed to compute an object with the desired properties. That is, the method derandomizes the proof. The basic idea is to replace each random choice in a random experiment by a deterministic choice, so as to keep the conditional probability of failure, given the choices so far, below 1. The method is particularly relevant in the context of randomized rounding (which uses the probabilistic method to design approximation algorithms). When applying the method of conditional probabilities, the technical term pessimistic estimator refers to a quantity used in place of the true conditional probability (or conditional expectation) underlying the proof. (en)
- В математике для доказательства существования математических объектов с некоторыми комбинаторными свойствами используется вероятностный метод, в котором показывается, что случайный объект, выбранный из некоторой вероятностной выборки, имеет требуемое свойство с положительной вероятностью. Следовательно, эти доказательства существования неконструктивны — они не описывают явно метод построения или вычисления таких объектов. Метод условных вероятностей преобразует такое доказательство во «вполне точном смысле» в эффективный детерминированный алгоритм, который гарантирует обнаружение объекта с желаемыми свойствами. То есть метод дерандомизирует доказательство. Основная идея — заменить каждый случайный выбор в случайном эксперименте детерминированным выбором таким образом, чтобы сохранить условное математическое ожидание неудачи, обусловленной выбором, меньшим 1. Метод частично уместен в контексте вероятностного округления (которое использует вероятностный метод для разработки аппроксимационных алгоритмов). Когда применяется метод условных вероятностей, технический термин пессимистический оценщик относится к величинам, использованным вместо условной вероятности (или условного математического ожидания) исходного доказательства. (ru)
|
| rdfs:comment
|
- In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects. (en)
- В математике для доказательства существования математических объектов с некоторыми комбинаторными свойствами используется вероятностный метод, в котором показывается, что случайный объект, выбранный из некоторой вероятностной выборки, имеет требуемое свойство с положительной вероятностью. Следовательно, эти доказательства существования неконструктивны — они не описывают явно метод построения или вычисления таких объектов. Метод частично уместен в контексте вероятностного округления (которое использует вероятностный метод для разработки аппроксимационных алгоритмов). (ru)
|
