article_with_style.DVI


Mathematical Problems of Computer Science 31, 60{72, 2008.

On M ultiple H ypotheses LAO T esting by I nfor med

Statistician for Ar bitr ar ily Var ying M ar kov Sour ce and

on Such Sour ce Coding Reliability Function

N a ir a M. Gr ig o r ya n

State Engineering University of Armenia nar.gri@gmail.com

Abstract

In this paper the problem of multiple hypotheses testing for arbitrarily varying
Markov source (AVMS) with state sequence known to the statistician is solved from
the point of view of logarithmically asymptotically optimal (LAO) testing. The matrix
of asymptotic interdependencies of all possible pairs of the error probability exponents
(reliabilities) in optimal testing for this model is studied. The LAO test, assuming
that exponents of some number of the error probabilities are given, ensure the best
asymptotic exponents for the rest of them. We ¯nd LAO test and the corresponding
matrix of all error probability exponents. As an application to information theory,
the E-optimal rate R(E) (the minimum rate R of the source sequences compression
when the decoding error probability is less than expf¡N Eg; E > 0) and the reliability
function E(R) of AVMS coding are determined.

Refer ences

[1 ] W . H o e ®d in g , \ 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 .
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 .

[2 ] I. Cs is z ¶a r a n d G. L o n g o , \ 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 ie n t ia r u m Ma t h e m . H u n g ., vo l. 6 , p p . 1 8 1 ¡1 9 1 , 1 9 7 1 .

[3 ] L . B ir g ¶ e , \ V it e s s m a xim a ls d e d ¶ c r o is m e 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 ie 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 ¡ 1 7 3 , 1 9 8 1 .

[4 ] E . A . H a r o u t u n ia n , \ 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 ic a l h yp o t h e s e s " , P roblems of Control and Information Theory, vo l. 1 9 , n o . 5 -6 , p p .
4 1 3 ¡4 2 1 , 1 9 9 0 .

[5 ] S . N a t a r a ja n , \ 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 Trans. Inform. Theory, vo l 3 1 , n o . 3 , p p . 3 6 0 ¡3 6 5 , 1 9 8 5 .

[6 ] F.-W . Fu a n d S .-Y . S h e n , \ 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 ia l-t yp e c o n s t r a in t " , IE E E Trans. Inform. Theory, vo l. 4 4 , n o . 2 , p p . 8 9 2 ¡ 8 9 5 ,
1 9 9 8 .

[7 ] E . A . H a r o u t u n ia n , \ 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 ) , Izvestiya Akademii Nauk Armenii, M athematika, vo l.
2 3 , n o . 1 , p p . 7 6 ¡ 8 0 , 1 9 8 8 .

6 0



N. Grigoryan 6 1

[8 ] E . A . H a r o u t u n ia n , \ On a s ym p t o t ic a lly o p t im a l c r it e r ia fo r Ma r ko v c h a in s " , ( in R u s -
s ia n ) , The ¯rst W orld Congress of B ernoulli Society, s e c t io n 2 , vo l. 2 , n o . 3 , p p .
1 5 3 ¡ 1 5 6 , 1 9 8 9 .

[9 ] E . A . H a r o u t u n ia n , \ 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 a n y s t a t is t ic a l 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 ) , 5-th Intern. Vilnius Conferance on P robability
Theory and M athem. Statistics, vo l. 1 ( A -L ) , p p . 2 0 2 ¡2 0 3 , 1 9 8 9 .

[1 0 ] R . F. A h ls we d e , E . V . A lo ya n a n d E . A . H a r o u t u n ia n , \ On lo 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 h yp o t h e s is t e s t in g fo r a r b it r a r y va r yin g s o u r c e wit h s id e in fo r m a t io n " ,
L ecture Notes in Computer Science, V o lu m e 4 1 2 3 , " Ge n e r a l Th e o r y o f In fo r m a t io n
Tr a n s fe r a n d Co m b in a t o r ic s " , S p r in g e r , p p . 4 5 7 ¡ 4 6 1 , 2 0 0 4 .

[1 1 ] E . A . H a r o u t u n ia n a n d P . M. H a ko b ya n , \ On Mu lt ip le h yp o t h e s is t e s t in g b y in fo r m e d
s t a t is t ic ia n fo r a r b it r a r ily va r yin g o b je c t a n d a p p lic a t io n t o s o u r c e c o d in g " , M athe-
matical P roblems of Computer Science, vo l. 2 3 , p p . 3 6 ¡ 4 6 , 2 0 0 4 .

[1 2 ] E . A . H a r o u t u n ia n , M. E . H a r o u t u n ia n a n d A . N . H a r u t yu n ya n , \ R e a la b ilit y c r it e r ia
in in fo r m a t io n t h e o r y a n d in s t a t is t ic a l h yp o t h e s e s t e s t in g " , F oundation and Trends
in Comunications and Information Theory, vo l. 4 , n o . 2 ¡3 , 2 0 0 8 .

[1 3 ] E . A . H a r o u t u n ia n a n d N . M. Gr ig o r ya n , \ On r e lia b ilt y a p p r o a c h fo r t e s t in g o f m a n y
d is t r ib u t io n s fo r p a ir o f Ma r ko v c h a in s " , M athematical P roblems of Computer Science,
vo l. 2 9 , p p . 8 9 ¡ 9 6 , 2 0 0 7 .

[1 4 ] I. Cs is z ¶a r a n d J. K Äo r n e r , \Information theory, coding theorems for discrete memoryless
systems", A c a d e m ic P r e s s , N e w Y o r k, 1 9 8 1 .

[1 5 ] M. Gu t m a n , \ A s ym p t o t ic a lly o p t im a l c la s s i¯ 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 Trans. Inform. Theory, vo l. 3 5 , n o . 2 , p p . 4 0 1 ¡ 4 0 8 , 1 9 8 9 .

[1 6 ] P . Ja c ke t a n d W . S z p a n ko vks i, \ Ma r ko v t yp e s a n d m in im a x r e d u n d a n c y fo r Ma r ko v
s o u r c e s ," IE E E Trans. Inform. Theory, vo l. 5 0 , n o . 7 , p p . 1 3 9 3 ¡ 1 4 0 2 , 2 0 0 4 .

[1 7 ] K . Ma r t o n , \ 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 wit h a ¯ e d e lit y c r it e r io n ," IE E E Trans.
Inform. Theory, vo l. 2 0 , n o . 2 , p p . 1 9 7 ¡ 1 9 9 , 1 9 7 4 .

î»Õ»Ï³óí³Í íÇ׳ϳ·ñÇ ÏáÕÙÇó ϳٳ۳ϳÝáñ»Ý ÷á÷áËíáÕ Ù³ñÏáíÛ³Ý
³ÕµÛáõñÇ í»ñ³µ»ñÛ³É µ³½Ù³ÏÇ í³ñϳÍÝ»ñÇ ëïáõ·áõÙÁ ¨ ³ÕµÛáõñÇ

Ïá¹³íáñÙ³Ý Ñáõë³ÉÇáõÃÛ³Ý ýáõÝÏódzÛÇ ·Ý³Ñ³ïáõÙÁ

Ü. ¶ñÇ·áñÛ³Ý

²Ù÷á÷áõÙ

ÈáõÍí³Í ¿ ϳٳ۳ϳÝáñ»Ý ÷á÷áËíáÕ ÏáÕÙݳÏÇ ÇÝýáñÙ³ódzÛáí Ù³ñÏáíÛ³Ý
³ÕµÛáõñÇ Ùá¹»ÉÇ Ñ³Ù³ñ µ³½Ù³ÏÇ í³ñϳÍÝ»ñÇ ëïáõ·Ù³Ý ËݹÇñÁ: M ( ¸ 2 )
ѳí³Ý³Ï³Ý³ÛÇÝ µ³ßËáõÙÝ»ñÁ h³ÛïÝÇ »Ý, ¨ ûµÛ»ÏïÁ ϳٳ۳ϳÝáñ»Ý ÁݹáõÝáõÙ ¿
¹ñ³ÝóÇó áñ¨¿ Ù»ÏÁ: ²Ûë Ùá¹»ÉÇ Ñ³Ù³ñ áõëáõÙݳëÇñí»É ¿ µáÉáñ Ñݳñ³íáñ ½áõÛ·»ñÇ
ë˳ÉÝ»ñÇ Ñ³í³Ý³Ï³ÝáõÃÛáõÝÝ»ñÇ óáõóÇãÝ»ñÇ (Ñáõë³ÉÇáõÃÛáõÝÝ»ñÇ) ÷áËϳËí³ÍáõÃÛáõÝÁ:
ºñáÏáõ í³ñϳÍÝ»ñÇ ¹»åùÁ ÁÝ¹Ñ³ï ³é³Ýó ÑÇßáÕáõÃÛ³Ý Ï³åáõÕáõ ѳٳñ »ñµ
íÇ׳ÏÝ»ñÇ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝÁ ³ÝѳÛï ¿ ÁݹáõÝáõÙ áñáßáÕÇÝ, ¹Çï³ñÏí»É ¿ üáõÇ ¨
Þ»ÝÇ ÏáÕÙÇó: ÆëÏ ÝáõÛÝ Ùá¹»ÉÇ Ñ³Ù³ñ, »ñµ íÇ׳ÏÝ»ñÇ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝÁ ѳÛïÝÇ
¿ íÇ׳ϳ·ñÇÝ ¹Çï³ñÏí»É ¿ ²Éëí»¹»Ç, гñáõÃÛáõÝÛ³ÝÇ ¨ ²ÉáÛ³ÝÇ ÏáÕÙÇó: ÆÝãå»ë
üáõÝ ¨ Þ»ÝÁ, Ù»Ýù ÝáõÛÝå»ë ëï³ó»É »Ýù ÏáÕÙݳÏÇ ÇÝýáñÙ³ódzÛáí ϳٳ۳ϳÝáñ»Ý
÷á÷áËíáÕ ³ÕµÛ»áõñÇ Ñ³Ù³ñ ³ñ³·áõÃÛáõÝ-Ñáõë³ÉÇáõÃÛáõÝ ¨ Ñáõë³ÉÇáõÃÛáõÝ-³ñ³·áõÃÛáõÝ
ýáõÝÏódzݻñÁ: