close

Вход

Забыли?

вход по аккаунту

?

О мультипликативном датчике случайных чисел.

код для вставкиСкачать
УДК 519.676
Вестник СПбГУ. Сер. 1, 2003, вып. 3 (№ 17)
С. М. Ермаков
О МУЛЬТИПЛИКАТИВНОМ ДАТЧИКЕ СЛУЧАЙНЫХ ЧИСЕЛ∗
1. Случайные числа.
Пусть α1 ,α2 ,. . . — последовательность независимых реализаций случайной величины
α, равномерно распределенной на промежутке [0,1] и f (X), X = (x1 , . . . , xs ) — интегрируемая с квадратом в единичном s-мерном гиперкубе Ds -функция, Ds = {X : 0 ≤ xi ≤
1, i = 1, . . . , s}. В литературе [1] иногда говорят об «истинно» случайных числах αi . Это
означает, строго говоря, что мы находимся в рамках теории вероятностей и предполагаем выполнение системы аксиом этой теории [2]. Если это так, то следующие факты
имеют место.
1.1. Пусть X (l) = (a(l−1)s+1 , . . . , als ), l = 1, . . . , N . Тогда для любой измеримой в
Ds функции (и при любом s = 1, 2, . . .) с вероятностью 1 имеет место равенство
N
! 1 (l)
lim
= f (x) dx
f X
N →∞ N
l=1
(1)
Ds
(частный случай Усиленного Закона Больших Чисел).
1.2. Если f суммируема с квадратом, то
⎧
⎫ y
N
⎨ √N 1 ⎬
! 2
2
(l)
− f (X) dx ≤ y =
lim P
f X
e−u /2 du,
⎩ σf N
⎭
N →∞
π
l=1
0
Ds
где
σf2 =
Ds
(2)
⎛
f 2 (x) dx − ⎝
⎞2
f (x) dx⎠
Ds
(частный случай Центральной Предельной Теоремы).
1.3. Утверждения 1.1 и 1.2 выполняются, если произвольным (не зависящим от
f ) образом изменен порядок нумерации членов последовательности α1 , . . . , αN . . .
Как известно, выполнения указанных свойств достаточно для решения широкого
круга прикладных задач, требующих вычисления интегралов большой кратности.
Очевидно также, что алгоритм получения псевдослучайных чисел, вычисляющий
последовательности чисел, удовлетворяющих свойствам (1.1–1.3), также был бы пригоден для решения упомянутого круга задач. Далее наша цель будет состоять в том,
чтобы теоретически показать, что для известного мультипликативного датчика свойства (1.1–1.3) выполняются приближенно, и уточнить о приближенности в каком смысле идет речь.
∗
Работа выполнена при поддержке РФФИ (грант № 01-01-00315), ГФЕН (грант № 99-01-39137).
c С. М. Ермаков, 2003
23
2. Равномерно распределенные последовательности.
Обращаясь к детерминированным алгоритмам, мы не должны пользоваться аппаратом теории вероятностей. Здесь аппаратом, позволяющим конструировать последовательности со свойствами близкими к свойствам (1.1–1.3) предыдущего раздела является
аппарат теории чисел.
Отметим, прежде всего [3], что нельзя указать алгоритм построения последовательности вещественных чисел, удовлетворяющих свойству 1.1 даже при s = 1. Множество
чисел такой последовательности счетно, имеет Лебегову меру нуль и существует измеримая функция f (x), для которой (1) не выполняется.
Тем не менее, сужение класса рассматриваемых функций позволяет построить детерминированные последовательности со свойством (1).
Если функция f интегрируема в смысле Римана, то последовательности, для которых выполнено (1) существуют [4,5]. Такие детерминированные последовательности называют равномерно распределенными в смысле Вейля (при s = 1). Аналогично определяются последовательности равномерно распределенных s-мерных векторов
e1 , e2 , . . . , en , . . . в Ds , где en = (e1n , . . . , esn ). Такая последовательность называется равномерно распределенной, если для любой интегрируемой в смысле Римана функции
f (X), в Ds справедливо предельное соотношение
N
1 f (en ) = f (X) dX.
(3)
lim
N →∞ N
n=1
Ds
Необходимым и достаточным условием равномерной распределенности последовательности является критерий Вейля.
Теорема. Для равномерной распределенности последовательности векторов en в
Ds необходимо и достаточно, чтобы для любого набора k1 , . . . , ks целых чисел, не
равных одновременно нулю, выполнялось равенство
N
1 2πi(k1 ε1n +k2 ε2n +...+ks εsn )
e
= 0.
N →∞ N
n=1
lim
(4)
Легко проверить, что при s = 1 (4) выполняется, например, для последовательности εn = {nβ}, где β — любое иррациональное число, а {α} означает дробную долю
числа α.
Очевидно, что для «настоящих» случайных чисел (с вероятностью 1) выполняются равенства (3) и (4); но последовательность ε = ε1 ε2 ε3 . . ., которая претендует на
сходство с последовательностью независимых реализаций случайной величины с равномерным распределением, должна также обладать следующим свойством.
Последовательность векторов
*
)
(5)
ẽn = ε(n−1)s+1 , . . . , εns , n = 1, . . .
при любом s должна быть равномерно распределенной в Ds .
Отметим, что в теории чисел обычно рассматривают векторы
en = (εn , εn+1 , . . . , εn+s−1 ).
(6)
Если последовательность этих векторов равномерно распределена, то последовательность ε называют s-равномерно распределенной и вполне равномерно распределенной, если она s-равномерно распределена при любом s.
24
Для целей обоснования алгоритма получения чисел похожих на случайные (псевдослучайных) более естественным является рассмотрение векторов вида (5).
Векторы (5) составлены из независимых компонент. Мы будем говорить, что исходная последовательность ε независимо s-равномерно распределена (н.s-р.р.), если для
нее равномерно распределена последовательность векторов (5).
Ряд результатов относительно s-р.р. последовательностей содержится в работе
Франклина [6]. Ниже мы приводим модификации некоторых его результатов для независимо s-р.р. последовательностей.
2.1. Если последовательность н.s-р.р., то она не обязательно н.s + 1-р.р.
Действительно, {nβ} при иррациональном β — 1-р.р. (и н.1-р.р.) При s=2 составим
векторы (5)
en (2) = ({(2n − 1)β} , {2nβ}) , n = 1, 2, . . .
Не умаляя общности, считаем β < 1. Покажем, что en (2) не распределены равномерно в квадрате. Действительно, в случае их равномерной распределенности должно
иметь место равенство
N
! 1 χ en (2) =
dx dy = 1/2 ,
N →∞ N
n=1
lim
(7)
где = {x, y : 0 ≤ x ≤ y ≤ 1}, а χ — характеристическая функция этого треугольника.
Равенство (7) означает также, что неравенство
{(2n − 1)β} ≤ {2nβ}
(8)
должно выполняться в пределе для половины числа членов последовательности en (2) .
Но, очевидно, {2nβ} = {{(2n − 1)β} + β} , (β < 1) , а
⎧
при {(2n − 1)β} + β < 1
⎨ {(2n − 1)β} + β
{{(2n − 1)β} + β} =
⎩
{(2n − 1)β} + β − 1 при {(2n − 1)β} + β > 1.
Но второй случай не может быть реализован, так как из (8) имеем
{(2n − 1)β} ≤ {(2nβ)} = {(2n − 1)β} + β − 1 ,
т. е. β −1 > 0 и β > 1, что противоречит предположению. Таким образом, наша точка
принадлежит треугольнику при условии {(2n − 1)β} ≤ 1 − β, т. е. в 1 − β = 1/2 случаев. Последнее вытекает из 1-р.р. последовательности {(2n − 1)β} и иррациональности
β. Из сказанного следует наше утверждение.
2.2. Справедливо также следующее утверждение. Если последовательность обладает свойством 1.3 первого раздела (перестановочностью), то из н.s-р.р. последовательности следует (при s > 1) ее н.(s-1)-р.р.
Утверждение это тривиально для s-р.р. последовательностей, причем перестановочность не требуется.
Д о к а з а т е л ь с т в о: Пусть последовательность векторов
)
*
en (s−1) = ε(n−1)s+1 , . . . , εns
25
р.р. в Ds , тогда очевидно
*
)
e˜n (s−1) = ε(n−1)s+1 , . . . , εns−1
р.р. в Ds−1 .
e˜n (s−1) будем называть проекцией en (s−1) на Ds−1 . Исходная последовательность перестановочна и н.s-р.р. и поэтому для любой последовательности en (s−1) найдется en (s) такая, что каждый вектор en (s−1) этой последовательности будет служить
e˜n (s−1) (проекцией) для соответствующего en (s) . Это и доказывает наше утверждение.
3. Последовательности дробных долей показательной функции
Предметом дальнейшего рассмотрения будут последовательности вида
αn = {M n x}, n = 0, 1, . . . , x ∈ (0, 1),
(9)
которые носят названия последовательностей дробных долей показательной функции.
Мы покажем, что для почти всех x из [0,1] последовательность (9) приближенно удовлетворяет свойствам случайных чисел, сформулированным в пункте 1. Для этих целей
нам понадобится следующее обобщение теоремы Сю [7,8].
Теорема 1. Пусть f (X) интегрируема по Риману в Ds и
ϕM (x) = f (x, {M1 x}, {M1 M2 x}, . . . , {M1 , . . . , Ms−1 x}) ,
где M1 , . . . , Ms−1 — натуральные числа большие единицы и M = min (M1 , . . . , Ms−1 ).
Тогда справедливо равенство
1
ϕM (x) dx =
lim
M→∞
0
f (X) dX.
(10)
Ds
В [8] имеются также оценки скорости сходимости для функции Липшицева класса.
Использование теоремы Сю позволяет получить элементарное доказательство некоторых фактов об асимптотических по M свойствах распределения векторов, составленных
из членов последовательности дробных долей показательной функции.
n
) Пусть αn =* {M x}, n = 0, 1, . . . , x ∈ (0, 1), Составим векторы Yk =
a(k−1)s , . . . , aks−1 , n = 0, 1, . . . и рассмотрим сумму
N
1 S(M, N, x, f ) =
f (Yk ),
N
(11)
k=1
где f — произвольная интегрируемая поРимануDs функция.
)
*
Тогда, если ϕM (x) = f (x, {M x} , . . . , M s−1 x ), то f (Yk ) = ϕM {M (k−1)s x } и, таким образом,
N
,
+
1 (k−1)s
lim S(M, N, x, f ) = lim
ϕM
x
.
M
N →∞
N →∞ N
k=1
Поскольку M > 1 — целое число, то M (k−1)s при k = 1, 2, . . . – различные числа
и по теореме 4.1 (см. [9], с. 42) последовательность чисел {M (k−1)s x}, k = 1, 2, . . ., —
26
распределена равномерно при почти всех x из (0, 1). Отсюда вытекает равенство
n
1 ϕM ({M (k−1)s (x)}) = ϕM (X)dx.
lim
N →∞ N
1
k=1
(12)
0
Это, в свою очередь, доказывает следующую теорему.
Теорема 2. Для любой интегрируемой по Риману функции f (X),X ∈ Ds , при
любом фиксированном s справедливо равенство
N
1 f (Yk ) = f (X)dX.
M→∞ N →∞ N
lim
lim
(13)
k=1
Доказательство следует из (10) и (13).
Свойство последовательности αn , выражаемое равенством (13) принято называть
также свойством асимптотической по M вполне равномерной распределенности.
Замечание. Легко видеть, что теорема 1 остается справедливой при изменении
нумерации компонент вектора X. Это обозначает, что при изменении порядка нумерации элементов последовательности αn , (но одинаковым образом в каждой группе
из s членов) равенство (13) остается справедливым.
Что касается произвольного порядка нумерации элементов последовательности (9),
то можно показать, что после такого изменения она удовлетворяет асимптотически по
M критерию Вейля.
Пусть N1 = Ns и α1 , α2 , . . . , αN1 — отрезок последовательности (9). При некотором
s из элементов этого отрезка образуем векторы
Yn = (αln1 , . . . , αlns ),
(14)
где Ln = {l1n , . . . , lsn }, n = 1, 2, . . . , N — множество s различных неотрицательных целых
чисел, причем
Ln ∩ Lm = ∅ при n = m и
N
-
Ln = {1, . . . , N1 }.
n=1
Докажем следующую теорему
Теорема 3. Для последовательности векторов (14) асимптотически с возрастанием M выполняются равенства (4) для почти всех x ∈ (0, 1) и любого набора целых
k1 , . . . , ks , не равных одновременно нулю.
Доказательство. Зафиксируем набор целых, не равных одновременно 0 чисел
k1 , . . . , ks и составим сумму
SM (N, x) =
N
.
)
*/
1 exp 2πi k1 aln1 , . . . , ks alns .
N n=1
Умножая S(N, x) на комплексно сопряженную к ней, имеем
2
|SM (N, x)| =
N
!
!! n
m
n
m
1 x .
exp 2πi k1 M l1 − M l1 + . . . + ks M ls − M ls
2
N m,n=1
27
Выделяя члены суммы, соответствующие m = n, имеем
2
|SM (N, x)| =
1
1
N + N2
N
m,n=1,
m=n
.
) ) n
) n
m*
m ** /
exp 2πi k1 M l1 − M l1 + . . . + ks M ls − M ls x .
Далее проинтегрируем обе части равенства (12) по x и рассмотрим предельное поведение обоих его частей при M → ∞. Имеем
1
0
|SM (N, x)|2 dx =
+ N12
lim
1
m=n M→∞ 0
1
N+
.
) ) n
) n
m*
m **/
exp 2πix k1 M l1 −M l1 + . . . +ks M ls −M ls
dx.
Заметим теперь, что каждая экспонента под знаком интеграла может быть представленна в виде
n
m
n
m
exp2πi(k1 ({M l1 x} − {M l1 x}) + . . . + ks ({M ls x} − {M ls x})).
(Дробная доля разности может отличаться от разности дробных долей разве лишь
на целое число) и, следовательно, может быть отождествлена с ϕM (x) (см. теорему Сю)
для функции 2s переменных exp[2πi(k1 (x1 − y1 ) + . . . + ks (xs − ys ))].
Имеем
lim
1
M∈∞ 0
2
|SM (N, x)| dx =
1
N
+
N (N −1)
N2
1
0
1
1
1
dx1 . . . dxs dy1 . . . dys ×
× exp[2πi(k1 (x1 − y1 ) + . . . + (ks (xs − ys )].
И по лемме Фату
0
0
0
1 ∞
SM(N ) (N 2 , x)2 dx < +∞.
0 N =1
Отсюда следует, что ряд под знаком интеграла должен сходиться при почти всех x при
всех M , превосходящих некоторое M0 . Иначе говоря,
lim lim SM (N 2 , x) = 0,
M→∞ N →∞
но для целого положительного N можно указать такое целое положительное m, что
m2 ≤ N < (m + 1)2 и
N
2m 1
2
2
≤ SM (m2 , x) + √ .
en ≤ SM (m2 , x) +
|SM (N, x)| ≤ SM (m , x) + N
N
N
n=m2 +1
Здесь N ≤ m2 + 2m, a элементы en , входящие в сумму SM (N, x) имеют модуль равный
единице.
Исключительное множество зависит от целочисленного вектора (k1 , . . . , ks ),
но множество таких векторов счетно, и сумма счетного множества множеств нулевой
меры есть нуль, что и завершает доказательство.
28
Таким образом, для последовательности векторов (14) критерий Вейля выполняется приближенно. Из этого не следует, вообще говоря, асимптотическая вполне неравномерная распределенность последовательности (9). Но легко видеть, что аналог Закона
Больших Чисел (3) следует из асимптотического по M выполнения критерия Вейля, если коэффициенты Фурье функции f убывают достаточно быстро, начиная с некоторых
достаточно больших номеров по каждой из переменных.
Отметим, наконец, что асимптотическая невполне равномерная распределенность
влечет также выполнение аналога Центральной Предельной Теоремы, что может быть
доказано после небольших видоизменений рассуждений в [8], стр. 396-401. Мы приведем
только формулировку этой теоремы.
Теорема 4. В условиях теорем 2 и 3 имеет место асимптотическое равенство
√ N
f (Yn ) − f (X) dX < y =
lim lim mesx∈(0,1) x : σN
1
f N
M→∞ N →∞
n=1
Ds
y
= π2 e−u/2 du.
0
Таким образом, мы имеем теоретическую конструкцию вне рамок теории вероятностей, которая приводит к последовательностям, удовлетворяющим приближенно свойствам 1.1–1.3 равномерно распределенных случайных величин.
4. О мультипликативном датчике случайных чисел.
Широко распространенный мультипликативный датчик псевдослучайных чисел α̃n
порождает последовательность чисел в соответствии с алгоритмом Zn ≡ M Zn−1 (modP )
α̃n = Zn / P,
(15)
M и P – целые, M > 1 и P > 1. В качестве Z0 часто берут Z0 = 1.
Особенно простым алгоритмом (15) оказывается при P = 2m (вычисления с m
битами). Последовательность Zk периодична с максимальным периодом 2m−2 . Алгоритм (15) имеет очевидное сходство с (9). Можно показать, что распределение (в
теоретико-числовом смысле) чисел α̃n сходится к распределению αn при m → ∞ (M —
фиксировано). Аналогичная (слабая) сходимость имеет место и для векторов размерности s, составленных из αn и α̃n соответственно.
Таким образом, факты относительно распределения дробных долей показательной
функции могут служить качественным обоснованием мультипликативного датчика.
Конечно, экспериментальные проверки качества с помощью статистических тестов играют важную роль, особенно, если учесть, что результаты 1.3 относятся к «почти всем»
x из (0,1). Это при переходе к числам с конечным числом разрядов может приводить в
конкретных случаях к не вполне предсказуемым последствиям.
Тем не менее, рассматривая семейство алгоритмов (15) при возрастающих m и M
мы можем быть уверены, что найдутся такие M = M (m), что свойства 1.1–1.3 для «настоящих случайных» чисел будут приближенно выполняться. Это, впрочем, подтверждается многочисленными результатами расчетов. В заключение заметим следующее.
1. Один из практических выводов состоит в том, что для получения последовательности α̃n с «хорошими» свойствами алгоритм (15) должен быть реализован с большим
числом m-двоичных разрядов. По-видимому, аппаратная реализация этого алгоритма
позволяет сделать его достаточно быстрым. Здесь можно привлечь средства конвейеризации и параллелизации.
29
2. Теорема Сю рассматривает отображение специального вида гиперкуба Ds на единичный отрезок (при M → ∞). Интересен вопрос: «Существуют ли другие удобные в
вычислительном отношении отображения такого рода? Могут ли они привести к другим и, может быть, принципиально другим датчикам псевдослучайных чисел?»
3. Приведенные результаты позволяют провести более четкую грань между методом
Монте-Карло и так называемым Квази-Монте-Карло методом [10]. По этому поводу см.
также работу [11].
Summary
Ermakov S. M. On the multiplicative random numbers generator.
Some properties of partial parts exponential function sequences are discussed. It allows to get
a qualitative justification for a congruential random numbers generator by elementary tools.
Литература
1. Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения.
М., 1987.
2. Колмогоров А. Н. Основные понятия теории вероятностей. ГОНТИ. М.; Л., 1936.
3. Ченцов Н. Н. Псевдослучайные числа для моделирования марковских цепей // Журнал
выч. мат. и мат. физ. 1967. № 3. С. 632–643.
4. Weyl H. Uber ein Problem aus dem Gebiete der diophantischen Approximationen // Nachr.
Ges. Wiss., Grottingen, Math.-Phis. K1. 1914. S. 234–241.
5. Коробов Н. М. О вполне равномерном распределении и совместно нормальных числах
// Изв. АН СССР. Сер. мат. 1956. Т. 20, № 5. С. 649–660.
6. Franklin J. N. Doterministic simulation of random processes // Math. Comp. 1963. Vol. 17.
P. 28–59.
7. Hsu L. C. A general approximation method of evaluating multiple integrals // Tohoku math.
J. 1957. Vol. 9, No 1. P. 45–55.
8. Ермаков С. М. Метод Монте-Карло и смежные вопросы. М., 1975.
9. Кайперс Л., Нидеррейтер Г. Равномерное распределение последовательностей. М., 1985.
10. Niderreiter H., Hellekalek P., Larcher G. and Zinterkof, editors. Monte Carlo and QuasiMonte Carlo Methods. 1966. Springer-Verlag, N.Y.
11. Ермаков С. М., Товстик Т. М. Квазислучайные последовательности в алгоритмах моделирования случайных процессов // Вестн. С.-Петерб. ун-та. 1999. Сер. 1. Вып. 4 (№ 22). С. 26–
33.
Статья поступила в редакцию 3 декабря 2002 г.
30
Документ
Категория
Без категории
Просмотров
15
Размер файла
206 Кб
Теги
датчик, случайных, мультипликативный, чисел
1/--страниц
Пожаловаться на содержимое документа