Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В теории вероятностей, если большое число событий независимы друг от друга и каждое из них имеет вероятность меньше 1, то существует положительная (возможно, малая) вероятность того, что ни одно из событий не произойдет. Локальная лемма Ловаса позволяет несколько ослабить условие независимости: пока события "в основном" независимы друг от друга и не слишком вероятны по отдельности, положительная вероятность того, что ни одно из них не произойдет, сохраняется. Она наиболее часто используется в вероятностном методе, в частности, для доказательств существования. Существует несколько различных версий леммы. Самая простая и наиболее часто используемая – симметричная, представленная ниже. Более слабая версия была доказана в 1975 году Ласло Ловасом и Полом Эрдошем в статье "Problems and results on 3 chromatic hypergraphs and some related questions". В 2020 году Робин Мозер и Габор Тардос получили премию Гёделя за их алгоритмическую версию локальной леммы Ловаса, которая использует энтропийное сжатие для предоставления эффективного рандомизированного алгоритма, находящего исход, в котором ни одно из событий не происходит.
In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs. There are several different versions of the lemma. The simplest and most frequently used is the symmetric version given below. A weaker version was proved in 1975 by László Lovász and Paul Erdős in the article Problems and results on 3 chromatic hypergraphs and some related questions. For other versions, see In 2020, Robin Moser and Gábor Tardos received the Gödel Prize for their algorithmic version of the Lovász Local Lemma, which uses entropy compression to provide an efficient randomized algorithm for finding an outcome in which none of the events occurs.
Конструктивный против неконструктивного
Обратите внимание, что, как это часто бывает с вероятностными рассуждениями, эта теорема является неконструктивной и не предоставляет способа указать конкретный элемент вероятностного пространства, в котором никакое событие не происходит. Однако существуют также алгоритмические варианты локальной леммы с более строгими предварительными условиями (Beck 1991; Czumaj и Scheideler 2000). Недавно Робин Мозер и Габор Тардош предложили конструктивную версию локальной леммы, не требующую более строгих предварительных условий.
Note that, as is often the case with probabilistic arguments, this theorem is nonconstructive and gives no method of determining an explicit element of the probability space in which no event occurs. However, algorithmic versions of the local lemma with stronger preconditions are also known (Beck 1991; Czumaj and Scheideler 2000). More recently, a constructive version of the local lemma was given by Robin Moser and Gábor Tardos requiring no stronger preconditions.
Пример
Предположим, что 11n точек расположены вокруг окружности и окрашены в n различных цветов таким образом, что каждый цвет используется ровно для 11 точек. В любой такой раскраске должно существовать множество из n точек, содержащее по одной точке каждого цвета, но не содержащее ни одной пары соседних точек. Чтобы увидеть это, представим, что мы выбираем по одной точке каждого цвета случайным образом, при этом все точки равновероятны (то есть, вероятность выбора каждой точки равна 1/11). 11n различных событий, которых мы хотим избежать, соответствуют 11n парам соседних точек на окружности. Для каждой пары вероятность выбора обеих точек в этой паре не превышает 1/121 (точно 1/121, если две точки окрашены в разные цвета, иначе – 0), поэтому мы примем p = 1/121. То, будет ли выбрана данная пара точек (a, b), зависит только от того, что происходит с цветами точек a и b, и никак не зависит от того, выбрана ли какая-либо другая группа точек в остальных n - 2 цветах. Это означает, что событие "a и b выбраны оба" зависит только от тех пар соседних точек, которые имеют общий цвет либо с a, либо с b. На окружности 11 точек, имеющих тот же цвет, что и a (включая саму точку a), каждая из которых участвует в 2 парах. Это означает, что существует 21 пара, отличная от (a, b), которая включает тот же цвет, что и a, и то же самое верно для b. В худшем случае эти два множества не пересекаются, поэтому мы можем взять d = 42 в лемме. Это дает.
Suppose 11n points are placed around a circle and colored with n different colors in such a way that each color is applied to exactly 11 points. In any such coloring, there must be a set of n points containing one point of each color but not containing any pair of adjacent points. To see this, imagine picking a point of each color randomly, with all points equally likely (i. e., having probability 1/11) to be chosen. The 11n different events we want to avoid correspond to the 11n pairs of adjacent points on the circle. For each pair our chance of picking both points in that pair is at most 1/121 (exactly 1/121 if the two points are of different colors, otherwise 0), so we will take p = 1/121. Whether a given pair (a, b) of points is chosen depends only on what happens in the colors of a and b, and not at all on whether any other collection of points in the other n − 2 colors are chosen. This implies the event "a and b are both chosen" is dependent only on those pairs of adjacent points which share a color either with a or with b. There are 11 points on the circle sharing a color with a (including a itself), each of which is involved with 2 pairs. This means there are 21 pairs other than (a, b) which include the same color as a, and the same holds true for b. The worst that can happen is that these two sets are disjoint, so we can take d = 42 in the lemma. This gives
По локальной лемме существует положительная вероятность того, что ни одно из неблагоприятных событий не произойдет, то есть наше множество не содержит пары соседних точек. Это подразумевает, что множество, удовлетворяющее нашим условиям, должно существовать.
By the local lemma, there is a positive probability that none of the bad events occur, meaning that our set contains no pair of adjacent points. This implies that a set satisfying our conditions must exist.