[Time series from CAs and ICAs] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Time series from CAs and ICAs

(Click here to view the original thread with full colors/images)


Posted by: Jason Cawley

NKS systems can be used to generate time series data, for example by just totaling cell counts across a row. The brief discussion of finance in the NKS book effectively does this using rule 90. There may be various practical applications, but it is also just a way of looking at NKS system data, a kind of minimal transform that throws away some of the information the complete system evolution gives to focus on one part. One can then characterized NKS systems by the sort of behavior they exhibit looked at this simplified way. The statistics of such sequences can be compared to random walks or deterministic functions, etc.

At the simplest, one is just looking at -

Total[Transpose[CellularAutomaton[rl, init, steps]]]

Any array produced by an NKS system evolution, you can do the same with.

Sometimes you want to remove the starting point to see only the overall change, which is just -

# - First[#] &[Total[Transpose[CellularAutomaton[rl, init, steps]]]]

If you put the initial condition on an infinite background of zeros, you will get a trend given by the growth in the width of the pattern. If you use a cyclic boundary you will get a stationary series instead. Varying the width tends to increase the variation step to step, obviously. Thus to look at a series with trend from a random initial condition of some width, I use -

CAseriesdata[rl_, width_, steps_] := # - First[#] &[
  Total[Transpose[
    CellularAutomaton[rl, { Table[Random[Integer], {width}], 0} , steps]]]]

Rule 54 gives particularly interesting behavior in this representation. It has an alternating background, which gives a large oscillation if all parts of the pattern are in phase. But regions that are out of phase cancel. They are separated by persistent triangle structures when you start from random initials. The portion of the overall pattern in or out of phase changes, typically giving a progression from regular oscillation to a quieter but random looking bit and back.

Rule 90 shows larger negative fluctuations - corresponding to those large white triangles - than positive, while progressively growing by the same amount between them. Random initials give random looking outcomes. On a white background you get a growth trend with the size of the pattern. The scale of the fluctuations goes about as the square root of the width.

Random walks, for comparison, are easily implimented as just -

Walk1D[Steps_, Size_, Trend_] := 
 NestList[(# + Trend + Random[Integer, {-Size, Size}]) &, 0, Steps]

If one leaves the terrain of the ECAs and includes the ICAs, you can get much more varied series behaviors. ICA series can be generated from the following functions. First the basic ICA set up (see previous forum thread 500, and acknowledgements to Todd Rowland for code) -

Tuples[list_, n_]:=
 Partition[Flatten@Outer[List, Sequence @@ Table[list, {n}]], n]

rlno[rn_] := 
 MapThread[Rule, {Tuples[{1, 0}, 4], IntegerDigits[rn, 2, 2^4]}, 1]

ICAStep[rule_, init_, 
  choice_] := (Append[#, choice] & /@ Partition[init, 3, 1, 2]) /. rule

ICAEvolveList[rule_, init_List, interact_List] := 
 FoldList[ICAStep[rule, #1, #2] &, init, interact] 

With sample assignments like -

startcondition = Table[Random[Integer], {100}];
interactioncondition = Table[Random[Integer], {100}];

Then just use -

ICAseriesdata[rn_] := 
 Total[Transpose[
   ICAEvolveList[rlno[rn], startcondition, interactioncondition]]]

Then you can examine the typical behavior from random initials and interaction condition by just e.g. wrapping a Table around that function to vary the rule number, and display a flock of them at once. Or keep the same rule number and vary the interactioncondition to a variety of periodic input signals, for example. You will find interesting behavior right away - e.g. ICA 10014 and 10096.

I hope this is interesting.


Posted by: Jason Cawley

Here is a notebook of basic functions for looking at times series generated by CAs and ICAs, with 1D random walks included for comparison. I hope it is helpful.


Posted by: Jason Cawley

Then the obvious things to do are (1) look at the statistical properties of the different types of series (CAs with fixed width on a white background, CAs "wrapped", ICAs, compared to the standard random walks) and (2) then look at linear combinations of characteristically different series behaviors.

E.g. 0.2 to 0.3 rule 90 from fixed width initials (gives "crash-ness"), 0.2-0.4 rule 54 from wrapped initials (cyclical bursts), 0.0-0.5 rule 30 either way (stationary rather than diffusing "noise"), 0.0-0.5 random walk ("new information" dispersion). I've fiddled with this just in an exploratory manner so far, and one can clearly build very realistic looking signals with a wide variety of obvious behaviors, statistical profiles, etc.


Posted by: Jason Cawley

When looking at linear combinations of CA generated series, one can find a least squares fit to some test data - just as a routine way to look at that issue - as follows.

Say I take some test pattern e.g. -

testpattern = Walk1D[100, 5, 1];

Then suppose I give myself 3 signals to mix together to create that pattern, 2 from CAs and 1 a random walk (not strictly necessary, but as an example). Then my linear combination might be something like -

x = CAseriesdata[54,100,100]; y = CAseriesdata2[90,100,100]; z = walk1D[100,5,1]; 

Resolve those so they have definite values. Then my function of my weights is -

weighted[a_, b_] := a x + b y + (1 - (a + b)) z 

Now I can consider it a continuous function of my weight parameters and so use it for things like -

score[series_] := Total[(series - testpattern)^2]

scoremap[a_, b_] := score[weighted[a, b]]

FindMinimum [scoremap[g, h], {g, 0}, {h, 0}]

I can input that line's output to assign g and h global values for the next section. Then I can compare the result to the test pattern -

ListPlot[ g  x + h y + (1 - (g + h)) z, PlotJoined->True ]
ListPlot[testpattern]
Show[%,%%]

For comparison, one can also look at what the built in function Fit gives, if you use a polynomial -


poly = Fit[testpattern, {1, v, v^2, v^3, v^4}, {v}]
Plot[poly, {v,0,100}]
ListPlot[testpattern]
Show[%,%%]


The polynomial gets decent at 4th order in this case, but reveals nothing about the bumpiness of the actual signal. That is effectively put down to random scatter about the smooth function. The CA series fit, in contrast, is in this case spikier than the original. CA fitting would seem to be more appropriate for rapidly varying random data.

At any rate it illustrates the idea of linear combinations of signals and what might be done with them. One could imagine e.g. searching over a variety of CA signals to combine, as well as weights given to each.

I hope this is interesting.




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings