NATIONAL BUREAU OF STANDARDS REPORT

1996

CHANGES OF SIGN OF SUMS OF RANDOM VARIABLES

by

P» Erdos and G. A. Hunt

<NBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. s. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

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

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

the divisions and sections 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.

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

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

Technology. Length. Gage.

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

Lubrication. Engine Fuels. Cryogenic Engineering.

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

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

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

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

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

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

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

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

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

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

Development.

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

Instrumentation.

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

Frequency Standards. Microwave Standards.

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

Electromechanical Ordnance, and development in advanced ordnance. Activities include

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

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

Defense.

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

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

Department of Defense.

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

NBS PROJECT NBS REPORT

1101-10-5100 August 29 , 1952 1996

CHANGES OF SIGN OF SUMS OF RANDOM VARIABLES

by

P. Erdos

National Bureau of Standards , Los Angeles

and

University College of London

and

G. A. Hunt

National Bureau of Standards 5 Los Angeles

and

Cornell University

PREPRINT

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

Office of Naval Research., USN.

The publication, reprln'

unless permission Is obt

25, D, C, Such permisi

cally prepared If that

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

part, Is prohibited

idards, Washington

rt has been specifirt for Its own use,

CHANGES OF SIGN OF SUMS OF RANDOM VARIABLES

^7

Po Erdos and G„ A„ Hunt

le Let x-p Xgc, 0 0 0 be independent random variables all hav^

ing the same continuous symmetric distribution^ let ~ x^ +

° ° !

and let N be the number of changes of sign in the sequence

XX

I s 5 n+1

Th 1, n

k~l

d. Eh}

n

k*l

Here EjN l denotes the expectation of N^ and 0(k) is

2lLk/2.Kll (

k

k+1 \[Jc/2

]) 2

Th 2o With probability one lira N^ log n ^ i|* We conjecture 9 but

o“k ^ ( 2 nf k) ”^/2

1

2

'

cannot prove s that also Tim N^/ (n log log n) £ l e

By considering certain subsequences we obtain an exact limit

theorem which is still Independent of the distribution of the x^

Let e< be positive and a the first integer such that (1 + cx) a ^ 2|

let I

s

c, 2\ o o o be any sequence of natural numbers satisfying

(k + l)

9 ^ (1 + c*)ks | and N^ be the number of changes of sign in

k+l‘

where s'J

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

Office of Naval Research9 USN„

National Bureau of Standards s Los Angeles 9 and University

College of London

National Bureau of Standards, Los Angeles, and Cornell University

Ih 3 e{^} » |

[k/a] and N’/ E^} 1

with probability one

<

It is likely that |[k/a] can be replaced by g-c*n/(l+o<) . For

k" - 2^ it is easy to see that s k/i\% so with probability

one the number of changes of sign in the first k terns of

Si, 09 *5 s ^

000 is asymptotic to k/U

«

Our proofs are elementary and hardly use more than Lemma 3

of the next section,, which gives Theorem 1 immediately We prove

Theorem 3 In §3 and then demonstrate Th 2 by considering particular

sequences ? 2\ ° ° °

«

A sequence °°° for which

N

r

. / log n 1/2 is exhibited in §U« And finally we sketch the

proof of the following theorem^ which was discovered by Paul Levy

when the x. are the Rademacher functions, 1

Th lie With probability one

n sgn s,

K. k~l

o(log n)

Our results are stated only for random variables with continuous

distributionSe Lemma 3 s slightly altered to take into account cases

of equality9 remains true however for discontinuous distributions!

the altered version is strong enough to prove the last three theorems

as they stand and. the first theorem with the exrbreme members slightly

changed,, The symmetry of the x^ is of course essential in all our

theorems

- 3 -

Let a-] s

° 00

s a

;n be positive numbers which are free in the

sense that no two of the sums a have the same value

n

These, sums^ arranged in decreasing orders we denote by S,

s S^ n |

q. is the excess of +'s over - ! s occurring in S,j and Q.~ q

+«<,• +q. # “X X" j_ x It is clear that Q . s Q for 1 ^ 1 < 2 1

2n-i

n

Lemma 0 = - i ^ ([n/^i + n

[n/2 ] -2b"1 for i i a

11"1

The proof of the first inequalitys which is evident for n = 1 ,

goes by induction. Let n > 1 and i ^ 2

.n-1 .

n-1

Define St and Qt for

3 3

1 ^ j “ 2 ' just as S„ and Q. above , but using only a . »

<3 <3 1 n-=± and let k and % be the largest integers such that - a ^ and

Sy + ^ S.« It may happen that no such k exists 5 then 1 ~ % and

jt> il. X>

Qi

s Qx

+ 2 “ t + t > 1

if i

4 2n“2

3

Q±-

Q’

ri -I + t

* 2n“1^: + t > i

1

2n

if 2

n”2 < £ < a

11"1

,, and

Q. ® Q® 1 + 2

11"1

- 2n“1 i i u 0n-l

if X

“ 2n ' . The remaining cases are dealt with in the same way.

In order to prove the second inequality we note that for each

i the maximum of is attained if the a_« are given such values that

S. > implies q„ ^ qv5 — this happens if the a. are nearly equal.

n_1

If n is odd is positive for i ^ i

Q

- 2

" and - i is maximum

for i - i » We have

u

Q. — ± \ 0

in/Z]

k“0

(n - 2

n~1

- ( [ n/2 ] + 1)

n ,n~l W2 L

n A similar computation for n even gives \ ' 2 '^1

• i^2'

and the

V J

same expression for Q. = i e This completes the proof

„

o

If e.p en+^ are real numbers let m(e.p c ^ ) be the

number of indices j for which jc,j > | h-j* c. We now consider

3

' ^ C i n + 1 positive numbers °°°

s ar+

-, which are ‘free* and define

M - M(a^ 5

° °

" s an+]_) “ 2m(±.a-^ s

•

o

• s ±a

n+2,)

the summation being taken over all combinations of + and - signs

„

Lemma 2 „ 2

n+1 ^ M * Ii([n/2] + 1) (s«)

It Is clear that M

.n+1

If a + °°° + a „ and we reduce Vl 55 ®1 '~n s

the other eases to this one by computing the change in M as an+1

is raised to + a^ + 1„ Let i be the integer between 1 and

2 for which Sc - < a , < Sc (we use the notation of Lemma 1 )

and let a^

+1 be slightly greater than S „ „ Then becomes

> S

± if a

n+^

is replaced by a^+1 and we see that there is a

contribution +I4. to M coming from the terms ±a

^

in the four sums

±S^ * a

n4Q_° In like manner B each +a_, occurring in S„ gives = 1| to M

and each -a. in 8, gives +h9 so that

M

<«i. •••» V Vi> M< a

i- V an+i

} W'k “ 1 >

“ 5 ~

Thus raising a

n+ ^

to 1+ aj+»«°+ anlowers M by U(Q^- i) = - 1)

and Lemma 2 follows from Lemma le

