Вероятностный метод и локальная лемма Ловаса в комбинаторике слов

Исполнительное резюме. Вероятностный метод широко применяется в комбинаторике слов для доказательства существования слов с заданными свойствами (например, без повторяющихся фрагментов). Ключевой инструмент – Локальная лемма Ловаса: она гарантирует, что при «редких» и «слабо зависимых» нежелательных событиях существует конфигурация без ни одного из них. В частности, рассмотрим бесквадратные слова (слова без подряд повторяющихся подслов). Для алфавита достаточного размера (|A| больших значений) случайное слово длинны n практически гарантированно не содержит квадратов: каждый потенциальный «квадрат» определяется событием с вероятностью P = |A|^{-ℓ} (ℓ – половина длины квадрата), а зависимости между такими событиями малы. Проверка условия леммы (например, симметричной: e·p·(d+1)≤1) показывает, что при больших |A| положительная вероятность отсутствия квадратов. Например, для алфавита из 50 символов и слова длины 10 выполнение условия локальной леммы подтверждается при любых потенциальных квадратных событиях (см. таблицу ниже). Таким образом, существует бесквадратное слово длины n. Алгоритмически оно может быть построено при помощи конструктивных версий леммы (алгоритм Мозера–Тардоша и др.).

Основные понятия

Алфавит Σ – конечное множество символов (букв). Слово над Σ – конечная последовательность букв из Σ. Длина слова w обозначается |w|. Пустое слово Λ имеет |Λ|=0.
Подслово (фактор) – слово u называется подсловом слова w, если u появляется в w как непрерывная подпоследовательность букв. Например, aba – подслово слова cababa (позиции 3–5).
Квадрат слова – слово вида \(xx\), где \(x\ne\Lambda\). Например, abab, zz.
Бесквадратное слово – слово, не содержащее в себе квадрата ни какого непустого слова. Например, abcacbab... (Туэ) – бесквадратный. А. Туэ доказал, что бесконечные бесквадратные слова существуют над любым алфавитом из ≥3 символов.
События (в вероятностном методе) – в наших применениях «событие» A_i обычно означает появление нежелательного паттерна (например, квадрата) в случайно выбранном слове. Вероятность P(A_i) – мера его «редкости».
Граф зависимостей – ориентированный (или неориентированный) граф D на множестве событий {A_1,…,A_n}, где ребро (i→j) означает, что события A_i и A_j зависят (не являются независимыми). Другими словами, для события A_i все события, не смежные с ним в графе, независимы от A_i.

Локальная лемма Ловаса (формулировка)

Асимметричная версия. Пусть A1,…,A_n – события в некотором вероятностном пространстве, и задан граф зависимостей. Введём для каждого события A_i число xi∈(0,1). Если для всех i выполнено [ P(A_i)\le xi\prod(1-xj), ] где Γ(i) – соседние события (зависимые) в графе, то вероятность того, что ни одно из событий не произойдёт, положительна: [ P\Bigl(\bigwedge\Bigr)\;\ge\;\prod}^n \overline{A_i{i=1}^n(1-xi)>0. ] Таким образом существует исход, при котором ни одно A_i не происходит.

Симметричная версия. Часто предполагают равные вероятности P(A_i)≤p и что у каждого события ≤d соседей. Тогда условие упрощается до [ e\;p\;(d+1)\le1, ] где e≈2.718…. Если это выполнено, то с положительной вероятностью ни одно событие не произойдёт. Условие вида epd≤1 тоже оказывается достаточным.

Из формулировки видно, что необходимы: (i) независимости A_i от всех не-соседних событий и (ii) малые величины P(A_i). Граф зависимостей отражает факт (i), а неравенства гарантируют (ii). Таким образом, ЛЛЛ требует, чтобы «каждое нежелательное событие редко, и любая группа слишком большого числа таких событий маловероятна одновременно».

Применение леммы: бесквадратные слова

Идея доказательства. Фиксируем длину n и алфавит Σ (|Σ|=m). Рассмотрим случайное слово W = (w1…wn), где каждая буква wi выбирается независимо и равновероятно из Σ. Определим «плохие» события: для любых позиций i и целой длины ℓ≥1 событие A = «слово W имеет квадрат из двух одинаковых блоков длины ℓ, начинающийся в позиции i», т.е. [ A{i,\ell}:\quad (w_i\cdots w)=(w{i+\ell}\cdots w)\,. ] Такие квадраты могут появиться при i=1,…,n-2ℓ+1. Вероятность любого события равна [ P(A_{i,\ell})=(1/m)^\ell, ] потому что независимая серия совпадений ℓ пар букв должна произойти.

