• Markov Processes

• Birth & Death queueing model

• Block Diagram and explanation of single and multiple server queuing system

• M/M/1/$\infty$ queueing system

**Mumbai University > Electronics and Telecommunication Engineering > Sem 5 > Random Signal Analysis

Marks: 10M

Year: May 2016

• Markov Processes

The stochastic process X(t) is referred to as a Markov Process if it satisfies the Markovian Property (i.e. memoryless property). This states that -

P{X(tn+1)=xn+1 | X(tn)=xn ...... X(t1)=x1} = P{X(tn+1)=xn+1 | X(tn)=xn}

for any choice of time instants ti , i =1,……, n where tj > tk for j>k .

This is referred to as the Memoryless property as the state of the system at future time tn+1 is only decided by the system state at the current time tn and does not depend on the state at the earlier time instants t1 ,…….., tn-1

Restricted versions of the Markov Property lead to different types of Markov Processes. These may be classified based on whether the state space is a continuous variable or discrete and whether the process is observed over continuous time or only at discrete time instants.

These may be summarized as -

(a) Markov Chains over a Discrete State Space

(b) Discrete Time and Continuous Time Markov Processes and Markov Chains

A Homogenous Markov Chain is one where the transition probability P{Xn+1=j | Xn = i } is the same regardless of n .

Therefore, the transition probability pij of going from state i to state j may be written as

$P_{ij}$= P{$X_{n+1}$ = j | $X_n$=i} Ɐ n

Note that this property implies that if the system is in state i at the nth time instant then the probability of finding the system in state j at the $(n+1)^{th}$ time instant (i.e. the next time instant) does not depend on when we observe the system, i.e. the particular choice of n. This simplifies the description of the system considerably as the transition probability $p_{ij}$ will be the same, regardless of when we choose to observe the system.

Example: Communication System:

Consider a communication system in which the digits 0 and 1 are transmitted through several stages. At each stage the probability that the entering digit will be transmitted unchanged is p. Let$ X_n$ denote the digit entering the $n^{th}$ step, then {$X_n$,n=0,1,2,……..} is a Markov Chain with two states. ∴ Transition probability matrix is given as

Future states of $X_{n+1}$

Present states of $X_n$

• Birth & death queueing model

Birth and Death processes constitute an important sub-class of Markov processes. A number of natural and industrial processes are modeled as birth and death processes.

The birth and death process can be explained as follows. Let X(t) be a continuous time Markov chain with discrete state space 0,1, 2,….X(t)=j indicates that the system has a population of j elements at time t. The system is then said to be in state $S_j$. This process can be called as birth and death process if there exists non-negative birth rates ($λ_j$,j=0,1,2,….) and non-negative death rates ($μ_j$,j=1,2,…..) satisfying the following conditions.

Change of states are allowed from state $S_j$ to $S_{j+1}$or from $S_j$ to $S_{j-1}$ if j ≥ 1, but from state $S_0$ to $S_1$ only.

If at time t, the system in state $S_j$ then in a time interval (t,t+∆t ) the state changes from $S_j$ to $S_{j+1}$ with probability $λ_j$ ∆t and from $S_j$ to $S_{j-1}$ with probability $μ_j$ ∆t

From (i) it is clear that only one birth and death can occur at a time and no death can occur when the system is empty.

So, birth-death processes is a continuous time Markov chain that takes the discrete state space values 0,1,2…….. and changes equally as +1 or -1.

In queueing theory the birth death process is referred as:

Arrivals can be considered as ‘births’ to the system, since if the system is in state $S_n$ (n customers are in the system) and an arrival occurs, the system is changed to $S_{n+1}$. On the otherhand , a departure occurring while the system is in state $S_n$ leads the system down to $S_{n-1}$ and can be looked upon as a ‘death’.

• Block Diagram and explanation of single and multiple server queuing system.

A queueing system can be described as customers arriving for service, waiting for service if it is not immediate, and if having waited for service, leaving the system after being served.

Service Pattern of Servers:

Service pattern can be described by service rate (number if customers served per some unit of time) or as time required to service a customer (inter service time). This pattern includes the distribution of the time to service a customer, the number of servers and the arrangement of servers may be in series, parallel etc. The number of servers may be finite or infinite. Service may be single or batch.

A single and multiple server queuing system are shown below:

$$Multiple Server Queue$$

We follow queueing system in which the service pattern follows Poisson distribution with service rate μ or inter service time has an exponential distribution with mean 1/μ

The queueing disciplines are classified as:

FIFO (First in first out), LIFO (Last in first out), SIRO (Selection in Random Order), PIR(Priority in Selection).

• M/M/1/$\infty$

The M/M/1 is a single-server queueing model, which can be used to approximate simple systems. The M/M/1 queuing system is described as a queuing model where:

Arrivals form a Poisson process i.e. interarrival time is exponentially distributed

Service time is exponentially distributed

There is one server

The length of queue in which arriving users wait before being served is infinite

The population of users (i.e. the pool of users) available to join the system is infinite

A simple M/M/1 queue with arrival rate λ and service rate µ

There are a lot of situations where an M/M/1 model could be used. For instance, you can take a post office with only one employee, and therefore one queue. The customers arrive, go into the queue, they are served, and they leave the system. If the arrival process is Poisson, and the service time is exponential, we can use an M/M/1 model. Hence, we can easily calculate the expected number of people in the queue, the probabilities they will have to wait for a particular length of time, and so on.

Steady State Distribution

A birth and death process is a M/M/1 queue when λi = λ and μi = μ for all i.

Let pn represents the probability mass function of a discrete random variable denoting the number of customers in the system in long run

pn = (1-ρ) ρn, ρ<1

where,

ρ = λ/µ represents the traffic intensity of the system. For a stable system the intensity ρ must be less than 1. It can be seen above that the steady state probabilities for an M/M/1 queue follows the geometric distribution with parameter (1- ρ).

Measures of Effectiveness