iSfeatisMfeaJj tv XjftbOM' "^.tibaal v .7 r

„

w\v LOU ^L/j U . <J 1

' ' * B

' NATIONAL BUREAU OF STANDARDS REPORT

1601

*5 V. , W^v

Explicit Formulae for the Distribution

Function of the Sums of n Uniformly

Distributed Variables

by

A, M. Ostrows&i

American University

April, 1962

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. As tin, Acting Director

THE NATIONAL BUREAU OF STANDARDS

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

iag of the divisions and sections engaged in technical work. In general, each section is en- gaged in specialised 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 hack 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. Testers ture Measurements. Thermodynami c s . Cryogenics. Engines and

Lubrication . Engine Fuels.

4. ATOMIC AND RADIATION PHYSICS. Spectroscopy. Radi ometry. Maas 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. Electrodepoaition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

6. MECHANICS. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydreulics. Mass. 'Capacity, Density, end Fluid Meters. 7. ORGANIC AND FIBROUS HATER SALS. Rubber. Textile*. Paper. Leather. Testing and

Specifications. Organic Plastics. Dental Research.

8* METALLURGY. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy . Corrosion.

3. MINERAL PRODUCTS. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Building Stone. Concreting Materials. Constitution end Microstructure. Chemistry ' of Mineral

Products

SO. BUILDING TECHNOLOGY. Structural Engineering. Fire Protection. Heating and Air Con- ditioning. Exterior and Interior Coverings. Codes assd Specifications.

N. APPLIED MATHEMATICS. Numerical Analysis. Confutation. Statistical Engineering. Ma- chine Development.

12. ELECTRONICS. Engineering Electronics, Electron Thbes Electronic Computers. Elecfeyffiaie Instrumeat*ties.

93. ORDNANCE DEVELOPMENT. Mechanical Research and Development. Electromechanical

Fuses. Technical Services. Missile Fusing Research. Missile Fuzing Development. Pro- jectile Fuses. Ordnance Components. Ordnance Tests. Ordnance Research.

W. RADI© PROPAGATION. Upper Atmosphere Research. Ionospheric Research. Regular Propagatic* Services. Frequency Utilisation Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

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

Missile Instrusentation. Technical Services. Combustion.
NBS PROJECT NBS REPORT

1102-21-1104 1601

Explicit Formulae for the Distribution

Function of the Sums of n Uniformly

Distributed Variables

by

A. M. Ostrowski

American University

April, 1952

Approved for public release by the

This report is issued Director of the National Institute of ion. reprinting, or reproduction

in any form, either in Standards and Technology (NIST)

emission in -rating is obtained

froa) the Office of the , Washington 25, D. C. on October 9, 2015

Explicit Formulae for the Distribution Function

of the Sums of n unifomly Distributed Variables

A„ fi 5 Ostrovski#

( 1)

1 . Let

«5 O <? O $

be n variables subject to the conditions

( 2 ) ! yH,VO(v -

and uniformly distributed In the corresponding intervals. %b&

distribution function F(cr) of the sms

C 3 J ?X t” o o .+ § |2

that is the probability for the inequality

(*). ^l *..„+ 5n i<r*

^

s has been a as far as I know, given explicitly only in the per1)

tieularly simple case °<£ ®°^2 *.«3<x

?j by Laplace • Indeed its

expression becomes /extremely eates« in the general case if

one does not use a convenient symbolism

,

2, Me us® the following notations. By w© denote

Further m will use the "displacement operatorw &' defined by

was 'prepared under contract of the National Bureau of

Standards with the American University, Washington, D. C. I

should like to gratefully acknowledge the discussions with Mr.

¥. F. Cahill, Brs.J* Ea Curtiss, ' C„ Elsenhart, F;, E. Greenwood,

A* <J. Hoffman, E „ Litoes and J„ fodd

.

1 .Laplace ^collected xmpers vol.7,PP 257-260?cf &1&® JT.V .Uspensky,Introduction to Mathematical Probabilities 1937,PP 277-278 end the

example 8-XO on page 200 jH .Cramer ,£-&thematleal Methods of Statistics

1940 ‘pp 2W-246*M.G.Eandftll*®ie Advanced Theory of Statistics, wol 1,

third edition , 19^7 ,pp . 140-145 sFeiler*Introduction to Probability

Theory and its Applications , vol *X ,Chap . XI , pp .255 -236 9 problems 11,
’ v \.:£ \:o , C

' ' -’v;^ i.u* w4 •,

\ ,.

' - =•• '. Vv ; ..

f
m Sjj f « s$ r

C

m) - r{n~ty

.

Then our expression* for Fjr) is

a.)

(T) F<« - ,4p - A ( > - X~ + < , S'*-- -

+ -*

)

3 . iTi our proof of (7) we eonslder^as did fcaplac© (l.c)

5 tho corresponding discrete probability problem 6 Lot for a certain

integer b isfeieh will toad to infinity^** be the rational fractions

( 8) j

I f 4 m

*h**e the integers xv are "uniformly distributed" between ~m

v

aad ¥@ obtain the ezpr@gs.ions Fa

{sr) of the probability for

the S,tt@qm,l±tj

( 9) rt*- f rn 4 crm

and get -finally Ffer) &» Xim Fffi (o-) if a^-^oo So that

(ID)

si c<

\> *•

4. However tafcan the above notations are used* the standard

method of complex integration gives, as ms pointed out to mo by

2* The corresponding frequency function is

I T * } F * (cr) w ry; JX (i-s ia, d 4^)VI *« ^

1 * -% ’•v® i

v' * K ’A 5 this follows at one® from the relations

(7

W

)

^ ^ "t < ~ n (<* +

1

, (' n - 3, ~ ) a i?*» ) rf fa + «r£*kr

t - —Vn * 5 1 ^ ~ 1 /°s , f ->* tv--)

eh!oh v;t« iaaediateXy vsrifled

.

-2-
• '

. .
B*. Jo If* Curtiss, a mrj simple proof of (7} «,

fj. Another approach to our problem which goes back probably

to He A* Fisher, 19X5* is a, geometric one. Denote by ? the

parallelepiped (2) and by Rj» the common part of P with the half

plan© (4)^ than w® have

{ 11} M

ITT

where- |Pl « 2so< . .c^^lsth® volume of p and j?r | is the volume

of Pjy- o Already in the LapXacian case Kendall (l.e) has used

this representation of p(<r) and derived, from this geometric interpretatioa another proof of X&pX&ea 8 s formula in using a pretty

involved geometric argument , It ms pointed oat to sae by Dr,

A u. 47 Hoffman that in $sing the expression (11) the formula (T)

can he easily verified « and Dr, Hoffman's proof is probably the

simplest proof of the formula ( 7)

6* However it seems that the standard statistical method

of complex integral is not easily applied to th© following

problem of a sore special character. Consider th® a variables

(1) subject to the conditions

(12) M&X " 1. £

then we mat' to determine "the probability" F*(<r) for the inequality (4)

,

However th© problem 1® in this form from th© point

of view of continuous probabilities not even completely determined

,

It is 'therefore better to state the corresponding problem concerning

discrete probabilities , ¥e consider again for a positive integer

m a set of » variables {8) where the integer numerators rv ra

"uniformly distributed" between -mv and mv « Let F%(ir) be the

probability of the Inequality (9) under the additional conditio.?
-• -v»

: . .

- ,

•/
(13) Max - 1

then F# {sr) is defined as

P*(cr) - Lim F%(oi W fn co m

¥© obtain in this way

(»v «o)®

cis) FVi.pfcnj 7X("*"‘'X«M ^ °n & v-.l

r

t

To This expressless ©an be interpreted in the following

m,j 0 Let ba the probability of the inequality (4) under

the conditions (12) and the additional condition j 5^)« • in

assuming that and are equally probable ve obtain

fro® the formula (7) easily ‘the expression

(

ft) rj(, 4 ^ _J1

<16) F ' ( ^)=

1 -

S

and ( 15) ean b@ wittea in the fora

1 -tr S ^ ;a a* \ / v ^ “ 4

' —^ A ( i + s ')(°<+v)t

v = 1

(17) P*(<r) - A.°AA<r)

r.=i

( 18) % - -r

_ ^£_ .

-}- 9 .

8 & It sight therefore s©@® that (15) can foe obtained

by straight forward application of the elementary probability

theorems If each co is interpreted as the probability for the

©quality sign 5m (2) being attained just for -v « ^

0 However the

"weight coefficients'5 co^ cannot be interpreted in this way since

the probability that ‘the ©quality sign in (5?) is assumed at least

for both “v =* 1 and « 2 would then b© 4 <jx lo while the corres- ^ ± z. ponding terms in the expression of F*{oi obviously tend to zero

with m ^ oo 0
'

V V;

-

. ... : , ; :

•
9* On the other hand the geometric interpretation in this

mm ls sti11 possible , but not quit® obvious* ‘Th© natural im~

tarp^fetatiaa would fee in terms of the (n~l) dimsasXcm&X surface

_ , different

s^vds os f snd Pg-.. However s /(n~l) -dimensional "faces* of these

surfaces would have to fee taken with the weights , proportional to

their areas.

rf.g a matter 01 fa,oty.t was the problem of the determination of

the probabilities F^fT) which arose in the course of & discussion

o.i. a. certain modification of the relaxation method and was the

starting po^fc of this whole investigation «, For our ismaediate purpose

tfe® p#C<r) has only the meaning of the limiting values of F*M{cr)

! , 10, It my further be mentioned that from (xi) it follows

iamaeaistely that F(cn is for -«v#crJ-c< a strictly scmotonicaXlY

i^SESSSiSfi. function without stationary intervals , same then

follows for the expression (16) and since the weights (18} are

constants,, we see that F*(cr) is a strictly monotonicaliy increasing

function of cr for - «* & cr 4 ct.

XI j Since all essential points of our original proof of (J)

occur also in the proof of (15) , 1 do. not give explicitly my

proof of (?) ? but reproduce in section 12 with Ms kind permission

wi-v proof due to Br„ A* J* Hoffman and in the sections 13—22 give

proof ox (15) » It is? believed that the devices used in this

proof can be employed in other similar .problems.

12. As we have obviously in the notation of no * 3 jp j « £•%<% . (?) follows at once if we only show

j_ ~fr i

n 5 * \ l tt&) p i

i a

! <r * s*

M -v w

} ( Os nr cr

>)..

v'n

!t

' Ol r- Y , +• n /

.a.
V

'

f.

' t-

,
Fop a » 1 the right hand side Is

(20) (a*+'c<i)+ - (c

and in considering separately the eases CT^®<x, Q& rr <<*, # ~c<2. c cr < o and cr^ we see" that (20) In each, ease gives the

length of the pant of C~,e<x^x> with x^rCF * ¥© can therefore

proceed by induction and assusa© that (19) is true for (n-1) dimensions • Consider ’the section- PC'-

4*) of with the (n«X)~dimansIomX.

plan® xn ** u|it is obviously gi/en by the corresponding coordinates

xi ? » which satisfy t'ton the conditions

( 20)

i &

! ^ c*

J

v>-l ^ Ot, n *1 *,u

+ + v, cr -*

therefore ia applying (19) to p( u ) m have for its {a-lj-dlxansiosal

0” volume

21) cr

\

f h-i)t no S

‘

’ v> ) ( ©C - «< n + o *— U. }

n-1

and obtain now

(22) _J

(nm 01

Ao-s du.

tout the integral in the right hand expression is equal toy ( 7) to

* t

[<* ' "\n O’- 0--«n £j ( I - ^" }(f< + ^1

13, In what follows we will have to use the "generalized

toinoaial coefficientsM

(23)

n

'-t •

y] . $ ( n / , ^

0

n i v o y^e

h -

!j a, - - - a

-6-

-ws©
.

I. . ,
systematic us© of this notation together with tie sysaboli-sss

introduced in 130 „ 2 appears to be very convenient In many coaabina-*

torial discussions. Its use would also simplify considerably

Laplace f s argument (l.c.) for the case <=<, esc*^ |>re fe&ve

fcr- any integer !c ^2 and any integer Y

!s,)

l *H dj'- [d] ^ ;

as • follows at once from { 23 ) for and f-ko.

In applying (24) repeatedly we have for two integers kla k2 * and any integer K i 2

(») £ UJ- t\"]- [ J]. (1-5

Vsh« ^ h J

<. **.- Ki

'tl

i r

]

14 » Suppose now that we have for at-»eo and a variable infeeger to

(25) - |

-»(3 '• ^> 00 ) Sj

then

(at) la j/lr- -*

(3^! (n - 1 , 2 ,...) .

Indeed if QkQs then

| ^ j

is either aero of

{ 28}

.1 1 » n! s ks

And if (5 > Oj, the left side in ( 28) tends to 77 6 Idri generally

if yo assume In addition to (26) that/a variable Integer X r ^/m

then 370 have from ( 27 )

-7-
>
(29)

--“4 n A- ... n 6 - X / , - 0 pj

't + m 13

t K5* We have with the notation (2

(?o$ (i-x)-ft - T

p2-'®0

f>4B~X 1

U»“l J

A?

\ h ^ ** u & o ^ ° J

Indeed the right side expression is by (23)

co -1

n-2.

rl—IX

"»Ji ©

4 X- \si” S

(31)

® (X-x)

3.6 u If we have a development

t?o ?(x) «* 21 r(h)xk

K*-«®

we have fox* say integer

OO

x

yPc«)’ 21 w<K)x K +•

'I oo

? NU-f)*^ 2L S w (*) *

-fionam i i

*4

,3. = - «> fv- - OO

and more generally for any polynomial in z

(32) #(x)P(x) -Z. J#(Sk )H(*)xK

.

K* 17* We consider now a integers (n \2) *i8p* ,. .

,

,?% and

denote by Ok the number of representations of the Integer k as

the sine

( 33) (Ofe) k ® xx

4* . * o4*xn (jxjj | • « » .* 1 x.n

1 &

of ii integers x-v satisfying the indicated conditions, Then w© can

write :0t « mn 4 „ . .+m^2

cj© 2l t * s

-

•K*-« •'

• inrV - m * s {# 4 X 4-« - +

ar»v4 .1

X “ + X v „ _ _+ X / - -. "V * A'")

x f'\ ( i+ + x

: Vsi

m

*> - x~ ' M A (-7-i T- ) V=1 * * ?

•8-
' J.

'
(3*0

O©

c« x “

;% - oc

y-M, N n JL , x (i-x) 7T ( >- X

v /;

the right eld© expression is by {30} ma (32)

V - J. OO

n 7T X

iBv H

00 F) = E 5

K 7T

then ws ofci^n "* ‘ v<*i

a mv *l -V \ <\ -* Vi-ll k

S * ? I X ® °K ' L «-* J " 5

(35) |C = * V** H

fn v + i> [ ^ -ir W.-S- ^ i*

s. 0 - i

1 «IL , 3. mv

* * \\ lv\* V\-- H -»i

j i = A d r>-V j

l8o From (35) we have again for two integers ^

y ^4

4

L.

and since the right hand sm 1© by (25)

ic =I 7t(*-s^

r, )[^;1

n i= A 0-s*""1 ")

k*K« ' -Jai

' * J ">>*1

, K* r . I mv> e

\

: HtMn-1

/

K a ft 4 h -

1

r

! ?i>Ki+ n

r

+ {(^4 “h

n

- (

K ~ « V\ , ^ i. \ C + K1 1

1

/ 1 n

grs.i‘:\ Z C

ii\“ &.S. sr

vl)7\(

a TA v

-t 1

M

H-f n

19. ¥© denote now by 0 the number of representations of k

as the sue of n integers *? satisfying the conditions )x v |< m

f V «* 15 toe*} Obviously we obtain S3 & from Cjr ^L*VA replacing each
<V

'

\ : .

<W
X.f m denote now by % the number of representations of k as the

«? a Integers x^ satisfying th© condition

(;>8) Max ^ ,1

V m v ^

obviously Die «• C2c - and from (35) and iTT)

20. In order to obtain now the probability' ?*

ffi (9-) of no. 6

w obtain th® numbar of all "favorable oases” in replacing la th©

right- head expression of (39) by an arbitrary negative cumber

# and kg by the greater Integer k « for mj contained, in srja e Then

we obtain

<*>) Nm(<rt*.

J f\ (i-S**’’

4

)- S"t\ (i-s'""'1 1 )?[

l r‘ J

®» of "all possible oases” Is obviously

*> >n im * 7T ( *. •'»„ i-i) - 7T ( *m

v

-i'5 % ^ 3 § Vs 1

by dividing we obtain

$v „A C4a,t ^(g-;*= ~§; - ~7T

w 7\ C a w. v +i)- f\ (im~ i)

S 43L am^lw n-S-y

|A('-Sr

• ^AK 4 n

= 1 V=i

obtained now the solution of the discrete probability problem

fo:rnuXated in no. 6.

21 » She expression !sf (or) can be brought into a form

'it&jth ”ssefuX as well for a geometric interpretation aa for the

passage to the limit . Wo can obviously write for the expression

:»wm^ ‘the braces ia (40)

i

(43) f | = Z 7T S^TV («- 5#- s

/fi-1 V~1

n>_

but w@ have Identically

S(X- - (> + 5

lW,<v )(t.-s)

&M (43) becomes

n Z<

i^ 5 t

( 44 ) non tfe© other

s

r”'

i

and so ( 40)

:

( 45)

h) C <r m

22 ,

( 46)

w»—v*~ •~9

’ fr)

I7T

V-l

a ro v + i • n

\ ”/4“ / ' w* v* 1

4 <r

r

'(

\ - '• )

) / \ < i - ^ i J - |

Vr,/*j + i

i

n-<t« v f r H + K + f* “ - 1

I S (»-s)( „ j

' L n-i J

n

f-i ~ *&.

f*~t g. M , +4. v a J£> f im.:

v ' 71 0-5 v

-i-, fro

) L h-a. j,

-!>- a. Vs^+4-

j fV) £fL -> ct ~ ~ - •+ °< n -

G5 m -» &£} J

fo obtain now the limit of the expression (42) m divide both

%(tr) and & ffi by For the denominator w© obtain

m • l^i Vt

« Ijg^BMnjwrtcW** ,40

ih:b?» transformation la obtained in special i sing /?• h.? appropriate

way the Ida ntity

A \-7\b, .- £ ( A^ A s

v - ft a v t\ b, {

* - - ’ - ' j V; 1, ^ V-i, V-|H. + i

n A-A-.

i £ "A a, A bv ( v b,)

tM-l V^l »=*+!.

-.11
sin

.

.
and tilts tends to

vm m <A-X

O 0+ JLJ)

2 , In tli® numerator w» haw

m

n (tr m

m

w ,

ft

. i* j , a r^v v ~tt“ / _dw,s4i\*Tr / f l *4- S ’ ) / \ ' A ~ ^ ji \ ^”' v

ft- 1 •V-A >!

/ , AMv" * \ 8T ft ~

ft

Is developing the term corresponding to a value ©f ^

w; obtain ^ ~t

C*i-9) “nT, (

!+ «,* 7T ( i- %

km'*x )jX ( | — $

* mv jf

*+ f\- 4

V , * *&- M '*> !L - 5 V^il f

_ ±1- c:

- V

V1°A^ t ^v

)*{ & f M * K t /H»j1

- 2. ^ ' L h -> ?

where a is an Integer^ -a <& <n.TSae general term of tim right hand

side converges fcy the formula® ( 29) and (46) to

JL

t^-01

8’

?. (M* f ^

4 « .. )

oC "V 81 A

1ft

and the limit of (49) 1® therefore

»<V’*v --), JL_ (, a

1**) Kf'- s^") 7T f.- A

(«-d!

Z 2

-V"A-'!-3

(50)

¥e obtain finally

<«r) |

ft m

m*-i

Q

n ^f 1- • z. . ft - 1 ^ ~ t

i,_g8 t\ (»- s r*o^>o-);

She formula (15) follows- Immediately,

THE NATIONAL BUREAU OF STANDARDS

Functions and 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 ma- terials, 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 NBS 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 Pub l i cat i ons 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 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 , 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.
))))