O (N?) CONVERGENCE IN THE FINrrE STATE ‘ RESTRICTED RISK COMPONENT SEQUENCE COMPOUND ., DECISION PROBLEM Dissertation for the Degree of Ph. D. MICHIGAN STATE UNIVERSITY STEPHEN BRUCE VARDEMAN 1975 This is to certify that the thesis entitled 0(N%) CONVERGENCE IN THE FINITE STATE {1 u ' _ M .s". .- .- 3. g -1t-': ‘.,. t'. ,_,.‘ ‘lsbwg-.'{l).-.- . 9"ka 22:. V3333? .\ H‘ "R J! 1 RESTRICTED RISK COMPONENT SEQUENCE COMPOUND DECISION PROBLEM ' ‘ - presented by St ephen Bruce Vardeman has been accepted towards fulfillment of the requirements for Statistics and Probability Major professor ABSTRACT 0(N%) CONVERGENCE IN THE FINITE STATE RESTRICTED RISK COMPONENT SEQUENCE COMPOUND DECISION PROBLEM By Stephen Bruce Vardeman We consider a sequence of independent, structurally identical, finite state restricted risk component decision problems, where the choice of risk point in the ath problem is allowed to depend on observa- tions from the previous problems, and the goal is to control the total risk incurred across the first N problems. k-extended standards for the risk of sequence compound procedures are introduced. In the most general situation in terms of allowable form of the component problem risk set and distributions of the observations, bounds are obtained for the risks of a family of procedures employing artificial randomization. Appropriate specification of a sequence of constants appearing in both the bounds and description of the procedures give *2 total risk approximating the k-extended standard at a 0(N ) rate. It is noted that the formulation of the problem given includes a game theoretic situation in which the information about past states carried by the observations is perfect. Four procedures appropriate to such a situation are offered, each of which has risk approximating the L k-extended standard at a OCNZ) rate. Finally, nondegeneracy con- ditions are imposed on the distributions of the observations and the Stephen Bruce Vardeman resulting statistical version of the problem is studied. A rate of weak convergence theorem of BhattaCharya ((1970). Rates of weak con- vergence for the multidimensional central limit theorems Theory 2; Probability and its Applications :2, 68-86.) and Mirahmedov ((1974). The rate of weak convergence in the multidimensional limit theorem. Izv. Akad. Nauk UzSSR Ser. Fiz.-Mat. Nauk 18 no. 2, 23-28, 92-93.) is applied to show that in a two state case, a natural procedure has risk approximating the usual unextended standard at a 0(N%) rate. 0(Ng) CONVERGENCE IN THE FINITE STATE RESTRICTED RISK COMPONENT SEQUENCE COMPOUND DECISION PROBLEM By Stephen Bruce Vardeman A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Statistics and Probability 1975 ACKNOWLEDGEMENTS I am truly grateful to Professor James Hannan for his guidance during my two years at Michigan State University. I feel fortunate to have been able to draw on his expert knowledge of mathematical statistics both in course work and in the preparation of this dissertation. Without his patience, encouragement and many suggestions this dissertation would never have come into existence. I would also like to thank the other members of my guidance committee, Professors Dennis Gilliland, Hira Koul, Raoul LePage and Joel Shapiro. Conversations with Professors Gilliland and LePage concerning sections one through three were especially helpful. Financial support provided by the Department of Statistics and Probability and the National Science Foundation made my graduate studies in Statistics possible. I wish to thank both of them. I am grateful to Mrs. Noralee Burkhardt, who typed this dissertation. Her excellent and fast typing of the manuscript was done cheerfully and quite unselfishly. Finally, I wish to thank my wife, Jo Ellen. The Supportive and encouraging Spirit that she has maintained over the past four years has been a major ingredient of my success as a graduate student. ii Section TABLE OF CONTENTS INTRODUCTION ........................................... THE k-EXTENDED FINITE STATE RESTRICTED RISK COMPONENT SEQUENCE COMPOUND DECISION PROBLEM ..................... 1.1. The component problem ............................ 1.2. The sequence compound problem .................... 1.3. Bayes rules in the component problem ............. 1.4. The rJC construct 0.000.000.0000...00.0.0000...9. 1.5. Assumption on the P6 and estimation of empirics. A BOUND ON THE RISK OF A k-EXTENDED PROCEDURE EMPLOYING ARTIFICIAL RANDOMIZATION ............................... 2.1. Two lemms ......O................O............... 2.2. Definition of the procedure § ................... 2.3. A bound for the risk of §_....................... k'EmENDED CAPE THEORETIC RESLILTS ...-00.000000000000000 3.1. Specialization to a game theoretic setting ....... 3.2. A decomposition of Yk(G:) in the case k > 1 ... 3.3. A modification of Hannan's game theoretic strategy ......................................... 3.4. A modification of BlaCkwell's game theoretic strategy ......................................... 3.5. A comment on the effect of play against a random perturbation of Gk 1 in the k-extended setting . a- ; THE UNEXEENDED STATISTICAL PROBLEM, 0(N2) CONVERGENCE To “(6:1) OF THE RISK OF THE NATURAL PROCEDURE IN THE Two STATE CASE ......OOOOOOOIOOOOOCOOOO.....IOOQOOOOOOOO 4.1. Specializations for the unextended statistical problem, assumptions on the P , the natural procedure pg .................9................... Bounds on A for general finite m .............. The two state problem ............................ 0(N2) rates in the two state problem ............ 4545-5 wa iii a>\1 O\$~£~ 10 10 ll 12 16 16 16 l7 19 21 23 24 26 33 34 Section Page APPENDIX ...................................................... 38 A.1. A bound for the risk of Blackwell's unextended Strategy .....................C...................... 38 A.2. Two lemmas concerning properties of multivariate norml diStribUtionS ......OOOOOCCCOCCI00.00.000.000. 42 A.3. A rate of weak convergence result of Bhattacharya- Mirahmedov .......OOOOOOOOO.....OOIOCOCOOOOOOOOOO.... 43 RHEENCES 0..........0.0.000.........OOOOIOOOOOO....0.0.0.0... 48 .iv 0. INTRODUCTION Simultaneous consideration of a number of independent structurally identical decision problems with the goal of controlling the average or total risk incurred across the problems was first suggested by Robbins (1951). Robbins termed his original example involving N independent discriminations between normal (1,1) and normal (-l,l) distributions a compound decision problem. The procedure he proposed has total risk approximating N times the Bayes risk versus the normalized empirical distribution of states in the component testing problem, and finding procedures with similar total risk performance became the usual objective in compound decision theory. Hannan (1956), (1957) in rather general finite state settings showed that the usual compound decision theoretic goal is achievable not only in situations in which all N of the problems are considered simultaneously, but also in situations where the independent structurally identical problems are faced serially. Such a modifica- tion of the compound setting has become known as a sequence compound decision problem. Hannan's procedures involve artificial randomiza- tion and are applicable in situations in which before making the ath decision one has available either the exact empiric distribution of states through the (a-1)st problem or an estimate of the same. Van Ryzin (1966b) showed that in many finite state finite act statistical versions of the sequence compound problem, the extra randomization 1 employed by Hannan is not necessary. In a sense, enough randomness enters through the estimation of empiric distributions of states. Van Ryzin's arguments are closely tied to his assumption of a finite action Space. Johns (1967) and Gilliland and Hannan (1969a) suggested standards of performance for compound procedures which are appropriate to sequence versions of compound problems and asymptotically more stringent than the uSual standards. These standards, which take into account kth order empirical dependenciesixithe sequence of states have become known as k-extended standards. Work of Ballard (1974) and Ballard, Gilliland and Hannan (1974) shows that in Van Ryzin's finite state finite act statistical setting, generalizations of his non- randomized procedures have risk approximating these k-extended objectives. In this thesis we treat a particularly tractable, yet quite general finite state sequence compound decision problem. The gen- erality of the problem derives primarily from the fact that a risk structure rather than action Space and loss structure is assumed for the component problem. In §1 this finite state restricted risk component sequence compound decision problem is described along with the unextended and k-extended standards for the problem. The estima- tion of kth order empirical distributions of states is also very briefly considered. Section 2 contains the description of procedures which are generalizations of the procedures involving randomization proposed originally by Hannan. We bound the total risk of the pro- cedures and note that appropriate choice of arbitrary constants yields bounds approximating the k-extended standards at a 0(N%) rate. In §3 it is noted that the problem includes a game theoretic situation in which the component risk set is composed of the risk points available to player II, and before each repetition of the game, II is furnished with the empirical distribution of 1's moves through the previous play. After noting a simple game theoretic decomposition of the k-extended standard, three procedures are provided in addition to the game theoretic Specialization of the procedure from §2, which have risk approximating the k-extended standard at a OCNI) rate. The basic technique employed in §3.3 and §3.4 has been uSed independently by Cover and Shenar (1974) in a less general situation. The results of §4 all concern the unextended version of the problem. Using a rate of weak convergence reSult of Bhattacharya (l970)- Mirahmedov (1974), we Show that certain natural procedures in a two state case have risks approximating the uSual standard at a O(N%) rate. The procedures are related to those of Van Ryzin in that no extra randomization is employed. The appendix contains several results applied in the body If the thesis. Several notational conventions should be mentioned. Vectors in Rm are considered to be column vectors, although to save Space they occasionally appear as row vectors in the text. Euclidean vector norms are denoted as “0“. V and A stand for supremum and infimum respectively. Q denotes the univariate standard normal distribution and em is the m-variate standard normal distribution function. m 6’ is the Borel sigma algebra on Rm} The term "range" of a matrix refers to its column Space. lbs and rhs are used to abbreviate left hand side and right hand side reSpectively. For probabilities v1 and v2, Ivl - V2I will denote the total variation of the signed meaSure v1 - v2. Displays are numbered consecutively in §1 through §4 with the diSplays in the appendix numbered separately. 1. THE k-EXTENDED FINITE STATE RESTRICTED RISK COMPONENT SEQUENCE COMPOUND DECISION PROBLEM 1.1. The component problem. We consider a (component) decision problem with states 9 6 ® = {l,2,...,m} and risk set S c:[0,a9“k For each 9 6 ® let iPe bea.probability on a measurable Space (1,3). In all that follows we shall assume that S is bounded, “sum S‘B < m for each s E S, where “.“m denotes the supremum norm for mdvectors. Gilliland and Hannan (1974) use the term "restricted risk" to in- dicate that 8 may be a proper subset of the largest possible risk set for a given action Space and loss function. For w a finite signed measure on ® and s 6 S we will let ws denote Js(-)dw(-). In the case where w is a proba- bility ws is the Bayes risk of 3 against the prior distribu- tion w. It will be convenient to identify each 9 6 ® with the probability on ® concentrated at 9. as is then the e co- ordinate of 3. Further notational economy will be possible by agreeing to also identify finite signed measures on ® with m- vectors, w correSponding to (w({l}), w({2}),...,w({m})) E Rm. 1.2. The sequence compound problem. A compound decision problem as introduced by Robbins (1951) involves N independent repetitions of the component problem des- cribed in section 1. We will consider a sequence version in which A the choice of risk function in component a is allowed to depend upon independent, Pe distributed observations for B s a-l, and the compound risk is taken as the sum of risks in components 1 through N. More precisely, let k be a positive integer and §'= (Sl’SZ’°"’SN) be such that sa is a Sa+k-2 measurable mapping into S. For 3N = (92_k,...,QN) we suppose that EN = (X2 k,...,XN) is distributed as X...X P . (The pur- P eZ-k pose of allowing indices 0 < l in the case k > 1 here is to simplify later notation.) The compound risk of the sequence rule g. is N N 2 E s X = V s - dP X...X (1) 0:1 ea 01(‘or-1) § 90! ( ) 62_k Pea-l When §_= (s,s,...,s) for s E S the risk (1) becomes N N 1 E e s = (2 e )S = GN S , 10’ 10‘ where as indicated earlier, we are identifying elements of @ with probabilities on ® rand G; is the non-normalized empiric distribu- . . l l 1 tion of {el,...,eN}. With Y (GN) = A G S, Hannan (1957), (1956) 568 N first exhibited procedures in versions of the sequence-compound problem achieving Y1(G;) asymptotically. Let 8* be a class of 3 - measurable mappings into S. We consider the sequence compound rules of the form §_= (8*,...,S*) for 3* 6 8*. For such g_ the risk (1) reduces to the functional (2) g E e 5*(X ... X ) = g jg 3*(-)dP X...X P 1 oz a-k+1’ ’a-l oz=1 oz Cork+1 Cw1 k of GN’ the non-normalized empirical distribution on EN of the vectors {(92_k,...,91),(93_k,...,ez) ,...,(eN_k+1---,QN)}. Swain (1965), Johns (1967), and Gilliland and Hannan (1969) have termed 3 RR)“ NE 8*X x ( ) Y (GN - *A * 2 ea ( a_k+1...., a_1 S 63 1 ) a k-extended simple envelope evaluated at G:: Notice that in the 3’: k .. case S is the class of all 3 1 measurable mappings into S, for fixed 3N, Yk(G:) s Yk-1(G:-1). That is, the extended envelopes are increasingly stringent. The purpose of this work is to exhibit sequence compound rules which achieve risk Yk(G:) asymptotically with rate. 1.3. Bayes rules ig_the component problem. We will make the assumption that S is not only bounded, but also closed. For any w E Rm, A ws is then attained and we denote an infimizing s by 0(w). ST: is a simple consequence of Corollary 1 of Brown and Purves (1973) that there is a Borel measur- able determination of o(-). In addition we may assume that o(-) has the property that o(pw) = o(w) for p > 0. (If not, we replace 0(w) by 0(W/HWH ) for w # 0, where H-“ is the usual Euclidean vector norm.) Notice that with this notation we have T1= A Gls=GN 0(GN) sES There is no essential loss of generality in the assumption m that S is closed. If S. denotes the closure of S in R , for any 6 > 0 and any sequence compound rule g} = (si,sé,...,s§) -2 _ where s 33 k measurable mapping into 8, there exists a -2 a rule §_= (81,...,SN) such that sq is a 3a+k measurable ' 't 3 'th s - - s'. sz‘o’ ... mapping in o Wi I98 a( ) 96 a( )I a each 95 E O N N X — E ' X ' f d Hence I g E 9080(‘o-1) E eoSo(—o~1)I < e or all 3N, an theorems concerning the risks of S' valued rules have s analogues for S valued rules. 1.4. The Pk construct. . . . . k k In order to describe compound rules achieVing risk Y (GN) asymptotically, we introduce a variant of Gilliland and Hannan's Pk decision problem. The Pk problem has finite state Space Gk k and risk set S c: [O,+Oo)m where k * * * ~ ~ m ~ S = {s 6 R I(e ,...,ek)s = f9 3 (-)dP XP X...XP for some 5 ES } 1 k e 9 9 1 2 k-l k . . The f problem Inherits the property of bounded risk from the com- ponent problem. We shall use notational conventions for the fk construct Similar to those introduced for the component problem. That is, we will identify each 3_ E @k with the probability on k k g degenerate at 3, let m -vectors correspond to signed measures on @k, and for v a signed measure on @k, S 6 S denote v§ = IS(-)dv(-). 5(v) will denote a Borel measurable, positive homogeneous minimizer of VS. (That no essential generality will be lost by the assumption that S is closed follows from a comment similar to that made in the previous paragraph.) k Using the P notation we have from (2) and (3) k k N , * Y (GN) = /\ z jeas (.)dPe ><...XPe * ~k .. _ N = A~ 2 (e . ,9 )§ ses 1 “’k+1 a = A~ a; s Ees k z k - GN 0(GN) k k We extend the domain of Y to all of Rm by defining k mk (4) Y (V) = v5(v) all v 6 R * It will be important to recover elements of S which give * rise to values of the minimizer 6(-). Thus assume that s (-,-) k is a mapping from Rm X IF-l into S with the property that for mk * * v E R , s (v,-) E S such that * ~ k (5) f9 8 (v,')dP x...x P = (e .....e )g(V) each 3_ e e . k e e 1 k 1 k-l Notice that in the case k = l, the Pk construct is identical A with the original component problem and we take 3 (v) = 5(v) = o(v). 1.5. Assumption 2_ the P9 and estimation g£.empirics. We will assume that é’= {P9} is a linearly independent GEO family of measures. That is, for real numbers a "%n’ g a P 1,.. eg@ 9 6 is the zero signed measure only if each a9 = 0. Robbins (1964), Van Ryzin(1966a), and Ballard (1974) discuss the estimation of mixtures of a finite number of linearly independent distributions. In the linearly independent Situation there are Rm valued, bounded, 3 measurable mappings t with the property that jt(')qu is the mdvector with all zero entries except a l in the 9 position. t(X ) is then an unbiased estimate of the m-vector corresponding to a 9 . Ballard (1974) uses vectors of all possible products of co- 0 k ordinates of k Such mappings t to construct Rm valued, k ~ bounded S measurable mappings t with the property that IE(.)dP9 X...X P9 is the mk-vector with all zero entries except a l k ~ ' 1 in the (el,ez,...,ek) position. t(X X ) is then an a-k'tl’u.’ a . . k . unbiased estimate of the m -vector correSponding to (e .---.9 ), 0’ a k+l a and E {(X, ,...,X.) is an unbiased estimate of the mk-vector j=1 J-k+l j k corresponding to G . a We will not assume a Special product structure for our ~ k estimates but will assume only that t is an S measurable mapping k . m . into R with the properties k ~ m - x...‘ = ,..., (6) [a )dPe x P6 (91 9k) 6 R , l k and (7) v (\\E( )I )de ~

1, o a-k+l a a j 1 J ‘— 0 otherwise. 2. A BOUND ON THE RISK OF A k-EXTENDED SEQUENCE COMPOUND PROCEDURE EMPLOYING ARTIFICIAL RANDOMIZATION We introduce a generalization of a Strategy in the sequence compound problem proposed by Hannan (1957), (1956) and bound its risk. When constants appearing in both the description of the pro- cedure and the bound are appropriately chosen, the strategy is seen to achieve risk Yk(G:) + 0(Ng) uniform in 3N. 2.1. mm. Forms of the two lemmas which follow appeared first in Hannan (1957) and variations of one or the other have since appeared in Samuel (1963), (1965), Swain (1965), Van Ryzin (1966), Gilliland (1969) and Gilliland and Hannan (1969a)- Lemma 1. Let f ,f .,f be real-valued functions on some set 1 2’“ N a .D. Denote F = g fj and suppose that for each 1 s a S N, a 1 1 d 6.3 such that F (d ) = A F (d). Let d be arbitrary. at or 01 (16.8 or 0 N N F d . Then Efama) g N(dN) _<_ EEO} 0H) a-l 0-1 N N-l r . f(d =F(d -::Fd )-F(d)).But Leaf 21: a a) N N) 1 (01(m1 a a N F d - F d 2 0. A13 2 f d = for each a, a( a+1) o( a) 0 1 o( 0-1) N F (d ) + 2 (F (d ) - F (d )). And for each a. N N 1 a o-l a a F d - F d 2 0 . 01‘ (H) “(0) I 10 11 The application we will make of this lemma is to take ,3 = S, k 0’ f (S) = v S for v E Rm , let V = 2 v and conclude a o a a _ B 3-1 N k N " V " V (8) Elva“ 01) g Y (VN) g 2 vao( 01-1) a-l a=l We will not prove the next lemma. Apart from slight nota- tional differences, the proof of a similar lemma in section 3 of Gilliland (1969) applies in our case also. Gilliland's assumptions that v,v',z are R” ‘vectors may be altered to v,v',z being Rmk vectors without change in the form of the proof, his B may be re-interpreted as our supremum norm on S, and his assumption that the co-ordinates of v,v' are non-negative may be dropped. Lemma 2. Let Z be uniformly distributed on [0,1]m andklet u be the distribution of Z. For any v,v' belonging to Rm , any .Q E @k I“- a(6(v + 2) - 5(V' + 2))I _<_B\Iv - V'IIl. where operator notation is used to indicate integration. The lemma then gives (9) “u,('5(v + z) - 5(v' + 2))“00 g BIIv - v'IIl . 2.2. Definition of the procedures 3, Take {H }:_1 to be a non-decreasing sequence of positive a _ constants. Define H = 0 for a 3.0 and denote h = H - H . a k a a 0-1 Let Z be a uniform [0,l]m random Vector independent of Xa for each 2-k g_a ng. We will consider the procedure = (S1,S Iv» 2,...,§N) where 12 *~ ‘ = z ,...,x (10) sa 3 (To-k + Ha-k , (Xa-k+1 o-1)) (In the a component, the proposed procedure uses an element of * ~ S correSponding to an element of S which is Pk Bayes against a randomly perturbed estimate of G:_k.) 2.3. A_bound for the risk of fig. Theorem 1. N N k 2 E e S g_Yk(G ) +~l-B H mk + B k T (1 + 2T 2 l"? a (10’ N 2 N k k _ H a=1 a-l a uniform in EN, where for each a, E Gaga is interpreted as an iterated integral, the first integration with reSpect to the dis— a-k+l’...’xa-l) on Ik-l, and the second with k ,x ) on 19'1 x [0,1]m . tribution of (X reSpect to the distribution of (X k,Z a- Proof. Use operator notation to indicate integration and 2_k,... the following notations for distributions. Let P. denote the joint distribution of ZN’ Pa = P6 X...X PS the joint distribution Z-k a-k of X , = P X...X P the joint distribution of -u-k go 9 9 a-k+l q-l (Xa_k+1,...,Xa_1), and u the distribution of Z. N N * ~ S = + ... N ~ = ,..., " T + H p u Pfi k (13) I€,P(5a-k - 80M _<_ NISOIIIlIIO.(TOPk - 25me T k ‘, T We write 8 k ' 5 = 3‘41;"+ fl ' 5 ‘Q'+ 2‘ and (13) and (9) a- d IH ' H .‘ oz-k or give Ifau(aa -k ‘ 5 a)I k ’3 Eel-Hi .31 .I:L______ _ " .EL__ _.L_ g IIEaII II J—I-I1= BIIEQII II Ha TOM‘S, _k H >II1 k o-k 1 1 1 PNE N (— 2 IN: .N + <—-—--—> EN alHai=a1 -1c+31 Hark qu=1IIJlI Hence N (14) z PIE Il-(O k - ‘5 )I a=k+l 9" 0’ N k a-k 1 1 1 3B 2 RI— 2 EIIIIIE- -II +(—‘""‘)EIEIIIIE-II o=k+l Ho j=1u1a o k+J 1 Ha-k Ha j=lI a 1 J 1) 14 The Schwarz inequality and (7) applied to (14) give .1. H . N N ~ ~ k 2 2 z memo -o)IgBZ(—T+(1 --L')(oz-k)'r) _ ' a ark d H k H H k a-k'I'l a=k+l CY d'k d 2 N 1 k N =BT 2kg—+zL-gg— k H111 _ H H or 01—1 or N-k 01 But k k P E ~ - " P If I " - " I < B k T 0131... PI (fowl, “a” s ”E .. PI aIlIIOoz-k “MI... _ 1. by the moment inequality. So we have 2 N 1 k N 2N AgBka+BTk ZR; {-1- )3 g—- 2 g“- _<_Bka'i'ZBkaZ k+l a oz=l a N-k or 1 0' Now bound C. N N k ~ c=1> ‘E'E SP E +hz” sP _uif do! _u213(a and _u‘I’(TN+HNz) by (8). But by (4) k ~ .. + H = + ~ g u ‘1' (TN NZ) 3 MTN HNZ)O'(TN + HNz) < P MT + H 2)8(Gk) = 1:65,, + THND 5mg) agamfi) + ELNIIaccgml RINGS) + 15%ka . IA , k k That is, C 5_Y (GN) + THNka and combining the bounds, the theorem is proved . I 15 It is clear from the proof that the result of Theorem 1 is k basically a P phenomenon, hence the iterated integral condition .. .. 1‘ k-1 appears. Under conditions suffic1ent to allow a 5” x 3 * measurable choice of s (-,-) the Special interpretation of eXpectation becomes unnecessary. L Corollary 1. With the choice H = a2 each a, o N (15) z E e ‘5: = Nk + 001%) (1:1 (y C! N uniform in 5N. Notice that the corollary shows that on an average, rather 1v than total risk scale, with H = oz, the risk incurred by the 0 Jv strategy §_ is Yk(%°G§) + 0(N 2) uniform in 3N. 3. k-EXTENDED GAME'THEORETIC RESULTS The framework introduced in section 1 is quite flexible. Both decision theoretic and game theoretic problems are covered. In this section we consider a game theoretic setting, that is a situation where the information about past states is assumed to be perfect. 3.1. Specializations to a game theoretic setting. We take I = 8, let S be the set of all subsets of ® * and suppose each P to be degenerate at e. S becomes the set 6 k- of all functions from O 1 into S and we may take E(3_) = mk k , §_ 6 R where we are still identifying m dvectors with Signed measures on @k and elements of @k with degenerate probabilities on CF. Theorem 1 and Corollary 1 are in force in this Situation so that Specializations of the strategies §_ provide asymptotic solutions of the k-extended game theoretic sequence compound problem. In addition, a simple decomposition of the k-extended enve10pe is available in this setting that allows us to modify solutions of the unextended problem to produce solutions of the k-extended problem. 3.2. AWQI Yk(G:) £95933 k>1. For each 3.6 QN-l define GZIfi' to be the g, section of Gk. That is, let GZIE. be the measure on ® defined by a _ l6 l7 czIaqep = Gk({(£.9)}) for e e O. a Lemma 3. In the game theoretic context, for any 3N k k l k Y ( ) = Z Y ( 3) . GN H GNI _QEO * * Proof. For 5 6 S N * S X ... E 0319a ( o-k+1’ ,X~_1) N “C = 293MB ”.9 )=2 2 9329 0’: Cl’ ’Y‘k'I'l, , (1‘1 EOk-l a (e — 0’ <1 6) a ‘ “ oz-k+1’ ° ° ' ,ed‘1)—'9' l: * k * = 2k 1 z 901‘ s (a) = 2k 1(GNI-Q>S (9) ~ A ‘ _ I as ' EEO I a 3 (ea-k+1""’ea-1)Ifi / 320 a - But (16) is minimal if s (3) = 0(G:Ig) for each §_E EN 1, Hence k k k k l k ‘1’(G)= z (GNI3)0(GIB)= 2: Y(GI_Q).. N k-l N k-l N EEO EEO The lemma suggests that given a strategy achieving the un- extended (k = l) envelope at some rate uniform in 3N, and such that the risk function used at stage 0 depends on E. 1 only a“ through G; , it may be possible to achieve the k-extended envelope 1 at the same rate by at stage a choosing the risk function according to e ) rather than C1 . Two examples of the k Ga-1I(ea-k+1’...’ 0-1 a-l use of this kind of technique follow. 3.3. A_mpdification gitHannan's game theoretic strategy, Hannan (1957) shows that for the case k = l, the risk in- curred in a game theoretic setting by the Specialization of .3 18 defined in (10) with Ha = (§Q)% achieves (17) «‘21 “0%13 E N ’é - Y1(G1) < Nl§(6 )&B 2 3' § ea 0 N —' m ' If we modify Hannan's strategy by replacing G1 1 with a- k 9 0-1 ) and H with H' = (6W6 (1‘1 0’ a ‘ Gk ( % a-1‘ 9a_k+1,.. . , Heal-16'1“” ,ea_1)\\1/m) k = 'Z r we have Sa 0(Ga_1\(ea_k+1,. .,ea_1) +‘Ha ). Then N k k 2 e S - ‘i’ (GN) a=1 a a l k = Zk1{ Z eaSa'Y(GN\fi)} . fleg - CY 3 (ea_k+_1"'°’ea_1)—& Denote the term in brackets by A(§D for each 3_E Gk-l, and the ' d‘ ' ... = ... 1n ices a for Wthh (ea-k+1’ ,%1_1) g. by a1 < 02 < < aN(E) where N(_Q) = HGS‘QHI. NE) A(g)=£ i: - $2, ‘ k E e 0ka _1\a+ (41—2-6 1) z - 3:1me . =1 an ' a. m ' J J \ J 1, The sequence {Gk ‘3} is a sequence of non-normalized a. J empirical distributions on @, with Gk \§.= e +Gk ‘fi 0. a ' a J 33 0-1) and Harman's result is applicable. 80 «15(9) ('2' m)%B g A(9) 3 N%(B)(6m)!i3. Noting that 2 N(3) = N, an application of the Schwarz E inequality yields 153 kkB N kk % k; (18) -N('2-m) gazes -\¥(G)_<_N(6m)2B, a=1 a a N uniform in 3N. Comparison of (17) and (18) shows the rate of convergence for the risk of the modified procedure to the extended envelope is the same as that for the original strategy. Indeed the bounds are m(k"1)/2 times the original bounds. 19 3.4. Q_modification of Blackwell's game theoretic strategy. Hannan (1957) states that an unextended game theoretic strategy proposed by Blackwell (1956) achieves risk Y1(G;) + 0(N%). We intro- duce this strategy and show that a natural modification achieves risk Yk(G§) + 0mg). For each a 2 l we let ¢ denote the m + 1 vector 0 a (8 ,9 S ) and ® =‘l Z a = (e ,r ). With A the convex subset a a a a 0 =1 '3 a Q [n+1 B of R defined by A = {(W,U) E R 11w : Rm corresponds to a probability on 1 ® and u g Y (w)], we let pa be the Euclidean distance of Ed from A. Arbitrarily set = O. For each m dimensional probability vector w let 00 y(w) = (w, Y1(w)) and let wa be the probability vector minimizing H% .2 H- 2 - 1 2 a - v(w)H = neg ' w“ + (rd ' Y (w)) Blackwell's strategy g is defined inductively, (19) g = 'any 8 E S which minimizes a . _ - 1 , - + - , f O. ieZ® (e(ea_1 WG—1) es(ro__1 Y (w0_1)) 1 pa_1 # A proof of the following proposition is contained in the appendix. Proposition. If S is convex, then N v 1 1r 2 2 s 2 e s - Y (cl) 3 N2((2 + B )(1 + mB ))2 a=1 a a N uniform in EN. 20 The convexity assumption on S appears in order to allow an applica- tion of the Minimax Theorem in the proof. Abbreviate “Gk\fifl as n (39 for 3.6 k-l. With a '1 0’ -k l <15 ‘ ((9 e >) 2 $8 a n - ,..., = a ak+2 a a B (es-k+1,...,ee_1) (ea.k+2,...,ea) 4k -k = (9 ) r )a a a where we interpret %-= 0, let pk be the Euclidean diStance of 6k 0’ 0’ from A and Q: be the m dimensional probability vector minimizing ¢ - y(w)H:. We consider a procedure ‘5 defined by 0’ i any 3 E S, if p:_1 - O (20) s = 1 any 5 6 S which minimizes a = l ’ - -k k . k : v (9(6k —wk )+es(r -~y1(w )). 1f 9 #0. : a-l 0'1 a-l a-l a-l \GECH) As before, N k k 1 k “ (21) zes-Y(G)=z f2: gas-Ham». 10’0 N E®k‘1 a ( 9 )= a0! N I, (1’: _ a ea_k+1”"3 a_1 _Q Denoting the term in brackets by A(§) for each 3.6 Ck-l, and the indices 0 for which (9 a with N(E) = nN(E), ,..., = b ... ea ) E. y al < a2 < < aN 4¢+1 -1 Me) 1 Nu) A(§) = z e s - Y ( 2 e > . . . . . a. J=1 0[J 0’J J=1 J With this notation ;k = —l—'J£1 ’k is the Euclidean L=1 at J 21 j-l distance from A to 72.. 2 ® , and wk is the m dimensional J-l _ a a.-1 ‘ 2 probability vector which minimizes “-l- 2 ¢ - y(w)“ So that comparing (19) and (20) and applying the proposition we see that if L S is convex A(3) s;N%(§)((2 + BZ)(1 + mB2))2. So applying the % mac-1) /2 55 Schwarz inequality the lhs (21) s N ((2 +-BZ)(1 +-mBZ)) , and the modification of Blackwell's strategy provides another solu- tion of the k-extended game theoretic problem. 3.5. A_comment 92 the effect gf_play against a_random perturbation _§_ Gk 1 ig_the k-extended setting. a- Recall the k-extended procedure suggested in §2.2 had the form A * ~ = + , , . . . , (10) s s (Tork HTkz (Xa_k+1 X014» The proof of Theorem 1 depends heavily on the fact that Ta-k + Hasz is independent of (xa-k+l of the P9 in the game theoretic situation, it is possible to replace ,...,Xa). However, because of the degeneracy fa‘kl+ Ha4kz by 50-1 + Ha-lz’ invoke unextended results for a sequence compound problem with Pk construct as the component problem, and improve on the bound of Theorem 1. That is, redefine s by * .... g = + Z , . . ., . C! S (Ta-l Ha-l , (Xa-k-i'l XQI-l)) ~ — * c“ + H z )) Then almost everywhere a, sa — S ( a-l a-l , (ea_k+1,.-.,ea_1 so that N N N 22 = ..., ~ + . . ( ) 2 E9 8 Z “(90;k+1a ea)o(Ga_l Ha-lz) a=1 a a 0:1 22 The unextended version of Theorem 1 applied to a compound problem With Tk component implies that (22) is bounded above by YR Gk) + l'BH mk + B l + 2 2 1‘9 0:1 a 52’ 'k/2 . . I In fact, with the choice H = (6a) m application of Hannan s a reSult quoted in §3.3 gives the bounds of (18) for (22). L 4. THE UNEXTENDED STATISTICAL PROBLEM, O(N2) CONVERGENCE TO Y1(G;) OF THE RISK OF THE NATURAL PROCEDURE IN THE TWO STATE CASE Artificial randomization plays a major role in the solutions of the k-extended sequence compound problem offered in §2. In that section it was shown that under mild aSSumptions on 65 a procedure which at stage a uses an element of 3* corresponding to a risk point Pk Bayes versus an estimate of GZ-k plus randomization is an asymptotic solution to the k-extended problem. It is not possible to retain the generality of §l, delete the randomization and prove a result parallel to Theorem 1. Even in the unextended case there are trivial game theoretic examples in which the non-randomized version of Theorem 1 fails. Gilliland and Hannan (1969b) and Helmers (1972) give smooth- ness conditions on a that allow deletion of the randomization in some unextended game theoretic cases. Van Ryzin (1966b) shows that under some non-degeneracy conditions on the P6, in the unextended finite state finite act decision theoretic setting, neither the smoothness of 0 nor the randomization is needed to obtain a result like Theorem 1. Ballard (1974) generalizes some of Van Ryzin's finite state finite act treatment to the k-extended level. In this section we consider the unextended finite state restricted risk component statistical problem. Under non-degeneracy conditions similar to Van Ryzin's we apply a result of Bhattacharya (1970) - MirahuedOV'(1974) and show that neither randomization nor 23 24 the smoothness of o are necessary in a two state problem. 4.1. Specializations for the unextended statistical problem, aSSumptions Qg_the P6, the natural procedure a. We continue under the k = 1 version of the assumptions con- tained in §l.l through §l.4, but will alter the aSSumptions on the Pe contained in §1.5. Throughout §4 we will suppose that t is an Rm valued, 3 measurable map with the prOperties that (23) jthe = a each 9 E @ and (24) 1 y < m such that 5‘90(t - e)\3dP < v for each 9,90 6 ®. 6 In addition to (23) and (24), we will impose one or the other of the following two sets of conditions on t and .9. (25) For each 9 6 ® the m X m matrix V9 = §(t-6)(t-e)'dPe is nonsingular. (26) E at = l and for each 9 6 O the m X m matrix 9 ya = j‘(t-e)(t-9)'dPe is of rank m-l. a a I Abbreviate t(X ) t0 t , Z t to T and —' Z V a a a a a _1 E 3:1 5’ B to Va. Ova is the covariance matrix of Ta. To obtain some of the elementary properties of V we digress slightly to consider matrices a which like V are averages of nonnegative definite matrices. 0 Suppose tl’°°"tn are nonnegative definite m X m matrices with common range £3 and fl_= (fi1,...,fin) iS a probability vector in 25 n n R (that is, each n, 2 0 and 2 fl. = 1). Let x denote the average 2 (niti). fin is nonnegative definite and has range N3 i=1 With 0 5 “Ii 3 n21 s...s “mi the eigenvalues of ti, let = .=1,ooo, , . =1,ooo, d ..>0 d n. A{nji\3 m i n an “13 1 an n = Vinmi‘i = 1,...,n]. The minimum positive eigenvalue of fin is then greater than or equal to I} and the largest eigenvalue of in is less than or equal to E. In the case that each ti is non- singular, the eigenvalues of t;1 are between n and 3:1. Throughout §4 we will let ‘L denote A{K\K > O is an eigenvalue of V6 for some 6 E @} and I denote Vik‘k is an eigenvalue of V6 for some 9 E ®]. The last two comments above then apply with V; replacing in and L_ and X' replacing fl, and a; The sequence compound procedure that we investigate in this section is §>= (Sl’°'°’SN) where for each a (27) 50 = o(Ta_ ) l The compound risk of g. is N N (28) 2298 =2Ets 10:01 1 00’ N N = E E t s + E t s - s . lacr’rl $050. oz+l) Denoting second term on the right above as A, Lemma 1 implies N E s S E T o T ) + A § ed a N ( N 1 1 s Y (GN) + A . 26 The goal of §4 is to give useful bounds for A. After brief considera- tion of the problem for general finite m, we will Specialize to the case m = 2 and show that under (25) or (26), where S is the lower boundary of a convex Subset of [0,B]2, there exists a constant X' 1/ depending only on B, {V9} and y Such that A s X'Nz. EE® 4.2. Bounds 92_ A, for general finite m, N Recall that A = E 2 t (oCT a a a=1 problem of bounding a typical summand 1) - cCIa)) and consider the (29) E twee"; - 0(T )). 0+1 Iterating expectations, (30) (29) = Emwwua) - oawmtw], ))‘ s E\E[ta+1(c(Ta) - o( ‘ta+1 my” 1“. Let 'Wa be independent of ta+1 with a normal distribution with the same mean and covariance structure as T , that is normal (G ,aV ). a a a Abbreviate t to t and E[ \t ] to Et through (38). Then, 0+1 0+1 W T W (31) rhs(30) s E‘Etto]wa+t\_ + E‘Ett(o]Ta+t - °]wa+t)\ . at a 0’ Denote the first term on the right above as Ca and the second as 6a and bound them separately. First consider Ca. Let v be normal (Cl,aVé) meaSure and a 1 v2 be normal (G1 + t,dv ) meaSure. CY (1’ 27 w (32) \Ettojw:+t\ = ijto d(v1 - v2)\ . Since “tHIB is a bound for \to\, if we let \vl - v2\(Rm) stand for the total variation of the signed measure v1 - v2 rhs(32) s BHtW1\v1 - v2\(Rm). Under (25) the q = l Specialization of Lemma Al in the Sppendix and the fact that the eigenvalues of d? are greater than or equal to a GA, Show that t % 2 - \vl - mm“) s <;;> Mm) . Thus under (25) -i 2 g ‘ (33) C& s a 23(239 EHt“1“tJ . Also, t W t l- W (34) \E talwgit\ = \E £0101 a l = \ftU d(V1 ‘ V2)\ 0! ——(W +t) ar+1 a -l l -l-' . where v is normal (0 G , a V ) measure and v is normal 1 a at 2 ((a+1)-1(C; + t),a(a+l)-2?;) measure. Under (26) the range of ‘7 is the orthogonal complement of the subSpace of Rm generated a -1 - by the vector ‘1 = :9. Since IL'((a+1) (G1 + t) - o 1Gil) = 0, Lemma 0’ Al is applicable with q chosen to be 0(a+l)-1. So 2 (3S) \vl-vzHRm) s 2((m-1>1og hag—+92) 01 + 01 m1): -1 t _1__ Gl\\2)% + — _— 2(202+za+1) n “0+1 d(d+1) a 28 where n is the minimum positive eigenvalue of 0-1? . Then weakening (35) a -1 ‘1 2 2 -l by replacement of n by a L, log 2 (2a + 2a + 1)(a + a) by -1 2 -l , g 2 (a +’q) , and by noting that for a,b > O, (a+b) s (a + 2a%b% + b)% = (3% + b%) , I 2 " 16 " $2 (36) \v1 - vZMR‘") s (4—12‘“ 1 > + 22. a 2 a > ‘lt - lclll - a+a 4a +‘4 0 define or from Rm-1 to S by qr(y) = o(w) for w V die point of Rm such that w'l = r and w = y. Then we may write under (26) 29 T i (39) Eeo1w" = E9001»? (1’ Q and for w 6 Rm with w'l = 1 T +w 0+1 f +& (40) 229.3waer = EEG 1,30% CY CY The advantage of such a reduction of dimension will become apparent in the proof of Lemma 4. . . m l m , For a function g mapping R to R and u 6 R define the function gu by gu(w) = g(u + w). For a set QVCLRm define - , m m(g,q0 = V{\g(w) - g(y)\\w,y 6 a3. With y E R and r 2 O, S(y,r) will denote {w e Rm\“w - y“ < r}. Lemma 4. Let Y have a normal (0,a?;) distribution. There exist 1 2 that under (25) constants K and K depending only on m, B, {V9} and V such T +w % a ‘ - ‘Eeolwafiw‘ S Kla + 2 V Ew(ea, S(Y + u, K2)) m UGR for any w E Rm, and under (26) T -1/ ‘Eeolwa\ S Kla 2 + 2 V 1Ew(eca, S(Y + u, K2)) a uERm and T +w 1 a - 'é d+1 ' \EEOJW +w1 S Kla + 2 Vm_1Ew(90 ,S(Y + u, K2)) a uER for any w E Rm with w'l = 1. Proof. All of the asserted bounds will follow from applications of the weakened form of the Bhattacharya-Mirahmedov Theorem Stated in 3O A.3. Consider first the situation under (25). Direct application of the result shows that with E a m x m nonsingular matrix Such that a E'E = V'l, “Ea“ the operator norm of E , g the function from Rm 0 a l . % -1 l to R defined by g(y) = 90(a Ea y + w + G ), and a = -3/2 3 0 ea C(m)a “Ea“ m55 z E(zie(t - e >\3, T +w E90 or 's . ,Rm + 2 V ‘6‘ ,S 1 Jwaiwl m. . -% m Since “Ed” 3 L , w(g,R ) s B, and (24) implies that a 3 . -% 3/2 8 E(Z\6(tB - 98)‘ ) 3 amy, we may Set 6 = C(m)L. m y and weaken 1 9 the bound to Tafiw’ _ -% imawpsahwnxwemxaam%m. Now '% t '% v jw(gu,sd¢m U U L -1 Where 8:00 = 900121310 y + u). But .} 3' -1 5' U)(gL:aS (X’a 23)) S (MGOJS (02130 X + UzC)’ 6"‘\Q'2E -l 5 -l -l “E H = n2 where n is the largest eigenvalue of (Ed )‘Ea . It a is always the case that for A a m X r matrix and B a r X m matrix, AB and BA have the same nonzero eigenvalues. Hence fl is also the largest eigenvalue of E;1(E-1)' ='V . So under (25) C1 0’ T +w | a ‘ -%B .52, (41) (1590)" ...w‘. S 01 e + 2v Ew(Eo,S(Y + u, 61.))- a U 31 The Bhattacharya- Mirhamedov result is not directly applic- able to the left sides of (39) or (40) under (26), as the V9 are singular. For 2 a m X m matrix, let 20 be the (m-l) X (m-l) matrix obtained from 2 by deleting the mth row and column. V: is then the covariance matrix of the random vector {(X) under the distribution P9. It is the case that under (26) each V2 is non- singular. To see this, suppose that Y has mean 9_ and covariance matrix V9. Y'1_= O a.e. so that the coordinate random variables of Y Span the same (m-l) dimensional subSpace of L2(P) as do the coordinates of Y. Hence the coordinates of Y are linearly independent in L2(P), that is V9 is nonsingular. Thus although the rate of weak convergence result is not directly applicable to lhs (39) or lhs (40),it is directly applicable to the right sides of the equations. And with Do a (m-l) X (m-l) l nonsingular matrix Such that DO 'Da = (VO)- , LP = A{k\k is an a eigenvalue of V2 for some 9 E ®}, i9 = Vikik is an eigenvalue of V2 for some 9 6 ®}, 60 = C(m-l)L9-%(m-1)3/2v, g0 the function from .. L. V Rm 1 to R1 defined by g0(y) = an(a2Da1y + 6;) and ho the function from Rm-1 to R1 defined by h0(y) = edy+l(a%D;1y + é;‘+ W), under (26) T - 0 o -% o \Eeolwa\ s a $5Be +'2 v ljw(gu, S(x,a 23 ))d¢m_1(x), a - _ m uER and for w with w'1= l T +w - 0 -L 0 a \ s a ;5860 + 2 V Iw(h ,S(x,a 2e ))de (X) . \EGOJW +w m-l u m-l uER Then by the same argument as applied under (25), 32 T ,‘ -L 0 v 0 1/ \E901wal 5 oz 236 + 2 v Ew(ec"‘,s 34 and s O and w < (45) g(w) = su for w Such that w2 2 2 Representing points w E R in polar form w = p(cos ¢, sin ¢)', the positive homogeneity of o guarantees that g(w) is independent of p >>O. With A E (-11\) ,-n/2)the angle from the positive 1 axis to the ray L 1 - s - 2 :)(S; - 8%) 1W1} fl (cm,0) , the coordinates of 2 {WER\w2=(S g(w) are monotone in a E (A, A'+ Zfi)- Because of these monotonicities, r 2 . a set a; of the form a? = {w E R \eo(w) > r} must be v01d, all of R or a region bounded by two distinct rays from the origin, possibly though not necessarily including the origin and or one or both of the rays. Also, the monotonicities guarantee that for any r > O, eor(y) is a monotone function of its real argument y. With r r r , r . . . . r . . 0 = (01, 02) , 01 ls nonincreaSing while 02 is nondecreaSing. L 4.4. 0(N2) rates la the two state problem. Theorem 2, Under hypothesis (25), in a situation where m = 2 and S is the lower boundary of a convex Subset of [O,B]2, there exists a real constant Ki depending only on B, {V9} and y such that A s XiNg. Proof. In view of the discussion in §4.2 it suffices to Show that there exists a real constant K3 depending only on B, {V6} and v such that for Y with a normal (Q, dY') distribution, a V Ew(80, S(Y + u, K2)) S K3a-g, where K2 is the constant from uERm Lemma 4. 2 Define functions g and h from R to R1 by g(w) = V{eo(x)‘x E R2 with “x - w“ < K2] and 35 h(w) = A{eo(x)\x E R2 with “x - w“ < K2}. Notice that w(eo, S(w,K2)) = g(w) - h(w). Both g and h are Borel measurable. For example, with r > O and a; = {W E R2\60(W) > r}, {w : R2\g(w) > r] 2 {w e R \S(w,K,> n at ¢ $3, {w e R21Hw - x“ < K 2 for some x 6 gr} 2 _ which is an open set in R . So with v normal (u, an) meaSure (46) Emma, S(Y + u, R,» = jg - h dv. By the Fubini representation of the integrals of the nonnegative functions g and h, rhs(46) =13 v({w‘g(w) > r}) - v({w\h(w) > r})dr . 2 Letting at be as above, and for any ,BC R denoting {w E R2\“w - x“ < e for some x in .D} as '86 and the complement C . of .B as .0 , notice that {w\g(w) > r} = a; and {w\h(w> > r}:: (((af>°>K2>° . So (47) Ew) s )2 v(d;2 - (((a;)C)K )C)dr. 2 r But because a; has one of the forms indicated in §4.3, GR - 2 (((6;)c)K2)C is either void or is a subset of the union of two 36 2 closed infinite strips in R of width 2K2. Lemma A2 then implies 2 that the integrand in (47) is bounded by 2(;—)% .3 the smallest eigenvalue of avg. Hence the integrand is bounded by 41<2(%-)}5(1,)'}50f}5 and (2K2) where ‘3 is NV" ~\"‘ 2} - Eu)(90a S(Y + U, K2)) 5 4BK2(TT)2(D 2 -lv The bound is uniform in u so that with K3 = ABK2(;;%L) 2 the proof is complete. I In the m = 2 case, hypothesis (26) implies that the matrices V and V2 have the forms 1 v2 _v2\ 2 v2 1 1 \ V2 2 vi = v2 v2 and V2 = \ v2 V2 \' 1 1‘ ' 2 2/ for v1 and v2 nonzero real numbers. Note then that with 2 —- v i, v2)', if Y has a normal (9, av ) distribution, Y is a univariate normal (0, v'Gi). v = (v Theorem 2. Under hypothesis (26), in a situation where m = 2 and 2 S is the lower boundary of a convex Subset of [0,3] , there exists a real constant K? depending only on B, {V9} and V such that A s XéNg. Proof. In View of the discussion in §4.2 it Suffices to show that there exists a real constant K depending only on B, {V9} 4 and V such that for Y with a normal (9, a?&) distribution v Emma“, so? + u. R,» < K {’5 uER 4 and 37 V Ew(eoa+1, S(§ + u, K2)) <‘K uER -% 4a where K2 is the constant from Lemma 4. By the monotonicities of CO and oo+l, for y E R Meg“, S>) s (-1>9‘1§eo“d> s <-1>e $900+ d(v1 - v2)- But the right sides above are bounded in absolute value by 1 L -L - B‘v1 - v2\(R1). And Lemma A1 shows that \Vl - v2‘(R ) s 2%" 2“ $5(2K2) v 2 where n is the variance of Y. With v = A{vi, v2) we may then bound v 2 -L -L -L Em(eoa, S(Y + u, K2)) 5 23/ fi 2v sza 2 and l v 3 2 -L - - Ew(eoa+ , S(Y + u, K2)) 5 2 l n 2V nga %. Since the bounds above are uniform in u the proof is complete. I APPENDIX APPENDIX A.1. A bound for the risk of Blackwell's unextended strategy. The following proof referred to in §3.4 derives from a 1957 note of Hannan. Proposition. If S is convex, then N v L 1 z e s - w1(c.1) s 24’2((2 + 32)(1 + 1:132)? 0:1 01 or N uniform in QN. Proof. Note that the concavity of Y1 and the definition of wth imply that 1f 90-1 > O (l) (yiw) - Y O for any w and (2) E -‘¥1(w )>o. 0-1 0.1 We first show that 2 2 2 2 2 + B (3) by s (l - a)pq_l + 02 If = 0 then 2 s \- — Q “2 But - - - = p 1 ’ pa \ma Varl‘ ° ¢a ©9‘1 l 2 - - 2 - 2 a<¢a - ¢ 1) and He - ¢a_1H - Med - 90-,H + (easd - ra_,> $2+B2, so that (3) holds in this case. In the case that p > 0 we a-l 38 39 first observe W2 3 V5 - y(w )WZ. Abbreviating v(w ) to Y bor ha a-l‘ o a’ 2 , - 2 " " " u" - 2 - - ' r' - a i. — (4) pa s H5014 Ya_1\\ + 2(00-1 Va’l)(0a WW1) + M d; 1H - Using the identity 1 - - ai<¢a - y -l) + (fy_l ‘ m _1)) 3* I (gr u 0-1 a on the right hand side of (4) 2- 2‘“ ~2 2" - - 2 s - —- , - , —-n - ., — + w' l (5) pa (1 o)\®a—l \d-IM +Da(‘a-l Ya-IH‘to/ Y01—1) H¢a fia-lx We can show that the cross product term above is non—positive and hence weaken (5) by its omission. To accomplish this, consider a game where I has pure strategies 9 E @, II has pure strategies 3 c S, and the risk R is taken to be R(w,s) = (w,ws)(rba_l _Na-l) V for probability vectors w. s was chosen to minimize a v (9, es)(:}. -v, )=v (w,ws>(5. -\/ ) €63 oz—l 0-]. w 01-]. CY-l Thus (6) v(e,e§>(.- -v)=v(,v)1 - ) BEG) oz 901-1 cy-l w “'st (Va—1 Ya‘l = A V (w,w:~3)(q)m_l “Ya-1) 868 w Applying the Minimax Theorem to the game described above we have -Yl(w )>). rhs(6) =v A (“(901-1 - wwl) + ws 0 case as well as in the pa-1 = 0 case. Iteration of (3) shows that p2 (3)(2)l __ N(N- -l)__2 <8) pV s (2+32)2 +‘fi?fi‘f7‘u > ) N-l N—2 l S<2+B2)(N(N- 1))(N +I—Q:I+"'+ 2) 2 l < (2 + B )N . Consider E — Yl( (I) V II - l 1 1 _ N rN — Y (wN) + Y (wN) ~ Y (SN). 1 1- -- V (wN) - Y (6N) wNo(wN) - eNo(eN) l/\ on<éV> - éNo(éV) So . _ '1 _ _ (9) rN - Y (SN) 3 HeN - w§hngB + (EN - yl(wN)). N'l(2 + 32) the Recalling “6N - wNHZ + (EN -“¥1(wN))2 = p§'< problem of bounding EN - Yl(éN) has been reduced to the problem 41 of bounding the function of two real variables f(u,v) = u + /h Bv 2 2 2 2 % on the ball u + v SépN. For such u and v, f(u,v) s;pN(l + mB ) . Hence __ _ _1/ l l (10) rN — vim“) SN 2(2 + Bzfiu + mBzfi and multiplication of (10) by N completes the proof. I A.2. Two lemmas concerning properties of multivariate normal distributions. The first lemma in this section is used in §4.2 and provides bounds on the total variation of the difference of certain multi- variate normal measures. Lemma Al. Let 2 be a nonnegative definite m x m matrix with range hfi With w and v elements of RI11 such that w—v E a; q >,0, and r = rank 2, let v1 be normal (v,ZD measure on Rm, v2 be normal (w, qZLD measure on Rm, and N be any r X m matrix such that NEN' = Ir’ the r X r identity matrix. Then 1 l 2 L T>+——Tz— )2- q 2(l+q ) \v - v21(Rm) s 2(r log(% + HN(w-v)“ In the case q = l 1-; __ 2(Qgflig%lglg _ i1 UN(W V)fll) , m " 21(R) 2 l Zéfi-%HN(w-v)“ . Vfl Further, if 71 is the minimum positive eigenvalue of Z, _1/ “NW-WEE S T1 2\\w-V\\- Proof. Let Y = (Y .,Ym)' have a normal (932) dis— 1,.. tribution. 42 43 \v - v2\(Rm) 1 2 v (P((Y + v) 6 a0 - P((qY + W) E 60). are” = 2 v (P(Y E GLV) - P(qY + (w-V) E GLV)), afifim \vi - vé‘(Rm), \\' where v' is normal (9,2) measure and v2 is normal (w—v, qzz) 1 measure. So for the rest of the proof we suppose v =‘Q and w 6 $2 Since 2 is of rank r, the subspace of L2(P) spanned by the coordinate random variables of Y is of dimension r. The coordinates of Z = NY form an orthonormal basis for this sub— space. Because each Yi is a linear combination of {2i}:=l the coordinates of Z, there exists a m X r matrix M such that Y = M2. Then Z = NMZ and the uniqueness of representation of elements of a subspace of L2(P) as linear combinations of elements of a basis for that subspace guarantees that NM = Ir' ThUS, since MM' = Z, the range of M is WI While MN is not Im it does act like the identity on RE That is, if h E N; h = MX for some r x E R and MNh = MNMX = Mx = h. 1 Both v1 and v2 concentrate on V, for if x 63"”, both x'Y and x'(qY + w) are 0 a.e.. Thus v1 - v21 = 2 v (v1 - v2> = m e a: — P((qY +w) e a). Also, P(Y e a) = P(NY eNa) and P((qY + w)€ a) = P((qNY + M) 6 N0), the equalities following because MNd= a, w E 1’, and Y E N with probability one. So (v1 — v2)(d) = P(NY t Na — P((qNY + Nw) 61152), and (11) \vl — v2!(Rm) = 2 V (P(NY 6 Nd) - P((qNY + Nw) c Nd). fimflf But as 67 ranges over éfl'r1y; Na’ ranges over 5;. So with ”1 normal (0, Ir) measure on Rr and ”2 normal (Nw, qzlr) measure on Rr l 1 m I' \vl — v21(R ) = rhs(ll) = \”1 - u2\(R ). and we bound \”1 - u2\(Rr)- Letting f be the density of ul with respect to Lebesgue 1 measure on Rr and f2 be the density of ”2, (12) \ul — u2\(Rr) = jifl - f2\dx . It is well known (see for example section 3 0f Hannan (1960)) that L L with p = ff; fgdx, 2 g g 2 (13) (rhs(12)) s 4j(f1 - £2) dx = 8(1-p) s -8 log p. 45 Abbreviating Nw to d, _1/ -I/ p = (det (1211,) “f(ZTr) 2exp -12(¥§(l+1—)x' x - 1—2x' d + ——1—2-d' d)dx, - <12 q 2‘1 - 'd d' = q r/2(§(1+12)) r/zj eXp (X—— 2 — —%3)f (X)dx, q 2q 4q where f3 is the normal (9, (%(l + l§))_llr) density. So q - ' 1 d UM p=<9+ls‘”€mm-3£~+aau+~a)1<——>(~—». 2 2q 2 2 AK1 q 2q2 2q2 - 2 d'd q 4(l+q ) Combining (12) through (14) the first bound holds. Now consider the special case where q = 1. Here f u, - u2\(Rr) = [11 - fiqdir $11 - exp(- 959-+ x'd)\d¢r(x), 1 H2 1d, = 511 - exp<~ “§*-+ Hde>ld2: \dl H = I 2 (l - exp(- ugfl—’+ Hdflz)d®(z) 2 m d‘ ‘ + EHdMeXM‘ JAEL + Whiz) ' 1)d¢(z), 2 l \ I' — 2(¢(u%l) - 2(- L311», and the Special bound for the q = 1 case holds. 46 '1 1 Finally, notice that £§¥h-= *gjfi-. For any a E Rm, “Manz = a'M'Ma 2 Wafizx where X is the minimum eigenvalue of M'M. It is always the case that for A a m X r matrix and B a r X m matrix AB, and BA have the same nonzero eigenvalues, so M'M has the same nonZero eigenvalues as Pm“. Also r 3 rank MN = rank N'M'MN g rank M'M s r. Thus M'M is nonsingular, A = fl, 2 11 1 A§l_§ g l’ and the proof is complete. i‘ “Md“ Tl The second lemma is used in §4.4 to bound the probability of . . . . . 2 . . . an infinite strip in R under a nonSingular bivariate normal meaSure. Lemma A2. Let L be a hyperplane in Rm. For 6 > 0 let L- 6R2“ -‘1 f s ‘-L Lt VERm ba e—{w MW y‘1.<€ or ome yc ]. e ,‘f, e m x m nonnegative definite matrix and v be normal (v,z) measure on Rm. Then v(L) «:- (1271—1121.: where 3' is the smallest eigenvalue of 2. Proof. Let W have a normal (v,2) distribution. Denote by d(w) the distance from a w E Rm to L. Then v(L ) = e P(d(W) < e). Let be a point of L and u be a unit vector y0 orthogonal to L - yo. uu' is then the matrix of orthogonal projection onto the line generated by u. SO d(W) = HUU'(W ‘ YO)H' But Huu'(W - yo)“ = \u'(w - yO)E. Since u'(W - yo) is univariate normal (u'(v - yo), u'Zu), P(‘u'(W - y0)1 < e) is the standard N\"‘ normal probability of some interval of length 23(u'2u)- The stated bound is then a weakening. . 47 A.3. A rate of weak convergence reSult 9£_Bhattacharya-Mirahmedov. Mirahmedov (1974) proves the following improvement of a rate of weak convergence result due to Bhattacharya (1970). Theorem Al. (BhattaCharya-Mirahmedov) Let X ,X ,...,X ,...,X be l 2 k n independent random vectors in Rd with E(X ) = Q_ and _ _ -1 1n . . Dk — Cox(Xk,Xk) . ASSume that Bn — n 21 Dk is non-Singular, -1 _ ' _ “3.2 ,n _ '3/2 ‘11 1 113 and 18C Bn - EnEn, Sn — n Enll Xk’ and L3n - n 215(hEnXkd ). d For any measurable function g(x) on R , set w(g,A) = V{1g(x) - g(y)1 : x,y E A}, and gu(x) = g(x + u). With S(X,r) = {y E Rd1HX-yH < r}, d \fg(y)(Pn(dy) - ©d(dy))\ s C(d)w(g,R )L3n + 2 SUP 311*(guy S(Xa C(d)L3n))Qd(dX) U where Pn is the distribution of S is the d-variate standard n’ éd normal distribution and C(d) is a constant depending only on d. Notice that with “En“ the operator norm of the matrix En’ 3 L S n-3/2 n3 n E(WXRH) , 3n HEN” 2:1 m 5 I; D. M p1 A n V o. :a V so the theorem may be weakened by the replacement of L3n by the last line above. REFERENCES REFERENCES Ballard, Robert John (1974). Extended rules for the sequence com- pound decision problem with m X n component. Doctoral thesis at Michigan State University. Ballard, Robert John, Gilliland, Dennis G. and Hannan, James (1974). 0(N-%) convergence to k-extended Bayes risk in the sequence compound decision problem with m x n component. RM-333, Statistics and Probability, FBU. Bhattacharya, R.N. (1970). Rates of weak convergence for the multi- dimensional central limit theorem. Theory of Probability and its Applications 15 68-86. ~~ Blackwell, D. (1956). Controlled random walks. Proc. Internat. Congress Math. Amsterdam 3 336-338. Brown, L.D. and Purves, R. (1973). MeaSUrable selections of extrema. Ann. Statist. 1 902-912. Cover, Thomas M. and Shenar, Aaron (1974). A compound sequential Bayes predictor for sequences with an empirical Markov structure. TR-ll, Department of Statistics, Stanford University. Gilliland. Dennis C. (1969). Approximation to Bayes risk in sequences of non-finite games. Ann. Math. Statist. 40 467-474. ~~ Gilliland, Dennis C. and Hannan, James F. (1969a). On the extended compound decision problem. Ann. Math. Statist. 40 1536-1541. Gilliland, Dennis C. and Hannan, James F. (1969b). 0n continuity of the Bayes reSponse and play against the paSt in a sequence of decision problems. RM-216, Statistics and Probability, MSU. Gilliland, Dennis C. and Hannan, James F. (1974). The finite state compound decision problem, equivariance and restricted risk components. RM-3l7, Statistics and Probability, MSU. Hannan, James F. (1956). The dynamical statistical decision problem when the component problem involves a finite number, m, of distributions. (Abstract) Ann. Math. Statist. 27 212. 48 49 Hannan, James (1957). Approximation to Bayes risk in repeated play. Contributions E2_the Theory g£_Games 3 97-139. Princeton University Press. Hannan, James F. (1960). Consistency of maximum likelihood estima- tion of discrete distributions. Contributions t9_Probability and Statistics, 249-257. Stanford University Press. Helmers, Merrilee (1972). On the continuity of the Bayes response. RM-305, Statistics and Probability, MSU. Johns, M.V., Jr. (1967). Two-action compound decision problems. Proc. Fifth Berkeley Symp. Math. Statist. Prob. 1 463-478. University of California Press. Mirahmedov, S.A. (1974). The rate of weak convergence in the multi- dimensional limit theorem. Izv. Akad. Nauk UzSSR Ser. Fiz.- Mag, Nauk 18 no. 2, 23-28, 92-93. Robbins, Herbert (1951). Asymptotically subminimax solutions of compound statistical decision problems. Proc. Second Berkeley Symp. Math. Statist. Prob., 131-148. University of California Press. Robbins, Herbert (1964). The empirical Bayes approach to statistical decision problems. Ann. Math. Statist. 35 1-20. ~~ Samuel, Ester (1963). Asymptotic solutions of the sequential com- pound decision problem. Ann. Math. Statist. 34 1079-1094. Samuel, Ester (1965). Sequential compound estimators?” A22, MEED: Statist. 36 879-889. Swain, Donald D. (1965). Bounds and rates of convergence for the extended compound estimation problem in the sequence case. Tech. Report No. 81, Department of Statistics, Stanford UniverSity. Van Ryzin, J.R. (1966a). The compound decision problem with m x n finite loss matrix. Ann. Math. Statist. 37 412-424. ~~ Van Ryzin, J.R. (1966b). The sequential compound decision problem with m X n finite loss matrix. Ann. Math. Statist. 37 954-975. M'11111111111111!1111111111111111111111111ES 77 6663