Please enable JavaScript.
Coggle requires JavaScript to display documents.
MSOWeek9 - Coggle Diagram
MSOWeek9
-
Classification of DTMC
reducible vs irreducible
if one can reach any state j from any i (including itself), it is said to be irreducible (in k steps)
for the no of steps, k, give the min no required to go from the furthest state to any other state.
-
however, if lets say you COMPLETELY CANNOT reach state k from state i at all (there exists at least 1 prob of 0) then its reducible
if the row of the matrix has 0s, it doesnt mean it is reducible, as it can take diff steps to go to any other state. So for eg: the prob of going from state 0 to state 3 is 0. but 0 - 1 -2 - 3 so this will still enable it to be considered irreducible
periodicity
as long as prob of visiting state i again is non zero, it is periodic (after d, 2d, 3d steps)
-
find the minimum period (d), dont care about the probability
1 - 2 - 1: d = 2
1 - 2 - 3 - 2 - 1: d = 4
choose the min d, so d = 2
if you can go from state i to itself with one step P(i-i) > 0 or PERIOD IS 1, it is aperiodic
recurrence
recurrent
probability is 100% that you will revisit state i again for any state i --> you can sum the columns for some matrices, and see if you get 1
-
-
transient
the probability of revisiting state i again is uncertain, not guaranteed at 100%. gambling eg: if you start at 0, prob of getting back 0 is not 100%
for recurrence, note that you always use n equals to the minimum number of returning steps
if the row has 0, it doesnt mean that the DTMC is not recurrent, because you can take k steps (like 1 - 2 - 1, or 1 - 2 - 3 - 2 -1 ) before you return to the original state
important points
-
if DTMC has infinitely many steps, it doesnt mean it is transient, it could be recurrent too
is p is large enough, the system will be transient, whereas if p is small enough, it would be recurrent (PROOF LATER)
check that the row sum, when you are filling in your P matrix is always equal to 1
-
theorems
for finite state DTMC, irreducible property guarantees recurrence
for finite state DTMC, recurrence is equal to positive recurrence
-
-
-