PROCESSI DI MARKOiFF DEL PRIMO ORDIlqE DERIVAI~TI iDA :PROCESSI DI MARKO:F:F DI ORDIiNE SUPERIORE (t) S. ANTONUCCI (2)

SOMMARIO Si studia quando un processo di Markoff del primo ordine si pub considerare derivato da un processo di Markoff di ordine superiore a uno. Ci6 viene fatto essenzialmente utilizzando la nozione di grafo associato ad un processo di Markoff. -

SUMMARY We study when a process of Markoff of the first order may be considered derived from a process of Markoff of higher order. This is obtained by using the notion of graph associated to a process of Markoff. -

1. I n t r o d u z i o n e . P r o c e s s i di Markoff di o r d i n e h s u p e r i o r e a 1 s o n o s t a t i c o n s i d e r a t i in [5] d~t R. V i n c i g u e r r a , che n e h a s ~ u d i a t o le proprietfi r i c o n d u c e n d o l i a p r o c e s s i di M a r k o f f di o r d i n e i n f e r i o r e ad h(3). Precisamente, questo &utore considera un sistema S in evoluzione a l e a t o r i a a n s t a t i E t , E 2 , . . . , E , ~ ; n o t i gli s t a t i E ~ , , E ~ , , . . . , E ~ h del s i s t e m a S n e g l i i s t a n t i t - - h, t ~ h -~- l, ..., t - - 1, h d e t e r m i n a t a la probabilitY, i n d i . p e n d e n t e d a g l i s t a t i del s i s t e m a n e g l i i s t a n t i cho p r e c e d o n o t ~ h, che il s i s t e m a S passi, a l l ' i s t a n t e t, nello s t a t e E j . Si c o n s i d e r a , poi, u n s i s t e m a S ~), c o n k ~ : h , c a r a t t e r i z z a t o da n k p o s s i b i l i s t a t i E~,i,...ik, tali che lo s t a t e di S(~) n e l l ' i s t a n t e t sia E~,~...~k q u a n d o il s i s t e m a S a b b i a preso, agli i s t u n t i t - - k Jr- 1, t - - k ~- 2, . . . , t, r i s p e t t i v a m e n t e gli s t a t i E i , , E i , , ..., E~k .

Ricevuto il 25-1-73. (l) Lavcro eseguito nell'ambito dell'attivitb, del G. N. S. A. G. A. e del G. N. A. F. A. del Comitato per lo Scienze Matematiche del C.N.R. (2) Istitato Matematico della Facolt~ d'Ingegneria, Universit~ di Napo]i. (3) Per le nozioai essenziali sui processi di Markoff del primo ordine si pub far riferimeato a [2] e [3]; numerosi esempi dei processi di Markoff di ordine superiore c o n s i d e -

r,~ti in [5] trovansi, poi, in [6].

422

S. ANTONUCCI: Processi di Markoff

D i r e m o che il sistema S ':k) cost o t t e n u t o ~ derivato dal sistema di S. Alcune propriet~ del sistema S si o t t e n g o n o in [5] s t u d i a n d o i sistemi S: ~), per k ~ 1~ 2~ ... ~h. Si b p e n s a t o che possa essere d q n t e r e s s e p e r v e n i r e ad S p a r t e n d o da S(k). I n questa 5Tota, dato un processo di Markoff del primo ordine, si vnole a p p u n t o studiare quando esso p o s s a considerarsi derivato da un processo di Markoff di ordine superiore al primo. Cib f a r e m o utilizzando essenzialm e n t e la nozione di grafo associato ad un processo di Markoff. Ricordiamo, a tale scopo, la nozione di grafo associato ad un processo di Markoff del p r i m o ordine (4). D a t o un processo di Markoff del p r i m o ordine a n stati ~ i , E2 ,...~Esi dice grafo associato al processo il grafo (orientato) i cui vertici siano gli stati ~ , E 2 , ' " , E , e tale che vi sia un arco con origine in E~ e t e r m i n e in Ej ogni volta c h e l a probabilit~ di transizione dallo stato E~ allo stato E i ~ non nulla. O v v i a m e n t e , uno stesso grafo r a p p r e s e n t a t u t t a u n a classe di processi di Markoff. U n processso di Markoff di ordine h superiore al primo si p u b a n c o r a r a p p r e s e n t a r e con un graf% c o n v e n e n d o che i vertici di esso siano successioni di h stati del p r o c e s s o ; n a t u r a l m e n t e , se vi ~ un arco con origine nel vertice (E~,, E ~ , ..., E~a) e t e r m i n e nel v e r t i c e (Ej~, Ej,, ..., Ejh) ~ dovr~ essere : E,, ---- E j , ,

Z;, =

E j , , . . . , E~ h ---- E~h_~

e7 inoltre, la probabilit~ di transizione dalla successione di stati E~I~Ei,,... ... ~E~ h a l l o stato Eja dovri~ essere non nulla. Allor% un processo di l~Iarkoff del primo ordine~ r a p p r e s e n t a t o su un grafo G~ sar~t il derivato di un processo di Markoff di ordine h superiore al primo~ se ai vertici di G si possono associare h-grammi (auccessioni di h lettere di un alfabeto con inflniti simboli)~ tali che risultino verificate le condizioni : a) se (a 1,a27...~ aa) ~ F h - g r a m m a associato al vertice V e se (b i ~b~,... ~ba) F h - g r a m m a associato al vertice W~ con V origine di un arco con t e r m i n e in W, deve risultare : a2 ~

bt ~ a q ~

b 2 ~ ... ~ aa ~

bh-t

b) a v e r t i c i distinti siano a s s o c a t i per il n o m e delle lettere).

h-grammi

(4) Per la n o m e n c l a t u r a oppure a [4].

considerazioni

e per ulteriori

distinti

(o p e r P o r d i n e

o

su i graft si rinvia a [1]

dei primo ordine derivanti da processl ecc.

428

Si t r a t t a , pertanto, di studiare la possibiliti~ di associare h g r a m m i ai vertici di un grafo orientate in mode che siano verificate le condizioni a) e b). Sar~ utile per il seguito ricordare che, date un vertice V di un grafo orientate, si dice grade dqngresso (risp. di uscita) di V il numero degli archi che hanno t e r m i n e (risp. origine) in V. D i a m % inol~re) la seguente definizione : dati due vertici V i e V~ di un grafo orientate, consideriamo una sequenza o di archi u t , u 2 , . . . ,u~ tale che, detti A i e B~ gli estremi di u~, per i ~ 1, 2 7... , l, risulti :

AI-~ Vt,

B~-~Ai+I

per i ~

1,2,...)/~1)

e o n s i d e r i a m o , po b l'applicazione f~ di c in I l , -

Bt-~- V2;

11 tale c h e :

f~(u~) -~- 1 o p p u r e ~ - - l,

per

i-----1,2 7 . . . , l ,

a seconda che A~ sia l'origine o i l t e r m i n e di u~. D i r e m o distanza del vertiee V i dal vertice V2 relativamente alla sequenza c) e la indicheremo con il simbolo d~(Vi) V2), il n u m e r o l

? re(u,).

i~l

E v i d e n t e m e n t e se v' i~ la sequenza v t , v 2 , . . . ~v~ tale ehe v~ ~ ut-~+l

per i ~- l, 2, ..., l,

risulta :

ao, (v~, vt) =

-

-

do ( v i , v~)

Infine, date un grafo G, s u p p o n i a m o che ad ogni vertice Vi di G siano associati u n n - g r a m m a g~ e un n - g r a m m a g~; allora) gli n-grammi g~ si diranno equivalenti agli n g r a m m i g[ se, det~o Z l'insieme delle lettere degli n-grammi gi e J l'insieme delle lettere degli n g r a m m i g~, esiste un)appli cazione b i u n i v o c a f di I su d tale the, se (ai,a2)...)a,~) ~ l ' n g r a m m a g~ associate al vertice V~, b (f(at)) f(as) , ... ,f(a~)) l'r~-gramma g~ associate a V~, q u a l u n q u e s i a i .

2. D i s p o s i z i o n e delle l e t t e r e negli n - g r a m m i . R i s u l t a fondamentale per il seguito la seguente PROPOSIZIONE 1. ~ia G ~ t grafo orientate ad ogni vertice del quale sia associate ur* n.gramma in mode the risultino veFij~ca.te le condizioni a) e b);

42L

S. ANTONUCCI: Processi di Markoff

allora, se ad un vertice V ~ associato l'n-gramma : (a t ~a 2 ~ ,.. ~ an)~ fissato l'indice i, con 1 < i ~ n, ad ogni vertice V ' per eui risulti :

(l)

n - - i . ~ dc( V, V') ~ i - - 1

relativamente ad una seque~za o di archi

(2)

che non tocchi vertici W tali che:

do(v, iV) < n -- i,

ozvpure tali che :

(3)

do(V, W ) > i - - 1

associato urt n-gramma che presenta nella i~osizione i--do(V,

V')

la lettera a~. Difatti, detto k il n u m e r o degli archi che costituiscono la sequenza v, o s s e r v i a m o chB la proposizione 1 i~ e v i d e n t e m e n t e v e r a se k ~ 1 ; s u p p o s t o p e r t a n t o che essa sia vera se k-----l, facciamo vedere che essa ~ a n c o r a v e r a se k ~ l - 4 - 1 . Considerata, a tale scopo, una sequenza c di l ~ l archi ut,u~,...,U~+l , r e l a t i v a m e n t e alia quale la distanza di V da V' verifichi le ipotesi della proposizione 1, sia 17 l'estremo

di u~+t diatinto da V ' ;

e v i d e n t e m e n t e la

d i s t a n z a di V da lY, r e l a t i v a m e n t e a c, verifica le ipotesi della proposizione, e p e r t a n t o , per l'ipotesi di induzion% al vertice V-~ associato uu n - g r a m m a ehe p r e s e n t a nella posizione i--do(V,

V)

la lettera a~. Allora, se V ~ origine di u~+l, la lettera a~ si trover/t nella posizione i - - d~( V, V) - - I nello n - g r a m m a associato a V ' (per la condizione b), a l t r i m e n t i nella posizione

r

V)+

