Прикладная математика
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Цепи маркова

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

ПРИМЕР 1: Рассмотрим ситуацию, при которой компьютер может находиться в одном из двух состояний: «работает хорошо» или «нуждается в регулировке». Если компьютер работает хорошо сегодня, вероятность того, что он будет работать хорошо завтра, равна 0,7. Вероятность того, что он завтра будет нуждаться в регулировке, соответственно равна 0,3. Предположим, что компьютер имеет механизм саморегулирования, который действует, не достаточно эффективно, так что если машина нуждается в регулировке сегодня, вероятность того, что она будет работать хорошо завтра, равна 0,6. Вероятность, что компьютер будет нуждаться в регулировке завтра, равна 0,4 (см. таблицу).

Таблица 1.

Куда/Откуда

Работает хорошо (состояние 1).

Требует регулировки (состояние 2).

Работает хорошо (состояние 1).

0,7

0,3

Требует регулировки (состояние 2).

0,6

0,4

Сумма вероятностей по любой из строк равна 1.

Матрица вероятностей переходов , полученная по таблице 1., имеет вид:

.

Предположим, что компьютер начинает работу в состоянии 1 («работает хорошо») в исходный момент времени, который мы будем считать нулевым периодом. Таким образом:

В этих обозначениях вектор состояний в период 1:

.

Вектор состояний машины в период 2:

.

Аналогично:

,

и для произвольного периода:

.

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

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

Марковское свойство может встречаться не только в случаях дискретных описаний состояний, но также и в случаях непрерывных описаний состояний системы. Если это свойство существует у системы с непрерывным множеством состояний, то такую систему называют марковским процессом; если же множество состояний дискретно, то ее называют марковской цепью.

Стационарные вероятности.

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

(1)

ПРИМЕР 2: Вернемся к компьютеру (см. пример 1). Для заданной матрицы уравнение (1) имеет вид:

. (2)

Обозначая и подставляя в уравнение (2) получим:

(3)

Одно из двух соотношений (3) лишнее, так как они оба сводятся к

. (4)

Однако существует еще одна связь между стационарными вероятностями:

. (5)

Таким образом, имеем систему

эквивалентную матричному уравнению

(6)

которое имеет решение

(7)

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

Неустановившееся. Периодическое и эргодическое поведение системы

Неустановившимся состоянием марковской цепи называется состояние с нулевой стационарной вероятностью.

ПРИМЕР 3: Предположим, что компьютер может быть в трех состояниях: 1–компьютер сломан и требует ремонта; состояние 2–нуждается в регулировании; 3–работает хорошо, а матрица вероятностей перехода имеет вид:

.

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

.

Если поведение машины характеризуется приведенной ранее матрицей , то

.

Следовательно, если куплен компьютер б. у., то с вероятностью 0,66 он окажется сломанным и будет нуждаться в ремонте спустя два периода времени. Заметим, что состояние 1 является поглощающим состоянием; вектор стационарных состояний равен (1; 0; 0).

Периодическое (циклическое) поведение.

ПРИМЕР 4: По матрице вероятностей перехода ,

,

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

Покажем это для случая: .

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

Периодические множества и эргодические системы.

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

,

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

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

,

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

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

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

ПРИМЕР 5: Рассмотрим систему с матрицей :

.

Состояния 1 и 2 образуют периодическое множество, состояние 3 есть переходное состояние, а состояние 4 – второе периодическое множество (поглощающее состояние). При достаточно больших вероятности пребывания в тех или иных состояниях зависят от начального состояния системы. Например, если начальным было состояние 1 или 2, то система будет описывать цикл из этих двух состояний; если начать с состояния 4, то система навсегда останется в нем; если начальным будет состояние 3, то в 30% случаев система будет переходить в первое периодическое множество и в 70% случаев – во второе периодическое множество. Элементы вектора вероятностей , удовлетворяющие уравнению и равные соответственно

,

в данном случае не имеют осмысленной интерпретации.

Существование стационарных вероятностей

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

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

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

,

состояние 2 есть переходное состояние с предельной вероятностью, равной нулю. Тогда система (вероятности, относящиеся к состоянию 2 исключаются из рассмотрения) удовлетворяет определению регулярной системы, и стационарные вероятности для состояний 1 и 3 действительно существуют. С ростом матрица стремится к

,

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

ПРИМЕР 6: Рассмотрим систему с матрицей:

.

Здесь нет переходных состояний. Чтобы проверить систему на регулярность, вычислим для увеличивающихся значений . Для

,

каждый элемент больше нуля. Таким образом, стационарные вероятности для этой системы будут существовать.

Добавить комментарий


Защитный код
Обновить

Google