Stochastic Processes Flashcards
(A∪B)’
A’∩B’
(A∩B)’
A’∪B’
(A∪B)∩C
(A∩C)∪(B∩C)
(A∩B)∪C
(A∪C)∩(B∪C)
Ratio test
Σa_n
L=lim n→∞ |a_n+1| / |a_n|
L < 1 ABSOLUTELY CONVERGENT
L > 1 DIVERGENT
L = 1 UNKNOWN
RV ‘X’ is normally distributed, notation
X ~ N(μ,σ²)
Var[aX]
= a²Var[X]
λ_eff
λ_eff = Σ(n=0) λ_n ⋅ P_n
What should you be careful of when drawing the steady state Diagram for a M/M/2 model?
μ_1
The rate of μ_1 will be less that μ_2 since one server will be idle.
Accessible states
State j is accessible from state i if
∃n>0 : (T^n)_ij > 0
Communicating states
States i and j communicate with each other if they are accessible to each other
Subchain
Equivalence classes of communicating states
Irreducible chain
A chain that cannot be split into further subchains
Absorbing state
State i is absorbing if T_ii = 1
Periodic state
State i has minimal period k ≥ 2 if
P( X_n = i | X_0 = i ) = 0 IF n =/= k, 2k, 3k, …
P( X_n = i | X_0 = i ) > 0 IF n = k, 2k, 3k, …
Aperiodic state
State i is not periodic, then it is aperiodic. It is possible to find times n1, n2 s.t. (T^n1)_ii, (T^n2)_ii > 0 AND gcd(n1,n2) = 1
f_i
Probability of eventual return to state i
f_i ^(n)
Probability of first return to state i at time n
How to determine if a state is transient or recurrent?
f_i = 1 RECURRENT
f_i < 1 TRANSIENT
How to determine if a state is positively or null recurrent?
μ_i < ∞ POSITIVELY RECURRENT
μ_i = ∞ NULL RECURRENT
Ergodic chain
All states are
Aperiodic &
Positively recurrent
θ_i in Simple Random walks
Probability of entering a state in W given that we start in state i∉A
Z = X1 + X2 + … + XN
PGF of Z
G_Z(θ) = G_N( G_X(θ) )
When is e=1, and e<1?
(1) e = 1 when μ_X ≤ 1
(2) e < 1 when μ_X > 1
What conditions in Poisson processes question requires the use of the binomial?
Poisson process
n events have happened in time T
X ~ the number of events by time t
X ~ B( n , t/T )
When can you also use the solution to P( N(t) = k )?
P( N(t) ≤ k ) or P( N(t) ≥ k )
P( N(t) ≤ k )
P( S_k > t )
P( S_k ≤ t )
P( S_k > t ) = P( N(t) < k ) = P( N(t) ≤ k-1 )
P( S_k ≤ t ) = P( N(t) ≥ k ) = 1 - P( N(t) ≤ k-1 )
Cov( X, Y )
Cov( X, Y ) = E[XY] - E[X]E[Y]
Tower Law
E[E[ X|Y ]] = E[X]
outer expectation w.r.t. y
Poisson Process
The intervals of time between successive events are independent and follow an exponential distribution
(inter-event times are iid)
X ~ Po( λ )
What is E[X]?
E[X] = λ
Also Var[X] = λ
T ~ Exp( λ )
What is E[T]?
E[T] = 1/λ
Define MGFs
M_X(t) = E[ exp^(tX) ]
Define PGFs
G_X(θ) = E[ θ^X ]