Лемма Ловаса: формулировка

• Мотивировочный пример: последовательность символов, на каждой границе $1\%$ пар комбинаций запрещён, доказать существование последовательности
• Решение: индукцией строим начало, которое блокирует не более $10\%$ вариантов следующей буквы. (Фубини: блокирующих более $10\%$ не более $10\%$, если произведение меньше $1\%$.)
• Формулировка леммы Ловаса: события $A_1,\ldots,A_n$, граф соседства (не обязательно симметричный; $N(i)$ --- соседи $i$), независимость со всеми не-соседями сразу, для некоторых положительных чисел $\varepsilon_i<1$ выполнено $$\Pr[A_i]\le \varepsilon_i \prod_{j\ne i, j\in N(i)} (1-\varepsilon_j).$$ Тогда $$\Pr[\lnot A_1 \land \ldots\land \lnot A_n]\ge \prod_i (1-\varepsilon_i)>0.$$
• Частный случай независимых событий, сравнение с union bound
• Применение к задаче о запрещённых парах соседей в последовательности: $\Pr[A_i]<\varepsilon(1-\varepsilon)^2$. Наилучшая оценка: $\varepsilon=1/3$, получается $4/27$

Доказательство леммы Ловаса

• По индукции надо доказывать два семейства неравенств: $$ \Pr[A_i | \lnot A_j \land \lnot A_k \land...]\le \varepsilon_i.$$ $$\Pr[\lnot A_i \land \lnot A_j\land\ldots| \lnot A_p\land \lnot A_q\lnot\ldots]\ge (1-\varepsilon_i)(1-\varepsilon_j)\ldots$$
• первое --- частный случай второго (одно событие слева от черты);
• второе следует из первого по индукции (произведение нескольких условных вероятностей);
• первое можно вывести из второго \emph{для меньшего числа переменных}: разделим в условии на соседей $N$ и несоседей $O$, получим $$\Pr[A_i|N\land O]=\frac{\Pr[A_i\land N\land O]}{\Pr[N\land O]}\le \frac{\Pr[A_i\land O]}{\Pr[N|O]\Pr[O]}.$$ Остаётся воспользоваться независимостью в числителе, оценкой $\Pr[N|O]\ge \prod_{j\in N(i)}(1-\varepsilon_j)$ и условием для $\Pr[A_i]$
• важно, что нет порочного круга: мы сводим в этом месте к утверждению для меньшего числа событий (без $A_i$)