^3c<-

Stat*s«cfl] V,r\r laboratory

National tin. an '>i Standards

jyaaiuii^tcn ‘lh, D. G.

NATIONAL BUREAU OF STANDARDS REPORT

2751

STOCHASTIC SEARCH TOR THE MAXIMUM OF A FTHETION

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Sinclair Weeks, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Astin, Director THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following listing of

the divisions and sections engagt i in technical work. In general, each section is engaged in specialized research, development, and engineering in the field indicated by its title. A brief description

of the activities, and of the resultant reports and publications, appears on the inside of the back

cover of this report.

Electricity. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Applied Electricity. Electrochemistry.

Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels. Cryogenic Engineering.

Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry. Solid State

Physics. Electron Physics. Atomic Physics. Neutron Measurements. Infrared Spectroscopy.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

Chemistry. Organic Coatings. Surface Cheipistry. Organic Chemistry. Analytical Chemistry.

Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing and Specifications. Polymer Structure. Organic Plastics. Dental Research.

Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy. Corrosion.

Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Concreting Materials. Constitution and Microstructure. Chemistry of Mineral Products.

Building Technology. Structural Engineering. Fire Protection. Heating and Air Conditioning. Floor, Roof, and Wall Coverings. Codes and Specifications.

Applied Mathematics. Numerical Analysis. Computation. Statistical Engineering. Machine

Development.

Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic

Instrumentation.

Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

Ordnance Development. These three divisions are engaged in a broad program of research

Electromechanical Ordnance, and development in advanced ordnance. Activities include

Ordnance Electronics. basic and applied research, engineering, pilot production, field testing, and evaluation of a wide variety of ordnance materiel. Special skills and facilities of other

NBS divisions also contribute to this program. The activity is sponsored by the Department of

Defense.

Missile Development. Missile research and development: engineering, dynamics, intelligence,

instnixnentation, evaluation. Combustion in jet engines. These activities are sponsored by the

Department of Defense. • Office of Basic Instrumentation • Office of Weights and Measures.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

1101-10-5102 August 12, 1953 2751

STOCHASTIC SEARCH FOR THE MAXIMUM OF A FUNCTION''

by

E . W„ Barankin

University of California, Berkeley, National Bureau of

Standards, Los Angeles, and Logistics Research Project,

University of California, Los Angeles

PREPRINT

“The preparation of this paper was sponsored (in part)

by ARDC

Approved for public release by the

The publication, ri

,

. . . Director of the National Institute of

unless permission 1 25 ,d.c. Such pe Standards and Technology (NIST)

cal ly prepared If l On October 9, 2015

In par t, Is prohibited

tandards, Washington

eport has been speclfireport for Its own use.

STOCHASTIC SEARCH FOR THE MAXIMUM OF A FUNCTION1

ty

2

E» Wo Barankin

io INTRODUCTION

Consider a real valued function f on a domain Do We assume that D

is a finite set of points, say N in number 0 Let M - max f(x), and

suppose f takes on the value M at exactly V points; the set of these

points will be denoted by K.

Far from looking upon our assumption of finiteness of D as a

specialization we consider that it reflects the real computing situation 0 Consequently, our results pertain also to situations in which D

is taken to be a continuum and in which continuous distributions are

employed; it is required only to' recognize the discontinuous distributions to which the given continuous distributions are approximations,.

It is our purpose here to study stochastic processes

more particularly, to study the implications of such a process for

the determination of M when the realized values x^ of the random

variables X^ are submitted to computation of f~ values. To be precise,

we suppose that after each stage of the process, say the i-th, if the

point x^ £ D is the realized value of X^, we compute f(x^). Thus,

The preparation of this paper was sponsored (in part) by ARDCo

^University of California, Berkeley, National Bureau of Standards,

Los Angeles, and Logistics Research Project, University of California,

Los Angeles

.

x € D

where each X^ is a random variable in D;

2

after the k-th stage, if the realized values of Xp X

2

, ° ° ° , X^ are

x]_s x

2 5

° e<>

s x

}c5 respectively, then we have before us the f- values

f(x^), fCx^, ->o °

5 f(x^) 0 This represents a certain amount of infor^-

mation about the function fj let us denote it by cfi ^°(x^ 5 Xg, *°°

9 x^.) „

