Реферат: Использование цепей Маркова в моделировании социально-экономических процессов - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

Использование цепей Маркова в моделировании социально-экономических процессов

Рефераты по математике » Использование цепей Маркова в моделировании социально-экономических процессов

§1. Основные понятия теории марковских цепей.

Пусть {Использование цепей Маркова в моделировании социально-экономических процессов , Использование цепей Маркова в моделировании социально-экономических процессов, ..., Использование цепей Маркова в моделировании социально-экономических процессов} - множество возможных состояний некоторой физической системы. В любой момент времени система может находиться только в одном состоянии. С течением времени система переходит последовательно из одного состояния в другое. Каждый такой переход называется шагом процесса.

Для описания эволюции этой системы введем последовательность дискретных случайных величин Использование цепей Маркова в моделировании социально-экономических процессов, Использование цепей Маркова в моделировании социально-экономических процессов,..., Использование цепей Маркова в моделировании социально-экономических процессов,... Индекс n играет роль времени. Если в момент времени n система находилась в состоянии Использование цепей Маркова в моделировании социально-экономических процессов, то мы будем считать, что Использование цепей Маркова в моделировании социально-экономических процессов= j. Таким образом, случайные величины являются номерами состояний системы.

Последовательность Использование цепей Маркова в моделировании социально-экономических процессов, Использование цепей Маркова в моделировании социально-экономических процессов,..., Использование цепей Маркова в моделировании социально-экономических процессов,... образует цепь Маркова, если для любого n и любых Использование цепей Маркова в моделировании социально-экономических процессов, Использование цепей Маркова в моделировании социально-экономических процессов, ..., Использование цепей Маркова в моделировании социально-экономических процессов,...

P(Использование цепей Маркова в моделировании социально-экономических процессов=j / Использование цепей Маркова в моделировании социально-экономических процессов= Использование цепей Маркова в моделировании социально-экономических процессов, ..., Использование цепей Маркова в моделировании социально-экономических процессов=i)=P(Использование цепей Маркова в моделировании социально-экономических процессов=j / Использование цепей Маркова в моделировании социально-экономических процессов=i).

Для цепей Маркова вероятность в момент времени n попасть в состояние Использование цепей Маркова в моделировании социально-экономических процессов, если известна вся предыдущая история изучаемого процесса, зависит только от того, в каком состоянии находился процесс в момент n-1. То есть при фиксированном "настоящем" "будущее" не зависит от "прошлого". Свойство независимости "будущего" от "прошлого" при фиксированном "настоящем" называется марковским свойством.

Вероятности Использование цепей Маркова в моделировании социально-экономических процессов( Использование цепей Маркова в моделировании социально-экономических процессов=j / Использование цепей Маркова в моделировании социально-экономических процессов=i), i, j=1,2,..., r называются вероятностями перехода из состояния Использование цепей Маркова в моделировании социально-экономических процессовв состояние Использование цепей Маркова в моделировании социально-экономических процессовза один шаг.

Цепь Маркова называется однородной, если вероятности перехода Использование цепей Маркова в моделировании социально-экономических процессовне зависят от n, т.е. если вероятности перехода не зависят от номера шага, а зависят только от того, из какого состояния и в какое осуществляется переход. Для однородных цепей Маркова вместо Использование цепей Маркова в моделировании социально-экономических процессовбудем писать Использование цепей Маркова в моделировании социально-экономических процессов.

Вероятности перехода удобно располагать в виде квадратной матрицы

Использование цепей Маркова в моделировании социально-экономических процессов

Матрица P называется матрицей вероятностей перехода однородной цепи Маркова за один шаг. Она обладает следующими свойствами:

а) Использование цепей Маркова в моделировании социально-экономических процессов;

б) для всех i: Использование цепей Маркова в моделировании социально-экономических процессов

Квадратные матрицы, для которых выполняются условия а) и б), называются стохастическими.

Вектор Использование цепей Маркова в моделировании социально-экономических процессов, где Использование цепей Маркова в моделировании социально-экономических процессов=P(Использование цепей Маркова в моделировании социально-экономических процессов), i=1,2...,r называется вектором начальных вероятностей.

Свойства однородных цепей Маркова полностью определяются вектором начальных вероятностей и матрицей вероятностей перехода.

Приведем пример: Завод выпускает телевизоры определенного типа. В зависимости от того, находит ли данный тип телевизора спрос у населения, завод в конце каждого года может находиться в одном из состояний: состояние 1 – спрос есть, состояние 2 – спроса нет. Пусть вероятность сохранить состояние 1 в в следующем году с учетом возможного изменения спроса равна Использование цепей Маркова в моделировании социально-экономических процессов, а вероятность изменить состояние 2 с учетом мероприятий по улучшению выпускаемой модели равна Использование цепей Маркова в моделировании социально-экономических процессов. Тогда процесс производства на данном заводе можно описать цепью Маркова с матрицей переходов:

Использование цепей Маркова в моделировании социально-экономических процессов

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

