There is no statistical test that assesses whether a sequence of observations, time series, or residuals in a regression model, exhibits independence or not. Typically, what data scientists do is to look at auto-correlations and see whether they are close enough to zero. If the data follows a Gaussian distribution, then absence of auto-correlations implies independence. Here however, we are dealing with non-Gaussian observations. The setting is similar to testing whether a pseudo-random number generator is random enough, or whether the digits of a number such as π <\/span>behave in a way that looks random, even though the sequence of digits is deterministic. Batteries of statistical tests are available to address this problem, but there is no one-fit-all solution.<\/p>\n Here we propose a new approach. Likewise, it is not a panacea, but rather a set of additional powerful tools to help test for independence and randomness. The data sets under consideration are specific mathematical sequences, some of which are known to exhibit independence \/ randomness or not. Thus, it constitutes a good setting to benchmark and compare various statistical tests and see how well they perform. This kind of data is also more natural and looks more real than synthetic data obtained via simulations. <\/p>\n 1. Definition of random-like sequences<\/strong><\/span><\/p>\n Since we are dealing with deterministic sequences (xn<\/span><\/em>) indexed by n<\/em> = 1, 2, and so on, it is worth defining what we mean by independence<\/em> and random-like<\/em>. These two elementary concepts are very intuitive, but a formal definition may help. You may skip this section if you have an intuitive understanding of the concepts in question, as the layman does. Independence in this context is sometimes called asymptotic independence<\/em>, see here<\/a>. Also, for all the sequences investigated here, xn<\/span><\/em> ∈ [0,1].<\/p>\n 1.1. Definition of random-like and independence<\/strong><\/p>\n A sequence (xn<\/span><\/em>) with xn<\/span><\/em> ∈ [0,1] is random-like<\/em> if it satisfies the following property. For any finite index family h<\/em>1<\/span>,…, hk<\/span><\/em> and for any t1<\/span><\/em><\/span>,…, tk<\/span><\/em> ∈ [0,1], we have <\/p>\n The probabilities are empirical probabilities, that is, based on frequency counts. For instance,<\/p>\n where χ(A<\/em>) is the indicator function (equal to 1 if the event A<\/em> is true, and equal to 0 otherwise). Random-like implies independence, but the converse is not true. A sequence is independently distributed<\/em> if it satisfies the weaker property <\/p>\n Random-like means that the xn<\/span><\/em>‘s all have the same underlying uniform distribution on [0, 1], and are independently distributed. <\/p>\n 1.2. Definition of lag-k<\/em> autocorrelation<\/strong><\/p>\n Again, this is just the standard definition of auto-correlations, but applied to infinite deterministic sequences. The lag-k<\/em> auto-correlation ρk<\/em><\/span> is defined as follows. First define ρk<\/em><\/span>(n<\/em>) as the empirical correlation between (x<\/em>1<\/span>,…, xn<\/span><\/em>) and (xk<\/span><\/em>+1<\/span>,… ,xk<\/span><\/em>+n<\/em><\/span>). Then ρk<\/em><\/span> is the limit (if it exists) of ρk<\/em><\/span>(n<\/em><\/span>) as n<\/em> tends to infinity. <\/p>\n 1.3. Equidistribution and fractional part denoted as { }<\/strong><\/p>\n The fractional part of a positive real number x<\/em> is denoted as { x<\/em> }. For instance, { 3.141592 } = 0.141592. The sequences investigated here come from number theory. In that context, concepts such as random-like and identically distributed are rarely used. Instead, mathematicians rely on the weaker concept of equidistribution<\/em>, also called equidistribution modulo 1. Closer to independence is the concept of equidistribution in higher dimensions, for instance if two successive values (xn<\/span><\/em>, xn<\/span><\/em>+1<\/span>) are equidistributed on [0, 1] x [0, 1].<\/p>\n A sequence can be equidistributed yet exhibits strong auto-correlations. The most famous example is the sequence xn<\/span><\/em> = { αn<\/em> } where α<\/em> is a positive irrational number. While equidistributed, it has strong lag-k<\/em> auto-correlations for every strictly positive integer k<\/em>, and it is anything but random-like. A sequence that looks perfectly random-like is the digits of π<\/span>: they can not be distinguished from a realization of a perfect Bernouilli process<\/a>. Such random-like sequences are very useful in cryptographic applications.<\/p>\n 2. Testing well-known sequences<\/strong><\/span> <\/p>\n The sequences we are interested in are xn<\/span><\/em> = { α n<\/em>^p<\/em> } <\/b> where { } is the fractional part function (see section 1.3), p<\/em> > 1 is a real number and α<\/em> is a positive irrational number. Other sequences are discussed in section 3. It is well known that these sequences are equidistributed. Also, if p<\/em> = 1, these sequences are highly auto-correlated and thus the terms xn<\/span><\/em>‘s are not independently distributed, much less random-like; the exact theoretical lag-k<\/em> auto-correlations are known. The question here is what happens if p<\/em> > 1. It seems that in that case, there is much more randomness. In this section, we explore three statistical tests (including a new one) to assess how random these sequences can be depending on the parameters p<\/em> and α<\/em>. The theoretical answer to that question is known, thus this provides a good case study to check how various statistical tests perform to detect randomness, or lack of it.<\/p>\n 2.1. The gap test<\/strong><\/p>\n The gap test (some people may call it run test) proceeds as follows. Let us define the binary digit dn<\/span><\/em> as dn<\/span><\/em> = ⌊2xn<\/span><\/em>⌋. The brackets represent the integer part function. Say dn<\/span><\/em> = 0 and dn<\/span><\/em>+1 <\/span>= 1 for a specific n. If dn<\/span><\/em> is followed by G<\/em> successive digits dn<\/span><\/em>+1<\/span>,…, dn<\/span><\/em>+G<\/em><\/span> all equal to 1 and then dn<\/span><\/em>+G<\/em>+1<\/span> = 0, we have one instance of a gap of length G<\/em>. Compute the empirical distribution of these gaps. Assuming 50% of the digits are 0 (this is the case in all our examples), then the empirical gap distribution converges to a geometric distribution of parameter 1\/2 if the sequence xn<\/span><\/em> is random-like.<\/p>\n This is best illustrated in chapter 4 of my book Applied Stochastic Processes, Chaos Modeling, and Probabilistic Properties of Numeration Systems, <\/em>available here<\/a>. <\/p>\n 2.2. The collinearity test<\/strong><\/p>\n Many sequences pass several tests yet fail the collinearity test. This test checks whether there are k<\/em> constants a<\/em>1<\/span>, …, ak<\/span><\/em> with ak<\/span><\/em> not equal to zero, such that xn<\/span><\/em>+k<\/em><\/span> = a<\/em>1<\/span> xn<\/span><\/em>+k-1<\/em><\/span> + a<\/em>2<\/span> xn<\/span><\/em>+k<\/em>-2<\/span> + … + ak<\/span><\/em> xn<\/span><\/em> takes only on a finite (usually small) number of values. In short, it addresses this question: are k<\/em> successive values of the sequence xn<\/span><\/em> always lie (exactly, approximately, or asymptotically) in a finite number of hyperplanes of dimension k<\/em> – 1? This test has been used to determine that some congruential pseudo-random number generators were of very poor quality, see here<\/a>. It is illustrated in section 3, with k<\/em> = 2. <\/p>\n Source code and examples for k<\/em> = 3 can be found here<\/a>. <\/p>\n 2.3. The independence test<\/strong><\/p>\n This may be a new test: I could not find any reference to it in the literature. It does not test for full independence, but rather for random-like behavior in small dimensions (k<\/em> = 2, 3, 4). Beyond k<\/em> = 4, it becomes somewhat unpractical as it requires a number of observations (that is, the number of computed terms in the sequence) growing exponentially fast with k<\/em>. However, it is a very intuitive test. It proceeds as follows, for a fixed k<\/em>:<\/p>\n Now plot the M<\/em> vectors (PT<\/span>, QT<\/span><\/em>), each corresponding to a different k<\/em>-uple, on a scatterplot. Unless the M<\/em> points lie very close to the main diagonal on the scatterplot, the sequence xn<\/span><\/em> is not random-like. To see how far away you can be from the main diagonal without violating the random-like assumption, do the same computations for 10 different sequences consisting this time of truly random terms. This will give you a confidence band around the main diagonal, and vectors (PT<\/span>, QT<\/span><\/em>) lying outside that band, for the original sequence you are interested in, suggests areas where the randomness assumption is violated. This is illustrated in the picture below, originally posted here<\/a>: <\/p>\n<\/a><\/p>\n
<\/a><\/p>\n
<\/a><\/p>\n
<\/a><\/p>\n
\n
<\/a><\/p>\n
\n