Chapter 6

Continuous-Time Markov Chains

  • Introduction
  • Definition: It is a stochastic process that moves from state to state in accordance with a discrete-time Markov chain, but the amount of time spent in each state is exponentially distributed.
  • Memoryless
  • Transition probability (pij) is the probability that the process will make a transition from state i to state j.
  • Pii = 0,all i
  • Pij = 1,all i

j

  • Problem 6.2 and 6.12(a)
  • Birth and death processes: A continuous-time Markov chain for which transitions may take place only between neighboring states (i.e. n to n + 1 or n – 1 only).

n n

  • n – arrival rate
  • n – departure rate
  • n and nare independent of time.
  • n and nmay be dependent on n.
  • State transition rate vi(the rate at which the process leaves the state i):
  • v0 = 0
  • vi= i + i
  • State transition probability:
  • p01 = 1
  • Birth before death:
  • Death before birth:
  • Problem 6.4
  • Special cases:
  • Pure birth process:  = 0. If  = constant, it is a Poisson process (Ex. 6-2)
  • Pure death process:  = 0. If  = constant, it is a Poisson process (Problem 6-9)
  • Queueing process basics:
  • M/M/1:

n = n 0;n = n 1

  • M/M/1 with blocking:

n is the probability that a customer will enter the system with n customers already in the system.

n = nn 0;n = n 1

  • M/M/s:

s = number of severs

n= n 0

n 1 ns

n=

s  ns

  • Transition time Ti: The time required to go from state i to state i+1.
  • Transition probability function:
  • Pij is the one-step transition probability.
  • Pij(t) is the transition probability for a time period equal to t, during which any number of steps including zero step can happen.
  • As a result, although Pii must equal to zero, Pii(t) is in general greater than 0.
  • Let vi be the transition rate when the process is in state i and qij be the transition rate from state i to state j.
  • From the above relationships we can derive a set of differential equations for the transition probability function Pij(t).
  • Kolmogorov’s backward equations:
  • Kolmogorov’s forward equations:
  • The general equation for Pii(t) is too messy to deal with. We will only discuss the birth and death process here (Example 6.11).
  • Limiting Probability:
  • General formulation:
  • For a birth and death process:

  • Limiting probability may not exist. For example, an M/M/1 process with  greater than  would have a queue that expands indefinitely. For a birth and death process the condition is:
  • Ex. 6.14 (Use infinite series)
  • Introduction to queueing theory (Chapter 8)
  • Definition: It is a class of models in which customers arrive randomly at a service facility. Upon arrival they will wait for their turns and then will be served. The time it takes to serve a customer is also a random function. Once served they are generally assumed to leave immediately.
  • Cost functions:
  • L – The average number of customers in the system
  • LQ – The average number of customers waiting in the queue
  • W – The average amount of time a customer spends in the system
  • WQ – The average amount of time a customer spends in the queue
  • Cost identity: Average earning rate (system) = a (average cost / customer)

(ais the average arrival rate of entering customers)

  • Little’s formula: Average number of customers in the system = the average arrival rate of entering customers  the average amount of time a customer spends in service.

L = aWLQ = aWQ

  • Steady-state probabilities: Pn is the limiting probability that there will be n customers in the system. It also represents the proportion of time that n customers in the system.
  • M/M/1 queue
  • M/M/1 with infinite capacity:

P0 = 1 – / , Pn = (/ )n (1 – / )

L = n Pn = / ( – ),W = L / a = 1 / ( – )

WQ = W – E[S] = /  ( – )LQ = a WQ= 2 /  ( – )

Example: On average a single-processor CPU completes 10 jobs per second and a job arrives every 0.4 seconds. Jobs are executed immediately if the CPU is idle. Otherwise they will be placed in the hard disk to wait for their turns according to the order of arrivals. If arrival and completion times of jobs are exponentially distributed,

a)estimate the average CPU time for each job.

1 / 10 = 0.1 second

b)estimate the average total wait time for each job.

 = 1/0.4 = 2.5 / seconds,  = 10 / seconds, WQ = /  ( – ) = 0.033 seconds

  • M/M/1 with finite capacity (N): The condition / < 1 is unnecessary in this case since the size of the queue is limited to N.

  • M/M/k queue
  • Erlang loss system (no queue):
  • For a M/G/k queue (Erlang loss formula):

where E[S] = 1/ is the mean service time.

  • Infinite queue:

  • Summary:
  • This is a basic presentation of the theory of queueing systems.
  • Other types of queueing systems include the G-types, which refer to general distributions.
  • Other complications include network of queues, open/closed queues, priority queues, busy and idle periods, …
  • Queueing theory itself is a graduate-level course.