4.5: Las cadenas de Markov y el algoritmo PageRank de Google
( \newcommand{\kernel}{\mathrm{null}\,}\)
En la última sección, utilizamos nuestra comprensión de los valores propios y vectores propios para describir el comportamiento a largo plazo de algunos sistemas dinámicos discretos. El estado del sistema, que podría registrar, digamos, las poblaciones de unas pocas especies que interactúan, en un momento fue descrito por un vectorxk. El vector estado luego evolucionó de acuerdo con una regla linealxk+1=Axk.
Continuamos nuestra exploración en esta sección observando las cadenas de Markov, que forman un tipo específico de sistema dinámico discreto. Por ejemplo, podríamos estar interesados en una empresa de alquiler de autos que alquile autos de varias ubicaciones. De un día para otro, el número de autos en diferentes ubicaciones puede cambiar, pero el número total de autos permanece igual. Una vez más, una comprensión de los valores propios y vectores propios nos ayudará a hacer predicciones sobre el comportamiento a largo plazo del sistema.
Vista previa Actividad 4.5.1.
Supongamos que nuestra compañía de autos de alquiler alquila desde dos ubicacionesP yQ. encontramos que el 80% de los autos rentados de la ubicaciónP son devueltos aP mientras que el otro 20% se devuelve aQ. Para autos rentados de ubicaciónQ, 60% son devueltos aQ y 40% a P.
UtilizaremosPk yQk para denotar el número de autos en las dos ubicacionesk. el día Al día siguiente, el número de autos enP igual al 80% dePk y 40% deQk. Esto demuestra que
- Si usamos el vectorxk=[PkQk] para representar la distribución de autos en el díak, encontramos una matrizA tal quexk+1=Axk.
- Encuentra los valores propios y los vectores propios asociados deA.
- Supongamos que inicialmente hay 1500 autos, todos los cuales están en la ubicaciónP. Escribe el vectorx0 como una combinación lineal de vectores propios deA.
- Escribe los vectoresxk como una combinación lineal de vectores propios deA.
- ¿Qué pasa con la distribución de autos después de mucho tiempo?
Un primer ejemplo
En la actividad previa, la distribución de autos de alquiler fue descrita por el sistema dinámico discreto
Esta matriz tiene algunas propiedades especiales. Primero, cada entrada representa la probabilidad de que un auto rentado en un lugar sea devuelto a otro. Por ejemplo, existe un 80% de posibilidades de queP se devuelva un auto rentado enP, lo que se explica la entrada de 0.8 en la esquina superior izquierda. Por lo tanto, las entradas de la matriz están entre 0 y 1.
Segundo, un auto rentado en una ubicación debe ser devuelto a una de las ubicaciones. Por ejemplo, ya que el 80% de los autos rentados enP se devuelven aP, ello se deduce que el otro 20% de los autos rentados enP se devuelven aQ. Esto implica que las entradas en cada columna deben sumar a 1. Esto ocurrirá frecuentemente en nuestra discusión por lo que introducimos las siguientes definiciones.
Un vector cuyas entradas no son negativas y se suman a 1 se denomina vector de probabilidad. Una matriz cuadrada cuyas columnas son vectores de probabilidad se denomina matriz estocástica.
Actividad 4.5.2.
Supongamos que vive en un país con tres partidos políticosP,Q, yR. Nosotros usamosPk,Qk, yRk para denotar el porcentaje de votantes que votan por ese partido en elecciónk.
Los votantes cambiarán de partido de una elección a otra como se muestra en la figura. Vemos que el 60% de los votantes se queda con el mismo partido. No obstante, el 40% de quienes voten por partidoP votarán por partidoQ en la próxima elección.
- Escribir expresiones paraPk+1,Qk+1, yRk+1 en términos dePk,Qk, yRk.
- Si escribimosxk=[PkQkRk], encontramos la matrizA tal quexk+1=Axk.
- Explicar por quéA es una matriz estocástica.
- Supongamos que inicialmente 40% de los ciudadanos votan por partidoP, 30% votan por partidoQ, y 30% votan por partidoR. Formar el vectorx0 y explicar por quéx0 es un vector de probabilidad.
- Encuentrax1, los porcentajes que votan por los tres partidos en la próxima elección. Verificar que tambiénx1 sea un vector probabilty y explique por quéxk será un vector de probabilidad para cadak.
- Encuentra los valores propios de la matrizA y explica por qué el espacio propioE1 es un subespacio unidimensional deR3. Luego verifica quev=[122] sea un vector base paraE1.
- Como cada vector enE1 es un múltiplo escalar dev, encontrar un vector de probabilidad enE1 y explicar por qué es el único vector de probabilidad enE1.
- Describa lo que le sucedexk después de mucho tiempo.
La actividad anterior ilustra algunos puntos importantes que deseamos destacar.
Primero, para determinarPk+1, observamos que enk+1, partido electoralP retiene el 60% de sus electores de la elección anterior y suma el 20% de los que votaron por partidoR. De esta manera, vemos que
Por lo tanto, definimos la matriz
y tenga en cuenta quexk+1=Axk.
Si consideramos la primera columna deA, vemos que las entradas representan los porcentajes de votantesP del partido en la última elección que votan por cada uno de los tres partidos en la próxima elección. Dado que todos los que votaron por partidoP previamente votan por uno de los tres partidos en la próxima elección, la suma de estos porcentajes debe ser de 1. Esto es cierto para cada una de las columnas de lasA, cuales explica por quéA es una matriz estocástica.
Comenzamos conx0=[0.40.30.3], el vector cuyas entradas representan el porcentaje de votantes que votan por cada uno de los tres partidos. Dado que cada elector vota por uno de los tres partidos, la suma de estas entradas debe ser 1, lo que significa quex0 es un vector de probabilidad. Entonces encontramos que
Observe que los vectores tambiénxk son vectores de probabilidad y que la secuenciaxk parece estar convergiendo a[0.20.40.4]. Es este comportamiento al que nos gustaría entender más a fondo investigando los valores propios y vectores propios deA.
Encontramos que los valores propios deA son
Observe que siv es un vector propio deA con valor propio asociadoλ1=1, entonces esAv=1v=v. decir,v no cambia cuando lo multiplicamos porA.
De lo contrario, tenemosA=PEP−1 donde
Observe que|λ2|=|λ3|<1 así las trayectorias sexk enroscan en el espacio propioE1 como se indica en la figura.
Esto nos dice que la secuenciaxk converge a un vector enE1. Es sencillo ver quev=[122] es un vector base paraE1 porqueAv=v asíxk esperamos que converja a un múltiplo escalar dev. Indeed, ya que los vectoresxk son probabilidad vectores, esperamos que converjan a un vector de probabilidad enE1.
Podemos encontrar el vector de probabilidad enE1 encontrando el múltiplo escalar apropiado dev. Notice quecv=[c2c2c] es un vector de probabilidad cuando loc+2c+2c=5c=1, que implica quec=1/5. Por lo tanto,q=[0.20.40.4] es el vector de probabilidad único enE1. Desde la secuenciaxk converge a un vector de probabilidad enE1, vemos quexk converge aq, lo que concuerda con los cálculos que mostramos anteriormente.
El papel de los valores propios es importante en este ejemplo. Ya queλ1=1, podemos encontrar un vector de probabilidadq que no se modifica por multiplicación porA. Además, los otros valores propios satisfacen|λj|<1, lo que significa que todas las trayectorias son arrastradas hacia el espacio propioE1. Dado quexk es una secuencia de vectores de probabilidad, estos vectores convergen al vector de probabilidad aq medida que se tiran haciaE1.
Cadenas de Markov
Si tenemos una matriz estocásticaA y un vector de probabilidadx0, podemos formar la secuenciaxk dondexk+1=Axk. llamamos a esta secuencia de vectores una cadena de Markov. El ejercicio 4.5.5.6 explica por qué podemos garantizar que los vectoresxk son vectores de probabilidad.
En el ejemplo que estudió los patrones de votación, construimos una cadena de Markov que describía cómo los porcentajes de votantes que escogían diferentes partidos cambiaban de una elección a otra. Vimos que la cadena de Markov converge aq=[0.20.40.4], un vector de probabilidad en el espacio propioE1. En otras palabras,q es un vector de probabilidad que no se modifica bajo multiplicación porA; eso es,Aq=q. Esto implica que, después de mucho tiempo, 20% de los votantes elige partidoP, 40% eligeQ, y 40% eligeR.
SiA es una matriz estocástica, decimos que un vector de probabilidadq es un vector estacionario o estacionario siAq=q.
Una pregunta importante que surge de nuestro ejemplo anterior es
Pregunta 4.5.3.
SiA es una matriz estocástica yxk una cadena de Markov, ¿xkconverge a un vector de estado estacionario?
Actividad 4.5.3.
Considerar las matrices
- Verificar que ambasA yB sean matrices estocásticas.
- Encuentre los valores propios deA y luego encuentre un vector de estado estacionario paraA.
- Formaremos la cadena de Markov comenzando con el vectorx0=[10] y definiendoxk+1=Axk. La célula de Sage a continuación construye los primerosN términos de la cadena de Markov con el comando
markov_chain (A, x0, N)
. Definir la matrizA y el vectorx0 y evaluar la célula para encontrar los primeros 10 términos de la cadena de Markov. ¿Qué notas de la cadena Markov? ¿Converge al vector de estado estacionario paraA? - Ahora encuentre los valores propios deB junto con un vector de estado estacionario paraB.
- Como antes, encuentra los primeros 10 términos de la cadena Markov comenzando conx0=[10] yxk+1=Bxk. ¿Qué notas de la cadena Markov? ¿Converge al vector de estado estacionario paraB?
- ¿Qué condición sobre los valores propios de una matriz estocástica garantizará que una cadena de Markov converja en un vector de estado estacionario?
Como implica esta actividad, los valores propios de una matriz estocástica nos indican si una cadena de Markov convergerá a un vector de estado estacionario. Aquí hay algunos datos importantes sobre los valores propios de una matriz estocástica.
- Como se demuestra en el Ejercicio 4.5.5.8,λ=1 es un valor propio de cualquier matriz estocástica. Normalmente ordenamos los valores propios por lo que es el primer valor propio, lo que significa queλ1=1.
- Todos los demás valores propios satisfacen la propiedad que|λj|≤1.
- Cualquier matriz estocástica tiene al menos un vector de estado estacionarioq.
Como se ilustra en la actividad, una cadena de Markov podría no converger a un vector de estado estacionario si|λ2|=1. Esto sucede para la matrizA=[0110], cuyos valores propios sonλ1=1 yλ2=−1.
Sin embargo, si todos menos el primer valor propio satisfacen|λj|<1, entonces hay un vector de estado estacionario únicoq y cualquier cadena de Markov convergerá aq. Este fue el caso de la matrizB=[0.40.30.60.7], cuyos valores propios sonλ1=1 yλ2=0.1. En este caso, cualquier cadena de Markov convergerá a la vector único de estado estacionarioq=[1323].
De esta manera, vemos que los valores propios de una matriz estocástica nos dicen si una cadena de Markov convergerá a un vector de estado estacionario. Sin embargo, es algo inconveniente calcular los valores propios para responder a esta pregunta. ¿Hay alguna manera de concluir que cada cadena de Markov convergerá en un vector de estado estacionario sin realmente calcular los valores propios? Resulta que hay una condición simple en la matrizA que lo garantiza.
Decimos que una matrizA es positiva si algunaA o alguna potenciaAk tiene todas las entradas positivas.
La matriz noA=[0110] es positiva. Esto lo podemos ver porque algunas de las entradas deA son cero y por lo tanto no positivas. Además, vemos esoA2=I,A3=A y así sucesivamente. Por lo tanto, cada potencia deA también tiene algunas entradas cero, lo que significa que noA es positivo.
La matrizB=[0.40.30.60.7] es positiva porque cada entrada deB es positiva.
Además, la matrizC=[00.510.5] claramente tiene una entrada cero. Sin embargo,C2=[0.50.250.50.75], que tiene todas las entradas positivas. Por lo tanto, vemos queC es una matriz positiva.
Las matrices positivas son importantes por el siguiente teorema.
Teorema 4.5.6. Perron-Frobenius.
SiA es una matriz estocástica positiva, entonces los valores propios satisfacenλ1=1 y|λj|<1 paraj>1. Esto significa queA tiene un único positivo, vector de estado estacionarioq y que cada cadena de Markov definida porA convergerá aq.
Actividad 4.5.4.
Exploraremos el significado del teorema de Perron-Frobenius en esta actividad.
- Considera la matrizC=[00.510.5]. Esta es una matriz positiva, como vimos en el ejemplo anterior. Encuentre los vectores propios deC y verifique que haya un vector de estado estacionario único.
- Usando la célula de Sage a continuación, construye la cadena de Markov con el vector inicialx0=[10] y describe lo que sucede axk medida quek se vuelve grande.
- Construir otra cadena de Markov con vector inicialx0=[0.20.8] y describir lo que sucede axk medida quek se vuelve grande.
- Considera la matrizD=[00.5010.50001] y calcula varias potencias deD abajo. Determinar siD es una matriz positiva.
- Encuentre los valores propios deD y luego encuentre los vectores de estado estacionario. ¿Existe un vector de estado estacionario único?
- Qué pasa con la cadena de Markov definida porD con vector inicialx0=[100]? Qué sucede con la cadena de Markov con vector inicialx0=[001].
- Explicar cómo las matricesC yD, que hemos considerado en esta actividad, se relacionan con el teorema de Perron-Frobenius.
El algoritmo PageRank de Google
Las cadenas de Markov y el teorema de Perron-Frobenius son los ingredientes centrales del algoritmo PageRank de Google, desarrollado por Google para evaluar la calidad de las páginas web.
Supongamos que ingresamos “álgebra lineal” en el motor de búsqueda de Google. Google responde diciéndonos que hay 24.9 millones de páginas web que contienen esos términos. En la primera página, sin embargo, hay enlaces a diez páginas web que Google juzga que tienen la mayor calidad y por lo tanto las que más probablemente nos interesen. ¿Cómo evalúa Google la calidad de las páginas web?
Como el momento en que se escribe esto, Google está rastreando 30 billones de páginas web. Claramente, esto es demasiado para que los humanos los evalúen. Además, los evaluadores humanos pueden inyectar sus propios sesgos en sus evaluaciones, tal vez incluso involuntariamente. La idea de Google es utilizar la estructura de Internet para evaluar la calidad de las páginas web sin ninguna intervención humana. Por ejemplo, si una página web tiene contenido de calidad, otras páginas web enlazarán a ella. Esto significa que el número de enlaces a una página refleja la calidad de esa página. Además, esperaríamos que una página tenga contenido de mayor calidad si esos enlaces provienen de páginas que a su vez se evalúa que tienen alta calidad. En pocas palabras, si muchas páginas de calidad enlazan a una página, esa página debe ser en sí misma de alta calidad. Esta es la esencia del algoritmo PageRank, que introducimos en la siguiente actividad.
Actividad 4.5.5.
Consideraremos un modelo sencillo de Internet que cuenta con tres páginas y enlaces entre ellas como se muestra aquí. Por ejemplo, la página 1 enlaza con ambas páginas 2 y 3, pero la página 2 solo enlaza con la página 1.
Mediremos la calidad de lajth página con un númeroxj, que se llama PageRank de páginaj. El PageRank está determinado por la siguiente regla: cada página divide su PageRank en partes iguales, una por cada enlace saliente, y da una pieza a cada una de las páginas a las que enlaza. El PageRank de una página es la suma de todo el PageRank que recibe de las páginas que enlazan a ella.
Por ejemplo, la página 3 tiene dos enlaces salientes. Por lo tanto, divide su PageRank porx3 la mitad y da la mitad a la página 1. La página 2 tiene solo un enlace saliente por lo que da todo su PageRankx2 a la página 1. Por lo tanto, tenemos
- Encuentra expresiones similares parax2 yx3.
- Ahora formamos el vector PageRankx=[x1x2x3]. Encuentra una matrizG tal que las expresiones parax1,x2, y sex3 puedan escribir en la formaGx=x. La matrizG se llama la “matriz de Google”.
- Explicar por quéG es una matriz estocástica.
- Dado quex se define por la ecuaciónGx=x, cualquier vector en el espacio propioE1 satisface esta ecuación. Para que podamos trabajar con un vector específico, definiremos el vector PageRank para que sea el vector de estado estacionario de la matriz estocásticaG. Encuentra este vector de estado estacionario.
- El vector PageRankx está compuesto por los PageRanks para cada una de las tres páginas. ¿Qué página de las tres se evalúa para tener la más alta calidad? Al referirse a la estructura de este pequeño modelo de Internet, explique por qué esta es una buena opción.
- Si comenzamos con el vector inicialx0=[100] y formamos la cadena de Markov,xk+1=Gxk, ¿qué nos dice el teorema de Perron-Frobenius sobre el comportamiento a largo plazo de la cadena de Markov?
- Verificar que esta cadena de Markov converja al vector PageRank en estado estacionario.
Esta actividad nos muestra dos formas de encontrar el vector PageRank. En el primero, determinamos un vector de estado estacionario directamente al encontrar una descripción del espacio propioE1 y luego encontrar el múltiplo escalar apropiado de un vector base que nos da el vector de estado estacionario. E1,Sin embargo, para encontrar una descripción del espacio propio, necesitamos encontrar el espacio nuloNul(G−I). Recuerda que la Internet real tiene 30 billones de páginas por lo que encontrar nosNul(G−I) requiere remar reducir una matriz con 30 billones de filas y columnas. Como vimos en la Subsección 1.3.3, eso no es computacionalmente factible.
Como sugiere la actividad, la segunda forma de encontrar el vector PageRank es usar una cadena de Markov que converja al vector PageRank. Dado que multiplicar un vector por una matriz es significativamente menor trabajo que la reducción de filas de la matriz, este enfoque es computacionalmente factible, y es, de hecho, cómo Google calcula el vector PageRank.
Actividad 4.5.6.
Considera Internet con ocho páginas web, que se muestra en la Figura 4.5.8.
- Construye la matriz de GoogleG para esta Internet. Luego usa una cadena de Markov para encontrar el vector PageRank en estado estacionariox.
- ¿Qué nos dice este vector sobre la calidad relativa de las páginas en este Internet? ¿Qué página tiene la mayor calidad y cuál la más baja?
- Ahora considere Internet con cinco páginas, que se muestra en la Figura 4.5.9.
Figura 4.5.9. Un modelo de Internet con cinco páginas web. Qué sucede cuando comienzas la cadena de Markov con el vectorx0=[10000]? Explica por qué este comportamiento es consistente con el teorema de Perron-Frobenius.
- ¿Cuál crees que debería ser el vector PageRank para este Internet? ¿Alguna página es de mayor calidad que otra?
- Ahora considere Internet con ocho páginas web, que se muestra en la Figura 4.5.10.
Figura 4.5.10. Otro modelo de Internet con ocho páginas web. Observe que esta versión de Internet es idéntica a la primera que vimos en esta actividad, salvo que se ha eliminado un solo enlace de la página 7 a la página 1. Por lo tanto, podemos encontrar su matriz de GoogleG modificando ligeramente la matriz anterior.
¿Cuál es el comportamiento a largo plazo de una cadena de Markov definidoG y por qué no es deseable este comportamiento? ¿En qué consiste este comportamiento con el teorema de Perron-Frobenius?
El teorema del teorema de Perron-Frobenius 4.5.6 nos dice que una cadena de Markovxk+1=Gxk converge a un vector de estado estacionario único cuando la matrizG es positiva. Esto significa queG o algún poder deG debe tener solo entradas positivas. Claramente, este no es el caso de la matriz formada a partir de Internet en la Figura 4.5.9.
Podemos entender el problema con Internet que se muestra en la Figura 4.5.10 agregando un recuadro alrededor de algunas de las páginas como se muestra en la Figura 4.5.11. Aquí vemos que las páginas fuera de la caja ceden todo su PageRank a las páginas dentro de la caja. Esto no es deseable porque se encuentra que los PageRanks de las páginas fuera de la caja son cero. Una vez más, la matriz de Google noG es una matriz positiva.
Google resuelve este problema modificando ligeramente la matriz de GoogleG para obtener una matriz positivaG′. Para entender esto, piense en las entradas en la matriz de Google como dando la probabilidad de que un usuario de Internet siga un enlace de una página de otra. Para crear una matriz positiva, permitiremos que ese usuario salte aleatoriamente a cualquier otra página de Internet con una pequeña probabilidad.
Para darle sentido a esto, supongamos que hayN páginas en nuestro internet. La matriz
es una matriz estocástica positiva que describe un proceso donde podemos pasar de cualquier página a otra con igual probabilidad. Para formar la matriz de Google modificadaG′, elegimos un parámetroα que se usa para mezclarG yHn juntos; es decir,G′ es la matriz estocástica positiva
En la práctica, se piensa que Google usa un valor deα=0.85 (Google no publica este número ya que es un secreto comercial) para que tengamos
Intuitivamente, esto significa que un usuario de Internet seguirá aleatoriamente un enlace de una página a otra 85% del tiempo y saltará aleatoriamente a cualquier otra página en Internet el 15% del tiempo. Dado que la matrizG′ es positiva, el teorema de Perron-Frobenius nos dice que cualquier cadena de Markov convergerá en un vector de estado estacionario único que llamamos el vector PageRank.
Actividad 4.5.7.
La siguiente celda de Sage generará la cadena de Markov para la matriz de Google modificadaG si simplemente ingresa la matriz original de GoogleG en la línea correspondiente.
- Considera el Internet original con tres páginas que se muestran en la Figura 4.5.7 y encuentra el vector PageRankx usando la matriz de Google modificada en la celda de Sage anterior. ¿Cómo se compara este vector PageRank modificado con el vector que encontramos usando la matriz original de Google?G?
- Encuentre el vector PageRank modificado para Internet que se muestra en la Figura 4.5.9. Explique por qué este vector parece ser el correcto.
- Encuentre el vector PageRank modificado para Internet que se muestra en la Figura 4.5.10. Explica por qué este vector PageRank modificado soluciona el problema que apareció con el vector PageRank original.
La capacidad de acceder a casi cualquier cosa que queramos saber a través de Internet es algo que damos por sentado en la sociedad actual. Sin embargo, sin el algoritmo PageRank de Google, Internet sería un lugar realmente caótico; imagínese tratando de encontrar una página web útil entre los 30 billones de páginas disponibles sin ella. (Existen, por supuesto, otros algoritmos de búsqueda, pero el de Google es el más utilizado). El papel fundamental que juegan las cadenas de Markov y el teorema de Perron-Frobenius en el algoritmo de Google demuestra el vasto poder que tienen las matemáticas para dar forma a nuestra sociedad.
Resumen
En esta sección se exploraron las matrices estocásticas y las cadenas de Markov.
- Un vector de probabilidad es aquel cuyas entradas no son negativas y cuyas columnas se suman a 1. Una matriz estocástica es una matriz cuadrada cuyas columnas son vectores de probabilidad.
- Se forma una cadena de Markov a partir de una matriz estocásticaA y un vector de probabilidad inicialx0 usando la reglaxk+1=Axk. Podemos pensar en la secuenciaxk como la descripción de la evolución de alguna cantidad conservada, como el número de autos de alquiler o votantes, entre una serie de estados posibles con el tiempo.
- Un vector de estado estacionarioq para una matriz estocásticaA es un vector de probabilidad que satisfaceAq=q.
- El teorema de Perron-Frobenius nos dice que, siA es una matriz estocástica positiva, entonces cada cadena de Markov definida porA converge a un vector único, positivo en estado estacionario.
- El algoritmo PageRank de Google utiliza cadenas de Markov y el teorema de Perron-Frobenius para evaluar la calidad relativa de las páginas web en Internet.
Ejercicios 4.5.5Ejercicios
Considera las siguientes matrices2×2 estocásticas.
Para cada uno, haga una copia del diagrama y etiquete cada borde para indicar la probabilidad de esa transición. Después, encuentra todos los vectores de estado estacionario y describe lo que sucede con una cadena de Markov definida por esa matriz.
- [1100].
- [0.810.20].
- [1001].
- [0.70.60.30.4].
Cada año, las personas se mueven entre poblaciones urbanas (U), suburbanas (S) y rurales (R) con las probabilidades dadas en la Figura 4.5.12.
- Construir la matriz estocásticaA describiendo el movimiento de personas.
- Explicar lo que nos dice el teorema de Perron-Frobenius sobre la existencia de un vector de estado estacionarioq y el comportamiento de una cadena de Markov.
- Usa la celda de Sage a continuación para encontrar algunos términos de una cadena de Markov.
- Describir la distribución a largo plazo de las personas entre poblaciones urbanas, suburbanas y rurales.
Determine si las siguientes afirmaciones son verdaderas o falsas y proporcione una justificación de su respuesta.
- Cada matriz estocástica tiene un vector de estado estacionario.
- SiA es una matriz estocástica, entonces cualquier cadena de Markov definida porA converge a un vector de estado estacionario.
- SiA es una matriz estocástica, entoncesλ=1 es un valor propio y todos los demás valores propios satisfacen|λ|<1.
- Una matriz estocástica positiva tiene un vector de estado estacionario único.
- SiA es una matriz estocástica invertible, entonces también lo esA−1.
Considerar la matriz estocástica
- Encuentra los valores propios deA.
- ¿Se aplican a esta matriz las condiciones del teorema de Perron-Frobenius?
- Encuentra los vectores de steady-state deA.
- Qué podemos garantizar sobre el comportamiento a largo plazo de una cadena de Markov definida por la matrizA?
Explique sus respuestas a lo siguiente.
- ¿Por qué Google usa una cadena de Markov para calcular el vector PageRank?
- Describir dos problemas que pueden ocurrir cuando Google construye una cadena de Markov usando la matriz de GoogleG.
- Describir cómo estos problemas son consistentes con el teorema de Perron-Frobenius.
- Describir por qué el teorema de Perron-Frobenius sugiere crear una cadena de Markov usando la matriz de Google modificadaG′=αG+(1−α)Hn.
En los próximos ejercicios, consideraremos la1×n matrizS=[11…1].
Supongamos queA es una matriz estocástica y quex es un vector de probabilidad. Nos gustaría explicar por qué el productoAx es un vector de probabilidad.
- Explica por quéx=[0.40.50.1] es un vector de probabilidad y luego encuentra el productoSx.
- De manera más general, six es algún vector de probabilidad, cuál es el productoSx?
- SiA es una matriz estocástica, explique por quéSA=S.
- Explicar por quéAx es un vector de probabilidad considerando el productoSAx.
Utilizando los resultados del ejercicio anterior, nos gustaría explicar por quéA2 es una matriz estocástica siA es estocástica.
- Supongamos queA yB son matrices estocásticas. Explicar por qué el productoAB es una matriz estocástica considerando el productoSAB.
- Explicar por quéA2 es una matriz estocástica.
- ¿Cómo seA2 comparan los vectores de estado estacionario con los vectores de estado estacionario deA?
Este ejercicio explica por quéλ=1 es un valor propio de una matriz estocásticaA. Para concluir queλ=1 es un valor propio, necesitamos saber que noA−I es invertible.
- Cuál es el productoS(A−I)?
- Explique por quéCol(A−I) está contenido enNul(S).
- Cuál es el productoSe1?
- Explicar por qué noe1 está contenido en el espacio de columnaCol(A−I).
- Explicar por qué podemos concluir que noA−I es invertible y queλ=1 es un valor propio deA.
Vimos un par de modelos Internets en los que una cadena de Markov definida por la matriz de GoogleG no convergía a un vector PageRank apropiado. Por esta razón, Google define la matriz
donden es el número de páginas web, y construye una cadena de Markov a partir de la matriz de Google modificada
Dado queG′ es positivo, se garantiza que la cadena de Markov converja en un vector de estado estacionario único.
Dijimos que Google eligeα=0.85 así que podríamos preguntarnos por qué esta es una buena opción. Exploraremos el papel deα en este ejercicio. Consideremos el modelo Internet descrito en la Figura 4.5.9 y construyamos la matriz de GoogleG. En la celda de Sage a continuación, puede ingresar la matrizG y elegir un valor paraα.
- Empecemos conα=0. Con esta elección, cuál es la matrizG′=αG+(1−α)Hn? Construir una cadena de Markov usando la celda Sage anterior. ¿Cuántos pasos se requieren para que la cadena de Markov converja con la precisión con la que sexk muestran los vectores?
- Ahora elijaα=0.25. ¿Cuántos pasos se requieren para que la cadena de Markov converja a la precisión con la que sexk muestran los vectores?
- Repita este experimento conα=0.5 yα=0.75.
- ¿Qué pasa siα=1?
Este experimento da una idea de la elección deα. Cuanto más pequeñoα es, más rápido converge la cadena de Markov. Esto es importante; dadoG′ que la matriz con la que trabaja Google es tan grande, nos gustaría minimizar el número de términos en la cadena de Markov que necesitamos calcular. Por otro lado, a medida que bajamosα, la matrizG′=αG+(1−α)Hn comienza a parecerseHn cada vezG menos. El valorα=0.85 se elige para que la matriz se parezcaG′ suficientementeG mientras que la cadena de Markov converge en una cantidad razonable de pasos.
Este ejercicio analizará el juego de mesa Chutes y Escaleras, o al menos una versión simplificada del mismo.
El tablero para este juego consta de 100 cuadrados dispuestos en una10×10 cuadrícula y numerados del 1 al 100. Hay pares de cuadrados unidos por una escalera y pares unidos por un canal. Todos los jugadores comienzan en la casilla 1 y se turnan para rodar un dado. En su turno, un jugador moverá adelante el número de casillas indicadas en el dado. Si llegan a un cuadrado en la parte inferior de una escalera, se mueven hacia el cuadrado en la parte superior de la escalera. Si llegan a una plaza en la parte superior de un chute, el movimiento hacia abajo a la plaza en la parte inferior de la misma. El ganador es el primer jugador en llegar al cuadrado 100.

- Comenzamos por jugar una versión más sencilla de este juego con sólo ocho cuadrados dispuestos en fila como se muestra en la Figura 4.5.13 y que no contienen rampas ni escaleras. En lugar de un dado de seis caras, voltearemos una moneda y avanzaremos uno o dos cuadrados dependiendo del resultado ya sea que tengamos cabeza o cola. Si estamos en el cuadrado 7, avanzamos al cuadrado 8 independientemente del volteo de la moneda, y si estamos en el cuadrado 8, nos quedaremos ahí para siempre.
Figura 4.5.13. Una versión simple de Chutes y Escaleras sin rampas ni escaleras. Construye la8×8 matrizA que registre la probabilidad de que un jugador se mueva de un cuadrado a otro en un movimiento. Por ejemplo, si un jugador está en el cuadrado 2, hay un 50% de probabilidad de que esté en el cuadrado 3 y un 50% de probabilidad de que esté en el cuadrado 4 al final del siguiente movimiento.
Desde que comenzamos el juego en el cuadrado 1, el vector inicialx0=e1. Generar unos términos de la cadena Markovxk+1=Axk.
¿Cuál es la probabilidad de que lleguemos al cuadrado 8 por el cuarto movimiento? ¿Por la sexta jugada? ¿Por la séptima jugada?
- Ahora modificaremos el juego agregando un canal y una escalera como se muestra en la Figura 4.5.14.
Figura 4.5.14. Una versión de Chutes y Escaleras con una canalización y una escalera. A pesar de que hay ocho cuadrados, sólo hay que considerar seis de ellos. Por ejemplo, si llegamos al primer cuadrado blanco, nos movemos hasta el cuadrado 4. De igual manera, si llegamos a la segunda plaza blanca, bajamos a la casilla 1.
Una vez más, construimos la matriz6×6 estocástica que registre la probabilidad de que nos movemos de un cuadrado a otro en un giro dado y generemos algunos términos en la cadena de Markov que comienza conx0=e1.
- ¿Cuál es el menor número de movimientos que podemos hacer y llegar a la plaza 6? ¿Cuál es la probabilidad de que lleguemos al cuadrado 6 usando este número de movimientos?
- ¿Cuál es la probabilidad de que lleguemos al cuadrado 6 después de cinco movimientos?
- ¿Cuál es la probabilidad de que sigamos en el cuadrado 1 después de cinco movimientos? ¿Después de siete movimientos? ¿Después de nueve movimientos?
- Después de cuántos movimientos tenemos un 90% de posibilidades de haber llegado a la plaza 6?
- Encuentra el vector de estado estacionario y discute lo que implica este vector sobre el juego.
Se puede analizar la versión completa de Chutes y Escaleras que tienen 100 cuadrados de la misma manera. Sin ningún tipo de rampas o escaleras, se encuentra que el promedio de movimientos requeridos para alcanzar el cuadrado 100 es de 29.0. Una vez que volvemos a sumar las rampas y escaleras, el promedio de movimientos requeridos para alcanzar el cuadrado 100 es de 27.1. Esto demuestra que el número promedio de movimientos no cambia significativamente cuando agregamos las rampas y escaleras. Hay, sin embargo, mucha más variación en las posibilidades porque es posible llegar al cuadrado 100 mucho más rápido y mucho más despacio.