I know it can have something to do with machine learning and it works as a good method of predicting, but it seems really complicated. Is there a simpler explanation that I can use as a booster?
In: 1
[deleted]
A markov chain is a specific type of random behavior. The system has multiple different “states,” and it can only exist in one state at a time. Every time interval, the system has a chance of changing states. Most importantly, the probability of changing states is only dependent on the current state, it isn’t modified by whatever states the system might have had in the past.
Edit: see other comments. My description is for first-order Markov chains, and higher-order Markov systems exist where the probability of a state change *is* modified by a few previous states in addition to the current state.
A Markov chain is first and foremost a way of **representing** systems. And if a system can be written as a Markov chain (not every system can), then this system will be reasonably easy to predict (thanks to a ton of powerful results on matrices).
The first step of using a Markov chain is to identify the possible **states** of the system. For example, if you’re playing snakes and ladders alone (fun, right?), then the state is simply the position of your token on the board (so a number between 1 and 100, since the board has 100 squares).
The second step is to identify the **transitions** and their probability:
* If you’re on the last square, you remain there as you won.
* If you’re at the bottom of a ladder, you climb the ladder with probability 1.
* If you’re at the top of a snake, you slide down the snake with probability 1.
* Otherwise, you roll two dices and advance by that many square. So with probability 2.8%, you advance by 2 squares, with probability 5.6% you advance by 3 squares, with probability 8.3% you advance by 4 squares, etc.
Markov chain only works if you can assign probabilities to every transition. So they’re good at representing a game like snake and ladders where nobody takes any decision, or at representing how a more complex game would unfold if everyone use a specific well-known strategy. (You need Hidden Markov Models for some more advances cases, but I don’t know much on them)
Then, how to use this Markov chain? You write a matrix 100×100 (because there are 100 states), on the column N row M you put the probability that you go from square N to square M. Then you use some clever maths (like eigen values) to deduce some properties.
In our specific case, and with most board of snakes and ladders, the main result will be that you will eventually win the game of snake and ladder, and that the probability that you remain indefinitely in a loop of snakes and ladders is zero.
(And you could probably use some other theorems to compute the average number of turns you need to win depending on the board)
Latest Answers