Распределение вероятностей экстремумов винеровского случайного процесса

В математической теории вероятностей винеровский процесс , названный в честь Норберта Винера , — это стохастический процесс, используемый при моделировании различных явлений, включая броуновское движение и колебания на финансовых рынках. Формула условного распределения вероятностей экстремума винеровского процесса и схема ее доказательства приведены в работе Х. Дж. Кушера (приложение 3, стр. 106), опубликованной в 1964 году. ^[1] подробное конструктивное доказательство появляется в работе Дарио Баллабио в 1978 году. ^[2] Этот результат был получен в рамках исследовательского проекта по алгоритмам байесовской оптимизации .

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

Предложение

Позволять $X(t)$ быть винеровским случайным процессом на интервале $[a,b]$ с начальной стоимостью $X(a)=X_{a}.$

По определению винеровского процесса приращения имеют нормальное распределение:

{\text{for }}a\leq t_{1}<t_{2}\leq b,\qquad X(t_{2})-X(t_{1})\sim N(0,\sigma ^{2}(t_{2}-t_{1})).

Позволять

F(z)=\Pr(\min _{a\leq t\leq b}X(t)\leq z\mid X(b)=X_{b})

— кумулятивная функция распределения вероятностей минимального значения $X(t)$ функция на интервале $[a,b]$ обусловлено значением $X(b)=X_{b}.$

Показано, что: ^[1]^[3]^{[примечание 1]}

F(z)={\begin{cases}1&{\text{for }}z\geq \min\{X_{a},X_{b}\},\\\exp \left(-2{\dfrac {(z-X_{b})(z-X_{a})}{\sigma ^{2}(b-a)}}\right)&{\text{for }}z<\min(X_{a},X_{b}).\end{cases}}

Конструктивное доказательство

Случай $z\geq \min(X_{a},X_{b})$ является непосредственным следствием минимального определения, в дальнейшем всегда будет считаться $z<\min(X_{a},X_{b})$ а также угловой корпус $\min _{a\leq t\leq b}X(t)=\min(X_{a},X_{b})$ будет исключено.

Давайте предположим $X(t)$ определенный в конечном числе точек $t_{k}\in [a,b],\ \ 0\leq k\leq n,\ \ t_{0}=a$ .

Позволять $T_{n}\ \ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ \{t_{k},\ \ 0\leq k\leq n,\}$ изменяя целое число $n$ быть последовательностью множеств $\{T_{n}\}$ такой, что $T_{n}\subset T_{n+1}$ и $\bigcup _{n=0}^{+\infty }T_{n}$ быть плотным множеством $[a,b]$ ,

следовательно, каждая окрестность каждой точки в $[a,b]$ содержит элемент одного из множеств $T_{n}$ .

Позволять $\Delta z$ быть действительным положительным числом таким, что $z+\Delta z<\min(X_{a},X_{b}).$

Пусть событие $E$ быть определен как: $E\ \ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ (\min _{a\leq t\leq b}X(t)<z+\Delta z)$ $\Longleftrightarrow$ $(\exists \,t\in [a,b]:X(t)<z+\Delta z)$ .

Исключив угловой случай $\min _{a\leq t\leq b}X(t)=\min(X_{a},X_{b})$ , это наверняка $P(E)>0$ .

Позволять $E_{n},\ \ n=0,1,2,\ldots$ быть событиями, определяемыми как: $E_{n}\ \ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ (\exists \,t_{k}\in T_{n}:z<X(t_{k})<z+\Delta z)$ и пусть $\nu$ быть первым k среди $t_{k}\in T_{n}$ которые определяют $E_{n}$ .

С $T_{n}\subset T_{n+1}$ это очевидно $E_{n}\subset E_{n+1}$ . Теперь уравнение (2.1) будет доказано.

(2.1) $\ \ \ \ E=\bigcup _{n=0}^{+\infty }E_{n}$

По $E_{n}$ определение событий, $\forall \,n\ \ E_{n}\Rightarrow E$ , следовательно $\bigcup _{n=0}^{+\infty }E_{n}\subset E$ . Теперь будет проверено соотношение $E\subset \bigcup _{n=0}^{+\infty }E_{n}$ следовательно, (2.1) будет доказано.

Определение $E$ , непрерывность $X(t)$ и гипотеза $z<X_{a}=X(a)$ подразумеваем, согласно теореме о промежуточном значении , $(\exists \,{\bar {t}}\in [a,b]:z<X({\bar {t}})<z+\Delta z)$ .

Благодаря непрерывности $X(t)$ и гипотеза о том, что $\bigcup _{n=0}^{+\infty }T_{n}$ плотный в $[a,b]$ вычитается, что $\exists \,{\bar {n}}$ такой, что для $t_{\nu }\in T_{\bar {n}}$ это должно быть $z<X(t_{\nu })<z+\Delta z$ ,

следовательно $E\subset E_{\bar {n}}\subset \bigcup _{n=0}^{+\infty }E_{n}$ откуда следует (2.1) .

(2.2) $\ \ \ \ P(E)=\lim _{n\rightarrow +\infty }P(E_{n})$

(2.2) вычитаем из (2.1) , учитывая, что $E_{n}\Rightarrow E_{n+1}$ следует, что последовательность вероятностей $P(E_{n})$ монотонно не убывает и , следовательно, сходится к своей верхней границе . Определение событий $E_{n}$ подразумевает $\forall n\ \ P(E_{n})>0\Rightarrow P(E_{n})=P(E_{\nu })$ и (2.2) влечет за собой $P(E)=P(E_{\nu })$ .

В дальнейшем всегда будет предполагаться $n\geq \nu$ , так $t_{\nu }$ хорошо определен.

(2.3) $\ \ \ \ P(X(b)\leqslant -X_{b}+2z)\leqslant P(X(b)-X(t_{\nu })<-X_{b}+z)$

Фактически, по определению $E_{n}$ это $z<X(t_{\nu })$ , так $(X(b)\leqslant -X_{b}+2z)\Rightarrow (X(b)-X(t_{\nu })<-X_{b}+z)$ .

Аналогично, поскольку по определению $E_{n}$ это $z<X(t_{\nu })$ , (2.4) справедливо:

(2.4) $\ \ \ \ P(X(b)-X(t_{\nu })>X_{b}-z)\leqslant P(X(b)>X_{b})$

(2.5) $\ \ \ \ P(X(b)-X(t_{\nu })<-X_{b}+z)=P(X(b)-X(t_{\nu })>X_{b}-z)$

Сказанное выше объясняется тем, что случайная величина $(X(b)-X(t_{\nu }))\thicksim N(\varnothing ;\ \ \sigma ^{2}(b-t_{\nu }))$ имеет симметричную плотность вероятности по сравнению со своим средним значением, которое равно нулю.

Применяя последовательно соотношения (2.3) , (2.5) и (2.4), получаем (2.6) :

(2.6) $\ \ \ \ P(X(b)\leqslant -X_{b}+2z)\leqslant P(X(b)>X_{b})$

Используя ту же процедуру, что и для получения (2.3) , (2.4) и (2.5), воспользовавшись на этот раз соотношением $X(t_{\nu })<z+\Delta z$ получаем (2.7) :

(2.7) $\ \ \ \ P(X(b)>X_{b})\leqslant P(X(b)-X(t_{\nu })>X_{b}-z-\Delta z)\ \$ $=\ \ P(X(b)-X(t_{\nu })<-X_{b}+z+\Delta z)\leqslant P(X(b)<-X_{b}+2z+2\Delta z)$

Применяя последовательно (2.6) и ( 2.7), получаем:

(2.8) $P(X(b)\leqslant -X_{b}+2z)\leqslant P(X(b)>X_{b})$ $\leqslant P(X(b)<-X_{b}+2z+2\Delta z)$

