§ 13.17. Стационарные правила остановки для марковских процессов

Предположим теперь, что для произвольного начального состояния существует оптимальное правило остановки, максимизирующее средний общий выигрыш (3) § 13.16, и это максимальное значение конечно. Заметим, что даже для простой цепи Маркова с конечным пространством состояний такое оптимальное правило может и не существовать. Например, допустим, что имеется состояние для которого с весьма большое число, причем по ходу наблюдений это состояние встречается довольно часто. Тогда для статистика может иметь смысл продолжать процесс выбора бесконечно, получая положительный выигрыш всякий раз, когда цепь попадает в состояние . С другой стороны, как мы видели, в широком классе задач оптимальная процедура, доставляющая конечный средний выигрыш, существует. Таким образом, наше предположение допустимо.

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

вероятностью 1 по крайней мере одно из состояний должно принадлежать множеству

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

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

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

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

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

Аналогично пусть для произвольного начального состояния обозначает среднюю стоимость наблюдений до достижения некоторого состояния из Тогда

Соотношение (2) получается из следующих соображений. Цена первого перехода из состояния есть с Если первый переход произошел в состояние то добавочная средняя стоимость равна с

Таблица 13.1 (см. скан)

ПРИМЕР. Рассмотрим цепь Маркова с четырьмя состояниями и стационарными переходными вероятностями. Пусть и переходная функция задается таблицей 13.1, где на пересечении строки и столбца стоит Допустим, что пустое множество, Пусть, далее, функция выигрыша имеет значения и (значения и несущественны), а цены наблюдений таковы: с Задача состоит в отыскании оптимального правила остановки.

Ясно, что если переходная функция на множестве определенная ранее, то при , и из таблицы 13.1 и соотношения (1) видно, что

удовлетворяет следующим равенствам:

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

Таблица 13.2 (см. скан)

Из сопоставления соотношения (2) и заданных значений видно, что средние стоимости наблюдений с удовлетворяют следующим соотношениям:

Решая эти уравнения, получаем: с Итак, задача сводится к случаю двух состояний с вероятностями перехода, указанными в таблице 13.2, с выигрышами и и ценами наблюдений с

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

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