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

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

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

ТогдаClean⊙ = , Clean⊙ = , Clean⊙ = , Clean⊙ = . Меры и , заданные на , отличаются тем, из какой меры они получены: мера — проекция меры на пространстве × , а — проекция меры напространстве × .По лемме 3.11, не ограничивая общности, можно считать, что и , и инвариантны,(︁ )︁приписывают нулевую вероятность множеству сверхслов, со­держащих ⊙⊙ , а их проекции приписывают нулевую вероятность слову изодних нулей.Опишем общий план доказательства.Идея в том, чтобы построить нужную функцию в самом простом случае,а потом решать возникающие проблемы с помощью усреднений и перехода кпредельной точке.74Мы построим объединённую меру в алфавите троек символов, такуючто очистка от⊙⊙её проекции на первые две компоненты даёт меру , а навторые две — меру .

То есть, мы хотим добиться того, что Clean ⊙ = ⊙и Clean ⊙ = .⊙Определение 3.8. Слово в алфавите {⊕, ⊙, ⊖} называется существенным,если оно не начинается и не заканчивается на ⊙ .Слово в алфавите пар или троек символов называется -существен­ным, если его -компонента существенная. Такое слово называется (, ) существенным, если количество ненулевых символов в -компоненте рав­но . Если количество ненулевых символов в -компоненте существенно­го слова не превышает , будем называть такое слово (, 6 ) -существен­ным.Проекции мер и на -компоненту отличаются только добавлениемнулей в некоторых местах. Мы хотим так добавить в случайные по мерам и последовательности символыодинаково распределены.⊙⊙, чтобы их -компоненты оказалисьСначала мы рассмотрим только слова с существенной -компонентой,так как для них легко определить количества нулей между соседними нену­левыми символами без рассмотрения краёв.Пусть есть два -существенных слова и в алфавите пар символов(мы считаем, что у первого есть компоненты и , а у второго слова —компоненты и ).

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

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

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

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

Формальное описание конструкцииОпишем теперь конструкцию формально.Определение 3.9. Будем обозначать проекцию меры на набор компонент как () . В качестве иллюстрации скажем, что выполняются равенства, () = и Clean⊙ () = Clean⊙ () .Аналогично будем обозначать и проекции слов.76Определение 3.10. Пусть дана инвариантная мера на пространстве дву­сторонних бесконечных последовательностей пар символов. Будем называть -существенным ограничением меры функцию, являющуюся ограниче­нием меры как функции на словах на множество -существенных слов.Будем обозначать такую функцию Restr − . Аналогично определяется(, ) -существенное ограничение, обозначаемое Restr,− .Нормированное (, ) -существенное ограничение меры получается изеё (, ) -существенного ограничения делением на меру наличия ненулевогосимвола в позиции 0 в -компоненте (то есть на ({0 ̸= ⊙}) ).

Обозначение:PRestr,− . (Буква P в обозначении от слова probabilistic).Данное определение применимо для меры с компонентами и (имеры с компонентами , и ).Замечание 3.4. Нормированное (, ) -существенное ограничение инвари­антной меры является распределением вероятностей на множестве (, ) существенных слов.Определение 3.11. Пусть функция задаёт меру на (, ) -существенныхсловах.

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

При этом мы нетребуем, чтобы при разных значениях параметра значения функции ()для (, ) -существенных слов были как-то согласованы.77Аналогично определяется правый сдвиг , обозначаемый RightShift .Замечание 3.5. Легко видеть, что левый и правый сдвиг коммутируют.Определение 3.12. Пусть дана мера на (, ) -существенных словах.Определим её применение к (, 6 ) -существенным словам. Каждое такоеслово будем отождествлять со множеством всех его продолжений вправо до(, ) -существенного слова. Иначе говоря, если слово является (, ) существенным, положим по определению ( ) = (RightShift− )( ) .Определение 3.13. Пусть дано (, ) -существенное слово с компонента­ми и и (, ) -существенное слово с компонентами и , причёмочистки их -компонент равны, Clean⊙ = Clean⊙ .Будем называть их ноль-склейкой и обозначать Join⊙ (, ) последова­тельность, полученную следующим алгоритмом. Для каждого < послепозиции -го ненулевого символа в -компоненте слова вставим в слово столько символов⊙⊙, сколько символов ⊙ стоит в -компоненте слова после -го ненулевого символа, и наоборот.При этом мы получим два слова ′ , ′ с одинаковой -компонентой.Отождествим их -компоненты и получим слово с компонентами , , ,которое обозначается Join⊙ (, ) .78⊙ y2⊙ y1⊙⊙ y1⊙⊙⊙ y2y0⊙⊙⊙⊙ y1y0⊙⊙ y1⊙y0⊙⊙y0⊙y0y0⊙⊙⊙⊙⊙⊙⊙⊙⊙⊙⊙ y1⊙⊙⊙⊙⊙⊙ y1⊙⊙⊙⊙⊙ y2⊙ y2⊙⊙⊙⊙⊙⊙⊙⊙ y2⊙⊙⊙⊙⊙ y2⊙⊙Иллюстрация действия Join⊙Определение 3.14.

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

На остальных (, ) -существенных словах она определяется (по ана­логии с Clean ) по формуле−(Clean∘, )() =Δ∑︁∈SpliceΔ () ().79Как и в случае со сдвигами, будем задавать той же формулой значение−(Clean∘, )() для , определённой на множествах (, ) -существен­Δных слов при ∈ .Пусть заданы меры D D . Пусть меры и доказывают этинеравенства. Будем считать меры и инвариантными и приписывающимимеру 0 слову⊙⊙и сверхслову из одних нулей в каждой из компонент (какмы ранее показали, это не ограничивает общность).Для каждого мы рассмотрим нормированные (, ) -существенныеограничения мер и и обозначим их через и .

Рассмотрим случай­ное слово длины по мере . После этого возьмём случайные слова и по условным распределениям и при условии равенства очистки компоненты слову . Рассмотрим Join⊙ (, ) . Обозначим распределение насловах Join⊙ (, ) , полученное таким образом, через .К сожалению, функции могут оказаться не согласованы между собой(то есть RightShift+1 ̸= ) и не инвариантны (то есть LeftShift ̸=∑︀RightShift LeftShift− 2 .RightShift ). Поэтому мы рассмотрим ′ = 1=0Эти функции будут приблизительно инвариантны (с точностью1).Рассматривая ′ как функцию на (, 6 ) -существенных словах можноопределить как предельную точку ′ , то есть функцию на -существен­ных словах, к которой поточечно сходится некоторая подпоследовательностьпоследовательности ′ .

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

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

Тогда легко видеть, что , -проекция меры доказывает неравен­ство D .Перейдём к точным формулировкам. Сначала мы сформулируем неко­торые леммы, потом мы объясним как из лемм следует теорема, и в самомконце мы докажем леммы.3.7.3. Формулировки леммЛемма 3.14. Неотрицательная функция на -существенных словах яв­ляется -существенным ограничением какой-то инвариантной меры тогда итолько тогда когда выполнены следующие условия:Во-первых, функция удовлетворяет условиям самосогласованности,аналогичным инвариантности и аддитивности, а именноLeftShift = RightShift = .Другими словами, оба её сдвига равны самой функции.Во-вторых, сумма значений функции на (, 2) -существенных словах,умноженных на их длину без единицы, должна быть конечна. Это соответ­ствует тому, что сумма значений на всех продолжениях пустого слова должнабыть конечна как мера всего пространства.

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

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