- Our task is to establish the mean value of cells in the central column as row \(n\rightarrow\infty,\ \)where the initial row is a single 1 (black) padded by infinitely many 0s (white), which we'll call the "standard progression".
- In rule 30, each row fully controls the row that follows, meaning that all future rows are completely determined by any prior complete row. We'll call a row along with all of its following rows a "progression", and when we talk about a row "configuration", we just mean the values of all the cells on some row.
- Every row \(n\) also has exactly 4 possible previous rows that would be logically consistent if used as row \(n-1\). This extends in general to \(4^{k}\) logically consistent row possibilities for row \(n-k\).
- Since we only care about the limit of the mean values at \(+\infty\), it turns out that there is nothing particularly special about the central column of the ...010... initial row of the standard progression. We can pick any row \(n\) in the future, backtrack from that \(n\) as far as we like along the branching alternative row histories, and then for any row configuration we find in that way, we could launch from there and treat the problem as though we need to find the limit of mean values in
*that*central column. - (This is illustrated below where the first plot is of the standard progression, while the 255 other plots show the situation if we choose a different initial row which is also compatible with the first yellow highlighted row.)
**In other words, given two distinct rows \(A\) and \(B\), neither of which generate the other at any point in their futures, the limit at \(+\infty\) of their central column mean value must be the same if they share a common descendant, that is, a row \(C\) which is present at some point in both of their futures.**In the plots below, our row \(C\) is the first yellow row, i.e. the first row that all plots share. After having a full row in common, any two distinct progressions can thereafter be treated as one, since they must be identical from that point on. So, any two progressions with a full row in common must have the same central column mean value in the limit.- Thus we have expanded the problem from its original form ("find the mean cell value in the limit in the central column of the standard progression") to additionally allow: "find the mean cell value in the limit in the central column of
*any*progression, provided it shares a descendant row with the standard progression". - It follows that all such progressions must have a single mean limit value (or lack thereof, if indeterminate) for their respective central columns. This also implies that the mean of the columns of any subset of these progressions will share that limit value as well, since of course the average of the same number multiple times is just that number, and as row \(n\rightarrow \infty\), all valid progressions will eventually have identical central column values. This lets us extend our redefinition above to support not only any progression with a shared descendant with the standard progression, but also the mean column values of any
*set*of valid progressions. - In the finite case, it is easy to show average cell values of \(1/2\). If you have a \(b\)-bit sequence in a row and backtrack \(m\) rows from there, each \(m\) effectively appends 2 bits to the end of another \(b\)-bit sequence (all of which is shifted left one column so as to expand out from your sequence), and statistically they are guaranteed to average to \(1/2\) across all \(4^m\) possibilities. So backtracking merely \(b\) rows is enough to guarantee that each of your original bits is now in a \(1/2\) column, and you need only half that to ensure \(1/2\) for your center column, meaning that these columns would contain equal numbers of 0s and 1s when all \(4^m\) legal configurations are tallied.
- Perhaps more intuitively, if you have a \(b\)-bit sequence and backtrack from it, those \(b\) bits are the only ones that will remain dependent on other factors. Every new bit introduced from backtracking is more or less immediately independent relative to all other cell values.
- In fact, it is helpful to note that in general, the left side of a progression is heavily dependent on the rest of the cells, while the rightmost cells can often be changed without immediately affecting anything but themsel. That said, altering
*any*cell, with no other changes, will NOT everything on that NW-SE diagonal, meaning that flipping any single bit will always alter every row and every column slightly, all the way out to infinity.