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

Определение

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

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

1. Последовательность случайных величин ${\displaystyle X_{1},X_{2},\ldots }$, чье совместное распределение предполагается известным
2. Последовательность «вознаграждающих» функций ${\displaystyle (y_{i})_{i\geq 1}}$ которые зависят от наблюдаемых значений случайных величин в 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).}$

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

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

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

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

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

Пусть ${\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}$-мерное компенсированная пуассоновская случайная мера, ${\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].}$

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

Если функция ${\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 \geq M}$ на ${\displaystyle {\mathcal {S}}}$ и
• ${\displaystyle {\mathcal {A}}\phi +L\leq 0}$ на ${\displaystyle {\mathcal {S}}\setminus \partial D}$, где ${\displaystyle {\mathcal {A}}}$ - бесконечно малый генератор из ${\displaystyle (Y_{t})}$

тогда ${\displaystyle \phi (y)\geq 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\}}$ - момент остановки

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

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

Примеры

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

(Например, где ${\displaystyle \mathbb {E} (y_{i})}$ сходится)

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

Вы хотите, чтобы сумма, которую бы вам заплатили, была бы максимальной, выбирая правило остановки. Если х_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)^{+}}$ для опциона вызова и ${\displaystyle g(x)=(K-x)^{+}}$ для опциона ставки. Вариационное неравенство

${\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}$ это граница физических упражнений. Решение известно^[3]

• (Бесконечный вызов) ${\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).}$

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

См. также

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

Ссылки