Page 133 - A First Course In Stochastic Models

THEORETICAL CONSIDERATIONS 125

The states are numbered or renumbered as i = 1, . . . , N. The algorithm uses the
following four rules:

(a) State i is absorbing if and only if b ii = 1 and b ij = 0 for j = i.
(b) If state j is absorbing and b ij = 1, then state i is transient.
(c) If state j is transient and b ij = 1, then state i is transient.
(d) If state i communicates with state j and state j communicates with state k,
then state i communicates with state k.

The goal of the algorithm is to find all recurrent subclasses and the set of transient
states. The algorithm rules (a), (b), (c) and (d). In particular, make repeated use of
rule (d) is used to reduce the size of the Boolean matrix B whenever possible. The
algorithm works using the following steps:
Step 1. Initialize the set T (i) := {i} for any state i. Find all absorbing states by
using rule (a) and classify T (i) = {i} as a recurrent subclass for each absorbing
state i. Classify any state i such that b ij = 1 for some absorbing state j as a
transient state.
Step 2. If all states are classified, then stop; otherwise, go to step 3.
Step 3. Take an unclassified state i 0 . Since state i 0 is not absorbing, there is another
= 1). Continuing
state i 1 (say) that can be reached from state i 0 in one step (i.e. b i 0 i 1
in this way, construct a chain of states i 0 , i 1 , . . . until one of the following two
exclusive possibilities occurs:
• A transient state i s is found. Then all states in T (i 0 ) ∪ T (i 1 ) ∪ . . . ∪ T (i s−1 ) are
classified as transient according to rule (c).
• A state i s is found that was already encountered during the development of the
chain, i.e. i s = i r for some r < s. Go to step 4.

Step 4. The circuit of communicating states i r , . . . , i s is replaced by a single aggre-
gated state i r and the Boolean matrix B is adjusted accordingly. This is done as
follows:

• Replace column i r by the union of the columns i r , . . . , i s−1 and replace row i r
by the union of the rows i r , . . . , i s−1 (the union of two Boolean vectors x and y
to a Boolean vector z is defined by z i = 0 if x i = y i = 0 and z i = 1 otherwise).
• Delete the row i k and the column i k for k = r + 1, . . . , s − 1.
• Let T (i r ) := T (i r ) ∪ T (i r+1 ) ∪ . . . ∪ T (i s−1 ).

Having done this, there are two possibilities:

• State i r is absorbing for the new Boolean matrix B. Then T (i r ) is classified as
a recurrent subclass of states. Classify any state that can reach the set T (i r ) in
one step as a transient state (rule (b)). Go to step 2.