Transcript Discrete Event Dynamic Systems — A Short Course

Stochastic Processes
Fundamental
Copyright by Yu-Chi Ho
1
Menu
•
•
•
•
•
•
Why Stochastic Process (SP)?
Specification
Definition of Stochastic Sequence (SS)
Simplify specification
Stochastic Process
Discrete State Space
Copyright by Yu-Chi Ho
2
Specification of Stochastic Processes
• Index (time) parameter
– Continuous-time
– Discrete-time
• State space
– Continuous-state
– Discrete-state
• Statistical dependence
Copyright by Yu-Chi Ho
3
Definition of a Stochastic Sequence (SS)
• An indexed set of random variables, . . .,x-1,
xo, x1, . . . , xi , . . .
• The joint probability density function of
ALL the random variables
p( . . . ., x-1, xo, x1, . . . , xi , . )
• This is usually a great deal of data ( a multidimensional function!)
Copyright by Yu-Chi Ho
4
Simplify Specification
•
•
•
•
•
Purely random sequence
Markov sequence
Gaussian
Gaussian-Markov sequence
Wide/strict sense stationary
Copyright by Yu-Chi Ho
5
Purely Random Sequence
• Assume p( . . . ., x-1, xo, x1, . . . , xi , . ) =
product of all p(xi) for all i, i.e., the random
variables are INDEPENDENT – only one
dimensional functions.
• Such stochastic sequence (SS) are called
purely random sequences or white noise.
• This is the simplest of all stochastic
sequences
Copyright by Yu-Chi Ho
6
Markov Sequence
• Next order of complication, we assume
dependence is only on the immediate past
• p( xo, x1, . . . , xi )=p(xi/ xi-1)p(xi-1/ xi-2)* … *p(x1/
xo)p(xo)
• In other words, the Markov assumption gives
computational advantage, p(xi/ xi-1, . . . , xo) = p(xi/
xi-1).
• Knowing the present separate the past and the
future – the Markov sequences
Copyright by Yu-Chi Ho
7
Gaussian
• We can also specialize the description of the joint
density function, e.g., all the random variables are
jointly Gaussian.
• A set of Gaussian rv’s are completely specified by
the mean vector and the covariance matrix. We
write x=[x1, . . . ,xn]T is N(x , S) where x is an ndimensional mean vector and S an nxn covariance
matrix.
Copyright by Yu-Chi Ho
8
Gaussian-Markov Sequence
• Thus a Gauss-Markov sequence is a stochastic
sequence obeying the conditions of all 3 previous
slides
• It is specified by giving the mean and covariance
of the p(xi/xi-1) for all t and the mean and
covariance of the initial p(xo).
• All joint density function can be derived from
these elementary one and two dimensional
functions
Copyright by Yu-Chi Ho
9
Wide/Strict Sense Stationary
• We can also approximately specifying a SS but
only specifying the mean and covariance of all the
random variables involved
• E[xt]=xt and Var[xt]=st for all t; in addition
E[(xt- xt )(xt- xt )]=R(t,t) = the correlation
function
• A SS is said to be wide sense stationary if R(t,t)
depends only on the difference t-t; it is strict
sense stationary if the joint density function is
invariant w.r.t.translation of the time index.
Copyright by Yu-Chi Ho
10
Stochastic Process
• We have a Stochastic Process instead of a
stochastic sequence
• All conceptual notions remain the same
• Mathematically we must be careful with
“measure-theoretic issues” when dealing
with continuous real variables
• Practically, you need not be concerned
Copyright by Yu-Chi Ho
11
Discrete State Space
•
•
•
•
•
•
Markov Chain
Semi-Markov Process (SMP)
Renewal Process
Markov Process
Random Walk
Birth-Death Process
Copyright by Yu-Chi Ho
12
Markov Chain & SMP
• P(xi+1/xi) becomes a nxn matrix of transition
probabilities, Pij where n is the # of possible
discrete values for x.
• If the time index is discrete and regularly spaced,
then we have a Markov Chain.
• If the time interval between a pair of indexing
variables, fr , is a random variable with successive
samples independently drawn, then we have a
Semi-Markov process (SMP).
Copyright by Yu-Chi Ho
13
Renewal Process & Markov Process
• When for a SMP we emphasize primarily the
indexing rv (regarded as a time of occurrence of
an event) and not the transition of state from event
to event, we have a Renewal Process.
• When the intervals between indexing variables, fr,
are exponentially distributed, we have a Markov
Process.
• Strictly speaking this should be called a doubly
Markov Process. Why? Explain. (Remember the
memoryless triangle?)
Copyright by Yu-Chi Ho
14
Random Walk & Birth-Death Process
• When the elements of the transition
probability matrix Pij=Pi-j, we have a
Random Walk.
• If in addition Pij=0 except when |i-j|=1, we
have a Birth-Death process.
• This is summarized in the following famous
diagram by Kleinrock (next slide)
Copyright by Yu-Chi Ho
15
Kleinrock Diagram
SMP
pij , arbitrary
RW
pij  q j i
f r , arbitrary
MP
pij , arbitrary
f r , arbitrary
f r , memoryless
BD
pij  0 for | j  i | 1
f r , memoryless
Poisson
process
RP
i  
q1  1
Pure birth process f , arbitrary
r
i  0
Figure 2.4 Queueing Theory,v.1, Leonard Kleinrock,
1975
Copyright by Yu-Chi Ho
16
End of the lecture
Copyright by Yu-Chi Ho
17
APPENDIX
Copyright by Yu-Chi Ho
18
Additional and Alternative specification of
Stochastic Processes
• Stationary processes
FX  x0 ,..., xn ; t0 t ,..., tn t   FX  x0 ,..., xn ; t0 ,..., tn 
for any t 
– Wide-sense stationarity
E  X  t    C and E  X  t  X  t  t    g t 
• Independent processes
FX  x0 , , xn ; t0 , , tn   FX0  x0 ; t1 
FXn  xn ; tn 
• Gaussian processes
Copyright by Yu-Chi Ho
19
Additional and Alternative specification of
Stochastic Processes (contd.)
• Markov processes (continuous state space)
P  X  tk 1   xk 1 | X  tk   xk , X  tk 1   xk 1 ,
, X t0   x0 
 P  X  tk 1   xk 1 | X  tk   xk 
for any t  t 
0
1
 tk  tk 1
– Markov chain (discrete state space)
P  X  tk 1   xk 1 | X  tk   xk , X  tk 1   xk 1 ,
, X  t0   x0 
 P  X  tk 1   xk 1 | X  tk   xk 
• Birth-death processes
• Semi-Markov Processes
• Generalized Semi-Markov Processes (GSMP)
Copyright by Yu-Chi Ho
20
Additional and Alternative specification of
Stochastic Processes (contd.)
• Random Walks
• Renewal Processes
• Poisson Processes
n
 t  et , t  0, n  0,1, 2,
– Definition Pn  t  
– Property
n!
• GSMP with Poisson clock structure
Copyright by Yu-Chi Ho
21