single-particle correlation data

Single-particle correlations from just one evolution, for width 251:

statistical sampling of correlations at each correlation distance

system width: 251

Find a histogram of the correlations at a given correlation distance

correlation histograms for various correlation distances

correlation envelopes

Now show the histogram as a function of correlation distance:

The boundaries above and below in the plot define an envelope for the correlations at this system width:

How does the shape of the envelope change as the system width is increased?

width 398

width 630

width 1000

width 1584

width 2511

width 3981

width 6309

width 10000

These plots totally look like jellyfish.

next: plot the raw particle trajectories in an interesting way …

ensemble of rule 18 single particle trajectories, for a number of different system widths

width 100

width 158

width 251

width 398

width 630

width 1000

with 1584

width 2511

with 3981

width 10000

autocorrelations in rule 18 particle position as a function of system size

It’s time to look at the autocorrelations in the rule 18 single-particle movement as a function of system size, for a larger range of system sizes (several orders of magnitude), with some statistics for each width.

Here’s the simulation code …

functions

simulation code:
correlation vs distance as a function of system size

data analysis

Now grab the resulting data files:

Each index here is a different width:

I chose widths logarithmically spaced spanning 3 orders of magnitude, in the range 100 to 10,000:

These widths will be evenly spaced on a log plot.

Take a look at a single run at width 100:

Here’s the particle position vs. time, run for 50k steps:

The particle position went periodic.  Not surprising for such a small system width.  Here’s the correlation function, which also has a strong periodicity:

Let’s look at all of the runs for width 100:

(Note that my particleposition code treats periodic boundary crossings as reflections.)

And all the correlations at this width:

The correlations have a pretty regular structure, since all the evolutions seemed to have gone periodic within about 10k steps.  Given this reglar structure, it seems worthwhile to take the average autocorrelation at each distance:

Do this for all the other system widths:

The correlation functions at each width have a prett similar structure.  It isn’t clear if I’m resolving any real differences it the correlations here at all actually.  It could be that the particle really isn’t much effected by the system size.

Vitaliy recommended that I look at the power spectrum, which is related to these correlation functions via the Weiner-Kinchin theorem.  That’s the next thing to do I think.

I ran a few batch jobs with longer evolutions of rule 18 (100k steps, used to be 10k steps), and measuring much longer-range correlations than before (out to distances of 50k and 100k correlation distances).

My first task was to speed up the correlation distance function as much as possible.

speeding up the correlation function

Generate a random walk:

My original version of the correlation function, which I want to speed up:

Timing for a single correlation data point (lag 1):

I want to do this without using Partition, since I think it’s taking a lot of memory.

Try using RotateRight instead … already an order of magnitude faster:

A similar version which doesn’t wrap at the boundaries.  I don’t want to wrap around the boundaries in *time*, because there’s no reason to correlate the beginning of the timeseries with the end of the timeseries.  Normalization uses a few less points of the list, so the correlation comes out numerically slightly different:

… but it’s just as fast as the RotateRight method, and I think it’s more accurate for my purposes since it doesn’t do temporal wrapping.

So here’s my new correlation function:

measuring long-range correlations in the rule 18 particle movement

Grab the particle correlation data for a rule 18 evolution of 100k timesteps (still using a width of 199 cells):

And grab the actual position vs. time for the particle:

Got about 50k correlation data points:

Here’s the beginning of the walk:

But it clearly went periodic:

And the correlations also went periodic:

So I did another evolution, this time using width of 999 cells:

Now the walk doesn’t go periodic, because the underlying evolution didn’t go periodic:

And behold the long-range correlations!

This is an interesting plot.  Correlations fall gradually here over about 50k lag, then hover around a negative correlation of around -0.4 from 50k to 100k lag.

Next steps:

1. Get a statistical distribution of correlations at each lag, from multiple runs of the rule 18 particle

Rule 18: Eating its own light cone (Part 5)

At the last ruleshack meetup, we discussed why the autocorrelation curve for the position of the rule 18 particle appears to be linear.  And we realized that I’m probably just not looking at large enough correlation distances (lags).

The particle position vs time looks like this:

And the autocorrelations out to lag 100 look like this:

During the meetup, we looked at the particle position with the mean subtracted (since that’s what the autocorrelation function is based on):

We noticed that the typical time between zero crossings (when the curve crosses the x-axis in this plot, or equivalently the instants in time when the particle passes through its average position), is greater than the maximum lag I was using of 100 time steps.  In fact, looking at the mean-subtracted position plot above, sometimes it’s more like 1000 time steps between crossings.  That means I need to sample much larger lags in order to capture more features of the random walk.

To be more precise, I can compute the crossing intervals, and the distribution of interval sizes:

The average interval size:

The interval distribution:

It looks like the average crossing interval size is of the order of a few hundred time steps, with a intervals of order 10 being most common, but with some rare intervals being on the order of 1000 time steps.  

Call the average crossing interval .  Then the products p(t)*p(t+r) will tend to be positive for .  But for lags , there will be more products where p(t) and p(t+r) have different sign, and thus contributing negative terms to the sum over t.  So I’d expect the autocorrelations to start becoming negative somewhere around .

Here’s what the correlations look like out to lag 2000 (which I ran on a server).  The curve is looking more interesting now, with the linearity going away at around lag 1000.

part 4

I need to measure the correlations in the particle position as a function of system size.  This will give me a sense if the results from part 3 are at all accurate.  Specifically, I want to know if perturbing the sides of the rule 18 evolution really does simulate an infinite system, or if that’s just perturbing the system and has nothing to do with the behavior for large system sizes.

So I’ve got my code for measuring the particle position versus time:

… and I run it on a rule 18 evolution with system width 199 for 10,000 steps:

And I get a list of the particle position versus time:

Now I take my code to measure the autocorrelations of the walk:

… and measure the autocorrelation as a function of the lag time r:

Now I want to see how this autocorrelation curve changes as a function of the system width:

Now I’ll plot each of the correlation vs. lag curves on one graph.  There’s might be a pattern emerging here, with larger system widths resulting in higher correlations:

Since the correlation seems to be pretty firmly linear with lag, let’s find the simple slope of these curves and plot slope vs. system width:

There’s a downward trend with N for small N < 400, but then a pretty consistent upward trend for 400 < N ≤ 1000.  But in order to confirm the trend, I need to look at a broader range of system widths.

But these preliminary results do agree with the results in part 3: correlations are going up for larger system sizes N (i.e. more random input, more perturbations to the system through time).

And this suggests that somehow the randomness in the particle movement is actually higher when there’s less external randomness being injected into the system.  It’s as though the particle is saying, “I can generate all the randomness I need thank you very much”.  So intuitively this seems to me like an example of intrinsic randomness generation at work.

To Do:
1. Look at the convergence of the autocorrelation values as a function of the number of time steps measured.
2. Measure autocorrelation slope vs. N for a wider range of values for N.