Вероятностный метод

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

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

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

История

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

Примеры

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

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

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

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

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

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

$\mu =2\cdot 2^{-(\genfrac{}{}{0ex}{}{r}{2})}.$

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

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

$M=(\genfrac{}{}{0ex}{}{n}{r})\cdot \mu =(\genfrac{}{}{0ex}{}{n}{r})\cdot 2\cdot 2^{-(\genfrac{}{}{0ex}{}{r}{2})}$

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

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

То есть, если

$2\cdot (\genfrac{}{}{0ex}{}{n}{r})<2^{(\genfrac{}{}{0ex}{}{r}{2})},$

то

$R(r,r)>n$

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

Замечания

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

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

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

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

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

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

$\frac{n!}{2\cdot i\cdot (n-i)!}\le \frac{n^i}{2}$

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

$\mathrm{Pr}(X>\frac{n}{2})\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).$ Шаблон:Ч.т.д.

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

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

$\mathrm{Pr}(Y\ge y)\le (\genfrac{}{}{0ex}{}{n}{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),$

когда

$y=\lceil \frac{n}{2k}\rceil .$ Шаблон:Ч.т.д.

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

Замечания

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

См. также

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

Литература

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

• Алон Н., Спенсер Дж. Вероятностный метод, Бином, 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