There is another more direct way of establishing the first inequality of Lemma 2 C Considering the n numbers (a,^ + a^s °°°9 an-(-l 5 we assume that there are at least 2" i^'“ inequalities of the form

(1) > IJ j > 2

or

(2) (a1

+ ag) > V

where the right members are positive, and U is a sum over

( a!

+ a

2

) 3 a a.. +13 an+1 with appropriate signs,,

and V is a sum over ° ‘

° s anii

° From. (1) we obtain an inequality

(l 8 ) by dropping the parentheses from (a^ + a^) in Uj from (2) we

obtain (2

! )s ap

> ap

“ F or a^ > V <= a^ according as a

2

is greater or

less than V (we assume without loss of generality that a^ > a

2

) e We

consider also the n numbers (a^ — a^ 5 °°’

s a

n+,p and bhe inequalities

(3) a > U

J j > 2

(U) ( aP

- a

2

) > vS

of which there are at least 2 e From (3) we derive (3

3 ) by dropping

the parentheses from (a.-, - a0 ) in U

8 j from (U) we obtain

(I4,

8 ) a^ > a

? + V

3 „ It is easy to see that no two of the primed inequalities are the same* Hence there must be at least 2°2n - 2 n ^

inequalities

- 6

n+X

in which the right member is positive. Taking into account the four

possibilities of attributing signs to the two members of each ine-=

quality we get the first statement of the lemma..

Lemma 3®

1

n+X

> + 4 0(n)

Here of course the x^ satisfy the conditions imposed at the

beginning of fl and 0(n) is the function defined there. Since the

joint distribution of the x. is unchanged by permutations of the

and multiplication of x, by -X3 we have

Pr >

3

where m and M are the functions defined above. So Lemma 3 follows

at once from Lemma 2

- 7 -

Ws cannot prove the inequality

n =2“ ^ P £ Prm+n nun

X.cx

1

n+m

< , Vr 0([n/m])

1. n+1

for m = n? which would make our later proofs somewhat easiere But

we shall use

(5) P 60([n/m]) < 3[n/m]' J2

and establish, it in. the fallowing manner; Let a ~ C n/m] and write

z •• X , + » + x

n+1

° + X. » u i, + • »

« + x , +

.1 am+ am+1

w = x , + ° » ° + x e It follows from Lemma 3 that the set E on n+1 ari+m

which the four inequalities \z\ < ju ± v ± wj hold has probability

at least 1 - U0(a + 1) and that the set F on which the two inequalities jv ± wj < ju j hold has probability at least 1 - 20(a). So

PrjEFj * 1 - 20(a) - U0(a + 1) > 1 - 60( a;

And clearly |u + irj > jzj on EF«

- 8 =

3«, It is easy to see that

E

n n ir,| -

i>—*->—o /> •> X ^fk ®k+i

<

°.

1 V“"l f. ,

.

• - 5 X H > |sk^

T V ksl k*l J

so that Lemma 3 implies Theorem 1,

Let us turn to Theorem 3„ Clearly the probability of and

,2k

2k'

i. differing in sign is l/h° Also

K-+S,

S-. j

is inde=

pendent of s£. and s

9 , j 9 for (k + a)

5 * (1 + oC) X i 2k\ Since

s l o has an even chance of taking on the same sign as 1

we must have PHs,8 s-f < 0 k u-a 2 Pr < o| = 1/8 » Eow5 if

s’ s^.+a < 0 there must be at least one change of sign in the sequence

SV Sk+U 5 s£

+a. Hence pk + Pk+1. + °°° + Pk+a-1 “ VS, where

Pk

~ Prjsk

sk+2 < oj 0 Consequently

( 6 ) E n

k

k. a]

and the first part of the theorem is proved

¥e next show that the variance of N

k

is 0(k) by estimating

p- . “ Pr4s ! s!,-i <0 and s! si n < Of for i < Let u - si,

| i i+i. j J"*'i J i v “ s! “ s! . w “ s! - s! ~i q z = s! -= s! and define the events i+l i

5 j i+l5 j+l j

Ag uv < 0

Bs |u| < |v|

Cs (u + v + w)z < 0

Dg |u + v + wj < | z j

D's lw 1 < | z j

Eg jz - wj > Ju + vj

so that = Pr{AB}-a - Pr{CD} s p^ , = Pr{ABCDj-e One sees immediately that As B 5 C 5 D" are independent and that ED ~ ED' 0 Writing E for the complement of E5 we have

ABCD « EABCD + EABCD”

1 ^ c E + ABCD 9

and

D* c E + D .

Hence

Pr{AB3D) ^ Pr{I} + PrfABC} Et{d ! ]

Pp{e| + Pr{ABC}(Pr{E) + Pr{D})

^ Pr{AC} Pr{cj Pr{D} + 2 Pt{e}

s P± P 1 + 2 Pt{e]>

How z - f is the sum of (j + l)

8 - (i + l)9 of the x” s and u + v is

the sum of (i + l)

8 of the x’sj moreover

(j + l)

8 - (i + l)

8 * {(1 + ^)d ”i -

1} ( i+1)

5 .

We may thus apply the inequality (5) following Lemma 3 to obtain

Pr{E} < 3{(1 +

provided j = i ^ a 9 A similar argument gives a lower bound for p_.

We have finally

10

for all ±9 2 ° This estimate yeilds

l“ij

>. p. p . + J i J

0-i (l + 0<) 2

e{^}2 + 0(k) .

Let us denote e[k^| by bj_. It follows from (6), (7) and Tchebyeheff' s

inequality that

l| > €| < 4-

£ k

for an appropriate c and all positive 6„ Hence

i > e

is the j“th term, of a. convergent- series if k(j) ~ so that

one* Since also bkQ)/b

and

N,k(j) 7 b

k(j) 1 with probability

k( j+1) 1

K. ^

M

k(j+1)

b

k

b

k(j)

for k(j) ^ k < k(j+l)c, the proof of Theorem 3 is complete*

Theorem 2 is obtained in the following way* Let r be a large

integer and let l', 2'

s

°

° ° be the sequence

n

r 5 (r + 1),

r% r(r + l) s (r + l)

2

coo /^(r + l) a °° % (r + 1)-J

'

5

Kl ni“l / » % / _ x rri r 9 r (r + 1), 00 % (r + 1)*%

with in defined by /

1+1 ^ (r + 1)^+1

> rm

0 Let us call 3 “favorable'

if (3 + l)

8 “ (1 + l/r)3 " c Then

a) (1 + l/r)j * ^ (3 + 1)

6 ^ (1 + rOj' for all 3

b) There are k + o{k) favorable 3 less than k (as k 00) .

We see at once that

log k

! - k log (1 + l/r) + o(k)

Furthermore § if 3 is favorable then 3

8 s r |(j + 1)

1 - 3

8 j-° sc 3 according to Lemma 3 S

and consequently

lira 21L lim 2N,'

*l \ k n “»oo log n k ~»oo log(k + l)

8

- lim

2Nk

(k + 1) log(l + l/r)

N. lim k

+ 1) log (1 + l/r)

_ 1 - (r + 1) log 1 + l/r

Letting r we have Theorem 2

13

ho Our construction of a sequence Xp Xg 5

° ° ° for which

K

n/ log n —5* 1/2 depends on the following observations* For a given

k define the random index i = i(k)

max |x,

l.dj ^n+1

and let A^. be the event |xjJ > Z |x. |, where the summation is over

j £ i3 1 ~ j “ k + lo Let f^ and g^ be the characteristic functions

of the events *sksk+1 < 08 and 8 i(k) - k + 1 and x

k+1(xy + ° ° ° + Xfc ) < 0o

It is clear gp g2 ^ 000 are independent random variables « that

2Pr|gk

^ lj- *= l/(k+l) 5 and that - gk on Ap If moreover

Z Pr|A^.| < 00 (here A^. is the complement of A^.) then with probability

one for all but a finite number of indices k* In this case

we have

n

n

f. k“l k

nE gk +

fc-1

1

HF+TJ + o(log n) 3

the last step being the strong law of large numbers applied to

gp g2 $ 000 Thus we have only to show that the x^ may so be chosen

that Prj^j s ojk jy saye

To do this we take x. = ±exp(exp l/ti = ) where u-, 5 000 is a

sequence of independent random variables each of which is uniformly

distributed on the interval (0 5 1) » For a given k let y and z be

the least and next to least of u^ s u

2 $

° °

° $ u

k+l? density

function of y and z is

(k + 1) k(l - z)

k ^ 0 < y < z <1

Consequently the event % 1/y > 1/2 + 1/k2 has probability

k

2/(k2+l)

dy (1 - z)

k“X

dz - 1 + 0(k“2

)

L2L__

-y/k"

t

‘ \r and the event E^s l/z > 3 log k also has probability 1 + 0(k,

It is easy to verify that as defined above contains D^E^l

PrjAjl = ojk and our example is complete.

so

- 15 -

5?o We prove Theorem 1* in the form

f n " y

l/k s | log n + ©(log n)

l“k~n

s, > 0

k

First EjT^J- - l/k = | log n + o(l)„ Next, the inequality

following Lemma 3 yields

“ S

’J < l sk!} “ t> k 9

so that

Pr|sk

> 0 and > oj- - |+ 0(|)^/;i %>k „

This implies

! (Tn} * | ^

Vk * 2 {l/U - <*$)*} £

1 2 = t (log n) + O(log n)

Tehebycheff “s inequality and the Borel-Gantelli lemma then yield

( 8 ) \ . 1 ci=s^» CD2

5 iog ^

where ~ 2

"

° arid the sequence is dense enough for (8) to imply

the theorem,,

[1] P 0 Levy Theorxe de l

8 addition des variables aleatoires Paris 1937°

October 1.3, 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.