Теория оптимальных правил "многократной остановки" тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

На правах рукописи УДК 519.21

Р Г Б ОД

НИКОЛАЕВ Михаил Леонидович

- 7 ФЕЗ 2000

ТЕОРИЯ ОПТИМАЛЬНЫХ ПРАВИЛ "МНОГОКРАТНОЙ ОСТАНОВКИ"

01.01.05— теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва 2000

//

Диссертация выполнена в Математическом институте им. В. А. Стеклова РАН и Марийском филиале Московского открытого социального университета.

Официальные оппоненты: доктор физико-математических наук,

профессор Веретенников А. Ю.,

Ведущая организация: Центральный экономико-математический

институт, г. Москва

Защита состоится 18 февраля 2000 года в 11 часов на заседании диссертационного совета Д 053.05.38 при Московском государственном университете по присуждению ученой степени доктора физико-математических наук по адресу: 119899, Москва, Воробьевы Горы, МГУ, Факультет вычислительной математики и кибернетики, ауд.

С диссертацией можно ознакомиться в библиотеке Факультета вычислительной математики и кибернетики МГУ.

доктор физико-математических наук Гущин А. А.,

доктор физико-математических наук, профессор Мельников А. В.

685.

Автореферат разослан января 2000 г.

Ученый секретарь совета профессор

Трифонов Н. П.

/5 /У/. 6\05

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В конце 40-х — начале 50-х годов в статистическом анализе возникло новое направление — последовательный анализ Вальда. Идея этого подхода оказалась очень плодотворной и на ее основе сформировалась новая ветвь статистики, развитая в работах А. Вальда, Дж. Волфовица, К. Дж. Арроу, Д. Блекуэлла и М. А. Гиршика. Под влиянием этого направления возникла также и задача оптимальной остановки случайных процессов, сформулированная Дж. Снеллом следующим образом.

Пусть на некотором вероятностном пространстве Р) за-

даны неубывающая последовательность ^-подалгебр С С ... С С Т и последовательность ^„-измеримых случайных величин Хп = Хп(ш), п = 0,1, 2,.... Обозначим С = {г} совокупность случайных величин со значениями из множества {0,1, 2,..., +оо} и таких, что Р(г < оо) = 1 и {ш : г (о/) = u} € Такие случайные величины называются моментами остановки, задающими правила остановки процесса Хп. Если интерпретировать Хп как "выигрыш", который получается при остановке в момент времени п, а ЕХГ — как средний выигрыш по правилу остановки г, то основные задачи теории оптимальных правил остановки состоят в нахождении цены v — supEXr и е-оптимальных правил т6 (е ^ 0), т.е. таких момен-

тес

тов, для которых ЕХГс + £ ^ v. В случае е = 0 момент т" = т0 называют оптимальным. Исходя из теории мартингалов Дж. Снелл (при достаточно широких предположениях) показал, что цена v есть Ei/o, где {Un,T„) — минимальный регулярный супермартингал, мажорирующий {Хп}, а момент т£ = inf{ra ^ 0 : Un ^ Х„ +е} является е-оптимальным (е > 0).

В работах И. Чао и Г. Роббинса, Г. Хаггстрома, Д. Сигмунда, JI. Шеппа и др. получено обобщение результатов Снелла, найдены решения некоторых задач последовательного анализа. Так ими, в частности, установлено, что если Сп С С есть класс моментов

остановки такой, что Р(т ) n) = 1 и /„ =esssup Е(А"1-|^ГП), то

гес„

"n-цена" v„ = sup ЕХГ равна Е/„, а е-оптимальный момент остановки те = inf{n ^ 0 : /„ ^ -f гг}, при Э'том последовательность {Л} совпадает (при некоторых предположениях) с минимальным регулярным супермартингалом {£/„}, мажорирующим последовательность {X,,}. Можно сказать, общая теория оптимальных правил остановки случайных процессов с дискретным временем достигла почти окончательного вида (см. книгу Г. Роббинса', Д. Сигмунда, И. Чао1 и библиографию там же).

В рассмотренную схему входит и тот случай, когда величины Хп представлены в виде Хп = • • • ,£«), где {£„} — некото-

рая последовательность, причем наибольший интерес представляет случай, когда последовательность {£„} является марковской. Общая теория марковского случая (с дискретным и непрерывным временем) построена, в основном, в работах Е. Дынкина, А. Ширяева и Б. Григелиониса. Именно эта модель детально исследована в известной монографии А. Ширяева2. А'. Факеев разработал теорию оптимальных правил остановки для процессов с непрерывным временем.

Естественным расширением общей теории оптимальных правил остановки является случай к (к 2) остановок случайного процесса. При к — 2 задача в основном решена Г. Хаггстромом3. Решение задачи в общем (к ^ 2) случае является актуальной проблемой. В качестве мотивации можно привести следующие задачи:

— обобщение задачи о наилучшем выборе на случай выбора к (к ^ 2) лучших объектов;

— многоразовая коррекция траектории движения материальной точки;

1 Роббинс Г., Сигмунд Д.. Чао И. Теория оптимальных правил остановки. М.: Наука, 1977.

2Ширяев А.Н, Статистический последовательный анализ. М.: Наука, 1969, 197G.

3Haggstrom G. Optimal sequential procedures when than one stop is required. -Aim. Math. Statist., 19G7, v.38, N G, p. 1618-1626.

— нахождение оптимальной стратегии я = (<т, т) в задаче "купли-продажи", когда покупка акции стоимостью осуществляется в случайный момент <г, продажа в момент г по цене 5Г и "доход" от операции составляет Х„т = 5Г —

— разработка процедур скорейшего обнаружения множественной разладки5.

Наконец, отметим, что проблематике статистического последовательного анализа в последние десятилетия посвящены многие конференции. г.

Замечание!..В дальнейшем под "многократной остановкой" условимся понимать к (к ^ 2) остановок случайного процесса.

Цели исследования. Диссертационная работа посвящена построению теории оптимальных правил многократной остановки случайных процессов с дискретным временем. Основными целями являются:

— нахождение условий существования и структуры оптимальных и ¿-оптимальных (е > 0) правил многократной остановки;

— исследование способов построения функции выигрыша (цены игры);

— отыскание необходимых и достаточных условий оптимальности правила многократной остановки;

—; рассмотрение ряда задач последовательного анализа, допускающих конструктивное решение.

Методика исследований базируется на основных результатах теории случайных процессов и общей теории оптимальных правил остановки случайных процессов с дискретным временем.

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

4 Ширяев А.Н. Основы стохастической финансовой математики. Т. 1, 2. М.: Фазис, 1998.

5Колмогоров А.Н., Прохоров Ю.В., Ширяев А.Н. Вероятностно-статистические методы обнаружения спонтанно возникающих эффектов. Труды МИАН СССР, М.: Наука, 1988.

к (к 2) остановок случайного процесса с дискретным временем. Наиболее существенные результаты диссертации:

— найдены условия существования и структура оптимальных и е-оптимальных (е > 0) правил многократной остановки случайных процессов;

— установлены необходимые и достаточные условия оптимальности правила многократной остановки;

— получены достаточные условия конечности с вероятностью единица кандидата на оптимальное правило многократной остановки;

— даны практически удобные способы построения выигрыша (цены игры);

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

— рассмотрены два обобщения классической задачи наилучшего выбора: выбор с максимальной вероятностью к (к ^ 2) лучших объектов из числа заданных N и задача выбора к (к ^ 2) объектов с минимальным суммарным рангом. Найдены оптимальные стратегии выбора и предельный выигрыш. Задачи показательны тем, что имеют явные решения, т.е. доведены до "числа".

Теоретическая и практическая ценность. Работа носит, в основном, теоретический характер. Ее результаты и методы могут быть использованы в научных исследованиях и учебных целях. Кроме того, разработанные процедуры могут найти применение в финансово-актуарном деле, моделях управления производством и в других областях.

Апробация работы. Результаты диссертации докладывались на семинарах, отечественных и международных конференциях как в нашей стране, так и за рубежом. В частности, на:

— семинаре Института математики АН СССР им. В.А.Стеклова

(рук. - проф. Новиков A.A., 1987), семинаре Института математики РАН (рук. - акад. РАН Прохоров Ю.В., 1999);

— Третьей (1981), Четвертой (1985) и Пятой (1989) Международных Вильнюсских конференциях по теории вероятностей и математической статистике;

— I Всемирном конгрессе Общества математической статистики и теории вероятностей им. Бернулли, Ташкент, 1986;

— 12-th European Meeting of Statisticians, Varna, Bulgaria, 1979;

— Первой (Абрау-Дюрсо, 1994), Второй (Йошкар-Ола, 1995), Третьей (Туапсе, 1996), Четвертой (Уфа, 1997), Пятой (Йошкар-Ола, 1998) и Шестой (Самара, 1999) Всероссийских Школах-коллоквиумах по стохастическим методам;

— XIX (1985), XX (1986) Всесоюзных школах по теории вероятностей и математической статистике, Бакуариани;

— 20-th Conference on Stochastic Processes and their Applications, Nahariya, Israel, 1991;

—- XII Internationaler Kongreßüber Anwendungen der Mathematik in den Ingenieurwissenschaften, Weimar, 1990;

— Всесоюзной научно-технической конференции с международным участием стран членов СЭВ "Применение статистических методов в производстве и управлении", Пермь, 1990.

Публикации. Основные результаты диссертации опубликованы в работах [1-16].

Объем и структура работы. Диссертация состоит из введения и двух глав, содержит 127 страниц текста, в списке литературы 50 названий.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении обоснована актуальность темы исследований, приведены цели работы и обзор литературы, дано краткое описание результатов диссертации.

Глава I посвящена построению теории оптимальных правил многократной остановки случайных процессов с дискретным временем.

В §1.1 приводятся необходимые для дальнейшего стандартные сведения из общей теории оптимальных правил остановки случайных процессов с дискретным временем.

В §1.2 содержится постановка задачи оптимальной многократной остановки случайных процессов с дискретным временем.

Основная схема, принятая в диссертации, следующая.

Пусть ух,у2, - ■ ■ (возможно конечная) последовательность случайных величин с известным совместным распределением. Эти случайные величины мы наблюдаем последовательно и должны решить, когда остановиться. Если мы останавливаемся в момент времени тт^ после наблюдений (у^,.. .,уШ1), то начинаем наблюдать другую последовательность 2/т1,,„1+1, у„1ит1+2, ■ ■ • (зависящую ОТ (уг,..., 2/т 1)) и решаем задачу оптимальной остановки новой последовательности. Если сделано г остановок в моменты т1,т2,...,т{ (1 ^ г ^ к — 1), то наблюдаем последовательность случайных величин у,„,,...,,„;,„,¡+1,!/™,.....«.¡да+г,---, распределение которой зависит

от (уи. ■ ■ ,у„11,утл,т1 + 1,...,утит1, • • •, 2/т, ,...,т, )• Наше решение остановиться в моменты m¡ (г = 1,2,... к) зависит лишь от наблюдений, которые уже сделаны, но не зависит от будущего, которое еще не известно. После к (к ^ 2) остановок получаем выигрыш

......тк — Зтп 1(?/1) • • • I Упг 1 ,тпл + 11 • ■ ■ 1 Ут ......ть ) )

где £Г,„,....,„1к — известная функция. Задача состоит в нахождении процедуры, которая максимизирует ожидаемый выигрыш.

Дадим более формальную постановку задачи. Всюду далее будем считать заданными:

1) вероятностное пространство

2) при каждом г — 1,2,...,к и наборе целых чисел 0 = т0 < Ш! < ... < т,-_! неубывающую последовательность ст-подалгебр {Р,,,,.....„.,■_,,ш;,т,- > т,_1} сг-алгебры Т такую, что

ГП],....ГН,-1 ^ ........ ^ -^1711,+ 1 I

3) для фиксированных целых mi,... , mfc_i, 1 ^ mi < ... < mt_i, случайный процесс

{^т 1 ,...,Г7)(,- ] ,711* ) ^rai , тщ i ^fc ^ .

В случае неформальной постановки, сделанной выше,

mi,...,mi — ^(i/ll • • • ) Ут \ j 2/т ,,011 + 1 j • • • i 2/т , ,;il2 ' ' " * > Уl .....'"i) *

Введем необходимые определения. Набор случайных величин (г!,..., г,-), принимающих значения 1,2,...,+оо, назовем правилом г-кратной остановки (1 ^ i ^ к), если он удовлетворяет следующим условиям:

а) 1 ^ Ti < т2... < г, < оо (Р-п.н.),

bj) {и> ■ П — Tnu...,Tj = rrij} £ J7mi,...tmj при всех TTij > m,_i > ... > mi ^ 1; j = 1,2,. ..,i.

Для удобства правило ¿-кратной остановки будем называть просто правилом многократной остановки (п.м.о.). Для каждого п.м.о. т = (т!,..., тк) естественным образом определим ZT = ZT, , положив

Ti(w) = mi,... ,тк(ш) = mk, mk > ... > mi > 1; если верно хотя бы одно неравенство вида r,(a>) ^ т1+1(и>) или тк (ш) = -foo.

Пусть Sm означает класс п.м.о. т = (ri,...^.) таких, что

тх ^ m (Р-п.н.). Положим vm = sup ЕZT, где супремум берется

resm

по всем т таким, что Е/?г существует. Функцию vm будем называть m-ценой, v = vx просто ценой, а п.м.о. г* € Sm, для которого математическое ожидание ЕZT. существует и ЕZT. = v, назовем оптимальным правилом многократной остановки в S,„. Будем говорить, что правило те € 5ТО является е-оптимальным (е > 0), если v,n — £ ^ и ЕZTt существует.

д

Zr{u>) =

mi т

-ОО,

Теперь мы в состоянии очертить круг основных задач:

А: отыскать условия существования и структуру т* и те;

В: найти необходимые и достаточные условия оптимальности п.м.о.;

С: получить достаточные условия конечности с вероятностью 1 кандидата на оптимальное п.м.о.;

D: вычислить ш-цену vm.

§1.3 носит вспомогательный характер. Здесь рассматриваются последовательности случайных величин, которые играют ключевую роль в нашем построении.

Введем предварительно ряд обозначений:

х+ = шах(ж,0), х~ = — шт(ж,0),

(A), = (Ai, Л2,.. ■ ,Л,), (A)i = Alf E(ni)l.i = E(f|^(ra)(),

А(т)Л = (SUP Е(т).+, (. . . (SUP Е^),,.^) ...)),

mi+1 тк-1

i(m)i£ = E(m)i( sup Е(т);+1 (... ( sup E(ra)fc_^) ...)).