l;

m a poieh~ nel p r i m o caso ~: d,(V, V ' ) = do(V, V ) +

del primo ordine derivanti da processi ecc.

425

m e n t r e nel seeondo case ~:

do(v, v ' ) = ~ ( v , ~ ) - - ~ se ne deduce ehe in entrambi i easi ]a ]ettera a~ si t r o v a nella posizione i--do(V, V') nello n - g r a m m a assoeiato a V'. R e s t a con cib d i m o s t r a t a la proposizione !.

3. P r o c e d i m e n t i

di r i d u z i o n e degli n g r a m m i .

D i m o s t r i a m o la seguente PROPOSlZIONE 2. Sia G un grafo orientate ad ogni vertice del quale sin associate uu n gramma ia mode che risultino verificate le condizioni a) e b); allora, ad ogag vertice di G ~ possibile associare un ( n - - 1 ) . g r a m m a in mode the risultino verificate le coudizioni a) e b). Sin G u n grafo orientate t h e verifiehi le ipotesi della p r o p o s i z i o n e ; associamo ai vertici di G gli ( n - - 1 ) - g r a m m i che si ottengono dai dati sopp r i m e n d o la p r i m a lettera. Si osserva subito che gli ( a - l)-grammi ottenuti verificano ancora la condizione a); non sempre perb risalter~ verificata la condizione b); precis a m e n t e la condizione b) non risulter~ verificata per gli (n - - 1 ) g r a m m i associati a vertici origini di arehi con uno stesso t e r m i n e o p p u r e per gli ( n - - 1 ) g r a m m i assoeiati a vertiei origini di archi con termini in vertici ai quali erano associati n g r a m m i che differivano solo p e r l ' u l t i m a lettera. P e r d i m o s t r a r e l'asserto occorre, p e r t a n t % m o s t r a r e come sia possibile modifieare gli ( n - - 1 ) - g r a m m i del ripe suddetto in mode che essi verifichino la eondizione b). S u p p o n i a m o , quindi, in primo luog% che V sin un vertice con g r a d e d q n g r e s s o m maggiore di uno e ehe V i , V2,... ,V,~ siano i vertici origini di archi con lo stesso t e r m i n e V; diciamo ( a i , a~, ..., a,~) l ' n - g r a m m a che era associate a V e (v~, a i ~ a 2 ~ . . . ~ a n - - 1 ) ~ per i = l, 27 ..., m, lo n - g r a m m a che era associate al vertiee v'~. Sostituiamo, allora, negli ( n - - 1 ) - g r a m m i assoeiati ai vertici V 2 , V s ~..., V,,, la lettera a i con le lettere xe ~ x.~, ... , x , , r i s p e t t i v a m e n t e , s u p p o n e n d o che le lettere x~ siano t u t t e distinte tra lore e dalle lettere gi/~ presenti negli (~t--1)-grammi assoeiati ai vertici del grafo. N a t a r a l m e n t e , pereh~ risulti sempre verifleata la condizione a)~ occorre operare la sostituzione d i a I con

426

$. ANTONUCCI: Processi di Markof]

le x~ anche in ( n - 1)-grammi assoeiati ad altri v e r t i c i ; p r e e i s a m e n t e , ricordando la proposizione 1, negli ( n - - 1 ) - g r a m m i associati a vertici X~0 tali che :

r e l a t i v a m e n t e a sequenze v di archi ehe non tocehino risulti : (4) dc ( V i, Y ) <2 n - - 2,

vertici

Y p e r cui

o p p u r e risulti : (5)

do(V~, Y ) ~

O;

la sostituzione di a i con x~ va effettuata, poi, s e m p r e posizione 1, aI posto

ricordando

la pro-

