MC9510-

Modelling in Operations
Research
Probabilistic Operations Research Models
Dr T. Mayooran,
Senior Lecturer,
Department of Interdisciplinary Studies,
Faculty of Engineering,
University of Jaffna.

Email: mayooran@[Link]
 Probabilistic Operations Research Models

•Introduction to Probability Theory

•Conditional Probability
•Markov Chains
•The Exponential Distribution and the Poisson Process
•Markov Processes and Birth-Death Processes
•Renewal Theory
•Queueing Theory
•Scheduling Theory
•Reliability Theory
•Bayesian Networks
•Monte Carlo Simulation

9-Sep-25 MC9510 2
 Introduction to Probability Theory
and
Conditional Probability

9-Sep-25 MC9510 3
What is a Random Variable?
• Random Experiment
• Sample Space

• Def: A random variable X is a function that

assigns a number of X(ζ) to each outcome ζ in the
sample space of S of the random experiment

S
X(ζ) = x

ζ
x real line

9-Sep-25 MC9510 4
Set Functions
• Define Ω as the set of all possible outcomes
• Define A as set of events
• Define A as an event – subset of the set of all
experiments outcomes
• Set operations:
• Complementation Ac: is the event that event A does
not occur
• Intersection A ∩ B: is the event that event A and
event B occur
• Union A ∪ B: is the event that event A or event B
occurs
• Inclusion A ⊆ B: an event A occurring implying event
9-Sep-25 B occurs MC9510 5
Set Functions
• Note:
• Set of events A is closed under set operations
• Φ – empty set
• A  B = Φ  are mutually exclusive or disjoint

9-Sep-25 MC9510 6
Axioms of Probability
• Let P(A) denote probability of event A:
1. For any event A belongs A, P(A) ≥ 0;
2. For set of all possible outcomes Ω, P(Ω) = 1;
3. If A and B are disjoint events, P(A U B) = P(A) + P(B)
4. For countably infinite sets, A1, A2, … such that Ai ∩ Aj
= Φ for i≠j

  
P  Ai    P Ai 
 i 1  i 1

9-Sep-25 MC9510 7
Additional Properties

• For any event, P(A) ≤ 1

• P(AC) = 1 – P(A)
• P(A  B) = P(A) + P(B) – P(A  B)
• P(A) ≤ P(B) for A  B

9-Sep-25 MC9510 8
Conditional Probability

• Conditional probability is defined as

P(A  B)
P(A|B) = ------------- for P(B) > 0
P(B)
• P(A|B) probability of event A conditioned on the
occurrence of event B
• Note:
• A and B are independent if P(A  B) = P(A)P(B)  P(A) =
P(A|B) (i.e. occurrence of B has no influence on A occuring)
• Independent is NOT EQUAL to mutually exclusive !!!

9-Sep-25 MC9510 9
The Law of Total Probability

• A set of events Ai, i = 1, 2, …, n partitions the set of

experimental outcomes if
n

A  i

and i 1

Ai  Aj  
Then we can write any event B in terms of Ai, i = 1, 2, …,
n as n
B   Ai  B
i 1
Furthermore,
n
P  B    P  Ai  B   i 1 P (B Ai )P  Ai 
n

i 1
9-Sep-25 MC9510 10
Bayes Rule
• Let A1, A2, …, An be a partition of a
sample space S. Suppose the event A
occurs

A3 … An-1
A1

B
A2
An
…
A Partition of S into n disjoint sets
9-Sep-25 MC9510 11
Bayes’ Rule
• Using the law of total probability and applying it to
the definition of the conditional probability, yields

P  Ai  B  P  Ai  B 
P  Ai B    n
P B   P  Ai  B 
i 1

P  A i  P (B A i )

 P (B A i )P  A i 
n
i 1

9-Sep-25 MC9510 12
The Cumulative Distribution
Function
• The cumulative distribution function (cdf)
of a random variable X is defined as the
probability of the event {X ≤ x}:

FX(x) = Prob{X ≤ x} for -<x< 

i.e. it is equal to the probability the variable X

takes on a value in the set (- ,x]

• A convenient way to specify the

probability of all semi-infinite intervals
9-Sep-25 MC9510 13
Properties of the CDF
• 0 ≤ FX(x) ≤ 1

• Lim FX(x) = 1
x 

• Lim FX(x) = 0
x -

• FX(x) is a nondecreasing function  if a < b  FX(a) ≤ FX(b)

• FX(x) is continuous from the right  for h > 0,

FX(b) = lim FX(b+h) = FX(b+)
h0

• Prob [a < X ≤ b] = FX(b) - FX(a)

• Prob [X = b] = FX(b) - FX(b-)

9-Sep-25 MC9510 14
Example 2: Exponential Random
Variable
• Problem: The transmission time X of a
message in a communication system obey
the exponential probability law with
parameter λ, that is
Prob [X > x] = e- λx x > 0

Find the CDF of X. Find Prob [T < X ≤ 2T]

where T = 1/ λ

9-Sep-25 MC9510 15
Example 2: Exponential Random
Variable – cont’d
• Answer:
The CDF of X is
FX(x) = Prob {X ≤ x} = 1 – Prob {X > x}
= 1 - e- λx x ≥ 0
=0 x<0

Prob {T < X ≤ 2T} = FX(2T) - FX(T)

= 1-e-2 – (1-e-1)
= 0.233
9-Sep-25 MC9510 16
Example 3: Use of Bayes Rule
• Problem: The waiting time W of a
customer in a queueing system is zero if
he finds the system idle, and an
exponentially distributed random length of
time if he finds the system busy. The
probabilities that he finds the system idle
or busy are p and 1-p, respectively. Find
the CDF of W

9-Sep-25 MC9510 17
Example 3: cont’d
• Answer:
The CDF of W is found as follows:

FX(x) = Prob{W ≤ x}
= Prob{W ≤ x|idle}p + Prob{W ≤ x|busy}(1-p)

Note Prob{W ≤ x|idle} = 1 for any x ≥ 0, and 0 otherwise



FX(x) = 0 x<0
= p+(1-p)(1- e- λx) x ≥ 0

9-Sep-25 MC9510 18
 Types of Random Variables
• (1) Discrete Random Variables
• CDF is right continuous, staircase function of x,
with jumps at countable set x0, x1, x2, …

FX(x)
pmfX(x)
1
7/8
3/8
1/2
1/8
1/8

0 1 2 3 x 0 1 2 3 x
pmf: probability mass function
9-Sep-25 MC9510 19
Types of Random Variables
• (2) Continuous Random Variables
• CDF is continuous for all values of x  Prob { X
= x} = 0 (recall the CDF properties)

• Can be written as the integral of some non

negative function x
FX (x )   f (t )dt

Or
dFX ( x)
f (t ) 
dx
f(t) is referred to as the probability
9-Sep-25 MC9510 density function or PDF 20
Types of Random Variables
• (3) Random Variables of Mixed Types

FX(x) = p F1(x) + (1-p) F2(x)

Example: Example on page 17 of the slides where

F1(x) is when the system is idle (discrete random
variable) and F2(x) is when the system is busy
(continuous random variable)

9-Sep-25 MC9510 21
Probability Density Function
• The PDF of X, if it exists, is defined as the
derivative of the CDF FX(x):
dFX ( x)
f x ( x) 
dx

9-Sep-25 MC9510 22
Properties of the PDF
• fx(x) ≥ 0
b

• P{a  x  b}   f x ( x)dx
a

• FX ( x)  f

x (t )dt

• 1 

f x (t )dt A valid pdf can be formed from any nonnegative, piecewise
continuous function g(x) that has a finite integral:


 g ( x)dx  c  


By letting fX(x) = g(x)/c, we obtain a function that satisfies the

normalization condition.
This is the scheme we use to generate pdfs from simulation
9-Sep-25 results!
MC9510 23
Conditional PDFs and CDFs
• If some event A concerning X is given, then
conditional CDF of X given A is defined by
P{[X ≤ x] ∩ A}
FX(x|A) = ------------------- if P{A} > 0
P{A}
The conditional pdf of X given A is then defined by

d
fX(x|A) = --- FX(x|A)
dx

9-Sep-25 MC9510 24
Expectation of a Random Variable
• Expectation of the random variable X can
be computed by
E[ X ]   xi P[ X  xi ]
i
for discrete variables, or

E [X ]   tf

X (t )dt

for continuous variables.

9-Sep-25 MC9510 25
nth Expectation of a Random
Variable
• The nth expectation of the random variable
X can be computed by
E[ X n ]   x n i P[ X  xi ]
i
for discrete variables, or

E [X n ]   f X (t )dt
n
t

for continuous variables.

9-Sep-25 MC9510 26
Expectation of a Function of the
Random Variable
• Let g(x) be a function of the random
variable x, the expectation of g(x) is given
by
E[ g ( x)]   g ( xi ) P[ X  xi ]
i
for discrete variables, or

