Первая страница / Теория / Процессы и автоматы /

Марковские процессы

Голосование: 5, 7

Определения, вводимые обозначения и соглашения

Рассмотрим дискретные моменты времени {tk}, k = 1, 2, …. Пусть ξtk — случайная величина, характеризующая соcтояние системы в момент времени tk.

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

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

j=1m pi(j) = 1

В этой формуле m — число состояний. Будем рассматривать процесс в последовательные моменты времени, начиная с момента 0. Зададим вектор начального распределения вероятностей p(0), где p(0)(i) — вероятность нахождения процесса в состоянии i в начальный момент времени. Тогда мы можем вычислить вероятность того, что в последующие моменты времени наш процесс будет последовательно находиться в состояниях i0i1, …, it, следующим образом:

P(i0i1, …, it) = p(0)(i0pi0(i1)×…×pit −1(it)

Легко убедиться в том, что для каждого момента времени t сумма вероятностей появления всевозможных цепочек событий равна 1. Аналогично определению вектора p(0) введем вектор p(t) — вектор, составленный из вероятностей p(t)(i) того, что процесс окажется в состоянии i в момент времени t. Набор вероятностей pi(j) образует матрицу P, в которой i может считаться индексом строки, а j — индексом столбца.

p00p01p02p03
p10p11p12p13
p20p21p22p23
p30p31p32p33

Сам процесс называется в этом случае марковской цепью, а соответствующая матрица — матрицей переходных вероятностей марковской цепи. Форма записи переходных вероятностей в виде матрицы удобна тем, что вектор p(t) можно вычислить следующим образом:

p(t) = p(0)×Pt

При некоторых достаточно естественных условиях оказывается, что векторы p (t) при больших t стабилизируются. Для стабилизации достаточно хотя бы того, чтобы все вероятности в матрице P были положительны.

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

Граф переходов

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

Диаграмма порядков

В ней можно указать целых 3 эргодических класса: S1 = {EL}, S2 = {B}, S3 = {AGKFJ}. Группы букв в вершинах диаграммы порядка соответствуют множествам соответствующих вершин графа переходов. Множество вершин {AGKFJ} обозначено буквой W. Состояния, находящиеся в эргодических классах принято называть существенными, оставшиеся же называют несущественными, поскольку процесс обязательно когда-либо окажется в одном из эргодических классов.

Процессы принятия решений с конечным и бесконечным числом этапов

Рассмотрим теперь процесс, в котором существует не одна, а несколько матриц переходных вероятностей. Для каждого момента времени выбор той или иной матрицы зависит от принятого нами решения. Поясним вышесказанное следующим примером. Садовник в результате химического анализа почвы оценивает ее состояние одним из трех чисел — хорошее (1), удовлетворительное (2) или плохое (3). В результате наблюдений на протяжении многих лет садовник заметил, что продуктивность почвы в текущем году зависит только от ее состояния в предыдущем году. Поэтому вероятности перехода почвы из одного состояния в другое можно представить следующей цепью Маркова с матрицей P1:

0.200.500.30
0.000.500.50
0.000.001.00

Из этой матрицы видно, что продуктивность почвы в текущем году не становится лучше, чем в предыдущем. Например, если в прошлом году состояние почвы было удовлетворительное, то в этом году оно может только остаться таким же или стать плохим. Однако в результате агротехнических мероприятий садовник может изменить переходные вероятности в матрице P1. Тогда матрица P1 заменится на матрицу P2:

0.300.600.10
0.100.600.30
0.050.400.55

Сопоставим каждому переходу из одного состояния в другое некоторую функцию дохода, которая определяется как прибыль или убыток за одногодичный период. Так как садовник может выбирать свою стратегию — использовать или не использовать удобрения, его доход или убыток будет изменяться в зависимости от принятого им решения. Сопоставим матрицам перехода P1 и P2 матрицы R1 и R2, определяющие функции дохода.

Матрица R1:

7.006.003.00
0.005.001.00
0.000.00−1.00

Матрица R2:

6.005.00−1.00
7.004.000.00
6.003.00−2.00

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

Рассмотрим конкретный пример. Поскольку тема наших визуализаторов связана с задачей принятия решений для конечного числа этапов, рассмотрим ее формулировку для ситуации с садовником. Предположим, что садовник намеревается прекратить свое занятие общественно-полезными агроработами через N лет. Наша задача теперь состоит в том, чтобы определить оптимальную стратегию поведения садовника, то есть стратегию при которой его доход будет максимальным. Конечность числа этапов в нашей задаче отражается в том, что садовнику не важно, что будет с его сельскохозяйственным угодьем на N+1 год (ему важны все года до N включительно). Ясно, что в этом случае задача поиска стратегии превращается в задачу динамического программирования. Если через fn(i) обозначить максимальный средний ожидаемый доход, который можно получить за этапы от n до N включительно, то несложно вывести рекуррентное соотношение, связывающее fn(i) с числами fn+1(j), где j = 1, 2, …, m

fn(i) = maxk{∑j=1mpijk[rjk + fn+1(j)]}, n = 1, 2, …, N

Здесь k — номер используемой стратегии. Это уравнение основывается на том, что суммарный доход rijk + fn+1(j) получается в результате перехода из состояния i на этапе n в состояние j на этапе n+1 с вероятностью pijk. Введем следующее вспомогательное обозначение:

vik = ∑j=1mpijkrijk

Тогда написанное выше рекуррентное уравнение можно переписать следующим образом:

fN(i) = maxk{vik}
fn(i) = maxk{vik + ∑j=1mpijkfn+1(j)}, n = 1, 2, …, N−1.

Именно этот алгоритм (использующий вычисления величин fn(i)) и лежит в основе решения задачи принятия решений с конечным числом этапов. Более подробно об этом можно прочитать в [2].

Литература

  1. Романовский И.В. Дискретный анализ. Издание второе, исправленное. — СПб: «Невский Диалект», 2000.
  2. Таха Х. Введение в исследование операций. — М.: Издательский дом «Вильямс», 2001.

Визуализаторы

  1. Алексеев В. Марковские процессы принятия решений (2002)
  2. Беляев А. Марковские цепи (2002)

Беляев А., Гаврилов М., Масальских А., Медвинский М.


Света / 2008-04-16 21:30:02

В "определения, вводимые понятия и обозначения" на рис. стрелка от А к В - лишняя.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий