Статья:

Линейно-конгруэнтный метод и распределение псевдослучайных чисел

Журнал: Научный журнал «Студенческий форум» выпуск №4(140)

Рубрика: Физико-математические науки

Выходные данные
Акжан Н.К. Линейно-конгруэнтный метод и распределение псевдослучайных чисел // Студенческий форум: электрон. научн. журн. 2021. № 4(140). URL: https://nauchforum.ru/journal/stud/140/86199 (дата обращения: 15.10.2024).
Журнал опубликован
Мне нравится
на печатьскачать .pdfподелиться

Линейно-конгруэнтный метод и распределение псевдослучайных чисел

Акжан Нурлан Кайдарулы
магистрант, Казахского университета экономики, финансов и международной торговли Казакстан, г. Нур-султан
Ахметова Айдана Жанатбековна
научный руководитель, доктор PhD, Казахского университета экономики, финансов и международной торговли Казакстан, г. Нур-султан

 

Оценивается несовпадение последовательностей псевдослучайных чисел, сгенерированных линейным конгруэнтным методом, что улучшает результат Ягермана. Упоминаются приложения к численному интегрированию.

Пусть m - модуль с примитивным корнем λ, и пусть y0 - целое число в системе наименьших вычетов по модулю m с НОД (y0m) = 1. Мы генерируем последовательность y0y1, ... целых чисел в системе наименьших вычетов по модулю m следующим образом: yi+1 = λyi (mod m) для j ≧ 0. Последовательность x0x1, … определяемая как xi = yi / m для j ≧ 0, тогда является часто используемой последовательностью псевдослучайных чисел в единичный интервал [0, 1]. Его элементы xi также могут быть явно описаны как xi = {λiy0/m}для j ≧ 0, где {x} обозначает дробную часть действительного числа x. Последовательность x0x1, ... имеет период Q = Φ(m), где Φ - функция Эйлера.

Для действительного числа α с 0 ≦ α ≦ 1 пусть A(α) будет количеством элементов последовательности x0x1, ... , xQ-1, лежащих в интервале [0,α]. Определим невязку D = sup0 ≦ α ≦ 1 |A(α) / Q - α|, которая измеряет отклонение от равномерного распределения. Ягерман [2] показал, что ≦ (4/π) ((3logm) / Q1/2. Его метод основан на оценке расхождения в терминах определенных тригонометрических сумм. В настоящей заметке мы покажем, что гораздо более простой метод дает значительно более точную оценку для D (см. Теорему 2). Мы доказываем также некоторые связанные результаты.

Для α сверху и положительного целого k пусть A(k) (α) - количество рациональных чисел i / k, 1 ≦ i ≦ k, НОД (i,k) = 1, лежащих в интервале [0,α].

Теорема 1. Для любого натурального числа k имеем

Доказательство. Для произвольного натурального числа r рассмотрим последовательность рациональных чисел l / r, 2 / r, … ,  r / r. В интервале [0, α] есть ровно [] элементов этой последовательности. Теперь посчитаем эти элементы вторым методом. Мы записываем рациональные числа j / r, 1 ≦  j ≦  r, в приведенной форме, а затем подсчитываем для каждого положительного делителя d числа r полученные рациональные числа со знаменателем d, лежащим в [0,α]. Таким образом, мы приходим к тождеству

                                                                (1)

Применяя формулу обращения Мебиуса к (1), получаем

Следовательно, для всех α с 0 ≦  α ≦ 1 имеем

       (2)

Следовательно, D(k) ≦  (1 / Φ(k)) ∑d|k|μ(d)| = g(k). Теперь, g(k) - мультипликативная функция теории чисел. Чтобы доказать, что limk⟶∞g(k)k1-  = 0 , поэтому достаточно показать, что limp8⟶∞g(p8)(p8)1- = 0, где p8 пробегает все простые степени. Ноg(p8)(p8)1- = 2p-∈8(1-1/p) ≦ 2p-∈8, и все готово.

Вернемся теперь к последовательности x0x1, ... , xQ-1. Поскольку существует примитивный корень по модулю m, мы должны иметь m = 2, 4, p8, или 2p8, где p - нечетное простое число, а s ≧ 1. Для m = 2 и 4 легко получаем D = ½  и D = ¼, соответственно, для остальных случаев справедливы следующие оценки.

Теорема 2. Если m = р8, то D ≦  l/Q. Если m = 2p8, то D ≦  2/Q.

Доказательство. Заметим, что последовательность x0x1, … , xQ-1 пробегает в некотором порядке все рациональные числа i/m с 1 ≦  i ≦ m и НОД (i,m) = 1. Следовательно, A(α) = A(m)(α), и мы можем применить (2). При m = p8 для всех α с 0 ≦  α ≦ 1 получаем

.

Для m = 2p8 мы получаем для всех α с 0 ≦  α ≦ 1

Хорошо известно (см., Например, [4]), что невязка D любой последовательности в [0, 1] с Q элементами должна удовлетворять D ≧ ½ Q. Следовательно, никакое существенное улучшение теоремы 2 невозможно. Мы отсылаем к [1] за результатами о распределении псевдослучайных чисел в случае m = 2с s ≧ 3 (конечно, тогда λ больше не является примитивным корнем).

Из теоремы 2 следует две оценки погрешности численного интегрирования на основе последовательности x0x1, … , xQ-1. Сначала применим неравенство Коксмы [3], которое утверждает, что для любой последовательности a0a1, … , aN-1, в [0,1] с невязкой DN и любого подынтегрального выражения / с ограниченной вариацией V(f) на [0,1], есть

Понятие несоответствия обычно определяется в терминах счетных функций относительно полуоткрытых интервалов [0,α), 0 < α ≦ 1. Но легко видеть, что это совпадает с нашим понятием несоответствия, в котором мы использовали счетные функции относительно отрезков [0,α], 0 ≦ α ≦ 1.

Следствие 1. Пусть f - функция с ограниченной вариацией V(f) в [0,1]. потом

Наконец, применим неравенство, данное автором в [4]: если a0a1, … , aN-1 последовательность в [0, ]1] с невязкой DN и f непрерывна в [0,1] с модуль непрерывности ω, то

Для удобства читателя мы прилагаем краткое доказательство. Без ограничения общности мы можем считать, что 0 ≦ a0 ≦ a1 ≦ ... ≦ aN-1 ≦ 1. Тогда мы знаем из [5, уравнение (4)], [6, теорема 1], DN также определяется формулой

Теперь

Следовательно

Но |ai - ξi| < max(|ai i/N|, |ai - (i + 1)/N|) ≦ DN для 0 ≦ i ≦ N - 1 , поэтому |f(ai) - f(ξi)| < ω (DN) для 0 ≦ i ≦ N - 1, и все готово.

Используя тот факт, что ω- неубывающая функция, приходим к следующему следствию.

Следствие 2. Пусть f - непрерывная функция в [0,1] с модулем непрерывности ω . Тогда

где c имеет то же значение, что и в следствии 1.

 

Список литературы:
1. U. Dieter, "Statistical interdependence of pseudo-random numbers generated by the linear congruential method," Proc. Sympos. on Applications of Number Theory to Numerical Analysis (Montreal, 1971), Academic Press, New York, 1972. 
2. D. L. Jagerman, "Some theorems concerning pseudo-random numbers," Math. Comp., v. 19, 1965, pp. 418-426. MR 32 #1877.
3. J. F. Koksma, "A general theorem from the theory of uniform distribution modulo 1," Mathematica Zutphen. B, v. 11, 1942, pp. 7-11. (Dutch) MR 7, 370.
4. H. Niederreiter, "Methods for estimating discrepancy," Proc. Sympos. on Applications of Number Theory to Numerical Analysis (Montreal, 1971), Academic Press, New York, 1972. 
5. H. Niederreiter, "Almost-arithmetic progressions and uniform distribution," Trans. Amer. Math. Soc, v. 161, 1971, pp. 283-292.
6. H. Niederreiter, "Discrepancy and convex programming," Ann. Mat. Pura Appl., 1972.