- Markov Chains in Python: Beginner Tutorial
- Sejal Jaiswal
- The Nuggets translation Project
- Permanent link to this article: github.com/xitu/gold-m…
- Translator: cdpath
- Proofread by jianboy, Kasheem Lew
Learn about Markov chains and their properties, learn about transition matrices, and implement them in Python!
A Markov chain is a mathematical system usually defined in terms of a set of random variables that can transfer states according to specific probabilistic rules. The set of transitions satisfies the Markov property, that is, the probability of transition to any particular state depends only on the current state and the elapsed time, and is independent of the previous state sequence. This unique property of markov chains is memorylessness.
Learn to use Markov chains with this tutorial and you will understand what discrete time Markov chains are. You will also learn the components needed to build a (discrete time) Markov chain model and its common features. Next, learn to implement a simple model using Python and its Numpy and Random libraries. You will also learn to represent Markov chains in various ways, such as state diagrams and transition matrices.
Want to handle more statistics in Python? Learn about DataCamp’s Python Thinking in Statistics course!
Let’s go…
Why the Markov chain?
Markov chains are widely used in mathematics. It is also widely used in economics, game theory, communication principles, genetics and finance. Often seen in the context of statistics, especially Bayesian statistics, and information theory. In reality, Markov chain provides solutions to problems such as cruise control system of motor vehicles, queuing sequence of passengers arriving at the airport and currency exchange rate. PageRank, first proposed by Google search engine, is based on markov process algorithm. Reddit has a subreddit called subreddit Simulator where posts and comments are automatically generated using markov chains. Cool!
Markov chain
Markov chains are stochastic processes with Markov properties. A random process or having random properties is a mathematical object defined by a set of random variables. There are many variations of Markov chains, given that they have either a discrete state space (a set of possible values of random variables) or a set of discrete indexes (usually representing time). And usually said “Markov chain” refers to the process with discrete time set, namely discrete time Markov chain (DTMC).
Discrete time Markov chains
Discrete time Markov chains contain systems in which each step is in a certain state, and the states between the steps vary randomly. These steps are often compared to moments in time (though you can think of them as physical distance or any discrete measure). Discrete time Markov chains are random variables X1, X2, X3… , but to satisfy the Markov property, so the transition to the next probability is only related to the current state, not the previous state. It is expressed by probability mathematical formula as follows:
Pr (Xn + 1 = x | X1 = X1, X2 = X2,… , Xn = xn) = Pr( Xn+1 = x | Xn = xn)
So the probability of Xn plus 1 only depends on the probability of Xn before. Therefore, the probability distribution of the current state can be determined only by knowing the previous state, which satisfies the condition independence (in other words, the next state can be determined only by knowing the current state).
The countable set S of possible values of Xi is called the markov chain state space. The state space can be anything: letters, numbers, basketball scores or weather conditions. Although the time parameters are usually discrete, the state space of discrete time Markov chains has no widely used constraints, and it is better to refer to the process in any state space. However, many applications of Markov chains use the simpler finite or countably infinite state space for statistical analysis.
model
Markov chains are represented by probabilistic automata (trust me it’s not as complicated as it sounds!). . A change in system state is called a transition. The probability of each state changing is called transition probability. Probabilistic automata consists of converting probabilities from known to transfer equations into transfer matrices.
Can also be markov chain as a directed graph, the figure is the edge of n labeled n moment is transferred to the n + 1 time state probability of Pr (Xn + 1 = x | Xn = Xn). This is read as the probability of going from a given state Xn to a given state Xn plus 1. This concept can also be represented by a transition matrix from time n to time n+1. Each state in the state space appears first as a row in the transition matrix and second as a column. Each element of the matrix represents the probability of moving from the state represented by this row to the column state.
If the Markov chain has N states, the transition matrix is N x N dimensional, where (I, J) represents the probability of moving from state I to state J. In addition, the transition matrix must be a probability matrix, that is, the sum of the elements in each row must be 1. Why is that? Because each row represents its own probability distribution.
So the main features of the model include: state space, transition matrix which describes the probability of a particular transition and the initial state of the state space given by the initial distribution.
Seems complicated?
Let’s look at a simple example to help understand these concepts:
If Cj is in a bad mood, she goes for a run, goobles on ice cream, or takes a nap to adjust.
Based on past data, if she takes a nap to refresh herself, she is 60 percent more likely to go for a run the next day, 20 percent more likely to stay in bed, and 20 percent more likely to eat a large portion of ice cream.
If she ran for relaxation, she was 60 percent more likely to run the next day, 30 percent more likely to eat ice cream, and only 10 percent more likely to go to bed.
Finally, if she indulged in ice cream when upset, she was only 10 percent more likely to eat ice cream the next day, 70 percent more likely to run, and 20 percent more likely to sleep.
The Markov chain represented by the state diagram above has three possible states: sleep, running, and ice cream. So the transition matrix is a 3 by 3 matrix. Note that the sum of the values of the arrows leaving a certain state must be 1, just as the sum of the elements in each row of the state matrix is 1, indicating a probability distribution. Each element in the transition matrix has a meaning similar to each state in the state diagram.
This example should help you understand several different concepts related to Markov chains. But how does this apply in the real world?
Using this example, you should be able to answer the question, “What is the probability that Cj will end up running after 2 days from sleep?”
So let’s do that. 12. To move from sleep to running, Cj has the following options: Sleep the first day and run the next (0.2 ⋅ 0.6); 12. Change to running the first day and continue running the next (0.6 Ice cream on the first day and running on the second. Counting down the probability is: (⋅ (0.2 0.6) + ⋅ (0.6 0.6), (0.7) 0.2 ⋅) = 0.62. So there’s a 62% chance that Cj will be running after 2 days from sleep.
Hopefully this example will show you what problems can be solved by markov chain networks.
At the same time, several important properties of Markov chains can be better understood:
- Interoperability: A Markov chain is irreducible if it can be transferred from any state to any state. In other words, if the probability of a sequence of steps between any two states is positive, it is irreducible.
- Periodic: The state of a Markov chain is periodic if it returns a state only if it is a multiple of an integer greater than 1. Thus, starting from state “I”, “k” can return to “I” only after an integer multiple of cycles, where k is the maximum of all integers satisfying the condition. If k = 1, the state “I” is not periodic, and if k > 1, “I” is periodic.
- Transient and recurrent: State “I” is transient if it is possible to start from state “I” and not return to state “I”. Otherwise, it is recurrent (or persistent). If a state can be repeated in a finite number of steps, it is recurrent, otherwise it is not.
- Ergodicity: State “I” has ergodicity if it satisfies aperiodic and positive recurrence. If every state of a non-reducible Markov chain is ergodic, then the Markov chain is ergodic as well.
- Absorption state: If it is impossible to move from state “I” to another state, “I” is in absorption state. Therefore, if pii = 1 and PIj = 0 when I ≠ j, state “I” is in the absorption state. If every state of a Markov chain can reach an absorptive state, it is called a Markov chain with absorptive states.
Tip: Check out this website for a visual explanation of markov chains.
Implement Markov chains in Python
Let’s use Python to implement the above example. Of course, the actual use of the library implementation of markov chain will be much more efficient, here is the example code to help you get started…
Import the libraries used first.
import numpy as np
import random as rm
Copy the codeThen we define the states and their probabilities, the transition matrix. Remember, because there are three states, the matrix is 3 X 3. You also need to define the transition path, which can also be represented by a matrix.
# state space
states = ["Sleep"."Icecream"."Run"]
# Possible sequence of events
transitionName = [["SS"."SR"."SI"], ["RS"."RR"."RI"], ["IS"."IR"."II"]]
# Probability matrix (transition matrix)
transitionMatrix = [[0.2.0.6.0.2], [0.1.0.6.0.3], [0.2.0.7.0.1]]
Copy the codeRemember, make sure the sum of the probabilities is 1. And there’s nothing wrong with printing more error messages when writing code!
if sum(transitionMatrix[0])+sum(transitionMatrix[1])+sum(transitionMatrix[1]) != 3:
print("Somewhere, something went wrong. Transition matrix, perhaps?")
else: print("All is gonna be okay, you should move on!! ;) ")
Copy the codeAll is gonna be okay, you should move on!! ;)
Copy the codeNow it’s time to get down to business. We use numpy.random. Choice to select a random sample from the set of possible transitions. The meaning of most of the parameters in the code is obvious from their names, but parameter p can be confusing. It is an optional parameter that can be passed in the probability distribution of the sample set, in this case the transition matrix.
# Implements functions of markov models that can predict states.
def activity_forecast(days):
Select the initial state
activityToday = "Sleep"
print("Start state: " + activityToday)
The selected sequence of states should be recorded. I only have the initial state here.
activityList = [activityToday]
i = 0
# Calculate the probability of activityList
prob = 1
whilei ! = days:if activityToday == "Sleep":
change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
if change == "SS":
prob = prob * 0.2
activityList.append("Sleep")
pass
elif change == "SR":
prob = prob * 0.6
activityToday = "Run"
activityList.append("Run")
else:
prob = prob * 0.2
activityToday = "Icecream"
activityList.append("Icecream")
elif activityToday == "Run":
change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
if change == "RR":
prob = prob * 0.5
activityList.append("Run")
pass
elif change == "RS":
prob = prob * 0.2
activityToday = "Sleep"
activityList.append("Sleep")
else:
prob = prob * 0.3
activityToday = "Icecream"
activityList.append("Icecream")
elif activityToday == "Icecream":
change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
if change == "II":
prob = prob * 0.1
activityList.append("Icecream")
pass
elif change == "IS":
prob = prob * 0.2
activityToday = "Sleep"
activityList.append("Sleep")
else:
prob = prob * 0.7
activityToday = "Run"
activityList.append("Run")
i += 1
print("Possible states: " + str(activityList))
print("End state after "+ str(days) + " days: " + activityToday)
print("Probability of the possible sequence of states: " + str(prob))
# Predict the likely state after 2 days
activity_forecast(2)
Copy the codeStart state: Sleep
Possible states: ['Sleep'.'Sleep'.'Run']
End state after 2 days: Run
Probability of the possible sequence of states: 0.12
Copy the codeAs a result, the possible transition from sleep state and its probability can be obtained. Extending the function further allows it to start in the sleeping state and iterate hundreds of times to get the expected probability of ending in a particular state. Let’s rewrite the Activity_forecast function and add some loops…
def activity_forecast(days):
Select the initial state
activityToday = "Sleep"
activityList = [activityToday]
i = 0
prob = 1
whilei ! = days:if activityToday == "Sleep":
change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
if change == "SS":
prob = prob * 0.2
activityList.append("Sleep")
pass
elif change == "SR":
prob = prob * 0.6
activityToday = "Run"
activityList.append("Run")
else:
prob = prob * 0.2
activityToday = "Icecream"
activityList.append("Icecream")
elif activityToday == "Run":
change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
if change == "RR":
prob = prob * 0.5
activityList.append("Run")
pass
elif change == "RS":
prob = prob * 0.2
activityToday = "Sleep"
activityList.append("Sleep")
else:
prob = prob * 0.3
activityToday = "Icecream"
activityList.append("Icecream")
elif activityToday == "Icecream":
change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
if change == "II":
prob = prob * 0.1
activityList.append("Icecream")
pass
elif change == "IS":
prob = prob * 0.2
activityToday = "Sleep"
activityList.append("Sleep")
else:
prob = prob * 0.7
activityToday = "Run"
activityList.append("Run")
i += 1
return activityList
Record each activityList
list_activity = []
count = 0
# 'range' counting from the first argument to the second argument (not included)
for iterations in range(1.10000):
list_activity.append(activity_forecast(2))
View all recorded 'activityList'
#print(list_activity)
Walk through the list to get all the activityLists whose final state is running
for smaller_list in list_activity:
if(smaller_list[2] = ="Run"):
count += 1
# Calculate the probability of starting your sleep state and ending your running state
percentage = (count/10000) * 100
print("The probability of starting at state:'Sleep' and ending at state:'Run'= " + str(percentage) + "%")
Copy the codeThe probability of starting at state:'Sleep' and ending at state:'Run'= 62.419999999999995%
Copy the codeSo the question is, why is this going to be 62%?
Notice that this is actually the law of large numbers in action. The law of large numbers is a law of probability theory that states that events with the same probability tend to occur with the same frequency over a sufficient number of trials. That is, as the number of trials increases, the actual ratio tends to the theoretical or predicted probability.
Markov thinking
So much for the Markov chain tutorial. This paper introduces markov chains and their properties. Simple Markov chains are the way to start learning Python data science. For more Python statistics resources, see this site.
If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.
The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.