Stochastic process fundamentals - Modelling with Generalised Stochastic Petri Nets - page 279

Figure A.6: State transition rate diagram of the two-processor model

A.5.1 Aggregation in Discrete-Time Markov Chains
Consider first a finite, ergodic DTMC { X n ,n = 0, 1, ···} with state space
S = { 1, 2, ··· ,N } , transition probability matrix P, state distribution η(n),
and steady-state distribution η.
Define a partition of S by aggregating states into macrostates A I such that

M

[ \

A J = ∅ ∀ I 6 = J I,J ∈ (1, 2, ··· ,M) S = A I and A I

I=1

(A.55)
A new stochastic sequence { Y n ,n = 0, 1, ···} can be defined on the set of
macrostates, with state space S 0 = { A 1 ,A 2 , ··· ,A M } . In order to determine
whether this new stochastic sequence is an ergodic DTMC, it is necessary
to examine the conditional probabilities

P { Y n+1 = A J | Y n = A I ,Y n−1 = A K , ··· ,Y 0 = A L } (A.56)

If such conditional probabilities only depend on the most recent macrostate
A I , we recognize that { Y n ,n ≥ 0 } is a DTMC, with transition probabilities
(see Fig. A.7)

p 0 IJ (n) = P { Y n+1 = A J | Y n = A I }
Summing over all states i in A I and all states j in A J , we obtain

X X

p 0 IJ (n) = p ij ν i|I (n) (A.57)

i∈A I j∈A J