ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2012, том 48, № 1, с. 80-93
МЕТОДЫ ОПТИМИЗАЦИИ
ФИДУЦИАЛЬНЫЙ ПОДХОД В ИНВАРИАНТНОЙ ЗАДАЧЕ ОПТИМАЛЬНОЙ ОСТАНОВКИ*
© 2012 г. В.З. Беленький, А.А Заславский
(Москва)
Статья является продолжением статьи (Беленький, Заславский, 2011). Подробно изучается задача оптимальной остановки (для инвариантного семейства). Вводится новое понятие "фи-дуциальная последовательность" (ФП). ФП обладает необычным дуалистическим свойством: ее члены имеют ту же физическую размерность, что и наблюдаемая последовательность, но ее вероятностное описание эквивалентно относительной безразмерной последовательности. Это свойство позволяет поставить задачу оптимальной остановки для инвариантного семейства, но с неинвариантным критерием (что ранее было невозможно). Приведены формулы функций, необходимых для расчета.
Ключевые слова: инвариантное семейство, задача оптимальной остановки, фидуциальная последовательность, принцип инертности.
ВВЕДЕНИЕ
Фидуциальные вероятности были предложены в 1920-х годах известным статистиком Р. Фишером в качестве апостериорного распределения неизвестного параметра наблюдаемой последовательности семейства случайных величин. Р. Фишер исходил из полуинтуитивной эвристической идеи "обращения вероятности", которая в дальнейшем получила строгое математическое оформление в рамках инвариантной теории. Однако инвариантная теория не вскрывает сути фишеровской идеи, ее содержательного смысла. В работе (Беленький, Заславский, 2011) инвариантная теория изложена в такой форме, которая позволила выявить сущность идеи обращения вероятности; мы назвали ее принципом инертности свободных случайных величин. Было показано, что принцип инертности имеет универсальный характер в том смысле, что инертными остаются все свободные бифункции.
Настоящая статья является продолжением публикации (Беленький, Заславский, 2011) и предполагает знакомство с нею. В работе на основе принципа инертности развивается фидуциальный подход в инвариантной проблеме оптимальной остановки (эту проблему называют обычно проблемой наилучшего выбора, best choice problem). Подход охватывает все известные ранее best choice-постановки, но позволяет также дать новые, не возможные прежде, постановки задач, когда в инвариантной ситуации критерий выбора задается неинвариантной функцией.
1. ПЕРВИЧНАЯ ЗАДАЧА ИНВАРИАНТНОГО ВЫБОРА
1.1. Каноническая постановка задачи выбора с полной информацией. Наблюдается входная последовательность (ВП) случайных величин (с.в.) p = (p., j = 1,..., n). Общее доступное число наблюдений n (горизонт просмотра) считается заданным. Априори известно совместное распределение с.в. pn := (p1,., pn)).
В каждый момент k = 1,., n наблюдатель знает уже просмотренные объекты xk = (x1,., xk) ! ! Xk (Xk - выборочное пространство с.в. pk := (p1,., pk)) и располагает двумя возможностями -
* Работа выполнена при финансовой поддержке Российского гуманитарного научного фонда (проект 09-02-00479) и Российского фонда фундаментальных исследований (проект 09-01-00156)
взять текущий наблюдаемый объект хк или продолжить наблюдение; в момент к = п вторая возможность отсутствует (взятие обязательно).
Стратегией выбора называется набор неслучайных функций 5 = {5^,..., sn}, удовлетворяющий условиям:
а) функция як зависит только от вектора хк наблюденных к моменту к величин и может принимать значения только ноль или единица; 5к(хк) = 1 означает, что при данной реализации объект хк выбирается;
п
б) необходимость и однократность выбора: / 5к(хк) / 1 6хп.
к =1
При стратегии 5 и реализации хп выигрыш наблюдателя составит величину1
п
К(хп): = / К(хк; хп)5к(хк), (1)
к =1
где неотрицательная критериальная функция К(у; хп) предполагается заданной.
Замечание 1. Не оговаривая этого особо, мы всегда предполагаем, что критериальная функция не зависит от порядка, в котором предъявляются члены входной последовательности, т.е. значение К(у; х1,., хп) не меняется при любой перестановке аргументов х,у = 1,., п (однородность во времени).
Наблюдатель решает следующую каноническую задачу оптимального выбора с полной информацией (из известного распределения).
Задача 1. Для ВП Р = (р,у = 1,., п) с известным совместным распределением найти стратегию 5, максимизирующую критериальный функционал
Сф):=Е К(рп) " тах : = V. (2)
Максимальное значение V функционала (2) называется ценой игры.
1.1.1. БР-метод. Каноническая задача может быть решена стандартным методом динамического программирования (БР). Для каждого момента наблюдения к определим тройку функций: и1 - выигрыш взятия, w1 - выигрыш продолжения, - полный (максимальный) выигрыш; все они имеют своим аргументом текущее состояние хк, а индекс 1 := п - к указывает остаточный горизонт. Функции взятия вычисляются заранее по формуле
и1 (хк) = Е (К(хк; рп)| рк = хк), 1 = 0, ..., п -1, к : = п -1, (2)
рп
и для последовательности троек функций {(и, м>, v)1} имеют место соотношения:
а) v1(xk) = тах[и1(хк), wl(xk)]■; 1 = 0,., п - 1; к := п - 1, (4)
б) ^+1 (хк-1) = Е (V1 (рк) | рк-1 = хк-1) = Е (V1 (хк-1, рк) | Рк-1 = хк-1);
рп р п
второе из которых выражает принцип оптимальности Беллмана. Если ВП - это последовательность независимых с.в., то формула (4б) упрощается и принимает вид:
б0 w1+1(xk-1) = E V1 (хк-1, р), 1 =0, ., п-1; к : = п -1.
Граничное условие
в) ^0(хп) = 0 6хп,
означающее невозможность продолжения игры при нулевом остаточном горизонте, позволяет рекуррентно найти функции w1, v1, наращивая индекс 1 = 0, 1,. по схеме
™1 -* V1-~Wl +1 . (5)
1 Мы ограничиваемся рассмотрением моделей, в которых плата за наблюдение отсутствует.
Замечание 2. Во всех этих соотношениях три целочисленных параметра k, l, n могут выбираться произвольными при соблюдении одного условия связи k + l = n.
После того как функции wl найдены, стратегия выбора s строится рекуррентно для k = 1,___,
n по правилу:
s0 := 0, sk(xk) = 1+ (s,.(xO = 0 6i = 0,_, k - 1 u(xk) > w(xk\ , = ). (6)
Эту стратегию коротко можно выразить словами: "Вести наблюдение k = 1,_, n до тех пор, пока не будет выполнено условие взятия
ul(xk) > wl(xk), l := n - k; (7)
на первом же объекте, удовлетворяющем этому условию, следует остановиться".
Таким образом, соотношения (4)-(7) описывают DP-метод решения задачи выбора.
Наиболее характерными примерами критериальных функций при выборе из ВП независимых с.в., равномерно распределенных на отрезке [0, 1], являются следующие.
Пример 1. Абсолютная независимая оценка объекта -
K(y; xn) = y. (8)
Этот пример рассмотрен в (Moser, 1956), см. также (Дынкин, Юшкевич, 1967, с. 136).
Пример 2. "Экстремистский" критерий -
'1, y = M(xn);
K (y; xn) =
M(xn) := max xf. (9)
j ! [1, n ]
0, у ! M(xn);
Выбор достигает цели только в том случае, если выбранный объект окажется максимальным среди всей группы объектов, возможных к наблюдению. Оптимальная стратегия должна максимизировать вероятность такого выбора. Пример рассмотрен в работе (Gilbert, Mosteller, 1966).
1.2. Задача инвариантного выбора. Пусть F = {Fg, g ! G} - семейство распределений с параметром g, значения которого принадлежат некоторому множеству G. Предполагается, что входная последовательность p = (p., j = 1, 2.) - это независимые одинаково распределенные с.в., подчиняющиеся общему для всех них параметру 6 ! G, значение которого абсолютно неизвестно (о нем нет никакой априорной информации, кроме включения 6 ! G). Через Y обозначим выборочное пространство членов ВП.
Семейство F называется инвариантно-групповым, если каждый элемент g задает преобразование g: Y " Y, - и семейство G этих преобразований образует непрерывную полную (g1, g2 ! G & g1g2 ! G) транзитивную группу (Vg1, g2 7 g : g2 = g1g, или, что равносильно, для любого g существует обратный элемент g-1).
Тождественному преобразованию соответствует единица группы G; обозначается 1. Свойство инвариантности состоит в том, что если p 7 6 (эта запись означает, что с.в. p подчиняется распределению F6 ! F), то gp 7 g6 Vg ! G; отсюда следует, что
Fg(y) = F(g-1y), у ! Y, g ! G, (10)
где опорная функция распределения (ф.р.) F отвечает значению g = 1.
Работа имеет методологический характер, и рассматриваются только одномерные с.в., выборочным пространством которых является либо вся прямая Y = R, либо положительная ось Y = R+ (хотя, в принципе, ничто не мешает рассмотрению многомерных с.в.).
Соответственно, рассматриваются три группы преобразований:
1) G = G сдвигов на прямой (gy := у + с);
2) растяжений G = А полуоси R+ (gy := Ay, А > 0);
3) полная, аффинных преобразований G = L на прямой (g = (А, с), gy := Ay + с).
1.2.1. Основные семейства. В работе исследуются следующие инвариантно-групповые семейства (основные семейства, (Беленький, Заславский, 2011, п. 1.1)):
Семейство 1. Равномерные распределения и(Д) на интервале А с плотностью
fg(x) = -^ X J1' x x ! R, (11)
| A | 0, x g A;
где | A | - длина интервала A.
1.1. A = [6 - 1/2, e + 1/2], g = e ! C = {с | с ! R} = R, d = 1.
1.2. a = [0, e], g = e ! л = {m | m > 0} = r+, d = 1.
1.3. A = [a, b], g = (b - a, a) ! L = {(m, с) | m > 0, с ! R}, d = 2. Здесь и всюду в дальнейшем d := dim G - размерность группы G. Семейство 2. Нормальные распределения N(a, v) с плотностью
fg (x )= _L exp{-(x - a )2/(2v2)}, x ! R. V2 rv
2.1. Параметр v задан, v := 1; g = a ! C, d = 1.
2.2. Параметр a задан, a := 0; g = v ! Л, d = 1.
2.3. g = (a, v) ! L, d = 2.
Семейство 3. Экспоненциальные распределения Ex(a, v) с плотностью
fg; л i(1/v)exp{-(x-a)/vь x>a;
f (x ) = I n x ! R
[ 0, x < a;
с подразбивкой на случаи 3.1-3.3 аналогично семейству 2.
Семейство 4. Гамма-распределения Camp(v) с плотностью
fg ( x ) = ■
здесь Г - функция Эйлера
1 .p-1
xp exp{-x /v}, x >0;
x <0; x ! R g = v ! Л;
Г(р) = У хр-1е-хЛ, р >0.
0
Отметим, что семейство 3.2 есть частный случай семейства 4, отвечающий значению р = 1.
1.2.2. Формулировка задачи инвариантного выбора. Задача ставится в предположении, что критериальная функция инвариантна. При таком критерии естественно потребовать, чтобы стратегия выбора была также инвариантной2.
Задача 2. Для
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.