50
правок
Изменения
Добавлены задачи и источники
== Локальная лемма Ловаса ==
Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой) '' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
{{Теорема
\end{equation}
</tex><br>
что и требовалось ''(здесь первое неравенство уже доказано, а второе следует из индукционного предположения)''.
}}
|proof=Выберем <tex>x_i = x = 1 / (d + 1)</tex>. Тогда <tex>(1 − x)^d \geq 1 / e</tex> - это следует, например, из определения числа $e$. Следовательно <tex>p \leq x(1 − x)^d</tex>, так что выполняются условия локальной леммы.
}}
==Применение локальной леммы==
{{Задача
|definition=пукпук
}}
'''Доказательство:'''<br>
пукпук
==Применение симметричной версии локальной леммы==
{{Задача
|definition=Пусть $G$ - граф, степени всех вершин которого не больше $d$, $P_i$ - непересекающиеся подмножества множества вершин графа $G$ такие, что <tex>|P_i| > 2e \cdot d</tex>. Тогда можно выбрать в каждом $P_i$ по вершине так, что никакие две соединенные ребром вершины не выбраны.
}}
'''Доказательство:'''<br>
Уменьшим при необходимости некоторые $P_i$ так, чтобы для всякого $i$ было <tex>|P_i| = k := [2ed] + 1</tex>. Будем выбирать вершины <tex>x_i \in P_i</tex> случайно и независимо. Каждому ребру <tex>(u,v)</tex> графа $G$ сопоставим событие $A_{(u, v)}$: оба конца $u$, $v$ этого ребра выбраны. Очевидно, что вероятность каждого такого события не больше, чем $1/k^2$. В случае, если концы ребра принадлежат одному и тому же $P_i$ или один из них не принадлежит ни одному $P_i$, вероятность равна
$0$ и такие события мы далее не рассматриваем. Для ребра $(u, v)$, для которого, скажем <tex>u \in P_1, v \in P_2</tex>, рассмотрим все ребра, выходящие из вершин множеств $P_1$ и $P_2$. Всего будет не более,
чем $2kd - 2$ таких ребер ''(не считая ребра $(u, v)$)''. Заметим, что событие $A_{(u, v)}$ не зависит от всех других событий типа <tex>A_{(u', v')}</tex>, где <tex>(u', v')</tex> - ребро, соединяющее вершины множеств, отличных от $P_1$ и $P_2$.<br> Таким образом, для применения симметричной версии локальной леммы достаточно проверить, что <tex>e(2kd − 1) / k^2 < 1</tex>, что имеет место.
== Источники информации ==
*[http://club.pdmi.ras.ru/oldsite/courses/07f_probmet/probmet3.pdf Конспект лекций Ф.В. Петрова {{---}} Локальная лемма Ласло Ловаса]
*[https://www.youtube.com/watch?v=Jht6zBVBS-w Лекция А.М.Райгородского в ШАД]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
