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

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

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

Введение [ править ]

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

Аналогичным образом, показ того, что вероятность (строго) меньше 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 С (г, 2)}$ ${\ displaystyle S_ {r} ^ {i}}$

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

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

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

{\ displaystyle \ sum _ {i = 1} ^ {C (n, r)} E [X (S_ {r} ^ {i})] = {n \ select 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 \ select r} 2 ^ {1- {r \ choose 2}} <1}

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

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

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

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

Второй пример [ править ]

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

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

\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 '$ на вершинах, содержащий только циклы длины не менее $g$ . Мы видим, что этот новый граф не имеет независимого набора размеров . $G '$ может быть разбит не менее чем на $k$ независимых множеств и, следовательно, имеет хроматическое число не менее $k$ . $n'\geq n/2$ $\left\lceil {\frac {n'}{k}}\right\rceil$

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

См. Также [ править ]

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

Ссылки [ править ]

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

Сноски [ править ]

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

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

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

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

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

[6] Следовательно, если , должна быть хотя бы одна раскраска, которая не является «плохой» для любого подграфа. ${\ displaystyle 2 ^ {r \ choose 2}> 2 {n \ choose r}}$

[а]