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

Работа состоит из введения, четырех глав, списка основных обозначений и списка литературы из 54 наименований.

В данной работе формулы, леммы и теоремы будут иметь номера из двух чисел, первое из которых — номер главы, а второе — номер формулы (леммы, теоремы) в этой главе. Определения нумеруются сквозным образом. Результаты других авторов нумеруются сквозным образом латинскими буквами.

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

Работа посвящена исследованию структуры предельных состояний цепей Маркова, определяемых стохастическими контекстно-свободными L системами. В работе мы будем придерживаться следующих соглашений.

Обозначим через S = {si,., sj^J конечное множество, которое мы будем называть алфавитом. Словом, а над алфавитом S назовем любую линейно-упорядоченную последовательность символов из S. Длину слова, а будем обозначать |а|. Через е = 0 обозначим пустое слово. Множество всех конечных слов над алфавитом S, включая пустое слово, мы будем обозначать через 5*- S+ = 5* {е}.

Определение 1. Для конечных слов, а = xi ¦ ¦ • хп, р = yi ¦ • • ут, т, п ^ О, yj? 5, г = 1,., n, j = 1,., га их композицией а/3 называется слово а/3 = х 1 • • • хпуг —-ут.

Определение 2. Слово a? S* является подсловом слова 7? S1*, если существуют такие слова /?, <5? 5*, что 7 = (Заё.

Определение 3. Подстановкой (или заменой) называется упорядоченная пара слов, а —" 6, а? S+, 6? S*.

Определение 4. ОL-системой (контекстно-свободной L — системой) называется тройка G = (S, [/, 7), где.

• S есть конечный алфавит;

• U есть конечное множество замен вида (5 —" a), s? S, а? S*, такое, что для каждого s? S существует, по крайней мере, одно слово, а? S* такое, что (s —" а)? U].

• 7 — '' • есть линейно упорядоченная последовательность символов Х{ G S или начальное слово.

Аналогично O-L-системам можно определить /L-системы, их определение отличается тем, что каждый символ может переписываться по разному в зависимости от своих соседей.

SOL-системы являются стохастическими версиями OL-систем. В этом случае каждой замене (s —" a) G U соответствует некоторая вероятность P{s -> а} > 0 и для каждого s е S: P{s а} = 1.

В определении SOL систем буква L пришла из имени Aristid Lindenmayer и означает, что L системы есть системы с параллельными заменамичисло О означает, что развитие происходит без взаимодействия, т. е. каждый символ s G S заменяется независимо от своих соседей, т. е. замены происходят контекстно-свободно-, символ S показывает, что система стохастическая.

Для исследования предельных свойств траекторий, порожденных SOL системами, мы будем использовать подход с точки зрения ветвящихся процессов (см. [6], [10], [22])). Напомним основные определения из теории ветвящихся процессов с несколькими типами частиц, которые нам понадобятся ниже.

Определим ветвящиеся процессы с |а9| типами частиц, где S есть число символов в алфавите S. Объектами в ветвящемся процессе будем считать символы ., S|s| из алфавита S. Начнем с обозначений:

• Все вектора в данной работе, если не оговорено противное, имеют размерность |5| и обозначаются или стрелочкой или жирным шрифтом, в зависимости от контекста — как удобней.

• = {(ii, zi, ., is G Z+}, где Z+ есть множество всех целых неотрицательных чисел.

• Введем вектора размерности l^l: 1 = (1,1), 0 = (0, ., 0) и ej = (0, ., 0,1, 0,., 0) — где 1 стоит на j-ош месте.

• Cs — [0,1] х • • • х [0,1] - есть единичный куб в R^l — |5|-мерном пространстве действительных чисел.

Определение 5. Ветвящийся процесс.

J^W = (JWiW (ei).JV (W (-|si)). с S типами частиц есть счетная цепь Маркова с множеством состояний.

Начальное состояние есть вектор вк. г = 1, .,|5| мы интерпретируем как количество объектов типа г (символов Si) в момент времени t ^ 0.

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

W (x) = /W (®b., a:|S|)= ]Г l,.^1—-^1, (В.1) jiv J|s|=0 где х = (хъ ., xS) С CS и p[k]{ji, ., js), к = есть вероятность того, что из объекта типа к, 1 ^ к ^ S появилось за один момент времени ji ^ 0 объектов типа 1, ., ^ 0 объектов типа S.

В общем, если N^ = (ji, ., js), то есть сумма ji + • • -+js независимых случайных векторов, ji из которых имеют производящую функцию /Ш, j2 векторов имеют производящую функцию /И, j|s| имеют производящую функцию /ИЭД. Если Nlk] = 0, то = 0.

В том случае, когда начальное состояние процесса А^ для нас неважно, мы будем опускать верхний индекс у Щ J и писать Nt.

Производящую функцию N^ при t > 0 обозначаем /Jfe'(x), fo (x) = х, ft (x) = (Л[11(х),.,/Р1](х))5 f (x) = fi (х) =(/W (x),.,/[l^(x)).

Определение 6. Матрицей средних ветвящегося процесса Л^, с (5| типами частиц называется матрица М с компонентами т^, = rriij = E (N^](Sj)) = ——х= (жь., а-|5,) Известно (см., например, [22], стр. 37), что.

Е (Nt+TNT) = NTM t, T⁰ (В.2).

Определение 7. Ветвящийся процесс Nt называется надкритическим, если максимальное по модулю собственное значение его матрицы средних М больше 1 и критическим, если равно 1.(см. [22] или [10]).

Определение 8. Ветвящийся процесс Nt с l^l типами частиц называется сингулярным, если его производящие функции f^(xi, ., xs), 1 ^ i < IS1] есть линейные по xi, функции без постоянных слагаемых (/х Е S :

Р (ж —> 0) = 0), таким образом, каждый символ имеет ровно одного потомка.

Замечание. Заметим, что если ветвящийся процесс является надкритическим ветвящимся процессом, то он автоматически является несингулярным ветвящимся процессом.

Определение 9. Матрицу М с компонентами т^ будем называть строго положительной и обозначать М > О, если min^ (те^) > 0.

Определение 10. Ветвящийся процесс Nt с |5| типами частиц называется положительно регулярным, если существует п > О такое, что Мп есть строго положительная матрица.

Мы будем рассматривать случаи, когда Nt является критическим или надкритическим ветвящимся процессом. Заметим, что свойство процесса быть критическим или надкритическим зависит только от его переходных вероятностей • ••, j|s|), определяемых формулой (В.4) и не зависит от его начального состояния, т. е. если N^ (над)критический ветвящийся процесс для некоторого jo5 1 ^ jo ^ S, тогда N^ является (над)критическим процессом и для j = 1,., l^.

Постановка задачи.

Каждая SOL система определяет цепь Маркова t = 0,1,2,. следующим образом:

Множество состояний процесса Zj7^ есть множество всех слов над алфавитом S. Во всей работе, если не оговорено противное, будем предполагать, что начальное состояние процесса Z^ есть фиксированное бесконечное слово 7 = хх2 • • •, где Xi G S, г = 1, 2,. Начальное состояние процесса мы будем также обозначать через 7(0) = (0)^2^(0) • • • = 7, где G S при г > 0.

Состоянием zj7' в момент времени t ^ 0 является слово:

7(0 = 47]W47lW—- где е 5, г = 1,2,.

Переходные вероятности определяются следующим образом: каждый символ х слова у (t) в момент времени t: независимо от других символов, заменяется на слово, а? S* с вероятностью Р (з- —> а) > 0, если (х а) (Е U и вероятность замены (х —> а) равна нулю, если (х —> а)? U. Мы будем исследовать структуру слова 7(t) при t —> 00.

Нам также понадобятся процессы zf к = 1,., I^l, определяемые S0L системами с начальными словами, состоящими из одного символа Sk Е S: zk к — 1,., |5| есть счетная цепь Маркова с множеством состояний S*, с теми же переходными вероятностями, что и у zjy, но начальное состояние zf^ есть 7^(0) = 2^(0) = Sk € S. Состояние zjfc' в момент t ^ 0 есть слово длины которое мы будем обозначать:

7W (t) = x[*t)xkt) ¦ —x[%[t)(t), где xft) E 5, г = 1,2, nW{t) = 0 при 7W (i) = 0.

Обозначим через п (а, /3), а € S+, /3 G S* число подслов, а в слове введя.

В.З) получим, что N^ = (JVj-^(si), есть ветвящийся процесс с |<5| типами частиц, начальным состоянием е^ и.

Р[к]{3ъJs) = Е (В.4) aeS*: n (s1,a)=j1,., n (sS, a)=js j|5|), к = 1,., |?| есть вероятность того, что из символа Sk S появилось за один момент времени ji ^ 0 символов ., ^ О символов.

