Сверхслова, меры на них и их полупрямые произведения (1104768), страница 3
Текст из файла (страница 3)
Обозначим через распределение случайной величины (, )(с исходами в × ), а через — распределение пары случайной величины(, ) (с исходами в ×). Несложно убедиться, что существует полупрямоепроизведение распределений и (на множестве × × × ), относительно которого с вероятностью 1 первая и третья координаты совпадают,а вторая и четвёртая координаты независимы при любой известной первой(= третьей) координате. Обозначим через ′ , ′ , ′ , ′ случайные величины,равные первой, второй, третьей и четвёртой координате четвёрки, выбраннойслучайно по распределению . Тогда ′ и ′ независимы при всяком известном исходе случайной величины ′ , поэтому исходное неравенство выполненодля этой тройки случайных величин. С другой стороны, распределение пары15(′ , ′ ) такое же, как и у пары (, ).
То же самое верно и для пары (, ) идля каждой из случайных величин , , . Поэтому шенноновская энтропияпары (′ , ′ ) та же, что и у пары (, ), и то же самое верно для пары (, )и для , , по отдельности. Следовательно, исходное неравенство верно идля данной (произвольной) тройки , , .В этом примере нам было нужно не только, чтобы случайная пара (, )с большой вероятностью относительно полупрямого произведения обладаланекоторым свойством, но также, чтобы и само полупрямое произведение обладало некоторым свойством.Пример 3.
Из этого примера и возник вопрос, изученный во второй главе. Пусть = есть пространство всех сверхслов из нулей и единиц. Пусть есть бернуллиевская мера на с рациональным параметром 1 , а естьбернуллиевская мера на с рациональным параметром 2 > 1 . (Бернуллиевская мера с параметром определяется, как распределение вероятностейна последовательностях, полученных в результате бесконечного числа независимых бросаний монетки, выдающей 1 с вероятностью и 0 с вероятностью1 − .) Будем рассматривать бесконечные 0-1-последовательности, случайныепо Мартин-Лёфу относительно распределения (определение случайности поМартин-Лёфу можно найти, например, в [7]). В работе [9] доказано, что в любой такой последовательности можно заменить некоторые нули на единицытак, чтобы полученная последовательность была случайна по Мартин-Лёфупо распределению .
Это доказывается с помощью рассмотрения вычислимого полупрямого произведения распределений и , относительно которого свероятностью 1 последовательность покомпонентно меньше последовательности (несложно доказать, что у бернуллиевских распределений с вычислимыми параметрами 2 > 1 такое полупрямое произведение в самом деле существует). Точнее, в [9] доказан следующий общий факт: если у вычислимыхраспределений и на пространстве бесконечных 0-1-последовательностей16существует вычислимое полупрямое произведение , относительно которогос вероятностью 1 последовательность покомпонентно меньше последовательности , то в любой бесконечной последовательности, случайной по Мартин-Лёфу относительно распределения можно заменить некоторые нули наединицы так, чтобы полученная последовательность была случайна по Мартин-Лёфу по распределению .В этой связи был поставлен вопрос, можно ли в этой теореме убратьусловие вычислимости полупрямого произведения.
Точнее, верно ли, что еслисуществует полупрямое произведение вычислимых мер и такое, чтоотносительно него с вероятностью 1 последовательность покомпонентноменьше последовательности , то существует и вычислимое такое полупрямоепроизведение. Во второй главе дается отрицательный ответ на этот вопрос.Основной результат главыТеорема 0.5.
(опубликовано в [17]) Существуют две вычислимые меры и на ΣN , которые имеют полупрямое произведение, согласованное с отношением 6, но не имеют вычислимого полупрямого произведения, согласованного с отношением 6.0.3. Транзитивность отношения Тоома на мерах на сверхсловахВ третьей главе изучаются отношения на мерах на двусторонних сверхсловах, в частности доказывается транзитивность отношения на мерах на двусторонних сверхсловах в алфавите из двух символов, предложенного проф.А.Л. Тоомом и позволяющего сравнить больше мер, чем стандартное продолжение на меры отношения > на алфавите, рассмотренное во второй главе.Данное отношение было введено с целью изучения вероятностных одномерных клеточных автоматов с возможностью стирания и добавления кле17ток.Во второй главе мы рассматриваем отношение порядка на мерах на односторонних сверхсловах.
В третьей главе рассматриваются двусторонниесверхслова и меры на них, инвариантные относительно сдвига. Рассмотренный во второй главе способ продолжения на меры отношения порядка непозволяет нам, например, сравнить меры, сконцентрированные на сдвигахсверхслов . . . (⊕ ⊖ ⊕⊖)∞ . . . и .
. . (⊕ ⊕ ⊖ ⊕ ⊕⊖)∞ . . .. При этом неформально можно сказать, что одна из мер получается из другой в каком-то смыследобавлением лишних плюсов. Рассматриваемое в третьей главе отношениебыло предложено А.Л. Тоомом для рассмотрения операторов, позволяющихвычёркивание. В частности, оно позволяет сказать, что вторая мера в новомсмысле больше первой.Общей чертой клеточных автоматов является представление системыв виде набора просто устроенных клеток, состояние каждой из которых современем меняется в зависимости от состояния небольшого количества её ближайших соседей. Исторически клеточные автоматы восходят к физическиммоделям на решётках (таким как модель Изинга намагничивания кристалла).С середины XX века их также рассматривают и в качестве вычислительныхмоделей.Вопрос сохранения вероятностным клеточным автоматом разницы между двумя конфигурациями представляет интерес при разных подходах к изучению клеточных автоматов.
Этот вопрос может быть интерпретирован и какхранение информации в вычислительной системе с помехами, и как моделирование фазового перехода, и как изучение условий эргодичности с точкизрения теории динамических систем. Для двумерных клеточных автоматовсохраняющий информацию при помехах клеточный автомат был построен вработе [11].
В работе [12] приводится пример одномерного клеточного автомата, в котором все вероятности перехода положительны и который способен18надёжно сохранять один бит информации несмотря на помехи.К сожалению, требуемая для этого конструкция оказывается очень сложной. В связи с этим представляют интерес родственные задачи с более слабыми требованиями. В работе [13] построен достаточно простой пример одномерного клеточного автомата с возможностью стирания клеток, которыйсохраняет один бит информации несмотря на положительные вероятностипочти всех переходов, и исследуются параметры фазового перехода междуэргодичностью и неэргодичностью для этого автомата.Неформально говоря, построенный клеточный автомат можно описатьследующим образом. На ленте стоят плюсы и минусы, причём за шаг каждыйминус может с некоторой вероятностью превратиться в плюс.
После этого пары соседних противоположных символов с некоторой (большей, чем вероятность появления ошибки) вероятностью стираются. (При строгом определение этого оператора требуется указать, что происходит с нумерацией позицийсверхслова, когда в нём выполняется бесконечно много стираний. Строгоеопределение этого оператора требует определять его как действующий намерах, инвариантных относительно сдвига.) Этот автомат, который мы называем асимметричным автоматом Тоома, имеет следующее свойство.
Если вначальный момент времени на ленте стоят одни минусы, то в любой моментвремени с большой вероятностью в случайно выбранной клетке ленты будетстоять минус. (Мы упрощаем формулировку, точное утверждение будет дано позднее.) С другой стороны, если в начальный момент времени на лентестоят одни плюсы, то в любой момент времени в любой клетке ленты будетстоять плюс. Это свойство и означает, что автомат способен сохранять одинбит информации.После этого возник вопрос, можно ли полученный результат перенестина случай двусторонней ошибки, то есть, на симметричный автомат Тоома.В симметричном автомате Тоома помехи могут менять как минус на плюс,19так и наоборот.
В качестве начального рассмотрим, например, состояние извсех минусов. Хотелось бы и для симметричного автомата установить, чтов любой момент времени с большой вероятностью в случайно выбраннойклетке ленты будет стоять минус. При этом было бы предпочтительно неповторять все вычисления из [13], а использовать этот результат и соображения сравнения распределений. Казалось естественным, что односторонняяошибка должна только ухудшать ситуацию, так как мы запретили случайно заменять неправильный символ на правильный. Действительно, начинаяс двустороннего сверхслова из одних минусов, мы ожидаем получить ещёбольшую вероятность минуса в каждой клетке в каждый момент времени.Вопрос сохранения преобладания плюсов перестаёт быть тривиальным (поддействием асимметричного оператора Тоома сверхслово из одних плюсов неизменяется никогда), но оказывается равносильным сохранению преобладания минусов.
Однако стандартное отношение сравнения на мерах на двусторонних сверхсловах не позволяет доказать монотонность рассматриваемыхоператоров из-за возможности стирания.Для преодоления этой трудности А.Л. Тоом предложил рассмотреть другое отношение сравнения, определённое только на мерах, инвариантных относительно сдвига, и являющееся на них продолжением стандартного отношения порядка. Нестрого его можно описать так: мера больше меры , если измеры можно вычёркиванием плюсов, добавлением минусов и заменой плюсов на минусы получить меру . Разумеется, можно обратными операциями(вычёркивание минусов, добавление плюсов и заменой минусов на плюсы)получать из меры меру или пытаться получить одну и ту же меру из и вычёркиванием плюсов из и минусов из .
В таких терминах стандартное отношение порядка требует получить из одной меры другую толькозаменами плюсов на минусы.В частности, данное отношение А.Л. Тоом упоминал и определял в курсе20[14].Нетрудно понять, что достаточно существования отношения < со следующими свойствами:1. Отношение < транзитивно.2. асим < сим , где сим , асим обозначают, соответственно симметричныйи асимметричный операторы Тоома.3.
Если < , то -вероятность плюса в данной клетке больше или равна-вероятности плюса в данной клетке.4. Хотя бы один из двух операторов Тоома обладает следующим свойствоммонотонности: < ⇒ () < ().Действительно, пусть эти условия выполняются. Обозначим исходнуюмеру, сосредоточенную на двустороннем сверхслове из одних минусов, 0 .Предположим для примера, что симметричный оператор Тоома монотонен.Тогда рассмотрим результаты -кратных итераций по индукции. База оче00видна: асим(0 ) = сим(0 ) = 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
