Свойства оптимального момента остановки в задаче наилучшего выбора

• Автор: Пешков, Николай Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Петрозаводск
• Количество страниц: 102 с.

Содержание
ВВЕДЕНИЕ

Г ЛАВА I. Асимптотические свойства оптимального момента остановки

в задаче наилучшего выбора

§ 1. Задача о секретаре

§ 2. Задача наилучшего выбора с полной информацией

§ 3. Задача наилучшего выбора с полной информацией и платой

за наблюдения

ГЛАВА II. Оптимальный момент остановки в задаче наилучшего

выбора с возвращением и в адаптивных моделях

§ 1. Задача наилучшего выбора с возвращением в условиях

полной информации
§ 2. Задача наилучшего выбора с возвращением в условиях
отсутствия информации
§ 3. Адаптивная модель задачи наилучшего выбора с частичной
информацией
ГЛАВА III. Свойства оптимального момента остановки в
многошаговых и игровых задачах наилучшего выбора
§ 1. Многошаговая задача наилучшего выбора
§ 2. Игра двух лиц с выбором из двух наблюдений
§ 3 Симметричная игра двух лиц с выбором из двух зависимых
наблюдений
§ 4 Игра с обманом с платой за наблюдения
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ВВЕДЕНИЕ
Работа посвящена исследованию структуры оптимальных правил остановки в различных моделях задачи выбора наилучшего объекта.
Задача наилучшего выбора занимает центральное место в классе задач оптимальной остановки. При решении задачи наилучшего выбора необходимо определить оптимальную стратегию поведения, т.е. оптимальный момент остановки и получаемый при использовании этой стратегии ожидаемый выигрыш.
Задача наилучшего выбора, в которой необходимо определить оптимальный момент остановки, задается последовательностью случайных величин Х, Х2,..., А'дг и последовательностью функций выигры-ша Уо! £/1(^1)^ £2),..., улг(^ 1> ®2,..., хдг), определенной на реализации
этой случайной последовательности. Различные постановки задачи наилучшего выбора возникают путем изменения способов задания данных последовательностей. Рассматриваются модели с полной информацией, в которых предполагается, что наблюдатель знает закон распределения поступающих случайных величин; модели без информации, когда решение о моменте остановки принимается на основе знания лишь относительного ранга текущего наблюдения среди всех ранее просмотренных; модели с частичной информацией, в которых известна лишь часть информации о характере распределения случайных величин. При рассмотрении последних моделей приходится применять адаптивные алгоритмы для оценки неизвестных параметров. Исследуются модели, допускающие возвращение к просмотренным ранее наблюдениям, допускающие возможность сделать выбор несколько раз и т.д. Кроме того, спектр рассматриваемых постановок расширяется за счет задания функций выигрыша. В классической задаче о секретаре необходимо максимизировать вероятность нахождения самого лучшего претендента; в задаче с полной информацией требуется максимизировать ожидаемый выигрыш.
Следует отметить, что результаты, полученные при решении задачи наилучшего выбора, привели к созданию теории оптимальной остановки в области управляемых случайных процессов, которая, в свою очередь, нашла широкое приложение, в том числе, в задаче различения статистических гипотез (Вальд [6]), в задаче быстрейшего обнаружения изменения свойств случайных процессов (так называемая ’’задача о разладке” (Ширяев [30])), в задачах о продаже недвижимости (Олбрайт [32], Дерман, Либерман, Росс [43],Мазалов, Саарио, Сакагучи [66,77,78]), в задачах стохастической финанасовой математики (Ширяев [31]).
Очевидно, что сталкиваясь с практической задачей, наблюдатель часто имеет определенные ограничения, связанные с периодом времени, в течении которого необходимо сделать выбор, или с потерями, которые он несет, обычно, финансового характера. Поэтому очень важно получить оценку длительности самого процесса выбора. Большое влияние на характер поведения момента остановки оказывают параметры задачи наилучшего выбора: информированность выбирающего о характере распределения поступающих наблюдений, наличие платы за просмотр предлагаемых вариантов, возможность возвращаться к ранее просмотренным предложениям. В связи с этим, крайне актуальной является задача оценки свойств ожидаемого момента остановки для различных постановок задачи наилучшего выбора. При рассмотрении реальных условий выбора наилучшего из предложений следует учитывать степень информированности о качестве поступающих вариантов и использовать информацию в максимально полном объеме. Для этого необходимо оценивать поступающую информацию и прогнозировать ожидаемый результат, принимая во внимание уже просмотренные предложения. Поэтому очень важным представляется построение ’’адаптивных” алгоритмов для решения задач в условиях неполной информированности. Не менее существенным является тот факт, что многие практические задачи определения лучшего объекта очень час-

Теперь определим *е следующим образом:
■{*; 4 5} = т1п{‘; 1 > }•
Итак, мы получили, что для любого положительного е существует г£, такое, что выполняется (1.35).
Отсюда следует, что верно неравенство N-1 N-1

!=*« + ! 1=<£ + 1 *=
Теперь покажем, что для любого положительного е можно определить ЛД, такой, что для всех N ^ Ые выполняется неравенство:
1=1 1=
Действительно, с учетом (1.34) и (1.38), получаем
J—l г—1 ]= з~ 4 “

ae/2c(N-I) _ ß (1 — &)аеу/^(ЛГ~1) — ß

Положим
Ne = min < N : ^ ^ 1,
l (1 - k)ae^N~l) - ß 2 J’
откуда, учитывая (1.33), окончательно получаем:
JVe = min ( ДГ: ЛГ > ln + 1) •
l V2с c(l + V2c) J
Таким образом, из (1.35) и (1.39) следует, что для любого е > О существуют te и Ne, такие что верна оценка: