Distribuzione di probabilità dei punti estremanti di un processo stocastico di Wiener

In alcuni problemi di ottimizzazione globale non è nota una definizione analitica della funzione obiettivo ed è solo possibile una sua valutazione in punti prefissati. Vi sono funzioni obiettivo in cui il costo di una valutazione è molto alto, come ad esempio avviene se la valutazione è il risultato di un esperimento o di una misurazione particolarmente onerosa. In questi casi la ricerca degli estremanti globali (massimi o minimi) deve essere effettuata con metodi denominati di “ottimizzazione bayesiana”, che tendono a ottenere il miglior risultato a priori possibile con un numero prefissato di valutazioni. In sintesi si ipotizza che al di fuori dei punti in cui la funzione è già stata valutata, questa abbia un andamento che può essere rappresentato da un processo stocastico con opportune caratteristiche. Il processo stocastico viene assunto come modello della funzione obiettivo, ipotizzando che la distribuzione di probabilità dei suoi punti estremanti dia la migliore indicazione a priori sui valori dei punti estremanti della funzione obiettivo. Nel caso più semplice della ottimizzazione unidimensionale, posto che la funzione obiettivo sia stata valutata in un certo numero di punti, si pone il problema di scegliere in quali degli intervalli così individuati sia più opportuno investire per l'effettuazione di una nuova valutazione. Se come modello della funzione obiettivo si è scelto un processo stocastico di Wiener, è possibile calcolare la distribuzione di probabilità dei punti estremanti del modello all’ interno di ciascun intervallo, condizionata dai valori noti assunti ai suoi estremi. Il confronto delle distribuzioni ottenute offre un criterio per la scelta dell'intervallo in cui iterare il procedimento. Un valore scelto a priori di probabilità di avere individuato un intervallo in cui cade il punto estremante globale della funzione obiettivo può fungere da criterio di arresto. L'ottimizzazione bayesiana non è un metodo efficiente per la ricerca precisa di estremanti locali per cui, una volta ristretto l'intervallo di ricerca, a seconda delle caratteristiche del problema si procede, se necessario, con metodi specifici per l'ottimizzazione locale.

La formula della distribuzione con un abbozzo di dimostrazione è indicata nell'articolo di H.J. Kushner (appendix 3, pagina 106) pubblicato nel 1964^[1], la dimostrazione costruttiva dettagliata è ripresa da^[2] , sviluppata nel contesto della ricerca nel campo degli algoritmi di ottimizzazione bayesiana.

Sia la funzione reale di variabile reale ${\displaystyle X(t)}$ definita sull'intervallo ${\displaystyle [a,b]}$ un processo stocastico di Wiener e sia inoltre ${\displaystyle X(a)=X_{a}.}$

Per le proprietà dei processi di Wiener, gli incrementi hanno distribuzione normale: ${\displaystyle a\leq t_{1}<t_{2}\leq b\ \ \Rightarrow }$ ${\displaystyle X(t_{2})-X(t_{1})\thicksim N(0;\ \ \sigma ^{2}(t_{2}-t_{1}))}$

Sia ${\displaystyle F(z)=P(\min _{a\leq t\leq b}X(t)\leq z\ \ |\ \ X(b)=X_{b})}$ la distribuzione di probabilità del valore minimo della funzione ${\displaystyle X(t)}$ nell'intervallo ${\displaystyle [a,b]}$ condizionata dal valore ${\displaystyle X(b)=X_{b}}$ .

Si dimostra che ^[1][2][3]:

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

Il caso ${\displaystyle z\geq \min(X_{a},X_{b})}$ è immediata conseguenza della definizione di minimo, nel seguito si supporrà sempre ${\displaystyle z<\min(X_{a},X_{b})}$ e si escluderà il caso limite ${\displaystyle \min _{a\leq t\leq b}X(t)=\min(X_{a},X_{b})}$.

Si consideri ${\displaystyle X(t)}$ definita in un numero finito di punti ${\displaystyle t_{k}\in [a,b],\ \ 0\leq k\leq n,\ \ t_{0}=a}$.

Posto ${\displaystyle T_{n}\ \ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ \{t_{k},\ \ 0\leq k\leq n,\}}$ al variare di ${\displaystyle n}$ la successione di insiemi ${\displaystyle \{T_{n}\}}$ sia tale che ${\displaystyle T_{n}\subset T_{n+1}}$ e che ${\displaystyle \bigcup _{n=0}^{+\infty }T_{n}}$ sia un insieme denso in ${\displaystyle [a,b]}$,

per cui ogni intorno di ogni punto di ${\displaystyle [a,b]}$ contiene un elemento di uno degli insiemi ${\displaystyle T_{n}}$.

Sia ${\displaystyle \Delta z}$ un numero reale positivo tale che ${\displaystyle z+\Delta z<\min(X_{a},X_{b}).}$

Sia ${\displaystyle E}$ l'evento così definito: ${\displaystyle E\ \ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ (\min _{a\leq t\leq b}X(t)<z+\Delta z)}$ ${\displaystyle \Longleftrightarrow }$ ${\displaystyle (\exists \,t\in [a,b]:X(t)<z+\Delta z)}$ .

Avendo escluso il caso limite${\displaystyle \min _{a\leq t\leq b}X(t)=\min(X_{a},X_{b})}$ è sicuramente ${\displaystyle P(E)>0}$.

Siano ${\displaystyle E_{n},\ \ n=0,1,2,\ldots }$ gli eventi così definiti: ${\displaystyle E_{n}\ \ {\overset {\underset {\mathrm {def} }{}}{=}}\ \ (\exists \,t_{k}\in T_{n}:z<X(t_{k})<z+\Delta z)}$ e sia ${\displaystyle \nu }$ il primo k fra i ${\displaystyle t_{k}\in T_{n}}$ che definiscono ${\displaystyle E_{n}}$.

dato che ${\displaystyle T_{n}\subset T_{n+1}}$ è evidentemente ${\displaystyle E_{n}\subset E_{n+1}}$. Si dimostrerà ora la (2.1):

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

Dalla definizione degli eventi ${\displaystyle E_{n}}$, ${\displaystyle \forall \,n\ \ E_{n}\Rightarrow E}$, per cui ${\displaystyle \bigcup _{n=0}^{+\infty }E_{n}\subset E}$ . Si verificherà ora che vale anche la relazione ${\displaystyle E\subset \bigcup _{n=0}^{+\infty }E_{n}}$ per cui resterà provata la (2.1).

La definizione di ${\displaystyle E}$, la continuità di ${\displaystyle X(t)}$ e l'ipotesi ${\displaystyle z<X_{a}=X(a)}$ implicano, per il teorema dei valori intermedi, ${\displaystyle (\exists \,{\bar {t}}\in [a,b]:z<X({\bar {t}})<z+\Delta z)}$.

Dalla continuità di ${\displaystyle X(t)}$ e dall'ipotesi che ${\displaystyle \bigcup _{n=0}^{+\infty }T_{n}}$ sia denso in ${\displaystyle [a,b]}$ si deduce che ${\displaystyle \exists \,{\bar {n}}}$ tale che per ${\displaystyle t_{\nu }\in T_{\bar {n}}}$ risulti ${\displaystyle z<X(t_{\nu })<z+\Delta z}$ ,

quindi ${\displaystyle E\subset E_{\bar {n}}\subset \bigcup _{n=0}^{+\infty }E_{n}}$ da cui la (2.1).

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

La (2.2) si deduce dalla (2.1) considerando che ${\displaystyle E_{n}\Rightarrow E_{n+1}}$, per cui la successione delle probabilità ${\displaystyle P(E_{n})}$ è monotona non decrescente e quindi converge al suo estremo superiore. Per la definizione degli eventi ${\displaystyle E_{n}}$, ${\displaystyle \forall n\ \ P(E_{n})>0\Rightarrow P(E_{n})=P(E_{\nu })}$ e per la (2.2) ${\displaystyle P(E)=P(E_{\nu })}$.

Nel seguito si assume sempre ${\displaystyle n\geq \nu }$, per cui ${\displaystyle t_{\nu }}$è ben definito.

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

Infatti dato che per definizione di ${\displaystyle E_{n}}$ è ${\displaystyle z<X(t_{\nu })}$, vale la relazione ${\displaystyle (X(b)\leqslant -X_{b}+2z)\Rightarrow (X(b)-X(t_{\nu })<-X_{b}+z)}$.

In modo analogo dato che per definizione di ${\displaystyle E_{n}}$ è ${\displaystyle z<X(t_{\nu })}$, vale la relazione (2.4):

(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)}$

Infatti la variabile casuale ${\displaystyle (X(b)-X(t_{\nu }))\thicksim N(\varnothing ;\ \ \sigma ^{2}(b-t_{\nu }))}$ ha una densità di probabilità simmetrica rispetto alla sua media che è zero.

Mettendo in sequenza le relazioni (2.3), (2.5) e (2.4) si ottiene la (2.6) :

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

Con lo stesso procedimento usato per ottenere (2.3), (2.4) e (2.5) sfruttando questa volta la relazione ${\displaystyle X(t_{\nu })<z+\Delta z}$ si ottiene la (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)}$

Applicando successivamente (2.6) e (2.7) si ha:

(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)}$

Da ${\displaystyle X_{b}>z+\Delta z>z}$, per la continuità di ${\displaystyle X(t)}$ e il teorema dei valori intermedi ${\displaystyle X(b)>X_{b}>z+\Delta z>z\Rightarrow E_{n}}$ , da cui ${\displaystyle P(X(b)>X_{b})=P(E_{n},X(b)>X_{b})}$

Sostituendo in (2.8) e passando ai limiti: ${\displaystyle \lim _{n\rightarrow +\ \infty }\ \ E_{n}(\Delta z)\rightarrow E(\Delta z)}$ mentre per ${\displaystyle \Delta z\rightarrow 0}$ l'evento ${\displaystyle E(\Delta z)}$ converge a ${\displaystyle \min _{a\leq t\leq b}X(t)\leqslant z}$

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

${\displaystyle \forall \,dX_{b}>0}$, sostituendo ${\displaystyle (X_{b})}$ con ${\displaystyle (X_{b}-dX_{b})}$nella (2.9) si ottiene l'equivalente:

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

Applicando il teorema di Bayes all'evento congiunto ${\displaystyle (\min _{a\leq t\leq b}X(t)\leqslant z,\ \ X_{b}-dX_{b}<X(b)\leqslant X_{b})}$

(2.11) ${\displaystyle \ \ \ \ P(\min _{a\leq t\leq b}X(t)\leqslant z\mid X_{b}-dX_{b}<X(b)\leqslant X_{b})=}$${\displaystyle P(\min _{a\leq t\leq 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})}$

Ponendo ${\displaystyle 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\}}$ risulta

${\displaystyle 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) ${\displaystyle \ \ P(A,C)=P(A,D)-P(A,B)}$

Sostituendo la (2.12) nella (2.11), si ottiene l'equivalente:

(2.13)${\displaystyle \ \ 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})}$

Sostituendo (2.9) e (2.10) nella (2.13):

(2.14)${\displaystyle \ \ \ \ P(\min _{a\leq 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})}$

Si osservi che nel secondo membro della (2.14) compare la distribuzione di probabilità della variabile casuale ${\displaystyle X(b)}$, normale con media ${\displaystyle X_{a}}$ e varianza ${\displaystyle \sigma ^{2}(b-a)}$.

Ai valori delle realizzazioni ${\displaystyle X_{b}}$ e ${\displaystyle -X_{b}+2z}$ della variabile casuale ${\displaystyle X(b)}$ corrispondono rispettivamente le densità di probabilità:

(2.15) ${\displaystyle \ \ \ \ 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) ${\displaystyle \ \ \ \ 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}}$

Sostituendo (2.15) e (2.16) nella (2.14) e prendendo il limite per ${\displaystyle dX_{b}\rightarrow 0}$ si è dimostrata la tesi:

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

${\displaystyle ={\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}}$${\displaystyle \ \ \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}=}$

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

• A versatile stochastic model of a function of unknown and time varying form - Harold J Kushner - Journal of Mathematical Analysis and Applications Volume 5, Issue 1, August 1962, Pages 150-167.
• The Application of Bayesian Methods for Seeking the Extremum - J. Mockus, J. Tiesis, A. Zilinskas - IFIP Congress 1977, August 8-12 Toronto.

• Variabile casuale
• Probabilità
• Evento (teoria della probabilità)
• Probabilità condizionata
• Processo stocastico
• Processo di Wiener

Portale Statistica: accedi alle voci di Wikipedia che trattano di statistica