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

Неконструктивный метод математических доказательств

В математике вероятностный метод — это неконструктивный метод, в основном используемый в комбинаторике и впервые предложенный Полом Эрдёшем для доказательства существования предписанного вида математического объекта. Он работает, показывая, что если случайным образом выбрать объекты из указанного класса, вероятность того , что результат будет предписанного вида, строго больше нуля. Хотя доказательство использует вероятность, окончательный вывод определяется наверняка , без какой-либо возможной ошибки.

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

Введение

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

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

Другой способ использования вероятностного метода — вычисление ожидаемого значения некоторой случайной величины . Если можно показать, что случайная величина может принимать значение меньше ожидаемого значения, это доказывает, что случайная величина может также принимать некоторое значение больше ожидаемого значения.

В качестве альтернативы вероятностный метод также может быть использован для гарантии существования желаемого элемента в пространстве выборки со значением, которое больше или равно рассчитанному ожидаемому значению, поскольку отсутствие такого элемента означало бы, что каждый элемент в пространстве выборки меньше ожидаемого значения, что является противоречием.

Распространенные инструменты, используемые в вероятностном методе, включают неравенство Маркова , границу Чернова и локальную лемму Ловаса .

Два примера, приведённые Эрдёшем

Хотя до него другие доказывали теоремы вероятностным методом (например, результат Селе 1943 года о том, что существуют турниры, содержащие большое количество гамильтоновых циклов ), многие из наиболее известных доказательств, использующих этот метод, принадлежат Эрдёшу. Первый пример ниже описывает один такой результат 1947 года, который дает доказательство нижней границы для числа Рамсея R ( r , r ) .

Первый пример

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

Для этого мы раскрашиваем граф случайным образом. Раскрашиваем каждое ребро независимо с вероятностью 1/2 быть красным и 1/2 быть синим. Мы вычисляем ожидаемое количество монохроматических подграфов на r вершинах следующим образом:

Для любого набора вершин из нашего графа, определите переменную как 1 , если каждое ребро среди вершин одного цвета, и 0 в противном случае. Обратите внимание, что количество монохроматических -подграфов является суммой по всем возможным подмножествам . Для любого отдельного набора ожидаемое значение является просто вероятностью того, что все ребра в имеют один и тот же цвет: ${\displaystyle S_{r}}$ ${\displaystyle r}$ ${\displaystyle X(S_{r})}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle X(S_{r})}$ ${\displaystyle S_{r}}$ ${\displaystyle S_{r}^{i}}$ ${\displaystyle X(S_{r}^{i})}$ ${\displaystyle C(r,2)}$ ${\displaystyle S_{r}^{i}}$

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

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

Это справедливо для любого из возможных подмножеств, которые мы могли бы выбрать, т.е. диапазонов от 1 до . Таким образом, мы имеем, что сумма по всем равна ${\displaystyle C(n,r)}$ ${\displaystyle i}$ ${\displaystyle C(n,r)}$ ${\displaystyle E[X(S_{r}^{i})]}$ ${\displaystyle S_{r}^{i}}$

