Сверхслова, меры на них и их полупрямые произведения (1104768), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

(Продолжая пустое слово вправои влево до первого ненулевого символа в -компоненте, мы получим (, 2) существенное слово. При этом каждое (, 2) -существенное слово получитсястолькими способами, сколько имеется промежутков между его последова­тельными символами.)Замечание 3.6. Разумеется, одной функции на -существенных словах мо­жет соответствовать много разных инвариантных мер. Изменение мер сверх­81слов без ненулевых символов в -компоненте никак не влияет на соответ­ствующую функцию на -существенных словах.Определение 3.15. Функцию на (, ) -существенных словах будем назы­вать имеющей лёгкие хвосты, если сумма значений на всех словах, содер­жащих нулевых символов подряд в -компоненте, убывает с ростом как ( 1 ) .Функция на -существенных словах имеет лёгкие хвосты, если привсех её ограничение на (, ) -существенные слова имеет лёгкие хвосты.Последовательность функций на -существенных словах имеет рав­номерно лёгкие хвосты, если для каждого существует константа ,такая что для любой функции из последовательности сумма значений навсех (, ) -существенных словах, содержащих нулевых символов подрядв -компоненте, не превышает.Лемма 3.15.

Инвариантные меры с равными -существенными ограниче­ниями и нулевой вероятностью сверхслова . . . ⊙ . . . в -компоненте равнымежду собой.Лемма 3.16. -существенное ограничение любой инвариантной меры имеетлёгкие хвосты.Лемма 3.17. Функции имеют равномерно лёгкие хвосты. Функции ′имеют равномерно лёгкие хвосты.Лемма 3.18. Пусть дана последовательность ограниченных в совокуп­ности функций, причём функция определена на (, 6 ) -существенныхсловах.Тогда существует функция на -существенных словах и подпосле­довательность такие, что для всех слов значение () является преде­лом значений функций выбранной подпоследовательности, то есть lim () .Лемма 3.19.

Условия самосогласованности RightShift′ = ′ и LeftShift′ =′ нарушаются не более, чем на величину1. (Левая часть определена на82(, − 1) -существенных словах, а правая на (, ) -существенных; сравнива­ются значения на пересечении областей определения). Существует предель­ная точка последовательности ′ , и для неё эти условия выполнены в точ­ности.Лемма 3.20. Для всех > 2 и 0 6 6 − 2 сумма значений функцииLeftShift RightShift−−2 2 на (, 2) -существенных словах, умноженных надлину, конечна при фиксированном . То же верно и для ′ .

То же верно идля .Лемма 3.21. Пусть задана инвариантная мера на × . Тогда -суще­ственная очистка -существенного ограничения инвариантной меры равна -существенному ограничению очистки исходной меры.Это можно записать таким равенством−Restr − = Restr − Clean∘⊙ .Clean∘,⊙⊙⊙Лемма 3.22. Выполняются пропорциональности:−{︂ ⊙ }︂ Clean∘, ∼ Restr,− ,⊙*−{︂ ⊙ }︂LeftShift RightShift Clean∘,++ ∼ Restr,− ,⊙*− ′{︂ ⊙ }︂ Clean∘, ∼ Restr,− и⊙*−{︂ ⊙ }︂ Clean∘, ∼ Restr − .⊙*Аналогичное верно и для и (, ) -проекций.3.7.4.

Доказательство теоремыПокажем, что эти леммы достаточны для доказательства теоремы. Фак­тически мы будем непосредственно пользоваться только леммами 3.14, 3.15,3.19, 3.20, 3.21, 3.22. Остальные леммы нужны только для их доказательства.83По лемме 3.19 существует (хотя и не единственная) функция , являю­щаяся предельной точкой последовательности ′ . При этом для выполне­ны условия самосогласованности = RightShift = LeftShift .По лемме 3.20 сумма по всем (, 2) -существенным словами произведе­ния длины слова и значения функции на нём конечна.Тогда по лемме 3.14 функция является -существенным ограничени­ем некоторой инвариантной меры : = Restr − .

Очевидно, что меру можно выбрать так, чтобы вероятность последовательности из одних нулейв -компоненте равнялась нулю. Докажем, что Clean ⊙ = .⊙По лемме 3.22 , -проекция -существенной очистки от⊙⊙функции пропорциональна -существенному ограничению меры . Тогда и существенное ограничение очистки от⊙⊙, -проекции меры пропорцио­нально -существенному ограничению меры по лемме 3.21. Действитель­но,− =Restr − = Clean∘,⊙⊙*−− Restr − == Clean∘, ∼ Clean∘,⊙⊙⊙⊙∘, −= Clean ⊙⊙ −Restr ∼ (по лемме 3.21) ∼∼ Restr − Clean ⊙ .⊙Тогда Clean ⊙ ∼ по лемме 3.15 и Clean ⊙ = так как две про­⊙⊙порциональные вероятностные меры равны.По леммам 3.7 и 3.10 отсюда следуют пропорциональностиClean⊙ ∼ (Лемма 3.10) Clean ⊙ ∼*∼ (Лемма 3.7) Clean ⊙ Clean ⊙ ∼*⊙∼ (Лемма 3.10) ∼ Clean⊙ Clean ⊙ ∼ Clean⊙ ∼ .⊙Аналогично можно убедиться в равенстве Clean⊙ = .Осталось убедиться, что мера согласована с покомпонентым по­рядком.

Рассмотрим -существенные слова, в которых на какой-то позицииесть нарушение порядка компонент. Заметим, что и на таких словах84принимают значение ноль как ограничения мер и . Операция Join⊙ до­бавляет только одну возможную пару символов в , - и (, ) -проекции,а именно⊙⊙, но это не создаёт нарушений порядка компонент.

