Characteristics of the quality of generators. - Modeling of systems

Generator quality characteristics.

With statistical modeling of the system & pound; using the software generators of pseudo-random quasi-uniform sequences, the important characteristics of the quality of the generator are the period length P and the length of the segment of aperiodicity L. The length of the aperiodicity interval b of the pseudo-random sequence {x ,}, given by the equation

is the largest integer such that, for 0, the event P {x/= x y } does not take place. This means that all the numbers x, are not repeated within the interval of aperiodicity.

Obviously, the use of the sequence of numbers {x,}, whose length is greater than the segment of aperiodicity, can lead to repetition of the tests under the same conditions as before, that is, an increase in the number of realizations does not give new statistical results.

The method of experimental determination of the period length P and the length of the aperiodicity interval b reduces to the following [29]. The program for generating the sequence {x & lt;} with the initial value x 0 is started and V of the numbers x, is generated. In most practical cases, we can assume F = (1 h-5) 10. The numbers of the sequence {x,} are generated and the number x y is fixed.

Then the program is restarted with the initial number x 0 and when the next number is generated, the truth of the event P '(x, = x to } is checked. If this event is true: r = /! and I = 1 2 (* 1 & lt; * 2 ​​& lt; is calculated the length of the sequence period P = r 2 -g 1 . The generation program starts with the initial numbers x 0 and x P . The fix is ​​

Fig. 4.12. Experimental determination of the length of a period from the length of a period of aperiodicity: a - varplat 1; b - adopted 2

is the minimum number r =/ 3 , at which the event P {x, = * | + & lt; }, and the length of the aperiodicity interval I, =/ 3 + P is calculated (Figure 4.12, a). If P 'turns out to be true only for/= Y, then b & gt; V (Figure 4.12, 5).

In some cases, a rather cumbersome experiment to determine the lengths of a period and a period of aperiodicity can be replaced by an analytical calculation, as shown in the following example.

Example 4.5. It is necessary to show that in the sequence of numbers {*, ·} described by the equation

for a simple module M we can choose the coefficient λ so that for any X 0 , is relatively prime to M, the length of the segment of aperiodicity, coinciding in this case with the length of the period P, will be 1. In other words, it is necessary to find for which

conditions of equality

holds with the minimum value of -1. We can write [see (4.11)], such that (4.14) holds for

(here it is essential that X 0 is relatively simple with M).

By assumption, it is required that the smallest exponent s

s (A), satisfying (4.15) and called the exponent A modulo M, was equal to A/-1. For any simple module M , there are φ <( M -1) values ​​of λ (primitive roots) satisfying the equation (4.15) for P and (A) *

(M), where

(A /) is the Euler function defined by as the number of natural numbers m ^ M, relatively prime to M. For a simple module M we have cp (M) A/- 1.

Thus, we have proved the existence of many λ for which the repetition of the elements of the sequence {x,} occurs on (M ~ 1) -th number of XV-i • • • 1 _, = P = M - 1, which was to be proved.

For the algorithms for obtaining sequences of numbers {x,} of general form (4.10), the experimental verification is complex (because of the large P and I), and the calculated relations are not explicitly obtained. Therefore, in such cases it is expedient to make a theoretical estimate of the length of the segment of aperiodicity of the sequence b. For this we use the elementary probabilistic model considered in the following example [4, 36, 37].

Example 4.6. Let there be a finite set containing N different numbers. We perform a sequence of independent experiments, in each of which a single number is extracted and written from this set. The probability of extracting any number in each of the experiments is equal, since the sample of numbers is carried out with a return. Let's denote by b a random number - the number of the experiment in which the number already written down earlier will be retrieved for the first time. One can prove that in this probabilistic model for this; about x & gt; 0 we have

Since the mathematical expectation of a random large value of with is such a distribution function is equal to> gt/2, then for A -> oo we obtain M [ Such estimation of the length of the period of aperiodicity is "rough", but it is useful in practice for the preliminary determination of b for the purpose of further refinement by an experimental method.

Let's consider some features of statistical verification of stochasticity of pseudo-random sequences. For this check, various statistical evaluation criteria can be used, for example, the Kolmogorov, Pearson, and so on criteria. But in practice, the simplest approximate verification methods are used most often [29, 37].

To check the uniformity of the basic sequence of random numbers x ь 1 = 1, #, you can use these estimates:

To test tables of random numbers, various tests are usually applied, in each of which the numbers are classified by some criterion and the empirical frequencies are compared with their mathematical expectations using the Pearson criterion [29, 46].

To test hardware random number generators, you can use the same techniques as for checking sequences of pseudo-random numbers obtained by software. The peculiarity of such a check will be that not the numbers that are then needed for modeling the system 5 are checked. Therefore, in addition to testing the quality of the random numbers produced by the generator, the stable operation of the generator should also be guaranteed for the duration of the machine experiment with the model M m .

Improve the quality of sequences. In view of the advantages considered, the main application in the practice of simulation systems is finding various software ways of obtaining numbers. Therefore, consider possible methods for improving the quality of sequences of pseudo-random numbers. One of the most common methods of such improvement is the use instead of formulas of the form (4.9), which are first-order recurrence formulas, of recurrence formulas of order r, that is,

where the initial values ​​ x 0 , x 1y ..., x, _, are given. In this case, the length of the segment of aperiodicity 7, for such a sequence for r & gt; 1

is much larger than for r = 1. However, this increases the complexity of the method, which leads to an increase in the expenditure of computer time for obtaining numbers and limits the possibilities of its use in practice.

To obtain a sequence of pseudo-random numbers with a long length of the period of aperiodicity b , one can use the perturbation method [29, 37]. This method of obtaining a sequence of numbers is based on a formula of the form

where the functions Φ (u) and '' (k) are different.

In this case, the formula x /+ 1 = F (х & lt;) is mainly used, and only when I is a multiple of A /, the sequence is perturbed & quot ;, that is, the transition to formula x & lt; + 1 = 'P (x /). The integer M is called the perturbation period.

All considered criteria for checking sequences of pseudo-random numbers are necessary for setting up simulation experiments on a computer with the model N m , but their sufficiency can be said only when considering the problem of modeling a particular system 5.

thematic pictures

Also We Can Offer!

Ошибка в функции вывода объектов.