Algorithm to tell if an infinite sequence is random or not?

Question

Background

I recently came up with an algorithm which creates patterns.

Consider the famous sequence of the primes. They have considerable amount of "structure" but no "obvious pattern". I will illustrate "row math" making a pattern emerge with the example of primes:

Row math

\begin{equation} 2,3,5,7,11,13,17,19,23,\dots \end{equation}

Now we will take the modulus/absolute difference of every element with its adjacent neighbor. \begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation}

Now we will take the difference (not the absolute difference) of the $2$'nd row with the first:

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,1,3,3,9,9,15,\dots \end{equation}

Again now we repeat the process of taking the absolute difference between adjacent neighbors:

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,1,3,3,9,9,15,\dots \end{equation} \begin{equation} 0,2,0,6,0,6,\dots \end{equation}

Again now we take the difference between this foremost row and the one preceding it:

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,1,3,3,9,9,15,\dots \end{equation} \begin{equation} 0,2,0,6,0,6,\dots \end{equation}

Alternating between these two procedures indefinitely on sees a pattern emerge:

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,\textbf{1},3,3,9,9,15,\dots \end{equation} \begin{equation} 0,\textbf{2},0,6,0,6,\dots \end{equation} \begin{equation} \textbf{1},\textbf{-1},3,-3,9,3,\dots \end{equation} \begin{equation} \textbf{2},\textbf{4},6,12,6,\dots \end{equation} \begin{equation} \textbf{-1},\textbf{-5},-3,-15,3,\dots \end{equation} \begin{equation} \textbf{4},\textbf{2},12,18,\dots \end{equation} \begin{equation} \textbf{-5},\textbf{-7},-15,-33,\dots \end{equation} \begin{equation} \textbf{2},\textbf{8},18,\dots \end{equation} \begin{equation} \textbf{-7},\textbf{-15},10,\dots \end{equation} \begin{equation} \textbf{8},\textbf{25},\dots \end{equation} \begin{equation} \textbf{-15},-40,\dots \end{equation} \begin{equation} \textbf{25},\dots \end{equation}

We note that in the number $1$ in bold in rowrepeats again in row. Similarly we see the bold $2$ repeats in another row. And so on for every bold number. Hence, as a pattern has emerged the sequence contains structure.

Algebraic Representation

The above manipulations can also be represented algebraically using a nilpotent matrix. Consider the following example of primes, again. But first some definitions:

Let $x = 1 - \epsilon $ where 1 represents the identity matrix and epsilon is a nilpotent matrix such that $\epsilon^2 = 0$. We define $y$ satisfying the properties: $ xy =1$ and $x^\lambda + y^\lambda = 2$ for any $\lambda$ being an integer.

\begin{equation} K = s x^2 + s^2 x^3 + s^3 x^5 + \dots \end{equation}

Multiplying $s$ both sides we get:

\begin{equation} Ks = 0+ s^2 x^2 + s^3 x^3 + s^4 x^5 + \dots \end{equation}

Subtracting the equations one gets:

\begin{equation} K(s-1) = -s x^2 + s^2 x^2(1-x) + s^3 x^3(1-x^2 ) + \dots \end{equation}

Note in the above procedure this is quite similar to taking absolute difference between the primes. Now, using $x^\lambda + y^\lambda = 2$:

\begin{equation} K(s-1) = -s x^2 + s^2 x^2(y-1) + s^3 x^3(y^2-1 ) + \dots \end{equation}

Defining $K_1$ as a sequence with only positive coefficients: $K_1 = s x^2 + s^2 x^2 + s^3 x^3 + \dots$ and using $ xy =1$. Hence,

\begin{equation} K(s-1) + K_1 = s^2 x + s^3 x + \dots \end{equation}

Note the above step is similar to subtraction between rows!

Hence, we can represent all the manipulations algebraically!

=

Questions

What are some non random sequences row math does not make a pattern emerge (I've tried it for Fibonacci, geometric, etc)? And a pattern emerges everytime (for some reason). Why does a pattern emerge to begin with?

Answer 1

It looks to me like your method always produces this pattern.

Here is a list of random integers between 1 and 10, and the result of your procedure:

$$ \begin{array}{cccccccccc} 10 & 7 & 8 & 5 & 10 & 8 & 5 & 3 & 3 & 1 \\ 3 & 1 & 3 & 5 & 2 & 3 & 2 & 0 & 2 & \text{} \\ 7 & 6 & 5 & 0 & 8 & 5 & 3 & 3 & 1 & \text{} \\ 1 & 1 & 5 & 8 & 3 & 2 & 0 & 2 & \text{} & \text{} \\ 6 & 5 & 0 & -8 & 5 & 3 & 3 & 1 & \text{} & \text{} \\ 1 & 5 & 8 & 13 & 2 & 0 & 2 & \text{} & \text{} & \text{} \\ 5 & 0 & -8 & -21 & 3 & 3 & 1 & \text{} & \text{} & \text{} \\ 5 & 8 & 13 & 24 & 0 & 2 & \text{} & \text{} & \text{} & \text{} \\ 0 & -8 & -21 & -45 & 3 & 1 & \text{} & \text{} & \text{} & \text{} \\ 8 & 13 & 24 & 48 & 2 & \text{} & \text{} & \text{} & \text{} & \text{} \\ -8 & -21 & -45 & -93 & 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 13 & 24 & 48 & 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -21 & -45 & -93 & -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 24 & 48 & 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -45 & -93 & -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 48 & 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -93 & -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \end{array} $$

Answer 2

Why does a pattern emerge to begin with?

Regardless of the source of the first row (deterministic vs. non-deterministic, random vs. non-random, etc.), your procedure may naturally produce that pattern because (1) it produces the pattern just when a row contains non-increasing segments, (2) it always replaces non-increasing segments by other non-increasing segments (thus maintaining the pattern once it appears), whereas (3) it often replaces increasing segments by non-increasing segments.

To see this, consider just the odd-numbered rows, the first row being row #1. If the $i$th element of an odd row equals the $(i+1)$th element of the preceding odd row, then let us say that those two positions exhibit "Pattern A" -- i.e., the pattern you've noticed.

Now if $(a,b,c,\dots)$ is any segment of an odd row, then the next odd row contains, in the same positions, segment $(a-|a-b|,\ b-|b-c|,\ldots)$; so, if $a\ge b$, then $a-|a-b|=b\ge b-|b-c|$, and the non-increasing pair $(a,b)$ is just replaced by another non-increasing pair $(b,\ b-|b-c|)$, thus exhibiting Pattern A in those positions in those two rows and in all future odd rows.

Hence, any segment of non-increasing values will generate Pattern A, and this pattern is permanent, as the "non-increasingness" persists in all future odd rows. On the other hand, examples show that the "increasingness" of a segment is often transient, so we should not be surprised to see Pattern A arising as some increasing segments get replaced by permanent non-increasing segments. (Evidently, a similar phenomenon occurs also among even-numbered rows.)

NB: If a sequence is not strictly increasing, then it is guaranteed to produce Pattern A in some positions, so I think there are some interesting unanswered questions concerning the odd rows:

1. What property of a strictly increasing sequence guarantees that it will never produce Pattern A (i.e., that it never generates a non-increasing segment). The only examples I've found are linearly increasing sequences; i.e., $x_n = an+b,\ \ a>0.$ Are there others?

2. What property of a sequence guarantees that it will never produce Pattern A in a particular place (i.e., that a particular increasing adjacent pair $(a,b)$ does not eventually get replaced by a non-increasing pair)?

   For the sequence of primes, here's a picture showing whether the first $80$ (overlapping) pairs in each odd row are increasing $(+)$ or non-increasing $(-)$; i.e., Pattern A occurs at every $(-)$. The index here counts how many odd rows precede it:

For the sequence of primes, do all pairs -- no matter how far down a row -- eventually become non-increasing (and hence exhibit Pattern A)?

Many very regular sequences have proper sub-regions where Pattern A seems to never appear, e.g., the Fibonacci sequence:

How to prove here that the $(+)$ (increasing) pairs in alternate positions never get converted to $(-)$ (non-increasing) pairs?