ITERATED LOGARITHM INEQUALITIES*

By D. A. DARLING AND HERBERT ROBBINS

UNIVERSITY OF CALIFORNIA, BERKELEY

Communicated by J. Neyman, March 10, 1967

1. Introduction.-Let x,x1,x2, ... be a sequence of independent, identically dis-
tributed random variables with mean 0, variance 1, and moment generating func-
tion sp(t) = E(eix) finite in some neighborhood of t = 0, and put s,, = xl+.* +X,
Tn = sn/n. For any sequence of positive constants an, n > 1, let
Pm = P(f > an for some n > in).
The law of the iterated logarithm gives conditions on the sequence an which guar-
antee that Pm -* 0 as mn -a* c, e.g. it suffices that an > (2c log2 n/n) 1/2 for some c >
1 (we write log log n = log2 n, etc.), but says nothing about the rate at which Pm
tends to 0. In the present note we give explicit upper bounds for Pm as a function
of m for various sequences an, including sequences such that a,, - (2 log2 n/n) 1/2 as
n a o, and for which Pm = O(1/log2 in). Such bounds have interesting statistical
applications, based on the following considerations.
Suppose yl,Y2,... are i.i.d. with distribution depending on an unknown mean ,
and with known variance a2. Put Xn = (Yn - M)/a and define the interval In =
(.n- aanagn + aan). Then
P(I
P(,1 e In for all n > inr) = -nI < an for all n > in) = 1 - Pm# 1
asm- c. (1)
n
Defining Jn = n Ij for n > m, we can therefore assert with probability > 1 - Pm
m
that for every n > mn the confidence interval J,,, of length . 2aan, contains ,11 (cf.
ref. 1).
Example 1, Optional stopping: To test Ho: 1A = ,io with a given type I error with-
out fixing the sample size in advance, reject Ho if for any desired N > In, Jio X IN
Then PH, (reject Ho) < P, which can be made arbitrarily small by taking in large
enough. The power function P5,(reject Ho) is bounded below by a calculable func-
tion of jA which tends rapidly to 1 as A- o o

Example 2, Tests with uniformly small error probability: To test Hi: JA < jo
against H2: At > 1o, stop sampling with N = first n > m such that juo Z In, and ac-
cept H1 or H2 according as IN is to the left or to the right of 1Ao. The error probabil-
ity is then < Pm and EAN < o for all /.L # ,u (cf. ref. 3).
Example 3, Tests with zero type II error: To test Ho: = Ao against H1: A >
/Uo, reject Ho with N = first n > m such that In is to the right of IAO. Then
PH, (reject Ho) < Pm and for yt > /Ao, P,,(reject Ho) - 1. (EJSN < o for ,A > I.'o but
PHO(N = co) > 0, which may be an advantage.) The case in which a2 is unknown
can also be treated. The applicability of bounds on the Pm of (1) goes beyond the
usual statistical decision framework in which a stopping rule and single terminal
action are assumed.
We proceed to derive the basic inequality (8) below. Under the assumptions of
the first sentence of this section, let zn - e31n/' "(t) for any fixed t for which
1188
Downloaded by guest on June 26, 2020
 VOL..57, 1967 MATHEMATICS: DARLING AND ROBBINS 1189

sp(t) < co. Then z,, is a nonnegative martingale with expected value 1. A simple
martingale inequality asserts that for any positive constant b,
1
P(z. >b forsomen 1) .< (2)
(G. Haggstrom called it to our attention and has independently considered using it
to obtain simultaneous confidence intervals.)
Putting b = emt'21 for any fixed m and t > 0 gives
( Mt + n log sp(t) for some n > 1 _e-mt' /2, (3)
Sn >
2f t/

Define
hD(t)e 1 logp(t) (-*.las t 0); (4)
2 t
then
P(xn > t h(t) for some n > m) < emt212 (5)
Let mn -o c be any increasing sequence of positive constants and tl any sequence
of positive constants, i > 1. From (5) we have for any integer j > 1,
co

P(tn > tih(tO) for some mi < n< mn+l, i > j) < E e- it,2/2 = Qj, say. (6)
Defining the sequence of constants b. for n > ml by putting
bn = tsh(t1) for all n such that mni < n < mi+i (i > 1), (7)
we can write (6) in the form
P(tn > bn for some n > m;) . Qj (j _ 1). (8)
We obtain various iterated logarithm inequalities by making different choices of
the sequences mi, tj that enter into (8).
2. A Special Case of (8).-Put for i _ 3
mi = exp(i/log i), (9)
tj = (2 log i + 4 log2 i + 2 log A)112.nMi-l2, (10)
where A is any positive constant. Then from (6),
1 0
11 1
AXi=ji(logi)2
A log(j1 /2) - Oasj cX (11)
We shall now find an upper bound for the be of (8). A little algebra shows that for
mi < n < mj+j,
log i < log2 n + log n + log 2,
log2 i . log3 n + log 2,
Downloaded by guest on June 26, 2020
 1190 MATHEMATICS: DARLING AND ROBBINS PROC. N. A. S.

Hence from (10)

tj < (2 1og2 n + 6 1og3 n + 6 log 2 + 2 log A)12n-1/2e(2 10g2 n)' = f(n), say, (12)
and from (7)
b. < f(n)h(v.), (13)
where Vn (= the t1 of (7)) is some constant such that
0 < Vn < f(n) (2 log2n/n)112 as n - o.
-
(14)
For the normal (0,1) distribution, h(t) = 1. For coin tossing with p = 1/2 and
more generally whenever (p(t) _ etl/2,h(t) . 1 and we can omit the term h(v.) in
(13). In any case, since h(t) 1 as t 0 and f(n) 0 as n Xo h(Vn) 1 as
n -* c. From (6), (7), and (13) we have for j _ 3

P (t. _ f(n)h(vVn) for some n elog j) < Qj

> (15)
where f(n) is defined by (12), h(t) by (4), Qj by (11), and vn satisfies (14). By com-
bining (15) with the analogous inequality for - tn we obtain
P(| -n >_ f(n)h(vn) for some n > elok) . 2Qj (16)
where now (14) is replaced by
0<jvnj <f(n). (17)
Putting an = f(n)h(vn) we have an inequality for the Pm of (1) with an (2 log2
n/n)112 and for which Pm O(1/log2 m).
3. Other Choices.-Replacing (10) by
tj = (2 c log i + 2 log A) 1/2.m-l/2 (18)
for some c > 1, we find the same results (15) and (16) as before, where now
f(n) = (2c log2 n + 2c log3 n + 2c log 2 + 2 log A) 1/2n-1/2e(2 1og2 n) 1 (19)
and

-A(c- 1) j - 1/2) (20)

A somewhat different result is obtained by putting
mn = ai where a is any number > 1, (21)
and retaining (18) for to. We obtain from (3) for j > 1

P >tn 1 +-ND/ f(n) for some n > ai) =

A(C - 1) (j l/)c (22)
where now f(n) = (2c log2 n - 2c log2 a + 2 log A)112n-1/2, (23)-
and
(If D=Do-1.)
so~t)
_
et212,
then1 + 2(h(v.) - 1)+ for 0 < v, < a1/2 f(n) (24)
(If (p(t) < e12/2 ,then D, =1.
Downloaded by guest on June 26, 2020
 VOL. 57, 1967 MATHEMATICS: DARLING AND ROBBINS 1191

4. An Extension.-There is an immediate extension of the preceding results to

additive processes. Let X(r) be an infinitely divisible process, T > 0, with X(O) =
0, and let E(X(1)) = 0, E2(X(1)) = 1, and suppose X(1) has a moment generating
function sp(t) = E(etX(1)) in some neighborhood of t = 0. Suppose X(r) is separ-
able. A necessary and sufficient condition for X(T) to be such a process is that log
E(etX(T)) = Tg(t), where

9(t)g
W (ex- 1 - tx)) dF(x)
= J (e'x
and F(x) is a distribution function whose moment generating futiction exists in some
neighborhood of the origin.
Then exp (tX(T) - rg(t)), T _ 0, is a positive martingale, and an almost literal
repetition of the steps leading to (15) yields for j > 3

P( ) > f(T)h(vT) for some r > e < Q (25)

where
(2 log2 r+ 6 log3 + 6 log 2 + 2 log A 1/2
f(T) = 2lg +6lg e2 10g2 T)~

h(t) = -2 + -t2 g(t)

and v, < f(r), Qj as in (11).

We remark that in the case of Brownian motion, where h(t) 1, there are in-
equalities due to Ito and McKean4 and Strassen,6 the latter giving asymptotic re-
sults for j co also. The bound Qj in (25) is of the same order of magnitude as
their bounds, though the theorems are not, strictly speaking, comparable.
5. Remarks.-An inequality for the Pm of (1) should be obtainable from Chow's
inequality2 (which generalizes (2) and ref. 5) without our subdivision of
the n-axis by the points mti. Even within the framework of the present method,
a great variety of inequalities can be obtained, and by a closer analysis minor
improvements in the inequalities of Sections 2 and 3 are possible; for example, by
letting rnj -o a little more slowly than in (9) we can replace the exponential
factor of (12) by something closer to 1. In general, however, sharper inequalities
for large n require a larger initial sample size m.
In a subsequent issue of these PROCEEDINGS we shall give results analogous to
the above for random variables for which the moment generating function does not
exist; such results, based on different specializations of reference 2, are necessarily
less sharp. We shall also give explicit bounds on the EN of Examples 2 and 3
above.
* Supported in part by National Science Foundation grant GP-6549.
1 Blum, J. R., and J. Rosenblatt, 'On some statistical problems requiring purely sequential
sampling schemes," Ann. Inst. Stat. Math., 18, 351-354 (1966).
2 Chow, Y. S., "A martingale inequality and the law of large numbers," Proc. Am. Math. Soc.,
11, 107-111 (1960).
Downloaded by guest on June 26, 2020
 1192 MATHEMATICS: DARLING AND ROBBINS PRoc. N. A. S.

I Farrell, R. H., "Asymptotic behavior of expected sample size in certain one sided tests," Ann.
Math. Stat., 35, 36-72 (1964).
4 Ito, K., and H. P. McKean, "Diffusion processes and their sample paths," in Grundlehren der
Mathematischen Wiasensehaften (Berlin: Springer, 1965), vol. 125.
6 Rnyi, A., and J. H~jek, "Generalization of an inequality of Kolmogorov," Acta. Math. Acad.
Sci. Hungar., 6, 281-283 (1955).
6 Strassen, V., "Almost sure behavior of sums of independent random variables and martin-
gales," Proc. Fifth Berk. Symp. (1965), in press.
Downloaded by guest on June 26, 2020