ASYMPTOTEC SOLUTIONS TO
COMPOUND DECISION PROBLEMS

THESIS FOR THE DEGREE OF Pk. Dr

 

MCHIGAN STATE

mun DAWAFJ. VAN.RV7JN ‘

THESIS

WWIHINWIWIWIWHflEH w

31293 01083 5043

This ll to eattfg that the

thesis entitled

ASYMPTOTIC SOLUTIONS TO
COMPOUND DECISION PROBLEMS

patented by .
John Raphael Van Ryz in

has been accepted towards fulfillment
of the requirements for
Ph.D. degree in Statistics

I ATE-W Mum/ma,“ ,
jj Major profenor

February 20, 1964

Date

0-160

L I BR A R Y
Michigan State
"W

University

 

 

 

MSU

LIBRARIES
m

‘

 

 

 

RETURNING MATERIALS:
P1ace in book drop to
remove this checkout from
your record. FINES wi11
be charged if book is
returned after the date
stamped be10w.

 

 

 

LFEBZOSEBQB ;

.- l “3'?" ~

if»! r £27996

3&8. 0 631998 _

cs: U u

. gig & B Qfin.
! .xip' U L?

 

 

ABSTRACT
ASYMPTOTIC SOLUTIONS TO
COMPOUND DECISION PROBLEMS

by John Raphael Van Ryzin

Simultaneous consideration of a large number of statistical
decisions having identical generic structure constitutes a compound
decision problem. In this thesis, decision procedures depending on
data from all problems are shown to have certain Optimal properties
asymptotically as the number of problems increases.

More specifically, let Xa, a = 1,2,... be a sequence of inde-
pendent random variables with Xa having distribution Pea, where on
takes a value in the finite parameter space 9 = {0,...,m-l}. Let the
space of all sequences {6“, a = l,2,...} be denoted by 9”. Fix N and
consider the first N members of the sequence of Xa's. For each
a = l,...,N, it is required to make a decisiOn do among n available
decisions {0,...,n-l}. Such an N-fold decision problem is called a
finite compound decision problem.

Any N x n matrix of functions T(x) = (taJ(x)), where
toj = Pr {do = Jlx} with x = (xl,...,xN), a = l,...,N, J = O,...,n-l,
is a decision procedure for the N-fold compound problem. Define the
risk of any such procedure, denoted by R(6,T) for 6 a Q”, as the
average of the risks for the N problems. With Pi(e) as the relative
frequency of problems in the first N problems having Pi as the govern-
ing distribution, 1 = 0,...,mpl, we see that p(6)== (p0(6),...,pm_l(6))
constitutes an empirical distribution on 9. There exists a non-

randomized procedure t'(

P 9) Bayes against p(6) which has risk

John Van Ryzin

¢(p(6)) = R(6,t;(e)). The function R(6,T) - ¢(p(6)). called the regret
risk function for the procedure T, is used as a measure of the Optimality
of the procedure T.

Existence of asymptotically good, unbiased estimates
h'= N-1 {i=1 h(Xa) of p(6) is verified. To obtain procedures whose
regret risk function converges to zero as N-+~, these estimates are
substituted into the procedure t£(6) to form the procedure té, which

depends on data from all N problems. Under integrability assumptions

on the kernel function h, convergence theorems for the regret risk

function of th

are proved. These theorems are all uniform in 6 c Q“.
The main result is that if lhl3 is integrable with respect to

P., i = 0,...,m-l, then the regret risk function of t1 converges to

1 h
zero at rate 0(N-l/2) uniformly in 9 a 9“. If m = n = 2, faster uni-
form convergence rates of 0(N-1/2) and 0(N-l) are attained under suc-

cessively stronger continuity restrictions on P0 and P1 and
integrability assumptions on h. A uniform theorem of 0(N-l) for the
general m x n problem is also given under a strong continuity condition
on the family {PO,...,Pm_l} and a certain restriction on the m x n

loss matrix of the generic problem. Examples violating the loss matrix
-1/2).

condition are shown to have rate no faster than 0(N

Additional results are presented when m = n = 2 and P6 , for
a

a 1,2,..., depends on a fixed, but unknown, nuisance parameter
T = (11,...,ts) in a non-empty open set of Euclidean s-space. Under

suitable regularity conditions on the likelihood ratio of P and P

l 0
at the point T, an asymptotic convergence theorem, uniform in 6 a (20°
- +
and of 0(N (1/2) e).£:>O, is proved for the regret risk function of

John Van Ryzin

the procedure obtained by substituting the estimate 3 for p(e) and a
suitably chosen unbiased estimate EI= N.l Za=l k(Xa) for T. Theorems
which are Jointly uniform in 6 s Q“ and T c C, a compact subset of RS,
are also given. When s = 1, two theorems drOpping the factor N+6 in
the convergence rate are established under apprOpriate restrictions.
Many examples illustrating the extent, applicability, necessity,
and non-vacuity of the various theorems are added for completeness.

The emphasis throughout the thesis is on obtaining optimal

asymptotic procedures in the sense of uniform regret risk convergence.

ASYMPTOTIC SOLUTIONS T0

COMPOUND DECISION PROBLEMS
By

John Raphael Van Ryzin

A THESIS .

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Statistics

l96h

G 3 “Ma!
7/: [(04

to LANI

ACKNOWLEDGEMENTS

I wish to express my sincere gratitude to Professor J. F. Hannah
for suggesting the area of research and for his inspiring guidance
throughout this investigation. His comments aided greatly in improv-
ing and simplifying many earlier results. I am deeply indebted to
him for giving me the unpublished lecture notes upon which section 1.3
is based.

Many thanks are also due to Professor G. Kallianpur, who, in the
absence of Professor Hannah, served as my guide. His suggestion of
the problem of Chapter IV, as well as many illuminating discussions,
were extremely helpful.

The financial support and creative atmosphere provided by the
Department of Statistics at Michigan State University, and by the
Applied Mathematics Division of Argonne National Laboratory, were
invaluable. This research was supported in part by the National
Science Foundation and the Office of Naval Research. I am also
grateful for support of graduate study through National Science
Foundation fellowships from June, 1960 to September, 1961.

Finally, I wish to thank Dr. R. F. King for his editorial help,
and M. Jedlicka and G. Krause for their excellent typing and cheerful

attitude in preparation of the manuscript.

iii.

TABLE OF CONTENTS

LIST OF APPENDICES O O O 0 O O 0 O O O O 0 O O O O O O 0 0 0

INTRODUCTION . .

CHAPTER

I.

II.

III.

THE FINITE COMPOUND DECISION PROBLEM . . . . . . .

1.1
1.2
1.3

1.h

Statement Of the Pr0blem e e e e e e e e e
DeCiSion ProcedureS. e e e e e e e e e e 0
Estimation of Empirical Distributions on Q

Non-simple Decision Functions. . . . . . .

ASYMPTOTIC RESULTS FOR THE COMPOUND TESTING
PROBLEM FOR TWO COMPLETELY SPECIFIED DISTRIBUTIONS

2.1
2.2
2.3
2.h

2.5

Introduction and Notation. . . . . . . . .
An Inequality for the Regret Risk Function
-1 2

/ )

A Convergence Theorem of 0(N
Convergence Theorems of Higher Order . . .

Examples Satisfying Theorem 3 or h . . . .

CONVERGENCE THEOREMS FOR THE GENERAL FINITE
COMPOUND DECISION PROBLEM. . . . . . . . . . . . .

3.1
3.2

3.3

3.h
3.5

IntrOdUCtioneeeeeeeeoeeeeee

Uniform Convergence Theorem of 0(N'l/2).

Sufficient Conditions for a Theorem of
Higher Order 0 o e e e e e e e e e o e e 0

Uniform Convergence Theorem of 0(N-l).

Counter-example to Theorem 6 when (C) is
ViOla-tedeeeeoeoeeeeeoeoee

iv.

Page

vi.

10

1h

18
18
21
23
27
32

38
38

39

hl
h6

50

Page

IV. THE TWO-DECISION COMPOUND TESTING PROBLEM IN
THE PRESENCE OF A NUISANCE PARAMETER . . . . . . . . . 53

he].IntrOduCtioneeeoeeeeeoeeeeeee53

h.2 A Convergence Theorem in the Presence
Of a NUisance Parame'tere e e e e e e o e e e o 57

h.3 Examples for Theorem 7 . . . . . . . . . . . . 6h
h.h Uniform Theorems in the Parameter T. . . . . . 69
h.5 Specific Results when 3 = l. . . . . . . . . . 78
SUMMARY. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
APPENDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

BIBLIOGRAPHY O O O O O 0 O O O O O O O O O O O O 0 O O O O O O O 92

V.

APPENDIX

1.

2.

3.

LIST OF APPENDICES

Page

Proof that Condition (11") Implies Condition (11')
whenu=P. .....................85
Truncation of E.to a Convex Set of Rs . . . . . . . . . 87

Extension of Results for a Randomized Procedure . . . . 89

vi.

INTRODUCTION

The idea of the compound decision problem was first presented by
Robbins in [lO]*. When a large number of decision problems of iden-
tical nature occur, then the compound approach is applicable. In his
paper, Robbins gave an example illustrating that when there are a
large number of testing problems between two normal distributions
N(-l,l) and N(l,l), then there exists a compound procedure whose risk
is uniformly close to the risk of the best "simple" procedure based on
knowing the prOportion of component problems in which N(l,l) is the
governing distribution. This compound procedure depended on data
from all component problems. Also in [10], heuristic arguments were
given to illustrate that such a phenomenon could be expected more
generally.

Hannah in [5] (see also hannan and Robbins [7]) extended this
result of Robbins to two arbitrary fully specified distributions;
while simultaneously strengthening the conclusion by replacing "simple"
by "invariant." Furthermore, in [7] it is shown that when the number
of component problems is large, the compound procedure given has risk
which is e-better than the available minimax procedure.

In this thesis, we improve and generalize some of the results of
hannan and Robbins. Specifically, we examine asymptotically the dif-
ference in the risks (the regret risk function) of certain compound

procedures and the empirical Bayes "non-simple" procedures.

 

*Numbers in square brackets refer to the bibliography.

l.

2.

In Chapter I, the general finite compound decision problem is
presented. Also, we define "simple" Bayes procedures, which in turn
motivate a class of "non-simple" compound decision procedures based on
estimatescnfthe empirical distribution on the finite parameter space.
Theorem I solves the necessary estimation problem, while Corollary 1
and Lemma 5 set the stage for later develOpments.

In Chapter II, we treat the case of compound testing between two
completely Specified distributions Po and P1' Theorem 2 extends the
basic theorem of Hannah and Robbins ([7], Theorem A) by strengthening
the asymptotic convergence rate of the regret risk function. Two
additional theorems (Theorems 3 and h) are proved. Both of these
theorems give faster convergence rates under certain continuity require-
ments on Po and Pl'

In Chapter III, we extend the results of Chapter II where possible
to the general finite compound decision problem of Chapter I.

Theorem 5 generalizes Theorem 2. Counter-examples to generalizations

of Theorems 3 and h are given. however, by restrictions on the loss
matrix of the component problem, Theorem 6 presents a suitable extension
of Theorem A.

In Chapter IV, the compound testing problem between two distribu-
tions in the presence of a nuisance parameter is considered. Conver-
gence theorems for the regret risk function are given under suitable
regularity conditions in the nuisance parameter.

At this point we introduce notation which will be used consistently

throughout this thesis.

3.
Let Rm be m-dimensional Euclidean space (R1 will be denoted simply
by B). Let x = (x ... x ) and y = (y ... y ) be vectors in Rm.
0. O m-l O, O III-1

Define the vector xy = (xoyo,...,xm_lym_l). The inner product and
m-l

norm of Rm will be denoted respectively by (x,y) = {i=0

xiyi and

l/2 . . .
"x" = (x,x) . The inner product (.,.) and norm “°" notations will
refer exclusively to Rm unless otherwise noted. Also, we will use
lxl to denote maxi Ixil.

Operator notation will be used to indicate integration. Let
(8,32?) be any finite measure space with ya O-field on S and P a
finite measure on (S.f). If X(s) is any real-valued integrable
function on S, then PX will be used to denote the integral J/N(s)dP(s).
If P is a probability measure and X is a real-valued random variable,
then PX denotes the expected value of X.

Also, we will make extensive use of the following notation for

the characteristic function of a set A. The characteristic function

of A will be denoted simply by A enclosed in square brackets; that is,

1 if a c A.
[A1(a) =
o if a t A.
In reference to the previous paragraph, if F is a set of F and X(s)
is any real-valued integrable function, then the P measure of F is
given by P[F] and the definite integral /:N(s)dP(s) by P(X[F]).
We will adopt the notation of Halmos ([h], Chapter VIII) to
indicate induced measures under measurable transformations. Let T
be a measurable transformation from (S,?,P) into (S', 3"), where 3"
is a a-field on S'. Then, let PT-l denote the finite measure induced

-l
on (8‘, f‘) under the transformation T. The measure PT is defined

by the identity PT'1[F'] = P[T'1(F')] for all F' e 5;".

h.

Finally, we shall make repeated use of the Berry—Esseen normal
approximation theorem (see Loéve [9], p. 288). This theorem, for
simplicity, will be referred to by the letters B-E and the uniform
constant in the bound by B. The standard normal distribution function
will be denoted by ¢(-) and the standard normal density by ¢'(-).

Further notation will be introduced as needed.

CHAPTER I

THE FINITE COMPOUND DECISION PROBLEM

1. Statement of the Problem.

Consider the following finite statistical decision problem. Let
U be a random variable (of arbitrary dimensionality) known to have one
of m possible distributions P6, 6 in the finite parameter space
9 = {0,...,m-l}. Based on observing U we are required to make a
decision d eoCr = {0,...,n-l} incurring loss L(i,J) (or Lg) if 'd = 3'
when U is distributed as Pi’ i = O,...,m-l; J = l,...,n-l.

If we simultaneously consider N decision problems each with this
generic structure, then the N-fold global problem is called a finite
compound decision problem. More precisely, let X“, a = l,...,N be
N independent observations each distributed as Pen with 6“ ranging in
9. Based on all N observations, a decision do in d5'is to be made for
each of the N component problems. For the nth subproblem, the decision
'da = 3' represents selecting the 3th column of the m x n loss matrix.
Note that in the case here considered all N decisions are held in
abeyance until all random variables X“, a = l,...,N have been observed.

In considering compound problems of the type described above, most
of the results are of an asymptotic nature; that is, as N + on. Hence,
it will be convenient to adOpt the following viewpoint. Let Q” be the
set of all sequences 6 = {Bald = 1,2,...}where ea ranges in 9. Consider
now the above-stated compound problem (for N finite) as imbedded in the

denumerable compound decision problem indexed by 6 e a”, 6 = {6“}.

.Let P6 be the product probability measure Xa=l Pe . The above N-stage
a

6.

compound problem is equivalent to the compound problem obtained by
observing the first N members of the sequence of random variables

{x1,x2,...} distributed as P e e 9.°

6’

Before proceeding, we introduce the following notation. With U
as the generic name for the random variables Xe of the component
problems, assume there exists a o-finite measure u dominating
{Po"'°’Pm-l} such that the measurable densities

dpi
(1) f.(u) =-—- (u) s K a.e. u
i d"

for some K < on. There is no loss of generality in this assumption
m—l
since we may always choose u = Zi-o Pi and K = 1.

J

Also in referring to the m x n matrix of losses L(i,J) or Li’

J

the rows will be denoted by Li’ the columns by L , and the difference

k
L(i,k) - L(i,J) by Lia, 1 = 0,...,m-1; 3.x = O,...,n-l.

2. Decision Procedures.
For the compound decision problem, a decision procedure may

depend on tne full observation X = (X1,...,XN). Any N x n matrix of

measurable functions T(x) = (taj(x)) will be called a randomized deci-

sion function (procedure) for the compound decision problem if for

d = l,...,N; J = 0,...,n-l, th(x) = Pr{da = Jlx} and 23-1

th (e) 3‘0
The a row of T(x) will be denoted by t (x) = (tao(x),...,tan_l(x)).

to3(x) ‘ l.

The decision function T(x) is said to be simple if there exist

. _ (a) -
functions tJ(.), J - O,...,n-l such that t (x) - (to(xa),...,tn_1(xa))
for a = l,...,N. A simple decision function will be denoted by

t = (to,...,tn_ ).

1

7.
With N fixed and 6 a an we denote by R(6,T) the risk function
for the compound decision procedure T(x). This risk is defined to be

(a)

the average of the component risks Ra(6,T) = P9(Le ,t (X)), for each
0.

subproblem, a = l,...,N. hence

N
(2) R(6,T) = N'1 za=i Ra(6,T) = P6W(9,T(X)),

N (a)

where W(6,T(x)) = N'1 2 (L6 ,t (x)).
n

“=1
The risk (2) may be considerably simplified in the case of a
simple decision function. For the sequence 6 e D” and i = 0,...,m-l,
define the relative frequencies, pi(6) = N.1 {:=l[ea = i], of problems
in the first N problems in which the distribution Pi governs. The

vector p(6) will be called the empirical distribution on 9.

Let t = (to,...,tn_l) be a simple decision function. The loss

incurred in using procedure t is

N
-l

(3) w(6.t) = N Z (Le .t(x ))

d=l a a

Zm-l
= p.(6) {AV _.(L .t(x ))} ,
i=0 1 60 -1 ed a
where AV6 =1 indicates the numerical average on the Npi values 9a = i.
0

Now since (L6 ,t(xa)) for 6a = i are independent identically distributed
random variabIes with mean pi(t) = Pi(Li,t(U)), we may express their
expected average as pi(t) to obtain from (2) and (3),

m-l

(h) R(6.t) = X pi(9) pi(t) = (p(6).p(t)).
i=0

8.
Let E = (50,...,£In 1) be any vector in m-dimensional Euclidean
space. Let tJ(u)1g_O, J = O,...,n-l be a set of measurable func-
n-l

tions such that 23_0 tJ(u) = 1. Define the function w(€,t) as

follows:

(5) W(€st) a (599(t))0

Note that for 5 = p(6) the function w becomes the risk function (h)
for the simple decision procedure t.

The problem of choosing t(u) to minimize w(€,t) for fixed 5 is
straightforward. From (1) and (5), we have
(6) Wat) = u) (£.L f(U)) tjw) .

3:0

Therefore, (6) is minimized in t for fixed 5 by any vector function
t5 (defined a.e. n) which is chosen as a probability distribution

concentrating on the columns LJ minimizing the quantities (§.LJf(u)).

That is, t is of the form

5
(7) tE J(u) = l, O or arbitrary, for (£,Ljf(u))
9
<, >, or = minv#J(§,va(u)),
n-l
such that t (u):g O for J = O,...,n-l and 2 t (u) = l a.e. u .
g”) J=o EIJ
Note that if E is abona fide a priori distribution,
m-l
(0 g 51, I £1 = 1), then such a t5 would be a decision procedure
i=0

Bayes against a.

We observe that any randomized procedure of the form (7) mini-
mizing w(£,t) may be replaced by a non-randomized version which
also minimizes w(£,t) for fixedg; In particular, one such non-

randomized version is given by the coordinate functions

9.
1 1r (£,L‘jf(u)) < or f—. (€,ka(u))
(8) t' (u) = ( according as k < J or k > J

S
0 otherwise.

 

\

To see that (8) is of the form (7) we merely note that
té(u) = (té’o(u),...,té’m_l(u)) is a probability distribution concen-
trating on the first column minimizing the quantities (€.LJf(u)).

In what follows we restrict ourselves to the non-randomized version

té of the Bayes procedure t

£0
In [6], p. 102, Hannah has given a useful inequality for Bayes

rules. A statement and proof ofla similar result is given here.

Lemma 1.
Let X be a space closed under subtraction. Let M(x,y) be a
real-valued function on X x Y such that M(-,y) is linear on X for

each y a Y and infy M(x,y) is attained for each x e X. Define

f(x) infy M(x,y) and let y(x) be any Y-valued function such that

M(x,y(x)) on X. Then, if x, x' e X,

f(x)

0 é M(x,y(x')) - f(x) §.M(x-x',y(x')) - M(x-X'.Y(x)).

Proof. The lower inequality results from the definition of f(x) and
the upper inequality follows by adding the non-negative term

M(X'.Y(x)) ' f(x')o

Now define for E c Rm the function

(9) ¢(£) = inft w(£.t) = (£.p(t€)).

10.
The last equality in (9) follows by noting that (7) minimizes w(§,t).

Observing that (£,p(t)) is linear in 5 and p, Lemma 1 and (9) yield

Corollary 1.
If a, 5' e Rm, then

(10) o 3 v(£.t£.) - ¢(£) 2 (€-€'.o(té) - 0(t£)).

This corollary inspires the non-simple rule to be adopted later
(see (12)). If p' e Rm is a good approximation to p(6) in the sense
that Hp'-p(6)|lis small, then Corollary 1 says that the simple proce-
dure tp,(u) has risk within "p‘-p(6)" Hp(tp,) - p(tp(e))” of the
minimum attainable risk in the class of all simple procedures, given
by ¢(p(e)). Therefore, not knowing p(6) in general, we seek estimates
p = p(xl,...,xN) of p(6) which with the aid of Lemma 5 take advantage

of the risk approximation of Corollary 1.

3. Estimation of Empirical Distributions on n.
The results in this section are based on some unpublished lecture
notes of Hannah [8].

Let OD’be the class of all distributions on Q = {O,...,m-l};
m m-l
that is, M0 = {nln e R , n. z 0, Z n.
1 - i=0 1
niPi with u-density fn(u) = (n,f(u)).

1} . For n e A” define

the probability mixture Pn = {m'1

The class of all distributions gg'is said to be identifiable if for
any n, n' a 5D, fn(u) = fn,(u) a.e. u implies that n a n'.

Let Ll(u) and L2(u) be the function spaces of u-integrable and
u-square integrable functions respectively. The usual norm and inner

product for r, g e L2(u) will be denoted respectively by “rIIu and

(fag) 0
LI

11.
Lemma 2.
The class 6£,is identifiable if and only if the set of densities

{fo,...,fm_l} are linearly independent in L1(u).

Proof. Sufficiency. Let fn(u) = fn,(u) a.e.u. Then, (n-n', f(u)) =
a.e.u and by linear independence of {f°,...,fmpl} it follows that

"i = n; for i = O,...,mpl. Hence, n = n' and 6Z)is identifiable.

Necessity. Let 0’ be identifiable and let c e Rm be such that

and c- as the positive and negative

(c,f(u)) = O a.e.u. Define c+ i

i

_ m- -1 mp1 + _ mpl -
parts of ci. Then 0 = u(c, f(u)) {11-0 c1 and hence {i=0 ci - i=0 ci.
m-l + _ m-l + -l c+ _ mpl + -l -

If {i=0 C1 > 0, define d: (2.1_o Ci) 1 and d;- (z.1_o c1) c1.

Then, f +(u) = r (u) a.e.u and by identifiability of 6’, d1 = d; for
d d-

all 1. Hence, c1 = c; - c; = 0 for all i and c = 0. Thus, necessity

is proved.

A vector function h = (ho’°°"hmpl) with coordinate functions
hi s Ll(u) is an unbiased estimate for the class MD if Pnh = n for
all n s W. Under the condition of identifiability of the class W ,
existence of unbiased estimates for M0 will be shown. .Henceforth, in
accord with Lemma 2, the set of densities {fo,...,fm_l} are assumed to

be linearly independent in L1(v). Let £3 be the class of all unbiased

estimates for the class AB.

12.
Lemma 3.
A necessary and sufficient condition for h s 8 is that
P h = a = (6 ,...,6

l 1 10 i m-l
Kronecker 6.

) for i = O,...,m-l, where 61 is the

J

Proof. Sufficiency. If (Pth) is the identity matrix, then
P h = h(Pih ) = n for all n a JD.
n J
Necessity. Observe that 6i 2 AD and unbiasedness of h imply

P h = 2.; that is P.h = e..
e i i i

The following subclass of 8 is of particular interest. Let 2)!
be the subclass of 5? such that if h s)%;, hJ e L2(u) for
).

Let S be any subspace of L2(u) and S

J = O,...,m-l, where h = (ho’°'°’hm-l

J'be the orthogonal comple-

ment of S in L2(u). For any g s L2(u), denote by gs, ESL the
proJection of g on S and SJ’respectively. Note that if g e L2(u),
8 = ES + 881'

We now give a theorem which proves the existence of unbiased
estimates for f and which yields the structure of the class 2%.
For J = O,...,m-l, let SJ be the subspace of L2(u) spanned by

{fili # J}. Let S be the subSpace of L2(u) spanned by {fo,...,fm_l} .

Theorem 1.

The class fi/ is non-empty. Furthermore, h a fi/ if and only if

2
h(u) = f*(u) + g(u) a.e. u, where f3(u) = (fJSJ(u)) (”fJSlllu )-1 and
J J

33(u) e SJ‘for J = O,...,m-1,

13.
Proof Note that since f. 5 SL' P-f' = (f* f ) = O for all i i J
‘ J 3’13 J’iu '
*_ i _ H 8
Also, we have that Fifi - (fi,fi)‘l - 1. Thus, by Lemma 3, f1 5
(and hence.3/ is non-empty since f; e L2(u)). Sufficiency follows
by observing that PiSJ = (gJ,fi)u = O for i,J = O,...,mpl.
Conversely, if h s fitfi, let h = hs + hSJ-having coordinate
functions hJ = hJS + hJSJ.for J = O,...,m-l. Since hJSL is in the
orthogonal complement of S for J = O,...,m-l, hs e.§#. Hence,
a _ = _ . e_ . .
(fJ-hJS’fi)u - O for i,J O,...,m 1. But this implies fJ hJS is in
SJ'as well as S. Hence, f” = hS a.e. u. Necessity follows by

defining g = hsln

Observe that the functions f: of Theorem 1 form the dual basis

to {fo,...,fm_l} in the conjugate space of the subspace S.

Corollary 2.

 

There exist h s f? such that Ihi(u)l ; M a.e. u for i = O,...,m-1

and M finite.

Proof. Choose hi(u) = f;(u) for i = O,...,m-1. Then, since the
fg's lie in S, they are essentially bounded as linear combinations

of the essentially bounded densities {fo,...,fm_l}.

The importance of the class 8 in obtaining estimates for p(6)
can now be seen. Let X = (Xl,...,XN) be the random observation for
the N-fold compound problem stated earlier. Define by use of the
kernel function h c {3 the random variable

N
- -1
(ll) h(X) = N 2a=1 h(Xa) .

in.
This equation yields an unbiased estimate of the empirical distribu-

.. -1 N
tion p(e) for all e s a“, since Peh(X) a N {081 can: p(e). If h oz?
and h is bounded as in Corollary 2, then EIx) inherits this bounded-
ness through (11).
Consider now the subclass 3! of 8 . If h I (ho’”"hm-l) e A],

then boundedness of the densities f implies P1h§(U) < 0. Denote the

i
variance of hJ under Pi for i,J = O,...,mpl as 012(h3)'
223;):
2 mp1
-— < 2 -1 2 2
If h e if; then PGHh-p(0)" = C N , where C = max1 {3'0 01(hJ)'

Proof. By direct computation, we have

__ 2 mpl __ 2
Penn-Ne)" = {J30 Pawn-pawn

_1 mp1 mpl 2
" 2J=o Zi=o 91(9) °i(hJ)

C2N-l.

I“

h. Non-simple Decision Functions.

With h s jfil and the estimate E(X) of p(6) given by (11), we
now define a non-simple decision function which results from substi-
tuting E(X) for p(9) in tp(0) as given by (7) (see Hannah and Robbins
[7], p. Ah). In so doing, we shall confine ourselves to that

particular non-randomized version of t ) given by (8) and denoted

p(e
by t£(e). The resulting non-simple, non-randomized decision

15.

procedure consists of the N vector functions t:(xa) = (t:. (xa),...,
h h,o

I
t__ (X )) for o = l,...,N, where
h,n-l o

f . __ J ... v
1 1f (h,L man < or ,<__ (n.1, f(xa))

(12) t:' (xa) = ( according as v < J or v > J
h’J

 

\ 0 otherwise,
J = O,...,n-l.

The question immediately arises regarding optimality prOperties
of the procedure ti, As a partial answer to this question, consider
the function h
(13) R(6.T) - ¢(p(e))

for the decision function T(x) and 6 e O” . This function will be

called the regret risk function against simple decision functions for

 

the decision procedure T(x). A worthy defensive goal is to select a
decision procedure T(x) which makes the regret risk function small
uniformly in O a Q”. In Chapters II, III, and IV it will be shown
that the procedure t:_(or a slightly modified version thereof), has,
under suitable condigions, good asymptotic prOperties in the sense
that its regret risk function given by (13) is close to zero uniformly
in 6 a Q” for N large.

We now give a useful decomposition lemma for the risk R(6,T) in

(13) for T(x) such that

T(a)

nu) (x) = tc(xa) ,

16.
where C = c(x) = ((xl,...,xN) takes its values on a finite Euclidean
k m-l

n-l(u)) is defined on R X U S.

(u),...,t i=0 1

k -
space R and tc(u) (tc,o C,

with s1 = {ulfi(u) > 0} such that 23;: tc.d(u) = l, tC’J(u) : 0.

Lemma 5.
Let T(x) be a compound decision function of the form (IA) and
let 6 a 9”. Then,

(15) R<e.T) = Pe<p<e>. o(tc))

-1 N k3
+ N Z(1:1 Zk¢J PePeaLea t§(a)’k(U) tCsJ(U) ’

(

Where 91(1):) = Pi(Li,tc(U)) and C U.) = C(xl’eee’xa_l,u,xa+l.eee,XN)

and the Pe integral in each of the N-terms of the second term of
d

(15) is on U.

(

a
Proof. Fix a = l,...,N and express P6(L6 , T ) (X)) as an iterated
a

integral, make a change of variable, and perform an added integration

as follows,

(16) P6(LeasT(a)(X)) =‘jkLea’tC(X)(xG)) dP9a(xa)ni#0gPGi

=[(Lea,tc(a)(u)) dP9a(u)ni¢odPBi

=fu.e ,t mm) are (mi ape.
o c o i
= P .
C
where POPS represents an iterated integral. Writing t (a)(u) =
a

t (a)(u) - tc(u) + tc(u) in the right-hand side of (16) and averaging
C

over all a, we have

17.

_-1N
(17) R(6.T) - N 23:1 P9P9a(Lea’tC(U))

+ N-1 ZN

“=1 P6P6o(Lea’tc(a)(U) - tC(U)) .

The first term on the right-hand side of (l7) may be simplified
to Pe(p(6),p(tc)) by noting that for ea = i’P6d(Led’tC(U)) are point-
wise equal to °i(t;(x))‘

The second term in (17) may be simplified to the second term
in (15) by observing that (L6 ,t (a)(u) - tc(u)) is the difference of
a C

two inner products and that the components of t (a)(u) and of tC(u)
C

sum to unity.

CHAPTER II

ASYMPTOTIC RESULTS FOR THE COMPOUND TESTING PROBLEM
FOR TWO COMPLETELY SPECIFIED DISTRIBUTIONS

1. Introduction and Notation.

In this chapter we discuss the compound decision problem of test-
ing between two specified distributions. Robbins [10] showed that in
the case where the component decisions were between N(-l,l) and
N(l,l) there exists a decision function whose regret risk function
approaches 0, uniformly in 659“, as the number of problems N becomes
large. Hannan and Robbins [7] extended this result to the case where
the component decisions were between any two completely specified
distributions. More extensive discussions of these and related
results are given in [S], [7], and [11].

We treat the case as given in [S] and [7]. Three uniform con-
vergence theorems for the regret risk function against simple decision

functions will be given. The first of these theorems (Theorem 2 below)

is an improvement of Theorem A in [7]. The improvement is in the
rate of convergence. Before proceeding to the theorems some nota-
tional simplifications for testing between two distributions Po and

P1 are in order.

Let m = n = 2 and take L(0,0) = L(l,l) = 0, a = L(l,0) > o, and

b = L(O,l) > O. Specify the dominating measure to be u = aPl + bPo,

and note that by (1.1),

(l) afl(u) + bfo(u) = l a.e. u.

18.

19.

Define now the measurable transformation into [0,1] by
(2) Z(u) = bfo(u)
with (l) implying that
(3) l - Z(u) = af1(u) a.e. u.

Let uzfil be the measure induced on [0,1] by the transformation (2)
and denote by uZ-l(z) the non-normed left-continuous distribution
function corresponding to uZ-l. Note that uZ-1(z) has total variance
a + b since uZ-l(0) = 0 and uZ-1(l+) = a + b.

Identifying ta(x) = to1(X) of Chapter I we can express a com-
pound procedure by the N functions ta(x), a = l,...,N, since
specification of tao(x) is not necessary as tao(x) = 1 - ta1(x). Also,
we represent a simple decision function by the single function t such
that ta(x) = t(xa).

For any p real, define the vector € = (l - p,p) in 2-space. In
accord with (1.5) define for the simple decision function t the function
(h) y(p.t) = b(l-p) Pot(U) + apPl (l-t(U)).

A simple decision function minimizing (h) for fixed p, as given by
(1.7), can with the aid of (l) and (2) be written as,

(5) tp(u) = 1,0, or 6 as Z(u) <,>, or = p, where O=<<Sp E l.

P

The non-randomized version of (5) with 6 = 0, corresponding to

P
(1.8), shall be denoted by t;.

Also, by defining B'= pl(6), we may simply express the Bayes risk,
given by (1.9), against (1:5;5) on Q = {0,1} as

' (6) ¢('e') = inft Malt) = Mat?) .

The assumption that PO and P1 are distinct implies that f0 and fl

20.
are linearly independent in L1(u). Furthermore, the choice of u
implies f0 and fl are essentially bounded functions. Thus, by
Theorem 1 there exists a scalar function hsL2(u) such that Pih(U) = i
for i = 0,1; that is, identify h with hl of Theorem 1 and regard 5*!
as a class of scalar functions (ho being defined as l-h). For such
an h e W, define for i = 0,1,

(7) of<t>

pi(n(u) - i)2, 32<n) = maxi=o,i (o§(h>}.

and for any 0 é p é l,

(a) o§(n)

po§(n) + (l-p) o§(h) .

From (1.11) we now have the unbiased scalar estimate g(X) = N-1

N ..

I h(Xa) of 9 and from (1.12) the associated compound decision rule
d=l

(here slightly modified at Z(xa) = 0 or 1) given by

tg(x) = (tifxl),,,,,t:(xN)), where, for o = l,...,N,
h

A

1 if Z(xa) E, Z(xa) 6 (0,1) or Z(xa)

O
(9) tfifixa) =

h 0 if Z(xa) l

"V
ll

'5', Z(xa) s (0,1) or Z(xa)
Observe that if E's [0,1], then (9) is a decision procedure Bayes
against a priori (IQR;R) in the component problem.

The Justification for modifying (9) at the endpoints Z(xa) = O
and Z(xa) = 1 will become apparent if one considers the risk function
R(9,t) for any decision procedure t(x) = (t1(x),...,tN(x)). The
component loss for the nth subproblem using t(x) is given by
a96(1-ta(x)) + b(l-6a)ta(x). Hence, this risk, as the expection of
the average of the N component losses, can, with the aid of (2) and

(3), be expressed as

21.

N
(10) R(6.t) = N-lpeza=l {°d(1’ta(X))(l'Z(xa))*(l'°a)te(X)Z(xa)}d“(xa)°

Now note that in (10) if ta(x) # l for Z(xu) = 0 or if ta(x) # 0 for
Z(xa) = 1 we may always redefine ta(x) at these endpoints to achieve
a risk which is at least as small as (10) (and maybe actually smaller,
in which case t would be inadmissible). To avoid such a possibility
with decision procedure (9) we have made the appropriate modifications

at the endpoints Z(xa) = 0 and Z(xa) = l, for o = l,...,N.

2. An Inequality for the Regret Risk Function.

 

We shall develOp a useful inequality (see (13)) for the regret

risk function. We have already defined the procedure t3 by (9) in

h
such a way that there is no contribution to the nth term of the risk

a
R(6,tgd in (10) at the endpoints Z(xa) = 0 or 1 for a l,...,N.

The risk R(6,t_) has this same prOperty since R(6,t_) R(6,t:).
6 6 6
Therefore, for convenience in notation, we define the restrictions

of the Pi measures to Z-1(0,l) as follows: P;(B) = Pi(BI"IZ-l(0,l))

for any Borel set B, i = 0,1. Also, observe that u' = aPi + bPé is
the restriction of u to z‘l(o,l).
Consider now the application of Lemma 5 to bound from above

R(6,t:) - 6(3). With tC = t: in Lemma 5, we bound the second term
h h
in the right-hand side of (1.15) from above by drOpping all terms

k
with negative coefficients Le
a

characteristic function form to obtain,

and express t:(n) and t: in their
h h

1 N kJ *
(11) N' P P L t—(a) (U)t_ (U)
021 k#J 8 ea 6a h 9k had
girl a: P P' [t(u) :2 <31
cell 9 l
—l ' _.5 4a)
+N bXQEI P6Po[h_Z<h ] ,
0
where I1 = {died = i} for i = 0,1.

The integrand in the first term on the right-hand side of (l.15)

can be expressed as w(6,t%) and, since t6 is Bayes against (1-6,6),¢(6)

by (6) equals w(6,t%). Hence, definition (h), expression of t; and

2
h

(12) (p(9).0(t%)) - (M?)

t in characteristic function form, and the definition of u' yield

(1' {(1-6)Z([Z<h-]-['z-<-e-]) + “e-(l-Z)([h'éZ]-['6-éZ])}

u' { ( 2:6) ( [Eiz<n']-[‘fisz<§] )} ,
where the second equality follows by set algebra and algebraic

cancellation.

Equations (11) and (12) combine to yield the following inequality

for the regret risk function:

(13) R(est§-)-¢(.9-)

; Peu' {(z-FH [BEBE-[$255] )}

+

-1 "(a)< "
N azadl P9 Pilh =z<h]

-1 _k _Jo) 9
' ...
N b 2:OLELIO P6 Pow.Z<h ]

+

where Ii = {olea = i} for i = 0,1.
When applying inequality (13) the three terms on the right-hand

side will be denoted by AN, BN, and CN respectively.

23.
3. A Convergence Theorem.of’0(N'l/2)3
Sufficient conditions for uniform convergence (in 959m) of
0(N'1/2) for the regret risk function of the procedure t;.will
be given. Before proceeding to the theorem we state the following

inequality: If C be a non-negative real number and if N'lépél, then

Verification of inequality (1h) is straightforward: If

(Np-1) % 02. then N1/2p(Np-l)'l/2c = Cpl/2(i-(np)-1)‘l’2

1/2
g p1/2(1102)1/2 , and if (Np-1) é c2, then N1/2p = (Np)1/2 p

"A

(1+C2)1/2 p1/2.

Theorem 2.

 

If h.e é? and e L3(Pi) for i = 0,1, then R(e,t§) - t(B) = 0(N'1/2)

uniformly in 6 a 0”.

Proof. In inequality (13) we show: (i) AN = 0(N‘l/2) uniformly in
e e an, and (ii) BN and CN are of'o(N'l/2) uniformly in e e O”.

(i) Since u'{(Z-O)([E<=Z<h] - [h-§Z<-6-])} é IE—B-Ha-tb) a.e. P9,

then Nl/2 AN é (a+b) pawl/25.61) .2 (a+b) can.) é (a+b) '5'(h).
Independence of 6 e am for the upper bound implies uniformity and (i) is
proved.

(ii) In bounding the term Nl/ZBN, we can assume without loss of

generality that I1 is non-void and oi(h)>0. If O§(h) = 0, then

_(0) ... _1 ..
h = h + N (h(u)-h(xa)) = h a.e. P9 x Pi for all a s 11, and hence
_Ia) ._
[h ;z<h] = 0 a.e. P6 x Pi for o 6 II; that is, EN = o.

2h.

Fix a e 11 and N and let 01 = 01(h) > 0. Define

2 _
S = {isll,i¢a (h(xi)-l), o = Var(S), and T = N(Z-9) + l - Zieloh(xi).
Then,
-(0)< -. <
(15) [h =z<h] = [T-h(xa)<S=T-h(u)] .

Apply the B-E theorem conditionally on u, xa, and x i 2 10’ to the

1’
normalized sum 0'18 at the endpoints c-1(T-h(xa)) and 0-1(T-h(u)) and
bound the resulting absolute difference in normal d.f.'s by
¢'(0)Ih(u)-h(xa)|O-l. Noting that 02=(N6;l)oi, the result from (15) is
(16) P6 Pi [h =z<h]

< .

= min{l.(Ne—1) (i'(o)ol PiPealh(U)-h(xa)l + 2da1))

_ -3 3
where al - Cl Pl|h(U)-ll .

Weakening the bound in (16) by the Schwarz inequality applied to

"A

Pipea|h(u)-h(xa)| {PiPe (h(U)-h(Xa))2}l/2 ; 21/20 , and summing (l6)
0.

-1/2

over all a s 11, we have BN é a 6 min{l,(N6;1) bl), where

2
bl = 21/ §'(0) + 2Bal. Inequality (1h) now yields the desired result

1/2 1/2

< 2
= a(l+bl) e

N B

N

1 2 1/2
/ cN 2 b(l+b§) , where bo =

A similar argument shows that N
21/2§'(0) + 28ao with a0 = OS3POIh(U)]3. Finally, since b0 and b1
do not depend on 6 a 9”, (ii) is proved. The theorem now follows by

(i), (ii) and inequality (13).

At this point it is worthwhile to make a few remarks regarding
the assumptions on h in Theorem 2. By the choice of u it is evident
that f0 and fl are essentially bounded and hence Corollary 2 guarantees
the existence of an estimate h which is also essentially bounded.Thus,
it seems unnecessary to weaken the assumptions on h in Theorem 2 to

include h's whose third absolute moments are finite under PO and P1'

 

25.

The importance of bounded h's is also illustrated by the constructive
procedure given by Hannah and Robbins ([7], pp. h2-h3) for obtaining
a uniformly bounded kernel estimate h which is unbiased and minimizes,
for fixed p, 0<p<l, O§(h) given by (8).

However, we present now an example which shows that the enlarged
class furnishes an unbounded unbiased estimate E(X) of E for all
6 c O, which is easy to compute when compared to the estimate ?3(x),

given by Theorem 1 and (1.11).

Example. Let Xe = (Xal,...,Xan) be the random variable for the 0th

subproblem. For each a = l,...,N, assume Xa1,...,X are n independent

on
identically distributed random variables having one of two distributions
Gi(') for i = 0,1. Let Gi(°) be a normal distribution function with
mean mi and variance 02, for i = 0,1. Assume “l > mo. Let Po and P1
denote the respective product measures 62 and GE. Denote by gi(.)

and Pi(°) for i = 0,1 the Lebesque densities of Gi and Pi respectively.
Then pi(u) =Ilg=1gi(“J) for i = 0,1 is the Joint density of the n
independent random variables Ul,..., Un'
Observe that pi(u), for i = 0,1 are bounded and we may apply

Theorem 1 and Corollary 2 to obtain a bounded estimate f*(u) =

f*(u ,...,u ). By Theorem 1, f*(u) = p [(u) "p 'L"-2 where p ,(u) =
l n 181 1Sl 181

-2

p1(u)-(po.p1)]]po]| po(u). The L2 norms and inner product in these

expressions are with respect to n-dimensional Lebesque measure. Simple

linear space algebra therefore yields

( ) *( ) IIpoII2 pl<u> - (po.p1> p.(u>
17 f u =

 

IIPOII2 llplllz - (P09P1)2

26.

We now compute the norms and inner product in (17). For i = 0,1

In“

(21702)-n

2
(18> bin

exp {-o-2(uJ-mi)2} du

n I
nJ=l J.»
= (21:1/2 O)-n

J

where the second equality follows from the transformations
v = 21/2 0-1(u -w.) for J = l,...,n. Also
J J 1
O
2 -n n J/' 2 -l 2 2
(2no ) IIJ=1 _m eXp {-(20 ) [(uJ'wo) +(uJ-wl) ]} du

(Pospl) J

(21rd2 ) n cnnn_lJ(; exp [-O-2[UJ - %(wo+wl)]2} du

J- J

where c = exp {-(20)-2(wl-wo)2}. The second equality follows by complet-

ing the square in u in the exponent of the n integrands. Transforming

J

the n integrands in this last expression by vJ = 21/20 -l[uJ "(m o+wl)]

l/2o)-n c“. This result

for J=l,...,n will then yield (po,pl) = (2n
together with (18), when substituted into (17), furnishes the unbiased
estimate
(19) r*(u) = (2n1/eo)” (l-c2“>'l (pl(u)-c“po(u)) .

With X = (Xl,...,XN) and X0 = (xdl’°'°’xan) for a = l,...,N, (19)

can be used as a kernel function in (1.11) to give the following

unbiased estimate of 6,
l N
- *
N {0:1 f (xa )

(20) ?*(x)

= (2"1/20)n (1-c2n )-lN '1 £:=1(Pl(xa ) -C npo (xa ))

-l N 2 n n 2
coN za=l{exP(clz:=l(de-wl) )-0 exp(0123=1(XaJ-wo) )} s

where co = (2)n/2(l-c2n)'l and c = -(2o2)'l. From (20) it is evident

1
that the unbiased estimate fP(X) of 6.15 not easy to compute.
However, consider the following unbounded estimate of 3: Let

- -1 n - -1 N - 1 -
x = n {J=1xa and x = N {uglxa. Define h(Xa) = (ml-mo) (Kc-mo).

27.

Then, we have P6 h(Xa) = 9“. Therefore, h(Xu) is an unbiased estimate
a

of 9a = 0 or 1. Hence, in accord with (1.11),

(21) T1710 = n-1 {i=1 ma) = (ml-worl (36 - we) ,

is an unbiased estimate of D for all 6 c Q”. The computational

advantage of (21) over (20) is apparent, and this example serves to

illustrate the usefulness of the weakened assumptions on h in Theorem 2.
The above example can be generalized to any two distributions

PO and P1 for which there exists a function C with Pi|c(U)I3 < m and

mi = Pi§(U) for i = O,l,mo¢m1. Define h(u) = (ml-no)'l (C(u)-wo).

Then h satisfies the conditions of Theorem 2 and can be used as the ker-

nel in (1.11). This is the type of estimate suggested by Robbins in [10]

_. _. - N
where he uses-%~(X + l), with X = N l 2 X , as an unbiased estimate

o=l a
of D'in the compound testing problem where the nth component problem is
testing N(-l,l) against N(l,l) based on one observation Xo°
In the next section this generality of estimates is not retained.
The proofs of Theorems 3 and h utilize stronger prOperties of h.

Theorem A requires essential boundedness, while Theorem 3 has strong

moment assumptions on h.

h. Convergence Theorems of Higher Order.

Convergence rates faster than that in Theorem 2 are obtainable under
successively stronger sufficient conditions. The following conditions
on the continuity of the induced distributions PiZ-l for i = 0,1 are
pertinent.

(I) Let the induced distributions PiZ"l be continuous functions
on (0,1) for i = 0,1.

1

It is an immediate consequence of (I) that u'Z' is continuous

(and hence uniform continuity) on [0,1].

28.

To see this, note that u'2'1(z) u[o<z(u)<z, Z(U)<l] implies that

u'z'1(o+) = infz,o u'Z'1(z) = 0 u'Z'l(O) and u'Z'l(l+) = infz>1

u'Z-1(z) 8 u'Z-1(l). These results together with left-continuity of

u'Z-1(z) imply u'Z-l is continuous on [0,1].

(II) Let A be Lebesque measure and Piz'l be absolutely continuous

with respect to A, for i = 0,1. Let there exist a K' < m such that

—1
dP'Z
(22) —l——(z) S.- K' a.e. A.
dA
It is an immediate consequence of (II) that
our1
(23) --a;--(z) é (a+b) K' a.e. A.

We now prove with the aid of inequality (13) the following two

uniform convergence theorems for the regret risk function.

Theorem 3.

- 2 -
Let h c f? be such that Pilh(U)—ilk é 2 loi(h)k! qk 2;

k = 2,3,...,i=0,l, and some q > 0. Then, if (I) holds R(6,t%)- t(E) =

o (N'l/Z) uniformly in 6 a 9”.

Proof. We show (i) AN = o(N’l/Z) uniformly in 6 c Q” and (ii) BN and
CN are 0(N-1/2) uniformly in 6 a Q”.

(i) Let c > 0 be given. Under assumption (I), u'Z'l(z) is
uniformly continuous on [0,1] (and hence on R). Therefore, there exists
a 6 = 6(5) > 0 such that u'Z-1[ ‘é 8-1/2

[21.22)] 2 whenever [22-21] < 6.

Choose No sufficiently large such that No ; 8(O€)-2 {(a+b)332, where
_2 .. ....
a = O 201). Let E = {lb-6| ; 6} and observe that by Tchebichev's

inequality,

29.

N'1 6'2 o%(h)

IIA

(an) Pew]

< - - -
= N l 6 2 02 .

Consider now the term A2 =N{Pu '(Z-6)[-6- é Z <h] )2. Use of the

l,N
pointwise inequality (Z-6)[6 5 Z <h]

"A (D1:

- - - 2
Ih-6|[6= z <h] in Al N.

2
l, N=

0%(h) Pe{u'[6 é Z <h]}2 . In the second factor of this bound, partition

fol-

lowed by the Schwarz integral inequality yields the bound A

the Space under the P integral into E and its complement EC, noting

6
that on EC, u'[6 é Zich] = u'Z-l[f6,h)] é 8-1/2 2 , while on E,
u'[6 é Z <h] ; (a+b). Hence, Ai N g o- g(h)(8-le 2 + (a+b)2 P6[E])°
D

Inequality (2h) and the choice of N yield for N g N , A g i-Ee.

o o l,N 2

By a similar argument we obtain A2 N=N Nl/2{Peu'(6-Z)[fiéz <6-J} §-:- 3:.

Observing that Nl/ZA = A +A the previous two inequalities yield

N l,N 2,N’

1/2

N A 5 3:. Since a is arbitrary, and since both 3 and No are inde-

N

pendent of 6 e a“, (i) is proved.

(ii) Let c > 0 be given. By uniform continuity of PiZ-1(z) on B,

there exists a 6' = 6' (e) > 0 such that P' lZ l[[zl ,z2 )] é§ :2 if

[22-21] g 6'. The proof for the term B relies upon properly bounding

N

the two terms on the right-hand side of the expression

(25) B, = m'1 a 2,811 Pym Path”) é z 651}

a 2,,IP1{(1-[F1>P[h‘°"= mm .

IM

Where F = {lz-§| 6'}. The two terms on the right-hand side of (25)

will be denoted by B and B respectively.
1,N 2,N

We first bound the B1 N term in (25) by a B-E approximation argu-
’

ment. As in the proof of Theorem 2, we assume without loss of generality

that of = oi(h)>~0 and I1 is non-void. By a B-E approximation condition-
. . th .
ally on u, x3, and xi, 1510 applied to a summand 1n Bl,N we have by

30.
(15) and (16).

(26) Pi{[F]Pe[h(°‘)£z <31}

-l/2 -l 0

§ min{Pi[F],(N6;l) (¢'(0)ol Pl

Pealh(U)-h(xa)I[F]+2BalPi[F])}.

Weakening in (26) by the Schwarz integral inequality to obtain

1/2

1/2
PiPeth(U)-h(xa)l[F] ; 2 ol{Pi[F]} , observing that our choice

of 6' implies that Pi[F] : s2, and summing (26) over all a 5 11, the

definition of B1 N and inequality (1h) yield
’

-l/2 l/2

[IA

(27) Nl/zBl’N ac2 Nl/2 E'min{l,(N3Ll) (2 §'(0)e'l + 28a1)}

lll‘

ae(s+2l/2§'(O)+2Bale).
Since a is arbitrary and the bound in (27) is independent of 6 a 9,, we
have
. 1/2 . .
(28) llm N B = O, uniformly in 6 s cm.
N.” l ,N

We now bound B2 N in (25) by Bernstein's eXponential inequality
’

given in the following theorem (see [2] for proof).

Theorem: (Bernstein).

 

Let Y , Y2,... be a sequence of independent random variables with

l
k—2

k
of = Var(Yi) and such that PIYi- PYiI ; 2'1 oik!q , for k = 2,3,...;

. _ _ n 2 _ n 2
l - 1,2,..., and some q > 0. Let Sn - {i=1 (Yi - PYi) and sn - 21:1 01.

- -1
Then, for any t > 0, P[{Snl>tsn] < 2exp{-(2+2qtsnl) t2} .

Before using this theorem for bounding B2." observe the following

set inclusion,
{IZ-E] > 6', h(u) < z <'h}
c {LEW} L){h'(°)-'é'<-6'} .
Substituting this set inclusion into 32,N and observing that a simple

-40) - ...-
change of variable implies P6Pi[h -e<-5'] ; Pe[h-6<-5'] for all a c 11,

31.
we obtain B2 N g aEPe[|hL31>6']. Application of Bernstein's inequality
9
to this last expression gives

a < 2a-6- exp{-N(6')2(20%(h) + 2q6')"1}

2,N
; 2a exp{4N(6')2(232(h) + 2q6')-¥} .

This exponential bound is independent of 6 s a” and hence

2

1/
limN+¢N B2,N

= 0 uniformly in 6 a 9“.
This last result together with (28), when substituted into (25)

2
/ ) uniformly in 6 e 9”. A similar argument holds

-1
implies EN = °(N
for CN and (ii) is proved. The theorem now follows by (i), (ii), and

inequality (13).

If the estimate h is essentially bounded by M, then the conditions
of Theorem 3 are met by taking q = 3-1M. The estimate h in the example
following Theorem 2 is an unbounded estimate satisfying the conditions

of Theorem 3.

Theorem h.

 

Let h e a and [h(u)] .5. M a.e. u. If (II) holds, then

R(e,t£J - ¢(3) = 0(N-1) uniformly in e e um.
h

Proof. We bound the terms AN, BN and ON in inequality (13). Expressing
the term AN in the integral form below and bounding in accord with (23)
(which flows from assumption (II)), we obtain a uniform bound for AN as

follows:

32.

-l
- p9fi(z.a')(['5';z<i] - [Hi-2661))”; (z) dz

 

>
2
I

"A

(a+b) K'Pefi z-F)[6-§z<h] dz

= N'1(a+b)%x'o§(h)
= N'l(a+b)!2'-K'o-2(h) .
The term BN can be treated in a similar manner after first bound-
ing 3(a): h + (h(u)-h(meN"l from below by h-QMN-l for each a 5 I1 and

then use assumption (II) to obtain,

— v "' -1 < -
BN . a6PeP1[h-N (2m) g z < h]
-1
— - ... i
= aepeflh-n'1(2m) ; z < h] dPiZ (2) dz
d.A
é N'l 2aK'M .

l 2bK'M.

In a similar manner, one has CN 2 N-
Substituting these three upper bounds for AN, BN, and CN

respectively into inequality (13) yields an upper bound on the regret

risk function for t%, given by N_l(a+b) K'(32(h) + 2M). Since this

bound does not depend on 6 a Q the theorem is proved.

5. Examples Satisfying Theorem 3 or N.

Two examples satisfying each of the Theorems 3 and h are given.

Example 1.

 

Let U = (U1....,Un) be the generic random variable for the cth
problem. Assume U1,...,Un are independent identically distributed as
either Go(t) = l - exp {-wot}, wo>o, t 2 0 or as 01(t) = 1 - exp {-wlt},
“l > O, t ; 0. Furthermore, assume that ”o < ”l < 2ND. Let go(t) and
gl(t) be the Lebesque densities of 00(t) and 01(t). Then Z(u) defined

by (2) is given by

33.

Z(u) bf0(u)

n
b HJ=1 go(uj)

 

a Hg=l gl(uJ) + b H§=l 80(uJ)

- - -l
{ab 1 (wlwol)n exp {(wo-wl) 22:1 “3} + l} .
The induced distributions PiZ'1(z) for i = 0,1 are given by

-1 = 9 < _ . n nn .
PiZ (z) w1,/(Z(u) z] exp { ml 23:1 uj} 3:1 duJ . Transformlng
this multiple integral by vk = 23=k “J; k = l,...,n, which has

Jacobian 1, followed by integration on the variable vn,vn_l,...,v2

yields for i = 0,1,

-l
w -w ) C(z)
- _ l o -
(29) P12 1(Z) = w? F 1(n) “é? v? 1 exp {-wivl} dvl
where g(z) = log {(mlwgl)n ab-lz(1-z)-l} . For i = O, transform this

integral by means of the transformation v1 = (ml-wo)'l§(w) to obtain

-1 -l
PoZ-l(z) = Co~/:z(l-W)(wl-wo) (ewe-ml) w(wo'wl) wl[C(W)]n-ldV

- '1 ( '1 '1 ‘*’o(wl"'wo)'-l n )-l
where Co - F (n){wo ml-mo) (“owl ) }

wo( (01" No
(ba'l)

- n n n -l
and C - bwo (awl + bwo) .

This integral expression immediately implies that Fez-1(2) is
absolutely continuous with respect to Lebesgue measure A, and we may

define the following density

dPoZ-l (ml-wo)-1(2wO-wl) (mo-w1)-lwl

(30) '—';;'_ (2) = Co(l-Z) z [t(Z)]n-l

if c 2 z < l and 0 otherwise.

Observe that the assumption 2wo > “1 > “0 implies that the factor
_ -l

(l-z)(w1 ”0) (2“0'w1) dominates the density (30) as 2 + l and hence

density (30) approaches 0 as 2 + 1. This result implies that density

(30) is continuous on the closed interval [C,l], and hence the density

3h.
(30) is bounded on the closed interval [0,1] (and therefore on [0,1]).
In a similar manner, it can be shown that
-l

dP Z w (w —w )‘l (w -w )'l(w -gm )
(31) --:;- (z) = C1(l-z) o l o z l o o l [c(z)]n'l

if C 2 z < l and 0 otherwise, where

- _ -1 n _ -1
C1 = F 1(n){wl(wl-wo)-1(wowl’l)w1(wl mo) } (ha-l)m1(ml wO)

An argument similar to that following (30) shows that density(3l)
is bounded on [0.1]. Note that the assumption 2mo > “1 is not
necessary in showing (31) is bounded on [0,1].

Since (30) and (31) are bounded on [0,1], assumption (II) is

verified and Theorem A holds for Example 1.

Example 2.

 

Same as Example 1 except assume that ml ; 2wo. Observe that the
density (30) now approaches a as 2 + l and, hence, is unbounded on
[0,1]. Therefore, the assumptions of Theorem A are violated. However,
asSumption (I) and, hence, Theorem 3 holds in this case by merely
noting that (29) implies that Piz'l[z=z] = o for i = 0,1 if

C ; z < l (and therefore if 0 < z < 1).

Example 3.

 

Let U = (Ul,...,Un) be the generic random variable for the nth

problem. Assume Ul,...,Un are independent identically distributed as
either Go(t) or Gl(t), where Gi(t), for i = 0,1, is a normal distribution
function with mean “i and standard deviation 0. Assume “l < mo.

Let go(t) and gl(t) be the Lebesque densities of Go(t) and 61(t). Then

Z(u), defined by (2), is given by

35.

z(u) bfo(u)

b "i=1 g0(“J)

 

n n
a “3:1 81(uJ) + b “3:1 go(uJ)

-1 n -l
{ab cl exp {c2 23:1 uJ} + 1} ,

where c1 = exp {n(202)'1(w§-w§).} and c2 = (ml-wo)a‘2 < 0.
Therefore, since 23:1 Uj is the sum of n independent normals, the induced

distributions PiZ'l(z) for i = 0,1 are given by

PiZ'l(z) PiUIUJ < c‘1 108 {(aclzrl b(l-z)}]

2

”61(2)
,/_m §'(t) dt,

where ;i(z) = (nl/zo)'l{c'2'l log {(aclz)’l b(l-z)} - nmi} and

¢'(t) is the density of N(O,l).
For i = 0,1, transform the integrals by t = (1(w) to obtain PiZ'l(z) =
J€z§'(61(w))lci(w)ldw' This integral expression immediately implies
that PiZ'l(z) is absolutely continuous with respect to Lebesque
measure A for i = 0,1 . Since Ic;(z)| = {nl/2 o|c2|z(l-z)}-l,
the induced Lebesque densities are given by

dP-Z'l
(32> --1--<z) = {cl/2 olc2Iz(l-z)}-l swim)

d1
if 0 < z < l and 0 otherwise for i = 0,1.
From the definition of ci(z), we see that ci(z) + —m or w according
as z + 0 or 1. Hence, §'(Ci(z)) + 0 at an eXponential rate as 2 + 0 or 1
and thus §'(C1(z)) is the dominant factor in (32) as 2 + 0 or z + 1.
Therefore, (32) + O as 2 + O or z + 1, for i = 0,1. Since the densities

(32) are continuous on the open interval (0,1), the above argument shows

that the densities (32) are continuous on the closed interval [0,1].

36.
This in turn implies that these densities are bounded on [0,1].

Assumption (II) is thereby verified and Theorem h holds for Example 3.

Example A.

 

Let U = (U1....,Un) be the generic random variable for the nth
problem. Assume Ul""’Un are independent identically distributed
random variables having distribution either G0(t) or Gl(t). Furthermore,
for i = 0,1 assume 61(t) is absolutely continuous with respect to
Lebesque measure and has density gi(t) = c(wi) exp {wiT(t)} h(t)
where T(t) is strictly monotone in t. Then Z(u). defined in (2),

is given by

Z(u) bfo(u)

{ab'l{C(w1)c'l(wo)}n exp {(wl-wo) 23:1 T(uJ)} + i}'1 .

Note that the induced distributions PiZ'1(z) for i = 0,1 are such that
<33) PiZ'1[Z=z] = Fitzggl T<u,> = c<z)1
for O < z < 1, where

z(z) = (ml-wo)'1 log{a’1b(l-z)z';fic(wo) c‘1(w1)]n .
With the aid of (33) we will show that PiZ‘“l is continuous on (0,1) for
i = 0,1, and hence Theorem 3 holds.

Let V(U1,...,Un) = {3:1 T(UJ). The measurable transformation V
from Rn into R induces a probability measure PiV'l, for i = 0,1, such that
(an) Pidgin m5) = ((2)1 = Piv-ltv = cm]
for 0 < z < 1.

Note that PiV'1(v) is the distribution of the sum of n independent
random variables T1""’Tm’ where TJ = T(UJ), J = l,...,n. Each of
n random variables T has, for i = 0,1, continuous induced distribution

J
functions P1T31(t) = Pi[T(UJ) < t]. Continuity follows since strict

37.

monotonicity of T(o) implies that PiT31[TJ = t] = Pi[T(UJ) = t]
= Pi[UJ = T'1(t)] = 0, for i = 0,1; J = l,...,n. Therefore, we conclude
that PiV-l(v), as the convolution of n continuous distribution functions,
is continuous, for i = 0,1.

Hence, for i = 0,1, we obtain that PiV'1[V = c(z)] = 0 for all
z in (0,1). This, in turn, implies by (33) and (3h) that PiZ‘1[Z=z] = O
for i = 0,1 and z s'(0,1).

We have now exhibited a whole class of distributions for which

assumption (I) and hence Theorem 3 are verified.

ChAPTER III

CONVERGENCE ThEOREMS FOR THE GENERAL
FINITE COMPOUND DECISION PROBLEM

I. Introduction.

In this chapter we shall extend Theorem 2 to the general finite
compound decision problem of Chapter I, where the component problem
has finite m x n loss matrix (L(i,J)). Counter-examples to the ex-
tensions of Theorems 3 and h are given. however, under a certain
restriction on the loss matrix (L(i,J)). a theorem analogOus to
Theorem h is proved.

In Chapter I, we prOposed the non-simple procedure tl defined

h
by (1.12). To facilitate asymptotic study, we express the regret
I

risk function of th in the form (1) below. Let p(6) = (p0(6),...,pm_1(6))
for 6 c Q” be the empirical distribution of 9. Recall that t;(e)

given by (1.8) with 5 = p(6) is a simple decision procedure Bayes

against p(6). Hence, by (l.h) and (1.5) we may express ¢(p(6))=

'

R(6,t%) = (p(6),P(t;)). Identify tC = ‘5 in (1.15) of Lemma 5 and
subtract the above term from the first term on the right-hand side

of (1.15). Since Corollary 1 yields (p(6),P(tfi) - ‘Kt;(e)) é

(P(9);B. P(tfi) - P(t;(e)), we then have

(1) a<e.tg) - ¢(p(6) é Pe<p(e)-B. p(tfi) - p(tp<e))

-1 k3 . .
+ N {0:1 JJ LeaPePeatE(c)’k(U)tE.J(U).

When applying inequality (1) the first and second terms on the right-

hand side of (1) will be denoted by AH and BK respectively.

38.

39-

1/2).

2. Uniform Convergence Theorem of 0(N-
The following theorem generalizes Theorem 2 for an arbitrary

m x n loss matrix.

Theorem 5.

 

If h e 6? and hJ e L3(Pi) for i,J = O,...,m-1, then

-l/2

R(e,tfi) - ¢(p(9)) = 0(N ) uniformly in e e 9,.

Proof. In inequality (1) we show: (i)AN = 0(N'l/2) uniformly in
6 e :2” and (ii) BN = 0(N-l/2) uniformly in 6 a £2”.

(i) By the Schwarz m-space inequality, we have,

N1/2 Pe|(p4h.p(t%) - p(t;)I

1/2 ~ 0 o
N Pelh-pfl "0(tg) - 0(tp)H .

(2) N1/2 A

"A

N

"A

Let Li - minJ L(i,J) and ii = maxJ L(i,J) and note that
(—
-Li = Range p1 = Li’ Then
' ' 2 m-l ' ' 2
(3) "p(tfi) - p(tp)u - 2._ {pi(t5) - pi(tp)}
l-O
m-l
< .—
= 2 (L. - 2,)?
. l 1
i=0
= [If - Luz, where
L = (Lo,ooo,Lm-l) and £0- : (9'0"...11111-1).

Also, note that by the Schwarz integral inequality and Lemma h,

(u) Nl/2 Fe n-p<e)| {upeua;p(e)u2}l/2 é o.

Inequalities (3) and (h), when substituted into (2), imply

1/2
N AN §C|ELE_

IIA

 

L Hence, (1) is proved.

ho.
(ii) Let I1 = {alea = i}, i = O,...,m-1. Let ri be the rank
of the covariance matrix of h = (ho,...,hm_l) under the distrizgtion
Pi’ i=O,...,m-l. Fix i, J, k, k < J and a e Ii’ and let d = L f(u)

and l (u) t% (u). Let h - ai = T2 with Zn an orthonormal

U
= t-
kJ h(a)’k ’
basis for the subspace of L2(Pi) generated by the functions h, - 621,
where c1 = (601""’6m-1,i) and 521 is the Kronecker 6. Abbreviate
Ifl'dfl-l T'd to g, where T' is the transpose of the matrix T.
Observe that 2,, as a linear combination of the functions hJ in

L3(P1), is in L3(Pi), l = l,...,ri. Also, since {z,|2 = l,...,ri}

is a set of orthonormal functions in L2(Pi)’ we have,

2
(s) Pi(Z.s)2 = HsH = 1
and,
(6) P.||z||2 = r .
1 i

We note that since it) é [o < (a,d) é (g;g(a)

O o + 2
i > O and T d # 0 Suppose zkj J

Then, conditionally on u, xa and all xw, w l Ii’ the sum

0(1)]. 2k.) 4" idk # 0

implies r k’# 0 and Npi > 1.

zm#c,chi(z(xm)’g) falls into an interval Of length |(Z(xa)-Z(u),g).,

Hence, a B-E approximation to this conditional probability of sz + th

-1 3
yields a bound, (Npi-l) /2{§'(0)I(Z(xa)-Z(u).s)l+ 2BP1I(Z.3)I 1.
after simplification by (5). Taking the bound on this conditional

probability to be 0 if lkJ + max = 0 and 1 if Npi = l and weakening the

P9 x P1 integral in this bound by the Schwarz ri-space and integral in-

equalitieS, the triangle inequality, and (6) used to obtain

1/2 1/2
PePiW‘xa) - z(u).a)| é PePiHZ‘x‘a) - z(u)" g fipillzlle} = 2 r1 9

>
we have if Npi = l ,

s , -1/2
(7) PepinkJ + ldk) — mln {l,(Npi - 1) Ci} ,

hi.
1/2 3
where c1 = §'(o) 2(ri) + aspillzll . If r1 = o, (7) holds with

C'=oand0.”=00

1
Observe that inequality (2.1h) implies that
111/2 p1 min {l,lhpi - l|"l/2 Ci}é pil/2(l + off/2 for all i.

Hence, since i:;: p = l, we have by the Schwarz m-space inequality

i

“1‘1 12 -
<8) 2 ’ l’eci} é (m +ncu2>l/2 .

2

. p1 min {l’lei'll
1=o
k3

-l N
~ 2051qu IL,

“A

' +
Noting that BN |P6Pea(£kJ £Jk), we see that

a
(7) and (8) imply

(9) Nl/zBN é (II) b(m + llq|2)1/2 ’
2
k3

where L = maxi’J’lei I .

Equation (9) implies (ii), which together with (i) and inequality

(1) completes the proof.

3. Sufficient Conditions for a Theorem of Higher Order.

 

In this section we shall examine certain sufficient conditions
which allow a generalized analogue of Theorem A in Chapter II. Two
types of sufficient conditions are imposed: a certain continuity

assumption relating to the class of probability measures {Po,...,P

m l}’

and a condition on the m x n component loss matrix (L(i,J)). The
continuity assumption is a "natural" extension of the sufficient
condition (II) of Theorem A in Chapter II. That an additional condition
is needed on the loss matrix will be ilhstrated by two examples.
Consider the following example, which illustrates that, regardless

of what continuity assumptions are imposed on a class {Po,...,Pm_l}

A2.
satisfying a mild regularity assumption (see (9) below), a uniform
convergence theorem of rate faster than 0(N'l/2) is unobtainable for

a certain loss matrix.

Example. Let n = 2 and h = (ho....,hm_l) e d? such that hJ e L3(Pi)

for i,J = O,...,mpl. Let I = (1+,IO,I_) be a prOper partition of
(O,...,m-1} according to Lio >, = or < 0. Define wu(v) = (Lloh(v),f(u)).
Note that wu e L3(Pi) for i = O,...,mpl. Assume there exists 1 e 10’

i' 6 I... L} I_ such that,

(9) Pi. [0127.0) > o] > 0.

Without loss of generality, we may assume i' e 1,. Existence of a
class {Po""’Pm-l} satisfying (9) can be assured by taking common
support S = {ulfi(u) > O} for all i, and noting that under this
assumption condition (9) is equivalent to Ll # LO.

1/2

Consider now 6 a £2m such that O < y _5- N p. ,§ 6 and

"A

pi

and define the set E= (E: H(x ) < 0}. Define s§(u) = Npi 012(wu)
xc
+ (Npi .-l) 0.. 2(wu ) and KN (u)= fi1(u) {wu(u) + (Npi.-l) Li? fi,(u)} .

= l - pi, for all N sufficiently large. Fix a such that 6“ = i'

Then, by a b-E approximation applied conditionally on Xa = u, we have

(10) P6[E|Xa = u]; Y N(u) ,

where YN(u) = T(KN(u)) - BSN 3(u) zifap6£ lwu_ quw VuIB

Note that on {uloiz(wu) > O}, N-ls 2(u)a~.voi2 (wu ) > O, and hence
on this set lim K N(u).2C(u), where C(u)-=-GI.g W,(u) fl( wu), Thus,
since lim YN =(lim YN )+ and §(-) is an increasing function, we have

(11) gm g(u) .3. new» on {of-(wu) > o} .

h3.
Therefore, Fatou's Lemma, (lO), and (ll) imply,

(12) lim Pom 11m Pi'PBU'IXQ = u]

llv

- - 2
Pi' 11m Pe [EIXG - u] — C,

where C = Pi' [012(wu) > 0] §(C(U)) > 0.

Finally, since Llois Optimal against both i and i', we see that
(13) y_m_ N1/2{n(e,t;;> - ¢(p(6))}

; $339- N-l/2 23:1 Peng trilmo)

= 2.1.9. NW 1. L119Pett']

‘; y Li? C > 0.

Inequality (l3) contradicts the possibility of a uniform

-1/2) in the general

convergence theorem of order greater than 0(N
finite compound decision problem with arbitrary loss matrix.

Consider now the following condition (C) on the loss matrix
(L(i,J)). Let ij = {iIng‘j = O}. The condition is:

(C) For all J,k (J#k) and i e I there exists an

kJ’

' >
i = 2(i,J,k) such that L12 > 0 and Lieg = O on ij'

Note that condition (C) is violated in the example above for
all i e lo. With this added restriction (C) we will obtain a uniform
convergence theorem for the regret risk function of 0(N-1). The
sufficiency of (C),together with the continuity assumption (II')
(or II") below,will be seen in the proof of Theorem 6. A certain
degree of necessity for this condition is shown by the above example
and is demonstrated more clearly by the example in section 3.5.

We mention here three important cases in which (C) is satisfied.

All three cases are concerned with the discrimination problem in which

hh.

msn and L(i,J)=0 or >0 according as i=3 or i#J. The three cases are:
(i) Let m = 2 or 3. This case reduces to the problem of

Chapter II for m = 2.

(ii) Define L(i,J) = a(l-Gij), where 6 is the Kronecker 6.

1J
Condition (C) is satisfied by choosing £(i,J,k) = 1.

(iii) Let w(t) be a strictly increasing function on [O,w) with

RJ
1

i > J and i < k or i < J and i > k, condition (C) is satisfied by

w(o) = 0. Define L(i,J) = w(Ii-JI). Since L = o for 3 ¢ k implies
choosing £(i,3,k) = i.

We now examine the sufficient condition to be imposed on the
class {Po,...,Pm_l}. Let u be some dominating measure for the Pi's

and define f = (f0....,fm_ ), where fi is the density of P1 with

I
respect to u. Let Pif-l denote the probability measure induced
under the measurable transformation u + f(u). Note that P11"-1 is a

probability measure on (Rm,é5m), where 43m is the o-field of Borel

sets on Euclidean m-space. Let Am denote m-dimensional Lebesque

measure. Define BJ in 43m. J O,...,m-l as

< < < < ,

(1h) 33 = BJ(v,a,b) = {o = (v,f) = a, Oéfjéb, oéfi=K, 1#J}.
where [VI = l, a g 0, b g 0. Consider now the following condition on
{PO’...’Pm-l}:

(II') There exists a measure u dominating the Pi's and finite
constants K, K' such that Pif-l[bj] ; K'AmlBJ] for all

i,J,v,a, and b with vJ(b-K) = 0 and Bd of the form (it).

This condition is by no means an obvious generalization of

condition (II) of Theorem 3. however, let P. = zm;:o Pi and let

Zi(u) be the density of P1 with respect to P.. Define E'as the

1.5.
1

measurable transformation u + (Zl(u)"°"Zm-l(u)) and Pig - the
induced measure on (Rm-l, @m'l) under 2'. Let Am-l denote m-l

dimensional Lebesque measure. Then we can state the following "natural"

extension of condition (II) as:

(II") For i = O,...,m-l, Pia ’1 is absolutely continuous with

reSpect to Am I and for some K" < a,

d Pi? '1 <
_ H
(15) dA - K o

m-l

 

Condition (11') is seen to be equivalent to condition (II) of
Chapter II by observing for m = 2, Pi[Z(U) < z] = Pi[Z(U) > C(z)],
where C(z) = {b + (a-b)z}-lb(l-z) and Z(u) is defined by (2.2).

It can now be seen that condition (11') generalizes condition (II)
in the sense that condition (II"), which is equivalent to (II) for
m = 2, implies (II') when u = P. in (II'). For the proof of this
statement, see Appendix 1.

We now give an example which fulfills condition (11').

Example. Let U = (Uo"'°’Um-l) be the generic random variable for
the component problem. Define, for i = O,...,m-l, the probability

measures Pi having densities with respect to Am given by fi(u) = 2 ui

if u c [O,l]m. If we let Pif-1(fo,...,fm_l) be the distribution

function corresponding to the induced probability Pif-l, then

-1 l
Pif (f0....,f

m-l) = 2-(m+l) (H?;: f3) f1 on f e [O,2]m. Hence, Pif-

is absolutely continuous with respect to Am and has Am-density

2"m fi on [0,2], which is bounded by 2- m+l on [0,21m. Therefore,
with K' = 2' m+l’ Pif-l[B] ; K' Am[B] for all Borel sets 5 on Rm;

A6.

and, hence, in particular for the sets B of condition (11') with

J
K = 2.

This example may be generalized. Let P1 be a probability measure

on m-space with Am-density gi(u). Choose, if possible, a measure n

such that Pi << u << Am with h(u) as the Am-density of u and such that

u + f(u) = g(u)/h(u) is a l-l map from {ulf(u) ¢ 0} into [O,K]m having

Jacobian J(u(f)/f) with h(u(f)) J(u(f)/f) bounded by K Then, on

00
the range of f, we have
I

(16) ffif:- (f f ) = f (u(f))h(u(f))J(u(f)/f)
d Am o"'°’ m-l i
EKK (a:
_ 0 ,
.. <
But (16) implies that Pif 1[B] = K K0 Am[B] for all Borel sets B on
Rm; and hence, in particular for the sets B of condition (11').

J
In the example given above, u = Am, h(u) = l, and gi(u) = fi(u)

= 2 u for u e [O,l]m with K = 2 and K = 2-m. Another example in

i 0
. . . . _ m nm-l _
which u plays a more dom1nant role 18 with h(u) - 2 J=o “3’ gi(u) _
m-l -l _ -l m
2 3 u1 ng=o uJ, and fi(u) - 2 3 ui for u a [0,1] , and with
K = hm 3"m and K = 2"1 3.

0

h. Uniform Convergence Theorem of 0(N-l).
Before stating and proving Theorem 6, we shall prove the

following useful lemma.

Lemma 6.

For sets BJ = BJ(V,a,b) 0f the form (1h), Am[BJ] g a b Km-2

if IvJI < l.

1.7.
Proof. Let 1 # 3 be such that Ivll = l. The lemma follows from

the transformation y2 = (v,f) and yk = fk, k # 1, which has unit

Jacobian.

Theorem 6.
If (G) and (11') hold and h s 6’ such that Ihi(u)| é M a.e. u

for i = O,...,m-l, then R(6,tfi) - ¢(p(6)) = 0(N-l) uniformly in 6 c Q”-

Proof. We show in inequality (1) that: (1) AN = 0(N-l) uniformly
in 6 e 9“ and (ii) BN = 0(N-l) uniformly in 6 2 {20° .

— U
(i) by noting ((pi - hi)L tfi(u) - t;(u)) is the difference

1’

of two simple functions, we see that the first term on the right-hand

side of (I) can be written as

(17) AN = Pena-F. p(tg) - p(tpn = 23¢]. DN(k.J).
m-l ,
where DN(k,j) = P6 2. (pi-3;)LEJ Pith;k(u) té’J(U). Without loss

1=o
of generality, we may assume p1 > 0 for all i = O,...,m-l in AN’

C
= — - ' =
since, if pi O, the term pi(pi(th) pi(tp)) 0 could be
eliminated prior to use of Corollary 1 in (1).

Fix i, J, k, and observe that for 2 = O,...,m-l,

(18) t; (u) t' (u)
h,k p.J
_. ' 2
..‘_[o.5.(ka3 ,f(u) )émzLKHp-hll][ZiEIkJPiLizfi(ugiiflkJPiLijfi(U) 1.

Consider the following two cases.

3-1

Case 1. Let maxi,£I p. m . Bound the second factor on the

1
kJ
right-hand side of (18) by unity and note that condition (11') and
. .. . _ 1.3-1 k.)
Lemma 6 applied to the rema1n1ng factor with v - IpL | pL ,

a = IkaJI"l ml/2 LK ”p-h]| and b = K yields

AB.

I < 111-2
1 P.t- U t' U = a h K K'
(9) 1 NJ ) M( >
g K ”P’HH 9
m
_ 3/2 -l ,m , . = . kJ kJ
where Km - m L LO h K with LO mlni,J,k {ILi I ILi # 0}.
Case 2. Let 0 < maxiw¢1k<m-l. Then there exists an
> m-1 J JR, >
w c ij such that pm = . Therefore, by condition (C), Li' - O
on IkJ and LJ2 > O for some 2. For such an 2, we have
32 ; JR ; 23 g kg -1 .
zielkjpiLi r. (u) prw fw(u) o and [Li I |Li | L LO for lélkj

Hence, the second factor on the right-hand side of inequality (18) is
bounded by [0 = pm LJlf w(u)= (m.1)L L0 lKIkaJI]. with this bound
in (18), condition (iI')land Lemma 6 applied to Bw(v,a,b) with

IkaJI'l kaJ. a = .21. Hp-filllkaJl'l. and

V

b K IkaJI , we have

II
A
’U

32 -1 -1
w Lw ) (m-l) L LO

IIA

' , .m-2 ,
(20) P1 tfi.k(U) tp’J(U) ab h K

IIA

KI; "P‘ill a

where K; = m3/2(m-l)(L L-l)2 Km K' is obtained by noting that

O

3 -1

32
pm Lu) m LO.

> >
Observing that K; = Km for m = 2, substitute the bound in (20)

into the term DN(k,J) for both case 1 and case 2 to obtain with the

< ..
aid of the Schwarz m-space inequality D N(k’J) = 1111/2 L K; PGHh-puz.

1/2

Hence, Lemma h and equality (1?) imply AN: <{h(n- l)m LKI;1C2}N-l

from whence (1) follows.

(ii) Fix 1,3,1. and define a = {0 i (BLk3,r(u)) é eln'l},
F2 = {o g (BL£3,r(u))} , 2 = O,...,m-l, and a1 = 2mMLK. Note that
by the definition of t'(a ) k(u) and tHJ (u) we have ti<a> k(u) té;j(u)
3

= [E] [F ] for a = l,...,N.k hence,

h9.
-l

(u) t'

(21) N p’J

kJ I
2061 Le Pape V— a

(u)
i a a h( ),k

5 k3 ,
- lpiLi I P9Pi [L] [F2].
We now consider bounding the right-hand side of (21) in two cases.

1 - -1
Case 1. LEt maxitI P m . Define the set A={“h-pH é(2m) }

kJ
Note that on A, IthJI ; L 0(2m)-1, and hence by condition (11') and

Lemma 6 we have, p 6'13 [sun] = p Gimp [a]: Wm L'1 16'” K'a ) u'l
Also, we have by Tchebichev's inequality and Lemma h,

Pe(l - [A]) é h m2 P6 “filpflz é h(mc)2 N'l. hence, with dz =
2m LBle-J'K'al + h(mC)2, it follows that

-l
(22) lp. LkJI P 6P. M([E][F ])= p. La2 N .
Case 2. Let max p < m-l. Then there exists an m e I
itlkj 1 k3
such that pm gm - . By condition (C), there exists an 1 = 2(w,J,k)
such that L32 > 0 and L4? 2 0 on I .
w 1 k3

"A

 

. Then, since (11')

and Lemma 6 imply, for IhDLkJI > 0, Pi[E] g 03 l'I-i'Lk‘jI"l N.1 where

Observe that lpiL§J| |pi-E;I L + |E'Lk3

-l
03 = Km K'al, we have

(23) IpiLEJI Pi([E][F£]) é Llpi.i;| Pi([E][F£]) + a3 N-l,

With 2: 2(m,J, k) and observing that ziél hi L1 Raf (u )=mLL0 lKIthJI
k

and that {i I (h. -pi)Liin(u)5 l/2LK Hp-hllon F2, we obtain the set
kJ

. . 2 -l-k -
1neluszon. F, (I {oéprg fw(u)§(mL0 th J|+n1/2||p-h H)LK} . Let

-'k -l 2 -
G = {IhL JI < N / }. Then, since Iprill g m 1 L0 we have on

G, (11') and Lemma 6 implying by the above set inclusion PilFl] ;

“-1 2+ ml 2 - -
(mL? / / IIp-h H) mLLOleK', while on the complement of G,

SO.

-l/2

( -
P1[E] = Km 1 K'a N . Hence, we have in the term Pi([E][F£]) for

l
2 = £(N,J,k),

(2h) Piutum) -‘- a, m‘“? + a5 IIp-Fll.

where a1‘ = Km.l K' {(m L61)2 KL + a1} and as = my2 L L61 Km K'.

To complete the proof for the term BN, substitute (2h) into the
first term on the rightsrhand side of (23). sum the P6 integral of this

bound plus the bound in (22) over all i,J,k,(J#k), and use Schwarz'
inequality to bound z Ipi-hil = m IIp-hfl ' The resulting

i-o
inequality from the definition of B

N and inequality (21) is

(25) 8N : n(n-l) {(Ld2 + ma3) N-l

m1/2 1/

- 2 - - 2
+ L(ohN Peuh-p||+ as PJIh-p” )} .

From (25) we see that B = 0(N-l) uniformly in 6 e a”, since by

1/2 P6 ItT-pllé N'lc and

N
Schwarz' inequality and Lemma h, N-

- 2 5 2 -1 .. . . .
Pe Hh~PH - C N . Therefore, (11) 18 proved, which together w1th

(i) and inequality (1) completes the proof.

5. Counter-example to Theorem 6 when (C) is Violated.

The example given in this section shows that even in the
discrimination case (L(i,J) > or = 0 as i # J or i = J, and m = n) and
with condition (11') satisfied, a violation of condition (C) prohibits

-1/2). This

a uniform convergence theorem of order greater than 0(N
example together with the first example in section 3.3 exhibits that
condition (C), although maybe not a necessary condition for Theorem 6,

is at least not an unwarranted assumption on the loss matrix (L(i,J)).

51.
Example. Let m = n = h and assume {Po,...,P3} satisfy condition (11').
<
Let h e d? with Ihi(u)| = M a.e. u for i = O,...,3. Suppose the

component loss matrix is given by:

F4 F‘ F‘ C)
F4 -4 C) +4
F‘ c> n3 Pd
c> F‘ F‘ F“

Note that in this example all conditions of Theorem 6 are met
except condition (C) which is violated when (k,J) = (0,3) or (3,0).
As will be seen, the conclusion of Theorem 6 is not true for this
example.

To facilitate construction of the example, choose distributions
with densities fi(u) having common support set S = {u'fi(u) > O}
for i = 0.1.2.3, and such that é-f2(u) é fl(u) § 2 f2(u) on 8.
Furthermore, assume that K ; fl(u) é K on S for some constants
K, K, O < K < K < mo

To see that this class of examples is non-empty, let fi(u) =
3'12ui on [1.2]h with u = Ah, x=3'12,K=3'lh. Then, s = [1,2]“ and

<

<
u2 = 2ul = hu2 on S. That condition (11') is satisfied follows by

analogy with the example satisfying (II') given in section 3.3 with m=h.

Now choose 6' a 9” such that for N sufficiently large,

0 < y g Nllz p (6') § 5 < a, p (e') = o, and 2p (9') + c é p (e')
o 3 2 l
3p2(9 ) e , O < e < 2 . By the cho1ce of 6 , tp(e,)’0(u) l a.e.u.

N

Hence, R(6',t%) - ¢(p(9')) = N-l za=l

3 k0
P6.Zk=l Lea tfixk(x0). Note

that condition (C) is satisfied for k = 1,2 and hence by the proof

of Theorem 6 and the fact that pé(9') O, we see

52.

(26) R(6',t;‘;) - ¢(p(6')) = m'1 {061 Pe'th 3(x ) + 0(N 1).
0

Fix a 6 I0 and define E = [hof o“(X ) - h3 f 3(Xa ) < 0]. Conditionally
on Xa = u, apply a B-E approximation to the sum z£#a(ho(xz)fo(u) -
h3(x£)f3(u)) and let 0(u) = mini=o.1.2 oi(h0(V)f0(u)-—-h3(V)f3(u)) > 0

on S to obtain,

(27) _l_.___im ms |x = u] é §(-6fo(u) a'1(u)) on 8.

Now, observe the following pointwise inequalities:

IIA

A

(28) o é [E1 - t— (x ) 1 - [<53L31r(xa>) < o] [H.L32f(xa) o]

h,3 a

llv
NV

0].

"A

[(h,L3lf(xa)) 0] + [(K,L32f(xa))

Then, with (3}L3kr(xa)) é HELp(e')” 12 K + (p(6'),L3kf(Xa)) for hs=1,2,
while our choice of the fi's and 6' implies (p(6'),Lk3f(xa))3efléeK ,

we see that (28) tOgether with Tchebichev's inequality and Lemma h

imply
é -- _ é ’_ I ; é '1
(29) o Pe.{[E] th.3(xa)} 2 Pe.[llh p(e )|| 12 K e x] no N ,
_ 2 -2
where do = 288 (KC) (ex) .
Thus, we have Pet-3 (Xa ) = P 6[E] + 0(N 1) from whence it follows
by (26) and (27) that
2 i
(29) lim nl/ (3(6'.t3) - ¢(p(6'))
>
= y lim POPB' [EIXa = u]
>
= y al > 0 ,
_ -1
where a1 - Po §(-6fo(U) a (U)) > 0.
Equation (29) demonstrates that a uniform convergence theorem

-l/2

of order better than 0(N ) is impossible in this discrimination

example where (C) is violated.

ChAPTER IV

THE TWO-DECISION COMPOUND TESTING PROBLEM
IN THE PRESENCE OF A NUISANCE PARAMETER

1. Introduction.

We now give a formulation of the testing problem considered in
Chapter II for testing between the parameter values a = O and l in
the presence of an unknown nuisance parameter r = (11,...,ts), s g 1.

Let T be a set in R8 with non-empty interior. Let (7% = {P6 T TET} be
9

 

a family of distributions for 9 = 0,1. We shall assume throughout
this chapter the existence of a o-finite measure v dominating the

families 0D

6' e = 0,1.

Consider now the compound problem of making N decisions,
'6 = O or 1', based on N independent observations X , a = l,...,N,
a a

where Xa is distributed as P for fixed I e T. Let the loss

6a,1

matrix for the component problem be given by:

0 b
(l) (:a 0:)

where b > 0 represents loss due to deciding Pl T when PO 1 is the
t 9

case and a > 0 the loss for deciding P when Pl 1 is true.
3

0,1
If T is known, the problem reduces to that of Chapter II.
However, we here consider the case where the vector parameter I is
unknown but assumed to be the same for all N problems. We shall give
a procedure which first estimates 1 and 6 based on X1,...,XN and then

adopts a compound procedure similar to that given by (2.9) in

Chapter II with I replaced by its estimate.

53-

Sh.

At this point it seems appropriate to remark on the above

formulation of the problem. Suppose we temporarily consider the
problem where the set T is a finite set of, say, k elements,
to’°"’tk-l' Then the problem reduces to that of Chapter III by
letting m = 2k with the class 6¢>= {Po’°"’Pm-l} being given by
P1 = P0,T£ and Pk+£ = Pl,1£ for 2 = O,...,k-l, and by choosing a
2k x 2 loss matrix with L(i,0) = 0 or a according as i < k or g k
and L(i,l) = 0 or b according as i g k or < k, where decision J,
for J = 0,1, corresponds to saying '6 = J'. In fact, in this case
r can vary over T from component problem to component problem. Hence,
we arrive at no new problem unless T is at least an infinite set.
The selection of T as a set in R8 with non-empty interior will be
seen in the proofs to follow. The assumption that T is the same
for all N problems permits the obtaining of estimates of T which
have good asymptotic properties as N + on.

With the formulation of T as a set in RS with non-empty interior
and 1 the same for all N decision problems, the earlier results do
not yield a solution. It is this problem to which we now devote our
attention. We will give asymptotic solution3(in the sense of regret
risk convergence) in Theorems 7-11.

Before stating the theorems specifically, a few preliminaries
are necessary. Let v be the assumed o-finite dominating measure for
,P

the families a, 9 = O or 1. Fix 1’ e T, and denote P nd

0,1 1,1 a

P by P , P1’ and P respectively. Define

6,1 g xa=l P60,t o
dPi
(2) gi(u) = a;-(u) for 1 = 0,1.

6

55-
Let u = aPl + bP0 as in Chapter II and note we may proceed exactly
as in equations (2.1) - (2.8). We shall suppress T in all these

equations except (2.2), where
(3) Z(u.r) = bf0(u) = {agl(u) + bgOWH-l bg0(u).

Consider now a scalar function h and a vector function
k = (k1,...,ks) such that h(U) is an unbiased estimate of 6 = O or 1

and k(U) is an unbiased estimate of T; that is,

for i

II
p.

(h) Pi h(U) 0,1,

Pi k(U) for i 0,1.

ll
.4

by (h), we then form unbiased estimates of 3 and 1 based on the

observations Xl,...,XN for all N, e e a” by defining the averages

(5) Rx) = N‘1 {i=1 h(xa).
- _ -1 N
k(X) - N Za=l k(Xa) .

Observe that by (h), Péh(X) = 3 and PBE(X) = I. For kernel functions

h, k = (k1,...,ks) such that h, k e L2(Pi) for i = 0,1; J=l,...,s,

J

2 _ . 2 _ 2
define 01(h) - Pi(h(U)-1f2and °i(kj) - Pi(kj(U) - TJ) . For p s [0,1],
2 _ 2 2 ._ .
define °p(kj) — p 01(kj) + (l-p) 00(kj)’ J-l,...,s. Then by Lemma h

and its analogue for k, we have

(6) p 17.6)? -f- "52(nm'1, pent-Tu? ‘

ll
0
PM
2

O

6(

{Oi(h)) and C2 = S

-2 _
where 0 (h) - max 1 maxi=0’l J=l

2
0 o
i=0,l 1(k3)
From the above formulation, it now becomes natural to consider
the compound procedure formed by substituting 3(x) and Z(x) for a and
T respectively in the non-randomized simple procedure given by (2.5)

with 56 = 0. however, since z(u,r) is only defined if T is in T, we

56.

must "truncate" h(X) to T. Hence, let k* denote a specified truncation
of I to T such that 2* = '1? if IeT and if I t T, then—k" is a point in T
within a distance of N-1 of a minimizer of HET- Tll on the closure of
the set T. A constructive method of truncating when T is a convex set
is given in Appendix 2.

We are now able to present a well-defined non-simple, non-

randomized procedure t: _ = (t1 _ (x ),...,t; -*(x,)) with coordinate
functions

0 - > --
(7) t5,k*(xa) = 1 or O as Z(xa,k*) < or = h, a = l,...,N.

The risk of this procedure under Pe will be denoted by R(6,t%.E*).
Under certain regularity assumptions this procedure will be shown to
have good, uniform in 9 a 9m, asymptotic properties in the sense of
regret risk convergence.

Certain assumptions will be needed in the proofs of Theorems 7-11.

Let I e T be fixed.

Assumption (Al): There exist functions h and k = (k1,...,ks)
such that (h) holds and h, kj 2 L3 (Pi) for i = 0,1; 3 = l,...,s.
Assumption (A2): The covariance matrix of (h,kl,...,ks) under

Pi’ denoted by Vi, is of rank 5 + 1, i = 0,1.

When they exist, define

 

32
(8) Z!(u.t) = --
J 31J T
u 32
Jk atjark

 

0
If s = 1, denote 21 and 2:1 by z and 2 respectively. Also, let

86 = {1' e hsl flt’ - Ill < 6} .

57.
Assumption (Bl): For some 6 = 6(1) > O and for almost all
u(v), Z(u,t) admits continuous first-order partial derivatives (rela-
tive to T)for non-isolated points 1': S {W 'T. Furthermore, there

1
Ml(u) a.e.*v on 86 (W T for J = l,...,s.

exists a function M e Ll(Pi) for i = 0,1 such that |Z$(u,r'fl é

Assumption (b2): For some 6 = 6(1) > 0 and for almost all
u(v), Z(u,1) admits continuous second-order partial derivatives (rela-
tive to T) for non-isolated points T'E:86 (W T. Furthermore,

Pi|23(u,t)| < w and there exists a function M e Ll(Pi) for i = 0,1

2
such that |Z3k(u,1')| é M2(u) a.e.\) on 86 {1 T for J,k = l,...,s.

2. A Convergence Theorem in the Presence of a Nuisance Parameter.

 

Theorem 7.

 

Let T be any interior point of T for which assumptions (Al)’
(A2), and (B2) hold. Then, R(6’th',i'*) - ¢('é') = 0(N'(l/2)+e) for

s > 0.

Proof. Since 118 an interior point of T, we assume, without loss of
generality, that the 6 of assumption (B2) is such that S6 C: T.

'
Identify tc = t in (1.15) of Lemma 5 to obtain,

(9) R(e.t'.-)
h k“

= {a3 P6P1(l-t-H’E*(U)) + b(l-E) PePotE. 13(0)}

oneIl P6P1(t;’:*(u) - tfiahfiaflwn

(U)) .

+ a N.1 Z

-1 v I
+bNZ PP(t *(U)-t
oeIO 6 O g(u)’i'(0) h,k*
where I1 = (alea = i}, i = 0,1. Let the three terms on the right-hand

side of (9) be denoted by AN, BN, and CN reSpectively.

58.

We establish the theorem by showing that: (i) AN - ¢(§) = 0(N-l/2)

-(1/2)+e)

uniformly in 6 e a”, and (ii) 5 and C are of 0(N , e > O,

N N
uniformly in 6 a Q“.

(1) Define A1; = Pe{a6 Pl(l-t%(U)) + b(i-E) Potf'l-(UH , where

t%(u) = 1 or O as Z(u,T) < or

>-

h. Then express AN - 6(5) as

(10) A1-6('6')= A,.'-¢(6)+AN- AN .

Observe that with u replacing u' in equality (2.12) and part (i)

of the proof of Theorem 2, we see by (6) that

(11) A.. - 6(6) a+b) 6(h).

Next consider the term AN - A& in (10). Again by a cancellation

argument of the type used to develOp (2.12), we may write
(12) AN" AN: P6 6 {( (6- z(u. 1)) ([E] - [F]).

where E = {Z(u,r) < E i Z(u,k*)} and F = {z(ujzar) < h 2 Z(u,t)} .

Under the Pe x u integral subtract and add Z(u,k*) ([E] - [F]) and

bound (5.2(u,i*)) ([E]-[F]) by |h'-5| and (Z(u,1-(*) - Z(u,1)) ([E] - [F])

by IZ(u,k*) - Z(u,1)l to obtain
(13) AN .. AI; é (a+b) Peli-‘e'l + Peqz(u,1?*)- Z(U,t)l

In the second term on the right-hand side of (13) Partition the

space under the P6 integral into G6 = {HELTH < 6} and its complement.

By Assumption (B2) and our choice of 6, expand Z(u;k*) = Z(u;k)
"

on G6 about Z(u,1) in a second-order Taylor expansion and bound ZJk

by M2 to obtain

59.

(1h) [z(u,§?) - Z(u,T)I

"A

8 -' ' A. _- _-
|2J=l(kj-rj) ZJ(u.I)I + 2 22,3 lkk 1k] ij TJI M2(u)

“A

S “ ' $_ -- 2
ngl I J-TJI IZJ(U’T)| + 2 “k T“ M2(u).

Use the Schwarz s—space inequality in the P6 x u integral of the first

term on the right-hand side of (1%) and inequality (6) in the P x u

6
integral of the both terms to obtain

(15) Pan {|z(U.E*) - Z(U,1)I [66]}
§ nil/2 01 al + g- m"1 Ci u (1.12(u)) ,
1

s , 2 2'
where a1 = {ZJ=1 (uI&3(U,t)l) } .
Since IZ(u,k*) - Z(u,t)| g 1, we have by Tchebichev's inequality
and (6),

(16) P9 u |z<u.£*> - z(u.r)| (1 - [06])

"A

(a+b) 6'2 p6||£-1n2

(a+b) 5'2 of u‘1 .

"A

hence, (15) and (16) together with the Schwarz inequality and (6)

-l/2

used to obtain P6 Ih-51 g N 3(h) imply by inequality (13) that

(17) A - A i

N 1; 11-1/2 {(a+b) 6(h) + a1 cl) + 0(N-l)

uniformly in 6 c Q“.

Substitution of (11) and (17) into (10) completes the proof of (i).

60.
(ii) We shall now bound the term BN in (9). Without loss of

generality we assume N6. Q 1. Let 0 < e < fi-be given. Pix (:511 and

define the sets E = {HELrflgN-(1/2)(l-5)) and Ea={flk‘a)-IIEN-(llz)(1-6)}.

We shall need the following pointwise inequality:

(18) t3. .(u) - tH,I(°‘)'(u)

; [2min <61 [z(u.f‘°)*> ; 31"“)](1-[B])(l-[Ea])+[E]+[Ea].

We now bound the P6 x Pl integral of the right-hand side of (18).
Observe that by a change of variable and an elementary set

inclusion, we have

(19) P9P1([E] + [201) = 2 Pe[E]

S-1/2 N-(l/2)(l-e)].

llv

S
2 Z Pe[|£5-T

.11 3

By a B-E normal approximation to each of the summands on the right of
(19), we have for J = l,...,s,

(20) P6[)£5'le 2 5‘1/2 N-(l/2)(l-c)]

"A

-1
2 {1 - T(s’l/2 NE/2 05 (kj)}

2 6 N-l/2

+

bJ(6) .
—_;3 - 3 — 3
where bJ(6) - oe (kj){€)Pl IKJ(U)-TJ| + (1-0) Po IkJ(U)-TJI }.

We bound from above the first term in (20) by noting that

1 -§(s"l/2 NE/e 061(kj)) g 1 - §(s-'l/2 NE/2 dgl) since for all 0 e Q0°
. _ 2 g 2 . .
dJ — maxi=0’l {°i(kj)} - 06(kj)' Then, by the exponential tail

inequality 1 -§(x) é §'(0) x"l exp {- %-x2}, for x > 0, (see Feller

[3]. p. 166), we have

61.

(21) 1 - §(s’1/2 NE/Q 039(k3))

é §c(0) 51/2 N'E/Q dJ exp {-(1/2) 5'1 d32 NE} .

Define bJ = maxp£[0.l]

of (20) is then 0(2 6bJ N .j

for all 6 e O“. This bound asymptotically dominates the exponential

bJ(p). The second term on the right-hand side

-1/2) uniformly in 6 c O”, since bj(§) g b

bound in (21) and when it is substituted with (21) into (20) for

J = l,...,s we see that by inequality (19).

(22) PePl([E] + [Ea]) = 0(bON-1/2) , uniformly in 6 e Om, where
3
b0 6 B {J‘l b3.
To bound the P x P integral of the first term on the right-hand

8 1
side of (18), choose N

N3(l/2)(l-€) <6. Then, by assumptions (b2), we may on the set

0 = No(r) sufficiently large such that

he [8 E: (c denoting complement) expand Z(u,k*) = Z(u,k) and

“(a)*

Z(u,k ) = Z(u,k(a)) about I in second-order Taylor expansions and

bound them from below and above as follows:

3
(23) um?) i Z(u,‘r) + {3:16.349 23(u,1’) - gr” 142(u)
‘(0) S S “(0) t l -l+€
and, Z(u,k ) - Z(u,t) + 23:1(k3 -TJ) ZJ(u,T) + E-N M2(u).

Define, w(xl) = (h(x£) - 02, kl(x£) - 11,...,ks(x£) - 11), for

2 = l,.u,N, and y(u) =(la-Zi(u,1),...,-Z;(u.T)).Inequalities (23)
applied to the first term on the right of (18) together with some
algebraic manipulation now imply that this term is bounded from above

by the function [Fa]’ where

62.

(2h) [Fa] = [w(z(u,r)-6) - §NEM2(u) - (y(u).W(xa) + 2,6Iow(x,))

< Ziell,£#a(y(u)’w(xl)) ; N(Z(u,1) - 5) + éNEM2(u)

- (y(u). W(u) + 2251 W(x£))].
O

i e I

Condition the P x P 1’ O

6 l

and apply a B-E approximation, obtaining an upper bound on the

integral of [Fa] on u, xa, and x

conditional probability given by

-l/2

(25) min {l,(NE-l) (§'(0){N€al(u) + a2(u.xa>} + 25a3(u))} .

where al(u)-41;H((3(u).W))M (u). a 20t(u.x )=0; H«Y(u).W)H(y(u).V(u)-W(x ))l

and a3(u) = 013((y(u),w)) Pl((Y(u),w)|3, with oi(t) denoting the

variance of t(V) under P Assume for the moment that oi, i- 1,2,3 are

l.
integral with respect to P6 x Pl' Then,
a
(26) P6P1[Fa] g min {1,(N6L1)'1/2 (N o* + o*)} ,

where a: = §'(0)Pl 61(U) and 6* = Q' (0)? (U. V) + 28P163(U).

1 P1°‘2
‘Recalling the definition of BN and the fact that the function

[Fa] bounds the first term on the right-hand side of (18), we see

that equations (22) and (26) substituted into the P6 x Pl integral

of inequality (18) and summed over all a s I imply

l

(27) BN é a N‘l/zi 1/26 min {1, (NB-1) 1/2 (Ne a1 *+o0 *)} + O(b0)}
Inequality (2.1h) when substituted into (27) with c = Neof'+ e; and
p = 6 yields

(28) BN = 0(N-(1/2)+€) uniformly in e e an.

63.
It must be recalled that equation (28) was derived under the

assumption that a for i = 1,2,3 were integrable with respect to

1

Pl x Pea, a all. Observe that

(29) o12((y(u).w)) = y(u) vl y'(u)

I y(u)I‘D P' y(u),

where F is an orthogonal matrix, D a diagonal matrix with diagonal
a
elements di’ i = 1,...,s+1. Let v = y(u)? and 8i = minidi.

Then,

2 * 2 *
Z V. Al = “y(u)” A10

llv

(30) va'

Therefore, weakening by the Schwarz inequality for 8+1 Space in the
numerators of 02(u,xa) and a3(u) and bounding the denominators from
below by (29) and (30), we have

(31) a2(u,xa) .5.- ”N(u) _ w(xa)“ (A:)-l/2

IIA

a3(u) Pl “w"3(1:)’3/2

Also, note that (29) and (30) imply

(32) 61‘“) i M2(u> (A:)‘l/2

since "y(u)l2 = l+£§=l{23(u,r)}2 E l. Integrability of a

now follows from (31) and (32) by observing that M

i for i=l,2,3

2: L1(P1) by assump-

tion (B2),HwHE:L3(P1) by assumptions (Al) and the cr-inequality (LOEve

[9], p.155), while assumption (A2) guarantees A*:>O. This completes

l
-(l/2)+c

the proof that BN=O(N ) uniformly in 6e:9m. A similar argument

-(1/2)+e

shows that CN=O(N ) uniformly in 62:9“, and (ii) is proved.

6h.

The proof is now established by (i), (ii), and equality (9).

*1:

Please note that the order here obtained has the factor N ,

O < e < %5 We were unable, in general, to remove this factor and
obtain convergence rates as good as those of Theorems 2 and 5.
however, in two later results (Theorems 10 and 11 below) two
interesting and rather revealing cases where this factor can be

eliminated are given.

3. Examples for Theorem 1,

Three examples satisfying Theorem 7 are given.

Exalee l o
S

J=l‘i ‘

> 0}, where Y is a fixed constant such that

Let T be the subset of RS given by T ={(Tl,o-o,ts)lz

J

1
5&1 -(s+1)y), I
0 < y < (5+1)-l. Note that T is a non-empty Open convex subset of

RS. Fix I e T and let the generic random variable U = (Ul,...,U

2s+2)

have the multinomial distribution for i = O, 1, Pi {U = u} =

2S+2 8+1 u u
-l . J . s+1+J
n! (nj=l uJ!) “J=l{(TJ + lY ) (13 + (1-1)y) } , where
2s+2 8+1 1
u = n and Z I. = -(1 - (s+1)Y). We show that assumptions
J=l J i=1 J 2

(Al), (A2) and (52) of Theorem 7 are satisfied.

Define the functions,

s+1
(33) h(u) = (y(s+1)}'l (n‘l {3:1 ”3 - %) 1%
kJ(u) = (2n)'1 (uJ + us+l+3) - g-y for J = l,...,s.

65.

Then, since PiU = n(I n(I + (1-i)y), for

J J s+l+J = J
i = 0,1; J = l,...,s, it follows that Pih(U) = i and PikJ(U) = I

+ iv) and PiU
J.
Assumption (Al) now follows from boundedness of [h(u)] and lkj(u)|
for J = l,...,s by %({Y(s+l)}-l + l) and %(l—y) respectively.

Assumption (A2) is satisfied since (h, k1,...,ks} forms a linearly

independent set of functions in L1(Pi) for i = 0,1.

To verify conditions (52), we first define

s+1 u -u
_ -1 = -l J s+1+J

(36) 6(u.1) Pl(u) {P0(u)} “3:1 (1 +YTJ ) .

H
Let W3 and ka be the first- and second-order partials of w with
respect to IJ and TJ,Tk respectively. The following relationships
then hold:

' =

I! '
where C (u I) = {I (I +y)}-l (u -u ) - {I (I +10}.l (u -u )

J ’ s+l s+l s+1 2s+2 J J J s+1+J

!
and (Jk - BLJ/Btk.

Therefore, by expressing Z(u,I) = (a())+b)-l b, differentiating
as indicated below and substituting equations (35) in the resulting

derivatives, we have for J,k = l,...,s,

(36) 23(u.r> = -ab y w cj(aw+b)'2.

n = -3 - _ 0
ij(u.t) ab Y w (aw+b) {Y cjck(aw b) (66+b) Cjk} .
hence, observing that 2 ab w(aw+b)42§ 1, we obtain from (36),

(37) |Z3(u.r)|§%vlcjl .

+

'II 1 '
I43k(u,1)l é E'Y {vlcjckl chkl} .

66.

JR
+ Y)}-2 (2I

From the definitions of c

) {I

and C it is readily seen that

J

s+l(Ts+l

U
CJk ' (“s+1 ' u2s+2 s+1 + Y) + 6Jk(“j'us+1+,j)

+ y), where 6Jk is the Kronecker 6. Hence, since

1-sy, for J = 1,...,s+1, we have for

J

<
= n and (2I

-2
{IJ(IJ + 7)} (2I

"A

I“ + Y)

J'“s+1+il
J,k = l,...,s,

J

"A

(38) Ic.|

J n (q(Is+l) + q(IJ))

and

chk) E n(l-sy) (q2(rs,l) + q2(rJ)) .

where q(x) = {x(x + y)}-1 > O for x > O.
The first inequalities of (37) and (38) yield

<

(39) PiIZS(u,T)| é-n Y {q(IS+l) + q(IJ)} < 0°. To complete

the verification of assumption (82) define 6 = 6(I) = ;-min

2
5-1/2 I } 3:: I3 = %(1 - (s+l)y). Define

s+l , where Z

{Tlt“”TSO

the hyperplanes hJ = {I e RSI IJ = O}, J = 1,...,s and

s s 1
= = — - . ‘ +
“5+1 {I e R I 2J=1IJ 2 (1 (s+l)Y)} These 5 1 hyperplanes
intersected with the closure of T form the boundary of T. The distance
between. “J and I is given by IJ for J = 1,...,s and by 8-1/2TS+1 for
J = 8+1. hence S C: T since T is convex and the radius 6 is half the

6
distance of I to the closest boundary point of T in the bounding
hyperplanes H3, J = 1,...,s+1.
We now define the function M . Observe that if I' = (Ii,...,I;)

2
o . 1 5+1 , 1
s 96’ then IJ > E'TJ for J = 1,...,s+l, where 23:1 IJ = 5(1 - (s+l)Y).
Hence, with q(x) a strictly decreasing function on (0,“) we have
C
q(IJ) < q(%-IJ) for J = 1,...,s+1. Thus, define M2(u) =

2
n y q0 {2 n y + (l-sy)}, where q0 = qo(T) = maxJ=l 8+1q(é-IJ).
.000,

67.
Then, by (37) and (38) we see I23k(u,I')|é M2(u) a.e. v for
J,k = 1,...,s if I' e 86' This together with (39) completes the
verification of (B2)°
We have now shown that assumptions (Al), (A2), and (be) are
met for any I e T and hence Theorem 7 is valid for Example 1 with
any fixed I in T.

We now give two examples in which 3 = l.

mwele 20

Let U be the generic name for the Xa's. With 5 = 1 and
T = (0,"), fix I c T. The distribution of U under Pi is normal with
mean i and variance I for i = 0,1. Represent kl(u) by k(u) and
define
(ho) h(u) = u , k(u) = u2-u.
Then, Pih(U) = i and Pik(U) = I for i=O,1, and fixed I. Hence,
assumption (Al) is satisfied, since all absolute moments PiIUIk,
k = 1,2,... are finite for i = 0,1. Assumption (A2) is satisfied
since h and k are linearly independent and non-degenerate in
Ll(Pi) for i = 0,1.

To see that (b2) is satisfied, let u be Lebesgue measure, and
note that for i = 0,1, gi(u) =(2NT)-l/2 exp {- (2T)-l (u-i)2} .
hence, (3) implies
(bl) Z(u,I) = b (a exp I-l(u - $0 + b }-l .
We see that Z has first and second continuous partials with respect

to I on (0,”) which are given by

68.

 

(“2) Z'(u.T) = 23b g(u‘T) 2
I(& exp ((u,I) + b exp { - C(u,I)})

and

(h3) 201(u’1) = ' hab C(Lh'r) __

 

I2 (a exp C(u,T) + b exp {- C(u.1)})2

+ hab ;?(u,I) (a exp g(u,I) - b exp {-45(u,t)})
I2 (a exp g(u,I) + b exp {- ((u,I)})3

where ((u,I) = (21)-1 (u - é).

Observe that for t real, [t({a exp t+b exp(-t)}"2 é émax{a'2,b-2}
and t2 {a exp t + b exp(-t)}'2 é é-max {a-d,b-2}. hence, from (A2) and

(b3) we obtain

(at) IZ'(u,t)| é 1'1 e0,
IZ"(u,I)I é hI-2 c ,
o

where co = max {a-lb, ab-l}. The two inequalities of (Rh) together

with 6 = évrand M2(u) = 16 COT-2 imply assumption (52). To see this,

suppose I'£:86=((1/2)I,(3/2)I). Then, by (DA), IZ"(u,I')| ; 1((I')-2 CC

2

hxample 2 for fixed I e (0,“) and hence Theorem 7 holds for such a I.

< 16 co I-2. Therefore, assumptions (A1)’ (A ), and (82) are valid in

Example 3.
th . .
In the a component deClSlon problem, let X0 = (Xa1’°"’x

).

>
n = 2 be n independent random variables, each distributed as normal

on

with mean 6“ = O or 1, and variance I e T = (0,“). With U as the

generic name for the Xa's, define

(as) h(u) = T: = n‘1 if ui ,
1:1
1 n -
k(u) = (n-l)- 21:1(ui-u ,

where k(u) denotes kl(u) of Theorem 7.

Then, h(u) and h(u) are unbiased estimates of i and I under Pi for

i = 0,1 and fixed I in (0,”). Defining v as n—dimensional Lebesgue

measure, an analysis similar to that of Example 2 shows that conditions

(Al), (A2) and (B2) of Theorem 7 are satisfied for such a I. hence,

Theorem 7 holds for Example 3 with h(u) and h(u) defined by (AS).
Please note that in Example 3, we have "bunching" of observations

on each component problem; that is, we make n, n g 2, independent

observations for each component problem. This "bunching" is what

allows obtaining the stronger result for this example via Theorem 10

below.

h. Uniform Theorems in the Parameter I .
Two theorems are presented in which convergence of the regret
risk function is made uniform in I c C (as well as in 6 c Q“), where
C is a suitably chosen compact subset of T. Also, it is shown that,
in Example 3 of section h.3, uniformity in I on (0,”) cannot be obtained

for a wide class of sequences 6 in Cm.

Theorem 8.
Let T be a non-empty open convex set in RS and let C be a
compact subset of T. Assume that (Al), (A2), and.®2) hold for all

I e T and for I e C; i = 0,1; J = 1,...,s we have:

70.

. <

(l) Pi,1 [23(U,I)l = A < m ’

.. 5 , ... . .

(11) Pi,I M2(U) - M2 < , where M2(u) ex1sts by (B2) ,

... 3 5 m 3 S .
(111) Pi.T |h(u)| - h < , Pi’Tij(U)| h < w ,

>
(iv) A? = A* > 0, where A? is the minimum eigenvalue of V.
1’1 191 1,1

-(l/2)+e

Then, for e > O, R(6, t%.i*) - 6(6) = 0(N ) uniformly in 6 e $2co

and I e C.

Proof. Since C is compact and T forms an open covering of C, there
exists a 6 > 0 such that for every I e C, 86(1) C: T. With 6 > 0,
which is now independent of I e C, proceed exactly as in the proof

of Theorem 7. To complete the proof we need only show that the bounds
obtained in the proof of Theorem 7 are uniform in I e C.

Assumption (iii) provides uniform upper bounds in (11) and (16),
while assumptions (i), (ii), and (iii) yield uniform upper bounds for
the two terms on the right—hand side of (15). Next observe that
condition (iii) furnishes a uniform upper bound for dJ’ J = 1,...,s

in (21). Also, (iii) and (iv) assure that b in (22) is uniformly

O

bounded from above on C. Finally, we need Show that Pl T x P6
’

integrals of oi, i = 1,2,3 are bounded from above on C. by assumption

>
(iv), A; I = A* > 0’ for i = 0,1, I e C; while conditions (ii) and
9

(iii) imply, respectively, that Pi M2(U) and Pi T“w(U)“3 are
’

D
uniformly bounded from above for i = 0,1, I e C. Therefore, by applying

the norm triangle inequality in the first inequality of (31) and

bounding A: T from below by )* in (31) and (32), we have that the

71.

0:1 for i = 1,2,3 have uniformly bounded integrals in C with respect

to P P6 ’1, a e I
a

1,I x 1'
Since all bounds in the proof of Theorem 7 (the bounds for the

term CN being similar) have been shown to be independent of I e C,

the proof is complete.

The conditions (i) - (iv) of Theorem 8 are satisfied by the
three examples given after Theorem 7. We shall verify this statement
for Example 1 only.

Note that q(TJ) for J = 1,...,s+l is a continuous function on
T and hence by compactness of C there exists a constant

ql = max C q(TJ). Hence with A = yn ql and

J=l.o o o ,S+l’TE

M anl2 {2ny + (l-sy)}, we have by (37) and (38), IZj(u,I)| g A

2
<
and kgk(u,I)I = M2 on C. Thus, (1) and (ii) are satisfied.

Assumption (iii) is satisfied by uniform boundedness of h(u) and k(u)
given by (33). Assumption (iv) follows since Ag’1 = min{”y”=l} yVi’Ty'
is a continuous function of I for i = 0,1. We have thus established
that Theorem 8 holds for Example 1. Detailed analysis of Examples 2
and 3 yield the same result.

We now give a theorem which states under what conditions we can
obtain uniform convergence of the regret risk function when s = 1 and
T = [tl,t2], tl < t2, is a closed, bounded interval on the real line.
We shall here truncate E'to k} in T, where k2 is given by
(“6) E¥(x) = t

E7x), or t as k(X) < t1, 5 [tl,t2] or > t

l’ 2 2'

72.
Theorem 2.
Let T = [tl,t2] be a non-empty, closed, bounded interval of
the real line. Assume that (Al), (A2),and (82) hold for I e T and

that for I e T, i = 0,1,

"A

(i) Pi’T IZ'(U,I)|2 A<w ,
(ii) Pi,I M2(U) ; M2 < m, where M2(u) exists by (B2),
(iii) Pi.Tlh(U)I3 g H < a, Pi’1|k(U)|3 E x < a ,
(iv) A:.T ; A* > 0, where AE’T is the minimum eigenvalue of Vi, .

-(l/2)+e)

Then, for 5 >0, R(6,tr:x 1*) - 6(6) =O(N uniformly in 6 c Q”

0
and I e T.

Proof. Fix I e T. As in the proof of Theorem 7, write R(6,t%;£‘) =
AN + BN + CN’ where A, BN,and Cn are three terms on the right-hand
side of (9).

Observe that a second-order Taylor expansion (relative to T)

of Z(u,k*) about Z(u,I) implies

(67) Pen (z(u,t) - Z(u.i*)|

"A

“ l - 2
Pelk - IIu IZ'(U ,I)I+ -2- Pe(k - I) n(I-law”.

k - TI. Now express AN - 6(5) as in (10) and bound

IIA

since Ik* - II
Afi - 6(6) and AN - A& by inequalities (11) and (13) respectively.
Substitute inequality (h7) into the second term on the right-hand

side of (13), weaken by the Schwarz inequality and (6) in

Pa IB-6| é ach)N-l/2 and pe|g - 1|; C1 N-i/2

two inequalities into the first term on the right-hand side of (13)

and substitute the last

and into (R7), respectively. The resulting inequality is

73.

(he) AN - 6(5) é {2(a+b) 3(h) + CluIZ'(U,I)|}N-l/2
+ %-0§ n(M2(U))N'l.

Since assumptions (1), (ii) and (iii) provide uniform bounds on T for
uIZ'(U,I)I,u(M2(U)) and 6(h) and Cl’ respectively, (h8) implies

(69) AN - .(6) = 0(N'l/2

) uniformly in 6 e 9“ and I e T.

-(l/2)+e)

We now prove that B is of 0(N , 0 < £<':-, uniformly in

N
6 c Q" and I e T. We assume without loss of generality that N6 ; 1.

Fix a e I and consider inequality (18). To bound the P x P integral

1 6 l
of the first term on the right-hand side of (18) expand Z(u,k*) and
Z(u,k*(a)) on the set Ec [W E: in a second-order Taylor expansion

about I and note that IE‘ - k*(a)l g N"1 [k(xa) - k(u)] to obtain,
(50) [Z(u.i*> < h] [z(u.ii‘°’ $‘£‘°)1 <1 - (£1) (1-[Ea])

é [N(Z(U,T) " .9.) 4’ N(E* " 1) Z.(ueT) ‘%N6142(u)

(h(xu) - l) - ZleIoh(x£) (h(xl) - l)

<
{tell,i#d

"A

N(Z(u,I) - 6) + mil. -1 ) Z'(u,I) + -1- N‘M2(u)

2
(h(u) - 1) - z h(xg) + [k(xa) - k(u)]lZ'(u,IH

Rel
0

Let [Fa] denote the right-hand side of (so). Partition the P9 x Pl

integral of [Fe] into the sets {k = E*}, {k > k*} and {k < k“) .

On the set {E = k*}, write k' =ik in [Fe] and enlarge the domain of

integration by taking [1 = k*] g 1. With y(u) = (1,-Z(u,I)) and

w(xi) = (h(X£)-l., k(X£)-T) apply the B—E normal approximation to

the sum of the N6'- 1 random variables (y(u), w(X£)), 2 e I 2 # a,

l.
conditionally on u, x0, x2, 1 5 IO, as in develOping (25) and (26).

7h.
The resulting upper bound for PePllFa][E = 2*] is then given by the

bound in (26) where the second term of the minimization is increased

by the term

- -1/2

(51) (NS-l) °"°)P1Pea|k(X.’-k<”)’| IZ'(U.I)I o;1((y(6).w>>,

where the P integral is on U, the P integral on X0 and oi((y(u),w))

l e
O.
is for each u, the variance of (y(u),w(V)) under Pl on V. Inequalities
(29) and (30) imply that the term (51) is 2 (N611)'l/26'(o)(iI T)‘1/2
’

ll
P P (k(x )-k(U)|. Since A. is uniformly bounded from below by
1 6a a 1,I

assumption (iv) and since P1 “w(u)u3 and Pl|k(U)| and P M2(U) are uni-

l
formly bounded from above by assumptions (iii) and (ii) respectively,

this inequality together with (31) and (32) substituted into (26) is

seen to yield

-l/2

(52) PePiIFe] [i’= I”) = 0(min {l,(nfiLi) N€})

uniformly in I e T.

On the set {E’< 1*}, write 1* = t1 in [Fa] and enlarge the domain

- — <
of integration under the Pe x Pl integral by taking [k < k’] = 1.

Then apply the B-E normal approximation theorem to the sum of the

(NE-l) random variables h(xz) - l, 2 # a, 2 e I , conditionally on

1

u, x“, xi, 2 5 I0 to obtain
(53) POPIIFQJ [k < k*1

-l/2 [

IIA

min {l,(NE-l) ol'l(h) 6'(0) {NEP1M2(U)

+ PlPea(|h(Xa) - h(U)] + [k(Xa) - k(u)| IZ'(U.r)|)}

+ ol‘3(h) Pl [h(u) - l|3]} .

75.
The Schwarz integral inequality applied twice in the Pl x Pe term,
a
together with uniformly bounding all terms of (53) in accord with

assumptions (1), (ii), (iii) and (iv), yields the result
(5h) PePl [Fa] [E < 12*] = 0(min {1,(N6-1)-l/2N€}’
uniformly in I e T. A similar analysis shows that

(55) POPIIFa] [E > Ea] = o(min(l.(mé-i)'l/2N‘})

uniformly in I e T.
Observe that assumptions (iii) and (iv) imply that

b = sup b0(I) < a, where b = b0(I) is the bound in (22), while

0
(I) < a, for d1(I) in (21). Hence

IeT

(iii) implies d = supTET dl

inequalities (18), (22), (50), (52), (5h), and (55) now combine to
yield

(56) P6Pl(tfi;i,(u) - ta.i(a)*(U)) = O(min {i,(Né—l)‘l/2N‘})

uniformly in I c T.

Finally, summing (56) over for all a e I and recalling the

1
definition of BN’ we see that inequality (2.1h) with C = N
-(1/2)+c

6

implies BN=0(N ) uniformly in 6 c Q” and I e T. The same is

true for the term C . Hence, these results for B

N and CN’ (h9) and

N
(9) now complete the proof.

An example will now be given to illustrate the distinction
between Theorem 7 and uniform results on compact sets as given in
Theorem 8 andTheorem 9. Specifically, we will use Example 3 of

section h.3 and show that for this example we can choose a sequence

76.
IN +'~ such that the sequence of regret risk functions RN (6, t— —) -
¢N(6) + C(z) > o as N‘+ a for all e e a” such that e + g, 5 # (a+b)"1
as N + .. Hence, for this example uniformity in I on the non-compact

set T 8 (0,~) is impossible.

Let IN 8 N1+6 for some 6 > 0 and let 6 e an be such that

3 +.g, g # (a+b)-lb as N + a. Observe that for Example 3 of h.3,

¢N(6’) = a6P1[q(6)-’- ' n(u - —)1 + b(1-6) P 0[q(e) < ‘N n(u - -)1.
where q(6) a log {(a6)N lb(l-6)}. Hence, since TNl/Z nl/2(U- i) is
N(O,l) under P1 for i = 0,1, we have

(57) end?) = a Mm“ 224)“? (1(6) - gnrghl/Zn

+ b(l-é') {l-§((IN {l)m (1(6) + é-(ntgl)l/2)} .

Noting that q(E) < or > 0 according as E > or < (a+b)-lb, we see

that with IN = Nl+6and 6'+ E. 5 # (a+b)-lb as N +-~, equation (57)
implies
(58) 6N(6) + b(l-fi) or ag according as E > or < (a+b)-lb.

We now examine R N(6, t— -) as N + o. Observe that for Example 3

h, k

.. -l
h(Xi) = Xi = n 23:1 Xi, and hence,
(59) RN(e’th,i) - aN 2deIlP6[NZ(Xo’k) - Xd - 22#a X2]

-1 - - ..
+ bN zaeIoP6[Nz(Xa’k) - Xe < z25‘s x2] ’

" ‘-l " l -l
where Z(Xa,k) = b(a exp {nk (Xa - 5)} + b) . Observe that

-1 1/2
TN ) e

or 'i ,x(x ),...,x(XN), where k(X ) = (n i)'1 {El-1“ 2.1 X-l)2 from (us).

Hence, we may integrate with respect to the Joint marginal distribution

(n(N-l)"l 22 H# (i. - 6 2) is N(O, 1) under P and is independent

77-
of the N-l variables i;, 1 # a in each of the summands of (S9) to

obtain,
(60) RN(3,té-,T‘)

1/2

_ -1 -l -1 — - -
- aN a6I1P6{§({n(N-l) 1N,} {NZ(Xa,k) - N6 - xa + ea})} ,

1/2

+ bN-l 2 Pe{l - i ({n(N—1)"lrN ’1} {NZ(xa,i) - NE'- in + 6a))j .

aeIoP

Observe that by our choice of T = Nl+5, 6 > 0, we can conclude that

N
since [Z(Xu,i) - 6| g l, the variable {n(N-l)-11§1}1/2

in probability as N4+ w, for each a = l,...,N. Also, since
(nT;1)1/2 (SEQ - am) is Mo ,1), we have (n(N-l)-l "1)“2 (

in probability for a = l,...,N. Hence, the sum of these two variables

{uz(xu,i) - N6} +~o
i - e ) + o
0. 0.

given by the variable

—1 -1} 1/2 _ _ _
(61) {n(N-l) {NZ(Xa,k) - N6 - xa + ea} + o in probability

for each = l,...,N.

We now use (61) to obtain a limiting value for (60). Since a
continuous function of a random variable converging in probability to a
constant converges in probability to the corresponding functional value
of that constant, we see from (61), continuity of 6, the bounded conver-
gence theorem, and the Toeplitz Lemma (see Loeve, [9], p. 238) that the

limiting value of (60) is given by
0 ' _.
(62) 11mN+Q RN(6,th’k)

-- a€§(o) + b(l-€)§(0) = g-{ea + b(l-m .
Equations (5Q)and (62) yield as a limit for the regret risk function

the expression

78.

(63) linuwmuwafi) - ¢N('é)}= %(a+b) |a—(e+b)'1b| a cm > o,
where 6 + 5 # (a+b)-lb and TN = Nl+6, 6 > O.

This completes the example which shows that uniformity in 6 5 9°
and t e T is unobtainable for Example 3 where T = (0,”) is non-compact.
That this is truly a contradiction to regret risk convergence uniform
in both 6 e O” and T e T follows from the observation: If uniformity
held on both a“ and T, then for the diagonal sequence (BN’tN)’ N = 1,2,...,
we would have RN(6’€H,E) - ¢N(6) + O, which is contradicted by (63)

for Example 3 of section h.3.

5. §pecific Results when 8 = 1.

Let s = l and T be an Open interval of the real line. Denote t1

by 1 and k by k, and fix 1 e T. We give two cases in which the factor

1
N+8 can be eliminated in the convergence rate of Theorem 7.

Theorem 10.

Let (A1), (A2), and (B1) hold. If M e L2(Pi) and if h and k are

-l/2)

1

independent under P for i = 0.1, then R(6,tfi E*) - ¢(6) = 0(N
O

i
uniformly in 6 e a“.

Proof. Choose 6 > 0 such that SG(:'T and express R(°'té,ia) = AN+BN+CN

N-l/2

as in Theorem 7. Observe that AN - ¢(6) = O( ) uniformly in 6 e a“

as in Theorem 7 with a first-order Taylor expansion in (1h).

To obtain a bound for B , assume N6 ; 1, fix a e I

N l’ and note

that

79-

(615) 135.12 *(U) - t. h“ ). E(a).(U)

é [NZ(u.E*) - h(xa) < z“ h(x >= mz(u."‘°"*)- h(u)].

Let [Fa] denote the right-hand side of (6%). If we condition on

u, xa, x t 2 IO and k(xz), l = l,...,N in the P x P integral of

g' 6 1
[Fa]' then the B-E theorem yields, by independence of h and k, a bound

for this conditional probability given by
(65) (n€.1)'1/2{w(o){al(n)}‘l{h(u)-ma)|+n|z(u,in)-z(u,g(a)e)lml} ,

where 61 = 28(ol(h)}‘3 Pllh(U) - 1|3.

In the second term on the right-—hand side of (65) expand z(u,£¥)
about Z(u,§(a)*) in a first-order Taylor expansion on

E = {'E3 - Tl < '%6} f1 {li(a)* - 1| < $6} to obtain

N'Z(u,i‘) - Z(u,E(a)*)’ é lk(u) - k(xa)‘Ml(u). On the complement of
E bound ‘Z(u,i‘) - Z(u:i(a)*)) by unity and note that a change of

variable,Tchebichev‘s inequality and (6) imply P6Pl(l - [E]) g

2 :- 86-2 C 2 N-l. Hence,

> 1 < —2 -
2P6[\k* - 1| = 56] = 86 Pe(k-T) 1

-2C 2

IIA

(66) NP 6P l[z(u, k*)-Z(U ,'*“)*)| MIk(U)-k(x )IM1(U)+86

Finally, weakening by the Schwarz inequality to obtain
5 2 1/2 _
P1|k(U) - k(Xa)|Ml(U) - {2 PlMl (u)} 01(k) - b2 and

21/2

"A

P1|h(U) - h(Xa)I 01(h), inequalities (65) and (66) imply

"A

-l/2 b3}

(67) P6P1[Fa] min {l,(Né—l)

-l —2 2 . n
where b3 = §'(O) {21/2 + a1 (h)(b2 + 80 01)} + bl < ,

80.

Recalling the definition of BN and summing the Pe x P1 integral of

inequality (6h) for all a e 11’ we have, by inequality (67) and (2.1h)

with C = b3 and p = 6}

2)l/2
3 O

-l/2

(68) ul/2 bu é a(l+b

Hence,by (68), 3N = 0(N ) uniformly in 6 c Q". A similar argument

holds for CN’ and Theorem 10 is proved.

Note that in Example 3 following Theorem 7 the selection of
n, nJI>= 2, independent observations per problem furnish estimates
h and k, given by (RS), satisfying the independence condition of

Theorem 10.

Theorem 11.
Let (Bl) hold and assume there exists a function R e L3(Pi)
satisfying (h) such that 012(k) > 0 for i = 0,1. For almost all

u(v), let Z(u,I) be a strictly monotone function on T. Then, the

-l/2

regret risk function R(6,t'§ 2,) — 6(6) = 0(N ) uniformly in e e a”.
’

Proof. Choose 6 of assumption (Bl) such that 86 (L T. Identify

' -
t( = t5,k* in Lemma 5 to obtain

(69) R(e,t!e— )

.1?“
= {afiPePlu-t'E’EJUH + b(l-5)P6P0té”Ra(U)}

-1 '
+ 3“ zaeIlP6P1(t6,K*(U) ’ tag-Jud”)

+ b u‘1 {M P6P0(tj_ —-(a)§(U) - té’wun.

o 6,k

81.
Let A;, BN,and c
(69).

N denote the three terms on the right-hand side of

Note tnat here Ag - 6(5) is equal to the AN - Afi term in the

proof of Theorem 7 with 3 replaced by 5: Hence,-replacing h by 6
in (12) and (13) in the proof of Theorem 7, we obtain

um fi-ofi)é%numB)-umfll.

In (70) partition the space under the P integral into D6 ={IE3-'t| < 6}

9

and its complement. For fixed u, expand Z(u;E*) about Z(u,I) on D6

in a first-order Taylor expansion to obtain P6|Z(u,E‘) - Z(u,I)I é

-l/2

PeIi-TIMl(u) g N C1M1(u), where the last inequality follows from

the Schwarz integral inequality and (6). Bound |Z(u,E*) - Z(u,I)I ’

by unity on the complement of D6 and note that Tchebichev's inequality

and (6) imply Pe(l-[D5]) § 5‘2 012 N'l. Hence, from (70) we obtain,

"A

-1/2 2 -1

Clu(Ml(U)) + 5'2 c N .

N 1

(n) fi-nd)

To bound the term BN,assume N5 3 l and fix a 5 11' The
monotonicity assumption on Z implies that a unique inverse function
of Z(u,°), denoted of 2:1, exists on the range of Z(u,°) for almost
all u(v). hence,

(72) té’gflhl) " té’i(a)*(u) = [Fa].

where = - -1 - g ‘(0) " -1 - ) -
Fa {kw<Zu (6) k } or {k > zu (6) = k(u)} according as

Z(u,') is strictly increasing or decreasing on T.
For fixed u, x0, xi, 2 e 10’ the sum 226112#a(k(x2) - T) in Fa
falls into an interval of length [k(xa) - k(u)]. Hence a B-E approxi-

mation applied to the Pe x P1 of [Fa] conditionally on u, x , and
a

82.

xi, 1 5 IO, together with weakening the resulting bound by

re Pllk(xa) - k(U)I § 21’2 01(k), yields
a
(73) P6P1[Fa] é min {1,(N5L-1)'l/2 c} ,
1/2

Where C = 2 §'(0) + 28{Ol(k)}-3 Pl|k(U)-Tl3o

Hence, recalling the definition of B and summing the P x P integral

N 8 l
of inequality (72) for all a e 11’ (73) and (2.1h) imply

(7h) Nl/2 B E a(1+C2)l/2 for all e c am-

N
A similar result holds for CN’ which together with (69), (71), and

(7h) completes the proof.

It is interesting to note that Theorem 11 combines with Theorem 2
of Chapter II to state that if 5 25.1 is known for the 2 x 2 compound
testing problem, then under suitable assumptions (see Theorem 2 and

-1/2) uniformly in

Theorem 11) a regret risk convergence of order 0(N
6 c Q” can be obtained. However, the convergence rate in Theorem 7
has an additional factor of NE, 6 > 0, when both 5 and 1 are unknown

+
and need to be estimated. Attempts to remove the factor N 6 when

both 5 and T are unknown were unsuccessful except in Theorem 10.

SUMMARY

This thesis has demonstrated that compound decision procedures
which are asymptotically optimal in the sense of regret risk convergence
are obtainable for a variety of compound decision problems. The
existence of such procedures was heuristically argued by Robbins in
[10] and substantiated in the compound testing problem for two
distributions by hannan and Robbins in [7]. Motivated by these two
papers, we proved convergence theorems for the regret risk function
of non-simple, non-randomized procedures which are "Bayes" against
estimates h'of the empirical distribution on 9. The existence and
structure of the estimates h'are given by Theorem 1 and (1.11).

Three cases were considered: (1) the compound testing problem
between two specified distributions; (ii) the general m x n compound
decision problem; and (iii) the compound testing problem between two
specified families of distributions indexed by a common nuisance
parameter.

Theorems 2, 5, and 7 give the basic regret risk convergence
theorems for the three respective cases. Theorem 5 is of particular
interest since it treats the original problem of Hannah and
Robbins (Theorem h, [7]) in the general m x n compound decision
problem. Theorems 2 and 5 have uniform (in 6 e 9”) convergence rates

of 0(N-l/2),

while Theorem 7 has the slightly slower rate of
0(N4?/9*e)’ s > 0, caused by added estimation of the nuisance param-
eter. With the nuisance parameter in an Open interval of the real

line, removal of the factor N+6 is established in Theorem 10, if'h

83.

8h.
is independent of the estimate of the nuisance parameter, and in
Theorem ll, if the empirical distribution on 9 = {0,1} is known.
Theorems 3 and h reveal that, in the compound testing problem

'1/2) and

for two distributions, uniform convergence rates of 0(N
0(N-1) are attained if apprOpriate continuity conditions are imposed
on P0 and P1. Note that Theorem h states conditions under which the
procedure (2.9) has, regardless of the size of N, a sum of expected
losses for the N problems within a uniform constant of the minimum
expected sum of losses among all simple procedures. Theorem 6
generalizes the result of Theorem h under a suitable condition on

the m x n loss matrix.

Examples illustrating the extent, applicability, and non-vacuity
of the sufficient conditions were given for all theorems. Examples
were also presented to show that Theorem 6 is false without condition
(C) and to demonstrate that uniformity in both the nuisance parameter I
and 6 s Q” is impossible in Theorem 7.

Finally, we point out that Theorems 2 - 11 can be extended to
include the non-simple, randomized procedure which is attained by
substituting h'for p(6) (and E for I in Theorems 7 - 11) in the simple
randomized procedure which assigns equal probabilities of selection

among the columns minimizing (p(6), va) in (1.7). This randomized

rule and the proof of this statement are given in Appendix 3.

APPENDIX 1.

Proof that Condition (II") Implies Condition (11') when u = P. .

 

See Chapter III for the discussion of conditions 11' and II".

Lemma l.l;

 

Let xi, 1 = O,...,m-l be independent and identically distributed
uniform random variables on [0,1]. If 0 < k é 1 and if 21 = xi(1,x)’l,
i = l,...,m-l and Z = (Zl"'°’Zm-l)’ then the conditional distribution
of Z given (l,X) = z:;: Xi = k is uniform on S = {z =(zl,...,zm_:L)|zi 5 O,

0 < (1,2) é l} .

m-l

Proof. Fix 2., i = l,...,m-l such that z.;o,<)<2 2. § 1, Then,
1 1 i=1 1

(l) P{(1,X) < k, Zi < 21, i = l,...,m-l}

[1 l
= . [ [(l,x) <k, xi <(l,x)zi, i‘l,...,m-l] dx ...dxm_

jO 0' JO 0 l
m-l z. k m-l
_ l m-l _ -l m
0 0
where the second equality follows from the transformation yi= xi(l,x)-l,

i = l,...,m-l, yo = (l,x), having Jacobian yg-l .

Similarly, the marginal distribution of Y0 = (l,X) is given by

1 l
(2) 99:0 <k} = [o ...[0 [o é (l,x)< k] dxo...dxm_l = (1:11)“1 km,

m-l
which follows from the transformation ya = {i=3 xi, 3 = O,...,m-l

having unit Jacobian. The lemma follows from (1) and (2) by expressing
the conditional density of (21,...,Zm_l) as the Joint density of
(21,...,zm,(1,x)) which by (1) equals km-1 divided by the density

of (1.x) which by (2) equals {(m-1)z}'l km’l.

85.

86.
Lemma 1.2.
-1 __1
Let11= P. = 2:;0 Pi and let Pi Z represent the induced
distribution on 8 under the transformation 2: u + Zl(u),...,Zm_l(u),
with 21 = dPi/dP , for i I l,...,m—l. If for some K", Fig-1 é KnAm-l’
then there exists a K' such that Pif’l[BJ] é K'Am[BJ] for BJ(v,a,b)

Of the form (3.1h) with K = l and vJ(b-K) = 0, where f = (Z0....,Zm_l).

Proof. Note that by the definition of Pif'l, PiEbl, and the assumption

of this lemma, we have for J = l,...,m—l,

-l ‘-l m-l
(3) Pif [BJ] é PiZ ([--vo é 22:1 (vi-v0) 2, § a-VOJIZJ é b])

< < m-l
.--. K"}‘m.1(['v° = {Pl‘vz'vohg g a-vo][zJ é b][z e 8]) .

m-l
If J = O, replace the second factor in (3) by [l-b ; {J31 23]. With
-1
= * =
ampl Am_l[S], we see that the measure Am-l am—l Ampl’ when

restricted to S, is uniform on S. Hence, by Lemma 1.1, the right-hand

side of (3) equals for J = O,...,m-l,

1 1
(1,) K' [o ”.[o [0;(V,x)§&(1,X)][Xjé(lsx)b][0 <(l,x) =<=l]dxo...dxm_l:
K. _ n -1 1 l <
"Here - K “m-1“m and am = /; ...]; [o < (1.x) = lldxo...dxm_l.

Observing that ck = {1:1}...1 for k = m-l or m and that the function
under the integral in (h) is bounded by [BJ](x), we have that (h) sub-

stituted into (3) implies Pif-llBJ] 5 K'Am[BJ], where

-l

0
K g am—l am

K" = m K", and the lemma is proved.

Lemma 1.2 proves that condition (II") implies condition (II')

when u = P .

APPENDIX 2

Truncation of’i'to a Convex Set of R8.
Let 1 = {1 = (11,...,18)|11 e R} be a convex set of RS. with T
as the nuisance parameter set of Chapter IV, we shall give a constructive

method of truncating 21X), given by (h.5). to T.

Lemma 2.1.

If 10 is an exterior point of T, then there exists a unique point

16 in the boundary of T, denoted B(T), such that "10-t6||=mintefi“tO-t"'

where T'is the closure of the convex set T.

0
Ibo-18II8 minréfll1o-1H. Suppose 16 is an inner point of T. Then

Proof. Since T'is closed, there exists a 1 c T. such that

the line segment 116 + (l-l)1o, 0 § 1 § 1, would intersect the boundary

It 1 . n -
of T at a point 10 I 1010 0 < 1. Then 10 e T and

"to-Tgllt 10 ”to-16II< '10-16", which is a contradiction. Therefore,

16 is not an inner point, and hence is a boundary point of T.

To show that 16 is unique, suppose there exists 11 in the boundary

of T such that "10-11||= mintcfi-"10-1“, 11 f 16. Then the three

points 10, 15,and 1 are the vertices of an isosceles triangle having

1
equal sides "10-16“ = "10-11 . Hence, the mid-point of the base,

given by 12 = %(16 + 11) satisfies the Pythagorean equality

2 2 2
(1) I‘1’“2' + "10.12“ = "10“1" ‘

But, by convexity of T, we have 12 e T'and thus minTEEJLb-1llé "10-12H

éé-Ihodéll 4» 510-11” = minufillro-d . Hence, (1) implies "11-12” = 0,

87.

88.

0 is unique and the

or 13 8 11, a contradiction. Therefore, 1

lemma is proved.

Lemma 2.2 (Blackwell and Girshick),

Let T be a convex set in R8. If 11 is an inner point of T and
12 a boundary point of T, then the points (1-A)1l + 112 are inner
points of T for o é x < 1.

Proof. See Lemma 2.2.1(a) of [1].

With the aid of Lemmas 2.1 and 2.2 we can now truncate
f(X) 3 (ii(X),...,E;(X)) to T as follows. Let to s T be a fixed
interior point of T, which exists by the assumption on T in Chapter IV.

.a .. ..
Denote k (X) = (k1*(x),...,h:(x)) as the truncation of k(X) to T

given by,
f(x) if f(x) c T
(2) 130:) = 11"(x) if 12"(x) sT, f(x) .5 T

-1 1 — . -
(AON) 1041-00147 )k'(X) 1f y(x) t T,
f(x) 1 T.
where E3(X) is the unique boundary value of T closest to EKX) given

in Lemma 2.1 and 10 = maxT€B(T)H1O-1|

that 901) ET in the case where "12"(x) t T and f(x) :5 T. The truncated

 

. Note that Lemma 2.2 guarantees

estimate E3 depends on the fixed value 10. Note that from (2) we have

that if E t T, then "Iii-1"" é (1011)"l [Ito-'1? II ..E. N’l. Thus with T a
convex set of R8 we have exhibited a constructive method of truncation

meeting the requirements of Chapter IV.

 

APPENDIX 3

Extension of Results for a Randomized Procedure.

We extend Theorems 2 - 11 to the non-simple, randomized procedure
defined by substituting the estimate 3 for p(6) (and E for 1 in
Chapter IV) in the simple randomized procedure which assigns equal
probabilities of selection among all columns minimizing (p(6), va)
in (1.7). Such a randomized, non-simple rule is given by the N x n

matrix of function T*(x) = (t;J(x)). where for J = O,...,n-l, a = l,...,N,
-l
(l) t:J(x) = r (d,x) or 0 according as J c or t Ra(x),

where Ra(x) - {JI(E,LJf(xa)) 8 m:n(h,ka(xo))}, having cardinality
r(c,x). We shall show that Theorems 2 - 11 (also, substitute 1'?”
v in Chapter IV) hold for the randomized procedure T*(x).

Let €h.be the class of all permutations on the integers
{O,...,n-l}. The elements of‘9b, denoted by n , are 1-1 functions of
(O,...,m-l) onto itself defined by n(O,...,n-l) = {u(0),...,n(n-1)},
where w(J) s {O,...,n-l} and n(J) = n(k) if and only if J = k.

Let ' denote the identity permutation having '(J) = J for J = O,...,m-1.

Now define the following class of non-randomized rules tg, n e 91. ,

 

given by
( .-
1 if (h,LJvf(xu)) < or § 0 according as
(2) t! (x ) = ( «m < «(3) or «m > m)
hoJ c
i 0 otherwise.

Note that t% J(xa) is that particular non-randomized, non-simple rule

given by (1.12) for which Theorems 2-11 are proved. Modifications of

89.

90.

this rule were made in Chapters II and IV and the corresponding
modifications hold for the permuted rules in (2).

Now average the regret risk functions of the n! rules ti- and
interchange the order of summation and integration to obtain
Theorems 2 - 11 holding for the non-simple procedure defined by the

N x n functions

-1
(3) (n!) Zn€9l tE.J(xQ), a = l,...,N, J = O,...,n-l.

We shall now prove that (3) = t;J(x).

Fix c,J,x and let r = r(c,x), R = Ra(x). Observe that J t R
implies tg.d(xa) = 0 for all u s ’2. Hence, if J t R, (3) = 0 and
so is t:J(x) given by (1). Next, observe that if J a R, then n-r
{1‘91 tg’dha) = {“92 [1(v) > n(J) for all u e R, where v 1‘ J] = {ta-o
x{ulu(J)=t} [n(v) > t for all v s R, where v # J]. The number of
permutations u 2 7L having the permuted position 1'(JJ) fixed at t and
with r-l permuted positions n(v) greater than t is (n—t-l)! P(n-r,t),
where P(n,k) is the permutation of n obJects k at a time. With C(n,k)
denoting the combination of n obJects k at a time, we have
(n-t-l)! P(n-r,t)=C(n-t—l,r-1) (n-r)! (r-l)! Hence, by our earlier

n-r
observations we have that if J c R, then {11572 t; J(x0) s Xt=°(n-t-1)!
O

n-r
P(n-r,t) = (n-r)! (r-l)! 2t-° C(n-t-1,r_1), Finally. since
n-r
{tgo C(n-t-l,r-l) = C(n,r), (see Feller [3], (12.8), p, 62). we

conclude that if J c R,

-1 u _ -1
m (a!) 2,59, 23.3“.) - r .

91.
hence, we have shown that t*a J(x) defined by (1) equals (3). Since
’

Theorems 2 - ll hold for the procedure given by (3), the same is true

for T*(x) defined by (1).

[1]

[2]

[3]

[h]

[5]

[6]

[7]

[3]

[9]

BIBLIOGRAPHY

BLACKWELL, DAVID and GIRSHICK, M. A. (1951;). Theory of Games

 

and Statistical Decisions. Wiley, New York.

CRAIG, CECIL C. (1936). On the Tchebycheff inequality of
Bernstein. Ann. Math. Statist. &: 9h-102.

FELLER, WILLIAM (195?). An Introduction to Probability Theory
and Its Applications. .1; (2nd ed.) Wiley, New York.

HALMDS, PAUL R. (1950). Measure Theory. Van'Nostrand,

 

Princeton.

HANNAN, JAMES F. (1953). Asymptotic solutions of compound
decision problems: Institute of Statistics MimeOgraph
Series, Univ. of North Carolina. No. 68, 1-77.

HANNAN, JAMES F. (1957). Approximation to Bayes risk in
repeated play. Contributions to the Theory of Games,
a: 97-139. Ann. of Math. Studies No. 39, Princeton
Univ. Press.

mum, JAMES F. and ROBBINS, RERBERT (1955). Asymptotic
solutions of the compound decision problem for two
completely specified distributions. Ann. Math. Statist.
39. 37-51.

RANNAN, JAMES F. (1957). Unpublished lecture notes.
Michigan State Univ.

LOEVE, MICHEL (1960). Probability Theory. (2nd ed.)

Van Nostrand, Princeton.

92.

93.
[10] ROBBINS, HERBERT (1951). Asymptotically subminimax solutions

of compound statistical decision problems. Proc. Second

 

Berkeley Symp. Math. Statist. Prob. 131—lh8. Univ. of
California Press.

[11] SAMUEL, ESTER (1961). On the compound decision problem in
the nonsequential and the sequential case. Ph.D. Thesis,

Columbia Univ.

ltem R
Crea

Reu
Stre

“.2

q—

 

"liffliiflillfi‘fli‘iiiflifiis