Markov chain transition probability written in Python

1.First of all

I will write an article about transition probabilities of Markov chains.

Specifically, I will introduce a function that obtains the transition probability from time series data and creates a matrix. Note that this is not an introduction to a function that deals with the transition probability matrix of Markov chains.

I will write detailed information from "2. What is a Markov chain?" If you want to know only the code, I think it is enough to refer to "3. Function to find the transition probability".

2. What is a Markov chain?

2.1. Definition of transition probability

Below is the definition of Markov chains in Wikipedia.

If the current state is determined by a series of random variables X1, X2, X3, ..., the past and future states are independent.

Source: https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%80%A3%E9% 8E% 96

2.2. Markov chain transition probability equation

The following is a Markov chain formula written on Wikipedia.

Pr(X_{n+1}=x | X_n=x_n,..., X_1=x_1,X_0=x_0) = Pr(X_{n+1}=x_{n+1} | X_n=x_n)

The possible values of> Xi are called the state space of the chain and form a countable set S. The Markov chain is represented by a directed graph, and the edge shows the probability of transition from one state to another.

An example of a Markov chain is a finite state machine. This means that if we are in state y at time n, the probability that it will move to state x at time n + 1 depends only on the current state, not on time n.

Source: https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%80%A3%E9% 8E% 96

The probability expressed by the following formula is called the transition probability.

Pr(X_{n+1}| X_n)

Source: https://mathtrain.jp/markovchain

2.3. Specific example

You actually find the transition probability, but I think it's hard to imagine just the definitions and expressions. Let's take the weather as an example.

• S * = {Sunny = 0, Cloudy = 1, Rain = 2} for one month of weather information.

tenki = np.array([0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1])
print('Sunny days:{0}Day, 曇のDay数:{1}Day, 雨のDay数:{2}Day'.format(np.count_nonzero(data==0), np.count_nonzero(data==1), np.count_nonzero(data==2))))

output

Sunny days:The 20th,Cloudy days:The 8th,Rainy days:Day 2

Looking at the above, you can see at a glance that sunny weather is the most, followed by cloudy weather and rain. However, the purpose is "how the weather has changed".

Therefore, I want a matrix with the transition probability known (Fig. 1), but I can't find it by searching.

So, let's create a function.

3. Function to find the transition probability

3.1. Python version / environment

I'm using Python 3.7.1. The usage environment is Jupyter notebook.

3.2. Creating a function

3.2.1 Import of required libraries

import numpy as np
import copy
import itertools
import seaborn as sns

seaborn does not have to be included functionally, but it is included because it will be visualized later.

3.2.2 Data

This time, I will use tenki.

3.2.3 Functions and their explanations

def tp(transition_probability):
    
    data = transition_probability
    zero = np.zeros((np.max(data)+1,np.max(data)+1))

    for i in range(len(data)-1):
        j = copy.deepcopy(i)
        j += 1
        for x, y in itertools.product(range(np.max(data)+1), range(np.max(data)+1)):
            if data[i] == x and data[j] == y:
                zero[x][y] += 1
    
    row_sum = np.sum(zero, axis=1).reshape((np.max(data)+1,1))
    prob    = zero / row_sum
    
    return prob

• zero --There are three pieces of information used in tenki, "0-2". --Therefore, if you take "np.max (data) +1", you can create a zero matrix with maximum value * maximum value. -(We can handle 3 or more or less.) 　 --Processing in for --"I, j" stands for Xn * and * Xn + 1 *, respectively. ―― “X, y” represents the column and row of the variable “zero” respectively. --By the processing in for, a concrete combination is entered in the variable "zero".

• row_sum --The variable "zero" is the count data. --The total count is given for each row.

• prob --Dividing the sum of each row and each individual value of each row.

3.2.3 Results

Now you have a matrix of transition probabilities.

print(tp(data))

output

[[0.65       0.25       0.1       ]
 [0.57142857 0.42857143 0.        ]
 [1.         0.         0.        ]]

3.2.4 Visualization

This alone is a little sad, so let's visualize it.

sns.heatmap(tp(data), cmap='Blues', vmin=0, vmax=1, center=.5,
            square=True, cbar_kws={"shrink": .5},
            xticklabels = 1, yticklabels = 1)

In this heatmap, the left axis represents * Xn * and the bottom axis represents * Xn + 1 *.

4. Finally

I wrote a function about the transition probability of a Markov chain, but how was it? I would appreciate it if you could point out any points that are difficult to understand or incorrect.

Reference URL

・ Markov chain (Wikipedia) https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%80%A3%E9%8E%96

・ The basics of Markov chains and the Kolmogorov equation (a beautiful story of high school mathematics) https://mathtrain.jp/markovchain