Registered: Sep 2009
Posts: 2

Hi.
My name is Federico Caramanica and I 'm a Phd student of the Department
of Information Engineering and Computer Science of the University of Trento, Italy.
My
main research interests are in antenna arrays, wave propagation in urban environment and inverse scattering.

Now, I'm facing the following problem with cellular automata:
- Framework
1) one-dimensional, 2-state cellular automata, with a neighbordhood of
k>=3 cells
2) the initial state of CA (the row at time t=0) is a random binary
array of black/white cells. The probability that a cell is "black/full" is denoted "p" (I call this probability "average density of the CA") and consequentely "q=1-p" is the probability of a "white/empty"
cell.
3) the horizontal extension of the CA is infinite (I don't consider boundary conditions).

- Problem Statement:
my problem is to find out a generic statistical description (analytical or algorithmical) of the average density of black cells "p(t)" in function of the the time "t" given the description of the rule and an initial state probability "p(t=0)=p" (e.g. p=0.6).
I can't use additivity, simmetry, approximations... and, if possible, I need a accurate statistical description for any rule.

Could you please suggest me a way to solve this problem?

I need this result to control my numerical results.

If I don't explain correctly the problem, please tell me!

Thank you for your attention.

Best regards,
Federico Caramanica

__________________
Federico

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

The likelihood of a cell being black, assuming of uncorrelated cells, is the mean field theory estimate. It is easy to figure it out for one step.

See the note on probabilistic estimates on p.953

For a number of steps t>1, one can consider a higher radius rule that performs t steps of the given CA in one step, and perform the probabilistic estimate in the same way. (radius is r)

From the one-step calculation, one can calculate the densities which are stable under iteration. These would be legitimate estimates as long as the assumption of uncorrelated states is valid. (the intersections of the probability function f with y=x where f is increasing).

As the note mentions, this assumption is usually not valid, and there is usually a discernible difference between a theoretically computed value and the actual limiting probabilities.

Specific rules mentioned on pp.953-4 are rules 22, 30, 73, 90, 126, 236.

Report this post to a moderator | IP: Logged

Registered: Sep 2009
Posts: 2

Thank you very much for your help and your attention.

Now I will go into more depth with the "Mean field theory". I hope your advise will be useful for my work.

If I have other questions or problem, I will post again.

Thank you.

Best Regards,

__________________
Federico

Report this post to a moderator | IP: Logged