Article_Final.DVI


Mathematical Problems of Computer Science 41, 63{73, 2014.

On LAO T wo-stage T esting of M ultiple H ypotheses

Concer ning M ar kov Chain

E vg u e n i A . H a r o u t u n ia n , P a r a n d z e m M. H a ko b ya n a n d A r a m O. Y e s a ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: evhar@ipia.sci.am, par h@ipia.sci.am, armfranse@yahoo.fr

Abstract

Two-stage testing of multiple hypotheses concerning Markov chain with two sep-
arate families of hypothetical transition probabilities is considered. The matrix of
reliabilities of logarithmically asymptotically optimal hypotheses testing by a pair of
stages is studied and compared with the case of similar one-stage testing. It is shown
that two-stage testing needs less operations than one-stage testing.

Keywords: Logarithmically asymptotically optimal (LAO) test, Multiple hy-
potheses testing, Multistage tests, Reliabilities matrix, Error probability exponent,
Markov chain.

1 . In t r o d u c t io n

In t h is p a p e r we s t u d y m u lt ip le h yp o t h e s e s L A O t wo -s t a g e t e s t in g b y a s a m p le o f s e qu e n c e
o f e xp e r im e n t s c o n c e r n in g a Ma r ko v c h a in . A n a lo g o u s p r o b le m wa s fo r m u la t e d a n d s o lve d
fo r t h e c a s e o f in d e p e n d e n t e xp e r im e n t s in [1 ].

Th e c la s s ic a l p r o b le m o f s t a t is t ic a l h yp o t h e s e s t e s t in g r e fe r s t o t wo h yp o t h e s e s [2 ]. Th e
p r o c e d u r e o f s t a t is t ic a l h yp o t h e s e s d e t e c t io n is c a lle d a t e s t . Th e p r o b a b ilit y o f in c o r r e c t
a c c e p t a n c e o f o n e h yp o t h e s is in s t e a d o f t h e o t h e r is a n e r r o r p r o b a b ilit y. W e c o n s id e r t h e
c a s e o f a t e s t s s e qu e n c e , wh e r e t h e p r o b a b ilit ie s o f e r r o r d e c r e a s e e xp o n e n t ia lly a s 2 ¡N E,
wh e n t h e n u m b e r o f o b s e r va t io n s N ( s iz e o f s a m p le ) t e n d s t o in ¯ n it y. Th e e xp o n e n t o f e r r o r
p r o b a b ilit y E we c a ll reliability. Th e t e s t is c a lle d logarithmically asymptotically optimal
( L A O) if fo r o n e o f t h e g ive n o f r e lia b ilit ie s t h e c o n s t r ic t e d t e s t p r o vid e d t h e g r e a t e s t va lu e
o f t h e o t h e r r e lia b ilit y. Th e g o a l o f r e s e a r c h wa s t o ¯ n d a n o p t im a l fu n c t io n a l r e la t io n
b e t we e n t h e e r r o r p r o b a b ilit ie s e xp o n e n t s o f t h e ¯ r s t a n d t h e s e c o n d t yp e s o f e r r o r . S u c h
o p t im a l t e s t s we r e c o n s id e r e d ¯ r s t b y H o e ®d in g [3 ], e xa m in e d la t e r b y Cs is z ¶a r a n d L o n g o [4 ],
Tu s n a d y [5 ], [6 ], L o n g o a n d S g a r r o [7 ], B ir g ¶ e [8 ] ( h e p r o p o s e d t h e t e r m L A O) a n d b y m a n y
o t h e r s . S o m e a u t h o r s fo r t h is c o n c e p t o f t e s t in g [6 , 9 , 1 0 ] a p p lie d t h e t e r m s exponentially
rate optimal ( E R O) . H o e ®d in g 's r e s u lt wa s g e n e r a liz e d t o ¯ n it e Ma r ko v c h a in in [1 1 ].

Th e n e e d o f t e s t in g o f m o r e t h a n t wo h yp o t h e s e s in m a n y s c ie n t ī c a n d a p p lie d ¯ e ld s h a s
in c r e a s e d r e c e n t ly. Th e p r o b le m o f L A O t e s t in g o f m u lt ip le h yp o t h e s e s wa s in ve s t ig a t e d in
[1 2 ] a n d wa s la t e r e xt e n d e d fo r a d is c r e t e s t a t io n a r y Ma r ko v s o u r c e a n d a r b it r a r ily va r yin g
Ma r ko v s o u r c e [1 3 ]{ [2 0 ].

6 3



6 4 On LAO Two-stage Testing of Multiple Hypotheses Concerning Markov Chain

Two -s t a g e p r o c e d u r e s o f t e s t in g a r e u s e fu l in a p p lic a t io n s fo r a c h ie vin g m in im a l e c o n o m ic
e xp e n d it u r e .

2 . D e ¯ n it io n s a n d N o t a t io n s

Th is s e c t io n is d e d ic a t e d t o n e c e s s a r y n o t a t io n s a n d p r o p e r t ie s . L e t X b e a ¯ n it e s e t o f
s t a t e s o f s t a t io n a r y Ma r ko v c h a in X0, X1, X2, ..., wh ic h is a s t o c h a s t ic p r o c e s s d e ¯ n e d b y
m a t r ix o f t r a n s it io n p r o b a b ilit ie s

P ( Xn = xjXn¡1 = u ) = P ( xju ) ; x; u 2 X :

Th e r e e xis t s t h e c o r r e s p o n d in g s t a t io n a r y p r o b a b ilit y d is t r ib u t io n ( P D ) Q = fQ( u ) g, s u c h
t h a t X

x2X
Q( u ) P ( xju ) = Q ( x ) ;

X

u2X
Q( u ) = 1 :

S u p p o s e L h yp o t h e t ic a l t r a n s it io n p r o b a b ilit ie s Gl = fGl ( xju) g, x; u 2 X , l = 1 ; L, wit h
c o r r e s p o n d in g s t a t io n a r y d is t r ib u t io n s Ql = fQl ( u ) g, l = 1 ; L, a r e g ive n a n d a r r a n g e d in
t wo d is jo in t fa m ilie s . Th e ¯ r s t fa m ily P1 in c lu d e s R h yp o t h e s e s a n d t h e s e c o n d fa m ily P2
in c lu d e s L ¡ R h yp o t h e s e s . It is u n kn o wn wh ic h o n e o f t h o s e d is t r ib u t io n s is r e a liz e d . On
t h e b a s e o f t h e s a m p le x = ( x0; x1; :::; xN ) 2 X N +1 o f t h e r e s u lt s o f N + 1 o b s e r va t io n s t h e
s t a t is t ic ia n is t r yin g t o m a ke a r e lia b le d e c is io n a b o u t r e a l d is t r ib u t io n .

Th e t wo -s t a g e t e s t o n t h e b a s e o f t h e s a m p le x we d e n o t e b y ©N ( x ) , it m a y b e c o m p o s e d
b y t h e p a ir o f t e s t s 'N1 ( x ) a n d '

N
2 ( x ) o f t wo c o n s e c u t ive s t a g e s , we wr it e ©

N = ( 'N1 ; '
N
2 ) .

Th e ¯ r s t s t a g e fo r s e le c t io n o f a fa m ily P1 o r P2 is a n o n -r a n d o m iz e d t e s t 'N1 ( x) . Th e n e xt
s t a g e is fo r m a kin g a d e c is io n in t h e d e t e r m in e d fa m ily o f P D s , it is m a d e b y n o n -r a n d o m iz e d
t e s t 'N2 ( x) b a s e d o n t h e s a m e s a m p le x.

W e d e ¯ n e a n y n e c e s s a r y c h a r a c t e r is t ic s S h a n n o n 's e n t r o p y a n d K u llb a c k-L e ib le r 's d ive r -
g e n c e s fo r Ma r ko v c h a in .

Th e S h a n n o n 's e n t r o p y fo r Ma r ko v c h a in is d e ¯ n e d a s fo llo ws :

HQ±P ( X )
4
= ¡

X

x;u

Q ( u ) P ( xju ) lo g P ( xju ) :

Th e c o n d it io n a l K u llb a c k-L e ib le r d ive r g e n c e D ( P kW jQ ) o f P D s Q ± P 4=
fQ( u ) P ( xju ) ) ; u 2 X ; x 2 X g a n d Q ± W 4= fQ( u ) W ( xju ) ) ; u 2 X ; x 2 X g o n X £ X
is :

D ( Q ± P kQ ± W ) = D ( P kW jQ ) 4=
X

u2X ;x2X
Q( u ) P ( xju ) lo g P ( xju )

W ( xju ) :

Th e in fo r m a t io n a l d ive r g e n c e o f P D P a n d P D Q o n X is :

D ( QkQl )
4
=

X

x2X
Q ( x) lo g

Q ( x )

Ql ( x)
:

Fo r p r o o fs we will u s e t h e m e t h o d o f t yp e s , wh ic h is a n im p o r t a n t t e c h n ic a l t o o l in In fo r m a -
t io n Th e o r y.

L e t u s n a m e t h e s e c o n d o r d e r t yp e o f t h e Ma r ko v ve c t o r x t h e s qu a r e m a t r ix o f jX j2
r e la t ive fr e qu e n c ie s fN ( u; x ) N ¡1; x; u 2 X g o f t h e s im u lt a n e o u s a p p e a r a n c e o n t h e p a ir s o f
n e ig h b o r p la c e s o f t h e s t a t e s u a n d x. It is c le a r t h a t

P
ux N ( u; x) = N.



E. Haroutunian, P. Hakobyan and A. Yesayan 6 5

D e n o t e b y T NQ±P t h e s e t o f ve c t o r s fr o m X N +1 wh ic h h a ve s u c h a t yp e t h a t fo r t h e jo in t
P D Q ± P , N ( u; x ) = NQ( u ) P ( xju ) ; x; u 2 X :

