Rozkład prawdopodobieństwa punktów ekstremalnych procesu stochastycznego Wienera

W matematycznej teorii prawdopodobieństwa proces Wienera , nazwany na cześć Norberta Wienera , jest procesem stochastycznym stosowanym w modelowaniu różnych zjawisk, w tym ruchów Browna i wahań na rynkach finansowych. Wzór na warunkowy rozkład prawdopodobieństwa ekstremum procesu Wienera oraz szkic jego dowodu pojawia się w pracy HJ Kushera (dodatek 3, strona 106) opublikowanej w 1964 r. Szczegółowy konstruktywny dowód pojawia się w pracy Dario Ballabio w 1978 r. Wynik ten został opracowany w ramach projektu badawczego pt optymalizacji bayesowskiej .

W niektórych problemach optymalizacji globalnej analityczna definicja funkcji celu jest nieznana i możliwe jest uzyskanie wartości jedynie w ustalonych punktach. Istnieją funkcje celu, w których koszt oceny jest bardzo wysoki, np. gdy ocena jest wynikiem eksperymentu lub szczególnie uciążliwego pomiaru. W takich przypadkach poszukiwanie ekstremum globalnego (maksymalnego lub minimalnego) można przeprowadzić przy użyciu metodologii zwanej „ optymalizacją Bayesa ”, która dąży do uzyskania a priori najlepszego możliwego wyniku przy określonej liczbie ocen. Reasumując, zakłada się, że poza punktami, w których została już oceniona, funkcja celu ma wzór, który można przedstawić za pomocą procesu stochastycznego o odpowiednich charakterystykach. Za model funkcji celu przyjmuje się proces stochastyczny, zakładając, że rozkład prawdopodobieństwa jego ekstremów najlepiej wskazuje na ekstrema funkcji celu. W najprostszym przypadku optymalizacji jednowymiarowej, zakładając, że funkcja celu została oceniona w wielu punktach, pojawia się problem wyboru, w którym z tak wyodrębnionych przedziałów bardziej nadaje się do dalszej oceny. Jeżeli jako model funkcji celu zostanie wybrany proces stochastyczny Wienera, możliwe jest obliczenie rozkładu prawdopodobieństwa ekstremalnych punktów modelu w każdym przedziale, uwarunkowanych znanymi wartościami na granicach przedziałów. Porównanie uzyskanych rozkładów stanowi kryterium wyboru przedziału, w jakim proces powinien być iterowany. Jako kryterium zatrzymania można zastosować wartość prawdopodobieństwa zidentyfikowania przedziału, w którym przypada globalne ekstremum funkcji celu. Optymalizacja bayesowska nie jest skuteczną metodą dokładnego wyszukiwania ekstremów lokalnych, dlatego po ograniczeniu zakresu poszukiwań, w zależności od charakterystyki problemu, można zastosować konkretną metodę optymalizacji lokalnej.

Propozycja

Niech będzie procesem stochastycznym $displaystyle$ na przedziale $, b]}$ ${\ displaystyle X (a) = X_ {a}.}$ wartości początkowej

Z definicji procesu Wienera przyrosty mają rozkład normalny:

{\ Displaystyle {\ tekst {dla}} a \ równoważnik t_ {1} t_ {2} \ równoważnik b, \ qquad X (t_ {2}) -X (t_ {1}) \ sim N (0, \ sigma ^{2}(t_{2}-t_{1})).}

Pozwalać

{\ Displaystyle F (z) = \ Pr (\ min _ {a \ równoważnik t \ równoważnik b } X(t)\równoważnik z\mid X(b)=X_{b})}

będzie funkcją skumulowanego rozkładu prawdopodobieństwa minimalnej wartości funkcji na przedziale $[a, b]}$ $\ displaystyle$ ${\ displaystyle X (b) = X_ {b}.}$ uwarunkowanej wartością

Pokazano, że:

{\ Displaystyle F (z) = {\ początek {przypadków} 1 i {\ tekst {dla}} z \ geq \ min \ {X_ {a}, X_ {b} \}, \\\exp \ lewo (-2 {\dfrac {(z-X_{b})(z-X_{a})}{\sigma ^{2}(ba)}}\right)&{\text{for }}z<\min(X_ {a},X_{b}).\end{cases}}}

