Information Technology Reference
In-Depth Information
The different behavior of the dynamics of the micro-simulations cannot re-
captured by just looking at the limit distribution. One needs additional informa-
tion. The most important one is the
expected passage time
. It gives the number
of transitions to get from one configuration to another one.
We recall how the
expected passage time
is computed. We label the con-
figurations
by integer numbers
.Let
be the transition matrix of
a Markov process with
different configurations, labeled with
.The
M
=(
m
ij
expected first passage times
from configuration
to configuration
can be
determined from a set of linear equations:
(3)
=0
;
1
i
K
(4)
k
=1
The right-hand side of equation (4) results from
unfolding
the Markov pro-
cess one step. In order to compute the expected first passage time from state
to state
it is sufficient to consider the vector of passage times
.Let
denote the reduced transition matrix resulting from
by deleting row
and column
.By
1
K
1
wedenote the vector consisting
;::: ;
K
1;K
(
of
ones. Translating the above equations in matrix notation and solving
for
leads to:
Theorem 2
The vector of expected first passage times from states
to state
can be computed by the following equation:
1
;::: ;K
1
1
K
1
(5)
^
M
)
=(
I
Theorem 2 shows that the computation of passage times is essentially a matrix
inversion problem. The matrix
is called the
fundamental matrix
.
Several other system characteristics can be expressed as functions of the funda-
mental matrix or its elements [1]. If we are interested in the passage times of a
stationary distribution we have to use
^
M
)
(
I
.
We summarize the results:
The Markov process analysis of CA is restricted
to small
instead of
. For many stochastic cellular automata there exist mathematically a
limit (stationary) distribution. But the stationary distribution is not sufficient to
characterize a Markov process. It characterizes only the long-term behavior. For
the short-term dynamics the passage times are also needed. The computation of
the passage times is very expensive.
It is numerically impossible to compute the exact stationary distribution and
the matrix of the expected passage times. But we want to mention that a number