p e r ogni i - ~ - 2 7 3 7 . . . , m . ]~ bone, a questo punto, o s s e r v a r e esplicitamente, per la c o e r e n z a del s u d d e t t o p r o c e d i m e n t o di sostituzioni, che non pub capitare l ' e v e n t u a l i t ~ c h e l a lettera a t si d e b b a sostituire, al primo posto dello ( n - - 1 ) - g r a m m a associate al vertice V~, per i ~ 2,3, . . . , m , con piil lettere x~; difatti, se ci6 accadesse, si avrebbe~ in base atla proposizione 17 per qualche coppia di interi i e j : do(V~ 7 V j ) = O r e l a t i v a m e n t e a sequenze c di archi t h e non tocchino vertici Y per cui si a b b i a n o le (4) o le (5); ma questo fatto porterebbe a vi ~ v1 , c e n t r e il verificarsi della condizione b) per gli u g r a m m i di partenza. Il procedimento s u d d e t t o v a r i p e t u t o per t u t t i gli ( n - - 1 ) - g r a m m i associati a vertiei origini di archi con uno stesso termine, oper~ndo sostituzioni di lettere con le stesse modalith, beninteso introducendo s e m p r e n u o v e lettere. E s a u r i t a quindi la considerazione degli ( n 1)-grammi associati a vertici origini di archi con uno stesso termine, si passa~ in secondo luogo, a considerate quegli ( n - - 1 ) - g r a m m i che sono associati a vertici origini di archi con termini in vertiei ai quali erauo associati n - g r a m m i ehe differiv a n e solo per l ' u l t i m a lettera. Aleuni di questi ( n - 1)-grammi sono stati gi~ considerati nella discussione p r e c e d e n t e ; per gli altri b a s t i dire che si proceder/~ in m a n i e r a del t u t t o analoga, cio~ con la sostituzione della p r i m a lettera negli ( n - - / ) - g r a m m i uguali e con le conseguenti sostituzioni della stessa lettera in altri ( n - - 1 ) g r a m m i assooiati ad altri vertici del grafo,

del primo ordine derivanti da processi ecc.

427

Si ha~ in tal rood% t h e per t u t t i gli ( n - - 1 ) - g r a m m i risulta verifieata~ oltre la condizione a)~ anehe la condizione b). R e s t a con cib d i m o s t r a t a la proposizione 2. I1 proeedimento segui~o, consistente cioi~ nelta soppressione della p r i m a lettera in tutti gli n g r a m m i e nelle successive sostituzioni di alcune lettere come n u o v e lettere si dir/t procedimento di riduzione 1 (degli n-grammi). P r o c e d e n d o d i v e r s a m e n t e 7 e p r e c i s a m e n t e associando ai vertici di G gli ( n - - 1 ) - g r a m m i ehe si ottengono dai dati con la soppressione delPultima lettera, si ha ancora il verificarsi della condizione a); la condizione b) non risulter~ inveee verificata per gli ( n - - 1 ) - g r a m m i associati a vertiei termini di archi con u n a stessa origine oppure per gli ( n - l)-grammi associati a vertiei termini di archi con origini in vertici ai quali erano associati ng r a m m i che differivano solo per P u l t i m a lettera. A n c h e in tal cas% in m o d e del t u t t o analogo a quanto fatto sopra, si possono modificare tutti gli ( n - - 1 ) - g r a m m i uguali in mode che verifichin% oltre la condizione a), anehe la condizione b); il procedimento sar~ detto, in questo ease, procedimento di riduzione 2 (degli n grammi). l~ i n t e r e s s a n t e osservare che gli n-grammi associati ai vertici di un grafo G, o t t e n u t i con il procedimento di riduzione 1 da certi (rt-t- 1)-grammi associati ai vertici di G, sono, sotto certe condizioni, equivalenti a quelli o t t e n u t i con il procedimento di riduzione 2 dagli stessi (n-~-1)-grammi. Q u a n t o detto ~ un~immediata conseguenza della seguente proposizione, che andiamo a dimostrare: PRO:eOSIZ~O~E 3. Sia G u n grafo orientato ai vertici del quale siano associati (n-~-1)-grammi in modo ehe risultino verifieate le condizioni a) e b) ed, inoltre, la seguente condizione e) se al vertice W generivo di G ~ associate l ' ( n ~ - 1 ) - g r a m m a (w I ~ w~ 7 ..., wn+l) la lettera w~ si trova soltanto negli (n -~- 1)-grammi asso. eiati a vertici W ' per e , i si abbia :

(6)

n+ l--i~do

(W, W ' ) ~ i - - 1

relativamente a sequenze e di archi ehe non tocchino vertici X per vui risulti : (7) oppure risulti : (8)

a, (W, x ) < n + 1 - - i do ( W, X ) > i - -

qualunque sia i. AUora gli n-grammi ottenuti dai dati con il proeedimento eli riduzione 1 sono equivaIenti agli n.grammi ottenuli dai dati con il ~rocedimonte di riduzione 2,

428

S. ANTONUCCI: Processi di Markof]

