Марковский момент

В математике теория момента остановки или марковский момент времени связана с проблемой выбора времени, чтобы принять определённое действие, для того чтобы максимизировать ожидаемое вознаграждение или минимизировать ожидаемые затраты. Проблема момента остановки может быть найдена в области статистики, экономики и финансовой математики (связанные с ценообразованием на американские опционы). Самым ярким примером, относящимся к моменту остановки, является Задача о разборчивой невесте. Проблема момента остановки часто может быть написана в форме уравнения Беллмана и поэтому часто решается с помощью динамического программирования.

Определение

Случай с дискретным временем

Как правило, проблема момента остановки связана с двумя объектами:

Последовательность случайных величин [math]\displaystyle{ X_1, X_2, \ldots }[/math], чье совместное распределение предполагается известным
Последовательность «вознаграждающих» функций [math]\displaystyle{ (y_i)_{i\ge 1} }[/math] которые зависят от наблюдаемых значений случайных величин в 1.:
[math]\displaystyle{ y_i=y_i (x_1, \ldots ,x_i) }[/math]

С учетом этих объектов, проблема заключается в следующем:

Вы, соблюдая последовательность случайных величин, на каждом [math]\displaystyle{ i }[/math] можете выбрать либо прекратить наблюдение либо продолжить
Если вы прекратите наблюдать на [math]\displaystyle{ i }[/math], вы получите награду [math]\displaystyle{ y_i }[/math]
Вы хотите выбрать правило остановки, чтобы максимизировать предполагаемое вознаграждение (или, что эквивалентно, минимизации ожидаемых потерь)

Случай непрерывного времени

Рассмотрим усиление процессов [math]\displaystyle{ G=(G_t)_{t\ge 0} }[/math] определёнными на фильтрованном вероятностном пространстве [math]\displaystyle{ (\Omega,\mathcal{F},(\mathcal{F}_t)_{t\ge 0},\mathbb{P}) }[/math] и предположим, что [math]\displaystyle{ G }[/math] это адаптирование фильтрации. Задача момента остановки состоит в том, чтобы найти время остановки [math]\displaystyle{ \tau^* }[/math] которое максимизирует ожидаемый выигрыш

[math]\displaystyle{ V_t^T = \mathbb{E} G_{\tau^*} = \sup_{t\le \tau \le T} \mathbb{E} G_\tau }[/math]

где [math]\displaystyle{ V_t^T }[/math] называется значением функции. Здесь [math]\displaystyle{ T }[/math] может иметь значение [math]\displaystyle{ \infty }[/math].

Более конкретная формулировка выглядит следующим образом. Мы считаем, адаптированный сильный Марковский процесс [math]\displaystyle{ X = (X_t)_{t\ge 0} }[/math] определённый на фильтрованном вероятностном пространстве [math]\displaystyle{ (\Omega,\mathcal{F},(\mathcal{F}_t)_{t\ge 0},\mathbb{P}_x) }[/math] где [math]\displaystyle{ \mathbb{P}_x }[/math] обозначает вероятность измерения, где случайный процесс начинается с [math]\displaystyle{ x }[/math]. С учетом непрерывных функций [math]\displaystyle{ M,L }[/math] и [math]\displaystyle{ K }[/math] в задаче момента остановки

[math]\displaystyle{ V(x) = \sup_{0\le \tau \le T} \mathbb{E}_x \left( M(X_\tau) + \int_0^\tau L(X_t) dt + \sup_{0\le t\le\tau} K(X_t) \right). }[/math]

Иногда это называется МЛС (Майер, Лагранж и супремум, соответственно) формулировка.^[1]

Методы решения

Есть два подхода к решению проблемы момента остановки. Когда основной процесс (или усиление процесса) описывается своим безусловным конечномерным распределением, тогда соответствующий метод решения — подход Мартингала, названный так потому, что он использует теорию Мартингала, наиболее важным понятием является разработка Снелла. В дискретном случае, если горизонт планирования [math]\displaystyle{ T }[/math] конечен, проблема может быть легко решена с помощью динамического программирования.

Когда основной процесс определяется семейством (условных) функций переходов приводящих к Марковскому семейству вероятностных переходов, часто могут быть использованы мощные аналитические инструменты теории Марковских процессов и такой подход называется Марковским методом. Решение обычно получается решения ассоциированных задач со свободными границами (Стефан проблемы).

Результат диффузии прыжка

Пусть [math]\displaystyle{ Y_t }[/math] будет диффузия Леви в [math]\displaystyle{ \mathbb{R}^k }[/math] из стохастического дифференциального уравнения

[math]\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 }[/math]

где [math]\displaystyle{ B }[/math] — [math]\displaystyle{ m }[/math]-мерное Броуновское движение, [math]\displaystyle{ \bar{N} }[/math] это [math]\displaystyle{ l }[/math]-мерное компенсированная пуассоновская случайная мера, [math]\displaystyle{ b:\mathbb{R}^k \to \mathbb{R}^k }[/math], [math]\displaystyle{ \sigma:\mathbb{R}^k \to \mathbb{R}^{k\times m} }[/math], и [math]\displaystyle{ \gamma:\mathbb{R}^k \times \mathbb{R}^k \to \mathbb{R}^{k\times l} }[/math] заданы такие функции, что единственное решение [math]\displaystyle{ (Y_t) }[/math] существует. Пусть [math]\displaystyle{ \mathcal{S}\subset \mathbb{R}^k }[/math] будет открытым множеством (область платежеспособности) и

