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

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

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

Вычеркнем все последовательности, в которыхлежали вычеркнутые элементы. Выберем в окончательный ответ первую изоставшихся невычеркнутыми и невыбранными последовательностей.По построению на каждой позиции элементы выбранных последователь­ностей имеют предел, что и требовалось.Следствием данного факта является следующая лемма:Лемма 3.4. Для любой последовательности ограниченных в совокупностифункций, определённых на некоторых конечных словах над конечным илисчётным алфавитом, существует подпоследовательность, имеющая пре­дел значений для каждого слова, на котором определены почти все функцииисходной последовательности.Доказательство.

Действительно, область определения каждой функции неболее, чем счётна, поэтому каждую функцию можно представить как счёт­ную последовательность значений, учитывая только значения на словах, гдеопределены почти все функции. После этого мы сможем применить лем­му 3.3.Покажем теперь, что это же утверждение можно применять и к мерам.63Лемма 3.5. Любая последовательность конечных мер на сверхсловах име­ет предельную точку, являющуюся мерой.Если исходные меры были вероятностными, таковой будет и предель­ная точка.Доказательство. Добавим в алфавит все целые числа.

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

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

Аналогично случаю конечных множеств, мыдокажем существование вероятностной меры на сверхсловах над алфави­том Σ × Σ × Σ , проекция которой на первую и вторую координаты равна , а проекция на вторую и третью координаты — . В частности, в любойпозиции с вероятностью 1 относительно первый символ будет не меньшевторого, а второй не меньшего третьего, поэтому проекция меры на первуюи третью координаты будет искомой мерой .64Значение на двустороннем слове понимается как -мера тонкогоцилиндра, заданного , то есть множества всех бесконечных продолжений влево и вправо.Ослабим сначала ограничение на проекции. Для каждого будем ис­кать меру , согласованную с порядком на компонентах, проекции которойсовпадают с , и только на цилиндрах с выпуклой оболочкой носителядлины не более .Определим множество состоящим из всех двусторонних слов (, )над алфавитом Σ , в которых длина и длина равны ровно .

Множество конечно. Сужение меры на × (которое мы понимаем как множестводвусторонних слов (, ) над алфавитом Σ × Σ , в которых длина и длина равны ровно ) задает распределение вероятностей на × , которое мыобозначим через . То же самое верно для сужения меры на × .Причем, обе меры согласованы с покомпонентым порядком и вторая проек­ция меры совпадает с первой проекцией меры . Как уже объяснялось,отсюда следует, что можно построить распределение вероятностей на 3 ,у которого проекция на первую и вторую координаты равны , а проекцияна вторую и третью координаты равны .Теперь рассмотрим предельную точку таких мер.

Она и будет требуемоймерой . Транзитивность доказана.Полезно понимать, что даже если меры и были инвариантными,указанное доказательство не гарантирует инвариантности построенной меры . Для получения инвариантной меры требуется дополнительная конструк­ция, которую мы приведём позже, в рамках доказательства леммы 3.12.Второе доказательство.Переформулируем определение порядка на мерах так, что транзитив­ность станет очевидной.Определение 3.6.

Верхним цилиндром называется объединение всех тон­ких цилиндров, больших либо равных данному в смысле определения 3.5.Верхним множеством называется конечное объединение верхних цилиндровс общим носителем.65Лемма 3.6. > тогда и только тогда, когда для любого верхнего мно­жества выполнено ( ) > ( ) .Доказательство. Везде в доказательстве будем использовать > на по­следовательностях, цилиндрах (и словах, задающих цилиндры) для обозна­чения частичного покомпонентного порядка, а на мерах — для обозначениявведённого порядка, транзитивность которого мы и доказываем.Если > , и — верхнее множество, то({(, ) | ∈/ , ∈ }) = 0.Отсюда следует( ) = ( × Σ∞ ) > ( × ) = (Σ∞ × ) = ( )(второе равенство здесь выполняется в силу > ).Пусть теперь вероятность любого верхнего множества по мере не мень­ше, чем по .

Нам нужно построить полупрямое произведение мер , ,согласованное с порядком.Пусть 2+1 , 2+1 — меры, являющиеся ограничением мер , на ци­линдры длины 2 + 1 с серединой в нулевой позиции. Определим меру 2+1на парах слов длины 2+1 с серединой в нулевой позиции (эти слова задаюттонкие цилиндры, у носителя которых середина находится в нулевой позициии длина равна 2 + 1 ), обладающую следующими двумя свойствами:1) по мере 2+1 могут иметь ненулевую вероятность только те пары словдлины 2 + 1 , у которых первая компонента больше или равна второй;2) Проекция меры 2+1 на первую координату равна 2+1 , а на вторуюкоординату — 2+1 .Существование такой меры 2+1 следует из теоремы 0.4 из второй гла­вы (которая позволяет явно построить меру на словах в алфавите пар сим­волов с помощью теоремы Форда-Фалкерсона о потоке и разрезе).Рассмотрим любую предельную точку этой последовательности мер.Функция определена на всех двусторонних словах над Σ × Σ .66Докажем, что задаёт искомое полупрямое произведение.

Во-первых,условия, говорящие, что функция на словах задаёт вероятностную меру —это согласованность мер цилиндров, с носителями, отличающимися добавле­нием одной позиции. Каждое такое условие выполнено для , поскольку оновыполнено для 2+1 для всех достаточно больших (точнее, для всех ,для которых это условие имеет смысл). По этой же причине выполнены усло­вия, говорящие, что проекции меры равны и (каждое такое условиеозначает, что сумма вероятностей для множеств слов в алфавите пар букв,у которых одна из проекций постоянна, равна данному числу и поэтому вы­полнено для 2+1 для всех достаточно больших ).Лемма 3.6 доказана.

Из неё сразу следует, что отношение > транзитивно(первое условие).Третье условие (на стр. 0.3) следует из определения. Действительно, мно­жество последовательностей, у которых в данной позиции стоит плюс, естьверхнее множество (и даже верхний цилиндр).

Поэтому, если мера большемеры , то -вероятность этого множества не меньше его -вероятности.Докажем невыполненность четвертого условия (при некоторых значени­ях параметров , ). Причина немонотонности операторов Тоома кроется внемонотонности оператора Ann . Докажем последнее для достаточно близ­ких к 1 значений . Для этого рассмотрим меру , сконцентрированную напоследовательностях с периодом⊕ ⊖ ⊕ ⊖ ⊕ ⊕ ⊕ ⊖ ⊖⊖,и меру , сконцентрированную на последовательностях с периодом⊕⊕⊕⊖⊕⊕⊕⊖⊖⊖.Ясно, что 6 по тем же причинам, по которым верно было аналогичноенеравенство для мер на односторонних сверхсловах (его мы доказали в на­чале второй главы).

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

Тогда оба оператора Тоома выродятся в Ann , азначит будут немонотонны. По непрерывности они будут немонотонны и прилюбых и достаточно близких к 0 и 1, соответственно.Заметим, что немонотонность оператора Ann является единственнойпричиной немонотонности асимметричного оператора Тоома асим . Напом­ним, что он определяется как композиция Flip+ и Duel . При этом операторFlip+ монотонен.

В самом деле, пусть 6 и мера есть полупрямое произ­ведение и , согласованное с порядком 6 . Рассмотрим оператор, которыйдействует на парах последовательностей, заменяя с вероятностью каждуюпару соответствующих символова каждую пару⊕⊖на пару⊕⊕⊖⊖на пару⊕⊕(для разных пар независимо),(так же с вероятностью ).

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

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