En 1998, Lawrence Page, Sergey Brin, Rajiv Motwani y Terry Vinograd publicaron el artículo "The PageRank Citation Ranking: Bringing Order to the Web", que describía el ahora famoso algoritmo PageRank, que se convirtió en la base de Google. Después de un poco menos de dos décadas, Google se convirtió en un gigante, y aunque su algoritmo ha evolucionado mucho, PageRank sigue siendo el "símbolo" de los algoritmos de clasificación de Google (aunque solo unas pocas personas realmente pueden decir cuánto peso tiene el algoritmo hoy) .
Desde un punto de vista teórico, es interesante observar que una de las interpretaciones estándar del algoritmo PageRank se basa en un concepto simple pero fundamental de las cadenas de Markov. Del artículo veremos que las cadenas de Markov son herramientas poderosas para el modelado estocástico que pueden ser útiles para cualquier científico de datos. En particular, responderemos preguntas tan básicas: ¿qué son las cadenas de Markov, qué buenas propiedades poseen y qué se puede hacer con su ayuda?
Breve reseña
En la primera sección, damos las definiciones básicas necesarias para comprender las cadenas de Markov. En la segunda sección, consideramos el caso especial de las cadenas de Markov en un espacio de estado finito. En la tercera sección, consideramos algunas de las propiedades elementales de las cadenas de Markov e ilustramos estas propiedades con muchos ejemplos pequeños. Finalmente, en la cuarta sección, asociamos las cadenas de Markov con el algoritmo PageRank y vemos con un ejemplo artificial cómo se pueden usar las cadenas de Markov para clasificar los nodos de un gráfico.
Nota Comprender esta publicación requiere conocer los conceptos básicos de probabilidad y álgebra lineal. En particular, se utilizarán los siguientes conceptos: probabilidad condicional , vector propio y fórmula de probabilidad completa .
¿Qué son las cadenas de Markov?
Variables aleatorias y procesos aleatorios.
Antes de presentar el concepto de cadenas de Markov, recordemos brevemente los conceptos básicos, pero importantes, de la teoría de la probabilidad.
Primero, fuera del lenguaje matemático, una
variable aleatoria X es una cantidad determinada por el resultado de un fenómeno aleatorio. Su resultado puede ser un número (o "similitud de un número", por ejemplo, vectores) u otra cosa. Por ejemplo, podemos definir una variable aleatoria como el resultado de una tirada de un dado (número) o como el resultado de un lanzamiento de moneda (no un número, a menos que designemos, por ejemplo, "águila" como 0, pero "colas" como 1). También mencionamos que el espacio de posibles resultados de una variable aleatoria puede ser discreto o continuo: por ejemplo, una variable aleatoria normal es continua y una variable aleatoria de Poisson es discreta.
Además, podemos definir un
proceso aleatorio (también llamado estocástico) como un conjunto de variables aleatorias indexadas por el conjunto T, que a menudo denota diferentes puntos en el tiempo (en lo que sigue asumiremos esto). Los dos casos más comunes: T puede ser un conjunto de números naturales (proceso aleatorio con tiempo discreto) o un conjunto de números reales (proceso aleatorio con tiempo continuo). Por ejemplo, si lanzamos una moneda todos los días, estableceremos un proceso aleatorio con tiempo discreto, y el valor siempre cambiante de una opción en el intercambio establecerá un proceso aleatorio con tiempo continuo. Las variables aleatorias en diferentes momentos pueden ser independientes entre sí (un ejemplo con un lanzamiento de moneda) o tener algún tipo de dependencia (un ejemplo con el valor de la opción); Además, pueden tener un espacio de estado continuo o discreto (el espacio de resultados posibles en cada momento).
Diferentes tipos de procesos aleatorios (discretos / continuos en espacio / tiempo).Propiedad de Markov y cadena de Markov
Existen familias bien conocidas de procesos aleatorios: procesos gaussianos, procesos de Poisson, modelos autorregresivos, modelos de promedio móvil, cadenas de Markov y otros. Cada uno de estos casos individuales tiene ciertas propiedades que nos permiten explorarlos y comprenderlos mejor.
Una de las propiedades que simplifica enormemente el estudio de un proceso aleatorio es la propiedad de Markov. Si lo explicamos en un lenguaje muy informal, la propiedad Markov nos dice que si conocemos el valor obtenido por algún proceso aleatorio en un momento dado, no recibiremos ninguna información adicional sobre el comportamiento futuro del proceso, recolectando otra información sobre su pasado. En un lenguaje más matemático: en cualquier momento, la distribución condicional de estados futuros de un proceso con estados actuales y pasados depende solo del estado actual, y no de estados pasados (la
propiedad de la falta de memoria ). Un proceso aleatorio con una propiedad de Markov se llama
proceso de Markov .
La propiedad de Markov significa que si conocemos el estado actual en un momento dado, no necesitamos ninguna información adicional sobre el futuro, recopilada del pasado.En base a esta definición, podemos formular la definición de "cadenas de Markov homogéneas con tiempo discreto" (en adelante, por simplicidad las llamaremos "cadenas de Markov").
La cadena de Markov es un proceso de Markov con tiempo discreto y un espacio de estado discreto. Entonces, una cadena de Markov es una secuencia discreta de estados, cada uno de los cuales se toma de un espacio de estado discreto (finito o infinito), satisfaciendo la propiedad de Markov.
Matemáticamente, podemos denotar la cadena de Markov de la siguiente manera:
donde en cada momento el proceso toma sus valores de un conjunto discreto E, de modo que
Entonces la propiedad de Markov implica que tenemos
Tenga en cuenta nuevamente que esta última fórmula refleja el hecho de que, para la cronología (dónde estoy ahora y dónde estaba antes), la distribución de probabilidad del siguiente estado (donde seré el próximo) depende del estado actual, pero no de los estados pasados.
Nota En esta publicación introductoria, decidimos hablar solo sobre cadenas de Markov homogéneas simples con tiempo discreto. Sin embargo, también hay cadenas de Markov no homogéneas (dependientes del tiempo) y / o cadenas de tiempo continuo. En este artículo no consideraremos tales variaciones del modelo. También vale la pena señalar que la definición anterior de una propiedad de Markov está extremadamente simplificada: la verdadera definición matemática utiliza el concepto de filtrado, que va mucho más allá de nuestro conocimiento introductorio del modelo.
Caracterizamos la dinámica de aleatoriedad de una cadena de Markov
En la subsección anterior, nos familiarizamos con la estructura general correspondiente a cualquier cadena de Markov. Veamos qué necesitamos para establecer una "instancia" específica de un proceso tan aleatorio.
Primero, observamos que la determinación completa de las características de un proceso aleatorio con un tiempo discreto que no satisface la propiedad de Markov puede ser difícil: la distribución de probabilidad en un momento dado puede depender de uno o más momentos en el pasado y / o en el futuro. Todas estas posibles dependencias de tiempo pueden potencialmente complicar la creación de una definición de proceso.
Sin embargo, debido a la propiedad de Markov, la dinámica de la cadena de Markov es bastante simple de determinar. Y de hecho. solo necesitamos determinar dos aspectos: la
distribución de probabilidad inicial (es decir, la distribución de probabilidad en el tiempo n = 0), denotada por
y
la matriz de probabilidad de transición (que nos da las probabilidades de que el estado en el tiempo n + 1 sea el siguiente para otro estado en el tiempo n para cualquier par de estados), denotado por
Si se conocen estos dos aspectos, entonces la dinámica completa (probabilística) del proceso está claramente definida. Y, de hecho, la probabilidad de cualquier resultado del proceso puede calcularse cíclicamente.
Ejemplo: supongamos que queremos saber la probabilidad de que los primeros 3 estados del proceso tengan valores (s0, s1, s2). Es decir, queremos calcular la probabilidad
Aquí aplicamos la fórmula para la probabilidad total, que establece que la probabilidad de obtener (s0, s1, s2) es igual a la probabilidad de obtener el primer s0 multiplicado por la probabilidad de obtener s1, dado que anteriormente recibimos s0 multiplicado por la probabilidad de obtener s2 teniendo en cuenta el hecho de que llegamos antes en el orden s0 y s1. Matemáticamente, esto se puede escribir como
Y luego se revela la simplificación, determinada por el supuesto de Markov. Y, de hecho, en el caso de las cadenas largas, obtenemos probabilidades fuertemente condicionales para los últimos estados. Sin embargo, en el caso de las cadenas de Markov, podemos simplificar esta expresión aprovechando el hecho de que
de esta manera
Dado que caracterizan completamente la dinámica probabilística del proceso, muchos eventos complejos pueden calcularse solo sobre la base de la distribución de probabilidad inicial q0 y la matriz de probabilidad de transición p. También vale la pena mencionar una conexión básica más: la expresión de la distribución de probabilidad en el tiempo n + 1, expresada con respecto a la distribución de probabilidad en el tiempo n
Cadenas de Markov en espacios de estados finitos
Representación matricial y gráfica
Aquí suponemos que el conjunto E tiene un número finito de estados posibles N:
Entonces, la distribución de probabilidad inicial se puede describir como
un vector de fila q0 de tamaño N, y las probabilidades de transición se pueden describir como una matriz p de tamaño N por N, de modo que
La ventaja de esta notación es que si denotamos la distribución de probabilidad en el paso n por el vector de fila qn de modo que se especifiquen sus componentes
entonces se preservan las relaciones simples de la matriz
(aquí no consideraremos la prueba, pero es muy simple reproducirla).
Si multiplicamos el vector de fila de la derecha, que describe la distribución de probabilidad en una etapa de tiempo dada, por la matriz de probabilidad de transición, entonces obtenemos la distribución de probabilidad en la siguiente etapa de tiempo.Entonces, como vemos, la transición de la distribución de probabilidad de una etapa dada a la siguiente simplemente se define como la multiplicación correcta del vector de filas de probabilidades del paso inicial por la matriz p. Además, esto implica que tenemos
La dinámica aleatoria de una cadena de Markov en un espacio de estado finito se puede representar fácilmente como un gráfico orientado normalizado de modo que cada nodo del gráfico sea un estado, y para cada par de estados (ei, ej) existe un borde que va de ei a ej si p (ei, ej )> 0. Entonces el valor de borde será la misma probabilidad p (ei, ej).
Ejemplo: un lector de nuestro sitio
Vamos a ilustrar todo esto con un simple ejemplo. Considere el comportamiento cotidiano de un visitante ficticio de un sitio. Todos los días tiene 3 condiciones posibles: el lector no visita el sitio ese día (N), el lector visita el sitio, pero no lee la publicación completa (V), y el lector visita el sitio y lee una publicación completa (R). Entonces, tenemos el siguiente espacio de estado:
Supongamos que, el primer día, este lector tiene un 50% de posibilidades de acceder solo al sitio y un 50% de posibilidades de visitar el sitio y leer al menos un artículo. El vector que describe la distribución de probabilidad inicial (n = 0) se ve así:
También imagine que se observan las siguientes probabilidades:
- cuando el lector no lo visita un día, existe una probabilidad del 25% de no visitarlo al día siguiente, una probabilidad del 50% solo de visitarlo y del 25% de visitar y leer el artículo
- cuando el lector visita el sitio un día, pero no lee, tiene un 50% de posibilidades de volver a visitarlo al día siguiente y no leer el artículo, y un 50% de posibilidades de visitar y leer
- cuando un lector visita y lee un artículo el mismo día, tiene un 33% de posibilidades de no iniciar sesión al día siguiente (¡espero que esta publicación no tenga ese efecto!) , un 33% de posibilidades de iniciar sesión solo en el sitio y 34% de visitar y leer el artículo nuevamente
Luego tenemos la siguiente matriz de transición:
De la subsección anterior, sabemos cómo calcular para este lector la probabilidad de cada estado al día siguiente (n = 1)
La dinámica probabilística de esta cadena de Markov se puede representar gráficamente de la siguiente manera:
Presentación en forma de gráfico de la cadena de Markov, que modela el comportamiento de nuestro visitante inventado en el sitio.Propiedades de las cadenas de Markov
En esta sección, hablaremos solo sobre algunas de las propiedades o características más básicas de las cadenas de Markov. No entraremos en detalles matemáticos, pero brindaremos una breve descripción de los puntos interesantes que deben estudiarse para usar las cadenas de Markov. Como hemos visto, en el caso de un espacio de estado finito, la cadena de Markov se puede representar como un gráfico. En el futuro, utilizaremos la representación gráfica para explicar algunas propiedades. Sin embargo, no olvide que estas propiedades no se limitan necesariamente al caso de un espacio de estado finito.
Descomponibilidad, periodicidad, irrevocabilidad y recuperabilidad.
En esta subsección, comencemos con varias formas clásicas de caracterizar un estado o una cadena completa de Markov.
Primero, mencionamos que la cadena de Markov es
indescomponible si es posible alcanzar cualquier estado desde cualquier otro estado (no es necesario que en un solo paso del tiempo). Si el espacio de estado es finito y la cadena se puede representar como un gráfico, entonces podemos decir que el gráfico de una cadena de Markov no descomponible está fuertemente conectado (teoría de los gráficos).
Ilustración de la propiedad de la descomposición (irreductibilidad). La cadena de la izquierda no se puede acortar: desde 3 o 4 no podemos entrar en 1 o 2. La cadena de la derecha (se agrega un borde) se puede acortar: se puede alcanzar cada estado desde cualquier otro.Un estado tiene un período k si, al abandonarlo, para cualquier retorno a este estado, el número de pasos de tiempo es un múltiplo de k (k es el divisor común más grande de todas las longitudes posibles de rutas de retorno). Si k = 1, entonces dicen que el estado es aperiódico, y toda la cadena de Markov es
aperiódica si todos sus estados son aperiódicos. En el caso de una cadena de Markov irreducible, también podemos mencionar que si un estado es aperiódico, todos los demás también lo son.
Ilustración de la propiedad de periodicidad. La cadena de la izquierda es periódica con k = 2: al salir de cualquier estado, volver a ella siempre requiere el número de pasos múltiplo de 2. La cadena de la derecha tiene un período de 3.Un estado es
irrevocable si, al salir del estado, existe una probabilidad distinta de cero de que nunca volvamos a él. Por el contrario, un estado se considera
retornable si sabemos que después de abandonar el estado podemos volver a él en el futuro con probabilidad 1 (si no es irrevocable).
Ilustración de la propiedad de devolución / irrevocabilidad. La cadena de la izquierda tiene las siguientes propiedades: 1, 2 y 3 son irrevocables (al abandonar estos puntos no podemos estar absolutamente seguros de que volveremos a ellos) y tienen un período de 3, y 4 y 5 son retornables (al abandonar estos puntos estamos absolutamente seguros que algún día volveremos a ellos) y tendremos un período de 2. La cadena de la derecha tiene otra costilla, lo que hace que toda la cadena sea retornable y aperiódica.Para el estado de retorno, podemos calcular el tiempo de retorno promedio, que es el
tiempo de retorno esperado al salir del estado. Tenga en cuenta que incluso la probabilidad de un retorno es 1, esto no significa que el tiempo de retorno esperado sea finito. Por lo tanto, entre todos los estados de retorno, podemos distinguir entre
estados de retorno positivos (con un tiempo de retorno esperado finito) y
estados de retorno cero (con un tiempo de retorno esperado infinito).
Distribución estacionaria, comportamiento marginal y ergodicidad.
En esta subsección, consideramos las propiedades que caracterizan algunos aspectos de la dinámica (aleatoria) descrita por la cadena de Markov.
La distribución de probabilidad π sobre el espacio de estado E se llama
distribución estacionaria si satisface la expresión
Ya que tenemos
Entonces la distribución estacionaria satisface la expresión
Por definición, la distribución de probabilidad estacionaria no cambia con el tiempo. Es decir, si la distribución inicial q es estacionaria, será la misma en todas las etapas posteriores del tiempo. Si el espacio de estados es finito, entonces p puede representarse como una matriz y π como un vector de fila, y luego obtenemos
Esto nuevamente expresa el hecho de que la distribución de probabilidad estacionaria no cambia con el tiempo (como vemos, multiplicar la distribución de probabilidad a la derecha por p nos permite calcular la distribución de probabilidad en la siguiente etapa del tiempo). Tenga en cuenta que una cadena de Markov indescomponible tiene una distribución de probabilidad estacionaria si y solo si uno de sus estados es un retorno positivo.
Otra propiedad interesante relacionada con la distribución de probabilidad estacionaria es la siguiente. Si la cadena es de retorno positivo (es decir, tiene una distribución estacionaria) y aperiódica, entonces, cualesquiera que sean las probabilidades iniciales, la distribución de probabilidad de la cadena converge a medida que los intervalos de tiempo tienden al infinito: dicen que la cadena tiene una
distribución limitante , que no es otra cosa, como una distribución estacionaria. En general, se puede escribir así:
Hacemos hincapié una vez más en el hecho de que no hacemos suposiciones sobre la distribución de probabilidad inicial: la distribución de probabilidad de la cadena se reduce a una distribución estacionaria (distribución de equilibrio de la cadena) independientemente de los parámetros iniciales.Finalmente, la ergodicidad es otra propiedad interesante relacionada con el comportamiento de la cadena de Markov. Si la cadena de Markov es indescomponible, entonces también se dice que es "ergódica" porque satisface el siguiente teorema ergódico. Supongamos que tenemos una función f (.) Que va del espacio de estado E al eje (esto puede ser, por ejemplo, el precio de estar en cada estado). Podemos determinar el valor promedio que mueve esta función a lo largo de una trayectoria dada (promedio temporal). Para los enésimos primeros términos, esto se denota comoTambién podemos calcular el valor promedio de la función f en el conjunto E, ponderado por la distribución estacionaria (promedio espacial), que se denotaEntonces el teorema ergódico nos dice que cuando la trayectoria se vuelve infinitamente larga, el promedio de tiempo es igual al promedio espacial (ponderado por la distribución estacionaria). La propiedad de ergodicidad se puede escribir de la siguiente manera:En otras palabras, significa que en el límite anterior, el comportamiento de la trayectoria se vuelve insignificante y solo el comportamiento estacionario a largo plazo es importante al calcular el promedio temporal.Volvamos al ejemplo con el lector del sitio.
Nuevamente, considere el ejemplo del lector del sitio. En este simple ejemplo, es obvio que la cadena es indescomponible, aperiódica y todos sus estados son positivamente retornables.Para mostrar qué resultados interesantes se pueden calcular utilizando las cadenas de Markov, consideramos el tiempo promedio de retorno al estado R (el estado "visita el sitio y lee el artículo"). En otras palabras, queremos responder la siguiente pregunta: si nuestro lector visita el sitio un día y lee un artículo, ¿cuántos días tendremos que esperar en promedio para que regrese y lea el artículo? Intentemos obtener un concepto intuitivo de cómo se calcula este valor.Primero denotamosEntonces queremos calcular m (R, R). Hablando sobre el primer intervalo alcanzado después de salir de R, obtenemosSin embargo, esta expresión requiere que para el cálculo de m (R, R) sepamos m (N, R) ym (V, R). Estas dos cantidades se pueden expresar de manera similar:Entonces, obtuvimos 3 ecuaciones con 3 incógnitas y después de resolverlas obtenemos m (N, R) = 2.67, m (V, R) = 2.00 ym (R, R) = 2.54. El tiempo promedio para volver al estado R es entonces 2.54. Es decir, usando álgebra lineal, pudimos calcular el tiempo promedio de retorno al estado R (así como el tiempo promedio de transición de N a R y el tiempo promedio de transición de V a R).Para terminar con este ejemplo, veamos cuál será la distribución estacionaria de la cadena de Markov. Para determinar la distribución estacionaria, necesitamos resolver la siguiente ecuación de álgebra lineal:Es decir, necesitamos encontrar el vector propio izquierdo p asociado con el vector propio 1. Al resolver este problema, obtenemos la siguiente distribución estacionaria:Distribución estacionaria en el ejemplo con el lector del sitio.También puede notar que π (R) = 1 / m (R, R), y si un poco de reflexión, esta identidad es bastante lógica (pero no hablaremos de esto en detalle).Dado que la cadena es indescomponible y aperiódica, esto significa que a la larga la distribución de probabilidad converge a una distribución estacionaria (para cualquier parámetro inicial). En otras palabras, cualquiera que sea el estado inicial del lector del sitio, si esperamos lo suficiente y seleccionamos un día al azar, obtendremos la probabilidad π (N) de que el lector no visite el sitio ese día, la probabilidad π (V) de que el lector se detendrá pero no leerá el artículo, y la probabilidad es π® de que el lector se detenga y lea el artículo. Para comprender mejor la propiedad de la convergencia, echemos un vistazo al siguiente gráfico que muestra la evolución de las distribuciones de probabilidad a partir de diferentes puntos de partida y (rápidamente) convergiendo a una distribución estacionaria:Visualización de la convergencia de 3 distribuciones de probabilidad con diferentes parámetros iniciales (azul, naranja y verde) a la distribución estacionaria (rojo).Ejemplo clásico: Algoritmo de PageRank
¡Es hora de volver al PageRank! Pero antes de continuar, vale la pena mencionar que la interpretación de PageRank dada en este artículo no es la única posible, y los autores del artículo original no necesariamente se basaron en el uso de cadenas de Markov al desarrollar la metodología. Sin embargo, nuestra interpretación es buena porque es muy clara.Usuario web arbitrario
PageRank está tratando de resolver el siguiente problema: ¿cómo podemos clasificar un conjunto existente (podemos suponer que este conjunto ya ha sido filtrado, por ejemplo, por alguna consulta) utilizando enlaces que ya existen entre las páginas?Para resolver este problema y poder clasificar las páginas, PageRank realiza aproximadamente el siguiente proceso. Creemos que un usuario arbitrario de Internet en el momento inicial está en una de las páginas. Luego, este usuario comienza a moverse aleatoriamente, haciendo clic en cada página en uno de los enlaces que conducen a otra página del conjunto en cuestión (se supone que todos los enlaces que salen de estas páginas están prohibidos). En cualquier página, todos los enlaces válidos tienen la misma probabilidad de hacer clic.Así es como definimos la cadena de Markov: las páginas son estados posibles, las probabilidades de transición se establecen mediante enlaces de página a página (ponderadas de tal manera que en cada página todas las páginas enlazadas tienen la misma probabilidad de selección), y las propiedades de falta de memoria están claramente determinadas por el comportamiento del usuario. Si también suponemos que la cadena dada es positivamente retornable y aperiódica (se utilizan pequeños trucos para cumplir con estos requisitos), entonces a la larga la distribución de probabilidad de la "página actual" converge a una distribución estacionaria. Es decir, sea cual sea la página inicial, después de mucho tiempo, cada página tiene una probabilidad (casi fija) de actualizarse si elegimos un momento aleatorio en el tiempo.PageRank se basa en la siguiente hipótesis: las páginas más probables en una distribución estacionaria también deberían ser las más importantes (visitamos estas páginas a menudo porque obtienen enlaces de páginas que también se visitan con frecuencia durante las transiciones). Luego, la distribución de probabilidad estacionaria determina el valor de PageRank para cada estado.Ejemplo Artificial
Para hacer esto mucho más claro, veamos un ejemplo artificial. Supongamos que tenemos un pequeño sitio web con 7 páginas, etiquetadas del 1 al 7, y los enlaces entre estas páginas corresponden a la siguiente columna.En aras de la claridad, no se muestran las probabilidades de cada transición en la animación que se muestra arriba. Sin embargo, dado que se supone que la "navegación" debe ser exclusivamente aleatoria (esto se denomina "caminata aleatoria"), los valores se pueden reproducir fácilmente a partir de la siguiente regla simple: para un sitio con K enlaces salientes (una página con K enlaces a otras páginas), la probabilidad de cada enlace saliente igual a 1 / K. Es decir, la matriz de probabilidad de transición tiene la forma:donde los valores de 0.0 se reemplazan por conveniencia por ".". Antes de realizar más cálculos, podemos notar que esta cadena de Markov es indescomponible y aperiódica, es decir, a la larga, el sistema converge a una distribución estacionaria. Como hemos visto, esta distribución estacionaria se puede calcular resolviendo el siguiente problema del vector propio izquierdoAl hacerlo, obtenemos los siguientes valores de PageRank (valores de distribución estacionarios) para cada páginaValores de PageRank calculados para nuestro ejemplo artificial de 7 páginas.Entonces el ranking de PageRank de este pequeño sitio web es 1> 7> 4> 2> 5 = 6> 3.
Conclusiones
Hallazgos clave de este artículo:- Los procesos aleatorios son conjuntos de variables aleatorias que a menudo se indexan por tiempo (los índices a menudo indican tiempo discreto o continuo)
- para un proceso aleatorio, la propiedad de Markov significa que para una corriente dada, la probabilidad del futuro no depende del pasado (esta propiedad también se llama "falta de memoria")
- la cadena de Markov de tiempo discreto es procesos aleatorios con índices de tiempo discreto que satisfacen la propiedad de Markov
- ( , …)
- PageRank ( ) -, ; ( , , , )
En conclusión, enfatizamos una vez más cuán poderosas son las herramientas de las cadenas de Markov para modelar problemas asociados con dinámicas aleatorias. Debido a sus buenas propiedades, se usan en varios campos, por ejemplo, en la teoría de colas (optimizando el rendimiento de las redes de telecomunicaciones, en las que los mensajes a menudo tienen que competir por recursos limitados y se ponen en cola cuando ya se han tomado todos los recursos), en estadísticas (conocido Monte Carlo según el esquema de la cadena de Markov para generar variables aleatorias se basa en las cadenas de Markov), en biología (modelando la evolución de las poblaciones biológicas), en informática (los modelos ocultos de Markov son herramientas importantes umentami en teoría de la información, y el reconocimiento de voz), así como en otras áreas.Por supuesto, las enormes oportunidades que ofrecen las cadenas de Markov desde el punto de vista del modelado y la computación son mucho más amplias que las consideradas en esta modesta revisión. Por lo tanto, esperamos haber podido despertar el interés del lector en seguir estudiando estas herramientas, que ocupan un lugar importante en el arsenal de un científico y experto en datos.