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

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

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

История

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

То есть, если

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

то

${\displaystyle R(r,r)>n}$

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

Замечания

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

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

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

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

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

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

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

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

${\displaystyle \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. ${\displaystyle G}$ не содержит независимое множество размера ${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$ . Точнее, вероятность того, что граф ${\displaystyle G}$ имеет независимое множество размера ${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$ стремится к 1 при ${\displaystyle n\to \infty }$ .

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

${\displaystyle \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),}$

когда

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

Поскольку ${\displaystyle G}$ имеет эти два свойства, мы можем извлечь максимум ${\displaystyle n/2}$ вершин из ${\displaystyle G}$ , чтобы получить новый граф ${\displaystyle G'}$ с ${\displaystyle n'\geq n/2}$ вершинами, содержащий только циклы длины не более ${\displaystyle g}$ . Мы видим, что ${\displaystyle G'}$ имеет независимый набор размера ${\displaystyle \lceil {\frac {n'}{k}}\rceil }$ . ${\displaystyle G'}$ может только быть разделён по крайней мере на ${\displaystyle k}$ независимых множеств, и, следовательно, имеет хроматическое число, по крайней мере ${\displaystyle 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. (неопр.) // Canad. J. Math.. — 1959. — Т. 11 , № 0 . — С. 34—38 . — doi : . 18 июля 2011 года.

• J. Matoušek, J. Vondrak. . Lecture notes.

• Alon, N and Krivelevich, M (2006).

Footnotes

1. Erdös, P. Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53, (1947). 292–294.