Оптимальна зупинка

У математиці теорія оптимальної зупинки або ранньої зупинки пов'язана з задачею вибору часу для здійснення певної дії, щоб максимізувати очікувану винагороду або мінімізувати очікувані витрати. Проблеми оптимальної зупинки можна знайти в областях статистики, економіки та фінансової математики (які пов'язані із ціноутворенням американських опціонів). Ключовим прикладом задачі оптимальної зупинки є задача про перебірливу наречену (в англомовній літературі зустрічається також під назвою задача про секретаря). Проблеми оптимальної зупинки часто можна записати у формі рівняння Беллмана, і тому їх часто розв'язують за допомогою динамічного програмування.

Визначення

Випадок безперервного часу

Задачі з правилом зупинки пов'язані з двома об'єктами:

1. Послідовність випадкових величин ${\displaystyle X_{1},X_{2},\ldots }$, спільний розподіл яких вважається відомим
2. Послідовність функцій «винагороди». ${\displaystyle (y_{i})_{i\geq 1}}$ які залежать від спостережуваних значень випадкових величин:

   ${\displaystyle y_{i}=y_{i}(x_{1},\ldots ,x_{i})}$

Грунтуючись на інформації про ці об'єкти, задача полягає в наступному:

• Ви спостерігаєте за послідовністю випадкових величин, причому на кожному кроці ${\displaystyle i}$, ви можете припинити спостереження або продовжити
• Якщо ви припините спостереження на кроці ${\displaystyle i}$, ви отримаєте винагороду ${\displaystyle y_{i}}$
• Ви хочете вивести правило зупинки, щоб максимізувати очікувану винагороду (або, що еквівалентно, мінімізувати очікувані втрати)

Випадок дискретного часу

Розглянемо процес посилення ${\displaystyle G=(G_{t})_{t\geq 0}}$ визначений у відфільтрованому ймовірнісному просторі ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )}$ і припустимо, що ${\displaystyle G}$ пристосований до фільтрації. Оптимальна задача зупинки полягає в знаходженні часу зупинки ${\displaystyle \tau ^{*}}$, що максимізує очікуваний прибуток

${\displaystyle V_{t}^{T}=\mathbb {E} G_{\tau ^{*}}=\sup _{t\leq \tau \leq T}\mathbb {E} G_{\tau }}$

де ${\displaystyle V_{t}^{T}}$ називається функцією цінності (${\displaystyle T}$ може мати значення ${\displaystyle \infty }$).

Більш конкретне формулювання виглядає наступним чином. Ми розглядаємо адаптований сильний марковський ланцюг ${\displaystyle X=(X_{t})_{t\geq 0}}$ визначений у відфільтрованому ймовірнісному просторі ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})}$, де ${\displaystyle \mathbb {P} _{x}}$ позначає міру ймовірності, з якої починається випадковий процес ${\displaystyle x}$. Задані неперервні функції ${\displaystyle M,L}$, і ${\displaystyle K}$, оптимальна задача зупинки це

${\displaystyle V(x)=\sup _{0\leq \tau \leq T}\mathbb {E} _{x}\left(M(X_{\tau })+\int _{0}^{\tau }L(X_{t})dt+\sup _{0\leq t\leq \tau }K(X_{t})\right).}$

Ще інколи називають формулою MLS (що розшифровується як Mayer, Lagrange and supremum відповідно).

Методи вирішення

Загалом існує два підходи до вирішення задачі оптимальної зупинки. Коли основний процес (або процес посилення) описується безумовними кінцевовимірними розподілами, відповідним методом вирішення є мартингальний підхід, який називається так тому, що він використовує мартингальну теорію, найважливішою концепцією якої є ^[en]. У випадку дискретного часу, якщо горизонт планування ${\displaystyle T}$ скінченний, задачу також можна легко вирішити за допомогою динамічного програмування.

Коли основний процес визначається сімейством (умовних) функцій переходу, що веде до марковського сімейства ймовірностей переходу, часто можна використовувати потужні аналітичні інструменти, надані теорією марковських процесів, і цей підхід називають методом Маркова. Розв'язок зазвичай отримують розв'язуванням пов'язаних ^[en] (^[en]).

Результат дифузії стрибка

Нехай ${\displaystyle Y_{t}}$ буде дифузією Леві в ${\displaystyle \mathbb {R} ^{k}}$, яка описується СДР

${\displaystyle dY_{t}=b(Y_{t})dt+\sigma (Y_{t})dB_{t}+\int _{\mathbb {R} ^{k}}\gamma (Y_{t-},z){\bar {N}}(dt,dz),\quad Y_{0}=y}$

де ${\displaystyle B}$ є ${\displaystyle m}$-мірний броунівський рух, ${\displaystyle {\bar {N}}}$ є ${\displaystyle l}$-вимірна компенсована ^[en], ${\displaystyle b:\mathbb {R} ^{k}\to \mathbb {R} ^{k}}$, ${\displaystyle \sigma :\mathbb {R} ^{k}\to \mathbb {R} ^{k\times m}}$, і ${\displaystyle \gamma :\mathbb {R} ^{k}\times \mathbb {R} ^{k}\to \mathbb {R} ^{k\times l}}$ - задані функції такі, що існує єдиний розв'язок ${\displaystyle (Y_{t})}$. Нехай ${\displaystyle {\mathcal {S}}\subset \mathbb {R} ^{k}}$ буде відкритою множиною (областю платоспроможності) і

${\displaystyle \tau _{\mathcal {S}}=\inf\{t>0:Y_{t}\notin {\mathcal {S}}\}}$

буде часом банкрутства. Оптимальна задача зупинки:

${\displaystyle V(y)=\sup _{\tau \leq \tau _{\mathcal {S}}}J^{\tau }(y)=\sup _{\tau \leq \tau _{\mathcal {S}}}\mathbb {E} _{y}\left[M(Y_{\tau })+\int _{0}^{\tau }L(Y_{t})dt\right].}$

Виявляється, що за деяких умов регулярності справедлива перевірочна теорема: Якщо функція ${\displaystyle \phi :{\bar {\mathcal {S}}}\to \mathbb {R} }$ задовольняє

• ${\displaystyle \phi \in C({\bar {\mathcal {S}}})\cap C^{1}({\mathcal {S}})\cap C^{2}({\mathcal {S}}\setminus \partial D)}$, де область продовження це ${\displaystyle D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}}$,
• ${\displaystyle \phi \geqslant M}$ на ${\displaystyle {\mathcal {S}}}$, і
• ${\displaystyle {\mathcal {A}}\phi +L\leqslant 0}$ на ${\displaystyle {\mathcal {S}}\setminus \partial D}$, де ${\displaystyle {\mathcal {A}}}$ є ^[en] ${\displaystyle (Y_{t})}$,

то ${\displaystyle \phi (y)\geqslant V(y)}$ для усіх ${\displaystyle y\in {\bar {\mathcal {S}}}}$. Крім того, якщо

• ${\displaystyle {\mathcal {A}}\phi +L=0}$ на ${\displaystyle D}$

Тоді ${\displaystyle \phi (y)=V(y)}$ для усіх ${\displaystyle y\in {\bar {\mathcal {S}}}}$ і ${\displaystyle \tau ^{*}=\inf\{t>0:Y_{t}\notin D\}}$ — це оптимальний час зупинки.

Ці умови також можна записати в більш компактній формі (^[en]):

• ${\displaystyle \max \left\{{\mathcal {A}}\phi +L,M-\phi \right\}=0}$ на ${\displaystyle {\mathcal {S}}\setminus \partial D.}$

Приклади

Підкидання монети

(Приклад, де ${\displaystyle \mathbb {E} (y_{i})}$ сходиться)

У вас є «чесна» монета, і ви постійно її підкидаєте. Кожного разу, перш ніж її підкинути, ви можете зупинити її підкидання та отримати виплату (скажімо, у гривнах) за середню кількість спостережених орлів.

Ви хочете максимізувати суму, яку вам платять, вибравши правило зупинки. Якщо X_i (для i ≥ 1) утворює послідовність незалежних, однаково розподілених випадкових величин із розподілом Бернуллі

${\displaystyle {\text{Bern}}\left({\frac {1}{2}}\right),}$

і якщо

${\displaystyle y_{i}={\frac {1}{i}}\sum _{k=1}^{i}X_{k}}$

тоді послідовності ${\displaystyle (X_{i})_{i\geq 1}}$, і ${\displaystyle (y_{i})_{i\geq 1}}$ — це об'єкти, пов'язані з цією задачею.

Продаж будинку

(Приклад, де ${\displaystyle \mathbb {E} (y_{i})}$ не обов'язково сходиться)

У вас є будинок і ви хочете його продати. Кожен день вам пропонують ${\displaystyle X_{n}}$ за ваш будинок, і ви платите ${\displaystyle k}$ продовжуючи рекламу будинку. Якщо ви продаєте свій будинок в день ${\displaystyle n}$, ви заробите ${\displaystyle y_{n}}$, де ${\displaystyle y_{n}=(X_{n}-nk)}$.

Ви хочете максимізувати зароблену суму, вибравши правило зупинки.

У цьому прикладі послідовність (${\displaystyle X_{i}}$) — це послідовність пропозицій для вашого будинку, а послідовність функцій винагород — це те, скільки ви заробите.

Задача про перебірливу наречену

Докладніше: Задача про перебірливу наречену

(Приклад де ${\displaystyle (X_{i})}$ є скінченною послідовністю)

Ви спостерігаєте за послідовністю об'єктів, які можна ранжувати від найкращого до найгіршого. Ви хочете вибрати правило зупинки, яке максимізує ваші шанси вибрати найкращий об'єкт.

Ось, якщо ${\displaystyle R_{1},\ldots ,R_{n}}$ (n — деяке велике число) — ранги об'єктів, і ${\displaystyle y_{i}}$ — це ймовірність вибору найкращого об'єкта, якщо ви припините навмисно відхиляти об'єкти на кроці i ${\displaystyle (R_{i})}$ і ${\displaystyle (y_{i})}$ — це послідовності, пов'язані з цією задачею. Ця задача була розв'язана на початку 1960-х років кількома людьми. Елегантне розв'язання задачі про перебірливу наречену та кілька модифікацій цієї задачі забезпечує більш сучасний алгоритм шансів (алгоритм Брюса).

Теорія пошуку

Економісти досліджували низку проблем оптимальної зупинки, подібних до «задач про перебірливу наречену», і зазвичай називають цей тип аналізу «теорією пошуку». Теорія пошуку особливо зосереджена на пошуку працівником високооплачуваної роботи або пошуку споживачем недорогого товару.

Проблема паркування

Особливим прикладом застосування теорії пошуку є задача оптимального вибору паркувального місця водієм, який прямує в оперу (театр, шопінг тощо). Наближаючись до пункту призначення, водій їде вулицею, вздовж якої є паркувальні місця — зазвичай вільними є лише деякі місця на парковці. Ціль добре видно, тому відстань до цілі оцінюється легко. Завдання водія — вибрати вільне місце для паркування якомога ближче до пункту призначення, не їздячи по колу, щоб відстань від цього місця до місця призначення була найменшою.

Торгівля опціонами

Під час торгівлі опціонами на фінансових ринках власнику американського опціону дозволяється скористатися правом купити (або продати) базовий актив за заздалегідь визначеною ціною в будь-який час до або на дату закінчення терміну дії. Таким чином, оцінка американських опціонів є, по суті, проблемою оптимальної зупинки. Розглянемо класичну модель Блека — Шоулза і дозволимо ${\displaystyle r}$ бути безризиковою процентною ставкою та ${\displaystyle \delta }$ і ${\displaystyle \sigma }$ — це ставка дивідендів і волатильність акцій. Ціна акцій ${\displaystyle S}$ підпорядковується геометричному броунівському руху

${\displaystyle S_{t}=S_{0}\exp \left\{\left(r-\delta -{\frac {\sigma ^{2}}{2}}\right)t+\sigma B_{t}\right\}}$

за нейтральною до ризику мірою.

Коли опція безстрокова, проблема оптимальної зупинки є

${\displaystyle V(x)=\sup _{\tau }\mathbb {E} _{x}\left[e^{-r\tau }g(S_{\tau })\right],}$

де функція виплати ${\displaystyle g(x)=(x-K)^{+}}$ для опції call (далі «колл») і ${\displaystyle g(x)=(K-x)^{+}}$ для put-опціону (далі «пут»). Варіаційна нерівність є

${\displaystyle \max \left\{{\frac {1}{2}}\sigma ^{2}x^{2}V''(x)+(r-\delta )xV'(x)-rV(x),g(x)-V(x)\right\}=0}$

для усіх ${\displaystyle x\in (0,\infty )\setminus \{b\}}$, де ${\displaystyle b}$ є межею вправи. Відомо, що розв'язок

• (Вічний колл) ${\displaystyle V(x)={\begin{cases}(b-K)(x/b)^{\gamma }&x\in (0,b)\\x-K&x\in [b,\infty )\end{cases}}}$ де ${\displaystyle \gamma =({\sqrt {\nu ^{2}+2r}}-\nu )/\sigma }$ і ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad b=\gamma K/(\gamma -1).}$
• (Вічний пут) ${\displaystyle V(x)={\begin{cases}K-x&x\in (0,c]\\(K-c)(x/c)^{\tilde {\gamma }}&x\in (c,\infty )\end{cases}}}$ де ${\displaystyle {\tilde {\gamma }}=-({\sqrt {\nu ^{2}+2r}}+\nu )/\sigma }$ і ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad c={\tilde {\gamma }}K/({\tilde {\gamma }}-1).}$

З іншого боку, коли термін придатності обмежений, задача пов'язана з двовимірною задачею з вільними границями, яка не має відомого розв'язку в замкненому вигляді. Однак можна застосувати різні чисельні методи. Див. модель Блека–Шоулза для різних методів оцінки, а також ^[en] для дискретного розрахунку оптимального часу для тренування ^[en].

Див. також

• Проблема зупинки
• Марковський процес вирішування
• ^[en]
• ^[en]
• ^[en]

Список літератури

Цитування

1. Chow, Y.S.; ; Siegmund, D. (1971). Great Expectations: The Theory of Optimal Stopping. Boston: .
2. (2007). Optimal Stopping and Applications. UCLA.
3. (2009). Knowing When to Stop. American Scientist. 97 (2): 126—133. doi:10.1511/2009.77.126. ISSN 1545-2786.
4. Peskir, Goran; (2006). Optimal Stopping and Free-Boundary Problems. Lectures in Mathematics. ETH Zürich. doi:10.1007/978-3-7643-7390-0. ISBN .
5. Øksendal, B.; (2007). Applied Stochastic Control of Jump Diffusions. doi:10.1007/978-3-540-69826-5. ISBN .
6. MacQueen, J.; Miller Jr., R.G. (1960). Optimal persistence policies. . 8 (3): 362—380. doi:10.1287/opre.8.3.362. ISSN 0030-364X.
7. Karatzas, Ioannis; (1998). Methods of Mathematical Finance. Stochastic Modelling and Applied Probability. Т. 39. doi:10.1007/b98840. ISBN .

Джерела

• , Optimal Stopping and Applications, retrieved on 21 June 2007
• , «Who solved the secretary problem?» Statistical Science, Vol. 4.,282–296, (1989)
• . «Sum the odds to one and stop.» Annals of Probability, Vol. 28, 1384—1391,(2000)
• F. Thomas Bruss. «The art of a right decision: Why decision makers want to know the odds-algorithm.» , Issue 62, 14–20, (2006)
• Rogerson, R.; Shimer, R.; Wright, R. (2005). Search-theoretic models of the labor market: a survey (PDF). . 43 (4): 959—88. doi:10.1257/002205105775362014. JSTOR 4129380.