Section C.5. Theory of Markov Chains


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.

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



Computer and Communication Networks
Computer and Communication Networks (paperback)
ISBN: 0131389106
EAN: 2147483647
Year: 2007
Pages: 211
Authors: Nader F. Mir

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net