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

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

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

Но этаоценка очень быстро растет.Будем обозначать через ∘ (·) функцию, являющуюся -кратной компо­зицией функции (·) с собой: ∘ () = ( (. . . ( ) . . . )).⏟⏞ разТеорема 0.1 ([3, 4]). Если у заключительно почти периодического сверх­слова регулятор не превосходит () − 1 и автомат имеет состояний,то у его образа под действием автомата регулятор (в смысле определения0.3) не превосходит ∘ ().Определение 0.4.

Прямым произведением двух сверхслов = 1 2 . . . и =1 2 . . . называется сверхслово ⊗ , состоящее из пар соответствующих сим­волов в сверхсловах и , то есть сверхслово (1 , 1 )(2 , 2 ) . . . Аналогичноопределяется прямое произведение конечных слов одной длины. Алфавитомпрямого произведения сверхслов является декартово произведение исходныхалфавитов.Оценка теоремы 0.1 имеет место для регулятора прямого произведениязаключительно почти периодического сверхслова и периодического сверхсло­ва с периодом .

Действительно, такое сверхслово может быть получено при­менением автомата с состояниями к исходному сверхслову (автомат пере­ходит по циклу от состояния к состоянию независимо от входных букв).На докладе [5], в котором были доказаны основные результаты [2, 4],М.Н. Вялый поставил вопрос о возможности уменьшения верхней оценки.9После того, как ответ на этот вопрос был дан автором диссертации, А.Л. Се­мёнов поставил вопрос о том, для какого класса конечных автоматов можнопровести аналогичное рассуждение.В первой главе для регулятора прямого произведения периодическогосверхслова и почти периодического сверхслова доказывается нижняя оцен­ка, отличающаяся от верхней только множителем в количестве итераций.При этом регулятор исходного почти периодического сверхслова может бытьсколь угодно быстрорастущей функцией.Основной результат главыОсновной результат, представленный в первой главе — существованиепочти периодического слова с регулятором (·), прямое произведение которо­го с периодическим словом с периодом имеет регулятор вида ∘Θ() .К сожалению, теорема в такой формулировке тривиальна (например,слово из одних нулей имеет в качестве регулятора тождественную функцию).Поэтому используется формулировка, которая позволяет потребовать быстро­го роста регулятора и при этом избежать технических трудностей, связанныхс оценкой регулятора почти периодичности для всех длин слов.Теорема 0.2.

(опубликовано в [16]) Если задана возрастающая функция на­турального аргумента , то существует почти периодическое сверхсло­во нулей и единиц со следующими свойством. Для всех > 100 и беско­нечно многих значение на регулятора почти периодичности сверхслова ⊗ Cycle превышает (max{, } + 1)∘⌊ 30 ⌋ (), где Cycle обозначает сверх­слово ( mod ), а — регулятор почти периодичности сверхслова .Данные свойства сохраняются и при выкидывании произвольного нача­ла из сверхслова .Эту теорему можно и усилить. В сформулированном результате дана10нижняя оценка на число итераций, равная30 .Можно добиться и нижнейоценки, равной − 3 (напомним, что верхняя оценка равна ).

Мы несколь­ко меняем условия быстрого роста регулятора, но для бесконечно многихдлин регулятор превышает результат − 3 итераций частично определённойфункции, которая превышает и регулятор, и заданную в качестве параметраконструкции функцию .Теорема 0.3. Пусть задана возрастающая функция : N → N. Тогда най­дётся почти периодическое сверхслово с регулятором почти периодично­сти и следующими свойствами.1) Для бесконечного количества аргументов превышает .

Болеетого, эти аргументы выстроены в цепочку: существует последователь­ность натуральных чисел , такая что1 ( ) < +1 6 ( ) 6 +1 .62) Для любого > 2 и любого регулятор почти периодичности ⊗Cycle удовлетворяет неравенствам ⊗Cycle ( ) > +−2 > ∘−2 ( ).3) Для любого достаточно большого регулятор почти периодично­сти всё того же прямого произведения ⊗ Cycle на всех достаточнобольших значениях аргументов превышает ∘−3 .При этом данная нижняя оценка на регулятор сохранится и при рас­смотрении выходной последовательности как заключительно почти периоди­ческой или обобщённо почти периодической.0.2. Вычислимость полупрямых произведений вычислимых мер,согласованных с отношением порядкаВо второй главе изучается вопрос о вычислимости полупрямого произ­ведения вычислимых мер на сверхсловах, согласованного с отношением по­11рядка, индуцированного порядком на алфавите.

Данный вопрос был постав­лен А. Шенём на докладе [6]. Доказывается существование двух конкретныхвычислимых мер, у которых есть полупрямое произведение, согласованное сотношением порядка, но любое такое полупрямое произведение невычислимо.Основные определенияОпределение 0.5. Пусть имеются вероятностные меры , на простран­ствах , . Напомним, что прямым произведением мер , называется мера × на прямом произведении пространств , такая, что для любых изме­римых множеств ⊂ и ⊂ выполнено равенство( × )( × ) = () × ().Говорят, что мера на пространстве × является полупрямым произве­дением и , если ее проекции равны и , то есть, для любого измеримого ⊂ выполнено( × ) = (),а также, для любого измеримого ⊂ выполнено( × ) = ().Примером полупрямого произведения мер , является их прямое произве­дение.Определение 0.6.

