Keywords: Central limit theorem, Or exclusive, Fibonacci sequence, Random numbers, Random noise, Higher order correlation coefficients

In this report one explicates the new method to generate random numbers whose the randomness is proved. One transforms data resulting from electronic files or provided by machines or software methods. This method can be applied directly in computers in the same way that the function "random". It can be also applied with the machines and the chips or software methods. In this report, one shows that ont one can use only the Fibonnacci functions. Moreover, one obtains new results about two other methods already obtained in a previous report.

General presentation of the matter

In this report, we present a new method to obtain IID sequences x n of random numbers 1 . This method can be used as well with machines as directly on a computer alone.

Presentation of the result

To have random number two methods exists : 1) Use of pseudo-random generators 2) Use of random noise.

These two methods have different defects. 1) For the best of them, the pseudo-random generators seem nondeterminist only during a certain time. This can be long enough for the cryptographic generators, but it is with the current means of calculations. Moreover in simulation, the pseudo-random generators must be tested for each application : cf [START_REF] Gentle | Random Number Generation and Monte Carlo Method[END_REF] page 151.

2) If random noises are used, bias and dependences can appear : cf [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]. One tries to remove them by mathematical transformations. But these methods have defects. They remove bias and the linear correlation, but not necessarily the dependence. On the other hand, these random noises can be produced by machines or chips. In this case, that thus require additional material which can suffer from malfunctions extremely difficult to detect : cf [START_REF] Knuth | the Art of Computer Programming[END_REF] page 3. Now, for some applications, a maximum quality is essential (Nuclear power, medical, cryptography). It is thus necessary to have generators without defects.

But, up to now no completely reliable solution had been proposed .

To set straight this situation, Marsaglia has created a Cd-Rom of random numbers by using sequences of numbers provided by Rap music. However, it does not have proved that the sequence obtained is really random.

However, there exists simple means of obtaining random sequences whose the quality is sure.

One can obtain perfect generators by using random noises, for example those produced by the machines or by software-based generators. In this case, one transforms these noises in a more effective way. Indeed, one uses assumptions much weaker than those of the current methods One can also obtain perfect generators usable directly on computer (without the use of machines). In this case, one uses the electronic files as random noises (like Marsaglia uses Rap music). Then they are transformed by the same method that we use for the machines.

Then, our technique can be applied with all the current methods.

One can thus obtain sequences of real numbers which are proved random, which is a completely new result.

Summary of the method

Currently, when one uses random noise, bias and dependences are removed. In this aim, one supposes that theses noises check some assumptions. But, generally, those are not checked. Moreover, for each samples x n there exists many possibles models X n such that x n = X n (ω). That can be problematic.

Our method consists to transform random noises under very weak hypotheses : we assume only that theses noises are not completely deterministic.

Moreover our results are true for all logical models possible. That suppress the problem of the model. That allows also to satisfy the mathematical definitions of random numbers (these definitions are very difficult to etablish cf [START_REF] Knuth | the Art of Computer Programming[END_REF]).

Then, the obtained sequences will be always IID. Now one can apply this method to many noises. So texts can be regarded as noises which satisfy these assumptions. It is also the case for numerous softwares which are recorded on computers : systems software for example.

Therefore, one can obtain directly IID sequences by transforming the files of computers. In this case, it is not necessary to use machines in order to have true random numbers.

On the contrary some electronics files can be studied logically. Then obtained numbers are surer than thoses obtained by machines which can have also malfunctions.

One can apply also our methods to noises furnished by machines, by chips, by mouse or by keyboard: of course, our results are much surer than those of current methods.

Definition of randomness

To produce a really random sequence, it is thus necessary to have a definition of the randomness. It is a subject which was studied much. But, it is extremely complex. Philosophical questions are even involved. A summary of this study is in the book of Knuth [START_REF] Knuth | the Art of Computer Programming[END_REF] pages 149-183. One reminds some definitions in section 2.1. In fact, one will understand that no current mathematical definition is really satisfactory.

Though, one can think to define randomness by the following way.

Definition 1.1.1 : One notes the approximation by ≈ : for x, y ∈ R, one sets x ≈ y if numerically x is nearly equal to y. Let L be the Lebesgue measure. A sequence x n ∈ [0, 1] is said random if, for all Borel set Bo, for all n+1, if the past x 1 , x 2 , , x n is given, one cannot predict the place of x n+1 with a probability very different from that of the uniform distribution : P e {x n+1 ∈ Bo|x 1 , ........, x n } ≈ L(Bo) , where P e {x n+1 ∈ Bo|x 1 , ........, x n } is the empirical conditional probability of Bo when the past is given.

This type of definition is that which one wishes. Unfortunately, it has a defect : one does not have specified enough the approximation. On the one hand, the definition of ≈ is very undetermined mathematically. On the other hand, one would like a definition closer to the statistics definitions. But it is difficult to obtain such a definition : cf section 2.1.1.

But these questions of mathematical definition will not obstruct us because we will circumvent this problem by using sequences which are really samples of sequences of random variables X n .

Unfortunately, an infinity of models X n corresponds to the sequence x n . Then, there is the problem of the choice of the model X n . We will avoid this problem by proving that x n behave as an IID sequence for all the logical possible models.

Presentation of the solution

Our method rests on a simple idea: to transform random noises by adapted transformations.

Like random noises, one can use those provided by the machines. It is what Vazirani, Neumann, Elias and others (cf [START_REF] Santha | Generating quasi-random sequences from semirandom sources[END_REF] [START_REF] Neumann | Various techniques used in connection with random digits[END_REF], [START_REF] Elias | The efficient construction of an unbiased random sequence[END_REF]) wanted to do, but with too restrictive assumptions.

One can also use some electronic files. It is what Marsaglia did with the Rap music (cf [START_REF] Knuth | the Art of Computer Programming[END_REF], [START_REF] Marsaglia G | CD ROM[END_REF] ). But he has transformed these data in a too elementary way (cf chapter 3).

Then, one has sequences of random noises y n : one can always assume y n = Y n (ω) with the following rule. Notations 1.2.1 When one has a sequence of real numbers which one can regard as one realization of a sequence of random variables, one will always note with small letters the data and with CAPITAL LETTERS the random variables which one will suppose defined on a probability space (Ω, A, P ).

When the y n 's mean random noises, to consider that y n = Y n (ω) is a traditional and normal assumption. It is also true for the y n extracted from certain electronic files.

Fundamental properties

Into this section, we introduce the properties which are at the heart of our study. We will use the following notations.

Notations 1.2.2 : The notation Ob(.) is that of the classical "O(.)" with the additional condition |Ob(1)| ≤ 1.

The sequences j 1 , j 2 , ......, j p , p ∈ N * , mean alway finite injective sequences j s ∈ Z, such that j 1 = 0. On the other hand, the sequences j ′ 1 , j ′ 2 , ......, j ′ p satisfy moreover 0 = j ′ 1 < j ′ 2 < ...... < j ′ p . The notation P X n ∈ Bo x 2 , ........, x p means always the conditional probability that the random variable X n belongs to the Borel Set Bo given X n+j2 = x 2 ,........,X n+jp = x p .

Let m ∈ N * . We set F (m) = {0/m, 1/m, ...., (m -1)/m} and F * (m) = {0, 1, ..., m -1}. We note by µ m and µ * m the uniform measures on F(m) and F * (m) , respectively : µ m (k/m) = 1/m.

Let X G be a random variable which has the distribution N(0,1) : X G ∼ N (0, 1). For all b > 0, we set Γ(b) = P {|X G | ≥ b}.

Transformation of Fibonacci

Definition 1.2.3 Let f i n be the Fibonacci sequence :

f i 1 = f i 2 = 1, f i n+2 = f i n+1 + f i n .
Let T be a congruence T (x) ≡ ax modulo m such that there exists n 0 > 3 satisfying a = f i n0 and m = f i n0+1 . Then T is said a Fibonacci's congruence with parameters a and m (or more simply m), Notations 1.2.4 Let h ∈ Z and m ∈ N * . We define h m by the following way 1) h m ≡ h modulo m.

2) 0 ≤ h m < m .

If the choice of m is obvious, we simplify h m into h.

Let h ∈ F (m) . We define h 1 by h 1 = mh m /m. Often we simplify h 1 into h.

In the same way, if the choice of m is obvious, and if T is a congruence : T (x) ≡ ax + c modulo m, we set T (x) = T (x)

m .

The reduction of Fibonacci congruences to their first bits will be very useful for our study. Definition 1.2.5 Let q, d ∈ N * . Let T be the congruence of Fibonacci modulo m.

We define the function of Fibonacci T d q : F (m) → F (d q ) by T d q = P r d q • T where 1) T (x) = T (mx)/m 2) P r d q (z) = 0, d 1 d 2 ....d q where z = 0, d 1 d 2 ... is the writing of z in base d.

If d=2, we simplify T d q in T q and P r d q in P r q .

To make IID by the functions of Fibonnacci

These functions T q make independent sequences of random variables Y n ∈ F (m). Moreover, they make uniform their marginal distributions. Now because Y n is discrete, one can always regard y n ∈ F (m) as the realization of a sequence of random variables Y n : y n = Y n (ω) such that Y n has a differentiable density with respect to µ m ⊗ .... ⊗ µ m .

Moreover, assume that this density have a Lipschitz coefficient K 0 which is not too large. That is a logical assumption. As a matter of fact, that is an assumption which most mathematicians admit: that is especially clear when they estimate the densities (which they suppose to exist) when N << m where N is the size of sample. Now, the conditional probabilities P {Y n |y n+j2 = y 2 , ..., Y n+jp = y p } have also a continuous density with a coefficient Lipschitz K cp 0 which is not too great. Then, one will prove that, for all interval I,

P T q (Y n ) ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p = L(I) 1 + O(1)K cp 0 N (I) (1.1)
where N (I) = card k/m k/m ∈ I, k ∈ N . For example, if m ≥ 2 100 , d=2, q = 50, K cp 0 ≤ 10, then

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , ......, Y n+jp = y p } = L(I) 1 + O(1)10 2 50
. We set X n = T q (Y n ). A good choice of the parameters N, m, q will imply that P X n ∈ Bo x 2 , ........, x p = L(Bo)[1 + Ob(1)ǫ] ,

where X n = T q (Y n ) and where ǫ ≈ 0, not only for intervals I, but also for all Borel sets Bo :

If ǫ is small enough with respect to N, the size of sample, X n cannot be differentiated from an IID sequence : cf section 2. 1.4. Because the assumption that the Lipschitz coefficient K 0 is not too large is correct, we deduce that the sequence X n behaves really as an IID sequence. Now, we are considering a new situation : we are considering the set of all the possible probabilities for sequences Y n , n=1,2,...,N. We provide it with a uniform probability, i.e. we want to know what occurs when the probabilities are randomly chosen.

Then, we shall prove in chapter 6 that, for all intervals I s , s=,..,p, with a probability larger than 1 -2pΓ(b) approximately, in this set of probabilities,

P {X n+j1 ∈ I 1 } ∩ .... ∩ {X n+jp ∈ I p } = p r=1 N (I r ) m p 1 + O(1).pb Inf s {N Is }
For example suppose m ≥ 2 100 , q = 50, d=2, b=40. Moreover, we can assume p ≤ Log 2 (N ). Indeed, the following remark is used.

Remark 1.2.1 One imposes p ≤ Log 2 (N ) because that does not have any meaning to consider the empirical dependence if p > Log 2 (N ), e.g., if p=5, and if one has a sample of size 10, that has not meaning to study its dependence in 32 = 2 5 cubes of width 1/2. ≈ O(1).pb 2 25 , one will not can differentiate X n with an IID sequence. Therefore, X n is IID with a probability larger than 1 -2Log(N ) 10 340 in the sets of all the possible models for the sequence y n . Let us remark also that, if necessary, one can choose b much greater.

Let us notice that the result is thus true even for a very large number of bad model Y n associated to y n . It is pointed out that with a sample, one can always associate a certain number of correct models. The other models will be bad: for example a model AR( 1) is a bad model for an IID sample. However our result is true with a probability of 1 -2p 10 340 . It is thus true even for an infinity of bad model of y n : it is thus a strong result.

One can still refine this result : in many cases, for example if y n is obtained from texts, the previous equation holds for all the logical models.

Therefore, X n is IID for all the logical models of Y n and even for an infinity of bad models.

That means that 1) X n is IID in almost all the cases. 2) One avoids the least error in the estimate of K cp 0 . It is especially useful if one knows nothing a priori about y n .

3) The functions T q are functions which make a sequence IID with a great power.

4) One is sure that X n is IID: there is no risk of error.

Also let us notice that thus one answers the problem of the definition of a random sequence : for every correct model or for almost all the models even bad Y n , P X n ∈ Bo x 2 , ........, x p = L(Bo)[1 + Ob(1)ǫ], i.e. X n cannot be differentiated with an IID sequence.

In conclusion there is really a method to obtain IID sequences X n and this result is proved.

Other Methods of construction

The first method applies to data having Lipschitz coefficient which are not too large. It is thus better to use only data which check surely this assumption, for example text files. Then one uses the CLT which smoothes the probability very quickly and thus decreases the Lipschitz coefficient. As a matter of fact it is better to summon these data modulo m, which corresponds to new a theorem limit, the XORLT (XOR Limit Theorem) which produces a smoothing even faster.

There are then transformed data which have Lipschitz coefficients not too large. One thus applies the functions of Fibonnacci T q to them. The choice of the parameters is carried out according to the results quoted previously.

The second method consists in standardizing data and then to apply a transformation to them which has characteristics rather similar to those of a permutation. After, the XORLT is used.

Indeed, in this case one is sure that one can apply results to the rate of convergence of the XORLT which one obtains in section 7. 3.4. Indeed, that one is extremely fast. For example one obtains P X n ∈ Bo x 2 , ....., x p = L(Bo)[1 + Ob(1)ǫ where ǫ = 0(1/2 50000 )!

We have concretely built IID sequences of real by using the method described here. This sequence can be asked to rene.blacher@imag.fr. Soon one will be able to obtain it in a website.

We carried out the traditional tests of Diehard with these sequences. All were checked : cf section 11.2.4.

Conclusion

The advantages compared to the current methods are clear:

1) It was proven that the numbers obtained are random.

2) There is not to test these numbers, especially in simulation where it had to be done for each new practical application.

3) The method is applicable directly on the computers: it is as easy as to use a function "random". Moreover, there does not need to add a machine or an additional chip to the computer.

4) If one uses the random noises (Machines, chips, software programs), one removes all the dependence, which generally the current methods do not do. Moreover that can remove certain dysfunctions of the machines.

A more detailed comparison with the current methods is carried out in section 2.2.2.

Chapter 2

Quality of obtained sequences 2.1 Criteria of randomness

Mathematical definitions

To determine the quality of a generator, one needs a definition of the randomness of a sequence of real numbers x n . Many studies were made to have reasonable definitions: there is a good summary of these studies in chapter 3-5 of Knuth : cf [START_REF] Knuth | the Art of Computer Programming[END_REF]. In this section 2.1.1, we summarize the study of Knuth. The common wish when one tries to obtain random sequences, it is to obtain a sequences of real numbers x n which can be regarded as a sample of an IID sequence of random variables X n . Then, one could propose the following definition.

Definition 2.1.1 : Let x n , n=1,2,....,N, be a sequence of real numbers in [0,1]. Then, x n is random if there exists an IID sequence of random variables X n ∈ [0, 1] defined on a probability space (Ω, A, P ) such that x n = X n (ω) where ω ∈ Ω.

But there is a problem with this definition : for example, x n can be increasing. Of course, it is possible only with a negligible probability. But it is possible. Then, Franklin proposed another definition. Definition 2.1.2 : Let x n , n=1,2,....,N, be a sequence of real numbers in [0,1]. Then, x n is random if it has each property that is shared by all samples of an IID sequence of random variables from uniform distribution. This definition is not precise and one could even deduce from it that no really random sequence exists (cf [START_REF] Knuth | the Art of Computer Programming[END_REF], Knuth page 149).

One must thus define differently what is a random sequence (or IID sequence). Also, the following definitions were introduced. Definition 2.1.3 : For all finite sequence of intervals I s ⊂ [0, 1], we denote by P e the empirical probability :

P e = (1/N 4 ) N4 n=1 1 I1 (x n )1 I2 (x n+1 ).....1 Ip (x n+p ) where N 4 = N -p. The sequence {x n } is said p-distributed if |P e -L(I)| ≤ N -1/2 4
for all

I = I 1 ⊗ I 2 ⊗ ... ⊗ I p . Definition 2.1.4 The sequence x n is random if it is p-distributed for all p ≤ Log 2 (N 4 ) .
Unfortunately, this definition does not take into account the randomness of subsequences x t1 , x t2 , ......x tm . However, it is known that one cannot extend this definition to all the transformations s → t s which define these subsequences : for example, this definition cannot be satisfied by the sequences x ts increasing. It is necessary thus that the application s → t s is too not complicated. Also Knuth proposes the following definition. Definition 2.1.5 : The sequence x n is random with respect to a set of algorithms A, if for all sequence x t1 , x t2 , ......x tm , determined by A, it is p-distributed for all p ≤ Log 2 (N ).

These definitions summarize those given by Knuth, [START_REF] Knuth | the Art of Computer Programming[END_REF] page 108. In fact he has especially studied the infinite case. But because in practice, there are always samples of finite size, we are limited to this case. This type of definition was the subject of many studies. In 1966, Knuth had thought that definition 3 defines the randomness perfectly: cf [START_REF] Knuth | the Art of Computer Programming[END_REF] page 163. It seems that he changed opinion since. In any case, none of these definitions is fully satisfactory. Knuth speaks philosophical debate on this subject. Thus, he points out that, according to certain principles, all the finite sequences can be regarded like determinist (cf pages 167-168 [START_REF] Knuth | the Art of Computer Programming[END_REF]).

Statistical definitions

Now, the definitions above are not satisfactory statistically. Indeed, it is known that if x n is really an IID sample, N 1/2 (Pe-L(I)) σ has approximatively the normal distribution where σ is the variance associated to P e . That means that it is possible that the event |P e -L(I)| > N -1/2 occurs. This property is thus different from the definition 2.1.5 de Knuth.

Therefore, one specifies statistically the definitions 2.1.4 and 2.1.5 in the following way. It is said that x n is random if, for all the sequences x ts defined by a set of algorithms A, for all suitable p, for all Bo = Bo 1 ⊗ ...... ⊗ Bo p , it checks all the tests associated to N 1/2 |P ′ e -L(Bo)| with the same frequency as a really IID sequence would do it.

By "same frequency", we understand that a really IID sequence will not check all the associated tests, but will check them only with a certain probability. For example, if all the tests to 1 percent was checked that would be abnormal.

Moreover in this definition, we use Borel sets rather than interval, because if not, there is an important gap (cf page 24 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] ).

Remark that it is known that one will always find Borel sets which does not check tests of randomness even for a really IID sequence. This fact is not annoying: this case is envisaged by the use of the terms "with the same frequency ".

On the other hand, it is not obvious that one has forgets not any dependence in the previous definitions. Also, to avoid gaps, we introduced definition 1.1.1 which we remind now. This definition seems a priori a good definition of the randomness. Indeed, it says that, knowing the past, one cannot predict the future with a probability too different from that of the uniform distribution. Intuitively, it is understood well that it is well the independence of the X n which one defines thus.

Besides, it is this condition which one wishes for the random sequences in much books. However, in these books, one does not adopt this definition. Indeed, the definition 2.1.7 is imprecise : one does not have specified the approximation.

In fact, it is also the case in the definition 2.1.6 where one does not have specified the frequency. However, that will pose problems as for the definition of Franklin. It would thus be necessary to specify our definitions and to make a theoretical study.

However that will not be necessary because we have avoided this problem by using sequences which are really samples of random variables.

Use of random variables

Then, we use really random variables. It is this technique used with machines by Von Neumann, Vazirani, and others ones : cf [START_REF] Neumann | Various techniques used in connection with random digits[END_REF], [START_REF] Santha | Generating quasi-random sequences from semirandom sources[END_REF], [START_REF] Elias | The efficient construction of an unbiased random sequence[END_REF]. They assume that x n is the realization of a sequence (not IID) of random variables and they transforms {X n }. But they obtain often the randomness under assumptions whose one is not sure that they are checked : in this case, x n is provided by physical phenomena in machines generating random numbers. Unfortunately, the intruments of measurements distort the physical phenomenon and induce bias and dependences.

As a matter of fact, it is necessary to choose a correct model for X n . But it is difficult.

At first, we know that one cannot choose definition 2.1.1 as definition of randomness. For example, an increasing sequence x n can check x n = X n (ω) where X n is IID (with a very negligible probability). As a matter of fact, this definition is not a problem solely when it is known a priori that the sequence X n is IID like the case of a mechanical roulette or a mechanical lotto. In this case, one starts from a machine and one extracts a sample from it.

But this technique is not thus appropriate inevitably when one starts from a real sequence y n (cf counterexample of increasing sequences).

To a sequence of real, it corresponds an infinity of models. Even if x n can be regarded as a sample of an IID sequence X n , it can be also logically regarded as the realization of an infinity of other models X a n (thus not IID). The question thus should be asked: if one associates a model to a sequence x n which criteria make that it possible to be sure that this model is correct? Generally, the following facts are admitted:

1) There never exists single model: a model is always related so that one wants to make of it.

2) Even when the goal is fixed, there are always several possible models, which all can be as valid the ones as the others. Then how to be sure that a model is the good? That seems impossible.

A solution of the problem

In order to resolve the problem of the definition of the random sequence, one can transform them : {X T n } = F({X n }) as Von Neumann, Vazirani, etc. But we use transformations which have good properties on a group of models. Indeed, one can admit that some sets of model contain always a correct model.

For example, when all the x n are different, one can admit that X n has a differentiable density with a Lipschitz coefficient K 0 not too large. This hypothesis is usually admitted by the statisticians especially those which use functional estimate.

Under this assumption, the transformations defined by Fibonacci functions T q have good properties. Indeed, if a sequence y n has models with continuous density and a Lipschitz coefficient K 0 , it will check

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p } = L(I) 1 + O(1)K 0 N (I) .
Then, one is sure that T q (Z n ) could be regarded reasonably as an IID sequence if K 0 is small enough and q not too large (i.e. N(I) great).

The problem of other models

Then a question is asked : if a model is correct and does not belong to the models with K 0 rather small, is what it will produce the same properties? If it produces another one, it will be a contradiction. There will be two possible logical conclusions. It seems impossible. However, it is not obvious1 . The problem of the choice of the definitions is found again.

A total answer

Now, by using the Fibonacci functions, one avoids the problem. In section 6.4.3, one proves mathematically that, for almost all the models, T q (X n ) behaves as an IID sequence . Indeed, one has

P {T q (X n+j1 ) ∈ I 1 }∩....∩{T q (X n+jp ) ∈ I p } = p r=1 N (I r ) m p 1+ O(1).pb Inf s {N Is }
It is a very satisfactory result. Indeed, it is wellknown that if one uses all the possible models without a priori, there will be an majority of bad models. Here, we find of it only a negligible number : it is already extraordinary. Moreover, there is another result. One indeed finds that for some data, for example those resulting from texts, ALL the logical models associated with y n will check (cf chapter 6.4)

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p } = L(I) 1 + ǫ .
One could better wish with difficulty like results. It is a very strong result which resolves the problem of definition.

Empirical properties

We remark that in the previous equation, there remain ǫ. We will see now that it is not annoying if it is rather small with respect to N, the size of sample.

Choice of the parameters

One thus chooses the parameters q, m and N according to the sample size. In this paragraph, we will clarify this point.

Let us suppose that we have a really IID sequence with uniform distribution on [0,1/2] and [1/2,0] and with a probability such as P {[0, 1/2]} = 0, 501. 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 it. To understand this difference, one will need samples with size larger than 1000.

One will thus solve the problem of the choice of ǫ in the same way: according to N , the wished size of the sample, one will choose ǫ and thus T q . Let us translate that mathematically.

Let us note by P e the empirical probability of an interval I associated with a sequence x * n = X * n (ω), n=1,2,....,N. Then, if X * n is a sequence of IID random variables with uniform distribution, if N is big enough,

P {N 1/2 |P e -L(I)| > σb} ≈ Γ(b) , where σ 2 = L(I)[1 -L(I)] . Now, if X * n checks only P {X * n ∈ I|x * 2 , ........, x * p } = L(I) + Ob(1)ǫ, one can prove that P {N 1/2 |P e -L(I)| > σb} ≤ Γ b[1 -η(ǫ)] ,
where η(ǫ) ≥ 0 and η(ǫ) → 0 as ǫ → 0. For example, let us suppose that we built T q so that η(ǫ) = 0.1. In this case, for b=1,5

P {N 1/2 |P e -L(I)| > σ.1.5} ≤ 0, 134 under IID hypothsesis, P {N 1/2 |P e -L(I)| > σ.1.5} ≤ 0, 148 if P {X n ∈ I|x 2 , ..., x p } = L(I) + Ob(1)ǫ.
However, it is known that if there is a really IID sequence, P e is close to L(I) with a certain probability: it is completely possible that P e is enough different from L(I), but the probability that occurs is weak. Now, if P {X n ∈ I|x 2 , ..., x p } = L(I) + Ob(1)ǫ, it is also possible that P e is enough different from L(I), but that is not likely much more to occur than in really IID case.

With such a result, it will be thus difficult to differentiate the x * n from a really IID sample.

Of course, if it is necessary, one can impose η(ǫ) smaller : for example, η(ǫ) = 0.01. In this case,

P {N 1/2 |P e -L(I)| > σ.1.5} ≤ 0, 135 if P {X n ∈ I|x 2 , ..., x p } = L(I) + Ob(1)ǫ.
This type of result holds again for I 1 ⊗ .... ⊗ I p where the I i 's are intervals. Moreover, one obtains a similar result for the empirical conditional probability P C e = P e {x n ∈ I|x 2 , ..., x p } :

P N 1/2 P C e -L(I) > b.σ C p ≤ Γ b[1 -η ′ (ǫ)] ,
where η ′ (ǫ) → 0 as ǫ → 0.

Case of Borel sets

Then, we can obtain P {X n ∈ I|x 1 , ......, x p } = L(I) + Ob(1)ǫ for the intervals I, by using the properties of T q . Then, for all Borel set Bo,

P {X n ∈ Bo|x 2 , ........, x p } = L(Bo) + Ob(1)2 q ǫ .
It is thus enough to choose q not too large and ǫ enough small so that 2 q ǫ is also enough small.

Relations about B 0 (n ′ )

The previous results being true for all Borel sets, one deduced equivalents results about the bits b 0 (n ′ ) provided by the writing of x(n) bases 2 :

P {B 0 (n ′ ) = b|b 2 , ........, b p } = 1/2 + Ob(1)ǫ ′ .
In practice ǫ ′ = Ob(1)α √ qN will be chosen where α ≤ 0.02 and where qN is the size of sequence b 0 (n ′ ).

Checking of definitions

It is thus proven that, that the model B 0 (n ′ ) built from ANY logical models of the data a(j) -or except maybe for a negligible minority (according to the case) -cannot be differentiated from a sequence of IID random variables.

In particular, it satisfies the properties

P {B 0 (n) = b | B 0 (n + j s ) = b s , s = 2, .., p} = 1/2 + Ob(1)α √ N q , P {N 1/2 |P C e -1/2)| > σ C p x} ≤ Γ x[1 -η] ,
which correspond theoretically and empirically to the definition 2.1.7 of the randomness.

It satisfies also

P {N 1/2 |P e -1/2 p | > σ p x} ≤ Γ x[1 -η] ,
which corresponds empirically to the definition 2.1.6 of the randomness.

Then all definitions of a random sequences are satisfied : the sequence b 0 (n ′ ) cannot be differentiated from a sample of IID random variables.

Comparison with the current generators 2.2.1 Various current techniques

Generators using algorithms 1) Pseudo Random generator for simulation . 2) Pseudo Random generator for cryptography.

3) Irrational numbers : for example π and e.

For these generators, it is admited that it will never provide really random sequence : "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin" : John Von Neumann (1951). These generators will certainly not check the definitions of randomness given by Knuth. One cannot thus mathematically regard them as random sequences. Then, the pseudo-random generators must be tested for each application : cf [START_REF] Gentle | Random Number Generation and Monte Carlo Method[END_REF] page 151.

Generators using random noises

1) Hardware-based random bit generators : they exploit the randomness which occurs in some physical phenomena :e.g. quantum phenomena. They use machine or chips.

2) Processes upon which software random bit generators may be based include 1) the system clock; 2) elapsed time between keystrokes or mouse movement; 3) content of input/output buffers.

A true random bit generator requires a naturally occuring sources of randomness. Designing a hardware device or software program to exploit this randomness and produce a bit sequence that is free of biases and correlation is a difficult task. Moreover, random bit generators based on natural sources of randomness are subject to influence by external factors, and also to malfunctions. It is imperative that such devices be tested periodically (cf [START_REF] Menezes | Handbook of Applied Cryptography[END_REF] ). Moreover, it is impossible to reproduce calculations exactly a second time when cheking out a program.

The major defect of all these systems is that there can be correlations and bias in the generated sequences. The underlying physical process can be random. But there are many measuring devices between the digital part of the computer and the physical device. These intruments can thus introduce bias and correlations (cf [START_REF] Schneier B | Applied Cryptography 2nd Edition[END_REF] ch 17.14 Bias and Correlation).

One removes these bias and these linear correlations by various mathematical transformations like that of Neuman or Vazirani ([4] [33]). One can also use hash functions (cf 17.14, [START_REF] Schneier B | Applied Cryptography 2nd Edition[END_REF] ).

However, the linear correlation are only one of the possible correlation. There exists correlations of higher order (quadratic cubic, etc : cf [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]). If there are bits, the correlation of higher order are the multilinear correlation between 3,4,5,..... bits. If one does not remove the correlation of higher order, one will not have independence.

Therefore, a priori the sequences of numbers built by the current methods to remove the linear correlation are not IID. It is a serious defect of the hardware device or software.

Tables of random numbers

One can obtain such tables by mechanical processes like the lotto or the roulette. They are the alone tables having results which are guaranteed IID.

But most of the time, these tables are obtained by the previous methods. They thus have the defects of them

In any case, these tables have a major defect: they are limited by their size. A particular case is the CD-Rom of Marsaglia. Indeed, the random bits of this CD-ROM were made by combining music rap with sources of electronic white noise and the output of deterministic random number generators.

But, the randomness of the obtained sequence was not proved mathematically. In this report, we want to know logically if this sequence were random: cf section 3. This study shows that to have more certainty, it is necessary that these sequences are built by a certain way That led us to take up the idea of Marsaglia: to regard certain electronic files as random noises, but to apply transformations a little more complex to them. That thus makes it possible to obtain true random numbers with a computer alone and to do without machines and chips. But, one can also use the numbers produced by machines

Conclusion

On none of the current generators there is certainty that the obtained sequences are random: that which approaches more this result is the Cd-Rom of Marsaglia.

However, much of users think that the provided generators are completely reliable and use them without precaution. All this already led to some scientific errors (cf [START_REF] Knuth | the Art of Computer Programming[END_REF] page 32). Thus, it is necesary to obtain a more reliable solution.

Comparisons

At first, it is proved that the obtained numbers by our method are really random. That had been obtained in no other method. Moreover, A) Comparison with the pseudo-random generators Our method thus brings obvious concrete advantages. In particular, in cryptography, there is no risks that the system can be broken. In simulation, there is not to test the numbers obtained.

Remind also that the usual opinion was that no generator built on computer is random. It is understood that it is an error : the truth is that no generator built by algorithm is random. B) Comparison with generators based on natural sources of randomness B-1) When one directly uses the program on a computer. 1) There does not need to add an additional machine to the computer.

2) There are no possible malfunctions as on the machines. Therefore, there is not to regularly test them like those.

3) The sequence obtained starting from the electronic files can be reproduced (it is useful for the checking of calculations). B-2) When one uses the program on a source of random noises 1) That removes all the dependences, and maybe even certain effects of the malfunctions.

2) One can have very long sequences quickly (contrary to the methods using software). C) Comparison with the CD-Rom of Marsaglia.

1) The results are proved.

2) The CD-ROM has a limited size.

3) A priori, it is possible that the sequence of the CD-Rom have defects.

Uses of these results

Direct programming on computer It is enough to transform certain files recorded on the computers. It is as simple to use as the function "random". Moreover, our generators are perfect. It is thus a method quite superior to the current generators.

Application to hardware devices One applies our transformations to data provided by machines or chips. That offers several advantages. On the one hand any dependence is removed, (and not only linear correlations).

On the other hand, our method can be applied as soon as the data are not completely deterministic. It is certainly the case for the data provided by the machines maybe even if they have malfunctions.

It is thus a new method which one proposes to transform the noises provided by these machines. The advantage, it is that it needs extremely weak assumptions to be applied.

Application to software methods One can choose as data those provided by the software methods. As for hardware devices, our method can be applied under wery weak assumptions. However, it is simpler to use text files than the system clock for example.

Use of files of IID sequences By using our method, one can develops files of numbers which are proved IID.

They could thus be placed for public use in the form of files to download, of files recorded on hard disk, of DVD or of CD-Rom as it is the case for the CD-Rom of Marsaglia (cf Internet site [START_REF] Marsaglia G | CD ROM[END_REF]).

Transformations of b 0 (n ′ ) From sequences b 0 (n ′ ) which are proved random, one can obtain a multitude of others by using any sequences y n provided by generators which are pseudo-random. Indeed, b 0 (n ′ ) + y n ′ modulo 2 is also IID (cf theorem 6).

Software for data external to the computer One can build softwares allowing to transform the majority of data external to the computer in random numbers, for example, texts.

Complete construction It is the matter to completely use the method of programming defined in this report with new data and choice of new parameters.

This method can be used when one wants, for various reasons, to obtain new sequences x n completely reliable.

Combination of several methods If one wants to avoid any risk of human error, of machine's error, of computer's error or other ones, one can build several sequences b 0 (n ′ ) as described above in section 2.3. Indeed, if one summons modulo 2 : b n = I s=1 b s n , it is enough that only one sequence b s n is random so that b n is it.

One will thus build them with different data. In this case, one can also use machines, even different machines. One can even employ the files of random numbers which exist over the world. That will reduce infinitely the probability of any potential error, human or different.

Chapter 3

Cd-Rom of Marsaglia

In this chapter, one will study the method which Marsaglia employed to create its CD-ROM. Marsaglia mixed digital tracks from rap and classical music selections. Then the random bits were made by combining three sources of electronic white noise with the output from a pseudo-random number generator. "They seem to pass all tests I have put to them -and I have some very stringent tests," Marsaglia says. Then, Marsaglia has studied his CD-Rom by using tests. But, it is possible to study it by logical reasoning.

In this section we give examples of such reasoning. In order to simplify we study only the case my ′ n = g n + my n ∈ F * (m) where g n is a pseudo random sequence and where the y n 's derive from a text1 .

Theoretical study

Case of 2-dependence

In section 11.2, we understand that the data d(j) which we use can be regarded as 2 dependent. Then, we study now the case where y n is 2-dependent. Suppose j ′ s+1 > j ′ s and j ′ s0+1j ′ s0 ≥ 2. Then, Then, it is enough to choose pseudo-random generators such that (g n , g n+1 , . ...., g n+22 ) are independent. In this case, to suppose that the y ′ n are independent will be a reasonable assumption.

(y ′ n+j ′ 1 , y ′ n+j ′ 2 , ....., y ′ n+j ′ p ) = (y ′ n+j ′ 1 , y ′ n+j ′ 2 , ....., y ′ n+j ′ s 0 )(y ′ n+j ′ s 0 +1 , .....,
Therefore the method of Marsaglia can be sufficient to obtain IID sequences if the parameters and the type of data have been suitably chosen.

However it remains to be checked that the marginal distributions are quite uniform: the tests of uniformity of the g n means that some tests are checked, for example for intervals. But is this case for all Borel sets? It is similar for independence : they are independence for some hypercubes of the g n : what is it for the others?

Transformation of datas

Now, one can use transformed data. It is what we do for sequence c(j) ∈ F * (32) defined in section 10.1.2 : we set d(j) = r0 r=1 c(r 0 (j -1) + r)32 r-1 .

Size of r 0 and conditional dependence

We choose again data resulting from texts. Then, if one finds a ". ", there is a strong probability so that it is followed by a "space character". Therefore, it is possible that it has there some strong dependences between c(j) and c(j+e) (where c(j) are the letters modulo 32) especially for e=1. But this dependence decreases very quickly if e increases.

That will mean that the possible concentrations of d(j+1) given d(j) = r0 r=1 c(r 0 (j -1) + r)32 r-1 will be less strong if r 0 increases. Indeed, suppose that d(j -1) means a piece of text ending in a "." . Then, d(j) belongs to the set of the part of texts starting with a "space character".

Then, the behavior of y ′ n depends on the choice of transformation and of parameters.

Independence induced by the data

We use again the example of ".". We note by p o their numerical value. Let z t ∈ {1, 2, ..., m} be the value of successive "n" such as y n = p o , i.e. y zt = p o . This sequence z t is random : one can write z t = Z t (ω 5 ) where Z t is a sequence of variable increasing in a random way, defined on a probability space (Ω 5 , A 5 , P roba 5 ). Then, in order to obtain my ′ n = g n + my n , we add g zt to y zt = p o .

In practice, we understand that Z t+1 -Z t is close to an IID sequence (not necessarily with uniform distribution). It is enough to make some numerical simulations to realize that (cf section 3.1.4 of [START_REF] Blacher R | Transformation d'une suite aléatoire q-dépendante[END_REF].

This result means that my ′ zt = g zt + my zt = g zt + mp o , has a behavior close to an IID sequence because g zt can be regarded as chosen randomly.

Conclusion

The previous study shows that one can improve the result by choosing better the parameters.

If they are well chosen, there is many reasons to think that y n is IID. But we have not a certainty : that is difficult to specify mathematically. Maybe a thorough study would allow to arrive at certainties.

But it is simpler to use transformations T q whose properties are appropriate well for the construction of an IID sequence and can be studied more easily. It is the aim of this report.

Chapter 4

Basic properties 4.1 Some properties Let X n ∈ F (m) be a sequence of random variables. In this section we study some properties of conditional probabilites when P X n ∈ Bo|x 2 , ...., x p = L(Bo) + Ob(1)ǫ for all Borel set Bo.

Proposition 4.1.1 Let Bo = Bo 1 ⊗ Bo 2 ⊗ ........⊗ Bo p be a Borel set of F (m) p .
Assume that, for all s ∈ {1, 2, ..., p}, for all sequence x t , t=2,3,..,p, and for all n ∈ N * , P X n ∈ Bo s |x 2 , ...., x p = L(Bo s ) + Ob(1)ǫ.

Then, for all injective sequence j s ∈ Z such that j 1 = 0 ,

P  {X n+j 1 ∈ Bo 1 } ∩ ...... ∩ {X n+jp ∈ Bop} ff = h L(Bo 1 ) + Ob(1)ǫ i ...... h L(Bop) + Ob(1)ǫ i .
In order to prove this proposition the following lemma is needed

Lemma 4.1.1 Let Y s ∈ F (m) , s=1,2,.
..,N be a sequence of random variables defined over a probability space (Ω, A, P ).

Let f ∈ L 1 be a measurable function defined over Y -(Ω) where Y -= (Y 1 , Y 2 , ..., Y n-1 , Y n+1 , ....., Y N ) and n ∈ {1, 2, ..., N } . Let Bo 1 be a Borel set of F(m). Assume P Y n ∈ Bo 1 |y 1 , ...., y n-1 , y n+1 , ..., y N = L(Bo 1 ) + Ob(1)ǫ for all (y 1 , ...., y n-1 , y n+1 , ..., y N ). Then, E 1 Bo1 (Y n )f (Y -) = L(Bo 1 )E f (Y -) + Ob(1)ǫE |f (Y -)| . Proof Let Q be the distribution of (Y 1 , Y 2 , ...., Y N ) and let Q -be the dis- tribution of (Y 1 , Y 2 , ..., Y n-1 , Y n+1 , ....., Y N ). Let Q(.|y 1 , ...., y n-1 , y n+1 , ..., y N ) be the distribution of Y n given Y s = y s , for s=1,2,...,n-1,n+1,...,N. Let y -= (y 1 , ...., y n-1 , y n+1 , ..., y N ). Then, E 1 Bo1 (Y n )f (Y -) = 1 Bo1 (y n )f (y -)Q(dy) = 1 Bo1 (y n )Q(dy n |y 1 , ...., y n-1 , y n+1 , ..., y N ) f (y -)Q -(dy -) = P Y n ∈ Bo 1 |y 1 , ...., y n-1 , y n+1 , ..., y N ) f (y -)Q -(dy -) = L(Bo 1 ) f (y -)Q -(dy -) + Ob(1)ǫ y -) f (y -)Q -(dy -),
where |ǫ y -) | ≤ ǫ. We deduce the lemma. We use the lemma 4.1.1 with N=p,

X n+js = Y s . Moreover, we choose f (Y -) = 1 Bo2 (Y n+j2 ).......1 Bop (Y n+jp ). Then, P {X n+j1 ∈ Bo 1 } ∩ ...... ∩ {X n+jp ∈ Bo p } = L(Bo 1 ) + Ob(1)ǫ P {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } .
Then, we prove the proposition by recurence. Now, one obtains a similar resul about conditional probability.

Proposition 4.1.2 Let Bo be a Borel set of F (m) p , Bo = Bo 1 ⊗ ..... ⊗ Bo p . Assume that P X n ∈ Bo 1 |x 2 , ...., x p = L(Bo 1 ) + Ob(1)ǫ. Then, P X n ∈ Bo 1 {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } = L(Bo 1 ) + Ob(1)ǫ.
Proof By using the proof 4.1.2 ,

P X n+j1 ∈ Bo 1 {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } = P {X n+j1 ∈ Bo 1 } ∩ {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } P {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } = L(Bo 1 ) + Ob(1)ǫ P {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } P {X n+j2 ∈ Bo 2 } ∩ ...... ∩ {X n+jp ∈ Bo p } = L(Bo 1 ) + Ob(1)ǫ.
The proof of the following theorem is a consequence of proposition 4.1.1.

Proposition 4.1.3 The sequence X n , n=1,2,.....,N, is IID if and only if, for all p ∈ {1, 2, ..., N -1}, for all sequence j s , for all n ∈ N * , for all Borel set Bo, for all sequence x s , s=1,...,p

P X n ∈ Bo X n+j2 = x 2 , ...., X n+jp = x p = L(Bo) .
Chapter 5

Dependence induced by linear congruences

We study in this chapter the dependence induced by T n (x 0 ), T n+1 (x 0 ) when T a congruence T (x) ≡ ax mod(m) with 0 < a < m and where a and m are fixed. Then, we study the set

E 2 = ℓ, T (ℓ) | ℓ ∈ {0, 1, ....., m -1} .
5.1 Theoretical study

Notations

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 5.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.

One denotes by d the smallest integer such as r d+1 = 0. One sets r d+2 = 0.

Therefore, 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, it is easy to prove the following result.

Proposition 5.1.1 The congruence T (x) ≡ a mod(m) is a Fibonacci conguence if h n = 1 for n=1,2,...,d, h d = 2 and r d = 1
In this case, r n is the Fibonacci sequence f i n , except for the last terms. In addition, one considers also the following sequences.

Notations 5.1.2 One sets k 0 = 0, k 1 = 1 and k n+2 = h n+1 k n+1 + k n if n + 1 ≤ d.
Remark that if h n = 1 for n=1,2,...,d-1, k n is also the Fibonacci sequence for n=1,2,...,d.

Theorems

One will understand that dependence depends on the h i : more they are small , more the dependence is weak. As h i ≥ 1, the best congruence will satisfy h i = 1 and h d = 2. It will be thus the congruence of Fibonacci.

Theorem 1 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. That 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 : E 2 ∩ [0, k n /2] ⊗ [r n-2 /2, r n-2 [ = ∅ . If h n-1 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.

Of course, one has equivalent results for rectangles modulo m :

R 0 = R 0 where R 0 = [x 0 , x 0 + k n ] ⊗ [y 0 , y 0 + r n-2 [ .
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⌋ ou ⌊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.

Principal theorem

Now, one takes in account the number of points of E 2 contained in rectangles of the type

R ect = [x, x + L[⊗[y, y + L ′ [. Theorem 2 It is supposed that T is invertible. Let R ect be a rectangle of F * (m) 2 , length L on ≥ 1, width L ar ≥ 1. Let N (R ect )
be the number of points of E 2 which belong to R ect and let S Rect be its surface. One denotes by Log the Neperian logarithm : Log(e)=1. Then,

N (R ect ) - S Rect m ≤ (p o + 1)[sup(h i ) + 1] ,
where p o is a function of (L on , L ar ) satisfying 2.0782.Log(m in ) + 2.00005 ≥ p o where m in = M in(L on , L ar ).

The proof is page 135 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] (cf also [START_REF] Blacher R | Quelques propriétés des congruences linéaires considérées comme générateur de nombres pseudo-aléatoires[END_REF]). This theorem shows that if sup(h i ) is small, the only rectangles where there is maybe breakdown of independence are the rectangles of the type [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] .

R 0 = [x, x + k n [⊗[y, y + r n-2 [ : cf page 135-140 of
Then, these rectangles do not contain enough points to make tests if h i is small. If y = T (x) the breakdown with independence is proved by theorem 1 : there is h n-1 + 1 lined up points. If h i is small, it is easy to understand that it is not important.

Thus, in the case of the Fibonacci sequence, all rectangles satisfy the test of normality. In fact, it is even statistically too. It is not important. We do not make use of it like sample of independent couple.

Numerical examples

We confirm by graphs the previous conclusion. We suppose m=21. If a = 13, we have a Fibonacci congruence : cf figure 5

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 .

Remark 5.1.1 For the Fibonacci congruence T 2 = ±Id where Id is the identity (cf page 141 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]) One cannot thus apply it to create directly a pseudo-random sequence.

Proof of theorem 1

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

Lemma 5.2.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.

Lemma 5.2.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 .
Proof : We prove this lemma by recurrence. For n=0,

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 5.2.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 5.2.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 .
If

h 1 = k 2 = 1, {1, 2, ..., k 2 -1} = ∅. In this case, we study t ∈ {1, 2, ..., k 3 -1} where k 3 = h 2 k 2 + k 1 = h 2 + 1. Then, 1 ≤ t ≤ h 2 . Then, at ≡ tak 2 ≡ -tr 2 . Moreover, m -r 2 ≥ m -tr 2 ≥ m -h 2 r 2 = r 0 -h 2 r 2 = r 0 -(r 1 -r 3 ) = r 3 + (r 0 -r 1 ) > r 3 . Therefore, because at ≡ m -tr 2 , at = m -tr 2 . Therefore, m -r 2 ≥ at > r 3 .
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 opposite to the assumption.
Then, in all the cases, for

t ′ ∈ {1, 2, ...., k n+1 -1}, m -r 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. One proves the recurrence by the same way as if n is even. Then the lemma is true for n+1.

Lemma 5.2.4

The following inequalities holds :

k d+1 ≤ m. Proof If t ∈ {1, 2, ..., k d+1 -1}, by lemma 5.2.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 5.2.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 5.2.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 5.2.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
The proof is basic.

Lemma 5.2.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 5.2.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 = m-r 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 5.2.7, si t ∈ L n+1 , t = l + gk n+1 where g ≤ h n+1 . By lemma 5.2.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. One proves this result by the same way as when n is even.

Proof 5.2.9 Now one proves theorem 1. 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 5.2.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 5.2.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 5.2.4,

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 .
Then, by lemma 5.2.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 5.2.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. One proves this result by the same way as when n is even.

Chapter 6

Randomization by the functions of Fibonacci

Study of the problem

In this section, we assume that our data y n are provided by texts. Then, one will understand how one can make IID the y n thanks to the Fibonacci functions

T d q = P r d q • T (cf Definition 1.2.5) (if d=2, one simplifies T d q in T q ).

Some Notations

In this chapter, the following notations are used.

Notations 6.1.1 In this chapter 6, q, d ∈ N * . Moreover, m is an element of the Fibonacci sequence :

m = f i n0 . Then, we set m = d Q where Q ∈ R + . Moreover, Y n ∈ F (m)
is a sequence of random variables defined on a probability space (Ω, A, P ) and

X n = T d q (Y n ) . Notations 6.1.2 Let k ∈ {0, 1, ...., d q -1}. We set I k = [k/d q , (k + 1)/d q [. We define the interval [c k /m, c ′ k /m[ with c k , c ′ k ∈ F * (m) by [c k /m, c ′ k /m[∩F (m) = [k/d q , (k + 1)/d q [∩F (m). We set N (I k ) = c ′ k -c k . More generally, we denote by I the intervals I = [k/d q , k ′ /d q [. Then, we de- fine [c/m, c ′ /m[ with c, c ′ ∈ F * (m) by [c/m, c ′ /m[∩F (m) = [k/d q , k ′ /d q [∩F (m). Then, N (I k ) is the number of t/m ∈ F (m) such that k/d q ≤ t/m < (k + 1)/d q . Notations 6.1.3 Let x s ∈ F (m). We set p xs = P T (mY n )/m) = x s . Of course, P X n = k/d q = P T (mY n )/m ∈ [c k /m, c ′ k /m[ = xs∈[c k /m,c ′ k /m[ p xs . Moreover, the following lemma holds. Lemma 6.1.1 With the previous notations, (c k -1)/m < k/d q ≤ c k /m and (c ′ k -1)/m < (k + 1)/d q ≤ c ′ k /m. Lemma 6.1.2 Let 1/d q = h 0 /m + r where 0 ≤ r < 1/m and h 0 ∈ N. Then, N (I k ) = h 0 or N (I k ) = h 0 + 1.
Moreover, m/d q = h 0 + e where 0 ≤ e < 1.

Sequence of real numbers regarded as IID

We show now that about any sequence of real numbers can be regarded as the permutation of an IID sequence.

Proposition 6.1.1 Let z n , n = 1, 2, ..., n 0 be a sequence of integers z n ∈ F * (m) such that all the z n 's are different.

Then, there exists a permutation φ such that z ′ n = z φ(n) , n = 1, 2, ..., n 0 , can be regarded as an IID sample having a distribution M Z .

Proof One can associate to z n a continuous distribution function F which is the smoothest possible and which have a density function which is the smoothest possible.

Let x n = x(n) be an IID sample with the distribution associated to F. For any function f, f (x n ) is a priori an IID sample. But it is necessary to be careful: it is better than f is not too complicated. For example f (x n ) can be increasing.

To avoid it, we denote by r x and r z the number of order of x(n) and z(n

) = z n , respectively : r x (n) and r z (n) are the permutations of {1, 2, ...., n 0 } such that x r -1 x (1) < x r -1 x (2) < .... < x r -1 x (n0) and z r -1 z (1) < z r -1 z (2) < .... < z r -1 z (n0) . Then, there exists a continuous function f such that f (x r -1 x (n) ) = z r -1 z (n) for n = 1, 2, ...., n 0 .
One can force this function to be smoothest possible with a Lipschitz coefficient not too large. Moreover, if it is not smooth enough, one can also use another IID sample {x 1 n }. Then, the following conjecture is applied. Conjecture 6.1.2 Let x n be an IID sample. One suppose that, for all function which is smooth enough with a Lipschitz coefficient not too large, f (x n ) can be regarded as an IID sample.

For this function f , f (x n ) can be regarded as an IID sample which has the same law as f (X 1 ). Now, {f

(x n ) | n = 1, 2, ..., n 0 } = {z n | n = 1, 2, ..., n 0 }.
Then, there exists a permutation φ such that z φ(n) = f (x n ) for n = 1, 2, ..., n 0 . Then, z φ(n) can be regarded as an IID sample. . Remark 6.1.3 Conjecture 6.1.2 is very likely. However it implies to choose a function according to the sample in order to deduce from it that the transformed sample is IID : it is always delicate. In fact it would be necessary to explicate all that. But it would be too long in this report.

But one understands well the meaning of this conjecture and one understands that it is very reasonable. Moreover, we have carries out many simulations which all, confirm it.

Now what means this result? It means that the sample z

′ n = f (x n ) behaves like a sample IID of law M Z . However if z ′
n is an IID sample, that means that, for almost all the permutations ψ, z ′ ψ(n) is a priori IID. Thus for almost all the permutations ψ ′ , z ψ ′ (n) is IID.

It is thus enough to check that it is indeed the case for various permutations chosen randomly. One thus tests the independence of the obtained sample.

For example, we choose a sample of the sequence not satisfying the CLT of Ibragimov-Linnik page 384 of [START_REF] Ibragimov | Independent and stationary sequences of random variables[END_REF]. Then, we have estimated multilinear correlation coefficients for various dimentions p : with a empirical variance equal to 39.57, the following values have been obtained : We have also used 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] ). All confirm independence. Moreover, if one takes subsamples, those are also independent and have the same law M Z . Now, one would like to apply the CLT. For studying this problem, we will apply proposition 6.1.1 to the sums. Corollary 6.1.5 For all sets F " = ψ ′ (F ′ ), except a negligible minority, n∈F " z ′ n behaves as the sum of an IID sample which has this same distribution M Z . Corollary 6.1.6 Let H be a measurable function. For all sets F " = ψ ′ (F ′ ), except a negligible minority, n∈F " H(z ′ n ) behaves as the sum of IID samples which have a same distribution M HZ . Corollary 6.1.7 For almost all the sets F,

1 card(F ) n∈F z n ≈ L where L does not depend on F.
Now, let us suppose that F is chosen randomly. Then, one can admit that F' is also chosen randomly.

Thus each time one has a sum over a set chosen randomly, one carries out a sum of a sample of an IID sequence of random variable Z ′ n . Then,

1 card(F ) n∈F Z ′ n → E{Z ′ 1 }.
Let us notice immediately that these results does not means that all the CLT can be regarded as a sum of IID sample. In no case, the sum Z 1 + ..... + Z n is necessarly close to a normal law. Now suppose that one uses the sample f (x(n)) = z(φ(n)). One separates it into several subsequences with the same size and one sums these subsequences. Then, the empirical distribution of those sums will be close to a normal law.

In figure 6.1, we have transformed by a permutation MATLAB chosen randomly a sample of size 900000 of the sequence not satisfying the CLT (cf page 384 of [START_REF] Ibragimov | Independent and stationary sequences of random variables[END_REF]). Then, one has it separated in 9000 successive subsequences which one has summed. It is understood that the distribution is close to a normal law. In the same way, if sums of the z n are chosen randomly, the sample consituted by these sums shows that one has a distribution close to a normal law. But these results do not mean inevitably that the exact distribution of a sum chosen randomly will be close to the normal law. By example, let us choose independent samples of the type z ψ(1) + .... + z ψ(n1) , n 1 < n 0 , where the subsamples z ψ(1) , ..., z ψ(n1) are all built with the same permutation ψ. Suppose that the sequence Z n has the distribution of the example not checking the CLT (page 384 of [START_REF] Ibragimov | Independent and stationary sequences of random variables[END_REF]).

Then these samples of sums will behave like a nonnormal samples. An estimate of the law obtained by these sample is in figure 6.2.

These results can appear strange. They thus should be explained. 1) If a sequence Z n does not satisfy the CLT, it is anyway possible that samples extracted of a sequence Z k+n2 , Z 2k+n2 , ..., Z nk+n2 do not satisfies the CLT, i.e. Z k+n2 + Z 2k+n2 + .... + Z nk+n2 has not a distribution close to the normal law. In this case, it is plausible that samples of type z ψ(1)+n2 , z ψ(2)+n2 ...z ψ(n)+n2 do not satisfy the CLT (where ψ is a permutation, for example of {1, 2, ...., kn}). Then, when one uses sums z ψ(1)+n2 , z ψ(2)+n2 ...z ψ(n)+n2 , they can regarded by two different ways : we have to choose which is the good one.

Then, Z ψ(1)+n2 + Z ψ(2)+n2 + .... + Z ψ(n)+n2
In subsection 6.1.3 below, what we want, it is to use

P {X n = k/d q } = xs∈[c k /m,c ′ k /m[ p xs where the sets T -1 ([c k , c ′ k [
) can be regarded as randomly chosen. Then, it is about sum randomly chosen : they behave as approximately normal.

Randomization of Y n

We have

P {X n = k/d q } = xs∈[c k /m,c ′ k /m[ p xs
. Now, there is no logical connection between text and the distribution of the points of {a 1 , a 2 , ....} = T -1 (I) where I is an interval. These two events are logically independent. Indeed, the sequence {a 1 , a 2 , ....} = T -1 (I) is built by a specific and relatively simple mathematical application whereas the data y n are the realization of a sequence of random variables Y n and thus unpredictable in an exact way. Moreover the sequence {a 1 , a 2 , ....} is well distributed in F(m). It is reasonable to think that this set is independent of sequences obtained starting from text. One can thus regard this set as randomly chosen.

That means that xs∈[c k /m,c ′ k /m[ p xs can be regarded as a sum s∈F p xs where the set F is a Borel set chosen randomly. According to the corollary 6.1.7, that means that, for all k, (d q /m) xs∈[k/d q ,(k+1)/d q [ p xs converges to the same limit L.

One is all the more sure of this result that only a negligible minority of the possible sets F will not check this property: because there is only d q "k" possible, it is thus enough to choose m enough large compared to d q .

At last [START_REF] Neumann | Various techniques used in connection with random digits[END_REF][START_REF] Neumann | Various techniques used in connection with random digits[END_REF]. We obtain,

, k xs∈[k/d q ,(k+1)/d q [ p xs = 1. Therefore, xs∈[k/d q ,(k+1)/d q [ p xs ≈ 1/d q . Example In figure 6.3, one supposes card [c, c ′ [∩F * (m) = 10. One under- stands that {a ′ 1 , a ′ 2 , ...., a ′ 10 } is about uniformly distributed in [-
P {X n = k/d q } ≈ 1/d q . -4 -3 -2 -1 0 1 2 3

Empirical Probability

Unidimensional case

Let us be interested with a sample x * n = T q (y n ), n = 1, 2, ...., n 0 , where all the y n are distinct. Let pe xs = P e T (mY n )/m = x s where P e is the empirical probability. Then, one has

P e T q (Y n ) ∈ [c/m, c ′ /m[ = xs∈[c/m,c ′ /m[ pe xs .
There is no logical connection between the set J =

Thus a priori, the probability that [N ewton

′ stheory] ∈ H is approximatively of card(H)/32 18 if y n ∈ {0, 1, ...., 31} 1 .
Now, there is no logical connection between the y n and the set A = {a 1 , a 2 , ....}. Then, the set {a 1 , ....., a c ′ -c } is well chosen randomly. Then, by corollary 6.1.7,

1 n0 n0 n=1 1 {a1,.....,a c ′ -c } (y n ) → N (A) m
where N A = c ′c. Finally, P e X n ∈ [k/d q , (k + 1)/d q [ ≈ 1/d q for any k.

One can also understand this result by a more classical way : cf section 6.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] Now, because the subsample of the y n such that y n ∈ A can be regarded as IID (cf corollary 6.1.6),

1 √ n0σ N A n0 n=1 1 {a1,.....,a c ′ -c } (y n ) -N A /m has asymp- totically a standard normal distribution where σ 2 N A = N A /m -(N A /m) 2 .
One has checked these results by testing them with the the sequence d(j), j=1,2,... : cf section 10.1 . All the tests conclude to the uniformity In figure 6.4 , we have the histogram for the sequence d(j). The figure 6.5 which represents the histogram for a pseudo-random sequence of uniform distribution.

Multidimensional case

For t=1,2,...,p, we set

I t = ct m , c ′ t m where c t , c ′ t ∈ F * (m). We set A t = T -1 (I t ) = {a t 1 , ....., a t c ′
t -ct } for t=1,2,...,p. There is no logical connection between the sets J and H s . Then, the probability that {[Newton's theory ], [of gravitation was], [ soon accepted wit]} ⊂ H 1 ⊗ H 2 ⊗ H 3 is approximatively equal to 3 t=1 card(H t )/32 18 . This result can be understood by simulation.

Because there is always no connection between parts of texts (y n+j1 , ....., y n+jp ) and the sets A 1 ⊗ .... ⊗ A p , it is thus logical that sums on the various possible sets A 1 ⊗ .... ⊗ A p (where p ≤ Log(n 0 )/log(2) ), behave as sums over sets chosen randomly, i.e.

P e X n+j1 ∈ I 1 ∩....∩ X n+jp ∈ I p = x 1 s 1 ∈I 1 .... x p sp ∈I p pe x 1 s 1 ,..,x p sp ≈ p t=1 L(I t ) ,
where pe

x 1 s 1 ,..,x p sp = P e {T (mY n+j1 )/m = x 1 s1 } ∩ .... ∩ {T (mY n+jp )/m = x p sp } .

Theoretical probability

Let us choose a random vector (X n+j1 , X n+j2 , ...., X n+jp ). We set

p x 1 s 1 ,..,x p sp = P (T (mY n+j1 )/m = x 1 s1 ) ∩ ... ∩ (T (mY n+jp )/m = x p sp ) .
Probabilities chosen randomly As for empirical probabilities P X n+j1 ∈ I 1 ∩....∩ X n+jp ∈ I p is equal to a sum of p x 1 s 1 ,..,x p sp . Because y n means texts and is independent with sets T -1 q (I 1 ) ⊗ .... ⊗ T -1 q (I p ), the sums are about sets randomly chosen. Therefore the p x 1 s 1 ,..,x p sp 's can be regarded as an IID sample of random variables which have a distribution M Z .

Model Because n 0 << m, there are many possibles models associated to the sample y n , n = 1, 2, .., n 0 . As a matter of fact there in an infinity of them. Then, because there are several possible correct models meaning this text, we will study the various possible probabilities p With a such model, we have proved in [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] section 8.4.2, that with a probability very close to 1,

P X 1 ∈ I 1 ∩ ..... ∩ X p ∈ I p ≈ s (c ′ s -c s ) m p 1 + Ob(1).bσ M E M s N (I s )
. Remark 6.3.1 This approximation is not the same as

1 n0 n0 n=1 1 {a1,..,a c ′ -c } (y n ) = N A /m + Ob(1).bσ N A √ n0
because in this last one, the empirical approximation is involved.

As a matter of fact with this probability P ′ x 1 s 1 ,..,x p sp , p is fixed. If p is changed, one changes space of measure.

The problem of marginals distributions

If the model defined on spaces (Ω p 1 , A p 1 , P roba p 1 ) is chosen (cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] page 217 section 8.4.2), there is a problem : one does not take account of the marginal probabilities.

If p=2, in space (Ω 2 1 , A 2 1 , P roba 2 1 ) those sums will be already sums of probabilities taken randomly. That means that, with this measure, the marginal probabilities p x 1

s 1 = x 2 s 2 p x 1 s 1 ,x 2 s 2
in their vast majority will have a priori uniform distribution. One thus does not take in account that the p x 1 s 1 are probabilities in two dimensions with marginal laws, i.e. with constraints.

It is thus a result which seems not to correspond to reality, for example if P ′ x 1 s 1 ,..,x p sp has continuous densities.

Anyway, this is not very important: measures of spaces (Ω p 1 , A p 1 , P roba p 1 ) are only measures giving an idea of the numbers of models close to a sequence IID. Moreover, that does not change anything with the ultimate result : only a negligible minority of models does not check

P X 1 ∈ I 1 ∩ ..... ∩ X p ∈ I p ≈ s (c ′ s -c s ) m p 1 + Ob(1)ǫ
where |ǫ| << 1.

Two dimensional case

If one wants to take account of the marginal laws, it is necessary to consider the probabilities of each Y n+jt , i.e the probabilities of the marginal laws. Then it should be considered that the sums are taken randomly: for example

xs 1 =x 0 s 1 ,xs 2 ∈A2 p xs 1 ,xs 2 ≈ p x 0 s 1
. Now, it is necessary to define associated probability spaces. One thus chooses probability spaces (Ω xs 1 , A xs 1 , P roba xs 1 ) for each x s1 : one uses product space (Ω 2 , A 2 , P roba 2 ) = One takes also into account the probability space (Ω 1 , A 1 , P roba 1 ) associated with the first marginal law and finally one uses product space (Ω, A, P roba) = (Ω 1 , A 1 , P roba 1 ) ⊗ (Ω 2 , A 2 , P roba 2 ).

xs 1 Ω xs 1 , T xs 1 A xs 1 ,
Let us notice that it poses the problem then to know if one chooses to take the sums

xs 1 =x 0 s 1 ,xs 2 ∈A2 p xs 1 ,xs 2 or xs 1 ∈A1,xs 2 =x 0 s 2 p xs 1 ,xs 2 .
As a matter of fact for the results which we try to obtain, we will understand that does not have importance. Hypothesis 6.3.1 Suppose that

p x 1 s 1 ,x 2 s 2 = p ′ x 1 s 1 p ′ x 1 s 1 ,x 2 s 2 P m i 2 =1 p ′ x 1 s 1 ,i 2 /m m i1=1 p ′ i1/m .
We assume that the p ′ . We assume also that, for each x 1 s1 , the p ′

x 1 s 1 ,x 2 s 2
's are a sample of an IID sequence of random variables P ′

x 1 s 1 ,x 2 s 2 . Then, p ′ x 1 s 1 ,x 2 s 2 = P ′ x 1 s 1 ,x 2 s 2
(ω) and

p ′ x 1 s 1 = P ′ x 1 s 1
(ω) where ω ∈ Ω.

One supposes that P ′

x 1 s 1

and, for each x 1 s1 , P ′

x 1 s 1 ,x 2 s 2
have the distribution M.

Let E M and σ 2 M be the associated expectation and variance.

Hypothesis 6.3.2 We assume that

I t = k t /d q , (k t + 1)/d q . Let N (I t ) be the number of r/m ∈ F (m) such that k t /d q ≤ r/m < (k t +1)/d q . Let c t , c ′ t ∈ F * (m) such that I t ∩ F (m) = [c t /m, c ′ t /m[∩F (m).
We suppose m enough large compared to d q and to h 0 . We suppose d q >> 1. We suppose that b and σ M are not too large and that E M is not too small.

We shall need the following notations.

Notations 6.3.1 Let b > 0. Let Γ ′ 1 (b) = M ax n≥h0 P roba |S n | ≥ b where S n = P n i 1 =1 P ′ i 1 /m σ M √ n . Remark that Γ ′ 1 (b) = M ax n≥h0 P roba |S ′ n | ≥ b where S ′ n = P n i 1 =1 P ′ x 1 s 1 ,i 2 /m σ M √ n and x 1 s1 ∈ F (m). Moreover, Γ ′ 1 (b) ≈ Γ(b) because m/d q is large enough.
Then, one has the following proposition.

Proposition 6.3.1 Under the hypotheses 6.3.1 and 6.3.2, with a probability larger than 1 -4Γ ′ 1 (b),

P {X 1 ∈ I 1 } ∩ {X 2 ∈ I 2 } = N (I 1 )N (I 2 ) m 2 [1 + Ob(1).ǫ ′ (2) ] ,
where

ǫ ′ (2) ≈ 2bσ M E M √ h0 .
Proof At First,

x 1 s 1 ∈I1 x 2 s 2 ∈I2 p x 1 s 1 ,x 2 s 2 = x 1 s 1 ∈I1 x 2 s 2 ∈I2 p ′ x 1 s 1 p ′ x 1 s 1 ,x 2 s 2 P m i 2 =1 p ′ x 1 s 1 ,i 2 /m m i1=1 p ′ i1/m = x 1 s 1 ∈I1 p ′ x 1 s 1 P x 2 s 2 ∈I 2 p ′ x 1 s 1 ,x 2 s 2 P m i 2 =1 p ′ x 1 s 1 ,i 2 /m m i1=1 p ′ i1/m .
We use the CLT. Then, with a probability larger than 1

-Γ ′ 1 (b), 1 N (I 2 ) x 2 s 2 ∈I2 p ′ x 1 s 1 ,x 2 s 2 = E M + Ob(1).bσ M N (I 2 ) .
Moreover, with a probability larger than 1

-Γ ′ 1 (b), 1 m m i2=1 p ′ x 1 s 1 ,i2/m = E M + Ob(1).bσ M √ m .
Then, with a probability larger than 1 -2Γ ′ 1 (b),

p ′ x 1 s 1 x 2 s 2 ∈I2 p ′ x 1 s 1 ,x 2 s 2 m i2=1 p ′ x 1 s 1 ,i2/m = p ′ x 1 s 1 N (I 2 ) m E M + Ob(1).bσ M √ N (I2) E M + Ob(1).bσ M √ m = N (I 2 )p ′ x 1 s 1 m 1 + Ob(1).bσ M E M √ N (I2) 1 + Ob(1).bσ M E M √ m = N (I 2 )p ′ x 1 s 1 m [1 + Ob(1).ǫ 2 ] ,
where

ǫ 2 ≈ bσ M E M √ N (I2) + bσ M E M √ m .
Moreover, with a probability larger than 1

-2Γ ′ 1 (b), 1 N (I 1 ) x 1 s 1 ∈I1 p ′ x 1 s 1 = E M + Ob(1).bσ M N (I 1 ) , 1 m m i1=1 p ′ i1/m = E M + Ob(1).bσ M √ m .
Then,

x 1 s 1 ∈I1 p ′ x 1 s 1 m i1=1 p ′ i1/m = N (I 1 ) m E M + Ob(1).bσ M √ N (I1) E M + Ob(1).bσ M √ m = N (I 1 ) m [1 + Ob(1).ǫ 1 ] ,
where

ǫ 1 ≈ bσ M E M √ N (I1) + bσ M E M √ m . Moreover, 1 N (I 1 ) x 1 s 1 ∈I1 Ob(1)p ′ x 1 s 1 = Ob(1) N (I 1 ) x 1 s 1 ∈I1 p ′ x 1 s 1 = Ob(1) E M + Ob(1).bσ M N (I 1 ) .
Then, with a probability larger than 1 -2Γ ′ 1 (b),

x 1 s 1 ∈I1 Ob(1)p ′ x 1 s 1 m i1=1 p ′ i1/m = Ob(1)N (I 1 ) m E M + Ob(1).bσ M √ N (I1) E M + Ob(1).bσ M √ m = Ob(1)N (I 1 ) m [1+Ob(1).ǫ 1 ] .
Then, with a probability larger than 1 -4Γ ′ 1 (b),

x 1 s 1 ∈I1 x 2 s 2 ∈I2 p x 1 s 1 ,x 2 s 2 = x 1 s 1 ∈I1 p ′ x 1 s 1 P x 2 s 2 ∈I 2 p ′ x 1 s 1 ,x 2 s 2 P m i 2 =1 p ′ x 1 s 1 ,i 2 /m m i1=1 p ′ i1/m = x 1 s 1 ∈I1 N (I2)p ′ x 1 s 1 m [1 + Ob(1).ǫ 2 ] m i1=1 p ′ i1/m 50 = N (I 1 )N (I 2 ) m 2 [1 + Ob(1).ǫ 1 ][1 + Ob(1).ǫ 2 ] = N (I 1 )N (I 2 ) m 2 [1 + Ob(1).ǫ ′ (2) ]
where

ǫ ′ (2) ≈ bσ M E M √ N (I1) + bσ M E M √ m + bσ M E M √ N (I2) + bσ M E M √ m ≈ 2bσ M E M √ h0 .
The form of this result resolve the problem of knowing if one chooses initially the sums

xs 1 =x 0 s 1 ,xs 2 ∈A2 p xs 1 ,xs 2 or xs 1 ∈A1,xs 2 =x 0 s 2 p xs 1 ,xs 2 .
Whatever the chosen sum, the result remains the same one :

ǫ ′ (2) ≈ 2bσ M E M √ h0 .
We have regarded the probabilities associated with (X n+j1 , X n+j2 ) when n and the sequence j s are fixed. But we will need also a definite probability space for any n and all j 2 . Then, we shall use the following assumptions. Hypothesis 6.3.3 We generalize by natural way the notations of hypothesis 6.3.1. For each n and each j 2 , we replace the notation of the probability space (Ω, A, P roba) by (Ω (n,j) , A (n,j) , P roba (n,j) ).

In this case, we denote by (Ω, A, P roba) the probability space (Ω, A, P roba) = n,j (Ω (n,j) , A (n,j) , P roba (n,j) ). and p ′

General case

x 1 s 1 ,x 2 s 2 in p ′ x 1 s 1 ,x 2 s 2
,...,x p sp which are samples of sequences of IID random variables defined on the probability spaces (Ω (n,j) , A (n,j) , P roba (n,j) ) and which have the distribution M. We denote by (Ω, A, P roba) the probability space (Ω, A, P roba) = n,j (Ω (n,j) , A (n,j) , P roba (n,j) ).

Then, one generalize easily proposition 6.3.1. Proposition 6.3.2 Under the hypotheses 6.3.4 and 6.3.2 , with a probability larger than 1 -2pΓ ′ 1 (b),

P {X 1 ∈ I 1 } ∩ .. ∩ {X p ∈ I p } = p r=1 N (I r ) m p [1 + Ob(1).ǫ ′ (p) ] ,
where

ǫ ′ (p) ≈ pbσ M E M √ h0 .
We deduce the following proposition.

Proposition 6.3.3 Under the hypotheses 6.3.4 and 6.3.2, with a probability larger than 1 -2pΓ ′ 1 (b),

P X 1 = k 1 /d q , ....., X p = k p /d q ≈ 1 d pq [1 + Ob(1).ǫ ′ (p) ] . Proof We have P X 1 = k 1 /d q , ....., X p = k p /d q = P {X 1 ∈ I 1 } ∩ .. ∩ {X p ∈ I p } = Q s (c ′ ks -c ks ) m p [1 + Ob(1).ǫ ′ (p) ] . Moreover, c ′ ks -c ks m = 1 d pq [1+ǫ a ]
, where ǫ a = p.d q Ob(1) m + p(p-1)d 2q Ob(1)

2m 2 +... << ǫ ′
(p) by hypothesis 6.3.2. Then,

P X 1 = k 1 /d q , ....., X p = k p /d q = 1 d pq [1+ǫ a ][1+Ob(1).ǫ ′ (p) ] ≈ 1 d pq [1+Ob(1).ǫ ′ (p) ] .
Now, we study the Borel sets of F (d q ) ⊗p : Bo = ∪ (k1,...,kp)∈Θ {(k 1 /d q , ..., k p /d q )} = ∪ (k1,...,kp)∈Θ {I k1 ⊗....⊗I kp } where

I kt = [k t /d q , (k t +1)/d q [. Then, L(Bo) = KΘ d pq .
We have the following proposition.

Proposition 6.3.4 . Assume that, for all (k 1 , ..., k p ),

P X 1 = k 1 /d q , ....., X p = k p /d q = 1 d pq [1 + Ob(1)ǫ ′ (p) ]. Then, P (X n+j1 , ...., X n+jp ) ∈ Bo = L(Bo)[1 + Ob(1)ǫ ′ (p) ].
Proof We can write

P (X n+j1 , ...., X n+jp ) ∈ Bo = (k1,...,kp)∈Θ 1 d pq [1+Ob(1)ǫ ′ (p) ] = K Θ d pq [1+Ob(1)ǫ ′ (p) ] .
Now, one can prove the following result.

Proposition 6.3.5 We assume that the the hypotheses 6.3.4 and 6.3.2 hold. Let 1 ≤ n ≤ n 0 . Let P Xn (Bo) = P (X n+j1 , ...., X n+jp ) ∈ Bo . One supposes that M is the uniform distribution. Then,

P roba n+jt,Bo P Xn (Bo) -L(Bo) ≤ 2b.pL(Bo) √ 3.d Q-q ≥ 1 -2p.n p 0 d pq Γ ′ 1 (b) . (6.1) Proof Let {k} = {k 1 } ⊗ .... ⊗ {k p }. Clearly, |Ob(1)|.pbσ M E M √ h0 ≈ |ǫ ′ (p) | ≤ 2pbσ M E M √ d Q-q .
Then, by the proof of proposition 6.3.3, with a probability larger than 1 -

2pΓ ′ 1 (b), P Xn ({k}) = L({k}) 1 + Ob(1).2p.bσ M E M . √ d Q-q .
Then, because σ 2 M = 1/12, E M = 1/2,

P roba P Xn ({k}) -L({k}) > L({k}) 2b.p √ 3.d Q-q ≤ 2pΓ ′ 1 (b) . n+jt,Bo P Xn (Bo) -L(Bo) ≤ L(Bo) 2pbσ M E M √ d Q-q ⊃ n+jt,{k} P Xn ({k}) -L({k}) ≤ L({k}) 2pbσ M E M √ d Q-q .
There are d pq sets {k}. Moreover, there is at the maximum (n 0 ) p "n + j t " possible. Then,

P roba n+jt,Bo P Xn (Bo) -L(Bo) ≤ L(Bo) 2b.p √ 3.d Q-q ≥ P roba n+jt,{k} P Xn ({k}) -L({k}) ≤ L({k}) 2b.p √ 3.d Q-q = 1 -P roba ∁ n+jt,{k} P Xn ({k}) -L({k}) ≤ L({k}) 2b.p √ 3.d Q-q = 1 -P roba n+jt,{k} P Xn ({k}) -L({k}) > L({k}) 2b.p √ 3.d Q-q ≥ 1 - n+jt,{k} P roba P Xn ({k}) -L({k}) > L({k}) 2b.p √ 3.d Q-q = 1 - n+jt,{k} 2pΓ ′ 1 (b) = 1 -2p.n p 0 d pq Γ ′ 1 (b) . Now, Γ ′ 1 (b) ≈ Γ(b) ≈ √ 2
√ πb e -b 2 /2 when b is big (cf (28)' page 56 [START_REF] Johnson | Continuous univariate distributions[END_REF]). Then, if

d=2, 2p(n 0 ) p 2 pq Γ ′ 1 (b) ≈ 2 √ 2.p(n0) p 2 pq e -b 2 /2 √ πb ≈ 2 √ 2.pe Log(n 0 )p e log(2)pq e -b 2 /2 √ πb
. Then, we have to impose b ≥ 2[Log(n 0 )p + Log(2)pq] in order that the inequality 6.1 is useful. We deduce the following properties. Proof Indeed, in this case,

2p(n 0 ) p 2 pq Γ ′ 1 (b) ≈ 2 √ 2.pe Log(n0)p e Log(2)pq e -b 2 /2 √ πb = 2 √ 2.pe Log(n0)p e Log(2)pq e -1.5.p[Log(n0)+q] 3πp[Log(n 0 ) + q] ≤ 2 √ 2.p.e -Log(n0)p/2 e -pq/2 3πp[Log(n 0 ) + q] .
Now, b has to be not too large.

Property 6.3.3 Assume d=2. Then, in order that the inequality 6.1 is useful, we can impose

ǫ 3 = [Log(n0)+q]p 3 2 q m << 1. Proof If one chooses b = 3p[Log(n 0 ) + q] 2bp √ 3 * 2 Q-q ≤ 2p 3p[Log(n 0 ) + q] √ 3 * 2 Q-q = 2 p 3 [Log(n 0 ) + q] √ 2 Q-q ≤ 2 [Log(n 0 ) + q]p 3 2 q m . If ǫ 3 << 1, P roba n+jt,Bo P Xn (Bo) -L(Bo) ≤ 2 √ ǫ 3 L(Bo) ≈ 1 .
Property 6.3.4 If d=2, in order that the inequality 6.1 is useful, we can impose 1) if one regards all the possible "p", [Log(n0)+q](n0) 3 2 q m << 1,

2) if one regards all the p ≤ p m = ⌊Log(n 0 )/log(2)⌋, [Log(n0)+q](pm) 3 2 q m << 1.

Continuous density

Consider the vector (X n+j1 , ..., X n+jp ). We know that

x 1 s 1 ∈ c 1 m , c ′ 1 m ..... x p sp ∈ cp m , c ′ p m p x 1 s 1 ,

54

Let us suppose that (Y n+j1 , ...., Y n+jp ) has a density function with a Lipschitz coefficient K 0 not too large. Suppose that the c ′ t -c t are large enough. We know that the sets

A t = T -1 (mI t )/m = T -1 [c t , c ′ t [ /m
are well distributed in F(m), i.e. the sets A t have a distribution close to that of {r/N (I t )|r = 0, 1, ..., N (I t )} (see below). Then, by applying the traditional methods of integration, it is clear that

x 1 s 1 ∈I1 ..... x p sp ∈Ip p x 1 s 1 ,..,x p sp ≈ p t=1 L(I t ) .
Under this assumption, one thus obtains easily IID sequences. Let us recall that, when n 0 << d p , one often accepts like model a model with continuous density and a Lipschitz coefficient K 0 not too large. That shows that the functions T q are a good tool to obtain IID sequences.

Theoretical study

For example if p=1, the following property holds.

Property 6.3.5 Let m >> 1. Let h N be the probability density function of Y ∈ F (m) with respect to µ m : Proof We need the following lemmas. Lemma 6.3.6 The following equality holds :

1 0 h N (u)µ m (du) = 1. Let h ′ N = (1/c 0 )h N be the probability density function 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].
c 0 = 1 + O(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.7
The following equality holds : 1

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

Proof The following equalities hold :

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

Therefore, by lemma 6.3.6,

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

Because m >> 1 and N (I) ≤ m/2, we deduce the lemma.

Then, the following property holds.

Property 6.3.8 Let I = [c/m, c ′ /m[. Let g N (k) = h N T -1 (k)/m . Assume
again that T is a Fibonacci congruence. The following approximation holds

1 N (I) c ′ -1 k=c g N (k) = 1 + 6Ob(1)K 0 N (I) . Proof Let k n , n=1,2,..,c'-c, be a permutation of I ∩ F (m) = {c/m, (c + 1)/m, ...., (c ′ -1)/m} 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

|T -1 (k r )/m -r/N (I)| ≤ 4/N (I) .
We deduce that |g N (k r )h N (r/N (I))| ≤ 4K 0 /N (I).

Therefore, by lemma 6.3.7,

1 N (I) c ′ -1 k=c g N (k) = 1 N (I) r g N (k r ) = 1 N (I) r h N (r/N (I)) + 1 N (I) r g N (k r ) -h N (r/N (I)) = 1 N (I) r h N (r/N (I)) + 4Ob(1)K 0 N (I) = 1 + 2Ob(1)K 0 N (I) + 4Ob(1)K 0 N (I) .
Remark 6.3.9 The only result which is not proven mathematically is

|T -1 (k r )/m -r/N (I)| ≤ 4/N (I) .
It is enough to prove this result in order that property 6.3.5 is fully proven. We point out that, by our numerical study, this result seems sure.

Proof of property 6.3.5 By the previous equalities, The previous results can be proved in another manner. In this case, there is a less fine approximation : cf property 7.1.21 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

P {T (Y )/m ∈ I} = 1 m k g N (k) = N (I) m 1 + 6Ob(1)K 0 N (I) = L(I) 1 + Ob(1) m 1 + 6Ob(1)K 0 N (I) = L(I) 1 + O(1)K 0 N (I) .

Numerical results

All the results which we have obtained confirm the previous result. For example, when h N (y) ≈ 10.e -[10(y-0. Many other numerical results are in [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] section 7.1.2. All the results which we have obtained confirm the property 6.3.5.

General numerical results

In [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] , we have studied the case where the probability density function of Y with respect to µ m is written in a form : h(y) 1 + η(y) co , where η(y) is a sample of a white noise independent of h and where h(y)µ m (dy) ≈ 1. We have obtained equivalent result. Here we recall some results when h is a normal or uniform density.

Normal case

We assume that h(y) ≈ 10.e -[10(y-0.5)] 2 /(2σ 2 )

√ 2πσ 2
, co ≥ 10. Then, we have proved

that P m √ σ|ǫ G I | 0.0485 √ N (I) ≥ b ≈ Γ(b) where ǫ G I = N (I)/m -P {X ∈ I}.
This result thus gives us a probable increase of |ǫ G I |. Example 6.3.12 Suppose that we do not have more than 10 6 possible intervals I. We know that Γ(6) ≤ 10 -9 .Then, if N(I) is not too small, one can assume

|ǫ G I | ≤ 0.291 N (I) m √ σ . (6.2)
For example, suppose m= 267914296 , a= 165580141. We choose intervals I length L(I) = (1/5)10 -j for j =1,...,6 . Choose standard deviations σ = 1/2, 1/4, 1/8, 1/40.

For each j, one calculated each ǫ G I for 50 intervals I s , s=1,2,..,50 length (1/5)10 -j . Then, one obtains the following table of M ax s {0. 0.0067 0.0328 0.0097 -0.1834 (1/5)10 -4 -0.0008 0.0004 0.0046 0.0083 (1/5)10 -5 -0.0008 -0.0014 0.0025 -0.0152 (1/5)10 -6 -0.0000 -0.0010 0.0010 0.0013 (1/5)10 -7 -0.0006 0.0002 -0.0032 -0.0044

We have other various numerical results : a more complete study has been done in section 7.1 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] Uniform distribution

Here we study the model P Y {Y = k/m} = 1 m 1 + u k where u k is a sample of an IID sequence U k with variance σ 2 U . Let I be an interval. We set ǫ I = N (I)/m -P {X ∈ I}. Let N Iel = Sup k card F (m) ∩ [k/2 q , (k + 1)/2 q [ = ⌊m/2 q ⌋ + 1. Then, for all interval I k , generally,

P m|ǫ I k | σ U √ N Iel ≥ b q ≤ 4 -q .
Because there are only 2 q intervals I k = [k/2 q , (k + 1)/2 q [, one can admit

|ǫ I k | ≤ b q σ U √ N Iel m . (6.3)
For example for datas h(n) used section 11.1.1, if m ≥ 1.4 * 10 31 , σ U ≤ 1 and if q=84, one choose b q = 15, N Iel ≈ 7520. Then, one can suppose

|ǫ I k | ≤ 9.3 10 29 .
A more complete study has been done in section 7.2 of [18]

Other congruences

Similar results are obtained with other congruences. But the approximations are less good. For example we proved the following result in section 4.1.1 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. Let Z ∈ F (m) be a random variable. Let f be the density of Z with respect to µ m . Let K 0 > 0 such that, for all z, z

′ ∈ F (m), |f (z) -f (z ′ )| ≤ K 0 |z -z ′ |. Then, P T (Z)/m ∈ I = N (I) m + O(6K 0 ) d p .

Remarks

Remark 6.3.13 The previous results were obtained by considering that one chose randomly a measure in the set of the possible probabilities. But, for that , one needs that the probabilities of the X n are not concentrated in a small number of points. If not, the majority of the p xs will be equal to 0 and could not thus be regarded as chosen randomly. Of course, it is one of the exception envisaged in section 5.4 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. But it is better to remove this case. At first, it is necessary that one has a sample of y n which all are different. In this aim, it is enough that m is large with respect to n 0 .

Moreover, it is better that a priori all the possible values of F (m) p can exist in a sample. For p=1, it is reasonably the case when one adds modulo m a pseudo-random sequence g n of period m : my ′ n = g n + my n . For p=2, one can use two generators g 1 2n ′ and g 2 2n ′ +1 : if n=2n', my ′ 2n ′ = g 1 2n ′ + my 2n ′ Remark 6.3.14 We can make this study without supposing that T is the congruence of Fibonacci. But, the conclusion does not hold when T is the identity and that the curve of the probabilities have the shape of a normal curve. It is natural : contrary to the congruence of Fibonacci, there is a dependence between T and text : if y n means an extract of texts, T (y n ) means the same extract of text. It is the same when T (x) ≡ d p x modulo d 2p -1 (cf proposition 6.3.6). Remark 6.3.15 There exists another method to prove our conclusions: it should be considered that the probabilities are fixed and the a i are taken randomly : cf section 8.3 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

Study of models

A more detailed study of models is in chapter 13 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

Continuous densities

Let us suppose that one has a sample resulting from texts, y n , n = 1, 2, ...., n 0 , y n ∈ F (m) where n 0 << m. We suppose y n = y n ′ if n = n ′ . Generally, that occurs always if m is great enough with respect to n 0 . This assumption involves that, for all subsequence y t(n) and for all p, (y t(n) , ...., y t(n+p-1) ) = (y t(n ′ ) , ...., y t(n ′ +p-1) ) if n = n ′ .

One can always regard y n ∈ F (m) as the realization of a sequence of random variables Y n : y n = Y n (ω) such that Y n has a a differentiable density with respect to µ m ⊗ .... ⊗ µ m . One assume also that this density have a Lipschitz coefficient K 0 which is not too large.

It is a logical assumption. In fact it is an assumption which most mathematicians admit when N << m : that is especially clear when they estimate the densities.

We have studied numerous examples which corroborate this hypothesis : cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. Now, in the case where densities are continuous, the conditional densities are also continuous. Then, the conditional probabilities P {Y n |y n+j2 = y 2 , ..., Y n+jp = y p } has a continuous density f y2,...,yp with a coefficient Lipschitz K cp 0 which is not too great. Then, by the same technique as for property 6.3.5, one obtains

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p } = L(I) 1 + O(1)K cp 0 N (I) ,
where h 0 is chosen big enough : N (I) ≥ h 0 .

Another group of models

In order to prove the previous equation, we used K 0 . But it is enough to read the proofs of property 6.3.5 in order to understand that it would be possible to use the coefficients of Lipschitz K r associated with each interval [r/N (I), (r + 1)/N (I)[ to obtain the same type of results.

In this case, it would be enough that r K r is not too large. It is felt well intuitively that this kind of conditions is satisfied by our models.

Admittedly, it is easier to understand for the classical densities of (Y 1 , ....., Y N ). But what interests us, are the conditional probabilities. Then to understand that the property " r K r not too large" is checked for the conditional densities, simplest way is to remember that the conditional density f y2,,yp (y 1 ) is equal to the product of the marginal densities f 2 (y 2 , y 3 , ., y p ) and of the density of dependence (cf [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF] or proposition 14.3.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] ) : f y2,...,yp (y 1 ) = f dep (y 1 ; y 2 , y 3 , ...., y p )f 2 (y 2 , y 3 , ...., y p ) .

Then, one confirms this assumption with simulations by using this equality.

Therefore, this kind of conditions on r K r seems checked by our models. That makes our end result even surer.

General case

The use of the previous models is interesting because that y n behaves well like a sample of one of these possible models Y n . We thus do not make any error while putting to us under these assumptions. Our calculations are thus right. That implies that the bits b 4 (n ′ ) obtained by our construction in section 10.1.4 behave well like IID sequences.

But it is probable that there do not need even to suppose to be under the assumptions of these models: it is probable that, for any logical model, one will still obtain

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p } ≈ L(I) .

A very strong result

Indeed, we understood that if one provides the set of possible probabilities with the measure defined in section 6.3, our results are checked for almost all the possible probabilities.

There is thus a slight restriction which is normal: in the set of ALL the models, there will be an infinity of them which will not be appropriate. However, it is already extraordinary that the result is true for almost all the possible models.

In order to understand it, let us take for example a sample really IID y n . One wants to associate with y n a model Y n . Clearly, among all the possible models, there is an infinity of good models and an infinity of bad ones. One can even think that there is much more bad models than goods.

In section 6.3, it is the opposite: in the set of all the possible models, almost all will be good. It is a very strong result.

A result checked by all the logical models

As a matter of fact, one can remove the bad models : one can admit that

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , .
.., Y n+jp = y p } ≈ L(I) will be checked for all the logical possible models.

Indeed, there is no connection between the T -1 (mI k ) and texts. Therefore, if a model was bad, that would mean that there is a logical connection between the T -1 q (I k ) and text. One can thus a priori exclude a such model.

Thus our result holds with all the possible logical models, those where there is no connection between text and the T -1 q (I).

Now, it is obtained that P Y 1 ∈ T -1 q (I) ≈ (c ′ -c) m 1 + Ob(1).b √ 3N (I)
for all the logical models. Then the question is put: which value to choose for b?

In order to know that, it is necessary to go back to the themself texts : i.e. it is necessary to study the associated empirical probabilities.

We thus estimated b for various texts and for various T -1 q (I). If p=1, all the numerical studies that we have made show that, for intervals I of the same length, the sets T -1 q (I) contains about the same number of possible texts : cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] section 13.1.2.

Finally, it is found that one can admit -and by far -in all the cases

P Y 1 ∈ T -1 q (I) = (c ′ -c) m 1 +
Ob(1).20

3N (I)

. (6.4) This increase (b=20) is not astonishing. Indeed, according to proposition 6.3.2, it occurs with a probability larger than 1 -2pΓ ′ 1 (b). Now, if b=20, Γ ′ 1 (b) ≈ 1.12/10 88 . Then, a priori, in order to find a case where that is not true, it would be necessary to use a such large number of texts that it is impossible to realize.

In any case it is even not sure that one can find cases where this equality is not checked empirically. Indeed, one does not use texts representing samples which have a fixed law. What one uses, it is, on the one hand, sequences which have the logic of the English language, and on the other hand, sets which have simple mathematical properties. Anyway, we never have encounter such a case. It is thus possible logically that it has no text not checking the equation 6.4.

If p=2, sets T -1

q (I 1 ) and T -1 q (I 2 ) behave like randomly selected compared to the text.

If p > 2, we have obtained results equivalent for p ≤ log(n0) log( 2) :

P Y 1 ∈ T -1 q (I 1 ) ∩.....∩ Y p ∈ T -1 q (I p ) ≈ s (c ′ s -c s ) m p 1+ Ob(1).20.p 3.Inf {N (I s )} .
Anyway a such value of b is not important because the equation

P {X n ∈ I | X n+j2 = x 2 , ..., X n+jp = x p } = L(I)[1 + Ob(1)ǫ]
is too strong. Indeed it is enough that

P {X n ∈ I | X n+j2 = x 2 , ..., X n+jp = x p } = L(I) + Ob(1)ǫ
where ǫ = α √ N when N is the size of sample and 0 < α ≤ 0.02. Indeed, in this case one cannot differentiate X n with an IID sequence : cf section 2.1.4 or example in section 11.2.3.

Then, the equation

P {X n ∈ I | X n+j2 = x 2 , ..., X n+jp = x p } = L(I)[1 + Ob(1)ǫ]
is too strong. Therefore a very strong connection between text and the sets T -1 (I k ) would be necessary in order not to obtain this kind of equation. It is not therefore advisable to worry about the value of b.

Conditional probabilities

The fact that there is no connection between text and the sets T -1 q (k/d q ) = {a 1 , ...., a c ′ -c } applies to the conditional probabilities. Indeed, there is always no logical connection between text and the sets T -1 q (I) = {a 1 , ...., a c ′ -c } in the conditional probabilities:

P {X n ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p } = P Y n ∈ T -1 q (I) ∩ {Y n+j2 = y 2 } ∩ .... ∩ {Y n+jp = y p } P ∩ {Y n+j2 = y 2 } ∩ .... ∩ {Y n+jp = y p } .
Therefore, the conditional probabilities behave well as sums on sets taken randomly, i.e.

P {T q (Y n ) ∈ I | Y n+j2 = y 2 , ..., Y n+jp = y p } = s P {Y n = a s | Y n+j2 = y 2 , ..., Y n+jp = y p } ≈ L(I) .
From this type of results we have deduced CLT with minimal assumptions whose the conditions are close to strong mixing assumptions.

In this aim, one decomposes X 1 + X 2 + ......... + X n in X 1 + X 2 + ......... + X u , X u+1 + X u+2 + ......... + X u+t and X u+t+1 + X u+t+2 + ......... + X u+t+u where u=u(n) and t=t(n).

Notations 7.1.1 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. Notations 7.1.2 Let σ(u) 2 = E{(X 1 + X 2 + ......... + X u ) 2 } . One sets S u = X 1 + X 2 + ......... + X u σ(u) , ξ u = X u+1 + X u+2 + ......... + X u+t σ(u) and S ′ u = X u+t+1 + X u+t+2 + ......... + X u+t+u σ(u) .
Then, one can define almost minimal assumptions for the convergence of moments.

Notations 7.1.3 : 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 (k) : ∀(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 → ∞.
Equivalent conditions can be defined for the convergence in distribution. Notations 7.1.4 : 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 → ∞, where A k,j = S u ∈ I k,j and B k,j = S ′ u ∈ I k,j with I k,j = j.4 -k , (j + 1)4 -k .
Then the following CLT holds : 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].

Theorem 4

We assume that H mS (∞) and H mI (∞) hold. We assume also that, for all p ∈ N * , E{(ξ u ) p } → 0 as n → ∞. Then, S n D → N (0, 1) .

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) .
It is this CLT that we use with our datas (cf chapter 9).

XOR Limit Theorem

Our secund limit theorem is based on the property of XOR. But it holds also modulo m. Then, by misusing of language, we call this this result "XOR Limit Theorem" (XORLT). The XORLT is much more general than the CLT. Then, one can use with many type of datas, in particular with the most part of electronic files.

Presentation

The XORLT relates to sums α

(n)(X 1 + X 2 + .... + X n )/σ(n), in particular X 1 + X 2 + .... + X n (in this section, h ≡ h modulo 1). Definition 7.2.1 Let (X 1 n , X 2 n , .....X p n ) ∈ R p be a sequence of random vectors. For s=1,...,p, let σ s (n) 2 = E{(X s 1 + .... + X s n ) 2 }.
Then, we set

S s n = X s 1 + .... + X s n σ s (n) .
The XOR limit theorem holds for (X

1 n , X 2 n , .....X p n ) if there exists p sequences α s (n) → ∞ as n → ∞ , such that (α 1 (n)S 1 n , ....., α p (n)S p n ) has asymptotically the uniform distribution on [0, 1[ p .
As a matter of fact, we have always obtained that X 1 + X 2 + .... + X n has asymptotically the uniform distribution on [0, 1[. In order to understand that, we recall the following theorem (cf theorem 4 [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]).

Theorem 6 Let X and Y be two independent random vectors, X, Y ∈ F * (m) p . Assume that X has the uniform distribution. Then, X + Y ∈ F * (m) p has also the uniform distribution.

For example assume that X 1 ∈ [0, 1[ has the uniform distribution and that X 1 is independent of (X 2 , ...., X n ). Then X 1 + X 2 + .... + X n has the uniform distribution on [0,1[. This result is general : if the CLT is satisfied, then the XORLT is satisfied.

Proposition 7.2.1 : Let X n be a sequence of random variables such that

E{X n } = 0 and S n = X1+....+Xn σ(n) D → S with E{S 2 } = 1.
Assume that S has a probability density function f with respect to the Lebesgue measure such that

|f (x) -f (x ′ )| ≤ K 0 |x -x ′ |.
Then, there exists a sequence α(n) → ∞ as n → ∞ such that, for all

0 ≤ t ≤ 1, P α(n)S n ∈ [0, t[ → t as n → ∞ .
The proof is in proposition 5.2.3 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. Remark that analog results hold also for random vectors (S n 1 , S n 2 , ....,

S n p ) ∈ R p . In general, α(n)σ(n) = 1, i.e. (X 1 + ....X n ) has asymptotically the uniform distribution on [0, 1[ . Indeed let µ ′ n ( k mσ(n) ) = µ ′ n ([0, 1]
) → 1 as n → ∞. Now the following XORLT holds (cf proposition 5.2.4 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). Proposition 7.2.2 Let (S n 1 , S n 2 , ...., S n p ) ∈ R p be a random vector such that E{(S s n ) 2 } = 1 for s=1,2,...,p. Let µ A be a measure on R : one assumes that µ A = µ 1 ⊗....⊗µ p where µ s = µ the Lebesgue measure for s=1,...,p or where µ s = µ ′ n for s=1,..,p. Assume that (S n 1 , S n 2 , ...., S n p ) has a probability density function

f n with respect to µ A such that |f n (x 1 , ..., x p ) -f n (x ′ 1 , .., x ′ p )| ≤ K 0 max(|x s -x ′ s |). Let α(n) be a sequence such that α(n) → ∞ as n → ∞. Then α(n)(S n
1 , S n 2 , ...., S n p ) has asymptotically the uniform distribution over [0, 1[ p .

Now, the condition " ∃K

0 : |f n (x) -f n (x ′ )| ≤ K 0 |x -x ′ | ∀ n ∈ N * "
is not a necessary condition of the CLT. Then, in some cases, the hypotheses of proposition 7.2.2 seem stronger than those of the CLT. But the reciprocal assertion is true too : e.g. the XORLT holds if X s = X 1 for all s :

X 1 + .... + X n = nX 1 .
Moreover, proposition 7.2.2 suggests that if the CLT holds, then, X 1 + .... + X n has asymptotically the uniform distribution. Anyway, under the assumptions of datas studied in this report, we have never found a single case where it is not verified.

Examples

In this section, we compare limit distributions. In these examples we shall note the strength of the XORLT.

Let

S 2 n ∈ R 2 such that S 2 n D → S 2 0 where S 2 0 ∼ N 2 (0, C) when C is a covariance matrix. One knows that g(S 2 n ) D → g(S 2
0 ) if g is continuous with P S 2 0 probability 1 (cf [START_REF] Serfling | Approximation theorems of mathematical statistics[END_REF] page 24). Then, S 2 n D → S 2 0 . Moreover, we shall note that the dependence of S 2 0 does not exist any more for S 2 0 . We shall deduce the XORLT for σ(n)S 2 n .

Example 7.3.1 Let X and Y be two independent random variable with distribution N(0,1). Let Z = X+aY √ 1+a 2 where a ∈ R.

Test of the linear correlation coefficient Under the previous hypotheses, Z has the N(0,1) distribution. Moreover the linear correlation coefficient of X and Z is ρ = (1 + a 2 ) -1/2 . For example, ρ = 0.701 si a=1. let ρ n be the empirical linear correlation coefficient associated to a sample (X s , Z s ). Let ρ U n be the empirical linear correlation coefficient associated to the sample (X s , Z s ).

Then, ρ n et ρ U n allow us to estimate the linear correlation coefficients of (X 0 , Z 0 ) and (X 0 , Z 0 ).

Let N be the size of the sample. The following results have been obtained Assume that the linear correlation coefficient is equal to 0.7071. We use a partition [START_REF] Blacher R | Une nouvelle condition d'independance pour le theoreme de la limite centrale[END_REF][START_REF] Blacher R | Une nouvelle condition d'independance pour le theoreme de la limite centrale[END_REF]. The chi-squared statistics has asymptotically the distribution N(0,1) (cf [START_REF] Knuth | the Art of Computer Programming[END_REF] page 44) :

ρ N ρ n ρ U n ρ n ρ U n 0.
√ 2χ 2 -√ 2d -1 where d is the degree of freedom : (15-1) . With this statistics, we obtained the following numerical results. As a matter of fact (X, Z) is enough close to an independent vector.

Conclusion

Under the previous hypotheses,

(X1 + ...... + X n , Z 1 + ...... + Z n ) → σ(n)(X, Z) .
Now (X, Z) is already close to an independent vector. Then, it will thus be even more true for σ(n)(X, Z) because the multiplication by σ(n) modulo 1 makes uniform the distribution as soon as σ(n) is enough big.

In conclusion, the fact that (X, Z) is already almost independent shows the rate of the convergence of the XORLT.

Example using datas of this paper

In section 5.3.3 of [START_REF] Blacher R | Transformation d'une suite aléatoire q-dépendante[END_REF] we have studied an example using the datas G(j) and H(j) defined in section 11. We note that the estimated density are close to the normal or uniform density.

As a matter of fact, we studied numerically various examples using data of the type "text", "computer programs", "mathematical reports", etc., we always found that X 1 + X 2 + .... + X n has asymptotically the uniform distribution.

We obtained results similar in several dimensions: for the data used in this report, we always found that (X 1,1

+ X 2,1 + .... + X n,1 , X 1,2 + X 2,2 + .... + X n,2 )
has asymptotically the uniform distribution on [0, 1] p for p=2. We obtained similar results for p=3,4,5,6.

Other theoretical study

One can confirm that it is more practical to use the XORLT than the CLT by another theoretical study : one can compare the the conditional densities of the sequences G(j) and H(j) (cf section 11.1.1). Indeed, in corollary 5.6.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] we have proved the following result. Proposition 7.3.1 Let f * g2,g3,.. (g/(mS)) be the conditional density of G i /(mS) = g/(mS) given G i+js = g s and let f * h2,h3,.. {h/m} be the conditional density of

H i /m = h/m given H i+js = h s .
Let K f G/(Sm) and K f H/m be the Lipschitz coefficients associated to f * g2,g3,..

and f * h2,h3,.. . Then, K f H/m ≤ K f G/(Sm) S .

Numerical study

In [START_REF] Blacher R | A Perfect Random Number Generator[END_REF], we have studied several examples of the rate of convergence de X 1 + X 2 + ..... + X n and X 1 + X 2 + ..... + X n when X s ∈ {0, 1, ..., q}. It is true as soon as, n ≥ 7 or if q is large enough q ≥ 20. For example, in figures 7.1 and 7.2, we obtain curves close to those of the normal or uniform distributions for non -independent vectors (X 1 , X 2 , ....., X 8 ). Then, in [START_REF] Blacher R | A Perfect Random Number Generator[END_REF], we notice that the graphs are about the ones of a normal distribution or a uniform distribution except when the probabilities are concentrated near a small number of points : cf figures 7.3 and 7.4.

We have studied numerically the rate of convergence of the XORLT when the CLT is satisfied. Then, we assume Y = X1+....+Xn σ √ n ∼ N (0, 1). Then, Here we study the distribution of X 1 + .... + X n when n=10 with the variances 1/50, 1/200 : cf figure 7.5, 7.6. We understand that we are enough near of the uniform distribution if σ 2 is not too big. For the data used in the construction of b 1 (n ′ ) in section 11.2, we can think that a sum of 10 terms is sufficient so that our hypotheses are satisfied.

X 1 + .... + X n = σ √ nY ∼ N (0, nσ 2 ).

Rate of convergence in the XORLT

In this section we understand that, in some cases, the convergence to the uniform distribution can be very fast.

Hypotheses

We assume that p" i xn = P " i xn (ω 7 ) where p"

i xn = (1/N )[1 + r i N (v i xn -v i N )
] and where v i xn = V i xn (ω 7 ) is a realization of an IID sequence defined by the following way.

Hypothesis 7.3.1 For all i ∈ {1, 2, ..., S}, we assume that v i xn is a realization of an IID sequence of random variables V i xn defined on a probability space (Ω 7 , A 7 , P roba 7 ) such that -1 ≤ V i xn ≤ N -1, E{V i xn } = 0, and all the V t xn t 's, t=1,..,S, n t = 1, .., N , are independent.

Then, we set

v i N = (1/N ) xs v i xs et V i N = (1/N ) xs V i xs .
Then, the following results holds Lemma 7.3.2 There exists a sequence of random variables

0 < R i N ≤ 1 such that -1 ≤ R i N (V i xn -V i n ) ≤ N -1 and R i N P → 1 as N → ∞. Proof : One can write -1 -e ≤ V i xn -V i N ≤ N -1 + e where e > 0. Then, one can write -1 ≤ R i N (V i xn -V i N ) ≤ N -1 where 0 < R i N ≤ 1. By the CLT, V i N P → 0. Therefore, R i N P → 1.
Then, we can define probabilities. Proposition 7.3.2 For all x n ∈ F * (N ), we set

P " i xn = (1/N )[1 + R i N (V i xn - V i N )]. Then, 0 ≤ P " i xn ≤ 1 and xn P " i xn = 1 Proof : We have xn P " i xn = xn (1/N ) + (R i N /N ) xn (V i xn -V i N )] = 1.
Then, we assume that the following hypothesis holds.

Hypothesis 7.3.2 For all i ∈ {1, 2, ..., S}, we assume that p" i xn is the realization of the sequence of random variables P " i xn defined over (Ω 7 , A 7 , P roba 7 ) by p" i xn = P " i xn (ω 7 ).

Then, we have the rate of convergence of XORLT.

Theorem 7 Assume that, for all s ∈ {1, 2, ..., S}, the variance of V s 1 is σ 2 Vs . Then, with a probability greater than 1 -Γ(b) approximately,

P {X 1 + ... + X S = y} = 1 N 1 + b.Ob(1)σ V1 ....σ V S √ N S-1 . Remark 7.3.3 If P i
x has a distribution similar to that of P i x = P ′i

x P N t=1 P ′i t when P ′i x has the uniform distribution, then σ 2 Vr = O(1). For example, one can choose σ 2

Vr ≤ 1.

Proof of theorem 7

At first, the following proposition holds.

Lemma 7.3.4

The following equality holds :

P {X 1 + ... + X S = y} = 1 N + r 1 N .....r S N N S x1+...+x S =y (v 1 x1 -v 1 N )........(v S x S -v S N ). Proof At first, P {X 1 + X 2 + .... + X S = y} = x1+...+x S =y p" 1 x1 ......p" S x S = (1/N S ) x1+...+x S =y [1 + r 1 N (v 1 x1 -v 1 N )].......[1 + r S N (v S x1 -v S N )]. Now, [1 + r 1 N (v 1 x1 -v 1 N )].......[1 + r S N (v S x S -v S N )] = 1 + r 1 N (v 1 x1 -v 1 N ) + ..... + r S N (v S xn -v S N ) +..
+ i1<i2<....<iq r i1 N (v i1 xi 1 -v i1 N )r i2 N (v i2 xi 2 -v i2 N )........r iq N (v iq xi q -v iq
N (v 1 x1 -v 1 N )r 2 N (v 2 x2 -v 2 N ).........................r S N (v S x S -v S N ).
We deduce the proposition by using the following lemma (7.3.5).

Lemma 7.3.5 Suppose q < S. Then,

x1+....+x S =y i1<i2<....<iq r i1 N (v i1 xi 1 -v i1 N )........r iq N (v iq xi q -v iq N ) = 0. Proof We have x1+....+x S =y i1<i2<....<iq r i1 N (v i1 xi 1 -v i1 N )........r iq N (v iq xi q -v iq N ) = 0 = i1<i2<....<iq x1+....+x S =y r i1 N (v i1 xi 1 -v i1 N )........r iq N (v iq xi q -v iq N ) .
For example, if i q < S,

x1+....+x S =y (v i1 xi 1 -v i1 N )........(v iq xi q -v iq N ) = xi 1 xi 2 .... xi S-1 x S =y-x1+....-x S-1 (v i1 xi 1 -v i1 N )........(v iq xi q -v iq N ) = xi 1 xi 2 .... xi S-1 (v i1 xi 1 -v i1 N )........(v iq xi q -v iq N ) = xi 1 (v i1 xi 1 -v i1 N ) ...... xi q (v iq xi q -v iq N ) = 0 because xi 1 v i1 xi 1 = N v i1 N .
Proposition 7.3.3 Under the hypothesis 7.3.1,

P x i 1 +....+x i S =y V 1 x i 1 V 2 x i 2 ....V S x i S N (S-1)/2
has asymptotically a distribution N (0, σ 2 V1 ......σ 2 V S ).

Proof We apply theorem 3 with

X ts = V 1 i1 ....V S-1 i S-1 V S y-i1-.....-i S-1
and

n = N S-1 .
The first relation of theorem 3 is obvious. For example, if S=3, this relation is equivalent to the convergence of (1/N 4 ) r =s E{(X s ) 2 (X r ) 2 }-E{(X s ) 2 }E{(X r ) 2 } , which is equivalent to the convergence of

P (i,j) =(i ′ ,j ′ ) E{(V 1 i V 2 j V 3 y-i-j ) 2 (V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ ) 2 }-E{(V 1 i V 2 j V 3 y-i-j ) 2 }E{(V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ ) 2 } N 4 . Now, in order that E{(V 1 i V 2 j V 3 y-i-j ) 2 (V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ ) 2 } = E{(V 1 i V 2 j V 3 y-i-j ) 2 } E{(V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ ) 2 }, it is necessary that i = i ′ or j = j ′ . Therefore, at the maximum, there is 2N 3 such V 1 i V 2 j V 3 y-i-j V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ . Then, there exists a constant C 2 3 such that 2C 2 3
N is greater than

P (i,j) =(i ′ ,j ′ ) E{(V 1 i V 2 j V 3 y-i-j ) 2 (V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ ) 2 }-E{(V 1 i V 2 j V 3 y-i-j ) 2 }E{(V 1 i ′ V 2 j ′ V 3 y-i ′ -j ′ ) 2 } N 4
. Now we study the condition p!

P t 1 <t 2 <.....<tp E{Xt 1 Xt 2 ......Xt p } (N S-1 ) p/2 → (N 2 ) p µ p .
First, assume S=2 : in this case,

X t1 = V 1 x 1 n V 2 y-x 1 n . Then, E{X t1 .....X tp } = E{V 1 x 1 n 1 V 2 y-x 1 n 1 .....V 1 x 1 np V 2 y-x 1 np } = E{V 1 x 1 n 1 }..........E{V 1 x 1 np }E{V 2 y-x 1 n 1 .....V 2 y-x 1 np } = 0 because the x 1 n are all dissimilar.
Assume S=3 : in this case,

X t1 = V 1 x 1 n 1 V 2 x 2 n 2 V 3 y-x 1 n 1 -x 2 n 2
. Then, one can write

E{X t1 X t2 ......X tp } = E{V 1 xn 1 .....V 1 xn p }E{V 2 x ′ n 1 .......V 2 x ′ np }E{V 3 y-xn 1 -x ′ n 1 ........V 3 y-xn p -x ′ np } . If p=2, E{X t1 X t2 } = E{V 1 xn 1 V 1 xn 2 }E{V 2 x ′ n 1 V 2 x ′ n 2 }E{V 3 y-xn 1 -x ′ n 1 V 3 y-xn p -x ′ np }. Be- cause t 1 < t 2 , x n1 = x n2 or x ′ n1 = x ′ n2 . Then, E{X t1 X t2 } = 0. If p=3, we have the same conclusion. If p=4, E{X t1 X t2 X t3 X t4 } = E{V 1 xn 1 V 1 xn 2 V 1 xn 3 V 1 xn 4 }E{V 2 x ′ n 1 V 2 x ′ n 2 V 2 x ′ n 3 V 2 x ′ n 4 } E{V 3 y-xn 1 -x ′ n 1 V 3 y-xn 2 -x ′ n 2 V 3 y-xn 3 -x ′ n 3 V 3 y-xn 4 -x ′ n 4
} .

In order that E{X t1 X t2 X t3 X t4 } = 0, it is necessary that, for example,

x n1 = x n2 , x n3 = x n4 , x ′ n1 = x ′ n3 and x ′ n2 = x ′ n4 .
Then, we assume that these relations hold.

Then, in order that

E{V 1 xn 1 V 1 xn 2 V 1 xn 3 V 1 xn 4 }E{V 2 x ′ n 1 V 2 x ′ n 2 V 2 x ′ n 3 V 2 x ′ n 4 } E{V 3 y-xn 1 -x ′ n 1 V 3 y-xn 2 -x ′ n 2 V 3 y-xn 3 -x ′ n 3 V 3 y-xn 4 -x ′ n 4 } = 0 , it is necessary that OR y -x n1 -x ′ n1 = y -x n2 -x ′ n2 and y -x n3 -x ′ n3 = y -x n4 -x ′ n4 . Therefore, x ′ n1 = x ′ n2 . Then, X t1 = V 1 xn 1 V 2 x ′ n 1 V 3 y-xn 1 -x ′ n 1 = V 1 xn 2 V 2 x ′ n 2 V 3 y-xn 2 -x ′ n 2 = X t2 : it is impossible. OR y -x n1 -x ′ n1 = y -x n3 -x ′ n3 and y -x n2 -x ′ n2 = y -x n4 -x ′ n4 . Then, x n1 = x n3 : it is impossible. OR y -x n1 -x ′ n1 = y -x n4 -x ′ n4 and y -x n2 -x ′ n2 = y -x n3 -x ′ n3 . Then, x n1 +x ′ n1 ≡ x n3 +x ′ n2 and x n1 +x ′ n2 ≡ x n3 +x ′ n1 . Therefore, 2(x ′ n1 -x ′ n2 ) ≡ 0 and 2(x n1 -x n3 ) ≡ 0. If N is odd, it is impossible. If N is even, x ′ n1 -x ′ n2 = δ 1 (N/2) and x n1 -x n3 = δ 2 (N/2)
where δ s = 0, -1 or 1. Therefore, there are

C ′ 0 N 4 N 2 possible variables X t1 = V 1 xn 1 V 2 x ′ n 1 V 3 y-xn 1 -x ′ n 1 , X t2 = V 1 xn 2 V 2 x ′ n 2 V 3 y-xn 2 -x ′ n 2 , X t3 = V 1 xn 3 V 2 x ′ n 3 V 3 y-xn 3 -x ′ n 3 , X t4 = V 1 xn 4 V 2 x ′ n 4 V 3 y-xn 4 -x ′ n 4 such that E{X t1 X t2 X t3 X t4 } = 0. Therefore, t1<t2<t3<t4 E{X t1 X t2 X t3 X t4 } (N 2 ) 2 < C ′ 0 N 2 N 4 → 0 .
One prove the general case by the same way.

Then all conditions of theorem 3 hold. Then,

P n 0 i=1 Xn √ N D → N (0, σ 2 V1 ....σ 2 V S ) be- cause E X 2 tr = E V 1 x 1 nr V 2 x 2 nr ...V S-1 x S-1 nr V S y-x 1 nr -...-x S-1 nr 2 = S r=1 E (V r 1 ) 2 .
Now, one can assume that x s n v s

x s n = 0. Lemma 7.3.6 Assume that the assumptions of proposition 7.3.3 hold. Then,

1 √ N S-1 x 1 n ,x 2 n ,.....,x S-1 n S-1 t=1 R t N (V t x t n -V t N ) R S N (V S y-x 1 n -....-x S-1 n -V S N )
has asymptotically the distribution N (0, σ 2 V1 ....σ 2 V S ).

Proof Assume S=2. Then,

1 √ N x 1 n R 1 N (V 1 x 1 n -V 1 N )R 2 N (V 2 y-x 1 n -V 2 N ) = R 1 N R 2 N √ N x 1 n V 1 x 1 n [V 2 y-x 1 n -V 2 N ] - R 1 N R 2 N V 1 N √ N x 2 n [V 2 x 2 n -V 2 N ] = R 1 N R 2 N √ N x 1 n V 1 x 1 n [V 2 y-x 1 n -V 2 N ] = R 1 N R 2 N √ N x 1 n V 1 x 1 n V 2 y-x 1 n - R 1 N R 2 N √ N V 2 N x 1 n V 1 x 1 n ,
where

R 1 N R 2 N √ N x 1 n V 1 x 1 n V 2 y-x 1 n and 1 √ N x 1 n V 1 x 1 n have asymptotically a normal dis- tribution (cf proposition 7.3.3). Moreover, V 2 N converges in probability to 0. Then, 1 √ N x 1 n R 1 N (V 1 x 1 n -V 1 N )R 2 N (V 2 y-x 1 n -V 2 N ) has asymptotically the dis- tribution N (0, σ 2 V1 σ 2 V2 ).
In the general case, we prove this proposition by the same way .

Proof 7.3.7 Now we prove theorem 7

R 1 N .....R S N x1+...+x S =y (V 1 x1 -V 1 N )........(V S x S -V S N ) √ N S-1
has asymptotically the distribution N (0, σ 2 V1 ......σ 2 V S ). We deduce (cf proposition 7.3.4) that, with a probability greater than 1 -Γ(b) approximately,

r i1 N .....r i S N x1+...+x S =y (v 1 x1 -v 1 N )........(v S x S -v S N ) N S = b.Ob(1)σ V1 ......σ V S √ N S+1 .

Problem in some cases

Theorem 7 is only a mathematical theorem with a measure on the set of the probabilities chosen a priori. This measure is not thus inevitably adapted to certain assumptions. It is not difficult to understand that theorem 7 has absurd consequences in the case of continuous density : cf pages 118-121 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

To avoid this problem, one can transform the random variables : for example one can multiply each X t by a suitably chosen number α t modulo 1: X ′ t = α t X t . For example, one can transform some lines by various Fibonacci congruences or various Fibonacci functions T q : cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] pages 118-121.

As a matter of fact, the multiplication by α t modulo 1 defines a permutation if α t is suitably selected. But in this case, one has again the problem of the choice of the permutations: the permutations too simple are not appropriate. Is this case here? This problem is not so simple. On the one hand, Knuth ([1]) explains why one cannot use permutations built by algorithm (cf also section 2.1.1). On the other hand, one understands in chapter 6 that the multiplication corresponding to a Fibonacci congruence is a good permutation. Now a simpler solution is to use transformation which have the same characteristic as a permutation really random. It is what we do in section 12.

Limit theorems for conditional probabilities

Here, we study G(j) = S i=1 F (i, j) where the rows F (i,.) are independent : cf section 11. In that case, the distribution of the sums admitting for probabilities the conditional probabilities is that one of a sum of independent variables. Proposition 7.3.4 Let X i,j , i=1,...,I, j=1,...,p, be a sequence of random variables. We assume that the rows X i,. ∈ F (m) p are independent. Then, In this section, we use the following notations (cf also property 6.3.3 ).

Notations 8.1.1 Let X 0 n ∈ F (m), n ∈ N * be a sequence of random variables defined on a probability space (Ω, A, P ).

Let j s , s=1,2,...,p, j s ∈ Z, be an injective sequence such that j 1 = 0. Let d 0 = min(j s |s = 1, 2, .., p) . Then, we set X n = X 0 n+d0 . Notations 8.1.2 Let Bo = Bo 1 ⊗ Bo 2 ⊗ .... ⊗ Bo p ⊂ F (m) p be a Borel set where L(Bo s ) ≤ 1/2 for s=1,...,p. We set L n = E 1 Bo (X n ) and L N (Bo) = (1/N ) N n=1 L n where 1 Bo (X n ) = 1 Bo1 (X n+j1 )1 Bo2 (X n+j2 )....1 Bop (X n+jp ). Hypothesis 8.1.1 One supposes that, for all p ∈ N * , for all Borel set Bo ⊂ F (m) p , for all injective sequence j s , for all n ∈ N * ,

E 1 Bo (X n ) = L(Bo) + Ob(1)L(Bo)ǫ p Bo ,
where

ǫ p Bo = 2 [Log(n0)+q]p 3 2 q m = e0p 3 2 q m << 1. Notations 8.1.3 We set σ 2 1 = (1/N )E N n=1 1 Bo (X n )-L n 2 . Moreover, if X n is IID, we write σ 2 B instead of σ 2 1 . For example, if p=1, σ 2 B = L(Bo)[1 -L(Bo)].
Now, we can expound the first empirical theorem. Let P e = 1 N N n=1 1 Bo (X n ). Then, the following inequality holds

P √ N P e -L(Bo) ≥ σ B x ≤ K 1 1 -β 1,p /x 1 + γ ′ 1,p x ,
where

K 1 (x) = P √ N |Pe-L N (Bo)| σ1 ≥ x .
Remark that if P e is asymptotically normal,

√ N [Pe-L N (Bo)] σ1
has asymptotically the distribution N(0,1). Now, one can also obtain similar results to theorem 8 if one replaces hypothesis 8.1.1 by the following way. Hypothesis 8.1.2 Let ǫ > 0. One supposes that, for all Borel set Bo ⊂ F (m), for all p ∈ N * , for all sequence j s , for all x 2 , ....., x p , for all n ∈ N * , such that n > d 0 , P X 0 n ∈ Bo X 0 n+j2 = x 2 , ....., X n+jp = x p = L(Bo) + Ob(1)ǫ . Then, one obtains results similar to theorem 8. These results can be specified when X n is asymptotically independent. In this case, one uses increases of

d M ax n∈N * E 1 Bo (X n ) -L n 1 Bo (X n+d ) -L n+d
: cf chapter 8 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. For example, if X n is q-dependent the following theorem holds.

Theorem 9

We suppose that X n is q-dependent. We set ǫ p = (1/2+ǫ) p -(1/2) p and

γ 1,p = 1 2A(p)L(Bo) (p 2 -p + 1) ǫ p + 2qǫ 2p + (1 + 2q) 2 1-p ǫ p + ǫ 2 p . T hen, P √ N P e -L(Bo) ≥ σ B x ≤ K 1 1 -β 1,p /x 1 + γ 1,p x ,
On the other hand, results similar can be obtained for empirical conditional probabilities : cf theorems 8 and 10 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

Theorem 10 We suppose that X n is q-dependent. We assume that the hypothesis 8.1.2 holds and that the assumptions of theorem 8 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] holds.

We set

p e = (1/N ) N n=1 1 Bo2 (X n+j2 )....1 Bop (X n+jp ). Then, if N is great enough, there exists K 2 ≈ Γ such that P √ N P e p e -L(Bo 1 ) > σ cp x ≤ K 2 1 -β 2,p /x 1 + γ 2,p x
where β 2,p ≈ 0 and γ 2,p ≈ 0 if ǫ is small enough and where σ 2 cp = N.E

Proof One can write 4 , where X ′ n is an IID sequence and where ǫ 4 = L(Bo)ǫ 2p Bo = L(Bo)2 3/2 ǫ p Bo .

σ 2 B = (1/N ) N n=1 m∈H(n) E 1 Bo (X ′ n )1 Bo (X ′ m ) -L(Bo) 2 = (1/N ) N n=1 E 1 Bo (X ′ n ) + m∈H * (n) E 1 Bo (X ′ n )1 Bo (X ′ m ) - m∈H(n) L(Bo) 2 ≥ (1/N ) N n=1 E 1 Bo (X ′ n ) -(p 2 -p+1)L(Bo) 2 = L(Bo)
ǫ 3 = L(Bo) 2 e0(2p) 3 2 q m = L(Bo) 2 2 3/2 ǫ p Bo . If m ∈ H(n), E 1 Bo (X n )1 Bo (X m ) = E 1 Bo (X ′ n )1 Bo (X ′ m ) + Ob(1)ǫ
Proof If m / ∈ H(n), by notation 8.1.1,

E 1 Bo (X n )1 Bo (X m ) = L(Bo ⊗ Bo) + L(Bo ⊗ Bo) e 0 (2p) 3 2 q m .
Assume m ∈ H(n). Clearly if n=m or if p=1, equation holds by notation 8.1.1.

Suppose p ≥ 2 and n = m. One can assume n < m. Then, there exists a sequence i s , s=1,...,p', p ′ < 2p, and a sequence of Borel sets Bo ′ s , s=1,...,p', such that L(Bo ′ s ) ≤ 1/2 and

1 Bo (X n )1 Bo (X m ) = 1 Bo1 (X n )1 Bo2 (X n+j2 ).....1 Bop (X n+jp )1 Bo1 (X m )1 Bo2 (X m+j2 ).....1 Bop (X n+jp ) = 1 Bo ′ 1 (X n )1 Bo ′ 2 (X n+i2 ).......1 Bo ′ p ′ (X n+i p ′ ) . (8.1)
Clearly p ≤ p ′ < 2p. Then,

E 1 Bo (X n )1 Bo (X m ) = E 1 Bo (X ′ n )1 Bo (X ′ m ) + L(Bo)θ e 0 (p ′ ) 3 2 q m ,
where 0 ≤ θ ≤ 1. ≈ L(Bo) 2 1 + 2Ob(1) e 0 p 3 2 q m . Lemma 8.1.5 The following equality holds

σ 2 1 = σ 2 B 1 + Ob(1)2γ ′ 1,p .
Proof Let X ′ n be an IID sequence with uniform distribution. Then, Study of some files

σ 2 1 = (1/N )E N n=1 1 Bo (X n ) -L n 2 = (1/N )E N n=1 N m=1 1 Bo (X n ) -L n 1 Bo (X m ) -L m = (1/N )E N n=1 m∈H(n) 1 Bo (X n )1 Bo (X m ) -L n L m +(1/N )E N n=1 m / ∈H(n) 1 Bo (X n )1 Bo (X m ) -L n L m ≈ (1/N )E N n=1 m∈H(n) 1 Bo (X ′ n )1 Bo (X ′ m ) + Ob(1)ǫ 4 -L(Bo) 2 + Ob(1)ǫ 5 +(1/N )E N n=1 m / ∈H(n) L(Bo) 2 + Ob(1)ǫ 3 -L(Bo) 2 + Ob(1)ǫ 5 = σ 2 B + (1/N )E N n=1 m∈H(n) Ob(1)ǫ 4 +(1/N )E N n=1 m / ∈H(n) Ob(1)ǫ 3 + (1/N )E N n=1 m Ob(1)ǫ 5 = σ 2 B + (1/N ) N n=1 m∈H(n) Ob(1)2 3/2 L(Bo)ǫ p Bo +(1/N ) N n=1 m / ∈H(n) Ob(1)2 3/2 L(Bo) 2 ǫ p Bo +(1/N )

Introduction

In this chapter, we study the data resulting from certain electronic files, especially from texts. By a study of these data based on logic, we will understand that one will be able to conclude that they behave like asymptotically independent sequences (and even Qd-dependent sequences).

In this section, we use a sequence y n which one can regard as a realization of a sequence of random variables : y n = Y n (ω) for all n=1,...,N .

We do not impose that the Y n are independent or identically distributed. But it can be useful that the CLT is satisfied.

Existence of satisfactory datas 9.2.1 Definition

At first, we had to know when a sequence y n can be regarded as a realization of a sequence of really random variables : y n = Y n (ω) for all i=1,...,N .

First, any sequences of reals numbers can be regarded as a realization of a sequence of random variable of a certain type (completely deterministic, IID, etc) : this sequence of random variable is the model. But this model is correct with a some probability.

Then, to suppose "y n = Y n (ω)" is a traditional scientific assumption if the y n represents a physical phenomenon. One wants thus to show in an unquestionable way that it is also the case when y n is resulting from certain electronic files As a matter of fact a such sequence is simply a not-determinist sequence : that is to say, a sequence such that it is impossible to predicte fully y n+p , when, one knows y 1 , y 2 , ......, y n .

Practical example

The sequence b 1 (n ′ ) which we have built in section 11.2 has been obtained by using texts. Concretely, one has used, in various languages dictionary, Encyclopaedia, Bible, etc. The dictionaries and the encyclopaedias are very good examples: the definitions which are consecutive in a dictionary generally represent independent facts : for example "decibel" is followed by "decide" in some dictionaries. The numbers which correspond to them are thus extracted from independent random sequences.

Use of text

Now, we show that one can prove by logical reasonings that texts are asymptotically independent. It is an davantage with respect to sequences furnished by machines for example. Indeed, this asymptotical independence is proved.

In the majority of the sequences obtained from texts, it is reasonable to admit asymptotic independence.

1) The writing of a book depend of a very large number of parameters. Normally, the number of parameters whose the content of the book depend will be always larger than the sample size of the example. One thus finds the argumentation introduced in section 9.2.3.

2) When they write a book many authors do not know what they will write exactly one page later. Concretely they would not predicte exactly what words he will use 100 words later. It will be even more difficult for letters. Then the dependence is weaker between more distant lines. That is, there is asymptotical independence.

3) Of course, it is more difficult to predict the letters used for the people who are not the author of the book.

4) Let us take the example of a novel. In fact if the beginning of a novel is known, there is a very great number of possible alternatives for the continuation of the history. Even for each alternative, there is a very great number of possible texts.

5) Not only, it quasi-impossible to predict about a text. But it is even more difficult to envisage the letters used.

6) To predict logically what is written in a book, it should initially be known that it is written in a certain language. It is not sure that one can arrive at this conclusion. Thus, one is unable to even currently decipher some languages. Could one have deciphered the Egyptian hieroglyphs if the Rosetta Stone had not been written in several languages?

In addition, it has to be known that this text is written with an alphabet of 26 letters for example. If the same book is written in Chinese, one has an alphabet much more important. If this book were written in a rational written form, but not yet invented by men, it would be still other matter. Then, it is not at all certain that, even with means of infinite calculations, it is possible to know that the sequences of numbers obtained has a meaning as a text of English language.

Then, in most of texts it is very clear that it is many more difficult to predict what words will used 200 words later than 100 words later. That is, there is asymptotical independence (for dictionary or encyclopaedia, there is Qd-dependence).

All these facts mean that logic implies that the files obtained starting from texts are asymptotically independent. One thus obtains a result concerning the first step of our method of construction of the random bits b 1 (n ′ ). That is logically surer than if one uses random sequences supposed being provided by machines always subjected to possible dysfunctions: if certain electronic files are used, there are certain assumptions which can be admitted because of logical reasoning.

Remark 9.3.1 Of course, we have tested theses conclusions. All tested texts conclude to asymptotical independence (and even Qd-dependence).

Other data

One can use other datas in order to obtain the sequences of random numbers : softwares, mathematical texts, musics , etc. Then, it is necessary to study by logical reasonning each type of files in order to the obtained sequences are fully proven random.

Moreover, an important thing is that in conclusion, the XORLT holds. However probably that arrives in much case since it does not require asymptotic independence.

Moreover, the number obtained in chapter 11 satisfies all these tests of randomness.

One can use several files, for example, a dictionary and a software. Those are often completely independent from each other. The sequences of numbers which they provide are thus also independent.

Conclusion

1) For this type of files, one can assume that y n is a realization of a sequence of random variable Y n : y n = Y n (ω) where ω ∈ Ω and Y n ∈ {0, 1 κ , 2 κ , ....., κ-1 κ } where κ = 32 . Moreover, there is asymptotical independence, and the CLT holds : often there is Qd-dependence. 2) By using certain files as sources of noises, there are assumptions much surer than if machines are used.

Notations of data

It is supposed that one has a sequence of data a(j) translated in number: a(j), j = 1, 2, ...., N 3 , a(j) ∈ {0, 1, ..., Ka-1}. One supposes that Ka is small enough. If it is not the case, one can break up the a(j)'s in order to have Ka small enough.

It is supposed that a(j) can be regarded as a sample of a sequence of random variables A(j) defined over a probability space (Ω, ∆, P ) : a(j) = A(j)(ω) where ω ∈ Ω.

Description of the method

Shortening of the a(j)'s Let κ ∈ N * . We set c(j) = a(j) mod κ. Comment One chooses κ in order to obtain a sequence c(j) such as, for all t ∈ {0, 1, ., κ -1}, P ′ e {C(j) = t} > 0 where P ′ e is the empirical probability associated with c(1), c(2), ...., c(N 3 ) .

Choice of the parameters

At first, we need the following notation.

Then, because,

2 √ [Log(n0)+q1](n0) 3 2 q 1 L(Bo) √ m
= ǫ 2 << 1, for all the models E 3 (j) except for for a very negilgible probability, P E 3 (j + j 1 ), ...., E 3 (j + j p ) ∈ Bo -L(Bo) ≤ ǫ 2 L(Bo) .

As a matter of fact, by property 6.3.3, one can even admit that if the parameters q 1 and r 1 are well chosen,

P E 3 (j + j 1 ), ...., E 3 (j + j p ) ∈ Bo -L(Bo) ≤ 2 √ ǫ 3 L(Bo) ,
for all the logical models E 3 (j) where, for example, one can impose

ǫ 3 = [Log(n0)+q1](n0) 3 2 q 1 m ≤ 1/10000 : cf section 6.4 (2 √ ǫ 3 = ǫ 2 ).

Use of theorem 8

In this case, p ≤ p m = ⌊Log(n 0 )/Log(2)⌋ is supposed : if not, it doesn't make sens. Now, by lemma 8.1.2, σ 2 B ≥ A(p)L(Bo). Then, in theorem 8,

β 1,p = √ n 0 [L N (Bo) -L(Bo)] σ B = √ n 0 Ob(1)L(Bo)ǫ p Bo A(p)L(Bo) = √ n 0 Ob(1) 2 √ [Log(n0)+q1](pm) 3 2 q 1 √ m 1 -(p 2 -p + 1)2 -p ≤ 2 √ [Log(n0)+q1]n0(pm) 3 2 q 1 √ m 1 -(p 2 -p + 1)2 -p ≤ 2 [Log(n 0 ) + q 1 ]/n 0 1 -(p 2 -p + 1)2 -p ǫ 1 . Moreover, γ ′ 1,p = n0ǫ pm Bo 2A(p) 2 3/2 + 2L(Bo) where ǫ pm Bo = e0(pm) 3 2 q 1 m . Then γ ′ 1,p ≤ 1 2 1 -(p 2 -p + 1)2 -p e 0 (n 0 ) 2 (p m ) 3 2 q1 m 2 3/2 + 2L(Bo) = √ e 0 2 3/2 + 2L(Bo) 2 1 -(p 2 -p + 1)2 -p ǫ 1 .
Then,

P √ N P e -L(Bo) ≥ σ B x ≤ K 1 1 -β 1,p /x 1 + γ ′ 1,p x ≈ K 1 θx , Then, γ ′ 1,pm ≤ √ e0 2 3/2 +2L(Bo) 2 1-(p 2 -p+1)2 -p ǫ 1 = 2 √ 44.5 2 3/2 +2L(Bo) 2 1-(p 2 -p+1)2 -p
0.68 10 3 ≈ 6.68 2 3/2 + 2L(Bo) 0.68 10 3 ≈ 12.845 10 3 ≈ 0.012.

2) We have

β 1,pm ≤ 2 √ [Log(n 0 )+q 1 ]n 0 (pm ) 3 2 q √ m 1-(p 2 -p+1)2 -p ≈ 2ǫ 1 √ [Log(n0)+q1]/n0 1 ≈ 1.36 10 3 44.6 10 5 = 0.000029. Then, if x ≥ 1, K 1 1-β1,p/x 1+γ ′ 1,p x ≈ Γ θx ≈ Γ 1-0.000029 1+0.011 x = Γ 0.98x = 0.3271 if x=1.
Because in the IID case, Γ(x) = 0.3173, it is no possible to differentiate the sequence E 3 (j) or B 4 (n ′ ) from an IID sequence.

Remark 10.1.2 It is not obliged that β 1,p and γ ′ 1,p are very small : cf example 11.2. One can thus moderate these conditions. What is sure, it is that under these assumptions, nothing can distinguish E 3 (j) or B 4 (n ′ ) from an IID sequence : cf section 2.1.4 .

3) We have (n0) 3 2 q 1 m = 10 15 10 10 Then, for all n, for all p, for all sequence j s , P E 3 (j + j 1 ), ...., E 3 (j + j p ) ∈ Bo -L(Bo) ≤ 0.0422.L(Bo) ,

P B ′ n+j1 , ...., B ′ n+jp = (b 1 , ...., b p ) - 1 2 p ≤ 0.0422 1 2 p .
Then, E 3 (j) or B 4 (n ′ ) are very close to IID sequences.

Use of theorem 10

If one uses the other empirical theorems one obtains equivalents results. For example, one can assume that D(j) is Q-dependent cf section 10.4.

P E 3 (j +j 1 ), ...., E 3 (j +j p ) ∈ Bo -L(Bo) ≤ 2 [Log(n 0 ) + q 1 ](n 0 ) 3 L(Bo) √ h 0
holds for all model E 1 (j) except a tiny minority. Moreover all the logical models are correct cf section 6.4. As a matter of fact for all the models which we studied we have found approximations still better than those which we have just understood previously. It is the case for the models with continuous density.

Let us choose E 2 (j) as a sequence of random variables which has a continous density with a Lipschitz coefficient K 0 not too big (it is equivalent that D(j) has a continous density with a Lipschitz coefficient K 1 not too big). Then, the conditional probabilty of E 2 (j) given E 2 (j + j 2 ) = e 2 , E 2 (j + j 3 ) = e 3 , ........,E 2 (j + j p ) = e p has also a Lipschitz coefficient K ′ 0 :

˛P n E 2 (j) = e 0 | E 2 (j + j 2 ) = e 2 , ...

o -P n E 2 (j) = e ′ 0 | E 2 (j + j 2 ) = e 2 , ... o˛≤ K ′ 0 |e ′ 0 -e 0 | .
Now one can apply property 6.3.5 to conditional probabilities. Then, for all interval I,

P E 3 (j) ∈ I | E 3 (j + j 2 ) = e 2 , ... = L(I) 1 + O(1)K ′ 0 N (I) .
It is clear that under this assumption, the approximation with an IID sequence is better: there is a denominator in N(I) instead of N (I). One thus ensures thus approximations better than those obtained by using the hypothesis 6.3.4. For example

P E 3 (j) ∈ I k | E 3 (j + j 2 ) = e 2 , ... = L(I k ) 1 + O(1)K 0 2 q1 m . instead of P E 3 (j) ∈ I k | E 3 (j + j 2 ) = e 2 , ... = L(I k ) 1 + Ob(1)e ′ 0 √ 2 q1 √ m
,

where e ′ 0 = 2 [Log(n 0 ) + q 1 ](n 0 ) 3 .
Therefore under reasonable hypotheses, we can prove that we have an approximation of an IID sequence which is better than that defined in the general case, for example in equation 10.1.

Conclusion

Now, almost all the models D(j) are good models. Moreover all the logical models are correct. On the other hand, the models with continous densities are closer to the IID sequences.

Chapter 11

Building of an IID sequence : II

General method

The building studied here must be associated with a model where the data have a density admitting a coefficient of Lipschitz not too large (it is known that it is a correct assumption : cf section 6.4.1).

Description of the method

We use again a sequence of data a(j) translated in number: a(j) , j = 1, 2, ...., N 3 , as in section 10.1.

Choice of the parameters a) We choose α ∈ R + such that α ≤ 0.02 according to the quality of the desired approximation 1 . b) One choose S=10. c) One chooses now r 0 = r 1 and q 0 ∈ N * such that :

c-1) q 0 /r 0 is maximum c-2) m S /2 q0 ≥ 1001, c-3) m S = m F ([m F (κ r0 )] 3/4 ) is sufficiently large but not too (cf remark 11.1.7 of [18] ) c-4) √ q 0 2 q0 Γ -1 (a S 2 ) ≤ 2α √ S √ N3 √ r 0 m S , where a S 2 = Γ Γ -1 (4 -q0 ) ⌊m S /2 q 0 ⌋ m S /2 q 0 + 2 q 0 m S ≈ 1/4 q0 .
1 As a matter of fact, in function of β 1,p : cf theorem 8

First transformation a) We transform the sequence of data a(j), j = 1, 2, ...., N 3 , into a sequence of random bits e 2 (j) by the same way as in section 10.1. b) We set e 3 S (j) = mT m 1 (e 2 S (j)/m 1 ) , 2 where m 1 = m F (κ r0 ). Remark 11.1.1 One can also use e 3 S (j) = mT m 1 (e 2 S (j)/m 1 ) only for the first j ∈ {1, 2, ..., ⌊N 3 /r 0 ⌋} : cf Remarks 11.1.1 and 11.1.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. Moreover, one can also suppress this step : in this case, one sets e 3 (j) = e 2 (j).

It is supposed that sequence E 3 (j) has asymptotic independence. One checks this asymptotic independence by logical and numerical studies : e.g. cf chapter 9.

Use of the limit theorems a) Because e 3 (j) depends on S, we write e 3 S (j) instead of e 3 (j).

b) We denote by e 4 S (t), t = 1, 2, ..........., N 2 , N 2 = N S ≤ ⌊N 3 /r 0 ⌋ , a subsequence of e 3 S (j) obtained by suppressing some subsequences e 3 S (ρ u ), e 3 S (ρ u +s u1 ), ......,e 3 S (ρ u + s un ) in order to ensure independence between the lines defined below. If one does not have independent files, this step is not necessary forcing. Checking of S a) One checks by numerical calculations that the curve of the

h → P {H S (n) = h | H S (n + j 2 ) = h 2 , ..., H S (n + j p ) = h p } 2 cf definition of T m 1 : definition 1.2.5 3
Indeed, in section 9.3, it was understood that, for some files (e.g. texts),

P n F (i, n) = f ˛F (i, n -j ′ 2 ) = f 2 , ...., F (i, n -j ′ p ) = fp o → P {F (i, n) = f } as j ′ 2 → ∞ when j ′ 1 = 0 < j ′ 2 < .... < j ′ p .
In order to have the same result for

P {F (i, n) = f |F (i, n + j ′ 2 ) = f 2 , ...., F (i, n + j ′ p ) = fp} → P {F (i, n) = f }, we invert the even lines.
Therefore, logically, when one will summon the lines f 1 (i, n), it is reasonable to think that it will be difficult to predict P i f 1 (i, n) knowing elements which are passed or future.

is enough close to that of the uniformity: it is necessary that the condition of equation 6.3 is satisfied. In general, it is well the case if S= 10. If it is not the case, one remakes several times the previous operations with various S > 10. One chooses smallest S ≥ 10 which is appropriate. It is noted

S 0 . b) We set h(n) = h S0 (n) for n = 1,...,N.
Use of the Fibonacci function a) Let m = m S0 = f i n3+1 and a = f i n3 < m where n 3 ∈ N. Let T q0 be the Fibonacci function with parameters a, m and q 0 . We set

x(n) = T q0 h(n)/m = 0, b n 1 , b n 2 .....b n q0
4 where q 0 was defined previously in 11.1.1.

b) We set b ′ q0n-r+1 = b n r for n=1,..,N and r = 1, 2, ..., q 0 (cf also step "f" section 10

.1.2 ) c) The sequence {b ′ n } is noted b 0 (n ′ ), n ′ = 1, 2, ..., N q 0 .
11.1.2 Explanation of the conditions about q 0 and r 0

Because the various steps of this construction, one can accept the model of the section 6.3.4 : [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

P {H(n) = h | H(n + j s ) = h s , s = 2, 3...} = 1 m 1 + u k : cf chapter 7 of
We deduce P X

(n) = k/2 q0 X(n + j 2 ) = x 2 , X(n + j 3 ) = x 3 , .... = 1/2 q0 + Ob(1)ǫ I k , where | ǫ I k | ≤ ǫ = Γ -1 (4 -q 0 ) √ N Iel m
: cf sections 11.1.3 and 11.1.4 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. We deduce that, for all sequences of bits bi n , for all finite injective sequence j s ,

P B 0 (n ′ ) = bi 1 B 0 (n ′ + j 2 ) = bi 2 , B 0 (n ′ + j 3 ) = bi 3 , .... = 1/2 + Ob(1)ǫ ,
where ǫ = α/ √ q 0 N when N q 0 is the size of sample {b 0 (n ′ )} : cf section 11.1.3 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. Now apply the theorem 9 :

P √ N P e -(1/2) p ≥ σ B x ≤ Γ 1-β1,p/x 1+γ1,p x , where β 1,p ≤ √ N q0ǫp √ A(p)L(Bo) ≈ √ N q0.2pǫ A(p) 1/2 2 p/2 = 2pα A(p) 1/2 2 p/2 .
Then, β 1,p is enough small in order that P (B 0 (n ′ ), B 0 (n ′ + j 2 ), ...., B 0 (n ′ + j p )) = (bi 1 , ...., bi p ) is about also close to (1/2) p that it would be it in case IID. One obtains the same type of results for theorem 10. It is not thus finally possible to distinguish the sequence b 0 (n ′ ) from an IID sample.

Example

In section 11.2 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] we study an example : we obtain a sequence of random bits b 1 (n ′ ). This sequence can be asked to rene.blacher@imag.fr. Soon one will be able to obtain it in a website 5 .

Currently, this sequence b 1 (n ′ ) is the first part of the sequence of numbers ξ n : n ≤ 1000000. Its size is N = 1.000.000.

One finds the sequence of bits b s by writing these ξ n in binary system in the form

ξ n = b n 1 b n 2 ....b n 50 6 .

Choice of random datas

We have used a sequence of data a(j) with N 3 = 298.159.056 and 1 ≤ a(j) ≤ 256.

The data result from texts, mathematical texts and file of programming : cf section 9.3.

In the study of data, our numerical results prove that one can consider that the sequence C(j) and D(j) are Qd-dependent with Qd=22 and Qd=2 : cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

We choose α = 0.02, S=10, q 0 = 57, r 0 = 28 and m 1 = m F (32 28 ).

11.2.2 Building of a random sequence b 1 (n ′ )

We have suppress some sequences {e 3 (ρ u ), e 3 (ρ u + 1)......, e 3 (ρ u + n 4 )} in order that f(i,n) and f(i',n') belongs to different files if i = i ′ . Then, the lines are independent.

Then, h(n) = 5 In order to know if this website is created, type the words "Rene Blacher random numbers" in Google for example 6 As a matter of fact, we obtain initially ξn = 2 57 x(n) where x(n) = 0, b n 1 b n 2 ....b n 57 . But, Matlab 2006 does not write numbers which have more 50 bits. Then it is simpler to forget the last bits b n 51 , ..., b n 57 . 7 The worst approximation occurs for the sample of maximum size: N 1 = q 0 N .

102

Then, we have used the assumption II :

P B 1 (n ′ ) = b B 1 (n ′ + j 2 ) = b 2 , ...., B 1 (n ′ + j p ) = b p = 1/2 + Ob(1)α √ N q 0 ,
where α/(N q 0 ) 1/2 ≈ 2.649/10 6 .

For example, we have studied the empirical aspect by using theorem 10 where one can consider that, the sequence b 1 (n ′ ) is surely Qd B -dependent with Qd B = 57. Various results are obtained in [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] Then, it is difficult to differentiate the sequence b 1 (n ′ ) from an IID sample. Indeed, if our data were not IID, that would imply that √ N q 0 P B e -(1/2) p would be large. That can certainly occur for some (bi 1 , bi 2 , ......., bi p ) but, as the previous increases show it, with a probability which is not too different from that of IID case.

In the previous results, one has increase our approximations by using the 2-dependence which exists for the sequence D(j). For the sequence B 1 (n ′ ), the results are much better because we did everything in our building so that it is identical to a sequence IID.

One could thus have finer increases. For that, it is necessary to calculate γ 1 p where σ

2 1 = σ 2 B [1 + 2γ 1 p ].
In [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] we have estimated σ 2 1 and have compared it with the exact value of σ 2 B for p=1,2,3,4,5. Remark that one obtains the same type of equations with X(n) as with the B 1 (n ′ ) : cf section 11.2.13 [START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

Tests

In section 11.2.14 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF], we are have controled the conclusions of this study by making tests. We use the classical Diehard tests ([2], [START_REF] Knuth | the Art of Computer Programming[END_REF]) and the Higher order correlation coefficients tests ( [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]). We tested the sequences b 1 (n ′ ) or x(n).

Results are in accordance with what we waited: for sequences b 1 (n ′ ) and x(n), the hypothesis "randomness" can be accepted by all these tests.

Conclusion

The inequalities above show that it could be that b 1 (n ′ ) does not check certain tests of an IID sequence, but that will occur with hardly more probabilities that for a sample of a really IID sequence. It is thus not possible to differentiate the sequence b 1 (n ′ ) from an IID sample by using these tests. Thus, it is not possible to differentiate the sequence b 1 (n ′ ) from an IID sample by using P B e and P B e /p B e . Morever B 1 (n ′ ) satisfies also the very important additional property : P B 1 (n ′ ) = b B 1 (n ′ + j 2 ) = b 2 , ...., B 1 (n ′ + j p ) = b p = 1/2 + Ob(1)ǫ.

Then, the sequence b 1 (n ′ ) satisfy all the conditions which we have indicates in section 2.1 and also this theoretical property. Then, one can admit that b 1 (n ′ ) is an IID sample.

Continuous case

Let us notice that the use of the CLT smoothes the probabilities of the sums G(j). One can thus admit that they have a continuous density. It is particularly true if E 3 (j) has already a continuous density. Then, this model has to be studied under the assumption as the density of E 3 (j) with respect to µ m ⊗ ..... ⊗ µ m is continuous and has a coefficient of Lipschitz which is not too large.

It is known that it is a correct assumption : cf section 6.4.1. Thus, this method is completely sure : we are sure that the sequence b 1 (n ′ ) is IID. This technique could be used with the machines which produce random numbers very quickly. It remains valid even if there are dysfunctions (provided that the produced numbers are not completely deterministic or very near to a completely deterministic model).

In fact, it is supposed that there is asymptotic independence: one can thus choose sums of S terms Z i,n with S=10, 20 or much if it is necessary. This study thus applies perfectly to the case of machines not having too great dysfunctions and quickly producing random numbers. 2 . By the CLT, the conditional distribution of G ′ n knowing G ′ n+j2 = g 2 ,.....,G ′ n+jp = g ′ p has a distribution close to a normal one. This normal law has a small variance if the linear correlation coefficients are rather close to ±1. Now it is supposed that, for any n, any p, any sequence j s , s=1,2,, p, P G ′ n+j1 = g | G ′ n+j2 = g 2 , ....., G ′ n+jp = g ′ p is too not concentrated nearly one only point. Because the CLT is used, that means effectively that the linear correlation coefficients are not too close to ±1.

As a matter of fact, what interests us is the conditional probability of the H n = Z 1,n + ... + Z S,n : it is not wanted that it is concentrated nearly one only point. It is thus supposed that P H n+j1 ∈ I|H n+j2 = h 2 , ...., H n+jp = h p is not too different from L(I). It is an assumption easy to check, considering that one has the asymptotic independence of H n+j1 , H n+j2 , ....., H n+jp (according to the properties of the XORLT : e.g. cf proposition 7.2.2). Then, one has already almost the wished equation. In order to be sure that this equation holds, it is enough to use besides the transformation T q .

Moreover the curve of probabilities of G ′ n is smooth. It is even more the case for H n . Then, the same method as that one of property 6.3.5 can be applied to the random sequence X n = T q (H n ) : therefore, one can assume that

P X 1 ∈ I | X n+j2 = x 2 , ....., X n+jp = x p = N (I) m 1 + O(1)6K ′ 0 N (I) ,
where most of the time, K ′ 0 ≤ 1 (and is even much smaller) and where O(1) ≈ 1. As one wants to avoid any risk of error, one will admit K ′ 0 ≤ 100 (of course this increase depends on data). It is easy to understand by using theorem 7 that if S increases K ′ 0 decreases very quickly8 . Therefore, generally, this increase is certainly much too strong. Therefore, Therefore, if one wants to use analog results to those of theorem 8, one will have to replace L(Bo)ǫ p Bo by pǫ/2 p , therefore to replace ǫ p Bo by pǫ, considering that in the case of random bits B n , L(Bo) = 1/2 p . Moreover, by using the same type of proof as in theorem 8, one understands that one will have to replace γ ′ 1,p = Therefore, so that X n cannot be differentiated from an IID sequence, it will be necessary to impose Remark 11.3.1 By using the theorem 8 one has used conditions too much strong if it is supposed that one has the asymptotic independence: in fact, one will obtain approximations much better concretely than those described by the previous results.

P X 1 ∈ I k | X n+j2 =
n 0 2A(p) 12pK ′ 0 2 q m [4 + 1] = 30n 0 p A(p) K ′ 0 2 q m << 1 .

Chapter 12

Building of IID sequences : III

Third method

In this section one uses the convergence of the XORTL (cf theorem 7). One does not apply it to a sequence of numbers as f(i,n), n=1,...,N, but to random numbers of size N, i.e. very large, for example with a sequence of bits of size 100.000.000, these numbers have values in {0, 1, ...., 2 100.000.000 -1}.

12.1.1 Method of construction of the sequence 1) We use again a sequence of data a(j) as in section 10.1. One transforms again it into a sequence of random bits b 3 (n ′ ) by the same way as in section 10.1. These b 3 (n ′ ) are grouped in S lines which we rewrite bt i (n ′ ), i=1,2,..,S, n'=1,2,...,J, each one belonging to files independent of the others. 2) One modifies the lines bt i (n ′ ), n ′ = 1, 2, ...., J, thanks to transformations having a behavior close to that of the permutations. In this aim, one uses other sequences of data c 1 i (n ′ ) ∈ {1, 2, ...., J}, n ′ = 1, 2, ..., J, where i = 1, 2, ...., 3S. Because we use transformations similar to permutations, we set c 1 i (n ′ ) = P erm i (n ′ ) in order that the notations are clearer.

2-a) One groups them togheter by sets of three successive sequences P erm i t (n ′ ) for t=1,2,3, i=1,2,...,S, n ′ = 1, 2, ....., J.

2-b) For each line i, for n ′ = 1, 2, ...., J, one sets, r i 0 (n ′ ) = bt i (n ′ ) and, for each t=1,2,3, r i t (n ′ ) = bt i (P erm i t (n ′ )) for n ′ = 1, 2, ....., J. 2-c) For each line i, we set r i (n ′ ) = r i 0 (n ′ ) + r i 1 (n ′ ) + r i 2 (n ′ ) + r i 3 (n ′ ) modulo 2 for n ′ = 1, 2, ....., J. 3) One definite g i as the number with J bits whose writing base 2 is g i = r i (1)r i (2)....r i (J).

Properties

One uses the properties of the XORLT : One sets X i = G i in order to use theorem 7. One supposes that σ 2

Vr ≤ 1 (cf remark 7.3.3) where V i xn is the sequence of random variables defined on probability space (Ω 7 , A 7 , P roba 7 ) in hypothesis 7.3.1 .

Then, by theorem 7, for all y ∈ {0, 1, ...., 2 J -1}, with a probability greater than 1 -Γ(b) approximately, 1) .

P {K = y} ≈ (1/2 J ) 1 + bOb(1) √ 2 J(S-

Now, one can write

{K = y} = {B 1 = b 1 } ∩ {B 2 = b 2 } ∩ ... ∩ {B 2 J = b 2 J }.
Then, if b 0 is large, with a probability infinitely close to 1, 1) .

P {B 1 = b 1 } ∩ {B 2 = b 2 } ∩ ... ∩ {B 2 J = b 2 J } = (1/2 J ) 1 + b 0 Ob(1) √ 2 J(S-

Permutations and associated transformations

One uses transformations having a behavior close to that of the permutations. Of course, one thinks that one could use Matlab permutations for example. But, it poses a problem: a priori they are not permutations taken randomly. As a matter of fact, one is in the case envisaged by Knuth ( [1] : cf also definition 2.1.5) and which it is necessary to avoid. One needs permutations taken randomly.

For that, one want to use nondeterministic sequences of data to define the permutations.

For example let us suppose that one wants to permute a sequence x(j) of size N and that one has data d(j) ∈ {0, 1, ..., N }. One would like to be able to define a permutation P by P(j)=d(j). But, there is no reason that P is injective.

One can try to remove the j, j' such that d(j)=d(j'), j = j ′ . But if N is large, that can be long. Then, it is easier to use these data differently.

Indeed, it is easy to understand that the technique defined in step 2 allows a mixture of the lines which is as random as it would be the choice of a permutation taken randomly. That is thus adapted perfectly so that we can suppose that the probabilities of each line are chosen randomly.

Example

By using the technique defined in section 12.1.1 with S=5, J=25402545, we have created a real sequence ξ n . This sequence can be asked to rene.blacher@imag.fr. Soon one will be able to obtain it in a website 1 .

Curently, this sequence consists of the secund part of the sequence ξ n which we have obtained by the three methods studied in this report : 1000000 < n ≤ 1.408.040. Its size is N = 508.040.

One obtains the sequence of bits b 2 (n), n=1,2,....,20.402.000 by writing in base 2 these ξ n in the form ξ n = b n 1 .....b n 50 : {b 2 (n ′ )} = {b n s } .

Properties

By using theorem 7 (because J(S -1)/2 ≥ 50.000.000), one understands that in the set of probabilities provided with the distribution such that σ 2 Vr ≤ 1, for all p, with a probability infinitely close to 1,

P {B n = b 1 } ∩ {B n+j2 = b 2 } ∩ ... ∩ {B n+jp = b p } = (1/2 p ) 1 +
Ob(1) 2 50.000.000 .

It is a very good approximation! It allows to obtain very fine results about empirical probabilities, e.g. β 1,p ≤ It is quite clear that with such an approximation, nothing could differentiate such a sequence from an IID sequence if one has sample with size 25.402.545. Now, the assumptions of theorem 7 are realistic : indeed r i t (n ′ ) = bt i (P erm i t (n ′ )) has the characteristic of permutations chosen randomly. Therefore, probabilities p s gs assocated to each g s have to be regarded as chosen randomly. Of course, there will be always models which will not check these assumptions. But there will be of it a negligible number with probability Γ(b) introduced into the theorem 7 : i.e. one can suppose that one has an IID sample which also can not check correct assumptions, but with a probability infintely negligible.

One must thus admit that the previous properties are well checked, i.e. one has an extremely fine approximation.

Tests

We have verifed the previous conclusions by making tests : cf [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] section 12.1.10. We have used the classical Diehard tests cf [START_REF] Gentle | Random Number Generation and Monte Carlo Method[END_REF], [START_REF] Knuth | the Art of Computer Programming[END_REF] and the higher order corre-lation 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.

Conclusion

We thus have one third method to build IID sequences. The advantage is this one has extremely strong mathematical properties and behaves exactly like an IID sequence : it is always possible that the sequence b 2 (n ′ ) is not good, but only with a very negligible probability.

Comparison of methods II and III

The method defined in this section 12.1.1 has theoretical results much better than those defined in the chapter 11.

But, such a quality of the approximation seems useless since one reasons on samples. In our method defined in chapter 11, we obtained an approximation theoretically less fine and yet, we saw that one can regard it as sufficient.

The improvement made in this section to the method defined in the chapter 11 seems not to mean much. For example, there exists always a probability close to 0.045 such as |Pe-(1/2 p )| σ √ N ≥ 2. The approximation provided by the method defined in this section 12.1.1 can thus be only one additional guarantee which one can take when one builds a sequence of random bits b n . It could however to be useful if one wanted to build functions of the b 2 (n ′ ) with certain mathematical properties Because m >> 1 and Inf s [N (I s ]) ≤ m/2, we deduce the lemma.

Then, the following property holds. .

Then, 1 -

 1 2pΓ(b) ≈ 1 -2p 10 340 and Inf s {N Is } ≈ 2 50 . Moreover, because O(1).pb √ Infs{N Is }

Definition 2 . 1 . 6 :N4n=1 1

 2161 Let P ′ e = (1/N 4 ) Bo1 (x n )1 Bo2 (x n+1 ).....1 Bop (x n+p )where the Bo i 's are Borel sets.

Proof 4 . 1 . 2

 412 We prove the proposition 4.1.1

. 1 .Figure 5 . 1 :Figure 5 . 2 :Figure 5 . 3 :

 1515253 Figure 5.1: sup(h i ) = 1

Corollary 6 . 1 . 4

 614 Let n∈F z n where F ⊂ {1, 2, ...., n 0 }. Then n∈F z n = n∈F ′ z ′ n , where z ′ n = z ψ(n) is an IID sample which has the distribution M Z and where F ′ = ψ(F ) and ψ = φ -1 .

Figure 6 . 1 :

 61 Figure 6.1: Sums of subsamples chosen randomly

Figure 6 . 2 :

 62 Figure 6.2: Law of a subsample chosen randomly

Figure 6 . 3 :

 63 Figure 6.3: Example : Normal curve

[

  Newton's theory ] [of gravitation was] [ soon accepted wit] [hout question, and ] [it remained unques] [tioned until the begin] [ning of this century. ] .................................... and the sets H s = [whgkudf ly cuqhjg] [aamxgusdggbxckmp] [x;cbkutcc ze xycyc x] [qtdxucdzlcxy yx vyxy] [ory of Relativity in 190] [xwtex pez! i yi qy yqhfg] .........................................

Figure 6 . 4 :Figure 6 . 5 :

 6465 Figure 6.4: Histogram of f(1,j)

xs 1 P roba xs 1 where T xs 1 A

 111 xs 1 is the σ-algebra generated by xs 1 A xs 1 .

x 1 s 1 '

 1 s are a sample of an IID sequence of random vari-

Hypothesis 6 . 3 . 4 1 s 1 ,x 2 s 2 1 s 1

 63411211 We generalize by natural way the notations of hypothesis 6.3.1. with probabilities p x ,...,x p sp . Then we generalize the p ′ x

Property 6 . 3 . 2

 632 Assume d=2. Then, in order that the inequality 6.1 is useful, we can impose b = 3p[Log(n 0 ) + q].

  Then, the following equality holds : P {T (mY )/m ∈ I} = L(I) 1 + O(1)K0 N (I) , where N (I) ≤ m/2.

Remark 6 . 3 . 10

 6310 One can easily generalize the proof of property 6.3.5 to the two-dimensional case. For example, if p=2, by proposition A.0.1, P T (mY 1 )/m, T (mY 2 )/m ∈ I 1 ⊗ I 2 = L(I 1 )L(I 2 ) 1 + O(1)K 0 Inf s [N (I s )] . Remark 6.3.11

Proposition 6 . 3 . 6

 636 Let (d, p) ∈ {2, 3, ...., } 2 . Let T (x) ≡ d p x mod m = d 2p -1.

Figure 7 . 1 :

 71 Figure 7.1: Normal convergence

Figure 7

 7 Figure 7.2: Uniform convergence

Figure 7

 7 Figure 7.3: Normal convergence

Figure 7 . 4 :

 74 Figure 7.4: Uniform convergence

Figure 7 . 6 :

 76 Figure 7.5: n=10, σ 2 = 50

Figure 7 . 7 :

 77 Figure 7.7: n=10, σ 2 = 200

  ...........................................................................

  N ) +............................................................................. +r 1

P n X 1 , 1 +

 11 .... + X I,1 ∈ Bo ˛X1,2 + .... + X I,2 = y 2 , ..., X 1,p + .... + X I,p = yp o = X x i,j :∀j,x 1,j +...+x I,j =y j η ′ {x i,j } P n X 1,1 + ... + X I,1 ∈ Bo ˛Xi,j = x i,j , i = 1, .., I, j = 2, .., p o ,where xi,j :∀j,x1,j +...+x I,j =yj η ′ {xi,j } = 1.

Theorem 8

 8 Let β 1,p = √ N [L N (Bo)-L(Bo)] ) 2 3/2 + 2L(Bo) where A(p) = 1 -(p 2p + 1)2 -p .

Lemma 8 . 1 . 4

 814 The following equality holds : L n L m = L(Bo) 2 +Ob(1)ǫ5 , whereǫ 5 ≈ 2Ob(1)L(Bo) 2 ǫ p Bo .Proof We have L n = L(Bo) + Ob(1)L(Bo)ǫ p Bo . Then,L n L m = L(Bo) + Ob(1)L(Bo)ǫ p Bo L(Bo) + Ob(1)L(Bo)ǫ p Bo = L(Bo) 2 + 2L(Bo)2 Ob(1)ǫ p Bo + Ob(1)L(Bo) 2 (ǫ p Bo ) 2

σ 2 B

 2 + N Ob(1)2 3/2 L(Bo)ǫ p Bo + 2N Ob(1)L(Bo)

10 5

 5 = 0.0422 = ǫ 2 << 1.

  c) We set f S (i, n) = e 4 S (n + N (i -1)) for i=1,...,S , n = 1,...,N. d) If i ∈ 2N, we set f 1 (i, n) = f (i, Nn + 1) for i=1,...,S, n = 1,...,N 3 . e) We set g S (n) = S i=1 f S (i, n) mod m S for n = 1,...,N. This corresponds to use the CLT. f) We set h S (n) = g S (n) mod m S for n = 1,...,N. This corresponds to use the XORLT.

10 i=1 f 1

 101 (i, n) for n= 1,...,N where N = 1.000.000 and x(n) = 0, b n 1 b n 2 ....b n 57 . We deduce the sequence b 1 (n ′ ), n'=1,2,...,57000000, where {b 1 (n ′ )} = {b n r }.

  .

where σ 2 n

 2 = E [Z 1,n -E{Z 1,n }] + .... + [Z S,n -E{Z S,n} ]

LetP X 1 ∈P B 1 =P

 11 x 2 , ....., X n+jp = x p = L(I k ) 1 Bo = ∪ k∈Θ I k . Then, Bo | X n+j2 = x 2 , ....., X n+jp = x p = b|B 2 = b 2 ....., B p {B n+j1 = b 1 }∩......∩{B n+jp = b p } = 1/2+Ob(1)ǫ/2 ...... 1/2+Ob(1)ǫ/2

Now, by lemma 8 . 1 . 2 , σ 2 B<< 1 .

 81221 ≥ A(p)L(Bo). Then, in theorem 8,β 1,p = √ n 0 [L N (Bo) -L(Bo)]For example, with K ′ 0 ≤ 100, let us choose p ≤ p m = ⌊Log(n 0 )/Log(2)⌋ and n 0 = 10 6 . Because log(n 0 )/log(2) ≈ 19.9, p A(p) m ≥ 10 34 , q=60 (2 60 ≈ 1.153 * 10 18 ), n 0 = 10 6 , log(n 0 ) = 13.

4 )

 4 We set k = S i=1 g i , mod M 2 + 1 where M 2 = 2 J -1 (calculations algorithms 107 are in[START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). 5) Let k = b 1 , b 2 , ...., the writing of k base 2. Then, the sequence b 1 , b 2 , ...., b J is a sequence of random bits.

1 2 1 2

 11 49.999.983 and γ 1,p ≤ 49.999.925 and, for x ≥ 1 2 1000 , P N 1 P B e -(1/2) p ≥ σ B x ≤ Γ 1 -1 2 49.998.982 x .

Property A.0. 4 1 N 1 N

 411 Let I 1 = [c 1 /m, c ′ 1 /m[ and I 2 = [c 2 /m, c ′ 2 /m[. Let g N (k, k ′ ) = h N T -1 (k)/m, T -1 (k ′ )/m .Then, the following approximation holds1 N (I 1 )N (I 2 )) g N (k, k ′ ) = 1 + 6Ob(1)K 0 inf s [N (I s )] . Proof Let k n , n = 1, 2, .., c ′ 1 -c 1 , and h n , n = 1, 2, .., c ′ 2 -c 2 , be two permutations of I 1 ∩ F (m) = {c 1 /m, (c 1 + 1)/m, ...., (c ′ 1 -1)/m} and I 2 ∩ F (m) = {c 2 /m, (c 2 + 1)/m, ...., (c ′ 2 -1)/m}, respectively such that T -1 (k 1 ) < T -1 (k 2 ) < T -1 (k 3 ) < ...... < T -1 (k c ′ 1 -c1 ) and T -1 (h 1 ) < T -1 (h 2 ) < T -1 (h 3 ) < ...... < T -1 (h c ′ 2 -c2). Then, for all numerical simulations which we executed, one has always obtained|T -1 (k r )/mr/N (I 1 )| ≤ 4/N (I 1 )and therefore|T -1 (h r )/mr/N (I 2 )| ≤ 4/N (I 2 ) .We deduce that|g N (k r , h r ′ )h N r/N (I 1 ), r ′ N (I 2 ) | ≤ 4K 0 .M ax s 1 N (I s ) = 4K 0 Inf s [N (I s )].Therefore, by lemma A.0.3,1 N (I 1 )N (I 2 ) g N (k, k ′ ) = 1 N (I 1 )N (I 2 ) r,r ′ g N (k r , h r ′ ) = (I 1 )N (I 2 ) r,r ′ h N r/N (I 1 ), r ′ /N (I 2 ) + 1 N (I 1 )N (I 2 ) r,r ′ g N (k r , h r ′ )-h N r/N (I 1 ), r ′ /N (I 2 ) = (I 1 )N (I 2 ) r,r ′ h N r/N (I 1 ), r ′ /N (I 2 ) + 4Ob(1)K 0 inf s [N (I s )] = 1 + 2Ob(1)K 0 inf s [N (I s )] + 4Ob(1)K 0 inf s [N (I s )] . Proof of property A.0.1 By the previous equalities, m 2 k,k ′ g N (k, k ′ ) = N (I 1 )N (I 2 ) m 2 1+ 6Ob(1)K 0 inf s [N (I s )] = L(I 1 )L(I 2 0 inf s [N (I s )] = L(I 1 )L(I 2 ) 1 + O(1)K 0 Inf s [N (I s )]

  Definition 2.1.7 : It is said that x n is random if P e {x n+1 ∈ Bo|x 1 , ........, x n } ≈ L(Bo), where P e {x n+1 ∈ Bo|x 1 , ........, x n }.

  has not a distribution close to the normal law. 2) But, by proposition 6.1.1, we know that if n 0 = kn 1 , the sample z ′

1 +....+z ′ n1 , z ′ n1+1 + .... + z ′ 2n1 , ...... , z ′ (k-1)n1+1 + .... + z ′ kn1 can be regarded as a sample with a distribution close to the normal law. Indeed, it is possible that Z ′ 1 + .... + Z ′ n1 has not a normal distribution. But the Z ′ n1+1 + .... + Z ′ 2n1 , ...... , Z ′ (k-1)n1+1 + .... + Z ′ kn1 have not the same distribution. Because that, they behave indeed as samples with normal law.

  One will provide the set of the p x 1 s 1 ,..,x p sp of a measure which is a probability : i.e. the set of the possible probabilities p x 1

		x 1 s 1	,..,x p sp .
	probability space. For example, one can choose p x 1 s 1 the p ′ x 1 s 1 ,..,x p	sp is itself the realization of a s 1 ,..,x p sp = ,..,x p p ′ x 1 s 1 ,..,x p sp P m i 1 =1 .... P m ip=1 p ′ where i 1 /m,...,ip/m

sp 's are a sample of a sequence of IID random variables P ′ x 1 s 1 ,..,x p sp defined on a probability space (Ω p 1 , A p 1 , P roba p 1 ) and which have a distribution M.

  1-(p 2 -p+1)L(Bo) . which has the roots p 1 ≈ 0.7888 and p 2 ≈ 3.5423 Therefore, (p 2p + 1)2 -p decreases and converges to 0 if p ≥ 4. Moreover, (p 2p + 1)2 -p = 3/4 if p=2, 7/8 if p=3, 13/16 if p=4, 21/32 if p=5. Then, (p 2p + 1)L(Bo) ≤ 7/8 . Bo (X n )1 Bo (X m ) = L(Bo) 2 + Ob(1)ǫ 3 , where

	Now, (p 2 -p + 1)L(Bo) ≤ (p 2 -p + 1)2 -p . Moreover,
	d(p 2 -p + 1)2 -p dp	= (2p -1)2 -p -Log(2)(p 2 -p + 1)2 -p
	Lemma 8.1.3 If m / ∈ H(n), E 1

  In section 11.2.10, 11.2.11, 11.2.13 of[START_REF] Blacher R | A Perfect Random Number Generator[END_REF], we study the samples b 1 (ψ(n)) , n = 1, 2, ...., N 1 , where N 1 ≤ N and where ψ : {1, 2, ...., N 1 } → {1, 2, ...., N } is an injective function7

11.2.3 Properties of B 1 (n ′ )

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

For example to say that, it would be to affirm that there is no characteristic of the English language such as there is a connection between the units T -1 (I k ) and English texts : cf section 6.4

Marsaglia has not used texts but Rap music. It is no important. We want only to study logically the method of Marsaglia. Then, we use texts because we studied them in a detailed way cf[START_REF] Blacher R | A Perfect Random Number Generator[END_REF].

mσ(n) for all k ∈ Z . Then,

Pe-L(Bo1)pe L(Bo2)...L(Bop) when X n is IID.

In order to know if this website is created, type the words "Rene Blacher random numbers" in Google for example

0, b n 1 , b n 2 ..... is the binary writting of T (h(n))/m.

In theorem 7 independence is assumed. But, clearly, the reasoning remains valid : cf also section 5.5 of[START_REF] Blacher R | A Perfect Random Number Generator[END_REF]

Chapter 7

Limit Theorems

Central Limit Theorem

The Central Limit Theorem (CLT) produces the limit distribution of (X 1 + ....X n )/σ when X n is a sequence of random variables such that E{X n } = 0 and σ 2 is the variance.

It has been proved under various hypotheses of asymptotical independence., in particular under the strong mixing condition or under martingale assumptions : cf [START_REF] Ibragimov | Independent and stationary sequences of random variables[END_REF] and [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]. Now, these condition are too strong for most of datas. Then, some authors have introduce weaker hypotheses : Versik Ornstein ( [START_REF] Bradley R | On a very weak Bernouilli condition[END_REF], [START_REF] Dehling H. Denker M | Versik Processes and very weak Bernouilli processes with summable rates are independent[END_REF]), Cogburn [START_REF] Cogburn R | Asymptotic properties of stationary sequences[END_REF] Rosenblatt [START_REF] Rosenblatt | Uniform ergodicity and strong mixing[END_REF], Pinskers [START_REF] Pinsker | Information and information stability of random variables and processes[END_REF], Doukhan-Louhichi [START_REF] Doukhan | A new weak dependence condition and application to moments inequalities[END_REF]. But theses assumptions are still strong in order to be used with data.

Fortunately, another look is possible : in [START_REF] Blacher R | Central limit theorem by polynomial dependence coefficients[END_REF] , one can use higher order correlation coefficients (cf Lancaster [START_REF] Lancaster | Orthogonal models for contingency tables[END_REF], Blacher [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]). Then, in [START_REF] Blacher R | Central limit theorem by polynomial dependence coefficients[END_REF] we have turned the convergence of moments into an equivalent conditions on these coefficients. For example we have proved the following theorem.

Theorem 3 Assume that the X n have the same distribution with variance σ 2 and that there exists bo > 0 such that |X n | ≤ bo. Assume that n s=1 r =s E{(X s ) 2 (X r ) 2 } -E{(X s ) 2 }E{(X r ) 2 } n 2 → 0 .

Let µ p = E{(X G ) p } where X G ∼ N (0, 1). Then, for all p ∈ N * ,

The proof is section 5.7 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]. These results show that, in many cases, P X 1,1 + .... + X I,1 ∈ Bo X 1,2 + .... + X I,2 = y 2 , ..., X 1,p + .... + X I,p = y p → L(Bo). In particular, results obtained in section 7.3.1 show that this limit is checked for all the data used to build the random sequences b 1 (n ′ ).

Applications

Now we study how one can apply the previous theorems. We are interested by the sequence of random bits b 1 (n ′ ) built in section 11.2 : we assume that B 1 (n ′ ), n'=1,....,N', is a sequence of random bits satisfying

Now, the sequence C(j) defined in section 11.2 is Qd-dependent with Qd=22.

Then,

.

We want that B 1 (n ′ ) behaves like an IID sequence. Thus, we use theorem 8 for Q'-dependent sequences and we increase P

(by lemma 8.1.2). Now, one proves the following lemma by basic method : cf lemma 9.2.9 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF] Lemma 8.1.6 The following inequality holds :

Proof 8.1.7 We prove now the theorem 8

The following inequalities hold.

Now, if we want that the CLT holds, we impose that there is an asymptotic independence. Of course, a such sequence is non-determinist.

Objections

But is what such sequences y n exist? It is a physical question. It is also a philosophical question. As a matter of fact, some people claimed that there does not exist finite random sequences : e.g. cf [START_REF] Knuth | the Art of Computer Programming[END_REF] page 167.

It is due partly so that any sample of a sequence of random variables can be regarded as fully determinist. Indeed the following proposition is obvious. Proposition 9.2.1 Let x n , n=1,...,N, a sequence of real numbers. Then, there exists a function g : {1, 2, ..., N } → R such that for all n ∈ N, x n = g(n).

Moreover, there exists p and a function g : R p → R such that for all n ∈ {1, 2, ..., N -p}, x n+p = f (x n , x n+1 , ..., x n-p+1 ).

Moreover, some philosophies claim that all is fixed. For example, meteorology would be fully determined by all data of earth (all temperatures in all point of earth, all the atmospheric pressures, etc).

In the same way, actions of the men would be fully determined by the context in which they live and by the cells of their brains. Then, a book is fully determined before his writing by theses events.

Of course, that involves problems : for example, the quantum theory is rejected. In order to reject this theory, one can call upon various reasons: 1) it is valid only for the infinitely small. 2) It is only a theory 3) It involves inadmissible contradictions for some people (Schrodinger cat).

But, all theses objections are false. In order to prove that, we use a counterexample : one can exhib a finite unpredictable sequence.

A finite random sequence

z 2 , ......, z N be a pseudo-random sequence with values in [0,1] obtainded by a good pseudo-random generator. Let y i = P (z i ) for i=1,2,....,N. Then, it is no possible to predict y n+p , n ≤ n + p ≤ N if one knows only y 1 , y 2 , ......, y n .

Indeed, even if one knew z 1 , z 2 , ......, z n+p , it would not possible because any polynomial Q such that deg(Q) = 2N and y s = Q(z s ) for s=1,2,...,n is a correct prediction of P. Then, all y * n+p = Q(z n+p ) is a correct prediction of y n+p . Now there exists an infinite number of possible polynomials Q. Then, it is no possible to predict y n+p even if one knew the sequence z n and if one had an infinite computing power (cf example 9.2.1 of [START_REF] Blacher R | A Perfect Random Number Generator[END_REF]). Now there is no reasons that the Y ′ n s have the same distribution, (y n = Y n (ω)). But is is not important because the philosophical objections are that the sequence is not independent.

Anyway, one can build a sequence y ′ n where the Y ′ n s have the uniform distribution : one uses y ′ n = F -1 (y n ) , where F is the distribution function of P(X) when X has the uniform distribution: F -1 (P (X)) has also the uniform distribution.

There is another reason that it no possible to predict y n+p . In order to estimate P, it would be necessary to compute all the polynomial correlation coefficient of order smaller than 2N (cf [START_REF] Blacher R | Higher Order Correlation Coefficients[END_REF]) .

It would thus be necessary to calculate the empirical orthogonal polynomials P N j of order J smaller than 2N associated with z 1 , z 2 , ......, z N . However P N j ≡ 0 if j > N : the empirical polynomials of a order larger than the sample size are impossible to estimate. Moreover, it is not surprising that y n is unpredictable : indeed P depends on more parameters than N. As matter of fact, many simple functions using more than N parameter z n can be appropriate to obtain unpredictable sequence. For example if

Indeed, in order to estimate the k ′ i s and the k ′ i ′ s, one has to resolve the N equations :

) for i=1,2,...,N, that is there are more parameters than equations.

Then, all sequence y 1 , y 2 , ......, y N which depend more parameters than N may be an unpredictable sequence.

Consequence 1

Then, the sequence y n is random : a sequence whose it is impossible to predict the future, it is inevitably random. It is even an independent sequence.

Then, the philosophy which affirms that there does not exists finite random sequences x n , n=1,...,n, does not corresponds to reality : a sequence which one cannot predict is obligatorily random. To say the opposite is illogical.

Consequence 2

In order to obtain sequences which satisfy concretely some asymptotical independence assumptions, we shall use data which depend a priori on a number of parameters much many larger than the size of sample.

Notations 10.1.1 For all x ≥ 2, we set m F (x) = f i n0-1 where f i n0-1 ≤ x < f i n0 (f i n : cf definition 1.2.3).

Then, one chooses now q 1 and r 1 ∈ N * such that 1) (n0) 2 (pm)

Building of the sequence a) We set d(j) = r1 r=1 c(r 1 (j -1) + r)κ r-1 for j = 1, 2, ...., n 0 . b) We set e 1 (j) = d(j)[m/κ r1 ] for j = 1, 2, ...., n 0 . c) We set e 2 (j) = e 1 (j) + rand 0 (j) mod m for j = 1, 2, ...., n 0 where rand 0 (j) ∈ F * (m) is a pseudo-random generator with period m or k 4 .m, k 4 ∈ N * . d) For j = 1, 2, ...., n 0 , we set e 3 (j) = T q1 (e 2 (j)/m) . e) Let 2 q1 e 3 (j) = b j 1 , b j 2 .....b j q1 , b j s ∈ {0, 1} , the binary writting of 2 q1 e 3 (j). f) We set b ′ q1j-r+1 = b j r for j = 1, ..., n 0 , and r = 1, ..., q

Remark 10.1.1 Step c) is not albsolutely necessary.

Study of data

It is supposed that the sequence d(j) is not fully deterministic. That can be checked, for example by logical reasonings as for texts : cf section 9.

One checks that M in j,j ′ ∈{1,...,n0} (|d(j)d(j ′ )|) is not too small. If not, one can choose r 1 more large.

Properties

Use of proposition 6.3.5

We study a sequence of random variables E 3 (j) associated to e 3 (j).

We use proposition 6.3.5 and properties 6.3.3 and 6.3.2, in the probability space (Ω, A, P roba) with the the uniform distribution M, associated to E 3 (j) and defined in hypothesis 6.3.4. Then, for all n, for all p, for all sequence j t , for all Borel set Bo, with a probability larger than 1

,

where

Bo (X n ) with the notations of theorem 8 when X j = E 3 (j) and where

Then, it is no possible to differentiate e 3 (j) and b 3 (n ′ ) of IID sequences : cf section 2.1.4. For example we have the following tables of Γ θx ≈ K 1 θx if n 0 is large enough for x=1 and x=2.

Example

By using this technique, we have created a real sequence ξ n . This sequence can be asked to rene.blacher@imag.fr. Soon one will be able to obtain it in a website 1 . This sequence consists of the last ξ n which one finds in this sequence : In order to obtain b 4 (n ′ ), we have used a sequence a(j), j = 1, 2, ...., N 3 with N 3 = 2.000.000 and 1 ≤ a(j) ≤ 256 obtained from texts : dictionary, encyclopedia, and Bible.

Then, we transform these sequences of letters in numbers. Now, there are only 26 letters. But it is necessary to add, the capital letters, the ":" , ";" , etc. There will be many of these 256 numbers which will not appear not or little. Also, we will write these numbers in base κ = 32 so that each number can have a probability reasonable to appear.

We choose r 1 = 20 (32 20 ≈ 1.2677 * 10 30 ), n 0 = N 3 /r 1 = 10 5 , m = m F (1.27 * 10 30 ), q 1 = 33 (2 q1 = 8.5895 * 10 9 ≈ 10 10 ). Then log(n 0 ) ≈ 11.513, log(n 0 ) + 33 ≈ 44.5. Then, one obtains a sequence of 3.300.000 bits which one denotes by b 4 (n ′ ). Then, 1) We have (n0) 2 (pm) 3 2 q 1 m ≈ 10 10 (5.Log(10)/Log(2)) Appendix A

Continous case in dimension 2

We want to prove property 6.3.5 in dimension 2. We keep the notations of section 6.3.3.

N be the probability density function such that

Assume again that T is a Fibonacci congruence. Then, the following equality holds :

where inf s [N (I s )] ≤ m/2.

Proof We need the following lemmas.

Lemma A.0.2 The following equality holds :

Proof The following equalities hold : .