Let us talk about Markov chain introduction. Markov chain is a system in which one state undergoes transitions to another state where states are always in the countable form. It’s the random process in which the next state does not depend on the sequence of the events that precede it, but on the current state. This is based on the Markov property and named after the scientist Andrey Markov.
Continuous Time Markov ChainsBack to Top
The Markov property of continuous time Markov Chains:
Pr(X(t)) = k | X(m) = l , X(tn-1) = ln-1 …… , X(t1) = l1) = P(X(t)) = k | X(m) = l)
The above general formula shows that the process at the current time depends only at the most recent time prior to the current time or we can say that the process at time ‘m’ does not depend on the process before the time ‘m’.
Since we know that the Markov property is not efficient in the distribution of time therefore, unlike discrete time Markov chains, the continuous time Markov chains consider only time homogeneous process.
Pr (X (t)) = k | X (m) = l) = P(X(t - m) = j | X(0) = l)
By time homogeneous it is meant the time whenever the process enters the state (i.e. that the process is starting in an initial state ‘l’ at time zero(t = 0)). Now time spent by the process in the current state is called holding time in the state. When the continuous time Markov process leaves the current state the following conditions must hold true:
1. The number of states it has skipped must remain the same.
2. The Set of states must also remain the same.
3. The probability of a process going to other state should remain the same.
The properties of Continuous time Markov chains:
The main entity of continuous time Markov chain is Cij which acts like an alarm when we enter the state. There is an alarm for each state which gives the notification that we entered the state from the previous state. The time of the alarm clock is exponentially distributed with the rate of the process.
Vi = ∑j є m Cij
Where Cij = 0, if the process does not go from current state to the next state. When the process goes from one state to other state the probability is Cij / Vi which can also be denoted by Pij. It is the transition probability or in other words jump chain. The above quantities are related by
Vi = ∑j є m Cij
Cij = Vi * Pij
Pij = Cij / Vi
Here we assume Vi is less than infinity for all the states of the chain as if Vi is equals to infinity then the process will immediately leave the current state after it enters it, then there will be no holding time left. We also assume that Vi > 0 for all the current states. If Vi = 0, then the process will stay at the current state forever.
Since we know that the time spent in the current state is exponentially distributed with the rate, we can Calculate The Probability of two or more transitions in a given time interval by
Pr (Ti > g) = e-vig
Where ‘Ti’ is the holding time and ‘g’ is the time interval.
By expanding the above formula we get
Pr (Ti > g) = e-vig
= 1 – vi g + (vi h)2 / 2! – (vi h)3 /3! + …..
= 1 – vi g + o (g)
Or we can say
P (Ti ≤ g) = vi g + o (g)
Now if Tj is the holding time of ‘j’ then Tj is exponentially distributed Vj but Tj ≠Ti or we can say that both the events are independent.
Let’s discuss the limiting Probabilities of Continuous time Markov chains.
We denote the limiting probabilities for Continuous time Markov chains
Lim Cij (t), t → ∞
Where Cij (t)= Pr (X (t) = j| X(0) = I) is the transition probability function of states of a Continuous time Markov chains. Earlier when we considered the constant distribution ∆ of Continuous time Markov chains and ∆ is the distribution when the process is equally distributed we can also say that ∆ is a proportion of time that the process is in the current state. The limiting probability is equal to the probability ∆ for all i є m or we can say that no matter the process is in state i, the probability of going to state j at time t approaches ∆ as ‘t’ increases. This is the only case available with Continuous time Markov chains. The limiting probability and the probability of each state are same in Continuous time Markov chains
Cij = 0 for all t > 0, or
Cij (t) > 0 for all t > 0
This is called Levy Dichotomy.
Examples of Continuous time Markov chains are:
1. Passion process (only i → i +1)
State space 0, 1, 2,…
Ti ~ exp (λ) so vi = λ, i = 0, 1, 2….
Pij = 1, j = i + 1
= 0, j ≠ I + 1
2. Pure Birth Process:
Same Pij as is Poisson Process, but with vi = λi.
Example: Yule process (linear birth process): λi = iλ.
3. Birth and death process (only i → i + 1 or i → i – 1 )
State space 0, 1,…. or 0, 1,….N
Time till ‘birth’ i → i + 1 is Xi ~ exp(λi)
Time till next ‘death’ i → i – 1 is Yi ~ exp (μi)
Time till next transition is min (Xi, Yi) ~ exp(vi) with vi = λi + μi
Pi,i+1 = P(Xi < Yi) = λi / λi + μi
Pi,i-1 = P(Xi > Yi) = μi / λi + μi
Applications of Continuous time Markov Chains:
Continuous time Markov Chains are used in physical processes, identical systems, independent processes and probabilities.
1. In chemical reaction it is used to find the state of the enzyme that goes through the chemical reaction from one state to another since the molecules of the enzymes are independent of each other. It also describes the probability of a molecule in a given state.
2. In queuing theory, where the jobs are exponentially distributed with passion arrival rate ‘R’ as the number of jobs are continuous time Markov chains with non negative integers.
Classification of States of Markov ChainsBack to Top
This can be concluded as each object would fall into one and only in one class if there is a collection of objects is partitioned. This is something like the equivalence relation according to which two objects are equivalent if one falls into the same partition as the other. There are three properties for the equivalence relation
For any object let it be X the relation (X, X) exits since an object is always equal to itself.
If there is existence of (X, Y) then there will be the existence of (Y, X) also since if ‘X’ is equivalent to the ‘Y’ then definitely ‘Y’ is equivalent to ‘X’.
If there is a existence of (X, Y) and (Y, Z) then the relation (X, Z) would be in existence also since ‘X’ is equivalent to ‘Y’ and ‘Y’ is equivalent to ‘Z’ then ‘X’ would be equivalent to ‘Z’ too.
Here it can be noticed that the relation of communicating is an equivalence relation. First is the definition of an object that belongs to the same communicating class as itself. Second shows that if ‘X’ and ‘Y’ communicate then it is possible to go from each state to the other and the last one shows that if ‘X’ communicates with ‘Y’ and ‘Y’ communicates with ‘Z’ then it is possible to go from ‘X’ to ‘Z’ as one can move from ‘X’ to ‘Y’ and then ‘Y’ to ‘Z’.
Here conclusion of is that, ‘X’ and ‘Y’ relates to the same communication class if and only if there is a communication between them means if it’s possible to go from ‘X’ to ‘Y’ and from ‘Y’ to ‘X’.
There are three state classifications for the finite Markov Chains that are transient state, ergodic state and periodic state. Two vertices’ relates to the same classification if they have the same classification. For the classification we first need to find the easiest vertex of that communicating class and then need to classify the vertex. Always find the communicating class before the classification of state. The classifications of states are,
Transient state is there if it is possible to leave the state and never return.
Periodic state exists if the state is returned to only on multiples of some positive integers > 1 and that Integer is the Period of the state.
Ergodic state exists if the state is neither transient nor periodic. This is all about classification of states.
Steady State BehaviourBack to Top
∂ P / ∂ t = 0
You all should know that a steady state behavior is seen in a system when some time has passed after the system has been started or has been initiated. In steady state behavior, the initial state is generally called as the transient state and the Period when the system starts till the steady state is known as the start-up or warm-up period.
There are many applications of steady state behavior and it plays a significant role in the fields of economics and thermodynamics. You have to understand that when a system is starts, initially it will show changes with time and will show transient behavior, but when at some Point it starts showing steady state behavior, then it will continue showing that behavior in the future also without any changes.
Let us understand this with some examples: like our tanks in our home, they are filled with fluids like water, milk, etc. They are the examples of transient state because the volume of fluid in it changes with time. But when we consider the case of pipes or tubes, then the flow of any fluid through them or we can also take the case of electricity through a network, they can be the cases of steady state behavior as the flow of the fluid in the tubes or network is constant.