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

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

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

Введение

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

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

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

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

Два примера из-за Эрдёша

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

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

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

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

Для любого набора ${ displaystyle S_ {r}}$ из ${ displaystyle r}$ вершины нашего графа, определите переменную ${ displaystyle X (S_ {r})}$ быть $1$ если каждый край среди ${ displaystyle r}$ вершины одного цвета, а $0$ иначе. Обратите внимание, что количество монохромных ${ 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$ приходит, потому что есть два возможных цвета).

Это верно для любого из ${ Displaystyle С (п, г)}$ возможные подмножества, которые мы могли бы выбрать, т.е. ${ displaystyle i}$ колеблется от $1$ к ${ 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$ . Поскольку ожидаемое количество монохромных $р$ -подграфов строго меньше, чем $1$ , должно быть, что конкретная случайная раскраска удовлетворяет тому, что количество одноцветных $р$ -подграфов строго меньше, чем $1$ . Количество однотонных $р$ -подграфы в этой случайной раскраске - неотрицательное целое число, поэтому оно должно быть $0$ ( $0$ единственное неотрицательное целое число меньше, чем $1$ ). Отсюда следует, что если

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

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

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

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

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

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

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

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

Свойство 1.

г

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

п /2

циклы длиной менее

г

.

Доказательство. Позволять $Икс$ быть количеством циклов длины меньше, чем $г$ . Количество циклов длины $я$ в полном графике на $п$ вершины

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

и каждый из них присутствует в $г$ с вероятностью $п я$ . Следовательно Неравенство Маркова у нас есть

{ 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).}

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

п

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

1/2

.

Свойство 2.

г

не содержит независимый набор размера

{ Displaystyle lceil { tfrac {п} {2k}} rceil}

.

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

{ displaystyle Pr (Y geq y) leq {n select 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 np)} = o (1),}

когда

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

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

п

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

1/2

.

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

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

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

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

использованная литература

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

Сноски

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

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

[3] Каждый р-подграфы имеет ${ 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}}$ , должна быть хотя бы одна раскраска, что неплохо для любого подграфа.

[а]