Procesos Markov: Básicos

Versión juego adaptivo

Este tutorial: Parte A: Procesos Markov: Básicos

Ir a Parte B: Procesos Markov regulares y absorbentes

(Se puede encontrar este tema en la Sección 8.7 en el libro Matemáticas finitas y cálculo aplicado)

¿Qué es un tutorial juego adaptivo? ▶

%%Note Para intender este tutorial, Debes saber cómo configurar y multiplicar matrices como se describe en el %%maddtut y el %%mtut.

Recursos

Herramienta álgebra matricial

Simulación de sistemas Markov

Utilidad computación para sistemas Markov

¿Qué es un sistema Markov?

#[A Markov system (or Markov process or Markov chain) is a system that can be in one of several (numbered) states, and can pass from one state to another each time step according to fixed probabilities.][Un sistema Markov (o proceso Markov o cadena Markov) es un sistema que puede estar en uno de varios estados (numerados) y puede pasar de un estado a otro en cada paso de tiempo según probabilidades fijas.]# #[If a Markov system is in state $i$, there is a fixed probability, $p_{ij}$, of it going into state $j$ the next time step, and $p_{ij}$ is called a transition probability.][Si un sistema Markov está en el estado $i$, existe una probabilidad fija, $p_{ij}$, de que pase al estado $j$ en el siguiente paso de tiempo, y $p_{ij}$ se denomina probabilidad de transición.]#

#[A Markov system can be illustrated by means of a state transition diagram, which is a diagram showing all the states and transition probabilities:][Un sistema Markov se puede ilustrar mediante un diagrama de transición de estados, que es un diagrama que muestra todos los estados y probabilidades de transición:]#

Sistema Markov: dos estados

Sistema Markov: tres estados

#[The matrix $P$ whose $ij$th entry is $p_{ij}$ is called the transition matrix associated with the system. Thus, for instance, the transition matrices dor the above two systems would be set up as follows.][La matriz $P$ cuya entrada $ij$ es $p_{ij}$ se denomina matriz de transición asociada al sistema. Así, por ejemplo, las matrices de transición para los dos sistemas anteriores se configurarían de la siguiente manera.]#

Dos estados

#[ To][Al]#

#[From][Del]# [,1,2;1,p_{11},p_{12};2,p_{21},p_{22}][,#[ Arrows from state 1][ Flechas del estado 1]#,#[ Arrows from state 2][ Flechas del estado 2]#]

\t \t

Tres estados

#[ To][Al]#

#[From][Del]# [,1,2,3;1,p_{11},p_{12},p_{13};2,p_{21},p_{22},p_{23};3,p_{31},p_{32},p_{33}][,#[ Arrows from state 1][ Flechas del estado 1]#,#[ Arrows from state 2][ Flechas del estado 2]#,#[ Arrows from state 3][ Flechas del estado 3]#]

%%Note #[If the system happens to be in state $i$ at the start of a time step, then it has a probability of 1 of being in some (possibly different) state the next time step. It follows that the sum of the probabilities][Si el sistema se encuentra en el estado $i$ al comienzo de un paso de tiempo, entonces tiene una probabilidad de 1 de estar en algún estado (posiblemente diferente) en el siguiente paso de tiempo. Por lo tanto, la suma de las probabilidades]#

$p_{i1}, p_{i2}, ..., p_{in}$

#[must be 1. In other words, the entries in each row of the transition matrix add up to 1.][debe ser 1. En otras palabras, las entradas en cada fila de la matriz de transición suman 1.]#

#[Example of a Markov system][Ejemplo de un sistema Markov]#

#[Weather][Clima]#: #[Consider a simple weather model with two states: "Sunny" and "Cloudy." Each day, the weather can either stay the same or change to the other state. The probabilities of transitioning from one state to another are defined as follows:][Consideremos un modelo simple de clima con dos estados: "Soleado" y "Nublado". Cada día, el tiempo puede permanecer igual o cambiar al otro estado. Las probabilidades de transición de un estado a otro se definen de la siguiente manera:]#

#[If today is Sunny, there is a 40% chance it will be Sunny again tomorrow and a 60% chance it will be Cloudy.][Si hoy está Soleado, hay un 40% de posibilidades de que mañana vuelva a estar Soleado y un 60% de posibilidades de esté Nublado.]#
#[If today is Cloudy, there's an 80% chance it will be Cloudy again tomorrow and a 20% chance it will be Sunny.][Si hoy es Nublado, hay un 80% de posibilidades de que mañana vuelva a llover y un 20% de posibilidades de que esté Soleado.]#

#[We can represent this system by the following state-transition diagram][Podemos representar este sistema con el siguiente diagrama de transición de estados]#

#[which has transition matrix][que tiene diagrama de transición]# [.4,.6;.2,.8].

#[Your turn][Tu turno]#

Vectores de distribución

Echemos otro vistazo al sistema general de tres estados como el que vimos anteriormente, y supongamos que este diagrama modela el flujo de tráfico de estudiantes entre tres ubicaciones:

El departamento de matemáticas
La biblioteca
La cafetería

#[Now, suppose that there is a 50% chance of a student on campus being at the math department (State 1), a 30% chance of being in the library (State 2), and a 20% chance of being in the cafeteria (State 3) as illustrated in the following diagram:][Ahora, supongamos que hay un 50% de posibilidades de que un estudiante del campus esté en el departamento de matemáticas (Estado 1), un 30% de posibilidades de que esté en la biblioteca (Estado 2) y un 20% de posibilidades de que esté en la cafetería (Estado 3), como se ilustra en el siguiente diagrama.:]#

.5 .3

👤👤👤👤👤 👤👤👤

.2
👤👤

%%Q ¿Cómo podemos esperar que estas probabilidades cambien? después de un paso de tiempo?
%%A #[First, consider what happens at the math department: State 1.][Primero, consideremos qué sucede al departamento de matemáticas: Estado 1]#

Como se muestra en la figura, 50 estudiantes comenzaron allí.De todos los estudiantes del campus, el 50% comienza allí, como se ilustra en la figura. La fracción de ese 50% que podemos esperar que permanezca allí después de un paso es $p_{11}$, por lo que, en promedio, una fracción $.5p_{11}$ del número original, permanecerá en el Estado 1 después de un paso.
Luego, agregamos a eso el porcentaje de estudiantes que esperamos que lleguen desde la biblioteca (estado 2): El 30% que se encuentra actualmente en el estado 2 resulta en una fracción adicional del $.3p_{21}$ que llega desde la biblioteca después de un paso.
Por último, a ese se agrega el porcentaje de estudiantes que esperamos que lleguen desde la cafetería (estado 3). Por último, a eso agreagmos el porcentaje de estudiantes que esperamos que lleguen desde la cafetería (Estado 3): El 20% que actualmente se encuentra en el estado 3 resulta en una fracción adicional del $.2p_{31}$ que llega desde la cafetería después de un paso.

Por lo tanto, la fracción total de estudiantes que podemos esperar encontrar en el Estado 1 después de un paso es

$.5p_{11} + .3p_{21} + .2p_{31}$ #[students][estudiates]#.

#[This quantity may remind you of matrix multiplication: In fact, the above expression is what we get by multiplying the row matrix that represents the initial distribution of students][Esta cantidad puede recordarte a la multiplicación de matrices: De hecho, la expresión anterior es lo que obtenemos al multiplicar la matriz de una fila que representa la distribución inicial de estudiantes.]#

$v ={}$ [.5, .3, .2] \t \gap[40] #[Initial distribution vector][Distribución inicial vector]#

by the first column of $P$:

[p_{11};p_{21};p_{31}]

#[By a similar argument, the expected probability that a student can be found at the library (State 2) after one step is][Mediante un argumento similar, la probabilidad esperado que un estudiante se puede encontrar en la biblioteca (Estado 2) después de un paso es]#

$.5p_{12} + .3p_{22} + .2p_{32}$,

que es igual al producto de $v = [.5,\ \ .3,\ \ .2]$ por la segunda columna de $P$. Finalmente, el número de estudiantes que se pueden encontrar en la cafetería (Estado 3) es el producto de $v$ por la tercera columna de $P$. #[So, when we calculate the product][Por lo tanto, cuando calculamos el produto]#

$vP ={}$[.5, .3, .2][p_{11},p_{12},p_{13};p_{21},p_{22},p_{23};p_{31},p_{32},p_{33}]

#[we get a row matrix whose entries are the probabilities of finding the student in each of the three locations (or states). This row matix is referred to as the expected probability distribution after one step.][Esta matriz se denomina distribución de probabilidad esperada después de un paso.]#

#[Expected distribution after one step = Initial distribution × Transition matrix][Distribución esperada después de un paso = Distribución inicial × Matriz de transición]#

#[Continuing in this way, if we now multiply the resulting row vector by $P$ again, we get the expected probability distribution after two steps:][Continuando de esta manera, si ahora multiplicamos nuevamente el vector de fila resultante por $P$, obtenemos la distribución de probabilidad esperada después de dos pasos:]#

#[Expected distribution after two steps][Distribución esperada después de do pasos]# = $vP \cdot P = vP^2$.

#[In general we have][Por lo general tenemos]#

#[Expected probability distribution after r steps][Distribución de probabilidad esperada después de r pasos]#

#[If][Si]# $v ={}$[v_1, v_2, ..., v_n] #[is the probability distribution of finding a Markov system in one of its $n$ states, then the expected probability distribution of the system after $r$ steps is given by][es la distribución de probabilidad de encontrar un sistema Markov en uno de sus $n$ estados, entonces la distribución de probabilidad esperada del sistema después de $r$ pasos se da por]#

#[Expected probability distribution after $r$ steps][Distribución de probabilidad esperada después de $r$ pasos]# \t ${}= vP^r$.

Dicho de otra manera, la $r$ésima potencia $P^r = P \cdot P \cdot ... \cdot P$ de una matriz de transición $P$ es la matriz de transición de un nuevo sistema Markov que da las probabilidades de ir de un estado a otro en $r$ pasos (en lugar de uno), por lo que pensamos en $P^r$ como representante del sistema Markov de $r$ pasos asociado.

#[Example][Ejemplo]#: #[Weather][Clima]#

#[Let\'s continue with the two-state weather model we looked at before (1 = Sumnny 2 = Cloudy), represented by the following transition matrix:][Continuemos con el modelo meteorológico de dos estados que analizamos antes (1 = Soleado, 2 = Nublado), representado por el siguiente diagrama de transición:]#

[.7,.3;.4,.6].

Si hoy hay un 40% de posibilidades de que esté soleado, entonces estamos especificando la siguiente distribución de probabilidad para el estado actual de nuestro sistema Markov:

[..2,.8]

#[Therefore, the expected weather tomorrow is given by][Por lo tanto, la clima esperada mañana se da por]#

$vP ={}$[..2,.8][.7,.3;.4,.6]

#[and the epected weather in three days\' time is given by][y la clima esperada dentro de tres días se da por]#

$vP^3\ $

\t $ ={}$[.2,.8][.7,.3;.4,.6]^3 \\ \t ${}={}$ [.2,.8][0.583,0.417;0.556,0.444]${}={}$ [0.5614,0.4386]

#[we can calculate $P^3$ using the %%malgtool or the %%marktool.][podemos calcular $P^3$ usando %%malgtool o %%marktool.]#

#[Your turn][Tu turno]#

Ahora prueba algunos de los ejercicios en la Sección 8.7 en el libro Matemáticas finitas y cálculo aplicado. o avanza por pulsar el vínculo "Tutorial siguiente" ubicado a la izquierda.