1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 23
Текст из файла (страница 23)
. . , Q̃ − 1 с равными вероятностями 1/Q̃, инепрерывная величина β̃ независимы. Действительно,P (γ = k) ∩ (β̃ ∈ (c, d)) = P k + c < Q̃α < k + d =k+ck+dd−c=P<α<== P{γ = k} × P β̃ ∈ (c, d) ;Q̃Q̃Q̃здесь k = 0, 1, . . . , Q̃ − 1 и 0 < c < d < 1.Таким образом,√ 11Dγr α, β̃ = pr γ, β̃ + r β̃, β̃ = .Q̃Q̃Q̃ 1/12Утверждение 9.4 доказано.Отметим, что доказательство утверждения 9.4 существенно уточнено по сравнению с учебником [9].Из утверждения 9.4 следует, что при Q 1 коэффициент корреляции между соседними членами β(s) и α = β(0) последовательности(9.12) невелик и убывает с ростом s степенным образом.Отметим также, что утверждения 9.3 и 9.4 сформулированы для«настоящего» стандартного случайного числа α вида (9.7). Можно сформулировать аналоги этих утверждений в случае применения метода(9.10), (9.11) для чисел {αn } с ограниченной мантиссой длины m.
Приэтом для достаточно большого m при удачном подборе множителя Qстатистические свойства членов последовательности (9.10), (9.11) и «настоящего» стандартного числа (9.7) близки (это показывают соответствующие статистические тесты – см., например, [5, 9, 23], а также следующие подразделы 9.5, 9.6 данного пособия).9.5. Периодичность и мера управляемости метода вычетов.Предположим, что начальный элемент последовательности (9.10), (9.11)равен α0 = 2−m , а множитель имеет вид Q = 52p+1 , где p – целоеположительное число, т. е. справедливо представлениеαn = kn 2−m ; k0 = 1, kn ≡ kn−1 52p+1 (mod 2m );143(9.13)см. также формулу (9.4).Приведем некоторые аргументы в пользу выбора множителя Q ввиде Q = 52p+1 .
Сначала приведем следующее утверждение.УТВЕРЖДЕНИЕ 9.5 [5]. Рассмотрим последовательностьxn =kn, где kn ≡ Q kn−1 (mod K),K(9.14)а K, Q, kn – натуральные числа и n = 1, 2, ... (запись (9.14) означает,что kn равно остатку, полученному при делении Q kn−1 на K). Еслизадать x0 в форме несократимой дроби x0 = k0 /K и предположить,что K взаимно просто с Q, то все xn из (9.14) будут несократимымидробями.ДОКАЗАТЕЛЬСТВО. Применим метод математической индукциипо n = 0, 1, 2, .... Число x0 является несократимой дробью со знаменателем K по условию.Пусть теперь n = s и xs = ks /K – несократимая дробь. ИмеемQ xs = Q ks /K. Согласно формуле (9.14)Q ks = r K + ks+1 ,(9.15)где r – натуральное число.Покажем, что ks+1 взаимно просто с K.
Действительно, если допустить, что у ks+1 и K есть общий простой множитель h, то из (9.15)следует, что Qks делится на h. Множитель Q делиться на h не может,так как по условию Q взаимно просто с K; поэтому на h должно делиться ks , но это противоречит индуктивному предположению о том,что ks /K – несократимая дробь.Итак, ks+1 взаимно просто с K, поэтому из равенства (9.15) имеем) ()(ks+1ks+1Q ks= r+=,xs+1 =KKKт. е. утверждение верно и для n = s + 1.
Утверждение 9.5 доказано.Из утверждения 9.5 следует, что если положить в соотношениях(9.10), (9.11) Q = 52p+1 ; K = 2m и x0 = 1/K (как в соотношениях(9.4) и (9.13)), то члены последовательности αn из (9.13) представляютсобой двоичные дроби с длиной мантиссы m, причем m-е разряды этихдробей равны единице.Существенный недостаток мультипликативного метода вычетов(9.13) связан с тем, что количество чисел, имеющих двоичную мантиссу144длины m и принадлежащих интервалу (0, 1), является конечным (не более чем 2m различных чисел), и поэтому последовательность (9.13)является периодической, т. е.
рано или поздно (через L ≤ 2m шагов) какое-нибудь значение αL совпадет со значением α0 , и тогда, в силусоотношений (9.10), (9.13), имеемαL+i = αi при i = 1, 2, . . .(9.16)Наименьшее число L, удовлетворяющее соотношению (9.16), называется длиной периода. Обычно для расчетов не рекомендуют использовать больше, чем L/2 чисел последовательности (9.13).Стандартными методами теории чисел можно доказать следующееутверждение.УТВЕРЖДЕНИЕ 9.6 [6].
Максимальная длина периода последовательности (9.14) при K = 2m ; m ≥ 3 равна L = 2m−2 , причем онадостигается для случая, когда остаток деления натурального множителя Q на 8 равен 3 или 5.Докажем также следующий простой факт.УТВЕРЖДЕНИЕ 9.7. Остаток от деления чисел Q(p) = 52p+1на 8 для всех p = 0, 1, 2, . . .
равен 5.ДОКАЗАТЕЛЬСТВО. Применим метод математической индукции.Для p = 0 имеем, что число Q(0) = 52×0+1 = 5 при делении на 8 даетостаток 5.Предположим, что для p = k число Q(k) = 52k+1 при делении на 8дает остаток 5. Для p = k + 1 имеемQ(k + 1) = 52(k+1)+1 = Q(k) × 25 = 8 × [3 × Q(k)] + Q(k).Первое слагаемое в последнем выражении делится на 8 нацело, аостаток от деления второго слагаемого на 8, согласно индуктивномупредположению, равен 5. Таким образом, остаток от деления числаQ(k + 1) на 8 равен 5.
Утверждение 9.7 доказано.Величина Q = 52p+1 в двоичном представлении оканчивается на 01,поэтому все αn из соотношения (9.13) являются m-разрядными двоичными дробями, последние два разряда которых равны 01. Вследствиеравенства L = 2m−2 остальные m − 2 разряда «пробегают» все возможные комбинации.
Поэтому в качестве α0 можно выбрать любуюm-разрядную двоичную дробь указанного типа.Утверждения 9.5–9.7 показывают, что конструкция мультипликативного метода вычетов (9.13) позволяет (с помощью выбора достаточно большой длины мантиссы m) получать последовательности вида145(9.1) со сколь угодно малой мерой управляемости µ = 1/2m−2 (см.
подраздел 9.1). Соответственно, последовательность (9.13) с малой меройуправляемости достаточно хорошо воспроизводит случайность, хаотичность, что в некоторой степени оправдывает введение определения мерыуправляемости итерационных процессов в подразделе 9.1.Из утверждения 9.4 следует, что из-за желательной независимости(а лучше сказать, «малой» зависимости) стандартных случайных чиселαn из (9.13) целесообразно выбирать натуральный параметр p такжедостаточно большим.В новосибирской школе методов Монте-Карло для алгоритмов с числом испытаний n порядка 109 и меньше долгие годы вполне удовлетворительным считается генератор (9.13) с параметрами m = 40 и p = 8,прошедший всестороннее многолетнее тестирование.В последнее время в связи с ростом мощностей современных вычислительных систем возникла потребность в генераторах с увеличеннымпериодом. В частности, для параллельных вычислений используется генератор (9.13) с параметрами m = 128 и p = 50054 [31].Определенные трудности конкретной реализации формул (9.13) накомпьютере связаны с тем, что нужно производить действия с числами,имеющими мантиссу длины m, превосходящую стандартный форматЭВМ.9.6.
Тестирование генераторов стандартных случайныхчисел. Применение мультипликативного метода вычетовв параллельных вычислениях. Окончательный вывод о качестве того или иного генератора случайных или псевдослучайных чисел следуетиз результатов тестирования этого генератора. Сразу следует заметить,что никакая, даже самая широкая, система тестов не является достаточной для того, чтобы объявить тот или иной генератор подходящим.Процесс проверки данного генератора, вообще говоря, бесконечен.Более того, каждую задачу с известным решением, при численном решении которой используется генератор случайных (псевдослучайных)чисел, можно рассматривать как очередной тест для этого датчика.
Мыупомянем наиболее распространенные тесты для проверки генераторов.В связи с необходимостью применения генераторов для решениямногомерных задач, одной из важнейших характеристик последовательностей {αn } является свойство d-равномерности, смысл которого146состоит в том, что векторы(d)(d)α1 = (α1 , ..., αd ), α2 = (αd+1 , ..., α2d ), . . .
, α(d)n = (αd(n−1)+1 , ..., αnd )(9.17)должны с ростом n с вероятностью единица равномерно заполнять единичный d-мерный куб ∆(d) . Это означает, что частота попадания в любую прямоугольную подобласть куба стремится к объему этой областипри n → ∞.Проверку этого свойства можно осуществлять, например, с помощью критерия хи-квадрат (см., например, [15]).Область ∆(d) разбивается на r = sd одинаковых достаточно малыхкубов (при этом вводится равномерная сетка шага 1/s по каждой координате), подсчитываются частоты {νi } попадания векторов (9.17) в этималые кубы и величинаχ̃2r−1 (n)rXνi − npi=npii=12,(9.18)где {pi = 1/r} – «теоретические» вероятности попадания равномерно распределенных векторов (9.17) в соответствующие кубы разбиения.Согласно теореме Пирсона (см., например, [15]), справедливо соотношениеZ xlim P χ̃2r−1 (n) < x =fχ2r−1 (u) du,n→∞0гдеfχ2r−1 (u) =u(r−1)/2−1 e−u/22(r−1)/2 Γ (r − 1)/2является плотностью хи-квадрат распределения с (r − 1) степенямиR +∞свободы, а Γ(v) = 0 wv−1 e−w dw – гамма-функция.Задается доверительная вероятность (или коэффициент доверия)ε (чаще всего берут ε = 0, 95; 0, 99; 0, 999) и из уравненияZ ∞fχ2r−1 (u) du = 1 − εχ2 (r−1,1−ε)находят (обычно с помощью соответствующих таблиц) величинуχ2 (r − 1, 1 − ε), которую называют доверительной границей с уровнемзначимости (1 − ε).147Доверительная граница сравнивается со значением χ̃2r−1 (n) из равенства (9.18), и если χ̃2r−1 (n) < χ2 (r − 1, 1 − ε), то исследуемая выборка(9.17) считается удовлетворительной, а если χ̃2r−1 (n) ≥ χ2 (r − 1, 1 − ε) –неудовлетворительной.
Для критерия χ2 рекомендуется выбирать n и rтаким образом, чтобы выполнялось неравенство n/r ≥ 10.Для проверки свойства d-равномерности применяется также ряд других тестов. Прежде всего упомянем тест «d-нормальности», основанный на переходе от векторов (9.17) к соответствующим d-мерным векторам независимых стандартных нормальных случайных величин. Весьма широкое применение имеют спектральные тесты, основанные накритерии Вейля (волновой тест и др.; см., например, [9]).Учитывая утверждение 9.2, при проверке генераторов можно исследовать случайность цифр стандартных чисел α.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
