Please see PDF version

The Annals of Probability
1977, Vol. 5, No. 6, 10361038


University of British Columbia
The uniform empirical integral differences of Sethuraman's large deviation theorem are proved to converge arbitrarily slowly.

1. Introduction. The purpose of this note is to answer a question of N. Glick [2, page 13801 concerning the rate of convergence to zero of a family of sample means as introduced by Sethuraman [1].
To introduce Glick's question we let (0, X, P) be a probability space, and let X, i = 1, 2, . .. be a sequence of Mvalued Borel measurable random variables which are independent and identically distributed. We will suppose also that M is a complete separable metric space. The distribution of the X,(w) will be denoted by p(.) and the sample probability measure of X,(co), X,(w), . . ., X,,((o) will be denoted by u(n, o), .). (That is, p(n, w, .) is the measure which places mass 1In at each of the points X,(w), X&), . .., X,.(w).)
Numerous authors have considered properties of the random variable defined by

(1. 1) supf., l~f(x)p(n, o), dx)  ~f(x)p(dx)l
where J7 is a suitable class of functions on M. Noteworthy among such results
both for its precision and generality is the large deviation theorem of Sethuraman
[11 and [2]. This result says, under certain restrictions on _57, one has for e >
0 that

(1.2) lim, 1 log P(supf . 1 ~ f(x)p(n, o), dx)  ~ f(x)p(dx)i ~ c)
log 6)

where 0 < a) < 1. The conditions which Sethuraman requires of in
(1.2) are only two:

(S) J7 is a class of functions from M to the real line which is precompact in the topology of uniform convergence on compact sets;
(SJ There is a function g(x) such that Iflx)l ;5 g(x) for all f e 97~ and such that ~ exp(tg(x))p(dx) < oo for all t.

The question posed by N. Glick [2, page 13301 is to ascertain the truth or falsity of

(1.3) n' supf. , 1 ~ f(x)p(n, o), dx)  5 f(x)p(dx)i = 0,(1)

Received February 28, 1977; revised May 16, 1977.
AMS 1970 subject classifications. 6OFIS, 60F10, 62E20.
Key words and phrases. Empirical measures, slow convergence, uniform convergence.


where 97satisfies the Sethuraman conditions S1 and S,. (Here one writes Z.. 0,(1) to mean, as usual, that max. P(Z,, ~t 2) > 0 as A+ oo.)
The fact that (1.3) is false is one immediate consequence of the main theorem of this note. Much more pointedly, it is proved that the random variables (1. 1) converge to zero arbitrarily slowly.

2. Main result.

THEOREM 1. Let X,, i = 1, 2, be i.i.d. and uniformly distributed on [0, 1
For any sequence c. such that c,). oo there is a class of functions J7 which is (a) uniformly bounded by 1 and (b) compact in the topology of uniform convergence such that

(1.4) c. sup,., 15 f(x)p(dx)  ~ f(x)p(n, a,, dx)i .> oo
with probability one.

PROOF. To construct the class J7 suppose that 0 < h, < 1 is a sequence of reals such that h. .> 0 and k. is a sequence of integers such that k. > n. For each n a finite set 9~ of functions is defined by the following procedure.
First [0, 11 is divided into k. intervals of equal length. Next a function f on [0, 1] is defined by (1) choosing n of the k. intervals and definingf to be zero on the chosen intervals; (2) defining f to be zero on the first and the last of the intervals; (3) definingf to be h. on the intervals wheref is not yet defined and which are not adjacent to intervals wheref has been defined, and (4) defining f by linear interpolation on all remaining intervals.
Finally is taken to be the set of all f defined by the preceding process. We note the elements of 97, are bounded by h. and that 5;~ contains at most Cn) distinct elements.
The class _57is defined to be the union of all the 97~ and the function which is identically zero. Since h. > 0 and since each is finite, any infinite sequence from .~7is seen to contain a uniformly convergent subsequence. Since the uniform topology is metric, this shows 57 is compact.
To provide estimates for (1.4) we suppose that k. is chosen so large that for A~ = {o): 1Xi  Xil :!9 llk,, for some i # j, i, j ~5 n} we have P(A.) ;5 l/n'. It will also be supposed that k. is taken so large that 2(n + 2)/k,' < h.12 for our future convenience.
Now for each o) e A,c one can select an f * e J~ such that f * is zero at each of the points Xl(o)), X,(w), . . ., X.(w). Consequently one has ~ f *(x)p(n, W, dx)
0. On the other hand, by elementary geometry one has
5 fp(dx) k h.  2(n + 2)/k.

for any f c Hence by the choice which was made for k., one has for
o) e A,,',

(1.5) supf. , 1 ~ f(x)p(dx)  ~ f(x)p(n, o), dx)l k J~ f*(x)p(dx)  ~ f*(x)p(n, o), dx)i ~> h~12


Since P(A. i.o.) = 0 by the BorelCantelli lemma we have for a.e. 0) an N(O)) such that

(1.6) c. supf., 15 f(x)p(dx)  ~ f(x)p(n, o), dx)i ~ c,,hJ2
for all n N(w). Finally, since the only property of h. required in the con
struction is that h.> 0, the h. can be selected such that c. h.  > 00. Such a
choice completes the proof of the theorem.

3. Applications and extentions. One should note that the class constructed in Theorem 1 certainly satisfies the Sethuraman conditions S, and S,. Con. sequently, the question posed by N. Glick is completely answered. In the style of that question one now has that

sup.., 1 ~ f(x),u(dx)  ~ f(x)p(n, o), dx)l = o,(1) is best possible under the conditions S, and S,.
The construction used in Theorem 1 obviously can be applied to yield more general results. In particular one can prove

THEOREm 2. Let X,, i = 1, 2, . .. be i.i.d. random variables which take values in R' and which have distribution p. Suppose also that pis not concentrated on any countable set. Then for any c, ), oo there is a uniformly bounded class 97 which is compact under uniform convergence such that (1.4) holds with probability one.

The proof of Theorem 2 requires only mild modifications of the technique used previously so it will not be given.

4. A conjecture. The two previous results should not make one overly doubtful of relationships such as suggested by (1. 3). In particular, if one considers a class G of functions on [0, 1] which are uniformly bounded and have uniformly bounded derivatives, the techniques of the present note do nothing to discredit the conjecture that

(4.1) ni supf. G 1 ~ f(x)p(dx)  ~ f(x)p(n, o), dx)i = 0,(1)
There are reasons to believe that (4.1) is in fact true. If (4.1) is true this fact would have several uses, and if (4. 1) is false this too should be learned.

[11 SETHURAMAN, J. (1964). On the probability of large deviations of families of sample means. Ann. Math. Statist. 35 13041316.
[21 SETHURAMAN, J. (1970). Corrections to "On the probability of large deviations of families of sample means". Ann. Math. Statist. 4113761380.