René Blacher

Fibonacci congruences and applications

Keywords: Fibonacci sequence, Random numbers, Congruence, Dependence, Correct models Suite de Fibonacci, Nombres aléatoires, Modelès corrects, Congruence

When we consider a congruence T (x) ≡ ax modulo m as a pseudo random number generator, there are several means of ensuring the independence of two successive numbers. In this report, we show that this dependence depends on the continued fraction expansion of m/a. We deduce that the congruences such that m and a are two successive elements of Fibonacci sequences are those having the weakest dependence. We will use this result to obtain truly random number sequences x n . For that purpose, we will use non-deterministic sequences y n such that the conditional probabilities have Lipschitz coefficients not too large. They are transformed using Fibonacci congruences and we will get by this way sequences x n . These sequences x n admit the IID model for correct model.

Introduction 1.Fibonacci Congruence

One needs a transformation which transforms the elements of {0, 1, ...., m -1} in independent numbers. Simplest is to use a congruence T (x) ≡ ax mod(m). Indeed, the dependence induced by T n (x 0 ), ....., T n+p (x 0 ) is easy to know. In particular, one can use the spectral test or the results of Dieter which allow to choose the best "a" and "m" (cf [START_REF] Dieter | Statistical interdependence of pseudo-random numbers generated by the linear congruential method, Applications of Number Theory to Numerical Analysis[END_REF], [START_REF] Knuth | the Art of Computer Programming[END_REF]) .

Then, in this report, we study the set E 2 = ℓ, T (ℓ) | ℓ ∈ {0, 1, ....., m-1} when z ≡ z modulo m and 0 ≤ z < m if z ∈ Z. We will understand that this dependence depends on the continued fraction m a , i.e. it depends on sequences r n and h n defined in the following way.

Notations 1.1 Let r 0 = m, r 1 = a. One denotes by r n the sequence defined by r n = h n+1 r n+1 + r n+2 the Euclidean division of r n by r n+1 when r n+1 = 0. Moreover, one denotes by d the smallest integer such as r d+1 = 0. One sets r d+2 = 0.

One sets k 0 = 0, k 1 = 1 and

k n+2 = h n+1 k n+1 + k n if n + 1 ≤ d.
Then, dependence depends on the h i 's : more they are small, more the dependence is weak.

