«Сверхслова, меры на них и их полупрямые произведения ...»

Докажем невыполненность четвертого условия (при некоторых значени­ ях параметров, ). Причина немонотонности операторов Тоома кроется в немонотонности оператора Ann. Докажем последнее для достаточно близ­ ких к 1 значений. Для этого рассмотрим меру, сконцентрированную на последовательностях с периодом и меру, сконцентрированную на последовательностях с периодом Ясно, что по тем же причинам, по которым верно было аналогичное неравенство для мер на односторонних сверхсловах (его мы доказали в на­ чале второй главы). Но после применения к ним оператора Ann с = образ меры сосредоточен на последовательностях с периодом, а образ меры — на последовательностях с периодом. Ве­ роятность верхнего цилиндра * * (звёздочка означает, что можно поставить любой символ алфавита) относительно равна 1/4, в то время как его -вероятность равна 1/6, что меньше 1/4. Поэтому, что до­ казывает немонотонность оператора Ann с = 1. (Заметим в скобках, что меры и несравнимы. В самом деле, -вероятность верхнего цилиндра равна нулю, в то время, как как его -вероятность равна 1/3.) В си­ лу непрерывности оператор Ann не монотонен и при любых, достаточно близких к 1.

Этот пример доказывает немонотонность операторов Тоома при любых и достаточно близких к 0 и 1, соответственно. В самом деле положим = 0 в операторах Flip, Flip+. Тогда оба оператора Тоома выродятся в Ann, а значит будут немонотонны. По непрерывности они будут немонотонны и при любых и достаточно близких к 0 и 1, соответственно.

Заметим, что немонотонность оператора Ann является единственной причиной немонотонности асимметричного оператора Тоома асим. Напом­ ним, что он определяется как композиция Flip+ и Duel. При этом оператор Flip+ монотонен. В самом деле, пусть и мера есть полупрямое произ­ ведение и, согласованное с порядком. Рассмотрим оператор, который действует на парах последовательностей, заменяя с вероятностью каждую пару соответствующих символов на пару (для разных пар независимо), а каждую пару на пару ратор к мере и обозначим полученную меру через. Ясно, что также, как и, согласована с порядком, причём ее маргинальные меры равны результату применения оператора Flip+ к и. Таким образом, если бы оператор Ann был монотонен, то и оператор асим был бы монотонным как композиция монотонных операторов.

Выполнено ли второе условие, неизвестно. Непосредственно из опреде­ из этого бы сразу следовало неравенство между интересующими нас опера­ торами: сим асим, однако мы уже видели, что это не так.

Начнем со следующего наблюдения.

Лемма 3.7. Clean1 Clean2 = Clean1 2.

Доказательство. Рассмотрим формулу на странице 57, определяющую Clean (). Рассмотрим отдельно сумму и нормирующий сомножитель пе­ ред суммой. В сумме для Clean1 Clean2 мы получаем сумму вероятностей слов, полученных вставкой между буквами слова произвольных последо­ вательностей символов из 1, а потом между буквами полученного слова — произвольных последовательностей символов из 2. Но такой парой опера­ цией между двумя соседними символами можно вставить произвольную последовательность символов из 1 2, причём единственным образом. По­ этому суммы для Clean1 Clean2 и Clean1 2 равны.

Теперь рассмотрим нормирующие множители. Они равны в случае поочерёдного применения и в случае одновременного. Заметим, что Обозначим (1 ) =, (2 ) =. Остаётся проверить, что что действительно является алгебраическим тождеством. Лемма 3.7 доказа­ на.

Аналогичное утверждение верно и для Clean.

Определение 3.7. Будем писать для инвариантных вероятност­ на сверхсловах над алфавитом {,, }, и Clean{} от которых даёт ис­ ходные меры: Clean{} =, Clean{} =. Другими словами, должна существовать мера с инвариантными проекциями на парах сверхслов над алфавитом {,, }, такая что оператор Clean{} в применении к её маргинальным мерам даёт меры и, соответственно, а при этом по вероятностному распределению первая компонента всегда больше либо равна второй относительно порядка > >.

достигается только при равенстве мер.

Доказательство. Действительно, пусть мера имеет проекции,, Разность этих выражений равна Это выражение всегда неотрицательно, поэтому () (). Теперь нам достаточно доказать, что из равенства числителя нулю следует (эти равенства гарантируют, что Clean от двух проекций меры совпадают).

Первое равенство следует из того, что в числитель входит квадрат.

Кроме того, в числитель входит произведение а значит оно равно нулю. Сумма в скобках равна) () и если она отлична от нуля, мы получаем желаемое следствие = 0. С другой стороны,, сосредоточены на последовательности из одних минусов и доказываемое утверждение очевидно.

Наконец, в числитель также входит произведение Сумма в скобках равна )() и если она отлична от нуля, мы получаем желаемое следствие = 0. С другой стороны, если () = 0, то этом случае обе меры, сосредоточены на последовательности из одних плюсов и доказываемое утверждение очевидно.

Лемма 3.9. Отношение антисимметрично.

Доказательство. Действительно, в силу предыдущей леммы, если, то вероятности слов и по этим мерам равны, а тогда полупрямое про­ изведение, согласованное с порядком, не может содержать слова и обязано Лемма 3.10. Очистка и проекция коммутируют. Точнее, 1 Clean = Clean 1 ( 1 означает проекцию на первую компоненту).

Доказательство. Рассмотрим меру произвольного слова, то есть величи­ ну (1 Clean )(). По определению проекции это можно переписать как (Clean )( || ). Но по определению очистки это равно Но так как множество { Splice ()| || } совпадает с { || | Splice ()}. А тогда мы получили выражения для желаемого результата (Clean 1 )() Лемма 3.11. Пусть и мера является обоснованием этого неравен­ ства. Будем рассматривать как меру над алфавитом из пар символов (3.1) на с. 53. Тогда можно так изменить, что она по-прежнему будет мерой, доказывающей неравенство между мерами, но символ имеет вероятность 0.

';

Доказательство. Действительно, возьмём и заменим все вхождения произведём Clean{ } над и обозначим полученную меру через. Яс­ но, что новых вхождений символов, у которых верхняя компонента меньше появится, а значит согласована с порядком. Образ проекций меры под действием Clean{} такой же, как и у. В самом деле, так как в каж­ дой проекции исходной меры соответствует или в новой до очистки, а затем производится две очистки (правда, одна из очисток происходит до перехода к проекции, а вторая после, но это не меняет результата по лемме 3.10), которые в силу леммы 3.7 эквивалентны одной.

Лемма 3.12. В определении ра приписывает слову вероятность 0 ).

При этом если мера приписывала вероятность 0 всем слова, содер­ жащих в одной из компонент, то этим же свойством будет обладать результат преобразования.

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

Для доказательства воспользуемся леммой 3.5.

Рассмотрим последовательность мер, где является средним ариф­ метическим сдвигов на, + 1,... 1, 0, 1,... 1,. Заметим, что проекции равны проекциям, так как проекция среднего равна среднему проекций, а среднее от сдвигов инвариантной меры равно ей самой.

Теперь заметим, что для любого слова вероятности его вхождения в как в среднем арифметическом будет лишь по одному отличающемуся слага­ емому из 2 + 1. Значит, в предельной точке вероятности вхождения любого слова в позициях 0 и 1 равны, из чего очевидно следует инвариантность.

точка мер будет обладать этим же свойством.

Лемма 3.12 доказана.

