Ловасздың жергілікті леммасы: Ықтималдық және алгоритмдік аспектілер
Lovász local lemma
Ықтималдық теориясындағы Ловас жергілікті леммасы: тәуелсіз емес оқиғалардың да орын алмауының ықтималдығын анықтайды. Экзистенциялық дәлелдерде қолданылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ықтималдықтар теориясында, егер көптеген оқиғалар бір-бірінен тәуелсіз болса және олардың әрқайсысының ықтималдығы 1-ден кем болса, онда ешбір оқиғаның орын алмауының оң (мүмкін кішкентай) ықтималдығы бар. Ловас жергілікті леммасы тәуелсіздік шартын сәл жеңілдетуге мүмкіндік береді: оқиғалар бір-бірінен «көптеп» тәуелсіз болған және жеке-жеке тым ықтимал болмаған жағдайда, олардың ешқайсысының орын алмауының оң ықтималдығы болады. Ол көбінесе ықтималдық әдісте қолданылады, әсіресе барлықтық дәлелдер беру үшін. Лемманың бірнеше түрі бар. Ең қарапайым және жиі қолданылатын түрі симметриялық түрі, төменде келтірілген. 1975 жылы Ласло Ловас және Пол Эрдос «3-хроматикалық гиперграфтардағы проблемалар мен нәтижелер және оған байланысты сұрақтар» мақаласында осы лемманың әлсіз түрін дәлелдеді. Басқа түрлері үшін қараңыз. 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.
Құрылысшы және құрылысшы емес
Байқаңыз, бұл теорема, ықтималдық аргументтерде жиі болатындай, конструктивті емес және ешбір оқиғаның орын алмауына кепілдік беретін ықтималдық кеңістігінің нақты бір элементін табуға мүмкіндік бермейді. Дегенмен, жергілікті лемманың күштірек алғышарттары бар алгоритмдік нұсқалары да бар (Бек 1991; Чжумай және Шейделер 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 нүкте шеңбердің бойына орналастырылып, әр түрлі түстермен боялған болса, әр түс дәл 11 нүктеге қолданылады. Мұндай бояуда әр түстің бір нүктесін қамтитын, бірақ ешбір көршілес нүктелер жұбын қамтымайтын n нүктелер жиынтығы болуы керек. Мұны түсіну үшін, әр түстің нүктесін кездейсоқ таңдап алуды көзге елестетіңіз, барлық нүктелер тең мүмкіндікке ие (яғни, таңдалу ықтималдығы 1/11). Бізге қажетті 11n түрлі жағдай шеңбердегі 11n көршілес нүктелер жұбына сәйкес келеді. Әр жұп үшін осы екі нүктені таңдау мүмкіндігіміз ең көп дегенде 1/121 (егер екі нүкте әр түрлі түс болса, дәл 1/121, әйтпесе 0), сондықтан p = 1/121 деп қабылдаймыз. Берілген (a, b) нүктелер жұбының таңдалуы тек a және b нүктелерінің түсіне байланысты, ал қалған n - 2 түстердегі нүктелердің таңдалған-таңдалмағандығына ешқандай қатысы жоқ. Бұл "a және b екеуі де таңдалады" деген жағдай тек a немесе b нүктесімен түсі ортақ болатын көршілес нүктелер жұбына ғана байланысты екенін көрсетеді. Шеңберде a нүктесімен бір түсті бөлісетін 11 нүкте бар (a нүктесінің өзі де соның ішінде), олардың әрқайсысы 2 жұпқа қатысады. Демек, (a, b) жұбынан басқа a-мен бірдей түске ие 21 жұп бар, және 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.