Cominciamo con l'osservare che, poich~ vale la condizione c) per gli (n -~- 1) grammi, sia gli n-grammi ottenuti con il procedimento di riduzione 1 sia gli n-grammi ottenuti con il procedimento di riduzione 2 verificano la propriet.~ e), dal memento che in entrambi i procedimenti le lettere che vengono ad essere aggiunte sono scelte in mode ehe siano distinte da t u t t e le altre gi~ presenti ; pertanto gli insiemi I e J delle lettere degli ngrammi ottenuti dai dati con i procedimenti di riduzione r i s p e t t i v a m e n t e 1 e 2 hanno lo stesso numero di elementi. Consideriamo, poi, Papplicazione f di I su J che verifica la seguente condizione d) se ( a t , a ~ , . . . ,an) ~ l'n-gramma associate ad un generico vertice V di G con il procedimento di riduzione 1, i~ ( f ( a t ) , f ( % ) , . . ,f(a,,)) l'n-gramma associate a V con il procedimento di riduzione 2. :Per completare la dimostrazione delia proposizione 3 basta far vedere c h e f ~ un~applicazione biunivoca di I su J. A tale scope, basra osservare che, se fosse a~-----aj con a i e aj lettere uguali in posizioni rispettive i e J negli n grammi associati a due vertici V e V', si avrebbe, per il verificarsi della condizione v), d,(V, V ' ) ~ i - - j e quindi anche, per il verificarsi delia eondizione a), f ( a d ~ f ( a j ) . A n a l o g a m e n t e si fa vedere ehe se f(a~)----.f(aj), risulta a~----at7 il che dimostra la tesi.

4. P r o c e s s i di M a r k o f f del p r i m o o r d l n e t h e n o n possono c o n s l d e r a r s i d e r i v a t i da processi di M a r k o f f di o r d i n e s u p e r i o r e . Dalla proposizione 3 discende in mode ovvio la PI~OPOSIZIONE 4. He G ~ un grafo orientate ai vertici del quale non sia ~ossibile associare k.grammi (k ~ 2) in mode che siaao verificate le condizioni a) e b), allora ai vertici di O non si possono associare n.grammi, con n > k, in mode che siano verificate le condizioni a) e b~. Difatti~ se ai vertici di G fosse possibile associare n-grammi (con n > k) in mode da verificare le a) e b), allora, in base alla proposizione 2 ripetutamente applicata, ai vertici di G sarebbe possibile associare ( n - - 1 ) - g r a m m i , ( n - 2)-grammi, ... ~k-grammi in mode che siano sempre verificate ]e a ) e b). La proposizione 4 afferma, sostanzialmente, t h e se un processo di Markoff del primo ordine non deriva da u n processo di Markoff di ordine k, allora esso non deriva nemmeno da un processo di Markoff di ordine n superiore a k. In particolare, per k ~ 2, si ha ehe, se ai vertiei di un grafo non possibile associare 2-grammi in mode che siano veriflcate le a) e b), allora un processo di Markoff del primo ordine r a p p r e s e n t a t o sul grafo non pub derivare da nessun processo di Markoff di ordine superiore. Risulta~ per,

det primo ordine derivanti da processi ecc.

429

tanto, utile trovare dei graft ai vertici dei quali non sia possibile associare 2.grammi in modo che siano verificnte le a) e b); la propriet~ detta varr~ anche per graft t h e hanno per sottografi parziali (s) i graft in questione. Riesee quindi utile il risultato seguente, la cui dimostrazione, che omettiamo, si riduce, in base alia condizione a), ad una semplice verifica: Ai vertiei dei graft seguenti non si possono associare 2-grammi in modo che risultino veril~cate le condizioni a) e b): grafo g~) vertici : A, B, C, D ; a r c h i : AB, AC, BD, CD. grafo g~) vertici : A, B, C; archi : AB, BA, AC, CA. (caso particolare di g~) grafo g3) vertici : A, B, C, D ; archi : AB, AC, AD, BC, CD. grafo g4) v e r t i c i : A , B , C,.D, E; a r c h i : AB, BC, AC, AD, AE, DE. grafo gs) v e r t i e i : A, B, C; archi: AB, BA, AC, BC. Allo stesso scopo h utile il risultato s e g u e n t e : Considerato il grafo G avente per vertici V i , V s .... , V~, W s, W3, ..., W,~-I e per archi V t Vs, V~ V3,... , V,,_I V,~, V l We, W~ W ~ , . . . , W,,_~ W,,, ai vertiei di esso non b possibile associare h-grammi, che veriflchino le a) e b)~ con h ~ - n - - 1 . Invero, supposto per assurdo la tesi non vera, siano associati ai vertici di G ( n ~ l ) - g r a m m i che verifichino le a) e b); siano, inoltr% (ai,a 2 .... ,an-l) P ( n ~ l ) - g r a m m a assoeiato a VI e (a s , a 3 , . . . , a , ~ _ l , b ) e (a s , a 3 , . . . , a ~ _ 1,c) gli (n--1)-grammi associati ai vertici V~ e W s rispettivamente, con b :4= c. I n base alla proposizione 1, poiehb, r e l a t i v a m e n t e alte sequenze di a r e h i : v3

