Сверхслова, меры на них и их полупрямые произведения (1104768), страница 9
Текст из файла (страница 9)
Определим оператор Clean . Сделаем это сразу в общемслучае — определим оператор стирания всех символов из множества Δ ⊂Σ в сверхсловах над Σ . Мы предполагаем, что вероятность наличия налюбой заданной позиции символа из Δ не равна 1 .Вероятность по мере CleanΔ непустого слова 0 . . . над алфавитом Σ ∖ Δ задается следующей формулой:=11−(Δ)(CleanΔ )(0 .
. . ) =∑︀(0 * 1 * 1 * 2 * . . . * * ).1 ,..., ∈Δ*В этой формуле — произвольные символы из алфавита Σ ∖ Δ . Другими словами, вхождению заданного слова в любой данной позиции мера CleanΔ приписывает вероятность, равную сумме вероятностей всехслов, которые можно получить из вставкой элементов Δ в произвольном количестве между буквами, поделённой на суммарную вероятностьсимволов не из Δ .Вероятность по мере CleanΔ пустого слова по определению равна 1 .Для мер, не являющихся вероятностными, можно говорить об операторе Clean∘ очистки без нормировочного множителя11−(Δ).Более того, это же определение можно применять и к функциям насловах.
Желательно, чтобы слова, отличающиеся только добавлением иудалением нулевых символов, входили или не входили в область определенияодновременно.Определение 3.4. Обозначим для всякого слова в алфавите Σ ∖ Δ черезSpliceΔ () множество всех слов, которые можно получить из вставкоймежду символами символов из Δ в произвольном порядке и количестве.Замечание 3.1. Можно определить оператор CleanΔ и другим способом,дающим тот же результат на основании неформального описания оператора как “вычёркивания нулей”. Сначала рассмотрим условную меру 1 ,58полученную ограничением на сверхслова, в которых в начале координатсимвол не из Δ . Для любого сверхслова с таким свойством корректно определено вычёркивание всех вхождений символов из Δ со сдвигом к началукоординат.
Нетрудно убедиться, что образ 1 под действием отображения вычёркивания равен CleanΔ . Коэффициент 1 − (Δ) в формуле дляCleanΔ () есть как раз вероятность условия “в начале координат стоитсимвол не из Δ ”.Замечание 3.2. Оператор Clean линеен.Лемма 3.2. Определение 3.3 для любой инвариантной меры задаёт инвариантную вероятностную меру.Доказательство. Нам нужно доказать, что вероятность по мере CleanΔ любого слова (включая пустое) равна сумме мер всех слов, полученных приписыванием к исходному слову с заданной стороны одной буквы из Σ ∖ Δ .Для пустого слова это требование обеспечивается нормирующим множителем11−(Δ).
Для непустых слов нам понадобится следующее определение.С помощью обозначения 3.4 мы можем написать, что(CleanΔ )() =11 − (Δ)∑︁(′ ).′ ∈SpliceΔ ()Таким образом, для проверки того, что мера слова равна сумме мер всехслов, полученных приписыванием слева к исходному слову любой буквы изΣ ∖ Δ , нам нужно установить следующее равенство:∑︁(′ ) =′ ∈SpliceΔ ()∑︁∑︁(′′ ).∈Σ∖Δ ′′ ∈SpliceΔ (*)Множество SpliceΔ ( * ) состоит в точности из всех слов вида * * ′ , где ∈ Δ* и ′ ∈ SpliceΔ () . Поэтому нам достаточно доказать, что при любомфиксированном ′ ∈ SpliceΔ () имеет место равенство(′ ) =∑︁ ∑︁∈Σ∖Δ ∈Δ*( * * ′ ).59Чем отличаются левая и правая части этого равенства? В левой части стоит -вероятность события “сверхслово содержит подслово ′ , начиная с нулевойпозиции”. В правой части стоит -вероятность пересечения того же событияс событием “в какой-то позиции с отрицательным номером имеется символиз Σ ∖ Δ ”.
Вероятности этих двух событий совпадают. В самом деле, мераинвариантна относительно сдвигов, вхождения слова из бесконечного концанулевых символов и одного ненулевого символа на различных позициях образуют счётный набор взаимоисключающих событий.Аналогичное рассуждение применимо для приписывания букв справа.Лемма 3.2 доказана.Таким образом, мы определили оператор Clean . Операторы Duel , Flipи Flip+ не требуют такого уточнения, а оператор Ann определяется какClean⊙ ∘ Duel .3.5. Частичный порядок > на инвариантных мерахОпределение 3.5. Тонкий цилиндр над упорядоченным алфавитом Σ называется большим либо равным другому тонкому цилиндру с тем же носителем если на каждой позиции носителя первый цилиндр задаёт большийлибо равный символ, чем второй цилиндр.
Для инвариантных вероятностных и на сверхсловах над упорядоченным алфавитом Σ мы пишем > , если существует полупрямое произведение мер и (не обязательно инвариантное), согласованное с отношением порядка > (здесь важно,что меры полностью определяются своими значениями на тонких цилиндрах). Другими словами, должна существовать мера на сверхсловах надалфавитом из пар букв с проекциями, равными и соответственно,для которой вероятность того, что первый символ в паре больше или равен второму, равна(︁1 .)︁(Для слов в алфавите {⊕, ⊖} это означает, что помере сверхслово ⊖должно иметь нулевую вероятность).⊕Проекция в этом определении понимается в следующем смысле.
Каждому слову над декартовым квадратом данного алфавита (алфавита пар букв)60соответствуетпара слов одной длины над этим алфавитом. Например, слову(︁ )︁⊕⊙соответствует пара слов (⊕⊙, ⊙⊖) . Такое же соответствие имеется⊙⊖и между последовательностями над декартовым квадратом алфавита и парами последовательностей над самим алфавитом. Благодаря этому каждоймере на последовательностях над декартовым квадратом соответствует мера на парах последовательностей над исходным алфавитом.
Первой (второй)проекцией меры называется мера, по которой распределены первые (вторые) компоненты пар случайно выбранной по этой мере последовательности.Если исходная мера инвариантна, то и обе ее проекции инвариантны.Теорема 3.2. Отношение > на мерах удовлетворяет первому и третьемуусловиям на стр. 20, но не удовлетворяет четвертому.Замечание 3.3. Если считать, что в операторе Тоома Flip происходитпосле Ann , то выполнение второго условия очевидно: Flip+ отличаетсяот Flip заменой некоторых минусов (обратно) на плюсы. Иначе вопросстановится достаточно сложным из-за немонотонности Clean и, соответственно, Ann . Этот вопрос мы рассматривать в данной работе небудем.Доказательство.
Докажем сначала первое условие (транзитивность).Пусть даны инвариантные вероятностные меры , , такие, что > > . Значит, существует полупрямое произведение мер , , согласованное с порядком, а также полупрямое произведение мер , , согласованноес порядком. Нам нужно установить существование полупрямого произведения мер , , согласованного с порядком.Это легко доказать для вероятностных мер на конечных множествах.
Аименно, пусть , , — распределения вероятностей на некотором конечномупорядоченном множестве . Тогда можно определить распределение вероятностей на 3 обладающие следующими двумя свойствами:1) проекция на первую и вторую координаты равна ,2) проекция на вторую и третью координаты равна .61Например, можно определить формулой(︃ )︃ (︃ )︃⎛ ⎞⎜ ⎟⎟=⎜.⎝ ⎠()⎛⎞⎜ ⎟⎟Это распределение соответствует такому процессу порождения слова ⎜⎝ ⎠:мы сначала выбираем случайно , используя вероятностную меру .
Затеммы выбираем случайно по условному распределению на первой координате при условии, что вторая координата равна уже выбранному . Наконец,мы независимо выбираем по условному распределению на второй координате при известной первой.Из свойств следует, что с вероятностью 1 относительно будут выполнены неравенства > > . Поэтому в качестве искомой меры можновзять проекцию на первую и третью координаты.Для дальнейшего важно понимать, что мера не определяется однозначно условиями 1) и 2). Пусть например = {0, 1} и обе меры , сутьравномерное распределение на множестве 2 .
Тогда построенная нами мера является равномерным распределением на 3 . При этом существуети другая мера со свойствами 1) и 2), например, равномерное распределение на множестве всех троек из 3 , у которых первая и третья координатасовпадают.Перейдем теперь к случаю мер на пространстве двусторонних последовательностей. Мы знаем два доказательства транзитивности и оба они неконструктивны в том смысле, что мера не строится явно по данным мерам и .Неконструктивность возникает из-за применения следующей леммы (предельная точка, существование которой утверждает лемма, может быть неединственна).62Лемма 3.3.
Последовательность счётных последовательностей вещественных чисел из заданного отрезка имеет предельную точку (с точки зренияпоточечной сходимости).Доказательство. Будем вычёркивать некоторые последовательности, а некоторые будем отбирать как участвующие в сходимости к предельной точке.Вначале мы ничего не выбрали и не вычеркнули.Мы будем бесконечно повторять один и тот же шаг, меняя множествавыбранных и вычеркнутых последовательностей.На -м шаге шаге мы смотрим на элементы с номером во всех невычеркнутых последовательностях. Это ограниченная последовательность, онаимеет предельную точку. Вычеркнем из неё элементы так, чтобы предельная точка стала пределом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
