Markov processes: Basics

Adaptive game version

This tutorial: Part A: Markov processes: Basics

Go to Part B: Regular and absorbing Markov processes

(This topic is also in Section 8.7 in Finite Mathematics and Applied Calculus)

What is an adaptive game tutorial? ▶

%%Note To follow this tutorial, you should know how to set up and multiply matrices as described in the %%maddtut and the %%mtut.

Resources

Matrix algebra tool

Markov system simulation

Markov system computation utility

What is a Markov system?

#[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:]#

Two-state Markov system

Three-state Markov system

#[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.]#

Two-states

#[ 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

Three-states

#[ 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]#

Distribution vectors

Let's take another look at the general three-state system as we saw above, and pretend that this diagram models the flow of student traffic between three locations:

The math department
The library
The cafeteria

#[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 How can we expect these probabilities to change after one time-step?
%%A #[First, consider what happens at the math department: State 1.][Primero, consideremos qué sucede al departamento de matemáticas: Estado 1]#

Of all the students on campus, 50% of them start off there as illustrated in the figure. The fraction of that 50% who we can expect to remain there after one step is $p_{11}$, so on average, a fraction $.5p_{11}$ of the total will remain in State 1 after one step.
Now add to that the fraction of students we expect to arrive there from the library (State 2): The 30% currently in State 2, results in an additional fraction $.3p_{21}$ coming in to State 1 after one step.
Lastly, add to that percentage of students we expect to arrive there from the cafeteria (State 3): The 20% currently in State 3, results in an additional fraction $.2p_{31}$ coming in to State 1 after one step.

Thus, the total fraction of students we can expect to find in State 1 after one step is

$.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}$,

which is equal to the the product of $v = [.5,\ \ .3,\ \ .2]$ with the second column of $P$. Finally, the number who can be found at the cafeteria (State 3) is the product of $v$ with the third column of $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$.

Put another way, the $r$ th power $P^r = P \cdot P \cdot ... \cdot P$ of a transition matrix $P$ is the transition matrix of a new Markov system that gives the probabilities of going from state to state in $r$ steps (instead of one), so we think of $P^r$ as representing the associated $r$-step Markov system.

#[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].

If today there is a 20% chance of if being sunny, then we are specifying the following probability distribution for our Markov system's current state:

[..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]#

Now try some of the exercises in Section 8.7 in Finite Mathematics and Applied Calculus. or move ahead by pressing "Next tutorial" on the sidebar.