NATIONAL BUREAU OF STANDARDS REPORT

1298

CONTRIBUTION TO THE THEORY OF MARKOV CHAINS

By

Kai Lai Chung

NBS

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
NATIONAL BUREAU OF STANDARDS

A. V. As tin , Acting Director

U., S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

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 Spectrome try. physical Electronics. Electron Physics. Atomic Physics. Neutron Measurements. Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atonic Energy Commission Instruments Branch.

5. CHEMISTRY. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry. Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure 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 Ttobes. Electronic Computers. Electronic Instrwsasatatiea.

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.

15. MISSILE DEVELOPMENT. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Instrumentation. Technical Services. Combustion.
NBS PROJECT

3011-60-0002 15 November 1951

NBS REPORT

1298

CONTRIBUTION TO THE THEORY OP MARKOV CHAINS

By

Kai Lai Chung

This report is issued f< Approved for public release by the l( reprinting, or reproduction

in any form, either in wl Director of the National Institute of tission in writing is obtained

froai the Office of the Di Standards and Technology (NIST) thington 25, D. C. on October 9, 2015
I

' ^ - : -..0 .y . * v ••

.

ii

i

j

' v' 5 -

v ' •":

, .: - y

, >. . ...

' *. - '

.

P

P

P

P

P

p;

Pi
FOREWORD

The theory of Markov chains is steadily gaining

5.n importance s and numerous new applications are

being made of this theory * It is hoped that the

results here presented id.ll be of interest to workers

in th© field® The present report introduces a n©Tf

problem in the theory of Markov chains by considering

three states; the initial state, the final state, and

a taboo state which must be avoided in the transition®

This work was done by Professor Kc L® Chung while

he was a guest t^orker at the National Bureau of

Standards during the summer of X9£lo It was performed

under Contract GST-52$ between the National Bureau of

Standards and the University of North Carolina®

J* H* Curtiss

Chief, National Applied

Mathematics Laboratories

iU Ve Astin

Acting Director

National Bureau of Standards
\

c ; -' tv'- ,Y : to

.

- V» U , •*. *

I I
CONTRIBUTION TO THE THEORY OF MARKOV CHAINS

By

Kai Lai Chung

abstract

sar-15,5 ??£

Jiarris turn

ST n3W ^3ults obtained LT E°' out to tie -m Wrv „<•»/ J\..* amplifications of Dobli-'s

1

£

ly

?

ith 80K®

consider the probabilities of hin.?^ 3 was led to

before another J

1 htt

,tinS on® state

Idea of considehL pi r^a thi - **». This

•! . , « — o.ng rnpoe states r>nft i n-?f ? e i 'taboo, n and one final j, »,!' Ni?! * ni \

iel > one

the present work. The notion developed in

to the "union" or "interne -tier" U

pa

f sag® ^me

also introduced ker.h! f

two state£ is

notions is illustrated.

interPlay between these

The fundamentals of the theory of denumerable Markov

ehaln“ Wlth 3tafcl °n£- ry transltion probabilities (D.M.C.S.)

-re laid down by Kolmogorov [1] and further work was done by Doblin [2], The theory of recurrent events of Feller [jj i s

Cl°Sely relatedj if not ®o-extena ive„ Recently some interestir.g new results were obtained bv T p . » . _

v “ c ® Harris [If.] and comrauni*

c

t

o ci go the author rpv,..^ j. § ' : 'jiphifi cations of Doolie 01121 j<> umi, <-> - w«** the author was engaged in

1 n Cenurnersible !1 nean^i , cu' .n" refers to a process

parameter
.

»

i

W

i

1 1
While Harris* main purpose lies elsewhere, he was led to consider the probabilities of hitting one state before another,

starting from a third on© 0 This idea of considering three

(instead of the customary two) states, one initial, one "taboo,

and one final, will be more fully developed in the present worko

The notion of first passage time to the "union” or "intersection

of two states will also be introduced here® The interplay

between these notions will be illustrated®

Recorded results in this paper will be labeled as formulas

and theorems, respectively e Relevant remarks as to their origin

or significance will be found in the body of the paper e The

author is indebted to Dr® Harris for communicating some of his

results before publication

1 0 The' sequence of random variables {X^} n = 0, 1, Z 9 forms a D 0 M*C„S 0 The states will be denoted simply by th©

positive integers® Tho (one»step) transition probability from

the state i to the state j will be denoted by pW 0 Because

of stationarity we have

= J

for all integers m ? 0 for which the conditional probability is

defined o VJith this understanding we shall permit ourse^.ves to

write xn = 0 in the definitions to follow, as if the conditional

probabilities were always defined 0 Notations

o

n, H, v, r, s, denote positive integers and will be used

as time parameters or general numerals;
'

/
it j, k „ p

&

h„ denote positive integers and will be used

as state labels:

p}" i = P(Xn = j | X0 * i) ; p(0) =

^(n) = P( xn = j, Xv 4= k, 1 < v < n | Xq *

- P(Xn

a 3, XvH, 1 1 v < n | Xo

*

£[f - P(Xn = J, Xv * J, * k, 1 < v < n |

00

Q,* = z oS n) n*l

i + j

i = j

1)

i)

x0 = 1)

where Q may stand for any of the symbols P

k ij

or P

k ij

We offer the following clue to the above notations 0 The

letter P designates "passage;" the letter F* "first passage;"

the fir^st right-hand subscript designates the initial state;

the second, the final state; the left-hand subscript designates

the n taboo state," namely one to b© eschewed during the passage

(exclusive of both terminals); the star on a letter with subscripts designates the sum of the corresponding infinite series

(finite or *oo) summed from n “ 1 ad c inf a We admit that this

is not the most logical system of notations we could have inventado For instance, we have the superfluity F( n ) =s p(n)

ij j ij * and if we had allowed more than on© left-hand subscript^ , we

could have used only one letter P and written F( n) ® F( n ) k ij j,k ij

2 This naturally suggests the consideration of more than one

taboo state 0 ,

<
t 1 ' g
CEJ

However, we consider our notations to be preferred to the

arbitrary use of all sorts of letters from the Latin and Greek

alphabets® Also, after painful deliberations we decided not

to define P(^) , Flo) or F(0) , while reserving the right to

