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

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

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

Введение

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

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

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

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

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

Два примера из рук Эрдеша

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

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

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

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

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

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

(коэффициент $2$ возникает потому, что существует два возможных цвета).

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

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

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

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

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

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

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

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

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

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

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

Свойство 1.

G

содержит не более

n /2

циклов длины меньше

g

.

Доказательство. Пусть $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}}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

не содержит независимого множества размера

\lceil {\tfrac {n}{2k}}\rceil

.

Доказательство. Пусть $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 \!.

Таким образом, при достаточно больших

n

свойство 2 выполняется с вероятностью более

1/2

.

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

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

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

См. также

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

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

Ссылки

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

Сноски

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

[2] Общее количество r -подграфов равно ${n \choose r}$ .

[3] Каждый r -подграф имеет ${r \choose 2}$ края и, таким образом, могут быть окрашены в $2^{r \choose 2}$ разные способы.

[4] Из этих раскрасок только две являются «плохими» для данного подграфа (раскраски, в которых все вершины красные или все вершины синие).

[5] Следовательно, общее количество плохих для некоторого (хотя бы одного) подграфа раскрасок не превосходит $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .

[6] Следовательно, если $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$ , должна быть хотя бы одна раскраска, не являющаяся «плохой» для любого подграфа.

[а]