E[ g ( x)]   g (t ) f

x (t )dt

for continuous variables.

9-Sep-25 MC9510 27
Some Important Random Variables
– Discrete Random Variables
• Bernoulli
• Binomial
• Geometric
• Poisson

9-Sep-25 MC9510 28
Bernoulli Random Variable
• Let A be an event related to the outcomes of some
random experiment. The indicator function for A is P(IA)
defined as
1-p p
IA(ζ) = 0 if ζ not in A (i.e. if A doesn’t occur)
=1 if ζ is in A (i.e. if A occurs)
X X
• IA is random variable since it assigns a number to each 0 1 IA
outcome in S
• It is discrete r.v. that takes on values from the set {0,1}
• PMF is given by

pI(0) = 1-p, pI(1) = p , where P{A} = p

P(IA≤iA)
• Describes the outcome of a Bernoulli trial
1 p
• E[X] = p, VAR[X] = p(1-p) 1-p
• Gx(z) = (1-p+pz)
X X
0 1 IA
9-Sep-25 MC9510 29
Binomial Random Variable
• Suppose a random experiment is repeated n independent
times; let X be the number of times a certain event A occurs
in these n trials
X = I1 + I2 + … + In

i.e. X is the sum of Bernoulli trials (X’s range = {0, 1, 2, …, n})

• X has the following pmf

 n k
Pr[ X  k ]    p (1  p) nk
for k=0, 1, 2, …, n k 

• E[X] = np, Var[X] = np(1-p)

• GX(z) = (1-p + pz)n

9-Sep-25 MC9510 30
 Binomial Random Variable – cont’d
• Example

Binomial Probablity Mass Function for N = 10 and p = 0.5 Binomial Cumulative distribution Function for N = 10 and p = 0.5
0.25 1

0.2 0.8

Prob[X <= k]
Prob[X = k]

0.15 0.6

0.1 0.4

0.05 0.2

0 0
0 1 2 3 4 5 6 7 8 9 10 0 2 4 6 8 10
X (random variable) X (random variable)

9-Sep-25 MC9510 31
Geometric Random Variable
• Suppose a random experiment is repeated - We
count the number of M of independent Bernoulli
trials UNTIL the first occurrence of a success
• M is called geometric random variable
• Range of M = 1, 2, 3, …
• M has the following pmf
k 1
Pr[M  k ]  (1  p ) p
for k=1, 2, 3, …

• E[X] = 1/p, Var[X] = (1-p)/p2

• GX(z) = pz/(1-(1-p)z))

9-Sep-25 MC9510 32
Geometric Random Variable - 2
• Suppose a random experiment is repeated - We
count the number of M’ of independent Bernoulli
trials BEFORE the first occurrence of a success
• M’ is called geometric random variable
• Range of M’ = 0, 1, 2, 3, …
• M has the following pmf

Pr[M  k ]  (1  p ) p
k

for k=0,1, 2, 3, …

• E[X] = (1-p)/p, Var[X] = (1-p)/p2

• GX(z) = pz/(1-(1-p)z))

9-Sep-25 MC9510 33
 Geometric Random Variable –
cont’d
• Example: p = 0.5; X is number of failures BEFORE a success
(2nd type)
• Note Matlab’s version of geometric distribution is the 2nd
type
Geometric Probablity Mass Function for p = 0.5 Geometric Cumulative distribution Function for p = 0.5
0.5 1

0.4 0.9

Prob[X <= k]
Prob[X = k]

0.3 0.8

0.2 0.7

0.1 0.6

0 0.5
0 1 2 3 4 5 6 7 8 9 10 0 2 4 6 8 10
X (random variable) X (random variable)

9-Sep-25 MC9510 34
Poisson Random Variable
• In many applications we are interested in counting the
number of occurrences of an event in a certain time period

• The pmf is given by ak

Pr[ X  k ]  e a
k!
For k=0, 1, 2, … ; a is the average number of event occurrences
in the specified interval

• E[X] = a, Var[X] = a
• GX(z) = ea(z-1)

• Remember: time between events is exponentially

distributed! (continuous r.v. !)
• Poisson is the limiting case for Binomial as n, p 0, such
that np = a

9-Sep-25 MC9510 35
 Poisson Random Variable – cont’d
• Example:

Poisson Probablity Mass Function for  = 0.5 Poisson Probablity Mass Function for  = 0.5
0.7 1

