Section 11.3

NATIONAL BUREAU OF STANDARDS REPORT

17911-

TIME “DISCRETE STOCHASTIC PROCESSES IN ARBITRARY SETS,

WITH APPLICATIONS TO PROCESSES WITH ABSORBING REGIONS

AND TO THE PROBLEM OP LOOPS IN MARKOFF CHAINS

by

D„ van Dantzig

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Astin, HHRoirector

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 engaged 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.

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

2. Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic Technology. Length. Gage.

3. Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and Lubrication. Engine Fuels.

4. Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry.

Physical Electronics. Electron Physics. Atomic Physics. Neutron Measurements.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation.

Radiological Equipment. Atomic Energy Commission Instruments Branch.

5. Chemistry. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical

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

6. Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters.

7. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing

and Specifications. Organic Plastics. Dental Research.

8. Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy.

Corrosion.

9. Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals.

Building Stone. Concreting Materials. Constitution and Microstructure. Chemistry

of Mineral Products.

10. Building Technology. Structural Engineering. Fire Protection. Heating and Air

Conditioning. Exterior and Interior Coverings. Codes and Specifications.

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

Machine Development.

12. Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic Instrumentation.

13. Ordnance Development. Mechanical Research and Development. Electromechanical Fuzes. Technical Services. Missile Fuzing Research. Missile Fuzing Development.

Projectile Fuzes. Ordnance Components. Ordnance Tests. Ordnance Research.

14. Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular

Propagation Services. Frequency Utilization Research. Tropospheric Propagation

Research. High Frequency Standards. Microwave Standards.

lo. Missile Development. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Instrumentation. Technical Services. Combustion.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

3011 - 60-0002 10 June 1952 179^

TIME-DISCRETE STOCHASTIC PROCESSES IN ARBITRARY SETS,

WITH APPLICATIONS TO PROCESSES WITH ABSORBING REGIONS

AND TO THE PROBLEM OF LOOPS IN MARKOFF CHAINS

by

D, van Dantzig

Contract CST-525

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

The publication, reprinting, or repr od from the Office of the Director, Natii which a report has been specifically

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

;ed unless permission is obtained In writing

is not needed, however, by an agency for

f that particular report for its own use.
FOREWORD

Time-discrete stochastic processes have many applications in physics, chemistry, and other fields — for example

in the study of configurations of atoms in large molecules,

and in connection with the relatively new method of statistical inference known as sequential analysis. As outlined in

the following Abstract, this report presents some new results

which it is believed will be of interest to both mathematicians and workers in applied fields.

These results were developed during the summer of 1951

by Dr. David van Dantzig, Professor of the Theory of Collective Phenomena at the University of Amsterdam, while a guest

worker in the Statistical Engineering Laboratory of the

National Bureau of Standards. The Statistical Engineering

Laboratory is Section 11.3 of the National Applied Mathematics Laboratories (Division 11, National Bureau of Standards)

and is concerned with the development and application of

modern statistical methods in the physical sciences and engineering. Research embodied in the present report was performed

under Contract CST-525 between the National Bureau of Standards

and the University of North Carolina.

J. H. Curtiss

Chief, National Applied

Mathematics Laboratories

A. V. As tin

Director

National Bureau of Standards
TIME-DISCRETE STOCHASTIC PROCESSES IN ARBITRARY SETS,

WITH APPLICATIONS TO PROCESSES WITH ABSORBING REGIONS

AND TO THE PROBLEM OF LOOPS IN MARKOFF CHAINS

By

D. van Dantzig

Prepublication

ABSTRACT

By means of generalized generating functions (functionals)

and generalized matrices, a linear operator C(A) in a space of

measurable functions on a given set E (containing e.g„ all

bounded ones) is introduced ^depending on the subset A where

absorption takes place. An interpretation, previously given,of

the auxiliary variables and functions as probabilities, e.g. of

the hon-occumence of sotne "catastrophe", appears to be useful for

this type of problems also. It is proved that C(A ) is a projection-operator and that for A^A^ CJ^and are commutable and that their product equals C(Ai ) . This identity contains

as a Special case an identity recently obtained in art Amsterdam

i Ph.D. -thesis by J .H.B.Kemperman. Moreover A.Wald‘s fundamental

identity is generalized and it is shown that the characteristic

function of a distribution can be considered as a special case of

an eigenvalue in a generalized sense, where the eigenfunction (in

the special case an exponential function) needs only be proportional to its transform by the linear operator outside the

absorbing set A , Finally some theorems on loops in the path ©f

a wandering point and some similar results are obtained by derivation of the generating functional with regard to the function

en which it depends

.

2

The purely mathematical theory of generalized matrix-multiplication is developed in the Appendix. In particular, sufficient

conditions for the associativity are given, in cases also where

the matrices are not bounded. Moreover the Appendix contains a generalization of a process by "independent increases", for the

case of a set on which (under some conditions) a transitive group

operates. I owe several remarks which improved the text to

Mr J.J.de Iongh, who assisted me in drawing up the final version

of this paper.

1 . The Method of Collective Marks .

According to A .Kolmogoroff a probability field is defined

as a set 77' on which a countably [l] additive set function (defined, i O and i i for all subsets A of 77 belonging to a 6 -field

Gji- , which contains 77 and each of its elements) is given. Denoting the set function by P the value it takes on a set A by

PA (instead of P(A) ) 3 we have

CS PA S / r Pjz ( 1 • 1 )

27 , it A -UAn and Am r\ An = o {qt m $ n (1*2)

In many problems of probability theory we have to do with

several countably additive set functions, all defined on a single

set 77 , i.e., P may vary over another set fl , usually called

[l] These countably additive set functions, defined by the condition 1.2 are also sometimes referred to as totally additive

absolutely additive, completely additive or 6 -additive set

functions

.

- 3

-

the "set of admissible hypotheses" or "parameter space". Then for

any Qe/2 we have a P , denoted by P taking on A. the value .

If IT is a countable (i.e. finite or denumerable) set, we have

Pf~Z. Pf , and if both IT and J2 are finite sets, Pf is deterAs.A

A ^

7~> O

mined by the ordinary rectangular matrix of the numbers } with

Ae./Z „ For this reason we call the system of values with 0^12,

-A s <3Jr , subject to the condition of countable additivity with

respect to /L a (generalized) matrix . Some of the fundamental properties of these matrices will be considered under somewhat more

general conditions in an Appendix to this paper (§§ 7 and 8). [2] . Generalizing an idea of Laplace, according to which a system

of probabilities pn (n= 0, 1 , 2 , — ) is represented by its "generating function"

<e U)€ ZPr

n

(1.5)

z being an auxiliary variable, it was found to be useful

(Cf. D.van Dantzig 1940), to represent a probability field

by the corresponding functional of an auxiliary function IT , defined on IT . Assuming this function to be 6 n -measurable

and the integral 1.4 to exist, and denoting the value, which

takes in a point A e TT , by IT

*

( instead of the customary ZL(\) ),

the corresponding functional may be written as

(1.4)

[2] The notation used in the Appendix ( Px instead of P^ ) is

slightly different from the notation in this paragraph, but

conforms to the use in § 2.

If C(U) is known for a sufficiently large class of functions U. , it determines P . In the simplest case, when it is known for all

bounded <5^. -measurable , we have

^ = (1 - 5)

where /,

L ( / =iota) denotes the characteristic function of the set

A , defined by

r 1 if A e

A

A ctf A. = < (1.6)

\ 0 if not .

(Cf. D.van Dantzig, 1935). In the more general case, when P varies over a setjQ , we can also introduce an auxiliary countably additive set function F on a 6-field (5xl of subsets of FI , assuming for any fixed A to be <5n

-measurable, and define

the corresponding functional

(1.7)

These functionals were introduced in my Amsterdam lectures in

19^7 and in a lecture given at Lyon in 19^8 (published 19^9)

J

and some applications of the method were given there. The auxiliary functions were called "marks", their functional the "collective mark". It will be found useful to use a notation and terminology, introduced on another occasion ( 1935 ).* viz. to call point

functions and countably additive set-functions (subject to certain hardly restrictive conditions specified in the Appendix,

functions of the first and the second kind respectively, and to

denote systematically the arguments (points) of the former ones
IH

II

ilniinnBII11III
- 5 -

by lower case letters written as upper suffixes, and those (sets)

of the latter ones by capitals, written as lower suffixes, except

that in the case where an integration is performed the limits of

"small" or "elementary" sets are represented by the symbol denoting the corresponding variable point, preceded by the letter d , instead of a capital letter.

Previous applications showed that the application of the

method was often considerably facilitated, if the auxiliary and

collective variables, functions and functionals were interpreted

as probab i lities , whilst restricting their range temporarily to

the real interval (0,1

)

. So in 1.7 we might restrict F@ (Oz

to 0 5 Fq~ 1 -

7~f2 , and interpret F® as the probability that, by

means of some random mechanism a Ge© were chosen. Also, assuming 05 V.

K 5 i 3 we might consider an auxiliary event E (which

has nothing to do with the probability problem under consideration)

and assume that whenever the latter results in a A e 71 , a random mechanism, depending on A , determines with a probability

i-U against U

X

, whether or not E happens. Then C{F,7F)

is the total probability that <5 doee not happen. It is essential, that the random mechanisms remain (at least partly) inde -

termined , so as to guarantee variability of F and ll over sufficiently large sets of functions. Roughly speaking, the wider the

class of functions over which F and U may vary, the larger the

class of problems for which their introduction is useful. The

interpretation of an auxiliary F as a probability distribution

is due to J.von Neumann (1928) and was extensively used in his

and 0 .Morgenstern ' s Theory of Games and Economic Behavior, (19^7)>

and in A. Wald's Statistical Decision Functions, (1950). Functions

b

of the first kind, however, whenever they occur in these places,

are usually given an economic interpretation as "gains" or

"losses". This, doubtless, has the advantage that they may vary

over all real numbers, not requiring restriction to the interval

(Ot i) , but the disadvantage, that products and powers of gains

or losses have no obvious interpretation, whereas products of

probabilities may readily be interpreted as probabilities.

For the same reason C and tl have been interpreted as

the total and conditional probabilities that an event <5 does

not (instead of does ) occur. We shall call this event a "catastrophe". The terminological advantage of taking occurences of

non £ instead of '£ lies in the fact that a conjunction of several non-occurences of <? can be described as a (total) nonoccurence of 'E , whereas a conjunction of several occurrences

of E cannot be described so simply as an occurrence. Anyhow, the

interpretation of the auxiliary quantities is not of primary importance, and moreover, nothing prevents us, so far as no convergence difficulties occur, to apply the probabilistic terminology

to negative or complex quantities also, in the same way as it is

done with the geometric terminology. (Cf. Bartlett, (1944)).

It is the purpose of the present paper to derive some results concerning stochastic processes by means of this method,

2 . Stochastic Processes .

We consider random variables, i.e, functions on 77 , the

"values" of which are elements x,y,z, . . . of an arbitrary set E.

Random variables (or random events) will be denoted by dropping
T

mm*>

IH

inn«iiiiiiiI
- 7

-

the argument A 6 77 and underlining the function symbol, e.g. Xs

y-s x/? 5,etc, [ 3]. Again we assume that on the set E and on its

direct product sets (£"x£\ 77x7. xTT, - - - ) S’ -fields of subsets

5 6E

i 3 ® e* ?

- - - are given (more general conditions are considered in the appendix § 7). [4] . We shall define a stochastic process (discrete in time) as

a sequence of random variables x 0 , , x 2 s

• • . in E , such

that the conditional probability distribution of each of them,

the preceding ones being given, exists:

^~(n) X

~ ^>j ~n I ^ ( 2 * 1 )

where xQ 3

. . . 3 x n_ 7 are arbitrary elements of E and X is an

element of <5 E . These probability distributions will be assumed

to be <o£n -measurable (in x0 5 . .

. , xn_ 7 ) and countably additive in

X and to satisfy the relations

7~\ >

* * * P 7 j X n-i

( 2 . 2 )

The common probability distribution of x ; , is given by

P

(n)

r

X0 3

• •

• 3 Xn

~ ‘ t -0 6 -X-o 7 ••*>£?/? 6 P-nJ 5 (2.3)

[ 3 ] Random variables often are denoted by capital letters. This

rarely is done consistently, capitals being used for other

purposes also, and some random variables being denoted by

other symbols. Our system of notation saves a whole alphabet

(capital letters) for other purposes,

[4] In order to obtain a definition of the probability distribution on E we have to restrict the random variables to

those functions on 77 which are <5E - <3 77

- -measurable, i.e.

for which the originals of <o£

-sets are always <3^ -sets.

We restrict ourselves to the case, where It is countably

additive, not only in each Xk separately, but also in the Xk

together, hence on <o . Assuming moreover that the multiple

integral equals the result of successive integrations, it is

then related to 2.1 by the recurrent relation for n jr. i .

/

^(n) s / -p

(n. r) *,*/?.;

• — ~ J " J

r dx° >

‘ ' * ><XXn-i

J (n) Xo Xn_, Descriptively we shall refer to the sequence of random

variables as to a "random walk" in E , or a point, "wandering"

or "jumping" through or over E , to the elements xeE as to

the states or "places" in which it may be, and to rfn> y as

to the ^transition probability from a point having "passed through"

*o »

• • • > xn.t successively to any state in X , The sequence of

states x0 >x 7S ..- through which the wandering point passes will be

th called its path, the sequence x0 ,...^xn its n path-segment, the

transition from x n _ 7 to xn the n step (or jump) .

A stochastic process is a (simple) Markoff process , if the

transition-probabilities for n> i depend on the last state

only, through which the wandering point has passed:

-p

x0 ~ p

x r>-r (n) X

~ (n) X

(n±i) (2.5)

P(n) is called the transition-matrix of the n

^

transition;

yn) yr is the probability that the wandering point, if x is

•j" its [n-i ) state, (i.e. x nt = x ) will jump into an element of

X (i.e. xn

e X ). The probability, under condition xn J - x , that x n+1 eX is J

P

fc/f) * , for which we shall write, using

the matrix notation discussed in greater detail in the Appendix

definition 8,37, ?+o)x * Generally we have for n z i

P[ (2.6) xn-r** e X/Zn-T = *] = (Po) • -

* Pn.^k))X

the matrix-multiplication being associative. (Cf. Appendix § 8,

lemma 5)

.

The Markoff process is stationary , if all transition-matrices

P(n) are equal to one and the same matrix P :

* 20 x

wX ~ ^

X

(r> £ 0 (2.7)

The matrix defined by 2.6 then simply is the k

^

power P

A of

P , independent of n . The asymptotic properties of general

stationary Markoff processes have been studied in an excellent

paper by W.Doblin (1940).

An important special case is the one in which E is the set

of all real numbers, and in which the Markoff prodess is invariant

under translation, i.e.

p _ P

*

(n)Xi- v

~ (n)X ( 2 . 8 )

for all real numbers v . Putting p ~ P

° we have then

(n)X

Such a process is sometimes called a "process by independent increases" ( i . i . -process ) , as the coordinate of the {n+7 ) ot state

is the sum of {n+i ) independent stochastic variables:

X n = Pa + Vi + + Pn ( 2 . 10 )

yk being distributed according to jo ^

term "invariant process".

; we might prefer the
i\
10

More generally we may consider the case, where E is an r -dimensional Euclidean space. Then, defining an invariant process by

2.8, where now x and v are vectors in r dimensions, 2.9 remains

valid. The same is true in the still more general case, where E

is an arbitrary Abelian group, additively written, x and v- now

being group-elements.

The case where t is a non-abelian group can be considered as

a specialization of the still more general case, where a group of

transformations of E into itself exists, which is transitive over

E , and under which P is invariant (Cf. Appendix, § 9)*

3 . The Collective Matrix of a Stationary Markoff Process in an

Absorbing Medium .

We consider a stationary Markoff process in a set E } determined by the transition matrix Pj* . We assume that the wandering

point starts from a given state x , that whenever it is in a

state y , there is a probability A

y that the process will not be

continued (we say then that the wandering point is "absorbed" in

y ) , in which case there is a probability i-LC* that the catastrophe C will occur; and a probability B = i-A y that it will be

continued, in which case there is a probability /- Ty that <f will

occur

.

Instead of the total probability C that E will not happen we

introduce the conditional probability C

x that the wandering point,

if starting at x , will be absorbed eventually without a cata -

strophe having happened.
I
11

It is easy to compute C

x

. The point being in x , it is

either absorbed at once (probability A

x

), in which case non- 5

has probability ZC

X

* or not* (probability 3

x

) in which case the

probability of non- is T

x

. But then it jumps to some point

y (transition-probability P^y if <^y represents a "small set"

containing y s namely a set on which the variation of the integrand is small)* and then the probability of eventual absorption

without P is Hence

C

K,A X U

X

+ B*Txf C

y . (5.1)

In order to obtain an expression for the solution of this

equation we introduce the "collective matrix" * which denotes

the probability that a point* starting in x * will eventually

be absorbed somewhere in X. * without a catastrophe having happened. The equation for C^- corresponding to 3-1 is now

CX” A

*u- T / r

cc</

If we make the assumption that a catastrophe can only happen

(with probability i- T

x

) in a state where the point is not ab~

sorbed* we have to substitute VC

x= 1 , and the equation for C

is specialized to

CX= A

*fx

* s*ryp* cy . (5.2)

The total C

x (for general ZC

X

) can now be expressed in this

yt X

specialized by

C*= C*(U) = / C^u y . (5.5)

12

We consider in particular the case where the local absorptionprobabilities A * have only the values o or 7 .If then A is the

set of all x with A

x

= 7 s 3 its complement, we have

, b*./; . (3.4)

Substitution of A into 3.3 gives in accordance with the

definitions of the diagonal matrices

( a )x — AnX - d • lx ( 8 . 7 )

( / ) x € /* _ / * / x

v B <x

- ' Bn X - 3

' '

X

(T )x =" TX/

x ( 8 . 8 )

and of matrix multiplication

(Q p)x g/Q« PZ ( 8 . 57 )

considered in greater detail in the Appendix § 8 , the equation

Cx=(lAx+ (/* TpC)x

or in matrix notation

C = U + 4 7

" /D<

- • (5.5)

Multiplying both members of 3.5 from the left by and and noting that 5 4 U ~ U j 4 ^ -

4

j we obtain the important and

often used identities

13

4 <?- U > 4 C - 4 77>C . (3.6)

From 3*5 we obtain by induction

c = r oB TP)°/a » (/s TPfc

.

( 5 . 7 )

Now, assuming first /I T// = Sup T

x

< / , then by 8.42 of the

xef

Appendix

H(IS TP) "c//i ///BTP// 7c/a //T//

N

( 3 . 8 )

as H/g // ~ 1 (unless B=0 s which trivial case we exclude), II Pll=r 1 and ilC //~1 , C£ being a probability distribution. Hence the second term in the right member of 3.7 tends to zero, and

C ,p(/s TP)'’/A , (3-9)

where the series converges if HT/!< / . We know, however, only that

Nth* 7 . if we replace T

x in 3.9 by^7" x

, e being a real

number, the series in the right member is convergent for ds e <

i

, hence an analytic function of 0 .As all its terms are =

o

and

its value, being a probability, remains * i , hence bounded for

0 = O < 1

, the series remains convergent for 6 ~ 1 also, and its

value remains ^ 1 . Hence 3*9 holds not only for H

T

/! < 1 , but

also for H TN= 7 . We may then drop (if necessary) the interpretation of the T

x as probabilities, and replace them by arbitrary

complex values. Then C becomes a (complex) analytic functional

of T , defined (at least) for //T//= 1 . For NTH< 1 we can write because of 8.50

14

c« 0~'b TP)~'/a

(3.10)

Multiplying both members of 3.9 from the right with /A we obtain

the identity

CIA = C , (3.11)

which expresses the fact that absorption occurs in A only,, i.e.

that

c

x

sCA n x • (3 - 12)

For 7~ x=7 (i.e. if no catastrophe occurs at all) 3.9 implies

the total probability of a point., starting at x , being absorbed

eventually somewhere in X . For the special case where E is the

TD -r~\ St set of natural numbers, so that / „ = 2L r,. .where

x y€x y

( p if y - x. -t-i P* s l (3.13)

i t-p if x~ r

and =o in all other cases, and where JB ~ jx€ E/ o < jc < a+b

J

, C

y

with rE r for (/=x-cc and solves the classical problem of

the Ruin of the Gamblers. In fact, 3.9 is essentially equivalent

with Abraham de Moivre's classical solution. For 7~ x= 7~ = constant

we obtain the generating function belonging to the problem of

Duration of Play. The generalization which was used in Wald's and

Barnard's original theory of Sequential Analysis is obtained if in

3.13 the conditions are replaced by and y

= x _ <x respectively, oc and /3 being natural numbers, whereas 7~ x= 7~ .

In particular the generating function used by Barnard corresponds

to the case ot = 7 , /3 > ; . More general cases were studied by

15

D .Blackwell and M . A . Girshick, G.Blom, M. A. Girshick and J.H.B.Kemperman. The latter considered the general i.i. stochastic process

in a Euclidean n-dimensional space, and studied in greater detail

the case where E is the set of all integers and ~Py = arbitraoo ry (but, of course, with 25 px i ). Also the case that a wan- - oo dering point will come somewhere in a set A 1 without having been

in a set A2 before, is contained in our general formula, by taking A-A 1 uA2

, X. = A j

. Some applications of the use of non-constant

/ will be given in section 6.

4 . Two Absorbing Regions .

We shall now establish a relation between the collective matrix belonging to an absorbing region A 7 , with the one belonging

to a second absorbing region A2 , contained in A 7

. We may think

of two kinds of wandering particles, those of the first kind being

absorbed in A 7 , those of the second kind in A 2 only. We shall

denote these two collective matrices by

^ and ^(a2)

respectively, and we shall prove:

Theorem 1 . If Af b A 2

, then

^(At ) ^(A2 ) ~ C(A2 ) - C(A 2 ) C(A f ) * (^* 1 )

We remark that the theorem applies if A f =A 3 , and then states

that C is idempotent (a "projection-operator"). The equation

4.1 suggests an analogy between the matrices C(Aj and spectral

operators. These matrices however are not additive in the sets A

Proof : The second equality in 4.1 is trivial. It makes use of the

fact only that by 3.11

16

C(A J

~ C <A z) 4a > (4.2)

and that by 3.5 and 3„6

CCa,) = 4, r 4s, Q/,) (4.3)

Now the definition of matrix multiplication 8.37 implies for

the diagonal matrices /x and /

y

/ /

/ 'x r = / Xn x

hence,, as A2 c Af and therefore c JP Ar\]~>-

Ay ts[zz <€

(^.4)

A ~ ^

(^.5)

4, 'A3 = /s2

/S r = /

3, (^.6)

^ - /b7 ^a 2 ~ o (^- 7 )

/a > 4, = 4, 4, = 4, - 42 = 42 . 4 ?

( 4 . 8 ) Prom 4.2, 4.3, 4. 5 , 4.7 we obtain at once

Q/i 2

) C(Af) = ^Az) ^A 2 ^Aj + C(AJ(/Ax /g j)C(Aj) =

G(a 2 ) U2 + o = C(a2 )

.

For the first part of the equation 4.1 we shall give two

proofs. The second proof * which is purely algebraic like the previous one, will be given later and in a slightly generalized form

so that it yields simultaneously another result.

The first proof is based on the probabilistic interpretation

of C(Af) and C(Aj

.

^(a 2 )x 4 s the probability of the following event uf : a point* starting in x * arrives ultimately in A

X

without a

catastrophe having happened and is absorbed there. Now consider the

region D= A 1 nB> 2 , i.e. the part between A 1 and A 2 . If <J°j

happens* then the wandering point may either have or have not passed through a point of ID . The two cases being exclusive and exX

(A ) X the sum the corresponding probabilities.

In the first case the probability is the same as if the larger

region A 1 had been the absorbing one* and it being required that

the point be absorbed* not only in DC * but in Az o X . Hence its

probability is C(A t)A 2 nX ~ ^(a 7 ) ^2 )x • In the second case there

is a point ye i) * where the wandering point comes for the first

time in D . The probability that it will arrive in any "small

set" dy is the probability of being absorbed there if A 7 had

been the absorbing region* . This must be multiplied

with the probability that the point goes from y to a point in

A k * A z being the absorbing region (always without a catastrophe)* i.e.* C(A

k )x * and integrated over y . Together we obtain

(4.9)
mmmMaaiiMaaiiiiiIi
- 18

or In matrix-notation

^(A2) ~ C(A 7) + C(a t ) 4> C’(A3) • (4.10)

But /D = /B* _/g?

, Qaj/a/s^ ° 3 hence

C(a2) = C(A t )(/a 2 + !b2 Qa*)) = C(A;) C(a2 ) by the identity analogous with

4.3. Hence the theorem has been proved.

Before giving the second proof we consider a very special

case. Let £ be the set of all integers. The integrations can

then (and generally if £ is countable) be replaced by summations

and we know the matrices and functions of the second kind if we

know their values for the one element sets X. only. Let £>2 be

the Interval - a < x. < 6 , and £r the interval ~ cC < x < £ , where _ a. <„d < o < b (a ,

6

and a? are positive i ntegers ). Further

we take x=o and X the set with the one element _ £ , with

_i ( v integer). Let further the process be invariant , so

7p X Tp xM

that / y

=? ry+t =Py.x f

' or integers and . Then 4.9 becomes with y- -/ :

(4.11)

where = £ns {x-hf / x$ A 2 J .

With a different notation and 7~ X

r- constant this relation was

found by J . H .B .Kemperman in his Amsterdam Ph.D. -thesis (p. 71).

By means of 4.10 C(a

3 )x can be found for all x and X if the

matrix is completely known, and Q/j 2 )x f° r x € -& only. By

iteration like in section 3* however, we can express £~(a 7 ) complete-

- 19 -

fcy by c(a ,) • As c r«4,; 4 CfA 2) = C(A)) /a2 =• C(A/) /£>z T PC(A:l)

by 3.6, 4.10 Is equivalent with

C(A 2 ) = Ch4, ) U 2 ^ Q/ fz> TPC(A . (4.12)

By means of the same iteration process as used before, this

yields

C(a 2 ) = c(a ,) f fe TPC(Ar) ) n

/Ai , ( 4 . 13 )

or, by 8.50 if /7~//< 7 :

C(A 2 ) - C(A 7 ) (' - 4) 7~^°Qa j) )fA a ( 4 . 1 4 )

For the special case /4,-£- hence -B, = <3 , Z)-&2a C^/)= / 5 this

leads back to 3.10.

The solution 4.14 is particularly simple if D cons'jsts of

one point d only. Denoting the middle factor in the last member

of 4.14 by / -t- Q , we have thus

(/-tatTPC(A' })(UQ). / ( ^ - 3-5 ) or

Q’kTPq^+^TPC'vQ,

(4.16)

showing that vanishes unless x = ai , in which case

i . e

.

v f rv;- r T'g>;

.

20

QjT- t *{<- Td(rc(X} "faJx

The solution 4.14 then becomes

(4.17)

C * C

*

, C * O

*

( 4 . 18 ) W-UX = ^(A,)A^X + 'a,) CL

•

If £* is countable, 4.17 and 4.18 give a recursive method

for computing successively the C(A ^ if we take Ba= o (whence

C(A )=/), and add successively one element each time to J3n . We assume, for simplification of the notation, that the elements x,y,z,... of £ are the integers /, 2,3 ,

. . . themselves, in the

order in which they are taken into B , so that Bn

i , . .

. ,nj , An

=^n+i,n+2 ,., .J and abbreviate C^A j by Cn . Moreover we remark

that for yin

Ck> /7_ 7 (pc„J£-£p;(c„j; *Z?:(cn_,\ P;

as (C„_ r )y = o if x ~ n unless x = y . The recursive relation then

becomes (Cn )^ = 0 if y$n and

0.19)

if y £ n+i ,

where we remind that (Cn_ 7 and (cj; are functions of the infinite number of independent variables T \ T \ T\ . . .(the superfixes are not exponents'.)

21

5. Second Proof and Wald's Fundamental Identity.

The second proof of the first equation of 4.1 can be given in

several ways, and consists just in verifying 4.1, 4.10 or 4.12 by

means of 3-5* 3*9 or 3.10, applied to and C(Ai)

. We choose the

following form. For 3.5 we can write / - C = /a _ fB TPC or

4 (/- TP) = 4/. 4 rpj(/- C) , (5.1)

or if //T//<7 3

/-C = (/- 4 TP)~’/b (/. TP) . (5.2)

Hence, if we multiply both members from the right with any

bounded matrix D , we find that

CD=Z) (5.5)

if D satisfies the identity

4 (/-TP)D=o. (5.4)

Now taking like before = 3, , D= C(A j

, 5.4 is satisfied.

For, by 3.6 C(a2 )~ if both members are multiplied from

the left with /Bj , 4.6 proves 5.4. Hence 5-3, i.e. the first

part of 4.1 is true.

The identities 5.1* 5-2 lead to other interesting results.

As the set ?C on which depends is irrelevant as long as D

enters into the equations as a last (right hand) factor only, we

/

) *

of the first kind.

Then formally our previous result 5.3* 5.4 becomes:^* satisfies the equation

(5.5)

22

(i.e. £ is an eigenfunction of C belonging to the eigenvalue 1 ) if

i.e. if

f

x

= T

x

(Pf)

X for xe3 . (5.6)

On the other hand., if 5-5 is satisfied, 5.2 shows that also

5.6 holds. The result that 5-5 is implied by 5.6 is valid if £

r ~ is bounded, and the series occurring implicitly in C and in the

right hand member of 5.2 are uniformly convergent. For this it is

sufficient that l/lB TP!B //< 1 , i.e. that JT X

/ <('D

B )

? for every x

in B , or, more generally, that U(fa TP L)

n

if < 1 for some n.

In the most important application, however, ^

is not bounded,

and then associativity has to be ascertained in another way, say

by the conditions of Lemma 4 (Appendix § 8) . Y/e have then:

Theorem _2. If_a jr = 0 aiLcL- a 7 o exist such tha t //7

D

^// <co, thajt

CsT *Wx (5 - 7)

and that

!lis T0 PIB i-ll!s To Pj/J/T0 P3 i

B si , ( 5 . 3 )

then for all T

x and with j

*/< a nd with / T

x/$ B T* for

all xeB with o < e < i , c being a constant , the e qua tions 5.5 and

