Has it ever crossed your mind how expert meteorologists make a precise prediction of the weather or how Google ranks different web pages? How they make the fascinating python applications in real world. These calculations are complex and involve several variables that are dynamic and can be solved using probability estimates.
When Google introduced its PageRank algorithm, it revolutionized the web industry. And if you’re familiar with that algorithm, you must also know that it uses Markov chains. In our introduction to Markov chains, we’ll take a brief look at them and understand what they are. So, let’s get started.
It’s essential to know a few concepts before we start discussing Markov chains. And most of them are from probability theory. Non-mathematically, you can define a random variable’s value as the result of a random event. So, for example, if the variable were the result of rolling a die, it would be a number whereas if it were a result of a coin flip, it would be a boolean (0 or 1). The set of these possible results could be continuous as well as discrete.
So we can say that a stochastic process is a collection of random variables that set indexes. That set represents different time instances. This set could be of real numbers (continuous process) or natural numbers (discrete process).
Introduction to Markov Chains
Markov chains get their name from Andrey Markov, who had brought up this concept for the first time in 1906. Markov chains refer to stochastic processes that contain random variables, and those variables transition from a state to another according to probability rules and assumptions.
What are those probabilistic rules and assumptions, you ask? Those are called Markov Properties. Learn more about Markov Chain in Python Tutorial
What is the Markov Property?
There are plenty of groups of random processes, such as autoregressive models and Gaussian processes. Markov property makes the study of these random processes quite easier. A Markov property states that we wouldn’t get more information about the future outcomes of a process by increasing our knowledge about its past if we know its value at a particular time.
A more elaborate definition would be: Markov property says that the probability of a stochastic process only depends on its current state and time, and it is independent of the other states it had before. That’s why it’s a memoryless property as it only depends on the present state of the process.
A homogeneous discrete-time Markov chain is a Marko process that has discrete state space and time. We can say that a Markov chain is a discrete series of states, and it possesses the Markov property.
Here’s the mathematical representation of a Markov chain:
X = (Xn)nN=(X0, X1, X2, …)
Properties of Markov Chains
Let’s take a look at the fundamental features of Markov chains to understand them better. We won’t delve too deep on this topic as the purpose of this article is to make you familiar with the general concept of Markov chains.
Markov chains are irreducible. That means they have no reducibility if it can reach any state from another state. The chain doesn’t need to reach one state from another in just a single time step; it can do so in multiple time steps. If we can represent the chain with a graph, then the graph would be firmly connected.
Let’s say a state’s period is k. If k = 1, then this state is aperiodic when any kind of return to its state requires some multiple of k time-steps. When all states of a Markov chain are aperiodic, then we can say that the Markov chain is aperiodic.
Transient and Recurrent States
When you leave a state, and there’s a probability that you can’t return to it, we say that the state is transient. On the other hand, if we can return to a state with probability 1, after we have left it, we can say that the property is recurrent.
There are two kinds of recurrent states we can have. The first one is the positive recurrent state that has a finite expected return time, and the second one is the null recurrent state that has an infinite expected return time. Expected return time refers to the mean recurrence time when we are leaving the state.
Applications of Markov Chains
Markov chains find applications in many areas. Here are their prominent applications:
- Google’s PageRank algorithm treats the web like a Markov model. You can say that all the web pages are states, and the links between them are transitions possessing specific probabilities. In other words, we can say that no matter what you’re searching on Google, there’s a finite probability of you ending up on a particular web page.
- If you use Gmail, you must’ve noticed their Auto-fill feature. This feature automatically predicts your sentences to help you write emails quickly. Markov chains help in this sector considerably as they can provide predictions of this sort effectively.
- Have you heard of Reddit? It’s a significant social-media platform that’s filled with subreddits (a name for communities in Reddit) of specific topics. Reddit uses Markov chains and models to simulate subreddits for a better understanding of the same.
It appears we have reached the end of our introduction to Markov chains. We hope you found this article useful. If you have any questions or queries, feel free to share them with us through the comments. We’d love to hear from you.
If you want to learn more about this topic, you should head to our courses section. You’ll find plenty of valuable resources there.
If you are curious to learn about data science, check out IIIT-B & upGrad’s PG Diploma in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.