Можно показать, что матрица вероятностей перехода цепи Маркова за n шагов равняется n-ой степени матрицы P вероятностей перехода за один шаг. Для однородной цепи Маркова при любом m выполняется равенство

P(Использование цепей Маркова в моделировании социально-экономических процессов)=P(Использование цепей Маркова в моделировании социально-экономических процессов).

Но последняя вероятность есть вероятность перехода из состояния Использование цепей Маркова в моделировании социально-экономических процессов в состояние Использование цепей Маркова в моделировании социально-экономических процессовза n шагов.

§2. Теорема о предельных вероятностях.

В 1930 году Дж.Биркгофом и Дж.фон Нейманом была сформулирована и доказана одна из основных эргодических теорем – теорема о предельных вероятностях:

Если при некотором Использование цепей Маркова в моделировании социально-экономических процессов все элементы матрицы Использование цепей Маркова в моделировании социально-экономических процессов =[Использование цепей Маркова в моделировании социально-экономических процессов] положительны, то существуют пределы

Использование цепей Маркова в моделировании социально-экономических процессовИспользование цепей Маркова в моделировании социально-экономических процессов , i,j =1,2,...,r.

Предельные вероятности Использование цепей Маркова в моделировании социально-экономических процессов не зависят от начального состояния Использование цепей Маркова в моделировании социально-экономических процессови являются единственным решением системы уравнений

Использование цепей Маркова в моделировании социально-экономических процессов
(1)
Использование цепей Маркова в моделировании социально-экономических процессов,

Использование цепей Маркова в моделировании социально-экономических процессов, j=1, 2, ..., r.

Физический смысл этой теоремы заключается в том, что вероятности нахождения системы в состоянии Использование цепей Маркова в моделировании социально-экономических процессовпрактически не зависят от того, в каком состоянии она находилась в далеком прошлом.

Цепь Маркова, для которой существуют пределы Использование цепей Маркова в моделировании социально-экономических процессов, называется эргодической. Решение (Использование цепей Маркова в моделировании социально-экономических процессов,Использование цепей Маркова в моделировании социально-экономических процессов,...,Использование цепей Маркова в моделировании социально-экономических процессов) написанной выше системы (1) называется стационарным распределением вероятностей для марковской цепи с матрицей перехода P = [Использование цепей Маркова в моделировании социально-экономических процессов].

Если из состоянияИспользование цепей Маркова в моделировании социально-экономических процессовсистема может перейти в состояние Использование цепей Маркова в моделировании социально-экономических процессовс положительной вероятностью за конечное число шагов, то говорят, что Использование цепей Маркова в моделировании социально-экономических процессов достижимо из Использование цепей Маркова в моделировании социально-экономических процессов.

Состояние Использование цепей Маркова в моделировании социально-экономических процессовназывается существенным, если для каждого состояния Использование цепей Маркова в моделировании социально-экономических процессов, достижимого из Использование цепей Маркова в моделировании социально-экономических процессов, Использование цепей Маркова в моделировании социально-экономических процессовдостижимо из Использование цепей Маркова в моделировании социально-экономических процессов. Если же для хотя бы одного j Использование цепей Маркова в моделировании социально-экономических процессовдостижимо из Использование цепей Маркова в моделировании социально-экономических процессов, а Использование цепей Маркова в моделировании социально-экономических процессовне достижимо из Использование цепей Маркова в моделировании социально-экономических процессов, то Использование цепей Маркова в моделировании социально-экономических процессов- несущественное состояние.

§3. Области применения цепей Маркова.

Цепи Маркова служат хорошим введением в теорию случайных процессов, т.е. теорию простых последовательностей семейств случайных величин, обычно зависящих от параметра, который в большинстве приложений играет роль времени. Она предназначена, главным образом, для полного описания как долговременного, так и локального поведения процесса. Приведем некоторые наиболее изученные в этом плане вопросы.

Броуновское движение и его обобщения – диффузионные процессы и процессы с независимыми приращениями. Теория случайных процессов способствовала углублению связи между теорией вероятностей, теорией операторов и теорией дифференциальных уравнений, что, помимо прочего, имело важное значение для физики и других приложений. К числу приложений относятся процессы, представляющие интерес для актуарной (страховой) математики, теории массового обслуживания, генетики, регулирования дорожного движения, теории электрических цепей, а также теории учета и накопления товаров.

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

Стационарные процессы. Самая старая из известных эргодических теорем, как отмечалось выше, может быть интерпретирована как результат, описывающий предельное поведение стационарного случайного процесса. Такой процесс обладает тем свойством, что все вероятностные законы, которым он удовлетворяет, остаются инвариантными относительно сдвигов по времени. Эргодическую теорему, впервые сформулированную физиками в качестве гипотезы, можно представить как утверждение о том, что при определенных условиях среднее по ансамблю совпадает со средним по времени. Это означает, что одну и ту же информацию можно получить из долговременного наблюдения за системой и из одновременного (и одномоментного) наблюдения многих независимых копий той же самой системы. Закон больших чисел есть не что иное, как частный случай эргодической теоремы Биркгофа. Интерполяция и предсказание поведения стационарных гауссовских процессов, понимаемых в широком смысле, служат важным обобщением классической теории наименьших квадратов. Теория стационарных процессов – необходимое орудие исследования во многих областях, например, в теории связи, которая занимается изучением и созданием систем, передающих сообщения при наличии шума или случайных помех.

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