Лемма 3.13. В определении казывающей неравенство, приписывают вероятность 0 сверхслову из всех нулей (а также является инвариантной и приписывает вероят­ Доказательство леммы 3.13. Действительно, пусть это не так. Пусть, например, в первой проекции сверхслово из одних нулей имеет положитель­ ную вероятность. Заметим, что тогда мера представима как выпуклая ком­ бинация какой-то меры и меры, сосредоточенной на сверхслове.... В силу линейности проекции и очистки, очистка первой проекции меры равна.

Заменим меру на прямое произведение и меры, сосредоточен­ ной на сверхслове...... и рассмотрим выпуклую комбинацию с теми же коэффициентами. второй проекция будет такой же, как у меры, а первая проекция будет выпуклой комбинацией двух мер с очисткой. При этом порядок между компонентами, очевидно, не мог нарушиться.

Таким образом, новая мера доказывает, но запрещает сверхслово...... в проекции, что и требовалось. Ясно, что использованное преобразо­ вание сохраняет свойства инвариантности и отсутствия вхождений слова.

Лемма 3.13 доказана.

3.7. Основной результат Теорема 3.3. Отношение транзитивно.

3.7.1. Общий план доказательства Доказательство. Обозначим 3 копии пространства сверхслов через алфавит этих сверхслов состоит из трёх символов, а меры, определённые исходно над алфавитом двух символов, приписывают словам содержащим символ меру 0. Рассмотрим меры, на пространствах и, подтверждающие эти неравенства. Обозначим проекции (маргинальные меры) меры через и, а проекции меры — через и. Тогда, заданные на, отличаются тем, из какой меры они получены: мера — проекция меры на пространстве, а — проекция меры на пространстве.

По лемме 3.11, не ограничивая общности, можно считать, что и, и инвариантны, ) ( приписывают нулевую вероятность множеству сверхслов, со­ держащих, а их проекции приписывают нулевую вероятность слову из одних нулей.

Опишем общий план доказательства.

Идея в том, чтобы построить нужную функцию в самом простом случае, а потом решать возникающие проблемы с помощью усреднений и перехода к предельной точке.

Мы построим объединённую меру в алфавите троек символов, такую вторые две — меру. То есть, мы хотим добиться того, что Clean = Определение 3.8. Слово в алфавите {,, } называется существенным, если оно не начинается и не заканчивается на.

Слово в алфавите пар или троек символов называется -существен­ ным, если его -компонента существенная. Такое слово называется (, ) существенным, если количество ненулевых символов в -компоненте рав­ но. Если количество ненулевых символов в -компоненте существенно­ го слова не превышает, будем называть такое слово (, ) -существен­ ным.

Проекции мер и на -компоненту отличаются только добавлением нулей в некоторых местах. Мы хотим так добавить в случайные по мерам и последовательности символы, чтобы их -компоненты оказались одинаково распределены.

Сначала мы рассмотрим только слова с существенной -компонентой, так как для них легко определить количества нулей между соседними нену­ левыми символами без рассмотрения краёв.

Пусть есть два -существенных слова и в алфавите пар символов (мы считаем, что у первого есть компоненты и, а у второго слова — компоненты и ). Пусть ещё очистка -компоненты от у них совпа­ дает. Вставим после каждого ненулевого символа в -компоненте слова слова после такого же по счёту ненулевого символа, и наоборот.

После такой операции мы получим слова и с одинаковой -ком­ понентой и можем соединить их в одно слово в алфавите троек символов.

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

Разумеется, порождаемые таким процессом распределения вероятностей для разных значений не будут согласованы между собой. Другими слова­ ми, непосредственное порождение слова данной длины и порождение его как суффикса или префикса более длинного слова дают разные распределения вероятностей.

Для преодоления этого препятствия мы рассмотрим порождение корот­ ких слов как случайно выбранных -существенных подслов длинных слов.

Мы будем порождать слово по -му распределению и выбирать в нём (, ) существенное подслово с началом в случайной позиции при > 2. Мы по­ кажем, что при одном и том же значении распределения для разных коли­ честв ненулевых символов в -компоненте будут согласованы с некоторой погрешностью, которая убывает с ростом.

После этого мы рассмотрим произвольную предельную точку этих рас­ пределений при. Мы убедимся, что при переходе к предельной точке мы получим для каждого значения распределение вероятностей на (, ) существенных словах, причём эти распределения для разных будут согла­ сованы.

После этого мы продолжим меру уже на все слова.

3.7.2. Формальное описание конструкции Опишем теперь конструкцию формально.

Определение 3.9. Будем обозначать проекцию меры на набор компонент как (). В качестве иллюстрации скажем, что выполняются равенства, () = и Clean () = Clean ().

Аналогично будем обозначать и проекции слов.

Определение 3.10. Пусть дана инвариантная мера на пространстве дву­ сторонних бесконечных последовательностей пар символов. Будем называть -существенным ограничением меры функцию, являющуюся ограниче­ нием меры как функции на словах на множество -существенных слов.

Будем обозначать такую функцию Restr. Аналогично определяется (, ) -существенное ограничение, обозначаемое Restr,.

Нормированное (, ) -существенное ограничение меры получается из её (, ) -существенного ограничения делением на меру наличия ненулевого символа в позиции 0 в -компоненте (то есть на ({0 = }) ). Обозначение:

PRestr,. (Буква P в обозначении от слова probabilistic).

Данное определение применимо для меры с компонентами и (и меры с компонентами, и ).

Замечание 3.4. Нормированное (, ) -существенное ограничение инвари­ антной меры является распределением вероятностей на множестве (, ) существенных слов.

Определение 3.11. Пусть функция задаёт меру на (, ) -существенных словах. Отбрасывание префикса слова вплоть до второго ненулевого символа в -компоненте (не включительно) задаёт отображение (, ) -существенных слов на (, 1) -существенные. Образ меры при этом отображении будем называть левым сдвигом и обозначать LeftShift.

Аналогично определяется левый сдвиг, если из компонент и при­ сутствует только одна.

Мы будем применять это обозначение и к функциям, определённым на бльших множествах слов. Пусть функция определена на множестве (, ) -существенных слов, где параметр пробегает какое-то множество на­ туральных чисел. Тогда LeftShift () определена на множестве (, ) существенных слов для той же самой формулой. При этом мы не требуем, чтобы при разных значениях параметра значения функции () для (, ) -существенных слов были как-то согласованы.

Аналогично определяется правый сдвиг, обозначаемый RightShift.

Замечание 3.5. Легко видеть, что левый и правый сдвиг коммутируют.

Определение 3.12. Пусть дана мера на (, ) -существенных словах.

Определим её применение к (, слово будем отождествлять со множеством всех его продолжений вправо до (, ) -существенного слова. Иначе говоря, если слово является (, ) существенным, положим по определению ( ) = (RightShift )( ).

Определение 3.13. Пусть дано (, ) -существенное слово с компонента­ ми и и (, ) -существенное слово с компонентами и, причём очистки их -компонент равны, Clean = Clean.

Будем называть их ноль-склейкой и обозначать Join (, ) последова­ тельность, полученную следующим алгоритмом. Для каждого < после позиции -го ненулевого символа в -компоненте слова вставим в слово столько символов после -го ненулевого символа, и наоборот.

При этом мы получим два слова, с одинаковой -компонентой.

Отождествим их -компоненты и получим слово с компонентами,,, которое обозначается Join (, ).

Иллюстрация действия Join Определение 3.14. Пусть дана функция на (, ) -существенных сло­ вах. Пусть ещё дано множество, содержащее только наборы (пары или тройки) символов с нулевой -компонентой.

Будем называть -существенной очисткой функции от элементов из множества и обозначать Clean, следующую функцию (по ана­ логии с Clean ).

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

неравенства. Будем считать меры и инвариантными и приписывающими меру 0 слову и сверхслову из одних нулей в каждой из компонент (как мы ранее показали, это не ограничивает общность).

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

К сожалению, функции могут оказаться не согласованы между собой (то есть RightShift+1 = ) и не инвариантны (то есть LeftShift = RightShift ). Поэтому мы рассмотрим = Рассматривая как функцию на (, ) -существенных словах можно определить как предельную точку, то есть функцию на -существен­ ных словах, к которой поточечно сходится некоторая подпоследовательность последовательности. Эта функция будет -существенным ограничением некоторой инвариантной меры на тройках символов.

Из построения следует, что мера требует, чтобы в каждой позиции в -компоненте стоял максимальный символ, а в -компоненте — минималь­ ный (разумеется, имеются в виду нестрогие неравенства).

Кроме того, на каждом шаге построения функции сохранялось следу­ ющее свойство. Рассмотрим -существенное слово в алфавите пар симво­ лов, не содержащее пары символов. Рассмотрим суммарную вероятность всех слов из Splice. Эта суммарная вероятность будет пропорциональна (). Аналогичное утверждение будет верно для -существенных слов с компонентами,,. Точнее,, -проекция -существенной очистки от (или ) функций,,, равна -существенному ограничению меры.

Таким образом, очистка от символа равняться мере.

Аналогичное утверждение будет верно для (, ) -проекции меры и ме­ ры. Тогда легко видеть, что, -проекция меры доказывает неравен­ Перейдём к точным формулировкам. Сначала мы сформулируем неко­ торые леммы, потом мы объясним как из лемм следует теорема, и в самом конце мы докажем леммы.

3.7.3. Формулировки лемм Лемма 3.14. Неотрицательная функция на -существенных словах яв­ ляется -существенным ограничением какой-то инвариантной меры тогда и только тогда когда выполнены следующие условия:

Во-первых, функция удовлетворяет условиям самосогласованности, аналогичным инвариантности и аддитивности, а именно Другими словами, оба её сдвига равны самой функции.

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

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

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

Лемма 3.16. -существенное ограничение любой инвариантной меры имеет лёгкие хвосты.

Лемма 3.17. Функции имеют равномерно лёгкие хвосты. Функции имеют равномерно лёгкие хвосты.

Лемма 3.18. Пусть дана последовательность ограниченных в совокуп­ ности функций, причём функция определена на (, ) -существенных словах.

Тогда существует функция на -существенных словах и подпосле­ довательность такие, что для всех слов значение () является преде­ лом значений функций выбранной подпоследовательности, то есть lim ().

Лемма 3.19. Условия самосогласованности RightShift = и LeftShift = нарушаются не более, чем на величину. (Левая часть определена на (, 1) -существенных словах, а правая на (, ) -существенных; сравнива­ ются значения на пересечении областей определения). Существует предель­ ная точка последовательности, и для неё эти условия выполнены в точ­ ности.

LeftShift RightShift2 2 на (, 2) -существенных словах, умноженных на длину, конечна при фиксированном. То же верно и для. То же верно и для.

Лемма 3.21. Пусть задана инвариантная мера на. Тогда -суще­ ственная очистка -существенного ограничения инвариантной меры равна -существенному ограничению очистки исходной меры.

Это можно записать таким равенством Лемма 3.22. Выполняются пропорциональности:

LeftShift RightShift Clean, ++ Restr,, Аналогичное верно и для и (, ) -проекций.

3.7.4. Доказательство теоремы Покажем, что эти леммы достаточны для доказательства теоремы. Фак­ тически мы будем непосредственно пользоваться только леммами 3.14, 3.15, 3.19, 3.20, 3.21, 3.22. Остальные леммы нужны только для их доказательства.

По лемме 3.19 существует (хотя и не единственная) функция, являю­ щаяся предельной точкой последовательности. При этом для выполне­ ны условия самосогласованности = RightShift = LeftShift.

По лемме 3.20 сумма по всем (, 2) -существенным словами произведе­ ния длины слова и значения функции на нём конечна.

Тогда по лемме 3.14 функция является -существенным ограничени­ ем некоторой инвариантной меры : = Restr. Очевидно, что меру можно выбрать так, чтобы вероятность последовательности из одних нулей в -компоненте равнялась нулю. Докажем, что Clean =.

пропорциональна -существенному ограничению меры. Тогда и проекции меры пропорцио­ нально -существенному ограничению меры по лемме 3.21. Действитель­ но, Тогда Clean по лемме 3.15 и Clean = так как две про­ порциональные вероятностные меры равны.

По леммам 3.7 и 3.10 отсюда следуют пропорциональности Аналогично можно убедиться в равенстве Clean =.

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

Итак, мера согласована с покомпонентым отношением порядка и имеет проекции, очистки которых равны мерам и соответственно. Тогда она доказывает, что и требовалось.

3.7.5. Доказательства лемм Приведём теперь доказательства лемм 3.14–3.22.

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

Докажем сначала в простую сторону.

Пусть дана инвариантная мера ; надо проверить, что её -существен­ ное ограничение удовлетворяет условиям.

Заметим сначала, что мера сверхслов, в которых в одной компоненте сколько-то ненулевых символов, но потом с какого-то места будут только нули, равна нулю.

Действительно, все варианты расположения начала хвоста из одних ну­ лей в этой компоненте несовместны и имеют одинаковую меру. Так как их счётное количество, все они имеют меру нуль.

Пусть = Restr. Проверим, что выполнено одно из равенств, а именно LeftShift =, после этого равенство RightShift = доказывает­ ся аналогично.

Фиксируем -существенное слово и будем доказывать равенство По мере вероятность того, что перед словом в -компоненте только нулевые символы, равна нулю. Тогда с вероятностью единица перед словом будет идти какое-то количество троек с нулевой - компонентой и пе­ ред ними тройка с ненулевой -компонентой. Это можно представить как равенство Проверим второе условие. Рассмотрим все возможные тонкие цилиндры со связным носителем, содержащим 0 и 1 и у которых содержание (то есть задаваемое слово) является (, 2) -существенным. Все они задают несовмест­ ные события, поэтому сумма их -мер не больше -меры всего простран­ ства (которая конечна). Теперь заметим, что мера тонкого цилиндра зависит содержания 1 раз.

Аналогично можно провести рассуждения для случая слов в алфавите пар символов, а не троек символов.

Пусть теперь дана функция и мы хотим построить по ней меру.

Определение 3.16. Пусть дано произвольное слово. Будем называть тон­ кий цилиндр со связным носителем и -существенным содержанием продол­ жением слова, если в позициях 0,..., || 1 он задаёт наличие слова.

Элементарным продолжением будем называть каждое максимальное по включению цилиндров продолжение (то есть продолжение, содержание кото­ рого не содержит в качестве подслова содержание другого продолжения).

Другими словами, элементарное продолжение задаёт на всех позициях носителя, кроме краёв и позиций 0... || 1, символ в -компоненте.

Аналогично определим элементарное продолжение тонкого цилиндра. Им является каждый содержащийся в тонкий цилиндр со связным носителем и -существенным содержанием.

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

Аналогично элементарным продолжениям определим элементарные про­ должения вправо и влево. Очевидно, что множество всех элементарных про­ должений слова — это множество всех элементарных продолжений вле­ во всевозможных цилиндров, являющихся элементарными продолжениями вправо слова.

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

Таким образом, с помощью элементарных продолжений мы определи­ ли значения искомой меры на всех словах, в том числе тех, у которых компонента не является существенной.

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

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

Для проверки аддитивности и инвариантности полученной меры надо проверить, что мера слова равна сумме мер всех его продолжений на один символ в какую-то одну сторону. Будем рассматривать, например, продолже­ ния вправо. Сначала предположим, что самый левый символ -компоненты ненулевой.

Если исходное слово имеет в качестве последнего символа -ком­ поненты, то все его элементарные продолжения содержат хотя бы один символ справа от самого правого символа, и сумма вероятностей элемен­ тарных продолжений односимвольных продолжений слова состоит из тех же слагаемых, что и просто сумма всех элементарных продолжений слова.

Если же -компонента заканчивается на ненулевой символ, то в сум­ му по элементарным продолжениям, определяющую меру слова, войдут меры всех способов приписать к -компоненте слова сколько-то нулей и ненулевой символ, а к двум другим компонентам — столько же произвольных символов.

Но такая сумма по первому свойству функции будет равна мере сло­ ва (мы сравниваем буквально значения на функции и её правого сдвига).

Общий случай легко сводится к частному случаю ненулевого самого ле­ вого символа. Действительно, пусть () — множество всех элементарных продолжений слова, а () и () — множество всех элементарных продолжений слова влево и вправо, соответственно. Нам надо доказать, что При этом нам уже известно, что если у слова 0 ненулевой самый левый символ -компоненты, то Вспомним, что -мера множества последовательностей, в которых, начиная с какого-то места, идут одни нули, равна нулю. Тогда Теперь заметим, что если бы на каком-то слове мера была бы беско­ нечна, то по аддитивности мера пустого слова была бы тоже бесконечна, а это неверно по второму свойству.

Лемма 3.14 доказана.

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

Пусть — инвариантная мера с данным -существенным ограничени­ ем, такая что множество сверхслов с -компонентой, содержащей только нули, имеет -меру 0.

В доказательстве леммы 3.14 мы установили, что и -мера множества сверхслов с бесконечным хвостом или началом из нулей равна нулю Для произвольного слова с хотя бы одним ненулевым символом в -компоненте мера имеет единственное возможное значение, так как мно­ жество всех сверхслов, содержащих и не содержащих бесконечного ко­ личества нулей подряд, является объединением элементарных продолжений слова.

Лемма 3.15 доказана.

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

Фиксируем параметр. Рассмотрим слова с хотя бы нулевыми сим­ волами подряд после -го ненулевого символа в -компоненте.

Сдвиги таких слов на 0,..., 1 описывают непересекающиеся цилин­ дры, так как ненулевой символ оказывается на месте нулевого или же сов­ мещаются разные ненулевые символы. Меры этих тонких цилиндров равны мере данного слова, а их сумма ограничена мерой всего пространства.

Всего возможных значений имеется штук, что не зависит от.

Мера всего пространства, делённая на и умноженная на является ( ) при фиксированном, что и требовалось доказать.

Лемма 3.16 доказана.

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

Чтобы при ноль-склейке двух слов получилось нулей подряд в нулей подряд в -компоненте компоненте, необходимо наличие хотя бы одного из склеиваемых слов. Более того, чтобы нулей подряд были после -го ненулевого символа, это же требование должно быть выполнено и для исходных слов.

Таким образом, сумма значений функции на всех словах, где в компоненте между -м и + -м ненулевыми символами есть хотя бы нулей подряд, не более 4, так как иначе мера всего пространства была бы больше единицы по хотя бы одной из исходных мер и.

Это свойство очевидно достаточно для равномерной лёгкости хвостов.

Кроме того, оно сохраняется при усреднении в ходе построения функций.

Лемма 3.17 доказана.

Доказательство леммы 3.18. Утверждение леммы является частным случаем утверждения леммы 3.5 о предельной точке. Лемма 3.18 доказана.

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

Равенство = RightShift верно из определения применения к щественным словам определялось с помощью правого сдвига).

Так как левый и правый сдвиг коммутируют, в разности левого и право­ го сдвига большинство слагаемых сократится и останется разность значений Это же можно записать как Лемма 3.19 доказана.

Доказательство леммы 3. является (, 2) -существенным то есть сумму вероятностей (, 2) -существенных слов по распределению 2, умноженных на количество нулей после -го ненулевого символа (плюс 1).

В каждом (, 2) -существенном слове из этой суммы слове сравним ко­ их (, ) -проекций, оценим количество нулей длиной этой очистки, а сум­ марную вероятность сгруппированных слов — вероятностью этой очистки по мере. Для остальных слов используем, -проекцию и меру.

Заметим, что каждая из двух сумм является суммой мер непересекаю­ щихся тонких цилиндров (умножение на количество нулей плюс 1 соответ­ ствует выбору нулевой позиции).

Получим оценку сверху искомой суммы удвоенной суммой двух конеч­ ных слагаемых.

Значения параметров и на оценку не влияют.

При переходе к происходит конечное усреднение сдвигов, которое не позволяет превысить общую для всех усредняемых верхнюю оценку.

Если бы это условие нарушилось для, то в какой-то допредельный момент мы бы превысили верхнюю оценку, справедливую для всех неза­ висимо от номера, что невозможно.

Лемма 3.20 доказана.

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

В левой части и правой частях равенства стоят функции, значение кото­ рых на данном существенном слове равно одной и той же сумме. А именно, сумме альфа-мер всех существенных слов, из которых после удаления всех пар нулей получается. Значение обеих функций на несущественных словах равно нулю по определению.

Лемма 3.21 доказана.

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

Первое равенство, Clean, = PRestr,, следует из того, что мы порождаем случайное -существенное слово по мере, добавляем в него нули по какому-то распределению, после чего приписываем -компо­ ненту. Тогда стирание всего добавленного должно дать исходно порождённое слово.

Отсюда следует равенство Поскольку существенное ограничение инвариантной меры не меняется при сдвигах, правая часть равна Restr,, что доказывает второе равенство леммы.

Третье равенство (для ) получается из второго усреднением левой и правой части (при этом используется то, что левый и правый сдвиги комму­ тируют с проекцией и существенной очисткой).

Четвёртое равенство (для ) получается переходом к пределу в последо­ вательности равномерно сходящихся рядов. В качестве ряда мы рассматрива­ ем ряд из определения сдвига. Равномерная сходимость выполнена по следую­ щей причине. При фиксированном значении у нас имеется ряд из неотри­ цательных слагаемых, который мы можем переупорядочить произвольным удобным нам способом. Упорядочим по возрастанию максимального коли­ чества нулей подряд в -компоненте. По лемме 3.17 имеется равномерная оценка на сумму всего остатка ряда, не зависящая от номера члена в по­ следовательности. Но сумма поточечного предела абсолютно и равномерно сходящихся рядов равна пределу сумм, что и требовалось доказать.

Лемма 3.22 доказана.

Таким образом, леммы 3.14–3.22 доказаны.

Замечание 3.7. Данное доказательство нетрудно обобщить на случай, когда порядок имеет чуть более общий вид. Например, можно брать в определении вместо Clean какой-то Clean, причём разрешать встав­ лять между символами исходного слова не любые конечные слова над, а только слова из некоторого множества * со следующим свой­ ством: 1 2, = 1 2. Кроме того, в качестве порядка на “неочищенных” словах можно брать не, а любой транзитивный порядок.

3.8. Возможные применения отношения Итак, мы доказали, что отношение транзитивно. Очевидно, что оно удовлетворяет также второму и третьему условию на стр. 20. Таким образом для доказательства гипотезы 1 остается установить, что хотя бы один из двух операторов Тоома монотонен относительно.

Поскольку эти операторы есть композиции операторов Ann, Flip, Flip+, достаточно доказать монотонность оператора Ann и хотя бы одного из опе­ раторов Flip, Flip+. Первое мы умеем делать. Верно ли второе, остаётся неясным.

Теорема 3.4. Оператор Ann = Duel Clean является монотонным отно­ сительно.

Доказательство. Будем рассматривать операторы на мерах на сло­ вах из символов {, }, задаваемые парами из отображения (которое мы тоже будем обозначать ) и меры (на последовательностях, возможно, другого алфавита). Аргументы отображения — последовательность симво­ лов и дополнительная случайная последовательность (которая будет предпо­ лагаться распределённой по ), а значение — последовательность символов.

Если мы хотим применить оператор к мере, то надо построить меру прямого произведения на произведении пространства входных последовательностей и пространства дополнительных случайных последовательностей, распределён­ ных по, после чего перенести её в пространство последовательностей при помощи отображения.

Заметим, что оператор Duel действует на сверхслово, разбивая его на блоки (детерминированным образом), после чего заменяя каждый блок слу­ чайным образом независимо от других на блок той же длины. Поэтому он имеет указанный в предыдущем абзаце вид.

Мы хотим получить средство для доказательства монотонности Clean по отношению к. Для этого нам достаточно существования оператора, который будет это конструктивно доказывать, то есть меру, существо­ вание которой требуется при проверке неравенства на аргументах, преобра­ зовывать в меру, существование которой означает нужное неравенство на результаты применения оператора. Первым аргументом отображения будут являться последовательности в алфавите из пар букв, в которых верх­ няя буква больше или равна нижней, а одиночные буквы теперь берутся из {,, }. Вторым аргументом будет дополнительная последовательность (которая опять будет предполагаться распределённой по ). Принимаемые значения — последовательности в том же алфавите пар букв.

Лемма 3.23. Пусть для и выполняются следующие условия:

1) Для любых мер инвариантной меры на словах над алфавитом из пар символов {,, } с первой проекцией, равной и второй проекцией, равной, образы проек­ ций при Clean равны Clean и Clean, соответственно. Здесь и понимаются как операторы, и распределение дополнительного случайного аргумента (из определения как оператора на мерах).