[math]\displaystyle{ \tau_\mathcal{S} = \inf\{ t\gt 0: Y_t \notin \mathcal{S} \} }[/math]

время банкротства. Задача оптимальной остановки:

[math]\displaystyle{ V(y) = \sup_{\tau \le \tau_\mathcal{S}} J^\tau (y) = \sup_{\tau \le \tau_\mathcal{S}} \mathbb{E}_y \left[ M(Y_\tau) + \int_0^\tau L(Y_t) dt \right]. }[/math]

Получается, что при некоторых условиях регулярности,^[2] следующая проверка теоремы содержит:

Если функция [math]\displaystyle{ \phi:\bar{\mathcal{S}}\to \mathbb{R} }[/math] удовлетворяет

[math]\displaystyle{ \phi \in C(\bar{\mathcal{S}}) \cap C^1(\mathcal{S}) \cap C^2(\mathcal{S}\setminus \partial D) }[/math] где области являются продолжением [math]\displaystyle{ D = \{y\in\mathcal{S}: \phi(y) \gt M(y) \} }[/math],
[math]\displaystyle{ \phi \ge M }[/math] на [math]\displaystyle{ \mathcal{S} }[/math] и
[math]\displaystyle{ \mathcal{A}\phi + L \le 0 }[/math] на [math]\displaystyle{ \mathcal{S} \setminus \partial D }[/math], где [math]\displaystyle{ \mathcal{A} }[/math] — бесконечно малый генератор из [math]\displaystyle{ (Y_t) }[/math]

тогда [math]\displaystyle{ \phi(y) \ge V(y) }[/math] для всех [math]\displaystyle{ y\in \bar{\mathcal{S}} }[/math]. Кроме того, если

[math]\displaystyle{ \mathcal{A}\phi + L = 0 }[/math] на [math]\displaystyle{ D }[/math]

Тогда [math]\displaystyle{ \phi(y) = V(y) }[/math] для всех [math]\displaystyle{ y\in \bar{\mathcal{S}} }[/math] и [math]\displaystyle{ \tau^* = \inf\{ t\gt 0: Y_t\notin D\} }[/math] — момент остановки

Эти условия могут быть записаны в более компактной форме (интегро-вариационного неравенства):

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

Примеры

Подбрасывание монетки

(Например, где [math]\displaystyle{ \mathbb{E}(y_i) }[/math] сходится)

У вас есть монета и вы её неоднократно бросаете. Каждый раз, перед тем, как её бросить, вы можете прекратить бросать её и получать деньги (в долларах, скажем), за средним числом наблюдаемых головок.

Вы хотите, чтобы сумма, которую бы вам заплатили, была бы максимальной, выбирая правило остановки. Если х_i (где i ≥ 1) образует последовательность независимых, одинаково распределенных случайных величин с распределением Бернулли

[math]\displaystyle{ \text{Bern}\left(\frac{1}{2}\right), }[/math]

и если

[math]\displaystyle{ y_i = \frac 1 i \sum_{k=1}^{i} X_k }[/math]

тогда в последовательности [math]\displaystyle{ (X_i)_{i\geq 1} }[/math] и [math]\displaystyle{ (y_i)_{i\geq 1} }[/math] будут объекты, связанные с этой проблемой.

Продажа дома

(Например, где [math]\displaystyle{ \mathbb{E}(y_i) }[/math] не обязательно сходится)

У вас есть дом и вы хотели бы продать его. Каждый день вам предлагают [math]\displaystyle{ X_n }[/math] за ваш дом, и платить [math]\displaystyle{ k }[/math] для продолжения рекламы. Если вы продаете ваш дом в день [math]\displaystyle{ n }[/math], вы заработаете [math]\displaystyle{ y_n }[/math], где [math]\displaystyle{ y_n = (X_n - nk) }[/math].

Вы хотите максимизировать сумму, которую вы зарабатываете, выбирая правило остановки.

В этом примере последовательности ([math]\displaystyle{ X_i }[/math]) является последовательностью предложений за ваш дом, а последовательность «вознаграждений» функций определяет, сколько вы будете зарабатывать.

Задача о разборчивой невесте

(Например, где [math]\displaystyle{ (X_i) }[/math] — это конечная последовательность)

Вы наблюдаете последовательность объектов, которые могут быть отсортированы от лучшего к худшему. Вы хотите выбрать правило остановки, которое максимизирует ваши шансы на выбор лучшего объекта.

