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

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

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

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

История

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

Примеры

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

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

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

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

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

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

$\mu =2\cdot 2^{-{r \choose 2}}.$

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

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

$M={n \choose r}\cdot \mu ={n \choose r}\cdot 2\cdot 2^{-{r \choose 2}}$

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

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

То есть, если

$2\cdot {n \choose r}<2^{r \choose 2},$

то

$R(r,r)>n$

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

Замечания

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

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

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

Зафиксируем большое целое число $n$. Рассмотрим случайный граф $G$ с $n$ вершинами, где каждое ребро в $G$ существует с вероятностью p = n^1/g−1. Покажем, что следующие два свойства выполняются с положительной вероятностью

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

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

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

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

$\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}\cdot E[X]\leq {\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}}\leq {\frac {g}{n}}\cdot n^{\frac {g-1}{g}}=g\cdot n^{-{\frac {1}{g}}}=o(1).$ ■

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

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

$\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),$

когда

$y=\left\lceil {\frac {n}{2k}}\right\rceil .$ ■

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

Замечания

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

См. также

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

Литература

• Айгнер М. Циглер Г. Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней. — Издательство «Лаборатория знаний» (ранее «БИНОМ. Лаборатория знаний»), 2014. — ISBN 978-5-9963-2736-2.

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

• А. М. Райгородский. Графы с большим хроматическим числом и большим обхватом (рус.) // Матем. просв., сер. 3. — 2016. — Т. 20. — С. 228—237.

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

• Erdős, P. Graph theory and probability (неопр.) // Canad. J. Math.. — 1959. — Т. 11, № 0. — С. 34—38. — doi:10.4153/CJM-1959-003-9. Архивировано 18 июля 2011 года.

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

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