Probability

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 1
 Outline
 Introduction
 Probability Theory and Statistics Theory
 Random variables
 Probability mass function (pmf)
 Probability density function (pdf)
 Cumulative distribution function (cdf)
 Expected value, nth moment, nth central moment, and variance
 Some important distributions

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 2
 Probability Theory and Statistics Theory

 Random Variables (RVs)

 Let S be sample associated with experiment E
 X is a function that associates a real number to each s S
 RVs can be of two types: Discrete or Continuous
 Discrete random variable => probability mass function (pmf)
 Continuous random variable => probability density function (pdf)

R
s X X(s)

S
S R
Dr. Laxmipriya Parida
Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 4
 Discrete Random Variables

 In this case, X(s) contains a finite or infinite number of

values
 The possible values of X can be enumerated
 E.g., throw a 6 sided dice and calculate the probability of a
particular number appearing.

Probability
0.3

0.2 0.2

0.1 0.1 0.1

Number
1 2 3 4 5 6

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 5
 Discrete Random Variables

 The probability mass function (pmf) p(k) of X is

defined as:
p(k) = p(X = k), for k = 0, 1, 2, ...
where
1. Probability of each state occurring
0  p(k)  1, for every k;
2. Sum of all states
 p(k) = 1, for all k.

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 6
 Continuous Random Variables
 In this case, X contains an infinite number of
values
 Mathematically, X is a continuous random
variable if there is a function f, called probability
density function (pdf) of X that satisfies the
following criteria:
1. f(x) 0, for all x;

2.  f(x)dx = 1.

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 7
 Cumulative Distribution Function
 Applies to all random variables
 A cumulative distribution function (cdf) is defined
as:
 For discrete random variables:

P(k) = P(X  k) =  P(X = k)

all  k

 For continuous random variables:

x
F(x) = P(X  x) =  f(x)dx
-

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 8
 Probability Density Function

 The pdf f(x) of a continuous random variable X is

the derivative of the cdf F(x), i.e.,
dFX x 
f x  
dx

f(x)
CDF
Area

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 9
 Expected Value, nth Moment, nth
Central Moment, and Variance
 Discrete Random Variables
 Expected value represented by E or average of random
variable
E[X] =  kP(X = k)
all  k
 nth moment
E[Xn] =  knP(X = k)
all  k
 nth central moment
E[(X – E[X])n] =  (k – E[X])nP(X = k)
all  k
 Variance or the second central moment
2 = Var(X) = E[(X – E[X])2] = E[X2] - (E[X])2

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 10
 Expected Value, nth Moment, nth
Central Moment, and Variance

0.3

0.2 0.2

E[X] = 0.166
0.1 0.1 0.1

1 2 3 4 5 6

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 11
 Expected Value, nth Moment, nth
Central Moment, and Variance
 Continuous Random Variable
 Expected value or mean value
+
E[X] =  xf(x)dx
-
 nth moment +
E[Xn] =  xnf(x)dx
-
 nth central moment +
E[(X – E[X])n] =  (x – E[X])nf(x)dx
-
 Variance or the second central moment
2 = Var(X) = E[(X – E[X])2] = E[X2] - (E[X])2

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 12
 Some Important Discrete Random
Distributions
 Poisson
k e  
P ( X k )  , k 0, 1, 2,..., and   0
k!
 E[X] = , and Var(X) = 
 Geometric
P(X = k) = p(1-p)k-1 ,
where p is success probability

 E[X] = 1/(1-p), and Var(X) = p/(1-p)2

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 13
 Some Important Discrete Random
Distributions
 Binomial
Out of n dice, exactly k dice have the same value: probability
p k and (n-k) dice have different values: probability(1-p) n-k.
For any k dice out of n:

n
P(X k)  pk(1 p)n k ,



k 



where,
k 0,1,2,...,n; n 0,1,2,...; p is the sucess probability, and
 n
 
  n!
k  k!(n  k)!
 

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 14
 Some Important Continuous Random
Distributions
 Normal
 ( x  )2
1 2
f X( x)  e 2 , for -   x  
2 
and the cumulative distribution function can be obtained by
x  ( y   )2
1
F X ( x) 
2  e

2 2
dy

 E[X] = , and Var(X) = 2

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 15
 Some Important Continuous Random
Distributions
 Uniform
 d 
 , for a  x b 
fX ( x)  b  a 

0, otherwise  
and the cumulative distribution function is
0, for x  a 
x  a 
 
FX ( x)  , for a  x b 
b  a 

1, for x  b  
 E[X] = (a+b)/2, and Var(X) = (b-a)2/12

Dr. Laxmipriya Parida

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 16
 Some Important Continuous Random
Distributions
 Exponential
0, x0 
fX ( x)   x 
e , for 0  x  
and the cumulative distribution function is
0, x0 
FX(x)   x 
1  e , for 0  x  

 E[X] = 1/, and Var(X) = 1/2

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 17
 Multiple Random Variables
 There are cases where the result of one experiment
determines the values of several random variables
 The joint probabilities of these variables are:
 Discrete variables:
p(x1, …, xn) = P(X1 = x1, …, Xn = xn)
 Continuous variables:
cdf: Fx1x2…xn(x1, …, xn) = P(X1  x1, …, Xn  xn)

n
 FX 1, X 2,... Xn( x1, x 2,...xn)
pdf: fX 1, X 2,... Xn( x1, x 2,...xn) 
x1x 2...xn

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 18
 Independence and Conditional
Probability
 Independence: The random variables are said to be independent
of each other when the occurrence of one does not affect the
other. The pmf for discrete random variables in such a case is
given by:
p(x1,x2,…xn)=P(X1=x1)P(X2=x2)…P(X3=x3) and for continuous
random variables as:
FX1,X2,…Xn = FX1(x1)FX2(x2)…FXn(xn)
 Conditional probability: is the probability that X1= x1 given that
X2= x2. Then for discrete random variables the probability
becomes:
P ( X  x1, X 2  x 2,..., Xn  xn)
1
P ( X 1  x1 | X 2  x 2,..., Xn  xn) 
P ( X  x ,..., X n  x n )
2 2

and for continuous random variables it is:

P ( X 1  x1, X 2  x 2,..., Xn  xn )
P ( X 1  x1 | X 2  x 2,..., Xn  xn ) 
P ( X 2  x 2,... Xn  xn )
Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 19
 Bayes Theorem

 A theorem concerning conditional probabilities of

the form P(X|Y) (read: the probability of X, given Y)
is
P (Y | X ) P ( X )
P( X | Y ) 
P (Y )
where P(X) and P(Y) are the unconditional
probabilities of X and Y respectively.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 20
 Important Properties of Random
Variables
 Sum property of the expected value

Expected value of the sum of random variables:
 n  n
E   aiXi   aiE[ Xi ]
 i 1  i 1

 Product property of the expected value

 Expected value of product of stochastically
independent random variables
 n  n
E   Xi   E[ Xi ]
 i 1  i 1

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 21
 Important Properties of Random Variables
 Sum property of the variance
 Variance of the sum of random variables is
 n  n n -1 n
Var   aiXi   ai Var ( Xi )  2  aiaj cov[ Xi, Xj ]
2

 i 1  i 1 i 1 ji 1

where cov[Xi,Xj] is the covariance of random

variables Xi and Xj and
cov[ Xi , Xj ] E[( Xi  E[ Xi ])( Xj  E[ Xj ])]
E[ XiXj ]  E[ Xi ]E[ Xj ]

If random variables are independent of each other,

i.e., cov[Xi,Xj]=0, then
 n  n
Var   aiXi   ai 2Var ( Xi )
 i 1  i 1

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 22
 Important Properties of Random Variables
 Distribution of sum - For continuous random variables with joint pdf fXY(x, y)
and if Z = Φ(X,Y), the distribution of Z may be written as
FZ ( z ) P( Z  z )  fXY ( x, y )dxdy
zZ
where ΦZ is a subset of Z.
 For a special case Z= X+Y  
Fz ( z ) 
fXY ( x, y )dxdy  fXY ( x, y )dxdy
Z   

 If X and Y are independent variables, the fXY (x,y)= fX(x)fY(y)


fZ ( z )  fX ( x ) fY ( z  x ) dx, for -  z  


 If both X and Y are non negative random variables, then pdf is the convolution
of the individual pdfs, fX(x)z and fY(y).
fZ ( z ) fX ( x) fY ( z  x) dx, for -   z  
0
Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 23
 Central Limit Theorem

The Central Limit Theorem states that whenever a random

sample (X1, X2,.. Xn) of size n is taken from any distribution
with expected value E[Xi] =  and variance Var(Xi) =  2,
where i =1,2,..,n, then their arithmetic mean is defined by

1 n
Sn   X i
n i 1

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 24
 Central Limit Theorem

 The sample mean is approximated to a normal

distribution with

E[Sn] = , and

Var(Sn) =  2 / n.
 The larger the value of the sample size n, the
better the approximation to the normal.
 This is very useful when inference between
signals needs to be considered.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 25
 Poisson Arrival Model

 A Poisson process is a sequence of events

“randomly spaced in time”.
 For example, customers arriving at a bank and
Geiger counter clicks are similar to packets
arriving at a buffer.
 The rate  of a Poisson process is the average
number of events per unit time (over a long time).

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 26
 Properties of a Poisson Process
 Properties of a Poisson process
 For a time interval [0, t] , the probability of n arrivals in
t units of time is
(t ) n  t
Pn (t )  e
n!
 For two disjoint (non overlapping ) intervals (t1, t2) and
(t3, t4), (i.e. , t1 < t2 < t3 < t4), the number of arrivals in
(t1, t2) is independent of arrivals in (t3, t4)

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 27
 Interarrival Times of Poisson Process
 Interarrival times of a Poisson process

We pick an arbitrary starting point t0 in time . Let
T1 be the time until the next arrival. We have
P(T1 > t) = P0(t) = e -t

Thus the cumulative distribution function of T1 is
given by
FT1(t) = P(T1≤ t) = 1 – e -t

The pdf of T1 is given by
fT1(t) = e -t
Therefore, T1 has an exponential distribution with
mean rate .
Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 28
 Exponential Distribution

 Similarly T2 is the time between first and second

arrivals,we define T3 as the time between the second
and third arrivals, T4 as the time between the third
and fourth arrivals and so on.
 The random variables T1, T2, T3… are called the
interarrival times of the Poisson process.
 T1, T2, T3,… are independent of each other and each
has the same exponential distribution with mean
arrival rate .

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 29
 Memoryless and Merging Properties
 Memoryless property
 A random variable X has the property that “the future is
independent of the past” i.e., the fact that it hasn't
happened yet, tells us nothing about how much longer it
will take before it does happen.
 Merging property
 If we merge n Poisson processes with distributions for the
inter arrival times
1- e- λit where i = 1, 2, …, n
into one single process, then the result is a Poisson process
for which the inter arrival times have the distribution 1- e -t
with mean
 = 1 + 2 +..+ n..
Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 30
 Basic Queuing Systems
 What is queuing theory?
 Queuing theory is the study of queues (sometimes
called waiting lines).
 Can be used to describe real world queues, or more
abstract queues, found in many branches of computer
science, such as operating systems.
 Basic queuing theory
Queuing theory is divided into 3 main sections:
 Traffic flow

 Scheduling

 Facility design and employee allocation

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 31
 Kendall’s Notation
 D.G. Kendall in 1951 proposed a standard
notation for classifying queuing systems into
different types. Accordingly the systems were
described by the notation A/B/C/D/E where:

A Distribution of inter arrival times of customers

B Distribution of service times
C Number of servers
D Maximum number of customers in the system
E Calling population size

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 32
 Kendall’s notation

A and B can take any of the following distributions types:

M Exponential distribution (Markovian)

D Degenerate (or deterministic) distribution
Ek Erlang distribution (k = shape parameter)
Hk Hyper exponential with parameter k

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 33
 Little’s Law

 Assuming a queuing environment to be operating

in a stable steady state where all initial transients
have vanished, the key parameters characterizing
the system are:
  – the mean steady state consumer arrival
 N – the average no. of customers in the system
 T – the mean time spent by each customer in the system
which gives
N = T

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 34
 Markov Process

 A Markov process is one in which the next state

of the process depends only on the present state,
irrespective of any previous states taken by the
process.
 The knowledge of the current state and the
transition probabilities from this state allows us
to predict the next state.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 35
 Birth-Death Process
 Special type of Markov process
 Often used to model a population (or, no. of jobs in
a queue).
 If, at some time, the population has n entities (n
jobs in a queue), then birth of another entity (arrival
of another job) causes the state to change to n+1.
 On the other hand, a death (a job removed from the
the queue for service) would cause the state to
change to n-1.
 Any state transitions can be made only to one of the
two neighboring states.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 36
 State Transition Diagram

0 1 2 n-2 n-1 n n+1

0 1 2 …… n-1 n n+1 …
1 2 3 n-1 n n+1 n+2

The state transition diagram of the continuous birth-death process

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 37
 M/M/1/ or M/M/1 Queuing System

 When a customer arrives in this system it will be

served if the server is free. Otherwise the customer
is queued.
 In this system customers arrive according to a
Poisson distribution and compete for the service in
a FIFO (first in first out) manner.
 Service times are independent identically
distributed (IID) random variables, the common
distribution being exponential.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 38
 Queuing Model and State Transition Diagram

 

Queue Server

The M/M/1/ queuing model

      
0 1 2 …… i-1 i i+1 …
      

The state transition diagram of the M/M/1/ queuing system

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 39
 Equilibrium State Equations
 If mean arrival rate is  and mean service rate is ,
i = 0, 1, 2.. be the number of customers in the
system and P(i) be the state probability of the
system having i customers.
 From the state transition diagram, the equilibrium state
equations are given by

P(0) P(1), i 0,

(   ) P (i ) P (i  1)  P (i  1), i 1.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 40
 Traffic Intensity

 We know that the P(0) is the probability of server

being free. Since P(0) > 0, the necessary condition
for a system being in steady state is,

  1

This means that the arrival rate cannot be more
than the service rate, otherwise an infinite queue
will form and jobs will experience infinite service
time.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 41
 Queuing System Metrics

  = 1 – P(0), is the probability of the server being

busy. Therefore, we have
P(i) = i(1- )
 The average number of customers in the system is

Ls =  
 The average dwell time of customers is
1
Ws =  

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 42
 Queuing System Metrics
 The average queuing length is
 2 2
Lq   (i  1) P(i )  
i 1 1    (   )

 The average waiting time of customers is

Lq 2 
Wq   
  (1   )  (    )

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 43
 M/M/S/ Queuing Model

S
.
 . S

2
Queue
1

Servers

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 44
 State Transition Diagram

      
0 1 2 …… S-1 S S+1 …
 2 3 (S-1) S S S

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 45
 Queuing System Metrics
 The average number of customers in the system is

 S P (0)
Ls  iP (i )  
i 0 S ! (1   ) 2

 The average dwell time of a customer in the system is

given by

 S P ( 0)
LS 1
WS   
  S .S!(1   ) 2

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 46
 Queuing System Metrics
 The average queue length is
S 1

P ( 0) 
Lq  (i  S ) P (i ) 
i s ( S  1)! ( S   ) 2

 The average waiting time of customers is

 S P (0)
Lq
Wq  
 S .S!(1   ) 2

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 47
 M/G/1/ Queuing Model

 We consider a single server queuing system whose

arrival process is Poisson with mean arrival rate .
 Service times are independent and identically
distributed with distribution function FB and pdf fb.
 Jobs are scheduled for service as FIFO.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 48
 Basic Queuing Model

 Let N(t) denote the number of jobs in the system

(those in queue plus in service) at time t.
 Let tn (n= 1, 2,..) be the time of departure of the nth
job and Xn be the number of jobs in the system at
time tn, so that
Xn = N (tn), for n =1, 2,..
 The stochastic process can be modeled as a
discrete Markov chain known as imbedded
Markov chain, which helps convert a non-
Markovian problem into a Markovian one.

Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 49
 Queuing System Metrics
 The average number of jobs in the system, in the steady state is
2 E[ B 2 ]
E[ N ]   
2(1   )
 The average dwell time of customers in the system is
E[ N ] 1 E[ B 2 ]
Ws   
  2(1   )
 The average waiting time of customers in the queue is
E[ N ] Wq  
 Average waiting time of customers in the queue is
E[ B 2 ]
Wq 
2(1   )
 The average queue length is
2 E[ B 2 ]
Lq 
2(1   )
Copyright © 2002, Dr. Dharma P. Agrawal and Dr. Qing-An Zeng. All rights reserved. 50