Сверхслова, меры на них и их полупрямые произведения (1104768), страница 14
Текст из файла (страница 14)
Действительно, пусть () — множество всех элементарныхпродолжений слова , а () и () — множество всех элементарныхпродолжений слова влево и вправо, соответственно. Нам надо доказать,что∀ : () =∑︁( * ).{︂ ⊕ ⊕⊖ }︂∈ ⊕ , ⊕ ,..., ⊖⊕ ⊙⊖При этом нам уже известно, что если у слова 0 ненулевой самый левыйсимвол -компоненты, то(0 ) =∑︁{︂ ⊕⊖ }︂∈ ⊕ ,..., ⊖⊕⊖(0 * ).Вспомним, что -мера множества последовательностей, в которых, начинаяс какого-то места, идут одни нули, равна нулю. Тогда∑︁∑︁∑︁() =(0 ) =(0 * ) =0 ∈ ()=∑︁∑︁{︂⊕⊖ }︂ 0 ∈ ()∈ ⊕ ,...,⊖⊕⊖0 ∈ ()(0 * ) ={︂⊕⊖ }︂∈ ⊕ ,...,⊖⊕⊖∑︁∑︁() ={︂⊕⊖ }︂ ∈ (*)∈ ⊕ ,...,⊖⊕⊖=∑︁{︂⊕⊖ }︂∈ ⊕ ,...,⊖⊕⊖( * ).88Теперь заметим, что если бы на каком-то слове мера была бы бесконечна, то по аддитивности мера пустого слова была бы тоже бесконечна, аэто неверно по второму свойству .Лемма 3.14 доказана.Доказательство леммы 3.15.Пусть — инвариантная мера с данным -существенным ограничением , такая что множество сверхслов с -компонентой, содержащей тольконули, имеет -меру 0.В доказательстве леммы 3.14 мы установили, что и -мера множествасверхслов с бесконечным хвостом или началом из нулей равна нулюДля произвольного слова с хотя бы одним ненулевым символом в -компоненте мера имеет единственное возможное значение, так как множество всех сверхслов, содержащих и не содержащих бесконечного количества нулей подряд, является объединением элементарных продолженийслова .Лемма 3.15 доказана.Доказательство леммы 3.16.Фиксируем параметр .
Рассмотрим слова с хотя бы нулевыми символами подряд после -го ненулевого символа в -компоненте.Сдвиги таких слов на 0, . . . , − 1 описывают непересекающиеся цилиндры, так как ненулевой символ оказывается на месте нулевого или же совмещаются разные ненулевые символы. Меры этих тонких цилиндров равнымере данного слова, а их сумма ограничена мерой всего пространства.Всего возможных значений имеется штук, что не зависит от .Мера всего пространства, делённая на и умноженная на является( 1 ) при фиксированном , что и требовалось доказать.Лемма 3.16 доказана.Доказательство леммы 3.17.Чтобы при ноль-склейке двух слов получилось нулей подряд в компоненте, необходимо наличие хотя бы2нулей подряд в -компонентеодного из склеиваемых слов. Более того, чтобы нулей подряд были после89 -го ненулевого символа, это же требование должно быть выполнено и дляисходных слов.Таким образом, сумма значений функции на всех словах, где в компоненте между -м и + -м ненулевыми символами есть хотя бы нулей подряд, не более 4 ×, так как иначе мера всего пространства былабы больше единицы по хотя бы одной из исходных мер и .Это свойство очевидно достаточно для равномерной лёгкости хвостов.Кроме того, оно сохраняется при усреднении в ходе построения функций ′ .Лемма 3.17 доказана.Доказательство леммы 3.18.
Утверждение леммы является частнымслучаем утверждения леммы 3.5 о предельной точке. Лемма 3.18 доказана.Доказательство леммы 3.19.Равенство ′ = RightShift′ верно из определения применения ′ к(, 6 ) -существенным словам. (Напомним, что применение к (, 6 ) -существенным словам определялось с помощью правого сдвига).Так как левый и правый сдвиг коммутируют, в разности левого и правого сдвига большинство слагаемых сократится и останется разность значенийраспределений, умноженная на1.Это же можно записать какRightShift′ − LeftShift′ =1 ∑︁RightShift LeftShift− 2 −= RightShift =01 ∑︁−LeftShiftRightShift LeftShift− 2 = =0+11 ∑︁RightShift LeftShift−+1 2 −= =11 ∑︁−RightShift LeftShift−+1 2 = =0=1(RightShift+1 2 − LeftShift+1 2 ).Но эта функция ограничена сверху по абсолютной величине числом1.90Лемма 3.19 доказана.Доказательство леммы 3.20Фиксируем 6 − 2 .
Сначала нам надо оценить∑︁ является (, 2) -существенным(|| − 1) × LeftShift RightShift−−2 2 (),то есть сумму вероятностей (, 2) -существенных слов по распределению2 , умноженных на количество нулей после -го ненулевого символа (плюс1).В каждом (, 2) -существенном слове из этой суммы слове сравним количество символовсимволов⊙⊙⊙⊙в , - и (, ) -проекциях. Первые (где количествобольше в , -проекции) сгруппируем по очистке от пары⊙⊙их (, ) -проекций, оценим количество нулей длиной этой очистки, а суммарную вероятность сгруппированных слов — вероятностью этой очистки помере . Для остальных слов используем , -проекцию и меру .Заметим, что каждая из двух сумм является суммой мер непересекающихся тонких цилиндров (умножение на количество нулей плюс 1 соответствует выбору нулевой позиции).Получим оценку сверху искомой суммы удвоенной суммой двух конечных слагаемых.Значения параметров и на оценку не влияют.При переходе к ′ происходит конечное усреднение сдвигов, которое непозволяет превысить общую для всех усредняемых верхнюю оценку.Если бы это условие нарушилось для , то в какой-то допредельныймомент мы бы превысили верхнюю оценку, справедливую для всех ′ независимо от номера, что невозможно.Лемма 3.20 доказана.Доказательство леммы 3.21.В левой части и правой частях равенства стоят функции, значение которых на данном существенном слове равно одной и той же сумме.
А именно,сумме альфа-мер всех существенных слов , из которых после удаления всехпар нулей получается . Значение обеих функций на несущественных словах91равно нулю по определению.Лемма 3.21 доказана.Доказательство леммы 3.22.−{︂ ⊙ }︂Первое равенство, Clean∘, = PRestr,− , следует из того,⊙⊙что мы порождаем случайное -существенное слово по мере , добавляемв него нули по какому-то распределению, после чего приписываем -компоненту. Тогда стирание всего добавленного должно дать исходно порождённоеслово.Отсюда следует равенство−{︂⊙ }︂++ =LeftShift RightShift Clean∘,⊙*= LeftShift RightShift Restr,++− .Поскольку существенное ограничение инвариантной меры не меняется присдвигах, правая часть равна Restr,− , что доказывает второе равенстволеммы.Третье равенство (для ′ ) получается из второго усреднением левой иправой части (при этом используется то, что левый и правый сдвиги коммутируют с проекцией и существенной очисткой).Четвёртое равенство (для ) получается переходом к пределу в последовательности равномерно сходящихся рядов.
В качестве ряда мы рассматриваем ряд из определения сдвига. Равномерная сходимость выполнена по следующей причине. При фиксированном значении у нас имеется ряд из неотрицательных слагаемых, который мы можем переупорядочить произвольнымудобным нам способом. Упорядочим по возрастанию максимального количества нулей подряд в -компоненте. По лемме 3.17 имеется равномернаяоценка на сумму всего остатка ряда, не зависящая от номера члена в последовательности.
Но сумма поточечного предела абсолютно и равномерносходящихся рядов равна пределу сумм, что и требовалось доказать.Лемма 3.22 доказана.Таким образом, леммы 3.14–3.22 доказаны.92Замечание 3.7. Данное доказательство нетрудно обобщить на случай,когда порядок D имеет чуть более общий вид. Например, можно братьв определении вместо Clean какой-то Clean , причём разрешать вставлять между символами исходного слова не любые конечные слова над ,а только слова из некоторого множества ⊂ * со следующим свойством: 1 2 , ∈ =⇒ 1 2 ∈ .
Кроме того, в качестве порядка на“неочищенных” словах можно брать не > , а любой транзитивный порядок.3.8. Возможные применения отношения DИтак, мы доказали, что отношение D транзитивно. Очевидно, что оноудовлетворяет также второму и третьему условию на стр. 20. Таким образомдля доказательства гипотезы 1 остается установить, что хотя бы один из двухоператоров Тоома монотонен относительно D .Поскольку эти операторы есть композиции операторов Ann , Flip , Flip+ ,достаточно доказать монотонность оператора Ann и хотя бы одного из операторов Flip , Flip+ . Первое мы умеем делать. Верно ли второе, остаётсянеясным.Теорема 3.4. Оператор Ann = Duel ∘ Clean является монотонным относительно D .Доказательство.
Будем рассматривать операторы на мерах на словах из символов {⊕, ⊖} , задаваемые парами из отображения (которое мытоже будем обозначать ) и меры (на последовательностях, возможно,другого алфавита). Аргументы отображения — последовательность символов и дополнительная случайная последовательность (которая будет предполагаться распределённой по ), а значение — последовательность символов.Если мы хотим применить оператор к мере, то надо построить меру прямогопроизведения на произведении пространства входных последовательностей ипространства дополнительных случайных последовательностей, распределённых по , после чего перенести её в пространство последовательностей припомощи отображения .93Заметим, что оператор Duel действует на сверхслово, разбивая его наблоки (детерминированным образом), после чего заменяя каждый блок случайным образом независимо от других на блок той же длины.
Поэтому онимеет указанный в предыдущем абзаце вид.Мы хотим получить средство для доказательства монотонности ∘Cleanпо отношению к D . Для этого нам достаточно существования оператора , который будет это конструктивно доказывать, то есть меру, существование которой требуется при проверке неравенства на аргументах, преобразовывать в меру, существование которой означает нужное неравенство нарезультаты применения оператора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
