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 that M 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.

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 G_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 G_m,

. The statistician have to accept one of M hypotheses

, on the base of a sequence of results x = (x₁, …, x_n, …, x_N), x_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

. The set

contains all vectors x for which the hypothesis H_l is adopted. The probability α_l∣m(φ_N) of the erroneous acceptance of hypothesis H_l provided that H_m is true is equal to

, l ≠ m, where

We define the probability to reject H_m, when it is true, as

()

The exponential decrease of the error probabilities as N → ∞ is studied. The error probability exponents which is pertinent to call reliabilities, of the sequence of tests φ, are defined as follows:

()

From (1) and (2) we see that

()

The matrix

()

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. Let X₁, X₂, and X₃ 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 (X₁, X₂, X₃) assumes values (x¹, x², x³) ∈ 𝒳³.

Let , , be a sequence of results of N independent observations of the vector (X₁, X₂, X₃). 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: H_m : G = G_m, . We call this procedure the compound test for three objects and denote it by Φ_N, it can be composed of three individual tests , , 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 φ¹, φ², …, φ^K.

Let

be the probability of the erroneous acceptance of the hypotheses triple

by the test Φ_N provided that the triple of hypotheses

is true, where (m₁, m₂, m₃)≠(l₁, l₂, l₃),

. The probability to reject a true triple of hypotheses

by analogy with (1) is the following:

()

We study corresponding reliabilities

of the sequence of tests Φ

()

Definitions (5) and (6) imply (cf. (3)) that

()

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 matrix of LAO tests for three objects.

We consider the problem for three objects for brevity; the generalization of the problem for K 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 X_i take values in different sets 𝒳_i and have hypothetical PDs , , , 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:

()

For given positive diagonal elements E_1∣1, E_2∣2, …, E_{M−1∣M−1} of the reliability matrix we consider sets of PDs

()

and the following values for elements of the future reliability matrix of the LAO tests sequence:

()

We recall the theorem concerning one object.

Theorem 1 ([11]). If the distributions G_m are different, that is, all divergences D(G_l| |G_m), l ≠ m, , are strictly positive, then two statements hold:

(a)when the given numbers E_1∣1, E_2∣2, …, E_{M−1∣M−1} satisfy the conditions

()

then there exists an LAO sequence of tests φ^*, the elements of the reliability matrix of which

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:

()

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. For m = M (16) is the sequence of (3). From the conditions (14) and (15) we see that , , , hence can be equal only to one , for . Assume that (16) is not true, that is, , 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 , may be determined by elements , m ≠ l, , with the following inverse functions:

()

Then it follows from (11) and our provisional supposition that

()

but one can see from conditions (14) and (15) that

for

. Our assumption is not correct, hence (16) is valid and equality (3) implies

3. LAO Testing of Hypotheses for Three Independent Objects

Now let us consider the model of three independent objects and M hypotheses. It was noted that the compound test Φ_N may be composed from separate tests , , . Let us denote by E(φⁱ) the reliability matrices of the sequences of tests φⁱ, , for each of the objects. The following lemma is a generalization of lemmas from [2, 12].

Lemma 1. If the elements E_l∣m(φⁱ), , are strictly positive, then the following equalities hold for Φ = (φ¹, φ², φ³):

()

Equalities (19) are valid also if for several pairs (m_i, l_i) and several i’s.

Proof. It follows from the independence of the objects that

()

Remark that here we consider also the probabilities of right (not erroneous) decisions. Because E_l∣m(φⁱ) are strictly positive then the error probability tends to zero, when N → ∞. According to this fact we have

()

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 when 3(M − 1) strictly positive elements of the last column of the reliability matrix E_{M,M,M∣m,M,M}, E_{M,M,M∣M,m,M} and E_{M,M,M∣M,M,m}, , are preliminarily given.

The following subset of tests:

()

is distinguished by the property that when Φ ∈ 𝒟 the elements E_{M,M,M∣m,M,M}(Φ), E_{M,M,M∣M,m,M}(Φ), and E_{M,M,M∣M,M,m}(Φ),

, of the reliability matrix are strictly positive.

Really, because E_m∣m(φⁱ) > 0, then in view of (3) E_M∣m(φⁱ) 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

()

Define the following family of decision sets of PDs for given positive elements E_{M,M,M∣m,M,M}, E_{M,M,M∣M,m,M}, and E_{M,M,M∣M,M,m},

()

Define also the values of the reliability matrix of the LAO test for three objects:

()

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 distributions G_m, , are different, (and equivalently D(G_l| |G_m) > 0, l ≠ m, ), then the following statements are valid:

(a) when given strictly positive elements E_{M,M,M∣m,M,M}, E_{M,M,M∣M,m,M}, and E_{M,M,M∣M,M,m}, , meet the following conditions:

()

then there exists an LAO test sequence Φ^* ∈ 𝒟, the reliability matrix of which

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,*, are LAO tests of objects X_i, 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

()

Taking into account (25) and (28) we can see that conditions (31)–(34) may be replaced by the following inequalities:

()

According to Corollary 1 in case of LAO test φ^i,*, , we obtain that (36) meets conditions (14)-(15) of Theorem 1. For each test Φ ∈ 𝒟, E_m∣m(φⁱ) > 0, , hence it follows from (3) that E_m∣l(φⁱ) 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(φⁱ), , or sums of them (see (19)–(21)). Then from definition of LAO test it follows that E_l∣m(φⁱ) ≤ E_l∣m(φ^i,*), then . Consequently Φ^* is an LAO test and 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 E_m∣l(φ^i,*) is equal to zero. Suppose E_3∣2(φ^1,*) = 0, then the elements E_{3,m,l∣2,m,l}(Φ^*) = E_3∣2(φ^1,*) = 0.

Theorem 2 is proved.

4. On the Case of K(> 3) Objects

When we consider the model with K independent objects the generalization of Lemma 1 will take the following form.

Lemma 2. If elements , , are strictly positive, then the following equalities hold for Φ = (φ¹, φ², …, φ^K):

()

For given K(M − 1) strictly positive elements E_{M,M,…,M∣m,M,…,M}, E_{M,M,…,M∣M,m,…,M}, …, E_{M,…,M,M,∣M,M…,m}, , 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 , 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 𝒳: G₁ = {0,10; 0,90}, G₂ = {0,85; 0,15}, G₃ = {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 E_1,2∣2,1(E_3,3∣1,3, E_3,3∣3,2) and E_1,2∣2,2(E_3,3∣1,3) are presented. For these distributions we have min (D(G₂| |G₁), D(G₃| |G₁)) ≈ 2,2 and min (E_2,2∣2,1, D(G₃| |G₂)) ≈ 1,4. We see that when the inequalities (32) or (33) are violated, then E_1,2∣2,1 = 0 and E_1,2∣2,2 = 0.

Description unavailable — **Figure 1**
Open in figure viewer PowerPoint

6. Conclusion

We exposed a solution of multiple hypothesis LAO testing problem for many objects. The first idea may be to study matrix E(Φ) by renumbering K-vectors of PDs from 1 to M^K as PDs of one complex object. We can give M^K − 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 M^K − 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.

References

1 Ahlswede R. F. and Haroutunian E. A., Testing of hypothesis and identification, Electronic Notes in Discrete Mathematics. (2005) 21, 185–189, https://doi.org/10.1016/j.endm.2005.07.020, EID2-s2.0-34247171372.
Google Scholar
2 Ahlswede R. F. and Haroutunian E. A., On logarithmically asymptotically optimal testing of hypotheses and identification, General Theory of Information Transfer and Combinatorics, 2006, 4123, Springer, New York, NY, USA, 462–478, Lecture Notes in Computer Science.
Google Scholar
3 Haroutunian E. A., Reliability in multiple hypotheses testing and identification problems, 198, Proceedings of the NATO-ASI Conference, 2005, Yerevan, Armenia, IOS Press, 189–201, NATO Science Series III: Computer and Systems Sciences.
Google Scholar
4 Bechhofer R. E., Kiefer J., and Sobel M., Sequential Identification and Ranking Procedures, 1968, The University of Chicago Press, Chicago, Ill, USA.
Google Scholar
5 Ahlswede R. F. and Wegener I., Search Problems, 1987, John Wiley & Sons, New York, NY, USA.
Google Scholar
6 Hoeffding W., Asymptotically optimal tests for multinomial distributions, Annals of Mathematical Statistics. (1965) 36, 369–401.
Google Scholar
7 Csiszár I. and Longo G., On the error exponent for source coding and for testing simple statistical hypotheses, Studia Scientiarum Mathematicarum Hungarica. (1971) 6, 181–191.
Google Scholar
8 Tusnády G., On asymptotically optimal tests, Annals of Statistics. (1977) 5, no. 2, 385–393.
Google Scholar
9 Longo G. and Sgarro A., The error exponent for the testing of simple statistical hypotheses, a combinatorial approach, Journal of Combinatories, Informational System Sciences. (1980) 5, no. 1, 58–67.
Google Scholar
10 Birgé L., Vitesses maximals de décroissance des erreurs et tests optimaux associeś, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. (1981) 55, 261–273.
Google Scholar
11 Haroutunian E. A., Logarithmically asymptotically optimal testing of multiple statistical hypothyses, Problems of Control and Information Theory. (1990) 19, no. 5-6, 413–421, EID2-s2.0-0025637429.
Google Scholar
12 Haroutunian E. A. and Hakobyan P. M., On logarithmically asymptotically optimal hypothesis testing of three distributions for pair of independent objects, Mathematical Problems of Computer Science. (2005) 24, 76–81.
Google Scholar

All articles

Multiple Hypotheses LAO Testing for Many Independent Objects

Abstract

1. Introduction

2. LAO Testing of Many Hypotheses for One Object

3. LAO Testing of Hypotheses for Three Independent Objects

4. On the Case of K(> 3) Objects

5. Example

6. Conclusion

References

Figures

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Multiple Hypotheses LAO Testing for Many Independent Objects

Abstract

1. Introduction

2. LAO Testing of Many Hypotheses for One Object

3. LAO Testing of Hypotheses for Three Independent Objects

4. On the Case of K(> 3) Objects

5. Example

6. Conclusion

References

Figures

References

Related

Information