От $X_{b}>z+\Delta z>z$ , учитывая непрерывность $X(t)$ и теорему о промежуточном значении мы получаем $X(b)>X_{b}>z+\Delta z>z\Rightarrow E_{n}$ ,

что подразумевает $P(X(b)>X_{b})=P(E_{n},X(b)>X_{b})$ .

Заменив сказанное выше в (2.8) и перейдя к пределам: $\lim _{n\rightarrow +\ \infty }\ \ E_{n}(\Delta z)\rightarrow E(\Delta z)$ и для $\Delta z\rightarrow 0$ , событие $E(\Delta z)$ сходится к $\min _{a\leq t\leq b}X(t)\leqslant z$

(2.9) $\ \ \ \ P(X(b)\leqslant -X_{b}+2z)=$ $P(\min _{a\leq t\leq b}X(t)\leqslant z,\ \ X(b)>X_{b})$

$\forall \,dX_{b}>0$ , заменив $(X_{b})$ с $(X_{b}-dX_{b})$ в (2.9) получаем эквивалентное соотношение:

(2.10) $\ \ \ \ P(X(b)\leqslant -X_{b}+2z+dX_{b})=$ $P(\min _{a\leq t\leq b}X(t)\leqslant z,\ \ X(b)>X_{b}-dX_{b})$

Применение теоремы Байеса к совместному событию $(\min _{a\leq t\leq b}X(t)\leqslant z,\ \ X_{b}-dX_{b}<X(b)\leqslant X_{b})$

(2.11) $\ \ \ \ P(\min _{a\leq t\leq b}X(t)\leqslant z\mid X_{b}-dX_{b}<X(b)\leqslant X_{b})=$ $P(\min _{a\leq t\leq b}X(t)\leqslant z,\ \ X_{b}-dX_{b}<X(b)\leqslant X_{b})$ $/\ \ P(X_{b}-dX_{b}<X(b)\leqslant X_{b})$

Позволять: $B\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \{X(b)>X_{b}\},\ C\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \{X_{b}-dX_{b}<X(b)\leq X_{b}\},\ D\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \{X(b)>X_{b}-dX_{b}\},\ A\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ \{\min _{a\leq t\leq b}X(t)\leqslant z\}$ Из приведенных определений следует:

$D=B\cup C\Rightarrow \ P(A,D)=P(A,B\cup C)=P(A,B)+P(A,C)\Rightarrow P(A,C)=P(A,D)-P(A,B)$

(2.12) $\ \ \ \ P(A,C)=P(A,D)-P(A,B)$

Подставив (2.12) в (2.11) , получим эквивалент:

(2.13) $P(\min _{a\leq t\leq b}X(t)\leqslant z\mid X_{b}-dX_{b}<X(b)\leqslant X_{b})=(P(\min _{a\leqslant t\leqslant b}X(t)\leq z,\ \ X(b)>X_{b}-dX_{b})-P(\min _{a\leqslant t\leqslant b}X(t)\leq z,\ \ X(b)>X_{b}))\ \ /\ \ P(X_{b}-dX_{b}<X(b)\leqslant X_{b})$

Подставляя (2.9) и (2.10) в (2.13):