0.6 0.95

0.9
0.5

Prob[X <= k]
Prob[X = k]

0.85
0.4
0.8
0.3
0.75
0.2
0.7
0.1 0.65

0
0 1 2 3 4 5 6 7 8 9 10 0 2 4 6 8 10
X (random variable) X (random variable)

9-Sep-25 MC9510 36
Some Important Random Variables
– Continuous Random Variables
• Uniform
• Exponential
• Gaussian (Normal)
• Rayleigh
• Gamma
• M-Erlang
• ….

9-Sep-25 MC9510 37
 Uniform Random Variables
• Realizations of the r.v. can take values from the interval [a,
b]

• PDF fX(x) = 1/(b-a) a≤x≤b

• E[X] = (a+b)/2, Var[X] = (b-a)2/12

• ФX(w) = [ejwb – ejwa]/(jw(b-a))

fx(x) Fx(x)=Prob[X≤x]

1/(b-a) 1

a b x a b x
9-Sep-25 MC9510 38
Exponential Random Variables
• The exponential r.v. X with parameter λ has pdf
0 x0
f X ( x)   x
• And CDF given by  e x0
0 x0
FX ( x)   x
1  e x0
• Range of X: [0, )

• E[X] = 1/λ, Var[X] = 1/λ2

This means:
• ФX(w) = λ/(λ-jw) Prob[X≤x] = 1-e-λx, or
Prob[X>x] = e-λx

9-Sep-25 MC9510 39
 Exponential Random Variables –
cont’d
• Example:
• Note the mean is 1/λ = 2

Exponential Probablity Density Function for  = 0.5 Exponential Cumulative distribution Function for  = 0.5
0.5 1

0.4 0.8

FX(x) = Prob[X <= x]

0.3 0.6
fX(x)

0.2 0.4

0.1 0.2

0 0
0 2 4 6 8 10 0 2 4 6 8 10
X (random variable) X (random variable)

9-Sep-25 MC9510 40
Exponential Random Variables –
Memoryless Property
• The exponential r.v. is the only continuous r.v. with the memoryless
property!!

• Memoryless Property:
P[X>t+h | X>t] = P[X>h]

i.e. the probability of having to wait h additional seconds given that one has
already been waiting t second IS EXACTLY equal to the probability of
waiting h seconds when one first begins to wait
Proof:
P[(X > t+h)  (X > t)]
P[X>t+h | X>t] = ---------------------------
P[(X > t)]

P[(X > t+h) e-λ(t+h)

= --------------- = ----------
P[X > t] e-λt

= e-λh
= P[X > h]

9-Sep-25 MC9510 41
Gaussian (Normal) Random
Variable
• Rises in situations where a random variable X is the sum of
a large number of “small” random variables – central limit
theorem
1  ( x   )2 /(2s 2 )
• PDF
f X ( x)  e
2s

For -<x< ; μ and s > 0 are real numbers

• E[X] = μ, Var[X] = s2
•  X (w )  e j w s 2w 2 / 2

• Under wide range of conditions X can be used to

approximate the sum of a large number of independent
random variables

9-Sep-25 MC9510 42
 Gaussian (Normal) Random
Variable – cont’d
• Example:

Normal Probablity Density Function for  = 5 and s = 2 Normal Probablity Density Function for  = 5 and s = 2
0.2 1

0.8

FX(x) = Prob[X <= x]

0.15

0.6
fX(x)

0.1
0.4

0.05
0.2

0 0
-5 0 5 10 15 -5 0 5 10 15
X (random variable) X (random variable)

9-Sep-25 MC9510 43
Gamma Random Variable
• Versatile distribution ~ appears in modeling of lifetime of devices
and systems
• Has two parameters: a > 0 and λ > 0

• PDF:  (x)a 1 e  x
f X ( x) 
(a )
• For 0 < x < 
• The quantity Г(z) is the gamma function and is specified by

( z )   x z 1e  x dx
0

• The gamma function has the following properties:

• Г(1/2) = √
• Г(z+1) = zГ(z) for z>0
• Г(m+1) = m! For m nonnegative integer
• E[X] = a/λ, Var[X] = a/λ2 If a = 1  gamma r.v.
• ФX(w) = 1/(1-jw/ λ)a becomes exponential
9-Sep-25 MC9510 44
Joint Distributions of Random
Variables
• Def: The joint probability distribution of
two r.v.s X and Y is given by

FXY(x,y) = P(X ≤ x, Y ≤ y)

where x and y are real numbers.

• This refers to the JOINT occurrence of {X

≤ x} AND {Y ≤ y}
• Can be generalized to any number of
variables
9-Sep-25 MC9510 45
Joint Distributions of Random
Variables - Properties
• FXY(-, -) = 0
• FXY(, ) = 1
• FXY(x1, y) ≤ FXY(x2, y) for x1 ≤ x2
• FXY(x, y1) ≤ FXY(x, y2) for y1 ≤ y2
• The marginal distributions are given by
• FX(x) = FXY(x, )
• FY(y) = FXY(, y)

9-Sep-25 MC9510 46
Joint Distributions of Random
Variables – Properties - 2

 2 FXY ( x, y )
• Density function: f XY ( x, y ) 
xy
x y

or FXY ( x, y )  f
 
XY (a ,  )dad

• Marginal densities: f X ( x)  f

XY ( x, y )dy

and 
f y ( y)  f

XY ( x, y )dx

9-Sep-25 MC9510 47
Joint Distributions of Random
Variables – Independence

• Two random variables are independent if

the joint distribution functions are
products of the marginal distributions:
FXY ( x, y)  FX ( x) FY ( y)
or
f X Y ( x, y )  f X ( x ) f Y ( y )

9-Sep-25 MC9510 48
Joint Distributions of Random Variables
– Discrete Nonnegative Variables
• Def:
 
FXY ( x, y )   P( X  xi , Y  yi )U x  xi U  y  yi 
i 0 j 0

where
P(X=xi, Y=yi) is the joint probability for
the r.v.s X and Y
U(x) is 1 for x ≥ 0 and 0 otherwise

9-Sep-25 MC9510 49
Example 4: Packet Segmentation
• Problem: The number of bytes N in a
message has a geometric distribution
with parameter p. The message is broken
into packets of maximum length M bytes.
Let Q be the number of full packets in a
message and let R be the number of
bytes left over.
A) Find the joint pmf for Q and R, and
B) Find the marginal pmfs of Q and R.

9-Sep-25 MC9510 50
Example 4: Packet Segmentation -
cont’d
• Solution:
N ~ geometric  P(N=k) = (1-p)pk

Message of N bytes  Q full M-bytes packets +

R remaining bytes
Therefore: Q  {0, 1, 2, …}, R  {0, 1, 2, …, M-1}

The joint pmf is given by:

P(Q=q, R=r) = P(N = qM+r) = (1-p)p(qM+r)

9-Sep-25 MC9510 51
 Example 4: cont’d
• Solution:
The marginal pmfs:
M 1
P(Q  q)   P(Q  q, R  r )
r 0
M 1
  (1  p) p qM  r 
r 0

 1  p M  p M 
q
q  0,1,2,...

and P( R  r )   P(Q  q, R  r )
q 0

  (1  p) p qM  r 
q 0
Verify the marginal pmfs add to ONE!!
P(R = r) is a truncated geometric r.v. 
1 p r
p r  0,1,..., M  1
9-Sep-25 1 MC9510
pM 52
Independent Discrete R.V.s
• For Discrete random variables:

P(M=i, N=j) = P(M=i) P(N=j)

9-Sep-25 MC9510 53
Example 5:
• Problem: Are the Q and R random variables
of Previous Example independent? Why?

9-Sep-25 MC9510 54
Conditional Distributions
• Def: for continuous X and Y
FY X  y x   P (Y  y X  x ) 
FXY (x , y )
FX (x )
Or
fY X  y x  
f XY (x , y )
f X (x )
• For discrete M and N

P M  i ,N  j 
P M  i N  j  
P N  j 

9-Sep-25 MC9510 55
Conditional Distributions - 2
• For mixed types:

FX x    P( N  j, X  x)
i 0


  P (N  j )P (X  x N  j )
j 0
or

P (N  j )   P (N

 j X  x )f X (x )dx

9-Sep-25 MC9510 56
 Conditional Distributions - 3
• For N random variables:
FX 1 ,X 2 ,...,X N  x 1, x 2 ,..., x N 
 FX 1  x 1   FX 2 X 1  x 2 x 1   ...  FX N X 1,...,X N 1  x N x 1 ,..., x N 1 

or

f X 1 ,X 2 ,...,X N  x 1, x 2 ,..., x N 
 f X 1  x 1   f X 2 X 1  x 2 x 1   ...  f X N X 1,...,X N 1  x N x 1 ,..., x N 1 

9-Sep-25 MC9510 57