D:\User\sbornik_38_pdf\25.DVI


Mathematical Problems of Computer Science 38, 61{65, 2012.

M any H ypotheses P ar allel Distr ibuted Detection of

the P air of Families of P r obability Distr ibutions

Fa r s h in H o r m o z i n e ja d 1 a n d E vg u e n i H a r o u t u n ia n 2

1Islamic Azad University, Ahvaz Branch, Iran
2Institute for Informatics and Automation Problems, NAS of RA

e-mails: hormozi-nejad@iauahvaz.ac.ir, evhar@ipia.sci.am

1 In t r o d u c t io n

Th e r e is a c o n s id e r a b le lit e r a t u r e o n t h e p r o b le m s o f d is t r ib u t e d d e t e c t io n a n d d e c is io n
in e n g in e e r in g c o n t e xt s [4 , 5 , 6 ]. Th e d e c e n t r a liz e d o r d is t r ib u t e d d e t e c t io n p r o b le m wa s
¯ r s t fo r m u la t e d a n d s t u d ie d b y Te n n e y a n d S a n d e ll [7 ]. It c o n s is t s o f N g e o g r a p h ic a lly
d is p e r s e d s e n s o r s , o n e -wa y c o m m u n ic a t io n lin ks , a n d a fu s io n c e n t e r . E a c h s e n s o r m a ke s
a n o b s e r va t io n ( d e n o t e d b y Xi; i = 1 ; N ) o f a r a n d o m s o u r c e , qu a n t iz e s Xi in t o a n M -a r y
m e s s a g e Ui = gi ( Xi ) , a n d t h e n t r a n s m it s Ui; i = 1 ; N t o t h e fu s io n c e n t e r . U p o n r e c e ip t
o f U1; U2; :::; UN t h e fu s io n c e n t e r m a ke s a g lo b a l d e c is io n U0 = D ( U1; U2; :::; UN ) a b o u t t h e
n a t u r e o f t h e r a n d o m s o u r c e . Th e m e s s a g e s U1; U2; :::; UN a r e a ll t r a n s m it t e d t o t h e fu s io n
c e n t e r wh ic h d e c la r e s h yp o t h e s is Hi; i = 1 ; N t o b e t r u e , b a s e d o n a d e c is io n r u le D.

H a r o u t u n ia n [1 ] in ve s t ig a t e d t h 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 s t a t is t ic a l h yp o t h e -
s e s . Th e m o d e l o f t h e t wo -s t a g e L A O t e s t in g in m u lt ip le h yp o t h e s e s fo r a p a ir o f fa m ilie s o f
d is t r ib u t io n s is in ve s t ig a t e d in [2 , 3 ]. In t h is p a p e r t h e p r o b le m o f p a r a lle l d is t r ib u t e d d e t e c -
t io n o f t wo -s t a g e m u lt ip le h yp o t h e s e s L A O t e s t in g t o d e t e c t b e t we e n h yp o t h e s e s c o n s is t in g
o f t h e p a ir fa m ilie s o f p r o b a b ilit y d is t r ib u t io n s ( P D s ) is s t u d ie d .

E a c h s e n s o r o b s e r va t io n x t a ke s va lu e s in t h e s e t X . A d e t e r m in is t ic M -a r y qu a n t iz e r is a
m e a s u r a b le m a p p in g g fr o m t h e o b s e r va t io n s p a c e X t o t h e m e s s a g e s p a c e U = f1 ; 2 ; :::; Mg.
R a n d o m va r ia b le ( R V ) X c h a r a c t e r iz in g t h e s t u d ie d o b je c t t a ke s va lu e s in t h e s e t X a n d
P ( X ) is t h e s p a c e o f a ll d is t r ib u t io n s o n X . Th e r a n d o m s o u r c e h a ve S h yp o t h e t ic a l p r o b -
a b ilit y d is t r ib u t io n s ( P D s ) o f X t h a t d ivid e d in t wo d is jo in t fa m ilie s o f d is t r ib u t io n s . Th e
¯ r s t fa m ily in c lu d e s R h yp o t h e s e s P1; P2; :::; PR a n d t h e s e c o n d fa m ily c o n s is t s o f S ¡ R
h yp o t h e s e s PR+1; PR+2; :::; PS. Th e d is t r ib u t io n o f X u n d e r h yp o t h e s e s Hi is d e n o t e d b y
Pi; i = 1 ; N. Th e d is t r ib u t io n s o f t h e m e s s a g e p r o d u c e d b y g a r e d e n o t e d b y Pi(g), a n d it is
o b t a in a b le fr o m Pi a n d g.

2 Th e On e -s t a g e L A O Mu lt ih yp o t h e s e s Te s t in g o f D is t r ib u t e d D e t e c t io n

W e c a ll t h e p r o c e d u r e o f m a kin g d e c is io n o n t h e b a s e o f N-s a m p le t h e t e s t ÁN wh e n it is
o n e -s t a g e . Th e s t a t is t ic ia n m u s t d e t e c t o n e a m o n g S h yp o t h e s e s . W e s t u d y t h e p r o b a -

b ilit ie s 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 h yp o t h e s is Hl p r o vid e d t h a t Hs is t r u e ®ljs ( Á
N )

4
=

6 1



6 2 Many Hypotheses Parallel Distributed Detection of the Pair of Families of PDs

P Ns ( U0 = l ) ; l; s = 1 ; S; l 6= s a n d if t h e h yp o t h e s is Hs is t r u e , b u t it is n o t a c c e p t e d , t h e n
t h e p r o b a b ilit y o f e r r o r is ®sjs ( Á

N )
4
= P Ns ( U0 6= s) =

P
l 6=s ®ljs ( Á

N ) ; s = 1 ; S: Co 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 o f t e s t s Á a s fo llo ws :

Eljs ( Á)
4
= lim s u p

N !1
f¡ 1

N
lo g ®ljs ( Á

N ) g; l; s = 1 ; S:

Fo r c o n s t r u c t io n o f t h e n e c e s s a r y L A O t e s t fo r p r e lim in a r ily g ive n p o s it ive va lu e s
E1j1; :::; ES¡1jS¡1, we d e ¯ n e :

Rs
4
=

n
Q : D ( QjjPs(g) ) · Esjs

o
; s = 1 ; S ¡ 1 ; RS

4
=

n
Q : D ( QjjPs(g) ) > Esjs; s = 1 ; S ¡ 1

o
;

E¤sjs
4
= Esjs; s = 1 ; S ¡ 1 ; E¤ljs

4
= in f

Q:D(QjjPl( g ) )·E¤ljl
D ( QjjPs(g) ) ; l; s = 1 ; S; s 6= l; E¤SjS

4
= m in

l 6=S
E¤ljs:

( 1 )
If a ll d is t r ib u t io n s Ps; s = 1 ; S, a r e d i®e r e n t s u c h t h a t t h e fo llo win g in e qu a lit ie s h o ld

E1j1 < m in
l=2;S

D ( Pl(g)jjP1(g) ) ; Esjs < m in
"

m in
l=1;s¡1

E¤ljs; m in
l=s+1;S

D ( Pl(g)jjPs(g) )
#
; s = 2 ; S ¡ 1 ;

( 2 )
t h e n t h e r e e xis t s a LAO s e qu e n c e o f t e s t s , a ll e le m e n t s o f t h e r e lia b ilit ie s m a t r ix E ¤ = fE¤ljsg
o f wh ic h a r e p o s it ive a n d a r e d e ¯ n e d in ( 1 ) .

W h e n o n e o f t h e in e qu a lit ie s ( 2 ) is vio la t e d , t h e n a t le a s t o n e e le m e n t o f t h e m a t r ix E ¤

is e qu a l t o z e r o .

3 Th e Two -s t a g e L A O Te s t in g o f D is t r ib u t e d D e t e c t io n

S u p p o s e N = N1 + N2 b e s u c h t h a t N1 = dÃNe; N2 = [( 1 ¡ Ã ) N]; 0 < Ã < 1 ; a n d
x = ( x1; x2 ) ; x 2 X N ; X N = X N1 £ X N2: A n d we h a ve ve c t o r s o f m e s s a g e s a s u =
( u 1; u 2 ) ; u 2 U N ; U N = U N1 £ U N2 : Th e t wo -s t a g e t e s t o n t h e b a s e o f N-s a m p le we d e n o t e
b y ©N = ( 'N11 ; '

N2
2 ) is t h e p a r a lle l d is t r ib u t e d d e t e c t io n s ys t e m d e p ic t e d in Fig u r e 1 . Th e

¯ r s t s t a g e is fo r c h o ic e o f a fa m ily o f P D s , it is e xe c u t e d b y a n o n -r a n d o m iz e d t e s t 'N11 ( u 1 )
u s in g m e s s a g e s s a m p le u 1. Th e n e xt s t a g e is a n o n -r a n d o m iz e d t e s t '

N2
2 ( u 2; U

0 ) b a s e d o n
m e s s a g e s s a m p le u 2 a n d t h e o u t c o m e o f t h e ¯ r s t fu s io n c e n t e r U

0.
Fir s t s t a g e o f t wo -s t a g e t e s t in g o f d is t r ib u t e d d e t e c t io n is a s fo llo ws :

L e t u s in t r o d u c e t wo s e t s o f in d ic e s D1 = f1 ; Rg a n d D2 = fR + 1 ; Sg a n d a p a ir o f d is jo in t
fa m ilie s o f P D s a r e P1 = fPs; s 2 D1g a n d P2 = fPs; s 2 D2g:

L e t ®0ijj ( '
N1
1 ) ; i 6= j; i; j = 1 ; 2 ; 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

i-t h fa m ily o f P D s p r o vid e d t h a t t h e j-t h fa m ily o f P D s 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 j-t h fa m ily)

®0ijj ( '
N1
1 )

4
= m a x

s2D j
P N1s ( U

0 = i ) ; i 6= j; i; j = 1 ; 2 :

W e c o n s id e r r e lia b ilit ie s o f t h e in ¯ n it e s e qu e n c e o f t e s t s

E0ijj ( '1 )
4
= lim s u p

N1!1

n
¡ 1

N1
lo g ®0ijj ( '

N1
1 )

o
; i; j = 1 ; 2 :

T heor em 1. If all distributions Ps; s = 1 ; S, are di®erent and the positive values E
0¤
1j1; is

such that
E

0¤
1j1 < m in

s2D 1; l2D 2
D ( Pl(g)jjPs(g) ) ;



F. Hormozi nejad and E. Haroutunian 6 3

another element of the reliabilities matrix E
0¤
2j2 of which de¯ned as follows:

E
0¤
2j2 < m in

s2D 2
in f

Q: m in
l2D 1

D(QjjPl( g ) )·E
0¤
1j1

D ( QjjPs(g) ) :

Fig u r e 1 : Th e t wo -s t a g e m u lt ip le h yp o t h e s e s d is t r ib u t e d d e t e c t io n s ys t e m

S e c o n d s t a g e o f t h e t wo -s t a g e t e s t in g o f d is t r ib u t e d d e t e c t io n is a s fo llo ws :
Th e t e s t 'N22 ( u 2; U

0 ) c a n b e d e ¯ n e d b y u s in g t h e ¯ r s t fu s io n c e n t e r U0 a n d t h e t h e s e c o n d
m e s s a g e s s a m p le u 2. Th e p r o b a b ilit y o f t h e fa lla c io 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 e s t
o f P D Pl, wh e n Ps is c o r r e c t a n d i-t h fa m ily o f P D s is a c c e p t e d , is

®00ljs ( '
N2
2 )

4
= P N2s ( U

00 = ljU0 = i) ; l 6= s; i = 1 ; 2 ; l 2 Di:

Th e p r o b a b ilit y t o r e je c t Ps, wh e n it is t r u e a n d i-t h fa m ily o f P D s is a c c e p t e d , is

®00sjs ( '
N2
2 )

4
= P N2s ( U

00 6= sjU0 = i) =
X

l 6=s
®00ljs ( '

N2
2 ) ; s 2 Di; i = 1 ; 2 :

Co 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 e s t , a r e

E00ljs ( '2 )
4
= lim s u p

N2!1

n
¡ 1

N2
lo g ®00ljs ( '

N2
2 )

o
; l; s = 1 ; S:

T heor em 2. If at the ¯rst stage of test the ¯rst family of P D s is accepted, then for given pos-
itive and ¯nite values E00sjs, s = 1 ; R ¡ 1 of the reliabilities matrix E 00 ( '2 ) , let us investigate
the regions:

R00s =
n
Q : D

³
Q k Ps(g)

´
· E00sjs

o
; s = 1 ; R ¡ 1 ; R00R =

n
Q : D

³
Q k Ps(g)

´
> E00sjs; s = 1 ; R ¡ 1

o
;



6 4 Many Hypotheses Parallel Distributed Detection of the Pair of Families of PDs

and the following values of elements of the future reliabilities matrix E 00 ( '¤2 ) of the L AO test
sequence:

E00¤sjs = E
00
sjs; s = 1 ; R ¡ 1 ; E00¤ljs = in f

Q2R 00
l

D
³
Q k Ps(g)

´
; l; s = 1 ; R; l 6= s; E¤RjR

4
= m in

l 6=R
E¤ljR;

W hen the following compatibility conditions are valid

E001j1 < m in
s=2;R

D ( Ps(g) k P1(g) ) ; E00sjs < m in [ m in
l=1;s¡1

E00¤ljs ; m in
l=s+1;R

D ( Pl(g) k Ps(g) ) ]; 2 · s · R¡ 1 ;

then there exists a L AO sequence of test '¤2, elements of reliabilities matrix E
00 ( '¤2 ) of which

are de¯ned above and are positive.
E ven if one of the compatibility conditions is violated, then E 00 ( '¤2 ) has at least one ele-

ment equal to zero.

If in t h e ¯ r s t s t a g e o f t e s t , 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 fo r S ¡ R ¡ 1
g ive n p o s it ive va lu e s E00sjs, s = R + 1 ; S ¡ 1 o f r e lia b ilit ie s m a t r ix E 00 ( '¤2 ) , t h e p r o c e d u r e is
a n a lo g o u s .
R e lia b ilit ie s a n d e r r o r p r o b a b ilit ie s o n t h e t wo -s t a g e t e s t in g o f d is t r ib u t e d d e t e c t io n a r e in
c o m in g :

®000ljs ( ©
N )

4
= P Ns ( U

00 = l ) ; l; s = 1 ; S; l 6= s; ®000sjs ( ©N )
4
= P Ns ( U

00 6= s) =
X

l 6=s
®000ljs ( ©

N ) ; s = 1 ; S;

E000ljs ( ©)
4
= lim s u p

N!1
f ¡ 1

N
lo g ®000ljs ( ©

N ) g; l; s = 1 ; S:

S o we c a n c o n s id e r e r r o r p r o b a b ilit ie s a s fo llo ws

®000ljs ( ©
¤N ) = P N1s ( U

0 = i ) ¢ P N2s ( U 00 = ljU0 = i) ; l; s 2 Di; i = 1 ; 2 ( 3 )

®000ljs ( ©
¤N ) = P N1s ( U

0 = j ) ¢ P N2s ( U00 = ljU0 = j ) ; s 2 Di; l 2 Dj; i; j = 1 ; 2 ; i 6= j ( 4 )
A c c o r d in g t o ( 3 ) { ( 4 ) a n d d e ¯ n it io n o f r e lia b ilit ie s we o b t a in

E000ljs ( ©
¤ ) = ( 1 ¡ Ã ) E00¤ljs ; l; s 2 Di; i = 1 ; 2 ;

E000ljs ( ©
¤ ) = ÃEIjjs + ( 1 ¡ Ã ) E00¤ljs ; s 2 Di; l 2 Dj ; i; j = 1 ; 2 ; i 6= j;

E000sjs ( ©
¤ ) = m in

l 6=s
E000ljs ( ©

¤ ) ; s 2 Di; i = 1 ; 2 :

W e c h a r a c t e r iz e t h e o p t im a l e r r o r e xp o n e n t s in a p a ir o f s t a g e s a n d we p r o vid e c o m p a t ib ilit y
c o n d it io n s fo r t h is t o h a p p e n a n d it is in ve s t ig a t e d d e s c r ip t io n o f c h a r a c t e r is t ic s o f L A O
h yp o t h e s e s t e s t in g o f d is t r ib u t e d d e t e c t io n a n d t h e g o a l is t o m a ke a d e c is io n o n t h e m a n y
p o s s ib le h yp o t h e s e s , b a s e d o n t h e m e s s a g e s r e c e ive d a t t h e fu s io n c e n t e r s .



F. Hormozi nejad and E. Haroutunian 6 5

R e fe r e n c e s

[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 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 s 5 -6 , p p . 4 1 3 -4 2 1 ,
1 9 9 0 .

[2 ] H a r o u t u n ia n E .A ., H a ko b ya n P .M. a n d H o r m o z i n e ja d F. \ On t wo -s t a g e 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 m u lt ip le h yp o t h e s e s c o n c e r n in g d is t r ib u t io n s fr o m t h e
p a ir o f fa m ilie s ." Transactions of IIAP of NAS of R A and of YSU, M athematical P roblems
of Computer Science, vo l. 3 7 , p p . 3 4 -4 2 , 2 0 1 2 .

[3 ] H o r m o z i n e ja d F., H a r o u t u n ia n E .A . a n d H a ko b ya n P .M. \ On 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 p a ir o f fa m ilie s o f d is t r ib u t io n s ." P roceeding of the Conference \Com-
puter Science and Information Technologies", Y e r e va n , A r m e n ia , p p . 1 3 5 -1 3 8 , 2 0 1 1 .

[4 ] Ts it s iklis J. N . a n d A t h a n s M., On t h e c o m p le xit y o f d e c e n t r a liz e d d e c is io n m a kin g a n d
d e t e c t io n p r o b le m s , IE E E Tr a n s . Automat. Contr., vol. ACT30, p p . 4 4 0 -4 4 6 ; 1 9 8 5 .

[5 ] Ts it s iklis J. N ., D e c e n t r a liz e d d e t e c t io n b y a la r g e n u m b e r o f s e n s o r s ,M ath. Contr., Sig-
nals, Syst., vo l. 1 , n o . 2 , p p . 1 6 7 -1 8 2 , 1 9 8 8 .

[6 ] K r e id l O. P ., Ts it s iklis J. N ., a n d Zo u m p o u lis S . I. On d e c e n t r a liz e d d e t e c t io n wit h p a r t ia l
in fo r m a t io n s h a r in g a m o n g s e n s o r s " . IE E E Transactions on Signal P rocessing, vo l. 5 9 ,
N o . 4 , A p r il 2 0 1 1 .

[7 ] Te n n e y R . R . a n d S a n d e ll N . R ., D e t e c t io n wit h d is t r ib u t e d s e n s o r s , IE E E Trans. Aerosp.
E lectron. Syst., vo l. 1 7 , p p . 5 0 1 -5 1 0 , 1 9 8 1 .