4.5: Las cadenas de Markov y el algoritmo PageRank de Google

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 vector\(\mathbf x_k\text{.}\) El vector estado luego evolucionó de acuerdo con una regla lineal\(\mathbf x_{k+1} = A\mathbf x_k\text{.}\)

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 ubicaciones\(P\) y\(Q\text{.}\) encontramos que el 80% de los autos rentados de la ubicación\(P\) son devueltos a\(P\) mientras que el otro 20% se devuelve a\(Q\text{.}\) Para autos rentados de ubicación\(Q\text{,}\) 60% son devueltos a\(Q\) y 40% a \(P\text{.}\)

Utilizaremos\(P_k\) y\(Q_k\) para denotar el número de autos en las dos ubicaciones\(k\text{.}\) el día Al día siguiente, el número de autos en\(P\) igual al 80% de\(P_k\) y 40% de\(Q_k\text{.}\) Esto demuestra que

\ begin {ecuación*}\ begin {alineado} P_ {k+1} & {} = {} 0.8 P_k + 0.4q_k\\ Q_ {k+1} & {} = {} 0.2 P_k + 0.6q_k\ texto {.}\\\ final {alineado}\ final {ecuación*}

1. Si usamos el vector\(\mathbf x_k = \twovec{P_k}{Q_k}\) para representar la distribución de autos en el día\(k\text{,}\) encontramos una matriz\(A\) tal que\(\mathbf x_{k+1} = A\mathbf x_k\text{.}\)
2. Encuentra los valores propios y los vectores propios asociados de\(A\text{.}\)
3. Supongamos que inicialmente hay 1500 autos, todos los cuales están en la ubicación\(P\text{.}\) Escribe el vector\(\mathbf x_0\) como una combinación lineal de vectores propios de\(A\text{.}\)
4. Escribe los vectores\(\mathbf x_k\) como una combinación lineal de vectores propios de\(A\text{.}\)
5. ¿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

\ begin {ecuación*}\ mathbf x_ {k+1} = A\ mathbf x_k=\ left [\ begin {array} {rr} 0.8 & 0.4\\ 0.2 & 0.6\\\ end {array}\ derecha]\ mathbf x_k\ texto {.} \ end {ecuación*}

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 que\(P\) se devuelva un auto rentado en\(P\text{,}\) 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 en\(P\) se devuelven a\(P\text{,}\) ello se deduce que el otro 20% de los autos rentados en\(P\) se devuelven a\(Q\text{.}\) 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.

Definición 4.5.1

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íticos\(P\text{,}\)\(Q\text{,}\) y\(R\text{.}\) Nosotros usamos\(P_k\text{,}\)\(Q_k\text{,}\) y\(R_k\) para denotar el porcentaje de votantes que votan por ese partido en elección\(k\text{.}\)

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 partido\(P\) votarán por partido\(Q\) en la próxima elección.

1. Escribir expresiones para\(P_{k+1}\text{,}\)\(Q_{k+1}\text{,}\) y\(R_{k+1}\) en términos de\(P_k\text{,}\)\(Q_k\text{,}\) y\(R_k\text{.}\)
2. Si escribimos\(\mathbf x_k = \threevec{P_k}{Q_k}{R_k}\text{,}\) encontramos la matriz\(A\) tal que\(\mathbf x_{k+1} = A\mathbf x_k\text{.}\)
3. Explicar por qué\(A\) es una matriz estocástica.
4. Supongamos que inicialmente 40% de los ciudadanos votan por partido\(P\text{,}\) 30% votan por partido\(Q\text{,}\) y 30% votan por partido\(R\text{.}\) Formar el vector\(\mathbf x_0\) y explicar por qué\(\mathbf x_0\) es un vector de probabilidad.
5. Encuentra\(\mathbf x_1\text{,}\) los porcentajes que votan por los tres partidos en la próxima elección. Verificar que también\(\mathbf x_1\) sea un vector probabilty y explique por qué\(\mathbf x_k\) será un vector de probabilidad para cada\(k\text{.}\)
6. Encuentra los valores propios de la matriz\(A\) y explica por qué el espacio propio\(E_1\) es un subespacio unidimensional de\(\mathbb R^3\text{.}\) Luego verifica que\(\mathbf v=\threevec{1}{2}{2}\) sea un vector base para\(E_1\text{.}\)
7. Como cada vector en\(E_1\) es un múltiplo escalar de\(\mathbf v\text{,}\) encontrar un vector de probabilidad en\(E_1\) y explicar por qué es el único vector de probabilidad en\(E_1\text{.}\)
8. Describa lo que le sucede\(\mathbf x_k\) después de mucho tiempo.

La actividad anterior ilustra algunos puntos importantes que deseamos destacar.

Primero, para determinar\(P_{k+1}\text{,}\) observamos que en\(k+1\text{,}\) partido electoral\(P\) retiene el 60% de sus electores de la elección anterior y suma el 20% de los que votaron por partido\(R\text{.}\) De esta manera, vemos que

\ begin {ecuación*}\ begin {alineada} {6} P_ {k+1} & {} = {} 0.6p_k & & & + 0.2 R_k\\ Q_ {k+1} & {} = {} 0.4p_k & {} + {} & 0.6q_k & {} + {} 0.2R_k\\ R_ {k+1} & {} = {} & {} {} & 0.4q_k & {} + {} 0.6R_k\\\ final {alineada}\ final {ecuación*}

Por lo tanto, definimos la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrr} 0.6 & 0 & 0.2\\ 0.4 & 0.6 & 0.2\\ 0 & 0.4 & 0.6\\ end {array}\ right]\ end {ecuación*}

y tenga en cuenta que\(\mathbf x_{k+1} = A\mathbf x_k\text{.}\)

Si consideramos la primera columna de\(A\text{,}\) vemos que las entradas representan los porcentajes de votantes\(P\) 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 partido\(P\) 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 las\(A\text{,}\) cuales explica por qué\(A\) es una matriz estocástica.

Comenzamos con\(\mathbf x_0 = \threevec{0.4}{0.3}{0.3}\text{,}\) 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 que\(\mathbf x_0\) es un vector de probabilidad. Entonces encontramos que

\ begin {ecuación*}\ begin {array} {cccc}\ mathbf x_1=\ threevec {0.300} {0.400} {0.300}, &\ mathbf x_2=\ threevec {0.240} {0.420} {0.340}, &\ mathbf x_3=\ threevec {0.212} {0.416} {0.372}, &\ ldots,\\\\ mathbf x_5=\ threevec {0.199} {0.404} {0.397}, &\ ldots, &\ mathbf x_ {10} =\ threevec {0.200} {0.400} {0.400}, & amp;\ ldots\\\ end {array}\ text {.} \ end {ecuación*}

Observe que los vectores también\(\mathbf x_k\) son vectores de probabilidad y que la secuencia\(\mathbf x_k\) parece estar convergiendo a\(\threevec{0.2}{0.4}{0.4}\text{.}\) Es este comportamiento al que nos gustaría entender más a fondo investigando los valores propios y vectores propios de\(A\text{.}\)

Encontramos que los valores propios de\(A\) son

\ begin {ecuación*}\ lambda_1 = 1,\ qquad\ lambda_2 = 0.4 + 0.2i,\ qquad\ lambda_3 = 0.4-0.2i\ text {.} \ end {ecuación*}

Observe que si\(\mathbf v\) es un vector propio de\(A\) con valor propio asociado\(\lambda_1=1\text{,}\) entonces es\(A\mathbf v = 1\mathbf v = \mathbf v\text{.}\) decir,\(\mathbf v\) no cambia cuando lo multiplicamos por\(A\text{.}\)

De lo contrario, tenemos\(A=PEP^{-1}\) donde

\ begin {ecuación*} E =\ left [\ begin {array} {rrr} 1 & 0 & 0\\ 0 & 0.4 & -0.2\\ 0 & 0.2 & 0.4\\\ end {array}\ derecha]\ end {ecuación*}

Observe que\(|\lambda_2| = |\lambda_3| \lt 1\) así las trayectorias se\(\mathbf x_k\) enroscan en el espacio propio\(E_1\) como se indica en la figura.

Esto nos dice que la secuencia\(\mathbf x_k\) converge a un vector en\(E_1\text{.}\) Es sencillo ver que\(\mathbf v=\threevec{1}{2}{2}\) es un vector base para\(E_1\) porque\(A\mathbf v = \mathbf v\) así\(\mathbf x_k\) esperamos que converja a un múltiplo escalar de\(\mathbf v\text{.}\) Indeed, ya que los vectores\(\mathbf x_k\) son probabilidad vectores, esperamos que converjan a un vector de probabilidad en\(E_1\text{.}\)

Podemos encontrar el vector de probabilidad en\(E_1\) encontrando el múltiplo escalar apropiado de\(\mathbf v\text{.}\) Notice que\(c\mathbf v = \threevec{c}{2c}{2c}\) es un vector de probabilidad cuando lo\(c+2c+2c=5c = 1\text{,}\) que implica que\(c = 1/5\text{.}\) Por lo tanto,\(\mathbf q=\threevec{0.2}{0.4}{0.4}\) es el vector de probabilidad único en\(E_1\text{.}\) Desde la secuencia\(\mathbf x_k\) converge a un vector de probabilidad en\(E_1\text{,}\) vemos que\(\mathbf x_k\) converge a\(\mathbf q\text{,}\) lo que concuerda con los cálculos que mostramos anteriormente.

El papel de los valores propios es importante en este ejemplo. Ya que\(\lambda_1=1\text{,}\) podemos encontrar un vector de probabilidad\(\mathbf q\) que no se modifica por multiplicación por\(A\text{.}\) Además, los otros valores propios satisfacen\(|\lambda_j| \lt 1\text{,}\) lo que significa que todas las trayectorias son arrastradas hacia el espacio propio\(E_1\text{.}\) Dado que\(\mathbf x_k\) es una secuencia de vectores de probabilidad, estos vectores convergen al vector de probabilidad a\(\mathbf q\) medida que se tiran hacia\(E_1\text{.}\)

Cadenas de Markov

Si tenemos una matriz estocástica\(A\) y un vector de probabilidad\(\mathbf x_0\text{,}\) podemos formar la secuencia\(\mathbf x_k\) donde\(\mathbf x_{k+1} = A \mathbf x_k\text{.}\) llamamos a esta secuencia de vectores una cadena de Markov. El ejercicio 4.5.5.6 explica por qué podemos garantizar que los vectores\(\mathbf x_k\) 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 a\(\mathbf q=\threevec{0.2}{0.4}{0.4}\text{,}\) un vector de probabilidad en el espacio propio\(E_1\text{.}\) En otras palabras,\(\mathbf q\) es un vector de probabilidad que no se modifica bajo multiplicación por\(A\text{;}\) eso es,\(A\mathbf q = \mathbf q\text{.}\) Esto implica que, después de mucho tiempo, 20% de los votantes elige partido\(P\text{,}\) 40% elige\(Q\text{,}\) y 40% elige\(R\text{.}\)

Definición 4.5.2

Si\(A\) es una matriz estocástica, decimos que un vector de probabilidad\(\mathbf q\) es un vector estacionario o estacionario si\(A\mathbf q = \mathbf q\text{.}\)

Una pregunta importante que surge de nuestro ejemplo anterior es

Pregunta 4.5.3.

Si\(A\) es una matriz estocástica y\(\mathbf x_k\) una cadena de Markov, ¿\(\mathbf x_k\)converge a un vector de estado estacionario?

Actividad 4.5.3.

Considerar las matrices

\ begin {ecuación*} A=\ left [\ begin {array} {rr} 0 & 1\\ 1 & 0\\\ end {array}\ right],\ qquad B=\ left [\ begin {array} {rr} 0.4 & 0.3\\ 0.6 & 0.7\\ end {array}\\ right]\ text {.} \ end {ecuación*}

1. Verificar que ambas\(A\) y\(B\) sean matrices estocásticas.
2. Encuentre los valores propios de\(A\) y luego encuentre un vector de estado estacionario para\(A\text{.}\)
3. Formaremos la cadena de Markov comenzando con el vector\(\mathbf x_0 = \twovec{1}{0}\) y definiendo\(\mathbf x_{k+1} = A\mathbf x_k\text{.}\) La célula de Sage a continuación construye los primeros\(N\) términos de la cadena de Markov con el comando markov_chain (A, x0, N). Definir la matriz\(A\) y el vector\(x0\) 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 para\(A\text{?}\)
4. Ahora encuentre los valores propios de\(B\) junto con un vector de estado estacionario para\(B\text{.}\)
5. Como antes, encuentra los primeros 10 términos de la cadena Markov comenzando con\(\mathbf x_0 = \twovec{1}{0}\) y\(\mathbf x_{k+1} = B\mathbf x_k\text{.}\) ¿Qué notas de la cadena Markov? ¿Converge al vector de estado estacionario para\(B\text{?}\)
6. ¿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,\(\lambda=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\(\lambda_1=1\text{.}\)
• Todos los demás valores propios satisfacen la propiedad que\(|\lambda_j| \leq 1\text{.}\)
• Cualquier matriz estocástica tiene al menos un vector de estado estacionario\(\mathbf q\text{.}\)

Como se ilustra en la actividad, una cadena de Markov podría no converger a un vector de estado estacionario si\(|\lambda_2| = 1\text{.}\) Esto sucede para la matriz\(A = \left[\begin{array}{rr} 0 & 1 \\ 1 & 0 \\ \end{array}\right] \text{,}\) cuyos valores propios son\(\lambda_1=1\) y\(\lambda_2 = -1\text{.}\)

Sin embargo, si todos menos el primer valor propio satisfacen\(|\lambda_j|\lt 1\text{,}\) entonces hay un vector de estado estacionario único\(\mathbf q\) y cualquier cadena de Markov convergerá a\(\mathbf q\text{.}\) Este fue el caso de la matriz\(B = \left[\begin{array}{rr} 0.4 & 0.3 \\ 0.6 & 0.7 \\ \end{array}\right] \text{,}\) cuyos valores propios son\(\lambda_1=1\) y\(\lambda_2 = 0.1\text{.}\) En este caso, cualquier cadena de Markov convergerá a la vector único de estado estacionario\(\mathbf q = \twovec{\frac13}{\frac23}\text{.}\)

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 matriz\(A\) que lo garantiza.

Definición 4.5.4

Decimos que una matriz\(A\) es positiva si alguna\(A\) o alguna potencia\(A^k\) tiene todas las entradas positivas.

Ejemplo 4.5.5

La matriz no\(A = \left[\begin{array}{rr} 0 & 1 \\ 1 & 0 \\ \end{array}\right]\) es positiva. Esto lo podemos ver porque algunas de las entradas de\(A\) son cero y por lo tanto no positivas. Además, vemos eso\(A^2 = I\text{,}\)\(A^3 = A\) y así sucesivamente. Por lo tanto, cada potencia de\(A\) también tiene algunas entradas cero, lo que significa que no\(A\) es positivo.

La matriz\(B = \left[\begin{array}{rr} 0.4 & 0.3 \\ 0.6 & 0.7 \\ \end{array}\right]\) es positiva porque cada entrada de\(B\) es positiva.

Además, la matriz\(C = \left[\begin{array}{rr} 0 & 0.5 \\ 1 & 0.5 \\ \end{array}\right]\) claramente tiene una entrada cero. Sin embargo,\(C^2 = \left[\begin{array}{rr} 0.5 & 0.25 \\ 0.5 & 0.75 \\ \end{array}\right] \text{,}\) que tiene todas las entradas positivas. Por lo tanto, vemos que\(C\) es una matriz positiva.

Las matrices positivas son importantes por el siguiente teorema.

Teorema 4.5.6. Perron-Frobenius.

Si\(A\) es una matriz estocástica positiva, entonces los valores propios satisfacen\(\lambda_1=1\) y\(|\lambda_j| \lt 1\) para\(j\gt 1\text{.}\) Esto significa que\(A\) tiene un único positivo, vector de estado estacionario\(\mathbf q\) y que cada cadena de Markov definida por\(A\) convergerá a\(\mathbf q\text{.}\)

Actividad 4.5.4.

Exploraremos el significado del teorema de Perron-Frobenius en esta actividad.

1. Considera la matriz\(C = \left[\begin{array}{rr} 0 & 0.5 \\ 1 & 0.5 \\ \end{array}\right] \text{.}\) Esta es una matriz positiva, como vimos en el ejemplo anterior. Encuentre los vectores propios de\(C\) y verifique que haya un vector de estado estacionario único.
2. Usando la célula de Sage a continuación, construye la cadena de Markov con el vector inicial\(\mathbf x_0= \twovec{1}{0}\) y describe lo que sucede a\(\mathbf x_k\) medida que\(k\) se vuelve grande.
3. Construir otra cadena de Markov con vector inicial\(\mathbf x_0=\twovec{0.2}{0.8}\) y describir lo que sucede a\(\mathbf x_k\) medida que\(k\) se vuelve grande.
4. Considera la matriz\(D = \left[\begin{array}{rrr} 0 & 0.5 & 0 \\ 1 & 0.5 & 0 \\ 0 & 0 & 1 \\ \end{array}\right]\) y calcula varias potencias de\(D\) abajo.
   Determinar si\(D\) es una matriz positiva.
5. Encuentre los valores propios de\(D\) y luego encuentre los vectores de estado estacionario. ¿Existe un vector de estado estacionario único?
6. Qué pasa con la cadena de Markov definida por\(D\) con vector inicial\(\mathbf x_0 =\threevec{1}{0}{0}\text{?}\) Qué sucede con la cadena de Markov con vector inicial\(\mathbf x_0=\threevec{0}{0}{1}\text{.}\)
7. Explicar cómo las matrices\(C\) y\(D\text{,}\) 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.

Figura 4.5.7. Nuestro primer Internet.

Mediremos la calidad de la\(j^{th}\) página con un número\(x_j\text{,}\) que se llama PageRank de página\(j\text{.}\) 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 por\(x_3\) 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 PageRank\(x_2\) a la página 1. Por lo tanto, tenemos

\ begin {ecuación*} x_1 = x_2 +\ frac12 x_3\ texto {.} \ end {ecuación*}

1. Encuentra expresiones similares para\(x_2\) y\(x_3\text{.}\)
2. Ahora formamos el vector PageRank\(\mathbf x = \threevec{x_1}{x_2}{x_3}\text{.}\) Encuentra una matriz\(G\) tal que las expresiones para\(x_1\text{,}\)\(x_2\text{,}\) y se\(x_3\) puedan escribir en la forma\(G\mathbf x = \mathbf x\text{.}\) La matriz\(G\) se llama la “matriz de Google”.
3. Explicar por qué\(G\) es una matriz estocástica.
4. Dado que\(\mathbf x\) se define por la ecuación\(G\mathbf x = \mathbf x\text{,}\) cualquier vector en el espacio propio\(E_1\) 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ástica\(G\text{.}\) Encuentra este vector de estado estacionario.
5. El vector PageRank\(\mathbf x\) 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.
6. Si comenzamos con el vector inicial\(\mathbf x_0 = \threevec{1}{0}{0}\) y formamos la cadena de Markov,\(\mathbf x_{k+1} = G\mathbf x_k\text{,}\) ¿qué nos dice el teorema de Perron-Frobenius sobre el comportamiento a largo plazo de la cadena de Markov?
7. 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 propio\(E_1\) y luego encontrar el múltiplo escalar apropiado de un vector base que nos da el vector de estado estacionario. \(E_1\text{,}\)Sin embargo, para encontrar una descripción del espacio propio, necesitamos encontrar el espacio nulo\(\nul(G-I)\text{.}\) Recuerda que la Internet real tiene 30 billones de páginas por lo que encontrar nos\(\nul(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.

Figura 4.5.8. Un modelo sencillo de Internet con ocho páginas web.

1. Construye la matriz de Google\(G\) para esta Internet. Luego usa una cadena de Markov para encontrar el vector PageRank en estado estacionario\(\mathbf x\text{.}\)
2. ¿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?
3. 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 vector\(\mathbf x_0=\fivevec{1}{0}{0}{0}{0}\text{?}\) Explica por qué este comportamiento es consistente con el teorema de Perron-Frobenius.

4. ¿Cuál crees que debería ser el vector PageRank para este Internet? ¿Alguna página es de mayor calidad que otra?
5. 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 Google\(G\) modificando ligeramente la matriz anterior.

   ¿Cuál es el comportamiento a largo plazo de una cadena de Markov definido\(G\) 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 Markov\(\mathbf x_{k+1}=G\mathbf x_k\) converge a un vector de estado estacionario único cuando la matriz\(G\) es positiva. Esto significa que\(G\) o algún poder de\(G\) 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 no\(G\) es una matriz positiva.

Figura 4.5.11. Las páginas fuera de la caja ceden todo su PageRank a las páginas dentro de la caja.

Google resuelve este problema modificando ligeramente la matriz de Google\(G\) para obtener una matriz positiva\(G'\text{.}\) 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 hay\(N\) páginas en nuestro internet. La matriz

\ begin {ecuación*} h_n =\ left [\ begin {array} {rrrr}\ frac1n &\ frac1n &\ ldots &\ frac1n\\ frac1n\\ frac1n &\ ldots &\ frac1n\\ vdots &\ vdots &\ ddots &\ ddots &\ vdots\\ vdots\\\ frac1n &\ ldots &\ frac1n\\\ end {array}\ derecha]\ end {ecuación*}

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 modificada\(G'\text{,}\) elegimos un parámetro\(\alpha\) que se usa para mezclar\(G\) y\(H_n\) juntos; es decir,\(G'\) es la matriz estocástica positiva

\ begin {ecuación*} G' =\ alfa G + (1-\ alpha) H_n\ texto {.} \ end {ecuación*}

En la práctica, se piensa que Google usa un valor de\(\alpha=0.85\) (Google no publica este número ya que es un secreto comercial) para que tengamos

\ begin {ecuación*} G' = 0.85 G + 0.15h_n\ text {.} \ end {ecuación*}

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 matriz\(G'\) 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 modificada\(G\) si simplemente ingresa la matriz original de Google\(G\) en la línea correspondiente.

1. Considera el Internet original con tres páginas que se muestran en la Figura 4.5.7 y encuentra el vector PageRank\(\mathbf x\) 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\text{?}\)
2. 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.
3. 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ástica\(A\) y un vector de probabilidad inicial\(\mathbf x_0\) usando la regla\(\mathbf x_{k+1}=A\mathbf x_k\text{.}\) Podemos pensar en la secuencia\(\mathbf x_k\) 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 estacionario\(\mathbf q\) para una matriz estocástica\(A\) es un vector de probabilidad que satisface\(A\mathbf q = \mathbf q\text{.}\)
• El teorema de Perron-Frobenius nos dice que, si\(A\) es una matriz estocástica positiva, entonces cada cadena de Markov definida por\(A\) 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

1

Considera las siguientes matrices\(2\times2\) 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.

1. \(\left[\begin{array}{rr} 1 & 1 \\ 0 & 0 \\ \end{array}\right] \text{.}\)
2. \(\left[\begin{array}{rr} 0.8 & 1 \\ 0.2 & 0 \\ \end{array}\right] \text{.}\)
3. \(\left[\begin{array}{rr} 1 & 0 \\ 0 & 1 \\ \end{array}\right] \text{.}\)
4. \(\left[\begin{array}{rr} 0.7 & 0.6 \\ 0.3 & 0.4 \\ \end{array}\right] \text{.}\)

2

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.

Figura 4.5.12. El flujo entre poblaciones urbanas, suburbanas y rurales.

1. Construir la matriz estocástica\(A\) describiendo el movimiento de personas.
2. Explicar lo que nos dice el teorema de Perron-Frobenius sobre la existencia de un vector de estado estacionario\(\mathbf q\) y el comportamiento de una cadena de Markov.
3. Usa la celda de Sage a continuación para encontrar algunos términos de una cadena de Markov.
4. Describir la distribución a largo plazo de las personas entre poblaciones urbanas, suburbanas y rurales.

3

Determine si las siguientes afirmaciones son verdaderas o falsas y proporcione una justificación de su respuesta.

1. Cada matriz estocástica tiene un vector de estado estacionario.
2. Si\(A\) es una matriz estocástica, entonces cualquier cadena de Markov definida por\(A\) converge a un vector de estado estacionario.
3. Si\(A\) es una matriz estocástica, entonces\(\lambda=1\) es un valor propio y todos los demás valores propios satisfacen\(|\lambda| \lt 1\text{.}\)
4. Una matriz estocástica positiva tiene un vector de estado estacionario único.
5. Si\(A\) es una matriz estocástica invertible, entonces también lo es\(A^{-1}\text{.}\)

4

Considerar la matriz estocástica

\ begin {ecuación*} A =\ left [\ begin {array} {rrr} 1 & 0.2 & 0.2\\ 0 & 0.6 & 0.2\\ 0 & 0.2 & 0.6\\ end {array}\ right]\ text {.} \ end {ecuación*}

1. Encuentra los valores propios de\(A\text{.}\)
2. ¿Se aplican a esta matriz las condiciones del teorema de Perron-Frobenius?
3. Encuentra los vectores de steady-state de\(A\text{.}\)
4. Qué podemos garantizar sobre el comportamiento a largo plazo de una cadena de Markov definida por la matriz\(A\text{?}\)

5

Explique sus respuestas a lo siguiente.

1. ¿Por qué Google usa una cadena de Markov para calcular el vector PageRank?
2. Describir dos problemas que pueden ocurrir cuando Google construye una cadena de Markov usando la matriz de Google\(G\text{.}\)
3. Describir cómo estos problemas son consistentes con el teorema de Perron-Frobenius.
4. Describir por qué el teorema de Perron-Frobenius sugiere crear una cadena de Markov usando la matriz de Google modificada\(G' = \alpha G + (1-\alpha)H_n\text{.}\)

En los próximos ejercicios, consideraremos la\(1\times n\) matriz\(S = \left[\begin{array}{rrrr} 1 & 1 & \ldots & 1 \end{array}\right]\text{.}\)

6

Supongamos que\(A\) es una matriz estocástica y que\(\mathbf x\) es un vector de probabilidad. Nos gustaría explicar por qué el producto\(A\mathbf x\) es un vector de probabilidad.

1. Explica por qué\(\mathbf x=\threevec{0.4}{0.5}{0.1}\) es un vector de probabilidad y luego encuentra el producto\(S\mathbf x\text{.}\)
2. De manera más general, si\(\mathbf x\) es algún vector de probabilidad, cuál es el producto\(S\mathbf x\text{?}\)
3. Si\(A\) es una matriz estocástica, explique por qué\(SA=S\text{.}\)
4. Explicar por qué\(A\mathbf x\) es un vector de probabilidad considerando el producto\(SA\mathbf x\text{.}\)

7

Utilizando los resultados del ejercicio anterior, nos gustaría explicar por qué\(A^2\) es una matriz estocástica si\(A\) es estocástica.

1. Supongamos que\(A\) y\(B\) son matrices estocásticas. Explicar por qué el producto\(AB\) es una matriz estocástica considerando el producto\(SAB\text{.}\)
2. Explicar por qué\(A^2\) es una matriz estocástica.
3. ¿Cómo se\(A^2\) comparan los vectores de estado estacionario con los vectores de estado estacionario de\(A\text{?}\)

8

Este ejercicio explica por qué\(\lambda=1\) es un valor propio de una matriz estocástica\(A\text{.}\) Para concluir que\(\lambda=1\) es un valor propio, necesitamos saber que no\(A-I\) es invertible.

1. Cuál es el producto\(S(A-I)\text{?}\)
2. Explique por qué\(\col(A-I)\) está contenido en\(\nul(S)\text{.}\)
3. Cuál es el producto\(S\mathbf e_1\text{?}\)
4. Explicar por qué no\(\mathbf e_1\) está contenido en el espacio de columna\(\col(A-I)\text{.}\)
5. Explicar por qué podemos concluir que no\(A-I\) es invertible y que\(\lambda=1\) es un valor propio de\(A\text{.}\)

9

Vimos un par de modelos Internets en los que una cadena de Markov definida por la matriz de Google\(G\) no convergía a un vector PageRank apropiado. Por esta razón, Google define la matriz

\ begin {ecuación*} h_n =\ left [\ begin {array} {rrrr}\ frac1n &\ frac1n &\ ldots &\ frac1n\\ frac1n\\ frac1n &\ ldots &\ frac1n\\ vdots &\ vdots &\ ddots &\ ddots &\ vdots\\ vdots\\\ frac1n &\ ldots &\ frac1n\\\ end {array}\ right]\ text {,}\ end {ecuación*}

donde\(n\) es el número de páginas web, y construye una cadena de Markov a partir de la matriz de Google modificada

\ begin {ecuación*} G' =\ alfa G + (1-\ alpha) H_n\ texto {.} \ end {ecuación*}

Dado que\(G'\) es positivo, se garantiza que la cadena de Markov converja en un vector de estado estacionario único.

Dijimos que Google elige\(\alpha = 0.85\) así que podríamos preguntarnos por qué esta es una buena opción. Exploraremos el papel de\(\alpha\) en este ejercicio. Consideremos el modelo Internet descrito en la Figura 4.5.9 y construyamos la matriz de Google\(G\text{.}\) En la celda de Sage a continuación, puede ingresar la matriz\(G\) y elegir un valor para\(\alpha\text{.}\)

1. Empecemos con\(\alpha=0\text{.}\) Con esta elección, cuál es la matriz\(G'=\alpha G + (1-\alpha)H_n\text{?}\) 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 se\(\mathbf x_k\) muestran los vectores?
2. Ahora elija\(\alpha=0.25\text{.}\) ¿Cuántos pasos se requieren para que la cadena de Markov converja a la precisión con la que se\(\mathbf x_k\) muestran los vectores?
3. Repita este experimento con\(\alpha = 0.5\) y\(\alpha=0.75\text{.}\)
4. ¿Qué pasa si\(\alpha = 1\text{?}\)

Este experimento da una idea de la elección de\(\alpha\text{.}\) Cuanto más pequeño\(\alpha\) es, más rápido converge la cadena de Markov. Esto es importante; dado\(G'\) 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\(\alpha\text{,}\) la matriz\(G' = \alpha G + (1-\alpha)H_n\) comienza a parecerse\(H_n\) cada vez\(G\) menos. El valor\(\alpha=0.85\) se elige para que la matriz se parezca\(G'\) suficientemente\(G\) mientras que la cadena de Markov converge en una cantidad razonable de pasos.

10

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 una\(10\times10\) 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.

1. 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 la\(8\times8\) matriz\(A\) 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 inicial\(\mathbf x_0 = \mathbf e_1\text{.}\) Generar unos términos de la cadena Markov\(\mathbf x_{k+1} = A\mathbf x_k\text{.}\)

   ¿Cuál es la probabilidad de que lleguemos al cuadrado 8 por el cuarto movimiento? ¿Por la sexta jugada? ¿Por la séptima jugada?

2. 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 matriz\(6\times6\) 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 con\(\mathbf x_0=\mathbf e_1\text{.}\)

   1. ¿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?
   2. ¿Cuál es la probabilidad de que lleguemos al cuadrado 6 después de cinco movimientos?
   3. ¿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?
   4. Después de cuántos movimientos tenemos un 90% de posibilidades de haber llegado a la plaza 6?
   5. 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.