v4,..., v,,_~ v,_~

c =

v 2 v3,

c' =

W s W3, W 3 W 4 , . . . ,

W,,-2 W,,-i

risulta :

do(V2, V , , _ l ) = n - - 3

dc,(W2, W , _ l ) = n - - 3 ,

al vertice V~_1 sarebbe associato un (~ - - 1)-gramma a v e n t e nella posizione 2 la lettera b e al vertiee W~_I sarebbe associato un ( n m 1)-gramma a v e n t e nella posizione 2 la lettera c. Ma, per l'esistenza degli archi V~-I V~ e W~-I V ~ sempre in base alla proposizione 1, gli ( n - - 1 ) g r a m m i assoeiati ai vertiei V~_I e W,,-1 dovrebbero presentare in posizione 2 la stessa lettera, eio~ dovrebbe risultare b ~ c, eontro l'ipotesi. Invocando allora la proposizione 4, t e s t a dimostrata la tesi. ~s) NelFaceezione del Berge, cfr. [1].

430

S. ANTONUCCI: Processi di Markoff

5. P r o e e d i m e n t i dl a m p l i a m e n t o d e g l i

ngrammi.

I n questo paragrafo vogliamo occuparci della questione inversa a quella considerata nel n. 3. Precisamente~ dato un grafo G ai vertici del quale sin possibile associare k-grammi, con k ~ 17 con le a ) e b)verifleate(~), vogliamo vedere se 6 possibile~ ed entro quali limiti~ associate ai vertici di (7 n grammi~ con u ~ k, con le a) e b) sempre verifieate. S a p p o s t o che cib sin possibile~ risul~a valida, come dimostreremo~ una proposizione analoga alla proposizione 3. Supponiamo che ai vertici di un grafo G siano associati k g r a m m i in modo ehe siano verificate le a) e b); precisamente~ diciamo ( a i , a~,...~ak) i! k-gramma associato al generico vertice V. Cib premesso, consideriamo il seguente procedimento di modifiea dei k-grammi, detto procedimento di a m p l i a m e n t o 1. Se V ha grado dqngresso 0, associamo a V il (k-~-1)-gramma ( p , a t , 9.. ~ au), essendo p una lettera distinta da t u t t e ]e lettere presenti nei k-grammi assoeiati ai vertici di G ; se V ha grado d~ingresso 1~ ed ~ (b~ a i , . . . ~ a ~ _ l ) il k-gramma associato al vertice origine delParco con termine in V, associamo a V il (k -{-1) gramma (b~a t , . . . , a k ) ; se V ha grado d~ingresso m muggiore di uno~ e sono (vi, a i , ... , ak-1) i k grammi associati ai vertici ir~ origini di archi con termine in V~i ~- 1~ 2~ ... ~m)~ presa una delle lettere vi, per esempio v I ~ associamo a V il (k -11-1).gr~lmma (t't, al ~ ... ~ak) e suecessivamente poniamo, nei /c-grammi associati ai vertici V~ v i ~ vi~ per i ~ 2~ 3 ~ . . . , m ; la stessa cosa facciamo per i k-grammi associati a vertioi W tali che 0 ~ d,(W~ V ~ ) ~ k - 1, relativamente a sequenze o di archi che non tocchino vertici Y per cui si abbia dr (Y~ V~) ~ 0 oppure, per cui si abbia d ~ ( I r, V ~ ) ~ k - - l ~ per i ~ 2 , 3 , . . . , m . Consideriamo~ poi~ il seguente altro procedimento di modifica dei k-grammi~ detto p r o c e d i m e n t o di a m p l i a m e n t o 2. Se V ha grado d~uscita 0, associamo a V il (k-~- 1) g r a m m a (ai~a~ 9.. ~ a u ~ p ) , essendo p ann lettera distinta da t u t t e le lettere p r e s e n t i nei kgrammi associati ai vertici di ~/; se V ha grado d'uscita 1~ ed ~ ( a ~ a a ~ ... , a ~ b ) il k-gramma assoeiato al vertice termine dell'arco con origine in V, associamo a V il (k-~-l)-gramma ( a ~ a ~ . . . ~ a ~ b ) ; se V ha grado d'uscita m maggiore di uno e sono ( a ~ a a , . . . , a ~ v ~ ) i k-grammi associati ai vertiei Vi (i ~ 1, 2~..., m) termini di archi con origine in V~ asaociamo a V iI (k -~- 1)-gramma (a~, a~, ... ~aa ~v~) e suceessivamente poniamo~ nei

(e) Per k ~ 1, si richiede solo i! verificarsi della b)~

del primo ordine derivanti da processi ecc,

431

k-grammi associati ai vertiei V~, v~ ~ v i ~ per i .-~ 2, 3~ ..., m ; la stessa cosa faceiamo per i k-grammi associati a vertici W tali che 0 .~ dr (W, V~) -_~ k - - 1 relativamente a sequenze e di archi che non tocchino vertiei Y per cui si abbia dr (Y, Vi) ~ 0 oppure, per cui si abbia dr (Y, Vi) ~ k - - l , per i~2~3,...,m. Si pub subito affermare che i (k nu 1)grammi ottenuti con l~uno o l'al. tro dei due procedimenti verifieano la a) ma~ in generale, non verificano la b). Inoltre, si pub anche affermare che i procedimenti di ampliamento 1 e 2 sono rispettivamente~ gli inversi dei procedimenti di riduzione 1 e 2~ nel senso precisato dalla seguente PROPOSIZIONE 5. Sia G u n grafo ai vertiei del quale siano associali n.grammi in modo che siano verificate lea), b) e c). Associamo ai vertici di G gli n-grammi ottenuti applicando successivamente~ e i~ un ordine qualsiasi il procedimento di riduzione 1 (ris~. 2) ed il procedimento di ampliamento 1 (risp. 2). Allora, gli n.grammi dati sono equivalenti agli n.grammi ottenuti. Difatti, supponiamo che si applichino~ nell'ordine~ i procedimenti di riduzione 1 (risp. 2) e di ampliamento 1 (risp. 2) ; in base alla proposizione 3, nelle ipotesi fatte, applicando il procedimento di riduzione 1 (risp. 2), ai vertici di G vengono associati ( n - 1)-grammi che verificano le a), b) e c); applicando, poi, il procedimento di ampliamento 1 (risp. 2) agli ( n - - l ) grammi ottenuti, ~ facile mostrare che risultano verificate ancora le condizioni a) e b); ripetendo~ allora~ le considerazioni fatte a proposito della dimostrazione della proposizione 3, si deduce immediatamente, in questo case, l~asserto. Supponiamo, viceversa, che si appliehino, nell'ordine, i procedimenti di ampliamento 1 (risp. 2) e di riduzione 1 (risp. 2); helle ipotesi poste~ applicando il procedimento di ampliamento 1 (risp. 2), ai vertici di O vengono ad assoeiarsi (n-~-l)-grammi che verificano le a) e c); nul]a pub dirsi circa il verificarsi della b). T u t t a v i a , poich~ i~ immediato mostrare che il procedimento di riduzione pub essere applicato anche a (n-~-1)-grammi che non verifieano la b) e che, in ogni caso~ esso non altera il verificarsi delle a) e v), applicando agli (n-~- 1)-grammi ottenuti il procedimento di riduzione 1 (risp. 2)~ si ottengono degli n-grammi che verificano le a ) e e); ne discende, ripetendo sempre le considerazioni fatte a proposito della proposizione 3, l'equivalenza, anche ia questo caso, tra gli n grammi ottenuti e quelli dati. Ragionamenti del tutto analoghi vengono seguiti per la dimostrazione della seguente PROPOSIZION~ 6. Sia G u n grafo ai vertici del quale siaao associati n-grammi in modo ehe siano verifieate le a), b)e e). Allora~ gli ( n + l ) g r a m m i otteauti eon il prooedi~neato di ampliamento 1 applieato agli n-grammi dati $o~o equivalenti a quelli ottenuti con il proeedimento di ampliamento 2.

432

S. ANTONUCCI: Processi di Markoff

Le proposizioni 3, 5, 6 consentono di affermare che, supposto che ai vertici di un grafo G siano associati n grammi che verfichino le a), b), e c), applicando h volte il procedimento di ampliamento 1 e n - - h - - 1 volte il procedimento di ampliamento 2, in un ordine qualsiasi, ad 1-grammi associati ai vertici di G che verificano l a b ) , con 0 ~ h ~ n - - 1 , si ottengono degli n-grammi che sono equivalenti ai dati. In altre parole, so u n processo di ~farkoff del primo ordine deriva da un processo di Markoff di ordine n che, rappresentato su un grafo G, verifica la c), allora ogni altro processo di Markoff di ordiae n che r a p p r e s e n t a t o su G verifichi ]a c), dal quale derivi il processo del primo ordine, ~ equivalente al dato, nel senso dell'equivalenza degli n-grammi. Abbiamo gi~ detto ehe, applicando Puno o l'altro dei procedimenti di ampliamento agli n-grammi associati ai vertici di un grafo G con le a ) e b) verificate, si ottengono degli ( n ~ l ) . g r a m m i che in generale non verificano h~ b); vogliamo ora vedere in quali casi la b) non risulta c e r t a m e n t e verificata. In questi casi ai potr~ affermare che un processo di Markoff del primo or(line rappreseatato sul grafo G non potr,~ derivare da alcun processo di Markoff di ordine n nu 1, e quindi (proposizione 4) da nessun processo di Markoff di ordine superiore a n. Consideriamo, a tale scopo, un grafo G ai vertici Vt, V~,... , V n del quale siano associati k-grammi in modo che siano verificate l e a ) , b) e c). Appliehiamo ai k-grammi il procedimento di ampliamento 1 (risp. 2); evidentemente, l'esistenza di un vertice con grado d'ingresso (risp. d'uscita) 0 comporta l'aggiunta di una nuova lettera, l'esistenza di un vertice con grado dTingresso (risp. d'useita) m maggiore o uguale a 1 comporta la soppressione d i m ~ 1 lettere. Ne segue che, detto I l'insieme delle lettere dei k-grammi e J (risp. J') l'insieme delle Iettere dei (k-~- I)-grammi o t t e n u t i con il procedimento di ampliamento 1 (risp. 2), se si indicano con n(ir), n (J), ~t (J') i humeri degli elementi degli insiemi I, J, J' e con g~ e g~ rispettivamente i gradi d'ingresso e d'uscita dei vertici V~(i = 1, 2,... ,n), si h a : n (J)

=

n (I) --

y.

(g, - -

1)

i---..l

=n(r)-i=l

poich~ ~ ~ g,----- -~ g~, [4], sar/~ anehe n ( J ) - = n(J'),

come del resto si sa

gi/~ in base alla proposizione 6. Supposto, poi, t h e la somma s =

( g , - I) = i----1

} i~-..~l

-

I)

del primo ordine derivanti da procesd ecc.

48'd

sia positiva~ e iterando il procedimento~ si n o t a che ogni volta vengono a s o p p r i m e r s i S l e t t e r e ; conseguentemente~ s u p p o n e n d o di partire dal valore k = 1, per il quale si ha n ( I ) = n~ si pub enunciare~ raccogliendo i risultati ottenuti~ la PRO:POSlZlONE 7. Su G u n grafo e siano g~ i gradi d'ingresso dei ",~ertici Vi(i = 1~ 2, ... ~ n) ; inoltre~ la somma

i=l

aia positiva ; allora, detto q il quoziente intero della divisio~e eli n p e r S, ai vertici del grafo uon Tossono assoeiarsi m - g r a m m i verificanti le a) e b), con m~q. Se~ invece 7 S ~ minore o uguale a zero~ in generale i~ possibile associare ai vertici di G m-grammi verificanti le a) e b)~ con m qualsiasi~ come facile riseontrare in certi esempi.

6. Conclusion|. Si ~ visto che se un processo di Markoff del primo ordine deriva da un processo di Markoff di ordine n superiore a 1 e quest~ultimo~ rappres c n t a t o su un grafo G~ d~ luogo ad n-grammi che verificano la c), allora qualsiasi altro processo di Markoff di ordine n che veriflca la stessa condizione pub considerarsi equivalente al dato~ nel sense deIPequivalenza degli n-grammi. Lo stesso~ perb~ non pub dirsi~ in generale~ per processi di Markoff~ dai quali derivi il proeesso del primo ordine~ che non verifichino la c). Tuttavia~ se ai vertici di un grafo orientate sono associati n-grammi che verificano le a ) e b)~ ~ sempre possibile modificare alcune lettere in mode ehe risulti verificat~ anche la e); da cib e dalle eonsiderazioni p r e m e s s e pub dedursi che se un processo di Markoff del primo ordine deriva da un processo di Markoff di ordine n che r a p p r e s e n t a t o su un grafo dit luogo ad n-grammi t h e non verificano la c)~ quest'ultimo~ allora~ pub ottenersi m e diante identificazione di stati da uno qualsiasi dei proeessi di Markoff di ordine n, t r a di lore equivalenti~ ehe~ r a p p r e s e n t a n o sal grafo O r dia luogo ad n g r a m m i che veriflchino la e). Q u e s t ' u l t i m a affermazione~ insieme con le considerazioni premesse~ ind i v i d u a p i e n a m e n t e la classe dei processi di Markoff di ordine n dai quali pub derivare nn processo di Markoff del p r i m o ordine.

484

S. ANTONUCCI: Processi di Markoff

BIBLIOGRAFIA

[1] C. BERGE, Th~orie des graphes et ses applications, 1967, Dunod, Paris. [2] P. DORE, Introduzione al calcolo delle probabilith e alle sue appticazioni ingegneristiche, 1964, Patron, Bologna. [3] M. FR~CHET, Les principes de la thdorie des probabilitds, 1938, Gauthi6r-Villar, Paris. [4] O. ORE, Theory of graphs, 1962, Am. Math. Soc., Providence. [5] R. VINCIGUE~aA, Processi finiti di Markoff di ordine superiore e procedimento per lo studio della loro regolarit?L Ann..Ist. Univ. Nay. 88 (1964). [6] E. Rtrsso-R. VINClCUERP,A, Esempi di processi di Markoff di ordine superiore e Ioro studio per mezzo di speciali procedimenti, Ann. Ist. Univ. Nay. 85 (1966).