Ann. Univ. Ferrara - Sez. VII - Sc. Mat. Vol. XXV, 63-68 (1979)

L'op6ration d'61agage.

CARLO S E M P I (*)

L'opdra.tion d '6lagage a 6t6 in t rodui te dans [1]. Elle consiste en l'61i- ruination d 'un des r6sultats possibles d 'un exp6riment et, par cons6quent en ]a modification des probabi]it6s de t o u s l e s autres r~sultats. Toutefois pour l 'applie~tion aux questionnaires ([2]), on ~ int6r~t s 6tudier une op6ra- tion d 'glagage p,~rtiel. Celle-ei sera d6finie comme 1~ suppression d 'une r6ponse et la r6a t t r ibut ion des probabil i tds des seules rdponses s la m6me question ( l 'aseendant imm6dia t de la r6ponse supprim6e).

Or si F ~ : = {(ql, q2 , . . . ,q~) :q > 0 (i = l , 2, ..., n), ~ q ---- 1} est la fa- i = l

mille des dis t r ibut ions de probabili[6 n-aires completes et si H~:_P=--~ R (n = 2, 3, ...) est une famille d 'entropies, la propri6t6 d'~lagage se t radui t par l 'in6galit6

H~(p~/p, p.Jp, ..., p,~/p)<H,,+~(p~, P2, ..., P~,, P~+~)

off p = 1 - - p~+~, pour chaque dis t r ibut ion (p~, P2, ..., P~+I) ~/~n+l.

Ds On dira que la suite d'entropies H,~: F , -~ R (n = 2 ,3 , ...) $ jouit de la propridtd d'dlagage d'ordre k oit k ~ 2 , s'il y a une suite {P,},,=~,k+l ....

avec p* ~]0, 1], tdle que pour tout n > k soit satis/aite l'in@alitg

P -- q P - - q q., 1 - - p ) - - H . ( q l , q . . , . . . , q . ) > O (1) H.+~ q~,q2 , . . . ,q~ ._ l , i~__qq, . , . . . ,1 q

k--1 oi~ (ql, q~, . - , q,) e F , , q = ~ q et ole Ies paramdtres p e t q sont assujettis

i ~ 1

aux conditions 0 <q < p * < p < 1 ( n > k).

(*) Indirizzo dell'autore: Istituto di Matematica dell'Universith, 73100 Lecce.

6 4 CARLO S E M I q

1. - L ' ~ l a g a g e d'ordre k p o u r l ' entropie de S h a n n o n .

~Nous nous proposons d 'abord de rechercher des conditions qui en- t ra inent que l 'entropie de Shannon

H , ( p l , P2~ ..., P,) = -- p logp~ i = k

(Pl, P2, ..., p , ) ~ F n satisf~sse s la propri~t~ d%l~gage d 'ordre k. L 'on dolt alors ~tudier la difference

/ ~ q H.+l [ql, q~, ..., qk-1, q~, . . . , (2) s -- P -- q

1 - - q - - q ) - - - - q . , 1 - - p - - H ~ q l , q 2 , . . . , q .

1 - - p ~ .q , l o g q , - - ( p - - q ) log p - q - - ( 1 - p ) l o g ( 1 - p ) . 1 -- q~-k -- q

L'in~galit4 de Shannon ([13]) appli~e ~ la distr ibution de probabilit~ incomplb~te (q~, q ~ , ..., q.) donne

(3) - - ~ q, log q ,> log (1 - - q) - - l og (n - - k ~- 1 ) .

I1 d6coule de (2) et de (3) que pour chaque distr ibution (q~, q2, ..., q.) ~ F . k--1

avec q ~- ~, q, donn6 en [0, 1[ on a i=1

H.+I ql, q~, -.., qk-1, p -- q P -- q T-~--q qk, "" , l __ q

>i(1 P - - q ) - - 1 qq l o g ( I - - q ) - - -

- ( l - - p ) l o g ( l - - p ) .

S - - q , , 1 - - p - - H~(q l , q~., . . . ,q~)>~

1 P log(n- - k ~- 1 )-- (p - -q ) log(p- - q) +

l - - q

On peut donc ~,noncer le suivant

TH~0R~ME 1. ~i ]in que l 'entropie de Shannon jouisse de la propridtd k - - I

d'e'lagage d'ordre k pour chaque distribution (ql, q2, ..., q.) ~ F . avec q ~ ~. qi donnd en [0, 1[ il faut et il su]]it que soit satis]aite l'indgaZit~ ~-1

(4) f(p) > 0

L'OP]~RATIO~N D' I~,LAG AGUE 65

ole la /onction ]: [q, 1] ~ R est dd/inie par

( (5) ] ( x ) : = l - - q ] - - _ log ( 1 - - q) - - l ~ l o g ( n - - k 4- 1) q-

