wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Problem: CA with Random Initial Condition
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Federico Caramanica
Eledialab - DISI
Trento - Italy

Registered: Sep 2009
Posts: 2

Problem: CA with Random Initial Condition

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

Old Post 09-17-2009 06:44 PM
Federico Caramanica is offline Click Here to See the Profile for Federico Caramanica Click here to Send Federico Caramanica a Private Message Edit/Delete Message Reply w/Quote
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 113

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

Old Post 09-18-2009 01:58 PM
Todd Rowland is offline Click Here to See the Profile for Todd Rowland Click here to Send Todd Rowland a Private Message Click Here to Email Todd Rowland Edit/Delete Message Reply w/Quote
Federico Caramanica
Eledialab - DISI
Trento - Italy

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

Old Post 09-19-2009 10:15 AM
Federico Caramanica is offline Click Here to See the Profile for Federico Caramanica Click here to Send Federico Caramanica a Private Message Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives