OnLogarithm15.DVI


Mathematical Problems of Computer Science 24, 2005, 16{33.

On Statistical H ypotheses Optimal T esting and

I denti¯cation

R u d o lf A h ls we d e a n d E vg u e n i A . H a r o u t u n ia n

UniversitÄat Bielefeld, FacultÄat fÄur Mathematik, Postfach 100131 33501 Bielefeld, Germany,
Institute for Informatics and Automation Problems of NAS of RA,

e-mail alhswede@mathematik.uni-bielefeld.de, evhar@ipia.sci.am

Abstract

A new aspect of the in°uence of the information-theoretical methods on the statisti-
cal theory is considered. The procedures of the probability distributions identi¯cation
for K(¸ 1) random objects each having one from the known set of M(¸ 2) distributions
are studied. N-sequences of discrete independent random variables represent results of
N observations for each of K objects. Decisions concerning probability distributions
of the objects must be made on the base of such samples. For N ! 1 the exponen-
tial decrease of the test's error probabilities is considered. The reliability matrices of
logarithmically asymptotically optimal procedures are explored for some models and
formulations of the identi¯cation problems. The optimal subsets of reliabilities which
values may be given beforehand and conditions guaranteeing positiveness of all the
reliabilities are investigated.

Refer ences

[1 ] R a o C. R ., L in e a r s t a t is t ic a l in fe r e n c e a n d it s a p p lic a t io n s . W ile y, N e w Y o r k, 1 9 6 5 .
[2 ] B e c h h o fe r R . E ., K ie fe r J, a n d S o b e l M., S e qu e n t ia l id e n t i¯ c a t io n a n d r a n kin g p r o c e -

d u r e s . Th e U n ive r s it y o f Ch ic a g o P r e s s , Ch ic a g o , 1 9 6 8 .
[3 ] A h ls we d e R . a n d W e g e n e r I., S e a r c h p r o b le m s . W ile y, N e w Y o r k, 1 9 8 7 .
[4 ] A h ls we d e R . a n d D u e c k G., Id e n t i¯ c a t io n via c h a n n e ls . IE E E Tr a n s . In fo r m . Th e o r y,

vo l. 3 5 , n o . 1 , p p . 1 5 -2 9 , 1 9 8 9 .
[5 ] A h ls we d e R ., Ge n e r a l t h e o r y o f in fo r m a t io n t r a n s fe r . P r e p r in t 9 7 -1 1 8 , S FB ., D is c r e t e

S t r u c t u r e s in d e r Ma t h e m a t ik, U n ive r s it Äa t B ie le fe ld .
[6 ] H o e ®d in g W ., A s ym p t o t ic a lly o p t im a l t e s t s fo r m u lt in o m ia l d is t r ib u t io n s . A n n a ls . o f

Ma t h . S t a t is t ., vo l. 3 6 , p p . 3 6 9 -4 0 1 , 1 9 6 5 .
[7 ] Cs is z ¶a r I. a n d L o n g o G., On t h e e r r o r e xp o n e n t fo r s o u r c e c o d in g a n d fo r t e s t in g s im p le

s t a t is t ic a l h yp o t h e s e s . S t u d ia S c . Ma t h . H u n g a r ic a , vo l. 6 , p p . 1 8 1 -1 9 1 , 1 9 7 1 .
[8 ] Tu s n a d y G., On a s ym p t o t ic a lly o p t im a l t e s t s . A n n a ls o f S t a t is t ., vo l. 5 , n o . 2 , p p .

3 8 5 -3 9 3 , 1 9 7 7 .
[9 ] L o n g o G. a n d S g a r r o A ., Th e e r r o r e xp o n e n t fo r t h e t e s t in g o f s im p le s t a t is t ic a l h y-

p o t h e s e s , a c o m b in a t o r ia l a p p r o a c h . J. o f Co m b in ., In fo r m . S ys . S c ., vo l. 5 , N o 1 , p p .
5 8 -6 7 , 1 9 8 0 .

1 6



R. Ahlswede and E. A. Haroutunian 1 7

[1 0 ] B ir g ¶ e L ., V it e s s e m a xim a le s d e d ¶ e c r o is s a n c e d e s e r r e u r s e t t e s t s o p t im a u x a s s o c i¶ e s , Z.
W a h r s c h . ve r w Ge b ie t e , vo l. 5 5 , p p . 2 6 1 { 2 7 3 , 1 9 8 1 .

[1 1 ] H a r o u t u n ia n E . A ., L o g a r it h m ic a lly a s ym p t o t ic a lly o p t im a l t e s t in g o f m u lt ip le s t a t is t i-
c a l h yp o t h e s e s . P r o b le m s o f Co n t r o l a n d In fo r m . Th e o r y. vo l. 1 9 , n o . 5 -6 , p p . 4 1 3 -4 2 1 ,
1 9 9 0 .

[1 2 ] Cs is z ¶a r I. a n d K Äo r n e r J., In fo r m a t io n t h e o r y: Co d in g t h e o r e m s fo r d is c r e t e m e m o r yle s s
s ys t e m s . A c a d e m ic P r e s s , N e w Y o r k, 1 9 8 1 .

[1 3 ] Cs is z ¶a r I., Me t h o d o f t yp e s . IE E E Tr a n s . In fo r m . Th e o r y, vo l. 4 4 , n o . 6 , p p . 2 5 0 5 -2 5 2 3 ,
1 9 9 8 .

[1 4 ] N a t a r a ja n S ., L a r g e d e via t io n s , h yp o t h e s e s t e s t in g , a n d s o u r c e c o d in g fo r ¯ n it e Ma r ko v
c h a in s . IE E E Tr a n s . In fo r m . Th e o r y, vo l. 3 1 , n o . 3 , p p . 3 6 0 -3 6 5 , 1 9 8 5 .

[1 5 ] H a r o u t u n ia n E . A ., On a s ym p t o t ic a lly o p t im a l t e s t in g o f h yp o t h e s e s c o n c e r n in g Ma r ko v
c h a in ( in R u s s ia n ) , Iz ve s t ia A c a d . N a u k A r m e n ia n S S R . S e r ia Ma t h e m . vo l. 2 2 , n o 1 ,
p p . 7 6 -8 0 , 1 9 8 8 .

[1 6 ] Gu t m a n M., A s ym p t o t ic a lly o p t im a l c la s s ī c a t io n fo r m u lt ip le t e s t wit h e m p ir ic a lly
o b s e r ve d s t a t is t ic s . IE E E Tr a n s . In fo r m . Th e o r y, vo l 3 5 , N o 2 , p p . 4 0 1 -4 0 8 , 1 9 8 9 .

[1 7 ] B la h u t R . E ., P r in c ip le s a n d p r a c t ic e o f in fo r m a t io n t h e o r y. A d d is o n -W e s la y, Ma s -
s a c h u s e t t s , 1 9 8 7 .

[1 8 ] B la h u t R . E ., H yp o t h e s e s t e s t in g a n d in fo r m a t io n t h e o r y, IE E E Tr a n s . In fo r m Th e o r y,
vo l 2 0 , n o 4 , p p . 4 0 5 -4 1 7 , 1 9 7 4 .

[1 9 ] Fu F.-W . a n d S h e n S . Y ., H yp o t h e s is t e s t in g fo r a r b it r a r ily va r yin g s o u r c e wit h e xp o -
n e n t s t yp e c o n s t r a in t . IE E E Tr a n s . In fo r m . Th e o r y, vo l. 4 4 , n o . 2 , p p . 8 9 2 -8 9 5 , 1 9 9 8 .

[2 0 ] A h ls we d e R . a n d Cs is z ¶a r I., H yp o t h e s e s t e s t in g wit h c o m m u n ic a t io n c o n s t r a in t s . IE E E
Tr a n s . In fo r m . Th e o r y vo l. 3 2 , n o . 4 , p p . 5 3 3 -5 4 2 , 1 9 8 6 .

[2 1 ] H a n T.S . a n d K o b a ya s h i K ., E xp o n e n t ia l-t yp e e r r o r p r o b a b ilit ie s fo r m u lt it e r m in a l h y-
p o t h e s is t e s t in g . IE E E Tr a n s . In fo r m . Th e o r y, vo l. 3 5 , n o . 1 , p p . 2 -1 3 , 1 9 8 9 .

[2 2 ] B e r g e r T., D e c e n t r a liz e d e s t im a t io n a n d d e c is io n t h e o r y, P r e s e n t e d a t IE E E S e ve n
S p r in g s W o r ks h o p o n In fo r m a t io n Th e o r y, Mt . K is c o , N Y , S e p t e m b e r 1 9 7 9 .

[2 3 ] Zh a n g Z. a n d B e r g e r T., E s t im a t io n via c o m p r e s s e d in fo r m a t io n . IE E E Tr a n s . In fo r m .
Th e o r y, vo l. 3 4 , n o . 2 , p p . 1 9 8 -2 1 1 , 1 9 8 8 .

[2 4 ] A h ls we d e R . a n d B u r n a s h e v M., On m in im a x e s t im a t io n in t h e p r e s e n c e o f s id e in fo r -
m a t io n a b o u t r e m o t e d a t a . A n n a ls o f S t a t is t ., vo l. 1 8 , n o . 1 , p p . 1 4 1 -1 7 1 , 1 9 9 0 .

[2 5 ] H a n T. S . a n d A m a r i S ., S t a t is t ic a l in fe r e n c e u n d e r m u lt it e r m in a l d a t a c o m p r e s s io n ,
IE E E Tr a n s In fo r m Th e o r y, vo l. 4 4 , n o . 6 , p p . 2 3 0 0 -2 3 2 4 , 1 9 9 8 .

[2 6 ] A h ls we d e R ., Y a n g E ., Zh a n g Z., Id e n t i¯ c a t io n via c o m p r e s s e d d a t a . IE E E Tr a n s . In -
fo r m . Th e o r y, vo l. 4 3 , n o . 1 , p p . 4 8 -7 0 , 1 9 9 7 .

[2 7 ] B o r o vko v A . A ., Ma t h e m a t ic a l s t a t is t ic s ( in R u s s ia n ) . N a u ka , N o vo s ib ir s k, 1 9 9 7 .
[2 8 ] Ih a r a , In fo r m a t io n t h e o r y fo r c o n t in u o u s s ys t e m s . W o r ld S c ie n t i¯ c , S in g a p o r e , 1 9 9 3 .
[2 9 ] Ch e n P .-N ., Ge n e r a l fo r m u la s fo r t h e N e ym a n -P e a r s o n t yp e -II e r r o r e xp o n e n t s u b je c t

t o ¯ xe d a n d e xp o n e n t ia l t yp e -I e r r o r b o u n d s . IE E E Tr a n s . In fo r m . Th e o r y, vo l. 4 2 , n o .
1 , p p . 3 1 6 -3 2 3 , 1 9 9 6 .

[3 0 ] H a n T. S ., In fo r m a t io n -s p e c t r u m m e t h o d s in in fo r m a t io n t h e o r y. S p r in g e r , B e r lin , 2 0 0 3 .
[3 1 ] H a n T.S . H yp o t h e s is t e s t in g wit h t h e g e n e r a l s o u r c e . IE E E Tr a n s . In fo r m . Th e o r y, vo l.

4 6 , n o . 7 , p p . 2 4 1 5 -2 4 2 7 , 2 0 0 0 .
[3 2 ] Ma u r e r U . M., A u t h e n t ic a t io n t h e o r y a n d h yp o t h e s is t e s t in g . IE E E Tr a n s . In fo r m .

Th e o r y, vo l. 4 6 , n o . 4 , p p . 1 3 5 0 -1 3 5 6 , 2 0 0 0 .
[3 3 ] Ca c h in C., A n in fo r m a t io n -t h e o r e t ic m o d e l fo r s t e g a n o g r a p h y. P r o c . 2 n d W o r ks h o p o n

In fo r m a t io n H id in g ( D a vid A u s m it h , e d .) , L e c t u r e N o t e s in c o m p u t e r S c ie n c e , S p r in g e r {
V e r la g , 1 9 9 8 .



1 8 On Statistical Hypotheses Optimal Testing and Identi¯cation

ìÇ׳ϳ·ñ³Ï³Ý í³ñϳÍÝ»ñÇ ûåïÇÙ³É
ï»ëïÙ³Ý ¨ ÝáõÛݳϳݳóÙ³Ý Ù³ëÇÝ

è.²Éëí»¹», º. гñáõÃÛáõÝÛ³Ý

²Ù÷á÷áõÙ

¸Çï³ñÏí³Í ¿ ÇÝýáñÙ³óÇáÝ–ï»ë³Ï³Ý Ù»Ãá¹Ý»ñÇ íÇ׳ϳ·ñ³Ï³Ý ï»ëáõÃÛ³Ý íñ³
³½¹»óáõÃÛ³Ý ÙÇ Ýáñ Ñݳñ³íáñáõÃÛáõÝ: àõëáõÙݳëÇñí³Í »Ý ѳí³Ý³Ï³ÝáõÃÛáõÝÝ»ñÇ
µ³ßËáõٻݻñÇ ÝáõÛݳϳݳóÙ³Ý ÁÝóó³Ï³ñ·»ñÁ K ( ¸ 1 ) å³ï³Ñ³Ï³Ý³óí³Í
ûµÛ»ÏïÝ»ñÇ Ñ³Ù³ñ, áñáÝóÇó Ûáõñ³ù³ÝãÛáõñÁ µ³ßËí³Í ¿ Áëï ïñí³Í M ( ¸ 2 )
µ³ßËáõÙ»ÝñÇó Ù»ÏÇ: ÀÝ¹Ñ³ï ³ÝÏ³Ë å³ï³Ñ³Ï³Ý Ù»ÍáõÃÛáõÝÝ»ñÇ N –ѳçáñ¹³Ï³-
ÝáõÃÛáõÝÝ»ñÁ Ý»ñϳ۳óÝáõÙ »Ý K ûµÛ»ÏïÝ»ñÇ Ûáõñ³ù³ÝãÛáõñÇ N ¹Çï³ñÏáõٻݻñÇ
³ñ¹ÛáõÝùÝ»ñÁ: àñáßáõÙÝ»ñÁ å»ïù ¿ ÁݹáõÝí»Ý ûµÛ»ÏïÝ»ñÇ Ñ³í³Ý³Ï³Ý³ÛÇÝ µ³ßËáõÙ-
Ý»ñÇ Ù³ëÇÝ: ¸Çï³ñÏí³Í ¿ ï»ëï»ñÇ ë˳ÉÝ»ñÇ Ñ³í³Ý³Ï³ÝáõÃÛáõÝÝ»ñÇ óáõóã³ÛÇÝ
Ýí³½áõÙÁ, »ñµ N ! 1: лﳽáïí³Í »Ý Éá·³ñÇÃÙáñ»Ý, ³ëÇÙåïáïáñ»Ý ûåïÇÙ³É
ÁÝóó³Ï³ñ·»ñÇ Ñáõë³ÉÇáõÃÛ³Ý Ù³ïñÇóÝ»ñÁ ÝáõÛݳϳݳóÙ³Ý ËݹñÇ ÙÇ ù³ÝÇ
Ùá¹»ÉÝ»ñÇ ¨ Ó¨³Ï»ñåáõÙÝ»ñÇ ¹»åùáõÙ: Üßí³Í »Ý ³ÛÝ Ñáõë³ÉÇáõÃÛáõÝÝ»ñÇ ûåïÇÙ³É
»Ýóµ³½ÙáõÃÛáõÝÝ»ñÁ, áñáÝó ³ñÅ»ùÝ»ñÁ ϳñáÕ »Ý ïñí»É ݳËûñáù ¨ ³ÛÝ å³ÛÙ³ÝÝ»ñÁ,
áñáÝù ³å³ÑáíáõÙ »Ý µáÉáñ Ñáõë³ÉÇáõÃÛáõÝÝ»ñÇ ¹ñ³Ï³Ý ÉÇÝ»ÉÁ: