Information Technology Reference
In-Depth Information
The time evolution of the distribution is given for one step by the equation
(1)
0
;t ) p ( x
p ( x ;t +1) =
p ( x ;t +1j x
;t )
defines the global transition matrix. It is of dimen-
sion
. The global transition probabilities can easily be computed from the
local transition rules of the automaton.
( p ( x ;t +1j x
;t ))
M ( t )
Definition 2 The stochastic process is a Markov process if
is independent
of
.
M ( t )
Thus CA are Markov processes. For a Markov process we have
(2)
t
p( x ;0)
p( x ;t)=M
This is the exact solution of our problem. Unfortunately it works only for
small
, because otherwise the dimension of the matrix is too large for practical
computations. There exist one major result.
Theorem 1 If all entries of
are greater than 0, then the stochastic CA has a
unique limit distribution. It is given by the eigenvector belonging to the eigen-
value
.The limit distribution is independent from the initial distribution.
The proof is based on the theorem of Frobenius-Perron .
The relationship between the results of micro-simulations and of the stochas-
tic analysis is very intricate. We will try to explain the problem. The determin-
istic voter model with
does have a stationary distribution,
depending on the initial distribution. It consists mainly of
and
and
. Furthermore there are fixed points consisting of configurations
with contiguous blocks of 0's and 1's. In micro-simulations we would observe
convergence to one of these configurations, depending on the initial configura-
tion. If we now change both
(0 ;::: ; 0)
to small values greater than 0, then the
assumptions of the above theorem are fulfilled. There exists a unique limit dis-
tribution, independent of the initial distribution. The limit distribution now con-
sists of the two configurations
and
from
0 to a small positive value has a huge impact. The stationary distributions are
very different.
The limit distribution of a a purely stochastic automata with
and
only. Thus changing the value of
and
consists of all configurations, the largest frequency have the configurations
and
.
0 : 2
Search WWH ::




Custom Search