2) Для любого сверхслова над алфавитом пар символов, такого что первая компонента больше либо равна второй, это же неравенство выполнено для его образа при.

Доказательство. Если мера является мерой, существование которой подтверждает отношение между их образами. Лемма 3.23 доказана.

Нам достаточно построить оператор, обладающий свойствами, описанными в предыдущей лемме.

Пусть задана последовательность в алфавите пар символов и допол­ нительная случайная последовательность из нулей и единиц (на каждом месте выбор делается независимо, и вероятность единицы равна ). Теперь опишем, как вычисляются компоненты пары, стоящей на заданном месте в образе.

Каждый символ из верхней и нижней компоненты будет либо оста­ ваться неизменным, либо заменяться на по следующему правилу. Рассмот­ рим по отдельности верхнюю и нижнюю компоненту. Назовём “связанны­ ми” те символы, которые входят в подслова вида, 0. Остальные символы будем считать “свободными”. Будем считать, что блок — это либо, либо отдельный свободный символ. Заметим, что возможна ситуация, например,, когда свободный символ стоит над связанным, и наобо­ рот. Свободные символы всегда переносятся в образ без изменений. Теперь определим, что происходит с блоками. К некоторым из них будет применена операция обнуления, то есть замены каждого символа блока на. Для того, чтобы образы блоков были независимы внутри верхней и нижней компонен­ ты, будем требовать, чтобы образ блока зависел только то символов, стоящих в и в на позициях, занимаемых рассматриваемым блоком. Для того, чтобы одновременно сохранить неравенство между верхней и нижней ком­ понентой и при этом получить правильные вероятности превращений, будем привязывать обнуление нижнего блока к обнулению верхнего блока, который мог бы обнулиться и испортить неравенство.

Если рассматривается блок в верхней компоненте, то просто заменим его на блок из одних нулей, если над его первым символом ( ) стоит единица.

Ясно, что каждый блок сохраняется с вероятностью 1 и обнуляется с вероятностью, что не отличается от происходящего при.

Теперь рассмотрим блок в нижней компоненте. Во-первых, возможно, что над последним символом блока ( ) стоит тоже. Тогда рассмотрим слово, стоящее над всем блоком. Оно начинается с, так только он разре­ шён над. Оно не содержит, кроме последнего символа, потому что разрешён только над. Таким образом,мы получаем. В любом случае, в верхней компоненте является связанным, и соответствующий ему лежит в пределах рассматриваемого блока. Кроме того, если левый в верхней компоненте связан, то он связан с правым в верхней компоненте.

Поэтому в этом случае будем рассматривать в крайней правой позиции фрагмента над блоком в верхней компоненте, находить парный ему и об­ нулять блок тогда и только тогда, когда на ( плюсу, в стоит 1. Например, для случая нам надо рассмотреть символ в на первой позиции, а для — на третьей.

Пусть теперь у нас есть блок в нижней компоненте, над последним сим­ волом которого стоит не. В этом случае над первым символом (которым является ) стоит, и мы обнулим блок, если на этой позиции в стоит 1.

Заметим, что мы сначала, не обращаясь к, определяем одну позицию внутри блока, проверяем символ в на этой позиции, и потом в соответствии с ним обнуляем или нет блок. Распределение вероятностей образов в любом случае соответствует считыванию одного символа из.

Теперь проверим неравенство между последовательностями. Если оба символа перенесены или оба обнулены, то проверять ничего не надо — по предположению, что вначале неравенство верно или потому, что. Ес­ ли при обнулении одного символа в паре верхний не уменьшился, а нижний не увеличился, то опять неравенство сохранится. Более того, если один из символов был уже, или если была пара, то неравенство будет выпол­ нено. Итак, нам надо доказать, что если в обнулился верхний символ или в обнулился нижний, то и второй тоже обнулился.

Рассмотрим сначала случай. Если нижний обнулился, то он свя­ занный, но верхний, как мы уже знаем, тоже связан. Более того, их обнуление зависит от одного и того же символа в, что и требовалось доказать.

Теперь рассмотрим случай. Верхний обнулился, значит, он свя­ занный. Рассмотрим слово вида, в которое он входит. Мы знаем, что под его первым символом стоит. Под его последним символом стоит, разумеется,. В середине — под — могут быть и. Поэтому, стоящий под первым, связанный. Докажем, что его обнуление зависит от того, что стоит в на той самой позиции, где он сам находится. Действитель­ но, чтобы это было не так, соответствующий ему должен стоять под.

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

Теорема 3.4 доказана.

1. M.Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, 2002.

2. Притыкин Ю. Л. Конечно-автоматные преобразования строго почти пе­ риодических последовательностей // Математические заметки. 2006.

Т. 80, № 5. С. 751–756.

3. Muchnik A., Semenov A., Ushakov M. Almost periodic sequences // Theoret­ ical Computer Science. 2003. Vol. 304. P. 1–33.

4. Притыкин Ю. Почти периодичность, конечно-автоматные преобразова­ ния и вопросы эффективности // Известия вузов. Математика. 2010.

Т. 1. С. 74–87.

5. Притыкин Ю. Действие конечных автоматов на почти периодические последовательности. доклад на Колмогоровском семинаре. 2005.

6. Шень А. Редкие множества. доклад на Колмогоровском семинаре. 2009.

7. Н.К. Верещагин, В.А. Успенский, Шень А. Колмогоровская сложность и алгоритмтическая случайность. М.: МЦНМО, 2012.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:

МЦНМО, 2001.

9. Bienvenu L., Romashchenko A., Shen A. Sparse sets // Proceedings of Sym­ posium on Cellular Automata, Journes Automates Cellulaires (JAC 2008).

2008. P. 18–28.

10. Makarychev K., Makarychev Y., Romashchenko A., Vereshchagin N. A new class of non Shannon type inequalities for entropies // Communications in Information and Systems. 2002. Vol. 2, no. 2. P. 147–166.

11. Тоом А. Устойчивые и притягивающие траектории в многокомпонентных системах // Многокомпонентные системы / Ed. by Р. Л. Добрушин.

Москва: Наука, 1978.

12. Gcs P. Reliable Cellular Automata with Self-Organization // Journal of Statistical Physics. 2001. Vol. 103, no. 1/2. P. 45–267.

13. Toom A. Non-ergodicity in a 1-D particle process with variable length // Journal of Stat. Physics. 2004. Vol. 115. P. 895–924.

14. Тоом А. Клеточные автоматы. НМУ, спецкурс. 2004.

15. Н.К. Верещагин, Шень А. Вычислимые функции. 2-е изд. М.: МЦНМО, 2008.

Список публикаций автора по теме диссертации 16. Pаскин М. А. О нижней оценке регулятора прямого произведения почти периодической и периодической последовательностей // Вестник Москов­ ского Университета. Серия 1. Математика и механика. 2011. № 6. С. 7–11.

17. Pаскин М. А. Согласованная с отношением порядка копроекция вычис­ лимых мер не всегда вычислима // Вестник Московского Университета.

Серия 1. Математика и механика. 2012. № 2. С. 17–19.

18. Pаскин М. А. Частичный порядок Тоома транзитивен // Проблемы пере­ дачи информации. 2012. Т. 48, № 2. С. 79–99.