Таким образом, SOL системы с начальным словом Sk 6 S порождают процесс zk который можно понимать как ветвящийся процесс с 1*91 типами частиц, в котором дополнительно введена нумерация частиц.

Краткий исторический обзор

Рассматриваемая задача возникла двумя способами: первый — как обобщение ветвящихся процессов на случай, когда дополнительно имеется нумерация частиц, и второй — изучение в терминах корреляционных функций предельного поведения траекторий порожденных случайными грамматиками и SOL системами.

Состояние исследований по теории ветвящихся процессов рассматривалось в книге В. А. Ватутина и A.M. Зубкова [1], а также, частично, в сборнике статей [15]. Мы же приведем только результаты, непосредственно связанные с тематикой данной работы.

В надкритическом случае:

Из теоремы Перрона-Фробениуса (см. ниже теорему Е) и формулы (В.2) очевидным образом следует.

Лемма. Пусть N^ есть положительно регулярный надкритический ветвящийся процесс с|5| типами частиц и матрицей средних М, которая имеет максимальное собственное значение g и соответствующие ему правый и и левый v собственные вектора с нормировкой (v • и) = 1 и (1 • и) = 1. Тогда lim —— = uk-v.

Г—>00 ql.

Теорема А. Пусть N^ = (./vf^(si),., A/f^s^i)) есть положительно регулярный и несингулярный надкритический ветвящийся процесс с (б^ типами частиц. Пусть матрица средних М этого процесса имеет максимальное собственное значение д и соответствующие ему правый и и левый v собственные вектора, нормированные следующим образом: (v • и) = 1 и (1 • и) = 1. Тогда существует неотрицательная одномерная случайная величина w^ такая, что filk] lim —ь— = w^ • v почти всюду t—> оо gf.

Причем Р (vj№ > 0) > 0 тогда и только тогда, когда выполнено.

Е (N[k](Sj) logN[kSj)) < оо Ю, J ^ |5|. (В.5).

Более того, если выполнено (В.5), то.

• p (wW = 0) = qW = Р (jvf1 — 0 при некотором t ^ 1), к = 1, S.

• преобразование ср^(х) = Ee~xuj[t i — 1,., |5| удовлетворяет р (х) = f где 6 х о/ р (х) = {<�рЩх),.,<�р№(х)).

• w^ имеет строго положительную непрерывную функцию плотности на множестве положительных чисел и имеет скачок в нуле на величину.

Эта теорема была впервые доказана Н. Kesten и B. Stigum (1966). До этого T. Harris (1963) доказал сходимость почти всюду: N^/g* к v-ш^ при предположении, что существуют все вторые моменты Nt. В критическом случае:

Теорема В. Если Nt есть критический ветвящийся процесс с типами частиц и E (JV]fc'(s^))2 < оо, г, k = 1,., |5|, то.

Ш и п^ Uk где и lim t Р (iVj J О) = —Т^ГТ' i-oo v t ^ - v • Q[u] m—1n—1 x] = [QM[x],., Q№[X]}.

Из этой теоремы, теоремы Перрона-Фробениуса (теорема Е) и формулы (В.2) очевидным образом следует:

Лемма А. Пусть щ есть положительно регулярный критический ветвящийся процесс с |5| типами частиц и матрицей средних М, которая имеет максимальное собственное значение g = 1 и соответствующие ему правый и и левый v собственные вектора с нормировкой (v • u) = 1 и (1 • и) = 1. Пусть E (7Vf](s*))2 < оо, i, k = 1,., S. Тогда t-^oo t.

Теорема С. Если Nt есть критический ветвящийся процесс с (^j типами частиц и E (A^(s-))2 < оо, г, k = 1,., S и если (w • v) > 0, то (Nt • w)/t при условии Nt т^ 0 сходится по распределению к случайной величине с плотностью.

Xх f (x) = —е Ti, х ^ О,.

7i где v • w).

71 =.

Эта теорема впервые была доказана Mullikin (1963) при предположении, что существуют третьи моменты. Данная же версия теоремы, предполагающая существование вторых моментов, была доказана Joffe и Spitzer (1967).

В случае, когда w ортогонален v, правильная нормировка была найдена P. Ney (1967): —*.

Теорема D. Если Nt есть критический ветвящийся процесс с 151 типами частиц и E (N[ksi))2 < оо, г, k = 1,., S и если (w • v) = 0, то (Nt • w)/Vt —* при условии Nt ф 0 сходится по распределению к случайной величине с плотностью, ,.

1 м.

Ых) = 7Г-е 72 > 0° < ^ < 00, 72 > О.

С другой стороны, как отмечалось выше, рассматриваемая задача возникла как изучение в терминах корреляционных функций предельного поведения траекторий порожденных случайными грамматиками и SOL системами. Некоторые сведения об основных направлений исследований теории L — систем и ее применений мы дадим в конце введения (более подробно, см., например, [18] - [20]). Отметим только, что изучение L — систем (и случайных грамматик) с использованием методов статистической физики, таких, как исследование термодинамического предела, техника кластерных разложений и т. д. началось недавно, см. [29]. В [29] рассматривались случайные грамматики с начальным словом у? Sz. Для них доказывалось существование и единственность динамики в термодинамическом пределе (см. [30]), доказывалось, что динамика является кластерной. Изучались инвариантные меры и поведения фрактального типа на больших временах.

Обзор основных результатов.

Основным инструментом исследований статистической структуры слов, порожденных^{ОХ-системами} с начальным словом у 6 Sz+ при времени стремящемся в бесконечность, в данной работе будут корреляционные функции. Напомним их определения.

Определение 11. Для любых t, j > 0 определим m-частичные корреляционные функции для процесса zj7': p[?](a-t) =p^(yi,., ym-t) = P^f) = yu 47|m-iW = Ут), где a = уi • • • ym есть произвольное слово из S+, yi,., ym € S, m > 0 и 7 есть произвольное начальное слово.

Нам также понадобятся эмпирические корреляционные функции, их определения мы дадим ниже.

Замечание. Терминология в этом определении (а также в определениях 12 и 15 эмпирических корреляционных функций) заимствована из статистической физики и отличается от принятой в теории вероятностей. Начинаем мы с доказательства почти очевидной леммы.

Лемма 1.1. Если Nt есть критический или надкритический ветвящийся процесс со строго положительной матрицей средних и существует К > 0 такое, что для любого s G S: P (s —> a) = 0 при |а| > К, то для любого бесконечного начального слова 7 = ¦ • •.

P (3t': |-у (01 < 00) = 0.

Все остальные результаты работы можно условно разделить на две группы:

• Надкритический случай, т. е. когда Nt является надкритическим ветвящимся процессом.

• Критический случай, т. е. когда Nt является критическим ветвящимся процессом.

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

Основной целью главы 1 является доказательство существования предела |а|-частичных корреляционных функций p^(a-t), j > 0 в надкритическом случае при t оо. Этот результат сформулирован в следующей теореме:

Теорема 1.1. Если Nt есть надкритический ветвящийся процесс и вероятности подстановок удовлетворяют.

Vx, s? S: P{x^s) >0, (В.6).

Ух eS: ^ Р (жа) = 1, (В.7) а€ 5″ Ма|СйГ то для любого слова a? S+, любого j > 0 и любого начального слова 7, |7| = оо существует предельная а-частичная корреляционная функция: irl?]{a) = lim pl?](a-t).

•i t—> 00.

Замечание. Заметим, что из условия (В.6) следует положительная регулярность процесса Nt.

Без ограничения общности доказательство существования проводится для j = I. Рассматриваются два случая.

В § 1.1 рассматривается случай, когда для каждого s Е S: P (s —" е) = 0. Доказательство теоремы 1.1 в этом случае было дано в [51] и приводится здесь для полноты изложения. В этом случае каждые первые |а| > 0 символов ., образуют конечную цепь Маркова (по t), являющуюся эргодической в силу предположений теоремы и, следовательно, имеющей стационарное распределение тт^а) = lim^oo (at).

В параграфах 1.2 и 1.3 рассматривается случай, когда существует s € S такое, что P (s —> е) > 0. В этом случае пишутся рекуррентные уравнения для rM (a, t) = P (nW (t)^Hxf (t) = zu ., x[^(t) = *|a|), t > 0, i = аналогичные обратным уравнениям Колмогорова для ветвящихся процессов и с помощью теоремы Перрона-Фробениуса (теорема Е) и критерия сходимости произведения матриц (теорема Н) доказывается существование предела r^(a) = lim Ala, t) t—> 00.

При этом, используя достаточно стандартную технику теории ветвящихся процессов, доказываются вспомогательные леммы:

Лемма 1.2. Если Nt есть надкритический ветвящийся процесс и вероятности подстановок удовлетворяют (В. 6) — (В. 7), то существует т, 0 < т < 1 и вектор-функция Q: Cs —> K^l такие, что для 0 ^ х < 1: q Q (x) при п оо, Q (q) = О, где q есть вектор размерности с компонентами qh] р (AfW q дЛЯ некоторого t ^ l) и функция Q (x) удовлетворяет следующим условиям.

О < Q (x) < оо для q < х < 1, |Q (x)| < оо для 0 ^ х < 1. и лемма.

Лемма 1.3. Если Nt есть надкритический ветвящийся процесс и вероятности подстановок удовлетворяют (В.6) — (В. 7), то для каждого j > 0 существуют С = C (j) > 0 и т < 1 такие, что, для всех t > 0, к = ., ks) выполнено.

Г P (ivf = к) < Ст i = l,.,|5| к: Ocfci-h-.+^i^j.

Доказательство следующей формулы завершает доказательство теоремы 1.1. оо тг М (а) = limpW (a^) = (pf ¦ r (a)) + • • • • г"), п=2 где г (а) есть вектор с компонентами г^(ск) и — е^, при = Si? S,.

1 < г < |5| и gi7l (t), n, t > 0 равна q^{t) при ai7l (0).

В главе 2 мы исследуем существования предельных (при t —" оо) эмпирических корреляционных функций в надкритическом и критическом случаях.

В § 2.1 мы напоминаем известные результаты из теории ветвящихся процессов с несколькими типами частиц для надкритического и критического случаев и выводим простейшие следствия из них (леммы 2.1 — 2.2).

В § 2.2 мы определяем эмпирические корреляционные функции в надкритическом случае и доказываем основной результат главы 2 в надкритическом случае — теорему 2.1.

Определение 12. В надкритическом случае для любого t > 0 и к = 1,., S определим эмпирические корреляционные функции:

И* л [k](t)).

ЕnW{t) — a + l где, а есть произвольное слово из S+.

Теорема 2.1. Если ветвящийся процесс Nt есть надкритический ветвящийся процесс со строго положительной матрицей средних и вероятности подстановок удовлетворяют (В. 7), то для любого слова a Е S+ существует предельная эмпирическая корреляционная функция li (a) = lim /j}kUa-t), k = 1,., 151, t—"оо независящая от k.

