article_with_style.DVI


Mathematical Problems of Computer Science 31, 73{78, 2008.

Application of LDT to M any H ypotheses Optimal

T esting for M ar kov Chain

L e a d e r N a va e i

Payame Noor University (PNU), IRAN

Abstract

The problem of many (L > 2) hypotheses testing on distributions of a ¯nite state
Markov chain is studied. We apply large deviations techniques (LDT). It is proved that
this method of investigation in solving the problem of logarithmically asymptotically
optimal (LAO) hypotheses testing is easier than the procedure that was introduced by
Haroutunian. The matrix of exponents E = fEljmg; m; l = 1; L, of error probabilities
of the LAO test Eljm(Á) = lim

N !1
¡ 1

N
log ®ljm(ÁN ); where ®

N
ljm(ÁN ) for l 6= m is the

probability to accept the hypothesis l, when the hypothesis m is true, is determined.

Refer ences

[1 ] B la h u t R . E . \ P r in c ip le a n d P r a c t ic e o f In fo r m a t io n Th e o r y" , r e a d in g , MA , A d d is o n -
we s le y, 1 9 8 7 .

[2 ] Cs is z ¶a r I. a n d S h ie ld s P . \ In fo r m a t io n Th e o r y a n d S t a t is t ic s " , Fu n d e m e n t a ls a n d Tr e n d s
in Co m m u n ic a t io n s a n d In fo r m a t io n Th e o r y, vo l. 1 , n o . 4 , 2 0 0 4 .

[3 ] Cs is z ¶a r I. a n d K Äo r n e r J. \ In fo r m a t io n Th e o r y: Co d in g Th e o r e m fo r D is c r e t e Me 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 wY o r k, 1 9 8 1 .

[4 ] 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 .

[5 ] D e m b o A . a n d Ze it o u n i O. \ L a r g e D e via t io n s Te c h n iqu e s a n d A p p lic a t io n s " , Jo n s a n d
B a r t le t . P u b lis h e r s , L o n d o n , 1 9 9 3 .

[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 .

[7 ] 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 .

[8 ] H a r o u t u n ia n E . A , H a r o u t u n ia n M. E a n d H a r u t yu n ya n A . N .\ R e lia b ilit y Cr it e r ia in
In fo r m a t io n Th e o r y a n d in S t a t is t ic a l H yp o t h e s is Te s t in g " , Fo u n d a t io n s a n d Tr e n d s in
Co m m u n ic a t io n s a n d In fo r m a t io n Th e o r y, vo l. 4 , n o . 2 -3 , 2 0 0 7 .

[9 ] K u llb a c k S . \ In fo r m a t io n Th e o r y a n d S t a t is t ic s " , W ile y, N e w Y o r k, 1 9 5 9 .
[1 0 ] 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 " , 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 1 ] N a va e i L .\ On m a n y h yp o t h e s e s L A O t e s t in g via t h e t h e o r y o f la r g e d e via t io n s " , Fa r

E a s t Jo u r n a l o f Ma t h e m a t ic a l S c ie n c e s , vo l. 2 5 , n o . 2 , p p . 3 3 5 -3 4 4 , 2 0 0 7 .

7 3



7 4 Application of LDT to Many Hypotheses Optimal Testing for Markov Chain

ØÞî ÏÇñ³éáõÃÛáõÝÁ سñÏáíÇ ßÕóݻñÇ Ñ³Ù³ñ µ³½Ù³ÏÇ
í³ñϳÍÝ»ñÇ ûåïÇÙ³É ï»ëï³íáñÙ³ÝÁ

È. ܳí³ÛÇ

²Ù÷á÷áõÙ

àõëáõÙݳëÇñí³Í ¿ í»ñç³íáñ íÇ׳ÏÝ»ñáí سñÏáíÇ ßÕóÛÇ Ýϳïٳٵ µ³½Ù³ÏÇ
í³ñϳÍÝ»ñÇ ëïáõ·Ù³Ý ËݹÇñÁ: ÎÇñ³éíáõÙ ¿ Ù»Í ß»ÕáõÙÝ»ñÇ ï»ËÝÇÏ³Ý (ØÞî):

²å³óáõóí»É ¿, áñ í³ñϳÍÝ»ñÇ Éá·³ñÇÃÙáñ»Ý ³ëÇÙåïáïáñ»Ý ûåïÇÙ³É (Ȳú)
ï»ëï³íáñÙ³Ý Ñ»ï³½áïÙ³Ý ³Ûë »Õ³Ý³ÏÁ ³í»ÉÇ Ñ»ßï ¿, ù³Ý гñáõÃÛáõÝÛ³ÝÇ ÏáÕÙÇó
Ý»ñÙáõÍí³ÍÁ: