Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessA stochastic process is a function whose values are random variables The classification of a random process depends on different quantities–state space–index (time) parameter–statistical dependencies among the random variables X(t) for different values of the index parameter t.1Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessState Space–the set of possible values (states) that X(t) might take on.–if there are finite states => discrete-state process or chain–if there is a continuous interval => continuous processIndex (Time) Parameter–if the times at which changes may take place are finite or countable, then we say we have a discrete-(time) parameter process.–if the changes may occur anywhere within a finite or infinite interval on the time axis, then we say we have a continuous-parameter process.2Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessIn 1907 A.A. Markov published a paper in which he defined and investigated the properties of what are now known as Markov processes.A Markov process with a discrete state space is referred to as a Markov ChainA set of random variables forms a Markov chain if the probability that the next state is S(n+1) depends only on the current state S(n), and not on any previous states3Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessStates must be –mutually exclusive–collectively exhaustiveLet Pi(t) = Probability of being in state Si at time t. Markov Properties–future state prob. depends only on current state»independent of time in state»path to state4Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessAssume exponential failure law with failure rate λ.Probability that system failed at t + Δt, given that is was working at time t is given bywithwe get5Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessFor small Δt 106Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessLet P(transition out of state i in Δt) = Mean time to transition (exponential holding times) If λ’s are not functions of time, i.e. if –homogeneous Markov Chain7Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessAccessibility–state Si is accessible from state Sj if there is a sequence of transitions from Sj to Si.Recurrent State–state Si is called recurrent, if Si can be returned to from any state which is accessible from Si in one step, i.e. from all immediate neighbor states.Non Recurrent–if there exists at least one neighbor with no return path.8Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov Processsample chainWhich statesare recurrentor non-recurrent?9Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessClasses of States–set of states (recurrent) s.t. any state in the class is reachable from any other state in the class.–note: 2 classes must be disjoint, since a common state would imply that states from both classes are accessible to each other.Absorbing State–a state Si is absorbing iff10Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 8Markov ProcessIrreducible Markov Chain–a Markov chain is called irreducible, if the entire system is one class»=> there is no absorbing state»=> there is no absorbing subgraph, i.e. there is no absorbing subset of
View Full Document
Unlocking...