Вероятностный метод в математических доказательствах
Probabilistic method
Вероятностный метод в математике: неконструктивное доказательство существования объектов через анализ вероятностей. Применяется в комбинаторике и других областях.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Неконструктивный метод математических доказательств
Nonconstructive method for mathematical proofs
В математике вероятностный метод — это неконструктивный метод, преимущественно используемый в комбинаторике и разработанный Полом Эрдошем для доказательства существования математического объекта заданного типа. Он заключается в том, чтобы показать, что при случайном выборе объектов из заданного класса вероятность получения объекта требуемого типа строго больше нуля. Хотя в доказательстве используется вероятность, окончательный вывод является достоверным и не содержит никакой погрешности. В настоящее время этот метод применяется и в других областях математики, таких как теория чисел, линейная алгебра и вещественный анализ, а также в информатике (например, рандомизированное округление) и теории информации.
In mathematics, the probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error. This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis, as well as in computer science (e. g. randomized rounding), and information theory.
Введение
Если каждый объект в коллекции объектов не обладает определенным свойством, то вероятность того, что случайно выбранный из коллекции объект обладает этим свойством, равна нулю. Аналогично, демонстрация того, что вероятность (строго) меньше 1, может быть использована для доказательства существования объекта, не удовлетворяющего заданным свойствам. Другой способ применения вероятностного метода – вычисление математического ожидания некоторой случайной величины. Если удается показать, что случайная величина может принимать значение, меньшее математического ожидания, это доказывает, что она также может принимать некоторое значение, превышающее математическое ожидание. В качестве альтернативы, вероятностный метод можно использовать для гарантии существования желаемого элемента в пространстве элементарных событий, значение которого больше или равно вычисленному математическому ожиданию, поскольку отсутствие такого элемента подразумевало бы, что каждый элемент в пространстве элементарных событий меньше математического ожидания, что является противоречием. К распространенным инструментам, используемым в вероятностном методе, относятся неравенство Маркова, оценка Черноффа и локальная лемма Ловаша.
If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero. Similarly, showing that the probability is (strictly) less than 1 can be used to prove the existence of an object that does not satisfy the prescribed properties. Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value. Alternatively, the probabilistic method can also be used to guarantee the existence of a desired element in a sample space with a value that is greater than or equal to the calculated expected value, since the non existence of such element would imply every element in the sample space is less than the expected value, a contradiction. Common tools used in the probabilistic method include Markov's inequality, the Chernoff bound, and the Lovász local lemma.
Два примера из-за Эрдоша
Хотя ранее другие доказывали теоремы вероятностным методом (например, результат Сзеле 1943 года о существовании турниров, содержащих большое количество гамильтоновых циклов), многие из наиболее известных доказательств, использующих этот метод, принадлежат Эрдошу. Первый пример ниже описывает один из таких результатов 1947 года, который дает доказательство нижней оценки для числа Рэмси R(r, r).
Although others before him proved theorems via the probabilistic method (for example, Szele's 1943 result that there exist tournaments containing a large number of Hamiltonian cycles), many of the most well known proofs using this method are due to Erdős. The first example below describes one such result from 1947 that gives a proof of a lower bound for the Ramsey number R(r, r).