Оглавление
Введение "" ' 3
1. Инвариантные меры и транзиентность для двумерных слов 8
1.1. Основные определения.................................. 8
1.2. (+,+)-меры........................................... 12
1.3. Доказательство Теоремы 1............................. 14
2. Инвариантные меры типа (-, +) и закон стабилизации 25
2.1. Формулировка основного результата.................... 25
2.2. Доказательство Теоремы 2............................. 26
2.2.1. доказательство леммы 7........................ 29
2.2.2. доказательство леммы 8........................ 34
2.2.3. доказательство леммы 9........................ 41
3. Блуждания на множестве пар конечных слов 50
3.1. Основные определения и предварительные результаты 50
3.1.1. Индуцированные цепи........................... 53
3.1.2. Эргодическая одномерная грань................. 54
3.1.3. Ассоциированная цепь.......................... 59
3.2. Формулировка основных результатов.................... 61
3.3. Вспомогательный процесс.............................. 66
3.4. Эргодичность......................................... 73
3.5. Транзиентность....................................... 79
3.5.1. Доказательство леммы 17....................... 82
3.6. Возвратность ........................................ 86
3.6.1. Доказательство леммы 18....................... 88
3.7. Неэргодичность....................................... 91
2
Введение
Настоящая работа посвящена изучению марковских цепей, которые описывают эволюцию конечных и полубесконечных слов (['2, 4, 5, 6, 7, 9]). Описываемый здесь класс марковских процессов тесно связан со случайными блужданиями на целочисленной решетке, со случайными блужданиями на дискретных группах, (наиболее известными примерами здесь являются аменабсльные группы (см. [12]) и свободные некоммутативные группы [13],[19]), а также С другой, бурно развивающейся областью - случайными блужданиями в случайной среде, замороженной (см. например [17]) или динамической.
Под конечным словом мы будем понимать последовательность символов
Ск' = Х\ • . . Хп,
где х, принадлежат некоторому конечному алфавиту 5 = {1,2,..., г}. Обозначим через 0 пустое слово. Рассмотрим однородную, счетную марковскую цепь с дискретным временем. Пространством состояний этой цепи является множество всех конечных слов, включая пустое Слово, обозначим это множество А. Динамика этой цепи определяется следующими переходными вероятностями:
• </(£,0) - вероятность зачеркнуть крайний правый символ слова при
условии, что он равен х;
• Я(Х>У) ~ вероятность заменить крайний правый символ х на символ
У\
• ({(х,уг) - вероятность заменить крайний правый символ х на два
символа у г.
Разумеется, мы предполагаем, что для всех х
Я(х, 0) + 12 «(*> У) + И </(*> У*) = 1-
У У*
Таким образом, переходные вероятности зависят только от крайнего правого символа слова, и за один шаг длина слова не может измениться более, чем на 1. Заданные выше вероятности полностью определяют динамику цепи в случае, когда слово не пустое (длина
3
слова строго больше 0). Мы предположим, что из пустого слова можно перейти только в слово длины не более 1, и что соответствующие вероятности положительны.
Если г = 1, то мы получаем классическое случайное блуждание на
Z+’
Отметим, что случайные блуждания на свободных некоммутативных группах являются частным случаем марковской цепи на множестве конечных слов. Рассмотрим свободно порожденную группу G с / генераторами и положим а_* = а“1. В работах [13],
[14], [16], [15] рассматриваюсь произведение независимых случайных величин с значениями в G. А именно, заданы вероятности
для переходов а -* аі,а Є G. Заметим, что о,- и о_, не могут стоять рядом и это частный случай нашей задачи. Действительно, достаточно задать
q(i, 0) = «-і, q{i,ij) = Uj, q(i, kj) = 0 if к ф і.
Нетрудно понять, что системы массового обслуживания с дисциплиной LIFO (последний пришел первым обслужился) также являются частным случаем нашего процесса.
Мы будем рассматривать также несчетные марковские цепи с дискретным временем, заданные на пространстве полубесконечных Слов, где под полубесконечным словом понимается бесконечная последовательность вида a = xi принадлежат алфавиту $.
Динамика для полубесконечных слов определяется теми же самыми вероятностями q(x< ft),q(x, у), q[x, yz).
Удобно представлять полубесконечное слово в момент времени t как функцию f{i,t) на Z х Z, со значениями в Su{0}, где значение 0 соответствует ’’вакууму”. В момент времени t эта функция не равна 0 на некотором интервале (—оо,«<] и равна 0 вне этого интервала. Здесь ai координата крайнего правого символа слова. В момент времени 0 начальное слово a = ..., задается функцией равной
Хі для * < 0 и * вакууму” для і > 0. Если /(a<, t) = х, то, к примеру, с вероятностью q(x, yz) следующее состояние будет таким: /(а, + 1, f +
1) — zy f[Qtyt + 1) = у и остальные значения не изменяются. Таким образом, в этом случае at+\ = ût + 1.
Очевидно, что в случае г = 1 мы имеем случайное блуждание на
Z.
4
Рассматриваемые нами процессы на пространстве иолубесконеч-ных слов занимают промежуточное положение между случайными блужданиями и процессами с локальным взаимодействием. Грубо говоря, состоянием процесса с локальным взаимодействием (см. [18]) является полубесконечнос слово, и в каждый момент времени может измениться ее произвольная конечная часть, а в нашем случае может меняться только один конец слова.
Б работах [4], [2] и [9] были получены законы стабилизации для конечных и полубесконечных слов. Под законами стабилизации мы имеем в виду предельные теоремы, в которых утверждается сходимость корреляционных функций символов в конце слова к некоторому предельному распределению с ростом времени. Пусть а(0 = .. •£„({) - состояние цепи в момент времени <. Рассмотрим
корреляционные функции р, в момент
р{(0 = Р{*п(<) = *'},
Р}{*,3) = Р{*п(0 = «,Яп(1)-1 = Л, и т.д.
Эти корреляционные функции однозначно определяют некоторое распределение //(<) на Б2*. В работе [4] был получен следующий закон стабилизации для транзиентной цепи а(<) (длина слова п(<) стремится к бесконечности).
Теорема 1. Если цепь а(<) транзиентна. Тогда
1) ц(<) слабо сходится к некоторому предельному распределению /Й
2) существует р(р) > 0 такое, что для всех начальных состояний
п(0 / \
—------> г-(р), <->оо
почти наверно;
В данной работе мы будем изучать марковские цепи, которые описывают эволюцию двух конечных или полубесконечных взаимодействующих слов. Когда оба слова непустые, динамика изучаемой цепи задается переходными вероятностями, зависящими от пары
5
символов, стоящих в конце слов. Если «, Ь - крайние правые символы первого и второго слова соответственно, то в следующий момент времени мы с вероятностью </(а,/>; 7*^,7^), вычеркиваем символы а, Ь и вместо них подставляем слова 7^, 7^, такие, что |У^1 < 2, |7^| < 2. Случаи, когда 7Й) = 0 означает, что мы просто вычеркиваем соответствующий символ. Введем естественное условие: для любых о, Ь 6
£ Е ф,6;7{1),7(2)) = 1
?(*>: Ь<°1<21<2): |Т«|<2
Для полного определения ди>1амики необходимо определить переходные вероятности в случае, когда одно из слов пустое. Эти граничные переходные вероятности зависят только от последнего символа непустого слова. Подробное определение будет дано ниже.
Динамика пары слов называется транзиентной, если с ростом времени длины обоих слов и ДО) «2(0 стремятся к бесконечности с вероятностью 1. В первой главе мы доказываем закон стнбилизациц для двух растущих слов. А именно, мы покажем, что если с ростом времени длины обоих слов 7?I (0? «2(0 стремятся к бесконечности с вероятностью 1, тогда
• существуют константы 111 > 0, т>2 > 0, такие, что
«1(0 «2(0
— — -»«
• распределение символов, стоящих на правых концах слов, стабили-
зируется.
Доказательство этого факта основано на методе спаривания.
Во второй главе мы рассмотрим марковскую цепь на пространстве полубесконечных слов, и предположим, что выполнены следующие условия Ляпунова: существуют к > 0, е > 0, такие, что
Е(а1(к)-а1(0)\г1(0))<~^
Е{а?{к) - а2(0) | г/(0)) > е,
для любых начальных конфигураций 7/(0) = (//ДО), 7/Д0)). Эти условия означают, что
<*1(0 —> -оо, а2(0 —* оо,
6
при * -> оо почти наверно. В этих условиях мы доказываем закон стабилизации: если начальная конфигурация гц{0) имеет бернулли-свское распределение, то с ростом времени распределение символов в концах слов стабилизируется. В данном случае предельная мера зависит от начальной конфигурации г/і(0).
В третьей главе мы рассматриваем марковскую цепь, пространством состояний которой определяется следующим образом. Рассмотрим объединение конечного числа копий (А х «4.),є{і,...,лг} множества всевозможных пар конечных слов. Копии [А х Л), будем называть двумерными гранями, а множества вида (0 х .4),- и (А х 0); - одномерными гранями. Отождествим все точки вида (0,0),. Предположим также, что некоторые одномерные грани могут быть отождествлены.
Переходные вероятности будут устроены так, что если цепь находится внутри двумерной грани, то одна из компонент будет всегда убывать, а другая возрастать, и вероятности перехода будут зависеть только от последнего символа убывающего слова. Точные формулировки даны в третьей главе.
Наша задача состоит в том чтобы даті, критерии эргодичности, ноль-возвратности и транзиентностн для этой цепи. Классификация этой цепи получается с помощью двух констант Ь и А/, экспоненты Ляпунова и свободной энергии.
Более точные формулировки дадим в соответствующем разделе. Здесь же отметим, что в случае, когда г = 1, мы получим частный случай однородного блуждания на двумерном комплексе. Такие блуждания были рассмотрены в [1] (см. главу 5), где были даны критерии эргодичности, ноль-возвратности и транзиентностн. Удивительным фактом явилось то, что множество параметров, на котором возникает ноль-возвратность не является множеством меры ноль. Такой же факт имеет место и для нашей цепи.
7
- Київ+380960830922