All two-point correlations equal to $0$, three-point correlation not $0$?

Question

Let $a_1,a_2,a_3,\dotsc \in \{-1,1\}$ be a sequence. Suppose that, for all $j>0$ and all $\epsilon, \epsilon'\in \{-1,1\}$, the proportion of $n\geq 1$ such that $(a_n,a_{n+j}) = (\epsilon,\epsilon')$ is $1/4$ (in the limit). I would like to see an example of such a sequence for which the average $S$ of $a_n a_{n+1} a_{n+2}$ is non-zero.

(... or doesn't exist; that would also be interesting.)

Reasons why this does not seem utterly trivial:

(a) We cannot have $S=1$ or $S=-1$; in fact, it's not too hard to show (using Cauchy-Schwarz) that $|S|\leq 1/\sqrt{2}$.

(b) Trying to produce such a sequence by a Markov chain where $a_{n+2}$ takes the value $1$ with probability $p_{(a_n,a_{n+1})}$ fails; that is, the only way in which the conditions are fulfilled (that is, all configurations $(a_n,a_{n+j})$ are equally likely) is if $p(a_n,a_{n+1}) = 1/2$ for every choice of $(a_n,a_{n+1})$. In other words, we would need a Markov chain of greater "depth".

Further, more open-ended question: what would be a "magic sauce" condition such that, if all configurations $(a_n,a_{n+j}) = (\epsilon,\epsilon')$ are equally likely for every $j$, and $\{a_n\}_n$ has "magic sauce", then the average of $a_n a_{n+1} a_{n+2}$ is zero?

Answer 1

I think you could make such an example by choosing any normal sequence $S$ on the alphabet $\{0,1,2,3\}$, and then applying the letter-to-word substitution $\tau$ defined by $0 \mapsto +++$, $1 \mapsto +--$, $2 \mapsto -+-$, $3 \mapsto --+$. (I'm abbreviating $1$ by $+$ and $-1$ by $-$.)

The twofold independence comes from normality of $S$; you basically just check that for any $0 \leq i,j < 3$ (representing locations within the $3$-blocks in the image of $\tau$), that the $16$ values $(\tau(a))(i), (\tau(b))(j)$ for $a,b \in \{0,1,2,3\}$ contain all four possible pairs four times each.

The lack of independence for $x_n x_{n+1} x_{n+2}$ is because of the lack of independence in the words $\tau(a)$; for $n$ a multiple of $3$, this product is always equal to $+1$, and for $n$ a non-multiple of $3$, the product is uniformly distributed over $+1$ and $-1$ for similar reasons as the pairwise independence argument above. So the average of $x_n x_{n+1} x_{n+2}$ should be $1/3 \cdot 1 + 1/3 \cdot 1 + 1/3 \cdot -1 = 1/3$. (Obviously some details are omitted here...)

Answer 2

$\def\ZZ{\mathbb{Z}}\def\RR{\mathbb{R}}$Here is a suggestion, with some details missing. Let $\theta$ be an irrational number and set $r_n = \{ \theta n^2 \}$, where $\{ \alpha \}$ is the fractional part of $\alpha$. Then I claim that the pairs $(r_n, r_{n+j})$ are equidistributed in $(\RR/\ZZ)^2$, but $(r_n, r_{n+1}, r_{n+2})$ is not equidistributed in $(\RR/\ZZ)^{3}$.

Proof of pairwise equidsitribution: To see that $(r_n, r_{n+j})$ is $0$, we just need to check that the expected value of $\exp((2 \pi i) (a r_n + b r_{n+j})$ is nonzero for any $(a,b) \in \ZZ^2 \setminus \{ (0,0) \}$. In other words, we need the expected values of $\exp((2 \pi i) \theta ((a+b) n^2 + 2bj n + b j^2))$ to be $0$. This follows from Weyl's equidistribution theorem, since it is impossible that $a+b=2b=0$ for $(a,b) \neq (0,0)$. $\square$

Proof of triple non-equidsitribution: We have $(\theta (n+2)^2) - 2 \theta (n+1)^2 + \theta n^2 = 2 \theta$. So $$r_{n+2} - 2 r_{n+1} + r_n = 2\theta \bmod \ZZ.$$ We also know that $$-2 \leq r_{n+2} - 2 r_{n+1} + r_n \leq 2.$$ So $r_{n+2} - 2 r_{n+1} + r_n$ lies on $4$ hyperplanes through the cube $[0,1)^3$. $\square$

Now, choose any function $f : \RR/\ZZ \to \{ \pm 1 \}$ with average value $0$. Then $f(r_n)$ will have all pointwise correlations $0$, but there is no reason that the triple correlation should vanish.

It probably wouldn't be hard to explicitly show that the triple correlation doesn't vanish, for some well chosen $f$, but I'll stop here.

Answer 3

Let $\{b_n\}_{n \ge 1}$ be a sequence of independent random variables taking the values $\pm 1$ with probability $1/2$ each. Define $\{a_n\}_{n \ge 1}$ by $a_n=b_{n-1} b_{n-2}$ if $\; n \equiv 0 \mod 3$ and $a_n=b_n$ otherwise. Then the variables $a_n$ are pairwise independent. For example, if $\epsilon, \sigma \in {\pm1 }$ then $P(a_2=\epsilon,a_3=\sigma)=P(a_1=\sigma\epsilon, a_2=\sigma)=1/4$.

Thus, by the Law of large numbers, for all $j>0$ and all $\epsilon, \sigma\in \{-1,1\}$, the limiting proportion of $n\geq 1$ such that $(a_n,a_{n+j}) = (\epsilon,\sigma)$ is $1/4$ with probability 1. (Formally, to apply the LLN, consider for each integer $\ell \in [0,2j)$ the limiting proportion of $k\geq 1$ such that $(a_{2kj+\ell},a_{2kj+\ell+j}) = (\epsilon,\sigma)$, then average over $\ell$.) However, the asymptotic average of $a_n a_{n+1} a_{n+2}$ is $1/3$ almost surely.