Konstruktywny dowód

Przypadek ${\ Displaystyle z \ geq \ min (X_ {a}, X_ {b})}$ jest bezpośrednią konsekwencją minimalnej definicji, w dalszej części zawsze będzie zakładane ${\ Displaystyle z <\ min (X_ {a}, X_ {b})}$ i także obudowa narożna ${\ Displaystyle \ min _ {a \ równoważnik t \ równoważnik b} X (t) = \ min (X_ {a}, X_ {b})} zostaną wykluczone$ .

Załóżmy, że zdefiniowano w skończonej liczbie punktów. $t$ ${\ displaystyle t_ {k} \ w [ X ( t ) {\ displaystyle$ .

Niech $\ Displaystyle T_ {n} \ \ {\ overset {\ underset {\ operatorname {def}} }} {=}} \ \ \ { t_ {k}, \ \ 0 \ równoważnik k \ równoważnik n, \}}$ poprzez zmianę liczby całkowitej będącej sekwencją zbiorów takich jak $\ displaystyle n$ ${n} \}}$ że ${\ Displaystyle T_ {n} \ podzbiór T_ {n+1}}$ i ${\ Displaystyle \ bigcup _ {n = 0} ^ {+ \ infty} T_ {n}}$ być zbiorem gęstym w ${\ displaystyle [a, b]$ }

$stąd$ każde otoczenie każdego $_$ . _

Niech $,$ liczbą rzeczywistą dodatnią, taką ${\ Displaystyle z + \ Delta z <\ min (X_ {a}, X_ {b}).}$

Niech zdarzenie zostanie zdefiniowane jako: $z$ $displaystyle E \ \ {\ overset {\ underset {\$ ${$ ${\ Displaystyle (\ istnieje \, t \ w [a, b]: X (t) <z + \ Delta z)}$ .

Po wykluczeniu przypadku narożnego ${\ Displaystyle \ min _ {a \ równoważnik t \ równoważnik b} X (t) = \ min (X_ {a} , X_ {b})}$ , to z pewnością ${\ displaystyle P (E)> 0}$ .

Niech ${\ displaystyle E_ {n}, \ \ n = 0,1,2, \ ldots}$ będą zdarzeniami zdefiniowanymi jako: ${\ Displaystyle E_ {n} \ \ {\ overset {\ underset {\ operatorname {def}} }} {=}} \ \ (\ istnieje \, t_ {k} \ w T_ {n}: z <X (t_{k})<z + \ Delta z)}$ i $niech$ będzie pierwszym k spośród $},$ które definiują $displaystyle E_ {n}}$ \

Ponieważ ${n+1$ ewidentne ${\ Displaystyle T_ {n}$ . Teraz zostanie udowodnione równanie (2.1) .

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

Według definicji zdarzeń, $mi$ ${\ Displaystyle \ bigcup _ {n = 0} ^ {+ \ infty} E_ {n} \ podzbiór E}$ n $displaystyle$ . Teraz zostanie zweryfikowana relacja ${\ displaystyle E \ podzbiór \ bigcup _ {n = 0} ^ {+ \ infty} E_ {n}}$ stąd (2.1) zostanie udowodnione.

Definicja , ciągłość i hipoteza $X (a) mi {\ displaystyle E} )}$ ${\ Displaystyle z$ $=$ wynika z twierdzenia o wartości pośredniej , ${\ Displaystyle (\ istnieje \, {\ bar {t}} \ w [a, b]: z <X ({\ bar {t}}) <z + \ Delta z)}$ .

Przez ciągłość i hipotezę, że $\ displaystyle \ bigcup _ {$ ⋃ $+ \ infty} T_ {n}}$ gęsty w ${\ displaystyle [a, b]}$ wywnioskowuje się, że dla ${\ displaystyle \ istnieje \, {\ bar {n}}}$ musi być $z <X (t_ {\ nu}) <z +$ $( t ν )$ ,

stąd ${\ displaystyle E \ podzbiór E _ {\ bar {n}} \ podzbiór \ bigcup _ {n = 0} ^ {+ \ infty} E_ {n}$ } implikuje (2.1) .

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

(2.2) odejmuje się od $displaystyle E_ {$ 2.1) , biorąc pod uwagę, że oznacza, że sekwencja prawdopodobieństw jest ${n+1}}$ jest monotoniczny i nie maleje, a zatem zbiega się do supremumu . Definicja $_$ implikuje ${\ Displaystyle \ forall n \ \ P (E_ {n})> 0 \ Strzałka w prawo P (E_ {n}) = P (E _ {\ nu}) }$ i (2.2) implikuje ${\ displaystyle P (E) = P (E _ {\ nu})}$ .

$W$ $dobrze$ zakłada się że zdefiniowane.

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

$X$ rzeczywistości z definicji jest to $}$ { ${\ Displaystyle (X (b) \ leqslant -X_ {b} + 2z) \ Strzałka w prawo (X (b) -X (t_ {\ nu}) <-X_ {b} + z)}$ .

$\ displaystyle$ definicji (2,4 prawidłowe n $n}$ E_

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

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

Powyższe wyjaśnia fakt, że zmienna losowa ${\ Displaystyle (X (b) -X (t_ { \nu }))\thicksim N(\varnothing ;\ \ \sigma ^{2}(b-t_{\nu }))}$ ma symetryczną gęstość prawdopodobieństwa w porównaniu ze swoją średnią, która wynosi zero.

Stosując w sekwencji zależności (2.3) , (2.5) i (2.4) otrzymujemy (2.6) :

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

Przy tej samej procedurze stosowanej do uzyskania (2.3) , (2.4) i (2.5) wykorzystując ten czas przez zależność. ${\ displaystyle X (t _ {\ nu}) <z + \ Delta z}$ otrzymujemy (2.7) :

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

Stosując kolejno (2.6) i ( 2.7) otrzymujemy:

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

pod uwagę ciągłość i twierdzenie o wartości pośredniej , otrzymujemy $z$ ${\ displaystyle X_ {$ ${\ Displaystyle X (b)> X_ {b}> z + \ Delta z> z \ Strzałka w prawo E_ {n}}$ ,

co oznacza ${\ Displaystyle P (X (b)> X_ {b}) = P (E_ {n}, X (b)>X_{b})}$ .

Zastąpienie powyższego w (2.8) i przejście do granic: ${\ displaystyle \ lim _ {n \rightarrow + \ \ infty } \ \ E_ {n } (\ Delta z) \rightarrow E (\ Delta z)}$ i dla ${\ Displaystyle \ Delta z \rightarrow 0}$ , zdarzenie mi $\ Displaystyle E (\ Delta z)}$ zbiega się do ${\ Displaystyle \ min _ {a \ równoważnik t \ równoważnik b} X (t) \ leqslant z}$

(2,9) ${\ Displaystyle \ \ \ \ P (X (b) \ leqslant -X_ {b} + 2z) =}$ ${\ Displaystyle P (\ min _ {a \ równoważnik t \ równoważnik b} X (t) \ leqslant z, \ \ X (b)> X_ { B})}$

${\ Displaystyle \ forall \, dX_ {b}> 0}$ , zastępując ${\ Displaystyle (X_ {b})}$ za ${\ Displaystyle (X_ {b}-dX_{b})}$ w (2.9) otrzymujemy równoważną zależność:

(2.10) ${\ Displaystyle \ \ \ \ P (X (b) \ leqslant -X_ {b} + 2z + dX_ {b}) =}$ ${\ Displaystyle P (\ min _ {a \ równoważnik t \ równoważnik b} X (t) \ leqslant z, \ \ X (b)> X_ {b} -dX_ {b})}$

Zastosowanie twierdzenia Bayesa do wspólnego zdarzenia ${\ displaystyle (\ min _ {a \ równoważnik t \leq b}X(t)\leqslant z,\ \ X_{b}-dX_{b}X(b)\leqslant X_{b})}$

(2.11) ${\ displaystyle \ \ \ \ P (\ min _ {a \ równoważnik t\leq b}X(t)\leqslant z\mid X_{b}-dX_{b}X(b)\leqslant X_{b})=}$ ${\ Displaystyle P (\ min _ {a \ równoważnik t \ równoważnik b} X (t) \ leqslant z, \ \ X_ {b} - dX_ {b} X (b) \ leqslant X_ {b})}$ ${\ Displaystyle /\ \ P (X_ {b} -dX_ { b<X(b)\leqslant X_{b})}$

Niech: ${\ Displaystyle B \ {\ overset {\ underset {\ operatorname {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\równoważnik t\równoważnik b}X(t)\ leqslant z\}}$ Z powyższych definicji wynika:

${\ Displaystyle D = B \ Puchar C \ Strzałka w prawo \ P (A, D) = P (A, B \ Puchar C) = P (A, B) + P (A, C) \ Strzałka w prawo P (A ,C)=P(A,D)-P(A,B)}$

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

Podstawiając (2.12) do (2.11) otrzymujemy odpowiednik:

(2.13) ${\ Displaystyle P (\ min _ {a \ równoważnik t \ równoważnik b} X (t) \ leqslant z \ środek 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 })}$

Podstawiając (2.9) i (2.10) do (2.13):

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

Można zaobserwować, że w drugim członie ${\ Displaystyle \ sigma ^ {2} (ba)}$ 2.14) pojawia się rozkład prawdopodobieństwa zmiennej losowej , normalny ze średnią e wariancją $X_ {a$ $displaystyle$ } .

Realizacje zmiennej losowej i $+ 2z}$ $displaystyle -X_ {b$ $}}$ odpowiednio prawdopodobieństwu gęstości:

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

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

Podstawiając (2.15) e (2.16) do (2.14) i biorąc granicę dla tezy zostaje udowodniona: ${\ displaystyle dX_ {b} \rightarrow 0}$

${\ Displaystyle F (z) = P (\ min _ {a \ równoważnik t \ równoważnik b } X(t)\równoważnik z\ \ |\ \ X(b)=X_{b})=}$

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

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

Bibliografia

Wszechstronny model stochastyczny funkcji o nieznanej i zmieniającej się w czasie postaci - Harold J. Kushner - Journal of Mathematical Analysis and Applications, tom 5, wydanie 1, sierpień 1962, strony 150-167.
Zastosowanie metod bayesowskich do poszukiwania ekstremum - J. Mockus, J. Tiesis, A. Zilinskas - Kongres IFIP 1977, 8–12 sierpnia Toronto.

Zobacz też

Notatki

^ ^a ^b HJ Kushner, „Nowa metoda lokalizowania maksymalnego punktu arbitralnej krzywej wieloszczytowej w obecności szumu”, J. Basic Eng 86 (1), 97–106 (01 marca 1964).
^ Dario Ballabio, „Una nuova classe di algoritmi stocastici per l'ottimizzazione globale” (Nowa klasa algorytmów stochastycznych do optymalizacji globalnej), Uniwersytet w Mediolanie, Instytut Matematyki, rozprawa doktorska przedstawiona 12 lipca 1978, s. 29–33 .
^ János D. Pintér, Global Optimization in Action: Continuous and Lipschitz Optimization, 1996 Springer Science & Business Media , strona 57.

[:0-1] HJ Kushner, „Nowa metoda lokalizowania maksymalnego punktu arbitralnej krzywej wieloszczytowej w obecności szumu”, J. Basic Eng 86 (1), 97–106 (01 marca 1964).

[:1-2] Dario Ballabio, „Una nuova classe di algoritmi stocastici per l'ottimizzazione globale” (Nowa klasa algorytmów stochastycznych do optymalizacji globalnej), Uniwersytet w Mediolanie, Instytut Matematyki, rozprawa doktorska przedstawiona 12 lipca 1978, s. 29–33 .

[3] János D. Pintér, Global Optimization in Action: Continuous and Lipschitz Optimization, 1996 Springer Science & Business Media , strona 57.