Тема 4. Оптимальная остановка цепи Маркова.

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

а) У п р а в л е н и е д л я ц е н ы у п р а в л е н я. Предположим сначала, что процесс рассматривается лишь при . Тогда и моменты остановки ( это моменты для которых событие определяется значениями ) принимают значения из [0, N]. Обозначим через цену управления цепью Маркова при условии, что . Для того, чтобы она была определена, будем предполагать, что F (x) ограничена снизу. Пусть - любое управление для цепи . Стоимость этого управления при условии равна

.

Если фиксированная величина , то , где на множестве есть момент остановки для цепи . Инфинум этого выражения очевидно совпадает с . Остается минимизировать выражение выбором . Минимум будет достигаться, если эта вероятность равна либо 0, либо 1. Значит,

. (14)

Так как , то соотношение (14) определяет функции . Покажем, как можно строить оптимальное управление тем самым докажем его существование. Пусть построены все функции . Положим

. (15)

Из вывода соотношения (14) вытекает, что если процесс не остановлен до момента k, то его следует остановить в этот момент, если и продолжать при . Таким образом это первый момент, для которого выполнено неравенство , ( считаем, что ).

В общем случае будем считать, что используются только конечные моменты остановки, т. е. Такие, для которых . Если - цена управления для цепи при условии , то , существование предела вытекает из того, что ограничены снизу и монотонно убывают с N. Переходя к пределу в (14), получаем

(16)

Для того чтобы определить , нужно на самом деле использовать управление (14). В данном случае уже нельзя утверждать существование оптимального управления. Но существуют оптимальные управления. Можно сначала так определить измеримую функцию N (x), чтобы

.

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

б) О д н о р о д н ы е ц е п и М а р к о в а . Пусть теперь вероятность перехода не зависит от n: , т. е. Цепь является однородной. Тогда распределение последовательности при условии совпадает с распределением последовательности при условии , поэтому не зависит от k. Положим Из (16) вытекает такое управление для U (x):

. (17)

Введем некоторые понятия, связанные с однородной цепью Маркова. Будем обозначать через Pf оператор, определенный равенством для всех f, для которых . Функция f называется гармонической, если Pf = f, супергармонической, если , субгармонической, если .

 

Т е о р е м а 3. U (x) есть максимальная субгармоническая функция, удовлетворяющая неравенству .

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

 

Поскольку для всякого можно построить такой марковский момент , что для всей х , то

,

отсюда и следует субгармоничность U (x).

Пусть - также субгармоническая функция, . Если - момент остановки, , то ,

.

Заметим, что . Поэтому - субмартингал, значит,

,

.

Выбирая так, чтобы , получаем .

П р и м е р. Несимметричное случайное блуждание. Рассмотрим случайное блуждание по целым точкам с шагами , если - величина шага в момент n, то

, , p +q=1, p>q.

Уравнение (17) принимает вид

.

Рассмотрим множество тех ч, где . Если это неравенство выполняется при a<x<b ( a, b, x –целые числа), тогда для таких х

.

Если U (a) =F (a), U (b)=F (b) ( т. е. (a, b)максимальный интервал, его нельзя расширить), то

, (18)

( здесь записано решение разностного уравнения с краевыми условиями). Функцию U (x) можно находить с помощью предельного перехода

,

где - цена остановки для случайного блуждания на [ -N, N ] с остановкой на концах интервала. Для тех интервалов для которых , также справедливо представление (18). Поэтому можно найти так. Вычислим функцию по формуле (18) при a = -N, b = N. Пусть - первая точка при движении от –N , к N, для которой

Определим функцию по формуле (18) для , считая a = -N, , и затем для , считая , b = N. Пусть теперь - первая точка, где Вычисляем по формуле (18) на интервалах , , . Продолжая эту процедуру, найдем .