К примеру, если [math]\displaystyle{ R_1, \ldots, R_n }[/math] (n - это некоторое большое число, возможно) — ранги объектов, и [math]\displaystyle{ y_i }[/math] это шанс, что вы выберете лучший объект, если вы остановите намеренное отклонение объектов на этапе i, то [math]\displaystyle{ (R_i) }[/math] и [math]\displaystyle{ (y_i) }[/math] являются последовательности, связанные с этой проблемой. Эта проблема была решена в начале 1960-х годов несколько человек. Изящное решение проблемы секретаря и несколько модификаций этой проблемы обеспечивается более современным алгоритмом оптимальной остановки (алгоритм Брюса).

Теория поиска

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

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

В торговле опционами на финансовых рынках, держатель американского опциона может осуществлять право купить (или продать) базовый актив по определённой цене в любое время до или в момент истечения срока. Таким образом, оценка американских опционов, по сути, проблема оптимальной остановки. Рассмотрим классическую модель Блэка-Шоулза и пусть [math]\displaystyle{ r }[/math] будет безрисковой процентной ставкой [math]\displaystyle{ \delta }[/math] и [math]\displaystyle{ \sigma }[/math] ставка дивидендов и непостоянство акции. Цена акций [math]\displaystyle{ S }[/math] следует следует за геометрическим броуновским движением

[math]\displaystyle{ S_t = S_0 \exp\left\{ \left(r - \delta - \frac{\sigma^2}{2}\right) t + \sigma B_t \right\} }[/math]

В соответствии с мерой риска.

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

[math]\displaystyle{ V(x) = \sup_{\tau} \mathbb{E}_x \left[ e^{-r\tau} g(S_\tau) \right] }[/math]

где функция выигрыша [math]\displaystyle{ g(x) = (x-K)^+ }[/math] для опциона вызова и [math]\displaystyle{ g(x) = (K-x)^+ }[/math] для опциона ставки. Вариационное неравенство

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

для всех [math]\displaystyle{ x \in (0,\infty)\setminus \{b\} }[/math] где [math]\displaystyle{ b }[/math] это граница физических упражнений. Решение известно^[3]

(Бесконечный вызов) [math]\displaystyle{ V(x) = \begin{cases} (b-K)(x/b)^\gamma & x\in(0,b) \\ x-K & x\in[b,\infty) \end{cases} }[/math] где [math]\displaystyle{ \gamma = (\sqrt{\nu^2 + 2r} - \nu) / \sigma }[/math] и [math]\displaystyle{ \nu = (r-\delta)/\sigma - \sigma / 2, \quad b = \gamma K / (\gamma - 1). }[/math]
(Бесконечная ставка) [math]\displaystyle{ V(x) = \begin{cases} K - x & x\in(0,c] \\(K-c)(x/c)^\tilde{\gamma} & x\in(c,\infty) \end{cases} }[/math] где [math]\displaystyle{ \tilde{\gamma} = -(\sqrt{\nu^2 + 2r} + \nu) / \sigma }[/math] и [math]\displaystyle{ \nu = (r-\delta)/\sigma - \sigma / 2, \quad c = \tilde{\gamma} K / (\tilde{\gamma} - 1). }[/math]

С другой стороны, когда конечный срок действия конечен, задача связана с двумерной задачей о свободной границе без известного решения замкнутой формы. Однако могут быть использованы различные численные методы. См. Модель Black-Scholes # Американские опционы для различных методов оценки здесь, а также Fugit для дискретного дерева на основе расчета оптимального времени для тренировки.

См. также

Стохастическое управление
Марковский процесс принятия решений

Ссылки

↑ Peskir, Goran; Shiryaev, Albert (англ.) (рус.. Optimal Stopping and Free-Boundary Problems (неопр.). — 2006. — Т. Lectures in Mathematics. ETH Zürich. — ISBN 978-3-7643-2419-3. — doi:10.1007/978-3-7643-7390-0.
↑ Øksendal, B. (англ.) (рус.; Sulem, A. S. Applied Stochastic Control of Jump Diffusions (неопр.). — 2007. — ISBN 978-3-540-69825-8. — doi:10.1007/978-3-540-69826-5.
↑ Karatzas, Ioannis; Shreve, Steven E. (англ.) (рус.. Methods of Mathematical Finance (неопр.). — 1998. — Т. 39. — ISBN 978-0-387-94839-3. — doi:10.1007/b98840.

[opt2006-1] Peskir, Goran; Shiryaev, Albert (англ.) (рус.. Optimal Stopping and Free-Boundary Problems (неопр.). — 2006. — Т. Lectures in Mathematics. ETH Zürich. — ISBN 978-3-7643-2419-3. — doi:10.1007/978-3-7643-7390-0.

[oksendal2007-2] Øksendal, B. (англ.) (рус.; Sulem, A. S. Applied Stochastic Control of Jump Diffusions (неопр.). — 2007. — ISBN 978-3-540-69825-8. — doi:10.1007/978-3-540-69826-5.

[karatzas1998-3] Karatzas, Ioannis; Shreve, Steven E. (англ.) (рус.. Methods of Mathematical Finance (неопр.). — 1998. — Т. 39. — ISBN 978-0-387-94839-3. — doi:10.1007/b98840.

[1]

[2]

[3]