# Multiple Hypotheses LAO Testing for Many Independent Objects

Authors: Evgueni Haroutunian; Parandzem Hakobyan
Journal: SRX Mathematics
 (2009)

---

## Abstract

The procedure of many hypotheses logarithmically asymptotically optimal (LAO)
testing for a model consisting of three or more independent objects is analyzed. It is supposed thatM probability distributions are known and each object follows one of them independently of others. The matrix of asymptotic interdependencies (reliability-reliability functions) of all possible pairs of the error probability exponents
(reliabilities) in optimal testing for this model is studied. This problem was introduced (and solved for the case of two objects and two given probability distributions) by Ahlswede and Haroutunian; it is a generalization of two
hypotheses LAO testing problem for one object investigated by Hoeffding, Csiszár
and Longo, Tusnády, Longo and Sgarro, Birgé, and others.


---

## Body

## 1. Introduction

In [1–3] Ahlswede and Haroutunian formulated an ensemble of new problems on multiple hypotheses testing for many objects and on identification of hypotheses. These problems are extensions of those investigated in the books mentioned in [4, 5]. Problems of distribution identification and distributions ranking for one object were solved in [2]. Also the problem of hypotheses testing for the model consisting of two independent or two strictly dependent objects (when they cannot admit the same distribution) with two possible hypothetical distributions was investigated in [2]. In this paper we study the specific characteristics of the model consisting of K(≥3) objects which independently of others follow one of given M(≥2) probability distributions. The study concerns certain number K of similar objects (cities, institutions, schools, hospitals, factories, etc.), or one object in a series of K different periods of time. The problem is a generalization of two hypotheses testing investigated in [6–10] and of testing of many hypotheses concerning one object solved in [11]. The case of two independent objects with three hypotheses was examined in advanced edition [12], in a local publication of small circulation.Investigation of testing of the distributions of many uniform objects is an interesting not yet fulfilled task. It is natural to begin this study with the simplest case of statistically independent objects.Let𝒫(𝒳) be the space of all probability distributions (PDs) on finite set 𝒳. There are given M distinct PDs Gm∈𝒫(𝒳), m=1,M¯, which are known as possible distributions of the objects.Let us recall main definitions from [11] for the case of one object. The random variable (RV) X, which is a characteristic of the studied object, takes values on 𝒳 and follows unknown PD G which is one of M given PDs Gm, m=1,M¯. The statistician have to accept one of M hypotheses Hm:G=Gm,m=1,M¯, on the base of a sequence of results x=(x1,…,xn,…,xN), xn∈𝒳, n=1,N¯ of N independent observations of the object. The procedure of the decision making is a nonrandomized test φN, which can be defined by division of the sample space 𝒳N into M disjoint subsets 𝒜lN={x:φN(x)=l}, l=1,M¯. The set 𝒜lN contains all vectors x for which the hypothesis Hl is adopted. The probability αl∣m(φN) of the erroneous acceptance of hypothesis Hl provided that Hm is true is equal to GmN(𝒜lN), l≠m, where GmN(x)=∏n=1NGm(xn). We define the probability to reject Hm, when it is true, as
(1)αm∣m(φN)≜∑l≠mαl∣m(φN).The exponential decrease of the error probabilities asN→∞ is studied. The error probability exponents which is pertinent to call reliabilities, of the sequence of tests φ, are defined as follows:
(2)El∣m(φ)≜limN→∞¯-1Nlogαl∣m(φN),m,l=1,M¯.
From (1) and (2) we see that
(3)Em∣m(φ)=minl≠mEl∣m(φ),m=1,M¯.The matrix(4)E(φ)=(E1∣1⋯El∣1⋯EM∣1⋯⋯⋯⋯⋯E1∣m⋯El∣m⋯EM∣m⋯⋯⋯⋯⋯E1∣M⋯El∣M⋯EM∣M)
we call it the reliability matrix of the sequence φ of tests. It was studied in [11]. The question is values of which number of elements of E(φ) can be given in advance and which optimal values can be guarantied by the best test for the others.The sequence of testsφ* is called logarithmically asymptotically optimal (LAO) if for given positive values of first M-1 diagonal elements of the matrix E(φ*) maximum possible values are provided to all other elements of it. The concept of LAO test was introduced by Birgé [10] and also elaborated in [11, 12].Let us now consider the model with three objects. LetX1, X2, and X3 be independent RVs taking values in the same finite set 𝒳 with one of M PDs, this RVs are the characteristics of the corresponding independent objects. The random vector (X1,X2,X3) assumes values (x1,x2,x3)∈𝒳3.Let(x1,x2,x3)≜((x11,x12,x13),…,(xn1,xn2,xn3),…, (xN1,xN2,xN3)), xnk∈𝒳,k=1,3¯,n=1,N¯, be a sequence of results of N independent observations of the vector (X1,X2,X3). The test have to determine unknown PDs of the objects on the base of observed data. The selection for each object should be made from the same set of hypotheses: Hm:G=Gm, m=1,M¯. We call this procedure the compound test for three objects and denote it by ΦN, it can be composed of three individual tests φN1, φN2, φN3 for each of three objects. We denote the infinite sequence of compound tests by Φ. When we have K independent objects the test Φ is composed of tests φ1,φ2,…,φK.Letαl1,l2,l3∣m1,m2,m3(ΦN) be the probability of the erroneous acceptance of the hypotheses triple (Hl1,Hl2,Hl3) by the test ΦN provided that the triple of hypotheses (Hm1,Hm2,Hm3) is true, where (m1,m2,m3)≠(l1,l2,l3), mi,li=1,M¯, i=1,3¯. The probability to reject a true triple of hypotheses (Hm1,Hm2,Hm3) by analogy with (1) is the following:
(5)αm1,m2,m3∣m1,m2,m3(ΦN)=∑(l1,l2,l3)≠(m1,m2,m3)αl1,l2,l3∣m1,m2,m3(ΦN).We study corresponding reliabilitiesEl1,l2,l3∣m1,m2,m3(Φ) of the sequence of tests Φ(6)El1,l2,l3∣m1,m2,m3(Φ)≜limN→∞¯-1Nlogαl1,l2,l3∣m1,m2,m3(ΦN),mi,li=1,M¯,i=1,3¯.Definitions (5) and (6) imply (cf. (3)) that
(7)Em1,m2,m3∣m1,m2,m3(Φ)=min(l1,l2,l3)≠(m1,m2,m3)El1,l2,l3∣m1,m2,m3(Φ).We call the test sequenceΦ* LAO for the model with K objects if for given positive values of certain part of elements of the reliability matrix E(Φ*) the procedure provides maximal values for all other elements of it.Our aim is to analyze the reliability matrixE(Φ*)={El1,l2,l3∣m1,m2,m3(Φ*)} of LAO tests for three objects.We consider the problem for three objects for brevity; the generalization of the problem forK independent objects will be discussed hereafter along the text and in Section 4, but before that we recall the results for one object. The generalization of the problem for cases when RVs Xi take values in different sets 𝒳i and have hypothetical PDs Gmi, m=1,M¯, i=1,3¯, will be only more complicated in notations.


## 2. LAO Testing of Many Hypotheses for One Object

We define the divergence (Kullback-Leibler distance)D(Q||G) for PDs Q and G from 𝒫(𝒳) as usual:
(8)D(Q||G)=∑xQ(x)logQ(x)G(x),For given positive diagonal elementsE1∣1,E2∣2,…,EM-1∣M-1 of the reliability matrix we consider sets of PDs
(9)ℛl≜{Q:D(Q||Gl)≤El∣l},l=1,M-1¯,ℛM≜{Q:D(Q||Gl)>El∣l,l=1,M-1¯},
and the following values for elements of the future reliability matrix of the LAO tests sequence:
(10)El∣l*=El∣l*(El∣l)≜El∣l,l=M-1¯,(11)El∣m*=El∣m*(El∣l)≜infQ∈ℛlD(Q||Gm),m=1,M¯,m≠l,l=1,M-1¯,(12)EM∣m*=EM∣m*(E1∣1,…,EM-1∣M-1)≜infQ∈ℛMD(Q||Gm),m=1,M-1¯,(13)EM∣M*=EM∣M*(E1∣1,…,EM-1∣M-1)≜minl=1,M-1¯EM∣l*.We recall the theorem concerning one object.Theorem 1 ([11]).
If the distributionsGm are different, that is, all divergences  D(Gl||Gm),  l≠m,  l,m=1,M¯, are strictly positive, then two statements hold:
(a)when the given numbersE1∣1,E2∣2,…,EM-1∣M-1 satisfy the conditions
(14)0<E1∣1<minl=2,M¯D(Gl||G1),(15)0<Em∣m<min[minl=1,m-1¯El∣m*(El∣l),minl=m+1,M¯D(Gl||Gm)],m=2,M-1¯,
then there exists an LAO sequence of tests φ*, the elements of the reliability matrix of which E(φ*)={El∣m*} are defined in (10)–(13) and all of them are strictly positive;
(b) even if one of the conditions (14) or (15) is violated, then the reliability matrix of any such test includes at least one element equal to zero.Corollary 1.
The diagonal elements of the reliability matrix of the LAO test in each row are equal only to the element in the same row and in the last column:(16)Em∣m*=EM∣m*,Em∣m*<El∣m*,l=1,M-1¯,l≠m,m=1,M¯.
That is, the elements of the last column are equal to the diagonal elements of the same row and due to (3) are minimal in this row. Consequently first M-1 elements of the last column also can be considered as given parameters for construction of the LAO test.Proof.
Form=M (16) is the sequence of (3). From the conditions (14) and (15) we see that Em∣m*<El∣m*(El∣l*), m=2,M-1¯, l=1,m-1¯, hence Em∣m* can be equal only to one El∣m*, for l=m+1,M¯. Assume that (16) is not true, that is, Em∣m*=El′∣m*, for one l′∈[m+1,M-1].
Applying Kuhn-Tucker theorem for (11) we can derive (the proof is not difficult, but long, so we avoid the exposition) that the elements El∣l*, l=1,M-1¯ may be determined by elements El∣m*, m≠l, m=1,M¯, with the following inverse functions:
(17)El∣l*(El∣m*)=infQ:D(Q||Gm)≤El∣m*D(Q||Gl),l=1,M-1¯.
Then it follows from (11) and our provisional supposition that
(18)El′∣l′*(El′∣m*)=infQ:D(Q||Gm)≤El′∣m*D(Q||Gl′)=infQ:D(Q||Gm)≤Em∣m*D(Q||Gl′)=Em∣l′*,m=1,l′-1¯,
but one can see from conditions (14) and (15) that El′∣l′*<Em∣l′* for m=1,l′-1¯. Our assumption is not correct, hence (16) is valid and equality (3) implies Em∣m*=EM∣m*.


## 3. LAO Testing of Hypotheses for Three Independent Objects

Now let us consider the model of three independent objects andM hypotheses. It was noted that the compound test ΦN may be composed from separate tests φN1, φN2, φN3. Let us denote by E(φi) the reliability matrices of the sequences of tests φi, i=1,3¯, for each of the objects. The following lemma is a generalization of lemmas from [2, 12].Lemma 1.
If the elementsEl∣m(φi),  m,l=1,M¯,  i=1,3¯, are strictly positive, then the following equalities hold for  Φ=(φ1,φ2,φ3):
(19)El1,l2,l3∣m1,m2,m3(Φ)=∑i=13Eli∣mi(φi),li,mi=1,M¯,mi≠li,i=1,3¯,(20)El1,l2,l3∣m1,m2,m3(Φ)=∑i∈[[1,2,3]-k]Eli∣mi(φi),mk=lk,mi≠li,i≠k,k=1,3¯,(21)El1,l2,l3∣m1,m2,m3(Φ)=Eli∣mi(φi),mk=lk,mi≠li,i=1,3¯,k∈[[1,2,3]-i].
Equalities (19) are valid also if Eli∣mi(φi)=0 for several pairs (mi,li) and several i’s.Proof.
It follows from the independence of the objects that(22)αl1,l2,l3∣m1,m2,m3(ΦN)=∏i=13αli∣mi(φNi),ifmi≠li,αl1,l2,l3∣m1,m2,m3(ΦN)=(1-αlk∣mk(φNk))×∏i∈[[1,2,3]-k]αli∣mi(φNi),mk=lk,mi≠li,k=1,3¯,i≠k,αl1,l2,l3∣m1,m2,m3(ΦN)=αli∣mi(φNi)∏k∈[[1,2,3]-i]×(1-αlk∣mk(φNi)),mk=lk,mi≠li,i=1,3¯.
Remark that here we consider also the probabilities of right (not erroneous) decisions. BecauseEl∣m(φi) are strictly positive then the error probability αl∣m(φNi) tends to zero, when N→∞. According to this fact we have
(23)limN→∞¯-1Nlog(1-αl∣m(φNi))=limN→∞¯αl∣m(φNi)Nlog(1-αl∣m(φNi))-αl∣m(φNi)=0.
From definitions (5) and (6), equalities (22), and applying (23), we   obtain   relations (19)–(21).
Now we will show how we can erect the LAO test from the set of compound tests when3(M-1) strictly positive elements of the last column of the reliability matrix EM,M,M∣m,M,M, EM,M,M∣M,m,M and EM,M,M∣M,M,m, m=1,M-1¯, are preliminarily given.
The following subset of tests:
(24)𝒟={Φ:Em∣m(φi)>0,m=1,M¯,i=1,3¯}
is  distinguished   by  the  property  that   when   Φ∈𝒟   the   elements  EM,M,M∣m,M,M(Φ), EM,M,M∣M,m,M(Φ), and EM,M,M∣M,M,m(Φ), m=1,M-1¯, of the reliability matrix are strictly positive.
Really, becauseEm∣m(φi)>0, then in view of (3) EM∣m(φi) are also strictly positive. From equalities (23) keeping in mind (6), (16), and (22) we obtain that the noted elements are strictly positive for Φ∈𝒟 and
(25)EM,M,M∣m,M,M(Φ)=EM∣m(φ1),EM,M,M∣M,m,M(Φ)=EM∣m(φ2),EM,M,M∣M,M,m(Φ)=EM∣m(φ3),m=1,M-1¯.
Define the following family of decision sets of PDs for given positive elements EM,M,M∣m,M,M, EM,M,M∣M,m,M, and EM,M,M∣M,M,m, m=1,M-1¯:
(26)ℛm(i)≜{Q:D(Q||Gm)≤EM,M,M∣m1,m2,m3,mi=m,mj=M,i≠j,j=1,3¯},m=1,M-1¯,i=1,3¯,ℛM(i)≜{Q:D(Q||Gm)>EM,M,M∣m1,m2,m3,mi=m,mj=M,i≠j,j=1,3¯},m=1,M-1¯,i=1,3¯.
Define also the values of the reliability matrix of the LAO test for three objects:
(27)EM,M,M∣m,M,M*≜EM,M,M∣m,M,M,EM,M,M∣M,m,M*≜EM,M,M∣M,m,M,(28)EM,M,M∣M,M,m*≜EM,M,M∣M,M,m,El1,l2,l3∣m1,m2,m3*≜infQ∈Rli(i)D(Q||Gmi),mk=lk,mi≠li,i≠k,i=1,3¯,k∈[[1,2,3]-i],(29)Em1,m2,m3∣l1,l2,m3*≜∑i≠kinfQ∈Rli(i)D(Q||Gmi),mk=lk,mi≠li,k=1,3¯,i∈[[1,2,3]-k],(30)El1,l2,l3∣m1,m2,m3*≜El1,m2,m3∣m1,m2,m3*+Em1,l2,m3∣m1,m2,m3*+Em1,m2,l3∣m1,m2,m3*,mi≠li.The following theorem is the main result of the present paper. It is a generalization and improvement of the corresponding theorem proved in [2] for the cases K=2,  M=2.Theorem 2.
If all distributionsGm,  m=1,M¯, are different, (and equivalently  D(Gl||Gm)>0,  l≠m,  l,m=1,M¯), then the following statements are valid:
(a) when given strictly positive elementsEM,M,M∣m,M,M, EM,M,M∣M,m,M, and EM,M,M∣M,M,m, m=1,M-1¯, meet the following conditions:
(31)max(EM,M,M∣1,M,M,EM,M,M∣M,1,M,EM,M,M∣M,M,1)<minl=2,M¯D(Gl||G1),(32)EM,M,M∣m,M,M<min[minl=1,m-1¯El,m,m∣m,m,m*,minl=m+1,M¯D(Gl||Gm)],m=2,M-1¯,(33)EM,M,M∣M,m,M<min[minl=1,m-1¯Em,l,m∣m,m,m*,minl=m+1,M¯D(Gl||Gm)],m=2,M-1¯,(34)EM,M,M∣M,M,m<min[minl=1,m-1¯Em,m,l∣m,m,m*,minl=m+1,M¯D(Gl||Gm)],m=2,M-1¯,
then there exists an LAO test sequence Φ*∈𝒟, the reliability matrix of which E(Φ*)={El1,l2,l3∣m1,m2,m3(Φ*)} is defined in (27)–(30) and all elements of it are positive,
(b) when even one of the inequalities (31)–(34) is violated, then there exists at least one element of the matrix E(Φ*) equal to 0.Proof.
The testΦ*=(φ1,*,φ2,*,φ3,*), where φi,*, i=1,3¯, are LAO tests of objects Xi, belongs to the set 𝒟. Our aim is to prove that such Φ* is a compound LAO test. Conditions (31)–(34) imply that inequalities analogous to (14) and (15) hold simultaneously for the tests for three separate objects.
Let     the   testΦ∈𝒟 be such that
(35)EM,M,M∣m,M,M(Φ)=EM,M,M∣m,M,M,EM,M,M∣M,m,M(Φ)=EM,M,M∣M,m,M,EM,M,M∣m,M,M(Φ)=EM,M,M∣M,M,m,m=1,M-1¯.
Taking into account (25) and (28) we can see that conditions (31)–(34) may be replaced by the following inequalities:
(36)EM∣m(φi)<min[minl=1,m-1¯infQ:D(Q||Gm)≤EM∣m(φi)D(Q||Gl),minl=m+1,M¯D(Gl||Gm)],m=1,M-1¯.
According to Corollary1 in case of LAO test φi,*, i=1,3¯, we obtain that (36) meets conditions (14)-(15) of Theorem 1. For each test Φ∈𝒟, Em∣m(φi)>0, i=1,3¯, hence it follows from (3) that Em∣l(φi) are also strictly positive. Thus for a test Φ∈𝒟 conditions of Lemma 1 are fulfilled and the elements of the reliability matrix E(Φ) coincide with elements of matrix E(φi), i=1,3¯, or sums of them (see (19)–(21)). Then from definition of LAO test it follows that El∣m(φi)≤El∣m(φi,*), then El1,l2,l3∣m1,m2,m3(Φ)≤El1,l2,l3∣m1,m2,m3(Φ*). Consequently Φ* is an LAO test and El1,l2,l3∣m1,m2,m3(Φ*) verify (27)–(30).
(b) When even one of the inequalities (31)–(34) is violated, then at least one of inequalities (36) is violated. Then from Theorem 1 one of elements Em∣l(φi,*) is equal to zero. Suppose E3∣2(φ1,*)=0, then the elements E3,m,l∣2,m,l(Φ*)=E3∣2(φ1,*)=0.
Theorem2 is proved.


