C.5. Theory of Markov ChainsA Markov process , X n , is a stochastic process in which the past state has no impact on the future state if the present state is specified. In other words, in a Markov process, any subsequent behavior of a state is independent of its past activity. We use a state machine called a Markkov chain to express a Markov process. Therefore, a Markov chain depicts the activities of a Markov process, state by state, which is a convenient way to grasp the essence of the process. Figure C.1 shows a simple Markov chain. Figure C.1. A simple Markov chain
A chain can start from a state 0 and move toward an ending state, if there is one. The chain in this figure shows three sample states on a Markov chain: i - 1, a past state; i , the present state; and i + 1, a future state. These three states are connected through their associated probabilities, shown in the figure. Markov chains are also classified as either discrete time or continuous time . C.5.1. Continuous-Time Markov ChainsIn a continuous-time Markov chain based on a random process, X ( t ), the transition probabilities occur in a very short period of time, . Assuming ± i,i to be the rate at which the process leaves state i , the probability that the process remains in state i during is estimated as Equation C.35
When it leaves state i , the process enters state j with probability i, j . Thus, the probability that the process remains in state j during is Equation C.36
Combining Equations (C.35) and (C.36), we derive Equation C.37
where ± i , j = ± i , i i,j is the rate at which process X ( t ) moves from state i to state j . If we divide Equations (C.35) and (C.37) by and take a limit, we get Equation C.38
To find a state j probability of the process at a given time t denoted by P j (t) = P [ X ( t ) = j ], we can elaborate further: Equation C.39
By subtracting P j (t) from both sides of this equation, dividing them by , taking a limit of 0, and applying the Equations in (C.38), we can derive Equation C.40
This is an important result, known as the Chapman-Kolmogorov equation on continuous-time Markov chains. This equation clearly deals with the differential operation of a state probability with respect to time t . |