§4. Управляемые цепи Маркова. Выбор стратегии.

Завод по изготовлению телевизоров, находясь в состоянии 1, может увеличить спрос путем организации рекламы. Это требует добавочных затрат и уменьшает доход. В состоянии 2 завод может увеличить вероятность перехода в состояние 1 путем увеличения затрат на исследования. Выделим две стратегии. Первая состоит в отказе от затрат на рекламу и исследования, а вторая - в согласии на них. Пусть матрицы переходных вероятностей и матрицы доходов для данных стратегий имеют вид:

Использование цепей Маркова в моделировании социально-экономических процессов Использование цепей Маркова в моделировании социально-экономических процессов

Использование цепей Маркова в моделировании социально-экономических процессов Использование цепей Маркова в моделировании социально-экономических процессов

В рассмотренной ситуации имеет место управляемая цепь Маркова. Управление соответствует выбору стратегии.

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

Пусть в i-м состоянии имеется не одно, а Использование цепей Маркова в моделировании социально-экономических процессов множеств переходных вероятностей Использование цепей Маркова в моделировании социально-экономических процессов. При Использование цепей Маркова в моделировании социально-экономических процессов имеем случай неуправляемой цепи Маркова. Если система находится в состоянии Использование цепей Маркова в моделировании социально-экономических процессов и принимается решение Использование цепей Маркова в моделировании социально-экономических процессов то

- она получает доход Использование цепей Маркова в моделировании социально-экономических процессов;

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

Таким образом, смысл Использование цепей Маркова в моделировании социально-экономических процессов-го решения в i-м состоянии заключается в выборе одного набора переходных вероятностей Использование цепей Маркова в моделировании социально-экономических процессов из Использование цепей Маркова в моделировании социально-экономических процессов возможных. Предполагается, что доход Использование цепей Маркова в моделировании социально-экономических процессовограничен при всех Использование цепей Маркова в моделировании социально-экономических процессови Использование цепей Маркова в моделировании социально-экономических процессов.

Кроме того,

Использование цепей Маркова в моделировании социально-экономических процессов, Использование цепей Маркова в моделировании социально-экономических процессов при всех Использование цепей Маркова в моделировании социально-экономических процессови Использование цепей Маркова в моделировании социально-экономических процессов.

Управляемой цепью Маркова называется конструкция, задаваемая параметрами Использование цепей Маркова в моделировании социально-экономических процессов, где К-решения, Р-вероятности переходов, r-доходы. Доход, полученный за несколько шагов, является случайной величиной, зависящей от начального состояния и принимаемых в каждый момент времени решений.

Назовем решение, принимаемое в конкретный момент, частным управлением. Тогда управление есть последовательность решений в моменты n = 1, 2, ... Качество управления можно оценить средним суммарным доходом (при конечном времени) или среднем доходом в единицу времени (при бесконечном времени).

Пусть Использование цепей Маркова в моделировании социально-экономических процессов (2)

Стратегией Использование цепей Маркова в моделировании социально-экономических процессов называется последовательность решений

Использование цепей Маркова в моделировании социально-экономических процессовИспользование цепей Маркова в моделировании социально-экономических процессов

где Использование цепей Маркова в моделировании социально-экономических процессов- вектор вида (2), i-я компонента которого, обозначаемая через Использование цепей Маркова в моделировании социально-экономических процессов, является решением, принимаемым в состоянии Использование цепей Маркова в моделировании социально-экономических процессовв момент п. Другими словами, задание стратегии означает полное описание в каждый момент времени t =1, 2, ..., п, ... конкретных решений, которые должны были бы приниматься в i-м состоянии , если бы система находилась в нем в рассматриваемый момент.

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

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

Использование цепей Маркова в моделировании социально-экономических процессов

Таким образом, при фиксированной стратегии Использование цепей Маркова в моделировании социально-экономических процессов получаем цепь Маркова с матрицами перехода Использование цепей Маркова в моделировании социально-экономических процессов

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

Использование цепей Маркова в моделировании социально-экономических процессовИспользование цепей Маркова в моделировании социально-экономических процессов при любых Использование цепей Маркова в моделировании социально-экономических процессов

называется оптимальной

Верны следующее утверждения:

Утверждение 1. Для бесконечного времени существует оптимальная стационарная стратегия.

Утверждение 2. Для конечного времени существует оптимальная марковская стратегия.

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

Список литературы

1. «Теория выбора и принятия решений»: учебное пособие. И.М. Макаров, Т.М. Виноградская, А.А. Рубчинский, В.Б. Соколов. Москва, изд. «Наука», 1982.

2. «Теория вероятностей» Е.С. Вентцель. Москва, изд. «Наука», 1969.