2007-uch-posob-vargapetyan-1

5. Покер!тест.

В полученной последовательности случайных чисел U1, U2, …, про изведем преобразование в целые числа 1, 2, …, 10 по правилу:

Заменим Ui на 1, если 0.0 ≤ Ui < 0.1 Заменим Ui на 2, если 0.1 ≤ Ui < 0.2

.

.

.

Заменим Ui на 10, если 0.9 ≤ Ui ≤ 1

Новые числа должны быть случайными, если Ui —случайные чис ла, в этом случае используется тест 2 с М = 10.

Вариант 1. Рассмотрим последовательные наборы из пяти чисел:

—пять любых одинаковых чисел из 1–10 обозначим ААААА;

—одно измененное число типа ААААВ;

—сочетание типа АААВВ;

—сочетание типа АААВС;

—сочетание типа ААВВС;

—сочетание типа ААВСD;

—сочетание типа ABCDE.

Только такие сочетания могут встречаться при проверке чисел. Вероятности появления сочетаний из пяти цифр при истинной слу чайности:

P (AAAAA) = 0.0001

P (AAAAB) = 0.0045

P (AAABB) = 0.0090

P (AAABB) = 0.0720

P (AAABC) = 0.1080

P (AABCD) = 0.5040

P (ABCDE) = 0.3024

Обычно в связи с малостью значений вероятности первое и второе сочетания объединяются вместе, в результате получается шесть со четаний из пяти цифр (отсюда карточное название теста).

Вариант 2. Для варианта 1 можно подсчитать, сколько различ ных цифр будет в пяти выбранных. Значения легко подсчитываются по данным варианта 1:

Р(1) = 0.0001

Р(2) = 0.0135

Р(3) = 0.1800

Р(4) = 0.5040

Р(5) = 0.3024

71

В этом варианте первое и второе значения чаще всего также объе диняются.

Вариант 3. Часто ограничиваются выбором не пяти цифр в соче тании, а четырех, в этом случае:

P (AAAA) = 0.001

P (AAAB) = 0.036

P (AABB) = 0.027

P (AABC) = 0.432

P (ABCD) = 0.504

И здесь первое и второе значения чаще всего объединяются.

6. Тест последовательных пар.

Имеем последовательность чисел U1, U2 , …,. Пусть имеется целое число М (М ≥ 2). Произведем замену каждого числа Ui на выражение 1 + ЦЧ (Ui М), где ЦЧ (.) — целая часть произведения случайного числа на М; в случае равенства произведения выбранному числу М ЦЧ (.) = М – 1.

Новые числа будут случайными целыми от 1 до М, если Ui случай ны. Теперь образуем матрицу из пар полученных чисел вида

(1, 1) (1, 2) … (1, М – 1) (1, М) (2, 1) (2, 2) … (2, М – 1) (2, М)

.

.

.

(М, 1) (М, 2)… (М, М – 1) (М, М)

и определим, в какой из М2 категорий лежит каждое число. При ис тинной случайности каждая пара должна иметь одинаковую вероят ность, равную 1/M2, и после этого можно использовать тест 1. Чаще всего принимают М = 3, 10, 20 для первого, второго и третьего вари анта соответственно.

Каждый из этих шести тестов оценивается статистиками, кото рые при случайности последовательности Ui примерно подчиняются хи квадрат распределению с числом степеней свободы, заданным в каждом тесте. Обычно выборка проверяемых чисел ограничивается количеством от 1000 до 10000. Если все тесты приводят к значению D (3.26) ≥ 0,95, то качество случайных чисел достаточно высокое. Если хотя бы один из тестов не проходит, то такой генератор не дол жен использоваться. Однако при этом следует помнить, что при уве личении объема выборки все тесты могут дать положительный ответ.

Проверка по критерию хи квадрат, распределений хи квадрат, получаемых при использовании каждого теста, носит название теста CHCH (chi square on chi square). Его введение позволяет нивелиро

72

вать непрохождение на случайность по какому либо из тестов. В на стоящее время существует программа TESTRAND, проверяющая 10 млн случайных чисел по всем названным критериям, однако ее применение прежде всего должно интересовать разработчиков гене раторов и в меньшей степени — пользователей. Вместе с тем при ИМ сложных, ответственных систем небесполезно проводить тщательную проверку генерируемых БСВ!

3.5.3.Теоретическая оценка качества генераторов

Внекоторых случаях до проверки последовательности БСВ на слу чайность проводится теоретическая проверка конгруэнтных генера торов, реализующих последовательность (3.22).

1. Последовательный корреляционный тест.

При случайности последовательности U1, U2 , …, корреляция стро

го равна 0, т. е. R (Ui, Ui +1) = 0.

Подставив Ui = xi /m в (3.22), можно показать, что

Если а и m простые числа, возможно (3.30) заменить на равен ство. Дадевичем [14] показано, что не рекомендуется применять ге нератор, у которого правая часть (3.29) больше 0.01, а правая часть (3.30) меньше 0.005. Например, для генератора URN13 при с = 0, а = 663 608 941 и m = 232, проводя оценку по (3.29), (3.30), получаем 1/a = 0.0000000015, (a + 6)/m = 0.1545, следовательно, генератор отвечает сформулированным правилам и проходит корреляционный тест.

2. Спектральный тест (межплоскостных расстояний).

Этот тест основан на утверждении, что n выборок (U1, …, Un),

(U2, …, Un+1), (U3, …, Un+2),…, полученных от генератора по формуле (3.22), лежат в конечном и малом числе параллельных, одинаково