It may be that some general knowledge concerning f can be coupled

with the information J ^°(x^ 5 x

2 , °°°

9 x^) t° give still a greater

amount of specific useful information after the k~th stage. Accordingly,

we shall take the k-th stage information scheme to be in general as

follows, in addition to J , °t

V(xr

x2

, x

k

) = a known number > V 4

max

i=l s 2 3

° f(x^) such that it is known

that M ^ Tk

(xi5

x

2

, xJ

V(xl> x2

. x^) % a known subset of D, A

k+^(x^ 5 x2

,

• °

° s x^,) —

|x^, Xg, •*°

3 x^j such that for each

x t \+i^x

l

3 x2'5

0 °°

5 x

k^ 5 although the

number f(x) may not be known exactly, it

is known that f(x) - T^Cx^, x^,, 000

9 x^) ;

^k 'xl

s x

2

3 °“° s x

k

) i a known subset of D s Bk+i^xis x

2

, - s x

k

) )

disjoint from A

k+^(x^, x

2

,

0 0 • ? x^) , such

that for each x £ Bk+]_(x-p X23 000

s x^) the

number f(x) is not known exactly, but it is

known that f(x) > T^Cx^, X2, °°° , x^)
'
3

The special case of this scheme , wherein

T,(x-, s x?3 °°° j xj = max f(x.) 3 i-ls 2 ,-..,k

^

{

Xf3 X2 3

° °

° 3 ^ 5

and

Bk+l^x

l

? *2; A

(where A denotes the empty subset of D) is that in which

<9 ^°(xi 3 Xg s

0 0 0 3 x

k

) is actually the total information at hand.

On the basis of the above information scheme, an immediately

suggested estimated value for M is T^Xx-p X23

0 0 • , x^) „ There are

alternatives to this] for example, the maximum of the function on D

obtained by a specified extrapolation of the known values of f on

However, in this article we shall fix our

attention on the estimator i = 1, 2, [

„ We are consequently

committed to study the stochastic convergence of the sequence of

random variables J - {^(X^), X

2

)

Of course, we have for all k = l s 2, • 0 °

, and all

:]_s ^2 : s x

k3 x

k+l 5

( 1 .1 ) T

k

(xi, x

2

3 ... 3 x

k

) ^ M

and

(l 02 ) ^k+l^x

l

5 X

2

S °°° s ^k+l^ ^k^x

l

s x

2 - x

k

)

o o
*
h

From (l„2) it follows that

(le3) ^k+2^ x

l

5 *2 5 Vl5 3

^k+l^^l j) 2 x

k

)

The stochastic process »& that will be at work producing points

of D, will be conditioned by the computer's behavior „ This conditioning is effected upon the conditional probabilities

(loU) {=Xk+1 X

i

= 1, 2, 5 x & D «

The conditioning is realized through the choice , by the computer, of

random devices which (he guesses) will secure desirable analytic conditions on the conditional probabilities (l.h)o Just what such desirable

analytic conditions are will be determined by studying the implications

of various analytic conditions on (l.h) in the light of our designated

criteria for the process <, Our criteria in this article are ‘the

following: large values for the probabilities

(i.s) P {VX

!» v •••

. V

" H

) > k 1> 2 > >

and weak and strong stochastic convergences of ^ to M. Thus^ the

problem that will occupy us is this: to find analytic conditions on

(l.U) which will give large values to the numbers (l,f>) and which will

insure weak and strong stochastic convergences of J to M„

Now, there is, of course, a limitation on the desirable analytic

conditions for which we may seek, a limitation that must be observed if

the computer is to be able to realize these conditions in the choices

(of random devices) that are open to him* namely, the fulfillment of
'
the conditions must be feasible under the 'information at hand at each

stage o To illustrate this,, consider that after any stage 9 say the k-th,

it would be hiphly desirable to select random devices to secure

(where Ak+1 denotes the complement of A^+ ^ in D) we do not have enough

information to locate a subset of Ks therefore not enough information

to secure (l 0 6)„ It will be seen in our discussion that our conditions

are feasible in the sense here indicated

„

Our results are stated in Theorem 1 (end of section 2) and in

Theorem 2 (end of section .3) . And in section h we discuss the matter

of improving these results.

2 0 SUFFICIENT CONDITIONS FOR STRONG CONVERGENCE OF J” TO M

As of each k-th stage , the computer is motivated in two ways

toward putting feasible analytic conditions on the probabilities

(loU)o First c, if neither of the situations (l „ 7) holds, he wishes

whatever be Xp ° • •

o ® o

, x^o But unless

A

k+l^ x

l s x2> 000

5 XjP = 0

or

to insure a positive (k+l)-th stage probability to each point of
.
6

x^)| this 5 by way of not ruling out the possibility