Пусть T(m),- — класс правил г-кратной остановки (т), = (ть ... ,т,) (г = 1,2,...Д')ст1 = ть ... ,r,-_i = mi_1, г,- ^ т,- (Р-п.н.), где Tj,,,), = Т„п означает класс всех таких моментов остановки т1г что Ti ^ ш^Р-п.н.). Положим Х(гп)к = Z(m)k и определим последовательно от i — к по убывающим значениям г:

V(m)i. = esssup E(m).X(r)j, (1)

(r),'6T(m).

= E(*T.),-_i V"(m)i_lj,„{_l+1, i — к, к - 1,..., 1, (2)

где X0 = 0.

Наглядный смысл очевиден — это максимальный средний выигрыш, который может быть получен, если первые (г — 1) остановок сделаны в моменты т^-.-.т,-.!, а г-я остановка после момента т, при условии уже проделанных т,- наблюдений. Случайная последовательность {X(m)f} — специально построенная последовательность, которую мы останавливаем в г-й раз (г = 1,2,..., к). Например, {Xmi} — исходная последовательность, используемая для остановки в первый раз, {Х(„,)2} — для остановки во второй раз (т2 ^ тj 1) и т.д.

Оказывается, Vjm), и Х(т),. связаны рекуррентным уравнением

774 ) wl j +1} (Р-п.н.), (3)

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

§1.4 посвящен отысканию условий существования и структуры оптимального и с-оптимальных (е > 0) п.м.о., достаточных условий конечности кандидата на оптимальное п.м.о. (задачи А, С).

Теорема 1.4.1 дает условия существования и структуру оптимального в S1 п.м.о.

Теорема 1.4.1. Пусть выполнено условие

А+: E(sup А(т)1 (sup < +оо.

т 1 (m)k

Положим для г = 1,2,..., fe

т* = inf{m, > m,-.! : V(m)i = X(ra)i}

на множестве Fj_х = {ш : ra* = т1,...,т*_1 = m,^}, где считаем, что т*(и>) = -f-oo на {и> : т'_1[ш) = +оо} и F0 = П. Тогда если случайный вектор т* = (tj,...,ta?) конечен с вероятностью единица, то т* € Si является оптимальным п.м.о. и Vi = ЕtZr. (Р-п.н.).

Замечание2. Условие А+ обеспечивает существование всех рассматриваемых математических ожиданий.

При построении e-оптимальных (е > 0) правил многократной остановки будет использоваться следующая теорема.

Теорема 1.4.2. Пусть выполнено условие А+. Определим для всякого е > 0 случайный вектор т£ = (г1е,..., тке), положив для ¿=■1,2,...,*:

т1£ = inf jm, > m¡_1 : X{m)¡ > V{m). - ^ j

на множестве Fi_i = {ы : rl£ = mi,... ,T(¿_1)£ = m¿_i}, где считаем, что tíc = -fco на {ш : t"(,_i)£ = +00} 'и F0 = Q. Тогда те является правилом многократной остановки и ЕiZTe ^ Vi — е (Р-п.н.).

Следующее утверждение является обобщением теоремы 1.4.1; доказывается совершенно аналогично.

Теорема 1.4.3. Предположим, что случайные величины Z(m)h удовлетворяют условию А+ и т ^ 1} — последователь-

ность случайных векторов — (TjTO,..., т£та), определенных следующим образом:

т*т = inf{m¡ > m,_i : X(m)j = У(т),}

на множестве Fi_1 = {w : = mi,...,^^ = m,_ 1},

где положим r,*m = -foo на {u> : = -foo}, F0 = П u

m0 — m — 1. Если случайный вектор т{т) конечен с вероятностью единица, то он является оптимальным п.м.о. в Sm и Fro - ЕmZr¡m) (Р-п.н.).

Приводимая ниже теорема раскрывает роль Vm как аналога экс-цессивной мажоранты для Z^m)k и как характеристики m-цены vm.

Теорема 1.4.4. Пусть выполнено условие А+. Тогда:

а) V,„ =esssup ЕmZT (Р-п.н.);

res,,,

б) EV„, = v,n ;

в) для любого оптимального п.м.о. т 6 Sm V,n = EmZf (Р-п.н.).

Определим случайный вектор тт(е) = (rlw(e),... ,rim(£)), положив

г,ш(е) = inf |m¿ > m,_! : X(m)i. ^ V(ra)i - ||

на множестве {а; : т1т(е) = mlt... ,r(i_i),„(е) = ггг,_х}, где будем считать, что T(J+1)m(£) = оо на {u> : т,-т(е) = 00} и F0 — П, ш0 = т — 1. Как и в случае теоремы 1.4.2, тт(е) есть п.м.о. в 5,„ и E„,Zr,n(e) ^ Vm - е (Р-п.н.).

Теперь мы способны рассмотреть вопрос о существовании и структуре £-оптимального п.м.о. (е > 0).

Теорема 1.4.5. Если выполнено условие , то правило многократной остановки rm(e) является £-оптимальным п.м.о. в S,„.

Заметим, что вектор т* = (т^,... ,т£) (как и r("m() не может быть конечным с вероятностью единица, если оптимального многократного правила в Si(Sm) не существует. Более того, можно построить примеры, в которых оптимальное правило существует, а г* не является конечным. Достаточные условия конечности с вероятностью единица кандидата на оптимальное п.м.о. г* устанавливаются в теореме 1.4.6.

Теорема 1.4.6. Пусть выполнено условие Тогда случайный вектор г' является конечным с вероятностью единица, если Р-п.н.:

ak) lim Z(m\ = -00 для всех тк-\ > > ... > mx ^ 1;

nifc—»CO '

а*—1) lim supm. Zim). = -00 для всех mA._2 > rnk_3 > ... >

Ulk-1—юо

mi ^ 1;

а,) lim A(m).(supmii Z[m)k) = —00 для всех > m,_2 > ... >

m! ^ 1, г — k - 2,... ,1.

Рассмотрим теперь конечный случай. Пусть задано семейство случайных величин

{Z{m)h, 1 ^ тпх ^ Ni, mi < m2 < iV2(™i),...,

<mk 4 ^(т1,,..,т(.1)},

где iVi, Ni(-) (i = 2,...,k) являются целыми положительными числами. В частности, в эту схему входит и модель вида

{Z(m)k, 1 <С m1 < m2 < ... < mk ^ N},

которая возникает при рассмотрении многих игровых задач последовательного анализа. Очевидно, теория оптимальных правил многократной остановки, построенная выше, справедлива и в этом случае. Тогда последовательность У(га). можно определить (см. (3)) из рекуррентных уравнений "индукцией назад":

У{т);_11ТЩ+1} (Р-П.Н.) (4)

при 1 ^ тпх ^ 7\Г1?... ,т,_2 < т,_1 ^ ЛГ1_1(т1,..., т{_2), т,_! < гп{ ^ ..., т,_1), где как и прежде полагаем Х(,„)к =

Оптимальное п.м.о. г" также находится по теореме 1.4.1, а теорема 1.4.4(6) и рекуррентное соотношение (4) позволяют в принципе найти цену игры .

Доказываемая в §1.5 теорема дает необходимые и достаточные условия оптимальности п.м.о. в случае, когда случайные величины Z^m)k удовлетворяет более сильному условию, чем условие А+ (задача В).

Теорема 1.5.1. Пусть выполнено условие А+ : Е(8ирЛт1(5ир.г+ )) < +оо.

"И (т)*

Для того чтобы п.м.о. т = (гх,... ,тк) было оптимальным, необходимо и достаточно выполнения условий (Р-п.н.):

