Содержание к диссертации
Введение
1 Марковские модели 11
I Двоичные цепи 11
1. Обозначения 11
2. Распределение (п) 12
3. Совместное распределение 13
4. Производящие функции 16
5. Распределение числа единиц 17
6. Распределение числа 1-серий 18
7. Первые моменты числа единиц 19
8. Первые моменты числа 1-серий 20
9. Ковариации 22
10. Нормальное приближение 25
11. Первые моменты /с-серий 27
12. Накрывающие серии 31
II Троичные цепи 41
1. Обозначения 41
2. Распределение (п) 43
3. Производящие функции 44
4. Среднее число а-событий 47
5. Дисперсия числа а-событий 48
6. Среднее число а-серий 55
7. Дисперсия числа а-серий 56
8. Ковариации 59
9. Частные случаи 64
2 Применения 70
I Сложение случайных чисел 70
1. Последовательное суммирование 70
2. Параллельное суммирование 74
II Применение в метеорологии 76
1. Марковская модель и ее адекватность 76
2. Результаты и их анализ 80
III Применение в социологии 88
1. Марковская модель 89
2. Результаты и их анализ 91
3. Структурные классификации семей 97
Заключение 112
Литература
Введение к работе
Цепи Маркова или марковские последовательности впервые были рассмотрены в книге [23], причем первая последовательность, которую описал А.А. Марков, была именно двоичной. В дальнейшем двоичные цепи, как важный частный случай конечных цепей Маркова, выделялись в большинстве работ, связанных данной тематикой. Троичные последовательности являются логичным обобщением двоичных цепей и также имеют самое широкое применение в различных приложениях.
Важнейшие результаты в теории марковских цепей связаны с именем А.Н. Колмогорова. Им была доказана локальная предельная теорема для конечных цепей Маркова ([19]), а его учениками проведен полный асимптотический анализ числа попаданий в одно из состояний для двоичных (Р.Л. Добрушин, [14]) и конечных (Л.Д. Мешалкин, [24]) цепей Маркова. Первые моменты числа попаданий в одно из состояний для конечных цепей, используя выражения, содержащие характеристические функции, получил В.И. Романовский ([25]).
Теория серий в случайных последовательностях развивалась параллельно с теорией марковских цепей. В случае независимых испытаний выделяются статьи А. Муда [44] (двоичный случай) и В.Л. Гончарова [11] (конечный случай), где рассматриваются распределения серий различных типов,
а также максимальной длины серии. Независимые испытания являются важным частным случаем марковской зависимости, и в дальнейшем это будет всюду подчеркиваться.
Локальная предельная теорема для числа серий в конечных марковских цепях была доказана в [33]. Теми же авторами в [33], [32], [17] получены точные формулы первых моментов числа серий для конечных цепей Маркова. Также рассмотрены различные частные случаи.
90-е годы прошлого века отмечены большим количеством работ по теории серий в марковских цепях. Подробная классификация различных типов серий дана в [38], где для них получены матричные производящие функции и рассмотрены некоторые численные примеры. Серии данной длины и различные связанные с ними характеристики исследовались в [40], [41], [50].
Вышеприведенные работы по теории марковских цепей обуславливают актуальность применения марковских моделей при описании естественных и социальных процессов. Во-первых, хорошо разработанный аппарат и сравнительно небольшое число входящих в марковскую модель параметров обеспечивают относительную простоту исследования по сравнению, например, с динамическими моделями. Во-вторых, для рассматриваемых процессов характерны случайные отклонения и взаимосвязь переменных во времени. Стохастические модели позволяют учитывать эти отклонения.
Выбор дискретной модели обусловлен тем, что наблюдения происходят в дискретные моменты времени с заданной периодичностью. Конечное множество значений объясняется тем, что в большинстве реальных процессов число возможных состояний системы так или иначе ограничено. Марков-
екая модель определяется вектором начальных и матрицей переходных вероятностей.
Множество значений марковской цепи выбирается в соответствии с характером наблюдений и условиями задачи. Очень часто число условий задачи можно уменьшить, объединив некоторые из них или отбросив несущественные. Таким образом, многие марковские модели так или иначе оперируют двух- или трехфазным множеством состояний. Важность данных частных случаев диктуется еще и тем, что для них получаются более простые формулы по сравнению со случаем произвольного конечного числа состояний. По этим формулам можно производить эффективные вычисления. Вместе с тем, несмотря на их относительную простоту, двоичные и троичные цепи нельзя считать полностью исследованными. Именно рассмотрению серийной структуры, а также исследованию поведения числа серий и событий в данных цепях посвящена первая глава диссертации. Исследуются как классические характеристики серий, так и ранее редко встречавшиеся в литературе функционалы на марковских цепях, также исследуются их совместные распределения. Достаточно универсальный метод производящих функций, сводящийся к построению рекуррентных соотношений, позволяет получить собственно производящие функции, первые и вторые моменты, а также сами распределения рассматриваемых функционалов. Из новых результатов можно отметить исследование совместных распределений и зависимости различных функционалов (в частности, числа серий и числа событий), показано, что в двоичном случае число событий х(п) и число серий у(п) асимптотически некоррелированы, то есть
К(х(п),у(п)) = 0(1/п). 6
Получены формулы для первых и вторых моментов рассматриваемых характеристик, удобные для расчета. Также обнаружено следующее важное свойство марковских последовательностей: в отличие от последовательностей независимых случайных переменных, в марковских цепях вероятности длин серий могут не всегда убывать с возрастанием числа испытаний п, и соответствующие распределения могут иметь сложный характер. Исследуются условия, при которых благодаря марковскому свойству возникает особенность: вероятности возрастают вместе с длиной серии.
Во первой части второй главы рассмотрен модельный пример, описывающий задачу о переносе разряда в компьютерных вычислениях. Данный перенос определяет скорость вычисления суммы. На данном примере показано применение результатов для марковских цепей с двумя и тремя состояниями.
Во второй части второй главы рассматриваются марковские модели в метеорологии. Стохастические процессы достаточно давно используются при моделировании временных рядов сумм осадков, причем как непрерывные, так и дискретные. К первым относятся непосредственно марковские процессы ([43]) и процессы, траектории которых моделируются методами Монте-Карло ([16]). Работ, использующих дискретные модели, заметно больше. Одним из наиболее часто встречающихся методов в литературе является метод приближения данной траектории кривой какого-нибудь известного распределения, в частности, в роли последних выступают Г-ра-спределение ([36], [48]), распределение Пойа ([45]), ^-распределение ([49]) и другие. Непосредственно дискретные марковские модели (с различным уровнем связности и числом состояний) рассматривались в работах [47]
(два состояния, простая цепь), [39] (семь состояний, простая цепь), [37] (два состояния, сложность цепи варьируется в зависимости от рассматриваемой местности). Во всех этих работах марковская модель используется только для расчета простейших характеристик, а дальнейшее исследование серийной структуры идет за счет различных предположений (например, в работе [39] предполагается, что количество осадков за сезон распределено равномерно или экспоненциально). В диссертации исследование серийной структуры рассматриваемой последовательности опирается на результаты первой главы. Используются данные наблюдений 1969 - 1983 гг. по западной (равнинной) части Новосибирской области. Строится марковская модель, описывающая последовательности сухих и дождливых суток, обосновывается ее адекватность. На основе формул первой главы считаются теоретические вероятности, которые используются при описании "экстремальных" погодных явлений (длинных сухих серий и серий из дождей), а также для исследования серийной структуры. Практическая важность поставленных задач заключается, в частности, в том, что на основе модельных реализаций, размер и число которых в принципе ничем не ограничены, можно вычислять такие климатические характеристики, которые по имеющимся данным наблюдений оценить либо трудно, либо вообще невозможно. Кроме того, модель позволяет вычислять характеристики, которые в климатические справочники не входят и не могут быть получены путем пересчета содержащихся в них показателей.
В третьем разделе второй главы, посвященном применению математических моделей в социологии, рассматриваются некоторые алгебраические модели классификации семей и марковские модели динамики размера се-
мьи, числа семейных поколений и числа детей в семье. Используются данные переписей 1994, 2000, 2002 гг. В последних исследованиях, проводимых демографами, социологами и экономистами все больше заметна тенденция к изучению населения не как совокупности индивидов, а как совокупности семей ([9], [26]). Состав семьи, а также другие ее характеристики, часть которых рассмотрена в работе, определяет и влияет на множество самых различных демографических процессов, основным из которых (и очень важным для России ввиду затянувшегося демографического кризиса) является воспроизводство населения. При этом прогнозирование численности и состава семей — одна из наименее разработанных областей как российской, так и мировой демографической науки, в частности, проблемам, с этим связанным, посвящена книга [1]. Причина этого — в сложности и изменчивости элементов структуры семьи. Моделирование трансформации структуры семьи в процессе ее жизнедеятельности представляет значительные алгоритмические трудности и плохо обеспечено статистической информацией. Данная проблема детально анализируется в статье [10]. Различные стохастические модели в социологии можно найти в [8]. Обзор математических методов (в том числе и марковских), используемых при изучении семейной структуры, можно найти в работах [2] и [42]. В диссертации рассматриваются марковские модели, описывающие число детей в семье, количество членов в семье и число поколений в семье.
Последний параграф третьего раздела посвящен проблеме классификации семей, которая является одной из центральных для демографии и связанных с нею областей социологии. Обычно применяемые при переписи классификации семей не обладают достаточной подробностью и строго-
стыо. Они не позволяют вычислять многие важные демографические, экономические, социальные, этнические и культурные характеристики семей. В диссертации описаны подробные и математически строгие классификации семей, учитывающие пол, возраст и другие нужные для исследования признаки членов семьи. Предлагаемые алгебраические модели позволяют описывать семьи и семейные структуры этнических и региональных групп населения любой сложности. Благодаря строгой формализации их удобно использовать при компьютерной обработке конкретных данных.
Для предлагаемого представления семьи специальной матрицей необходимо разбить семью на простые части и на семейные поколения. Они являются главными элементами структуры семьи. Разработан общий алгоритм разбиения семьи на простые части и семейные поколения. Его компьютерная реализация позволила провести исследования некоторых конкретных групп населения. Предлагаемый алгоритм можно применять и для решения других задач, где нужно разбивать на части множества с определенными для них отношениями порядка и эквивалентности.
Рассматриваются марковские модели, описывающие динамику размера семьи, числа поколений и числа детей в семье. Моделирование этих характеристик семьи тесно связаны с ее основной функцией — воспроизводством населения. Адекватных математических моделей этого сложного процесса не существует. Но конструирование простых моделей, которые позволяют строить правдоподобные гипотетические прогнозы и выявлять намечающиеся тенденции, имеет научное и практическое значение.
Результаты диссертации опубликованы в работах [3] - [6], [22], [28] - [31].
Совместное распределение
Каждая из реализаций последовательности , для которой выполнено (0) = а, (п) = Р, х(п) = г, у(п) = j, имеет одну и ту же вероятность Pap(iJ,п) =аа{\- а)1-"?1- (1 - ру-Р (1 - q)j-a q"-i-i+ +0. (l.l) В самом деле, из определений следует, что Pa/jfti,n) = flc(0)(l-a)W(0)x Е №-\ш Ё Цк-\){\-т) ,л . Е (i(k-i))t{k) ± (1- -1))(1- ( )) Xpfc=i (1 — p) =i (1 — 7) =1 gfc-i Как легко проверить, п s(n)-y(n) = ( ;-1)« ), п 2/(п)-«п) = $( ;-1)(1-« )), fc=i У(П)-«О)= (1-«Л-1))«Л), п п - s(n) - у(п) + «0) + (п) = Х; (1 - да - 1)) (1 - №)) k=l Поэтому pap(i,j,n) = aWHl-a)1-Wx х х(п)-у(п) ц _ \у{п)-(п) Q _ у(п)-(0) П-Х(П)-у(п)+ф)+(п) и при (0) = а,,(п) = /3,х(п) = г,у(п) = j получается равенство (1.1). Заметим, что Pap{h3,п) = 0 (г п + 1 или і j или j [п /2] + 1), Ра/з(і,0,п) = 0 (г 0) ([rr] обозначает целую часть вещественного числа х). Выделяются вероятности для единственных полных 0-серии и 1-серии: рв/3(0,0, п) = (1 - а) (1 - Р) (1 - a) f, ра/3(п + 1,1, n) = арарп.
Рассмотрим событие toa(3(i,j,n) = (:(0) = а,(п) = /3,х(п) = г,у{п) = j}.
Пусть Pap{i,j,n) = Pr{Qap(i,j,n)}. Тогда из сказанного в 3.1 следует: Pa0(i,j,Tl) =Caf3(i,j,n)pap(i,j,7l), (1.2) где ca0(i,j,n) = ca,rd(Qap(i,j, п)). Этот коэффициент легко вычислить, используя известную формулу для числа s (т, к) разложений натурального числа т на к слагаемых. Для целых к, т положим: = -гт-( 7Т7 при 0 к т, I 1 = 0 в остальных случаях. k) к\{т — к)\ \к J Имеем: s(m, к) = (7Гі) При 1 г та, 1 j [та /2] + 1 верны равенства: cap(ij,n) = s (г J) s (та - г + 1J + 1 - а - (3) = Г _ j ( " l_ ) (1.3) (г единиц распределяются по j 1-сериям, и та — г + 1 нулей распределяются по j + 1 — а — (3 0-сериям). Из (1.1) - (1.3) следует, что = (г - 1\ / та - г \ а _ ay-api-j _ру-Р (х _ qy- qn-i-j+«+P, \j -IJ \j-OL- /3J (1.4) Введем обозначения Ь(к,т,х)= (}хк(1-х)т-к, Хар = (аа + (1 - а)(1 - a)) (J3 (1 - д) + (1 - 0) (1 - р)). При 1 г та, 1 j [п /2} 4-1 равенство (1.4) эквивалентно равенству Рар(і,3,п) = Хар b(j - 1,і - 1,1 -р) b(j - а - Р,п - і,1 - q), (1.5) 3.3. Рассмотрим событие ft(M,n) = { : ж(п) = г, з/(та) = j} = JilQ/?(i,j,n). Из сказанного в 3.2 следует, что при 1 г п, 1 j [n/2] + 1 для вероятности Р(г, j, та) = Pr{fi,(i,j,n)} верны равенства: P{hhn) = Pap{iJ,n) = = Ь (j - 1, г - 1,1 - р) Ха/?Ь (j - а - Р, та - г, 1 - q). (1.6) а,/? Выделяются вероятности для единственных полных 0-серии и 1-серии: Р(0,0, п) = (1 - a) qn, Р(п + 1,1, та) = арп. (1.7) Найдём Е(х(п)у(п)). Для этого продифференцируем производящую функцию h(s,t,v) по s и t, взяв значение производной в точке 5 = 1, t = l: _(a+(l-a-q)v)(l-(l + d)v + (2pq-d)v2) n«V l v - (1- )3(1- )2
Разлагая полученное выражение в ряд по степеням v, получаем: h"t(l, 1, v) = (а + (1 - q - а{р + q + 1)) v + (qd - p + a(l + 2pg)) v2+ +(1 - a - q)(2pq - d)v ) (k + 1) Л M Ltil,,» = A;=0 n=0 oo = ,(1,1) , n=0
После некоторых преобразований находим: /г ( п)(1,1) = Е{х(п)у(п)) = п262(1 - р) + А п + В + Д(п), (1.21) где Л = 6 (2(a - 6)(1 -6) + 1-6(1- 6)(1 + d)), С = 2(a - 6)6(1 - 6), 5 = a + - - ((a -b)(d- 26(1 -6)(1 + /)) + 262(1 - b)d), J. (Jb D = -—Ц ((a - 6) (d - 26(1 - 6)(1 + d)) - 262(1 - b)d), 1 — a R{n) = Cndn + 6 f\ 9.2. Для стационарной последовательности (а = 6) коэффициенты в выражении (1.21) существенно упрощаются: d \ l-dr А = 6 (1 - 6(1 - 6)(1 + d)), = 6(1 + 26(1 - 6) R(n) = -262(1 - 6)—. В случае последовательности Бернулли, когда а = 6 = ри і = 0, эти равенства превращаются в A = p(l p(l-p)), В = р, R{n) = 0. 9.3. Вычислим ковариацию Cov(x(n),y(ri)) числа 1-событий и 1-серий. После некоторых преобразований получаем: Cov(rc(n),y(n)) = п6(1 - 6)(1 - 26) + Со + ДС(п), где 1 h Со = - -: ((а - 6) (1 - а - 26 - М) + 6 + 2b2d), Cl = b(2q-pq-p2), С2 = = -т- -j {{а - 6) (a (6-(1- b)d) - 26(1 -6) + (1- 2b)d) - 262(1 - b)d) , С3 = r bd, RC{n) = dndn + C2dn + C3d2n. 9.4. Для стационарной последовательности (a = 6) коэффициенты в выражении для ковариации существенно упрощаются:
Распределение числа 1-серий
Среднее значение Щх(п)) случайной величины х(п) выражается равенствами: Е(х(п)) = (« ;)) =J2Pk =J2{b+(a-b)dk). к=0 к=0 к=0 Используя формулу для суммы членов геометрической прогрессии, находим: Е{х(п)) = (п + 1) Ъ + с (1 - dn+l). (1.17) 7.2. Последовательно дифференцируя равенство (1.13) и разлагая вто рую производную при 5 = 1 в ряд по v, после некоторых преобразований получаем: (1 - dv) (1 - vf jU V » oo = E4)(1 ". /;8(i, к) = rs(i,v) ,.2 " = 2i(i, „) f; (6+(і - 6) d»)«»= n=l (l-v)(l-dv) = Е/(п)(ік n=l
Вычисляя коэффициенты /(п)(1), /(п)(1) полученных рядов, находим: V(x(n)) = #,(1) + 4,(1) - (/( „,(1))2 = П = 2 (((n-m + l)6 + c(l-dn-m+1))(6+(l-6)(im)) + га=1 + (n + 1) b + с (1 - dn+1) - ((n + 1) b + с (1 - dn+1))2. Суммируя и выделяя главную часть, получаем формулу для дисперсии: V(x(n)) = а (1 - а) + пЬ (1 - Ъ) 7 + А + Л(п), (1.18) где 1 + d _ 2(а - 6) (1 - 26) d 7 = T3d Б = rrd Л = -- y{ia-b)2(2-d)-(a-b)(l -26) + 26(1-b)d) d, С = (2(а - Ь)2 - (а - Ь) (1 - 6) (3 - d) + 26 (1 - Ъ) d) d, D = _f{a_ \ R(n) = Bndn + Cdn + Dd2n. 7.3. Для стационарной последовательности (а = Ь) формулы (1.17), (1.18) дают: Е(х(п)) = (п + 1)6, Y(x(n)) = (n + l)b(l-b)j-2b - 2d(l-d ). 8. Первые моменты числа 1-серий 8.1. Дифференцирование равенства (1.16) по t и разложение в ряд по степеням v дают: //, ч (I — pv)(a +(I — a —q)v) ,л 1л . . v / Э = (1-„)»(!-&) q"=a + (l-(l-a)q)v + (a+ ті— \ + (1 - о)(1 - q)n - ]Г (1 - Q) (1 - Я - а(! -d)(m + 1) dn-m 2) J гЛ тп=0 Среднее число 1-серий выражается формулой: Е(у(п)) = а + пЪ{1 -р)-{а- 6)6 (1 - dn). (1.19)
8.2. Дифференцирование равенства (1.16) даёт: ffe(l,t,) = 2(l-p)(l-,) (x- d-d»). Л Разлагая правую часть равенства в ряд по степеням v, вычисляя коэффициенты д /п}(1), используя для дисперсии числа 1-серий формулу Шп)) = п)(1) + Е(у(п)) - Е(у(п))2, после некоторых преобразований находим: V(y(n)) = а(1 - а) + таЬ(1 - 6)7 + + Д(п), (1.20) где l = p{b-q) + q(l -6), В = -2(а - 6)62(1 - )(1 + ), Л = 6 ((а - 6)2(2 - 6) - (а - 6)(1 - 26)(3 - 26) - 2(1 - Ъ)Ъ2), С = Ь (-2(а - 6)2(1 - 6) + (а - 6)(1 - 26)(3 - 26) + 2(1 - 6)62) , D = -(a- 6)262, R(n) = Bndn l + Cdn + Dd2n. 8.3. Для стационарной последовательности (а = 6) формулы (1.19), (1.20) дают: Е(у(п)) = Ь + пЬ(1-р), V(2/(n)) = (1- 6)6 (1 + П7 - 262 (1 - dn)) . В случае последовательности Бернулли, когда а = 6 = р = 1 — q и d = О, эти равенства приобретают вид: Е(у(п))=р(1 + п(1-р)), V(y(n))=p(l-p)(l-2p2 + n(l-3p + 3p2)) (п 1).
9.1. Найдём Е(х(п)у(п)). Для этого продифференцируем производящую функцию h(s,t,v) по s и t, взяв значение производной в точке 5 = 1, t = l: _(a+(l-a-q)v)(l-(l + d)v + (2pq-d)v2) n«V l v - (1- )3(1- )2
Разлагая полученное выражение в ряд по степеням v, получаем: h"t(l, 1, v) = (а + (1 - q - а{р + q + 1)) v + (qd - p + a(l + 2pg)) v2+ +(1 - a - q)(2pq - d)v ) (k + 1) Л M Ltil,,» = A;=0 n=0 oo = ,(1,1) , n=0 После некоторых преобразований находим: /г ( п)(1,1) = Е{х(п)у(п)) = п262(1 - р) + А п + В + Д(п), (1.21) где Л = 6 (2(a - 6)(1 -6) + 1-6(1- 6)(1 + d)), С = 2(a - 6)6(1 - 6), 5 = a + - - ((a -b)(d- 26(1 -6)(1 + /)) + 262(1 - b)d), J. (Jb D = -—Ц ((a - 6) (d - 26(1 - 6)(1 + d)) - 262(1 - b)d), 1 — a R{n) = Cndn + 6 f\
Среднее число а-событий
Дифференцируя /(ж, -г) в равенстве (2.9) по а: и разлагая в ряд по степеням z, получаем (используются равенства (2.1)-(2.3)): , Oi + (71 - ai(l + k))z + (-71 + (fli - bi)fc + bi(l + d))z2 Jx[ ,Zj (l-b + dz2)(l-z)2 = («i + (71 - ai(l + &))z + (-71 + (ai - Ьі)Аг + 6i(l + d))z2) x 00 00 x 5 (t + 1) J A(j + 1) = (ai + (71 -oi(l + fc))z+ г=0 j=0 00 n + (-71 + (ai - Ьі)Л + 6i(l + d)) 2) (n - г + 1)Л(г + 1)гп = n=0 г=0 ai + (71 - ai(l + fc)) + (-71 + (ai - bi) +-61(1+- d))22 (1 - fc + d)2 x (2d - к + С(гг + 1) + d(d - 1)Л(п + 1) +{к- 2d)A(n + 2)) zn = n=0 = 01 + (ai + 7і)г +- Л S ( 6iC2(n + 1) +" C(7i + (ai - 6i)(l -к)- h n=2 - ((71 - aifc - 6i(l - fc))(l - к) - (аг - bi)d)A(n + 1) - (71 + (ai - 6i)(l -к)- Ьі)Л(п + 2))\zn, откуда получаем среднее значение E(#i(n)) случайной величины Xi(n): Ezi(n) = Ьх{п + 1)+ 1_fc + d(7i + (ai - h){l - k) - h - ((71 - агк - h(l - fc))(l -k)- {ai - bi)d)A(n + 1) - (71 + (ai - bi)(l - k) - Ьі)Л(п + 2)). (2.11) Используя замечание 1.3, имеем окончательно: ЕХІ{П) = Ьі(п + 1)+ x_fc (7г + (at - 6.-)(1 - A;) - bf - ((7t - aik - bi(l - k))(l -к)- (а{ - bi)d)A(n + 1) -(ъ + ( И Ьг)(1-к)-Ьг)А(п + 2)У (2.12) В стационарном случае (а = 7г = h) Exi(n) = ai(n + 1).
Последовательно дифференцируя равенство (2.9) и разлагая вторую производную при х = 1 в ряд по z, получаем: 2z ар (1_z)3(1_bHrd22)2V +(Ml- )4-p7i-a( +(2 + %)),+ + ((71 -a(l + k)+p)h(l-k + d) -71 (d-h2p)-ha{(2-hk)d+(l + 2k)p))z2+ + (bl(l-k+d)2-(j1-ak+d+p)bl(l k+d)+ {2d+p)-a{(l+2k)d+kp))z3-h ) 00 = E/(n)(1) n- (2лз) n=0 Так как V( i(n)) = 4)(1) + 4(1) - (4)(1))2 = f(n)W + Efafa)) - (E n)))2 , (2.14) то для нахождения дисперсии V(:ci(n)) достаточно вычислить коэффициент // )(1) ряда (2.13). Привлекая равенства (2.1) - (2.3), имеем:
Найденные в главе 1 характеристики используются при решении задачи о переносе разряда при сложении случайных двоичных чисел. Этот перенос определяет скорость вычисления суммы ([27]).
1. Последовательное суммирование
Рассмотрим два двоичных (n + 1)-разрядных числа t и и, каждое из которых представляется последовательностью Бернулли с параметрами (р = 1/2, п + 1). Разряды записываются слева направо: = fofi n, l = Voli---Vn, РгЙ = 1} = Рг{гц = 1} = 1/2 (0 і п), п t = Y, № = &2 + &21 + 222 + + п2", :=0 п u = J2 № = о20 + 77121 + г)222 + - + г]п2\ г=0 Случайные переменные &, rjj предполагаются независимыми в совокупности: Рг{& = а,ъ = Р} = 1/4 (ij = 0 ,а,ре {0,1}). Кроме того Рг{п+1 = 0} = 1, Рг{г]п+1 = 0} = 1.
К числам t, и добавим двоичное число г = TQT\ ... тп, описывающее переносы разрядов при сложении г- с щ. Тройка (І,Г)І,ТІ) описывается числом, равным в своей десятичной записи величине . Числа 101 = 5, Oil = б и 111 = 7 описывают переносы разряда, а числа 110 = 3 и 001 = 4 - начало и конец переноса (со сдвигом на одну позицию). Например (разряды записываются слева направо):
Так как складываемые числа t, и выбираются независимо и случайно, то можно считать, что сложение описывается марковской последовательностью С = С(п) с множеством состояний С = {0,1,2,3,4,5,6,7}, начальным распределением Р и матрицей перехода Q : Р = (1/4,1/4,1/4,1/4, 0,0,0,0), 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 0 0 0 0 1/4 1/4 1/4 1/4 0 0 0 0 0 0 0 0 0 0 0 0 / Q = \ 0 0 0 o\ 0 0 0 0 0 0 0 0 1/4 1/4 1/4 1/4 0 0 0 0 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4,
В силу разложимости матрицы Q (см. [18]) состояния данной последовательности можно укрупнить, рассмотрев множества А = {3,5,6,7} и В = {0,1,2,4}. Тогда 3/4 1/4 Q = Р = (1/4,3/4), 1/4 3/4 для новой марковской случайной величины fi = fj,(n): fi(n) = 1, если С(п) Є А, 0, если С(п) Є В. Переносы разряда описываются теперь сериями из единиц. 1.3. Используя результаты главы 1, легко найти моменты рассматриваемых характеристик. Итак, а — 1/4, р = q = 3/4, d = 1/2, b = 1/2, и среднее число всех переносов равно Еф) = І(п+(І п+Г среднее число всех серий переносов равно %(n) = i(3 + n-(I)" то есть, складывая, например, 22-значные двоичные числа (n = 21) можно ожидать появления в среднем 3 серий из переносов разряда, при этом число переносов будет равно примерно 10.5.
Дисперсии числа переносов и числа серий из переносов соответственно имеют вид: Vy(n) = (7 + 3n + 6g)n"-( Корреляционная зависимость между числом переносов и числом серий из переносов: К(х(п),у(п)) = = 10-3nQ)n+1-15()n+1 + 2(i)n+1 (_2 + Зп + 11 (ІГ1 - (I)-1) (7 + Зп + 6 (I)""1 - (J)») то есть уже при п = 21 К(х(гі),у(гі)) « 0.15 и, так как Q = Q , то при дальнейшем увеличении п выполнено К(х(п),у(п)) — 0 согласно 1.9. Среднее число серий переносов данной длины к ищется по формуле: Е ")4(Ї) (Я- +7+0" Тогда среднее число серий у( к,п) переносов длины, большей к, равно ЕУ (к,п) =Еу(к,п) -f Ey(k,n) = U J и + п-к- Q) Например, при п = 21 среднее число серий переносов длины, большей, чем 3, будет равно примерно 1.1.
Параллельное суммирование
Заметим, что ввиду сильной неоднородности количества осадков, для каждого месяца придется вводить свои начальные и переходные вероятности. Переходные вероятности qij (i,j Є {0,1}) будем моделировать следующим образом ([25, 75]). Найдем число всевозможных переходов 11, 10, 01, 00 по каждой из станций за каждый год. Например, за месяц май в 1969 году на первой станции было зафиксировано 4 перехода из 1 в 1, 9 переходов 10, 9 переходов 01 и 8 переходов 00. Среднее число переходов г — j по всем станциям и годам в течение одного месяца обозначим тпц. Тогда оценка q вероятности q (i,j Є {0,1}) будет иметь вид: ГПі (мє{о,і}). nj 13 тю + ГПц Например, для мая тц = 4.224, гаю = 5.070, откуда р = q n = 0.455.
Данные оценки являются, очевидно, несмещенными и сильно состоятельными, так как к ним применим усиленный закон больших чисел. Для подсчета начальных вероятностей необходимо число всех единиц, отмеченных первого числа месяца на всех станциях и по всем годам, поделить на общее число наблюдений. Таким образом, оценка имеет вид:
Вышеперечисленные оценки по всем месяцам вместе со вспомогательными обозначениями приведены в таблице 2.3 (всюду далее, где не будет путаницы, полученные оценки отождествляются с теоретическими вероятностями, например, р = р).
Рассмотрим пределы, в которых могут колебаться значения переходных вероятностей. Для оценки qij может служить его квадратичная погрешность, приближенно равная где п - длина месяца. Имеем для мая: тц = 0.09, 7оо = 0.08.
Используя центральную предельную теорему, можно показать, что значения р и q с надежностью 14/15 = 0.933 будут находиться в интервалах 0.287 р 0.622, 0.6 q 0.893.
На практике дело обстоит следующим образом. В таблице 2.4 приведена зависимость эмпирических переходных вероятностей от года.
Таким образом на временном отрезке за 15 лет из доверительного интервала "вылетели" по два года. То есть можно сказать, что "экстремальные" в том или ином смысле года наступают в среднем раз в 7-8 лет. Более качественный анализ, видимо, возможно сделать только при увеличении временного промежутка. Значения р и q вместе со своими доверительными интервалами (xi\xr) при уровне надежности 0.93 и количеством п "вылетевших" из интервала значений для каждого месяца приведены в таблице 2.5.
Итак, вероятности матрицы перехода являются достаточно неустойчивыми характеристиками во времени. Даже на модельном уровне, например, для мая "разлет" вероятности сохранения дождливой и сухой погоды составляет примерно 0.33 и 0.29 соответственно. Рассмотрим следующую характеристику:
Это вероятность так называемого сохранения погодных условий. Ее среднее квадратичное отклонение равно 0.047, что более чем в полтора раза раза меньше тіп{сгу}. Таким образом, можно сказать, что невзирая на "экстремальность" года вероятность изменения погодных условий намного более устойчива, чем отдельные вероятности сохранения конкретной погоды. Разница между средними квадратичными отклонениями сгц, 7оо и сгс для р, q и qc соответственно показана в таблице 2.6.
Так называемые "облака разлета" для р, q и qc показаны на рисунках 2.1 - 2.3 (месяц май). Видно, что точки графика qc расположены намного менее хаотично и больше напоминают прямую линию.
