§ 14.2. Марковские процессы решения с конечным числом шагов

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

Пусть на некотором шаге процесс находится в состоянии и статистик выбирает альтернативу а 6 А. В этом случае он получает выигрыш или средний выигрыш после чего процесс переходит в новое состояние пространства S в соответствии с о. в. п., задаваемой переходной функцией Предполагается, что как переходная функция так и функция выигрыша зависят только от текущего состояния процесса и от альтернативы выбранной статистиком. Ни одна из этих функций не меняется от шага к шагу и не зависит ни от состояния процесса на каком-либо из предыдущих шагов, ни от альтернатив, выбранных на этих шагах. Это предположение, как уже отмечалось в § 13.16, не является слишком ограничительным по следующей причине. Если переходная функция и функция выигрыша меняются от шага к шагуг то переопределяя пространство состояний S таким образом, чтобы номер шага процесса являлся компонентой состояния, можно обычно добиться выполнения указанного предположения. Процессы, удовлетворяющие этим требованиям, часто называют марковскими процессами решения.

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

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

Вид оптимальной процедуры может быть найден с помощью метода индукции назад. Для всякого состояния положим и определим функции следующей рекуррентной формулой:

Из этого определения ясно, что

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