на множестве {ш : Тх — тпх,...,?{ = mi,Ti > т;};

на множестве {и> : тх — гпх,..., г,-_1 = т,_1, г, > т,}, I — 1,2,... ,к.

В общей схеме случайные величины Х(т)1 и т-цену V,,,

невозможно найти непосредственно, исходя только из определений и рекуррентных уравнений (§1.3) и теоремы 1.4.4(6) (§1.4). В связи с этим важно исследовать вопрос о возможности такого построения У(т),, Х{т){ и т-цены V,,,, которое давало бы практически удобный способ их нахождения (задача Ю).

Рассмотрим конечный случай. Пусть задано семейство случайных величин

{Z[m]k, 1 ^ Ш! < т2 < ... < тк ^ N} .

Как мы уже сказали, теория оптимальных правил многократной остановки, построенная выше, справедлива и в этом случае. Определим естественным образом основные объекты схемы. Положим (для 1 ^ ш ^ N - к + 1):

= {т € Sm : P(m ^ п < т2 < ... < тк <L N) = 1} , = sup Е ZT,

res%

T£={r16Tmi:P(T1$N-k + l) = l},

T(l)< = {(T)' e T0"h ■■P(Ti^N-k + i\ T1=m1,...,

ri_1 = m,_i) = l}, i = 2, ...,&,

У(т){ = esssup E(m).X^lt (г)<ет(т).

— i — к, к - 1, . . . , 1,

где Х£ь = Z(rh , Xrna = 0.

В силу (4) последовательность {У^.} можно определить из рекуррентных уравнений "индукцией назад":

y-.V _ yN

v»)t = rnax{xfm)(I E)ra)i^)f_iiW(+1}

при т,_! < т,- ^ JV — к + i — 1, i = к, к — 1,..., 1. Ясно, что С С ... С Sm, поэтому

Аналогично,

Vra (Р-П.н.).

Следовательно, существуют пределы

lim г£и V£= lim при этом v*n <: г>„, и Уп; v,„.

Вспомним теперь, что по теореме 1.4.4(6) m-цена v^ — поэто-

му можно вычислить из рекуррентных уравнений. Естественно задаться вопросом: при каких условиях на Z(m)k v*m совпадает с

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

Теорема 1.6.1. Предположим, что Z(m)k удовлетворяют условиям А+ и

А' : E(supmi ,4(m)l(sup(mK Z^n)J) < +оо. Тогда для г = 1,2,..., к

= Ä, = J™.

Следствие 1.6.1. Если выполнены условия А+ и А~, то т-цена

vm = lim EV^.

Л ->со

Далее мы рассмотрим другие способы конструктивного построения случайных величин V(Tn)i, Ar(m). и га-цены vm. Пусть для —со < о ^ 0 ^ b < -i-oo

z(m), (а) = max {Z{m)i, a} , Z(mh (b) = min {Z(m)k, b}

и

{b, Z(m)k > b, Z(m)!,, a ^ Z(m)i ^ b,

°> Z(m)k < a-

Определим очевидным образом (см. (1) и (2)) случайные величины ^(m).Ot (где снова х(т)Л-) = z(mhl))> соответствующие

последовательностям {^(1П)к(а)}, [Z(m)k(b)} и {Z^m)lt(a, b)}. Понятно, что они также удовлетворяют рекуррентным уравнениям (3).

Теорема 1.6.2. Пусть выполнено условие А+. Тогда Р-п.н. для ¿=1,2,..., А

lim V{m).(a) = V{n)i, lim X(mh(a) - X(m)i.

a-f — oo > ' ' Q-^ — oo i

Следствие 1.6.2. Пусть справедливо условие А+. Тогда: /P-n.w.J;

= lim lim ЕК?(а) = lim EVra(a).

<j-+-OO ЛГ-юо 0-+-00

Теорема 1.6.3. Если выполнено условие А~, то Р-га.и. lim Vjm).(6) = V(,„)., lim X(m)i(b) = X(m)i.

Следствие 1.6.3.

Пусть выполнено условие A~. Тогда (как и для Х^„).)

Vim)i = lim lim V{Zh(b) = lim lim (Р-п.н.);

О—ЮоЛ—ЮО 1 ' JV—> oo Ь—t-oo v "

Если выполнены оба условия А+ и А~, то

vm = lim lim EV^(ft) = lim lim EKiv(b).

b—юо iV—voo m V ' A'-*oc 4-+oo m V '

Пусть случайные величины Z(m)k удовлетворяет условию Л+. Положим тогда для iV ^ 2

—JV

r^.V

= maX{^(m)k,E(m)fcFjn)k ii,nt + 1} , Ш^х < mk < N. Обозначим предел Vim)k = lim , и

N—юс ^ 'h

Определим далее

V

(m)k_2,,V-l yJV-1

V (m)fc-i

SUp Х(т)к_2 r), шах , Е(т)к_, } ,

т*_з < тк-1 < N — 1, и т.д. Наконец, "jv-jt+i = EjV-jt+x( sup Xr),

r>N-k+l

V

■N-k + 1

max{xmi,ErniF^i+1+1} , 1 ^ ma < Лг - к + 1.

Теорема 1.6.4. Пусть выполнены условия А+ и А~. Тогда с верояностью единица = ^(т), и = Х(т)г

Следствие 1.6.4. При выполнении условий А+ и А~

lim EV*.

ЛГ-юо m

Мы суммируем предшествующие результаты в следующей теореме.

Теорема 1.6.5. Пусть выполнено условие А+. Тогда

lim lim lim ЕV£(a,b),

о—» - ос Ь—юо N—юо

lim lim lim EV£'(a,ft),

_ 3-+-OC ЛГ-ЮО l-»cc

lim lim lim EV^fa, t),

ci —^ — oc b—юо Л"-юо

lim lim lim EF,„(a, 6).

. a—» —со Л'—too fr—юо

Для большого класса задач оптимальной многократной остановки можно ограничиться рассмотрением случая, когда случайные величины 2(т))г представимы в виде — д{хт1,... ,хт/1), где {¡с,,} — марковская последовательность.

Целью параграфа 1.7 является описание оптимальных и е~оптимальных правил многократной остановки в марковском случае.

Дадим более точную формулировку марковского случая. Предположим, на произвольном вероятностном пространстве (П, Т, Р) заданы:

1) марковская цепь {жт, Тт, т ^ 1} в фазовом пространстве {X,13), где — неубывающая последовательность <т-подалгебр сг-алгебры Т\

2) при каждом г ~ 1,2,... ,к а наборе целых чисел 0 = т0 < т 1 < ... < т,_! неубывающая последовательность <т-подалгебр {^г(то).,т1- > т,..!} сг-алгебры Т такая, что

(т);_1 С ^(т); С т," >

3) для фиксированных целых тп1,..., тпк_1, 0 = га0 < гпх < ... < случайный процесс {2{т)к,^{т)к,тк > тк_1}, где ■Я(т)к ~ ^(«т,, • • • 1к), а д{х,у, ... ,г) является действительной Вк-измеримой функцией, определенной на Хк.

Определим ш-цену игры

ит = вир Е2Т - вир Ед(хГ,----,хГк)

и скажем, что п.м.о. т е 5т, если г € 5„, и существуют такие В, € Б, что

тг = тГ{гп! ^ т : хт1 € Вх} , г, = тГ {т, > : ж,,,,. € Д } ,

где B¡ ~ B¡(тl,.. .,гГь,..., гГ)._,), г — 2,..., к. Наглядный смысл 5т понятен — это класс п.м.о. без "памяти", т.е. запоминаются лишь состояния цепи в моменты ,..., тк.

