Локальная лемма Ловаса - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:06:17Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:30, 1 сентября 2022

2022-09-01T06:30:16Z

176.59.5.114: full article

2020-04-05T20:32:16Z

full article

176.59.5.114: /* Локальная лемма Ловаса */

2020-04-05T20:31:29Z

‎Локальная лемма Ловаса

176.59.5.114: Новая статья

2020-04-05T20:31:13Z

Новая статья

Новая страница

== Локальная лемма Ловаса ==

Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.

{{Теорема
|id=thLovas
|about=Локальная лемма Ловаса
|statement='''Пояснение:''' Пусть имеется семейство событий <tex>A_1, A_2, ... , A_n</tex>, и для каждого события <tex>A_i</tex> выделено множество индексов <tex>M(i) \subset \{ 1, 2, . . . , n \}</tex> такое, что <tex>A_i</tex> не зависит от всех событий <tex>A_j
, j \notin M(i)</tex>. Это означает, что для любого события <tex>B</tex>, выражаемого через множество событий <tex>\{ A_j, j \notin M(i) \}</tex>, события <tex>A_i</tex> и <tex>B</tex> независимы. Через <tex>\bar{A}</tex> будем обозначать дополнение события <tex>A</tex>. 
'''Формулировка теоремы:''' 
Предположим, что нашлись такие числа <tex>x_i \in (0, 1)</tex>, что для всех <tex>i</tex> выполняется неравенство <tex>P(A_i) \leq x_i\prod_{j \in M(i)}(1-x_j)</tex>. Тогда <tex>P(\bigcap \bar{A_i}) \geq \prod(1-x_i)</tex>, что значит, что с положительной вероятностью ни одного из событий <tex>A_i</tex> не происходит.
|proof= Докажем более сильное утверждение: если <tex>I = I_1 \sqcup I_2</tex>, где $I_1, I_2$ - множества
индексов, то
 <tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) \cdot \prod\limits_{j \in I_1}(1-x_j)
\end{equation}
</tex> 
Для пустого $I_2$ получаем требуемое. Докажем индукцией по <tex>|I|</tex>. Если <tex>|I| = 1</tex>, то при <tex>I_2 = I, I_1 = \emptyset</tex> имеет место равенство, а при <tex>I_1 = I, I_2 = \emptyset</tex> имеем <tex>P(\bar{A_i}) = 1 - P(A_i) \geq 1 - x_i</tex>. Теперь предположим, что для всех множеств индексов мощности меньше <tex>|I|</tex> и любых их подразбиений на два подмножества неравенство имеет место. Докажем его для $I$. Рассмотрим сначала случай <tex>|I_1| = 1, I_1 = \{ k \}</tex>. Обозначим <tex>P(\bigcap_{i \in I_2} \bar{A_i}) = p_0</tex>. Имеем
 <tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) = p_0 - P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \cap A_k \right) \geq p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \cap A_k \right) =
\end{equation}
</tex> 
<tex>
\begin{equation}
p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k) \geq p_0(1-x_k)
\end{equation}
</tex>. 
Чтобы проверить выполнение последнего неравенства, перепишем его в равносильном виде
 <tex>
\begin{equation}
p_0x_k \geq P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k)
\end{equation}
</tex>. 
Это неравенство следует из оценки <tex>P(A_k) \leq x_k \prod_{j \in M(k)}(1-x_j)</tex> и индукционного предположения. 
Пусть теперь <tex>I_1 = \{ k \} \sqcup I_3, |I_3| > 0</tex>. Имеем
 <tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2 \cup I_3} \bar{A_i} \right) (1 - x_k) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) (1 - x_k) \prod\limits_{j \in I_3} (1-x_j),
\end{equation}
</tex> 
что и требовалось ''(здесь первое неравенство уже доказано, а второе следует из индукционного предположения)''.
}}

'''Замечание.''' Как видно из доказательства, вместо независимости каждого события $A_i$ от событий, не входящих в $M(i)$ достаточно требовать для любого множества $I$ такого, что <tex>I \cap (M(i) \cup \{ i \} ) = \emptyset</tex> оценки
 <tex>
\begin{equation}
P \left( A_i | \bigcap\limits_{j \in I} \bar{A_j} \right) \leq x_i \prod \limits_{j \in M(i)} (1-x_j).
\end{equation}
</tex> 
Иногда используется именно такая версия локальной леммы. 
В случае, когда оценки на вероятности всех событий совпадают, из леммы можно получить следующее утверждение:

{{Теорема
|id=thLocalLovas
|about=Симметричная версия локальной леммы
|statement=Предположим, что <tex>e \cdot p \cdot (d + 1) \leq 1,</tex> каждое событие $A_i$ происходит с вероятностью не больше, чем $p$ и <tex>|M(i)| \leq d</tex> для всех $i$. Тогда с положительной вероятностью ни одного события $A_i$ не происходит.
|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>, так что выполняются условия локальной леммы.
}}

← Предыдущая		Версия 06:30, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.		Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.

← Предыдущая		Версия 20:32, 5 апреля 2020
Строка 57:		Строка 57:
	\|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>, так что выполняются условия локальной леммы.		\|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=Пусть $G$ - граф, степени всех вершин которого не больше $d$, $P_i$ - непересекающиеся подмножества множества вершин графа $G$ такие, что <tex>\|P_i\| > 2e \cdot d</tex>. Тогда можно выбрать в каждом $P_i$ по вершине так, что никакие две соединенные ребром вершины не будут выбраны.
		+	}}
		+
		+	'''Решение:'''<br>
		+	Уменьшим при необходимости некоторые $P_i$ так, чтобы для всех $i$ выполнялось <tex>\|P_i\| = k</tex>, где <tex>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$ и такие $A_{(u, v)}$ мы далее не рассматриваем. Для ребра $(u, v)$, для которого, скажем <tex>u \in P_1, v \in P_2</tex>, рассмотрим все ребра, выходящие из вершин множеств $P_1$ и $P_2$. Таких ребер, не считая ребра $(u, v)$, будет не более,
		+	чем $2kd - 2$. Заметим, что событие $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=upytqnd6iqs Лекция А.М.Райгородского в ШАД]
		+	[[Категория: Дискретная математика и алгоритмы]]
		+	[[Категория: Теория вероятности]]

← Предыдущая		Версия 20:31, 5 апреля 2020
Строка 1:		Строка 1:
−	~~== Локальная лемма Ловаса ==~~
−
	Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.		Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.

← Предыдущая		Версия 16:06, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.		Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.