Усреднение ипереход к пределу не создают новых возможных троек символов, так как приусреднении оказываются возможными слова, которые и раньше являлись под­словами возможных слов. Таким образом, мера требует упорядоченностикомпонент в каждой позиции.Итак, мера согласована с покомпонентым отношением порядка иимеет проекции, очистки которых равны мерам и соответственно. Тогдаона доказывает D , что и требовалось.3.7.5. Доказательства леммПриведём теперь доказательства лемм 3.14–3.22.Доказательство леммы 3.14.Докажем сначала в простую сторону.Пусть дана инвариантная мера ; надо проверить, что её -существен­ное ограничение удовлетворяет условиям.Заметим сначала, что мера сверхслов, в которых в одной компонентесколько-то ненулевых символов, но потом с какого-то места будут тольконули, равна нулю.Действительно, все варианты расположения начала хвоста из одних ну­лей в этой компоненте несовместны и имеют одинаковую меру.

Так как ихсчётное количество, все они имеют меру нуль.Пусть = Restr − . Проверим, что выполнено одно из равенств, аименно LeftShift = , после этого равенство RightShift = доказывает­ся аналогично.Фиксируем -существенное слово и будем доказывать равенство(LeftShift )() = ().По мере вероятность того, что перед словом в -компоненте тольконулевые символы, равна нулю. Тогда с вероятностью единица перед словом85 будет идти какое-то количество троек с нулевой - компонентой и пе­ред ними тройка с ненулевой -компонентой. Это можно представить какравенство(︁ )︁ −1 .. ..

.. 2 1 () = () = ⊙⊙ ⊙* = −1 . . . 2 1,1 ,..., , ̸=⊙,1 ,...,(︁ )︁∑︁ −1 .. .. .. 2 1= ⊙⊙ ⊙ * = (LeftShift )(). −1 . . . 2 1∑︁,1 ,..., , ̸=⊙,1 ,...,Проверим второе условие. Рассмотрим все возможные тонкие цилиндрысо связным носителем, содержащим 0 и 1 и у которых содержание (то естьзадаваемое слово) является (, 2) -существенным. Все они задают несовмест­ные события, поэтому сумма их -мер не больше -меры всего простран­ства (которая конечна). Теперь заметим, что мера тонкого цилиндра зависиттолько от содержания, а каждое слово длины > 2 встречается в качествесодержания − 1 раз.Аналогично можно провести рассуждения для случая слов в алфавитепар символов, а не троек символов.Пусть теперь дана функция и мы хотим построить по ней меру .Определение 3.16. Пусть дано произвольное слово .

Будем называть тон­кий цилиндр со связным носителем и -существенным содержанием продол­жением слова , если в позициях 0, . . . , || − 1 он задаёт наличие слова .Элементарным продолжением будем называть каждое максимальное повключению цилиндров продолжение (то есть продолжение, содержание кото­рого не содержит в качестве подслова содержание другого продолжения).Другими словами, элементарное продолжение задаёт на всех позицияхносителя, кроме краёв и позиций 0 . . . || − 1 , символ ⊙ в -компоненте.Аналогично определим элементарное продолжение тонкого цилиндра .

Им является каждый содержащийся в тонкий цилиндр со связнымносителем и -существенным содержанием.У всякого -существенного слова есть единственное элементарное про­должение — оно само. Кроме того, никакие два элементарных продолженияслова не пересекаются как цилиндры.86Аналогично элементарным продолжениям определим элементарные про­должения вправо и влево. Очевидно, что множество всех элементарных про­должений слова — это множество всех элементарных продолжений вле­во всевозможных цилиндров, являющихся элементарными продолжениямивправо слова .Заметим, что мера, которую мы должны построить, должна иметь сле­дующее свойство.

Мера любого слова равна сумме значений на содер­жаниях всех его элементарных продолжений; притом разные элементарныепродолжения с одинаковым содержанием (отличающиеся сдвигом) учитыва­ются в сумме отдельно.Таким образом, с помощью элементарных продолжений мы определи­ли значения искомой меры на всех словах, в том числе тех, у которых компонента не является существенной.Заметим сразу, что полученная продолжением мера множества сверх­слов, в которых после некоторого символа ̸= ⊙ идут одни нули подрядв -компоненте равна нулю.

(Мы рассматриваем продолжения вправо, ното же самое верно для продолжений влево). Действительно, пусть эта мерабольше некоторого положительного числа . Тогда при всех сумма значе­ний на всех элементарных продолжениях слова вправо длины более больше числа .Но тогда мы получили бы, что сумма значений функции на различ­ных (, 2) -существенных словах, умноженных на их длину без 1, не меньше( − 1) для любого .Для проверки аддитивности и инвариантности полученной меры надопроверить, что мера слова равна сумме мер всех его продолжений на одинсимвол в какую-то одну сторону. Будем рассматривать, например, продолже­ния вправо.

Сначала предположим, что самый левый символ -компоненты ненулевой.Если исходное слово имеет в качестве последнего символа -ком­поненты ⊙ , то все его элементарные продолжения содержат хотя бы одинсимвол справа от самого правого символа , и сумма вероятностей элемен­87тарных продолжений односимвольных продолжений слова состоит из техже слагаемых, что и просто сумма всех элементарных продолжений слова .Если же -компонента заканчивается на ненулевой символ, то в сум­му по элементарным продолжениям, определяющую меру слова , войдутмеры всех способов приписать к -компоненте слова сколько-то нулей иненулевой символ, а к двум другим компонентам — столько же произвольныхсимволов.Но такая сумма по первому свойству функции будет равна мере сло­ва (мы сравниваем буквально значения на функции и её правогосдвига).Общий случай легко сводится к частному случаю ненулевого самого ле­вого символа.

Характеристики

Список файлов диссертации