Утверждение, что тп-цена ига достигается на 5,,,, является интуитивно очевидным, так как в марковском случае наше решение об

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

Теорема 1.7.1. Предположим, что условие А+ выполнено. Тогда

ут = вир Ед(хТ1,...,хГк).

г£5га

В главе II рассматривается применение общих результатов теории оптимальных правил многократной остановки к трем задачам последовательного анализа. Задачи показательны тем, что допускают явные решения, т.е. доведены до "числа".

Предмет §2.1 составляет задача нахождения оптимального п.м.о. в схеме Бернулли.

Пусть задана последовательность независимых испытаний имеющих распределение Бернулли с Р(£, = 1) = р = 1 - = 0) = 1 — д, 0 < р < 1. Определим длину успешной серии испытаний (число единиц, идущих подряд, считая назад от г-го наблюдения):

1

Щ = = Уп+1 = ... = у,- = 1).

» ->

Определим наш суммарный выигрыш после к (к ^ 2) остановок (серий успешных испытаний)

г{т)к = л?» + + ■ • •+- стк = ¿с.1+1>

¡=1

1 ^ г«! < т2 < ... < тк,

где с — цена за испытание, причем с < 1, так как при с ^ 1 Z^m)k ^ 0 и стратегия тривиальна — не делать испытаний, д™*_1+1 = с(ш, - т,_ 1) — "чистый" выигрыш только после г-ой серии (как всегда тп0 = 0).

Положим

vN - sup EZr.

resf

Цель параграфа — описать оптимальное правило многократной остановки г* = (гг*,... ,т£) 6 Sf, вычислить цену игры vN и найти lim vx.

N-+00

Установлено, что оптимальное правило многократной остановки т* = (rj,..., г£) имеет вид:

т" — min{m, > m,_i : (mf) ü"J;_j+1) G Г,}

на множестве F,_x = {а» : т{ = m1(... ,т*_1 = m^i}, г = 1,2,..., к, где т0 = О, F0 = П, (тi,Rn]_l+1) — состояние игры на момент rrii в г-ой серии успешных испытаний, а Г, — специальные опорные множества.

Структура опорных множеств Г2 (при к — 2) раскрывается в теореме 2.1.1.

Теорема 2.1.1.

1) Состояние {t,R) £ Г2 тогда и только тогда, когда

„ р — с v<i 1 р — с с,

R > --+ и*-*-1, где иГ1 = ---, и? = 0.

Ч Я

2) Если с ^ 2 — 1/р, то (t, 72) 6 Д тогда и только тогда, когда

N—t — 1 V—t

_ р — с и, а — и, V . 1 n п

R 2 --+ —---1— + И"1-1, где u° = = 0.

Ч Ч

Здесь и'з" — цена игры с m испытаниями и одной остановкой.

В следующей теореме найдена формула, позволяющая вычислять предельный оптимальный выигрыш lim vN (к 2).

Лг~*оо

Теорема 2.1.2. Пусть R - min{Ä' > 0 :pn'+1 ^ с}. Тогда lim ^АД-МЦЙ.

JV-»oo IP

В качестве примера приведем численные значения при р — \

