CA Stochastic

2 collaborators

Uri Wilensky (Author)

Eytan Bakshy (Author)

WHAT IS IT?

This is a one-dimensional stochastic cellular automaton. (See the CA 1D Elementary model if you are unfamiliar with cellular automata.) Unlike most cellular automata, whose behavior is deterministic, the behavior of a stochastic cellular automaton is probabilistic. Stochastic cellular automata are models of "noisy" systems in which processes do not function exactly as expected, like most processes found in natural systems.

The behavior of these cellular automata tend to be very rich and complex, often forming self-similar tree-like or chaotic behavior. They are capable of mimicking many phenomena found in nature such as crystal growth, boiling, and turbulence.

HOW IT WORKS

At each time step, every cell in the current row evaluates the state of itself and its immediate neighbors to the right and left. There are 8 possible on/off rule configurations for every 3-cell neighborhood, each with a certain probability of turning on the cell below it at the next time step. The rules are applied accordingly, and the next state of the cellular automaton appears in the row directly below, creating a space vs. time view of the cellular automaton's evolution.

HOW TO USE IT

Set up:

SETUP RANDOM initializes the model with a percentage of the cells "on". The percentage on is determined by the DENSITY slider.
SETUP EXAMPLE initializes the rule settings according to the EXAMPLE slider
AUTO-CONTINUE? automatically wraps to the top once it reaches the last row when the switch is on
GO begins running the model with the currently set rule. It runs until it reaches the bottom of the world. If GO is pressed after it has completed, it will wrap to the top and continue.
ON-COLOR & OFF-COLOR set the "on" and "off" cell colors respectively.

Rule Setup: There are 8 sliders, the names of which correspond to cell states. "O" means off, "I" means on. For example, the upper-right slider is called "IIO," corresponding to the state where a cell and its left neighbor is on, and its right neighbor is off. (NOTE: the switch names are composed of the letters "I" and "O", not the numbers zero or one, because NetLogo switches can't have numbers for names.) If this slider is set to 70%, then the following rule is created: when a cell is on, its left neighbor cell is on and its right neighbor cell is off, then there is a 70% chance the cell below it will be set "on" at the next time step, otherwise the cell below it will be set to "off" at the next time step.

Plot: This plot measures two types of entropy, or disorder in a system. Cellular automata can produce patterns with varying degrees of randomness. If a pattern is perfectly random, each subsequence occurs with an equal probability, and the entropy is 1. The more likely certain subsequences occur, the lower the entropy. If a pattern is perfectly ordered, then the entropy is 0. In this plot, 4-cell subsequences ("correlation length") are used to calculate the entropy. The first type of entropy is the spatial topologic entropy, which measures how many subsequences are present. The second type of entropy, spatial metric entropy, measures the probability that all subsequences occur with the same frequency.

Plot Configuration:

PLOT? switches plot on or off
AUTO-CLEAR? if on, the plot is automatically cleared after each complete screen of cellular automata evolution

THINGS TO NOTICE

Why is it a better idea to have a density that isn't too big or too small?

What is the relationship between the cellular automata display and the entropy plot?

How does the size of the black triangles affect the entropy?

What kinds of configurations lead to long lived chaotic behavior?

THINGS TO TRY

You may want to set AUTO-CONTINUE? to 'on' in order to study the long-term behavior of each cellular automaton configuration. Also, if you have a fast enough computer, you may want to increase the size of the world in order to get a better view of the "big picture." If you turn the plot off, it will also increase the speed of your model.

Change the example slider to 1, and click SETUP EXAMPLE. Click GO and experiment with the III slider, running each configuration a couple of times:

What happens when III is set to 0%?
- Why do you think the cellular automaton always ends up in the same uniform, or "absorbing" state?
As you increase III, what happens to the density of the trees that are formed?
- Does this seem to effect the time it takes to reach an absorbing state?
What happens when III is set to 100%?
- It seems very unlikely that this configuration will reach an absorbing state, but is it possible?
- Why or why not?

Change the example slider to 2, and click SETUP EXAMPLE. Click GO and experiment with the IOO slider, running each configuration a couple of times:

Why does this configuration want to have either vertical or horizontal stripes?
What happens when you change IOO to 0% or 100%?
- Why does it always end up producing a majority of horizontal or vertical stripes?
How does changing the OOI slider in conjunction with the IOO slider affect the model?

Change the example slider to 3, and click SETUP EXAMPLE. Click GO and experiment with the IOO slider, running each configuration a couple of times:

As you change IOO, what happens to the outer shape of the cellular automaton?
- What happens to the shape of the triangles inside?
- How is the value of the IOO slider related to the spread of on cells?
- What should IOO be set to if you want perfectly symmetric triangles?
Set IOO to 100%, and experiment with the OOI slider in a similar fashion.
What is the relation between the IOO and OOI slider?

Change the example slider to 4, and click SETUP EXAMPLE. Click GO and experiment with the IOO slider, running each configuration a couple of times:

As you increase IOO, what transition do you see in the structures formed by the cellular automata?
- Why do you think this transition, or "phase change," happens?
Once you get to 100%, notice that the triangles aren't very symmetric.
- Which slider should you move accordingly in order to make the triangles look more symmetric?
Now try moving both sliders together in order to find the point at which the cellular automaton makes its phase transition.

Change the example slider to 5, and click SETUP EXAMPLE Experiment with the OOI and IOO sliders together.

What differences do you notice between the this example and the previous one?
Does either cellular automaton have lower phase transition point with respect to the OOI and IOO sliders?
- If so, what accounts for this difference?

EXTENDING THE MODEL

Often times one might want to change multiple sliders in parallel, while leaving other sliders unchanged. Try automating this process by creating additional switches and sliders.

Can you measure the entropy more accurately by using subsequences greater than 4?

There are many other ways to measure order in a system besides entropy, can you think of any?

Can you make a stochastic cellular automata with more neighbors? For example, the cellular automata might have two neighbors on each side.

Try making a two-dimensional stochastic cellular automaton. The neighborhood could be the eight cells around it, or just the cardinal cells (the cells to the right, left, above, and below).

NETLOGO FEATURES

The plot-entropy procedure makes extensive use of the MAP and FILTER primitives. First, MAP is used to convert a list containing the number of occurrences of each pattern of ON? values to a list of probabilities of each pattern occurring. This is done by dividing each item in the first list by the total number of possible patterns. Since both entropy calculations involve the use of a logarithm, FILTER is used to remove all elements in the list that are equal to 0 so that no errors occur. For calculating the topological entropy, MAP is used to change all the remaining elements in the probability list to 1. When calculating the metric entropy, MAP is used to multiply each element in the probability list by its logarithm. Using MAP and FILTER allows these complex calculations to be done in a clean, compact manner.

RELATED MODELS

CA 1D Elementary - a widely studied deterministic equivalent to this model CA 1D Totalistic - a three color 1D cellular automata Percolation (in Earth Science) - a model demonstrating the percolation of an oil spill using probabilistic rules similar to this model Turbulence (in Chemistry & Physics) - a continuous cellular automata that exhibits phase change behavior similar to this model Ising (in Chemistry & Physics) - a microscopic view of a magnetic field which undergoes phase changes with respect to temperature DLA (in Chemistry & Physics) - a growth model demonstrating how the accumulation of randomly placed particles can lead to complex structures found throughout nature

CREDITS AND REFERENCES

Chate, H. & Manneville, P. (1990). Criticality in cellular automata. Physica D (45), 122-135. Li, W., Packard, N., & Langton, C. (1990). Transition Phenomena in Cellular Automata Rule Space. Physica D (45), 77-94. Wolfram, S. (1983). Statistical Mechanics of Cellular Automata. Rev. Mod. Phys. (55), 601. Wolfram, S. (2002). A New Kind of Science. Champaign, IL: Wolfram Media, Inc.

Thanks to Eytan Bakshy for his work on this model.

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

Wilensky, U. (2003). NetLogo CA Stochastic model. http://ccl.northwestern.edu/netlogo/models/CAStochastic. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

CC BY-NC-SA 3.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

This model was created as part of the projects: PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN CLASSROOMS and/or INTEGRATED SIMULATION AND MODELING ENVIRONMENT. The project gratefully acknowledges the support of the National Science Foundation (REPP & ROLE programs) -- grant numbers REC #9814682 and REC-0126227.

Comments and Questions

Click to Run Model

globals [
  row        ;; current row we are now calculating
  done?      ;; flag set to allow you to press the go button multiple times
  prob-list  ;; list of the probabilities of each pattern occurring
]

patches-own [on?]

;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; SETUP PROCEDURES     ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; setup general working environment.  the other setup procedures call this.

to setup-general
  clear-patches
  set row max-pycor   ;; reset current row
  set done? false
end 

;; setup a random selection of patches in the top row to have on? true

to setup-random
  setup-general
  clear-all-plots
  ;; randomly place cells across the top of the world
  ask patches with [pycor = row]
  [
    set on? ((random-float 100) < density)
    color-patch
  ]
  build-prob-list
  reset-ticks
end 

;; setup the patches to continue a particular model run.  this will copy the bottom
;; row of patches to the top row.

to setup-continue
  let on?-list []

  ;; make sure go has already been called
  if not done?  [ stop ]

  if auto-clear?
  [
    clear-plot
    set-plot-x-range ticks (ticks + world-height)
  ]

  set on?-list map [ [on?] of ?] sort patches with [ pycor = row ]  ;; copy states from bottom row to list
  setup-general
  ask patches with [ pycor = row ]
  [
    set on? item (pxcor + max-pxcor) on?-list  ;; copy states from list to top row
    color-patch
  ]
  set done? false
end 

;; setup the sliders to have specific values that are interesting to study

to setup-example
  if( example = 1 )
    [ set III 0 set IIO 50 set IOI 50 set IOO 50 set OII 50 set OIO 50 set OOI 50 set OOO 0 ]
  if( example = 2 )
    [ set III 0 set IIO 50 set IOI 0 set IOO 50 set OII 50 set OIO 100 set OOI 50 set OOO 100 ]
  if( example = 3 )
    [ set III 0 set IIO 50 set IOI 50 set IOO 66 set OII 50 set OIO 50 set OOI 100 set OOO 0 ]
  if( example = 4 )
    [ set III 0 set IIO 50 set IOI 50 set IOO 66 set OII 50 set OIO 50 set OOI 50 set OOO 0 ]
  if( example = 5 )
    [ set III 0 set IIO 100 set IOI 0 set IOO 66 set OII 100 set OIO 0 set OOI 66 set OOO 0 ]
  set density 25
  setup-random
end 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; RUNTIME PROCEDURES   ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; run the model.  this applies the current rules to the patches with pycor equal to row.
;; if that row of patches is the bottom row and auto-continue? is true, we will setup the
;; model to continue.

to go
   ;; if the end has been reached, continue from the top or stop
  if (row = min-pycor)
  [
    ifelse auto-continue?
    [
       ;; if we are stuck in an absorbing state, there is not reason to continue
       ifelse( ((sum ([true-false-to-int on?] of patches with [pycor = row]) = 0) and OOO = 0.0) or
               ((sum ([true-false-to-int on?] of patches with [pycor = row]) = world-width)
                 and III = 100.0))
         [ stop ]
         [
           set done? true
           display    ;; ensure all the patches get drawn before we clear
           setup-continue
         ]
    ]
    [
      ;; if a run has already been completed, continue with another.  otherwise just stop
      ifelse done?
        [ setup-continue ]
        [
          set done? true
          stop
        ]
    ]
  ]
  ask patches with [ pycor = row ]  ;; apply rule
    [ do-rule ]

  set row (row - 1)
  ask patches with [ pycor = row ]  ;; color in changed cells
    [ color-patch ]

  build-prob-list
  tick
end 

;; the patch will set the on? value of the patch below it based on three factors,
;; 1) its own on? value
;; 2) the on? values of the patches to the left and right of it
;; 3) the current settings for the rules

to do-rule  ;; patch procedure
  let left-on? [on?] of patch-at -1 0  ;; set to true if the patch to the left is on
  let right-on? [on?] of patch-at 1 0  ;; set to true if the patch to the right is on

  ;; each of these lines checks the local area and (possibly)
  ;; sets the lower cell according to the corresponding switch
  let new-value
    (III != 0  and left-on?       and on?       and right-on?          and (random-float 100) < III)    or
    (IIO != 0  and left-on?       and on?       and (not right-on?)    and (random-float 100) < IIO)    or
    (IOI != 0  and left-on?       and (not on?) and right-on?          and (random-float 100) < IOI)    or
    (IOO != 0  and left-on?       and (not on?) and (not right-on?)    and (random-float 100) < IOO)    or
    (OII != 0  and (not left-on?) and on?       and right-on?          and (random-float 100) < OII)    or
    (OIO != 0  and (not left-on?) and on?       and (not right-on?)    and (random-float 100) < OIO)    or
    (OOI != 0  and (not left-on?) and (not on?) and right-on?          and (random-float 100) < OOI)    or
    (OOO != 0  and (not left-on?) and (not on?) and (not right-on?)    and (random-float 100) < OOO)
  ask patch-at 0 -1 [ set on? new-value ]
end 

;; for plotting

to build-prob-list
  let i min-pxcor  ;; index of where in the row we are currently doing calculations
  ;; make a 16 element list for storing the number of occurrences of each distinct 4-patch pattern
  let counter-list n-values 16 [0]

  ;; fill the counter-list with the appropriate values.  that is to say, count
  ;; the number of occurrences of each distinct 4-patch pattern of on? values.
  while [ i < max-pxcor ]
  [
    let an-index binary-list-to-index (patches-to-binary-list i)
    set counter-list replace-item an-index counter-list (item an-index counter-list + 1)
    set i (i + 1)
  ]

  ;; make a list of the probabilities of each pattern occurring
  set prob-list map [? / (sum counter-list)] counter-list
end 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; UTILITY PROCEDURES   ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; report the base 10 equivalent of a binary number represented by a list of 0's and 1's.
;; in the list, the 0th item is the highest power of 2 and the highest item is the lowest power.

to-report binary-list-to-index [binary-list]
  let list-sum 0
  let i 0
  let list-length length binary-list
  while [i < list-length ] [
    set list-sum list-sum + (2 ^ i) * ((item (list-length - i - 1) binary-list) mod 2)
    set i i + 1
  ]
  report list-sum
end 

;; report a list of binary digits based on the values of on? for the current row's
;; patches starting at 'offset'

to-report patches-to-binary-list [offset]
  let binary-list []
  set binary-list lput ([true-false-to-int on?] of patch offset row) binary-list
  set binary-list lput ([true-false-to-int on?] of patch (offset + 1) row) binary-list
  set binary-list lput ([true-false-to-int on?] of patch (offset + 2) row) binary-list
  set binary-list lput ([true-false-to-int on?] of patch (offset + 3) row) binary-list
  report binary-list
end 

;; convert true/false values to 1/0

to-report true-false-to-int [b]
  ifelse b
    [ report 1 ]
    [ report 0 ]
end 

;; color the patch based on whether on? is true or false

to color-patch  ;; patch procedure
  ifelse on?
    [ set pcolor on-color ]
    [ set pcolor off-color ]
end 


; Copyright 2003 Uri Wilensky.
; See Info tab for full copyright and license.

There are 10 versions of this model.

Uploaded by	When	Description	Download
Uri Wilensky	over 11 years ago	Updated to NetLogo 5.0.4	Download this version
Uri Wilensky	about 12 years ago	Updated version tag	Download this version
Uri Wilensky	about 12 years ago	Updated to version from NetLogo 5.0.3 distribution	Download this version
Uri Wilensky	almost 13 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Model from NetLogo distribution	Download this version
Uri Wilensky	over 14 years ago	CA Stochastic	Download this version

Attached files

File	Type	Description	Last updated
CA Stochastic.png	preview	Preview for 'CA Stochastic'	over 11 years ago, by Uri Wilensky	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo