Local Markov Chains of the Elementary Cellular Automata

The Constellations of the ECA

Rodrigo A. Obando

Columbus State University

Introduction

Each cell in an Elementary Cellular Automaton changes from one value to another according to a function that takes the cell's own value ((Subscript[a, 0])) and the value of the cells in the defined neighborhood ((Subscript[a, -1]),(Subscript[a, 1])). 
The rule is normally deterministic and for given cell value and the values of its neighborhood cells there is always a given future value for the cell.
The number of possible values for a cell is defined by k and in the case of binary there are only two values or colors.

Graphics[{{Hue[.7,1,1,.7],Rectangle[{0,0},{1/3,1}]},Text[Style[(Subscript[a, -1]),Large],{1/6,1/2}],{Hue[.7],Rectangle[{1/3,0},{2/3,1}]},Text[Style[(Subscript[a, 0]),Large],{3/6,1/2}],{Hue[.7,1,1,.7],Rectangle[{2/3,0},{1,1}]},Text[Style[(Subscript[a, 1]),Large],{5/6,1/2}]},AspectRatio->1/4]

Beyond a cell

From cell to cell + neighborhood

If we consider not only the value of the cell but the combined value of the cell and its neighborhood, we would extend the number of possible values or states to (k^(2r+1))given that we have a one-dimensional CA. In the case of the Elementary Cellular Automata the number of states would be (2^(2+1))=(2^3)=8.  We would have 8 different values or states but in this situation we do not really know the values for the cells in the neighborhood since they depend not only on the values of the previous step but on the values of other cells beyond this neighborhood.

Graphics[{{Hue[.7,1,1,.4],Rectangle[{0,0},{1/5,1}]},Text[Style[(Subscript[a, -2]),Large],{1/10,1/2}],{Hue[.7,1,1,.7],Rectangle[{1/5,0},{2/5,1}]},Text[Style[(Subscript[a, -1]),Large],{3/10,1/2}],{Hue[.7],Rectangle[{2/5,0},{3/5,1}]},Text[Style[(Subscript[a, 0]),Large],{5/10,1/2}],{Hue[.7,1,1,.7],Rectangle[{3/5,0},{4/5,1}]},Text[Style[(Subscript[a, 1]),Large],{7/10,1/2}],{Hue[.7,1,1,.4],Rectangle[{4/5,0},{1,1}]},Text[Style[(Subscript[a, 2]),Large],{9/10,1/2}]},AspectRatio->1/4]

Local Markov Chains

Equally Probable

If we assign a probability to the different values of the cells just beyond the neighborhood ((Subscript[a, -2]),(Subscript[a, 2]))  we then can express the probability of the cell and neighborhood to go from one value (state) to another using a Transition Matrix and expressing the rule as a Markov Chain.
As a matter of simplification and to get started with the model, we can assign equal probability to each of the values and create the Transition Matrix to draw a Markov Chain Graph of the rule.
The following is the Markov Chain Graph (using SpringEmbedding for display) and Transition Matrix for rule 30.

theRule=30;
{{ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[theRule,1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[theRule,1]]],EdgeStyle->Normal,PlotLabel->theRule],TableForm[1/GetAdjacencyMatrix[theRule,1]]}}//TableForm

Other Examples

