Transcript Appendix I – The Transform 2 and The Laplace Transform

Appendix II – Probability
Theory Refresher
Leonard Kleinrock, Queueing Systems, Vol I: Theory
Nelson Fonseca,
State University of Campinas, Brazil
Appendix II – Probability Theory
Refresher
• Random event: statistical regularity
• Example: If one were to toss a fair coin four
times, one expects on the average two heads
and two tails.There is one chance in sixteen
that88 no heads will occur. If we tossed the
coin a million times, the odds are better than
10 to 1 that at least 490.000 heads will
occur.
II.1 Rules of the game
• Real-world experiments:
– A set of possible experimental outcomes
– A grouping of these outcomes into classes
called results
– The relative frequency of these classes in many
independent trials of the experiment
Frequency = number of times the experimental
outcome falls into that class, divided by number
of times the experiment is performed
•
Mathematical model: three quantities of
interest that are in one-to-one relation with
the three quantities of experimental world
1. A sample space is a collection of objects
that corresponds to the set of mutually
exclusive exhaustive outcomes of the
model of an experiment. Each object  is
in the set S is referred to as a sample point
2. A family of events  denoted {A, B,
C,…}in which each event is a set of
samples points { }
3. A probability measure P which is an
assignment (mapping) of the events defined
on S into the set of real numbers. The
notation is P[A], and have these mapping
properties:
a) For any event A,0 <= P[A] <=1
(II.1)
b) P[S]=1
(II.2)
c) If A and B are “mutually exclusive” events
then P[A U B]=P[A]+P[B]
(II.3)
• Notation
A   :  not in A   complement
c
  S  null evnt (contains
c
of A
no sample point since S contais all the points)
If AB   , then A and B are said to be mutually e xclusive (or disjoint)
• Exhaustive set of events: a set of events
whose union forms the sample space S
• Set of mutually exclusive exhaustive events
A1 , A2 ,..., An  , which have the properties
Ai A j  
for all i  j
Ai  A2  ...  An  S
• The triplet (S, , P) along with Axioms (II.2)(II.3) form a probability system
• Conditional probability

P A B 
P  AB 
P B 
P B   0
• The event B forces us to restrict attention from the
original sample space S to a new sample space
defined by the event B, since B must now have a
total probability of unity. We magnify the
probabilities associated with conditional events by
dividing by the term P[B]
• Two events A, B are said to be statistically
independent if and only if
P  AB   P  A P  B 
• If A and B are independent
PA | B   PA
• Theorem of total probability
n
P  B    P  Ai B 
i 1
If the event B is to occur it must occur in
conjunction with exactly one of the
mutually exclusive exhaustive events Ai
• The second important form of the theorem
of total probability
P B  
n
 P B A P  A 
i
i
i 1
• Instead of calculating the probability of
some complex event B, we calculate the
occurrence of this event with mutually
exclusive events
P B  
n
n
 P B A P  A    P BA   P B 
i
i 1
i
i
i 1
• Bayes’ theorem
P  Ai B  
P  AB Ai P [ Ai ]
 P AB
n

A j P[ A j ]
j 1
i
Where {A }are
a set of events mutually exclusive
and exhaustive
• Example: You have just entered a casino and
gamble with a twin brother, one is honest and the
other not. You know that you lose with
probability=½ if you play with the honest brother,
and lose with probability=P if you play with the
cheating brother
II.2 Random variables
• Random variable is a variable whose value
depends upon the outcome of a random
experiment
• To each outcome, we associate a real number,
which is in fact the value the random variable
takes on that outcome
• Random variable is a mapping from the points of
the sample space into the (real) line
• Example: If we win the game we win $5, if
we lose we win -$5 and if we draw we win
S
$0.
W
D
L
(1/4)
(3/8)
 5

X ( )   0
 5

(3/8)
W
D
L

Notation
: [ X  x ]   : X ( )  x 
P[X  x]  probabilit
y that X(  ) is equal to x
P[X  - 5 ]  3 8
P[X  0 ]  1 4
P[X  5 ]  3 8
• Probability distribution function (PDF), also
known as the cumulative distribution
function
 X  x    : X ( )  x 

 PDF : F X ( x )  P  X  x 
 Properties
:
Fx ( x )  0
Fx ( )  1
F x (  )  0
F x ( b )  F x ( a )  P[a  X  b] for a  b
Fx (b )  F x ( a )
for
a b
FX ( x)
3
5
1
8
8
1
3
4
8
x
-5
0
+5
P[  2  x  6 ]  5 8
P [1  x  4 ]  0
 At points of discontinu
ity the PDF takes on the upper valu
e
• Probability density function (pdf)

f X ( x) 
FX ( x) 
We have
dF X ( x )
dx

x

f X ( y ) dy
f X ( x )  0 and F X (  )  1 then

 f ( x ) dx  1
• The pdf integrated over an interval gives the
probability that the random variable X lies
in that interval
b
P a  X  b    f X ( x ) dx
a

X
• Distributed random variable
PDF :
1  e   x
FX ( x)  
 0
pdf :
  e  x
f X ( x)  
 0
0 x
x0
0 x
x0
P [ a  x  b ]  F X (b )  F X ( a )  e
P[a  x  b ] 

b
a
 0
f X ( x ) dx  e
 a
 a
e
e
 b
 b
f X (x)
3
1
8
-5
4
0
3
8
+5
• Impulse function (discontinuous)
– Functions of more than one variable

F XY ( x , y )  P [ X  x , Y  y ]

f XY ( x , y ) 
2
d F XY ( x , y )
dxdy
– “Marginal” density function
f X ( x) 


y  
f XY ( x , y ) dy
– Two random variables X and Y are said to be
independent if and only if
f XY ( x , y )  f X ( x ) f Y ( y )
f X 1 X 2 ... X n ( x1 , x 2 ,..., x n )  f X 1 ( x1 ) f X 2 ( x 2 )  f Xn ( x n )
• We can define conditional distributions and
densities

f X Y (x y) 
d
dx
P X  x Y  y  
• Function of one random variable
f XY ( x , y )
fY ( y )
Y  g(X )
Y  Y ( )  g ( X ( ))
• Given the random variable X and its PDF, one
should be able to calculate the PDF for the
variable Y
FY ( y )  P Y  y   P  : g ( X ( ))  y 
 In general cases
n
Y 
X
i 1
i
 For the case of n  2 ,
y  x1  x 2
FY ( y )  P Y  y   P  X 1  X 2  y 
X1
y
y
X1  X 2  y 0
FY ( y ) 

 

X
2


f X 1 X 2 ( x1 , x 2 ) dx 1 dx 2
Due to the independen
ce of X 1 and X 2 we then obtain
the PDF for Y as

y  x2

 f ( x ) dx
FY ( y )  
f
(
x
)
dx
X1
1
1
X2
2
2


 




FY ( y ) 
fY ( y ) 






F X ( y  x 2 ) f X 2 ( x 2 ) dx 2
1
f X 1 ( y  x 2 ) f X 2 ( x 2 ) dx 2
fY ( y )  f X1 ( y )  f X 2 ( y )
fY ( y )  f X1 ( y )  f X 2 ( y )    f X n ( y )
II.3 Expectation
• Stieltjes integrals deal with discontinuities
and impulses
Let F(x) : a nondecreas ing function
 (x) : a continuous
function
{t k } and { k } : two sets of points such that
t k 1   k  t k
and there is a limit | t k  t k 1 | 0
  (
k
k
)[ F ( t k )  F ( t k 1 )] 
  ( x ) dF ( x )
 PDF  F ( x ) and pdf dF ( x )  f ( x )

dF ( x )  f ( x ) dx
• The Stieltjes integral will always exist and therefore it
avoids the issue of impulses
• Without impulses the pdf may not exist
• When impulses are permitted we have
  ( x ) dF ( x )    ( x ) f ( x ) dx
