PROBABILITY & QUEUING THEORY

UNIT-I (RANDOM VARIABLES)

1)

Discrete random variable:
Arandomvariablewhosesetofpossiblevaluesiseitherfiniteorcountably
infiniteiscalleddiscreterandomvariable.
Eg:(i)LetXrepresentthesumofthenumbersonthe2dice,whentwo
dicearethrown.InthiscasetherandomvariableXtakesthevalues2,3,4,5,6,
7,8,9,10,[Link].
(ii)Numberoftransmittedbitsreceivedinerror.
2)

Continuous random variable:
ArandomvariableXissaidtobecontinuousifittakesallpossiblevalues
betweencertainlimits.
Eg:Thelengthoftimeduringwhichavacuumtubeinstalledinacircuit
functionsisacontinuousrandomvariable,numberofscratchesonasurface,
proportionofdefectivepartsamong1000tested,numberoftransmittedin
error.
3)


[Link]. Discrete random variable Continuous random variable
1
( ) 1
i
i
p x

= = = =
= == =


( ) 1 f x dx


= == =


2
[ [[ [ ] ]] ] ( ) F x P X x = = = =
[ [[ [ ] ]] ] ( ) ( )
x
F x P X x f x dx

= = = = = = = =


3
[ [[ [ ] ]] ] Mean ( )
i i
i
E X x p x = = = = = = = =


[ [[ [ ] ]] ] Mean ( ) E X xf x dx


= = = = = = = =


4
2 2
( )
i i
i
E X x p x ( ( ( ( = == =



2 2
( ) E X x f x dx


( ( ( ( = == =


5
( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) )
2
2
Var X E X E X ( ( ( ( = = = =

( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) )
2
2
Var X E X E X ( ( ( ( = = = =


6
Moment=
r r
i i
i
E X x p ( ( ( ( = == =



Moment= ( )
r r
E X x f x dx


( ( ( ( = == =


7 M.G.F M.G.F
Formulas
[Link]


( (( ( ) )) ) ( )
tX tx
X
x
M t E e e p x ( ( ( ( = = = = = = = =



( (( ( ) )) ) ( )
tX tx
X
M t E e e f x dx


( ( ( ( = = = = = = = =



4) ( (( ( ) )) ) ( (( ( ) )) ) E aX b aE X b + = + + = + + = + + = +
5) ( (( ( ) )) ) ( (( ( ) )) )
2
Var Var aX b a X + = + = + = + =
6) ( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) )
2 2
Var Var aX bY a X b Var Y = + = + = + = +
7) ( (( ( ) )) ) Standard Deviation Var X = == =
8) ( ) ( ) f x F x = == =
9) ( ) 1 ( ) p X a p X a > = > = > = > =
10) ( (( ( ) )) )
( (( ( ) )) )
( (( ( ) )) )
/
p A B
p A B
p B
= == =

, ( (( ( ) )) ) 0 p B
11) IfAandBareindependent,then ( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) ) p A B p A p B = = = = .
12) 1
st
Momentaboutorigin= [ [[ [ ] ]] ] E X = ( (( ( ) )) )
0
X
t
M t
= == =
( ( ( (

(Mean)
2
nd
Momentaboutorigin=
2
E X ( ( ( (

= ( (( ( ) )) )
0
X
t
M t
= == =
( ( ( (


Theco-efficientof
!
r
t
r
=
r
E X ( ( ( (

(r
th
Momentabouttheorigin)
13) Limitation of M.G.F:
i) [Link].
ii) [Link],yetthe
[Link].
iii) ArandomvariableXcanhaveallorsomemoments,[Link]
existexceptperhapsatonepoint.
14) Properties of M.G.F:
i) IfY=aX+b,then ( (( ( ) )) ) ( (( ( ) )) )
bt
Y X
M t e M at = == = .
ii) ( (( ( ) )) ) ( (( ( ) )) )
cX X
M t M ct = == = ,wherecisconstant.
iii) IfXandYaretwoindependentrandomvariablesthen
( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) )
X Y X Y
M t M t M t
+ ++ +
= = = = .
15) P.D.F,M.G.F,MeanandVarianceofallthedistributions:
Sl.
No.
Distributio
n
P.D.F ( ( ) P X x = == = )
M.G.F Mean Variance
1 Binomial x n x
x
nc p q

( (( ( ) )) )
n
t
q pe + ++ +

np npq
2 Poisson
!
x
e
x

( (( ( ) )) )
1
t
e
e

3 Geometric 1 x
q p

(or)
x
q p
1
t
t
pe
qe

1
p

2
q
p

[Link]


4 Negative
Binomial
1
( 1)
k x
k
x k C p p

+ + + +
1
k
t
p
qe
| | | | | | | |
| | | |

\ \ \ \

kq
p

2
kq
p

5 Uniform
1
,
( )
0, otherwise
a x b
f x b a

< < < < < < < <

= == =




( )
bt at
e e
b a t



2
a b + ++ +

2
( )
12
b a

6 Exponential
, 0, 0
( )
0, otherwise
x
e x
f x



> > > > > > > >
= == =



t



1


2
1


7 Gamma 1
( ) , 0 , 0
( )
x
e x
f x x




= < < > = < < > = < < > = < < >


1
(1 ) t




8 Weibull
1
( ) , 0, , 0
x
f x x e x




= > > = > > = > > = > >

16) Memorylesspropertyofexponentialdistribution
( (( ( ) )) ) ( (( ( ) )) ) / P X S t X S P X t > + > = > > + > = > > + > = > > + > = > .

UNIT-II (RANDOM VARIABLES)

1) 1
ij
i j
p = == =

(Discreterandomvariable)
( , ) 1 f x y dxdy


= == =

(Continuousrandomvariable)
2) ConditionalprobabilityfunctionXgivenY, { {{ { } }} }
( (( ( ) )) ) ,
/
( )
i i
P x y
P X x Y y
P y
= = = = = = = = = = = = .
ConditionalprobabilityfunctionYgivenX, { {{ { } }} }
( (( ( ) )) ) ,
/
( )
i i
P x y
P Y y X x
P x
= = = = = = = = = = = = .
{ {{ { } }} }
( (( ( ) )) ) ,
/
( )
P X a Y b
P X a Y b
P Y b
< < < < < < < <
< < = < < = < < = < < =
< << <

3) ConditionaldensityfunctionofXgivenY,
( , )
( / )
( )
f x y
f x y
f y
= == = .
ConditionaldensityfunctionofYgivenX,
( , )
( / )
( )
f x y
f y x
f x
= == = .

[Link]


4) IfXandYareindependentrandomvariablesthen
( , ) ( ). ( ) f x y f x f y = == = (forcontinuousrandomvariable)
( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) ) , . P X x Y y P X x P Y y = = = = = = = = = = = = = = = = = = = = (fordiscreterandomvariable)
5) Jointprobabilitydensityfunction ( (( ( ) )) ) , ( , )
d b
c a
P a X b c Y d f x y dxdy = = = =

.
( (( ( ) )) )
0 0
, ( , )
b a
P X a Y b f x y dxdy < < = < < = < < = < < =


6) MarginaldensityfunctionofX, ( ) ( ) ( , )
X
f x f x f x y dy


= = = = = = = =


MarginaldensityfunctionofY, ( ) ( ) ( , )
Y
f y f y f x y dx


= = = = = = = =


7) ( 1) 1 ( 1) P X Y P X Y + = + < + = + < + = + < + = + <
8) Correlation co efficient (Discrete):
( , )
( , )
X Y
Cov X Y
x y

= == =
1
( , ) Cov X Y XY XY
n
= = = =

,
2 2
1
X
X X
n
= = = =

,
2 2
1
Y
Y Y
n
= = = =


9) Correlation co efficient (Continuous):
( , )
( , )
X Y
Cov X Y
x y

= == =
( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) ) ( , ) , Cov X Y E X Y E X E Y = = = = , ( )
X
Var X = == = , ( )
Y
Var Y = == =
10) IfXandYareuncorrelatedrandomvariables,then ( , ) 0 Cov X Y = == = .
11) ( (( ( ) )) ) ( ) E X xf x dx


= == =

, ( (( ( ) )) ) ( ) E Y yf y dy


= == =

, ( (( ( ) )) ) , ( , ) E X Y xyf x y dxdy


= == =

.
12) Regression for Discrete random variable:
RegressionlineXonYis ( (( ( ) )) )
xy
x x b y y = = = = ,
( (( ( ) )) ) ( (( ( ) )) )
( (( ( ) )) )
2 xy
x x y y
b
y y

= == =




RegressionlineYonXis ( (( ( ) )) )
yx
y y b x x = = = = ,
( (( ( ) )) ) ( (( ( ) )) )
( (( ( ) )) )
2 yx
x x y y
b
x x

= == =




Correlationthroughtheregression, .
XY YX
b b = = = = Note: ( , ) ( , ) x y r x y = == =
[Link]


13) Regression for Continuous random variable:
RegressionlineXonYis ( (( ( ) )) ) ( ) ( )
xy
x E x b y E y = = = = ,
x
xy
y
b r


= == =
RegressionlineYonXis ( (( ( ) )) ) ( ) ( )
yx
y E y b x E x = = = = ,
y
yx
x
b r


= == =
RegressioncurveXonYis ( (( ( ) )) ) ( (( ( ) )) ) / / x E x y x f x y dx


= = = = = = = =


RegressioncurveYonXis ( (( ( ) )) ) ( (( ( ) )) ) / / y E y x y f y x dy


= = = = = = = =


14) Transformation Random Variables:
( ) ( )
Y X
dx
f y f x
dy
= == = (Onedimensionalrandomvariable)
( , ) ( , )
UV XY
u u
x y
f u v f x y
v v
x y


= == =


(Twodimensionalrandomvariable)
15) Central limit theorem (Liapounoffs form)
IfX
1
,X
2
,X
n
[Link][X
i
]=
i
andVar(X
i
)=
i
2
,i
=1,2,nandifS
n
=X
1
+X
2
++X
n
thenundercertaingeneralconditions,S
n

followsanormaldistributionwithmean
1
n
i
i

= == =
= == =

andvariance
2 2
1
n
i
i

= == =
= == =

as
n .
16) Central limit theorem (Lindberg Levys form)
IfX
1
,X
2
,X
n
[Link][X
i
]
=
i
andVar(X
i
)=
i
2
,i=1,2,nandifS
n
=X
1
+X
2
++X
n
thenundercertain
generalconditions,S
n
followsanormaldistributionwithmean n andvariance
2
n as n .
Note:
n
S n
z
n



= == = (fornvariables),
X
z
n



= == = (forsinglevariables)
[Link]
[Link]


UNIT-III (MARKOV PROCESSES AND MARKOV CHAINS)

1) Random Process:
Arandomprocessisacollectionofrandomvariables{X(s,t)}thatare
functionsofarealvariable,namelytimetwheresSandtT.

2) Classification of Random Processes:

Wecanclassifytherandomprocessaccordingtothecharacteristicsoftimet
[Link]
havingvaluesintheranges-<t<and-<x<.

Continuousrandomprocess
Continuousrandomsequence
Discreterandomprocess
Discreterandomsequence
Continuous random process:
IfXandtarecontinuous,thenwecallX(t),aContinuousRandomProcess.
Example: IfX(t)representsthemaximumtemperatureataplaceinthe
interval(0,t),{X(t)}isaContinuousRandomProcess.
Continuous Random Sequence:
ArandomprocessforwhichXiscontinuousbuttimetakesonlydiscretevaluesis
calledaContinuousRandomSequence.
Example: IfX
n
representsthetemperatureattheendofthenthhourofaday,then
{X
n
,1n24}isaContinuousRandomSequence.
Discrete Random Process:
IfXassumesonlydiscretevaluesandtiscontinuous,thenwecallsuchrandom
process{X(t)}asDiscreteRandomProcess.
Example: IfX(t)representsthenumberoftelephonecallsreceivedintheinterval
(0,t)the{X(t)}isadiscreterandomprocesssinceS={0,1,2,3,...}
Discrete Random Sequence:
Arandomprocessinwhichboththerandomvariableandtimearediscreteis
calledDiscreteRandomSequence.
Example: IfX
n
representstheoutcomeofthenthtossofafairdie,the{X
n
:n1}isa
[Link]={1,2,3,...}andS={1,2,3,4,5,6}

3) Condition for Stationary Process: [ [[ [ ] ]] ] ( ) Constant E X t = == = , [ [[ [ ] ]] ] ( ) constant Var X t = == = .
Iftheprocessisnotstationarythenitiscalledevolutionary.

4) Wide Sense Stationary (or) Weak Sense Stationary (or) Covariance Stationary:
ArandomprocessissaidtobeWSSorCovarianceStationaryifitsatisfiesthe
followingconditions.
i) Themeanoftheprocessisconstant(i.e) ( (( ( ) )) ) ( ) constant E X t = == = .
ii) Autocorrelationfunctiondependsonlyon (i.e)
[ [[ [ ] ]] ] ( ) ( ). ( )
XX
R E X t X t = + = + = + = +
5) Property of autocorrelation:

(i) ( (( ( ) )) ) ( (( ( ) )) )
2

( ) lim
XX
E X t R



( ( ( ( = == =


(ii)
( (( ( ) )) ) ( (( ( ) )) )
2
( ) 0
XX
E X t R = == =
6) Markov process:
Arandomprocessinwhichthefuturevaluedependsonlyonthepresentvalue
andnotonthepastvalues,[Link]
representedby
1 1 1 1 0 0
( ) / ( ) , ( ) ... ( )
n n n n n n
P X t x X t x X t x X t x
+ + + + + + + +
= = = = = = = = = = = = ( ( ( (

1 1
( ) / ( )
n n n n
P X t x X t x
+ + + + + + + +
= = = = = = = = ( ( ( (

Where
0 1 2 1
...
n n
t t t t t
+ ++ +

7) Markov Chain:
Ifforall n,
1 1 2 2 0 0
/ , , ...
n n n n n n
P X a X a X a X a

= = = = = = = = = = = = = = = = ( ( ( (
1 1
/
n n n n
P X a X a

= = = = = = = = = = = = ( ( ( (

thentheprocess { {{ { } }} }
n
X , 0,1, 2, ... n = == = [Link]
0 1 2
, , , ... , ...
n
a a a a arecalledthestatesofthemarkovchain.
8) Transition Probability Matrix (tpm):
WhentheMarkovChainishomogenous,theonesteptransitionprobabilityis
denotedbyP
ij
.ThematrixP={P
ij
}iscalledtransitionprobabilitymatrix.
9) Chapman Kolmogorov theorem:
IfPisthetpmofahomogeneousMarkovchain,thenthensteptpmP
(n)
is
equaltoP
n
.(i.e)
( )
n
n
ij ij
P P ( ( ( ( = == =

.
10) Markov Chain property:If ( (( ( ) )) )
1 2 3
, , = = = = ,then P = = = = and
1 2 3
1 + + = + + = + + = + + = .
11) Poisson process:
If ( ) X t representsthenumberofoccurrencesofacertaineventin (0, ) t ,then
thediscreterandomprocess { {{ { } }} } ( ) X t iscalledthePoissonprocess,providedthe
followingpostulatesaresatisfied.

[Link]


(i) [ [[ [ ] ]] ] ( (( ( ) )) ) 1 occurrence in ( , ) P t t t t O t + = + + = + + = + + = +
(ii) [ [[ [ ] ]] ] ( (( ( ) )) ) 0 occurrence in ( , ) 1 P t t t t O t + = + + = + + = + + = +
(iii) [ [[ [ ] ]] ] ( (( ( ) )) ) 2 or more occurrences in ( , ) P t t t O t + = + = + = + =
(iv) ( ) X t isindependentofthenumberofoccurrencesoftheeventinany
interval.
12) Probability law of Poisson process: { {{ { } }} }
( (( ( ) )) )
( ) , 0,1, 2, ...
!
n
t
e t
P X t n n
n



= = = = = = = = = = = =
Mean [ [[ [ ] ]] ] ( ) E X t t = == = ,
2 2 2
( ) E X t t t ( ( ( ( = + = + = + = +

, [ [[ [ ] ]] ] ( ) Var X t t = == = .

UNIT-IV (QUEUEING THEORY)

nNumberofcustomersinthesystem.
Meanarrivalrate.
Meanservicerate.
n
P SteadyStateprobabilityofexactlyncustomersinthesystem.
q
L Averagenumberofcustomersinthequeue.
s
L Averagenumberofcustomersinthesystem.
q
W Averagewaitingtimepercustomerinthequeue.
s
W Averagewaitingtimepercustomerinthesystem.

Model I (M / M / 1): ( / FIFO)

1) ServerUtilization



= == =
2) ( (( ( ) )) ) 1
n
n
P = = = = (P
0
nocustomersinthesystem)
3)
1
s
L


= == =


4)
2
1
q
L


= == =


5)
( (( ( ) )) )
1
1
s
W

= == =


[Link]


6)
( (( ( ) )) ) 1
q
W


= == =


7) Probabilitythatthewaitingtimeofacustomerinthesystemexceedstis
( )
( )
t
s
P w t e

> = > = > = > = .
8) Probabilitythatthequuesizeexceedstis ( (( ( ) )) )
1 n
P N n
+ ++ +
> = > = > = > = where
1 n t = + = + = + = + .
Model II (M / M / C): ( / FIFO)
1)
s



= == =
2)
( (( ( ) )) ) ( (( ( ) )) )
( (( ( ) )) )
1
1
0
0
! ! 1
n s
s
n
s s
P
n s




= == =
( ( ( (
( ( ( ( = + = + = + = +

( ( ( (



3)
( (( ( ) )) )
( (( ( ) )) )
1
0 2
1
. !
1
s
q
s
L P
s s


+ ++ +
= == =


4)
s q
L L s = + = + = + = +
5)
q
q
L
W

= == =
6)
s
s
L
W

= == =
7) Theprobabilitythatanarrivalhastowait: ( (( ( ) )) )
( (( ( ) )) )
( (( ( ) )) )
0
! 1
s
s
P N s P
s


= = = =


8) Theprobabilitythatanarrivalenterstheservicewithoutwaiting=1P(an
arrivalhattowait)= ( (( ( ) )) ) 1 P N s
9) ( (( ( ) )) )
( 1 )
0
( ) 1
1
!(1 )( 1 )
s t s s
t
s e
P w t e P
s s s






( ( ( (


> = + > = + > = + > = +
` ` ` `


) ) ) )

Model III (M / M / 1): (K / FIFO)

1)



= == =
[Link]


2)
0 1
1
1
k
P


+ ++ +

= == =

(Nocustomer)
3) ( (( ( ) )) )
0
1 P = = = = (effectivearrivalrate)
4)
( (( ( ) )) )
1
1
1
1 1
k
s k
k
L



+ ++ +
+ ++ +
+ ++ +
= = = =


5)
q s
L L



= = = =
6)
s
s
L
W

= == =


7)
q
q
L
W

= == =


8) [ [[ [ ] ]] ]
0
a customer turned away
k
k
P P P = = = = = = = =
Model IV (M / M / C): (K / FIFO)
1)
s



= == =
2)
( (( ( ) )) ) ( (( ( ) )) )
1
1
0
0
! !
n s
s k
n s
n n s
s s
P
n s





= = = = = = = =
( ( ( (
( ( ( ( = + = + = + = +
( ( ( (



3)
( (( ( ) )) )
( (( ( ) )) )
0
0
,
!
,
!
n
n
n
n s
s
P n s
n
P
s
P s n k
s s






= == =

4) Effectivearrivalrate: ( (( ( ) )) )
1
0
s
n
n
s s n P

= == =
( ( ( (
= = = =
( ( ( (



5)
( (( ( ) )) ) ( (( ( ) )) )
( (( ( ) )) )
( (( ( ) )) )
1
0 2
1
! 1
1
s k s
k s
q
s k s
L P
s





+ + + +
( ( ( (


( ( ( ( = = = =

( ( ( (


6)
s q
L L



= + = + = + = +
7)
q
q
L
W

= == =


[Link]


8)
s
s
L
W

= == =


UNIT-V (NON MARKOVIAN & QUEUEING NETWORK)

1) Pollaczek Khintchine formula:
( (( ( ) )) )
[ [[ [ ] ]] ]
2
2
( ) ( )
( )
2 1 ( )
S
Var t E t
L E t
E t



( ( ( (
+ ++ +

= + = + = + = +


(or)
( (( ( ) )) )
2 2 2
2 1
S
L



+ ++ +
= + = + = + = +


2) Littles formulas:
( (( ( ) )) )
2 2 2
2 1
S
L



+ ++ +
= + = + = + = +


q S
L L = = = =
S
S
L
W

= == =
q
q
L
W

= == =
3) Series queue (or) Tandem queue:
Thebalanceequation
00 2 01
P P = == =
1 10 00 2 11
P P P = + = + = + = +
01 2 01 1 10 2 1 b
P P P P + = + + = + + = + + = +
1 11 2 11 01
P P P + = + = + = + =
2 1 1 11 b
P P = == =
Condition
00 10 01 11 1
1
b
P P P P P + + + + = + + + + = + + + + = + + + + =
4) Open Jackson networks:
i) Jacksonsflowbalanceequation
1
k
j j i ij
i
r P
= == =
= + = + = + = +


[Link]


Whereknumberofnodes,r
j
customersfromoutside
ii) Jointsteadystateprobabilities
( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) ) ( (( ( ) )) )
1 2
1 2 1 1 2 2
, , ... 1 1 ... 1
k
n n n
k k k
P n n n = = = =
iii) Averagenumberofcustomersinthesystem
1 2
1 2
...
1 1 1
k
S
k
L


= + + + = + + + = + + + = + + +


iv) Averagewaitingtimeofacustomersinthesystem
S
S
L
W

= == = where
1 2
...
k
r r r = + + + = + + + = + + + = + + +
5) Closed Jackson networks:
Intheclosednetwork,therearenocustomersfromoutside,therefore 0
j
r = == =
then
i) TheJacksonsflowbalanceequation
1
k
j i ij
i
P
= == =
= == =

0
j
r = == =
(or)
( (( ( ) )) ) ( (( ( ) )) )
11 12 1
2 21 22
1 2 1 2
1 2
...
...
... ...
...
k
k
k k
k k kk
P P P
P P P
P P P

| | | | | | | |
| | | |
| | | |
= == =
| | | |
| | | |
| | | |
\ \ \ \


ii) Ifeachnodessingleserver
( (( ( ) )) )
1 2
1 2 1 2
, , ... ...
k
n n n
k N k
P n n n C = == =
Where
1 2
1 2
1
1 2
...
...
k
k
n n n
N k
n n n N
C

+ + + = + + + = + + + = + + + =
= == =


iii) Ifeachnodeshasmultipleservers
( (( ( ) )) )
1 2
1 2
1 2
1 2
, , ... ...
k
n n n
k
k N
k
P n n n C
a a a

= == =
Where
1 2
1 2
1 1 2
...
1 2
...
k
k
n n n
k
N
n n n N
k
C
a a a


+ + + = + + + = + + + = + + + =
= == =


[Link]


! ,
! ,
i i
i i i
i
n s
i i i i
n n s
a
s s n s

< << <

= == =

[Link]