Теория оптимальных правил «многократной остановки»

В конце 40-х — начале 50-х годов в статистическом анализе возникло новое направление — последовательный анализ Вальда. Идея этого подхода оказалась очень плодотворной и на ее основе сформировалась новая ветвь статистики (А.Вальд [1], А. Вальд, Дж. Волфовиц [2] и К.Дж.Арроу, Д. Блекуэлл, М. А. Гиршик [3]). Под влиянием этого направления возникла также и задача оптимальной остановки случайных процессов, сформулированная Дж. Снеллом [4] следующим образом. Пусть на некотором вероятностном пространстве заданы неубывающая последовательность сг-подалгебр С С. С Тп С Т и последовательность ^" &bdquo—измеримых случайных величин Хп = 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, с. 23 129.

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.