N ~ г>(Л') „(ЛИ

ожидаемого выигрыша v и длин успешных серии R{ ' и щ для iV-шаговой игры, когда необходимо остановиться в первый и во второй раз, соответственно, если остается сделать т испытаний, а также значения для v* = lim vN.

N—юо

с = 0.25 с = 0.125

R[N) = 1, m £ 2 (jV, f 1, 2^m<4, 1 ~ 1 2, m > 4

R{2W) = 1, m £ 1 (jv) _ j 1, m = 1, Л2 ~ \ 2, m > 1

N vN N г;Л' ■

2 0.5000 2 0.7500

3 0.6875 3 1.0313

4 0.8125 4 1.2350

5 0.8906 5 1.3909

6 0.9375 6 1.5158

7 0.9648 7 1.6388

8 0.9805 8 1.7309

9 0.9893 9 1.8436

10 0.9942 10 1.9343

N со 1 iV —^ oo 2.5

Последующие два параграфа главы II посвящены двум различным обобщениям классической задачи наилучшего выбора.

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

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

Задача в классической постановке рассматривалась в работах М. Гарднера, Е. Дынкина, Е. Дынкина и А. Юшкевича, И. Чао, С. Моригути, Г. Роббинса и С. Самуэлса, А. Ширяева и др. Как известно, оптимальная стратегия выбора имеет вид; существует такой номер ку, что первые к"у - 1 объектов надо пропустить, а затем остановить свой выбор на первом объекте, который лучше всех предшествующих; при этом Ы/е < к^ < И/е + (2 - 1/е) и вероятность удачного выбора при N —оо равна 1/е 0,368.

Всевозможные обобщения, но на случай выбора только одного объекта, исследовались в работах Е. Дынкина и А. Юшкевича, И. Джилберта и Ф. Мостеллера, С. Гусейн-Заде. Э. Пресмана и И. Соиина, Б. Березовского и А. Гнедина.

В §2.2 изучена задача выбора с максимальной вероятностью сразу к (к ^ 2) лучших объектов.

Пусть имеется N объектов, которые определенным образом упорядочены по качеству, т.е. можно сказать, какой из них самый лучший, какой второй по качеству и т.д. Занумеруем объекты в том порядке, как мы знакомимся с ними. Объекты поступают к нам в случайном порядке, т.е. все /V! перестановок равновероятны. В момент я нам известны сравнительные качества объектов аь а2,..., а,, но мы ничего не знаем о качестве остальных N — я объектов. После ознакомления с а, мы можем его либо принять (и тогда выбор одного объекта сделан), либо отвергнуть и продолжить наблюдения (тогда вернуться к отвергнутому объекту невозможно). Требуется найти оптимальную стратегию, обеспечивающую наибольшую вероятность выбора к объектов, лучших по качеству.

Поставленная выше задача математически может быть описана следующим образом. Пусть (ах, а2,..., а^) — любая из ЛМ перестановок чисел (1,2,...,АГ) (число 1 соответствует лучшему объекту, N — худшему). Так как порядок выбора объектов случаен, то ве-

рояхность любой комбинации (аи а2,..., a.v) равна Для каждого г — 1,2,..., N определим y¡ = т] если а, является m-м по качеству среди объектов (аь ..., а,). Нетрудно показать, что yi,.-.,yt\ независимы и

р (j = l,2,...,¿), г

Р(а, = т\ у1=1и..., у,_х - у, =

^m-l^JV-m

P (а, -m\yi- j)

a

N

где (как всегда) 0! = 1, С™ — 0 при п < т и то < 0.

Пусть (г1}..., ik) — произвольная перестановка чисел 1,2,..., к. Стратегию выбора г* = (т^,..., т£), 1 ^ т{ < < ... < ^ N, для которой

Р ( U {ат; = ¿1. • ■ • > = «»})

(.■„-,и)

- sup р( IJ {аГ1 =»!,..., аг„ = »*}) = Р;,, (5)

(и,...,..) 7

назовем оптимальной.

Задача наилучшего выбора состоит в нахождении оптимальной стратегии т* = (г^,..., г£).

Обозначим — ^mlV.V.'mk условную вероятность события

{amj = г\,..., a„lJr = гА.} относительно <т-алгебры ^(,,,)„ = (где Тт>, порождена наблюдениями (ух,... ,ymh)) и положим

Zl™)> - Y1 Щт)ь > (¿1, ...,«•*)

где

í=i

и

Bi = {w : ym, - jhymi+1 > 1,- ..,y„„+l_i > I ~ 1,2,... - 1;

2/m, = 1, Ут2 = 1 или 2, ..., ymii = 1 или 2 ... или к.

Тогда из (5) следует, что

P*v = EZT. = sup EZr = т/f. res.

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

Показано, что решением задачи является следующая оптимальная стратегия: существует такой набор (ttJ,. .. 1 ^ ttJ < ... < 7ГI ^ N, что первые — 1 объектов надо пропустить, а затем остановиться на первом объекте, который лучше всех предшествующих, во второй раз — на первом объекте, который лучше всех предшествующих или хуже ровно одного (в том случае, если просмотрено т, -1 объектов); третий выбор следует делать на первом объекте, который лучше всех предшествующих или хуже ровно одного (если просмотрено — 1 объектов) или хуже ровно двух (если просмотрено 713 — 1 объектов) и т.д.

Разберем подробнее задачу о наилучшем выборе двух объектов.

Обозначим и Z^'^ условные вероятности событий {em —

1, а„ = 2} и {ат —2, а„ = 1} относительно Ттп — Тп (тп < п) и положим Zmn = + ZgfK Тогда из (6)

п ,, п(п — 1)

т'п ~ N(N - 1) *Ут = > > 1.У.. = 2),

¡о 14 п(п — 1)

= N(N - 1)"Ут = Ут+1 > 1' • • • ' У"-1 > 1. У» = 1).

а оптимальная стратегия выбора двух лучших объектов т* = (тг*, г,) имеет следующую структуру:

т{ = min{m ^ к'у : ym = 1}, То — min[min{7z > m : уп — 1},

min{n > m : п Гм,уп = 2}] на {т^ = mj,

где ку и l"N (1 < к~у < l*N ^ Лг) — найденные "пороговые" значения Приведем теперь выражение для оптимального предельного вы игрыша. Положим а* = lim ß* — lim и Р* — lim Pt. =

JV-чоо N N-¥oo Л ЛГ-+0О

lim vf. Тогда

N-ico

P* = sfep - 2 Inц + 2ve - 5) % 0,225,

Vе

где 229 есть корень уравнения у/ёц - In ц = ~ - у/ё, а а* — ц

ß* — е'1?2.

В задаче о наилучшем выборе (§2.2) пусть г,- обозначает абсо лютный ранг выбранного объекта, т.е. ж, = 1+число объектов и: (ах, а2,..., а.у) < а,-. Требуется (§2.3) найти оптимальную стратегик выбора, которая будет минимизировать математическое ожидание абсолютных рангов Е(гт, ... + xTk), k ^ 2.

Математически задачу можно описать следующим образом Пусть (®х, ж2,..., Ху) — случайная перестановка чисел (1,2,..., N) т.е. все N1 перестановок равновероятны. Для каждого i — 1,2,..., Л определим относительный ранг г-го объекта у, = т, если среди объ ектов а,,а2,... ,а,_! существует ровно т - 1 объект с качествам* меньшими качества объекта а, . Как мы уже отметили, у1> уг, ■ ■ ■, у2\ независимы и

Р(гл = Я = 1Л 0'= 1,2,...,«),

Р(ж,- = k\ y1-l1,..., 1 = li-uVi = j) = P(®f = k I Vi = л

fii-ls-ii-} ^k-l^N-k

где (как обычно) 0! = 1, С,"' = 0 при га < m и m < 0.

Тогда

| Vi = i) = f; fcP(a< = Л I У.- = j) = (7)

Положим

Цель настоящего параграфа — найти оптимальную процедуру выбора к объектов г* = ... 6 Sf и предельный выигрыш v* — lim v?.

Л'-юс

Пусть Я(1И){ есть (г-алгебра, порожденная наблюдениями (j/i>y2i-- -! Утщ)- Чтобы привести нашу задачу к стандартному виду задач оптимальной многократной остановки, необходимо положить

дг 1

тп)k = E(m)fc {xml + ••■ + X,„k) = 2^gmiT»b + ~-->

~ m(. + i

где £rn!iint - E(m)k«mi.. Тогда из (7)

. . iV + 1

E(m);«mi = у,„.) — -—Угщ

rrij + 1

и = inf EZr (где г = (r)t. = (ть ..., г*)).

Итак, наша задача свелась к задаче нахождения оптимального п.м.о. т" для последовательности {Z[,n)k}-

Оказывается, оптимальное п.м.о. т*, задающее оптимальную стратегию выбора к объектов, имеет вид:

т- = min{m, > rn,_1 : ym. ^

на множестве = {о; : т{ = ... — m,_i}, где F0 = Q, — специально построенные последовательности целых чисел.

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

вид.

Кроме того, установлено, что при к — 2

В заключение приведем численные значения при N — 5,1С ожидаемого выигрыша г»^ и последовательностей чисел <5(1) =

N ¿(2) <

5 (0,1,1,5) (1,1,2,5) 131/30

10 (0,0,1,2,2,3,4,5,10) (0,0,1,1,2,2,3,5,10) « 6,318

Поясним на примерах. Пусть (2,5,1,3,4) — пример перестановки чисел (1,2,3,4,5), где 1 соответствует лучшему объекту, 5 — худшему. Их относительные ранги: уг = 1, у2 = 2, = 1, = 3, у5 — 4. Тогда оптимальная процедура выбора, задаваемая правилом двукратной остановки т* = (т{, г,*), где

г* - min{m ^ 1 : ym ^

Tj = min{n > m : у,, ^ при Tj = m,

даст t* — 3 (и £3 = 1), rj = 5 (и хъ — 4), т.е. выигрыш будет равен ж3 +£4 = 1-1-4 — 5 (чуть хуже, чем 1+2 = 3). Еще один вариант: (4,2,5,1,3). Тогда т{ — 2 (и х2 = 2), т2 = 4 (и ж3 = 1) и выигрыш есть х2 + = 2 + 1 = 3, т.е. в этом случае оптимальная процедура выбора "вылавливает" оба лучших по качеству объекта.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Николаев М.Л. Об одном обобщении задачи наилучшего выбора.

- Теория вероятн. и ее примен., 1977, т. 22, вып. 1, с. 191-194.

2. Николаев М.Л. Построение цены одной последовательной игры. -

Вероятностные методы и кибернетика. Казань, 1978, вып. 14, с. 56-67.

3. Николаев М.Л. Обобщенные последовательные процедуры. -

Литов. матем. сб., 1979, т. 19, N3, с. 35-44.

4. Nikolaev M. Generalized sequential procedures in Markov case. - In:

12-th European Meeting of Statisticians. Abstracts. Varna, 1979, p. 176.

5. Николаев М.Л. О критерии оптимальности обобщенной после-

довательной процедуры. - Литов. матем. сб., 1981, т. 21, N3, с. 75-82.

6. Николаев М.Л. О способах отыскания цены обобщенной после-

довательной игры. - В сб.: XIX школа-коллоквиум по теории вероятностей и математической статистике. Тезисы докладов. Бакуриани, 1985, с. 86-87.

7. Николаев М.Л. Об одном способе отыскания цены обобщенной по-

следовательной игры. - В сб.: IV Международная вильнюская конференция по теории вероятностен и математической статистике. Тезисы докладов. Вильнюс, 1985, т. II, с. 121-122.

8. Николаев М.Л. Задача наилучшего выбора к объектов. - В сб.:

Первый Всемирный Конгресс общества математической статистики и теории вероятностей. Тезисы докладов. Ташкент, 1986, т. 1, с. 323.

9. Nikolaev M. Generalized sequential procedures for Markov sequences

- In: The 20-th Conference on Stochastic Processes and the.ii applications. Abstracts. Nahariya, Israel, 1991, p. 73.

10. Николаев М.Л. Оптимальные правила многократной останови

в схеме Бернулли. - В сб.: Всероссийская школа-коллоквиум по стохастическим методам. Тезисы докладов. М.: ТВП, 1994 с. 86-88.

11. Николаев М.Л. Об одном способе отыскания цены в зада-

че многократной остановки,- В сб.: II Всеросийская школа-коллоквиум по стохастическим методам. Тезисы докладов. М.: ТВП, 1995, с. 108-110. .

12. Николаев М.Л. Об одной игровой задаче последовательного ана-

лиза. - Обозрение прикладной и промышленной математики,

1997, т. 4, вып. 3, с. 385-386.

13. Николаев М.Л. Об оптимальной многократной остановке по-

следовательности независимых наблюдений. - Обозрение прикладной и промышленной математики, 1998, т. 5, вып. 2, с. 260.

14. Николаев М.Л. Оптимальные правила многократной остановки.

- Обозрение прикладной и промышленной математики, 1998, т. 5, вып. 2, с. 309-348.

15. Николаев М.Л. Об оптимальной многократной остановке мар-

ковских последовательностей. - Теория вероятн. и ее примен.,

1998, т. 43, вып. 2, с. 374-382.

16. Николаев М.Л. О некоторых задачах оптимальной многократ-

ной остановки, допускающих конструктивное решение. - Обозрение прикладной и промышленной математики, 1999, т.6, вып. 1, с. 183-184.

Введение

Глава I. Оптимальные правила многократной останов

§1.1. Задача оптимальной остановки

§1.2. Постановка задачи многократной остановки

§1.3. Вспомогательные результаты.

§1.4. Оптимальные и ^-оптимальные правила многократной остановки

§1.5. Необходимые и достаточные условия оптимальности правила многократной остановки.

§1.6. О способах построения цены игры.

§1.7. Марковский случай.

Глава II. Некоторые применения к задачам последовательного анализа

§2.1. Оптимальное правило в схеме Бернулли.

§2.2. Об одном обобщении задачи наилучшего выбора

§2.3. Задача выбора к объектов с минимальным суммарным рангом.

В конце 40-х — начале 50-х годов в статистическом анализе возникло новое направление — последовательный анализ Вальда. Идея этого подхода оказалась очень плодотворной и на ее основе сформировалась новая ветвь статистики (А.Вальд [1], А.Вальд, Дж.Волфовиц [2] и К.Дж.Арроу, Д.Блекуэлл, М.А.Гиршик [3]). Под влиянием этого направления возникла также и задача оптимальной остановки случайных процессов, сформулированная Дж. Снеллом [4] следующим образом. Пусть на некотором вероятностном пространстве заданы неубывающая последовательность сг-подалгебр С С . С Тп С Т и последовательность ^"„-измеримых случайных величин Хп = Xn(uj),n = 0,1,2,Обозначим С = {г} совокупность случайных величин со значениями из множества {0,1,2., +оо} и таких, что Р(т < оо) = 1 и {ш : т(ш) — п} G Тп. Такие случайные величины называются моментами остановки, задающими правила остановки процесса Хп. Если интерпретировать Хп как "выигрыш", который получается при остановке в момент времени n, а ЕХТ — как средний выигрыш по правилу остановки т, то основные задачи теории оптимальных правил остановки состоят в нахождении цены v = sup ~ЕХТ и тес е-оптималъных правил те{е ^ 0), т.е. таких моментов, для которых ЕХТе + е ^ v. В случае £ = 0 момент т* = tq называют оптимальным. Исходя из теории мартингалов Дж.Снелл (при достаточно широких предположениях) показал, что цена v есть Ei7o> где (Un,Fn) минимальный регулярный супермартингал, мажорирующий {Хп}, а момент те = inf{n ^ 0 : Un ^ Хп + г} является е-оптимальным (е > 0).

В работах И.Чао и Г.Роббинса [5] - [7], Г.Хаггстрома [8], Д.Сиг-мунда [9], Л.Шеппа [10] и др. получено обобщение результатов Снел-ла, найдены решения некоторых задач последовательного анализа. Так ими, в частности, установлено, что если Сп С С есть класс моментов остановки такой, что P(r ) n) = 1 и /„ =esssup Е(Хт\Тп), то тесп n-цена" vn = sup ЕХТ равна Е/п, а ¿г-оптимальный момент остатесп новки те = inf{n ^ 0 : /п ^ Хп + е}, при этом последовательность {/п} совпадает (при некоторых предположениях) с минимальным регулярным супермартингалом {Un}, мажорирующим последовательность Можно сказать, общая теория оптимальных правил остановки случайных процессов с дискретным временем достигла почти окончательного вида (см. книгу Г.Роббинса, Д.Сигмунда, И.Чао [11] и библиографию там же).

В рассмотренную схему входит и тот случай, когда величины Хп представлены в виде Хп = дп(£о, ., £п), где {£п} — некоторая последовательность, причем наибольший интерес представляет случай, когда последовательность {£п} является марковской. Общая теория марковского случая (с дискретным и непрерывным временем) построена, в основном, в работах Е.Дынкина [12], А.Ширяева и Б.Григелиониса [13], Б.Григелиониса [14]. Именно эта модель детально исследована в книге А.Ширяева [15]. А.Факеев [16] разработал теорию оптимальных правил остановки для процессов с непрерывным временем.

Естественным расширением общей теории оптимальных правил остановки является случай к (к ^ 2) остановок случайного процесса. При к = 2 задача в основном решена Г. Хаггстромом [18]. Решение задачи в общем (к ^ 2) случае является актуальной проблемой. В качестве мотивации можно привести следующие задачи: обобщение задачи о наилучшем выборе на случай выбора к (к ^ 2) лучших объектов; многоразовая коррекция траектории движения материальной точки; нахождение оптимальной стратегии тг = (сг, г) в задаче "купли-продажи" , когда покупка акции стоимостью осуществляется в случайный момент сг, продажа в момент г по цене Бт и "доход" от операции составляет Х^ — Бт — Ба [17], [43], [44]; разработка процедур скорейшего обнаружения множественной разладки [42].

Замечание 1. В дальнейшем под "многократной остановкой" условимся понимать к (к ^ 2) остановок случайного процесса.

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

Остановимся несколько подробнее на содержании диссертации.

1. Валъд А. Последовательный анализ. М.: Физматгиз, 1.60.

2. Wald A., Wolfowitz J. Optimum character of the sequential probabilityratio test.- Ann. Math. Statist., 1948, v. 19, N 3, p.326-339.

3. Arrow K.I., Blackwell D., Girshick M.A. Bayes and minimaxsolutions of sequential decision problems.- Econometrica, 1949, v. 17, p. 213-214.

4. Snell I.L. Applications of martingale system theorems.- Trans. Amer.Math. Soc., 1953, v. 73, p. 293-312.

5. Chow Y.S., Robbins H. A martingal system theorem and applications.- In: Proc. Fourth Berkeley Symp. Math. Statist Prob. / Univ. Calif. Press, USA, 1961, v. 1, p. 93-104.

6. Chow Y.S., Robbins H. On values associated with a stochastic.sequence.- In: Proc. Fifth Berkeley Symp. Math. Statist. Prob. / Univ. Calif Press, USA, v. 1, 1967, p. 427-440.

7. Chow Y.S., Robbins H. On optimal stopping rules.- Z.Wakrssheinlichkeitstheorie, 1963, N 2, p. 33-49.

8. Haggstrom G. Optimal stopping and experimental design.- Ann. Math.Statist., 1966, v. 37, N 1, p. 7-29.

9. Siegmund D.O. Some problems in the theory of optimal stoppingrules.- Ann. Math. Statist., 1967, v. 36, N 6, p. 1627-1640.

10. Shepp L.A. Explicit solutions to some problems of optimal stopping.- Ann. Math. Statist., 1969, v. 40, N 3, p. 993-1010.

11. Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. М.: Наука, 1977.

12. Дынкин Е.Б. Оптимальный выбор момента остановки марковскогопроцесса.- ДАН, 1963, т. 150, вып. 2, с. 238-240.

13. Григелионис Б.И., Ширяев А.Н. О задаче Стефана и оптимальныхправил остановки марковских процессов. Теория вероятн. и ее примен., 1966, т. 11, вып. 4, с. 612-631.

14. Григелионис Б.И. Об оптимальной остановке марковских процессов.-Литов. матем. сб., 1967, т. 7, вып. 2, с. 265-279.

15. Ширяев А.Н. Статистический последовательный анализ. М.: Наука, 1969, 1976.

16. Факеев А.Г. Об оптимальной остановке случайных процессов с непрерывным временем. Теория вероятн. и ее применен., 1970, т. 15, вып. 2, с. 336-344.

17. Ширяев А.Н., Кабанов Ю.М., Крамков Д.О., Мельников А.В. Ктеории расчетов опционов европейского и американского типов.

18. II.- Теория вероятн. и ее применен., 1994, т. 39, вып. 1, с. 23129.

19. Haggstrom G. Optimal sequential procedures when more than one stopis required. Ann. Math. Statist., 1967, v. 38, N 6, p. 1618-1626.

20. Николаев M.JI. Обобщенные последовательные процедуры. Литов. матем. сб., 1979, т. 19, N 3, с. 35-44.

21. Николаев M.JI. О критерии оптимальности обобщенной последовательной процедуры. Литов. матем. сб., 1981, т. 21, N 3, с. 75-82.

22. Николаев M.JI. О способах отыскания цены обобщенной последовательной игры. В сб.: XIX школа-коллоквиум по теории вероятностей и математической статистике. Тезисы докладов. Баку-риани, 1985, с. 86-87.

23. Николаев M.JI. Об одном способе отыскания цены обобщенной последовательной игры. В сб.: IV Международная вильнюская конференция по теории вероятностей и математической статистике. Тезисы докладов. Вильнюс, 1985, т. II, с. 121-122.

24. Николаев M.JI. Построение цены одной последовательной игры.- Вероятностные методы и кибернетика. Казань, 1978. вып. 14, с. 56-67.

25. Николаев M.JI. Об одном способе отыскания цены в задаче многократной остановки. В сб.: Всеросийская школа-коллоквиум по стохастическим методам. Тезисы докладов. М.: ТВП, 1995, с. 108-110.

26. Starr N. How to win a war if you must: optimal stopping based onruns. Ann. Math. Statist., 1972, v. 43, p. 1884-1893.

27. Nikolaev M. Generalized sequential procedures in Markov case. In:12.th European Meeting of Statisticians. Abstracts. Varna, 1979, p. 176.

28. Gardner M. Mathematical games Sci. Amer., 1960, v. 202, N 1,p.150-156; 1960, v. 202, N3, p. 173-182.

29. Дынкин Е.Б. Достаточные статистики для задачи об оптимальнойостановке. Теория вероятн. и ее примен., 1968, т. 13, вып. 1, с. 150-151.

30. Дынкин Е.Б., Юшкевич А.А. Теоремы и задачи о процессах Маркова. М.: Наука, 1967.

31. Chow Y.S., Moriguti S., Robbins H., Samuels S.M. Optimal selectionbased on relative rank (the "secretary problem"). Israel J.Math., 1964, v. 2, N 2, p. 81-90.

32. Gilbert J.P., Mosteller F. Recognizing the maximum of a sequence.J.Amer.Statist.Assoc., 1960, v. 61, N 313, p. 35-73.

33. Гусейн-Заде С.М. Задача выбора и оптимальное правило остановки последовательности независимых испытаний.- Теория веро-ятн. и ее примен., 1966, т. 11, вып. 3, с. 534-537.

34. Пресман Э.Л., Сонин И.М. Игровые задачи оптимальной остановки. Существование и единственность точек равновесия. В кн.: Вероятностные проблемы управления в экономике. М.: Наука, 1977.

35. Пресман Э.Л., Сонин И.М. Задача наилучшего выбора при случайном числе объектов. Теория вероятн. и ее примен., 1972, т. 17, вып. 4, с. 695-706.

36. Березовский Б.А., Гнедин A.B. Задача наилучшего выбора. М.:Наука, 1984, 196 с.

37. Николаев M.JI. Об одном обобщении задачи наилучшего выбора.- Теория вероятн. и ее примен., 1977, т. 22, N 1, с. 191-194.

38. Николаев M.JI. Задача наилучшего выбора к объектов. В сб.:Первый Всемирный Конгресс общества математической статистики и теории вероятностей. Тезисы докладов. Ташкент, 1986, т. 1, с. 323.

39. Tamaki М. A secretary problem with double choices.- J.Oper.Res.Soc.Jap., 1979, v. 22, p. 257-265.

40. Vanderbey R. The optimal choice of a subset of population.-Math.Oper.Res., 1980, v. 5, N 4, p. 481-486.

41. Glasser K. The ¿-choice secretary problem.- Cent. Nav. Anal. Profess.Pap., 1979, N 253.

42. Glasser K., Holzsager R., Barron A. The d choice secretaryproblem. Commun. Statis. - Sequential analysis, 1983, v. 2, p. 177-199.

43. Колмогоров A.H., Прохоров Ю.В.,Ширяев А.Н. Вероятностностатистические методы обнаружения спонтанно возникающих эффектов. Труды МИАН СССР, М.: Наука, 1988.

44. Ширяев А.Н. Основы стохастической финансовой математики. Т.1, 2. М.: Фазис, 1998.

45. Мельников А.В. Финансовые рынки. М.: ТВП, 1997.

46. Nikolaev М. Generalized sequential procedures for Markov sequences.- In: The 20-th Conference on Stochastic Processes and their applications. Abstracts. Nahariya, Israel, 1991, p. 73.

47. Николаев M.JI. Об одной игровой задаче последовательного анализа. Обозрение прикладной и промышленной математики, 1997, т. 4, вып. 3, с. 385-386.

48. Николаев М.Л. Об оптимальной многократной остановке последовательности независимых наблюдений. Обозрение прикладной и промышленной математики, 1998, т. 5, вып. 2, с. 260.

49. Николаев М.Л. Оптимальные правила многократной остановки.Обозрение прикладной и промышленной математики, 1998, т. 5, вып. 2, с. 309-348.

50. Николаев М.Л. Об оптимальной многократной остановке марковских последовательностей. Теория вероятн. и ее примен., 1998, т. 43, вып. 2, с. 374-382.

51. Николаев М.Л. О некоторых задачах оптимальной многократной остановки, допускающих конструктивное решение. Обозрение прикладной и промышленной математики, 1999, т.6, вып. 1, с. 183-184.