расположенных гиперплоскостей [15]. То, что они лежат в конечном числе плоскостей, очевидно, а то, что количество плоскостей мало, является предметом обсуждения. Каждая плоскость должна содер жать по меньшей мере три точки, тогда наименьшее число плоско стей будет равно (n!m)1/n. В табл. 3.7 приведены значения этого про изведения для разного числа выборок n при m = 232.

Естественно, что существуют различные наборы плоскостей, со держащие все эти точки. Рассмотрим такой набор, когда расстояние

73

Таблица 3.7. Значения произведения

между плоскостями будет наибольшим, тогда критерием спектраль ного теста будет являться расстояние между плоскостями dn при n

измерениях. Существует алгоритм TSTM4, входящий подпрограм мой в TESTRAND, легко подсчитывающий это расстояние при раз личных значениях коэффициентов (3.22). Очевидно, что при фикси рованном n, чем меньше dn, тем лучше генератор. Критерий, приме няемый в литературе, выглядит следующим образом: dn ≤ 2–30/n, в табл. 3.8 это значение приводится в зависимости от n.

Например, для генератора RANDU, широко применяемого в Рос сии, при данных c = 0, a = 216 + 3, m = 232 имеем: d2 = 0.00002, d3 = 0.092, d4 = d5 = d6 = d7 = d8 = d9 = 0.093, т. е. этот генератор соответствует спектральному тесту только для двумерного случая. Кстати, генератор, используемый в GPSS/H, проходит спектраль ный тест до n = 9.

Название «спектральный тест» пришло из теории распростране ния волн, где наибольшее значение vn = 1/dn служило критерием наи лучших условий распространения (а в нашем случае — случайности).

Все векторы чисел (Ui, …, Ui+n–1) лежат в n(мерном единичном кубе. Наименьшее расстояние между двумя плоскостями этого куба равно расстоянию от начального значения (0,0, …, 0,0) до (0,0, …, 0,1) и вычисляется как

dL(n) = ((0 – 0)2 + (0 – 0)2 + … + (0 – 1)2)0.5 = 1, а наибольшее расстояние до (1, 1, …, 1,1) — из выражения

Поскольку расстояние длиной l может быть разделено r плоско стями на r – 1 равных промежутка длиною l/(r – 1), то отсюда следу ет, что генератор номера плоскости (n!m)1/n будет иметь расстояние между плоскостями, лежащее между

74

Таблица 3.9. Значения наилучшего расстояния

Первое значение является наилучшим возможным расстоянием при n(мерной выборке для генератора модуля m. В табл. 3.9 представ лены значения наилучшего расстояния в зависимости от n и m, и мож но считать, что они являются стандартом для оценки добротности ге нератора, выраженной в расстоянии между плоскостями d2, …, d9 при заданном m.

Если поделить d исследуемого генератора на лучшее расстояние, приведенное в табл. 3.9 для выбранного m, то полученное значение ri в пределе равно 1 и генератор тем лучше, чем ближе результат деле ния к 1. Например, проверим на основе этого правила генератор RANDU, пользуясь значениями dL,полученными выше:

r2 = 0.00002/0.00001 = 2, r3 = 307, r4 = 52, r5 = 19, r6 = 12, r7 = 7, r8 = 5, r9= 4.

Из расчета видно, что наиболее плохое поведение генератора — при размерностях 3 и 4. Из (3.31) найдем число плоскостей для 3 размерного случая для этого генератора. В этом случае расстояние d3 = 0.092, следовательно, нижний предел равен 1/ 0.092 + 1 = 11.8, а верхний — 3 / 0.092 + 1 = 19.8. На самом деле, для этого генера тора возможное число плоскостей (см. табл. 3.7) равно 2953, поэто му с определенными оговорками этот генератор можно принять.

Пример. Проиллюстрируем сказанное на примере генератора с коэф фициентами

xi+1 = 7xi mod 11, x0 = 1.

Из (3.29) оценим корреляцию R (Ui+1, UL) = 1/7 + ε, а из (3.30) ε ≤ 13 /11 = = 1.18

Таким образом, такой генератор может пройти тест благодаря большо му значению ошибки. При n = 2 получим последовательность 1, 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, которая имеет период m – 1 = 10. В результате получим 10 пар случайных чисел (1, 7), (7, 5), (5, 2), (2, 3), (3, 10), (10, 4), (4, 6), (6, 9), (9, 8), (8, 1). Спектральный тест предусматривает получение 10 плос костей с интервалом 1/11 = 0.909, каждая из которых содержит одну из пар (рис. 3.11, линии А).

Но для конгруэнтного генератора при данных параметрах плоскостей должно быть не больше (2! 11) 1/ 2 = 4 (рис. 3.11, линии Б) — это, естествен но, предельный — худший — случай. Линии В (рис. 3.11) представляют

75

Рис. 3.11. Расположение пар чисел

три плоскости, содержащие все точки. Расстояние между параллельными плоскостями d2 = 0.3162. Лучшее расстояние для этого генератора при m = 11, n = 2 равно 1 / (4 – 1) = 0.33; таким образом, r = 0.362/0.333 = 0.95. Следовательно, рассматриваемый генератор для заданных параметров весь ма хорош. Однако, если принять m = 232, что естественно для современных компьютеров, у которых в этом случае лучшее расстояние равно 0.00001, то значение r = 0.3162/0.00001 = 31620. Это отношение очень большое, и такой генератор не может использоваться категорически!

Приведенный пример подчеркивает, что рекомендации по выбору генератора должны всегда соблюдаться, среди них главными явля ются:

—период генератора должен быть не менее 1 млрд;

—генератор должен пройти все проверки.

Использование плохого генератора обесценит все усилия исследо вателя даже при идеальной модели.

76