Markov chains are a common way of modelling random processes, and they make use of Linear Algebra. We will study the basics and learn to use Sage to do computations with them.
A random variable (in Spanish variable aleatoria) is simply a value that may change every time we observe it. For example, a dice roll.
Let us simulate it with Sage. We will produce random numbers 0,...,5 with probability 1/6 each. Run the next cell several times.
[1/6, 1/6, 1/6, 1/6, 1/6, 1/6] 5 [1/6, 1/6, 1/6, 1/6, 1/6, 1/6] 5 

What is the relation between one result and the next? ¿Qué relación hay entre un resultado y el siguiente? 
Unfortunately, in many reallife situations the result of a random process depends on the previous results. For example, the answer to the question "Will it rain tomorrow?" is related to whether it rained today. But for this purpose Markov chains are very well suited.
A box has 3 white balls and 3 black balls. If we take one out at random, and repeat (up to 6 times of course), does the probability of white/black change? En una caja hay 3 bolas blancas y 3 bolas negras. Si sacamos una al azar y repetimos (hasta 6 veces claro), ¿cambia la probabilidad de blanco/negro? 
A Markov chain consists in:
In this way, a Markov chain can be understood as a random variable that takes as values infinite sequences of states (in Spanish sucesiones infinitas de estados). Each time we observe the chain we see a different infinite sequence.
It can happen that the next state depends only on the one before; or it can happen that it depends on previous states. For example, "Will it rain tomorrow?" depends on what happened during several days (it basically depends on the season, for example). Here we will only work with processes where each state depends only on the previous state.
If it rains one day, does it matter which is the season of the year in order to guess the next day's weather? Si un día llueve, ¿importa la estación a la hora de adivinar si lloverá al día siguiente? 
If I want to guess the next result of a regular dice, does it help to know the previous ones? Para adivinar la siguiente tirada de un dado normal, ¿me ayuda conocer las anteriores? 

Some examples of processes that we can model with Markov chains:

If we want to determine a Markov chain we need to say the states in a certain order, and the probability that one state changes to another one. These values can be written into a transition matrix: each row are the probabilites that a given state becomes any other one.
For example, for the economical situation model, we choose states "Rich", "Middle class" and "Poor" in that order, so the matrix is:
[ 4/5 1/5 0] [1/10 3/5 3/10] [ 0 1/10 9/10] [ 4/5 1/5 0] [1/10 3/5 3/10] [ 0 1/10 9/10] 
Write the transition matrices of two other examples. Escribe las matrices de transición de otros dos ejemplos. 



Any matrix can be a transition matrix, if it satisfies two conditions:
In some of the examples there are one or more states with the property that, once we arrive, we will stay there. They are called absorbing states. When every initial state can reach an absorbing state, the chain itself is called an absorbing chain.
In each example of the list, find the absorbing states. En cada ejemplo de la lista, encuentra los estados absorbentes. 
The absorbing states can be detected in the transition matrix: if the $i$th row has all zeros and a one, and the one is in position $i$, then the $i$th state is absorbing.
Find the absorbing states of the drunk walk, whose matrix is below. Mira los estados absorbentes del paseo del borracho, cuya matriz está debajo. 
[ 1 0 0 0 0 0] [2/3 0 1/3 0 0 0] [ 0 2/3 0 1/3 0 0] [ 0 0 2/3 0 1/3 0] [ 0 0 0 2/3 0 1/3] [ 0 0 0 0 0 1] [ 1 0 0 0 0 0] [2/3 0 1/3 0 0 0] [ 0 2/3 0 1/3 0 0] [ 0 0 2/3 0 1/3 0] [ 0 0 0 2/3 0 1/3] [ 0 0 0 0 0 1] 
The next image is a random graph (like the one described in the list of examples). Find the absorbing states in the image and also looking at its matrix (we will write it in class). La imagen siguiente es un grafo aleatorio (como el de la lista de ejemplos). Encuentra los estados absorbentes en la imagen y luego mirando su matriz (en clase la escribiremos). 


Now we will start using the power of Sage to compute interesting things about Markov chains.
The first thing we can do is the following: choose an initial state at random and simulate a value of the chain. We do this with a loop:
Calculate 10 steps of the drunk walk, supposing that we start in an intermediate position that you choose. Repeat it a few times. Calcula 10 pasos de borracho, suponiendo que empecemos en una posición intermedia que tú elijas. Repítelo varias veces. 


After your experiments, where could we be in 10 steps? Después de tus experimentos, ¿dóne podríamos estar dentro de 10 pasos? 
The last question can be answered in a precise way using the matrix $M$. Suppose that we write a vector with the probabilities of the initial state. For example if we choose a concrete place to start it could be $(0,0,0,1,0,0)$. But if we are not sure of the initial state we could have different probabilites. For example if we could be equally be in two places we would write something like the vector $(0,0,0,1/2,1/2,0)$.
Then: if $v$ is a vector of state probabilities, $v\cdot P$ is the vector of probabilities in the next state.
For example, if we start one block away from the bar:
(0, 0, 0, 2/3, 0, 1/3) (0, 0, 0, 2/3, 0, 1/3) 
If we don't know at all where we are (same probability for each state):
(1/6, 1/6, 1/6, 1/6, 1/6, 1/6) (5/18, 1/9, 1/6, 1/6, 1/18, 2/9) (1/6, 1/6, 1/6, 1/6, 1/6, 1/6) (5/18, 1/9, 1/6, 1/6, 1/18, 2/9) 
If we start next to the bar, where could we be after 2 steps? And 3 steps? Calculate the probabilities. And after 50 steps? Si empezamos al lado del bar, ¿dónde podríamos estar después de 2 pasos? ¿Y 3 pasos? Calcula las probabilidades. ¿Y después de 50 pasos? 



As we can expect, if $P$ gives the probabilities of transitions after one step, $P^n$ gives the probabilities of transitions after $n$ steps.
Calculate $P^{100}$ and interpret the result. It will be easier to work with approximations: apply .n(digits=4) to the result. Calcula $P^{100}$ e interpreta el resultado. Es más fácil aproximando: aplica .n(digits=4) al resultado. 


Let us consider now the example of the Yes/No message that is transmitted from one person to the next. Suppose that with $p=0.99$ it is transmitted correctly. Then, if the states are Yes and No:
[ 0.99 0.010000000000000009] [0.010000000000000009 0.99] [ 0.99 0.010000000000000009] [0.010000000000000009 0.99] 
The probability of each result after 100 steps is read in the rows of:
[ 0.5663097779473767 0.43369022205262364] [0.43369022205262364 0.5663097779473767] [ 0.5663097779473767 0.43369022205262364] [0.43369022205262364 0.5663097779473767] 

You can see that independently of how you started there is a similar probability of receiving Yes or No after 100 steps.If you took more steps, Yes and No would have probabilities of about 50%. Conclusion: it doesn't matter what the initial message was, after many steps the result is nearly the same.
This is a common characteristic of many Markov chains:
Independently of the initial vector $v$, the limit $v\cdot P^n$ when $n\to\infty$ is always the same vector $w$.
(It is not true for every chain but we will not go into details.)
In one of the two examples that you did before, take an initial probability vector and apply a large number of steps, then take other initial vectors to see if you get a similar results. En uno de los dos ejemplos que hiciste antes, toma un vector inicial de probabilidades y aplica un número grande de pasos, después toma otros vectores iniciales para ver si te salen resultados parecidos. 



In the next graph, take several initial vectors and calculate many steps, to see if we get different results. En el grafo siguiente, toma varios vectores iniciales y calcula muchos pasos para ver si obtenemos resultados distintos. 
[0 0 1 0 0 0 0 0] [0 0 1 0 0 0 0 0] [1 1 0 1 0 0 0 0] [1 1 1 0 0 0 0 0] [0 0 0 0 0 1 0 0] [0 0 0 0 1 0 1 1] [0 0 0 0 0 0 0 1] [0 0 0 0 2 0 0 0] [0 0 1 0 0 0 0 0] [0 0 1 0 0 0 0 0] [1 1 0 1 0 0 0 0] [1 1 1 0 0 0 0 0] [0 0 0 0 0 1 0 0] [0 0 0 0 1 0 1 1] [0 0 0 0 0 0 0 1] [0 0 0 0 2 0 0 0] 

An important property of the limit vector $w$ is that it satisfies $w=w\cdot P$. So:
The vector $w$ is an eigenvector (in Spanish, autovector o vector propio) of the matrix $P$ for the eigenvalue 1.
With Sage:
[ 0.99 0.010000000000000009] [0.010000000000000009 0.99] [1.0, 0.98] [ 0.99 0.010000000000000009] [0.010000000000000009 0.99] [1.0, 0.98] 
[(1.0, [(0.7071067811865475, 0.7071067811865475)], 1), (0.98, [(0.7071067811865475, 0.7071067811865475)], 1)] [(1.0, [(0.7071067811865475, 0.7071067811865475)], 1), (0.98, [(0.7071067811865475, 0.7071067811865475)], 1)] 
(0.7071067811865475, 0.7071067811865475) (0.7071067811865475, 0.7071067811865475) 
(0.5, 0.5) (0.5, 0.5) 

In summary, we can, for any Markov chain:
Choose another example of the list and do (1) a simulation, (2) calculate the probability from some state to another state in three steps, (3) the limit probabilities. Elige otro ejemplo de la lista y haz (1) una simulación, (2) calcula la probabilidad entre dos estados concretos tras tres pasos, (3) las probabilidades límite. 





Now we will concentrate on absorbing chains.
Intuitively, in the drunk walk example we already expected that we will always end at home or at the bar, if we walk long enough. This can be checked experimentally as before. It is also the content of one of the main theorems on absorbing chains:
Theorem: If a Markov chain is absorbing, the probability of eventually reaching an absorbing state is 1.
So, it may take a long time, but we should not expect to escape forever.
We can ask some other questions:
We will work on these questions now. For this we need to do more things with the matrix $P$.
Since we can put the states in any order, suppose that we put all the absorbing states in the beginning. How would the matrix look like? It would have blocks like this:
\[ P=\left(\begin{array}{cc} I & 0 \\\hline R & Q \end{array}\right) \]
The topleft is an identity matrix, because the first states are absorbing so they go to themselves with probability 1. The topright is zero because the absorbing states never go to other states. The two bottom blocks are arbitrary. Note that if $R$ is zero, then the nonabsorbing states cannot reach the absorbing ones, so we would not have an absorbing chain (the condition was that every state could reach an absorbing state after some steps).
In our example, we rearrange $P$:
[ 1 0 0 0 0 0] [ 0 1 0 0 0 0] [2/3 0 0 1/3 0 0] [ 0 0 2/3 0 1/3 0] [ 0 0 0 2/3 0 1/3] [ 0 1/3 0 0 2/3 0] [ 1 0 0 0 0 0] [ 0 1 0 0 0 0] [2/3 0 0 1/3 0 0] [ 0 0 2/3 0 1/3 0] [ 0 0 0 2/3 0 1/3] [ 0 1/3 0 0 2/3 0] 
The submatrix $Q$ is important.
[ 0 1/3 0 0] [2/3 0 1/3 0] [ 0 2/3 0 1/3] [ 0 0 2/3 0] [ 0 1/3 0 0] [2/3 0 1/3 0] [ 0 2/3 0 1/3] [ 0 0 2/3 0] 
$Q^n$ contains the probabilities between the nonabsorbing states after $n$ steps. We can see that as $n$ becomes large the probabilities become small, because it is more and more probable to reach an absorbing state. In fact, $Q^n \to 0$.
[4.783e13 0.0000 3.869e13 0.0000] [ 0.0000 1.252e12 0.0000 3.869e13] [1.548e12 0.0000 1.252e12 0.0000] [ 0.0000 1.548e12 0.0000 4.783e13] [4.783e13 0.0000 3.869e13 0.0000] [ 0.0000 1.252e12 0.0000 3.869e13] [1.548e12 0.0000 1.252e12 0.0000] [ 0.0000 1.548e12 0.0000 4.783e13] [4.783e13 0.0000 3.869e13 0.0000] [ 0.0000 1.252e12 0.0000 3.869e13] [1.548e12 0.0000 1.252e12 0.0000] [ 0.0000 1.548e12 0.0000 4.783e13] [4.783e13 0.0000 3.869e13 0.0000] [ 0.0000 1.252e12 0.0000 3.869e13] [1.548e12 0.0000 1.252e12 0.0000] [ 0.0000 1.548e12 0.0000 4.783e13] 
Now we define the fundamental matrix:
\[ N=(IQ)^{1} \]
It answers the first question, "how many times will we visit each state before ending in an absorbing state?". The row indicates the initial state, the column indicates the state that we want to visit, and the value in that position is the average number of times that we will visit before we fall into an absorbing state.
Below is $N$ for our example. What is the meaning of $N[3,2]$? Debajo está la $N$ de nuestro ejemplo. ¿Qué significa $N[3,2]$? 
[45/31 21/31 9/31 3/31] [42/31 63/31 27/31 9/31] [36/31 54/31 63/31 21/31] [24/31 36/31 42/31 45/31] 42/31 [45/31 21/31 9/31 3/31] [42/31 63/31 27/31 9/31] [36/31 54/31 63/31 21/31] [24/31 36/31 42/31 45/31] 42/31 
Next question: how many steps until we reach an absorbing state?
Consider $N$ again. We just saw that if we choose an initial state (a row of $N$), the elements of the row are the number of visits to the other nonabsorbing states. From this we have:
Theorem: the column vector $N\cdot\left(\begin{array}{c} 1 \\ \vdots \\ 1 \\ \end{array} \right)$ contins the average number of steps until the end, from the different initial states.
Why is it true? Think of what hapens when you multiply a row of $N$ by the column of ones. ¿Por qué es así? Piensa en lo que pasa cuando multiplicas una fila de $N$ por la columna de unos. 
[ 78/31] [141/31] [174/31] [147/31] [2.516] [4.548] [5.613] [4.742] [ 78/31] [141/31] [174/31] [147/31] [2.516] [4.548] [5.613] [4.742] 
The first row means that it takes about two and a half steps to finish the walk if you start next to home. The last one means that it takes almost five if you start next to the bar.
For the last question, "If there is more than one absorbing state, what is the probability of ending at each one?", the answer is in the matrix $NR$. Again, each row indicates an initial state (nonabsorbing), and it contains the probabilities of ending at each absorbing state.
[2/3 0] [ 0 0] [ 0 0] [ 0 1/3] [2/3 0] [ 0 0] [ 0 0] [ 0 1/3] 
[30/31 1/31] [28/31 3/31] [24/31 7/31] [16/31 15/31] [30/31 1/31] [28/31 3/31] [24/31 7/31] [16/31 15/31] 
For example, the first row means: if you start at distance 1 from home, then almost surely you will end at home. The last row means: if you start next to the bar, it is almost 5050 that you go home or to the bar.
Generate a random graph that has at least one absorbing state. Answer the three questions that we learned about absorbing chains. Genera un grafo aleatorio que tenga algún estado absorbente. Responde las tres preguntas que hemos aprendido sobre cadenas absorbentes. 




We will model a known board game in order to practice what we have learned and interpret the results.











