Markov Chain
Markov chain is a relatively simple concept in the field of random processes. We can think of a random process as a collection of random variables indexed by times. For a simple example, we can consider a series of coin tossing as a random process. Each of the tossings is a Bernoulli random variable (can get one of two states), and we can index them according to the order of tossing.
In general, the result of the random variable X(n+1) may be depended on the previous results {X(0), …, X(n)}
but in some cases, P(X(n+1)) is only depended on the previous state, P(X(n)), and not on the whole history
This property is called Markov property. The property says that the future state (X(n+1)) is only dependent on the current state (X(n)) and not on the past states. A (discrete) random process that satisfies the Markov property at any time is called a Markov chain.
Accordingly, we can describe a Markov chain as a states machine — we have several states (possible results of the random process) and some transition probability of moving from one state to another. For example, let’s think of a casino machine that can output three numbers {1,2,3} as in the following diagram:
The arrows represent the probability of transition from state to state. Since this is a Markov chain, the probability of moving to a certain state is only dependent on the current state. For example, if now the casino machine is showing the number 1, the probability of getting 2 in the next round is 0.6. Pay attention that since we deal with probability, the sum of the weights of all the arrows go from a certain state must be equal to 1.
The above diagram can be represented using a matrix P which is called the transition matrix. Each row in the matrix describes the probability of transition to the other states (the arrows in the diagram). In our case, the transition matrix is
You can again see that the sum of each row is 1. The entry (i, j) is the transition probability from state i to state j. Suppose now we are in state 1. We can write it as a state vector π = (1, 0, 0), and by multiplying it with the transition matrix, we get the probabilities of the next state
That means, if we know we are in state 1, in the next round, we have probabilities of 0.2, 0.6, and 0.2 to be at state 1, 2, or 3, respectively.
What about the next state? Again, we can take our new probability state vector and multiply it by the transition matrix to get the probabilities after two rounds when we start with the state of 1. We can go on as many time as we want.
From the above example, we can see that if we start from a known state π, we can know what are the probabilities of the different states after m rounds simply by multiplying π with P at the power of m.
Stationary State
In some cases, after a lot of rounds, the probability of the states will be constant. If that constant probability state vector is π, it must be that:
This equation is an eigenvector equation with an eigenvalue of 1. We can solve this equation together with the fact that the sum of π must be 1 (as a probability vector) to find the stationary state.
In our example, we can solve and see that π = (0.3521, 0.2112, 0.4366) (try to multiply it with the transition matrix).
Past Forgetness
Generally speaking, the stationary state of a Markov chain depends on the initial state. Let’s consider the following diagram:
We can see that if our initial state is 1, we can’t move to any other state, so after each step, we still be in state 1. The same is true for state 4. If we start from state 2 or 3, we may end in state 1 or state 4. But there are cases where the initial state does not matter.
We say that a Markov chain forgets the past if, after infinite steps, the probability of moving to state j does not depend on the initial condition.
If so, there is a probability state vector π(∞), such as
so π(∞) is a stationary state. Since there is no dependent on the starting state π(0), and the limit should exist (and be the same) for any π(0), we can look on the standard basis eᵢ = (0, 0, …, 0, 1, 0, …, 0), e.i. 1 only at the i-th position:
and the result is that if the Markov chain forgets the past, we get
This means that in a column, there is only one value, so the transition probability to a certain state is the same regardless of the current state, as we define it at the beginning.
Classification of States in Markov Chain
The possibilities of transition from state to state lead to several classes of states:
- Accessibility — a state j is called accessible from i if there is a finite set of steps that lead from i to j. For example, state 3 is accessible from state 1, but state 1 is not accessible from state 5.
- Connectivity — states are connected if the accessibility between them is going both ways. For example, 1 and 3 are connected because 3 is accessible from 1, and 1 is accessible from 3.
- Class — a group of connected states. {1, 2, 3, 4} and {5} are the classes in the above diagream.
- Recurrent state — a state which is accessible from all the states that are accessible from it. State 5 is a recurrent state.
- Transient state — a state which is not recurrent. There is a chance that after many steps, we can’t go back to such a state. 1, 2, 3, and 4 are transient states because if we move to state 5, we can never go back to any of them
