PRÀCTIQUES DE CADENES DE MARKOV Esteve Codina Sancho · 1 diplomatura d’estadÍstica investigaciÓ operativa estocÀstica prÀctiques de cadenes de markov esteve codina sancho

1

DIPLOMATURA D’ESTADÍSTICA

INVESTIGACIÓ OPERATIVA ESTOCÀSTICA

PRÀCTIQUES DE CADENES DE MARKOV

Esteve Codina Sancho

2

OBJECTIU ................................................................................................................................................. 3

EXERCICIS................................................................................................................................................ 4

ENUNCIATS DE PRACTIQUES............................................................................................................. 6

1 FUNCIONAMENT DEL PROGRAMA ............................................................................................. 16

1.1 INTRODUCCIÓ DE DADES .......................................................................................................... 16 Fitxers d’entrada / sortida ................................................................................................................. 16 Manualment........................................................................................................................................ 27 2.1.3 Correcció de dades.................................................................................................................... 29

1.2 ANÀLISI DE CLASSES DE LA CADENA..................................................................................... 30 Composició en classes d’equivalència ............................................................................................... 30 Estructura del diagrama .................................................................................................................... 31 Tractament de classes transients........................................................................................................ 33

1.3 ANÀLISI D’ESTAT ESTACIONARI ............................................................................................. 38 Probabilitats d’estat estacionari ........................................................................................................ 38 Temps mitjos de primer pas................................................................................................................ 44 Equacions de Chapman-Kolmogorov ................................................................................................ 46

2 PROBLEMES D’EXEMPLE............................................................................................................... 47

3 MANIPULACIÓ ................................................................................................................................... 55

Presentació......................................................................................................................................... 55 3.1.2 Menú principal .......................................................................................................................... 56 3.1.3 Introducció de dades ................................................................................................................. 57 3.1.4 Anàlisi de classes de la cadena ................................................................................................. 67 3.1.5 Anàlisi d’estats estacionari ....................................................................................................... 68

3

OBJECTIU L’objectiu d’aquestes pràctiques és el de la utilització de un programa orientat a analitzar cadenes de Markov finites per poder aconseguir un major aprofundiment i familiarització en els conceptes que s’exposen a les sessions teòriques de l’assignatura de Investigació Operativa Estocàstica de la Diplomatura d’Estadística. Aquests apunts contenen, per una part una sèrie d’enunciats que resulten en una modelització mitjançant cadenes de Markov, una sèrie d’exercicis consistents en l’anàlisi d’una cadena de Markov determinada i finalment en un manual d’utilització del programa. Aquest programa va estar realitzat pels alumnes de la Diplomatura d’Estadística Ramón Garreta Fabré i Ivan Lisón García com Projecte Final de Carrera en curs acadèmic 1996/97.

4

EXERCICIS

5

6

ENUNCIATS DE PRACTIQUES

7

8

9

10

11

12

13

14

15

16

1 FUNCIONAMENT DEL PROGRAMA Es pot dividir el funcionament en tres apartats ben diferenciats: el primer d’ells, i imprescindible per portar a terme els càlculs posteriors, és la Introducció de dades. Aquesta acció es pot dur a terme de dues formes: una mitjançant la utilització de fitxers que continguin la matriu de probabilitats, les probabilitats inicials i els costos associats a cadascun dels estats i l’altra manualment a través del teclat. Un cop llegides i introduïdes les dades, el programa dóna tota la informació que caracteritza aquella cadena de Markov i està en disposició de donar a l’usuari altres opcions. Aquestes les podem dividir en dues subseccions: Anàlisi de classes de la cadena i Anàlisi d’estats estacionari. La primera d’elles l’anomenarem així perquè permetrà trobar quantes classes comunicants té la cadena de Markov i de quins estats estan formades, identificar la característica d’absorció i gestionar les classes absorbents i les classes transients, ja sigui calculant les matriu B, M i M1. La segona part permetrà de trobar les probabilitats a llarg termini, els temps mitjos de primer pas i utilitzant les equacions de Chapman-Kolmogorov podem obtenir la probabilitat no condicional de trobar-nos a un estat després de n períodes. Un cop dins el Menú Principal es disposa de quatre opcions: 1) Introducció de dades, 2) Anàlisi de classes de la cadena, 3) Anàlisi d’estats estacionari i 4) Sortir del programa.

1.1 INTRODUCCIÓ DE DADES

El programa pot llegir les dades de dues formes: Manualment o través de Fitxers. Si s’escull aquesta darrera opció s’haurà de tenir present l’existència prèvia de tres fitxers d’entrada. En cas contrari serà l’usuari qui mitjançant el teclat haurà d’introduir les probabilitats i els costos.

Fitxers d’entrada / sortida El programa gestiona quatre fitxers. Els tres primers són fitxers d’entrada i han d’estar creats abans si es vol executar el programa mitjançant l’utilització d’aquests. El darrer és un fitxer de sortida que crearà el programa a partir de les accions portades a terme al llarg de l’execució. Cal tenir en compte que utilitzar fitxers d’entrada és opcional. Si no es volen utilitzar fitxers, les dades poden ser introduïdes manualment, és a dir, mitjançant el teclat. El mateix podem dir del fitxer de sortida, acció que es dóna també de forma opcional. Aquesta opció es força recomanable ja que proporciona un

17

registre de les operacions efectuades en una sessió d’execució del programa. Els tres fitxers es copiaran o es crearan al mateix directori del programa principal. La lectura correcta és possible únicament si els fitxers es troben a la mateixa àrea de treball que conté l’executable. El fitxer de sortida es generarà també a la mateixa àrea on hi ha la resta.

Fitxers d’entrada Els fitxers d’entrada o de definició de dades són tres. El primer d’ells contindrà els valors de la matriu de probabilitats de transició en un pas. Els dos restants contindran el vector de costos i el vector de les probabilitats inicials associades a cadascun dels estats de la cadena de Markov. Aquests dos darrers fitxers s’utilitzaran a l’hora de trobar les probabilitats no condicionals de trobar-se en un estat qualsevol de la cadena i, un cop obtingudes les probabilitats a llarg termini, el cost mig esperat a llarg termini. Estructura del fitxer de la Matriu de Probabilitats de transició: El fitxer que conté la matriu de probabilitats ha d’estructurar-se en quatre parts ben diferenciades: Comentaris referents al fitxer de dades, dimensió del problema, dades en si i finalment un caràcter diferenciador de fi de fitxer. Comentaris: C C Comentaris referents al fitxer. C • Constarà d’un nombre determinat de línies de comentaris. Cal que aquestes línies comencin pel caràcter “C” o “c” i aquest es trobi situat a la primera columna. Les línies de comentaris han d’anar seguides i no poden haver línies en blanc pel mig. Dimensió n Dimensió de la cadena de Markov. • “n” ha de ser un enter (és a dir sense punt decimal) i ha d’anar tot seguit a les línies de comentaris. No cal que es trobi just a la primera columna, perquè el programa l’identifica a qualsevol posició entre les columnes 1 i

18

80; cal, però, que es trobi a la fila immediatament posterior a la darrera fila de comentaris. Aquest valor no pot excedir d’uns límits (1, NMAX); altrament, el programa dóna el següent missatge: “∗ La dimensió introduïda no es troba entre els límits permesos.“.

Dades: fila 1 col 1 : element col 2 : element . . . col n : element fila 2 col 1 : element col 2 : element . . . col n : element . . . fila n-1 col 1 : element col 2 : element . . . col n : element fila n col 1 : element col 2 : element . . . col n : element • Correspon als valors que componen la matriu. Només caldrà indicar quins valors de la matriu són diferents de 0. Els valors, per a cadascuna de les files, no cal que estiguin ordenats. El mateix passa per a les columnes. Els valors d’una fila poden ocupar més d’una línia d’espai, tantes com es vulgui, sempre i quan es respecti l’estructura parell “col n : element”, és a dir, primer el valor de la columna, seguit dels espais que es vulgui (com si no se’n posa cap), els dos punts (:) com a separació i el valor que ha de prendre en format de punt flotant o exponencial. Fi de fitxer: # Element de fi de fitxer. • Cal que es trobi seguint als registres que defineixen la matriu i a la primera columna del fitxer. No poden haver files en blanc entre mig.