5J5 jare e quivalent . [

5*]

Proof: Y/e have by f. H I'or n ± i : //(^ TQ Pj /B

//s 1

5

//$ (i/r/P)7s i+fl%(iBlrlP)

n

iB lTlT>ll s

5 Gf. J.H.B .Kemperman, theorem 1 and 2 (p. 15, 14) for the case,

where £ is the real axis, the process invariant (but not necessarily stationary and A a half-line.

s ( + | e"

f'//

l

B z P/s 7/7/4 4 * ©C- er 74 4 Pff .

so that C and the right member of 5.2 exist absolutely* and are*

moreover* bounded. Hence* with P tf. Z. (lB

{Tj P)

n

3 P is bounded and

= 0 * and (P/ft/

)

exists for all x as it is

s(ZOB /T/p)

n

/f/)

x

s c$PceZe*0B zr/B r(/B To P)f; g

s C.//U.C eO-e)-’///3 r,P//fo x

.

In the same way(RlT/Pljjl)'^exists* hence also (/?/'LTPjjfrj

)

X

* and*

similarly (Cfi)* . Hence the conditions of Lemma 4 (Appendix § 8)

with instead of F

y

(for any fixed x )* / (/-TP) instead of P * are satisfied and we have

/- eg . 0- c)S - />4 0- TP)jf -{* 4 h- tp)s} = o

if 5-8 holds. The transition from 5.5 to 5.8 is similar and even

simpler

.

We now shall apply this result to the case of an i.i. process

We take * to be of the form

X , f X

/

= e and T

x - T - constant

and /being real or complex numbers.

Then with (cf 2.8)

t> x /" /x+v H

X ~ J Pd^ 'x

we have

(5.9)

(PS)-VW~’V/w -

(5.10)

(5.11)

where

c?; = fpdxr 2 ( 5 . 12 )

is the characteristic function of the distribution function.

The interchange of the integrations is certainly allowed if the

integrals in 5.11 converge absolutely} i.e. if 5.12 converges

absolutely^ i.e.* if <^(Pe^) exists . Hence we have proved

Theorem 5. For_ each § f^r^ whicji extists_> £

x=q^x is an

eige nfunction of the i.i. matrix P , satisfying 5.10* bel onging

to the eigenvalue <?(§

)

. Substitution of 5»9> 5.11 into 5.6 shows that the latter

equation is satisfied if and only if

(5.13)

(as soon as 5 is not empty) 5 and then holds for allxeP (not

only 65 )

.

In order to apply theorem 2 we choose being

real and such that PJ° , hence ^(f0 ) exists,, and TQ

X

-

7~

0 = const.,

real, > o s and The last condition, hence 5.3, is always

satisfied if T0 ~ 1 . Condition 5.7 (with equality sign) is satisfied if

To*(to)=i (5.14)

Further we take a T and satisfying 5.13 with J7~/T0

~ 7 =e< 1 3 and

such that (fo _ Pe$)x z -tn c for all x in B . Then., writing

C =Z. T”C(„) j (5.15)

so that C(„)x

is the probability of absorption in 3C following the

n -th step, we have

<7 -'C£)

X

‘ e r "fCm (5.16)

and. we find that 5.13 entails., for ,x=o , the left member of

5.16 being equal to 1 :
II

II

II

' II

II

'll

II
25

l'e(trnJC,n>Zv

e*".->. (5.17)

The identity 5.17 is known as Wald's Fundamental Identity.

We have seen that it is a special case of the identity ££- £ > which holds for all £ , satisfying £

- 7~P£ o nB under the conditions of theorem 2.

A partial generalization for arbitrary stochastic processes

is considered in the Appendix ( § 10)

.

6. The Prob lem o f Loops

We consider a stationary process without absorption. As,

however, we want to consider properties of initial segments of given

length n of the path, we have to admit discontinuation of the process at any moment. We start therefore with the expression 5*1 and

substitute

B

x= B = const. , A

X =/_B ( 6 . 1 ) where B is an auxiliary variable. Moreover, we take U\ T

x and 3. fixed Initial point x - ct . We obtain

C

a

= Z B

n

(l-B)({TP)n T)* (6.2)

so that not C

a but C£ (/-B) is the generating function with B as

variable

.

For some applications of the theory of Markoff and other stochastic processes, e.g. in the chemical statistics of longchain

molecules (cf.e.g. G. King 1948, 1949, E .W .Montroll, 1950, Ch.M.Tchen,

1951, J.J. Hermans, M.S.Klamkin and R.Ullman, 1952 and- the literature quoted there) it may be of some use to have methods by which

26

the occurrence of "loops" In the path, i.e. of returns of the wandering point to a state where it has been before, can be studied.

Without going into these applications and without prejudging its

workability or its ability to yield non-trivial results In

practically important cases, we shall outline sich a method here,

which in any dase might give a line of attack of this and similar

problems, and is apt to be generalized for adaptation to other

problems

.

Evidently the probability of coincidence of x^ and x

i

for

k /

£

is zero if the xk have continuous distributions

.

In order to avoid irrelevant complications we shall assume, that

these distributions are purely discontinuous, i.e. £ is an

enumerable set. In some of the applications mentioned E is such

a set, namely a point-lattice (e.g. a tetrahedral lattice) in

space. According to Appendix 8.1 the transition-matrix then

is completely determined by the ordinary (infinite) matrix Py