do so later in some cases®

Formula I® If i £ j* then

Ftr i

F

ij 11 * /IV 111

where on the right side 0 9 00 is to b© taken as 0 o 3

Proof® Wo start from the formula

/ x H-l

p(n) - 2 p( v ) F ( nc* v ) ij v=0 3 ii 1 13

( 1 )

where vre agree that _,p(0) = 1„ (1) i3 proved as follows?.

Either the state i is not entered at all during the passage from

i to j 9 which contingency contributes the term corresponding to

v “ 0 on the right side of (1); or there is a last entry of i,

occurring at the step® 1 i v i n • 1, which contingency

contributes the general term®

Summing (1) over n, we obtain

cd n«l

Z Z p(v) p(n-v)

n=l v=0 j 11 i ij

13 i ij U y ii ' »

Since the terms of the double series are non®n©gative , the in®

version is justified and (I) is proved© Moreover, this proves

It follows from (I) that

This convention will b© understood in similar circumstances®

1 t Ff,

CD

** Z F( n ) ij n~l ij

CD QO

e S p(^) 2

V^O j ii n«v*»-l

that if ,F‘*^ > 0 , then P*^ « qo
.

'
*

*

' " j

a ^ ^

an^ cn^r = namely p( n ) = 0 for all n Q

Formula II 0 if j £ k 9 then

A, - /r4

