Головна   Всі книги

з 2а. Задачі про оптимальну зупинку. Супермартингальная характеризация

Приведена в з 1с супермартингальная характеризация послідовності Y - (У") відносно кожної із заходів сімейства не покажеться несподіваної, якщо операцію взяття ess sup в (12), з 1с, інтерпретувати як оптимизационную задачу вибору "найкращої" ймовірностний міри.

При такому розумінні цікавляча нас супермартингальное властивість є не що інакше, як одне із затверджень широко відомого "принципу оптимальності", якому задовольняє процес-ціна ( "функція Беллмана") в стохастичних оптимизационних задачах.

Окремим випадком таких задач є задача про оптимальну зупинку деякої стохастичної послідовності / = (FN)NПусть / - (fn, 3n)0^n^N - деяка стохастична послідовність на (&п) об ^n^N, Р),&про =

{0, fi}, = Будемо передбачати, що Е¦/"¦Цікавляча нас задача складається: 1) у відшуканні функцій (цін)

VnN= sup Е/т, (1)

де sup береться по класу всіх моментів зупинки г таких, що п ^ г ^ N, і 2) у відшуканні оптимального моменту зупинки (такий в даній ситуації існує).

Задача, що Розглядається зараз про оптимальну зупинку сформульована не в загальному випадку (див. далі п. 4), в якому допускається N - оо (тоді - це клас всіх кінцевих моментів зупинки г Js п), а лише для випадку кінцевого "горизонту" N. Основная причина складається в тому, що цей випадок розбирається порівняно елементарно і, в той же самий час, в цьому випадку "працює" метод індукції назад, що є одним з основних прийомів відшукання і цін, і відповідних оптимальних моментів зупинки.

3. Введемо послідовність = (-fn)об^n^N таким штучним чином:

7n= in,. .

7^ = max(/n, Е(7?+1¦*,)). ^)

Покладемо також для 0 ^ п ^ N

т? = min{п - Гf }-

Наступний результат є одним з центральних в теорії задач про оптимальну зупинку на кінцевому тимчасовому інтервалі 0 ^ nТеорема 1. Послідовність jN = (j^визначений рекурентний співвідношеннями (2), і моменти, 0 ^ п ^ N, володіють наступними властивостями:

т^бЯН?;

Е(/TN І &п) = 7^',

Е (/т І 9п)7п = esssupE(/r І і, зокрема, 7^ = sup Е/т = Е/тлг;

тєші^ гєші^ 0

VnN =

Доказ. Для спрощення запису в цьому доказі і до кінця п. 3 будемо всюди опускати індекс N, означаючи - уп, Vn, оТ", т" замість 7

Властивість (а) виходить з визначення тп. Властивості (Ь) і (з) очевидні для п - N. Дальше будемо міркувати індукцією назад.

Нехай ці властивості вже встановлені для п = N, N- 1,..., до. Покажемо, що тоді вони виконані і для п = до - 1.

Нехай г Є Шк-1 і АЄ Зк-1- Покладемо г = тах (т, до). Ясно, що т Є Шк итогдадля АЄ Зк з урахуванням того, що {т ^ до} Є Зк-1, знаходимо:

= Е [ІАГ\{т=к Іт] + Е [ІАП {т^до}/т]

- Е[^An{r=fe-l}/fe-l] + Е[^n{r^fe}Е(/r ¦^fe-l)]

= Е[lAn{r=k-l}fk-l] +Е [іАП {т > кМШг\Зк)\Зк Е[^n{r=fc-i}A-i] + Е[^n{r > fc}Е(7fe l^fe-i)]

де остання нерівність слідує з (2).][

Тим самим, Е (/т ¦ Зк) ^ 7fe-i- Необхідні твердження (Ь) і (з) будуть встановлені для п = до - 1, якщо показати, що

Ц/тк l^fc-i)][ = 7fc-i- (4)

З цією метою звернемося до ланцюжка нерівностей в (3) і покажемо, що для т = Тк~і насправді в (3) ми маємо всюди рівність.][

Дійсно, на безлічі і ^ fc}, по визначенню Тк, маємо т = Tfc і, оскільки по припущенню індукції Е(/rjt ¦ Зк) = 7fe, то в (3)

= Е ¦/АП {т*_1 =fe-i} /fe-i]

= Е [ІАп {тк_1=к} Ік] + Е[/J4n{1-Jt_1^.fe}Е(7fc І Зк)]

- Е[/A7fe-i] j ¦

де остання рівність виходить з того, що (по визначенню) "fk-i = тах (Д_ь Е(7fe \Зк і = Д на {rfe_i = до - 1}, а на мно

жестве {тк > до - 1} маємо fk-1Итак, твердження (Ь) і (з) доведені, а отже, доведено і твердження (d).)( Нарешті, оскільки для всякого г є із (з)

Е/гто Vk - sup Е/т = Е/TJb -? )(7*;)(, т.)( е.)( має місце твердження (е).)( г€Шк

Зауваження 1.)( В приведеному доказі був використаний той факт, що якщо г Є те момент г = тах (т, до) міститься в Шк.)(

В випадку, що розглядається нами просто передбачається, що клас Шк містить такі моменти.)( В цьому значенні можна сказати, що класи 9Як, до ^ N, є "досить багатими" (См.)( з цього приводу кінець п.)( 1.)

Слідство 1.)( Послідовність 7 = (jn)n^N є супермартингалом.)( При цьому 7 - найменший супермартингал, мажорирующий послідовність f = (fn)n^.N в тому значенні, що якщо 7 = (7") п^лг є також супермартингал і 7" ^ /" для всіх п ^ N, то 7п7n = max(/, "Е(7n+1 ¦ #,)), nс 7jv = fN, то 7пПоложим 7jv - /лг і нехай для п1п = max(/n, Е (7п+1 I ^п)) ¦ (8)

Ясно, що 7n ^ /п для всіх п ^ ЛГ, і 7 = (7n)n^N є супермартингалом.)( Оскільки, по припущенню, 7 = (jn)n^N володіє властивістю минимальности, то

max(/, "Е (7п+1 ¦ &п)) = уп = In- (9)

Тому для пmax(/, "Е (7п+1 ¦ &п)) = уп > 7" > тах (/, "Е (7"+і ¦ Зп)) і для n - N

fN = 7лг ^ 7N > /лг- Отже, 7^ = 7^ = f^, і, в силу (9), для всіх п7» - InТем

самим, кагіменьшгій супермартингал 7 = (jn)n^N, мажорирующий послідовність f - (fn)n^N > задовольняє рівнянням (6) з 7лг = /лг-Слідство

3.)( Момент

Те = min

{0 ^ г ^ N:)( fi = 7^ } є оптимальним моментом зупинки в класі 971^:)(

sup Е/Т=Е/ w (=7^).)( r&Btg 0

4.)( Розглянемо питання про узагальнення теореми 1 на випадок, коли ЛГ - оо.)( Точніше, будемо передбачати, що = - клас всіх тих кінцевих марковских моментів г = т (а > ), для яких т (і > ) ^ п, ш Є Я. Через 2Я* будемо означати клас оTq°. )(

Нехай, далі, / = ( стохастична послідовність, задана на (

V*= sup Е/т, (10)

rean7n

~ ess sup Е(7* = тах (/, "Е (7*+1 \9п))- (13)

Аналогічне, також природно чекати, що момент т*, визначений в (12), є оптимальним моментом в класі 9JI* в тому значенні, що

Уп - sup Е/т = Е/т* (14)

гезет*

V"* = Е7;)(. (15)

В загальній теорії оптимальних правил зупинки, що викладається, наприклад, в [75] і [441], показується, що при певних умовах (але не завжди!) сформульовані результати дійсно мають місце.)(

Посилаючи за подробицями до згаданих монографій, приведемо лише один досить загальний результат в цьому напрямі.)(

Теорема 2.)( Нехай f = (/n,^n)n > про ~ стохастична послідовність з Esup fnп

а) Послідовність 7* = (7^)N^ОС

7* =esssupE(M^") (16)

т€ Ш1*

задовольняє рекурентний співвідношенням

7* = max(/n, Е (7*+11 Зп)) (17)

і, отже, є супермартингалом, мажорирующим послідовність f = (/").)(

Послідовність 7* = (7^) п > 0 є найменшим супермартингалом, мажорирующим послідовність / = (/n)n^оПусть

т* = inf{А;)( ^ п:)( Д = 7^}.)( Тоді, якщо Esup¦/"¦п

Р (*V* = sup Е/т = Е/т», (18)

т€!)(«я;)(

= ess sup Е (Д ¦ 9п) = Е (т- ¦ (19)

гезет;)(

Для кожного п ^ 0 (Р-п.)( н.)

7^ Т 7п (20)

при iV -? 00.)(

5. Як було відмічено вище, у разі кінцевого тимчасового горизонту (NВ випадку ж нескінченного тимчасового горизонту (N = оо) задача відшукання послідовності функцій 7) = (уп) п^про стає більш делікатною, оскільки замість умови в момент часу N доводиться звертатися до додатковим характеризапиям і властивостям цін Vn, п Js 0.

Наприклад, іноді вдається використати при відшуканні потрібного рішення системи рівнянь (17) те міркування, що необхідне рішення повинне бути найменшим рішенням з безлічі всіх рішень.

Техніка рішення задач про оптимальну зупинку найбільш розвинена і просунена в марковском випадку.

Для відповідного викладу передбачимо, що існує однорідний марковский процес X = (хп, Зп, Рх) з дискретним часом п = 0,1,..., фазовим простором станів {Е,? е) і сімейством ймовірностний заходів Рх на = V Для кожного початкового стану х ЄЕ (див., детальніше, [126], [441]).

Нехай Т - оператор переходу за один крок (Т f(х) = Ех/(жі) для вимірних функцій / = f(xі) з Ex¦/(xi)¦Нехай також g = g(х) - деяка ^-вимірна функція, х Є Е.

Як розглянуті раніше функції /п візьмемо функції д (хп), п ^ 0, і нехай Ex[supg_(xn)](21)

s(х) - sup Ехд (хТ), т€Ш*

де Ш* - {г: т (ш) задача, що Розглядається про оптимальну зупинку для марковского процесу X складається у відшуканні функції s(х), оптимальних моментів т* (т. е. таких, що s(х) = 'хд (хг*), х ЄЕ), або е-оптимальних моментів т* (т. е. таких, що s(х) - є ^ Ехд (Хт+), х ЄЕ), якщо такі існують.

Зрозуміло, в чому складається перевага марковской ситуації - в цьому випадку розглянуті вище умовні математичні очікування Ех (- ¦ 3-п) стають такими, що залежать від "минулої історії лише через значення процессавмоментвременип, т. е. тільки від хп. Зокрема, розглянуті вище функції 7", стають лише функціями від хп.

Приведемо марковскую версію теорем 1 і 2, якої далі (в гл. VI) ми будемпользоваться, наприклад, при аналізі опціонів Американського типу.

Теорема 3. Нехай д = д (х) - 38 (Ш)-вимірна функція з Ехд (хь)(22)

SAT (же) = sup ЕХд (хт),

гдеЩУ = {г: 0(23)

Qg(х) = max(g{х), Tg(х))

і.

N

Tq = min

{0Тогда

(a)

(25)

SN(X) = QNg{Х);

SN(X) = max(g(х), TsN-I(х)), (26)

де s0(х) =g(х);

в класі ЗЯд^ марковский момент т^ є оптимальним-.

Е x9[xTn) = sn(х), х? е\ (27)

послідовність -yN = З 7m = SN-m(Xm) утворить супер мартингал при кожному N ^ 0.

Доказ цієї теореми і її узагальнень дається у другому розділі монографії [441], присвяченому "марковскому підходу" до задач про оптимальну зупинку. Її можна, звісно, вивести і як окремий випадок з доведеної вище теореми 1, за винятком хіба лише того, що все одно доведеться окремо дослідити структуру операторів Qg(х) і їх ітерацій Qng(х). (См. з цього приводу детальніше за з 2.2 в [441].).

З результатів приведеної теореми витікає наступна інтерпретація структури оптимальних моментів зупинки в класі = {г: 0 ^ г ^ N} для фіксованого NПусть

= {х-.sN-n(х)=g(х)}, Об^n^N, (28)

з»=e\d". (29)

Відповідно до теореми 3 оптимальний момент т^ може бути записаний у вигляді

r0N =min

{0Иначе говорячи, послідовність областей DQ, -Df,..., = Е утворить послідовність областей зупинки спостережень, а послідовність областей Сд^, З^,..., Cjy = 0 утворить послідовність областей продовження спостережень.

Помітимо, що

dg З d? З - - ¦ З d% = е

і

З? 2 З? 2 - ¦ - 2 З# - 0.

Тому, якщо хо Є Dq, то спостереження не здійснюються і т^ = 0. Якщо ж XQ є CQ, то проводиться Спостереження і якщо XI Є DF, то відбувається зупинка спостережень; а якщо х± є те здійснюється наступне спостереження і т. д. У заключний (термінальний) момент часу N спостереження явно закінчується (в цьому випадку Djy = Е).

Зауваження 2. З теореми 1 слідує, що в якісному відношенні мало що зміниться, якщо замість ціни sлг (я), визначуваної формулою (21), розглядати ціни "з дисконтуванням і платою за спостереження":

(21')

sjv(х) - sup Еа

Ртд (хг) - 5Zc(xfe_i)

fc=1

(якщо т = 0, то вираження у [ - ] вважається рівним д (х); 0Формула (25) зберігає свою силу з

Qg(х) = max(g(х), /ЗТд (же) - з (х)). (23')

Реккуррентное рівняння (26) прийме наступний вигляд:

SJV(х) = max(g(х),/3Tsjv-i(х) - з (х)) (26')

з so (же) = 9ІХ) - Детальніше див. [441; гл. II].

Приклад 1. Нехай є = (еі, Є2,-¦ ¦) ~ бернуллиевские величини з

Р (Єі = 1) = Р (Єі = -1) =

Нехай хп = х + (єі Н 1-? "), х ЄЕ =

{0, ±1,... } і

SN(X) = sup EX/3Txr. тєалгу

Якщо /3 = 1, то Qg(х) = д (х) для д (х) = х при всіх х ЄЕ і як оптимальний момент зупинки можна взяти момент т^ = 0.

Якщо ж 0(Якщо xn Є {-1, -2,... } при всіх 0Заметим, що у випадку 0SN(х) t х+ = max(0, х), Nоо.

6. Звернемося тепер до задачі про оптимальну зупинку у разі нескінченного горизонту (N = оо). Покладемо

s(х) = sup ЕХд {хг), (31)

ТЄ9Л*

де 9Я* = {т: 0Для формулюючі соответствуюшей теореми відносно структури ціни s - s(х), х ЄЕ, і оптимальних (або е-оптимальних) моментів зупинки доцільно нагадати наступне

Визначення (див., наприклад, [441]). Функція / - /(ж) з Ех¦/(жі)¦f{х) > Tf(х) (32)

називається жсцессивной функцією для однорідного марковского процесу X = (хп, Зп, Рх) п > 0, х Є Е.

Якщо, до того ж, /(же) ^ д (х), то функція / = /(ж) називається жсцес-сивной мажорантой функциид = д (х).

Зрозуміло, що якщо функція / = /(ж) є ексцессивнаямажоранта функ- пії д = д {же), те

f(х) > max(g(х), Tf(х)). (33)

Наступна теорема розкриває роль ексцессивних мажорант в задачах про оптимальну зупинку однорідних марковских процесів

X = (хп, Зп, Рх) п^про, х? Нехай функція д = д (х) така, що Ех ¦^supg~(a;)(n)Jцена s - s(же) є найменшою жсцессивной мажорантой функції g - g(же);

ценаз (х)= lim Qng(х) (- lim sn(х)) і задовольняє уравп

-+оо \ п-юо /

(34)

s(х) - max(g(х), Ts(х));

нению (ср. з (33))

якщо Ех ^sup ¦^(х")¦J0 момент

т* =inf{n > 0: s(xn) ^д {хп) + є} (35)

є є-оптимальним, т. е.

а (х)-єпусть Ех ¦sup ¦т* = inf{n ^ 0: s(xn) = з (х")},

т. е. т* - Tq; якщо Рж ((х) = БірЕх (¦жг¦ - ст), (38)

де sup береться по тих моментах зупинки т, для яких ЕхтЕхж2 =х2 + Е хТ (39)

і, значить,

ЕХ (До¦ - ст) = сх2 + Ех (¦жг¦ - е¦жг¦2). (40)

Тому

s(a:) = сх2 + sup Е Хд (хг),

де д (х) - ¦же¦ - е¦ж¦2 і sup береться по тим т, для яких ЕхтПоськольку функція д (же) досягає максимального значення при

1 1 х = ± -, те у разі цілочисельних - бачимо, що

s(х) ^сх2 + ~. (41)

Визначимо момент тс = inf¦n: ¦х"¦ = Якщо ¦ж¦,, 1

\хТс \^ - - -2 _ ".2

(2 з)

^ ExX\TcAN) =хг + Ех (тс ЛN).

Звідси граничним переходом по ЛГ - > оо (по теоремі про монотонну збіжність) знаходимо, що Ехтсиз якого слідує, що якщо ¦ж¦ ^ -, те насправді Ехтс = ~ '

Оскільки для гс і ¦х¦ ^ -

Ех (¦хТс¦ - стс) = 1 - - х2) = з*2 + і,

то з (41) бачимо, що момент тс є ^для всіх тих х, для яких ¦х¦ ^ - ^ оптимальним моментом зупинки. ЗАДАЧІ, ТЕСТИ І ВПРАВИ: На які три основні методи спирається статистичне дослідження?:  ЗАДАЧІ, ТЕСТИ І ВПРАВИ: На які три основні методи спирається статистичне дослідження? Метод спостереження, метод показників, метод експерименту. Б. Метод спостереження, метод угруповань, метод показників. Метод угруповань, метод показників, метод зведення. Хто був
ЗАДАЧІ, ТЕСТИ І ВПРАВИ: Проведіть первинний контент-аналіз приведеного в «Задачах, тестах і:  ЗАДАЧІ, ТЕСТИ І ВПРАВИ: Проведіть первинний контент-аналіз приведеного в «Задачах, тестах і вправах» четвертого розділу уривка з роботи П. Кроссера. Керуйтеся наступним методом: виділіть основні смислові одиниці даного тексту: а) поняття; б) дієслова; в)
ЗАДАЧІ, ТЕСТИ І ВПРАВИ: У 1962 р. в СРСР була видана робота американського економіста Пауля:  ЗАДАЧІ, ТЕСТИ І ВПРАВИ: У 1962 р. в СРСР була видана робота американського економіста Пауля Кроссера "Економічні фікції ", присвячена критиці економістів так званої суб'єктивістської школи (К. Менгера, Е. Бем-Баверка, Дж. Б. Кларка і т. п.)[162]. Робота П. Кроссера не
8.6. Задачі по темі «Валютна система РФ і міжнародна кредитна:  8.6. Задачі по темі «Валютна система РФ і міжнародна кредитна система»: Задача 1. Визначте курсову різницю і результат від операції, якщо клієнт хоче обміняти:. долари на рублі;. евро на рублі. Сума, яку хоче обміняти клієнт, становить 140 000. Ціна продажу і ціна купівлі повинні бути взяті по сьогоднішньому
7.5. Задачі по темі «Фінанси підприємств різних форм власності»:  7.5. Задачі по темі «Фінанси підприємств різних форм власності»: Задача 1. Визначте майбутню вартість капіталу компанії, якщо її первинний капітал становить 10 млн крб., вкладений на 5 років і процентна ставка банку становить 7% річних. 3адача2. Визначте суму первинного внеску капіталу компанії,
Задачі реформування управління державними і муніципальними:  Задачі реформування управління державними і муніципальними фінансами: Реформування державних і муніципальних фінансів в 2006-2008 роках в Кемеровської області здійснювалося згідно: - Концепції підвищення ефективності межбюджетних відносин, якості управління державними і муніципальними фінансами в
6.8. Задачі і приклади: Позика в розмірі 380 млн. крб. видана на квартал (чверть року) під:  6.8. Задачі і приклади: Позика в розмірі 380 млн. крб. видана на квартал (чверть року) під 36 річних простих відсотків. При видачі позики втримані комісійні в розмірі 5% від суми позики. Визначте внутрішню норму прибутковості для кредитора у вигляді річної ставки складних