Вероятность: основные понятия, структура, методы. - Скороход A.B.
Скачать (прямая ссылка):
2.2. Оптимальная остановка цепи Маркова. Рассмотрим
цепь Маркова в фазовом пространстве {X, с вероятностью
перехода на я-ом шаге рп(х,А), п = 0, 1, 2..... Обозначим
через (|„, n=0, 1, 2...} реализацию этой цепи. Управление
цепью состоит в выборе момента остановки цепи т, стоимость
управления определяется некоторой ^-измеримой функцией
F(x), и если цепь остановлена в момент т, то стоимость равна
F(i,x). Как и раньше, нужно найти управление (т. е. момент
остановки), который делает средний убыток М/Г(^т) как можно
меньшим.
а) Уравнения для цены управления. Пред-
положим сначала, что процесс рассматривается лишь при
^Л^. Тогда и моменты остановки т (это моменты, для которых
событие {i = k} определяется значениями £о, \h) принимают
значения из [О, N]. Обозначим через UhN(x) цену управления
цепью Маркова |лг при условии, что %к = х. Для того,
чтобы она была определена, будем предполагать, что F(x)
ограничена снизу. Пусть т — любое управление для цепи
{%,k, ■ ■ ■, |л-}- Стоимость этого управления при условии \k = X
равна
F(x)P{x = k\lk=x}+M(F(lx)\U = x, x>k)P{x>k\lk — x).
Если фиксирована величина Р{х>k \\к = х}, то M(F (lx)\lk=^x,
t>£) = M(M(/7(iT')|b+i)|ift = -x:), где х' = х на множестве т> k
есть момент остановки для цепи ...,\n\- Инфимум этого
выражения очевидно совпадает с М {Uk+\ (Ia+i) 1\к = х) =
= ^ Uk+\ (х')рк (х, dx'). Остается минимизировать выражение
F(x)P{x = k ||ft = x} + (l-P{t = A \U=x}) \ и%+1(х)рк(х, dx')
выбором P{x = k/£,k = x}. Минимум будет достигаться, если эта
вероятность равна либо 0, либо 1. Значит,
U%(x) = F (х)л[рк(х, dx')U^(x'). (14)
Так как U%(x) = F (х), то соотношение (14) определяет функции
Uk(x). Покажем, как можно строить оптимальное управление
тем самым докажем его существование). Пусть построены все
функции Uk (х). Положим
U? (х) = J U?+i (х') рк (х, dx'). (15)
Из вывода соотношения (14) вытекает, что если процесс не
остановлен до момента к, то его следует остановить в этот
момент, если F (\к)<Uк (Ik) и продолжать при F \%k)>Uk (lk).
Таким образом х — это первый момент, для которого выполнено
неравенство F (|А)<Uk (£А), k<N (считаем, что 0%(х) =
= U»(x) = F(x)).
В общем случае будем считать, что используются только
конечные моменты остановки, т. е. такие, для которых
Р{т<оо}=1. Если Uk(x) — цена управления для цепи
{5*. Ъш,- ••} при условии Ък = х, то ик{х) = Ш1Г"(х), суще-
ствование предела вытекает из того, что и% (х) ограничены
снизу и монотонно убывают с N. Переходя к пределу в (14),
получаем
ик = (*) Л $ Ри (х, их') и^х (х'). (16)
Для того чтобы определить ик(х), нужно на самом деле ис-
пользовать уравнение (14). В данном случае уже нельзя утвер-
ждать существование оптимального управления. Но существу-
ют е-оптимальные управления. Можно сначала так определить
измеримую функцию М(х), чтобы
и$м(х)<и0{х) + е.
Если начальное значение процесса %ч = х, то, выбирая опти-
мальное управление для цепи {£0, • • •, \щх)}, получим е-опти-
мальное для процесса на бесконечном промежутке времени.
б) Однородные цепи Маркова. Пусть теперь
вероятность перехода не зависит от п: Рп(х, А) =Р (х, А), т. е.
цепь является однородной. Тогда распределение последователь-
ности п = 0, ...} при условии 1к = х совпадает с распреде-
лением последовательности п = 0, 1, ...} при условии |й =
= х, поэтому ик(х) не зависит от к. Положим ик(х)=и(х).
Из (16) вытекает такое уравнение для и(х):
1/(х) = Г(х)А]и{х')Р(х, йх'). (17)
Введем некоторые понятия, связанные с однородной цепью
Маркова. Будем обозначать через Р/ оператор, определенный
равенством Р\(х)=\\(х')Р(х,йх') для всех/, для которых
./ [0Л(—!{х'))]Р(х, йх') <оо. Функция / называется гармо-
нической, если Р/ = /, супергармонической, если Р/^/, субгар-
монической, если Р/^/.
Теорема 3. и(х) есть максимальная субгармоническая
функция, удовлетворяющая неравенству И (х) ^Р(х).
Доказательство. Для момента остановки т обозначим
через т' момент остановки для цепи {|ь \г-> . .., с]п}, где
1п = ?я+ь построенный точно так, как х для цепи (10, |ь ...}:
событие {х' — п} точно также выражается через |ь ...,^\+п, как
событие {х = п) через |0, ...,|п. Тогда 1+т' будет моментом
остановки для {£„}. Поэтому
и {х)<Ш(Р (|1+т,) | £0 = х) = М(М(Р (|1+т.) | Ь) \1о = х) =
= ^ (МР (£х,)\£0 = х')Р {х, ах') = $ М (Р 110 = х') Р (х, йх').
Поскольку для всякого е>0 можно построить такой марков-
ский "момент те, что для Есей х М(Р (|г8) | ^ ==х)< и (х) + 8, то
U(x)<$U{x')p(jc, dx') + B,
отсюда и следует субгармоничность U (х).