Markov Chain

Markov chain often appears in the concept of machine learning, because many situations in life can be modeled with Markov chain, we first give the mathematical definition, and then take a life-oriented example corresponding to mathematical formula, we can understand the Markov chain.

Ps: You can first look at the example of life, and then look at the mathematical formula, it is easier to understand

Mathematical definition

A Markov chain is a set of discrete random variables. In particular, given a random variable X = {Xn: n > 0} X = \ {X_n: n > 0 \} X = {Xn: n > 0}, if values are within a countable set of random variables X = si, si ∈ X = s_ {I}, s_ {I} \ in sX = si, si ∈ s: p (Xt + 1 ∣ Xt,… , the X1) = p + 1 ∣ Xt (Xt) p \ left (X_ {t + 1} \ mid X_ {t}, \ ldots, X_ {1} \ right) = p \ left (X_ {t + 1} \ mid X_ {t} \ right) p (Xt + 1 ∣ Xt,… ,X1)=p(Xt+1∣Xt) XXX is called Markov chains, countable set S ∈Zs \in Zs∈Z is called state space, the value of Markov chains in the state space is called states.

The above equation defines the Markov property along with the Markov chain. This property is also referred to as “memorylessness”. The random variables at t+1 step are given t step random variables conditionally independent from the rest of the random variables.

Life example 1

A common example of a Markov chain is a simplified model of a stock going up or down: if a stock goes up one day, then the next day it has a probability that P will start to fall and 1-P will continue to rise. If the stock falls during the day, then the stock has the probability that q will start to rise tomorrow and 1-Q will continue to fall. Then, the rise and fall of the stock is a Markov chain, and the corresponding concepts in the mathematical definition are as follows:

Markov chain is a random process. In this example, the ups and downs of stocks in a certain period can be defined as markov chain.

  • Random variable X: the state of the stock on day t; State space S: “up” and “down”; Index set: days.
  • Conditional probability relationship: By definition, even if all the historical states of a stock are known, its movements on a given day are only related to the previous day’s state.
  • No memory: The stock’s performance on the day is related only to the previous day, independent of other historical states (no memory is defined along with the conditional probability relationship).

Life example 2

First talk about our village IQ is 0 wang Ergou, silly people do not pull a few, see people giggle, 12 o ‘clock every day standard match, three states: eat, play, sleep. This is the legendary distribution of states, in other words, the formula
s i s_i There are only three values: eat, play and sleep.You want to know what his state will be at 12 o ‘clock in n daysX)? Is it eating, or playing, or sleeping? What are the probabilities of each of these states? You know you don’t, just pretend you doStudying is really tiring)

So let’s start with a hypothesis, where each state is given a probability, like what’s the probability that he plays today, that he sleeps tomorrow, what’s the probability that he plays today, that he plays tomorrow, just to make it a little bit clearer.This matrix isThe transition probability matrix PAnd it stays constant, that is, from day one to day twoTransition probability matrixIt’s the same transition probability matrix from day two to day three. So given this matrix, and assuming we know his state distribution on day one, we can figure out his state distribution on day NTH.

S1 is the state distribution matrix [0.6, 0.2, 0.2] at 12:00 noon on April 1, in which the numbers represent the probability of eating, playing, and sleeping respectively. then

On April 2, the state distribution matrix S2 = S1 * P.

The state distribution matrix S3 on April 3 is S2 * P (see, it doesn’t depend on S1, only on S2).

On April 4, the state distribution matrix S4 = S3 * P (see, not related to S1, S2, only S3).

.

The state distribution matrix of April n is Sn = sn-1 * P (see, it only depends on the previous state sn-1).

Think of the picture below as a Markov chain. It’s essentially a process in which a random variable changes over time in accordance with markov properties.

Additional: S2 calculation process (not interested students skip), probability theory of addition principle

What the hell is markov chain? – Zhihu Markov Chain – Baidu Baike