(i *

„ij’

• <”>

Proof,, We start from the formula

P

(n) « 2 P(v) P (n»v) (2) k Ij V=1 k ij k jj

where as before p(0) = 1. If v;e ignore the left-hand subk J j

scripts * (2) reduces to a familiar formula* The proof of the

latter extends immediately to (2)

Summing (2) over n we obtain

GO oo n

Pf = 2 . P(") =22 ,?(») p(n-v)

* ij n=l k -*-j n=l v=l K *j k jj

CD 00 - Z f(v). 2T p ( n-v ) , p*'n + p* ) v=l ^ ^ J n=^v k j j k i j

‘ k j j

VI© note the following corollaries to (I) and (II). to bo

used later 0 Formula (Ila)* If i £ j then

p‘iir = F*' r\ j. p*f \ i ij i ij (1 i

A jj'

Formula (lib). If j ^ k then

P* p* m p* p*

j jk k

r

ij jk' k I j

°

F ormula (lie)* If i r J then

F* (1 + P^ ) as p* (X + P* ) ir i jy i ij u

j it

Pornula (III). If i f j then

N

2 p(n)

lira = P* <

l ,

. i ij 00 ° 2 p(n)

n=0 il

(Ila)

(lib)

(lie)

(III)
.

t i
Proof o W© start from the formula

p(n) ^ x p('? ) j>(n=v) ( 3 ) U v*0

" 11 i iJ

where w® agree that p(0) a o 0 Th® proof of (3) is entirely

1 i J

similar bo that of (1) Q

Summing (3) from n®0ton~H9 we obtain

N , , N n , x ,

. N , v N«v

£ P £ 2 ?<VMT { V)m 2 p !

) 2 O

n-0 n^Ov^O ii i lj v=0 -*- 1 n*0

W© need an elementary lemma which is frequently used in

(k)

such connections

CO

Lemma , Let 0 < av

< 1 9 by > 0 ; 2 av » 0

v«0

lira bv

s b i 4oo c Then

N

^ °N«v

lim *SQ « B

N-^oo S

^ Sr

Applying the lemma to (1|.) w© obtain (III) 0 That

clear from (II&), and th© remarks at th® end of the proof of (X} 0 Theorem 1® The limit

N

. P ; , < 00 is

i xj

p(n.)

lim

ii

H-^oo H , , 2 p( n ) nio JJ

( 5 )

exists £.nd is equal to any of the following three expressions:

1 * J?r ii

1 + p*

i n

F*

. —

u

p*

i ij

p# p#

- LL 1 J-i

p& p*

ji i ij

(IVa,b 8 o)
( ' . I ’ '
the first always, tho second if 1 - j. the third If F* F** > 0

ij ji

Proof o Doblin [2] has shown, trivially, that

lim

N co

N

% P( n ) n-0 :i 2 N

“ " % p(^)

n*=0 2 2

o ( 6 )

Comparing (III) and (6) w© obtain (IVb) if i £ j 0 (IVa) now

follows from (He) and obviously holds for i = j* If

Ff F* > 0- then the denominator of (IVc) is not zero, and this

ij Ji

is then equal to (IVb) by (lib) with k 32 i«

That the limit (5) exists and is finite and not zero was

proved by Doblin [2); that it is equal tc (IVa) was previously

proved by the author [53© The present approach seems to be the

simplest

o

2S£2HS£2.° If I?, J, arc distinct states of one class s 4

thon

N f S pf n ) lim BSLdL

M-»ao ®

X P,' n/

n-1 k£

a

Naturally there are other expressions for it and we omit

tho tedious considerations when some of the states are identical*

2* We now consider two states i and j belonging to tho same

r

o

current c 1 as s , name ly

7?#

" ii

ss * 1 ©

r;

f Slightly generalizing Kolmogorov, we define a class to be a

sot of state 0 such that for any two states i and j belonging

to it, wo havo Pf p* > 0 o See [6] 0 ij jl
c : 1I . J ' * L\ . V ' '
*

A fundamental idea in the theory of D # H0 C 0 S 6 j already found

in JLoImogorov ! s work* is to notice that whatever transpires between

successive entries ab a recurrent state forms a sequence of inimpendent events© F.irsuing this idea, Harris [43 discovered

the following very elegant theorem© Our proof is somewhat

different from his©

Let i i j and define

Yn

= uhe. number of v, 1 < v in, such that X7

«* i;

Zn

th) number of v p 1 < v i n, such thit X7 * j 0

In words , Y (or t ) is the number of entries at the state i (or j) n a

in the first u at 3 ps 0 Using the average ergo&ic theorem (see (11)

(•

below) it ie jaay to show that^J la a positive state? and P(X

Q®CJ * 1

where C Is Ae class containing then we have

Z.

P( lim

n-€>oo & p

iv

1 ) 2l •» 1

The folic j is theorem covers both positive am null classes 0 ?h> rtm 2 (Harris)© If i and j are two ;<;;at©a in a recurrent

class C i'd ?(Xq 6G) .« 1, then

n , X 3 p(v)

pf s lim v—o \ &

‘n*oo Yn n»oo n

~~ ' £ p(v)

v*0 ii

( 7 )

P.oof © Since i is recurrent- we have P( y« *• oo) = 1

n«*co n

Let v

j

*• Vo <**© be the successive indices v, such that *v * * Let fl* » the number of v 0 < v < suet that .l r

.

Tr.cn., r remarked above, the Wg 9

fi are independent, identically

di:-f 1 hated random variables© Evidently we have
1*1 \ : V

>.\ i

• :

oc- b s - wc-i a o* (.8;

t - * ;v r 3

x‘

; J ilriB^xioc eaalo

a q rtf ©si el©*

’ *

y

- an i w t. *3 -’ * -

: - •

c>7. eec ;>Oi/o dcV *>d

v > a v to aetfmwr. i

.7 •; ' ' ' £>
TO ^ =

E(Vto

)

CD

2. 4^ - P# < OD

n»l i 13 " i U

?!: *. tj definition we have vYr -

“ * VYn * 1

and

*

n~i

Z Wo

S'l

•a i«si V1 ^ ^ ws

a=l

Consequently

Yirl

£ W; S K 1 "TT

Y,

Zn Tl ^ YTiE^ n Ti

n

2 ws 8-1

-n

( 8 )

Applying Khintahine-Kolmogorov 3 a strong law of large numbers

so© @ e g 0 [9] p o g08) to the sequence {iK we obtain?

•n

p f 11m S=1

<£

i « s

oo p

w

) = 1

Yr 1 ij

Moreover* P(vi < 4-oc) = 1 „ It follows from (8) and (9) that

(9)

PClim * p* ) - 1

n-soc Yn 1 ij ( 10 )

Now Ff =s X 0 Hence Theorem 2 follows from (10) and Theorem 1*

1 j

using ( IYb ) there©

This theorem Includes as special case a previous result by

Erdos and the author 17 ]* Consider independent* identically

distributed random variables {Un} which assume only integer

values x^rlth mean zero© They form a D o H o 0oS© with all integers

as the states © Since the mean is zerq, all possible states are

recurrent by a theorem of Fuchs and the author [8]©^

This important step cannot b© circumvented by the present

more general* approach*,
c p

» :c- ...

' r

, >

- v

'<

*

:;1 1o wal susa-s^a a

*

:#oia%oiaX«au*oJrio*«*Jtt

;

' ’ M) eoi'.f? up

"

.

'
10

Without loss of generality w© may suppose that every integer

is a possible, therefore recurrent, state 0 Writing

m

Sn - U Uy we see that

v»l

P

(n) * p(sn = j-i)

Hanca, F;*1 ) * = P „ and (7) becomes H 00

7

which is Theorem 8 in JiS]o Needless to say, as far as this

statement is concerned, Harris 0 approach is incomparably better

However, we note that there we actually proved a sharper result,

i o e o l*e

P Mj} T loOe)