Пусть заданы конечные множества , и распределениявероятностей и на и , соответственно. Пусть также задано некото­рое бинарное отношение ⊂ × . Будем говорить, что распределение находится в отношении с , если существует полупрямое произведение и , относительно которого множество пар имеет вероятность 1.

Такоеполупрямое произведение будем называть согласованным с .12В терминах случайных величин находится в отношении с (обо­значается ), если существуют две случайные величины и на одномвероятностном пространстве со значениями в , , распределения которыхравны и , соответственно, и для которых находится в отношении с (во всех точках вероятностного пространства).Определение 0.7.

Напомним стандартное определение вычислимой меры.Рассмотрим множество Σ = {0, 1}. Через ΣN обозначим пространствосверхслов из нулей и единиц. Введем на нем покомпонентный частичный по­рядок: 0 1 2 . . . 6 0 1 2 . . ., если 6 при всех . Будем рассматривать ме­ры, заданные на сигма-алгебре, порожденной множествами сверхслов, являю­щихся продолжениями заданных конечных слов. Мера на пространстве ΣNназывается вычислимой, если существует алгоритм, который по ∈ Q, > 0,и конечному слову в алфавите Σ находит с точностью меру множествавсех бесконечных продолжений (см., например, [7]).

Аналогично определя­ются меры и их вычислимость на пространстве ΣN × ΣN : измеримыми яв­ляются элементы сигма-алгебры, порожденной множествами пар сверхслов,первое из которых является продолжением одного слова, а второе — другогослова. Алгоритм должен по > 0 и словам , находить с точностью мерумножества всех пар, в которых первая компонента продолжает слово , авторая — слово .Для вычислимости вероятностной меры достаточно существования ал­горитма порождения этого распределения как выхода вероятностного алго­ритма. Точнее, распределение на ΣN вычислимо, если существует вероят­ностный алгоритм (алгоритм, имеющий доступ к независимым бросаниямсимметричной монеты) без входа, который на выходной ленте печатает слу­чайную бесконечную последовательность с распределением .13Существование полупрямых произведений, согласованных сотношениямиИз теоремы Форда–Фалкерсона [8] о максимальном потоке и разрезеследует следующий простой критерий того, что распределение находится вотношении с , приведённый, например, в работе [9]:Теорема 0.4.

[Автор неизвестен] Распределение находится в отношении с , тогда и только тогда, когда не существует подмножеств ⊂ , ⊂ , таких что все -соседи лежат в и () > ().Если же = и — отношение порядка (транзитивное рефлексивноеотношение), то критерий можно переформулировать так: () 6 () длявсякого замкнутого вверх множества ⊂ . (В самом деле, можно считать,что состоит только из соседей, тогда оно замкнуто вверх в силу транзи­тивности отношения порядка и содержит в силу рефлексивности, а значитможно замкнуть вверх.)Применение полупрямых произведений мер и историярассматриваемого вопросаПолупрямые произведения, согласованные с отношением порядка, явля­ются одним из примеров применения полупрямых произведений, не являю­щихся прямыми.

Например, нам может понадобиться, чтобы случайная пара(, ) с большой вероятностью относительно полупрямого произведения об­ладала некоторым “хорошим” свойством. Мы приведём три таких примера,Пример 1. Даны распределения вероятности , на одном и том же ко­нечном множестве . Требуется найти их полупрямое произведение , длякоторого вероятность события “первая координата совпадает со второй” мак­симальна. Эта задача возникает при доказательстве некоторого неравенства,14ограничивающего разницу между шенноновской энтропией и в терминахстатистического расстояния между и (см. [7]).Пример 2.

Одним из двух известных методов получения не шеннонов­ских информационных неравенств является «метод независимизации», при­мененный в [9, 10]. Мы изложим этот метод вкратце, а для более подробногознакомства отсылаем читателя к книге [7]. В простейшей ситуации метод со­стоит в следующем: пусть дано некоторое неравенство, в которое входит шен­ноновские энтропии случайных величин , и , шенноновская энтропияпары случайных величин (, ) и шенноновская энтропия пары случайныхвеличин (, ) (например, 2() + 2() + 2() 6 3(, ) + 3(, )).Допустим, удалось доказать это неравенство для любых трёх совместно рас­пределённых случайных величин , , таких, что случайные величины и независимы при всяком известном исходе случайной величины . Тогда этонеравенство истинно и для любых вообще совместно распределённых случай­ных величин , , .В самом деле, пусть даны произвольные совместно распределённые слу­чайные величины , , с исходами в некоторых множествах , , , соот­светственно.

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

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