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

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

Определение

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

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

1. Последовательность случайных величин $X_1,X_2,\dots$, чьё совместное распределение предполагается известным.
2. Последовательность «вознаграждающих» функций $(y_i{)}_{i\ge 1}$ которые зависят от наблюдаемых значений случайных величин в 1:

   $y_i=y_i(x_1,\dots ,x_i)$

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

• Вы, соблюдая последовательность случайных величин, на каждом шаге $i$ можете выбрать прекратить или продолжить наблюдение.
• Если вы прекратите наблюдать на шаге $i$, вы получите награду $y_i$.
• Вам нужно выбрать правило остановки, чтобы максимизировать предполагаемое вознаграждение (или, что эквивалентно, минимизировать ожидаемую потерю).

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

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

$V_t^T=𝔼G_{{\tau }^{*}}=\underset{t\le \tau \le T}{\sup }𝔼G_{\tau }$

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

Более конкретная формулировка выглядит следующим образом. Мы рассматриваем адаптированный сильный Марковский процесс $X=(X_t{)}_{t\ge 0}$, определённый на фильтрованном вероятностном пространстве $(\mathrm{\Omega },ℱ,({ℱ}_t{)}_{t\ge 0},{\mathbb{P}}_x)$, где ${\mathbb{P}}_x$ обозначает вероятностную меру, при которой случайный процесс начинается с $x$. Учитывая непрерывные функции $M,L$ и $K$, задача оптимальной остановки:

$V(x)=\underset{0\le \tau \le T}{\sup }{𝔼}_x(M(X_{\tau })+\underset{0}{\overset{\tau }{\int }}L(X_t)dt+\underset{0\le t\le \tau }{\sup }K(X_t)).$

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

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

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

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

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

Пусть $Y_t$ будет диффузия Леви в ${ℝ}^k$ из стохастического дифференциального уравнения

$d{Y}_t=b(Y_t)dt+\sigma (Y_t)d{B}_t+\underset{{ℝ}^k}{\int }\gamma (Y_{t-},z)\overline{N}(dt,dz),Y_0=y$

где $B$ — $m$-мерное Броуновское движение, $\overline{N}$ это $l$-мерная компенсированная случайная мера Пуассона, $b:{ℝ}^k\to {ℝ}^k$, $\sigma :{ℝ}^k\to {ℝ}^{k\times m}$, и $\gamma :{ℝ}^k\times {ℝ}^k\to {ℝ}^{k\times l}$ заданы такие функции, что существует единственное решение $(Y_t)$. Пусть $𝒮\subset {ℝ}^k$ будет открытым множеством (область платежеспособности) и

${\tau }_{𝒮}=\inf \{t>0:Y_t\notin 𝒮\}$

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

$V(y)=\underset{\tau \le {\tau }_{𝒮}}{\sup }{J}^{\tau }(y)=\underset{\tau \le {\tau }_{𝒮}}{\sup }{𝔼}_y[M(Y_{\tau })+\underset{0}{\overset{\tau }{\int }}L(Y_t)dt].$

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

Если функция $\varphi :\overline{𝒮}\to ℝ$ удовлетворяет

• $\varphi \in C(\overline{𝒮})\cap C^1(𝒮)\cap C^2(𝒮\setminus \partial D)$ где область продолжения $D=\{y\in 𝒮:\varphi (y)>M(y)\}$,
• $\varphi \ge M$ на $𝒮$, и
• $𝒜\varphi +L\le 0$ на $𝒮\setminus \partial D$, где $𝒜$ — бесконечно малый генератор $(Y_t)$

тогда $\varphi (y)\ge V(y)$ для всех $y\in \overline{𝒮}$. Кроме того, если

• $𝒜\varphi +L=0$ на $D$

Тогда $\varphi (y)=V(y)$ для всех $y\in \overline{𝒮}$ и ${\tau }^{*}=\inf \{t>0:Y_t\notin D\}$ — оптимальный момент остановки.

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

• $\max \{𝒜\varphi +L,M-\varphi \}=0$ на $𝒮\setminus \partial D.$

Примеры

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

(Пример, где $𝔼(y_i)$ сходится)

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

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

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

и если

$y_i=\frac{1}{i}\sum _{k=1}^i{X}_k$

тогда последовательности $(X_i{)}_{i\ge 1}$ и $(y_i{)}_{i\ge 1}$ являются объектами, связанными с этой проблемой.

Продажа дома

(Пример, где $𝔼(y_i)$ не обязательно сходится)

У вас есть дом, и вы хотите продать его. Каждый день вам предлагают $X_n$ за ваш дом, и платите $k$, чтобы продолжать рекламировать его. Если вы продадите ваш дом в день $n$, вы заработаете $y_n$, где $y_n=(X_n-nk)$.

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

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

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

Шаблон:Main (Пример, где $(X_i)$ — это конечная последовательность)

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

Здесь, если $R_1,\dots ,R_n$ (n - некоторое большое число) — ранги объектов, и $y_i$ — это шанс, что вы выберете лучший объект, если прекратите намеренно отбрасывать объекты на шаге i, то $(R_i)$ и $(y_i)$ — последовательности, связанные с этой проблемой. Эта задача была решена в начале 1960-х годов. Изящное решение задачи секретаря и несколько модификаций этой задачи обеспечивают более современный алгоритм оптимальной остановки (алгоритм Брюса).

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

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

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

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

$S_t=S_0\exp \{(r-\delta -\frac{{\sigma }^2}{2})t+\sigma B_t\}$

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

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

$V(x)=\underset{\tau }{\sup }{𝔼}_x[e^{-r\tau }g(S_{\tau })]$,

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

$\max \{\frac{1}{2}{\sigma }^2{x}^2{V}^{″}(x)+(r-\delta )x{V}^{\prime }(x)-rV(x),g(x)-V(x)\}=0$

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

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

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

См. также

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