The expectatio


E[ X ]  X  
n of a real random variable


E[ X ]  X  
xdF X ( x )


xf X ( x ) dx
is
The mean or average value of X is
E[ X ] 


0
[1  F X ( x )] dx  
0

F X ( x ) dx
Expeted value - Random function
Y  g(X )
E Y [Y ] 



yf Y ( y ) dy
E Y [ y ]  E X [ g ( X )] 



g ( x ) f X ( x ) dx
• Expectation of the sum of two random variables
E[ X  Y ] 








 
 





( x  y ) f XY ( x , y ) dxdy
xf XY ( x , y ) dxdy 
xf X ( x ) dx 


 



yf Y ( y ) dy
 E [ X ]  E [Y ]
E [ X  Y ]  E [ X ]  E [Y ]

X Y  X Y


yf XY ( x , y ) dxdy
• The expectation of the sum of two random
variables is always equal to the sum of the
expectations of each variable
• This is true even if the variables are dependent
• The expectation operator is a linear operator
E [ X 1  X 2  ...  X n ]  E [ X 1 ]  E [ X 2 ]  ...  E [ X n ]
The question is: what is the probability of your being
playing with the cheating brother since you lost?
P D C L  
P L D C P  D C 
P L D C P  D C   P L D H P  D H


1
p 
2p
2

 1   1  1  2 p  1
p      
 2   2  2 

N!
( N  K )!
 N ( N  1)  ( N  K  1)
 The number
N
by 
K
of combinatio

N!
 
 K ! ( N  K )!
ns of N things
taken K at a time is denoted
E [ XY ] 
E [ XY ] 








 
 
xyf XY ( x , y ) dx dy
xyf X ( x ) f Y ( y ) dx dy  E [ X ] E [Y ]
XY  X Y
– The expected result of the product of variables is equal
to the product of the expected values if the variables
are independent
– Expected value of the product of random functions
E [ g ( X ) h (Y )]  E [ g ( X )] E [ h (Y )]
– nth moment

E[ X ]  X
n

n



n
x f X ( x ) dx
– nth central moment

(X  X )  
n


( x  X ) f X ( X ) dx
n
– The nth central moment can be expressed as a function
of n moments
n k
nk
( X  X )     X (  X )
k 0  k 
n
n
n k
nk
( X  X )     X (  X )

k 0  k 
n
n
n k
nk
    X (  X )
k 0  k 
n
– First central moment = 0
(X  X )  X  X  0
– Second central moment => variance


  (X  X )  X  (X )
2
x
2
2
2
– Standard deviation (central moment)
x 

2
X

X
– Coefficient of variation

CX 
X
• Covariance of two random variables X1 and X2
Cov (X1, X2) = E[(X1 – E[X1]) (X2 – E[X2])]
var (X1 + X2) = var (X1)+var (X2) + 2Cov(X1, X2)
Corr (X1, X2) = Cov (X1, X2) / (1 2)
Normal
Notation
X ~ Nor (  ,  )
2
Range
   X  
Parameters – Scale
 :0 
Parameters – Shape
 :     
Normal
Probability Density Function
f (X ) 
e
1 X  
 

2 


2
2
 1 X   
exp   
 
 
 2 
f (X ) 
 2
2
Normal
=10 =2
=10 =1
Normal
=0 =2
=0 =1
=0 =1
Normal
Normal
Expected Value
E(X )  
Normal
Variance
V (X )  
2
Chebyshev Inequality
P
x  X

x 

x
2
2
Strong Law of Large Numbers
Wn 
Wn  X
1
n
n

xi
i 1
W
2
n

X
n
2
Strong Law of Large Numbers
lim
n 
Wn  X
Central Limit Theorem
n
Zn 
lim
n 

X i  nX
i 1

X
n
P Z n  x     x 
Exponential
Probability Density Function
f ( X )  e
 X
Distribution Function
F(X ) 1 e
 X