xn

0

n

for every e > 0, where Mn * $ ?(SV « i) 0 see also Theorem ?

ytsl

1

in Ip] o It would be of interest to investigate eorrespond5.ng

strong relations for the general Markov-chain case, using perhaps

& more precise form of the strong law of large numbers G 3o W© now consider a positive recurrent class C e According to Kolmogorov, in C all mean recurrence and first passage

times are finite, namely for all i, jeC we have

co

ra m "

nfx n Fl ?

5 < °°
'

I

.

c
« 11 •»

V® introduce the notions of first passage to j(Jk and to as

follows© Let j # k 0 T(i ,jOk) * the smallest integer n > 1 such that Xn = j or

52 k p whichever happens first* given that Xq * i;

T{i ? j$k) = the smallest integer n > 1 such that there exist

. two integers nq and ng such that n^S g 1 1 i n*

Thus ©• a the event that Xq ** i and the state j is reached before

the stat'.i k© Sine© I* j and k belong to one recurrent ©lass

we have

'} ©k « {ws Xq(w) « 1}

Let P(Xq 38 i) ~ c > 0 © W© have th® following relations* immediate

consequences of the definitions©

»(i,J«k) = E{T(i,j©k)} ; m(ijf)k) - E { T(i, J©k) }

Let w cle iote the sample point © Put

©ji :s { w i. Xq(w) * i, $ j* f k for 1 < v < n; X^v) => j } ?

*

Jti

{ Ij

nP(dw) *Jk

< n+BSkj) M(u) )

* C3n(i, jfik) + p(e*£) mk<
.
12 -

cm>: , j$k) ~ ^

lj ^ n*mjk) P(dw) + f (n+n^j) ?(dw) } n~x <

* o

k

n n

- cm(i 9 jOk) + P(©3) raj^ + P(e^) o Now by definition we have

n®il

sT “ p*

k ij

z<j£l

c

pfc

j Ik

Hence v® obtain from the above;

Fc.?t ala VI o If J ^ k then

m( 1 , Jtnc) * m13 - jPik irijjj * mlk • i^ij Mjk

Fcrr ula VII® If j ^ k then

ra(i,J$k) * Hij + k

pij «jk “ ®ik +

jpik Mfcj

Sine e

(VI)

(VII)

p# 4. F* _ 1

k ij j ik

we deduce from (VII):

Fcrrnla VIII. If j ^ k then

raik + mkj - mij * k^ij^jk + »kj> • < vm>

i of (VIII):

mkk * kFkj f

- mjk + mkj) « (Villa)

This las formula is due to Harris [Ij.], who also derived from

It the following cute relation:

We oote the following special case (i =

k^kj

. (VUIb)

% Now in a positive class the ergodic theorem of Kolmogorov holds

& This theorem actually establishes the limit of p( n ) as n^ooc The average form (11) is an easy consequence of A^Hardy®

Littlewood Tauberian theorem!
VO *
• 1J -

1 $

p(v)

oo n

* A m m. ( 11 ) v=l 4,1 jj

Thus (VUIb) turns out to be a special case of Theorem 1, using

(IVc) and noting that = 1 G Dividing (VIII) by the product of (Villa) and (VUIb)

wo obtain

mlk » mkj . n

13 , — wnm n mwiurtli ma

,IBr" 'L1 "' y 1*

(12)

By Formula (lib), the left side is , since = 1 in the

present case® Thus we obtain

Formula (IX)* If J ^ k then

p* - mlk + mkj ~ mij

k iJ * ra jj

(IX)

As an application consider, as in the Central Limit Theorem

for Harkov chains, random variables {Yn } attached to the Markov

chain (xn

\ in the following wayr

Y x, if X * i where the x, ®s are arbitrary real numbers

n i n 1

* Theorem 3. Let 1 be a positive state. Given X

Q

« i, let

v^ denote the smallest n > 1 such that X * i_ Then if the series

u n

on the right-hand sides converge, we have

® r: i n

E {Y^ ooo + Yv | Xq ~ i }

55

E {(YX

m‘ii

< + Yy

0

) 2

! x0

- 1 }

GO X? OO X4 OO

&

A* —- *• 2:aii y .1 df n

3S j=*i njj k-1

(Xa)

(Xb)

raji + mijf • mjk

mkk

*

j>oob pointed out to me that this is a case of ftol& 8 s equation

for Markov chains 0
Jt

; ! t f

:

"1

.

-©fosfra ;vJU Lsoq a od 1 NHL

'

.

’ t
114- -

Proof o It Is more convenient to consider new variables

Zn defined as follows:

( 0 if Xy s i for some v e 1 * v < n |

2 » <i£

x. If Xn = 3 and Xy >j= i, 1 i v < n ; inhere j may be I in th© last»writtan lin© 0 Evidently we have

then

v0 OD 00

jfE { £ Yr jXn S3 t ; 35 E{ Z ZnlXo “ 1 }

32 Z fi n«l n=l n*l

oo 00 00 co - 1 2 . pj«> X * 2 P* X *= Z ®ii

n~l J-l 1 ij j j-l i ij 3 j-l b

jj

by (IX) with i * k.

Fur (hermore we have

v-»

,2

CD

E {( 2 YxO^IXq - 1} - E {( Z Zn)2jxo = i } n«l n~l

oo * E { S ( Z~- » 2 £ Zp Z&)

n*l

As before we obtain readily

co , oo

E { 2 z2 } . * !ii *2

n=l m

jJ J

Next we have

a? oo

S 2 E(Z-Zg)

r*l 3*r+l

1 “

CO

i Plj *J ^ i r jk xk

JH

00 CO CD GO

£ 2 £ £ 4 p|?) X, 1 P(S“p ) X.

r*l s*r+l 3*1 k=l 1 1 J J 1 Jk k

j+i

CO

By (IX) this reduces to (Xb) 0
* *

5
The two expressions on the left sides of (Xa) and (Xb)

play an Important role in Dobiin ‘ a Central Limit Theorem for

Do^^oSo Vo refer the reader to [2] for details. They are here

evaluated in what seems to us more tangible terms,

I4.0 From Formulas (VI) and (VII) it follows that

v €1

This relation ia in striking resemblance to a familiar formula

in the elementary calculus of probabilities, according to which

If A and B are any two events then

P(a0B) + P(A$B) « P (A ) + P(B) o The generalizations of the last relation to any finite

number of events i3 known as Poincare 8 s formula (see 8 s g 0 { 9 j 9 p 0 61); and we immediately suspect that the same may be true

for the msan first passage times 0 This is indeed so, W© define

o»oUh) and 0 ../lj 0 ) as the obvious extensions

from tha case 3*2. Wo shall also rcrite t#0 fl 3 8 t J to denote ij-n 0#o r* j r-ln j r4>1

n if j • j r u<r<s) and

4,n ,,,nj is not one of the j

3 is s.

r

Formula XI. If »o« # J t are distinct states In a positive

class to which i also belongs, then

»(*,&». = Sm(i,jr ) » 2 m(i,

j

r,Ojro ) r~l lii‘-,<r 2

<8 1

II

'S' -.< <r» <-r> <* )

+ (- 1) 8 " 1 ... $j a

) .

(XI)

II

O

Proof e Put

'n “ ( vt *<}(«) 35 i»Xv

(w) 4= Jip ..o 8 j 8 for*l< v < n, xn

(w) * j p }

p s G 4 . n-1
. •II

‘

1

' •' If

I

' w.

'

.

I*

]1

1

I

V

J

.

I
16

#a haV0' as at tte *SInning of § 3 , f\ OOQ n V 2_ s co 1

E A * • * &

4

( 13 )

®**»JXU...UJ>

) lo-l *(«*

o « 6 I l lr

) o 1 3 r-1 _ ^ Substitute (13) int0 the -i«ht b1(1a A , ?

t»l«a c-lpur,.,;. .

, 8 S1“ *

•»* •««« the

A f ] 0 0 0

? ?

1

, * *, T

} wh3r® r * « diet inct from . . r diet, U Sppears 311 right side of Ul) Onoe “<iB V " V and once In ®(ieJ ^ « n Wito eigne; and dees not appear in ** "

*

’ D8t

oa the right aide of (i^V^

***""* ^

**

to consider the term «(*,<„_ _

S "r° 0 "

r<SmalllS

term and hence it. net coefficient lY

“ * ‘WS *“* * eVdry

'1^ " ! J) + (|) + + (=i)S~l a 1

Therefore (XI) i. establish.

;:;;;: - *“• —*• ** - « »«,

- ~ w vJZZZZ 7"’ '~U “»

«ny closer relation bafcw&*n *u P^ent twins. We aiso We ,

* the two apJcnown extensions of Polo '•

’ " °* ®nsiona »ugge 8 ted by the Poincare formula to the interested

•'*' We reader now giV0 another -et.nodthod ofnf computing p* ~ , metnod requires the ergodie - «

' ' 1Ms

8 dlc J;eorenl (ID. An interesting h proauct. is the following- * testing by-
; „

' |

ri ^

i

__ ,tt o eflia {sl ?

T<

I

oi „.M -no »

•*' * n ' i:

; • " JA . t

lJ 0OSO ** " ‘ '

I

* -

• * 1 '

6 x- ooao a'w etc

-

I

< .>
Theorem 5> 0 If i 9 j and k (not necessarily distinct)

belong to a positive class s then

ao2 { FI") - pte} } * o n=l 1K iA

^ick

Pro<f e Using the familiar formula (cf e the remark after (2))

p

(n) * 5 p(v) p(n-v)

ik v=a

Ik kk

w© h&vt

- ?

ss

! > X

{T&' - p S’ 1 5

p^’ • aw

Substitut ing from (XI)* we see that the right side of (lij.) Is*

ae N-hjo, asymptotically equivalent to

H N°v

N

_ pjy) » f(y )

i

2=s

v—1. mkk

(15)

CO

ss <oo 9 we have* as H^co

N

N 1 I F‘( ¥ ) ® p(v) 1 s

v=l ik Jk

oo V*R4-1

00

V Fi; How ainoo F^ (y) k

* Fjk « 1» and 2 v pj k

j * n»ik <oo , - . * jk

ik

) «• f{yJ l «§-o

jit

Using this in (15) » we see that its limit as H ^

oo is

Xim

N ^co in

1^SZE*JBK» kk

*r«

di V~X

ss mkk

0

We rote that Theorem 5 gives a convenient determination of

the mean first passage times in terms of th© transition proba«

bilitiesi in particular
c

.

-
°* 16

oo N

nu k * 1 + 2 { p£^ ° P (-? ) } „lim i. 2 P,(”)

We do not know what the situation is in a null class 0 All we

can info? from Theorem 1, (IVc), las If i and j belong to on©

recurrent class and 4

s ^hen

oo

S (»!}) - p$3

> J —CO

To ?©turn to . P

ft k ij

If J 4

s k we have evidently

1 , p(p) p(D « p(n+l)

h*k k ih '*$ k ij ( 16 )

where 9 as later, an unspecified summation runs from 1 to oo 0 Summing (16) over n, we obtain

% p# 1) 3 p# « p(l)

h|k k ih hj k i j k i j

or

t , P

, -fill k lh h

( 1 ) 4- p

( 1

)

k

r

ij rkj

»(i)

ij (IT)

since , » 1 and . pj^) « pj^) k ik k ij ij

We is sent that In general

n

1 ,F* Pi”> - .P* + 2 {P.£)' - p|v)> . h

k ih hj k ij V=1 kj ij

This is readily shown by induction on n 9 starting with (17)

o

Now sum ?rom n~l to n=N, divide by N 9 and let N’=^co 0 By (11)

and Theorem 5 we obtain

l i A] STT

s

k

p

ij

+ J HV - ? n

) > * k

p ij

* o>:m

jj
- <
19

Bov

2

h

P

*' k ih

DO €&

2 2

h-X n~X

p(n)

k ih

ost ?(XV + k,l S v < n

n=X

i)

OD OD -2 S' n=l v^n

?.(v)

ik

(19)

(18) ani (19) give { X)

‘
II
20 -

REFERENCES

E1--3 A 0 N« Kolmogorov, "Anfangsgrude der Theerie der Markoff

schen Ketlen mit unendlichen vielen meglichen

Zu3t&nden © " Materoatlceskl i Sbornlk , N * S © , Vol * 1

(1936), ppo 6oT^FIF; ffiuTIT 3e i*0nXv « d^Etat Moscow

(In Russian), Vol 0 X *fl9T?T« T'orYarT exposition TrT

English see Chapter'll of [53*

[2] Vo Doblin, "Sur deux problemes de M* Kclmogoroff conoernant

les chain® 3 denombrable s

o ” Bull© Soe* Math© de France,

Vol. £2 (1942), pp. 37-*4.

[31 Wo Feller, "Fluctuation theory of recurrent ©vents*" Trans » Amer* Math* See Q , Vol© 67 (1949 )

pp© 98 -119* See

ilio^IoTTChSp'ter 12 .

'

(41 Ee Harris, "First passage and recurrence distributions

„

f! Net yet published.

[53 K» Chung, "An orgoclic theorem’ for stationary Markov

chains with a countable number of states , Technical

Report Nop 18 8 Project ONR 042«*03^, Borke1®y7 V B l9foT“

[6] K* L0 Chung, Lec ture notes on Markov chains , Columbia

OraduateTISTFemat 1 c n! * sti c 3 Cour re , Rev Yor !:

„

1951 • [7] K© L© Chung and P 9 Erdos, "Probability limit theorems

assuming only the first moment I." Memoirs Amer 0 Spc , » No© j5 (1951)*

Math© mmrB. ow.rnj*

[8] K 0 L© Chung and W* Fuchs, "On the distribution of values of

suras of random variables," Memoirs Amar© Math© Socu* - * — n —I—ir«n ^a*gir > —C-. lffirran..-wm.w..w ^ No, 6 (1951)

a

f $ 1 W« Foliar, An introduction to probability theory and its

applications » ’Jchn~WTley and Son3 , Hay lorkj f9pG*
'

l

’ < ... >

l

:

. ^

• •

.

.

*

.
THE NATIONAL BUREAU OF STANDARDS

Functions one Activities

The National Bureau of Standards is the principal agency of

the Federal Government for fundamental and applied research in physics, mathematics, chemistry, and engineering* Its activities range

from the determination of physical constants and properties of materials, the development and maintenance of the national standards

of measurement in the physical sciences, and the development of

methods and instruments of measurement, to the development of special

devices for the military and civilian agencies of the Government*

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

and various scientific and technical advisory services. A major

portion of the N8S work is performed for other government agencies,

particularly the Department of Defense and the Atomic Energy Commission. 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. The scope of activities is suggested in

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 itseif 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 re- ports 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 t 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 calibration 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 Of fice

.

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