Probability distribution of extreme points of a Wiener stochastic process explained

In the mathematical theory of probability, the Wiener process, named after Norbert Wiener, is a stochastic process used in modeling various phenomena, including Brownian motion and fluctuations in financial markets. A formula for the conditional probability distribution of the extremum of the Wiener process and a sketch of its proof appears in work of H. J. Kusher (appendix 3, page 106) published in 1964.[1] a detailed constructive proof appears in work of Dario Ballabio in 1978.[2] This result was developed within a research project about Bayesian optimization algorithms.

In some global optimization problems the analytical definition of the objective function is unknown and it is only possible to get values at fixed points. There are objective functions in which the cost of an evaluation is very high, for example when the evaluation is the result of an experiment or a particularly onerous measurement. In these cases, the search of the global extremum (maximum or minimum) can be carried out using a methodology named "Bayesian optimization", which tend to obtain a priori the best possible result with a predetermined number of evaluations. In summary it is assumed that outside the points in which it has already been evaluated, the objective function has a pattern which can be represented by a stochastic process with appropriate characteristics. The stochastic process is taken as a model of the objective function, assuming that the probability distribution of its extrema gives the best indication about extrema of the objective function. In the simplest case of the one-dimensional optimization, given that the objective function has been evaluated in a number of points, there is the problem to choose in which of the intervals thus identified is more appropriate to invest in a further evaluation. If a Wiener stochastic process is chosen as a model for the objective function, it is possible to calculate the probability distribution of the model extreme points inside each interval, conditioned by the known values at the interval boundaries. The comparison of the obtained distributions provides a criterion for selecting the interval in which the process should be iterated. The probability value of having identified the interval in which falls the global extremum point of the objective function can be used as a stopping criterion. Bayesian optimization is not an efficient method for the accurate search of local extrema so, once the search range has been restricted, depending on the characteristics of the problem, a specific local optimization method can be used.

Proposition

Let

X(t)

be a Wiener stochastic process on an interval

[a,b]

with initial value

X(a)=Xa.

By definition of Wiener process, increments have a normal distribution:

fora\leqt1<t2\leqb,    X(t2)-X(t1)\simN(0,

2(t
\sigma
2

-t1)).

Let

F(z)=\Pr(minaX(t)\leqz\midX(b)=Xb)

be the cumulative probability distribution function of the minimum value of the

X(t)

function on interval

[a,b]

conditioned by the value

X(b)=Xb.

It is shown that:[3] [4]

F(z)=\begin{cases}1&forz\geqmin\{Xa,Xb\},\\ \exp\left(-2\dfrac{(z-Xb)(z-Xa)}{\sigma2(b-a)}\right)&forz<min(Xa,Xb). \end{cases}

Constructive proof

Case

z\geqmin(Xa,Xb)

is an immediate consequence of the minimum definition, in the following it will always be assumed

z<min(Xa,Xb)

and also corner case

minaX(t)=min(Xa,Xb)

will be excluded.

Let' s assume

X(t)

defined in a finite number of points

tk\in[a,b],  0\leqk\leqn,  t0=a

.

Let

Tn  \overset{\underset{def

}}\ \ \ by varying the integer

n

be a sequence of sets

\{Tn\}

such that

Tn\subsetTn+1

and
+infty
cup
n=0

Tn

be a dense set in

[a,b]

,

hence every neighbourhood of each point in

[a,b]

contains an element of one of the sets

Tn

.

Let

\Deltaz

be a real positive number such that

z+\Deltaz<min(Xa,Xb).

E

be defined as:

E  \overset{\underset{def

}}\ \ (\min_X(t) < z + \Delta z)

\Longleftrightarrow

(\existst\in[a,b]:X(t)<z+\Deltaz)

.

Having excluded corner case

minaX(t)=min(Xa,Xb)

, it is surely

P(E)>0

.

Let

En,  n=0,1,2,\ldots