theRules={164,144,86,110};
Map[{{ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[#,1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[#,1]]],EdgeStyle->Normal,PlotLabel->#],TableForm[1/GetAdjacencyMatrix[#,1]]}}&,theRules]

Equivalent Classes

theRules=GetEquivalentClass[30,1];
Map[{{ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[#,1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[#,1]]],EdgeStyle->Normal,PlotLabel->#],TableForm[1/GetAdjacencyMatrix[#,1]]}}&,theRules]

More Equivalent Classes

theRules=GetEquivalentClass[110,1];
Map[{{ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[#,1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[#,1]]],EdgeStyle->Normal,PlotLabel->#],TableForm[1/GetAdjacencyMatrix[#,1]]}}&,theRules]

Even More Equivalent Classes

theRules=GetEquivalentClass[90,1];
Map[{{ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[#,1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[#,1]]],EdgeStyle->Normal,PlotLabel->#],TableForm[1/GetAdjacencyMatrix[#,1]]}}&,theRules]

Still Even More Equivalent Classes

theRules=GetEquivalentClass[3,1];
Map[{{ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[#,1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[#,1]]],EdgeStyle->Normal,PlotLabel->#],TableForm[1/GetAdjacencyMatrix[#,1]]}}&,theRules]

Displaying All Markov Chains

Using the primitives defined by Obando in NKS2004, NKS2006, the ordering of the graphs is shown on the next slide. The similarity of the graphs for neighboring rules is remarkable and it shows that this particular ordering or partitioning of the rules allows for finding rules with similar Transition Matrices or Markov Chains. The colors indicate the Wolfram Class of the rule and they are assigned as follows: Class 1 -> Green, Class 2 -> Yellow, Class 3 -> Purple, and Class 4 -> Red.

The Entire Elementary Cellular Automata Rule Space

radius=1;
colors={Green,Yellow,Purple,Red};
pZero={0,8,4,2,1,9,6,3,5,12,10,14,11, 13,7,15};
pOne={15,14,13,11,7,6,9,3,5,12,10,8,2,4,1,0};
MarkovChainView=MatrixForm[Table[ShowGraph[SpringEmbedding[FromAdjacencyMatrix[GetAdjacencyMatrix[BuildRule[{pZero[[i]],pOne[[j]]},radius],1],EdgeWeight,Type->Directed],100,0.15`],EdgeColor->colors[[GetWolframClass[BuildRule[{pZero[[i]],pOne[[j]]},radius],radius]]],EdgeStyle->Thick,ImageSize -> 64,PlotLabel->BuildRule[{pZero[[i]],pOne[[j]]},radius]],{j,1,Length[pOne]},{i,1,Length[pZero]}]]

Measuring Evolution of the Cellular Automata

If we take a particular ECA and start its evolution with random input, we measure the probability of the CA to go from one state (as defined above) to another, we find that the Transition Matrix that is generated is very close to the calculated one. In general, if the CA is of Class 1 we do not really have the same matrix since the randomness introduced in the input is removed by the rule itself and the 'sides' of the range that we measure is no longer random. For Class 2 and Class 3 we find that the measured matrix is very close.  There was one observation in the case of rule 110 where many ranges where the measurement was made the resulting matrix was also close except for one particular range where there was a different matrix.  This result is still preliminary and it will need more investigation.

Increasing the Number of States

We can also increase the number of states in the Markov Chain. If instead of only using the central cell and its neighborhood we add two more cells we generate 32 states.  Still Applying the same reasoning we have different Markov Chains that might provide an alternative model.

Graphics[{{Hue[.7,1,1,.2],Rectangle[{0,0},{1/7,1}]},Text[Style[(Subscript[a, -3]),Large],{1/14,1/2}],{Hue[.7,1,1,.4],Rectangle[{1/7,0},{2/7,1}]},Text[Style[(Subscript[a, -2]),Large],{3/14,1/2}],{Hue[.7,1,1,.7],Rectangle[{2/7,0},{3/7,1}]},Text[Style[(Subscript[a, -1]),Large],{5/14,1/2}],{Hue[.7],Rectangle[{3/7,0},{4/7,1}]},Text[Style[(Subscript[a, 0]),Large],{7/14,1/2}],{Hue[.7,1,1,.7],Rectangle[{4/7,0},{5/7,1}]},Text[Style[(Subscript[a, 1]),Large],{9/14,1/2}],{Hue[.7,1,1,.4],Rectangle[{5/7,0},{6/7,1}]},Text[Style[(Subscript[a, 2]),Large],{11/14,1/2}],{Hue[.7,1,1,.2],Rectangle[{6/7,0},{1,1}]},Text[Style[(Subscript[a, 3]),Large],{13/14,1/2}]},AspectRatio->1/4]

We assume that the values for the outer cells ((Subscript[a, -3]),(Subscript[a, 3])) are equally likely.  Note that the former equally likely cells are part of the known information and they are not assumed equally likely.

Some Examples

Map[{{ExpandedMarkovChainGraph[#]}}&, {128,73,30,110,77, 54,90,142}]

All the ECA rule space

pZero={0,8,4,2,1,9,6,3,5,12,10,14,11, 13,7,15};
pOne={15,14,13,11,7,6,9,3,5,12,10,8,2,4,1,0};
MarkovChainView=MatrixForm[Table[ExpandedMarkovChainGraph[BuildRule[{pZero[[i]],pOne[[j]]}]],{j,1,Length[pOne]},{i,1,Length[pZero]}]]

Transition Matrix Power

Given a Transition Matrix, we can find the resulting Transition Matrix after some iterations of the system. We find this by multiplying the matrix by itself (power) as many times as we need to find when the system might reach a steady state. We can track these intermediate matrices and see how quickly the system reaches a 'steady state'. The following figure is for rule 30 and 10 iterations.

thisRule=30
Table[GraphPlot[MatrixPower[1/ExpandedMarkovChainMatrix[thisRule],y],PlotLabel->y,Method->"SpringEmbedding"],{y,1,10,1}]

Rule 110

thisRule=110
Table[GraphPlot[MatrixPower[1/ExpandedMarkovChainMatrix[thisRule],y],PlotLabel->y,Method->"SpringEmbedding"],{y,1,15,1}]

Rule 90

thisRule=90
Table[GraphPlot[MatrixPower[1/ExpandedMarkovChainMatrix[thisRule],y],PlotLabel->y,Method->"SpringEmbedding"],{y,1,10,1}]

Rule 4

thisRule=4
Table[GraphPlot[MatrixPower[1/ExpandedMarkovChainMatrix[thisRule],y],PlotLabel->y,Method->"SpringEmbedding"],{y,1,10,1}]

Rule 73

thisRule=73
Table[GraphPlot[MatrixPower[1/ExpandedMarkovChainMatrix[thisRule],y],PlotLabel->y,Method->"SpringEmbedding"],{y,1,10,1}]

Rule 54

thisRule=54
Table[GraphPlot[MatrixPower[1/ExpandedMarkovChainMatrix[thisRule],y],PlotLabel->y,Method->"SpringEmbedding"],{y,1,10,1}]

Using GraphPlot3D For Rule 54

GraphPlot3D[1/ExpandedMarkovChainMatrix[54],PlotLabel->54,Method->"SpringEmbedding",EdgeRenderingFunction->(Cylinder[#1,.03]&),VertexRenderingFunction->({ColorData["Atoms"][RandomInteger[{1,117}]],Sphere[#1,.15]}&),PlotStyle->Directive[Specularity[White,20]]]

Using GraphPlot3D For Rule 102

GraphPlot3D[1/ExpandedMarkovChainMatrix[102],PlotLabel->102,Method->"SpringEmbedding",EdgeRenderingFunction->(Cylinder[#1,.03]&),VertexRenderingFunction->({ColorData["Atoms"][RandomInteger[{1,117}]],Sphere[#1,.15]}&),PlotStyle->Directive[Specularity[White,20]]]

Using GraphPlot3D For Rule 142

GraphPlot3D[1/ExpandedMarkovChainMatrix[142],PlotLabel->142,Method->"SpringEmbedding",EdgeRenderingFunction->(Cylinder[#1,.03]&),VertexRenderingFunction->({ColorData["Atoms"][RandomInteger[{1,117}]],Sphere[#1,.15]}&),PlotStyle->Directive[Specularity[White,20]]]

Using GraphPlot3D For Rule 110 With the Original Markov Model

GraphPlot3D[1/GetAdjacencyMatrix[110],PlotLabel->110,Method->"SpringEmbedding",EdgeRenderingFunction->(Cylinder[#1,.03]&),VertexRenderingFunction->({ColorData["Atoms"][RandomInteger[{1,117}]],Sphere[#1,.15]}&),PlotStyle->Directive[Specularity[White,20]]]

Conclusion

This research is in its preliminary stages and it has been just the beginning of an exploration on the subject.  This model can be expanded to more colors and larger radii. It should be interesting to use this to explore larger rule spaces in search of interesting rules or even just graph structures.  Perhaps the Local Markov Chain model of the rules might reveal properties that may have not been obvious otherwise.

Some Functions to use

Initialization code

colors={Green,Yellow,Purple,Red};
ruleDigit[input_,rule_]:=IntegerDigits[rule,2,8][[input+1]];
mapRule[input_,rule_]:=Map[ruleDigit[FromDigits[input[[#;;#+2]],2],rule]&,Table[n,{n,1,Length[input]-2}]];
ExpandedMarkovChain[rule_]:=Module[{mappings=Map[Union[Table[FromDigits[mapRule[#[[x]],rule],2],{x,1,4}]]&,Map[Table[Join[{IntegerDigits[n,2,2][[1]]},IntegerDigits[#,2,5],{IntegerDigits[n,2,2][[-1]]}],{n,0,3}]&,{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}]]},Flatten[Table[Table[n-1->mappings[[n]][[m]],{m,1,Length[mappings[[n]]]}],{n,1,Length[mappings]}]]];
ExpandedMarkovChainMatrix[rule_]:=Module[{mappings=Map[Union[Table[FromDigits[mapRule[#[[x]],rule],2],{x,1,4}]]&,Map[Table[Join[{IntegerDigits[n,2,2][[1]]},IntegerDigits[#,2,5],{IntegerDigits[n,2,2][[-1]]}],{n,0,3}]&,{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}]],theMatrix=Table[Infinity,{n,1,32},{m,1,32}]},
For[n=1,n≤Length[mappings],n++,For[m=1,m≤Length[mappings[[n]]],m++,theMatrix[[n,mappings[[n]][[m]]+1]]=Length[mappings[[n]]]]];
theMatrix];
ExpandedMarkovChainGraph[rule_]:=Module[{mappings=Map[Union[Table[FromDigits[mapRule[#[[x]],rule],2],{x,1,4}]]&,Map[Table[Join[{IntegerDigits[n,2,2][[1]]},IntegerDigits[#,2,5],{IntegerDigits[n,2,2][[-1]]}],{n,0,3}]&,{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}]]},GraphPlot[ExpandedMarkovChain[rule],DirectedEdges->True,VertexLabeling->False,MultiedgeStyle->None,PlotLabel->rule,EdgeRenderingFunction->({colors[[GetWolframClass[rule]]],Arrow[#]}&)]];
BuildRule[prims_] := Module[{
	tempPrims = {},
	tempRule = {}}, 
		tempPrims = {IntegerDigits[prims[[1]], 4, 2], IntegerDigits[prims[[2]], 4,2]};
		Do[tempRule = Append[Append[tempRule, (tempPrims[[2]])[[n]]], (tempPrims[[1]])[[n]]], {n, 1, Length[tempPrims[[1]]]}];
		FromDigits[tempRule, 4]];
GetWolframClass[rule_] := Module[{
	classes = {{0, 4, 8, 12, 13, 32, 36, 40, 44, 64, 68, 69, 72, 76, 77, 78,
	79, 92, 93, 96, 100, 104, 128, 132, 136, 140, 141, 160, 164, 168, 172,
	192, 196, 197, 200, 202, 203, 204, 205, 206, 207, 216, 217, 218, 219, 
	220, 221, 222, 223, 224, 228, 232, 233, 234, 235, 236, 237, 238, 239, 
	248, 249, 250, 251, 252, 253, 254, 255}, {1, 2, 3, 5, 6, 7, 9, 10, 11,
	14, 15, 16, 17, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 31, 33, 34, 35,
	37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58,
	59, 61, 62, 63, 65, 66, 67, 70, 71, 73, 74, 80, 81, 82, 83, 84, 85, 87,
	88, 91, 94, 95, 97, 98, 99, 103, 107, 108, 109, 111, 112, 113, 114, 115,
	116, 117, 118, 119, 121, 123, 125, 127, 130, 131, 133, 134, 138, 139, 
	142, 143, 144, 145, 148, 152, 154, 155, 156, 157, 158, 159, 162, 163, 
	166, 167, 170, 171, 173, 174, 175, 176, 177, 178, 179, 180, 181, 184, 
	185, 186, 187, 188, 189, 190, 191, 194, 198, 199, 201, 208, 209, 210, 
	211, 212, 213, 214, 215, 226, 227, 229, 230, 231, 240, 241, 242, 243, 
	244, 245, 246, 247}, {18, 22, 30, 45, 60, 75, 86, 89, 90, 101, 102, 105, 
	106, 120, 122, 126, 129, 135, 146, 149, 150, 151, 153, 161, 165, 169,
	182, 183, 195, 225}, {54, 110, 124, 137,147, 193}}},
		Do[If[MemberQ[classes[[n]], rule], Return[n]], {n, 1, Length[classes]}]];
GetCombinations[triad_] := Module[{
	expTriad = IntegerDigits[triad, 2, 3]},
		Table[Join[(IntegerDigits[m, 2, 2])[[Table[n, {n, 1, 1}]]], Join[expTriad, (IntegerDigits[m, 2, 2])[[Table[n, {n, (-1), (-1)}]]]]], {m, 0, 3}]];
GetIndices[fivead_] := Module[{
	fused = {}},
		Table[FromDigits[fivead[[Table[m, {m, n, n + 2}]]], 2], {n, 1,3}]];
GetAdjacencyMatrix[rule_] := Module[{
	expRule = Reverse[IntegerDigits[rule, 2, 8]],
	nextStates},
		nextStates = Table[Union[Table[FromDigits[expRule[[GetIndices[(GetCombinations[m])[[n]]] + 1]], 2], {n, 1,4}]], {m, 0, 7}] + 1;
		Table[Table[If[FreeQ[nextStates[[n]], m], Infinity, Length[nextStates[[n]]]], {m, 1, 8}], {n, 1,8}]]