Theorem 1 Let (x 0 , y 0 ) ∈ E 2 . Let R 0 = [x 0 , x 0 + k n ] ⊗ [y 0 , y 0 + r n-2 [ and let R 0 = R 0 , be the rectangle R 0 modulo m. Then If n is even, E 2 ∩ R 0 = (x 0 + k n-1 ℓ , y 0 + r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 . Moreover the points (x 0 + k n-1 ℓ , y 0 + r n-1 ℓ) are lined up modulo m .

If n is odd, E 2 ∩ R 0 = (x 0 + k n-2 + k n-1 ℓ , y 0 + r n-2r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 . Moreover, the points (x 0 + k n-2 + k n-1 ℓ , y 0 + r n-2r n-1 ℓ) are lined up modulo m.

Of course, in general, it is only on the border that R 0 , the rectangle modulo m, satisfies R 0 = R 0 . If not, R 0 is a normal rectangle.

For example if x 0 = y 0 = 0, this theorem means that the rectangle [0, k n /2] ⊗ [r n-2 /2, r n-2 [ does not contain points of E 2 if n is even : [START_REF] Knuth | the Art of Computer Programming[END_REF] is large, that will mean that an important rectangle of R 2 is empty of points of E 2 : that will mark a breakdown of independence.

E 2 ∩ [0, k n /2] ⊗ [r n-2 /2, r n-2 [ = ∅ . If h n-
As h i ≥ 1, the congruence which defines the best independence of E 2 will satisfy h i = 1 and h d = 2. In this case we call it congruence of Fibonacci. Indeed, there exists n 0 such that a = f i n0 and m = f i n0+1 where f i n is the sequence of Fibonnacci : f i 1 = f i 2 = 1, f i n+2 = f i n+1 + f i n . Moreover sequences h n and k n are the sequence of Fibonacci except for the last terms.

Application : building of random sequence

To have IID random number1 two methods exists : use of pseudo-random generators (for example the linear congruence) and use of random noise (for example Rap music). But, up to now no completely reliable solution had been proposed (cf [START_REF] Schneier B | Applied Cryptography 2nd Edition[END_REF]). To set straight this situation, Marsaglia has created a Cd-Rom of random numbers by using sequences of numbers provided by Rap music (cf [START_REF] Marsaglia G | CD ROM[END_REF], page 3 of [START_REF] Knuth | the Art of Computer Programming[END_REF]). But, it does not have proved that the sequence obtained is really random.

Congruences of Fibonacci cannot be used in order to directly generate good pseudo random sequences because T 2 = ±Id where Id is the identity (cf page 141 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). However, by using Fibonacci congruences, there exists simple means of obtaining random sequences whose the quality is sure : one uses the same method as Marsaglia, but one transforms the obtained sequence by using functions T q defined by the following way. Definition 1.2 Let q ∈ N * . Let T be the congruence of Fibonacci modulo m. We define the function of Fibonacci T q by T q = P r q • T where 1) T (x) = T (mx)/m, 2) P r q (z) = 0, b 1 b 2 ....b q when z = 0, b 1 b 2 ... is the binary writing of z.

In order to build IID sequences, we will need to have a truly random sequence ỹn = my n ∈ {0, 1, ...., m -1}, n=1,2,....,N, admitting for model a sequence of random variables Ỹn defined on a probability space (Ω, A, P ). We will need that Y n = Ỹn /m satisfies the following condition : the conditional probabilities of Y n admit densities with Lipschitz coefficient bounded by K 0 not too large.

In fact, since Y n is with discrete value, we can always assume that Y n has a continuous density with respect to µ m , where µ m is the uniform measure : µ m (k/m) = 1/m for all k such that k ∈ {0, 1, ...., m -1}. One can always admit that this density has a Lipschitz coefficient bounded by K 0 > 0. The assumption which we make about Y n is that K 0 is not too large.

We will see in Section 8 that there is such sequences y n .

So, in Proposition 6.1, we shall prove easily that the conditional probabilities of T q (Y n ) check

P T q (Y n ) = x 0 Y n-1 = y ′ 1 , Y n-2 = y ′ 2 , ...., Y n+1 = y" 1 , Y n+2 = y" 2 , ..... = (1/m)[1+O(1)K 0 2 q /m] .
By setting X n = T q (Y n ) and x n = T q (y n ), we shall deduce that

P X n = x 0 X n-1 = x ′ 1 , X n-2 = x ′ 2 , ...., X n+1 = x" 1 , X n+2 = x" 2 , ..... = (1/m)[1+O(1)K 0 2 q /m] ,
and that, for all Borel set Bo ⊂ {0/2 q , 1/2 q , ...., (2 q -1)/2 q } N ,

P (X 1 , ...., X N ) ∈ Bo = L(Bo)[1 + O(1)ǫ] ,
where |ǫ| ≤ K 0 N 2 q /m and where L is the measure corresponding to the Borel measure in the case of discrete space. We prove this result in Section 6.

We shall choose m and q such that ǫ is small enough. Indeed, if ǫ is small enough with respect to N, the size of sample, then x n = T q (y n ) cannot be differentiated from an IID sequence.

Indeed, it is wellknown that, for a sample x n , there is many correct models : in particular, if x n is a sample of an IID sequence of random variables, models such that P {(X 1 , ...., X N ) ∈ Bo} = L(Bo)[1 + ǫ Bo ], |ǫ Bo | ≤ ǫ, are correct if ǫ is small enough. Reciprocally, if the sequence of random variables X n checks P {(X 1 , ...., X N ) ∈ Bo} = L(Bo)[1 + ǫ Bo ], the model IID is also a correct model for the sequence x n . Thus one will be able to admit that IID model is a correct model for the sequences x n . As a matter of fact, one will be even able to admit that there exists another correct model Y θ0 n of y n such that T q (Y θ0 n ) is exactly the IID sequence. We shall prove this result in proposition 5. [START_REF] Knuth | the Art of Computer Programming[END_REF].

In fact, we must know what is called a correct model. We will discuss this problem in Section 4.

So finally we can build sequences x n admitting for correct model the IID model. This means that, a priori, these sequences x n behave as random sequences. It is always possible that they do not satisfy certain tests. But it will be a very weak probability as we know that it is the case for samples of sequences of IID random variables.

By using this technique, we have created such real sequences x n by using various texts. We have tested the sequence x n with classical Diehard tests, and higher order correlation coefficients. Results are in accordance with what we waited : the hypothesis "randomness" is accepted by all these tests (cf section 9.2) . One can obtain such real random sequences in [START_REF] Blacher R | File of random Number[END_REF].

By this method, we therefore have a means to develop the technique used by Marsaglia to create a CD-ROM. We can indeed prove mathematically that the sequence obtained can be regarded a priori as random, what Marsaglia did not.

One sets k

0 = 0, k 1 = 1 and k n+2 = h n+1 k n+1 + k n if n + 1 ≤ d.
Then we have the writing of m/a in continued fraction :

m a = h 1 + 1 h 2 + 1 h3+ 1 h 4 +.... . Now, h n ≥ 1 for all n=1,2,...,d and r d-1 = h d r d + r d+1 = h d r d + 0 = h d r d .
The full sequence r n is thus the sequence r 0 = m, r 1 = a, .........., r d+1 = 0, r d+2 = 0. Then, if T is a Fibonacci conguence, r n is the Fibonacci sequence f i n , except for the last terms.

Remark that if h n = 1 for n=1,2,...,d-1, k n is also the Fibonacci sequence for n=1,2,...,d. Indeed by definition,

k 0 = 0, k 1 = 1, k 2 = 1 and k n+2 = k n+1 + k n if n + 1 ≤ d.

Theorems

Now, in order to prove the theorem 1, it is enough to prove the following theorem.

Theorem 2 Let n ∈ {2, 3...., d}. Then If n is even , E 2 ∩ [0, k n [⊗[0, r n-2 [ = (k n-1 ℓ , r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 . Moreover the points (k n-1 ℓ , r n-1 ℓ) are lined up. If n is odd, E 2 ∩ ]0, k n ]⊗]0, r n-2 ] = (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 . Moreover, the points (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) are lined up.
Then, if there exists h i large, there is a breakdown of independence. For example suppose n=2. Then, one has a wellknown result. Indeed, m = r 0 , r 1 = a, k 1 = 1 and k 2 = h 1 = ⌊m/a⌋ where ⌊x⌋ means the integer part of x. Thus, the rectangle Rect 2 = [0, m/(2a)] ⊗ [m/2, m[ will not contain any point of E 2 . However, this rectangle has its surface equal to m 2 /(4a). Thus if "a" is not sufficiently large, i.e if h 1 is too large, there is breakdown of independence.

Numerical examples

We confirm by graphs the previous conclusion. We suppose m=21. If a = 13, we have a Fibonacci congruence : cf figure 1. If one chooses a=10, sup(h i ) = 20 : cf figure 2 . If one chooses a=5, sup(h i ) = 5 : cf figure 3.

Conclusion

To avoid any dependence, it is necessary that sup(h i ) is small. In the case of the Fibonacci congruence, independence is checked on all rectangles R ect .

., c ′ -1} such that T -1 (k 1 ) < T -1 (k 2 ) < T -1 (k 3 ) < ...... < T -1 (k c ′ -c
). Then, for all numerical simulations which we executed, one has always obtained, for r=0,1,2,....,c'-c-1,

|T -1 (k r )/m -r/N (I)| ≤ ϕ(m)/N (I)
where ϕ(m) << Log(m). In fact, it seems ϕ(m) is the order of Log(Log(m)). Moreover,

M ax r=0,1,....,N (I)-1 N (I)T -1 (k r )/m-r seems maximum when I is large enough : c ′ -c > m/2.
For example, in figures 4, 5 and 6, we have the graphs N (I)T -1 (k r )/mr, r=0,1,....,N(I)-1 for various Fibonacci congruences when c'-c=100.

Proof of theorem 2

In this section, the congruences are conguences modulo m. Now the first lemma is obvious.

Lemma 3.1 For n=3,4,...,d+1, k n+1 > k n > k n-1 . Moreover k n+2 = h n+1 k n+1 + k n is the Euclidean division of k n+2 by k n+1 .
Now, we prove the following results. Proof : We prove this lemma by recurrence. For n=0,

Lemma 3.2 Let n=0,1,2,...,d. If n is even, k n a = m -r n . If n is odd, k n a = r n .
k n a = 0 = 0 = m -m = m -r 0 . For n=1, k n a = a = a = r 1 .
We suppose that it is true for n. One supposes n even. Then,

k n+1 a ≡ ah n k n + ak n-1 ≡ -h n r n + r n-1 = r n+1 . One supposes n odd. Then, k n+1 a ≡ ah n k n + ak n-1 ≡ h n r n -r n-1 = -r n+1 ≡ m -r n+1 . Therefore, k n+1 a = m -r n+1 . Lemma 3.3 Let n=2,3,...,d+1. Let t ∈ {1, 2, ..., k n -1}. If n ≥ 2 is even, r n-1 ≤ at < m -r n . If n ≥ 3 is odd, m -r n-1 ≥ at > r n . Moreover, if n ≥ 2 is even, k n a = m -r n . If n ≥ 3 is odd, k n a = r n .
Proof : The second assertion is lemma 3.2. Now, we prove the first assertion by recurrence.

One supposes n=2. Then, m = r 0 = h 1 r 1 + r 2 = h 1 a + r 2 . Moreover, k 2 = h 1 . If 1 ≤ t < h 1 = k 2 , r 1 = a ≤ at < h 1 a = m -r 2 .
One supposes that the first assertion is true for n where 2 ≤ n ≤ d.

Let 0 < t ′ < k n+1 . Let t ′ = f k n + e be the Euclidean division of t' by k n : e < k n . Then, f ≤ h n . If not, t ′ ≥ (h n + 1)k n + e ≥ h n k n + k n-1 = k n+1 .
One supposes n even.

In this case, r n-1 ≤ at < m -r n for t ∈ {1, 2, ..., k n -1}. Moreover, at ′ ≡ f ak n + ae ≡ f (m -r n ) + ae ≡ -f r n + ae. First, one supposes e = 0. Then, f ≥ 1. Moreover, because n ≥ 2, m -r n ≥ m -f r n ≥ m -h n r n = m -(r n-1 -r n+1 ) = r 0 -r n-1 + r n+1 ≥ r 0 -r 1 + r n+1 > r n+1 . Therefore, because at ′ ≡ -f r n , at ′ = m -f r n . Therefore, m -r n ≥ at ′ > r n+1 . Now, one supposes f < h n and e > 0 . By recurrence, m -r n ≥ ae ≥ ae -f r n ≥ r n-1 -f r n ≥ r n-1 -(h n -1)r n = r n + r n+1 > r n+1 . Therefore, because at ′ ≡ -f r n + ae, at ′ = ae -f r n . Therefore, m -r n ≥ at ′ > r n+1 . One supposes f = h n , e = k n-1 and e > 0. If e = k n-1 , ae = k n-1 a. Indeed, if not, a(e -k n-1 ) = 0. For example, if e -k n-1 > 0, k n > e -k n-1 > 0. Then, because our recurence, a(e -k n-1 ) > r n-1 > 0 : it is impossible. Now, if n = 2, k n-1 a = k 1 a = a = r 1 = r n-1 . Moreover, if n > 2, n ≥ 4. Then, by recurence k n-1 a = r n-1 . Then, if e = k n-1 , ae = k n-1 a = r n-1 . Then, ae > r n-1 . Moreover, m -r n ≥ ae ≥ ae -f r n > r n-1 -f r n ≥ r n-1 -h n r n = r n+1 . Therefore, because at ′ ≡ -f r n + ae, at ′ = ae -f r n . Therefore, m -r n ≥ at ′ > r n+1 . One supposes f = h n and e = k n-1 . Then, t ′ = h n k n + k n-1 = k n+1 . It is oppositite to the assumption.
Then, in all the cases, for t ′ ∈ {1, 2, ...., k n+1 -1}, mr n ≥ at ′ > r n+1 . Therefore, the lemma is true for n+1 if n is even. Then, it is also true for n+1=3.

One supposes n odd with n ≥ 3. In this case, r n < at ≤ mr n-1 for t ∈ {1, 2, ..., k n -1}. Moreover, ak n = r n . Therefore, at ′ ≡ f ak n + ae ≡ f r n + ae.

Assume e = 0. Then, f ≥ 1. Then, r n ≤ f r n ≤ h n r n = r n-1 -r n+1 < m -r n+1 . Then, because at ′ ≡ f r n , r n ≤ at ′ = f r n < m -r n+1 . Assume e > 0 and f ≤ h n -1. By recurrence, r n < ae+f r n ≤ m-r n-1 +f r n ≤ m-r n-1 +(h n -1)r n = m-(r n-1 -h n r n )-r n = m -r n+1 -r n < m -r n+1 . Then, because at ′ ≡ f r n + ae, r n < at ′ = ae + f r n < m -r n+1 Assume e > 0, e = k n-1 and f = h n . Because, e = k n-1 , ae = m -r n-1 . If not, ae = ak n-1 = m -r n-1 . For example, if e > k n-1 ,
a(ek n-1 ) = 0 where 0 < e-k n-1 < k n . Then, by the assumption of recurrence, a(ek n-1 ) > 0. It is impossible. Then, ae < mr n-1 . Then, by recurrence,

r n ≤ ae + h n r n < m -r n-1 + h n r n = m -r n+1 .
Then, because at ′ ≡ h n r n + ae, r n ≤ at ′ = ae + h n r n < mr n+1

One supposes f = h n and e = k n-1 . Then, t ′ = h n k n + k n-1 = k n+1 . It is oppositite to the assumption.

Then the lemma is true for n+1. Lemma 3.4 The following inequalities holds : k d+1 ≤ m.

Proof If t ∈ {1, 2, ..., k d+1 -1}, by lemma 3.3, r d ≤ at < m -r d+1 or m -r d ≥ at > r d+1 , i.e. r d ≤ at < m or m -r d ≥ at > 0 where r d > 0. Then, 0 < at < m or m > at > 0.
Then, if k d+1 > m, there exists t 0 ∈ {1, 2, ..., k d+1 -1} such that t 0 = m, i.e. at 0 = am = 0. It is impossible.

Lemma 3.5 Let t, t ′ ∈ {1, 2, ..., k d+1 -1} such that at = at ′ . Then, t=t'.
Proof Suppose t > t ′ . Then, a(tt ′ ) ≡ 0 and a(tt ′ ) = 0. Then, by lemma 3.3,

r d ≤ a(t -t ′ ) < m -r d+1 or m -r d ≥ a(t -t ′ ) > r d+1 = 0 where r d > 0. Then, 0 < a(t -t ′ ). It is a contradiction. Lemma 3.6 Let n=1,2,...,d. Let H n = h 1 k 1 +h 2 k 2 +h 3 k 3 +.......+h n k n . Then, H n = k n+1 +k n -1. Proof We have H n = h 1 k 1 + h 2 k 2 + h 3 k 3 + ....... + h n-1 k n-1 + h n k n = k 2 -k 0 + k 3 -k 1 + k 4 -k 2 + k 5 -k 3 + k 6 -k 4 + k 7 -k 5 + ........ + k n -k n-2 + k n+1 -k n-1 . Therefore, if n=2m, H n = k 2 -k 0 + k 3 -k 1 + k 4 -k 2 + k 5 -k 3 + k 6 -k 4 + ...... + k 2m -k 2m-2 + k 2m+1 -k 2m-1 = k 2 -k 0 + k 4 -k 2 + k 6 -k 4 + ........ + k 2m -k 2m-2 +k 3 -k 1 + k 5 -k 3 + k 7 -k 5 + ........ + k 2m+1 -k 2m-1 = k 2m -k 0 + k 2m+1 -k 1 = k n+1 + k n -k 1 -k 0 = k n+1 + k n -1.
If n=2m+1

H n = k 2 -k 0 + k 3 -k 1 + k 4 -k 2 + k 5 -k 3 + k 6 -k 4 + ...... + k 2m+1 -k 2m-1 + k 2m+2 -k 2m = k 2 -k 0 + k 4 -k 2 + k 6 -k 4 + ........ + k 2m+2 -k 2m +k 3 -k 1 + k 5 -k 3 + k 7 -k 5 + ........ + k 2m+1 -k 2m-1 = k 2m+2 -k 0 + k 2m+1 -k 1 = k n+1 + k n -1 . Lemma 3.7 Let n=1,2,3,...,d-1 . Let L n = t t = 0, 1, 2, ...., H n . Then, for all n ≥ 1, L n+1 = t = l + gk n+1 l ∈ L n , g ≤ h n+1 . Proof Let l ∈ L n , l ≤ H n . Let g ≤ h n+1 . Therefore, if t = l + gk n+1 , t ≤ H n + h n+1 k n+1 = H n+1 . Therefore, t = l + gk n+1 l ∈ L n , g ≤ h n+1 ⊂ L n+1 .
Reciprocally, let t ∈ L n+1 and let t = f k n+1 + e , e < k n+1 be the Euclidean division of t by k n+1 .

We know that

H n = k n+1 + k n -1 ≥ k n+1 . Therefore, e ≤ H n . Therefore, e ∈ L n . Therefore, if f ≤ h n+1 , t = f k n+1 + e ∈ t = l + gk n+1 l ∈ L n , g ≤ h n+1 . Moreover, if f > h n+1 + 1 , t = f k n+1 + e ≥ (h n+1 + 2)k n+1 + e ≥ h n+1 k n+1 + 2k n+1 = H n+1 -H n + 2k n+1 = H n+1 -k n+1 -k n + 1 + 2k n+1 = H n+1 + k n+1 -k n + 1 ≥ H n+1 + 1 . Therefore, t / ∈ L n+1 . Then, suppose f = h n+1 +1. Then, t = f k n+1 +e = (h n+1 +1)k n+1 +e = h n+1 k n+1 +k n+1 +e = H n+1 -H n + k n+1 + e = H n+1 -k n+1 -k n + 1 + k n+1 + e = H n+1 -k n + 1 + e. Because t ∈ L n+1 and t = H n+1 -k n + 1 + e, e + 1 -k n ≤ 0. Therefore, e ≤ k n -1. Therefore, t = f k n+1 + e = h n+1 k n+1 + k n+1 + e, where k n+1 + e ≤ k n+1 + k n -1 = H n Therefore, t = h n+1 k n+1 + e ′ where e ′ ≤ H n . Therefore, t ∈ t = l + gk n+1 l ∈ L n , g ≤ h n+1 . Therefore, L n+1 ⊂ t = l + gk n+1 l ∈ L n , g ≤ h n+1 . Therefore, L n+1 = t = l + gk n+1 l ∈ L n , g ≤ h n+1 . . Lemma 3.8 Let F n = at t = 0, 1, 2, ...., H n . Let E n = at + km t = 0, 1, 2, ...., H n , k ∈ Z . We set E n = {o n s |s ∈ Z} where o n 0 = 0 et o n s+1 > o n s for all s ∈ Z. Then, for all s ∈ Z, o n s+1 -o n s = r n or o n s+1 -o n s = r n+1 .
Proof We prove this lemma by recurrence. Suppose n=1. Then, r 1 = a, H 1 = h 1 k 1 = k 2 = h 1 . Therefore, F 1 = at t = 0, 1, 2, ..., h 1 = 0, a, 2a, ..., h 1 a = 0, r 1 , 2r 1 , ..., h 1 r 1 = mr 2 . Therefore, the lemma is true for n=1.

Suppose that the lemma is true for n.

Then, E n+1 = at + km t = 0, 1, 2, ...., H n+1 , k ∈ Z , where

H n+1 = h 1 k 1 + h 2 k 2 + h 3 k 3 + ....... + h n+1 k n+1 = H n + h n+1 k n+1 .
Because t ∈ {0, 1, 2, ...., H n+1 }, t ∈ L n+1 . By lemma 3.7, si t ∈ L n+1 , t = l + gk n+1 where g ≤ h n+1 . By lemma 3.2, at ≡ a(l + gk n+1 ) ≡ al + (-1) n+2 gr n+1 ≡ al + (-1) n gr n+1 .

Therefore,

E n+1 = at + km t ∈ L n+1 , k ∈ Z = at + km t = l + gk n+1 , l ∈ L n , g ≤ h n+1 , k ∈ Z = al + (-1) n gr n+1 + km l ∈ L n , g ≤ h n+1 , k ∈ Z = f + (-1) n gr n+1 + km f ∈ F n , g ≤ h n+1 , k ∈ Z = o n s + (-1) n gr n+1 + km s ∈ Z, g ≤ h n+1 , k ∈ Z .
Suppose that n is even.

Then, o n s + (-1) n gr n+1 = o n s + gr n+1 ≤ o n s + r n -r n+2 because gr n+1 ≤ h n+1 r n+1 = r n -r n+2 .
Use the recurrence. Suppose

o n s+1 -o n s = r n . Then, o n s + (-1) n gr n+1 ≤ o n s + r n -r n+2 = o n s+1 -r n+2 . Therefore, {o n+1 t | o n s ≤ o n+1 t < o n s+1 } = {o n s < o n s + r n+1 < .... < o n s + h n+1 r n+1 < o n s+1 } . Therefore, o n+1 t+1 -o n+1 t = r n+1 or r n+2 if o n s ≤ o n+1 t < o n+1 t+1 ≤ o n s+1 . Suppose o n s+1 -o n s = r n+1 . Then, s is fixed . Let T = min{t = 0, 1, ..., |o n s+t+1 -o n s+t = r n }. Therefore, o n s+T +1 -o n s+T = r n . Let O = ∪ T t=0 {o n s+t + gr n+1 | 0 ≤ g ≤ h n+1 }. Then, O = {o n s , o n s+1 , ....., o n s+T -1 } ∪ {o n s+T + gr n+1 | 0 ≤ g ≤ h n+1 }. Therefore, O = {o ′ s , o ′ s+1 , ....., o ′ s+K } where o ′ s ′ +1 -o ′ s ′ = r n+1 . Moreover, o n s+T +1 -o ′ s+K = r n -h n+1 r n+1 = r n+2 . Therefore, if o n+1 t ′ and o n+1 t ′ +1 ∈ {o n+1 t | o n s ≤ o n+1 t ≤ o n s+T +1 }, o n+1 t ′ +1 -o n+1 t ′ = r n+1 or r n+2 .
Suppose that n is odd.

Then, o n s + (-1) n gr n+1 = o n s -gr n+1 ≥ o n s -r n + r n+2 because gr n+1 ≤ h n+1 r n+1 = r n -r n+2 . Suppose o n s -o n s-1 = r n . Then, o n s + (-1) n gr n+1 ≥ o n s -r n + r n+2 = o n s-1 -r n+2 . Therefore, {o n+1 t | o n s ≥ o n+1 t > o n s-1 } = {o n s > o n s -r n+1 > ..... > o n s -h n+1 r n+1 > o n s-1 }. Therefore, o n+1 t -o n+1 t-1 = r n+1 or r n+2 if o n s ≥ o n+1 t > o n+1 t-1 ≥ o n s-1 . Suppose o n s -o n s-1 = r n+1 . Let T = min{t = 0, 1, ..., |o n s-t -o n s-t-1 = r n }. Therefore, o n s-T -o n s-T -1 = r n Let O = ∪ T t=0 {o n s-t -gr n+1 | 0 ≤ g ≤ h n+1 }. Then, O = {o n s , o n s-1 , ....., o n s-T +1 } ∪ {o n s-T -gr n+1 | 0 ≤ g ≤ h n+1 }. Therefore, O = {o ′ s , o ′ s-1 , ....., o ′ s-K } where o ′ s ′ -o ′ s ′ -1 = r n+1 . Moreover, o ′ s-K -o n s-T -1 = r n -h n+1 r n+1 = r n+2 . Therefore, if o n+1 t ′ and o n+1 t ′ -1 ∈ {o n+1 t | o n s ≥ o n+1 t ≥ o n s-T -1 }, o n+1 t ′ -o n+1 t ′ -1 = r n+1 or r n+2 .
Proof 3.9 Now one proves theorem 2.

Suppose that n is even.

Then, k n-1 a = r n-1 , 2k n-1 a = 2r n-1 , ......h n-1 k n-1 a = h n-1 r n-1 = r n -r n-2 . Now, ak n-1 ℓ = ℓr n-1 = ℓr n-1 for ℓ = 0, 1, 2, ...., h n-1 . Therefore, (k n-1 ℓ, r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 = (k n-1 ℓ, ak n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 ⊂ E 2 .
Moreover, r n-2 = h n-1 r n-1 + r n . On the other hand, by lemma 3.8 , all the points of

E 2 = (t, at), t ≤ H n-1 , have ordinates distant of r n or r n-1 .
Therefore, if there is other points of

E 2 ∩ [0, H n-1 ]⊗[0, r n-2 [ that the points (k n-1 ℓ, r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 , there exists ℓ 0 ∈ {1, 2, ...., h n-1 } and (x 1 , y 1 ) ∈ E 2 ∩ [0, H n-1 ] ⊗ [0, r n-2 ] such that r n-1 ℓ 0 -y 1 = r n . Because H n-1 = k n + k n-1 -1 < k n+1 ≤ k d+1
, by lemma 3.5, there exists an only t ∈ {1, ...., H n-1 }, such that at = y 1 : t = x 1 . Because y 1 = 0, there exists an only

t ∈ {0, 1, ...., H n-1 }, such that at = y 1 . Now, r n-1 ℓ 0 -y 1 = aℓ 0 k n-1 -at = r n = -ak n . Then, aℓ 0 k n-1 --ak n = at. Then, a(ℓ 0 k n-1 + k n ) = at. Because r d-1 = h d r d with r d-1 > r d , h d ≥ 2. Moreover, d ≥ n ≥ 2. Then, d -1 > 0. Then, k d-1 > 0.
Then, by lemma 3.4, 0

< k n-1 + k n ≤ ℓ 0 k n-1 + k n ≤ h n-1 k n-1 + k n ≤ k n -k n-2 + k n = 2k n -k n-2 ≤ 2k d < 2k d + k d-1 ≤ h d k d + k d-1 = k d+1 ≤ m. Then, 0 < ℓ 0 k n-1 + k n < k d+1 . Now 0 < t ≤ H n-1 = k n + k n-1 -1 < k d + k d-1 ≤ k d+1 . Moreover, 0 < ℓ 0 k n-1 + k n < k d+1 . Then, because a(ℓ 0 k n-1 + k n ) = at, by lemma 3.5, t = ℓ 0 k n-1 + k n . Then, t = ℓ 0 k n-1 + k n ≥ k n-1 + k n > H n-1 . It is a contradiction.
Therefore, there is not other points of

E 2 ∩ [0, H n-1 ] ⊗ [0, r n-2 [ that (k n-1 ℓ, r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 .
Therefore, there is not other points of

E 2 ∩ [0, k n [⊗[0, r n-2 [ that the points (k n-1 ℓ, r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 .
Therefore,

E 2 ∩ [0, k n [⊗[0, r n-2 [ = (k n-1 ℓ, r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 .
According to what precedes,

(k n-1 ℓ, ak n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 = (k n-1 ℓ, r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 is located on the straight line y = (r n-1 /k n-1 )x if n is even. Suppose that n is odd. Then, k n-2 a = r n-2 , k n-2 a + k n-1 a = r n-2 -r n-1 , k n-2 a + 2k n-1 a = r n-2 -2r n-1 , ......, k n-2 a + h n-1 k n-1 a = r n-2 -h n-1 r n-1 . Therefore, (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 = (k n-2 + k n-1 ℓ , k n-2 a + ℓk n-1 a ℓ = 0, 1, 2, ...., h n-1 ⊂ E 2 . For ℓ = 0, 1, 2, ...., h n-1 , k n-2 + k n-1 ℓ ≤ k n-2 + h n-1 k n-1 = k n . Therefore, (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 ⊂ E 2 ∩ ]0, k n ]⊗]0, r n-2 ] . Moreover, r n-2 -h n-1 r n-1 = r n .
On the other hand, by lemma 3.8 , all the points of

E 2 = (t, at), t ≤ H n-1 , have ordinates distant of r n or r n-1 .
Therefore, if there is other points of

E 2 ∩ [0, H n-1 ]⊗]0, r n-2 ] that the points (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 , there exists ℓ 0 ∈ {1, 2, ...., h n-1 } and (x 1 , y 1 ) ∈ E 2 ∩ [0, H n-1 ] ⊗ [0, r n-2 ] such that y 1 -(r n-2 -r n-1 ℓ 0 ) = r n . Because H n-1 = k n + k n-1 -1 < k n+1 ≤ k d+1
, by lemma 3.5, there exists an only t ∈ {1, ...., H n-1 }, such that at = y 1 . Because y 1 = 0, there exists an only t ∈ {0, 1, ...., H n-1 }, such that at = y 1 .

Then,

y 1 -(r n-2 -r n-1 ℓ 0 ) = at-k n-2 a + ℓ 0 k n-1 a = r n = ak n . Then, at = k n-2 a + ℓ 0 k n-1 a+ ak n . Then, at = a(k n-2 + ℓ 0 k n-1 + k n ). Now, because r d-1 = h d r d with r d-1 > r d , h d ≥ 2. Now, n ≥ 3. Then, d -1 ≥ n -1 > 1. Then, k d-1 > 0. Then 0 < k n-2 + ℓ 0 k n-1 + k n ≤ k n-2 + h n-1 k n-1 + k n ≤ 2k n ≤ 2k d < 2k d + k d-1 ≤ h d k d + k d-1 = k d+1 ≤ m. Now 0 < t ≤ H n-1 = k n + k n-1 -1 < k d + k d-1 ≤ k d+1 . Then, because a(k n-2 + ℓ 0 k n-1 + k n ) = at, by lemma 3.5, t = k n-2 + ℓ 0 k n-1 + k n . Then, t = k n-2 + ℓ 0 k n-1 + k n ≥ k n-1 + k n > H n-1 . It is a contradiction.
Therefore, there is not other points of

E 2 ∩ [0, H n-1 ]⊗]0, r n-2 ] that the points (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 .
Therefore, there is not other points of

E 2 ∩ ]0, k n ]⊗]0, r n-2 ] that the points (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 : i.e. E 2 ∩ ]0, k n ] ⊗ [0, r n-2 [ = (k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 .
According to what precedes,

(k n-2 + k n-1 ℓ , r n-2 -r n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1 = (k n-2 + k n-1 ℓ , ak n-2 + ak n-1 ℓ) ℓ = 0, 1, 2, ...., h n-1
is located on a straight line.

Correct models 4.1 General study

One can always suppose that y n , n=1,2,...,N, is the realization of a sequence of random variables Y n defined on a probability space (Ω, A, P ) :

y n = Y n (ω) where ω ∈ Ω and where Y n is a correct model of y n .
As a matter of fact, there exist an infinity of correct models of y n . It is thus necessary to be placed in the set of all the possible random variables.

.,N, defined on the probabilities spaces

(Ω, A, P θ ), θ ∈ Θ : (Y θ 1 , Y θ 2 , Y θ 3 , Y θ 4 , ............., Y θ N ) : Ω → {0/m, 1/m, ...., (m -1)/m} N . One assumes that Y θ n = Y n for all θ ∈ Θ.
For example, one can assume that Ω = {0, 1, ...., m -1} N and (Y 1 , ...., Y N ) = (Id, ...., Id).

Definitions

It thus raises the question to define correctly what is a correct model. Indeed, if a model Y θ n is not correct, it is however possible that y n = Y θ n (ω) , where Y θ n is a sequence of random variable defined on a probability space (Ω, A, P ).

In the case where the model Y θ n is IID, to define a correct model is a generalization of the already very complex problem of the definition of an IID sequence (cf [START_REF] Knuth | the Art of Computer Programming[END_REF]). However one can have a solution because one wants only to prove that the correct models T q (Y θ n ) will be close to the IID model.

A scientific assumption

Generally, one feels well that correct models exist. In fact, it is a traditional assumption in science. In weather for example, the researchers seek a correct model, which implies its existence (if not, why to try to make forecasts?). One could thus admit that like a conjecture or a postulate without defining exactly what is a correct model.

Definition using tests

Now, in order to know if a sequence y n is a realization of a model Y n , tests are generally used. So we could say that the model Y n is a correct model of a sequence y n if the sequence y n satisfies all the tests that one could make about hypothesis "y n is a realization of Y n " with a frequency equivalent2 to that real realizations of model Y n .

Definitions using estimate

In fact, this is a case a little similar to the definition using the tests. We will estimate the parameters of the distribution of Y n . In order to do this the easiest way is to estimate the marginal distributions and higher order correlation coefficients : cf [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]. This will define the dependence of the model Y n .

In some cases, it is indeed possible. So for some texts, one can admit the Q dependence when Q is not too large (cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] section 10) and perhaps the stationarity. Indeed, in this case, there will need to define only some dependences between Y n , Y n+1 and Y n+2 , for example.

However, in more general cases, this may pose difficulties. Estimators may then be less clear. It is the relation between the coefficients of p variables p and p' variables, p ′ > p, which is a problem. For example if we have a sample of size N = 4, and points on each interval [0,1/2[ and [1/2,1[ of X 1 and X 2 , it is possible that in the associated squares, there is one with an empirical probability equal to 0. If p is large, it is possible that there are many such hypercubes. This raises problems.

But in concrete cases, it is always possible to get estimates for models Y n , n=,2,...,N. It can be assumed that such estimates exist.

Other definition

One can also define a correct model by the following way : if Y n is a correct model for the sequence y n , n=1,2,...,N, that means that the event "the sequence y n is the result of a choice at random of ω ∈ Ω where y n = Y n (ω)" is an event which has reasonable probability to be carried out.

We thus find the same problem as the definition using tests : what is the probability that it is reasonable3 ? But we feel that a such definition means and it is reasonable. The simplest is to assume that it exists.

To predict the future

In fact, a correct model depends on its usefulness. For example, in meteorology, its usefulness is to predict weather.

One can transpose that to unspecified sequences of real numbers y n , n=1,2,....,N. The usefulness of a model will be in general to predict the future. That applies perfectly to the research which we carry out in order to obtain IID sequences : if a sequence is IID random, one will not be able to predict the future knowing the past.

One could thus admit like definition of a correct model this one : a correct model is a model such as, knowing the past Y θ n-s = y ′ n-s , s=1,2,..., this one makes possible to predict the best possible the future. To be more complete, it is necessary to extend this definition to the sequences y φ(n) where φ is a permutation of {1, 2, ...., N }.

It is necessary thus that the forecast is good : it has to be the most precise possible, but, if knowing the past, one predicts the future in a too precise way and that it is not real, the model will be bad.

Let us notice, that, under this condition, we suppose that one does not know the future y φ(n+s) , s=1,2,... : if not, the empirical probability would be a correct model.

Mathematical definition

Mathematically, one can thus specify that: it will be said that Y θ n is a correct model, if, for any permutation φ of {1, 2, ..., N }, for all sequence y ′ s , for all n, it makes possible to give the conditional probability of Y θc φ(n) knowing the past Y θc φ(n-1) = y ′ 1 , Y θc φ(n-2) = y ′ 2 ,....., which is the best possible one.

It will be thus true in particular when y ′ s = y φ(n-s) for s=1,2,3,.... It will thus be known that

P {Y θc φ(n) ∈ Bo | Y θc φ(n-1) = y φ(n-1) , Y θc φ(n-2) = y φ(n-2)
, ......} will be the most precise possible by taking account of what one really knows, i.e the sequence y φ(n-s) .

Therefore, one can nothing object to this conditional probability in order to define the future when what one really knows, it is the sequence y n . Of course it is in question conditional probabilities which one could really deduce from the sample y n if all the mathematical properties were known and if one had an infinite computing power.

Some difficulties

Unfortunately, in these definitions, one made only to move the problem: mathematically, what means "probabilities the most precise possible" and "the best possible"? One understands well what one wishes. But to define it mathematically seems complicated.

However, one can do our study without knowing it. Indeed, which interests us, it is that the

X θ n = T q (Y θ n ) have a law close to an IID distribution. Now, if Y θc n is a correct model, P {Y θc φ(n) ∈ Bo | Y θc φ(n-1) = y ′ 1 , Y θc φ(n-2) = y ′ 2 , .........} defines the future Y θc φ(n) ∈
Bo sufficiently well for all Borel set Bo, when, which one knows, it is the sequence y φ(n) . It will be thus true in particular for [START_REF] Blacher R | Correct models[END_REF]). Therefore, this conditional probability defines a good forecast of the future. That means that if one knows x φ(n-s) , s=1,2,.., a good prediction of x φ(n) will be given by this conditional probability. However we will prove in theorem 3 that [START_REF] Knuth | the Art of Computer Programming[END_REF]ǫ] where ǫ is small enough for the models with a continuous density and a coefficient of Lipschitz K ′ 0 not too large. Moreover, one will understand in section 8 that one can admit that such models are correct if y n is obtained from texts. At last, we shall prove in section 5.9 that, in this case, there exists a correct model Y θc n such that

P {T q (Y θc φ(n) ) ∈ Bo ′ | Y θc φ(n-1) = y ′ 1 , Y θc φ(n-2) = y ′ 2 , .........}, and, therefore, for P {X θc φ(n) ∈ Bo ′ | X θc φ(n-1) = x ′ 1 , X θc φ(n-2) = x ′ 2 , ....} (cf proposition A1
P {X θc φ(n) ∈ Bo ′ | X θc φ(n-1) = x ′ 1 , X θc φ(n-2) = x ′ 2 , ....} = L(Bo ′ )[1+Ob
P {X θc φ(n) ∈ Bo ′ | X θc φ(n-1) = x ′ 1 , X θc φ(n-2) = x ′ 2 , ....} = L(Bo ′ ) if ǫ is small enough.
That means that if one knows x φ(n-s) , s=1,2,.., a good prediction of x φ(n) will be given by uniform probability. Then, we have proved that, there exists a correct model Y θc n such that T q (Y θc n ) is exactly the IID random sequence.

A Problem

It raises a problem : according to the definition which one chooses, it is often the empirical model which is the best model possible. It is a known problem of the definition of an IID sequence : some say there is no random sequence of finite dimension (cf [START_REF] Knuth | the Art of Computer Programming[END_REF] and section 10.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]).

In this case, the IID model is one of the worst model. For example if we use the definition of Section 4.2.4, an increasing sequence x n has as much chance to be realized than a real IID sample IID. In spite of this difficulty, we happens to prove that this model is correct for the sequences T q (y n ). It's almost a feat.

In order to adress this problem, we can try to impose conditions -known a priori or not -like the Lipschitz coefficient not too large. But in this case again, it will be the models whose marginal densities are bumps near each point of the sample y n which are the best. This is also true for a real IID sample : the model with bumps will be the best model possible.

Even if we assumed that the Y n 's have the same distribution, one could assume that each Y n is concentrated only on the points of the sample. One might assume that there is in addition a function g such that Y n+1 = g(Y n ) (in this case, K 0 would be great) .

Other definition

To remedy this, we can introduce a new definition : we say that a model Y n is correct if the hypothesis "y n = Y n (ω)" is an assumption that nothing prevents. This means that y n is perfectly plausible as realization of Y n . Then, expected properties of a such sample should be checked, especially the tests and estimates.

Connection between some definitions

Some definitions have common points : the definition which defines the best conditional probability for all sequences y φ(n) and the definition saying that the hypothesis "y n = Y n (ω)" is a plausible hypothesis (especially using the tests and estimates). In order to understand this connection, it is enough to assume that the conditional probabilities are defined by estimate (e.g. by using higher order correlation coefficients cf [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]). It can be difficult to define all the conditional probabilities depending on the choice of the permutations φ in some cases. But in others cases, it is possible as is the case for texts. In this case the two definitions are almost equivalent because how is it possible to know the conditional probabilities of the model if we are not able to estimate?

In conclusion, a correct model would make possible to obtain the best conditional probability for all sequences y φ(n) , In particular, by taking into account the estimate Does there exist such a model? Presumably, because generally y n represents a physical phenomenon. It is thus normal to suppose its existence. Moreover, in certain cases, one can show such models : it is the case for texts.

Texts

Now, we consider the particular case where the y n 's result from texts.

A priori, a correct model would be a model which makes possible to predict the following letters (y n , y n+1 ,.....) with a satisfactory probability if one knows the preceding letters y n-1 , y n-2 ..... One could thus say that the model will predict all the possible texts which follows the beginning of the text.

We will choose therefore as model the model of all possible texts with the uniform probability (or another: see below). We can also choose more perfect models as all possible texts of the author.

This seems a good model because knowing any subsequence, we can predict the following letters with reasonable probability 4 .

However such a model is too precise: indeed, for sequences representing a text, to suppose that one is in an English text is a priori which is wrong : cf 6) page 307 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. For example, one could logically predict words invented not existing. A model in modern English language would be a correct model. But a model in a possible evolution of the English language would be it too.

These model can be refined besides: if a novel is used, it would be astonishing to find texts speaking about mathematical theorem. Therefore, there are models which make possible to better predict the continuation than others. But it is necessary that is explained by the text which precedes. If one takes only 100 words, one will not deduce from it the style of the author.

In fact in order to admit that only the English texts can represent the y n , it would be necessary that sequence y n consists of a very large number of books which make possible to decode the language. In this case, it is possible that the only correct models are texts, even texts of the author.

Let us suppose that it is the case. That makes possible to define precise correct models. Indeed, in this case, one can admit that the correct model will be that representing all the possible texts written according to the style of the author. Of course, there is an almost infinite number of possible texts as soon as N, the sample size of y n is large.

Concerning the associated probabilities, one can suppose that all the texts are equiprobable. That seems a correct model.

But it is not the alone one. One can choose other probabilities than the equiprobable probability, for example a close probability, even another. Indeed, it seems that certain text are likely more to exist than the different ones. The equiprobable model is thus not the best inevitably. In order to find the best models it would be necessary to find those whose probabilities correspond the best to all which one knows about texts of the author. That seems impossible to realize. But theoretically, it could exist. In fact, there are several suitable models.

It thus seems difficult to find exactly all the possible correct models and especially to find a better model. However, it is felt well that these models including all the texts which the author can write seems rather correct and that there are from them which are better than others.

Therefore, for the texts, one can show correct models. All the possible texts of the author with an about uniform probability seems be a good model. Then this model defines conditional probabilities

P {Y θt φ(n) ∈ Bo|Y θt φ(n-1) = y ′ 1 , Y θt φ(n-2) = y ′ 2
, ....} for all n, for all y ′ s , s=1,2,..., and for all permutation φ. Now, if we use the definition by estimates, we obtain similar results if we assume that we have a very large number of texts at our disposal.

Of course, this is not the case. But it is not serious : what matters to us is being able to increase the Lipschitz coefficients of conditional probabilities. We reach this result by adding a pseudo random and a text written backward (cf section 8).

Conclusion

Thus in certain cases, there exist correct models which enable us to predict the future correctly. One can suppose that the method described for the texts is good and can be generalized.

If this assumption is refused, it may be easier to admit that there exists such correct models defining correctly the conditional probabilities without more precise details as one does it in weather and elsewhere. It was understood that it is enough in order to prove that the IID model is a correct model of x n = T q (y n ).

5 Models equivalent with a margin of ǫ n is also a correct model of y n if ǫ is small enough.

Example

Let us suppose that we have a really IID sequence of random variables X ǫ n with uniform distribution on [0,1/2] and [1/2,1] and with a probability such as P {X ǫ n ∈ [1/2, 1]} = 0, 500[1 + ǫ] where ǫ = 0, 001. Then, this sequence has not the uniform distribution on [0,1]. However, if we have a sample with size 10, we will absoluetely not understand that X ǫ n has not the uniform distribution on [0,1]. It is wellknown that one need samples with size larger than N=1000 minimum in order to test this difference.

More precisely, by the CLT (Central Limit Theorem),

P | P N n=1 (1 [1/2,1] (X ǫ n )-1/2-ǫ/2)| √ N (1-ǫ 2 )/4 ≥ b ≈ Γ(b) where Γ(b) = P {|X G | ≥ b} when X G ∼ N (0, 1). Then, P | P N n=1 (1 [1/2,1] (X ǫ n )-1/2)| √ N/4 ≥ b ≈ Γ b[1 -η(ǫ)]
where η is continuous with η(0) = 0.

More generally, one cannot test significantly H 0 : "X θ n has the uniform distribution" against

H 1 (ǫ) : "P {X θ n ∈ Bo} = L(Bo)[1 + Ob(1)ǫ] " if √ N ǫ ≤ 1/10.
For example, if √ N ǫ = 1/10 and b=2, the probability of obtaining

P N n=1 [1 [1/2,1] (X θ n )-1/2] √ N/4
≥ 2 is about 0.0466 under H 1 (ǫ) and about 0.0455 under H 0 : i.e. the probability of rejecting the assumption IID, H 0 , under H 1 (ǫ) is not much bigger than that of rejecting H 0 if X θ n is really IID (cf also section 4.3 of [START_REF] Blacher R | Correct models[END_REF]).

IID models with a margin of ǫ

These results hold in dimension p , i.e. for 1

N -p n 1 Bo1 (Y θ1 n+j1 )......1 Bop (Y θ1 n+jp ).
One deduces from what precedes that, if x n is the realization of a sequence of random variables X θ n such that P {(X θ 1 , ...., X θ N ) ∈ Bo} = L(Bo)[1+Ob(1)ǫ] for all Borel set Bo, one will not be able to differentiate this model from an IID model if ǫ is rather small with respect to N.

Reciprocally, if x n , n=1,2,....,N, is really an IID sample, a model such that P {(X θ 1 , ...., X θ N ) ∈ Bo} = L(Bo) [1 + ǫ] is also a correct model of the sequence x n .

Because we shall obtain P {(X θ 1 , ...., X θ N ) ∈ Bo} = L(Bo)[1 + ǫ] in theorem 3 if m and q are well chosen, one will be able to admit that the IID model is a correct model of the sequences x n which we built in this report.

Case where the CLT holds

One can adopt assumptions more general than those of the IID case by only supposing that the CLT is checked. For example, assume that the CLT holds and that the Y θ1 n 's have the same distribution for n=1,2,....,N. Let P Y1 (I) = P {Y θ1 n ∈ I} where I is an interval. Let P 1 e = (1/N ) n 1 I (Y θ1 n ) and P 2 e = (1/N ) n 1 I (Y θ2 n ). Let σ 2 B the variance of P 1 e . Then, if N is big enough, by the CLT,

P {|P 1 e -P Y1 (I)| > σ B b} ≈ Γ(b) ,
where Γ(b) = P {|X G | ≥ b} when X G ∼ N (0, 1). Then, it is easy to prove (cf page 8 of [START_REF] Blacher R | Correct models[END_REF])

P {|P 2 e -P Y1 (I)| > σ B b} ≈ Γ(b)[1 + Ob(1)ǫ] .
Then, there will not be possible to conclude that y n is a realization of Y θ1 n rather than of Y θ2 n by testing P Y1 (I). For example, let us suppose N = 10 4 , ǫ = 0.00001. In this case, for b=2,

P {|P 1 e -P Y1 (I)| > 2σ B } ≈ 0.0455, P {|P 2 e -P Y1 (I)| > 2σ B } ≤ c 2 , where c 2 ≈ 0.0500 . Now, if y n is a realization of Y θ1
n , it is known that (1/N ) n 1 I (y n ) is close to P Y1 (I) with a certain probability : it is completely possible that (1/N ) n 1 I (y n ) is enough different from P Y1 (I), but the probability that occurs is weak.

Moreover, if y n is a realization of Y θ2 n , it is also possible that (1/N ) n 1 I (y n ) is enough different from P Y1 (I), but that is not likely much more to occur than if y n is a realization of Y θ1 n . Then, for the test associated to P Y1 (I), it will be thus impossible to differentiate the model Y θ1

n and Y θ2 n as good model for the sequence y n .

These results are not only true for the estimate of only one P Y1 (I), but of several (cf page 9 of [START_REF] Blacher R | Correct models[END_REF] with p s = P {Y θ1 n ∈ I s }) :

P N s 1 N n 1 Is (Y θ2 n ) -p s 2 ≥ a = P N s 1 N n 1 Is (Y θ1 n ) -p s 2 ≥ a [1 + Ob(1)ǫ] .
Then, if ǫ is small enough, one cannot differentiate Y θ1 n and Y θ2 n by this chi squared test.

One can generalize these results in dimension p : one uses n 1 Bo1 (Y θ1 n+j1 )......1 Bop (Y θ1 n+jp ). Of course, one can also generalize to other functions, i.e. to about the totality of the known tests. Because of it, it seems impossible to differentiate Y θ1 n and Y θ2 n as models of y n .

Then, we have just studied the tests associated to these models. In order to be able to apply them it is useful to be able to use the CLT. Now, in general, the sequences y n which we use are asymptotically independent (for example texts or numbers provided by machines). The models where the CLT is checked are thus correct. The conclusions that we deduce of it are thus correct too : it is impossible to differentiate Y θ1 n and Y θ2 n as models of y n . n and Y θ2 n as models of y n in other cases than the case where the CLT holds.

Another case

For example, this results holds also if only the Weak Law of Large Number holds. Indeed one does not know the exact law of P e -P Y1 (I). But it exists theoretically. However, to know this law is not important : it is enough that one has the relation P {|P 2 e -P Y1 (I)| > b} = P {|P 1 e -P Y1 (I)| > b}[1 + Ob(1)ǫ] for all b > 0 in order to be able to conclude from it that one will cannot differentiate the models Y θ1 n and Y θ2 n . Moreover, the inequality of Bienaymé-Tschebischeff shows that the sums divided by the variance are normalized. One deduced from it that one cannot differentiate the effects of these models.

General Case

One now asks if to prove this result in the general case is possible, i.e. if, whatever the model Y θ1 n (for example without tests), the relation

P {(Y θ2 1 , ...., Y θ2 N ) ∈ Bo} = P {(Y θ1 1 , ...., Y θ1 N ) ∈ Bo}[1 + Ob(1)ǫ] implies always that one cannot differentiate Y θ1
n and Y θ2 n . It is maybe the case. But, in order to prove it, there is likely philosophical or other problems of the type of the definition of the randomness of Franklin (cf [START_REF] Knuth | the Art of Computer Programming[END_REF], [START_REF] Franklin | Deterministic simulation of random processes[END_REF]). That is thus likely a complicated study.

But one can say still a certain number of thing in the general case.

Empirical probability

It is observed now that, if a model Y θ1 n is correct and a model Y θ2 n is not correct, it would be necessary that a variation of the probability which would be smaller than P (Y θ1 1 , ......, Y θ1 N ) ∈ Bo ǫ exchange something sufficiently important so that one understands a difference of the models with respect to the sample. Therefore, the probability in question will be close to the empirical probability. Thus the model would be very close to the empirical model.

However, the empirical model is in general a bad theoretical model. Thus, in the case of texts, it is known a priori that the empirical probability is not the good model because it will fail as soon as one increases N. One thus arrives at a contradiction.

Then, even if the empirical probability can be selected like correct model, a probability of a model Y θ2 n where one changes only a little this probability is also correct. It would be thus astonishing that a model as special as the empirical model Y θ1 n satisfies effectively that, if Y θ1 n is correct, an approximate model Y θ2 n will be it also and that an unspecified model does not check this implication. In particular, it would be astonishing for models with continuous density and coefficient of Lipschitz not too large. It would be even astonishing for models with unspecified coefficient of lipschitz, i.e. in the general case. Of course astonishing means that this is intuitive.

Presentation of the intuition

In fact, this intuition is based on the following reasoning: if Y θ1 n is a correct model for the sequence y n , that means that the event "the sequence y n is the result of a choice at random of ω where y n = Y θ1 n (ω)" is an event which has reasonable probability to be carried out. Then, it is not understood what can prevent that y n = Y θ2 n (ω) is a realization equally probable if one changes only a little the probabilities (except in the case studied in section 5.8).

The only cases where they could have problem seem those of the probability concentrated close to some points like the empirical probability. But one has just understood that even in this case, it is still true.

One thus understands well what leads to think that, in all the cases, one will not be able to differentiate Y θ1 n and Y θ2 n .

where

|ǫ ′ Y | ≤ C 0 ≈ ǫ X (q 0 ). Then, |ǫ ′ Y | < ǫ Y .
Then, for all Borel sets Bo,

P (Y θ0 1 , ......, Y θ0 N ) ∈ Bo = P (Y θc 1 , ......, Y θc N ) ∈ Bo [1 + Ob(1)ǫ ′ Y ] . Then, Y θ0
n is a correct model of y n . Moreover T q0 (Y θ0 n ) is the IID model. Now, generally, by theorem 3 one can find models correct Y θc n such that P {(X θc 1 , ..., X θc N ) ∈ Bo} = L(Bo)[1 + Ob(1)ǫ ′ ] where ǫ ′ is increasingly small if q decreases when K 0 is not too large.

Then, we shall understand in section 10 that it is possible to build in practical terms a such sequence y n , i.e. a sequence y n such that the model IID is a correct model of x n .

6 Approximation theorem

Theorem

In this section, we assume that T is a Fibonacci congruence and we use Fibonacci function T q in order to build IID sequences. Notations 6.1 Let Y n ∈ {0/m, 1/m, ...., (m -1)/m}, n=1,2,...,N, be a sequence of random variables defined on a probability space (Ω, A, P ). We define the sequence X n , n=1,2,...,N, by

X n = T q (Y n )
Now we define a measure equivalent to the Borel measure in the discrete case. Notations 6.2 For all p ∈ N * , let L be the measure defined on {0/2 q , 1/2 q , ...., (2 q -1)/2 q } p by L(Bo) = Card(Θ)

2 pq
when Bo = ∪ (k1,...,kp)∈Θ {(k 1 /2 q , ..., k p /2 q )}.

For example, if p=1, and if I = {k/2 q , (k + 1)/2 q , ....., (k ′ -1)/2 q }, L(I) = (k ′k)/2 q the length of interval [k/2 q , k ′ /2 q [. Because Y n is a sequence with values in a discrete space, it always admits a density with respect to the discrete uniform measure. Notations 6.3 We denote by µ m the uniform measure defined on {0/m, 1/m, ...., (m -1)/m} by µ m (k/m) = 1/m for all k ∈ {0, 1, ..., m -1}.

For all permutation φ of {1, 2, ..., N }, for all n ∈ {1, 2, ..., N }, we denote by f n,φ (.|y ′ 1 , y ′ 2 , ....) the conditional density with respect to

µ m of Y φ(n) given Y φ(n-1) = y ′ 1 , Y φ(n-2) = y ′ 2 ,
(y|y ′ 1 , y ′ 2 , ...) -f n,φ (y ′ |y ′ 1 , y ′ 2 , ...)| ≤ K 0 |y -y ′ |.
In order to simplify the proofs we suppose K 0 > 1.

Under these conditions, if m and q are well chosen, X n is approximately the IID sequence : for all Borel set Bo ⊂ {0/2 q , 1/2 q , ...., (2 q -1)/2 q } N , P (X 1 , ...., X N ) ∈ Bo = L(Bo)[1 + Ob(1)ǫ], where ǫ ≈ 0.

Theorem 3 Let γ(m) = [2 + ϕ(m)].
We assume γ(m)N K 0 2 q /m ≈ 0 and m/K 0 >> 1. Then, for all Borel set Bo,

P (X 1 , ...., X N ) ∈ Bo = L(Bo) 1 + γ(m)Ob ′ (1)N K 0 m/2 q .
where |Ob ′ (1)| is increased by a number close to 1.

If K 0 is not too large, there is no difficulty to choose m and q in such a way that ǫ ≤ γ(m)2 q N K 0 /m is small enough. Therefore, P (X 1 , ...., X N ) ∈ Bo = L(Bo) 1 + Ob ′ (1)ǫ .

First proposition

In order to prove theorem 3, we shall use the following proposition. Proposition 6.1 Let h N be the probability density function of Y ∈ {0/m, 1/m, ......, (m -1)/m}, with respect to µ m :

1 0 h N (u)µ m (du) = 1. Let h ′ N = (1/c 0 )h N such that 1 0 h ′ N (u)du = 1. Let K 0 ∈ R + such that |h N (r) -h N (r ′ )| ≤ K 0 |r ′ -r| and |h ′ N (r) -h ′ N (r ′ )| ≤ K 0 |r ′ -r| when r, r ′ ∈ [0, 1].
One supposes 2 q /m ≈ 0, and m/K 0 >> 1 .

Then, the following equality holds :

P {T (mY )/m ∈ I k } = L(I k ) 1 + γ(m)Ob ′ (1)K 0 m/2 q ,
where

I k = [k/2 q , (k + 1)/2 q [, L(I k ) = 1/2 q .
Proof The proof of this proposition is simple : the points of T -1 (mI k ) are well distributed in {0, 1, ...., m-1}. Thus in figure 7, it is easy to understand that the sum of points of

h ′ N (T -1 (mI k )) will be close card mI k ∩ {0, 1, ...., m -1} /m because 1 0 h ′ N (u)du = 1.
: Points of h ′ N [T -1 (mI k )] when h ′ N (t) = sin(4πt) + 1 1 1.2 1.4 1.6 1.8 2 Figure 7
Now in order to prove mathematicaly this proposition, we need the following lemmas.

Lemma 6.1 Let N (I k ) be the number of t/m ∈ {0/m, 1/m, ...., (m -1)/m} such that k/2 q ≤ t/m < (k + 1)/d q . Then, N (I k ) = m/2 q + Ob(1).

Proof We define the interval [c k /m, c ′ k /m[ with c k , c ′ k ∈ {0, 1, ...., m -1} by [c k /m, c ′ k /m[∩{0/m, 1/m, ...., (m -1)/m} = [k/2 q , (k + 1)/2 q [∩{0/m, 1/m, ...., (m -1)/m}. Then, (c k -1)/m < k/2 q ≤ c k /m and (c ′ k -1)/m < (k + 1)/2 q ≤ c ′ k /m. Let m/2 q = h 0 +e where 0 ≤ e < 1 and h 0 ∈ N. Then, N (I k ) = c ′ k -c k = h 0 or N (I k ) = h 0 +1. By our definition h 0 ≤ m/2 q ≤ (h 0 + 1). Then, N (I k ) = m/2 q + Ob(1). Lemma 6.2
The following equality holds :

c 0 = 1 + Ob ′ (1)K 0 m .
Proof The following equalities hold :

1 = t (t+1)/m t/m h ′ N (u)du = t (t+1)/m t/m h ′ N (t/m) + Ob(1)K 0 /m du = 1 m t h ′ N (t/m) + Ob(1)K 0 m = 1 0 h ′ N (u)µ m (du) + Ob(1)K 0 m .
Then,

1 0 h ′ N (u)µ m (du) = 1 + Ob(1)K0 m . Therefore, 1 = 1 0 h N (u)µ m (du) = c 0 1 0 h ′ N (u)µ m (du) = c 0 1 + Ob(1)K 0 m . Lemma 6.3
The following equality holds : 1

N (I k ) r h N (r/N (I k )) = 1 + Ob ′ (1)K0 N (I k )
.

Proof The following equalities hold :

1 = r (r+1)/N (I k ) r/N (I k ) h ′ N (u)du = r (r+1)/N (I k ) r/N (I k ) h ′ N (r/N (I k )) + Ob(1)K 0 /N (I k ) du = 1 N (I k ) r h ′ N (r/N (I k )) + Ob(1)K 0 N (I k ) . Therefore c 0 = 1 N (I k ) r h N (r/N (I k )) + Ob(1)c0K0 N (I k ) .
Therefore, by lemma 6.2,

c 0 = 1 + Ob ′ (1)K 0 m = 1 N (I k ) r h N (r/N (I k )) + Ob(1)[1 + Ob ′ (1)K0 m ]K 0 N (I k )
.

Because K 0 /m ≈ 0 and N (I k )/m ≈ 0, we deduce the lemma.

Lemma 6.4 Let g N (k) = h N T -1 (k)/m . The following approximation holds 1 N (I k ) c ′ k -1 k=c k g N (k) = 1 + [1 + ϕ(m)]Ob(1)K 0 N (I k ) . Proof Let k n , n = 1, 2, .., c ′ k -c k , be a permutation of {c k /m, (c + 1)/m, ..., (c ′ k -1)/m} such that T -1 (k 1 ) < T -1 (k 2 ) < T -1 (k 3 ) < ...... < T -1 (k c ′ k -c k ).
Then, by definition of section 2.3,

|T -1 (k r )/m -r/N (I k )| ≤ ϕ(m)/N (I k ) . We deduce that |g N (k r ) -h N (r/N (I k ))| ≤ K 0 ϕ(m)/N (I k ).
Therefore, by lemma 6.3,

1 N (I k ) c ′ k -1 k=c k g N (k) = 1 N (I k ) r g N (k r ) = 1 N (I k ) r h N (r/N (I k )) + 1 N (I k ) r g N (k r ) -h N (r/N (I k )) = 1 N (I k ) r h N (r/N (I k )) + Ob(1)ϕ(m)K 0 N (I k ) = 1 + Ob ′ (1)K 0 N (I k ) + Ob(1)ϕ(m)K 0 N (I k ) .
Proof of proposition 6.1 By the previous equalities,

P {T (Y )/m ∈ I k } = 1 m k g N (k) = N (I k ) m 1 + [1 + ϕ(m)]Ob ′ (1)K 0 N (I k ) = L(I k ) + Ob(1) m 1 + [1 + ϕ(m)]Ob ′ (1)K 0 N (I k ) = L(I k ) 1 + Ob(1) mL(I k ) 1 + [1 + ϕ(m)]Ob ′ (1)K 0 N (I k ) = L(I k ) 1 + 2 q Ob(1) m 1 + [1 + ϕ(m)]Ob ′ (1)K 0 m/2 q + Ob(1) = L(I k ) 1 + 2 q Ob(1) m 1 + 2 q [1 + ϕ(m)]Ob ′ (1)K 0 m[1 + Ob(1)2 q /m] = L(I k ) 1 + 2 q [2 + ϕ(m)]Ob ′ (1)K 0 m .

Other propositions

Proposition 6.2 Let X n , n=1,2,...,N, be a sequence of random variables. Assume that, for all p ∈ N * , for all sequence x s , s=1,...,p, for all n ∈ N * , for all sequence of intervals, J s , s=1,2,..,p, for all injective sequence j s , s=1,2,...,p, such that j 1 = 0 and j s + n ∈ {1, 2, ..., N },

P X n+j1 ∈ J s |X n+j2 = x 2 , ...., X n+jp = x p = L(J 1 ) + Ob(1)ǫ .
Then, for all injective sequence j s ∈ Z such that j 1 = 0 ,

P {X n+j1 ∈ J 1 } ∩ ...... ∩ {X n+jp ∈ J p } = L(J 1 ) + Ob(1)ǫ ...... L(J p ) + Ob(1)ǫ .
Proof Let Q be the distribution of (X n+j1 , X n+j2 , ...., X n+jp ) and let Q -be the distribution of (X n+j2 , ...., X n+jp ). Let Q(.|x 2 , ...., x p ) be the distribution of X n+j1 given X n+js = x s , for s=1,2,...,p.

Then,

P {X n+j1 ∈ J 1 } ∩ ...... ∩ {X n+jp ∈ J p } = 1 J1 (x 1 )......1 Jp (x p )Q(dx 1 , ..., dx p ) = 1 J1 (x 1 )Q(dx 1 |x 2 , ...., x p ) 1 J2 (x 2 )......1 Jp (x p )Q -(dx 2 , ..., dx p ) = P X n+j1 ∈ J 1 |X n+j2 = x 2 , ...., X n+jp = x p 1 J2 (x 2 )......1 Jp (x p )Q -(dx 2 , ..., dx p ) = L(J 1 ) 1 J2 (x 2 )......1 Jp (x p )Q -(dx 2 , ..., dx p ) + Ob(1)ǫ1 J2 (x 2 )......1 Jp (x p )Q -(dx 2 , ..., dx p ) = L(J 1 ) + Ob(1)ǫ P {X n+j2 ∈ J 2 } ∩ ...... ∩ {X n+jp ∈ J p } .
Then, we prove the proposition by recurence. Proposition 6.3 Let Y n ∈ {0/m, 1/m, ...., (m -1)/m} be a sequence of random variables defined on a probability space (Ω, A, P ) and let X n = T q (Y n ). Then, for all Borel set Bo,

P {X n ∈ Bo | X n-s = x s , s = 1, 2, ..., p} = ys 1 ∈T -1 q (x1)
....

ys p ∈T -1 q (xp)
η ys 1 ,...,ys p P {X n ∈ Bo|Y n-j = y sj , j = 1, 2, ..., p} where

ys 1 ∈T -1 q (x1)
....

ys p ∈T -1 q (xp)
η ys 1 ,...,ys p = 1 .

Proof We have :

P {X n ∈ Bo|X n-s = x s , s = 1, 2, ..., p} = P {X n ∈ Bo} ∩ {X n-1 = x 1 } ∩ .... ∩ {X n-p = x p } P {X n-1 = x 1 } ∩ .... ∩ {X n-p = x p } = P {X n ∈ Bo} ∩ ∪ ys 1 {Y n-1 = y s1 } ∩ .... ∩ ∪ ys p {Y n-p = y sp } P ∪ ys 1 {Y n-1 = y s1 } ∩ .... ∩ ∪ ys p {Y n-p = y sp }
where

∪ ys t {Y n-t = y st } = ∪ ys t ∈T -1 q (xt) {Y n-t = y st }.
Then,

P {X n ∈ Bo|X n-s = x s , s = 1,

Proof of theorem 3

We apply proposition 6.1 when Y has for distribution the distribution of the conditional probability of Y φ(n) given Y φ(n-1) = y ′ 1 , Y φ(n-2) = y ′ 2 , ...... Let K ′ 0 which satisfies the condition of Lipschitz coefficient of proposition 6.1. By lemma 6.2, K ′ 0 = Ob ′ (1)K 0 . Then, we have

P T (mY )/m ∈ I k } = P T q (Y ) = k/2 q } = P X φ(n) = k/2 q Y φ(n-1) = y ′ 1 , Y φ(n-2) = y ′ 2 , .... = P X φ(n) ∈ I k Y φ(n-1) = y ′ 1 , Y φ(n-2) = y ′ 2 , .... = L(I k ) 1 + γ(m)Ob ′ (1)K ′ 0 m/2 q = L(I k ) 1 + γ(m)Ob ′ (1)K 0 m/2 q ,
where L(I k ) = 1/2 q .

By applying proposition 6.3 to the sequence Y φ(n-s) ,

P X φ(n) ∈ I k X φ(n-1) = x ′ 1 , X φ(n-2) = x ′ 2 , .... = y ′ s 1 ∈T -1 q (x ′ 1 )
.........

y ′ s N -1 ∈T -1 q (x ′ N -1 ) η y ′ s 1 ,...,y ′ s N -1 P X φ(n) ∈ I k Y φ(n-1) = y ′ s1 , Y φ(n-2) = y ′ s2 , .... = y ′ s 1 ∈T -1 q (x ′ 1 )
.........

y ′ s N -1 ∈T -1 q (x ′ N -1 ) η y ′ s 1 ,...,y ′ s N -1 L(I k ) 1 + γ(m)Ob ′ (1)K 0 m/2 q = L(I k ) 1 + γ(m)Ob ′ (1)K 0 m/2 q .
Then, by proposition 6. . Because γ(m)N K 0 2 q /m ≈ 0, we deduce that

P (X θ 1 , ...., X θ N ) ∈ I k1 ⊗ ...... ⊗ I k N = 1 2 N q 1 + γ(m)Ob ′ (1)N K 0 m/2 q .
Now, we study the Borel sets of {0/2 q , , ...., (2 q -1)/2 q } N : Bo = ∪ (k1,...,k N )∈Θ {(k 1 /2 q , ..., k N /2 q )}. Then, L(Bo) = Card(Θ)/2 N q . We deduce, that, for all Borel set Bo

P (X 1 , ...., X N ) ∈ Bo = L(Bo) 1 + γ(m)Ob ′ (1)N K 0 m/2 q .
Then, by using results of section 5, because γ(m)N K 0 2 q /m ≈ 0, X n cannot be differentiated with the IID model.

Use of text witten backward

There exists noises y n such that K 0 is not too large and m large enough. In order to obtain these noises, one can use texts. This choice is justified because it is easier to study their properties logically (cf section 10.3 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]) : For example asymptotical independence holds. Of course, one could use other random noises, for example, noises provided by machines. One could also use rap music as Marsaglia but its properties are more difficult to study logically.

Use of texts

Now, we suppose that we use sequences y n obtained from texts. As a matter of fact, in this section we define y n by the following way.

We choose two consecutive elements a and m of the Fibonacci sequence : m can be chosen with respect to N, the size of the sample. Then, we choose r 1 such that a < 32 r1 ≤ m.

It is supposed that one has a sequence of data a(j) obtained from texts and translated in number: a(j), j = 1, 2, ...., N 3 , a(j) ∈ {0, 1, ..., 255}. Let N 0 = ⌊N 3 /r 1 ⌋, the integer part of N 3 /r 1 . a) We set c(j) = a(j) mod κ = 325 . b) We set d(n) = r1 r=1 c(r 1 (n -1) + r)κ r-1 for j = 1, 2, ...., N 0 . c) We set y ′ n = d(n)m/κ r1 /m for j = 1, 2, ...., N 0 .

Use of a pseudo-random sequence

Moreover, a pseudo-random sequence rand 0 (n) is added to used texts : y n = my ′ (n) + rand 0 (n)/m. That makes possible to have sequences y n which have a good randomness (cf [START_REF] Deng | Some characterizations of the uniform distribution with applications to random number generation[END_REF], or chapter 3 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). Now, it is necessary that a priori all the possible values of {0/m, 1/m, ...., (m -1)/m} can exist in a sample. It is reasonably the case when one adds modulo m a pseudo-random sequence rand 0 (n) of period m. Normally any value k/m has a chance reasonable to be realized a priori. There is no reason that can not occur. Moreover, a priori all k/m has about as much chance to be an image than any other k/m. Therefore, a priori, " P {Y ′ n = y} is not too different from 1/m " is a reasonable assumption. Now if we use simulations, they confirm this result. While, it is always possible that this is not the case. But it has a weak probability to happen.

Recall also that, for the texts, as soon as one takes as sequence y ′ n a sequence of group of Q=10 or 20 letters for example, one finds the Q-dependence statistically (chapter 10 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). Now, we suppose that (rand 0 (n), rand 0 (n + 1)) has a distribution close to independence. So, normally this will be the case also for (my ′ (n) + rand 0 (n) , my ′ (n + 1) + rand 0 (n + 1)). This can be understood by simulation. But a priori, it is always possible that this is not checked with, it seems, a very weak probability 6 .

In this case, a two-dimensional model (Y n , Y n+1 ) with a continuous density and a Lipschitz coefficient not too big will be a good model. By the same way, P {Y n = y|Y n-1 = y 1 } will have a continuous density with a coefficient of Lipschitz K y1 checking K y1 ≤ K" 0 for y 1 = 0, 1, ...., m -1 where K" 0 is small . Therefore, P {Y n = y|Y n-1 = y 1 } is not too different of P {Y n = y} which is not too different from 1/m. Then, it is normal to accept this hypothesis for sequences Y n7 .

Text written backward

In an obvious way, the texts are realizations of sequences of random variables: for example, one can take as model, the set of the possible texts provided with the uniform probability. In this model, if one knows a text until the letter "n-1", there are a large number of alternatives for the r following letters as soon as r is rather large. That means indeed that the conditional probability of Y n knowing the past, is not concentrated in a too small number of points. However there is a problem for some subsequences y ′ φ(n) : if one knows a text until the letter "n-1" and the text after the letter "n+r", (for example r=18), there will be much less possibilities for the r letters ranging between the two parts of texts than if only the past is known. To answer this point, we will add modulo m a text and a text written backward.

But that seems exaggerated because it is not known a priori that we are in an English text if one has only a few texts 8 . Moreover, a priori all the words possible of the English language are not known : one cannot thus predict them. That does not prevent from concluding : if the conditional probabilities of the texts are not concentrated in some points in a model of English text, a fortiori, it is also the case if it is not known that one is in a English text. Now, it is encore easier to prove that the conditional probability of Y n knowing the past, is not concentrated in a too small number of points if y n = [my ′ (n) + rand 0 (n) + my"(n) + rand 1 (n)]/m where y"(n) represent a text written backward independent of y ′ n and rand j (n) pseudo-random sequences for j=0,1 (which have good empirical independence assumptions for p successive pseudo random numbers with p ≥ 3). In this case, one can show that this condition is correct.

Theorem

Indeed, now we suppose that the sequences x n and y n represent two independent texts at which one adds to each one a good pseudo-random sequences. Let Y n and X n be two correct models. One is interested to the sequence X n+s + Y n-s , s = 0, ±1, ±2, ..... As matter of fact, one adds a text to a text written backward Then, we will understand that the probability that X n + Y n = a 0 given X n+s + Y n-s = a s for s=1,-1, will be about that of

X n + Y n = a 0 given X n-1 = b 1 and Y n-1 = c 1 .
At first, we have the following theorem Theorem 4 Let Y n and X n be two independent sequences of random variables defined on a probability space (Ω, A, P ) such that X n , Y n ∈ {0/m, 1/m, ...., (m -1)/m}. Then,

P {X n + Y n ≡ a 0 | X n-1 + Y n+1 ≡ a 1 , X n+1 + Y n-1 ≡ a 2 } = x1,y1 η x1,y1 α x1,y1 P X n + Y n ≡ a 0 Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 , where α x1,y1 = P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 , Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 P X n-1 = x 1 , Y n-1 = y 1 Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 , η x1,y1 = P {X n-1 = x 1 } ∩ {X n+1 ≡ a 2 -y 1 } P {Y n+1 ≡ a 1 -x 1 } ∩ {Y n-1 = y 1 } x1,y1 P {X n-1 = x 1 } ∩ {X n+1 ≡ a 2 -y 1 } P {Y n+1 ≡ a 1 -x 1 } ∩ {Y n-1 = y 1 } , x1,y1 = (x1,y1)∈{0/m,1/m,....,(m-1)/m} 2 , x1,y1 η x1,y1 = 1.
Proof We have

P {X n + Y n ≡ a 0 | X n-1 + Y n+1 ≡ a 1 , X n+1 + Y n-1 ≡ a 2 } = P {X n + Y n ≡ a 0 } ∩ {X n-1 + Y n+1 ≡ a 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } P {X n-1 + Y n+1 ≡ a 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } = P  {Xn + Yn ≡ a 0 } ∩ n ∪x 1 {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n ∪y 1 {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff P  n ∪x 1 {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n ∪y 1 {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff = X x 1 ,y 1 P  {Xn + Yn ≡ a 0 } ∩ n {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff P x 1 ,y 1 P  n {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff = X x 1 ,y 1 P  n {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff P x 1 ,y 1 P  n {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff P  {Xn + Yn ≡ a 0 } ∩ n {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff P  n {X n-1 = x 1 } ∩ {X n-1 + Y n+1 ≡ a 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 + Y n-1 ≡ a 2 } o ff = X x 1 ,y 1 ηx 1 ,y 1 P  {Xn + Yn ≡ a 0 } ∩ n {X n-1 = x 1 } ∩ {Y n+1 ≡ a 1 -x 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 ≡ a 2 -y 1 } o ff P  n {X n-1 = x 1 } ∩ {Y n+1 ≡ a 1 -x 1 } o ∩ n {Y n-1 = y 1 } ∩ {X n+1 ≡ a 2 -y 1 } o ff = X x 1 ,y 1 ηx 1 ,y 1 P  Xn + Yn ≡ a 0 ˛Xn-1 = x 1 , Y n+1 ≡ a 1 -x 1 , Y n-1 = y 1 , X n+1 ≡ a 2 -y 1 ff .
On the other hand,

P X n + Y n ≡ a 0 X n-1 = x 1 , Y n+1 ≡ a 1 -x 1 , Y n-1 = y 1 , X n+1 ≡ a 2 -y 1 = Cx 1 , y 1 P X n + Y n ≡ a 0 Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 ,
where

c x1,y1 = P X n + Y n ≡ a 0 X n-1 = x 1 , Y n+1 ≡ a 1 -x 1 , Y n-1 = y 1 , X n+1 ≡ a 2 -y 1 P X n + Y n ≡ a 0 Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 = P {Xn+Yn≡a0}∩ {Xn-1=x1}∩{Yn+1≡a1-x1} ∩ {Yn-1=y1}∩{Xn+1≡a2-y1} P {Xn-1=x1}∩{Yn+1≡a1-x1} ∩ {Yn-1=y1}∩{Xn+1≡a2-y1} P {Xn+Yn≡a0}∩{Yn+1≡a1-x1}∩{Xn+1≡a2-y1} P {Yn+1≡a1-x1}∩{Xn+1≡a2-y1} Study of P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 , Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 .
One understands, by simulation, that P

X n-1 = x 1 , Y n-1 = y 1 X n +Y n ≡ a 0 , Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 is not too different from P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 . It is not astonishing: X n-1 is almost independent of X n+1 . Therefore, P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 , Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 depends especially on X n + Y n 9 .
One can also understand it because of following relations

P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 , Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 = P n {X n-1 = x 1 } ∩ {Y n-1 = y 1 } ∩ {Xn + Yn ≡ a 0 } ∩ {Y n+1 ≡ a 1 -x 1 } ∩ {X n+1 ≡ a 2 -y 1 } o P n {Xn + Yn ≡ a 0 } ∩ {Y n+1 ≡ a 1 -x 1 } ∩ {X n+1 ≡ a 2 -y 1 } o = P n {X n-1 = x 1 } ∩ {Y n-1 = y 1 } ∩ n ∪x 0 {Xn = x 0 } ∩ {Xn + Yn ≡ a 0 o ∩ {Y n+1 ≡ a 1 -x 1 } ∩ {X n+1 ≡ a 2 -y 1 } o P nn ∪x 0 {Xn = x 0 } ∩ {Xn + Yn ≡ a 0 o ∩ {Y n+1 ≡ a 1 -x 1 } ∩ {X n+1 ≡ a 2 -y 1 } o = X x 0 P n {X n-1 = x 1 } ∩ {Y n-1 = y 1 } ∩ n {Xn = x 0 } ∩ {Yn ≡ a 0 -x 0 } o ∩ {Y n+1 ≡ a 1 -x 1 } ∩ {X n+1 ≡ a 2 -y 1 } o P x 0 P nn {Xn = x 0 } ∩ {Yn ≡ a 0 -x 0 } o ∩ {Y n+1 ≡ a 1 -x 1 } ∩ {X n+1 ≡ a 2 -y 1 } o = X x 0 P n {X n-1 = x 1 } ∩ {Xn = x 0 } ∩ {X n+1 ≡ a 2 -y 1 } o P n {Y n-1 = y 1 } ∩ {Yn ≡ a 0 -x 0 } ∩ {Y n+1 ≡ a 1 -x 1 } o P x 0 P n {Xn = x 0 } ∩ {X n+1 ≡ a 2 -y 1 } o P n {Yn ≡ a 0 -x 0 } ∩ {Y n+1 ≡ a 1 -x 1 } o = X x 0 βx 0 P n {X n-1 = x 1 } ∩ {Xn = x 0 } ∩ {X n+1 ≡ a 2 -y 1 } o P n {Y n-1 = y 1 } ∩ {Yn ≡ a 0 -x 0 } ∩ {Y n+1 ≡ a 1 -x 1 } o P n {Xn = x 0 } ∩ {X n+1 ≡ a 2 -y 1 } o P n {Yn ≡ a 0 -x 0 } ∩ {Y n+1 ≡ a 1 -x 1 } o = x0 β x0 P X n-1 = x 1 |X n = x 0 , X n+1 ≡ a 2 -y 1 P Y n-1 = y 1 |Y n ≡ a 0 -x 0 , Y n+1 ≡ a 1 -x 1 where x0 β x0 = 1.
It is not too difficult to understand, that, for example,

P {X n-1 = x 1 |X n = x 0 , X n+1 ≡ a 2 -y 1 is hardly more concentrated than P {X n-1 = x 1 |X n = x 0 if x n represents
only texts. It is even truer if x n represents a text to which one adds a good pseudo random sequence, and it is even truer in the case which interests us considering than one summons on all the x 0 . Then, it is not astonishing that P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 , Y n+1 ≡ a 1x 1 , X n+1 ≡ a 2y 1 is not too different from P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 . Now, P {X n + Y n ≡ a 0 } ≈ 1/m because one adds a pseudo random sequence to text (cf pages 199-202 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). Therefore,

P X n-1 = x 1 , Y n-1 = y 1 X n + Y n ≡ a 0 = P {X n-1 = x 1 , Y n-1 = y 1 , X n + Y n ≡ a 0 } P {X n + Y n ≡ a 0 } ≈ m.P X n-1 = x 1 , Y n-1 = y 1 P X n-1 = x 1 , Y n-1 = y 1 , X n + Y n ≡ a 0 P X n-1 = x 1 , Y n-1 = y 1 , = m.P X n-1 = x 1 P Y n-1 = y 1 P X n + Y n ≡ a 0 X n-1 = x 1 , Y n-1 = y 1 , ≈ (1/m)P X n + Y n ≡ a 0 X n-1 = x 1 , Y n-1 = y 1 , .
Of course, P X n + Y n ≡ a 0 X n-1 = x 1 , Y n-1 = y 1 , is, this time, the conditional probability knowing the past. There are thus about the same results that above for P X n + Y n ≡ a 0 Y n+1 ≡ a 1x 1 , X n+1 ≡ a 2y 1 . Therefore, P X n + Y n ≡ a 0 X n-1 = x 1 , Y n-1 = y 1 , will be not too different from 1/m.

Conclusion

By joining together all these results, one understands that α x1,y1 P X n + Y n ≡ a 0 Y n+1 ≡ a 1x 1 , X n+1 ≡ a 2y 1 will be not too different from 1/m. Now,

η x1,y1 = P {X n-1 = x 1 } ∩ {X n+1 ≡ a 2 -y 1 } P {Y n+1 ≡ a 1 -x 1 } ∩ {Y n-1 = y 1 } x1,y1 P {X n-1 = x 1 } ∩ {X n+1 ≡ a 2 -y 1 } P {Y n+1 ≡ a 1 -x 1 } ∩ {Y n-1 = y 1 } ≈ P {X n-1 = x 1 }P {X n+1 ≡ a 2 -y 1 }P {Y n+1 ≡ a 1 -x 1 }P {Y n-1 = y 1 } x1,y1 P {X n-1 = x 1 }P {X n+1 ≡ a 2 -y 1 }P {Y n+1 ≡ a 1 -x 1 }P {Y n-1 = y 1 } ≈ 1/m
P X n + Y n ≡ a 0 Y n+1 ≡ a 1 -x 1 , X n+1 ≡ a 2 -y 1 .
However in general, to make a sum on x 1 , y 1 standardizes the probabilities (it is true as soon as one can consider that they are randomly selected cf section 6.1.2 of of [START_REF] Blacher R | A Perfect Random Number Generator II[END_REF]). Therefore, in most case, P {X n + Y n ≡ a 0 | X n-1 + Y n+1 ≡ a 1 , X n+1 + Y n-1 ≡ a 2 } will be even more close to (1/m) that the previous reasonings which is carry out without the sums x1,y1 did not let it suppose.

Finally, all this confirms that P {X n + Y n ≡ a 0 | X n-1 + Y n+1 ≡ a 1 , X n+1 + Y n-1 ≡ a 2 } is not too different from 1/m. One deduces from it that the coefficient of Lipschitz will not be too large. Then, it is enough to apply T q in order to have sequences proved IID. This is not surprising because when one tests the sequences of groups of letters y ′ n , we understand that models Y ′ n behave like Q-dependent sequences and also like Markov chain as soons as r 1 ≥ 20. Of course, that is even more true for sequences Y n .

This leads to the conclusion that we can increase the Lipschitz coefficient of this conditional probability by a K 0 which is not too large.

Important remark

One might wonder if the sequence built (by adding text, a text written backward and pseudorandom sequences) is not an lID sequence. It is a similar hypothesis which Marsaglia does by building its CD-Rom. It is a such tendency that matches the result of [START_REF] Deng | Some characterizations of the uniform distribution with applications to random number generation[END_REF]. But in fact, nothing is proved.

One might then wonder if you can not apply to these sequences, the same technique as that used for sequences T q (Y n ) and to prove P (X 1 , ...., X N ) ∈ Bo = L(Bo) 1+Ob(1)ǫ . But it seems very difficult to prove in a sure way.

Finally, it is much easier to apply the functions T q : in this case, it requires only that K 0 the Lipschitz coefficient is not too big. It's an hypothesis much simpler to be verified and it does not require many efforts in some cases. That is why we choose to build IID sequences using this technique

Use of Central limit theorem

There exists other noises y n such that K 0 is not too large and m large enough. For example, one can use software programs noises provided by machines and chips, etc.. In these cases, on can use the CLT (Central Limit theorem). That is a possibility which is natural when one wants to increase reliably Lipschitz coefficient of conditional probabilities. Moreover, this technique has the advantage of giving a clear idea of K 0 since the conditional densities are so close to Gaussian densities and since convergence is quick (e.g. cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). On the other hand, CLT holds under hypotheses rather weak if we use the following decomposition. .

Then, one can define assumptions of asymptotic independence.

Notations 8.2 : Let k ∈ N * . We define conditions H mS (k) and H mI (k) by the following way : H mS (k) : ∀p ∈ N , p < k + 1 , E (S u ) p -E (S ′ u ) p → 0 as n → ∞. H mI (2k) : ∀(p, q) ∈ (N * ) 2 , p + q < k + 1 , E (S u ) p (S ′ u ) q -E (S u ) p E (S ′ u ) q → 0 as n → ∞.

Notations 8.3 : Let I k,j = j.4 -k , (j +1)4 -k . Let A k,j = S u ∈ I k,j and B k,j = S ′ u ∈ I k,j . Then, we define condition H S and H I by the following way : H S : ∀k ∈ N, ∀j ∈ N, P {A k,j } -P {B k,j } → 0 as n → ∞ , H I : ∀k ∈ N, ∀(j, j ′ ) ∈ N 2 , P {A k,j ∩ B k,j ′ } -P {A k,j }P {B k,j ′ } → 0 as n → ∞ .

Then, if H mS (∞) and H mI (∞) the CLT holds and an equivalent condition holds for H I and H S cf ( [START_REF] Blacher R | Central Limit Theorem by moments[END_REF], [START_REF] Blacher R | Une nouvelle condition d'independance pour le theoreme de la limite centrale[END_REF]). For example, the following theorem holds.

Theorem 5 We assume that H S , H I , H mS (4) and H mI (4) hold. We assume also that E{(S u ) 2 }-E{(S ′ u ) 2 } → 0 and E{ξ 2 u } → 0 as n → ∞ . Then, S n D → N (0, 1) .

We can then apply these results to random sequences obtained from machines, chips, various electronic files which have a certain asymptotic independence. More if one adds modulo m a good pseudo random, tests show that the conditions H mS (∞) and H S (∞) are checked.

We therefore use lines of noises y i,n ∈ {0, 1, ...., m -1} which we sum : y n = S i=1 y i,n /m and we apply T q . Indeed, in this case, the conditional densities are approximately Gaussian. We can then increase K 0 by estimating the coefficients of linear correlation. Thus we obtain coefficient K 0 whose we are sure and which are in general not too large.

Figure 1 :

 1 Figure 1: Fibonacci congruence

Figure 2 :Figure 3 : 5 Fig 2 . 3

 23523 Figure 2: sup(h i ) = 20

Figure 4 Figure 6 :

 46 Figure 4: a= 1346269, m=2178309

Notations 4 . 1

 41 Let m ∈ N * . One considers the sequences of random variables Y θ n , n=1,......

  As a matter of fact, the relation P {(Y θ2 1 , ........., Y θ2 N ) ∈ Bo} = P {(Y θ1 1 , ..........., Y θ1 N ) ∈ Bo} [1 + Ob(1)ǫ] for all Borel set Bo ⊂ {0/m, 1/m, ...., (m -1)/m} N is a very strong relation. Because of it, it seems impossible to differentiate Y θ1

  2 used with ǫ = L(I k )ǫ, for all I k1 ⊗ ...... ⊗ I k N , P (X 1 , ...., X N ) ∈ I k1 ⊗ ...... ⊗ I k N = N s=1 L(I ks )[1 + Ob(1)ǫ] ,where |ǫ| ≤ γ(m)|Ob ′ (1)|K0 m/2 q

7. 6

 6 Increase of K 0Similar results can be obtained forP {X n + Y n ≡ a 0 | X n-1 + Y n+1 ≡ a 1 , X n-2 + Y n+2 ≡ a 2 , , ...., X n+1 + Y n-1 ≡ b 1 , X n+2 + Y n-2 ≡ b 2 , ......}.

Notations 8 . 1

 81 We denote by κ(n) ∈ N, an increasing sequence such that κ(1) = 0, κ(n) ≤ n and κ(n)/n → 0 . We define the sequences u(n) and t(n) by : u(1)=1, u(n) = max m ∈ N * 2m + κ(m) ≤ n , and t(1)=0, t(n) = n-2u(n) if n ≥ 2. Let σ(u) 2 = E{(X 1 + X 2 + ......... + X u ) 2 }. One sets S u = X1+X2+.........+Xu σ(u), ξ u = Xu+1+Xu+2+.........+Xu+t σ(u) and S ′ u = Xu+t+1+Xu+t+2+.........+Xu+t+u σ(u)

  Ob(1)ǫ , where ǫ is small enough and where Ob(.) means the classical O(.) with the additional condition |Ob(1)| ≤ 1. One supposes that Y θ1 n is a correct model of the sequence y n , n=1,2,....,N. One wants to prove that Y θ2

	5.1 The problem
	Let Y θ2 n and Y θ1 n be two sequences of random variables such that, for all Borel set Bo,
	P (Y θ2 1 , ......, Y θ2

N ) ∈ Bo = P (Y θ1 1 , ......, Y θ1 N ) ∈ Bo 1 +

  ...... Since Y n is discrete, we can also assume that f n,φ (.|y ′ 1 , y ′ 2 , ....) has a finite Lipschitz coefficient.

Notations 6.4

We denote by K 0 a constant such that, for all permutation φ of {1, 2, ..., N }, for all n ∈ {1, 2, ..., N }, |f n,φ

  2, ..., p}= P ∪ ys 1 .... ∪ ys p {X n ∈ Bo} ∩ {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } P ∪ ys 1 .... ∪ ys p {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } {X n ∈ Bo} ∩ {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } ys 1 .... ys p P {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } p η ys 1 ,...,ys p P {X n ∈ Bo} ∩ {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } P {Y n-1 = y s1 } ∩ .... ∩ {Y n-p =y sp } where η ys 1 ,...,ys p = P {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } ys 1 .... ys p P {Y n-1 = y s1 } ∩ .... ∩ {Y n-p = y sp } .

	= P = ys 1 .... ys p ....
	ys 1
	Of course,
	....
	ys 1

ys ys p η ys 1 ,...,ys p = 1 .

  4 x1,y1 (1/m 4 ) ≈ 1/m 2 . x1,y1 α x1,y1 P X n + Y n ≡ a 0 Y n+1 ≡ a 1x 1 , X n+1 ≡ a 2y 1

	Therefore,
	x1,y1
	is not too different from
	(1/m 2 )
	x1,y1

η

By abuse of language, we will call "IID sequence" (Independent Identically Distributed) the sequences of random numbers.

It agree to know what we call "equivalent frequency". Then, in this definition, we assume that there is a mathematical answer, which is reasonable, but not completely sure. Note that there may exist infinitely from them and that we may be in the same problem (there are an infinite number of possible tests). In this case, the easiest will be to choose one from them. It is therefore assumed here that there are mathematical definitions of this fact without giving more details. For example the test of uniformity by the chi-square could be not verified : the probability of result which vould be found would be only one percent that uniform assumption is verified. But if we do 100 tests, it is possible that such an event happens. It would be necessary still that these tests are independent and it would then be necessary to know what "independent tests" means. Such a study might be long.

Remark that if yn = Yn(ω) is an event which has reasonable probability to be carried out, the tests will have to be checked with a good frequency.

It is not embarrassing to be limited to the following letters : it is enough to take a subsequence containing the letters preceding and following a portion of text to get a correct estimate.

There are only 26 letters. But it is necessary to add the capital letters, the ":" , ";" , etc. Also, we will write these numbers in base 32 so that each number has a reasonable probability to appear.

If one wants to build random numbers, one can always check if this hypothesis holds. If this is not the case, we choose other generators or other texts

Of course, if we want to be sure from it, we can confirm it by tests.

Let us recall difficulties in order to discover the meaning of certain languages in archeology : all are not identifed. Let us recall also the hieroglyphs on the Rosetta Stone whose one had however 3 translations.

In the general case, that could be false : e.g. cf the properties of higher order correlation coefficients (cf[START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF])

Value of ǫ

To get an idea of the value of ǫ, the best is to return to the definition using tests. Because P {(Y θ 1 , ...., Y θ N ) ∈ Bo} = P {(Y θ0 1 , ...., Y θ0 N ) ∈ Bo}[1+Ob [START_REF] Knuth | the Art of Computer Programming[END_REF]ǫ] implies that P {g(Y θ 1 , ...., Y θ N ) ∈ Bo ′ } = P {g(Y θ0 1 , ...., Y θ0 N ) ∈ Bo ′ }[1 + Ob(1)ǫ], we can consider that all tests defined by a function of type g, will produce results not very different if ǫ is small enough. Then, one can choose ǫ = 1/10, 1/100 ou 1/1000, ...... Now, if we wanted to avoid any doubt, intuition would dictate that we choose ǫ as a function of N. Intuitively, one might therefore wish to impose ǫ = 1/N . But this is probably exaggerated and there is nothing which justifies this intuition. Moreover, in theorem 3, it already imposed ǫ = K 0 N 2 q /m. The idea of choosing ǫ as a function of N is already realized 5.8 A problem 1)ǫ] would be also correct. One would end up finding models which would not be correct.

Therefore, there is no reason that Y θ3 n is also correct. It cannot be differentiated of Y θ2 n , but not of Y θ1 n . In other words, this relation is not transitive.

IID Case

That thus poses a problem because if one uses for example a realization y n of the IID model, and that if one takes for sequence Y θ1 n a model checking

where ǫ 1 is small enough but not very small, there are no reasons a priori that Y θ2 n is a correct model. Indeed, in order that Y θ2 n is not correct, it is enough that Y θ1 n is in extreme cases of the correct models, i.e. it is enough that ǫ 1 is in extreme cases of the possible values of the ǫ's such

What we want

But what interests us is that there exists correct models Y θ1 n such that all models close Y θ n , i.e. 1)ǫ] would be also correct. But we need that ǫ is small but not too, i.e. of the order of what we saw : ǫ = 1/10, 1/100 or at worst ǫ = 1/N if need be (cf section 5.7)

Case of a known model

To understand that this is the case, suppose first that we have an sequence x n , sample of an IID sequence X n and that it is a good realization of X n . So we know that models checking P {(X θ 1 , ...., X θ N ) ∈ Bo} = L(Bo)[1 + Ob(1)ǫ] will also correct models. In this case, we can admit that there is a model (the IID model) such as all close models are correct models.

If we are not in the IID case but in any case and if one knows the model : it is the same matter. However we can always accept that a sequence y n is the realization of a given model Y 1 n : this is indeed the usual hypothesis in Statistics. The model Y 1 n will be thus "at the center of some models close" :

implies that Y θ n will be also a correct model.

Intuitively, one feels that it is general : there are many correct models, Y θ n of a sequence y n , n=1,2,...,N, such that models close with a margin of ǫ are also correct.

Use of estimates

Suppose we take the IID example of section 5.2 : P {X ǫ n ∈ [1/2, 1]} = 0, 5[1 + ǫ] when ǫ = 0, 001. Suppose that the sample x n is a good sample. It is then clear that there are many correct models close to the model X ǫ n if ǫ is small enough. But it is possible that there are other such models. Thus, we can choose for correct model, the IID model X 2 n such that P {X 2 n ∈ [0, 1/2[} = p e , the empirical probablity of [0,1/2[. In this case, it is clear that there are many close models which are correct. For example, consider as a model

It is also a correct model and the close models 1)ǫ] will be also correct models if ǫ is small.

More generally, we know that it should exist estimates of models (these estimates are easier to calculate in some cases as texts). Then, we can choose as model Y θ1 n , the model provided by these estimates. If these estimates are correct, then it is clear that all close models checking 1)ǫ] will be also correct models.

Exact IID model

One assumes also that, for all (k 1 , ...., k N ),

where sup k1,....,k N |ǫ k1,....,k N (q)| = ǫ X (q). One assumes that ǫ X (q) is increasing, that ǫ X (1) << ǫ Y and that there exists q 1 ∈ N * such that ǫ X (q 1 ) is small enough.

Then, there exists q 0 ∈ N * and a correct model Y θ0 n of the sequence {y n } n=1,...,N such that, for all (k 1 , ...., k N ),

Proof There exists q 0 ≤ q 1 such that ǫ X (q 0 ) ≤ (1/2)ǫ Y . Then, one uses the model Y θ0 n such that, for all (k 1 , ...., k N ),

). It ckecks

It ckecks also : for all (y ′ 1 , ......., y ′ N ),

Application

Let us suppose again that the sequences x n and y n represents texts at which one adds to each one a good pseudo-random sequence. It is supposed that Y n and X n are two correct models. One is interested by X n+s + Y n-s , s = 0, ±1, ±2, .... : one adds a text and a text written backward.

We know that P X n + Y n ≡ a 0 Y n+1 ≡ a 1x 1 , X n+1 ≡ a 2y 1 is the conditional probability that X n + Y n ≡ a 0 given the futures Y n+1 and X n+1 .

There will be thus a probability which will not be more concentrated that of a text knowing the future. But it is an increase: the probability of the sum X n + Y n knowing the future Y n+1 ≡ a 1 -x 1 and X n+1 ≡ a 2 -y 1 is probably less concentrated than, for example, the probability of X n knowing the future X n+1 ≡ a 2y 1 .

In fact, the conditional probability will be much less concentrated than that: it is not known that one is in a text. Moreover, because a good pseudo-random generator is added, this probability will be rather close to that of independence :

Therefore, the probability of the sum X n + Y n knowing the future is not concentrated close to some points. That means that there will be no points where it is close to 0, and not points where it is close to 1. That means that, in the case of models with continuous density, the coefficient of Lipschitz will not be too large.

Study of P {X

Then, by applying T q and choosing good parameters depending on N, we obtain sequences x n which we can consider as a sample of an IID sequence of random variables Now if we sum the random variables modulo m : y n = S i=1 y i,n /m, we get even a better result because in this case, the Y n are asymptotically independent (cf section 5.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). This improves again, if it was necessary, the quality of the increase of K 0 . 9 Building of random sequence

Choice of m and q

We are interested in the choice of parameters in the building of IID sequences.

We consider the case of texts y n = [my ′ n + rand 0 (n) + my" n + rand 1 (n)]/m defined in section 8. Then, we shall impose that the sample size N 0 satisfies γ(m)N0K0 m/2 q = 1/1000 (cf theorem 3 ).

We could take γ(m)N0K0 m/2 q = 1/10 or 1/100 without problem. We choose 1/1000 in order to be sure that there will be absolutely no mistake.

Likewise, because the y n are obtained using the method described in section 8, we chooseK 0 = 1000 although the calculations made in section 8 shows that we can probably choose it much smaller.

So finally, we choose m and q so that 2 q /m = 1 γ(m)N010 6 . Then, the particular choices of m and, therefore also of q, depends on questions of convenience. For example, is that the computer has a program to perform multiplication and division of numbers which have more than 30 digits? In this case, we can choose m of order of 10 30 if the other conditions permit.

If we use the CLT, we proceed in exactly the same way except that we may normally choose K 0 smallest : K 0 ≤ 10.

Example

By using this technique, we have created sequences x n which admit the IID model for correct model. We have used dictionary, encyclopedia, and Bible. As a matter of fact, we combine both methods : we are made sums of 10 lines including 5 written backwards 10 . We have estimated K 0 = 0.01. In order to avoid any error we have choose K 0 = 10 4 in the building of x n .

One can download these real random sequences written in Matlab files in [START_REF] Blacher R | File of random Number[END_REF].

We have tested this sequence x n . We have used the classical Diehard tests (cf [START_REF] Knuth | the Art of Computer Programming[END_REF], [START_REF] Gentle | Random Number Generation and Monte Carlo Method[END_REF]), and the higher order correlation coefficients (cf [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]). Results are in accordance with what we waited : the hypothesis "randomness" is accepted by all these tests.

For example, we have used the Coupon collector's Test. We keep the notations of [START_REF] Knuth | the Art of Computer Programming[END_REF] page 64. We choose d=3,4,5,6,7,8 (with the notations of [START_REF] Knuth | the Art of Computer Programming[END_REF] ). Then, one uses chi squared statistics : we denote them by χ 2 N1 . We use various t (with the notations of [START_REF] Knuth | the Art of Computer Programming[END_REF] ). We choose t as a function of d. We lump a few categories of low probability together.

We use samples with various sizes N 1 . We are interested in the maximum of these various χ 2 N1 . The following table is that of the maxima of χ

This means that the method employed in order to obtain these sequences is still much safer than what we assumed at this time.

For this test, we took many different samples (more than 100). It is not surprising that maximum are close to α 5 .

We have carried out 100 tests in each category of other tests with significance level 5/100. We denote by n r tp and n r tf , the number of tests passed or failed. Then, we have the following results.

Conclusion

By theorem 3 one can find models correct Y θ n such that P {(X θ 1 , ..., X θ N ) ∈ Bo} = L(Bo)[1+Ob(1)ǫ] where ǫ is small and it is possible to build such sequences concretely. Now, K 0 increases very little when r 1 increases. Even, in some cases, it seems that it decreases. It seems to be the case as soon as there is asymptotic independence. Then, at most 2 q /m decreases much more quickly than K 0 increases.

So by taking m large enough and by choosing well q, we found ǫ small enough in a way that there exists correct models which checks the conditions of proposition 5.1. Then, there exists a correct model Y θ0 n of {y n } such that T q (Y θ0 n ) is the IID model.

Then, this result show that one can build sequences x n such that the model IID is a correct model of x n .

That means that x n behaves like any IID sample : a priori, x n can check not the properties which one awaits from a IID sample like certain tests, but that occurs only with a probability equal to that of any IID sample.

By this method, we therefore have a mean to value the technique used by Marsaglia to create its CD-ROM. We arrive in fact to prove mathematically that the sequence obtained can be regarded a priori as random, what Marsaglia did not.