Observacions: 1. Com s’ha comentat abans, els parells “col n : element” han de ser escrits a la mateixa fila, mai podem trobar el valor d’una columna i els dos punts a una fila i el valor corresponent per aquella columna i fila de la matriu de probabilitats a la línia següent. fila n col 1 : element col 2 : element ....... col n : element 2. Cal que hi hagi com a mínim un espai de separació entre dos parells “col n : element”. fila n col 1 : element_ col 2 : element ....... col n : element

19

3. Cal que cada element estigui entre [0,1] i que la suma per cadascuna de les files sigui igual a 1 ± ε. Aquest error és un altre dels paràmetres que conté el fitxer PARAMS.FOR. Exemple 1: C C Matriu de prob. de transició. 9 estats període 3. C 9 1 3 : 0.6 4 :.4 2 3 : 0.6 4:0.4 4 5 : .6 6:.4 3 5 :.6 6:.2 9:.2 5 1: .6 2:.3 8 : .1 8 7 : 1. 9 9:1. 6 1: .6 2:.4 7 8 : .3 7 : 0.7 # Exemple 2: C C Dades de l'exercici 8. C 3 1 2: 0.8 3 : 0.2 3 3 : 0.1 2: 0.5 1 : 0.4 2 1 : 0.3 2 : 0.7 # Estructura del vector de Probabilitats Inicials: El fitxer conté les probabilitats inicials associades a cadascun dels estats. Ha d’estructurar-se en quatre parts ben diferenciades: Comentaris referents al fitxer de dades, dimensió del problema, dades en si i finalment un caràcter diferenciador de fi de fitxer. Comentaris:

C C Comentaris referents al fitxer. C

20

• Constarà d’un nombre determinat de línies de comentaris. Cal que aquestes línies de comentaris comencin pel caràcter “C” o “c” i aquest es trobi situat a la primera columna. Les línies de comentaris han d’anar seguides i no hi pot haver línies en blanc pel mig. Dimensió:

n Dimensió de la cadena de Markov. • “n” ha de ser un enter i ha d’anar tot seguit a les línies de comentaris. No cal que es trobi just a la primera columna, perquè el programa l’identifica a qualsevol lloc, això sí, cal que es trobi a la línia immediatament posterior a la darrera línia de comentari. Aquest valor ha de coincidir amb la dimensió del fitxer que conté la matriu de probabilitats; altrament, el programa dóna un missatge d’advertència visual per pantalla . Dades: col 1 : element col 2 : element col 3 : element ... col n-2 : element ..... col n-1 : element col n : element • Correspon als valors que prendrà el vector. Només caldrà indicar quins valors del vector són diferents de 0. Els valors poden ocupar més d’una línia d’espai, tantes com es vulgui, sempre i quan es respecti l’estructura “col n : element”, és a dir, primer el valor de la columna, seguit dels espais que es vulgui (no és necessari posar-ne cap), els dos punts (:) com a separació i el valor que ha de prendre en format de punt flotant o exponencial. Fi de fitxer:

# Element de fi de fitxer. • Cal que es trobi tot seguit als valors que defineixen el vector de probabilitats inicials i a la primera columna del fitxer. Observacions: 1. Cada parella ”col n : element” ha d’estar a la mateixa fila. No es pot trobar un element corresponent a una columna n-èssima a la línia següent on es troba indicat el valor de la columna. col 1 : element col 2 : element . . . col n : element

21

2. Cal que hi hagi com a mínim un espai de separació entre dos parells “ col n : element”.

col 1 : element_col 2 : element . . . col n : element 3. Cal que cada element estigui entre [0,1] i que la suma per tots els estats sigui igual a 1 ± ε. (ε és una tolerància prefixada). Exemple 1: C C Comentaris del fitxer de probabilitats inicials d’una matriu C de 6 estats. C 6 2 : 0.22 4 : .48 3 : .1 5 : 0.05 1: 0.15 # Exemple 2: C C Comentaris del fitxer de probabilitats inicials. C 3 3 : 0.51 1: 0.49 # Exemple 3: C C Fitxer de probabilitats inicials ( 9 estats ). C 9 1: .2 2: .1 3: .1 4: .1 5:.1 6:0.4 7 :0. 8:. 9: . # Exemple 4: C C Fitxer de probabilitats inicials ( 4 estats ). C 4 4 : .1 1 : 0.1 2 : 0.35 3 : .45 # Estructura del vector de costos:

22

El fitxer que conté els costos associats a cada estat ha d’estructurar-se en quatre parts: Comentaris referents al fitxer de dades, dimensió del problema, dades en si i finalment un caràcter diferenciador de fi de fitxer. Comentaris: C C Comentaris referents al fitxer. C • Constarà d’un nombre determinat de línies de comentaris. Cal que aquestes línies de comentaris comencin pel caràcter “C “ o “c” i aquest es trobi situat a la primera columna. Les línies de comentaris han d’anar seguides i no hi pot haver línies en blanc pel mig. Dimensionalitat:

n Dimensionalitat de la cadena de Markov. • “n” ha de ser un enter entre 1 i NMAX i ha d’anar tot seguit a les línies de comentaris. No cal que es trobi just a la primera columna, perquè el programa l’identifica a qualsevol lloc. Cal que es trobi a la línia immediatament posterior a la darrera línia de comentaris. Aquest valor ha de ser el mateix que al fitxer d’abans; altrament, el programa dóna el següent missatge d’advertència per pantalla: “ * La dimensió NO coincideix.”. Dades: col 1 : element col 2 : element . . . col n : element • Correspon als valors que prendrà el vector. Només caldrà indicar quins valors del vector són diferents de 0. Si el cost d’un estat s’ignora es considerarà nul. En aquest cas no disposem de files perquè es tracta d’un vector. Els valors d’una fila poden ocupar més d’una línia d’espai, tantes com es vulgui, sempre i quan es respecti l’estructura “col n : element”, és a dir, primer el valor de la columna, seguit dels espais que es vulgui (no és necessari posar-ne cap), els dos punts (:) com a separació i el valor que ha de prendre (element de tipus real ).

Fi de fitxer: # Element de fi de fitxer.

23

• Cal que es trobi tot seguit als valors de la matriu i a la primera columna del fitxer. Observacions: 1. Cada parella ”col n : element” ha d’estar al mateix registre. No es pot trobar un element corresponent a una columna n-èssima a la línia següent on es troba indicat el valor de la columna. col 1 : element col 2 : element ... col n : element 2. Cal que hi hagi com a mínim un sol espai de separació entre dos elements. col 1 : element_col 2 : element 3. El tipus de l’element ha de ser real, no superior a cinc xifres decimals. 4. No s’admeten costos negatius. Exemple 1: C C Comentaris del fitxer de costos d’un vector C de 9 estats. C 9 2 : 1.5 7 : 4. 3 : 7. 5 : 8. 1: 2.5 # Exemple 2: C C Fitxer de costos ( 6 estats ). C 6 2: 23.5 3: 1.0 4:100.0 5:.1 6:5.0 # Exemple 3: C C Fitxer de costos ( 10 estats ). C 10 1: 1004.0 2: 23.5 3: 1.0 4:100.0 5:.1 6:5.0 7:20. 8:20.

24

9:20. # Exemple 4: C C Comentaris del fitxer de costos d’un vector C de 3 estats. C 3 3 : 400. 2 : 200. 1 : 100. #

Fitxer de Sortida El fitxer de sortida té un objectiu ben clar. Ha de servir de suport a l’usuari per tal que disposi d’un registre de l’execució del programa. Aquest únic fitxer de sortida contindrà les línies de comentaris dels tres fitxers d’entrada, juntament amb la matriu de probabilitats, presentada de forma matricial (igual que per pantalla), el vector de costos i el vector de probabilitats inicials. Inclourà una classificació d’estats de la cadena de Markov (les classes irreductibles que la formen, el període de cadascuna d’elles i els grups de periodicitat).

Estructura del fitxer de sortida:

El fitxer de sortida té per objectiu proporcionar a l’usuari un registre de totes les operacions efectuades amb un problema concret. El fitxer de sortida consta de dues parts ben diferenciades: 1 ) A la primera part es reprodueixen les dades que defineixen el problema (matriu de probabilitats de transició, vector de probabilitats inicials i vector de costos associats als estats de la cadena). El format en el que apareixen les dades de definició és el mateix que el definit a l’apartat 2.1 .1.1 d’aquest manual d’usuari. Addicionalment, en aquesta primera part del fitxer de resultats, poden aparèixer missatges d’advertència o d’error corresponents a les següents comprovacions:

Pij∈[0,1] i ∑Pij = 1±ε

on ε és una tolerància predefinida. També en aquesta primera part apareixerà una classificació dels estats i la periodicitat de cada classe.

25

2 ) A la segona part del fitxer de sortida hi constaran els resultats corresponents als diferents mòduls que s’hagin executat. Observacions: • Els mateixos comentaris que s’inclouen dins el fitxer de la matriu de probabilitats. • Representació matricial de les probabilitats de transició en un pas ordenades numèricament per estats i els missatges d’advertència en cas d’anomalia. • Classificació prèvia del número de classes que formen la cadena de Markov, el període de les classes i els estats que formen els grups de periodicitat (si aquesta és periòdica i absorbent alhora). • Si una classe no és periòdica, llavors apareixerà per pantalla el missatge: “LA CLASSE n ES APERIODICA”. Exemple:

A partir del problema de test no. 9 i amb un fitxer de dades com el següent: C C Aquestes dades son extretes d'uns exercicis que fets a C l'assignatura de IOE. Dades de l'exercici 7. C 6 1 3 : 1. 3 5 :1. 5 1 : 1. 2 6 : 1. 4 1 : .25 2 : .25 4:.5 6 2: .33 6:.66 # Obtindrem una sortida com la següent C C Aquestes dades son extretes d'uns exercicis que varem fer a C l'assignatura de IOE. Dades de l'exercici 7. C 1 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 2 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 3 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 4 0.2500 0.2500 0.0000 0.5000 0.0000 0.0000 5 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000

26

6 0.0000 0.3333 0.0000 0.0000 0.0000 0.6667 * EL PERIODE DE LA CLASSE 1 ES: 3 El grup de periodicitat 1 esta format pels estats: 1 El grup de periodicitat 2 esta format pels estats: 3 El grup de periodicitat 3 esta format pels estats: 5 * LA CLASSE 2 ES APERIODICA. * LA CLASSE 3 ES APERIODICA La part corresponent al vector de probabilitats inicials constarà de: • Els mateixos comentaris que s’inclouen dins el fitxer que conté el vector de probabilitats inicials. • Representació vectorial (vector fila) de les probabilitats inicials ordenades numèricament per estats. En cas d’existir Pij < 0, Pij > 0 o ∑Pij ≠ 1±ε s’adjunta el corresponent missatge d’advertència: “ * L’element de la fila * i columna * NO està entre 0 i 1.“ i “ * Els elements del vector de probabilitats inicials NO sumen 1.”. Exemple: Si disposem d’un fitxer de dades per a un vector de probabilitats com el següent: C C Comentaris del fitxer de probabilitats inicials. C 6 2 : 0.22 1 : .78 # Obtindrem una sortida com la següent: C C Comentaris del fitxer de probabilitats inicials. C VECTOR DE PROBABILITATS INICIALS. --------------------------------------------------------- 1 : 0.7800000 2 : 0.2200000 3 : 0.0000000 4 : 0.0000000 5 : 0.0000000 6 : 0.0000000 La part corresponent al vector de costos constarà de:

27

• Els mateixos comentaris que s’inclouen dins el fitxer que conté el vector de costos. • Representació vectorial dels costos associats a cada estat ordenats numèricament. Poden tenir qualsevol valor real no superior o igual a 104. Exemple: Si disposem d’un fitxer de dades per a un vector de costos com el següent: C C Comentaris del fitxer de costos d’una vector de 6 estats. C 6 3 : 1. 2 : 1.0 1 : 33.00 # Obtindrem una sortida com la següent: C C Comentaris del fitxer de costos d’una vector de 6 estats. C VECTOR DE COSTOS. ------------------------------- 1 : 33.00 2 : 1.00 3 : 1.00 4: 0.00 5 : 0.00 6 : 0.00

Manualment Si s’escull aquesta segona opció del submenú presentat dins l’opció 1 del menú principal l’usuari s’han d’introduir un a un tots els elements de la matriu de probabilitats, i dels vectors de probabilitats inicials i costos. Es demana primer de tot la dimensió del problema (número d’estats de la cadena de Markov). Cal que aquest valor s’escaigui entre 1 i NMAX. En cas contrari s’advertirà visualment mitjançant un missatge: “La dimensió excedeix del permès“ . Un cop introduïda la dimensió caldrà introduir tots els valors de la matriu, ja siguin nuls o no, seguint l’ordre dels estats, primer per files ↓ i després per columnes →. Els valors hauran d’estar dins de l’interval [0,1], condició

28

de probabilitat, i el sumatori per a cadascuna de les files haurà de ser ≈ 1 ( ∑Pij = 1±ε). Les condicions són les mateixes de l’opció Fitxers. En cas d’errades a l'hora d’introduir les dades, un cop finalitzada la lectura, el programa permet de rectificar tots aquells valors que es vulguin, sempre i quan s’acompleixin les propietats abans esmentades. El procés de rectificar els valors és el següent: 1.- Es demanen un a un tots els valors. A mesura que s’introdueixen per teclat es comprova únicament si són probabilitats (si es troben dins els límits). Si s’introdueix un valor fora de límits es demanarà rectificar-lo al moment. Caldrà introduir els valors de la fila i la columna (tipus enter) corresponents a aquell element i modificar-lo pel valor correcte. 2.- Un cop obtinguts tots els valors (de la matriu o bé el vector de probabilitats) es comprova el sumatori per totes les files i s’adverteix per pantalla de quines són les que no acompleixen la propietat ∑ Pij = 1 ± ε. Llavors és l’usuari qui decideix els valors a canviar, prèvia indicació de la fila i columna correponents a l’element a modificar.

Un cop el programa ha llegit correctament la matriu, la representa de forma matricial per pantalla juntament amb les principals característiques de la classificació d’una cadena de Markov -número de classes, periodicitat i grups de periodicitat-. El contingut dels vectors no es mostra. Tota aquesta informació que se subministra és la mateixa si l’opció escollida és la de Fitxers, exceptuant aquest darrer punt.

29

2.1.3 Correcció de dades El programa disposa d’una rutina que “ajusta” els valors d’una fila o d’un punt determinat per a casos on, en no poder introduir l’element de forma a

a (fraccionada) s’introdueix de forma periòdica amb poca precisió Llavors aquest algorisme s’encarrega d’ajustar els valors i fer que aquests s’aproximin amb la precisió desitjada.

Exemple: Disposem d’una línia corresponent a un estat amb unes probabilitats com les següents 2 3 : 0.66 4 : 0.33 El sumatori d’aquesta fila correspondria a 0.99. Si l’error mínim s’ha definit prèviament com EPS = 0.0001 caldrà rectificar els valors d’aquella fila per tal que la diferència (1-0.99) sigui, com a mínim, igual o més petita a EPS. La rectificació que faria l’algorisme equivaldria a tenir inicialment uns valors com els següents: 2 3 : 0.6666 4 : 0.3333 El sumatori d’aquesta “nova” fila correspondria a 0.9999. Després de rectificar els valors, la suma dels quals ja no desfà la propietat de sumar 1 amb la precisió desitjada. Perquè1-0.9999 ≤ 0.0001 = EPS Altrament, quan la suma d’una fila, ja sigui a la matriu de probabilitats o bé al vector de probabilitats inicials, és molt inferior (sum<<1) o molt superior (sum>>1) apareix el missatge d’advertència: “ La fila n NO suma 1”.

Aquest haurà de sortir del programa i modificar els valors que cregui necessaris, tornant després a executar el programa.

30

1.2 ANÀLISI DE CLASSES DE LA CADENA Un cop dins l'Opció 2 del menú principal veurem un nou menú, en aquest cas el menú de l'Anàlisi d’estat absorbent, que presenta les vuit opcions següents: 1.- Composició en classes d’equivalència. 2.- Càlcul de la matriu d’adjacència A. 3.- Càlcul de la matriu de descendència R. 4.- Càlcul de la matriu d’ascendència Q. 5.- Càlcul de la matriu fonamental M. 6.- Càlcul del vector M1. 7.- Càlcul de la matriu B. 8.- Càlcul de la matriu de probabilitats del graf condensat. El menú està exposat a la secció 3.1 d’aquest manual. Cadascuna d’aquestes opcions podrà ser executada el nombre de cops que es vulgui, i els resultats es mostraran per pantalla alhora que s'enregistraran al fitxer de sortida.

Composició en classes d’equivalència A través d’aquesta opció s’efectua el càlcul de les classes comunicants, és a dir, es defineix el nombre de classes comunicants que existeixen a la cadena de Markov i els estats que la composen. La presentació dels resultats d’aquesta opció es fa de la següent manera: les classes comunicants de la cadena de Markov són numerades pel programa de manera que si la cadena de Markov té k classes comunicants aquestes es numeren amb números entre 1 i k, així que per pantalla apareix el número que representa cada una de les classes i seguidament els estats que formen aquestes classes.

Exemple:

La matriu de probabilitats de transició utilitzada en aquest exemple és la presentada al problema de test no. 1. C

31

C Matriu de probabilitats de transició amb 9 estats. C 1 0.0000 0.0000 0.6000 0.4000 0.0000 0.0000 0.0000 0.0000 0.0000 2 0.0000 0.0000 0.6000 0.4000 0.0000 0.0000 0.0000 0.0000 0.0000 3 0.0000 0.0000 0.0000 0.0000 0.6000 0.2000 0.0000 0.0000 0.2000 4 0.0000 0.0000 0.0000 0.0000 0.6000 0.4000 0.0000 0.0000 0.0000 5 0.6000 0.3000 0.0000 0.0000 0.0000 0.0000 0.0000 0.1000 0.0000 6 0.6000 0.4000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 7 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.7000 0.3000 0.0000 8 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 9 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000

CLASSES COMUNICANTS ====================== La classe 1 es TRANSIENT i està formada pels estats seguents: 1 2 3 4 5 6 La classe 2 es ABSORBENT i està formada pels estats seguents: 7 8 La classe 3 es ABSORBENT i està formada pels estats seguents: 9

Estructura del diagrama

Matriu d’adjacència A La rutina Calcular_A és l’encarregada d’efectuar el càlcul de la matriu A, i ho fa a partir de la matriu de probabilitats inicial: en cas que la probabilitat de transició de l’estat i cap a l’estat j sigui major que zero (i per tant existeix un arc que va de xi cap a xj) el valor de aij serà 1; en cas contrari, és a dir, quan la probabilitat de transició de l’estat xi cap a l’estat xj sigui zero

32

(cosa que implica que no existeix cap camí directe de xi cap a xj) el valor de aij serà 0. La presentació de la matriu d’adjacència A es fa de la manera estàndard, presentant l’element aij a la fila i i la columna j. Exemple: Utilitzant la matriu de transició en un pas presentada al problema de test no. 9 i triant l’opció 2 del submenú d 'anàlisi de classes de la cadena obtindrem una sortida com la següent MATRIU D'ADJACÈNCIA ===================== Estats 1 2 3 4 5 6 1 0 0 1 0 0 0 2 0 0 0 0 0 1 3 0 0 0 0 1 0 4 1 1 0 1 0 0 5 1 0 0 0 0 0 6 0 1 0 0 0 1

Matriu de descendència R

El càlcul de la matriu R s’efectua mitjançant la rutina Calcular_R. Aquesta rutina conté un algorisme que es basa en l'algorisme de Floyd-Warshall i revisa, partint de la matriu A, tots els camins possibles per, a partir de l’estat xi, assolir l’estat xj. L'algorisme de Floyd-Warshall serveix per a trobar el camí més curt entre cada parell de vèrtexs i per a detectar circuits de cost negatiu a partir de la matriu de transició en un pas. Quan en aplicar l'algorisme s'obté que el camí més curt entre un parell de vèrtexs (xi, xj) és finit això implica que xj és successor de xi. En cas que aquest camí sigui infinit podrem afirmar que xj no és successor de xi. L’algorisme fa la cerca, per a cada estat xi, dels seus successors immediats, dels successors dels successors de xi, etc., fins, recursivament, assolir tots els estats a què és possible arribar partint de l’estat xi. La presentació de la matriu R es fa de manera anàloga a la de la matriu A. Exemple:

33

En aquest exemple s’utilitza la matriu de probabilitats de transició corresponent al problema de test no. 1. Escollint l’opció 3 del submenú d’anàlisi de classes de la cadena el programa dóna una sortida com la següent: *MATRIU DE DESCENDÈNCIA ========================= Estats 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 7 0 0 0 0 0 0 1 1 0 8 0 0 0 0 0 0 1 1 0 9 0 0 0 0 0 0 0 0 1

Matriu d’ascendència Q La matriu Q és la transposada de la matriu R, Q=RT. Aquest càlcul es fa mitjançant la rutina Transposar La presentació de la matriu Q es fa de manera anàloga a la de les matrius A i R.

Tractament de classes transients

Matriu fonamental M La matriu M és una matriu quadrada de dimensió k (on k és igual al nombre d’estats transients de la matriu), de manera que té tantes files o columnes com estats transients. L’element mij de la matriu M d’una cadena de Markov amb estats transients és igual al valor esperat de passes que es visita l’estat transient Sj (j-èssim

34

estat transient) si el procés s’inicia a l’estat transient Si (i-èssim estat transient).

El càlcul de la matriu M es fa mitjançant la rutina de resolució d’equacions lineals de les llibreries NAG. Aquest càlcul es fa simultàniament al del vector M1 i la matriu B. La matriu M que s’obté en executar aquesta opció del programa es presenta de manera anàloga a la matriu A de l’opció 1. Exemple: Introduint la cadena de Markov amb 13 estats presentada al problema de test no. 3 i demanant el càlcul de la matriu M obtindrem els següents resultats: MATRIU M = 1 / (I-Q') ================== Estats 1 2 3 5 6 8 10 11 12 13 1 2.11 0.42 0.00 1.37 0.63 0.63 0.47 0.00 0.00 0.00 2 2.11 1.42 0.00 1.37 0.63 0.63 0.47 0.00 0.00 0.00 3 0.74 0.35 1.00 0.78 0.22 0.22 0.17 0.00 0.00 0.00 5 1.05 0.21 0.00 1.68 0.32 0.32 0.24 0.00 0.00 0.00 6 0.53 0.11 0.00 0.84 1.16 1.16 0.87 0.00 0.00 0.00 8 0.00 0.00 0.00 0.00 0.00 2.00 1.00 0.00 0.00 0.00 10 0.00 0.00 0.00 0.00 0.00 2.00 2.00 0.00 0.00 0.00 11 0.00 0.00 0.00 0.00 0.00 2.00 1.67 1.33 0.67 0.17 12 0.00 0.00 0.00 0.00 0.00 2.00 1.33 0.67

35

1.33 0.33 13 0.00 0.00 0.00 0.00 0.00 2.00 1.67 1.33 0.67 1.17

Nombre total de transicions abans d’absorció El vector M1 (resultant del producte de la matriu M amb un vector columna que només conté 1’s i que anomenarem 1) té dimensió k, on k és el nombre d’estats transients que té la cadena de Markov. L’i-èssima component del vector M1 és igual al valor esperat del nombre de passes abans d’entrar en una classe absorbent quan el procés té inici a l’i-èssim estat transient. El càlcul del vector M1 es fa mitjançat la rutina de resolució d’equacions lineals F04ATF de les llibreries NAG, i es fa simultàniament al de les matrius M i B. En executar aquesta opció del programa, aquest presenta el vector M1 en format columna, indicant el valor (mi) de cadascun dels elements del vector.

Exemple Fent servir la matriu de probabilitats de transició presentada al problema de test no. 3 i escollint el càlcul del vector M1 obtindrem el següent resultat MATRIU M1 ========== M1( 1)= 5.631579 M1( 2)= 6.631579 M1( 3)= 3.471053 M1( 5)= 3.815789 M1( 6)= 4.657895 M1( 8)= 3.000000 M1(10)= 4.000000 M1(11)= 5.833333 M1(12)= 5.666667 M1(13)= 6.833333 Els estats 4, 7 i 9 no apareixen per pertànyer a una classe absorbent (la classe 3).

36

Probabilitats d’absorció B La matriu B és de dimensió k*m, on k és el nombre d’estats transients i m és el nombre d’estats absorbents que conte la cadena de Markov. L’element bij de la matriu B correspon a la probabilitat de que si una cadena de Markov s’inicia a l’estat transient Si entrarà per primer cop en una classe absorbent visitant l’estat Sj. El càlcul de la matriu B es fa mitjançant la rutina de resolució d’equacions lineals F04ATF de les llibreries NAG alhora que es calculen la matriu M i el vector M1. La presentació de la matriu B en executar aquesta opció del menú serà anàloga a la de la matriu M de l’opció 6. Exemple:

Tornant a la matriu de probabilitats de transició del problema de test no. 3 i en cas de demanar el càlcul de la matriu B el programa donarà el següent resultat: MATRIU B ========= Estats 4 7 9 1 0.00 1.00 0.00 2 0.00 1.00 0.00 3 0.50 0.50 0.00 5 0.00 1.00 0.00 6 0.00 1.00 0.00 8 0.00 1.00 0.00 10 0.00 1.00 0.00 11 0.00 1.00 0.00 12 0.00 1.00 0.00 13 0.00 1.00 0.00

Càlcul de les matrius M i B i del vector M1

37

Atès que el càlcul de les matrius M i B i del vector M1 estan basats en un sistema lineal on la matriu d’aquest sistema és ( )I Q− poden determinar-se de forma simultània. Dels resultats presentats a l'apartat de teoria es pot deduir fàcilment que les equacions següents són correctes:

( )( )( )

I Q M II Q MI Q B R

− =− =− =

1 1

on I és la matriu identitat de dimensió igual al nombre d'estats transients de la cadena de Markov, 1 és un vector columna que conté només 1’s i R és la submatriu inferior esquerra pertanyent a la matriu de probabilitats reordenada P. Per tal de simplificar la resolució de les opcions 5, 6 i 7 hem aprofitat la necessitat d'utilitzar la matriu fonamental ( )I Q− en qualsevol dels càlculs a fi de resoldre tots els càlculs mitjançant un sol sistema d'equacions. Amb aquesta intenció ha estat creada la rutina Trobar_DRETA. Aquesta rutina es basa en el següent resultat algèbric:

( )( )( )

| | ) ( | | )I Q M II Q MI Q B R

M M R I− =− =− =

⇒ =1 1 1 1(I - Q)(B

És evident que un cop creada la matriu (R|1|I) (que al programa anomenarem DRETA) podrem resoldre els tres sistemes d'equacions com si en fossin un de sol. Són utilitzades tres rutines per tal de resoldre aquest problema: per començar, la subrutina Trobar_DRETA crea i guarda la matriu (R1I) com a DRETA; tot seguit la rutina Solucio_Sistema resol, fent ús de la rutina F04ATF de les llibreries NAG, el sistema presentat anteriorment, de manera que obtindrem com a resultat la matriu (BM1M), que al programa anomenarem SOL. Finalment, la rutina Tractar_Solucio tracta la matriu SOL de manera que en treu i emmagatzema les submatrius B, M1 i M que cercàvem.

38

1.3 ANÀLISI D’ESTAT ESTACIONARI Un cop dins l’Opció 3 del menú principal, veurem un menú, en aquest cas el menú de l’Anàlisi d’estat estacionari, amb tres opcions: Probabilitats d’estat estacionari, Temps promitjos de primer pas i les Equacions de Chapman-Kolmogorov. Les tres opcions es podran executar el nombre de vegades que es vulgui, i els resultats es mostraran per pantalla alhora que s’enregistraran al fitxer de sortida en un format molt semblant al que apareix per pantalla (tants cops com s’executi una opció). No es pot dur a terme l’opció 2 (temps promitjos de primer pas) prèviament a l'opció 1 (probabilitats d’estat estacionari). Això es deu a que pel càlcul del temps promitjos s’utilitza els valors de les π‘s, i per tant sembla lògic que primer s’executi aquesta opció i després la 2. Si es prova apareix per pantalla el següent missatge: “* Cal executar primer l’opció 1“.

Probabilitats d’estat estacionari Per a una cadena de Markov qualsevol el programa analitza les diferents classes que la componen i permet calcular les probabilitats a llarg termini per als estats de les classes absorbents10, siguin o no periòdiques. Si es tracta d’una classe periòdica (de període k>1) llavors el tractament que fa el programa per tal de trobar les probabilitats a llarg termini és completament diferent del cas en que la classe és aperiòdica.

Classe aperiòdica El procés utilitzat per tal de calcular les probabilitats d’estat estacionari és el següent: Teorema 1: Sigui P la matriu de transició per a s estats d’una cadena de Markov ergòdica. Llavors existeix un vector π = [ π1 π2 . . . πs ] tal que

10 Entenem com a classes absorbents d' una cadena totes aquelles que no són transients.

39

lim Pn

n

s

s

s

→∞=

π π ππ π π

π π π

1 2

1 2

1 2

. . .

. . .. . .. . .. . .

. . .

Cal recordar que l’element ij-èssim de Pn és Pij

(n). El teorema 1 diu que per qualsevol estat inicial i, lim P n

n ij j→∞=( ) π

S’observa que per a valors grans de n, Pn s’aproxima a una matriu amb totes les files pràcticament iguals. Això significa que a llarg termini, la cadena de Markov s’instal·la, i (independentment de l’estat inicial i) existeix la probabilitat π j que trobar-se a l’estat j. El vector π = [ π1 π2 . . . πs ] s’anomena la distribució d’estat estacionari o distribució d’equilibri, de la cadena de Markov. Per a una cadena amb matriu de transició P, es pot trobar la distribució d’estat estacionari?. Del teorema 1, s’observa que per a valors alts de n i per tot i, P n P nij ij j( ) ( )+ ≅ ≅1 π (1) des que P nij ( )+ =1 ( fila i-èssima de Pn ), caldrà escriure

P n P n pij ik kjk

k s

( ) ( )+ ==

=

∑11

(2)

Si n és gran, se substitueix (1) dintre (2)

π πj k kjk

k s

p==

=

∑1

(3)

En notació matricial, (3) caldrà escriure π π= P (3)’ Desafortunadament, el sistema d’equacions especificat a (3) té un nombre infinit de solucions, perquè el rang de la matriu P sempre resulta ser ≤s-1.

40

Per obtenir un únic valor per a les probabilitats d’estat estacionari, es veu que per qualsevol n i qualsevol i P n P n P ni i is1 2 1( ) ( ) ( )+ + ⋅ ⋅ ⋅ + = (4) Deixem que n s’aproximi infitament a (4), s’obtindrà π π π1 2 1+ + ⋅ ⋅ ⋅ + =s (5) Per això, després de substituir les equacions a (3) per (5), s’haurà d’utilitzar (3) per tal de resoldre les probabilitats d’estat estacionari. D’aquí s’obtindrà les probabilitats a llarg termini. El procés que segueix el programa és el següent:

Les probabilitats d’estat estacionari verifiquen: Ptπ π− = 0 i π ii

n

=∑ =

!

1.

p p pp p p

p p p

n n

n n

n n nn n n

11 1 1 21 2 1

12 1 22 2 2 2

1 1 2 2

00

0

π π π ππ π π π

π π π π

− + + ⋅ ⋅ ⋅ ++ − + +

⋅ ⋅⋅ ⋅⋅ ⋅+ + ⋅ ⋅ ⋅ + −

=⋅⋅⋅

,

se substitueix una qualsevol de les files del primer sistema per la segona

equació π ii

n

=∑ =

!

1.

el nou sistema en notació matricial quedarà de la següent manera

π π ππ π π π

π π π π

1 2

12 1 22 2 2 2

1 1 2 2

10

0

+ + ⋅ ⋅ ⋅ ++ − + +

⋅ ⋅⋅ ⋅⋅ ⋅+ + ⋅ ⋅ ⋅ + −

=⋅⋅⋅

n

n n

n n nn n n

p p p

p p p

,

41

la fila substituïda és sempre la primera i correspondrà a la primera columna de la matriu de probabilitats, pel fet de transposar-se anteriorment. S’utilitza la llibreria matemàtica NAG per a resoldre el sistema.

1 1 11

1

10

0

12 22 2

1 2

1

2

⋅ ⋅ ⋅−

⋅ ⋅⋅ ⋅⋅ ⋅

⋅ ⋅ ⋅ −

⋅⋅⋅

=⋅⋅⋅

p p p

p p p

n

n n nn n

ππ

π

Es comprova la validesa dels valors obtinguts a través del càlcul de residus com s’explicarà posteriorment.

Exemple: S’utilitza el problema de test no. 4. Una cadena de Markov irreductible formada per quatre estats. • El resultat que s’obté amb aquest conjunt de dades serà el següent Probabilitats de transició a llarg termini. pi( 111) = 0.503067 pi( 2) = 0.055215 pi( 3) = 0.233129 pi( 4) = 0.208589 • És pot comprovar com la suma de les probabilitats és 1 i mitjançant el càlcul dels residus es pot veure el nivell d’aproximació.

Classe Periòdica El procés utilitzat per tal de calcular les probabilitats a llarg termini és el següent: sigui una matriu P de probabilitats de transició

11 Aquests valors corresponen als estats, s’especifica clarament a quin estat pertany la probabilitat.

42

P

p p pp p p

p p p

n

n

n n nn

=

⋅ ⋅ ⋅⋅ ⋅ ⋅

⋅ ⋅⋅ ⋅⋅ ⋅

⋅ ⋅ ⋅

11 12 1

21 22 2

1 2

.

Es multiplica successivament per sí mateixa fins a obtenir uns valors que no difereixin molt d’una iteració a la següent.

P

p p pp p p

p p p

n

n nn

n

n nn

n

nn

nn

nnn

=

⋅ ⋅ ⋅⋅ ⋅ ⋅

⋅ ⋅⋅ ⋅⋅ ⋅

⋅ ⋅ ⋅

11 12 1

21 22 2

1 2

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

Un cop multiplicada la matriu de probabilitats per sí mateixa un determinat nombre de vegades s’efectua un recorregut per cadascun dels estats i es cerca un element per a cada columna que sigui diferent de 0; aquest valor no és res més que la probabilitat de trobar-se en aquell estat després de n transicions, on n és el nombre de cops que s’ha multiplicat la matriu original tenint en compte que la classe és periòdica, per tant aquest valor es va repetint cada k períodes, on el valor de k és el període de la classe. Exemple: El problema de test no. 5 conté una cadena de Markov irreductible, formada doncs per una sola classe que contindrà tots els estats. El període de la classe és 2. El programa, en cas d’existir una o més classes periòdiques, identifica els grups de periodicitat i els estats pertanyents a cada grup de periodicitat per a cada classe (absorbent) existent.

• El resultat que s’obté amb aquest conjunt de dades serà el següent

SOLUCIO de les probabilitats de la CLASSE ABSORBENT formada pels estats: 1 2 3 4 PI_B( 1)= 0.166667 PI_B( 2)= 0.166667

43

PI_B( 3)= 0.333333 PI_B( 4)= 0.333333

Residus També apareixen per pantalla, conjuntament amb la solució del sistema, els residus. Aquests són els valors que s’obtenen en substituir les π obtingudes com a solució, dins l’equació [Pt*π-π]. Exemple: Utilitzant les dades del problema de test no. 4 s’obtindrà una sortida per pantalla amb 7 xifres decimals com la següent

SOLUCIO de les probabilitats de la CLASSE ABSORBENT formada pels estats: 1 2 3 4 PI_B( 1)= 0.166667 PI_B( 2)= 0.166667 PI_B( 3)= 0.333333 PI_B( 4)= 0.333333

• Amb uns residus aproximats de SOLUCIO de les probabilitats de la CLASSE ABSORBENT formada pels estats: 1 2 3 4 residu( 1) = 0.0000000 residu( 2) = 0.0000000 residu( 3) = 0.0000000 residu( 4) = 0.0000000

44

2.3.1.4 Cost mig esperat per unitat de temps El cost mig esperat per unitat de temps a llarg termini obeeix a l’expressió:

( ) ( )lim En

C X C jn t

t

n

jj

M

→∞= =∑ ∑

=

10!

π

Exemple:

Es disposa d’aquest fitxer de costos: C C comentaris del fitxer de costos. C VECTOR DE COSTOS. ------------------------------- 1 : 1.50 2 : 5.60 3 : 8.10 4 : 12.30 • Per a unes probabilitats a llarg termini com les següents: PI_B( 1)= 0.166667 PI_B( 2)= 0.166667 PI_B( 3)= 0.333333 PI_B( 4)= 0.333333

• S’obtindrà el següent valor com a cost mig esperat en funció dels costos

* Si tenim en compte els costos, el cost mig esperat per unitat de temps a la llarga serà de: 1.50 * ( 0.17) + 5.60 * ( 0.17) + 8.10 * ( 0.33) + 12.30 * ( 0.33) = 7.98

Temps mitjos de primer pas Per a una cadena de Markov ergòdica, sigui µij el nombre esperat de transicions abans de trobar-se a l’estat j, donat que es troba a l’estat i. µij és el temps mig de primer pas de l’estat i a l’estat j. Les magnituds µij verifiquen el següent sistema lineal:

45

µ µij ij ik kjk j

p p= + +≠∑ ( )1

per i=j es té la relació µπii

i

=1

El mètode de resolució mitjançant la utilització de llibreries matemàtiques, concretament la rutina F04ATF de les llibreries NAG, que permet la resolució de sistemes compatibles determinats. El sistema anterior passarà a ser n sistemes de (n-1)x(n-1) equacions/incògnites. Per tant caldrà resoldre per als n estats els (n-1) valors, perquè ja es disposa de les µ ii de forma directa.

Exemple: Utilitzant les dades del problema de test no. 6 s’obtindrà una sortida per pantalla amb 7 xifres decimals com la següent • El resultat que s’obté amb aquest conjunt de dades serà el següent

Solucions del temps esperat de primer pas per l'estat 1 mu( 1, 1)= 9.000002 mu( 2, 1)= 7.000000 mu( 3, 1)= 8.000000 mu( 4, 1)= 9.000000 mu( 5, 1)= 8.000000 mu( 6, 1)= 9.000000 Solucions del temps esperat de primer pas per l'estat 2 mu( 1, 2)= 2.000000 mu( 2, 2)= 3.000001 mu( 3, 2)= 1.000000 mu( 4, 2)= 2.000000 mu( 5, 2)= 1.000000 mu( 6, 2)= 2.000000 Solucions del temps esperat de primer pas per l'estat 3 mu( 1, 3)= 3.571429 mu( 2, 3)= 4.142857 mu( 3, 3)= 5.142858 mu( 4, 3)= 1.000000 mu( 5, 3)= 5.142857 mu( 6, 3)= 4.857143 Solucions del temps esperat de primer pas per l'estat 4 mu( 1, 4)= 9.000000 mu( 2, 4)= 7.000000 mu( 3, 4)= 8.000000 mu( 4, 4)= 9.000002 mu( 5, 4)= 8.000000 mu( 6, 4)= 9.000000 Solucions del temps esperat de primer pas per l'estat 5 mu( 1, 5)= 4.600000 mu( 2, 5)= 6.200000 mu( 3, 5)= 7.200000 mu( 4, 5)= 8.200000 mu( 5, 5)= 7.200001 mu( 6, 5)= 2.800000 Solucions del temps esperat de primer pas per l'estat 6 mu( 1, 6)= 9.000000 mu( 2, 6)= 7.000000 mu( 3, 6)= 8.000000 mu( 4, 6)= 9.000000 mu( 5, 6)= 8.000000 mu( 6, 6)= 9.000002

46

Equacions de Chapman-Kolmogorov Les equacions de Chapman-Kolmogorov proporcionen un mètode per a calcular les probabilitats de transició en n passos, pij

n( ) . Aquestes probabilitats de transició poden ser útils quan el procés es troba a l’estat i i es desitja la probabilitat que el procés es trobi a l’estat j després de n períodes. En el cas en que les cadenes de Markov no continguin classes periòdiques, les equacions de Chapman-Kolmogorov poden utilitzar-se també per obtenir una aproximació de les π‘s. La potència successiva (n) de la matriu de probabilitats de transició P proporciona les probabilitats de transició condicionals de trobar-se en qualsevol dels estats de la cadena de Markov després de n passos. Finalment, si es vol obtenir la probabilitat de transició no condicional, d’una o n passes, de trobar-se a un estat qualsevol de la cadena de Markov cal haver introduït la distribució de probabilitat de l’estat inicial Q iX0

( ) , on { }Q i P X iX0 0( ) = = , per a 0, 1, . . ., M. de forma que { }P X j Q p Q p Q M pn X j

nX j

nX Mj

n= = + + ⋅ ⋅ ⋅ +0 0 0

0 10 1( ) ( ) ( )( ) ( ) ( ) Aquestes probabilitats inicials s’introduiran tal com s’ha especificat abans. Dins l’apartat de l’anàlisi d’estats estacionari, el programa també permet obtenir la potència n-èssima de la matriu de transicions en un pas. Això pot servir a l’usuari per trobar la Pij

(n) per a un valor de n determinat i utilitzar el vector de probabilitats inicials introduït mitjançant fitxer o de forma manual per l’usuari. Exemple: A partir del problema de Test no. 9, si volem obtenir la potència 30-èssima de la matriu de probabilitats de transició caldrà disposar també de les probabilitats inicials associades a cadascun dels estats. Haurà de ser un fitxer de probabilitats inicials com el següent: C C comentaris del fitxer de probabilitats inicials.

47

C VECTOR DE PROBABILITATS INICIALS. --------------------------------------------------------- 1 : 0.0000000 2 : 0.1200000 3 : 0.3000000 4 : 0.2500000 5 : 0.2200000 6 : 0.1100000 • Per a una potència n-èssima (en aquest cas 30) de la matriu de probabilitats inicials obtindrem una probabilitat no condicional per a cadascun dels estats de la cadena de Markov. Obtindrem unes probabilitats no condicionals per cadascun dels estats com les següents: POTÈNCIA 30 DE LA MATRIU DE PROBABILITATS ============================================ Estat 1 2 3 4 5 6 1 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 2 0.0000 0.2500 0.0000 0.0000 0.0000 0.7500 3 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 4 0.0714 0.1250 0.1429 0.0000 0.2857 0.3750 5 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 6 0.0000 0.2500 0.0000 0.0000 0.0000 0.7500 * Probabilitat després de 30 transicions per l'estat 1 0.01786 * Probabilitat després de 30 transicions per l'estat 2 0.08875 * Probabilitat després de 30 transicions per l'estat 3 0.33571 * Probabilitat després de 30 transicions per l'estat 4 0.00000 * Probabilitat després de 30 transicions per l'estat 5 0.29143 * Probabilitat després de 30 transicions per l'estat 6 0.26625

2 PROBLEMES D’EXEMPLE. Les dades es presentaran de la següent manera. Primer la matriu de probabilitats de transció ordenada per estats i seguidament la representació gràfica de la cadena de Markov. ∇ Problema de test nº1

48

P =

123456789

0 0 0 0 0 6 0 4 0 0 0 0 0 0 0 0 0 00 0 0 0 0 6 0 4 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 6 0 2 0 0 0 0 0 20 0 0 0 0 0 0 0 0 6 0 4 0 0 0 0 0 00 6 0 3 0 0 0 0 0 0 0 0 0 0 01 0 00 6 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . .0 0 0 0 0 0 0 0 7 0 3 0 00 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10

. . . . . .. . . . . . . . .. . . . . . . . .

1

2

3

4

5

6

78

9.2

.1

1 .

.3

.8.4

.4

.6

.6

.2

.6

.6

.6

.3 .6

.6

.4

1 .

∇ Problema de test nº2

P =123

0 0 08 0 20 3 0 7 0 001 05 0 4

. . .

. . .

. . .

1 2

3

. 8

. 3. 7

. 5. 1

. 4

. 2


49

P

123456789

10111213

=

0 00 0 20 0 00 0 00 050 0 30 0 00 0 00 0 00 0 00 0 00 0 00 0 00100 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 000 00 0 20 0 00 050 0 30 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 000 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 100 0 00 0 00 0 00 0 00050 0

. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. .00 0 00 0 00 0 00 0 00 050 0 00 0 00 0 00 0 00 0 00 0 00

0 00 0 00 0 00 0 00 050 0 00 0 00 0 25 0 00 0 25 0 00 0 00 0 000 00 0 00 0 00 100 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 000 00 0 00 0 00 0 00 0 00 0 00 050 0 00 0 00 050 0 00 0 00 0 000 00 0 00 0 00 0 00 0 00 0 00 100 0 00 0

. . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .

00 0 00 0 00 0 00 0 000 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 100 0 00 0 00 0 00 0 000 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 050 0 00 050 0 000 00 0 00 0 00 0 00 0 00 0 00 0 00 0 50 0 00 0 00 0 25 0 00 0 250 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 100 0 00 0 00

1 2 3 4

5 6

7

89

10

11

12

13

x1 x6 x10 x1

1

x13

x12

x8

x5x2

x3

x4

x9

x7

.3

1.5 .5

.5.5

.5 .5

1

.5

.5 .5

.5

.51

.5.5

.3.2

.5

1

1

1

X2


P =

1234

0 70 0 00 0 00 0 300 20 0 20 0 40 0 200 60 010 010 0 200 00 010 0 90 0 00

. . . .

. . . .

. . . .

. . . .

50

1

2

3

4

. 3

. 7

. 6 . 1. 2

. 9

. 2

. 1

. 2

. 4

. 2. 1


P =

1234

0 00 100 0 00 0 000 00 0 00 100 0 000 00 0 00 0 00 100050 0 00 050 0 00

. . . .

. . . .

. . . .

. . . .

1 2

34

1 .

1 . .5

.5

1 .


P =

123456

0 00 0 00 050 0 00 050 0 000 33 0 00 0 00 0 33 0 00 0 330 00 100 0 00 0 00 0 00 0 000 00 0 00 100 0 00 0 00 0 000 00 100 0 00 0 00 0 00 0 000 00 0 00 0 25 0 00 0 75 0 00

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

51

1

2 3

4

5

6

.5.5

.333

.333.333

1.

1 .

1.

.75

.25


P =

1234

0 200 0800 0 000 0 0000 000 0 000 0 900 01000 400 0500 0100 0 0000 000 0 000 0 000 1000

. . . .

. . . .

. . . .

. . . .

1

2

3

4

.2

1.

.1

.5.9

.4

.8

.1


P =

0 000 1000 0 000 0 0000 000 0 000 1000 0 0000 000 0 000 0 000 10000500 0500 0 000 0 000

. . . .

. . . .

. . . .

. . . .

52

1 2

34

1 .

1 . . 5

1 .

. 5


P

123456

=

0 00 0 00 100 0 00 0 00 0 000 00 0 00 0 00 0 00 0 00 1000 00 0 00 0 00 0 00 100 0 000 25 0 25 0 00 050 0 00 0 00100 0 00 0 00 0 00 0 00 0 000 00 0 33 0 00 0 00 0 00 0 66

. . . . . .

. . . . . .

. . . . . .

. . . . . .. . . . . .. . . . . .

1

2

3

4

5

6

.5 .25

.25

1. 1.

1 .

.33

.66

1.


P

1234567

=

0 05 0 0 05 0 00 05 0 05 0 0 00 0 0 1 0 0 00 0 0 0 1 0 00 0 0 0 1 0 00 0 05 0 0 0 050 0 0 05 0 05 0

. .

. .

. .. .

53

X 1

X

X

X

X

X

X

. 5

.5

.5

.5

.5

1 .1 .

1 .

.5

.5

.5


P =

12345

0 00 0 60 0 30 010 0 000 00 0 30 0 20 0 20 0 300 00 010 0 40 0 00 0500 00 0 00 0 00 100 0 000 00 0 00 0 00 0 00 100

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1

2

34

5

1 .

1 .

.5

.3.1

.2

.6

.2

.1

.3

. 3

.4

54

55

3 MANIPULACIÓ Per tal d'executar el programa dins l’entorn VAX/VMS cal donar la comanda: $Run CADENA.

Presentació

El primer que apareixerà serà un pantalla de presentació. Aquesta pantalla presentarà un format com el de la imatge. Per sortir d’aquesta pantalla caldrà prémer la tecla <Enter>. Un cop fora d’aquesta pantalla de presentació ens apareixerà el Menú principal.

Pantalla 1 Presentació.

56

3.1.2 Menú principal

Un cop dins el Menú principal veurem les següents opcions possibles (Introducció de dades, Anàlisi de classes de la cadena, Anàlisi d’estats estacionari i Sortir del programa ). Un cop escollida l’opció caldrà prémer la tecla <Enter>.

Pantalla 2 Mení Principal.

• Observacions: 1.- La introducció de dades és la primera acció a fer. Si s’escull l’Opció 2 o la 3 prèvia a la 1, no duran a terme cap càlcul. 2.- Si introduïm un valor que no sigui cap dels possibles s’ignorarà i es tornarà a preguntar per l’opció a escollir.

57

3.1.3 Introducció de dades Si l’opció escollida dins del menú principal ha estat la primera, Introducció de dades, ens apareixerà un altre menú com el següent.

Pantalla 3 Introducció de dades.

• Observacions: 1.- Si introduïm un valor que no sigui cap dels possibles s’ignorarà i es tornarà a preguntar per l’opció a escollir. 2.- Tant si s’escull l’Opció 1 com la 2 el primer que es demanarà serà el nom del fitxer de sortida o registre de la sessió on volem guardar els resultats que vagin apareixent per pantalla. 3.- Si s’escull l’opció 1 és passarà a llegir les dades de forma manual. Altrament el primer que es demanarà serà el nom del fitxer que ha de contenir les probabilitats de transició en un pas.

58

3.1.3.1 Fitxer de sortida Com bé es diu a les observacions de la pantalla anterior, tant si s’escull la introducció de dades de forma manual com mitjançant fitxers, l’acció prèvia que caldrà fer sempre serà escollir si es vol guardar la informació en un fitxer de sortida.

Pantalla 4 Fitxer de Sortida.

• Observacions: 1.- El programa dóna (per defecte) com a certa l’afirmació de crear un fitxer de sortida. Únicament cal prémer la tecla <Enter> per a confirmar l’acció. Altrament cal escriure “n” o “N” (s’admeten les dues possibilitats). 2.- Si es vol un fitxer de sortida per enregistrar la sessió es demanaria el nom d’aquest. S’aconsella que els noms i extensió dels fitxers de sortida sigui per exemple: *.RES.

59

3.1.3.2 Manual

Un cop introduït el nom del fitxer de sortida i si hem escollit l’opció Manual a l'hora d’introduir les dades, el primer que caldrà saber serà la dimensió del problema. Podem veure més clar tot el procés amb un exemple:

Pantalla 5 Lectura manual I.

• Observacions: 1.- La dimensió és el nombre total d’estats que componen la cadena. Cal que aquest valor sigui superior a 1 i per sota del límit màxim establert dins el parametre NMAX que conté el fitxer PARAMS.FOR. 2.- Un cop escollida la dimensió cal prémer la tecla <Enter> per confirmar l’acció. El valor ha de ser enter.

60

• Continuació de l’exemple d’introducció de dades de forma Manual

Un cop introduïda la dimensió cal introduir les probabilitats de transició en un pas que composaran la matriu P.

Pantalla 6 Lectura manual II.

• Observacions: 1.- S’introdueixen els valors un a un. Valors de tipus real. En cas d’errada, és a dir, que el valor no sigui correcte (per sobre d’1 o bé per sota de 0) es demana de nou el valor. Cal prémer la tecla <Enter> per a confirmar el valor cada vegada. 2.- Si el valor d’una fila no suma 1, llavors un cop introduïdes totes les probabilitats, ho adverteix amb un missatge12 i demana que es rectifiquin tots els valors que calgui per tal les probabilitats sumin 1.

12 Advertència: “El valor introduït es troba per sobre d'1 o per sota de 0“.

61


Un cop introduïda la matriu de probabilitats de transició, cal omplir el vector de probabilitats inicials associades a cadascun dels estats.

Pantalla 7 Lectura manual III.

• Observacions:

1.- S’introdueixen els valors un a un. Valors de tipus real. En cas d’errada, és a dir, que el valor no sigui correcte (per sobre d’1 o bé per sota de 0) es demana de nou el valor. Cal prémer la tecla <Enter> per a confirmar el valor cada cop. 2.- Si el valor de les probabilitats inicials per a tots els estats no suma 1, ho adverteix13 i demana que es rectifiquin tots els valors que calgui per tal d'acomplir-se la probabilitat.

13 Advertència: “El valor de les probabilitats inicials per a tots els estats no suma 1“.

62


Un cop introduïdes les probabilitats inicials, cal omplir el vector de costos associats a cadascun dels estats. Aquests costos composaran el vector VC.

Pantalla 8 Lectura manual IV.

• Observacions: 1.- S’introdueixen els valors un a un. Valors de tipus enter, malgrat que el programa els tracta com a reals a l'hora de fer operacions. No admet costos negatius. El valor del cost no pot ser superior a 104. 2.- Cal prémer la tecla <Enter> a fi de confirmar el valor cada vegada i un cop finalitzada la operació de lectura de tots els valors.

63

3.1.3.3 Fitxer Un cop introduït el nom del fitxer de sortida i si hem escollit l’opció Fitxer a l'hora d’introduir les dades, el primer que caldrà saber serà el nom del fitxer que conté les probabilitats de transició en un pas que composen la matriu P. Podem veure més clar tot el procés amb un exemple:

Pantalla 9 Lectura fitxer I.

• Observacions: 1.- El nom del fitxer ha de constar d’un màxim de 13 lletres contant el punt. Les vuit primeres són per al nom que identifica les dades i les tres darreres per a distingir el tipus de format en què està escrit. 2.- Cal prémer la tecla <Enter> per a confirmar el nom del fitxer. En cas de no existència prèvia d’aquest fitxer s’advertirà14 de l’errada mitjançant un missatge per pantalla.

14 Advertència: "No existeix cap fitxer amb aquest nom".

64

• Continuació de l’exemple d’introducció de dades amb Fitxers

Un cop introduïdes les probabilitats de transició, cal omplir el vector de probabilitats inicials associades a cadascun dels estats.

Pantalla 10 Lectura fitxer II.

• Observacions: 1.- El nom del fitxer ha de constar d’un màxim de 13 lletres contant el punt. Les vuit primeres són per al nom que identifica les dades i les tres darreres per distingir el tipus de format en què està escrit. 2.- Cal prémer la tecla <Enter> per confirmar el nom del fitxer. En cas de no existència prèvia d’aquest fitxer s’advertirà de l’errada mitjançant un missatge per pantalla.

65

• Continuació de l’exemple d’introducció de dades amb Fitxers

Un cop introduïdes les probabilitats inicials, cal omplir el vector de costos associats a cadascun dels estats.

Pantalla 11 Lectura fitxer III.

• Observacions: 1.- El nom del fitxer ha de constar d’un màxim de 13 lletres contant el punt. Les vuit primeres són pel nom que identifica la dades i les tres darreres per distingir el tipus de format en què està escrit. 2.- Cal prémer la tecla <Enter>* per a confirmar el nom del fitxer. En cas de no existència prèvia d’aquest fitxer s’advertirà de l’errada mitjançant el següent missatge:“No existeix cap fitxer amb aquest nom“. 3.- La dimensió ha de coincidir amb la dimensió del fitxer anterior. Altrament també ho adverteix. Si s’han rectificat valors també s’adverteix.

66

• Continuació de l’exemple d’introducció de dades amb Fitxers Un cop introduïts els costos ja tenim totes les dades que necessita el programa per tal de poder dur a terme qualsevol dels càlculs possibles.

Pantalla 12 Lectura fitxer IV.

• Observacions: 1.- Cal prémer la tecla <Enter> per a confirmar el nom del fitxer. En cas de no existència prèvia d’aquest fitxer s’advertirà de l’errada mitjançant el següent missatge:“No existeix cap fitxer amb aquest nom“. 2.- La dimensió ha de coincidir amb la dimensió dels fitxers anteriors. Altrament també ho adverteix.

67

3.1.4 Anàlisi de classes de la cadena

Un cop introduïdes les dades, si decidim escollir la segona opció del menú principal, anàlisi de classes de la cadena, ens apareixerà un altre menú com el següent

Pantalla 13 Anàlisi de classes de la cadena.

Observacions: 1.- L’ordre d’execució de les opcions és independent, no està establert. 2.- Si escollim les opcions 5, 6 i 7 i no disposem d’estats absorbents se'ns farà saber mitjançant un missatge15. 3.- Cada cop que s’esculli una opció d’aquest menú, els resultats que apareixeran per pantalla s’enregistraran al fitxer de sortida (sempre que s’hagi escollit aquesta opció prèviament).

15 Missatge: “Tots els estats són absorbents, i per tant no hi ha cap estat transient, de manera que el càlcul de les matriu M, M1 i B no té sentit”.

68

3.1.5 Anàlisi d’estats estacionari

En canvi, si escollim la tercera opció del menú principal, anàlisi d’estats estacionari , el menú que apareixerà serà

Pantalla 14 Anàlisi d’estats estacionari.

Observacions: 1.- Cal executar l’opció 1 prèviament a l’opció 2. La raó esta documentada dins l’apartat 2.3 d’aquest manual. 2.- Si introduïm un valor que no sigui cap dels possibles s’ignorarà i es ornarà a demanar l’opció a escollir. Caldrà prémer la tecla <Enter> per tal de confirmar l’opció escollida. 3.- Cada cop que s’esculli una opció d’aquest menú, els resultats que apareixeran per pantalla s’enregistraran al fitxer de sortida (sempre que s’hagi escollit aquesta opció prèviament).

69

Documents

PRÀCTIQUES DE CADENES DE MARKOV Esteve Codina Sancho · 1 diplomatura d’estadÍstica investigaciÓ operativa estocÀstica prÀctiques de cadenes de markov esteve codina sancho