${\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

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

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

Рассмотрим, что произойдет, если это значение меньше 1. Поскольку ожидаемое число монохроматических r -подграфов строго меньше 1 , существует раскраска, удовлетворяющая условию, что число монохроматических r -подграфов строго меньше 1. Число монохроматических r -подграфов в этой случайной раскраске является неотрицательным целым числом , следовательно, оно должно быть равно 0 ( 0 — единственное неотрицательное целое число, меньшее 1 ). Из этого следует, что если

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

(что справедливо, например, для n = 5 и r = 4 ), должна существовать раскраска, в которой нет одноцветных r -подграфов. ^[a]

По определению числа Рамсея это означает, что R ( r , r ) должно быть больше n . В частности, R ( r , r ) должно расти по крайней мере экспоненциально с r .

Слабость этого аргумента в том, что он совершенно неконструктивен . Хотя он доказывает (например), что почти каждая раскраска полного графа на (1.1) ^r вершинах не содержит монохроматического r -подграфа, он не дает явного примера такой раскраски. Проблема нахождения такой раскраски остается открытой уже более 50 лет.

---

1. Тот же факт можно доказать без вероятности, используя простой подсчетный аргумент:
   • Общее число r -подграфов равно . ${\displaystyle {n \choose r}}$
   • Каждый r -подграф имеет ребра и поэтому может быть раскрашен по- разному. ${\displaystyle {r \choose 2}}$ ${\displaystyle 2^{r \choose 2}}$
   • Из этих раскрасок только 2 являются «плохими» для данного подграфа (раскраски, в которых все вершины красные или все вершины синие).
   • Следовательно, общее число раскрасок, которые являются плохими для некоторого (хотя бы одного) подграфа, не превышает . ${\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}$
   • Следовательно, если , то должна быть хотя бы одна раскраска, которая не является «плохой» для любого подграфа. ${\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1}$

Второй пример

В статье Эрдёша 1959 года (см. ссылку, указанную ниже) рассматривалась следующая проблема теории графов : если заданы положительные целые числа g и k , существует ли граф G, содержащий только циклы длины не менее g , такой, что хроматическое число графа G не менее k ?

Можно показать, что такой граф существует для любых g и k , и доказательство достаточно простое. Пусть n очень велико и рассмотрим случайный граф G на n вершинах, где каждое ребро в G существует с вероятностью p = n ^{1/ g  −1} . Мы показываем, что с положительной вероятностью G удовлетворяет следующим двум свойствам:

Свойство 1. G содержит не более n /2 циклов длины меньше g .

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

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

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

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

Таким образом, при достаточно большом n свойство 1 выполняется с вероятностью более 1/2 .

Свойство 2. G не содержит независимого множества размера . ${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$

Доказательство. Пусть Y — размер наибольшего независимого множества в 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 \!.}$Таким образом, при достаточно большом n свойство 2 выполняется с вероятностью более 1/2 .

При достаточно большом n вероятность того, что граф из распределения обладает обоими свойствами, положительна, поскольку события для этих свойств не могут быть непересекающимися (если бы они были непересекающимися, их вероятности в сумме давали бы больше 1).

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

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

Смотрите также

• Математический портал

• Интерактивная система доказательств
• Алгоритм Лас-Вегаса
• Метод несжимаемости
• Метод условных вероятностей
• Вероятностные доказательства невероятностных теорем
• Случайный график

Дополнительные ресурсы

• Вероятностные методы в комбинаторике, MIT OpenCourseWare

Ссылки

• Алон, Нога; Спенсер, Джоэл Х. (2000). Вероятностный метод (2-е изд.). Нью-Йорк: Wiley-Interscience. ISBN  0-471-37046-0 .
• Эрдёш, П. (1959). «Теория графов и вероятность». Can. J. Math . 11 : 34–38. doi : 10.4153/CJM-1959-003-9 . MR  0102081. S2CID  122784453.
• Erdős, P. (1961). «Теория графов и вероятность, II». Can. J. Math . 13 : 346–352. CiteSeerX  10.1.1.210.6669 . doi :10.4153/CJM-1961-029-9. MR  0120168. S2CID  15134755.
• Я. Матушек , Я. Вондрак. Вероятностный метод. Конспекты лекций.
• Алон, Н. и Кривелевич, М. (2006). Экстремальная и вероятностная комбинаторика
• Элишаков И., Вероятностные методы в теории конструкций: случайная прочность материалов, случайная вибрация и выпучивание, World Scientific, Сингапур, ISBN 978-981-3149-84-7 , 2017 
• Элишакофф И., Линь Ю.К. и Чжу Л.П., Вероятностное и выпуклое моделирование акустически возбуждаемых структур, Elsevier Science Publishers, Амстердам, 1994, VIII + стр. 296; ISBN 0 444 81624 0 

Сноски