be the events defined as:

En  \overset{\underset{def

}}\ \ (\exists \,t_k \in T_n : z < X(t_k) < z + \Delta z) and let

\nu

be the first k among the

tk\inTn

which define

En

.

Since

Tn\subsetTn+1

it is evidently

En\subsetEn+1

. Now equation (2.1) will be proved.

(2.1)

    E=

+infty
cup
n=0

En

By the

En

events definition,

\foralln  EnE

, hence
+infty
cup
n=0

En\subsetE

. It will now be verified the relation

E

+infty
\subsetcup
n=0

En

hence (2.1) will be proved.

The definition of

E

, the continuity of

X(t)

and the hypothesis

z<Xa=X(a)

imply, by the intermediate value theorem,

(\exists\bar{t}\in[a,b]:z<X(\bar{t})<z+\Deltaz)

.

By the continuity of

X(t)

and the hypothesis that
+infty
cup
n=0

Tn

is dense in

[a,b]

it is deducted that

\exists\bar{n}

such that for

t\nu\inT\bar{n}

it must be

z<X(t\nu)<z+\Deltaz

,

hence

E\subsetE\bar{n}\subset

+infty
cup
n=0

En

which implies (2.1).

(2.2)

    P(E)=\limnP(En)

(2.2) is deducted from (2.1), considering that

EnEn+1

implies that the sequence of probabilities

P(En)

is monotone non decreasing and hence it converges to its supremum. The definition of events

En

implies

\foralln  P(En)>0P(En)=P(E\nu)

and (2.2) implies

P(E)=P(E\nu)

.

In the following it will always be assumed

n\geq\nu

, so

t\nu

is well defined.

(2.3)

    P(X(b)\leqslant-Xb+2z)\leqslantP(X(b)-X(t\nu)<-Xb+z)

In fact, by definition of

En

it is

z<X(t\nu)

, so

(X(b)\leqslant-Xb+2z)(X(b)-X(t\nu)<-Xb+z)

.

In a similar way, since by definition of

En

it is

z<X(t\nu)

, (2.4) is valid:

(2.4)

    P(X(b)-X(t\nu)>Xb-z)\leqslantP(X(b)>Xb)

(2.5)

    P(X(b)-X(t\nu)<-Xb+z)=P(X(b)-X(t\nu)>Xb-z)

The above is explained by the fact that the random variable

(X(b)-X(t\nu))\thicksimN(\varnothing;

2(b-t
  \sigma
\nu))
has a symmetric probability density compared to its mean which is zero.

By applying in sequence relationships (2.3), (2.5) and (2.4) we get (2.6) :

(2.6)

    P(X(b)\leqslant-Xb+2z)\leqslantP(X(b)>Xb)

With the same procedure used to obtain (2.3), (2.4) and (2.5) taking advantage this time by the relationship

X(t\nu)<z+\Deltaz

we get (2.7):

(2.7)

    P(X(b)>Xb)\leqslantP(X(b)-X(t\nu)>Xb-z-\Deltaz)  

=  P(X(b)-X(t\nu)<-Xb+z+\Deltaz)\leqslantP(X(b)<-Xb+2z+2\Deltaz)

By applying in sequence (2.6) and (2.7) we get:

(2.8)

P(X(b)\leqslant-Xb+2z)\leqslantP(X(b)>Xb)

\leqslantP(X(b)<-Xb+2z+2\Deltaz)

From

Xb>z+\Deltaz>z

, considering the continuity of

X(t)

and the intermediate value theorem we get

X(b)>Xb>z+\Deltaz>zEn

,

which implies

P(X(b)>Xb)=P(En,X(b)>Xb)

.

Replacing the above in (2.8) and passing to the limits:

\limn  En(\Deltaz)E(\Deltaz)

and for

\Deltaz0

, event

E(\Deltaz)

converges to

minaX(t)\leqslantz

(2.9)

    P(X(b)\leqslant-Xb+2z)=

P(minaX(t)\leqslantz,  X(b)>Xb)

\foralldXb>0

, by substituting

(Xb)

with

(Xb-dXb)

in (2.9) we get the equivalent relationship:

(2.10)

    P(X(b)\leqslant-Xb+2z+dXb)=

P(minaX(t)\leqslantz,  X(b)>Xb-dXb)

Applying the Bayes' theorem to the joint event

(minaX(t)\leqslantz,  Xb-dXb<X(b)\leqslantXb)

(2.11)

    P(minaX(t)\leqslantz\midXb-dXb<X(b)\leqslantXb)=

P(minaX(t)\leqslantz,  Xb-dXb<X(b)\leqslantXb)

/  P(Xb-dXb<X(b)\leqslantXb)

Let:

B\overset{\underset{def

}} \ \, \ C \ \overset \ \, \ D \ \overset \ \, \ A \ \overset \ \ \From the above definitions it follows:

D=B\cupCP(A,D)=P(A,B\cupC)=P(A,B)+P(A,C) P(A,C)=P(A,D)-P(A,B)

(2.12)

    P(A,C)=P(A,D)-P(A,B)

Substituting (2.12) into (2.11), we get the equivalent:

(2.13)

P(minaX(t)\leqslantz\midXb-dXb<X(b)\leqslantXb)= (P(mina\leqslantX(t)\leqz,  X(b)>Xb-dXb)- P(mina\leqslantX(t)\leqz,  X(b)>Xb))   /  P(Xb-dXb<X(b)\leqslantXb)

Substituting (2.9) and (2.10) into (2.13):

(2.14)

    P(minaX(t)\leqslantz\midXb-dXb<X(b)\leqslantXb)=

(P(X(b)\leqslant-Xb+2z+dXb)-P(X(b)\leqslant-Xb+2z)

/  P(Xb-dXb<X(b)\leqslantXb)

It can be observed that in the second member of (2.14) appears the probability distribution of the random variable

X(b)

, normal with mean

Xa

e variance

\sigma2(b-a)

.

The realizations

Xb

and

-Xb+2z

of the random variable

X(b)

match respectively the probability densities:

(2.15)

    P(Xb)dXb=

1
\sigma\sqrt{2\pi(b-a)
}\exp \biggl(- \frac \frac \biggr) \, dX_b

(2.16)

    P(-Xb+2z)dXb=

1
\sigma\sqrt{2\pi(b-a)
}\exp \biggl(- \frac \frac \biggr) \, dX_b

Substituting (2.15) e (2.16) into (2.14) and taking the limit for

dXb0

the thesis is proved:

F(z)=P(minaX(t)\leqz  |  X(b)=Xb)=

=

1
\sigma\sqrt{2\pi(b-a)
}\exp \biggl(- \frac \frac \biggr) \, dX_b

  \diagup  

1
\sigma\sqrt{2\pi(b-a)
}\exp \biggl(- \frac \frac \biggr) \, dX_b =

=\expl(-

1
2
(-X+2z-
2
X
a)
-(Xb-
2
X
a)
b
\sigma2(b-a)

r)=

  \expl(-2  

(z-Xb)(z-Xa)
\sigma2(b-a)

r)

Bibliography

See also

References

  1. H. J. Kushner, "A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise", J. Basic Eng 86(1), 97–106 (Mar 01, 1964).
  2. Dario Ballabio, "Una nuova classe di algoritmi stocastici per l'ottimizzazione globale" (A new class of stochastic algorithms for global optimization), University of Milan, Institute of Mathematics, doctoral dissertation presented on July 12th 1978, pp. 29–33.
  3. János D. Pintér, Global Optimization in Action: Continuous and Lipschitz Optimization, 1996 Springer Science & Business Media, page 57.
  4. The theorem, as set out and shown for the case of the minimum of the Wiener process, also applies to the maximum.