§ 13.19. Функциональное уравнение для марковского процесса
Мы завершим эту главу кратким обсуждением функционального уравнения, характеризующего оптимальные правила остановки. Рассмотрим задачу с выходной платой при пустом множестве 
и заданных функции стоимости с, переходной функции 
и множестве 
Для всякого 
определим 
как средний общий выигрыш от оптимального правила остановки, когда начальное состояние процесса есть 
Тогда V удовлетворяет следующему функциональному уравнению:
Так как мы предполагаем существование оптимальной процедуры, то уравнение (1) должно иметь решение. Следующие две теоремы дают некоторые условия, при выполнении которых уравнение (1) обладает единственным решением в некотором заданном классе.
Предположим, что 
функции на 
удовлетворяющие уравнению (1). Рассуждения, близкие к проведенным при доказательстве теоремы 1 § 12.12, показывают, что если 
и либо 
либо 
то
Для всех других состояний 
имеем 
Следовательно, неравенство (1) выполняется для всех состояний 
Повторяя эти рассуждения, видим, что при 
и всех состояний 
справедливо неравенство
Ясно, что каждая функция V, удовлетворяющая уравнению (1), неотрицательна на множестве 
Допустим, что средний общий выигрыш оптимальной процедуры ограничен сверху на S
неотрицательной функцией 
которая при всех 
удовлетворяет условию
Это условие вполне аналогично условию (2) § 12.12 о стабильности задач последовательного статистического решения, рассматривавшихся в том параграфе.
Теорема 1. Пусть 
неотрицательная функция на 
такая, что условие (4) выполнено при всех состояниях 
Тогда существует самое большее одна функция V, удовлетворяющая уравнению (1) и условию 
при всех 
Доказательство. Предположим, что 
две функции, удовлетворяющие уравнению (1), причем обе они ограничены «сверху функцией 
. Тогда 
для всех 
и из (3) и (4) видно, что 
для всех 
Следующая теорема применяется в основном к цепям Маркова с конечным или счетным числом состояний. Так как статистик должен закончить выбор, когда процесс находится в состояниях из множества 
то задача не меняется, если изменить переходную функцию на множестве 
так, чтобы выполнялось следующее условие: как только процесс попадает в состояние 
он остается в этом состоянии при всех дальнейших шагах. Состояния, обладающие таким свойством, называются поглощающими. Таким образом, задача статистика не изменится, если предположить, что все состояния из 
поглощающие. Предположим далее, что для некоторого состояния 
известно, что оптимальное правило остановки требует прекращения выбора в состоянии 
Тогда задача не изменится, если включить состояние 
в множество 
и считать 
поглощающим состоянием. Действительно, в этом состоянии процедура все равно должна окончиться. Этими замечаниями оправдываются предпосылки следующей теоремы.
Теорема 2. Предположим, что все состояния из 
поглощающие и для всякого начального состояния 
процесс с вероятностью 1 попадает в множество 
Тогда существует самое большее одна ограниченная на S функция 
удовлетворяющая уравнению (1).
Доказательство. Предположим, что 
две функции, ограниченные на S и удовлетворяющие уравнению (1). Так как 
для 
то из предположения теоремы следует, что для каждого заданного начального состояния 
с вероятностью 1 справедливо соотношение
Поскольку 
ограниченные функции, то из (5) видно, что математическое ожидание в правой части неравенства (3) сходится к 0 при 
Таким образом, при всех 
имеем 
Для любой цепи Маркова с конечным пространством состояний всякая функция на S ограничена и, следовательно, в условиях теоремы 2 существует не более одной функции, удовлетворяющей уравнению (1).
УПРАЖНЕНИЯ
(см. скан)
