Let X T Be a Pure Birth Continuous Time Markov Chain odd Even

Chapter 5. Continuous-Time Markov Chains

The evolution of time-dependent systems can be obtained by different methods, the most commonly known one is the method of differential equations. In addition, if they exhibit random movements the situation becomes even more complicated. It is not the aim of this chapter to deal with the theory of stochastic processes since it has a wide literature and their mathematical level exceeds the level of the note. Omitting the precise mathematical treatment we concentrate only on the simplest processes which be used later on in the performance modeling of queueing systems. There is a variety of sources on this topic in either digital or printed form but for our purposes the following books fit best: Allen [ 2 ], Kleinrock [ 48 ], Ovcharov [ 60 ], Sztrik [ 81 ], Tijms [ 91 ], Trivedi [ 94 ].

This section is devoted to one of the most commonly used stochastic processes, that is when each time we have a random variable taking values representing the states of the process. To know the evolution of the process we need the connection of the random variables at different times, in other words, we have to formulate mathematically how the future depends on th past. The simplest relationship is when the future depends on the past only through the present which can expressed as follows

Definition 5.1. (Markov-property) If for any n and states

then process is called a Markov chain .

Let denote the transition probability probability of the chain, which is in time-homogeneous case is denoted by Clearly it means that the process during time changes its state from to irrespective to where it is.

It is easy to see that

To get how the distribution of the states changes during the time we have to know how the transition probabilities changes. Thus we define

Definition 5.2. (Intensity matrix, rate matrix) The intensity matrix with elements is defined by

Hence the transition probabilities can be expressed as

Let us introduce the distribution of the process at time , that is

Then for the balance equations we have

These can be written as

Taking the limit the desired system of differential equations can be obtained, namely

Steady-state, stationary distribution

One can easily notice that all the systems treated in the previous problems are special cases of continuous-time Markov chains. As we have seen it is rather difficult to get the transient solution even for quite simple systems. To obtain treatable formulas we are interested in the limiting distribution which is called steady-state , stationary distribution . Mathematically this can be written as .

Then the steady-state balance equations can be obtained as

In performance modeling of different systems we have to identify the stochastic process describing the dynamic behavior of the system. The most widely used, consequently the most thoroughly investigated class of stochastic process is the Markov process. Many practical problems can be treated by the help of a continuous-time Markov chain that is why without proof we state the following theorem

Theorem 5.3. A stochastic process is a continuous-time Markov chain if and only if the sojourn time in any state is an exponentially distributed random variable with parameter , j=0, 1, 2... .

5.1. 5.1. Birth-Death Processes

To simplify the investigations let us assume that the process enters to neighboring states only. This situation can be formulated as follows

In this case , and are called birth, death intensities , respectively. Then the balance equations are also simplified, namely

In steady-state we have

To obtain the solution let us notice that for any we get

since it is easy to see that

By using this relationship it can be verified that

which is called the steady-state distribution of a birth-death process and later on plays an important role in modeling several queueing systems.

In the case of an infinite state space the series concerning to the normalizing condition should be convergent. In many times conditions assuring the convergence are referred to as stability conditions . It could be proved that under stability condition the solution is unique.

Let us consider the following simple example

Example 5.1. Let and .