- - ( x - - q ) log (x -- q ) - - ( 1 - x) l o g ( 1 - - x ) .

II fuudra alors 5 tud ie r la fonct ion ] que l ' on v i en t de d~finir. On a d ' a b o r d ](q)~ 0 et ](l) = 0. Lu d~riv~e de ] es t donn~e p a r

l ' (x)

L' in~gal i t5

(6)

~qu ivau t g Fau t r e

ou bien

q log ( 1 - - q ) q- 1 l o g ( ~ t - - k , ~ - l ) + l o g l - - x 1 - - q 1 - - q x - - q "

l ' (x) > o

(~ - q)l ' (x) = l o g / (1 - q ) ( \ ~ - q ]

(1 - - x ) / ( x - q) > ( ( 1 - q)~/(n - - k -F 1)} ~(~-~ �9

0 ;

E n posun t v :---- ((1 - - q)~/(n-- k ~- 1)} '~(~-') e t en d~finissant ~: ]q, l] -> R e p~r q~(x):--~ ( l - x) / (x - -q ) , on r4condu i t l 'S tude de l ' in~gulit~ (6) s eelui de l u s u i v u n ~ : ~ ( x ) > v. Or il es t fa.cile de v~rifier que

l im ~(x) = -~- o o , F(1) = 0 e t ~0'(x) --- -- (1 -- q ) / ( x - q)'-< O.

11 suftit m u i n t e n a n t d ' o b s e r v e r que r e s t pos i t ive e t que ~ es t con t inue p o u r ~tabl i r que, p o u r t ou t q E ]0, 1] donn~, il y u un, e t un seul, n o m b r e Xo ~ ]q, ] ] tel que ~(x0) ---- v (d 'a i l leurs xo - - (1 ~ qv)/(l -{- ~)) e t que, p a r con- s~.quent, l ' inSgali t4 F ( x ) > v - - e t donc l~inSgalit~ qui lui ~ q u i v a u t - - es t sa t i s fa i te pa r x :> (1 -t- q~)/(1 -F v). L a fonc t ion f es t alors c ro issante en [q, (1 ~- qv)/(1 Jr- v)] e t d5croissante en ](1 ~- q~,)/(1 -F ~), 1], ][(1 ~- qv)/(1 ~ v)] es t lu va leu r m a x i m u m de ] en [q, 1]; de plus elle es t pos i t ive . I1 y u donc un e t un seul n o m b r e r~el p* duns F i n t e r v a l Jq, (1 -F qv)/(1 ~- v)[ tel que ](p*) 0. Ainsi p e u t - o n ~ff i rmer que ](x)>~O pour ~ p . .

I l est enfin uis5 de receuill ir les r4su l tu t s ob tenus au m o y e n du su iv~nt

Tm~O~]~ME 2. ]~tant donnd q e[O, l [ , l'entropie de Shannon satis]ait d l'indgalitd (1) d'e'lagage d'ordre k pour chaque distribution de probabilitg corn-

66 CARLO S E M P I

plate (q,, q~, ..., q~) e F~ telle que q~ ~ q~ 4- ... ~- q,_, = q et pour tout p > p * . L'entropie de t t a r t l ey

(7) H~(p~, p~, ..., p,,) = log A~

off A~ ') est le nombre des 51~ments de ~ = (p~, p, , ..., p ~ ) e F , qui different de z~ro, satisfait g l'in~g~lit4 (1) s i p > q (car pour p = q, l'in4galit~ (1) peut 6tre fausse si q~ r 0). Les entropies H . : F~--> R d~finies par

(8) H,(p~, P2, . . . , P , ~ ) = aH~(p~, p~, ..., p ,) -+- b log vV(ff)

avec a, b>0 jouissent alors de la propri6t6 d'6lagage d'ordre k pour p > p * (n> k).

2 . - T h ~ o r ~ m e s de c a r a c t ~ r i s a t i o n .

Le but de cette section-ci est de rechercher lesquelles parmi les entro- pies additives et subadditives ([4]) jouissent de la propri~t~ d'~lagage d'ordre k.

Soit F~' l 'in%rieur de F . , savoir

F ' = ((ql, q 2 , . . . , q ~ ) : q , > O ( i = l , 2 , . . . , n ) , ~q~----1} . i=1

Tm~oR]~:~ 3. Si la suite d'entropies H~: F"--> R jouit des propridt& de subadditivitd, d'additivitd, de symdtrie, d'glagage d'ordre k pour p > q et de la normalisation H2(�89 1 ) ~ 1, alors, et seulement alors, les entropies de la suite ont la repr&entation

H.(ql , q2, ..., q.) = logn

pour ehaque (ql, q~, ..., q.) e F'. (n>k) .

D~iMONSTRATION. Lu subadditivitS, l 'additivit5 et la sym~trie entrafnent ( oir [4])

H.(qL, q~, ..., q~) = att~(q,, q2, ..., q.) ~- A(n)

off A est une fonction compl~tement additive d~finie sur les naturels, savoir A(mn) = A(m) -~ A(n) (m, n > k ) et a > 0 . Or comme la difference au premier membre de l'in~galit~ (1) est plus grand (ou ~gal) que a/(p) ~ A (n ~ 1) --A(n), on doit ~tudier l'in~galit4

a 1 ( p ) + A ( n + l ) - - A ( n ) > O p eJq, 1]

L ' O P ] ~ R A T I O N D ' I ~ , L A G A G E 6 7

ou puisque inf {a](p}: p ~ ]q, 1]] = aq log ( 1 - q) -- log (n -- k ~- 1), l'inSgalit~