W e will u s e t h e fo llo win g p r o p e r t ie s o f t yp e s o f s e c o n d o r d e r [1 3 ]{ [1 5 ]: t h e n u m b e r jT NQ±P j
o f ve c t o r s in T NQ±P is t h e fo llo win g

jT NQ±P j = e xp fNHQ±P ( X ) + o( 1 ) g; wit h o ( 1 ) ! 0 ; wh e n N ! 1; ( 1 )

a n d t h e n u m b e r o f e le m e n t s o f s e t s T NQ±P fo r d i®e r e n t P D s Q ± P d o e s n o t e xc e e d ( N + 1 ) jX j
2
.

Th e p r o b a b ilit y o f t h e ve c t o r x 2 X N +1 o f t h e Ma r ko v c h a in wit h t r a n s it io n p r o b a b ilit ie s
Gl a n d s t a t io n a r y d is t r ib u t io n Ql is d e ¯ n e d a s fo llo ws :

Ql ± GNl ( x )
4
= Ql ( x0 )

NY

n=1

Gl ( xnjxn¡1 ) ; l = 1 ; L;

Ql ± GNl ( A )
4
=

[

x2A
Ql ± GNl ( x) ; A ½ X N +1:

Th e p r o b a b ilit y o f t h e ve c t o r x fr o m T NQ±P fo r l = 1 ; L, c a n b e wr it t e n a ls o in t h e fo llo win g
fo r m :

Ql ± GNl ( x ) = Ql ( x0 )
Y

u;x

Gl ( xju ) NQ(u)P (xju)

= Ql ( x0 ) e xp fN
X

x;u

Q ( u) P ( xju ) lo g Gl ( xju) g

= Ql ( x0 ) e xp

(
¡N

X

x;u

Q( u ) P ( xju )
"
lo g

P ( xju)
Gl ( xju )

¡ lo g P ( xju )
#)

( 2 )

= e xp f¡N [D ( Q ± P kQ ± Gl ) ¡ HQ±P ( X ) ¡ o ( 1 ) ]g ;

wh e r e o( 1 ) ! 0 , wh e n N ! 1.
A c c o r d in g t o ( 1 ) a n d ( 2 ) we o b t a in

Ql ± GNl ( T NQ±P ) = e xp f¡N [D ( Q ± P kQ ± Gl ) + o ( 1 ) ]g : ( 3 )

3 . Fir s t S t a g e Te s t o f Two S t a g e s

Th e ¯ r s t s t a g e o f d e c is io n m a kin g c o n s is t s in u s in g t h e s a m p le x fo r t h e s e le c t io n o f o n e
fa m ily o f t wo o f P D s b y a t e s t 'N1 ( x) ; wh ic h c a n b e d e ¯ n e d b y t h e d ivis io n o f t h e s a m p le

s p a c e X N in t o t h e p a ir o f d is jo in t s u b s e t s ANi
4
= fx : 'N1 ( x) = ig , i = 1 ; 2 : Th e s e t ANi

c o n s is t s o f a ll ve c t o r s x fo r wh ic h i-t h fa m ily Pi o f P D s is a d o p t e d .
In fa c t t h is is t h e p r o b le m o f t wo c o m p o s it e h yp o t h e s e s t e s t in g s t u d ie d in [9 , 1 0 ]. A t t h e

s a m e t im e t h e ¯ r s t s t a g e t e s t o f t wo s t a g e s is c o n n e c t e d wit h t h e id e n t ī c a t io n p r o c e d u r e
wh ic h wa s c o n s id e r e d in [2 1 ]{ [2 6 ].

Th e t e s t 'N1 ( x) c a n h a ve t wo kin d s o f e r r o r s fo r t h e p a ir o f h yp o t h e s e s Pi; i = 1 ; 2 . L e t
®02j1 ( '

N
1 ) b e t h e p r o b a b ilit y o f t h e e r r o n e o u s a c c e p t a n c e o f t h e s e c o n d fa m ily P2 p r o vid e d

t h a t t h e ¯ r s t fa m ily P1 is t r u e ( t h a t is t h e c o r r e c t P D is in t h e ¯ r s t fa m ily) a n d ®01j2 ( 'N1 )
b e t h e p r o b a b ilit y o f t h e e r r o n e o u s a c c e p t a n c e o f P1 p r o vid e d t h a t t h e s e c o n d fa m ily P2 is
t r u e . W e d e ¯ n e

®02j1 ( '
N
1 )

4
= ®01j1 ( '

N
1 )

4
= m a x

r:r=1;R
Qr ± GNr ( AN2 ) ; ( 4 )



6 6 On LAO Two-stage Testing of Multiple Hypotheses Concerning Markov Chain

®01j2 ( '
N
1 )

4
= ®02j2 ( '

N
1 )

4
= m a x

l:l=R+1;L
Ql ± GNl ( AN1 ) : ( 5 )

Th e c o r r e s p o n d in g r e lia b ilit ie s a r e d e ¯ n e d fo r in ¯ n it e s e qu e n c e '1 o f t e s t s :

E0ijj ( '1 )
4
= lim in f

N!1

½
¡ 1

N
lo g ®0ijj ( '

N
1 )

¾
; i; j = 1 ; 2 ; i 6= j: ( 6 )

Th e t e s t s e qu e n c e '1 is c o n s id e r e d t o b e L A O if fo r t h e g ive n va lu e o f E
0¤
2j1 it p r o vid e s

t h e la r g e s t va lu e t o E
0¤
1j2. Ou r a im is t o ¯ n d t h e r e lia b ilit y fu n c t io n E

0¤
1j2 ( E

0
2j1 ) .

Fo r t h e g ive n E
0¤
2j1 we c a n d e ¯ n e L A O t e s t '

¤N
1 b y d ivis io n o f X N in t o t h e fo llo win g t wo

d is jo in t s u b s e t s

BN1 =
[

Q±P : D(QkQr )<1; m in
r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1

T NQ±P ; a n d BN2 = X N n BN1 :

T heor em 1: F or any E02j1 > 0 the reliability function E
0¤
1j2 ( E

0
2j1 ) of the L AO test for

testing many hypotheses Gl, l = 1 ; L, concerning M arkov chains is given as follows:

E
0¤
1j2 ( E

0¤
2j1 ) = m in

l: l=R+1;L
in f

Q±P : D(QkQr)<1; m in
r: r=1;R

D(Q±P kQ±Gr)·E0¤2j1
D ( Q ± P kQ ± Gl ) :

P r oof: Fr o m t h e e s t im a t io n s o f t h e c o r r e s p o n d in g e r r o r p r o b a b ilit ie s u s in g ( 3 ) it fo llo ws :

®02j1 ( '
N
1 ) = m a x

r: r=1;R
Qr ± GNr ( BN2 )

· m a x
r: r=1;R

( N + 1 ) jX j
2

m a x
Q±P : D(QkQr )<1; m in

r;r=1;R

D(Q±P kQ±Gr)>E0¤2j1
Qr ± GNr ( T NQ±P )

· m a x
r: r=1;R

m a x
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr)>E0¤2j1
e xp f¡N [D ( Q ± P kQ ± Gr ) + o ( 1 ) ]g

· e xp f¡N[ m in
r: r=1;R

m in
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr)>E0¤2j1
D ( Q ± P kQ ± Gr ) + o( 1 ) ]g

· e xp
n
¡N

h
E

0¤
2j1 + o ( 1 )

io
;

Fo r ®01j2 ( '
N
1 ) we h a ve t h e fo llo win g e s t im a t io n :

®01j2 ( '
N
1 ) = m a x

l:l=R+1;L
Ql ± GNl ( BN2 )

· ( N + 1 ) jX j2 m a x
l:l=R+1;L

m a x
Q±P : D(QkQr )<1; m in

r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1
Ql ± GNl ( T NQ±P )

· m a x
l:l=R+1;L

m a x
Q±P : D(QkQr )<1; m in

r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1
e xp f¡N[D ( Q ± P kQ ± Gl ) + o ( 1 ) ]g

= e xp f¡N[ m in
l:l=R+1;L

m in
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1
D ( Q ± P kQ ± Gl ) + o( 1 ) ]g:

N o w le t u s p r o ve t h e in ve r s e in e qu a lit y fo r ®01j2 ( '
N
1 ) :



E. Haroutunian, P. Hakobyan and A. Yesayan 6 7

®01j2 ( '
N
1 ) = m a x

l:l=R+1;L
Ql ± GNl ( BN2 )

¸ m a x
l:l=R+1;L

m a x
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1
Ql ± GNl ( T NQ±P )

= m a x
l:l=R+1;L

m a x
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1
e xp f¡N [D ( Q ± P kQ ± Gl ) + o( 1 ) ]g

= e xp f¡N[ m in
l:l=R+1;L

m in
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr)·E0¤2j1
D ( Q ± P kQ ± Gl ) + o ( 1 ) ]g:

A c c o r d in g t o t h e d e ¯ n it io n s o f t h e c o r r e s p o n d in g r e lia b ilit ie s we o b t a in t h e p r o o f o f t h e
t h e o r e m .

4 . S e c o n d S t a g e Te s t o f Two S t a g e s

A ft e r s e le c t in g a fa m ily o f P D s fr o m t h e t wo , it is n e c e s s a r y t o d e t e c t o n e P D in t h is fa m ily.
If t h e ¯ r s t fa m ily o f P D s is a c c e p t e d , we c o n s id e r t h e t e s t 'N2 ( x) wh ic h c a n b e d e ¯ n e d b y
t h e d ivis io n o f t h e s a m p le s p a c e B1 t o R d is jo in t s u b s e t s

C Nr
4
= fx : 'N2 ( x) = rg; r = 1 ; R:

L e t ®00ljr
³
'N2

´
b e t h e p r o b a b ilit y o f t h e e r r o n e o u s a c c e p t a n c e a t t h e s e c o n d s t a g e o f t h e t e s t ,

in wh ic h P D Gl is a c c e p t e d wh e n Gr is t r u e :

®00ljr
³
'N2

´ 4
= Ql ± GNr

³
C Nl

´
; r = 1 ; R; l = 1 ; L:

Th e p r o b a b ilit y t o r e je c t Gr, wh e n it is t r u e , is

®00rjr
³
'N2

´ 4
= Qr ± GNr

³
C Nr

´
=

RX

l=1; l 6=r
®00ljr

³
'N2

´
+ Qr ± GNr ( BN2 ) ; r = 1 ; R: ( 7 )

Th e c o r r e s p o n d in g r e lia b ilit ie s fo r t h e s e c o n d s t a g e o f t h e t e s t a r e d e ¯ n e d a s :

E00ljr ( '2 )
4
= lim in f

N !1

½
¡ 1

N
lo g ®00ljr

³
'N2

´¾
; r = 1 ; R; l = 1 ; L: ( 8 )

U s in g t h e p r o p e r t ie s o f t yp e s t h e fo llo win g e qu a lit ie s a r e d e r ive d fo r e a c h r = 1 ; R:

EI2jr
4
= lim

N !1

½
¡ 1

N
lo g

h
Qr ± GNr ( BN2 )

i¾

= in f
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr )>E0¤2j1
D ( Q ± P kQ ± Gr ) : ( 9 )

Fr o m ( 7 ) { ( 9 ) it fo llo ws t h a t

E00rjr ( '2 ) = m in

"
m in
l=1;R

E00ljr ( '2 ) ; E
I
2jr

#
; r = 1 ; R:



6 8 On LAO Two-stage Testing of Multiple Hypotheses Concerning Markov Chain

Remar k 1: If at the ¯rst stage the ¯rst family of P D s is accepted, when our decision
in the ¯rst stage is true, but we have an error in the second stage, the reliabilities of the
corresponding error probabilities are E00ljr, r; l = 1 ; R. W hen our wrong decision comes from

the ¯rst stage, the corresponding reliabilities are E00ljr, l = 1 ; R, r = R + 1 ; L.
In t h is c a s e t h e r e lia b ilit y m a t r ix fo r t h e s e c o n d s t a g e o f t h e t e s t E 00 ( '2 ) is t h e fo llo win g :

2
666666666666664

E001j1 E
00
2j1 : : : E

00
Rj1

E001j2 E
00
2j2 : : : E

00
Rj2

: : : : : : : : : : : :
E001jR E

00
2jR : : : E

00
RjR

E001jR+1 E
00
2jR+1 : : : E

00
RjR+1

E001jR+2 E
00
2jR+2 : : : E

00
RjR+2

: : : : : : : : : : : :
E001jL E

00
2jL : : : E

00
RjL

3
777777777777775

:

If t h e s e c o n d fa m ily o f P D s is a c c e p t e d , t h e n t h e t e s t 'N2 ( x) is a d ivis io n o f t h e s a m p le
s p a c e A2 t o L¡R d is jo in t s u b s e t s . Th e d e ¯ n it io n s o f e r r o r p r o b a b ilit ie s a n d t h e c o r r e s p o n d -
in g r e lia b ilit ie s a r e s im ila r t o t h e a b o ve c o n s id e r e d c a s e .

U s in g t h e p r o p e r t ie s o f t yp e s ( like in t h e p r o o f o f Th e o r e m 1 ) t h e fo llo win g e qu a lit ie s a r e
d e r ive d fo r e a c h l = R + 1 ; L:

EII2jl
4
= lim

N !1

½
¡ 1

N
lo g

h
Ql ± GNl ( BN1 )

i¾

= in f
Q±P : D(QkQr)<1; m in

r;r=1;R

D(Q±P kQ±Gr )·E0¤2j1
D ( Q ± P kQ ± Gl ) : ( 1 0 )

Remar k 2: If at the ¯rst stage, the second family of P D s is accepted, when our decision
in the ¯rst stage is true, but we have an error in the second stage, the reliabilities of the
corresponding error probabilities are E00ljr, r; l = R + 1 ; l. W hen our wrong decision comes

from the ¯rst stage, the corresponding reliabilities are E00ljr, l = R + 1 ; l, r = 1 ; R.
In t h is c a s e t h e r e lia b ilit y m a t r ix fo r t h e s e c o n d s t a g e o f t h e t e s t E 00 ( '2 ) is t h e fo llo win g :

2
666666666666664

E00R+1j1 E
00
R+2j1 : : : E

00
Lj1

E00R+1j2 E
00
R+2j2 : : : E

00
Lj2

: : : : : : : : : : : :
E00R+1jR E

00
R+2jR : : : E

00
LjR

E00R+1jR+1 E
00
R+2jR+1 : : : E

00
LjR+1

E00R+1jR+2 E
00
R+2jR+2 : : : E

00
LjR+2

: : : : : : : : : : : :
E00R+1jL E

00
R+2jL : : : E

00
LjL

3
777777777777775

:

In t h e fo llo win g t h e o r e m s we s h o w t h e o p t im a l d e p e n d e n c e o f r e lia b ilit ie s .
T heor em 3: If in the ¯rst stage the ¯rst family of P D s of M arkov chain is accepted,

then for the given positive and ¯nite values E001j1; E
00
2j2; :::; E

00
R¡1jR¡1, satisfying the following

compatibility conditions

0 < E001j1 < m in
r=2;R

[D ( Qr ± GrkQr ± G1 ) ] ;



E. Haroutunian, P. Hakobyan and A. Yesayan 6 9

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢
0 < E00rjr < m in [ m in

1·l<r
E00¤ljr ; m in

r<l·R
D ( Ql ± GlkQl ± Gr ) ; EI2jr]; 2 · r · R ¡ 1 ;

there exists a L AO sequence of tests '¤2, the elements of reliability matrix E
00 ( '¤2 ) = fE00¤ljsg

of which are positive and given as follows:

E
00¤
rjr

4
= E

00
rjr; r = 1 ; R ¡ 1 ; ( 1 1 )

E
00¤
ljr = in f

Q±P 2R 00
l

D ( Q ± P kQ ± Gr ) ; l = 1 ; R ¡ 1 ; r 6= l; r = 1 ; L; ( 1 2 )

E¤RjR = m in

"
m in

l=1;R¡1
E00ljR ( '2 ) ; E

I
2jR

#
; ( 1 3 )

where for l = 1 ; R ¡ 1 ,

R00l
4
= fQ±P : m in

l;l=1;R
D ( Q±P kQ±Gl ) · E02j1; D ( Q±P kQ±Gl ) · E00ljl; D ( QkQl ) < 1g; ( 1 4 )

R00R
4
= fQ ± P : m in

l=1;R
D ( Q ± P kQ ± Gl ) · E02j1; D ( Q ± P kQ ± Gl ) ¸ E00ljl; l = 1 ; R ¡ 1 g; ( 1 5 )

W hen even one of the compatibility conditions is violated, then at least one element of
the matrix E 00 ( '¤2 ) is equal to 0 .

T heor em 4: If in the ¯rst stage the second family of P D s of M arkov chain is accepted,
then for the given positive and ¯nite values E00R+1jR+1; E

00
R+2jR+2; :::; E

00
L¡1jL¡1 satisfying the

following compatibility conditions

0 < E00R+1jR+1 < m in
r=R+2;L

D ( Qr ± GrkQr ± GR+1 ) ;

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢
0 < E00rjr < m in

·
m in

R+1·l<r
E00¤ljr ; m in

r<l·L
D ( Ql ± GlkQr ± Gr ) ; EII2jr

¸
; R + 2 · r · L ¡ 1

there exists a L AO sequence of tests '¤2, the elements of reliability matrix E
00 ( '¤2 ) g of which

are positive and formulated as follows:

E
00¤
rjr

4
= E

00
rjr; r = R + 1 ; L ¡ 1 ; ( 1 6 )

E
00¤
ljr = in f

Q±P 2R 00
l

D ( Q ± P kQ ± Gr ) ; l = R + 1 ; L ¡ 1 ; l 6= r; r = 1 ; L; ( 1 7 )

E¤LjL = m in

"
m in

l=R;L¡1
E00ljL ( '2 ) ; E

II
2jL

#
; ( 1 8 )

where for l = R + 1 ; L ¡ 1 ,

R00l
4
= fQ±P : m in

r=1;R
D ( Q±P kQ±Gr ) > E02j1; D ( Q±P kQ±Gl ) · E00ljl; D ( QkQl ) < 1g; ( 1 9 )

R00L
4
= fQ±P : m in

r=1;R
D ( Q±P kQ±Gr ) > E02j1; D ( Q±P kQ±Gl ) ¸ E00ljl; l = R + 1 ; L ¡ R ¡ 1 g:

( 2 0 )
W hen even one of the compatibility conditions is violated, then at least one element of

the matrix E ( '¤2 ) is equal to 0 .
Th e p r o o fs o f Th e o r e m s 3 a n d 4 a r e s im ila r t o t h e p r o o f o f Th e o r e m 1 fr o m [1 5 ].



7 0 On LAO Two-stage Testing of Multiple Hypotheses Concerning Markov Chain

5 . Co m p a r is o n o f R e lia b ilit ie s o f Two -s t a g e Te s t W it h R e lia b ilit ie s o f On e -
s t a g e Te s t

In t h is s e c t io n we will c o m p a r e t h e r e lia b ilit ie s o f o n e s t a g e t e s t c o n s id e r e d in [1 5 ] a n d t h o s e
o f t h e t wo -s t a g e t e s t d e ¯ n e d in t h is p a p e r .

Fr o m t h e r e s u lt s o f t h e ¯ r s t a n d t h e s e c o n d s t a g e s we c a n o b t a in t h e ¯ n a l r e lia b ilit ie s
E

000
ljr ( ©) , l = 1 ; L. Fr o m R e m a r ks 1 a n d 2 it fo llo ws , t h a t wh e n c o m p a t ib ilit y c o n d it io n s in

Th e o r e m s 1 , 3 a n d 4 , a r e s a t is ¯ e d t h e n E
000
ljr ( ©) = E

00
ljr, l = 1 ; L.

Fo r c o m p a r is o n we will t a ke e qu a l d ia g o n a l e le m e n t s Eljl = E
000
ljl, l = 1 ; L ¡ 1 o f t h e

r e lia b ilit y m a t r ic e s o f o n e -s t a g e a n d t wo -s t a g e c a s e s .
Th e c o r r e s p o n d in g e le m e n t s o f t h e c o lu m n r = 1 ; R ¡ 1 S R + 1 ; L ¡ 1 o f o n e -s t a g e m a t r ix

a n d t wo -s t a g e m a t r ix a r e e qu a l. Th e e le m e n t s o f t h o s e c o lu m n s a r e fu n c t io n s o f d ia g o n a l
e le m e n t s o f t h e c o r r e s p o n d in g c o lu m n s a n d fo r m u la s o f t h o s e fu n c t io n s a r e t h e s a m e fo r t h e
o n e -s t a g e a n d t wo s t a g e t e s t s . W h e n we g ive t h e s a m e va lu e s t o d ia g o n a l e le m e n t s o f t h e
r e lia b ilit y m a t r ic e s o f t wo -s t a g e a n d o n e -s t a g e c a s e s , t h e va lu e s o f t h o s e fu n c t io n s a r e e qu a l.

Th e e le m e n t s o f R-t h a n d S-t h c o lu m n s o f t wo -s t a g e r e lia b ilit ie s m a t r ix c a n b e s m a lle r
o r g r e a t e r t h a n t h e c o r r e s p o n d in g e le m e n t s o f o n e -s t a g e m a t r ix.

Th e n u m b e r o f o p e r a t io n s fo r r e a liz a t io n o f t wo -s t a g e L A O t e s t is le s s t h a n t h a t o f o n e -
s t a g e L A O t e s t .

6 . Co n c lu s io n

In t h is p a p e r we c o n s id e r e d t wo -s t a g e m u lt ih yp o t h e s e s t e s t in g h a s a n y a d va n t a g e fo r Ma r ko v
c h a in . In t h is t e s t in g t h e s a m p le s e t is d ivid e d in t o R+2 o r L¡R+2 s u b s e t s , s o t h e p r o c e d u r e
o f t wo -s t a g e t e s t in g is s h o r t e r , t h a n o n e -s t a g e t e s t in g , in wh ic h t h e s a m p le s p a c e wa s d ivid e d
in t o L d is jo in t s u b s e t s . W e a ls o s h o w, t h a t t h e n u m b e r o f p r e lim in a r y g ive n e le m e n t s o f t h e
r e lia b ilit ie s m a t r ix in t wo -s t a g e a n d o n e -s t a g e t e s t s wo u ld b e t h e s a m e b u t t h e p r o c e d u r e o f
c a lc u la t io n s fo r t h e ¯ r s t o n e wo u ld b e s h o r t e r .

A s in [1 ] we c a n a ls o c o n s id e r t h e t wo -s t a g e L A O t e s t b y t h e p a ir o f s a m p le s x = ( x1; x2 ) 2
X N , x1 = ( x1; x2; : : : ; xN1 ) ; x1 2 X N1 ; x2 = ( xN1+1; xN1+2; : : : ; xN ) ; x2 2 X N2; N = N1+N2,
X N = X N1 £ X N2 . Th e ¯ r s t s t a g e u s in g t h e s a m p le x1 s e le c t s o n e o f t h e fa m ilie s P1 o r P2
a ft e r t h a t u s in g t h e s a m p le x2 t h e s e c o n d s t a g e s e le c t s o n e P D in t h is fa m ily.

A c kn o wle d g e m e n t

Th is wo r k wa s s u p p o r t e d in p a r t b y S CS o f ME S o f R A u n d e r Th e m a t ic P r o g r a m N o S CS
1 3 { 1 A 2 9 5 .

Refer ences

[1 ] E . H a r o u t u n ia n , P . H a ko b ya n a n d F. H o r m o z i n e ja d , \ On Two -s t a g e L A O t e s t in g o f
m u lt ip le h yp o t h e s e s fo r t h e fa m ilie s o f d is t r ib u t io n s " , International J ournal of Ststistics
and E conometrics M ethods, vo l. 2 , n o . 2 , p p . 1 2 7 { 1 5 6 , 2 0 1 3 .

[2 ] E . L . L e h m a n n a n d J. P . R o m a n o , Testing Statistical Hypotheses, Th ir d E d it io n .
S p r in g e r , N e w Y o r k, 2 0 0 5 .



E. Haroutunian, P. Hakobyan and A. Yesayan 7 1

[3 ] 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 " , Annals of
M athematical Statistics. vo l. 3 6 , p p . 3 6 9 { 4 0 1 , 1 9 6 5 .

[4 ] 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 " , Studia Scientiarum M athematicarum Hungarica, vo l. 6 ,
p p . 1 8 1 { 1 9 1 , 1 9 7 1 .

[5 ] G. Tu s n ¶a d y, \ On a s ym p t o t ic a lly o p t im a l t e s t s " , Annals of Statatistics, vo l. 5 , n o . 2 ,
p p . 3 8 5 -3 9 3 , 1 9 7 7 .

[6 ] G. Tu s n ¶a d y, \ Te s t in g s t a t is t ic a l h yp o t h e s e s ( a n in fo r m a t io n t h e o r e t ic a p p r o a c h ) " ,
P reprint of the M athematical Institute of the Hungarian Academy of Sciences, B u -
d a p e s t ( P a r t 1 , 1 9 7 9 , P a r t 2 , 1 9 8 2 ) .

[7 ] G. L o n g o a n d A . S g a r r o , \ 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 yp 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 ournal of Combinatorics, Information and
System Sciences, vo l. 5 , n o . 1 , p p . 5 8 -6 7 , 1 9 8 0 .

[8 ] L . B ir g ¶ e , \ V it e s s e s m a xim a ls d e d ¶ c r o is s 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 . V e r w. Ge b ie t e , vo l. 5 5 , p p . 2 6 1 { 2 7 3 , 1 9 8 1 .

[9 ] M. Fe d e r a n d N . Me r h a v, \ U n ive r s a l c o m p o s it h yp o t h e s is t e s t in g : a c o m p e t it it ve
m in im a x a p p r o a c h " , IE E E Transactions on Information Theory, vo l. 4 8 , n o . 6 , p p .
1 5 0 4 -1 5 1 7 , 2 0 0 2 .

[1 0 ] E . L e vit a n a n d N . Me r h a v, \ A c o m p e t it ive N e ym a n -P e a r s o n a p p r o a c h t o u n ive r s a l
h yp o t h e s is t e s t in g wit h a p p lic a t io n s " , IE E E Transactions on Information Theory, vo l.
4 8 , n o . 8 , p p . 2 2 1 5 -2 2 2 9 , 2 0 0 2 .

[1 1 ] 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 Transactions on Information Theory, vo l. 3 1 , n o . 3 , p p . 3 6 0 -3 6 5 ,
1 9 8 5 .

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

[1 3 ] E . H a r o u t u n ia n , M. H a r o u t u n ia n a n d A . H a r u t yu n ya 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 " , F oundations and Trends in
Communications and Information Theory, vo l. 4 , n o . 2 -3 , 2 0 0 8 .

[1 4 ] E . A . H a r o u t u n ia n , \ Ma n y s t a t is t ic a l h yp o t h e s e s : in t e r d e p e n d e n c e o f o p t im a l t e s t 's
e r r o r p r o b a b ilit ie s e xp o n e n t s " ( in R u s s ia n ) , Abstract of the report on the 3rd All-Union
school-seminar, \P rogram-algorithmical software for applied multi-variate statistical
analysis", Tsakhkadzor, P a r t 2 , p p . 1 7 7 { 1 7 8 , 1 9 8 8 .

[1 5 ] E . 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 ) ,
F irst W orld Congress of B ernoulli Society, vo l. 2 , n o . 3 , p p . 1 5 3 { 1 5 6 , 1 9 8 9 .

[1 6 ] 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 Ch a in " ( in R u s s ia n ) , 5-th International 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 7 ] E . H a r o u t u n ia n , \ R e lia b ilit y in m u lt ip le h yp o t h e s e s t e s t in g a n d id e n t ī c a t io n p r o b -
le m " , in D ata F usion for Situation M onitoring, Incident D etection, Alert and R espons
M anagement, NATO Science Series: Computer and System Sciences, IOS P r e s s , vo l.
1 9 8 , p p . 1 8 9 { 2 0 1 , 2 0 0 5 .

[1 8 ] E . H a r o u t u n ia n a n d P . H a ko b ya n , \ On m u lt ip le h yp o t h e s e s t e s t in g fo r m a n y in d e p e n -
d e n t o b je c t s " , VII International School-seminar \M ultidementional statistical analysis
and econometrics", p p . 7 8 ,7 9 , Ts a kh a d z o r , 2 0 0 8 .



7 2 On LAO Two-stage Testing of Multiple Hypotheses Concerning Markov Chain

[1 9 ] E . H a r o u t u n ia n a n d N . Gr ig o r ya n , \ On r e lia b ilit 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 " , Transactions of IIAP NAS R A, M athematical
P roblems of Computer Science, vo l. 2 9 , p p . 9 9 -9 6 , 2 0 0 7 .

[2 0 ] E . H a r o u t u n ia n a n d N . Gr ig o r ya n , \ On a r b it r a r ily va r yin g Ma r ko v s o u r c e c o d in g a n d
h yp o t h e s is L A O t e s t in g b y n o n -in fo r m e d s t a t is t ic ia n " , P roc. of IE E E Internatioan
Symposium Information Theory, S e o u l, S o u t h K o r e a , p p . 9 8 1 -9 8 5 , 2 0 0 9 .

[2 1 ] R . F. A h ls we d e 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
t e s t in g o f h yp o t h e s e s a n d id e n t i¯ c a t io n " , L ecture Notes in Computer Science, vol.
4123, \General Theory of Information Transfer and Combinatorics", S p r in g e r V e r la g ,
p p . 4 6 2 { 4 7 8 , 2 0 0 6 .

[2 2 ] E . A . H a r o u t u n ia n a n d P . M. H a ko b ya n , \ R e m a r ks a b o u t r e lia b le id e n t i¯ c a t io n o f
p r o b a b ilit y d is t r ib u t io n s o f t wo in d e p e n d e n t o b je c t s " , Transactions of IIAP of NAS
of R A, M athematical P roblems of Computer Science. vo l. 3 3 , p p . 9 1 { 9 4 , 2 0 1 0

[2 3 ] E . A . H a r o u t u n ia n , A . O. Y e s s a ya n a n d P . M. H a ko b ya n , \ On r e lia b ilit y a p p r o a c h
t o m u lt ip le h yp o t h e s e s t e s t in g a n d id e n t i¯ c a t io n o f p r o b a b ilit y d is t r ib u t io n s o f t wo
s t o c h a s t ic a lly c o u p le d o b je c t s " , International J ournal \Informations Theories and Ap-
plications", vo l. 1 7 , n o . 3 , p p . 2 5 9 { 2 8 8 , 2 0 1 0 .

[2 4 ] E . A . H a r o u t u n ia n a n d A . O. Y e s s a ya n , \ On r e lia b ilit y a p p r o a c h t o m u lt ip le h yp o t h e s e s
t e s t in g a n d t o id e n t ī c a t io n o f p r o b a b ilit y d is t r ib u t io n s o f t wo s t o c h a s t ic a lly r e la t e d
o b je c t s " , P roc. of IE E E Internation Sympos. Information Theory, S e in t -P e t e r b u r g ,
R u s s ia , p p . 2 6 7 1 -2 6 7 5 , 2 0 1 1 .

[2 5 ] E . A . H a r o u t u n ia n a n d L . N a va e i, \ On o p t im a l id e n t ī c a t io n o f Ma r ko v c h a in d is t r ib u -
t io n s s u b je c t t o t h e r e lia b ilit y c r it e r io n " , Transactions of IIAP NAS R A, M athematical
P roblems of Computer Science, vo l. 3 2 , p p .6 6 { 7 0 , 2 0 0 9 .

[2 6 ] L . N a va e i, \ On r e lia b le id e n t i¯ c a t io n o f t wo in d e p e n d e n t Ma r ko v c h a in d is t r ib u t io n s " ,
Transactions of IIAP NAS R A, M athematical P roblems of Computer Science, vo l. 3 2 ,
p p .7 4 { 7 7 , 2 0 0 9 .

Submitted 12.01.2014, accepted 07.03.2014.

سñÏáíÛ³Ý ßÕóÛÇ í»ñ³µ»ñÛ³É µ³½Ù³ÏÇ í³ñϳÍÝ»ñÇ
»ñÏ÷áõÉ È²ú ï»ëï³íáñáõÙ

º. гñáõÃÛáõÝÛ³Ý, ö. гÏáµÛ³Ý ¨ ². ºë³Û³Ý

²Ù÷á÷áõÙ

¸Çï³ñÏí»É ¿ ³ÝóáõÙ³ÛÇÝ µ³ßËáõÙÝ»ñÇ »ñÏáõ ÁÝï³ÝÇùÝ»ñáí µÝáõó·ñíáÕ
سñÏáíÛ³Ý ßÕóÛÇ í»ñ³µ»ñÛ³É µ³½Ù³ÏÇ íÇ׳ϳ·ñ³Ï³Ý í³ñϳÍÝ»ñÇ ëïáõ·Ù³Ý
·áñÍÁÝóóÁ: àõëáõÙݳëÇñí»É ¿ »ñÏáõ ÷áõÉ»ñÇ Éá·³ñÇÃÙáñ»Ý ³ëÇÙïáïáñ»Ý ûåïÇÙ³É
ï»ëï³íáñÙ³Ý ë˳ÉÝ»ñÇ Ñáõë³ÉÇáõÃÛáõÝÝ»ñÇ Ù³ïñÇóÁ ¨ ³ÛÝ Ñ³Ù»Ù³ïí»É ¿ Ùdz÷áõÉ
ï»ëïÇ Ñáõë³ÉÇáõÃÛ³Ý Ù³ïñÇóÇ Ñ»ï: òáõÛó ¿ ïñí»É, áñ »ñÏ÷áõÉ ï»ëïÁ å³Ñ³ÝçáõÙ ¿
³í»ÉÇ ùÇã ·áñÍáÕáõÃÛáõÝ, ù³Ý Ùdz÷áõÉ ï»ëïÁ:



E. Haroutunian, P. Hakobyan and A. Yesayan 7 3

Î äâóõýòàïíîì ËÀÎ òåñòèðîâàíèè ìíîãèõ ãèïîòåç
îòíîñèòåëüíî Ìàðêîâñêîé öåïè

Å. Àðóòþíÿí, Ï. Àêîïÿí è À. Åñàÿí

Àííîòàöèÿ

Ðàññìîòðåíî òåñòèðîâàíèå öåïè Ìàðêîâà õàðàêòåðèçóþùåéñÿ äâóìÿ ñåìåéñò-
âàìè âîçìîæíûõ ïåðåõîäíûõ âåðîÿòíîñòåé. Ìàòðèöà íàäåæíîñòåé ëîãîðèôìè-
÷åñêè àñèìïòîòè÷åñêè îïòèìàëüíîãî òåñòèðîâàíèÿ â äâà ýòàïà èçó÷åíà è
ñðàâíåíà ñî ñëó÷àåì àíàëîãè÷íîãî îäíîýòàïíîãî òåñòèðîâàíèÿ. Ïîêàçàíî, ÷òî
äâóõýòàïíîå òåñòèðîâàíèå òðåáóåò ìåíøüå îïåðàöèè, ÷åì îäíîýòàïíîå.