Exponential
• Inter arrival time of phone calls
• Inter arrival time of web session
• Duration of on and off periods for
voice models
Heavy-tailed distributions
P Z  x   cx
0  2

x
Heavy- Tailed distributions
• Hyperbolic decay
• Infinite variance
0  2
• Unbounded mean
0  1
• Network context
1  2
Pareto
Notation
X ~ Par ( ,  )
Range
  X  
Parameters – Scale
 :0  
Parameters – Shape
 :0 
Pareto
Distribution Function
 
F ( x)  1   
 x

Pareto
Probability Density Function
  
f (X ) 
 
 X 
f (X ) 

X

 1
 1
Pareto
=1 =1
=1 =2
Pareto
=10 =5
=5 =10
=5 =10
Pareto
Pareto
Expected Value
E(X ) 

 1
1
Pareto
Moments Uncentered
' 
j

j
  j
j
Pareto
• Distribution of file size in Unix
systems
• Duration of on and off periods in data
models (ethernet individual user)
Weibull
Notation
X ~ Wei ( b , c )
Range
0  X  
Parameters – Scale
b:0  b
Parameters – Shape
c:0  c
Weibull
Probability Density Function
f ( X )  cb X
c
f (X ) 
c 1
cX
b
c
c 1
e
(X /b)
c
 X  
exp     
  b  
c
Weibull
Distribution Function
F (x)  1  e
(X /b)
c
 X  
F ( x )  1  exp     
b

 

c
Weibull
b=1 c=1
b=2 c=1
Weibull
b=1 c=2
b=2 c=2
Weibull
b=10 c=5
b=5 c=10
b=25 c=10
Weibull
Weibull
Moments Uncentered
 '  b  [( c  j ) / c ]
j
j
j
c  j 

'  b 
 b  1
 c 


c
j
j
j
Weibull
Expected Value
1  b 1 
 c  1

E ( X )  b
 b 1 
 
 c 

c  c  c 
E(X ) 
b
c
 [1 / c ]
Weibull
Variance
b   2  1  1   
V (X ) 
2         
c  c  c  c   
2
2
b 
1

V (X ) 
2  2 / c     1 / c 

c 
c
2
2
Lognormal
Notation
X ~ Logn (  ,  )
2
Range
0  X  
Parameters – Scale
 :  0
or
m :m  0
Parameters – Shape
 :  0
or
w:w  0
Lognormal
Probability Density Function
 1  ln ( X )    
exp  




 
 2
f (X ) 
2 X
2
2
2
Lognormal
Expected Value
1
E(X )  e
 
2
2
or
E(X )  m w
1


 exp   


2

2
Lognormal
Variance
V (X )  e
2   2
V (X )  e e
2

2
2
e
e

2
2  
2
 1
V ( X )  exp [ 2  ]  exp [ ]  exp [ ]  1
2
or
V ( X )  m w ( w  1)
2
2
Lognormal
=0 =0.5
=0 =0.7
Lognormal
=1 =0.5
=1 =0.7
Lognormal
=0 =0.1
=1 =0.1
Lognormal
=0 =1
=1 =1
=0 =1
Lognormal
Lognormal
• Multiplicative efffect
II.4 Transforms, generating functions and
characteristic function
• Characteristic function of a random variable
x(X(u)) is given by:

 X (u)  Ε [ e
j
juX
]



e
jux
f X ( x ) dx
1
– u – real variable
 X (u) 
e
juX



e
jux
f X ( x ) dx
1
 X (u) 

 X (u)  1


f X ( x ) dx
– Expanding ejux and integrating
 X (u) 



 1  ju X 
f X ( x )[ 1  jux 
( ju )
2!
2
x  ...
2
( jux )
2!
2
 ...] dx
X( 0 )  1
d  X (u)
n
du
– Notation

g
(n)
( x0 ) 
 j X
n
n
u 0
n
d g(x)
dx
n
x  x0
X (0 )  j
(n)
(n)
X
n
n
– Moment generation function

M x (v )  E [e



M
e
vx
(n)
X
vX
f x ( x ) dx
(0)  X
n
]
• Laplace transform of the pdf
– Notation:
A( x )  P[ X  x ]
PDF
a(x)
p .d . f .
*
Transform
A (x)

A ( s )  E [e
*



A
e
*( n )
 sx
 sX
]
a ( x ) dx
( 0 )  (  1) X
n
n
 x ( sj )  MX (  s )  A ( s )
*
n
X
n
 j  X (0)
X
n
 M
X
n
 (  1) A
(n)
(n)
X
(0)
n
*( n )
(0)
– Example
  e  x
f X ( x)  a( x)  
 0
  ju
(v ) 
X
x0

 x (u ) 
M
x0
A (s) 
*

 v

s
 X (0)  M X (0)  A (0)  1
*
X 
X
2
1


2

2
– Probability generating function – discrete variable

G (z)  E[z ] 
X

k
G
(1 )
(1)  X
G
(2)
(1)  X
G (1)  1
2
 X
k
z gk
– Sum of n independent variables
u
xi , Y 

Xi
i 1
 Y (u )  E [ e
E [e
juX 1
 ju  X i 
]  E  e i 1  


u

e
juX
2
 Y (u )  E [ e
juY
e
juX 1
juX
n
]
]E [e
juX
2
] E [ e
 Y ( u )   X ( u ) X ( u )   X ( u )
1
n
2
– xi – Identically distributed
 Y ( u )  [ X ( u )]
n
juX
n
]
– Sum of independent variables
Y  X1  X 2   X n
n2
Y
2
 (X1  X 2)  X1  2 X1X 2  X 2
2
2
2
(Y )  ( X 1  X 2 )  ( X 1 )  2 X 1 X 2  ( X 2 )
2
2
2
2
 Y  Y  (Y )  X 1  ( X 1 )  X 2  ( X 2 )  2 ( X 1 X 2  X 1 X 2 )
2

2
2
x1

2
2
x2
2
2
 2( X 1 X 2  X 1 X 2 )
2
2
– x1 and x2 independent
X1X 2  X1 X 2
Y 
2
2
X1

2
X2
– The variance of the sum of independent random
variables is equal to the sum of variances
Y 
2
2
X1

2
X2
 
2
Xn
– Variable  sum of independent variables and the
number of variables is a random variable
N
Y 

Xi
i 1
– Where N: is a random variable with mean N and
variance X2
– [ Xi ] is independent and identically distributed
– N and [ Xi ] independent
– FY(y) - Compound distribution

Y ( s )  E e

*
N
s  X i
i 1



 s  X i 
  E  e i 1  P [ N  n ]
n0




  E [e
n
 sX 1
] E [e
 sXn
]P[ N  n ]
n0
– [ Xi ] - identically distributed variables

Y ( s )   [ X ( s )] P [ N  n ]
  

n0  
*
*
n
z - transform for N
Y ( s )  N ( X ( s ))
*
*
Y  NX
 Y  N
2
2
X
 (X ) 
2
2
N
II.6. Stochastic process
– To each point of the sample process space S a time
function x is associated => Stochastic process family
 PDF :
F X ( x , t )  P [ X (t )  x ]
 F X ( x , t )  F X 1 X 2  X n ( x1 , x 2 ,  , x n ; t1 , t 2 ,  t n )

 P [ X ( t1 )  x1 , X ( t 2 )  x 2 , X ( t n )  x n ]
 FX ( X ; t   )  FX ( X ; t )
 pdf .

f X ( X ,t) 
FX ( x; t )
X ( t )  E [ X ( t )] 
X



xf X ( x ; t ) dx
– Autocorrelation:
R XX ( t1 , t 2 )  E [ X ( t1 ) X ( t 2 )]





 
x1 x 2 f X 1 X 2 ( x1 , x 2 ; t1t 2 ) dx 1 dx 2
– Wide sense stationary process
X (t )  X
R XX ( t1 , t 2 )  R XX ( t 2  t1 )