Двумерные случайные блуждания в изменяющейся среде тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Введение

1. Инвариантные меры и транзиентность для двумерных слов

1.1. Основные определения.

1.2. (+,+)-меры.

1.3. Доказательство Теоремы 1.

2. Инвариантные меры типа (—, +) и закон стабилизации

2.1. Формулировка основного результата

2.2. Доказательство Теоремы 2.

2.2.1. доказательство леммы 7.

2.2.2. доказательство леммы 8.

2.2.3. доказательство леммы 9.

3. Блуждания на множестве пар конечных слов

3.1. Основные определения и предварительные результаты

3.1.1. Индуцированные цепи

3.1.2. Эргодическая одномерная грань.

3.1.3. Ассоциированная цепь.

3.2. Формулировка основных результатов.

3.3. Вспомогательный процесс.

3.4. Эргодичность.

3.5. Транзиентность.

3.5.1. Доказательство леммы 17.

3.6. Возвратность

3.6.1. Доказательство леммы 18.

3.7. Неэргодичность.

Настоящая работа посвящена изучению марковских цепей, которые описывают эволюцию конечных и полубесконечных слов ([2, 4, 5, 6, 7, 9]). Описываемый здесь класс марковских процессов тесно связан со случайными блужданиями на целочисленной решетке, со случайными блужданиями на дискретных группах, (наиболее известными примерами здесь являются аменабельные группы (см. [12]) и свободные некоммутативные группы [13],[19]), а также с другой, бурно развивающейся областью - случайными блужданиями в случайной среде, замороженной (см. например [17]) или динамической.

Под конечным словом мы будем понимать последовательность символов

ОС — ОС X • • • ^ 71 *) где Х{ принадлежат некоторому конечному алфавиту $ = {1,2,., г}. Обозначим через 0 пустое слово. Рассмотрим однородную, счетную марковскую цепь с дискретным временем. Пространством состояний этой цепи является множество всех конечных слов, включая пустое слово, обозначим это множество Л. Динамика этой цепи определяется следующими переходными вероятностями:

• q(x, 0) - вероятность зачеркнуть крайний правый символ слова при условии, что он равен х;

• д(х, у) - вероятность заменить крайний правый символ х на символ

У;

• q(x, у г) - вероятность заменить крайний правый символ х на два символа ух.

Разумеется, мы предполагаем, что для всех х д(х, 0)+£ д(х, у) + £ уг) = 1.

У У^

Таким образом, переходные вероятности зависят только от крайнего правого символа слова, и за один шаг длина слова не может измениться более, чем на 1. Заданные выше вероятности полностью определяют динамику цепи в случае, когда слово не пустое (длина слова строго больше 0). Мы предположим, что из пустого слова можно перейти только в слово длины не более 1, и что соответствующие вероятности положительны.

Если г — 1, то мы получаем классическое случайное блуждание на

Z+.

Отметим, что случайные блуждания на свободных некоммутативных группах являются частным случаем марковской цепи на множестве конечных слов. Рассмотрим свободно порожденную группу G с / генераторами ai,.,щ и положим a¿ = ajl. В работах [13], [14], [16], [15] рассматривалось произведение независимых случайных величин с значениями в G. А именно, заданы вероятности = 1,.,/, —1,., —I для переходов а —>■ ai, а & G. Заметим, что a¿ и a-i не могут стоять рядом и это частный случай нашей задачи. Действительно, достаточно задать q{i, 0) = u-i, q{i, ij) = Uj, q(i, kj) = 0 if к ф i.

Нетрудно понять, что системы массового обслуживания с дисциплиной LIFO (последний пришел - первым обслужился) также являются частным случаем нашего процесса.

Мы будем рассматривать также несчетные марковские цепи с дискретным временем, заданные на пространстве полубесконечных слов, где под полубесконечным словом понимается бесконечная последовательность вида а = .Х-2Х-1, Х{ принадлежат алфавиту S. Динамика для полубесконечных слов определяется теми же самыми вероятностями q(x, 0), q(x, у), q(x, yz).

Удобно представлять полубесконечное слово в момент времени t как функцию /(г, t) на Z х Z+ со значениями в .SujO}, где значение 0 соответствует "вакууму". В момент времени t эта функция не равна 0 на некотором интервале (—оо, at] и равна 0 вне этого интервала. Здесь at - координата крайнего правого символа слова. В момент времени 0 начальное слово а = ., Х-2%-1 задается функцией равной Х{ для i < 0 и "вакууму" для i > 0. Если f(at, t) = х, то, к примеру, с вероятностью q(x, yz) следующее состояние будет таким: /(a¿ +1, ¿ + 1) = z, f(at,t + 1) = у и остальные значения не изменяются. Таким образом, в этом случае at+1 = a¿ + 1

Очевидно, что в случае т — 1 мы имеем случайное блуждание на Z

Рассматриваемые нами процессы на пространстве полубесконечных слов занимают промежуточное положение между случайными блужданиями и процессами с локальным взаимодействием. Грубо говоря, состоянием процесса с локальным взаимодействием (см. [18]) является полубесконечное слово, и в каждый момент времени может измениться ее произвольная конечная часть, а в нашем случае может меняться только один конец слова.

В работах [4], [2] и [9] были получены законы стабилизации для конечных и полубесконечных слов. Под законами стабилизации мы имеем в виду предельные теоремы, в которых утверждается сходимость корреляционных функций символов в конце слова к некоторому предельному распределению с ростом времени. Пусть a(t) = х\. - состояние цепи в момент времени t. Рассмотрим корреляционные функции р\ в момент t. р}(г) = P{jn(i) = г},

Pt(hJ) = PR(i) = hxn[t)i = j}, и т.д.

Эти корреляционные функции однозначно определяют некоторое распределение p(t) на Sz+. В работе [4] был получен следующий закон стабилизации для транзиентной цепи a(t) (длина слова n(t) стремится к бесконечности).

Теорема 1. Если цепь a(t) транзиентна. Тогда

1) ¡i{t) слабо сходится к некоторому предельному распределению

2) существует > 0 такое, что для всех начальных состояний n(t) , , —- v(fJL), t -> оо L почти наверно;

В данной работе мы будем изучать марковские цепи, которые описывают эволюцию двух конечных или полубесконечных взаимодействующих слов. Когда оба слова непустые, динамика изучаемой цепи задается переходными вероятностями, зависящими от пары символов, стоящих в конце слов. Если а, Ь - крайние правые символы первого и второго слова соответственно, то в следующий момент времени мы с вероятностью д(а,Ь; 7^,7^), вычеркиваем символы а, Ь и вместо них подставляем слова 7^, 7^, такие, что 17^1 < 2, |7^| < 2. Случай, когда 7^ = 0 означает, что мы просто вычеркиваем соответствующий символ. Введем естественное условие: для любых а, Ъ Е 5

Е Е дМ;7(1),7(2)) = 1

Для полного определения динамики необходимо определить переходные вероятности в случае, когда одно из слов пустое. Эти граничные переходные вероятности зависят только от последнего символа непустого слова. Подробное определение будет дано ниже.

Динамика пары слов называется транзиентной, если с ростом времени длины обоих слов щ(£), стремятся к бесконечности с вероятностью 1. В первой главе мы доказываем закон стибилизации для двух растущих слов. А именно, мы покажем, что если с ростом времени длины обоих слов П1(£), п^) стремятся к бесконечности с вероятностью 1, тогда

• существуют константы > 0, г>2 > 0, такие, что

• распределение символов, стоящих на правых концах слов, стабилизируется.

Доказательство этого факта основано на методе спаривания.

Во второй главе мы рассмотрим марковскую цепь на пространстве полубесконечных слов, и предположим, что выполнены следующие условия Ляпунова: существуют к > О, е > 0, такие, что

Е(а1(Аг)-О1(0) |»у(0))<-£г, Е(а2(Аг) - а2(0) | гу(0)) > в, для любых начальных конфигураций 77(0) = (771 (0), 772 (0)). Эти условия означают, что

-—оо, 0,2(1) —> оо, при £ —> оо почти наверно. В этих условиях мы доказываем закон стабилизации: если начальная конфигурация щ(0) имеет бернулли-евское распределение, то с ростом времени распределение символов в концах слов стабилизируется. В данном случае предельная мера зависит от начальной конфигурации 771(0).

В третьей главе мы рассматриваем марковскую цепь, пространством состояний которой определяется следующим образом. Рассмотрим объединение конечного числа копий (А х Л)^]^.^} множества всевозможных пар конечных слов. Копии (А х Л)г- будем называть двумерными гранями, а множества вида (0 х Л)г- и (А х 0)г- - одномерными гранями. Отождествим все точки вида (0,0)г-. Предположим также, что некоторые одномерные грани могут быть отождествлены.

Переходные вероятности будут устроены так, что если цепь находится внутри двумерной грани, то одна из компонент будет всегда убывать, а другая возрастать, и вероятности перехода будут зависеть только от последнего символа убывающего слова. Точные формулировки даны в третьей главе.

Наша задача состоит в том чтобы дать критерии эргодичности, ноль-возвратности и транзиентности для этой цепи. Классификация этой цепи получается с помощью двух констант Ь и М, экспоненты Ляпунова и свободной энергии.

Более точные формулировки дадим в соответствующем разделе. Здесь же отметим, что в случае, когда г = 1, мы получим частный случай однородного блуждания на двумерном комплексе. Такие блуждания были рассмотрены в [1] (см. главу 5), где были даны критерии эргодичности, ноль-возвратности и транзиентности. Удивительным фактом явилось то, что множество параметров, на котором возникает ноль-возвратность не является множеством меры ноль. Такой же факт имеет место и для нашей цепи.

1. G. Fayolle, V.A. Malyshev and M.V. Menshikov (1995) Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press.

2. V.A. Malyshev (1992) Stabilization Laws for Processes with a Localized Interaction. Rapport de Recherche INRIA, No. 1635.

3. V.A. Malyshev (1993) Networks and Dinamical Systems. Adv. Appl. Prob. 25, 140-175.

4. B.A. Малышев (1994) Эволюция случайных струн: законы стабилизации. Проблемы передачи информации 30 (3), 79-95.

5. В.А.Малышев (1997) Взаимодействующие цепочки символов. Успехи Мат. Наук, Т.52, вып. 2(314), 59-86.

6. А.С. Гайрат, В.А. Малышев, М.В. Меньшиков, К.Д. Пелих (1995) Классификация марковских цепей, описывающих эволюцию случайных струн. Успехи мат. наук 50 No. 2 (302), 5-24.

7. A.S. Gajrat (1995) Random Walk of an Active Particle in Non-Homogeneous Environment. Markov Proc. Relat. Fields 1, 91113.

8. A.S. Gajrat, R.Iasnogorodski, V.A.Malyshev, (1996) Null Recurrent String. Markov Proc. Relat. Fields 2, 427-460.

9. A.S. Gajrat, V.A. Malyshev, A.A. Zamyatin (1995) Two-Sided Evolution of a Random Chain. Markov Proc. Relat. Fields 2, 281-316.

10. А.А. Замятин, А.А. Ямбарцев (1996) Транзиентная динамика двух взаимодействующих слов. Фунд. и прикладная математика том 2, вып.4, 1029-1043.

11. Р. Беллман (1976) Введение в теорию матриц. М.: Наука.

12. R.I. Grigorchuk (1980) Symmetrical Random Walks on Discrete Groups. Multicomponent Random Systems. Adv. Probab. Rel. Topics. V.6. New York: Marcel Dekker, P.285-326.

13. Е.Б.Дынкин, М.Б.Малютов (1961) Случайные блуждания на группах с конечным числом образующих. Докл.АН СССР, Т.2, 399-402.

14. Б. Левит, С.А. Молчанов (1971) Инвариантные цепи на группах с конечным числом образующих. Вестник Московского Университета 6, 80-88

15. Y. Derriennic (1975) Marche aleatoire sur le groupe libre et frontiere de Martin. Z. Wahrscheinlichkeitstheor. Verw. Geb. 32, 261276.

16. S. Sawyer, T. Steger (1987) The Rate of Escape for Anisotropic Random walks in a Tree. Prob. Th. Rel. Fields 76, 207-230

17. H.Kesten, M.Kozlov, F.Spitzer (1975) A limit law for random walk in a random environment. Compositio Matematica. V.30, N2, 142-168.

18. Т.Лиггетт (1989) Марковские процессы с локальным взаимодействием. М.: Мир.

19. S.Lalley (1993) Finite range random walks on free groups and homogeneous tree. Ann. Probab. V.21, N4, 2087-2130.

20. T.Lindvall (1992) Lectures on the Coupling Method. Wiley series in probab. and math. stat. A Wiley-Interscince Publication JOHN WILEY& SONS,INC.

21. H.Furstenberg, H.Kesten (1960) Products of random matrices. Ann. Math. Stat. 31, N2, 457-469.

22. G.Frobenius (1912) Uber Matrizen aus nicht-negativen Elementen. Sitzsber. der Kgl. preuss. Acad. Wiss., 456-477.

23. В.И.Оселедец (1968) Мультипликативная эргодическая теорема. Труды Моск. Мат. Общества 19, 179-210.

24. В. Феллер (1967) Введение в теорию вероятностей ложения. Т1. М.: Мир.

25. А.А.Ширяев (1989) Вероятность. М.: Наука.