автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели естественных и социальных процессов, основанные на конечных цепях Маркова

Введение

1 Марковские модели

I Двоичные цепи.

1. Обозначения

2. Распределение £(п).

3. Совместное распределение.

4. Производящие функции.

5. Распределение числа единиц.

6. Распределение числа 1-серий.

7. Первые моменты числа единиц.

8. Первые моменты числа 1-серий. рг 9. Ковариации.

10. Нормальное приближение.

11. Первые моменты /с-серий.

12. Накрывающие серии.

II Троичные цепи.

1. Обозначения м 2. Распределение £(п).

3. Производящие функции.

4. Среднее число а-событий. fy 5. Дисперсия числа а-событий. 6. Среднее число а-серий.

7. Дисперсия числа а-серий

8. Ковариации.

9. Частные случаи. щ 2 Применения

I Сложение случайных чисел.

1. Последовательное суммирование.

Ф 2. Параллельное суммирование.

II Применение в метеорологии.

1. Марковская модель и ее адекватность.

2. Результаты и их анализ.

III Применение в социологии.

1. Марковская модель.

2. Результаты и их анализ.

3. Структурные классификации семей.

Цепи Маркова или марковские последовательности впервые были рассмотрены в книге [23], причем первая последовательность, которую описал А.А. Марков, была именно двоичной. В дальнейшем двоичные цепи, как важный частный случай конечных цепей Маркова, выделялись в большинстве работ, связанных данной тематикой. Троичные последовательности являются логичным обобщением двоичных цепей и также имеют самое широкое применение в различных приложениях.

Важнейшие результаты в теории марковских цепей связаны с именем

A.Н. Колмогорова. Им была доказана локальная предельная теорема для конечных цепей Маркова ([19]), а его учениками проведен полный асимптотический анализ числа попаданий в одно из состояний для двоичных (P.JI. Добрушин, [14]) и конечных (Л.Д. Мешалкин, [24]) цепей Маркова. Первые моменты числа попаданий в одно из состояний для конечных цепей, используя выражения, содержащие характеристические функции, получил

B.И. Романовский ([25]).

Теория серий в случайных последовательностях развивалась параллельно с теорией марковских цепей. В случае независимых испытаний выделяются статьи А. Муда [44] (двоичный случай) и B.JI. Гончарова [11] (конечный случай), где рассматриваются распределения серий различных типов, а также максимальной длины серии. Независимые испытания являются важным частным случаем марковской зависимости, и в дальнейшем это будет всюду подчеркиваться.

Локальная предельная теорема для числа серий в конечных марковских цепях была доказана в [33]. Теми же авторами в [33], [32], [17] получены точные формулы первых моментов числа серий для конечных цепей Маркова. Также рассмотрены различные частные случаи.

90-е годы прошлого века отмечены большим количеством работ по теории серий в марковских цепях. Подробная классификация различных типов серий дана в [38], где для них получены матричные производящие функции и рассмотрены некоторые численные примеры. Серии данной длины и различные связанные с ними характеристики исследовались в [40], [41], [50].

Вышеприведенные работы по теории марковских цепей обуславливают актуальность применения марковских моделей при описании естественных и социальных процессов. Во-первых, хорошо разработанный аппарат и сравнительно небольшое число входящих в марковскую модель параметров обеспечивают относительную простоту исследования по сравнению, например, с динамическими моделями. Во-вторых, для рассматриваемых процессов характерны случайные отклонения и взаимосвязь переменных во времени. Стохастические модели позволяют учитывать эти отклонения.

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

Множество значений марковской цепи выбирается в соответствии с характером наблюдений и условиями задачи. Очень часто число условий задачи можно уменьшить, объединив некоторые из них или отбросив несущественные. Таким образом, многие марковские модели так или иначе оперируют двух- или трехфазным множеством состояний. Важность данных частных случаев диктуется еще и тем, что для них получаются более простые формулы по сравнению со случаем произвольного конечного числа состояний. По этим формулам можно производить эффективные вычисления. Вместе с тем, несмотря на их относительную простоту, двоичные и троичные цепи нельзя считать полностью исследованными. Именно рассмотрению серийной структуры, а также исследованию поведения числа серий и событий в данных цепях посвящена первая глава диссертации. Исследуются как классические характеристики серий, так и ранее редко встречавшиеся в литературе функционалы на марковских цепях, также исследуются их совместные распределения. Достаточно универсальный метод производящих функций, сводящийся к построению рекуррентных соотношений, позволяет получить собственно производящие функции, первые и вторые моменты, а также сами распределения рассматриваемых функционалов. Из новых результатов можно отметить исследование совместных распределений и зависимости различных функционалов (в частности, числа серий и числа событий), показано, что в двоичном случае число событий х{п) и число серий у(п) асимптотически некоррелированы, то есть

К(х(п),у(п)) = 0(1/п).

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

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

Во второй части второй главы рассматриваются марковские модели в метеорологии. Стохастические процессы достаточно давно используются при моделировании временных рядов сумм осадков, причем как непрерывные, так и дискретные. К первым относятся непосредственно марковские процессы ([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].

Заключение

В заключение перечислим основные результаты диссертационной работы:

1. Получены удобные для расчетов точные формулы для первых двух моментов распределений характеристик серий в бинарных и тернарных цепях. Также исследованы совместные распределения этих характеристик и их корреляционные зависимости.

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

3. На основе данных многолетних наблюдений для равнинной части Новосибирской области построена марковская модель для описания помесячной динамики суточных сумм жидких осадков и оценки характеристик, связанных с экстремальными сериями сухих и дождливых суток. Результаты для этой модели хорошо согласуются с эмпирическими.

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

Пользуясь случаем, автор выражает искреннюю благодарность своему научному руководителю профессору Л.Я. Савельеву за плодотворное руководство работой и всестороннюю поддержку.

1. Антонов А.И. Микросоциология семьи. - М., 1998.

2. Бабиков Г.В. Математическое моделирование динамики социально-демографических показателей //В кн.: Региональные особенности формирования населения и использования трудовых ресурсов. -Свердловск: УНЦ АН СССР, 1981, с. 87 - 92.

3. Балакин С.В. Численные характеристики случайных последовательностей // Труды IV Региональной научно-практической конференции студентов и аспирантов. 4.2. - Новокузнецк, НФИ КемГУ, 2004. - С. 5.

4. Балакин С.В. Численные характеристики случайных последовательностей // Труды международной конференции по вычислительной математике. 4.1. - Новосибирск, 2004. С. 249-250.

5. Балакин С.В. Характеристики серий в марковских последовательностях // Материалы XLIII международной научной студенческой конференции (секция "математика"). Новосибирск, НГУ, 2005. - С. 218— 219.

6. Балакин С.В. Марковская модель задачи о переносе разряда // Материалы XLIV международной научной студенческой конференции (секция "математика"). Новосибирск, НГУ, 2006. - С. 168 - 169.

7. Бойко В.И., Гончарова Г.С., Попов С.В., Савельев Л.Я. Семья в Новосибирской области. Институт философии и права СО РАН, Новосибирск, 1996.

8. Валтер Я. Стохастические модели в экономике. М., Статистика, 1976.

9. Волков А.Г. Семья — объект демографии. М., 1986.

10. Волков А.Г., Сороко Е.Л. Типология семей и домохозяйств в России: развитие и анализ (по данным микропереписи 1995 года) // Вопр. статистики, 1999. №5. - С. 40-52.

11. Гончаров В.Л. Из области комбинаторики // Изв. АН СССР. Математика, 1944. т. 8, т. - С. 3-49.

12. Гончарова Г.С., Савельев Л.Я. Структурные характеристики семей. -Новосибирск, изд-во НГУ, 2002. 86 с.

13. Гончарова Г.С., Савельев Л.Я. Семейно-брачные отношения у народов Сибири: проблемы, тенденции, перспективы. Новосибирск, Нонпарель, 2004.

14. Добрушин Р.Л. Предельные теоремы для цепи Маркова из двух состояний // Известия АН СССР. Сер. мат., 1953. Т.17. - 291-330.

15. Дробышев А.Д., Марченко А.С., Огородников В.А., Чижиков В.Д. Статистическая структура временных рядов суточных сумм жидкихосадков в равнинной части Новосибирской области // Труды ЗапСиб-НИИ Госкомгидромета, 1989. Вып. 86. - С. 44-74.

16. Жуковский Е.Е., Бельченко Г.Г., Брунова Т.М. Вероятностный анализ влияния изменений климата на потенциал продуктивности агроэкоси-стем // Метеорол. и гидрол., 1992. №3. - С. 92-103.

17. Захаров В.К., Сарманов О.В. О законе распределения числа серий в однородной цепи Маркова // ДАН СССР,1968. 179, № 3 - С. 526-528.

18. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1978. - 280 с.

19. Колмогоров А.Н. Локальная предельная теорема для классических цепей Маркова // Известия АН СССР. Сер. мат., 1949. Т. 13. - С. 281300.

20. Колчин В.Ф. Случайные графы. Москва, Физматлит, 2000.

21. Крамер Г. Математические методы статистики. Москва, Мир, 1975.

22. Лаврентьев М.М., Савельев Л.Я., Балакин С.В. Матричные операторные уравнения. Новосибирск, 2004. - 32 с. / Препринт РАН. Сиб. отд-ние. Институт математики, №148.

23. Марков А.А. Исчисление вероятностей. Санкт-Петербург, Типография Императорской Академии Наук, 1913.

24. Мешалкин Л.Д. Предельные теоремы для цепей Маркова с конечным числом состояний. Теор. вер. и ее применения, 1958. 3, №4. - С. 361385.

25. Романовский В.И. Дискретные цепи Маркова. Москва, Гостехиздат, 1949.

26. Ружже B.JI., Елисеева И.И. Кадибур Т.С. Структура и функции семейных групп. М., 1983.

27. Савельев Л.Я. Длинные серии в марковских последовательностях // Предельные теоремы теории вероятностей, 1985. том 5. - С. 137-144.

28. Савельев Л.Я., Балакин С.В., Хромов Б.В. Накрывающие серии в двоичных марковских последовательностях // Дискретная математика, 2003. том 15, вып. 1. - С. 50-76.

29. Савельев Л.Я., Балакин С.В. Совместное распределение числа единиц и числа 1-серий в двоичной марковской последовательности // Дискретная математика, 2004. том 16, вып. 3. - С. 43-62.

30. Савельев Л.Я., Балакин С.В. Накрывающие серии // 4-я Всероссийская конференции по финансово-актуарной математике и смежным вопросам. Тезисы докладов. Красноярск, 2005. - С.71.

31. Савельев Л.Я., Балакин С.В. Характеристики серий в двоичных марковских последовательностях // 4-я Всероссийская конференции по финансово-актуарной математике и смежным вопросам. Тезисы докладов. Красноярск, 2005. - С.72-73.

32. Сарманов О.В., Захаров В.К. Комбинаторная задача Н.В. Смирнова // ДАН СССР, 1967. 176, № 3. - С. 530-532.

33. Смирнов Н.В., Сарманов О.В., Захаров В.К. Локальная предельная теорема для чисел переходов в цепи Маркова и ее применения // ДАН СССР, 1966. 167, № 6. - С. 1238-1241.

34. Феллер В. Введение в теорию вероятностей и ее приложения. Том 1. -Москва, Мир, 1984.

35. Типы и состав домохозяйств в России (по данным микропереписи 1994 г.). М., 1995.

36. Aleman P.A., Garcia Е. The Variability of Rainfall in Mexiko and Its Determination by Means of the Gamma Distribution // Geogr. Ann., 1981. A 63, №1-2. - P. 1-10.

37. Chin E.H. Modeling Daily Precipitation Occurence Process With Markov Chain // Water Resour. Res., 1977. 13, №6. - P. 949-956.

38. Fu J.C. and Koutras M.V. Distribution theory of runs: A Markov chain approach. // J. Amer. Statist. Assoc., 1994. 89. - P. 1050-1058.

39. Haan C., Allan D., Street I.A. Markov Chain Model of Daily Rainfall // Water Resour. Res., 1976. 12, №. - P. 443-449.

40. Aki S., Hirano K. Discrete Distributions Related to Succession Events in a Two-State Markov Chain // Stat. Sci. and Data Anal., 1993. P. 467-474.

41. Hirano K., Aki S. On Number of Occurrences of Success Runs of Specified Length in a Two-State Markov Chain // Statist. Sinica, 1993. 3. -P. 313-320.

42. Keyfitz N., Beekman J.A. Demography Through Problems. New-York, Springer-Verlag, 1984.

43. Masashi N., Jsuyoshi K. Statistics on Ratio of Successive Rainfall Series // Trans. Jap. Civ. Eng., 1980. 11. - R 140-142.

44. Mood A.M. The Distribution Theory of Runs. // Annals of Math. Stat., 1940. v. 11, № 4. - R 367-392.

45. Morelli S., Santangelo R. Statistical Model for Daily Precipitation // New Perspect. Clim. Modelling, Amsterdam, 1984. P. 69-78.

46. Pepper E.D. Asymptotic Expression for the Probability of Trials Connected in a Chain // Ann. Math. 1926. 28. - P. 318-326.

47. Stern R.D. Computing a Probability Disribution for the Start of the Rains a Markov Chain Model for Precipitation // J. Appl. Meteorol., 1982. 21, №. - P. 420-423.

48. Stern R.D., Сое R.A. A Model Fitting Analysis of Daily Rainfall Data // J. R. Statist. Soc., A, 1984. Vol. 147, pt. 1. - P. 1-34.

49. Swift L.W., Schreuder H.T. Fitting Daily Precipitation Amounts Using the SB Distribution // Mon. Weather Rev., 1981. 109, №12. - P. 2535-2541.

50. Uchida M. On Number of Occurrences of Success Runs of Specified Length in a Higher-order Two-state Markov Chain. // Ann. Inst. Statist. Math., 1998. Vol. 50, No. 3. -P. 587-601.