Два события A{i,ℓ} и A имеет лишь «локальных» соседей: вероятно пересекаются только с теми квадратами, которые начинаются в пределах O(ℓ) позиций вокруг i. Число соседей можно оценить сверху (зависит от n и максимальной ℓ).} зависимы (не могут считаться независимыми), если их блоки перекрываются в слове (их позиции пересекаются). В графе зависимостей мы ставим ребро между событиями, если они перекрываются. Каждое событие A_{i,ℓ

По Лемме Ловаса достаточно проверить для каждого A{i,ℓ} условие вида P(A)≤x·∏(1-x) соседей. В симметричной формулировке достаточно положить P=P(A), d – максимальная степень в графе. Условие ≈ e·P·(d+1)≤1 должно выполняться. При достаточно большой m оно обычно выполняется для всех ℓ: события редки.

Пример расчётов (числовой). Возьмём, скажем, алфавит из 50 букв и длину n=10. Возможны квадраты половины длины ℓ=1…5. Укажем число возможных позиций, вероятность и оценку e·P·(d+1):

ℓ (половина квадрата)	Кол-во позиций i	P(A_{i,ℓ}) = m^{-ℓ}	макс. число соседей d	e·P·(d+1)
1	9	1/50 = 0.02	16	0.924
2	7	1/50² = 0.0004	20	0.0228
3	5	1/50³ = 0.000008	22	0.00050
4	3	1/50⁴ ≈1.6e-7	24	0.0000109
5	1	1/50⁵ ≈3.2e-9	24	0.000000217

Как видно, для ℓ≥2 условие e·P·(d+1)≪1 выполнено с большим запасом; для ℓ=1 мы получили примерно 0.924<1. По симметричной версии ЛЛЛ e·p·(d+1)≤1, следовательно, с положительной вероятностью ни один из квадратичных событий не происходит. То есть существует слово длины 10 без квадратов (бесквадратное).

flowchart LR A[Выбрать случайное слово длины n над алфавитом Σ] --> B[Определить «плохие» события A_{i,ℓ} – наличие квадрата длины 2ℓ в позиции i] B --> C[Вычислить вероятность P(A_{i,ℓ}) = |Σ|^{-ℓ}] C --> D[Построить граф зависимостей: события связаны, если их блоки перекрываются] D --> E[Оценить число соседей d и проверить e·P(A)(d+1) ≤ 1 для всех событий] E --> F[Заключение: есть положительная вероятность отсутствия всех «плохих» событий] F --> G[Следствие: существует бесквадратное слово длины n]

На схеме показан общий план применения леммы: выбор пространства, определение событий, расчёт P(A_i), построение графа, проверка условия Леммы, и вывод существования нужного слова.

Полезные замечания и ограничения метода

В условиях симметричной ЛЛЛ обычно достаточно иметь алфавит достаточно большой: при маленьких |Σ| неравенство e·p·(d+1)≤1 нарушается. Например, для бинарного алфавита (|Σ|=2) сразу появляется множество перекрывающихся квадративных событий и метод не сработает. Известно, что над 2 буквами бесквадратное слово ограничено длиной 3, а над 3 буквами (Туэ) бесконечное слово существует конструктивно, но не силами простой ЛЛЛ (запрещённых слов слишком много, F*k=2^k, см. условия Миллера). ЛЛЛ даёт существование бесквадратных слов для большего |Σ| и конечных n, а из бесконечной последовательности (через компактность) – для всех n.
Оценочные версии: условие e·p·(d+1)≤1 – грубая достаточная оценка. Более точный порог нашёл Ширер (Ширер, 1985): p<(d-1)^{d-1}/d^d. Однако на практике чаще используют простую форму с e.
Ограничения: ЛЛЛ даёт не конструктивное существование (он не строит слово явно). Тем не менее алгоритмические версии позволяют эффективно находить такие слова. Например, метод усиленного ресэмплинга Мозера–Тардоша (2010) гарантирует, что при LLL-условиях можно пошагово «перебрасывать» буквы и получить бесквадратное слово за ожидаемое время близкое к O(n). Также есть специальные алгоритмы для избегающих последовательностей.

Алгоритмическая конструкция

Локальная лемма Ловаса в классическом виде является неконструктивной. Однако с появлением алгоритма Мозера–Тардоша (2009–2010) стало возможным на практике строить такие слова. Идея в том, что при появлении «плохого» события (квадрата) мы заново выбираем случайно буквы на соответствующем отрезке (локальный ресэмплинг). Анализ Мозера–Тардоша показывает, что при выполнении условий Леммы ожидаемое число пересэмплов невелико, и алгоритм быстро находит бесквадратное слово. Альтернативно, существуют специальные алгоритмы (иногда приписываемые G. Molnár и др.), генерирующие бесквадратные последовательности путём жадного добавления символов с откатом при образовании квадрата. Эти алгоритмы основаны на идеях Леммы Ловаса и обычно работают эффективно для алфавитов средней величины.