(xe E * y eEj, and the integrals like

///^x /

>x pass into (in general

infinite) sums Z Ex £

x

. C

GL now is an analytic function of an enumerable infinity of

variables T

x

, i.e. of a vector in a infinitely dimensional space.

The partial derivatives of a function of the T

x with respect to

these variables can be considered as the components of another

vector, the gradient. We shall denote the differentiation-operator

by V with

a dTx (6.3)

The suffix is written as a lower one because 1° in vector-analysis

the derivatives with respect to a contravariant vector form a co-

27-

variant vector,, 2° the generalization of 6.3 to non -enumerable E

will be found to lead to functions of the second kind.

If

C = Zpn T

n (6.4)

is an ordinary generating function (Tn being here the n -th power

of T) of the probabilities pn = P[n =nj of the values taken by a random variable n , the successive derivatives of C with respect to

T give for T- 7 the successive factorial moments:

(6.5)

/ = k, npn = Cn (6.6)

T=i

~J ^Zn !s

pn =%n /2

(6.7)

J

T;1 where 8 is the expectation-symbol* whereas

x (x _ 1)

. .

. (x -k + 7J

(6.8)

denotes the k -th "factorial power" of x . By writing out the implicit matrix-summations in 6.2 we

get an infinite sequence of terms,, each of which is the probability

of a definite path of length n * multiplied by T

x

°. . . T

Xn B

n(LB)

.

If the path passes k times through the state x * application of

Vx and subsequent substitution of T=

1

gives k times the probability of the path. Hence* i f /? denotes the number of times a path

passes through x * we have

V

L x c

* CL

T= i = £ Ox (6.5)

In the same way we find

- 28 -

fy*

Cnx

2 if y=x

ZquOk if y*x

( 6 . 10 )

etc .

It follows that

2. [iKvx c^]

xat T=r

i 'e T

j n

xsE — X ( 6 . 11 )

Now if n^o or nx = i , then p^2 =o j if n = 2 , i.e. if x is a double point of the path., then f nx = i . Hence 6.11 gives the

expectation of the number of double-points in a path,, a triple-,

quadruple-, /c-uple point being counted, as usual in algebraic

geometry, as 3>, 6, ±k(k-i) double-points. Hence, we have proved

Theo rem 6 : Lf D denotes the random variable which on each path

e qua ls the numbe r of double-points or loops, counted in the afore

said manner, we have

ZD =[in C

a

]T > ( 6 - 12 )

where denotes the generalized Laplacian operator

oif Z(vx y = L (£.)* . X.HE xzE

(6.15)

Similar relations, of course, hold for the number of triplepoints, etc.

In the derivation of 6.12 we used the fact only that C

a

is a

power series in the T

x

, but not its special form 6.2. Hence the

result holds fbr arbitrary non-stationary and also non-Markovian processes also. In the special case 6.2 the left members of 6.9* 6.10

and 6.11 are easily computed. In fact, we have

- 29

7X

((TP)

n Tj = £r(TP) m

/x (P r) n~ m

(6.14)

v«vx ((rp)”r)=2M& (tp)

k+£-pm*n % PCrp/- 1 /K (PT)m

Hence we obtain

+ 2HD (Tp//X P(TP) {- 7 /(P7T

.

kP+rr^n * (6.15)

fiaCi *(lb)23S (p*) a(p''*')*(p m+)* , L 2. •‘Tsi x«£ •* x £

But (PT)*^JP£y T P* = i if T \-

1

for all * . Hence

= B(/-3y’ and 6.12 3 6

.

16 may also be written as

( 6 . 16)

TBm(Pm)* =

ZD—

= BZxe£ x x 0y (6.17)

where

?* if (iB"Pn)* = (0- Sp/’ r

y

(6.18)

In the special case., where the stationary Markoff process

is an invariant one, 6.17 simplifies still further. For in that

case $x is independent of jc ^ so that the summation is extended

over only and gives 9£ . Hence for an invariant process

6 . 17 becomes

ZD = 3(/-B)~'($°-i) (6.19)

Expressed in the conditional expectations Z(n) D> for given n „ the

GO left member of 6.19 is 3

n(L3jZ(n) D 3 so that 6.19 shows that

t(n)D is the coefficient of 3

n in 3 (LB)

3($°- i) , hence

t(n) SD(n-0(P): . ( 6 . 20 )

~ 30

Here (Pm)° is the probability that a path of length m will be

closed* i.e. that its first and its last ((m+i)

th) state coincide

(whether it contains double points or not) . Like so many simple

specializations of general theorems* however* this result is trivial: in a path of length n a loop can have any length £ * and* if so* it- can begin at the t

si\ .

. . point; in the

case of an invariant process these cases have equal probabilities which are equal to (P^J° * i.e. the value of the if -fold

convolute of pv

(cf. 2.8) for the value v = o . The method scetched here can be generalized for arbitrary

stochastic processes and applied to other problems than the expectation of the mean number of loops

.

For an arbitrary functional of a function T

x we define

(cf. Hadamard 1910* Frechet 1912* 191^* Van Dantzig 1935)

V$(T) S (&) v / / = i&lQziW (6.21) x £ M o a

'

if this limit exists. Under certain regularity conditions ? which are

e.g. satisfied in the case of an analytic § * this quantity is

a countably additive function of the set X . The dual definition

for a functional $ of a function Vx of the second kind would be

(£ ) X

f( V) = iim

( 6 . 22 )

yielding for sufficiently regular & a function of the first kind.

For a matrix P we can define

( dp/A

P(P) ~ tim

o $(p+s/A r)-¥(p)

£ (6.23)

31

where (/A

/ a

J.x = /A J* is to be distinguished from = =//* . In this paper we shall have to do with 6.21 only.

Applying the operator Vx to the general stochastic process

C ~0-B)22 B

(n) P d* ~2 Xc

• w"\'?.7 T

•*/?-

1

(6.24)

from which the'special case (6.2) is reobtained by the specialization

(2.5) with a P(n) ~P independent of n and Po>x - 6T s we obtain:

^x CJt„ - S ^X . (6.25)

where the random variable n for any given 36 is the number of

.A. times that the process passes through a state in X . For X=£

n - n is the number of steps made until the process is stopped

In the same way we find; as a generalization of 6.10

Z(?x ar -nXnY) (6.26)

In the case of continuous distributions of the jumps, the problem

of loops becomes trivial: their probability then is zero. We can

however consider related problems, e.g. the question, how often a path returns into states within a given distance from one of its

previous states, without any pretention that this can be used for

the solution of the generalized problem of loops ("almost loops"),

which to give a precise form seems itself a rather hard problem.

We shall suppose here that E is a Euclidean space, or, more

generally, a metrical space, where any two states .x and y have a distance, denoted by . More generally we may take any two-state

function (apart from conditions of integrability) , and form

the operator

nu P ff2 v v

(f) - Jj

> vdx vdy (6.27)

- 52

which passes for the case of a finite set E into the generalized

Laplacian

(f) = Z

7 2? p lj i>_

d T

i a TJ ( 6 . 28 )

where the f

LJ are constants (independent of the 7" 1

)

, Under sufficient regularity conditions the order of the derivations may he

interchanged^ so that 6.27 then vanishes identically for an antisymmetrical -P ( f

xy

= _ f

yx

) . We shall therefore restrict ourselves to symmetrical f ( f

xy ~ fyx

).

Provided the interchange of integrations is allowed,, 6.26

gives

:

(i D(f) C)r„

~ i ^ If-"CL.

x

- i f

x x (6.29)

Here the integrals after the second and the first expectationsign respectively become for a path of length n _ 7 * passing,

times respectively, through r different points xfi ,.. y xr , (so that n ~ 23 n. / x*

v -x T -c ) x

‘

-f XX

= ZJ

1 Oi P (6.30)

Jf-ndx Ody

U H n • r P -J

1 1 ~ ‘ (6.51)

Hence the righthand member of 6.29 is the expectation of

£ i LL n f**J , 21 i (nc - ,) f *

4 y 4 (6.52)

This quantity is the sum of the P-‘-I ( 4 ,y' = ) over all

pairs i ^ j , together with the sum of the P

-< -< over all multiple

- 35 -

points,, counted as multiple double points like before.

The second term vanishes identically

1° f

xx - 0 for all x , e.g. if P is the distance z xv of x and y , 2° if n . takes the values o and i only (except for

a probability o )

.

In the latter case, which occurs always, if the transition

probabilities have continuous distributions, we can omit the x t

-

with n = o , so that n. = i for all i and 6.32 becomes

(6 ' 35)

where the x t

- are the n(=r) different points through which the

path passes. Hence in this case the operator 6.29 gives the expectation of the sum of the values of P for all pairs of different

points of the path.

If in particular P

xy is the distance z xy of x and y , this

2 - (- ~ 0 times the mean distance taken over the path of

any two states through which the wandering point passes.

If, instead of P

xy - z xy

, we take for •/* the characteristic

function of any relation %(x,y) between two states (e.g. Rfay)

g (z^s a), where CL is a non-negative number), i.e.

r* = /

1

t o

if R(x 3 y) holds

if not.

(6.34)

then 6.33 becomes half the number of ordered pairs of different

states in a path for which P(x,y) holds, (e.g. which have a

distance * CC )

. In the case of a symmetrical relation this is the

number of unordered pairs.

- 34 -

In the stationary Markovian case we again can easily compute

the left member of 6.29. Like before we obtain for a symmetrical/5 ^

i

(?)

C = (7-3)2— B k., m

-t-m

'J/((TP)%Jp(TPf% f**((PT)

For Tx

= / this becomes, as (P/) y then also equals i ,

i (a(f) C^.Q.BXZZ B

k^mJf(P^(P% f*" . (6.35)

rZp Z j tTl

For the case of an invariant process, given by 2.8, this simplifies

still further, if /°

.

We have then

Jf(p

kUp<X

Z fJx+v

cix J a

( being the €*** convolute of pz ), as J/^^i and Jp^- 1 - Hence the coefficient of (/-B) B

n

, becomes, as if must be £ i ,

i £ (n-Ofp%f v

. ( 6 . 36 )

^ iPj 1 J

Like before, this relation can easily be proved in an elementary

way.

If /* y has the Fourrier transformers : ?

v=je lvtXSt)d* , (6.37)

6.36 becoraestoecause of JpB

qCV

- '

, where

^

g?JPdv e

‘ w ,

35

t(n) i Z = Z (n-{)J<e(ty ^(t) cu =

= f

(ZlbZL ait . J 0-<e(t))*

For a given p and f , hence <£ and % , 6.38 gives the

expectation in the form of one integral.

( 6 . 38 )

required
I
APPENDIX

§ Ll F

u

nc tio ns of the Firs t_ and the Second Kind

According to Kolmogoroff a probability field on a set E is

given by a countably additive set function on E , defined and

non-negative for all sets belonging to a 6 -field 0Eof subsets of

E , and taking the value 7 on E . More generally we shall,. instead of a <5 -f ield ^consider a

-field (according to the terminology used in Hahn-Rosenthal)

,

i.e. a system of sub-sets of E which has the following properties :

\. is a field (i.e. contains with any two sets .X and X

their union ( " join" ) Xu'Y , their difference( s ) which we

denote by X--Y and Y--X respectively, hence also their

intersection ( "meet" )X/1 Y ; ii. cf£ contains the intersection /? Xn of any sequence (Xnj

of sets Xn contained in it

;

iii

.

E is the union of a sequence {EnJ

of sets belonging to

^E • n It follows by replacing En by UEk , that we can assume without

restriction that

Em-7 D E

n

> En 6 d£ /or all n } (7.1)

whereas i and ii imply that the union X=C/Xn of a sequence (X

,

nJ

of sets belonging to 6£ belongs to if (and only if) all Xn are contained In some Ye S£

. For in that case XcY and

- 37

Hence <fE is a. 5 -field if and only if £ e 6£ . The use of a cf -field instead of a <5 -field has the advantage

that function-" values co (cf. e.g. Hahn-Rosenthal , Halmos, etc)

may be avoided.

Generalizing a terminology introduced on a previous occasion

(D.van Dantzig, 1935) we define a function o f the s econd kind as

a real function F , de fine d and countably additive on . We

denote the value which F takes on a set 3C by Fx . Calling a sequence of sets d£ which are mutually exclusive and which

have X s J£ as union a dissection of 3C , and denoting this by

{Xn J

e D(X) , hence

(

X

n }

e D(X) = U

X

n =r X 3 and Xm n Xn =0 // m ? n (7.2)

(O being the vacuous set), we then have

{Xnj 6 -ZW — Z rXn = Fx (7.3)

The absolute-value function of F which itself is a function

of the second kind, is denoted b y/Fj , and defined by

/fLyr £- SUP Zn /Fy. / . X (Xn}eL(X) {7X)

On the other hand we define a function of the first kind as a

real function P , defined for all xz£ } and bounded and cf -measurable on each X e <$£ . Hence, if we denote by P

x (instead of the

customary f(x) ) the value which / takes in x , and by FnsfeefjAMj

the set of allxs^T for which the statement A(x) holds, we have le

.

-X e cf£ —» /fPl!

X < co , (7.5)

where

m/ xa m

,

X€ X

(7.6)

58

and 2e

.

Ens fx. s X/jP

x

.1 cj e 6£ (7*7)

for all real c and Xscl,

The set functions HP//

X

are in general not countably additive,

hence not functions of the second kind.

We remark that lP/x

and HPHXare finite lfXecf£ and can be

considered as "norms" of F and P on X if X is fixed. In particular, if }F/£ and///£

are finite, they have the ordinary properties of norms of F and P on E .In the latter case we shall sometimes omit the suffixes E . More generally we may admit the values of F and P to be complex numbers, and in some cases even to be taken from arbitrary

dual Banach spaces.

The integral of P with respect to F exists on each subset

X e d'£ and will be denoted by

or shortly by (FP) . It is, according to well-known theorems, a

si. function of the second kind, satisfying the inequality

i(rf)/x £ Irljf/F (7.8)

for any X e <F . Also according to known theorems we have:

/ov)-(9?)/x £ /F. g/x

//s//

x+ /g/x ///-y/

x

, (7.9)

an inequality which is often applied. In particular, denoting by

•var P the variation of P on X , i.e.

var P sup F

X— inf p

x

, (7*10) X x e X x e X. and for any dissection {XnJ

of X :

- 39 -

(7.11)

( 7 . 12 ) This follows from 7.9 with Cj = F and = f

Xn if x e X. n

§8. Matrices

Let £ and £' be two arbitrary sets, on each of which a

<7 -field 4 an(3 of subsets is given, satisfying the conditions of § 7.

We consider a function P (to be called a generalized

"matrix", or more explicitly an (£„£') -matrix), determining a real (occasionally a complex) number PP. as a function of l

6

. an

element yef' and 2°. a subset X.€ <$E , subject to the conditions:

1° . For fixed X = Ae<f£ Pj? determines a function (denoted by PA ) of the first kind on £

' ; 2°. For fixed y=b<zE' determines a function (denoted by P

b

)

y\. of the second kind on £ .

If in particular £ is countably (finite, or enumerably infinite),

and if cf£ contains every set consisting of one element, we have

and if £' also is enumerable, P^ is determined by the ordinary

rectangular finite or infinite matrix P£ . The norm for fixed y

is given by

py = £ P*

X xeX x

( 8 . 1 )
S3Ii3i

l!I1aa8I1iI
- 40

!P*L = sup Zn/P* /. * Mem) X”' (8.2)

( 8 . 5 )

It is itself a matrix. Its norm for fixed X is given by

upipx

a

yesuEI mA

and is not a matrix in the above sense,, Y being a set instead of

an element of £'

, and l/Pllx

moreover not being completely additive

in X . The matrix P is called bounded if HZ//x

is bounded, i.e.

if

su^UPp=HPH* <cc . £’

X

' £'

'X ( 8 . 4 ) If E $ <f£ , then l/P/l* is not defined for X=.E . In that case we

take the equality 8.4 as a definition of IIPft/ . Instead of the symbol // P//

we shall also use the symbol IlFll .

In particular the sets E and E' may coincide. In that case

we shall suppose that the fields 6£ and also coincide. A

special case here is the "unit-matrix", denoted by / (iota), and

defined by

7 x e X

l* = / X to?/' not

( 8 . 5 )

For fixed X=A JA is the characteristic function of the set A j for fixed a / a might be called the "characteristic function of the

second kind of the point a "j it takes the value i on each set

containing a and o on each other one. Evidently / is bounded with

— 1 and

,X , X I x. X, X2 " XT nX2

( 8 . 6 )

More generally with every subset A e S£ corresponds a matrix,

also denoted by fA , and defined by

- 41

(/ ) * & /AnX (8.7)

In the case of finite £ = £' it corresponds according to 8.1

with a matrix having / in all elements of the main diagonal , the

suffixes of which belong to A , and o in all other places. Evidently /A also is bounded and /’/

'A //=i unless A is empty.

With every function P of the first kind corresponds a matrix,

to be denoted by P/ , and defined by

O'/)* = /*/* = l

P* ifxeX,

O if not . ( 8 . 8 )

In the case of an enumerable £ =£' the matrix which corresponds

to PI according to 8.1 is a diagonal matrix, having the value

P* in the element of the main diagonal which corresponds with . Evidently/1 / is bounded if and only if P is, and ////=/// ^

.

We now return to the general case, where £ and £' may differ.

Then let P be a matrix like before, and P a function of the first

kind on £ . Then for any Xe <S£ and for any fixed ye/', writing PPJ

for P(P/) , (ptO£jx ?L fX (8.9)

exists and is countably additive in X for/Ce^and measurable and

bounded in y on each Ye S£, , as

!lPfll/*sl/P/£//f// x

(8.io)

so that PP/ is a matrix. In particular (?/)*= (p//)/ , if it

exists for all y , is a function of the first kind on £'

, and

is bounded if P and P are

.

On the other hand, let P be a function of the second kind

- 42 -

on £?' . Then

Le mma 1 . For any X e 6£ , Ye 6E

>

=/r F^ Fx ( 8 . 11 )

exists and is a function of the second kind on cf and on <S

.

Proof: The countable additivity with respect to Y on S£ , for

constant X follows from that for . For constant Y (FP)y^

is trivally additive in X . For the countable additivity on cf£

if X

is a decreasing sequence of sets Xn

e S£ with empty intersection

We choose an e >

o

and define

it is therefore sufficient to prove that lim (FPY y = o

n~*co n

Bn = Ens{V sY//P«/Xn teJ.

Then, as /P y/ is countably additive and io for each ysF' , and as

X„,cX„, we have also 5W7 c . Moreover /? j&n = o , for if there

existed an ye/? Bn , then for this y //^/^ £ S for all n , contradicting the countable additivity of fP*j , as O

X

n -0 .

In the same way for all. sufficiently large n , /FJB^^e . Now,

if Cn is the complement Y—Bn of Bn with respect to Y then

But

(Fp)y,x* = (Fp)B„,xn

/(fpXxJs

/b

lFl*Yp

%„ zlrlsjmli s £C'

With C1 -=:llPll^ n

. And

/Mi.xn t* /

* /FF 11 pY: = ^ £

with C2 =/F/y , as Cn cY , and //P//^n ^sup JP*L 1 t by definition

1 xn ye Cn Xn of Bn and Cn . Hence !(PP)yx /- + C2 )

£

for all sufficiently large

n , £ >o being given, i.e.

lim (TP) = 0 , Q££> . S7-+ CO > > '"/7 It follows easily that for all X , Y

AFXx/£/r/

r /p/x (8.12)

If, in particular, F and P are bounded, then also FP is.

By means of the Inequalities 8.10 and 8.12 we have

Lemma 2 . A bounded matrix P transforms the bounded functions /

of the first kind on £ into such ones on £' and the bounded

functions of the second kind on £' into such ones on E with

ftm/s/p/M (San

/(FP)/ s/F/fP/

(8>l4)

(where the suffixes E and E' have been omitted).

Lemma 3 . If_ P and F are functions of the first and second kind

on E and E

respectively, and P is a matrix, then if X e 6£

and Ye $ , , fx

'{/

y

^ PLi ^ .

< 8 • 18 >

i.e. the order of the integrations may be re versed . Proof: If we put for arbitrary U s <f£ , Ve S£

, ,

7

-

' Pf jp fx c<-f p * / x p< y ct-f / ? p y

V - YnV » t ~ r 'a > U

- 'y rXnU (8.16)

then F' , P' and f' are bounded and 8.15 is equivalent with

IU ^ p*/£

r *- (8.17)

Hence it is sufficient, to prove the theorem for bounded

functions and matrices with the integrations extended over the

- 44

whole sets E and E' (which we shall then omit) . We omit the primes

and we may write 8.17 in the abbreviated form

(FP)t = F(Pf) (8 . 18)

We put then

PfHs , «•«. Sf f S* , (8.19)

I*. gx £

/

, ( 8 . 20 )

and we have to prove

qt*Fd , i.e. gdx f

X

=Js

, rctv 3* (8.21)

Let 6 >

o

be given. As £ is bounded, we can find a finite dissection with nsN and yar

{x j

f = £

(Divide e.g. the finite interval ("l///*, +I-PJ

B

) into N exclusive

subintervals Jn , and take Xn ~Insjx.^E/E K ^Jn

’j ). Hence choosing

the xn

e Xn arbitrarily, by 7.12

//9dx f*~Z” gx„ t

x:/z/g/t ( 8 . 22 )

As each of the N functions Pv is bounded, we can find a finite

dissection of E' (obtained e.g. by intersecting the N dissections

belonging to the Px

separately ) {Ym }<zD(E) (m M) with ~ ^

for all n s /V . Hence, choosing the arbitrarily, again

by 7.12:

/gXn - & FYm /

5 /Fj Vn ( 8 . 23)

and with 8.22 and /(y /= /E/EP/I

// *£ f*"/ sc,e (8.24)

with C1 ~ /F/(l/Pfj+ HE/lj . On the other hand

(8.25)

- 45 -

for every y e E' 3 in particular for y = ym . Hence

//f* PI )fx"/z/FlllPlU. (3.26)

But

// pl

- % r

xZ /= MVN (8.27)

P 5 */n . Hence , as n £ /V 8.25 - 8.27 give:

X-n //^ g* -lb Hr F^

m

P*” f

x"/?C,f. ( 8 . 28 )

From 8.24 and 8.28 we ob.tain

( 8 . 29 )

Hence, as this holds for every £>o , 8.21, whence 8.17 and 8.15>

<£££> . We need a sufficient condition for 8.15 to hold over the

whole sets E and E' where /u, P and f may be unbounded and prove

therefore along well-known lines:

Lemma 4. If

c ( 8 . 50 )

/> y «/ lf xl

( 8 . 31 )

exist for all X and respectively, and if either

J£

Mdx /fX

/ < OO J (8.32)

or

- 46

fa. '£• l^lcLa ” h < CO , (8.33)

then the o ther one of these two inequalities holds also, and

f / f t pv J t x / r f i ( 8 . 3^) J£ (

J£

' A

<*y

A *x f

+ = J£

. A

<*y

rdx. t •

Proof: It is sufficient to prove the theorem for non-negative F , P and P 3 in which case and/? = <7 „ According to lemma 3> 8.15

holds for 36=^ , Y- with arbitrary/: and { (cf. 7.1). Now, if

8.32 is satisfied, the left member of 8 . 3^ is

3 9<*

x * 4 4 4 {4 ^ ' '

x

-

4>

P S' f * ~ax ^

As the latter expression is non-decreasing if £ _> co , t?_* co , and bounded, it has a limit,, which is the second member of 8.34,

so that its existence has been proved, i.e. 8.32 and J£

<jcCx 3 * = 9

y •

In the same way it is proved that j Pgl<j$ v = f 9ax ^ 3 whence

8.34. Analogously in the second case,i,e. if 8.33 is assumed.

Lemma 5 . (Cf. R.G. Cooke (1950) page 29). If

,

F, , F3 , £3 , are

arbitrary sets wi t h corresponding cf -fields <£. , $£ , 3^ } 6£^

s if.

t , x , y , z and T , AT , Y , Z de no t e arb i t r

a

ry_ elements and subsets

of £7 3 E2 3 £

3

, 3 and <?£ 3 3£ 3 ^ j </f re spectively, and if M , P and Q are (F, , t 2 )~ , (F 2i £i )-

,

and fe, , Fn ) -matrices respec t ively , then

Jx U P^JM

r =4 <4 4 *

X

r ( 8 . 35 )

If, in parti cular

j

M , P and O are bounded, or If

J£ /p%k !m% , , JJQ%1P% . L* . y zy lM xlr

< CO or JJQ V«y P/ < 00 5 (8.36)
I

I

)

i

I

I

i

i

I

i

i

i

i
- 47 -

t hen th ma

t

rix -

p

roduct, de fine d_ by

(8.57)

( 8 . 38 )

is associative:

(QP)M= Q(PM) (8.59)

i . e

(8.40)

Proof: Follows immediately from lemmas 3 and 4 with, for constant z and T , F

y ~Qy and -f x

= M* . From this lemma 5 it follows that the ordinary matrix-calculus,, with Lebesgue-Stielt jes -Radon integration instead of summation can be applied as soon as all matrices and functions of

either kind concerned are bounded , or, more generally, if they

satisfy 8 . 38 . For simplicity we shall further omit (unless special notice

is given) the first case, i.e. restrict ourselves to bounded matrices and function of either kind, unless the contrary is stated

explicitly, and assume moreover that the sets E , E' , E

,

, E2 , etc. all coincide. In this case the increasing sequences Ek also

can be omitted, as we may take Ek = E for all k .

If P , hence, is a "square” bounded matrix, i.e. E - E' , and

- 48

Up// = Up//f = sup sup Zr /p* / < oo

£ , (8.4i)

{xn }e2>(£) n V '

then powers of P and polynomials in P can be formed, and as long

as the coefficients are constants ("scalars") these are commutable.

From 8.13* 8.14, 8.37, 8.4l follows easily that

IIPQ.II SlIPlIlQI! . (8.42)

We note for later use the following identities:

F/ = 7 » 7

‘ e - /Fcu * Fx >

( 8 . 43 )

/

If* f , '.«• //„'

^ ; (8.44)

IP*PI*P , Pi = fPty * Px (8.45)

Further we remark that any two diagonal matrices are commutable:

Ay; -/vi; . /v/y . (8.46)

We can, however, not replace the symbol 77 for the diagonal

matrix by // , which denotes the function of the first

kind 8.44. If /V is followed by another factor (matrix or

function of the first kind) we may omit the / , e.g.

f / P = tP with (PPj* =

/' * PJ/ , and also (fy)

x=(f/j)*= Z q*.

The integrals over subsets of £ can be expressed by means of the

partial unit matrices /A (cf. 8.7)“

(8-v)

The partial unit matrices also serve the purpose of truncating functions

:
•
- ^9 -

if x e -4

if not

(8.48)

(FU)x = FAnX

if XcA

if Xc E-A (8.49)

and analogously /A P/a . oo A sufficient condition for the convergence of Z.(Pn )£ (where

the Pn are bounded matrices) for all * and X is the convergence

Of z llPnll -

It follows in particular that if //P// < i 3 whence by 8.32

llP

n/ls!/P/l < i

^ denoting the /7-th matrix-power * Z P

n

O converges and is the (unique) left and right-handed inverse of

/.. P : oO (7- P)'

1 = Z P

n

, 7 / //Pll < i . (8.50)

More generally* if a matrix M can be brought in the form

M- P + Q (8.51)

where P'

1 exists (we use this expression only if PX = XP- / has

one and only one solution X = P'

1 ) * whereas either //QP~'/I< 1

or fp'

r Q/! < 1 * then M

1 exists and

M-Pp- rf(- QP- 1)

n

=L(-P~', QTP~\ (8.52)

i The proof that both series in 8.52 are identical* converge

if one of the inequality conditions is satisfied* satisfy the

equations for the inverse* and are their -only solution , are

trivial

.

- 50

A special and well-known case [6] occurs if £ = /7 is a diagonal matrix,, 8.51 and 8.52 become

M = + Q , ( 8 . 55 )

M-’.Z(.r'Q)nf’/ , ( 8 . 54 ) o provided f

x^o for all and e.g. //’~ !'(?/< 1 * i.e.

/Q

x/= sup Z/Q* /</{*/ ( 8 . 55 ) {xn}sL(£) x*

for all x .

§ Markoff processes invariant under a transitive group .

As a generalization of the invariant processes studied in

§ 2* we consider a Markoff process on a set E such that a group

Ej of transformations r of E in itself exists* which is transitive

over E . An important special case of this is the one in which E

is a sphere in any number of dimensions* being the group of all

rotations of E in itself. We consider then a matrix P which is

invariant under all transformations of Cj : p

x

_ p

x * ( 9 - 1 ) X ~ zX

for all re £* where

[6] Cf. R.G. Cooke (1950* pag. 51, (2.4* II)) and for the case of

finite matrices Olga Taussky (1949), and the older literature

mentioned there.
iiIilliill
51

rX H Ens{zx/xeXj . (9.2)

We choose arbitrarily a point cc e £ and define// as the subgroup consisting of all re Cj which leave a, invariant

The sets FT

are mutually exclusive and have as their union.

Evidently z e Fz ; re //*=! Fv= H • Fz oFv ^opr'e Ft p r eFr

, p Fv

, - Ft . Choosing arbitrarily in every Fr

a unique representative xv , let A be the set of all these representatives.

Now to each exists are^ with r« = x , hence a z e a and ^

,r? 'e /-/ with } hence with x = rjzn 'a. = yZa as rj'a-a.

because of 7?'e // . If also x=r^2r7 <x then r{ "= r, s N , hence

r7 = r

rj " e HzF , hence z,=r as the representatives are

unique so that dr is uniquely determined byx = ^<ra(in general^ is

not). Then 9.1 entails, putting p ~ P* :

(9.5)

Putting for any z e

(9.5)

Here p also is countably additive, and so with pe = i , and,

jL C

also by 9.1

Py = Pr(Y for all ^

e H . For any Fc a we put

df

H-i— PHra. »

(9.6)

(9-7)

so that <% r is countably additive and =o with <2^=7 . Then for a given Y and varying Fc a p is completely

- 52 -

additive in r % ± o 3 and s q, r , and can therefore be written in

the form

PYnHTa = / Ycttr^Y * ( 9 - 8 )

Here Yy can be chosen to be completely additive in Y and to

vanish unless, MY . In fact Yy is the conditional probability

that x e Y under the condition that x <= Hva . For every fixed Y the functions Yy are defined as measurable functions on A except for a set of -measure o . We introduce now:

Assumption A: The definition of the quantities Yy can be extended in such a way that they are defined for all Y and all v as

univalent functions of their arguments., for fixed Y measurable in

3" and for fixed 2r countably additive in Y . According to Doob (1948) a sufficient condition for assumption

A to be fulfilled is: £ is a Borel-set in a Euclidean space and

the <5 -field over E consists of all Borel-subsets of £ . The equality 9*6 entails

Y*y ^ Yy for all (9-9)

Taking in 9*9 especially Y^KEcc with KcH 3 Tc A , r e £ , Y*r<x for variable K is countably additive,, , hounded, and invariant

under all ^

e f-t s hence it has the properties of a Haar-measure

.

We now introduce:

Assumption B: The Haar-measure on H is uniquely determined except

for a proportionality factor.

According to A.Haar (1933) (cf. also J.von Neumann (193^> 193^*

L.H. Loomis (194-5)) a sufficient condition for assumption B to be

- 53

fulfilled is: H is a locally compact topological group.

Assumptions A and B together are certainly satisfied e.g.

if E is a Euclidean sphere of any number of dimensions and 9

the

group of all rotations of E into itself. Hence* if is the

Haar-measure* normalized to /jl h = 1 > and m

* the proportionalityfactor*

as

dr ATct mr -o unless dr e r

Extension of

ar<x

- mr^K = ^

Moreover ^nra. - ^

r

> whence m

to fy with arbitrary Y gives

( 9 . 10 )

/l" (9 ' U)

and substitution into 9.8 with E=a gives

Py = / 9dr fpr-dy 'yTM ( 9 . 12 ) JA

J H ' and finally by 9-5

px f f / vx

r

l

7r<x =JA

'x ) ( 9 . 13 )

where rx is any re 9

with zx a = x. . On the other hand it is clear

that 9-13 satisfies our conditions.

If in particular 9

is simply transitive over E , i.e,, if

H consists of the unit element only* and 9*7 and 9*13 simplify to <i r — pfA and

( 9 . 14 )

If* more in particular* E and 9 are identical* we can take

a = 7

* rx * x * and we get <^ r

=r pr and

P

x ~/b 'x* (9 - 15)

If 9is commutative and additively written* this leads back

- 54 -

to 2.8.

§ 10 , Wald's fundamental identity for arbitrary stochastic

processes .

Exactly the same argument , which leads to Wald's fundamental

identity (5.17) , holds if £ is an r -dimensional Euclidean space,

jc and y

are real vectors and % is a complex vector in r dimensions, and fjc is the scalar product. It also holds in the more

general case, where £ is an additive Abelian group and t = §* + i where and if are homomorphisms on the set of real numbers, i.e.

for all x and y in £ , jc is a real number such that £ L (* + {/) =

= ( 6'= 7 >2 )

. We can resume our result in:

Theorem 4 : If E is an (additive) Abelian group, if $ a 4 % , and

are homomorphisms in the additive group of real numbers; if

S = + $2 and <?(%„) <co and inf )jc > - e® then the “ v —— XSB 7 —

identity

-r (5.17)

is satisfied .

A partial generalization of this theorem to arbitrary stochasX ... ^ tic processes, determined by the transition probabilities x

satisfying 2. 1-2.

A

is derived as follows.

We make the additional assumption, that when the wandering

point arrives in the state (n*i) after having passed if ng2

through ^xn2 , there is a probability * X°‘ 1 that the

point will be absorbed hence a probability

- 55

°(n) - 7 _ /

H

'•!>)••• 5 7

fr»; that it will not be absorbed.

Moreover we introduce the auxiliary quantities

' }Xn~ 1 and

7}n)°

’ " "

Xn 1 interpreted as the conditional probabilities that the

catastrophe £ does not happen under the condition that the wandering point has passed through jc 05 ... and has ( for U ) or has not

( f or T ) been absorbed in x/7 _ 7 „ Finally we define

as the total conditional probability that § will not occur under

condition that the point has passed through ,

. . . , x-n-7 • *o •> * • * 9 x n. 7 In order to compute CXn) for n

t

7 we remark that

there are two complementary cases: either the point is absorbed in

^(n+i)

> X-n-7 5 y

x-n .1 (probability A(n)° 5

‘ “ 5 Xn~ 1 ), in which case non- 'S has probability U-(n) '

* * 3 X/?-/

> or it is not absorbed ( probability i3^° 4

and § does not occur (probability T(r} *° ’ ' ‘ ' 5 Xn ~ }

) and it jumps

into some "small" set tfy (probability P(nf' "* yXn~ 7 cXy ) > and it lives

happily ever after (i.e. £ does not occur further on; probability

) . Hence we have

C

x9 Xn-7 a x o •) • • • ) xn-7 / / *o :>• *-n- 7 T) ‘ t Xn-r T1 xo>- •>xn.?/T)Xo)

'-- 3 Xf}.r / -1 -1 \

(r>) - r\(n) X-Hn) + M(n) J-(n) J

r(n) cly^Cn+i) V 1U . 1

)

For n.o we have a similar equation, with the only difference

that the upper suffixes except y fail.

In order to simplify the formulae we shall omit the lower

suffixes (n) and replace the sequence of upper suffixes xo: by a single symbols (= path). Then 10.1 becomes:

(10.2)

By successive substitution we obtain a formal development for

C” , jt being given (in particular also if sr is "empty"):

56 -

CKA7rU*+B’rT’rJP*v A**U*% + B”T*JP^B**’T"*fP”^A"%%UJr*''* + ...=

*. , , , (10.3)

^Zt-B^T*!? ? . . /P**’-?*., A** yk.xU"*'-**-’

o J tyi J J cCy^

In order that this development be convergent and a solution

of 10.2 it is, necessary and sufficient, that

R" B”T”jP"

v B ”*• T"*J . .Jp*%

C**~ •** (10.4)

tends to zero for k oo .

In order to generalize theorem 2 we consider solutions of the

system of equations 10.1 in the unknowns C

' “ 5 Xn~'' where the

(n) U, and the T need not be probabilities,, but may be arbitrary real

or complex sequences of (not necessarily bounded) functions.

Theorem 5 : I f A , for all n and all n = *0

, . . . , xn_ , € E* real numbers

U-q

t T* exis t, such that

A.l T* z o for all n and all jt ,

A. 2 U* z 0 for all n and all 7r ,

A. 3 T’Jp^U^sU *for all n and all jt with B*^o ; If B. the functions T*s LI* are defined for all n and

all jt e E

n if G and c are real numbers, and if

B . 1 os G < i j B. 2 IT*/ £ 0 T* for all n and all jt , B . 3 IU*I*C LL* for all n and all Jr , then the equations 10.2 have solut ions C , given by 10. J> 3 whic h

s t he equations

c*s u

(10.5)
IiII1I!
Proof: Writing

( 10 . 7 )

A. 3 becomes

/<?4 ups B”U? (

. 10 . 8 )

from which the existence of the left member follows. The terms of

the sum 10,3 with 7J , U.0 instead of T , U. are ao. The (/<:y-r)st

term of this sum is g the same expression with the f actor

(which is g i ) omitted,, hence by 10.8 with jryr

. t .</ instead of

Tr and yk instead of if g the k »th term with A

rrt^1

' ' ' ^k- r replaced by

jgjrfr" 'i/M-T m Added to the k -th term itself the sum is g the k -th

term with the factor ‘ omitted. Continuing in this way

we find that the sum of the first k+i terms is s u* , so that

the series is bounded, hence convergent. Denoting its sum by

we have then 0 < C* g and also 0 g g , where

is the expression 10.4 with T and C replaced by and CQ „ From

B.1-B.3 it follows then that the integrals in 10.3 as well as the

whole series, exist absolutely and that /KZ/ae*P&aO*U? , whence Cim = o , so that 10.3 satisfies 10.2. Now,, if a solution of 10.2 satisfies 10.5, it is trivial (by 5.17) that also

10.6 holds. If, on the other hand, 10.6 holds together with

10.3, we have

- 58 -

c ”•‘*{3**'- ?KJ- •/<? dyk

A

Jr^---^U 7r^1 '‘^K

-"Vn-y £*</, "•/* LA”?, " y, (10.9)

The expressions between the curved brackets vanish because of

10.6, 10.7 (with 7r</

r

, . .

.

> instead of-v and instead of y )

,

hence they remain zero after repeated integrations , and the first

sum between the square brackets in the right member of 10.9

vanishes . The last term between the square brackets is absolutely

= O Li0

° hence it tends to zero, which proves 10.5 and the theoIn the proof of theorem 5 lemma 5 (Appendix § 8) has not been

used. It is therefore to be expected that theorem 5 will not completely imply theorem 4. In fact, in the special case of theorem 2

we have

Then the conditions of theorem 2 except 5.8 are satisfied, but

10.6 passes into

rem

.

( 10 . 11 )

so that it remains to be proved that

( 10 . 12 )

where C

is given by 5*10* if 5.8 is satisfied. We shall not go

- 59 -

into the question, under which precise conditions this latter relation is satisfied. In any case a generalization of lemma 2 with

-P x^ instead of is needed.

References .

N . Arley , 1 943y On the theory of stochastic processes and their

application to the theory of cosmic radiation.

Copenhagen, Thesis University of Copenhagen.

G. A .Barnard, 1946 , Sequential tests in industrial statistics.

Journal Royal Statistical Soc . Supplement 8, 1-21.

M .S .B artlett , 1944 , Negative probability, Proc . Cambr. Phil. Soc.

41, 71-73.

G .Birkhof

f

, 1948 , Lattice theory (2nd edition). Am. Math. Soc.

Colloquium Publications, Vol. 25.

D .Blackwell and M. A . Girshick , 194*5, On functions of sequences of

independent chance vectors with applications to

the problem of 'random walk* in k dimensions.

Annals Math. Statistics 17, 310-317.

G .Blom, 1949 , A generalization of Wald's fundamental identity.

Annals Math. Statistics 20, 439-444.

R.G. Cooke, 1950 , Infinite matrices and sequence spaces, London,

Macmillan and Co.

D. van Dantzig , 1935, La nation de derivee d'une fonctionnelle,

C.R.Ac.Sc. Paris, 201, 1008-1010.

idem , 193*5, Ricci-calculus and functional analysis,

Proc. Kon. Ned. Ak. v. Wet., 39, 785-794.

idem , 1941 , Mathematische en empiristische grondslagen

der waarschi jnli jkheidsrekening, Ned. Tijdschrift

voor Natuurkunde 8, 70-93.

idem , 1947 , Mathematische Statistiek, Hoofdstuk 2, Collectieve kenmerken, voortbrengende en karakteristieke

functies, Mathematisch Centrum, Amsterdam, sten-
IiiiiiiIIIIIIiiI
60

cilled

.

D. van Dantz ig , 1949, Sur la methode des fonctions generatrices,

Colloques internationaux du centre national de la

recherche scientifique, 13 , 29-45.

W ,Do( e)blin , 1940 , Elements d

1 une theorie generate des chaines

simples constantes de Markoff, Annales sc. £c .

< Norm. Sup. (3)* 579 61-111.

J .

L

.

D

o ob , 1 938 , Stochastic processes with an integral-valued

parameter. Transactions Am. Math. Soc . 44, 87-151.

idem, 1945 , Markoff chains - denumerable case. Transactions

Am. Math. Soc. 58 , 455-473.

idem, 1948, Asymptotic properties of Markoff transition probabilities, Transactions Am. Math. Soc. 63 , 393-421.

W .Feller , 1 949 , On the theory of stochastic process, with particular reference to applications. Proceedings Berkeley

Symposion on Mathematical Statistics and Probability

403-432.

idem, 1950 , An introduction to probability theory and its appli

cations, Vol. I, New York, John Wiley and Sons.

M.Frechet , 1913 * Sur la notion de diff erentielle dans le calcul

des fonctionnelles, C .R . Congres des soc. savantes

(1912), 45-58.

idem , 1914 , Sur la notion de diff erentielle d'une fonction de

ligne. Transactions Am. Math. Soc. 15., 135-161.

idem , 1950 , Generalites sur les probabilites. Elements aleatoires - Traite du calcul des probabilites et de

ses applications. Tome I (Les principes de la theorie des probabilites). Fascicule III (Recherches

theoriques modernes sur le calcul des probabilites),

Livre I. Paris, Gauthier Villars.

M . A . Girshick , 1946, Contributions to the theory of sequential analysis, part II, Annals Math. Statistics 17, 282-291.

A

.

Haar , 1933, Der Massbegriff in der Theorie der kontinuierlichen

Gruppen, Annals of Math. (2), 34 , 147-169.

- 6l

J . Hadamard , 1910 > Le£ons sur le calcul des variations, Tome I,

Paris,, A. Hermann,

H .Hahn and A .Rosenthal , 1948 , Set functions, Albuquerque, Univ. of

New Mexico Press.

P . R.Halmos , 1950 j Measure theory, New York, D.van Nostrand Company.

J . J .Hermans , M „S .Klamkin , R .Ullman , 1952 * The excluded volume of

polymer chains. To appear in: Journal of Chem.

Physics

.

J .H.B .Kemperman , 1950 * The general one-dimensional random walk with

absorbing barriers, with applications to sequential

analysis, ( Ph .D-Thesis, Amsterdam), ' s -Graven hage.

Excelsiors Poto-Offset.

G ,W .King , 1948 , Dependence of physical properties of high polymers

on molecular structure; statistical investigations

with the aid of punched earth methods. Office

of Naval Research, Technical Report no. 1.

idem, 19^9 > New methods in the statistical mechanics of high

polymers. Office of Naval Research, Technical Report no . 2 . L.H. Loomis , 1945 * Abstract congruence and the uniqueness of Haar

measure. Annals of Math. (2) 46, 348-355.

E.W. Montroll , 1950 * Markoff chains and excluded volume effect in

polymer chains, Journal of Chem. Physics _l 8 , 734-

743 . J.von Neumann , 1928 , Zur Theorie der Gesellschaftsspiele, Math.

Annalen, 100 , 295-320.

idem , 1934 , Zum Haarschen Mass und topologischen Gruppen,

Compositio Math., 1, 106-114.

idem , 1936 , The uniqueness of Haar measure. Math. Sbornik

1 , 721-734.

J.von Neumann and 0 .Morgenstein , 1944 , Theory of games and economic behavior, Princeton, N.J., Princeton University

Press, 2nd ed., 1947.
IIIIppIIppppppp

IIKI
- 62

Olga Taussky , 1949 , A recurring theorem on determinants. Am. Math.

Monthly, 56 , 672 - 676 . Ch ,M . Tchen , 1951 , Stochastic processes and dispersion of configura

tions of linked events. Journal of Research, National Bureau of Standards, 46, 480-488.

A, Wald , I960 , Statistical decision functions. New York, John Wiley

and Sons

.

W oWascw , 1991 , On the duration of random walks. Annals of Math.

Statistics 22 , 199-216.

National Bureau of Standards, Washington D.C

Mathematical Centre, Amsterdam

1952.

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.