suivante

(9) A ( n -~ 1) -- A ( n ) > a l o g ( n - - k + 1)-- aq log (1 - - q).

L'in4g~lit~ ci-dessus montre que l 'on doit avoir a----0, cur, si a > 0, il d6eouleruit de (9) que lim inf {A(n ~- 1) -- A(n)] ---- ~ ~ ; en p~rticulier

n--> oa

lim inf {A(n ~- 1) -- A(n)} > 0 et un lemme de K~tui ([5]) donner~it A(n ) -~ n---> co

----blogn (b>~O,n>k) . Muis alors (9) est impossible ~vec a > 0 . Donc a -= 0; dans ce cus-l~ on ~ A(n -~ 1)>A(n) et un th~or~me bien connu ([6]) donne A(n) -= b log n. C.Q.F.D.

Si l 'on pose

P - - q P - - q 1 p~- (10) ~ ( n ) : = inf p e ] O , 1 ] : a H ~ + ~ q ~ , q ~ , . . . , q ~ _ ~ , ~ q~, . . . , 1 - - q q ' ' --

- - aH~(q~, q~, . . . , q~) ~- A ( n ~- l ) -- A ( n ) > O } (n>k)

les th~or~mes suivunts peuvent ~tre prouv6s de 1~ m~me mnni~re que les r4sultuts correspondents dans 1.

Tn-s 4. L a l imite de q:~(n) pour n qui tend ~ l ' in f in i existe et l 'on a

l im ~ (n ) ~ 0 ou bien lim ~ ( n ) = ]. n---> co n-->r

Tm~OR~I~E 5. L'indgali td

o{(1_ q ~ P - - q) l og (1 - -q ) 11_q-- p l o g ( n - - k -k 3) - - (p - - q) l o g ( p - - q) - -

- - (1 - - p) l o g (1 - - p ) } q - b log (n ~- 1) - - b l o g n > O

o4 a, b > 0, eat v&i/ ide par chaque dis tr ibut ion de probabilitd (ql, q2 , ... , q,) E P;

et par tout p ~ ]~k(n), 1]. Le r6sult~t suiv~nt est m~intennnt 6vident. ]1 ~m61iore 1~ c~r~ct~ris~-

tion du th6or~me 4 de [1].

Tn~OR]~XE 6. Lea entropies de la suite H ~ : I"~ ~ R ( n > k ) son t subadditives,

additives, sym~triques et jouiaaent de la propri~td d'dlagage d'ordre si, et aeuZe-

ment ai, ellea ont la reprdaentation (8).

Pervenuto in Redazione il 18 ottobre 1978.

68 CARLO SEMPI

RIASSUNTO

Si introduce un'operazione di pruning pifl generale di quella introdotta in [1]; si mostra tut tavia ehe valgono gli s~essi teoremi di caratterizzazione nella famiglia delle entropie additive e subadditive.

R~SUM]~

On introduit une opdration d'dlagage plus faible que celle introduite dans [1]; on montre ccpendant la validitd des m6mes thdorbmes de caractdrisatioa dans la famille des entropies additives et subadditives.

BIBLIOGRAPII IE

[I] B. FORTE - C. SEMPI , Pruning and measures of uncertainty, R.A.I.R.O. Informat. Thdor., 12 (1978), pp. 157-168.

[2] C.-F. PICARD, Graphes et Qaestio~naires, Gauthier-Villars, Paris, 1972. [3] J. AcZt~L - Z. DARSCZr, On measures of information and their characterizations,

Academic Press, New York - London, 1975. [4] J. ACZ~L - B. FORTE - C. T. No,, Why the Shannon and Hartley entropies are

~, natural ~), Advances in Appl. Probability, 6 (1974), pp. 131-146. [5] T. K~TAI, A remark on additive arithmetical ]unctions, Ann. Univ. Sci. Budapest

EStvSs Sect. Math., 10 (1967), pp. 81-83. [6] P. ERD(SS, On the distributive function of additive ]unctions, Ann. of Math., 47

(1946), pp. 1-20.