Случайные контекстно-свободные L-системы

• Автор: Петров, Алексей Игоревич
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 107 с.

Содержание
Введение

1 га-частичные корреляционные функции

1.1 Случай нулевой вероятности вырождения (Ув € 5 : Р(з -> е) = 0)

1.2 Вспомогательные результаты

1.3 Случай ненулевой вероятности вырождения (Зв Е в : Р(з е) > 0)

2 Эмпирические корреляционные функции..

2.1 Вспомогательные результаты

2.2 Надкритический случай

2.3 Критический случай

2.4 Случай нулевой вероятности вырождения.

3 Закон больших чисел
3.1 Надкритический случай
3.2 Критический случай
4 Поведение при больших 4, У
4.1 Вспомогательные результаты
4.2 Основная лемма
4.3 Существование предела при £, 3 —> оо
Список обозначений
Список литературы

Введение Структура работы
Работа состоит из введения, четырех глав, списка основных обозначений и списка литературы из 54 наименований.
В данной работе формулы, леммы и теоремы будут иметь номера из двух чисел, первое из которых — номер главы, а второе — номер формулы (леммы, теоремы) в этой главе. Определения нумеруются сквозным образом. Результаты других авторов нумеруются сквозным образом латинскими буквами.
Основные определения
Работа посвящена исследованию структуры предельных состояний цепей Маркова, определяемых стохастическими контекстно-свободными Ь системами. В работе мы будем придерживаться следующих соглашений.
Обозначим через Б = {51,..., конечное множество, которое мы будем называть алфавитом. Словом а над алфавитом Б назовем любую линейноупорядоченную последовательность символов из Б. Длину слова а будем обозначать |а|. Через е = 0 обозначим пустое слово. Множество всех конечных слов над алфавитом Б, включая пустое слово, мы будем обозначать через 6'*; = Б* {е}.
Определение 1. Для конечных слов
а = х /3 = ух • • • ут, т, п ^ О,
Хг, yj Е Б, г = 1,..., п, j = 1,т их композицией а(3 называется слово
СХ/3 Х • ■ • хпу • • • ут
Определение 2. Слово а Е Б* является подсловом слова 7 Е Б*, если существуют такие слова /?, 5 Е Б*, что 7 = (Зад.
Определение 3. Подстановкой ( или заменой ) называется упорядоченная пара слов а —6, а Е Б+, 6 Е Б*.
Определение 4. ОЬ-системой (контекстно-свободной Ь - системой) называется тройка й — (Б, С/, 7), где
• Б есть конечный алфавит;
• II есть конечное множество замен вида (в а), в Е Б, а Е Б*, такое, что для каждого в Е Б существует, по крайней мере, одно слово а Е Б* такое, что (в —» а) 6 (7;
ВВЕДЕНИЕ

• 7 = Х1Х2 ■ • • есть линейно упорядоченная последовательность символов Х{ £ S или начальное слово.
Аналогично 0 L-системам можно определить /L-системы, их определение отличается тем, что каждый символ может переписываться по разному в зависимости от своих соседей.
SOL-системы являются стохастическими версиями OL-систем. В этом случае каждой замене [s —* а) Е U соответствует некоторая вероятность P{s -> а} > 0 и для каждого s в S : J2a:(s^a)€U P{s —> си} = 1.
В определении SOL систем буква L пришла из имени Aristid Lindenmayer и означает, что L системы есть системы с параллельными заменами; число О означает, что развитие происходит без взаимодействия, т.е. каждый символ s € 5 заменяется независимо от своих соседей, т.е. замены происходят контекстно-свободно; символ S показывает, что система стохастическая.
Для исследования предельных свойств траекторий, порожденных SOL системами, мы будем использовать подход с точки зрения ветвящихся процессов (см. [б], [10], [22])). Напомним основные определения из теории ветвящихся процессов с несколькими типами частиц, которые нам понадобятся ниже.
Определим ветвящиеся процессы с |S| типами частиц, где (S'] есть число символов в алфавите S. Объектами в ветвящемся процессе будем считать символы 5i,..., 5|5| из алфавита S.
Начнем с обозначений:
• Все вектора в данной работе, если не оговорено противное, имеют размерность |S| и обозначаются или стрелочкой или жирным шрифтом, в зависимости от контекста - как удобней.
• Д|5[ = {(Д, ...,i|5|), Ч, •••Д|5| G Z4}, где Ъ+ есть множество всех целых неотрицательных чисел.
• Введем вектора размерности |S'| : 1 = (1,..., 1), 0 = (0, ...,0) и ej = (0,..., 0,1, 0,..., 0) - где 1 стоит на j-ом месте.
• Cs = [0,1] х • • • х [0,1] - есть единичный куб в - |А|-мерном пространстве действительных чисел.
Определение 5. Ветвящийся процесс
Л?1 = (Af Ц.,,)), 1« < |S|
с |S'| типами частиц есть счетная цепь Маркова с множеством состояний Д^ь
Начальное состояние есть вектор е^. Nfsi), г — 1,..., |S| мы интерпретируем как количество объектов типа % (символов si) в момент времени t ^ 0.
т-ЧАСТИЧНЫЕ КОРРЕЛЯЦИОННЫЕ ФУНКЦИИ.
Лемма 1.4. Если Nt есть надкритический ветвящийся процесс и вероятности подстановок удовлетворяют (1.1) - (1.2), то максимальное по модулю собственное значение д* матрицы Q равно 1.
Доказательство . Обозначим через g*(t) максимальное по модулю собственное значение матрицы Q — E(t). Будем доказывать от противного. Пусть иначе:
Пусть g* > 1, тогда в силу (1.21) существует Т > 0 : /t > Т : g*(t) > g' > 1. Тогда из (1.20) и теоремы Перрона-Фробениуса следует, что существуют То > Т, s Е S : f(s, То) > 1, что невозможно.
Пусть g* < 1, тогда в силу (1-21) существует Т > 0 : Vt > Т : g*(t) < g' < 1. Но тогда из (1-20) и теоремы Перрона-Фробениуса следует, что Vs £ S : Нт^осДйЛ) = 0, а это противоречит тому, что в надкритическом случае gl1!,..., дИ5!! < 1 ( см. [22, с.41] ) Следовательно, g* — 1. ■
Из оценки (1.21), леммы 1.4 и критерия сходимости произведений матриц ( см. [25, с.416] или [10, с.187] ) следует существование предела (1.20) при
rl*l(s) = lim rl*l(s,i), г = 1,..., S. (1-22)

В случае |а| ^ 2 рекуррентные соотношения на f(ot,t), t > 0 выглядят следующим образом:
г(аД) = (Q — E(t — l))r(a:, t — 1) + 5(a,t — 1), (1-23)
где матрицы Q и E(t— 1) были определены выше и 5(а, Г), Т ^ 0 есть вектор с компонентами ö^(a,T), k = 1,..., S, которые определяются следующим образом:
№(a,0)=Y;P(sk-+
VT > 0 : 5Ща,Т) =
К |Si m n
у Е Е Пр(ты(г) = л3),
m=2 ii,...,im=l п=2 (Л1,...,Аи)еД(п,а) j=