§ 13.14. Регулярные супермартингалы

Теперь мы увидим, какую важную роль играют супермартингалы в общей задаче об оптимальной остановке. Будет показано, что использование установленных свойств супермартингалов облегчает нахождение оптимального правила остановки в широком классе задач.

Пусть последовательность образует супермартингал относительно последовательности . В предыдущих трех параграфах были приведены условия, при которых для заданного правила остановки Дадим теперь следующее определение. Супермартингал называется регулярным, если для всякого правила остановки с конечным средним имеем

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

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

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

С другой стороны, если выполнено соотношение

то для принятия решения о том, надо или нет продолжать наблюдение, статистик должен проанализировать дальнейший ход процесса; Хотя средний выигрыш от проведения ровно одного наблюдения не превосходит выигрыша от немедленного окончания

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

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

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

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

Обозначим через выигрыш экзаменуемого на шаге Если он ответил правильно на первые вопросов,

то , а в случае одного неправильного ответа Если на некотором шаге, то с вероятностью с вероятностью Следовательно,

Нетрудно видеть, что тогда и только тогда, когда

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

Далее, если то распределение таково:

Отсюда видно, что случайные величины равномерно интегрируемы и, значит, по теореме 1 § 13.12 супермартингал регулярен.

Согласно теореме 1, оптимальная процедура для экзаменуемого состоит в том, чтобы отвечать на вопросы, пока его выигрыш у не достигнет порогового значения из (5), и затем остановиться.

Другими примерами применения теоремы 1 могут служить упр. 31 и 32 к гл. 12 и упр. 14 к настоящей главе.

Ситуация, описанная в теореме 1, была названа Чжоу и Роббинсом (1961) монотонным случаем и подробно изучалась ими. Таким образом, в монотонном случае, согласно теореме 1, оптимальной для статистика является «близорукая» процедура, при которой решение на каждом шаге совпадает с наилучшим решением на этом шаге, если до окончания выбора статистику разрешено провести не больше одного наблюдения.