Information Technology Reference
In-Depth Information
of new numerical methods have been proposed to compute the limit distribution
and the expected first passage times approximately in reasonable time [6].
In this paper we will describe a different method to compute the distribu-
tions. Instead of using the full distribution, we will approximate the distribution
by products of marginal distributions using a small number of parame-
ters. Our ultimate goal is to characterize the results of micro-simulations by a
probabilistic analysis.
The deterministic automaton with
p(
x
;t)
has very complex behavior. If
n
cannot be divided by 3 then the automaton has no attractors at all, but only
cycles. Thus this automaton belongs to
class III
defined by Wolfram [16].
For
wehave stochastic automata fulfilling the assumptions of
theorem 1. It has a unique stationary distribution, depending only on
and
.
How do the automata behave if we continuously increase
from 0 to 1? What
happens on the transition from
to
?
4.1Approximations of the Probability Distribution of 1-D SCA
For notational convenience we set
. We will
now derive difference equations involving uni-variate, bi-variate, and tri-variate
marginal distributions only. We have by definition for the von Neumann neigh-
borhood
,and
(
t
(
t
)
(6)
i
1
i
1
i
1
;
The conditional distribution
is uniquely defined by the tran-
sitions of the cellular automaton, in our case by the voter model with parameters
i
1
p
(
j
. But on the right hand side tri-variate marginals appear. For these we
obtai
p(
i
1
;
i
;
i+1
)=
and
(7)
i
1
i
2
i
2
;
i
1
i
2
;
i
1
;
i
;
i+1
)
Thus now marginal distribution of size 5 enter. In order to stop this expansion
we approximate the marginal distributions of order 5 by marginal distributions
of order 3. From the definition of the SCA we obtain
(8)
i
1
i
2
;
i
1
;
i
;
i+1
)=p(
i
1
j
i
2
;
i
1
;
i
)
i
1
)
From the theory of graphical models we obtain the approximation
(9)