Computer and Communication Networks (paperback)

C.5. Theory of Markov Chains

A 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.

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 Chains

In 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 .