Основной идеей доказательства является написание рекуррентных уравнений для En (a, 1 < k < |5|, a Е S+ при t > 0, аналогичных обратным уравнениям Колмогорова для ветвящихся процессов. Используя эти уравнения, мы доказываем, что при t —> оо: En (а, 7^(2)) ~ Uk$d (a), где есть константа, зависящая только от слова a Е g > 1 есть максимальное по модулю собственное значение матрицы средних М ветвящегося процесса Nt и 1 ^ к ^ S есть компоненты правого собственного вектора и матрицы М, соответствующего собственному значению g с нормировкой (1-u) = 1. Для этого доказаны две вспомогательные леммы (леммы 2.3 и 2.4).

С другой стороны из теоремы Перрона-Фробениуса следует, что Е (t) ~ ukQtY^i=ivki где Vk, 1 ^ к ^ S есть компоненты левого собственного вектора матрицы М, соответствующего собственному значению д.

Рассматривая отношение Е n (a: и Е пЩ при t —> оо, мы доказываем существование предела /Jkcc, t) при t оо и, тем самым, завершаем доказательство теоремы 2.1.

В лемме 2.5 нами приведен пример подсчета /i (a) в случае нулевой вероятности вырождения (P (s —0) = 0 для всех s Е S) для слов одлины два —*.

Лемма 2.5. Если Nt есть надкритический ветвящийся процесс со строго положительной матрицей средних, вероятности подстановок удовлетворяют (В.7) и для всех s Е S: P (s —> 0) = 0, то для любого слова a Е S*, |ск| = 2 :

Ка) = т-~Т7—-тт (<*) 5 (vi + '-' + uis-iXe-/-A) v «где матрицы Ли В имеют размерность ^рх^ри^х^ря определяются через переходные вероятности Р (s —> /3,) s Е S, (3 Е S+ формулами (2.17) и (2.18) соответственно.

В § 2.4 приведен другой метод подсчета (и доказательства существования) эмпирических корреляционных функций в случае нулевой вероятности вырождения (Vs Е S: P (s —> 0) = 0.) Заметим, что если для всех х Е S :

Р (х —* 0) = 0 и существуют хотя бы один символ s G S и слово a G 1 такие, что P (s —" а) > О, то процесс Nt автоматически является надкритическим ветвящимся процессом.

Метод, рассматриваемый в § 2.4, был предложен в [51] и основан на уравнениях, аналогичных прямым уравнениям Колмогорова для ветвящихся процессов. Этот метод кажется более удобным в случае нулевой вероятности вырождения, однако он трудноприменим в случае, когда 3s Е S: P (s —> 0) > 0. Основываясь на этом методе в случае нулевой вероятности вырождения, мы приводим пример подсчета fi (a) для слов, а длины 3.

Лемма 2.9. Если.

VxeS: Р (х е) = 0, ^ Р{х (3) = 1.

Зе5+: feK и ветвящийся процесс Nt имеет строго положительную матрицу средних с максимальным по модулю собственным значением g > 1, то.

3) fi^R +^W ^ 0−1-Р где W есть матрица размерности х S|3, R есть матрица размерности |5|2 х |5|3 и Р есть матрица размерности l^l3 х l^j3. Матрицы W, Р, R выражаются через переходные вероятности по формулам (2.39), (2.42) и (2.43).

Этот пример мы используем при построении числового примера, показывающего, что мера /х (-) на словах из S+, вообще говоря, не бернулиевская и не марковская. Где под бернулиевской мерой мы понимаем меру, удовлетворяющую следующему определению:

Определение 13. Вероятностная мера /л (а) на словах, а Е S+ называется бернулиевской, если для любых двух слов а, (3 Е S+ выполнено: ц (а0) = fi (a) • ц ((3). а под марковской:

Определение 14. Вероятностная мера /л (а) на словах, а? S+ называется марковской, если существует такая стохастическая матрица Q размерности S х S такая, что для любого слова, а — у • • -уа, yi, ., У|а|? S, |а| > 1 выполнено:

Мш • • • Уа) = V>{y • • • ya-l) • Я{Уа-Ъ Уа).

В § 3.1 доказана теорема типа равномерного (по координате) закона больших чисел в надкритическом случае.

Для ее формулировки для всех то, те, t > 0, а € S+ и произвольного начального слова 7, |7| = оо введем следующее обозначение.

N^ (а, [то, п]) = п (л, я-WW ¦ • • 4%)) • —+.

Теорема 3.1. Если Nt есть надкритический ветвящийся процесс со строго положительной матрицей средних и вероятности подстановок удовлетворяют (В. 7), то для любого слова a Е S4″ и любого е > О существуют L (e, a) > 0 и t{s, a) > 0 такие, что для любых L > L (e, a), t > t (e, a), j > 0 и любого начального слова 7, |7| = оо выполнено:

— IL{OL).

L-a+ 2? < ?

Доказательство теоремы 3.1 разбито на пять лемм (леммы 3.1 — 3.5). Основной идеей доказательства этой теоремы является аппроксимация данного слова x^t) • • объединением случайного числа r (L) непересекающихся слов, А (Г), i = C (j) + 1, • • •, ((j)+r (L) (некоторые А (Т) могут быть пустыми) случайной длины таких, что.

Еп (а, А (Г)) = Еп (а, 7Щт)) j)+r (L).

Е (|А (Т)|) = Е (п^(Т)),? E (|A (T)|)~L.

Ш)+1 при больших L и некоторых 0 < Т < t, 1 ^ k (i) < S. ?(j) > 0 есть некоторая случайная величина.

А с другой стороны, из теоремы 2.1 следует, что при больших Т.

Е (пт{т)) ^ к<*а.

Значит,.

Ега (а, А (Т)) ~ /i (a) E (п^(Т)) = /i (a) Е (|Д (Т)|) или суммируя по i.

CC?)+r (x) C (j)+r (i).

СС?')+1 «=С (7')+1.

Т и r (L) подбираются так, чтобы при любых значениях Q (J) > 0,^о ^ 0, t0 = t—T и L > 0 отклонение Egf^ от Е^Йж Е было «небольшим». Тогда доказывается, что a. jjj + i]), ,.

L-a + 2 L.

Также в § 3.1 мы выводим следующее следствие из теорем 1.1 и 3.1: —*.

Теорема 3.2. Если Nt есть надкритический ветвящийся и вероятности подстановок удовлетворяют (В. 6) и (В. 7), то для любого слова a? S+, любого I > 0 и произвольного начального слова 7, |7| = оо выполнено: lim tS7^^) =.

Г, k=l.

Результаты главы 4 являются общими для надкритического и критического случаев, и мы приведем их ниже.

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

В § 2.3 мы определяем эмпирические корреляционные функции для критического случая.

Определение 15. В критическом случае для любого t > 0 и к — 1,., S определим эмпирические корреляционные функции:

Л] En (a>7IJfc]WM*]W⁰) где, а есть произвольное слово из S+.

И доказываем основной результат главы 2 для критическом случая:

Теорема 2.2. Если ветвящийся процесс Nt есть критический ветвящийся процесс со строго положительной матрицей средних и вероятности подстановок удовлетворяют (В. 7) и.

3xeS: (В.8) seS то для любого слова a? S+ существует предельная эмпирическая корреляционная функция fi (a) = lim/j}k](a-t), k = 1,., Sl t—"oo независящая от k.

Для доказательства этой теоремы пишутся рекуррентные уравнения для Еп (а, 7ol Е t > О аналогичные обратным уравнениям Колмогорова для ветвящихся процессов. Они в точности совпадают с рекуррентными уравнениями для En (a, j^(t)) в надкритическом случае. Используя эти рекуррентные уравнения, теорему Перрона-Фробениуса, теорему В и формулу 0) доказывается, что при t —> оо: Еп (а, ^kt)n^(t) > 0) ~ c (a)t, где с (а) есть константа, зависящая только от слова, а 6 5+ и правая часть не зависит от 1 ^ к ^ S. При этом доказаны три вспомогательные леммы (леммы 2.6 -2.8).

С другой стороны, из леммы, А следует, что > 0) ~ Ci, где константа С > 0 и правая часть не зависит от 1 ^ к ^ |5|.