of any such point being realized in the (k+l)-th stage, since (according to the information at hand) f may have the value M only at one of these

complementary points „ Secondly , he wishes to assign high probabilities

to sets concerning which he has been led to believe that in them the

values of f are higher than the f~ values he has already discovered,,

The conditions we shall put on the probabilities (ijj.) will embody

these motivations

o

But first, consider (l*7) . If either of these situations holds,

and only if one of them holds, we know exactly which points constitute

K 0 And it is then feasible to make the probability of K unity c Thus,

we shall take

k+1(

x

1

o ^2

,

(2.1) p(\+1

£ K | X. = x., i = ls 2 S ••• 3 kj - 1 if (1*7) holds .

Now consider the first motivation„ One feasible realization of

this is in terms of a chosen positive number < 1, and is as follows: Whatever be x^s Xg, 000

s if (l 0 7) does not hold , we take

( 2 . 2 )

^ {^k+l ** x ® ^i x

i

s ^

000

,

x £ ^k+l^l 5 x

2 3 9 xk^

k for each

The nature of this condition is such as to imply a sharper restriction

on ck+1 . Let p(x^ 3 X

2

., 000

s x^) denote the nuntoer of points in

^k+l^xl 5 X

2 , 000

, x^.) o (This number is known under the ( information

7

at hand). Then s according to (2 ,2 ) 5 the conditional probability of the

set A

k+1

(xls X23

000

s x^.) is greater than or equal to

[N-/(x15 x

2

, <>«>

, x

k

)] c k+1 ,

and therefore this Humber must be less than or, equal to unity s whence

1

"k +l

“

/?(x15 x?5

Moreovers since ek+^is> taken to be independent of Xp x2S

we must have

s

( 2 .3 ) 'k+l N ~ min

X

l

3X

2

3

° ,oX

k

^7^7 000 3 77

"

¥e cannot say anything more explicit about the number

0 s x

k

) without further assumptions concerning

s

„ As an example 9 if

min

j0 (x-p x

2

s xi 5 x

2 s »-

s x

k

the sets Ak+1 (xp x

2

,

A

k+l^ x

l s ^2 • V - fxls X,23 >*}

for all Xp x

2 j

and we get

x

k

3 then

x,13

min

x

2

3

°

° ° ?x

k

X

2

3

° ° °

3 ^3

(2 oh)

Of course 3 the right-hand side of (2 0 U) is not greater than the righthand side of ( 2 „ 3 )s consequently5 if we required the fulfillment of

(2 o 10 3 then ( 2 , 3) would be automatically satisfied.

8

We now go to the second motivation,, And this leads us immediately

to favor at least the set Xg, »<><>

, x^) „ That is, if this set

is not empty,, then we know that the f- values at the points in it are

greater than the largest value of f so far discovered, and therefore

we want to give the ooints of B^-^ a "better than minimal chance" of

being realized,, If the second of the two situations (l e ?) holds, then

we know that B^^ (xp Xg, 000

, x^) “ K, and we proceed according' to

(2 cl) „ But if (1 0 ?) does not hold, we do not wish to throw all, the

conditional probability into B^p Bor, according to our incomplete

information, the value M may very well be taken on only in

•^k+1 U ®k+l° Bhus, we shall want only this much: to give each

point of B^.+^

a probability - a positive number, say b^. +p

this number

being greater than e^p

( 2 05 ) b

k+l > ®k+l

1 2

Thus do we favor the points of B^.+^ in particular, over the points

of in general o

But--we repeat—K may not intersect B^+^at all e The computer

may have some feeling about this, not at all based on the formal information at hando This is to say that he may feel justified in

making a guess over and above any logical justification by his information „ We want to allow for such guessing, and we do so as follows:

there shall be designated a set F^+1 (xp 0 * 0 $ x^) s disjoint from

B^+p

such that each of its points , as well as the points of B^p

shall be given a conditional probability - bjp^ o

9

We have now carried out fully the second motivation,, and it has

led to the following formal prescription; whatever be x^ 9 3 x^,

if (lo7) does not hold. we take

pfxk+1 = x I X

±

- xls 1, 2,

( 2 . 6)

“ s k| - b^..^ for each

x ^

^k-tl^ x

l

s x

2 3

°

°

° 5

where

^k+l^ x

l

s x

2

:

®k+l^xl

5 x

2

5

0 0 0 9 -^k^ U ^k+i^l 3 x

2 V

If t(x-^ 5 Xg'j 000

a Xy) denotes the number of points in the set

*\+l x

l s x

2

9

(2.7) V\ — Dk+1

x^) then we must have

1

max flx13 X-2

, 000

s x^J

y -y o a o y

ty2-*-2 s 5 K

It is to be remarked that if is empty then might very

well include the set

( 2 . 8 ) ^k+hx

l

5 x2 x

k

) =

x is known to have the

property that

f(x) = T

k

( xls x

2

? °“°» xi^s

< x E. x

2 9

° ° 0 s x

k^

or v x is not known to have the

property that

f(x) < T^(x-^ s X

2

,

0 • 0 s x

k

)

10

This would represent the guess -that M may already have been achieved,,

We shall, in fact, make this inclusion assumption! that is, if

^k+l^ x

l

5 x

2 3 000

3 x

k^ — emPt3r -

> then we take

(2 e 9) ^k+l^ x

ls x

2 3 00 ° 3 ~ A

k+l^ x

l 3 x

2

5

”

° ° 3 x

k

^ °

We have how finished our specification of a feasible set of analytic

conditions on the conditional probabilities (l„U), and we are ready to

study the implications of these conditions „ We direct our attention to

obtaining a lower bound 5 in terns of the constants bj, and

k - 2, 3 S

0 0 0 5 s for the comprehensive probability

P {T

s (X15 X23

0 0 0

3 X

g

) - M} . Let us define another estimator

{Tk

°, k = 1, 2, »co

| as follows?

(2 o 10) Tj

c°( xis x

2

'5 °

”

° , x^) - max f(x)

y»jy *y* o o o ‘V’

By virtue of the inclusion X

2

3 000, x^j S A

k+l^xl

3 X

2

S

0 0 0 3 3

we have always

(2-U) T

k°( x

i3

x

2

3 °°°

3 V £ T k

(xl

3 X

2

3 3 ^ °

Snd therefore

( 2 . 12 )

P

{ Ts (Xl> X2> > Xk

) “ M

}

X

2

, •••

, Z

s

) - M} , s - 1, 2
-
11

Hence , we shall have a lower bound for the left-hand side of (2„12) when

we have found a lower bound for the right-hand side „

Now, the right-hand side of (2„12) is equal to

1- p{Ts °(X1s X2s •••

, X

s

) < m] ( cf o (1.1) and (2.11)), apd therefore we may, and shall actually work first toward an upper bound for

(2.13) P (t

s°(X13 X

2 , •••

, X

s

) < M} = P (f(X

±

) < M, i = 1, 2, ..o

, s}

Toward this end we set down the following equalities and inequalities, derived from (2 d) , (2.2), (2 „6) , and (2„9).

(2.1U) P {f(Xk+1) < M | Xj. = x

±

, i - 1, 2, •••

, k] = 0 if (1.7) holds

If (l„7) does not hold , and if K f| G

k+^(x-^, x

2

, 000, x^) fit , then

(2.1?) P {f(Xk+1) < M | X

±

= x

i5 i = 1, 2, 000

? k

]

4 1 _ b

k+1 .

If (I.?) does not hold , and if K D G

k+^(x^ s x

2

,

0 • 0 , x^,) - A 3

then ,

(2.16) P {f(Xk+1) < M | X

± = x

±

, i - 1, 2, • ••

, k

} ^ 1 - V ck+1 .

I

These three assertions, for k - 2, 3, 000

, s - 1, together with

P { f(X

2

) < M

| - 1 ,

are now applied to the relations

12

P (f(X

i

) < M, i = 1, 2, °°°

, k + l) ®

Xp{Xi=Xi? i = l s 2 3

‘> <’«

3 kj> 3 k=2 3 33' , 0

5 s-l

And the result in general is the followings

p{f(X

i

) < M, i = 1, 2, ...

, s} ^

( 2 .18 ) oTT (max [1 - b ., 1 - vc,]), s = 2, 3 S 000

, j=2 3 J

whence

p { T

s°

(xi> x2>

••• x

s

5 =M} -

(2.19)

s 1 “ TT ( max [! “ b 1 " s = 2, 3, ••• . j=2 J J

¥e have said that (2„l8) is the consequence of our calculations

in general . One finds, in carrying out those calculations, that the

following hold:

If for all k = 2, 3, ° 00

, and all x^, • • • ,

G

k+l^ x

l 5 X

2

J °°° 5 con

~baj- ns a point of K, then

(2 a 20)

P {t

s°(X1s x

2

, •••

, X

s

) = m} *

1 - fr (1 - b ), s = 2, 3, ••• . 5 S2

j

13

If for all k - 2„ 3

^k+l^ x

l s x

2

3

°

° ° s amd all x^, Xg 9

x^) contains no point of Ks then

(2 e 2l)

{

T

s0(x Y

I s 2

J

(1 - Vc „)

* X

s

) - to j

3 c,

The import of these special results is this 0 Suppose the computer has

great confidence in his sets * 0 ° » x^.) 5 that is 5 confidence

that they contain points of K 0 Then he will make the numbers bj big

(i e e 05 very close to l) with the result that they will be much bigger

than the corresponding numbers Then if5 although this is not

within his information, the sets ^^(x^ X2, °°°

5 x^.) do in fact all

contain points of K(i 0 e 0 , his confidence in these sets is, unbeknown

to him9 actually verified), the probabilities P jT^

0

(X^ 9 X2? ,) = M I

have the larger lower bounds 1 - Jj (l - b.) . On the other hand, if t j-2 J in facte, none of the sets G^+-^ contains a point of K (in spite of his

confidence) then we can only assert (2 e 2l), with the smaller lower

s bounds 1 -

"f[ (1 - Vc .)

Now, a necessary and sufficient condition that the products in

(2 0 l8) and (2.19). for s = 2, 3, tend to 0 is that the series

oo min [bj S Vc .]

be divergento This condition, which, through (2„19) and (2„12) is

seen to be a sufficient condition for weak convergence of Cf to M, is

iu

however, not a feasible condition, for, we do not know the value of V .

However, by virtue of (2 £) we have

s s £ min [b , yc ] > £ e , s = 2, 3, ••• • j

*:

2

3 J

j -2 J

Hence, we can take the feasible condition that 2 c . be divergent « This

has, in addition, the consequence (again through (2,5)) that also 2 b

3

is divergent, Thus, the convergence to 1 of the right-hand sides of

all three inequalities (2.19), (2„2l), and (2.20 ) is assured.

Hence, the divergence of 2 c . insures the weak convergence of j

to M in any case * But more than this 5 it insures the strong convergence

of cf to Mo This is a consequence of (1.2) . That is, by virtue of

(1.2) we have, for each s - 1, 2, ° °

» ,

(2.22)

|(x15 Xg ; «• •) £ DXDX o,o

| Tc (x15 Xg, ° 8 °

» • “) 2 DX D X ° ° °

j lim T (x^, x0 , r—* oo r

> x

s

) = M

j

° * °

, x

r

) = m]

which implies that, for each s s

1, 2,_°.. ,

P

(

lim Tr

(Xls X

2 , •••

, X ) = M

j *

( 2 .23 ) p{t

s (XiS X2S ••• , X

s

)

=. m} ,

so that weak convergence implies strong convergence.

If we combine (2,12) with the inequalities (2,19), (2,20), and

(2 ,2l) to writes in general

IS

(2 e 2b)

1 -

p{ts

(Xi » X

2

, , x

s

) -«} *

S

TT (max[l - b., 1 - VcJ), s s 2 5 3 9 j= 2

J J

9

if for an k - 2, 3, o o o

9 . and all x-^ .9 ^2 9

9 • O 3 X

k

9 Gk+l^ x

l-9 X2

S contains a point of then

P <iVx

i> x2J 3 xj =

s »]f -

(2 0 25j) s i- rr a- b,) 9 S = 2 S 3 5, c . O

j

2* 2

3

if for all k = 2 5 3 S 3 . and all 9 X

2

9

o © o 3 X

k3 Gk+l^xl

s *2 3 contains no point of K 9 then

(2 0 26)

p

l

o o o $ x

s

) - M j, 'a

s 1 - TT (1 - VC,), s - 2, 3, ••• I 3-2 0

then we can state our result as follows?

THEOREM 1 0 If the sto ehasti c process $ satisfies the conditions

(2 0 l), (2 0 2)j {2 S) 9 (2 0 6) s and (2„9) 5 then the inequalitie s (2 «,2 U) 3

(2 0 2E>) 9 and (2.26) hold in the respective cases described „ And in any

ease a sufficient condition that Cf - {T

g (XiS Xg, •••

, X

g

) J,

s - 1, 2 S °] converge almost to M is that the series 2 c . be

0 divergent

This theorem actually states a weaker convergence result than we

have establishedo That is s (l 02) and consequently (2 c 22) and (2 C 23)

16

hold also with T° in place of T„ Therefore^ through the inequalities

(2 019) s ( 2 „ 20 ) s and (2 0 2l ) 5 the divergence of 2 implies almost sure

convergence of ° ” ° > X

g

)5 s = 1, 2 S

»

• ° "j to M 0

And this is the stronger result by virtue of (2 c ll) and (l„l) „ However s

our attention is concentrated on the random variables T (X^, °°°

s x

s and this being the case 5 our detailed results*, namely the inequalities

(2„2U), (2 e 25») $ and (2 0 26 ) are in fact the weaker for having come about

by our taking advantage of (2 o 12 ) 0 We shall say more about this in

section I4 ,

3o NECESSARY CONDITIONS FOR STRONG CONVERGENCE OF J TO M

In this section we shall obtain upper bounds for the probabilities

P ^T^(X^3

0 , X

g

) s M*j 5 s ~ 1 3 2 5 °°° 3 and from them obtain a

necessary condition for strong convergence of CT to M,

Let us define

(3 ol)

V

|x 6 A

]c+1

(x1 , x

2

, •••, x

fc

) I f(x) is known jand

(3<>2) a^+1

rain p { x

k+i

8 A

k+l^x

l* x

2

s

°

! " * I x

i

= V 1 = 2 > 000

j k

X]_S X

2

}

° ° °

k s 1 , 2 , •••

17

It is to be noted that the are feasible parameters! that is5 the

computer can control them (to within the requisite guessing) .

Now let us direct our attention to the following important subsets

of Ttt

( 33) H

k (xls ••• , xka=1 ) =| x

k

£ D|Tk

(x15 ^5 ° • ° , < M

|

.

For k = 1 we set also

( 3 , ^ - [x 2 D | T

1

(x) < mJ>

By virtue of (l„2) we have

(3.S)

M \ e H

k

( X1S X2: 5 X

k“l^ 3 ^en

x

k-=l

5 Hk-l^l5 *2 9

° os

5 x

k=2^

An equivalent statement is the followings

«N

if £ H

k. 1

(x1

, x

2

, •••

, ^_2

)

^k^x

l 3 x

2 ;

(3.6)

then

1 9 000

j x

k“l^ A

A consequence of this is that if H

k=^(x-^ a X

2

^ °”°

9 x

k

„2^ = A 3 then

for each x

k=1 E D also H^x-^ X

2

5

°

0 9 x

k_]_^ ” A „

From (3a 1?) or (3„6) we get the following identity!
'
18

(3 o?)

3^ £

XpS Hg (x^) o o o x

s-l£ HS“1^

X

1

5X2 5

°

’ °s x

s-2^

{t

s

( x1s X

2

, ...

, X

s

) < m} -

P(X

S a Hg(XpX2>

>00

3 X

S«1

) l X

l

s V 1 = Vs 000

, 3-!}

P X

s-1

* X

s=ilx

i

= x±s i = 1,2,°°°, S - 2}

p{x

2 ~ ^2 I xi = x

l| ^

pfx

i

- Xj} .

The importance of the sets is that they provide this exact expression

• , X

s

) < m] „

If it were the case that T

g (x^ s Xg, 0

for T

a (Xls X

2

,

, x

g

) = M for ail s and all

X

]_ 9 x

2

? x,„, then (3o?) would vanish identically c However., we are * a

S

5 excluding this extraordinary situation, and therefore we are assured

that for each k there is at least one set H^(x-^, x

2 ,

0 0 0 , x^-^) which is

not empty

o

Now let us take note of our information scheme. If, at the (k=l)th

stage, the knowledge of the values of f on A

k

°(x]_s x^,, , x^=^) could

in itself improve upon the number T^-^(x^s x

2

,

0 0 0 , x^=^) s then in the

information at that stage we should have put , not Tk=^(x^, Xg, 0 0 • , x^, )

I but the improved number 0 In other words, it is implicit in the information scheme that if the k-th realized point, x^, is, as a point of D, a

duplicate of one of the points in A^°(x^, x

2

,

0 •

° , x^_^) then

Tk

(x15 Xg* , V Tk-fx

l» x

2 : , x^-^) — that is, the T -value
'
19

does not increase „ In particular 5 there fore 9 if

\"l^x

l

s x

2 3 °°° 5 X

k“l^

< ^len for eac^ x e A

k°^

X

l

5 we have T^(x^, Xg 3

°

« ° s x

k«,]_3 x) < M * Otherwise expressed:

r

(3o8)

if 1 ^ ^k~l^x

l

3 x

2 3 3 x^) 5 then

A

k

U

( X13 X

2

3 0C ° S X

k„X

) & %(X*| ^ Xp 1 3 X

k_]_^

Combining this with (3 e 6) we get;

if x

2 3 °'° 3 x

k-i^ ^ A 3 then

^ ^ x]_s x

2

3 °°° 3 x

k“l^ — ^k^x

l

3 x

2

9

From (3«,2) and (3 ®9) we get the following inequalities:

Vi>

P h ? vX13 X

2

3 °°° 3 ^“1

k - 2 S 3,

iji-'lj 2, •• 0 , k - :

Ifs now3 we set

p|xi £ H^J = ai

and apply (3®10) to (3.?) s we obtain the following result:

{t

s (x I

s X

2

3 X

s

) < m] » JT ( 3 . 11) a

And therefore,,

(3.12) P {t

s (X1? X2? ... , Xs

) - m] * 1

1

3=1

3 x

k=1 )

} ~ \ >
I d
20

If there is strong convergence of U to M„ then the left-hand

side of (3 «X2) must tend to 1 as s ro 0 Consequently we must have

s

"fj a. 0 (by our assumption of a non-trivial problem 5 a, > 0) 0 We

j-2 0 1

state this result in

THEOREM 2 „ A necessary condition that the s toe hastic process

give strong ( or weak ;, since the two are equivalent by virtue of ( 1 „2

)

convergence of to M is that (cf„ ( 3 0 2)

)

s (3,13) lim Tf a. = 0 o s~^ co j=2 J

The inequalities (3 .12 ) hold for J „

It is readily seen that the relations

(3 .111) ^ 1 - q± , i ~ 2 s 3 S 000

hold^ so that the divergence of 2 c^ implies (3.13)

This theorem is in the nature of an exact verification of the

first motivation discussed in section 2„ It says,, roughly9 that we

must not consisteritly allot too much conditional probability to the

points at which the value of f is alre ac£y knowns if we are to have

stochastic convergence of 3T to Mo

By virtue of (2,11), the inequalities (3.12) and the theorem

hold a fortiori if T is replaced by T

0

o
m
21

he CONCERNING SHARPENING OF THE RESULTS

The results we have obtained in section 2 are quite obviously

obtained actually for the estimator ^T.,

0

, s-l? 2 ? °"°| s and come to

bear upon *£t

s5

s = 1 5 2,

* ta j

through (2,12), This means that those

results could have been obtained even if we had not introduced the

hypothesis of additional k-th stage information embodied in the generally

conceived sets Xg, 0 6 0 s x^) and B^, +-(x15

°°°

? if we had assumed V(xi> Xgj 000

5 x^.) as the only k-th stage information, And the results in section 3 obtain by the grace of (3*9) 5 which is

a completely general relation,, therefore holding also in the special

case where c)^°(x^ s X23 000

5 x^) is the only information.

One of the directions for investigation after bounds which will

be improvements on (2,2^), (2 0 2^) s (2,26)3 and (3,12)3 is in making

additional assumptions concerning the information scheme. For example,

if1 we specialize to the situation that D is a rectangular lattice in

the plane,

D - [ (mh, nh) | m, n = l s 2, , ° ° 0

' , r

j

5

and that the computer knows f to have the property

|f(rnh, nh) - f(m 5 h s n'h) j < ^

for m* = m t 1, n* - n ± 1 ,

where °( is a fixed number, then the following can be said: if

x.(j = 1, 2, 000

, k) is such that f (x „) + & - max

i+1,2, * 0 *k

f (x.

)

22

then the four points x„ * (h„ h) s x„ + (-h, h) 9 x„ + (h

5 ~h) 5 and

<D <D 0

Xj + (~h 5 -h) all belong to A^^Cx^

Such additional facts concerning the sets A^+^, 311(1 iFk+l

would enable us in general to improve the inclusion relation (3 0 9)

|

that is s enable us to assert a larger set than A^° included, in

In this way we could obtain smaller upoer bounds for

P X

2 9

° 00 ' 3 X

g

) ~ m} than given in (3d2) 0

It is easy to see that we always have:

(lid) H

k

(xls Xg, 000

, x

k_1

) c K o

This relation can be used with (3 0 7) to obtain lower bounds for the

probabilities P {T

g (X^ 5 X23 ° s X

g

) - M

|

„ And these lower bounds

are precisely (2 0 2k) s (2 0 2£) s and (2 0 26) 0 Mow, additional facts

concerning the sets A^

+^

s and F.^ would in general enable us

also to improve (lul), and thereby,, through (3»7) to obtain better

bounds than given in (2 0 2i|) 3 (2 02E>) 5 and (2 0 6) 0

Of course 5 such improved bounds would in turn give us less

stringent sufficient conditions for convergence of J" to M and more

complete necessary conditions „

But even without making additional assumptions concerning the

information scheme, there is a refinement that can be made to improve our results 0 This is to introduce more control parameters

than the b^ and namely,, different parameters for different
'

©8 -e -rii

-
23

values of /?(x^ s x2?

°°°

, x^.) s X (x^ 5 x

2

,

° °

°

, x^) , and

X(x^ 3 x23 ° °

» 3 x^) (- number of points in x^ 8 8 ° > x^))

as well as for different stages k„ This would call for more refined

calculations with (2„17) and (3 o7)

August 12 9 19^3

THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The functions of the National Bureau of Standards are set forth in the Act

of Congress, March 3, 1901, as amended by Congress in Public Law 619, 1950.

These include the development and maintenance of the national standards of

measurement and the provision of means and methods for making measurements

consistent with these standards; the determination of physical constants and

properties of materials; the development of methods and instruments for testing

materials, devices, and structures; advisory services to Government Agencies on

scientific and technical problems; invention and development of devices to serve

special needs of the Government; and the development of standard practices,

codes, and specifications. The work includes basic and applied research, development, engineering, instrumentation, testing, evaluation, calibration services

and various consultation and information services. A major portion of the

Bureau’s work is performed for other Government Agencies, particularly the

Department of Defense and the Atomic Energy Commission. The scope of activities is suggested by the listing of divisions and sections on the inside of the

front cover. Reports and Publications

The results of the Bureau’s work take the form of either actual equipment and

devices or published papers and reports. Reports are issued to the sponsoring

agency of a particular project or program. Published papers appear either in the

Bureau’s own series of publications or in the journals of professional and scientific

societies. The Bureau itself publishes three monthly periodicals, available from

the Government Printing Office: The Journal of Research, which presents complete papers reporting technical investigations; the Technical News Bulletin, which

presents summary and preliminary reports on work in progress; and Basic Radio

Propagation Predictions, which provides data for determining the best frequencies

to use for radio communications throughout the world. There are also five series

of nonperiodical publications: The Applied Mathematics Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous Publications.

Information on the Bureau’s publications can be found in NBS Circular 460,

Publications of the National Bureau of Standards ($1.00). Information on cali- bration services and fees can be found in NBS Circular 483, Testing by the National

Bureau of Standards (25 cents). Both are available from the Government Printing Office. Inquiries regarding the Bureau’s reports and publications should be

addressed to the Office of Scientific Publications, National Bureau of Standards,

Washington 25, D. C.