## 4. On the Case ofK(>3) Objects

When we consider the model withK independent objects the generalization of Lemma 1 will take the following form.Lemma 2.
If elementsEli∣mi(φi),  m,l=1,M¯,  i=1,K¯, are strictly positive, then the following equalities hold for Φ=(φ1,φ2,…,φK):
(37)El1,l2,…,lK∣m1,m2,…,mK(Φ)=∑i=1KEli∣mi(φi),ifmi≠li,i=1,K¯,El1,l2,…,lK∣m1,m2,…,mK(Φ)=∑iEli∣mi(φi),ifmj=lj,mi≠li,i,j=1,K¯,i≠j.For givenK(M-1) strictly positive elements EM,M,…,M∣m,M,…,M, EM,M,…,M∣M,m,…,M,…, EM,…,M,M,∣M,M…,m, m=1,M-1¯, for K independent objects we can find the LAO test Φ* in a way similar to case of three independent objects. So the problem of many hypotheses testing for the model with K independent objects can be solved by corresponding sets ℛm(i),i=1,K¯,m=1,M¯, as in (27)–(30) and conditions analogous to (31)–(34).


## 5. Example

Some illustrations of exposed results are in examples concerning two objects. The set𝒳={0,1} contains two elements and the following PDs are given on 𝒳: G1={0,10;0,90}, G2={0,85;0,15}, G3={0,23;0,77}. As it follows from relations (28)–(30) of Lemma 2, several elements of the reliability matrix are functions of one of given elements, there are also elements which are functions of two or three given elements. For example, for a case of two objects in Figures 1 and 2 the results of calculations of functions E1,2∣2,1(E3,3∣1,3,E3,3∣3,2) and E1,2∣2,2(E3,3∣1,3) are presented. For    these    distributions    we    have min(D(G2||G1),D(G3||G1))≈2,2 and min(E2,2∣2,1,D(G3||G2))≈1,4. We see that when the inequalities (32) or (33) are violated, then E1,2∣2,1=0 and E1,2∣2,2=0.Figure 1Figure 2


## 6. Conclusion

We exposed a solution of multiple hypothesis LAO testing problem for many objects. The first idea may be to study matrixE(Φ) by renumbering K-vectors of PDs from 1 to MK as PDs of one complex object. We can give MK-1 diagonal elements of such matrix E(Φ) and apply Theorem 1 concerning one object. In this case the number of the preliminarily given elements of the matrix E(Φ) would be greater (because MK-1>K(M-1), M≥2,K≥2), and the procedure of calculations would be longer than in our algorithm presented in Section 3.Proposed approach to the problem gives also the possibility to define the LAO tests for each of the separate objects. It must be noted that the approach with renumbering of the triples of hypotheses does not have this opportunity.In applications one of two approaches may be used in conformity with preferences of the investigator.



---

*Source: 921574-2009-09-17.xml*