(2.14) $\ \ \ \ P(\min _{a\leq t\leq b}X(t)\leqslant z\mid X_{b}-dX_{b}<X(b)\leqslant X_{b})=$ $(P(X(b)\leqslant -X_{b}+2z+dX_{b})-P(X(b)\leqslant -X_{b}+2z)$ $/\ \ P(X_{b}-dX_{b}<X(b)\leqslant X_{b})$

Можно заметить, что во втором члене (2.14) появляется распределение вероятностей случайной величины $X(b)$ , нормальный со средним $X_{a}$ электронная дисперсия $\sigma ^{2}(b-a)$ .

Реализации $X_{b}$ и $-X_{b}+2z$ случайной величины $X(b)$ соответствуют соответственно плотностям вероятности:

(2.15) $\ \ \ \ P(X_{b})\,dX_{b}={\frac {1}{\sigma {\sqrt {2\pi (b-a)}}}}\exp {\biggl (}-{\frac {1}{2}}{\frac {(X_{b}-X_{a})^{2}}{\sigma ^{2}(b-a)}}{\biggr )}\,dX_{b}$

(2.16) $\ \ \ \ P(-X_{b}+2z)\,dX_{b}={\frac {1}{\sigma {\sqrt {2\pi (b-a)}}}}\exp {\biggl (}-{\frac {1}{2}}{\frac {(-X_{b}+2z-X_{a})^{2}}{\sigma ^{2}(b-a)}}{\biggr )}\,dX_{b}$

Подставив (2.15) e (2.16) в (2.14) и приняв предел для $dX_{b}\rightarrow 0$ тезис доказан:

$F(z)=P(\min _{a\leq t\leq b}X(t)\leq z\ \ |\ \ X(b)=X_{b})=$

$={\frac {1}{\sigma {\sqrt {2\pi (b-a)}}}}\exp {\biggl (}-{\frac {1}{2}}{\frac {(-X_{b}+2z-X_{a})^{2}}{\sigma ^{2}(b-a)}}{\biggr )}\,dX_{b}$ $\ \ \diagup \ \ {\frac {1}{\sigma {\sqrt {2\pi (b-a)}}}}\exp {\biggl (}-{\frac {1}{2}}{\frac {(X_{b}-X_{a})^{2}}{\sigma ^{2}(b-a)}}{\biggr )}\,dX_{b}=$

$=\exp {\biggl (}-{\frac {1}{2}}{\frac {(-X_{b}+2z-X_{a})^{2}-(X_{b}-X_{a})^{2}}{\sigma ^{2}(b-a)}}{\biggr )}=$ $\ \ \exp {\biggl (}-2\ \ {\frac {(z-X_{b})(z-X_{a})}{\sigma ^{2}(b-a)}}{\biggr )}$

Библиография

Универсальная стохастическая модель функции неизвестной и изменяющейся во времени формы - Гарольд Дж. Кушнер - Журнал математического анализа и приложений, том 5, выпуск 1, август 1962 г., страницы 150-167.
Применение байесовских методов поиска экстремума - Дж. Мокус, Дж. Тиесис, А. Жилинскас - Конгресс ИФИП, 1977 г., 8–12 августа, Торонто.

См. также

Примечания

^ Теорема, изложенная и показанная для случая минимума винеровского процесса, применима и к максимуму.

Ссылки

^ Jump up to: ^а ^б Х. Дж. Кушнер, «Новый метод определения точки максимума произвольной многопиковой кривой в присутствии шума», J. Basic Eng 86 (1), 97–106 (1 марта 1964 г.).
^ Дарио Баллабио, «Новый класс стохастических алгоритмов для глобальной оптимизации», Миланский университет, Институт математики, докторская диссертация, представленная 12 июля 1978 г., стр. 29–33.
^ Янош Д. Пинтер, Глобальная оптимизация в действии: непрерывная и липшицевая оптимизация, 1996 Springer Science & Business Media , стр. 57.

[4] Теорема, изложенная и показанная для случая минимума винеровского процесса, применима и к максимуму.

[:0-1] Jump up to: ^а ^б Х. Дж. Кушнер, «Новый метод определения точки максимума произвольной многопиковой кривой в присутствии шума», J. Basic Eng 86 (1), 97–106 (1 марта 1964 г.).

[:1-2] Дарио Баллабио, «Новый класс стохастических алгоритмов для глобальной оптимизации», Миланский университет, Институт математики, докторская диссертация, представленная 12 июля 1978 г., стр. 29–33.

[3] Янош Д. Пинтер, Глобальная оптимизация в действии: непрерывная и липшицевая оптимизация, 1996 Springer Science & Business Media , стр. 57.

[1]

[2]

[3]

[примечание 1]