Chapman-Kolmogorov Equations
A random process is a discrete/continuous function that varies with time where each time instant is assigned an outcome of a random experiment conducted. When a random process follows Markov Property (independence from past data), it is called Markov Process. To know about Markov Property in detail, refer to the blog “Markov Jump Processes”. A Markov Process with discrete state space and discrete-time is called Markov Chain. Transition Probabilities of a Markov Chain follow the Chapman-Kolmogorov Equation. This blog talks about Markov Chains and Chapman-Kolmogorov Equations. I hope it is informative.
Markov Chains
The Markov Chain is dynamic in nature, i.e. it keeps on changing with time, and thus it is not static. As an example, let us consider a model of a shop which provides discounts to its customers according to the following rules:-
1. A new customer starts at a 5% discount.
2. If he buys something within a week, he moves one level up or remains at the top level.
3. If he doesn’t buy for a week, he moves to a level down or remains at the lowest level.
The three discount states are 5%, 15%, 20%.
The probability that a customer shops within a week of the last purchase is ¾, i.e. 0.75, and that he doesn’t shop is ¼, i.e. 0.25.
Transfer from one state to the other is called transition, even staying at the same state is a possible transition. The probabilities of these transitions are called transition probabilities. A matrix showing transition probabilities is known as a transition matrix.
Mathematically, transition probabilities are denoted by:-
P[Xn = j | Xm = i] = pij(m,n)
Here, pij(m,n) denotes the probability of being in a state j at time n given that at time m, it had been in state i. Here, the transition happens from time m to time n. If the transition is just one step; then the equation would become:-
P[Xm+1 = j | Xm = i] = pij(m,m+1)
This will tell us the probability of the immediate future. The basic ideology behind Chapman-Kolmogorov Equation includes combining such one-step transitions to determine long term transitions. According to the equation, the probability of being in state j at time n having been in state i at time m is equal to the product of probability of being in state k at time l having been in state i at time m and the probability of of being in state j at time n having been in state k at time l, where k is any state similar to i and j and l is any time between m and n. Note that states are not often arranged in definite order, so k need not be any state between i and j.
Mathematically:-
pij(m,n)=∑k∈S pik(m,l)pkj(l,n)
; for all states i, j and k which belong to the state space S, and times m, l and n where n>l>m.
So this was all about Chapman-Kolmogorov Equations. I hope it was helpful. Suggestions and reviews to help me improve are most welcomed. Thank you for visiting.
Shreya Kashyap