Русская Википедия:Вероятностный метод

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.

К распространённым инструментам, используемым в вероятностном методе, относятся неравенство Маркова, неравенство Чернова и локальная лемма Ловаса.

История

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

Примеры

Следующие два примера применения вероятностного метода обсуждаются в деталях в книге «Доказательства из Книги» Мартина Айгнера и Гюнтера Циглера.

Нижняя оценка на число Рамсея

Нам нужно доказать существование раскраски в два цвета (скажем, красный и синий) рёбер полного графа с <math>n</math> вершинами (при не очень больших значениях <math>n</math>) такой, что не существует полного  монохроматического подграфа с <math>r</math> вершинами (то есть, с каждым ребром одного цвета).

Выберем цвета случайным образом. Цвет каждого ребра выбираем независимо с равной вероятностью красный или синий. Рассчитаем ожидаемое число полных монохроматических подграфов с <math>r</math> вершинами следующим образом:

Для любого набора <math>S</math> из <math>r</math> вершин нашего графа, определим значение <math>X(S)</math> равное 1, если каждое ребро с концами в <math>S</math> одного цвета, и 0 в противном случае. Обратите внимание, что число монохроматических <math>r</math>-подграфов это сумма <math>X(S)</math> по всем <math>S</math>.

Для любого <math>S</math>, математическое ожидание <math>\mu</math> от <math>X(S)</math> это вероятность того, что все <math>{r \choose 2}</math> ребра в <math>S</math> имеют тот же цвет. И значит

<math>\mu=2 \cdot 2^{-{r \choose 2}}.</math>

Множитель 2 появляется, потому что есть два возможных цвета.

То же самое справедливо для любого из <math>{n \choose r}</math>  возможных подмножеств с <math>r</math> вершинами. Так, что математическое ожидание суммы <math>X(S)</math> по всем <math>S</math> равно

<math>M={n \choose r}\cdot \mu={n \choose r}\cdot2 \cdot 2^{-{r \choose 2}}</math>

Сумма математических ожиданий равна ожиданию суммы (независимо от того, являются ли переменные независимыми). Иначе говоря <math>M</math> есть среднее число монохроматических <math>r</math>-подграфов случайно покрашенном графе.

Число монохроматических <math>r</math>-подграфов в случайной раскраске всегда будет целое число. Поэтому если <math>M<1</math>, то по крайней мере в одной раскраске, не должно быть полных монохроматических <math>r</math>-подграфов.

То есть, если

<math>2\cdot {n \choose r}<2^Шаблон:R \choose 2,</math>

то

<math>R(r, r) > n</math>

где <math>R(r, r)</math> обозначает число Рамсея для <math>r</math>. В частности,  <math>R(r, r)</math> растёт по крайней мере экспоненциально по <math>r</math>.

Замечания

• Приведённое доказательство дано Эрдёшем.
• Этот метод не дает явный пример такой раскраски. Вопрос описания конкретного примера был открыт в течение более чем 50 лет.

Построение графа без коротких циклов с большим хроматическим числом

Пусть даны целые положительные числа <math>g</math> и <math>k</math>. Нам надо построить граф <math>G</math> со всеми циклами циклы длины не менее <math>g</math>, и при этом хроматическое число G как минимум на <math>k</math>.

Зафиксируем большое целое число <math>n</math>. Рассмотрим случайный граф <math>G</math> с <math>n</math> вершинами, где каждое ребро в <math>G</math> существует с вероятностью Шаблон:Math. Покажем, что следующие два свойства выполняются с положительной вероятностью

Свойство 1. <math>G</math> содержит не более чем <math>n/2</math> циклов длины меньше, чем <math>g</math>. Точнее, вероятность того, что граф <math>G</math> имеет не больше чем <math>n/2</math> циклов длины меньше, чем <math>g</math> стремится к 1 при <math>n\to\infty</math>.

Доказательство. Пусть <math>X</math> — число циклов длины меньше, чем <math>g</math>. Число циклов длины <math>i</math> в полном графе на <math>n</math> с вершинами равно

<math>\frac{n!}{2\cdot i \cdot (n-i)!} \le \frac{n^i}{2}</math>

и каждый из них содержится в <math>G</math> с вероятностью Шаблон:Math. Следовательно, по неравенству Маркова имеем

<math>\Pr \left (X> \tfrac{n}{2} \right )

\le\frac{2}{n}\cdot E[X] \le \frac{1}{n}\cdot \sum_{i=3}^{g-1} p^i\cdot n^i = \frac{1}{n}\cdot \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n}\cdot n^{\frac{g-1}{g}} = g\cdot n^{-\frac{1}{g}} = o(1).</math> Шаблон:Ч.т.д.

Свойство 2. <math>G</math> не содержит независимое множество размера <math>\lceil \tfrac{n}{2k} \rceil</math>. Точнее, вероятность того, что граф <math>G</math> имеет независимое множество размера <math>\lceil \tfrac{n}{2k} \rceil</math> стремится к 1 при <math>n\to\infty</math>.

Доказательство. Пусть <math>Y</math> обозначает размер наибольшего независимого множества в <math>G</math>. Очевидно, мы имеем

<math>\Pr (Y\ge y) \le {n \choose y}(1-p)^{\frac{y(y-1)}{2}} \le n^y e^{-\frac{py(y-1)}{2}} = e^{- \frac{y}{2} \cdot (py -2\ln n - p)} = o(1),</math>

когда

<math>y = \left \lceil \frac{n}{2k} \right \rceil.</math> Шаблон:Ч.т.д.

Поскольку <math>G</math> имеет эти два свойства, мы можем извлечь максимум <math>n/2</math> вершин из <math>G</math>, чтобы получить новый граф <math>G'</math> с <math>n'\geq n/2</math> вершинами, содержащий только циклы длины не более <math>g</math>. Мы видим, что <math>G'</math> имеет независимый набор размера <math>\lceil \frac{n'}{k} \rceil</math>. <math>G'</math> может только быть разделён по крайней мере на <math>k</math> независимых множеств, и, следовательно, имеет хроматическое число, по крайней мере <math>k</math>.

Замечания

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

См. также

• Случайный граф

Литература

• Шаблон:Книга

• Алон Н., Спенсер Дж. Вероятностный метод, Бином, 2007, с. 320, 1100 экз. ISBN 978-5-94774-556-6

• Шаблон:Статья

На английском

• Шаблон:Статья

• J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.

• Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics