3
$\begingroup$

Is there a proof that for the sequence $x_{n+1}=4x_n(1-x_n)$, the lag-$m$ autocorrelation for $m=1,2$ and so on, is zero if you start with a random seed $x_0$, or say $x_0=\frac{1}{3}$?

It is defined as follows:

$$ \rho(m) = \lim_{n\rightarrow\infty} \frac{1}{8n}\sum_{k=1}^n \Big(x_k-\frac{1}{2}\Big)\Big(x_{k+m}-\frac{1}{2}\Big). $$

Just asking as there are plenty of authors spending a lot of time doing computations to show it is very close to zero, in the context of random number generation. I have an elegant proof that it is exactly zero regardless of $m>0$, I'd like to publish it but I'm wondering if such a fundamental result was not already proved long ago. If you start with a random seed, then $\rho(m)$ is a.s. zero. If you start with $x_0=\frac{1}{3}$, it would be zero if the number $\pi^{-1}\arcsin(\sqrt{1/3})$ is normal in base 2. Proving the latter is a very hard, unsolved problem, although everyone strongly believe this conjecture (about normalcy) to be true.

Update

To avoid confusion, here is a different (simplified) version of the problem. If it has been proved (which I suspect, but could not find any reference), would love to see a reference. If not, I have a proof but rather than sharing it, I'd encourage readers to try to prove it. It's not that hard, but not trivial either. Happy to share my proof too if there is interest.

Assume $X_0$ has a $\text{Beta}[\frac{1}{2},\frac{1}{2}]$ distribution. Let $X_{k+1}=4X_k(1-X_k)$. Then $\text{E}[X_0 X_k] = \text{E}[X_0] E[X_k]$ for all $k>0$.

$\endgroup$
12
  • 1
    $\begingroup$ What do you mean with 'is zero if you start with a random seed'? What sort of randomness and how do you say it is zero? There are certainly some seeds where your definition of $\rho(m)$ it is not zero. $\endgroup$ Commented Mar 2, 2023 at 10:38
  • $\begingroup$ Say $x_0$ is uniformly distributed on $[0,1]$. If instead $x_0\sim \text{Beta}[1/2, 1/2]$ then $x_1,x_2$ and so on all have the same Beta distribution, which is the invariant measure in this case. If $x_0$ is uniform, $x_n$ eventually has that same Beta distribution when $n\rightarrow\infty$. $\endgroup$ Commented Mar 2, 2023 at 13:57
  • $\begingroup$ I can share my proof if you are interested. There's nothing wrong about it, I'm just interested to know if this has been proved in the past, possibly 100 years ago. I could not find any proof. Then you are welcome to post your own proof. Mine has some little tricks but in the end it is no more advanced than what you would expect from a student in a master thesis in stats or math. Of course it assumes ergodicity of the sequence, which I am sure is well established. $\endgroup$ Commented Mar 2, 2023 at 14:03
  • $\begingroup$ It is not so clear what you are trying to proof. $\rho(m)$ is non-zero for infinitely many values of $x_0$. So that is probably not what you want to show. But do you want to compute something for a distribution of starting points $x_0$ that we have the average of $\rho(m)$ is zero or show that $\rho(m) = 0$ almost surely? $\endgroup$ Commented Mar 2, 2023 at 15:40
  • 1
    $\begingroup$ So just showing it for $x_0 = \frac{1}{3}$ is not enough right? It needs to work for all numbers except a fraction with zero density. $\endgroup$ Commented Mar 2, 2023 at 16:29

1 Answer 1

2
$\begingroup$

A derivation of $\mathbf{E[X_0X_k] = 1/4}$

The solutions of this special case of the logistic map can also be written parameterized by $\theta$

$$x_n(\theta) = \frac{1}{2} - \frac{1}{2} \cos(2^n\pi \theta )$$

And the case $X_0 \sim Beta(\frac{1}{2},\frac{1}{2})$ would be similar to $\theta \sim U(0,1)$ (a typical transformation between the uniform distribution and the arcsine distribution).

Below are some graphs of this transformation from $\theta$ to $x_n$ for different $n$

example

The expectation of $x_0x_k$ can be written as the integral

$$\begin{array}{} E[x_kx_n] &=& \int_{0}^1 x_0(\theta) x_n(\theta)f(\theta) \,\text{d}\theta\\& = &\int_{0}^1 \left( \frac{1}{2} + \frac{1}{2} \cos(2^k\pi \theta ) \right) \left( \frac{1}{2} + \frac{1}{2} \cos(2^n\pi \theta ) \right) \text{d}\theta \\ &=& \begin{cases} \frac{1}{4} & \quad \text{if $k\neq n$} \\ \frac{3}{8} & \quad \text{if $k = n$} \end{cases} \end{array}$$

Where the last equation is found by using the fact that the product of the cosine terms with different frequencies cancel because they are orthogonal.

Other distributions than $\mathbf{X_0 \sim Beta[1/2,1/2]}$

Also when we would start with a different distribution as $\theta = U(0,1)$ if it is a continuous distribution, then eventually we will approach the same result.

We can cut the domain of $\theta$ into $2^n$ evenly spaced intervals and each interval will eventually be distributed as an arcsine distribution This is because the image $x_n$ of $\theta \in (k \frac{1}{2^n}, (k+1) \frac{1}{2^n})$ such intervals is similar to the image $x_0$ of $\theta \in (0,1)$.

Then by letting $n \to \infty$ the domain of any continuous distribution will eventually be able to be split up into intervals, except for some part whose density approaches zero, that all map to the arcsine distribution.

What if $\mathbf{x_0 = 1/3}$

I don't think that the above result is strong enough to be able to say anything about specific cases.

We already have for the set $x_0 = q^2$ with $q$ a rational number between zero and one, that the $x_n$ will have a cycling behaviour.

In addition we may have that for other numbers $x_0$ we have $\rho(m) \neq 0$. The above result only tells that $E[\rho(m)] = 0$ when we average over all numbers. We could have a set of numbers, with non-zero density, for which $\rho(m) \neq 0$ as long as the negative and positive cases are cancelling out in an average over a distribution.

$\endgroup$
4
  • $\begingroup$ Thank you! I will add a reference to your proof in my upcoming book on chaotic dynamical systems. My proof uses similar arguments. The main difference is that I say that the integral leading to $1/4$ if $k=n$ and $3/8$ if $k\neq n$ (actually a different but similar integral) is a special case of a general integral that is true if you replace $2^k$ by $k'$ and $2^n$ by $n'$ for all integers $k', n'$, not just powers of $2$. $\endgroup$ Commented Mar 3, 2023 at 15:34
  • $\begingroup$ Yes the case $x_0=1/3$ or any other specific case other than artificially manufactured numbers, is (and may forever) be impossible to prove. To see this, use the homomorphism between the full chaotic logistic map and the dyadic map. Proving the case for $1/3$ is equivalent to proving that the binary digits of $\pi^{-1}\arcsin\sqrt{1/3}$ have no autocorrelation of any lag. Something I am working on but I am nowhere close to a solution. Possibly the coolest result obtained so far is that binary digits of numbers such as (say) $\sqrt{2}$ and $\sqrt{3}$ are uncorrelated. $\endgroup$ Commented Mar 3, 2023 at 15:46
  • $\begingroup$ [Continued] See the proof (on this very forum!) at stats.stackexchange.com/questions/422354/… $\endgroup$ Commented Mar 3, 2023 at 15:47
  • $\begingroup$ One final comment: the set of numbers with $\rho(m)\neq 0$ has zero density. A consequence of the proven fact that non-normal numbers in base 2 (dyadic map) have a zero density. That said, that are infinitely many such numbers. $\endgroup$ Commented Mar 3, 2023 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.