Nuevo

Universidad del Pa´ Vasco ıs Matem´tica Aplicada y Estad´ a ıstica

Matrices no negativas, paseos aleatorios y cadenas de Markov
Juan-Miguel Gracia

Extracto: Damos algunas definiciones de digrafo, cadena de Markov, paseo aleatorio, as´ como su reı laci´n con la teor´ de Perron-Frobenius de matrio ıa ces no negativas. Contiene programas en Matlab.

Copyright 2008 juanmiguel.gracia@ehu.esActualizado el: 28 de noviembre de 2008 (enlaces revisados) Version final, 11 de noviembre de 2002

©

Tabla de Contenido
1. Digrafos 1.1. Subdigrafo 1.2. Paseo 1.3. Digrafo fuertemente conexo 1.4. Digrafo ponderado 1.5. Isomorfismo de digrafos 1.6. Paseo aleatorio 2. Potencias de una matriz 3. Matrices no negativas 3.1. Forma normal de una matriz reducible 3.2. Teoremas de Perron y Frobenius3.3. Matrices reducibles 3.4. Matrices primitivas 3.5. Matrices estoc´sticas a 4. Cadenas de Markov discretas 4.1. Estados recurrentes, transitorios y absorbentes • Periodicidad 4.2. Cadenas de Markov reducibles 4.3. Cadenas de Markov cualesquiera 5. Clases de una matriz no negativa

Tabla de Contenido (cont.)

3

6. Matlab • Forma normal de una matriz reducible en Matlab • Forma de Frobeniusen Matlab • Relaciones binarias en Matlab 7. Soluciones 8. Acreditaciones 8.1. Agradecimientos

Toc

Volver

Doc

Doc

4

1. Digrafos La terminolog´ sobre grafos no est´ estandarizada y var´ m´s de lo ıa a ıa a que ser´ de desear de unos autores a otros. Hasta donde llega nuestra ıa experiencia sobre este tema, nos induce a leer con cuidado las definiciones de cada autor. En laliteratura, muchos conceptos no son siquiera definidos y se debe apelar a su significado intuitivo. Nuestras definiciones persiguen la claridad formal, conscientes del sacrificio intuitivo del tema; ´ste aspecto e lo fiamos a las figuras que insertamos. Un digrafo (grafo dirigido u orientado) D es un par (V, E) donde V es un conjunto finito de elementos llamados v´rtices (puntos o nodos) e y E es unsubconjunto de V × V . Todo par ordenado (a, b) ∈ E se llama arco del digrafo D. N´tese que un digrafo puede contener tanto los arcos o (a, b) y (b, a) con a y b v´rtices distintos como arcos de la forma (a, a); ´stos e e ultimos arcos se denominan lazos . Los v´rtices a y b de un arco α = (a, b) ´ e se llaman extremos del arco α. Adem´s, a es el v´rtice inicial u origen y b a e es el v´rtice final de α. Sedice que el arco (a, b) es incidente con los v´rtices e e a y b. El n´mero de arcos que salen de un v´rtice es el grado saliente del u e v´rtice. El n´mero de arcos que entran en un v´rtice es el grado entrante e u e del v´rtice. Convenimos que un lazo en un v´rtice aporta una unidad al e e grado saliente y tambi´n una unidad al grado entrante. Se dice que el arco e (a, b) es incidente con losv´rtices a y b. e

Toc

Volver

Doc

Doc

Secci´n 1: Digrafos o

5

1.1. Subdigrafo Un subdigrafo del digrafo D = (V, E) es un digrafo D1 = (V1 , E1 ) tal que V1 ⊂ V y E1 ⊂ E. Se dice que el subdigrafo D1 es un subdigrafo generador de D si D1 tiene el mismo conjunto de v´rtices que D, es decir, si V1 = V . e 1.2. Paseo Un paseo de D es una secuencia finita de v´rtices w = (v0 , v1 , . .. , vp ) tal e que (vi−1 , vi ) ∈ E para i = 1, 2, . . . , p y p > 0. El n´mero p es la longitud u del paseo w. Este n´mero coincide con el n´mero de arcos u u (v0 , v1 ), (v1 , v2 ), . . . , (vp−1 , vp ) del paseo w; contando los arcos cuantas veces se pase por ellos para ir desde el v´rtice v0 al v´rtice vp . e e

Toc

Volver

Doc

Doc

Secci´n 1: Digrafos o

6

Ejemplo 1.1Consideremos el digrafo D representado por la Figura 1. % /(R )*,+ ./G()*,+ .3 c2  y  „                   /(W )*,+ ./()*,+ ./()*,+ .4 6 5 Figura 1: Digrafo D. Aqu´ D = (V, E) con V = {1, 2, 3, 4, 5, 6} y ı E = {(1, 2), (2, 1), (2, 2), (2, 3), (3, 5), (3, 6), (4, 2), (4, 4), (5, 2), (6, 3)}. El paseo w1 = (1, 2, 3, 6) tiene longitud 3 y w2 = (1, 2, 2, 1, 2) es un paseo...