Рассматривая отношение En (a^ry^(t)n^(t) > 0) к Е (гаЮ (?)|п^(2) > 0) при t —" оо мы доказываем существование предела (скt) при t —> оо и тем самым, завершаем доказательство теоремы 2.2.

В § 3.2 мы доказываем теорему типа равномерного (по координате) закона больших чисел в критическом случае: —>

Теорема 3.3. Если ветвящийся процесс Nt есть критический ветвящийся процесс со строго положительной матрицей средних и вероятности подстановок удовлетворяют (В. 7) и (В.8), то для любого слова a Е S+ и любого е > 0 существуют L (e, a), t{e) а) такие, что для любых L > L (s, a), t > t (e, a), j > 0 и произвольного начального слова 7, |7| = оо выполнено:

Доказательство этой теоремы аналогично доказательству теоремы 3.1 в надкритическом случае с некоторыми изменениями.

Основной идеей доказательства этой теоремы является аппроксимация данного слова x’y it) • • -x^L (t) объединением случайного числа r (L) непересекающихся слов j3i (T), i = + 1,. •, ССЛ + f (L) (некоторые Д (Т) могут быть пустыми) случайной длины таких, что.

Еп (а,&(Т)) = Еп (а,^Щ ал+гщ.

E (|A®|) = E (nf*"l®), ]Г Е (ШТ))~Ь i=c (j)+1 при больших L и некоторых 0 < Т < t, 1 ^ k (i) ^ S. CU) > 0 есть некоторая случайная величина.

Вводятся также случайные величины k (Si, L) = n (Si, 4^)+1(to) • • • 4cr)+r (L)(to)) (1 — P (n®(T) = 0)), где to = t — T, 1 ^ i ^ и доказывается, что при больших L г=1 <=С0')+1.

S| C (j)+r (L) fc (s^L) En (a, 7^(T)|n^(T) > 0) = En (a> У[ЩКТ))i=1 i=C0')+l.

А с другой стороны, из теоремы 2.2 следует, что при больших Т.

— ' ' ' - ч У ~ ^ лГ (j,(а, 1 < i < 5 .

E (nW (T)|nW (T) > 0) Р V ' - '' 1 1.

Значит,.

En (а, 7й СО И CO > 0) ~ А (а) Е (пи (Г)|тгИ (Т) > 0) или суммируя по г.

CU)+r (L) С (з)+гЩ E (n (a, A (T)))= J] Е п (а^ЦТ)) = i=CU)+1 «=ССг)+1 ]Г L) E (n (a, 7[г](Г))|пй (Г) > 0) -i=i.

S| /i (a) L) E (n г=1.

T и r (L) подбираются так, чтобы при любых значениях > 0, to ^ 0, £о = t-TnL > Оотклонение Е^н? &-СП) отЕЙ^н? Етг (а, A (T))/L было «небольшим». Тогда доказывается, что.

L~lal+ 2 ~ L.

Доказательство теоремы 3.3 разбито на восемь вспомогательных лемм.

В главе 4 в надкритическом и критическом случаях доказаны достаточные условия существования предела |а|-частичных корреляционных функций p^(a-t) при t, j оо и его совпадения с предельной эмпирической корреляционной функцией /и (а). Приведен пример, показывающий, что этот предел существует не всегда.

В § 4.1 мы напоминаем теорему о больших уклонениях (теорема I) и локальную теорему (теорема J) для сумм независимых случайных величин и выводим из них.

Лемма 4.3. Пусть ••• есть последовательность независимых случайных величин, принимающих значение в Z. Будем предполагать, что существует константа I? Z+ такая, что для каждого j > 0 существует г = i (j), 1 ^ г ^ I такое, что для любого m € Z :

Pjm = = m) = pW, где для рто, г = 1,.,/, то Е Z существует константа К > О такая, что.

Для каждого % существует m = m (i), 0 ^ m < К, такое, что выполнено: п.

РЙ > 0, Рш+1 > о,.

• рй = 0 при тп [О, К],.

• = 1.

Тогда для каждого <5: 0 < <5 < | существует АГ0 > 0 такое, что для всех n > No, N > 0 выполнено: n n Q.

J=1 3=1 с> о. п1 «.

Также в этом параграфе доказывается вспомогательная лемма 4.4. Основываясь на лемме 4.3 и лемме 4.4 в параграфе 4.2 доказывается.

Лемма 4.5. Если Nt есть надкритический или критический ветвящийся процесс и для каждого символа s Е S существуют такие слова a = cu (s), (3 = /3{s) € S*, что a = (3 + 1, P (s -> a) > 0, P (s (3) > 0, MseS: P (s <0 = 1, aGS’MaKiir то для любого слова a G S+ и любого e > 0 существует Jq > 0 такое, что для любых t > 0, j > Jo и любого начального слова Т? 1т1 ~ 00 выполнено: р^а-^-р^а-Щке (В.9).

Отметим также, что скорость убывания левой части (В.9), которую можно получить, доказывая эту лемму, основываясь на лемме 4.3, не позволяет из нее вывести существование предела lim^00p^(at) при t > 0. Улучшить же скорость сходимости в лемме 4.3, основываясь на теоремах I и теорема J также не представляется возможным.

Основываясь на лемме 4.5 и теореме 3.1 (для надкритического случая) и теореме 3.3 (для критического случая) в параграфе 4.3 доказывается основной результат главы 4 — теорема 4.2: —?

Теорема 4.2. Если Nt есть надкритический или критический ветвящийся процесс со строго положительной матрицей средних М и для каждого символа s € S существуют такие слова a = a (s) и /3 = (3{s) такие, что а| = (3 + 1, P{s -«¦ a) > 0, P{s (3) > 0, (В.10).

Ж ^ 1: Vs е S: Yl Р (5 = то для любого слова a? S+ и произвольного начального слова 7, |7| = оо существует предел lim p^a-t) = /i (a), j-юо J t—>00 независящий от 7. Где /i (a) есть предельная эмпирическая корреляционная функция, определяемая формулой ц{а) = lim /^(а- *) = Ит ^^1, k = 1,., S.

->оо £->оо t mKi[t) — |а| + 1 в надкритическом случае и формулой а) = km «I (a-t) = jS Е (nH (<)|nW (t) ^ Q) |а| + * = 1. Ю в критическом случае.

В надкритическом случае, если дополнительно выполнено условие.

Vx, seS: P (s х) > О, то существует также и повторный предел lim limp-г = limpyl (a'}t) = fi (a).

ОО t—>00 J j—>.'ОО ^ oo.

Заметим, что если выполнены все условия теоремы 4.2, то //(а) является вероятностной мерой на словах фиксированной длины, т. е. fi (a) неотрицательна, аддитивна и для любого m > 0: X) aeS+: ы=тМа) = 1.

В этом же параграфе мы доказываем предложение 4.4 показывающее, что условие (В. 10) в теореме 4.2 существенно. Если оно не выполнено, то предел lim^oo^oop^a-^), а? может и не существовать.

Краткие сведения об L — системах и грамматиках.

Аналогом L — систем в случае, когда замены происходят не параллельно, а последовательно являются грамматики. В информатике дается следующее определение грамматик:

Определение 16. Грамматикой с нетерминальными символами называется четверка G — (W, V, U, 7), где.

• W есть конечное множество, элементы которого называются нетерминальными символами;

• V есть конечное множество такое, что 7 0^ = 1, его элементы называются терминальными символами;

Алфавит S определяется как объединение множеств W и V: S = W U У;

• U есть конечное множество подстановок: {а —> ?}, где си есть слово над S, содержащее по крайней мере один символ из W, а <5? S*;

• 7? W есть начальное нетерминальное слово.

Разделение алфавита на терминальные и нетерминальные символы позволяет, в частности, отфильтровывать, по крайней мере, некоторые неподходящие слова.

Определение 17. Высказывание определяется следующим образом: 7 есть высказываниеесли а/Зт есть высказывание и {(3 —5) € [/, то адт тоже есть высказывание.

Предложением (или словом), порожденным грамматикой (7, называется высказывание, не содержащее нетерминальных символов.

Языком L{G), порожденным грамматикой G, называется множество всех предложений, порожденных грамматикой G.

Две грамматики Gi и G2 называются эквивалентными, если L{Gi) = L{G<2). Приведем простейшие классы грамматик. Грамматика называется:

• контекстно-зависимой, если каждая замена из U имеет вид: где, а — uAu2, (5 = щхщ Щ, Щ? 5*, А? W, х? S+;

• линейной, если каждая замена из U имеет вид: п —> агп (3, где п, т Е W, a,/3eV*;

• линейной справа, если каждая замена из U имеет вид: п —" am, где п, т eW, а е У*;

• контекстно-свободной, если каждая замена из U имеет вид: п а, где neW, ae S*;

• регулярной, если каждая замена из U имеет вид: п —а, где п Е W, аЕVUVWU е.

Приведем классы L-систем, аналогичные классам контекстно-свободных грам матик:

• OL-система имеет лишь замены вида s —" a, s Е S, a E S* и для каждого s E S имеется, по крайней мере, одна замена s a;

• DOL-системы (детерминированнные OL-системы) — это ОL системы, в которых для каждого s Е S имеется ровно одна замена s —> а, а € S*;

• POL-системы не содержат замен вида s —"• е, s Е S*.

• EOL-системы. В них разрешено использование нетерминальных символов, т. е. алфавит делится на две части — терминальные символы и нетерминальные. Но только слова из терминальных символов считаются принадлежащими языку L (EOL).

• контекстно-зависимые Х-системы имеют замены вида: asp —> cry (3, s Е 5, а, 7,/3? S* например, 2Ь-система имеет замены вида as (3 —> ajfi, где |a|, |/?| ^ 2.

Заметим, однако, что языки, порожденные одинаковыми грамматикой и L-системой различаются: действительно, если рассмотреть грамматику G[ = (И7, У, U, а], где VT = {а}, У = 0, U = {{а а2}} и 0L систему Gi — (S, U, а), где S = {a}, U = {{а —> а2}}, то очевидно, L{G[) = {апп ^ 0} ф {а2Пп ^ 0} = L (Gi). Это различие объясняется тем, что в грамматиках замены последовательны, а в L-системах параллельны.

Теория грамматик изучает траектории, т. е. последовательности слов 7 = 7(0), 7(1), ., 7(t) такие, что для любого j = 1,1 — 1 слово + 1) получается из 7(j) удалением некоторых подслов с^ слова 7(7) и добавлением вместо них слов Si, т. е. заменой щ на где (щ —> Е С/. Т. е. замены происходят последовательно.

Теория L-систем Линденмайера исследует траектории, для которых в каждый дискретный момент времени все возможные замены должны быть выполнены одновременно и независимы. Это налагает некоторые ограничения, так как может возникнуть неоднозначность. Поэтому обычно рассматривают лишь случай, когда в левой части каждой замены стоит только один символ (т.е. ОL — системы).

Одним из основными направлений исследований в теории грамматик и L-систем является изучение структур языков, обладающих каким-то свойством, изучение отношений между языками, порожденными различными грамматиками и различных свойств этих языков. Текущие состояние исследований в данном направлении можно найти, например, в [18] - [20].

Другим важным направлением исследований в теории грамматик и L систем является моделирование различных процессов.

Первые работы в этом направлении принадлежат, по видимому, Axel ТЬие [46,47]. В середине тридцатых годов Alan Turing опубликовал работу [48], основной идеей которой является построение модели вычислений.

В середине 1950;х годов, следуя идее Чарльза Дарвина связать эволюцию языков с биологией, большой вклад в развитие грамматик и грамматических структур языка дала лингвистика (Noam Chomsky [16] и др.) Лингвисты путем анализа слов и предложений языков пытаются находить сходства и различия между различными языками, объединять похожие языки в группы, отслеживать изменение языков во времени вместе с миграцией языков и людей. Для более глубокого изучения истории необходимо связывать генетические, археологические и лингвистические исторические источники. Молекулярная генетика может тестировать некоторые элементы предложенных теорий эволюции языков утверждений. Например, сравнивая насколько отличаются гены в разных поселениях можно видеть насколько это подтверждает предсказания, полученные из различия языков. Генетические и лингвистические истории, по крайней мере, грубо соответствуют друг другу, поскольку обе отклоняются в случае раздельного развития. Соответствующую диаграмму, базирующуюся на работах Luigi Luca, Cavalli-Sforza и Maerritt Ruhlen можно найти в [37]. В частности, из нее видно, что распределение генов хорошо коррелирует с распределением языков. Специфичные задачи моделирования дают начало разнообразным языкам. Типичным примером этого являются L-системы введенные Aristid Lindenmayer [28] в 1960;х годах для моделирования растений. Объединяя локальные процессы, имеющие место на уровне индивидуальных модулей, в образцы, связанные с развитием структуры целых растений, модели L-систем адресуют центральную проблему морфогенезиса: описание и понимание механизмов жизни организмов, посредством которых они приобретают свою форму. Как правило, закон, по которому развивается организм не известен, а имеется лишь набор статистических данных, поэтому кажется, что стохастические L системы должны более точно отражать действительность, нежели детерминированные. P. Eigh-horst и J. Savitch в [17] изучали свойства функции роста стохастических ОL-системы и элементарные условия эквивалентности двух SQL-систем. При этом использовалась стандартная техника ветвящихся процессов (при этом авторы переоткрыли некоторые результаты теории ветвящихся процессов). Соотношение между языками порожденными специальными 501/-системами и Е’ОЬ-системами изучались в [50].

Огромные возможности моделирования L систем сделали возможным их применение во многих областях науки (лингвистика, информатика, статистическая физика, биология и др.) В частности, в биологии L системы используются как для исследования первичной и вторичной структуры ДНК и РНК (большое количество ссылок можно найти в [13], [43], [14], [44], [9]), так и для для визуализации структур и моделируемых процессов в компьютерной графике (см, например, Смит [45]). Применение L систем в компьютерной графике обусловлено, в первую очередь, их тесной связью с фракталами [36]. Приведем пример, несколько выходящий за рамки данного выше определения L — систем, но тесно с ними связанный (слова это одномерные структуры, расширение определения L — систем на «многомерный слу-чай» см. в [20]):

Пусть множество U состоит из замену.

И «И и начальное слово 7 есть квадрат, тогда 7(0)-П 7(1)= УД 7(2) =.

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

Основные результаты данной диссертации опубликованы в работах автора [52] - [54].

Они докладывались на Большом научно-исследовательском семинаре кафедры теории вероятностей МГУ под руководством чл.-корр. РАН, проф. А. Н. Ширяева, на семинаре лаборатории больших случайных систем в МГУ под руководством проф. В. А. Малышева, на семинаре в ИППИ под руководством проф. Р. А. Минлоса, на семинаре в МИ РАН под руководством проф.

1. Ватутин В. А., Зубков A.M. Ветвящиеся процессы, в кн.: «Итоги науки и техники», (сер. «Теор. вероятн. Мат. статист. Теорет. кибернетика.» М., Т.23, с.3−67,1985.

2. Гантмахер Ф. Р. Теория матриц, Москва, «Наука», 1967.

3. Курош А. Г. Курс высшей алгебры, Москва, «Наука», 1968.

4. Петров В. В. Суммы независимых случайных величин, Москва, «Наука», 1972.

5. Петров В. В. Локальная теорема для решетчатых распределений, // Доклады АН СССР, 1957, т. И5, № 1, с.49−52.

6. Севастьянов Б. А. Ветвящиеся процессы, Москва, «Наука», 1971.

7. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления, Т. 1−3, Москва, «Наука», 1969.

8. Ширяев А. Н. Вероятность, Москва, «Наука», 1989.

9. Математические методы для анализа последовательностей ДНК, под редакцией М. С. Уотермана, Москва, Мир, 1999.

10. К.В. Athreya, P.E.Ney, Branching processes, Springer-Verlag, New-York, 1972.

11. K.B. Athreya, A.N.Vidyashankar.Lan/e deviation rates for supercritical and critical branching processses. In IMA, v. 74 «Classical and Modern Branching Processes», 1997, p. 3−18.

12. K.B. Athreya, A.N.Vidyashankar. Large deviation results for branching processes, -II, the multitype case, j j Annals of Applied Probability, 1995, V. 5, Ж 2, p. 566−576.

13. Michael P. S. Brown, RNA modeling using context-free grammars, j j PhD thesis, University of California, Santa Cruz, 1999.

14. Michael P. S. Brown, Small subunit ribosomal RNA modeling using stochastic context-free grammars, // ISMB, 2000, p. 55−66, (www.aaai.org).

15. Classical and Modern Branching Processes, 1997, IMA, v. 74.16.