Определение качества генераторов
Вы можете применить различные тексты для определения случай-
ности последовательности чисел. Ни один из тестов не скажет, что
последовательность является случайной, однако, он скажет, если
она не является таковой. Тесты могут выявить не случайные после-
довательности, но, если тест не нашел недостатков, это не означа-
ет, что данная последовательность действительно случайная. Тесты,
однако, повышают уверенность в генераторе случайных чисел, кото-
рый породил последовательность. Теперь мы кратко рассмотрим нес-
колько простых способов тестирования последовательностей.
Для начала рассмотрим способ определения того, насколько
близко распределение чисел в последовательности соответствует
ожидаемому. Например, вы пытаетесь генерировать последователь-
ность случайных чисел от 0 до 9. Вероятность появления каждой
цифры равна 1/10. Пусть была сгенерирована следующая последова-
тельность
9 1 8 2 4 6 3 7 5 2 9 0 4 2 4 7 8 6 2
Если вы подсчитаете число появлений каждой цифры, то получи-
те результат
Цифры Число появлений
0 1
1 1
2 4
3 1
4 3
5 1
6 2
7 2
8 3
9 2
Далее вам следует ответить самому себе на вопрос, достаточно
ли похоже данное распределение на ожидаемое вами.
Помните: если генератор случайных чисел хороший, он генери-
рует последовательности случайно. В истинно случайном варианте
все последовательности возможны. Действительно, как какая-то пос-
ледовательность может быть не случайной, если любая последова-
тельность возможна? Просто некоторые последовательности менее по-
хожи на то, какой должна быть случайная последовательность, чем
другие. Вы можете определить вероятность того, что данная после-
довательность является случайной, используя критерий хи-квадрат.
В критерии хи-квадрат ожидаемое количество вычитается из
наблюдаемого количества встреч числа в сгенерированной последова-
тельности. Этот результат называется V. Вы можете использовать V
для нахождения процента в таблице значений хи-квадрат. Этот про-
цент определяет вероятность того, что была порождена случайная
последовательность. Малая таблица хи-квадрат приведена на
рис.7-1; вы можете найти полные таблицы в большинстве книг по
статистике
-----------------------------------------------------------
p=99% p=95% p=75% p=50% p=25% p=5%
n=5 0.5543 1.1455 2.675 4.351 6.626 11.07
n=10 2.558 3.940 6.737 9.342 12.55 18.31
n=15 5.229 7.261 11.04 14.34 18.25 25.00
n=20 8.260 10.85 15.45 19.34 23.83 31.41
n=30 14.95 18.49 24.48 29.34 34.80 43.77
------------------------------------------------------------
Рис.7-1. Выбранные значения хи-квадрат.
Для определения вероятности того, что последовательность не
случайная, найдите строку в таблице, показанной на рис.7-1, с
числом элементов последовательности; в данном случае это 20. За-
тем ищите число по строке, которое больше V. В данном случае это
колонка 1. Это означает, что существует вероятность 99% того, что
пример из 20 элементов будет иметь V больше 8,260. С другой сто-
роны это означает, что существует вероятность только в 1% того,
что проверяемая последовательность была сгенерирована случайным
образом. Чтобы пройти через критерий хи-квадрат, вероятность V
должна снизиться до уровня от 25% до 75%.
Однако, вы можете противопоставить этому выводу вопрос: Так
как все последовательности возможны, как может данная последова-
тельность иметь только однопроцентный шанс быть законной? Ответ
такой: это всего лишь вероятность. Фактически, если вы применяете
критерий хи-квадрат, вам следует получить несколько различных
последовательностей и усредненный результат, чтобы избежать от-
вержения хорошего генератора случайных чисел. Любая единичная
последовательность может быть отвергнута, но ряд различных после-
довательностей после усреднения должен давать хороший результат.
С другой стороны, последовательность может пройти через кри-
терий хи-квадрат и не быть случайной. Например, последователь-
ность
1 3 5 7 9 1 3 5 7 9
пройдет критерий хи-квадрат, но она выглядит не очень случайной.
В данном случае сгенерирован пробег по диапазону значений. Пробег
- это просто возрастающая или убывающая последовательность чисел
с произвольным интервалом. В данном случае каждая группа из пяти
цифр представляет собой возрастающую последовательность и как та-
ковая не может считаться случайной последовательностью. Можно
создать тест для обнаружения такой ситуации, но это выходит за
рамки данной книги.
Другой характеристикой, подлежащей оценке, является длина
периода: то есть, как много чисел может быть сгенерировано до на-
чала повторения последовательности. Все машинные генераторы слу-
чайных чисел всегда генерировали повторяющуюся последователь-
ность. Чем длинее период, тем лучше генератор. Даже если частота
чисел внутри периода распределена равномерно, числа не образуют
случайную серию, так как действительно случайная серия не может
достаточно повторяться. В общем случае период в несколько тысяч
чисел удовлетворяет большинству применений. Тест для выяснения
периода может быть разработан.
Различные другие тесты могут быть применены для определения
качества генератора случайных чисел. Наверное можно написать
больше программ для проверки генераторов случайных чисел, чем
создать самих генераторов. Рассмотрим еще один тест, который поз-
волит вам проверить генератор случайных чисел "визуально", ис-
пользуя диаграмму для демонстрации характеристик сгенерированной
последовательности.
В идеале диаграмма должна основываться на частоте каждого
числа. Однако, так как генератор может порождать тысячи различных
чисел, это не выполнимо. Вместо этого будут создаваться диаграм-
мы, сгруппированные до десяти цифрам. Например, так как порождае-
мые числа лежат в области от 0 до 1, число 0.9365783 будет вклю-
чено в группу 9, а число 0.34523445 будет включено в группу 3.
Это означает, что диаграмма вывода случайных чисел имеет 10 ли-
ний, каждая из которых представляет число попаданий в группу.
Программа также выводит среднее значение последовательности, ко-
торое может быть использовано для обнаружения смешения. Как и все
другие программы данной главы следующая программа выполняется
только на персональном компьютере IBM PC, который имеет адаптер
цветного графического дисплея. Разработанные ранее функции Ran1 и
Ran2, а также встроенная функция Турбо Паскаля Random, продемонс-
трированы рядом для сравнения.
{ программа, которая сравнивает три генератора случайных чи-
сел }
program RanGenerator;
uses
Graph;
const
COUNT = 1000;
var
freg1, freg2, freg3: array[0..9] of integer;
a2, a1: integer;
f, f2, f3: real;
r, r2, r3: real;
y, x: integer;
GraphDriver, GraphMode: integer;
{отображение графического вывода}
procedure Display;
var
t : integer;
begin
for t := 0 to 9 do
begin
Line(t*10, 180, t*10, 180-freg1[t]);
Line(t*10+110, 180, t*10+110, 180-freg2[t]);
Line(t*10+220, 180, t*10+220, 180-freg3[t]);
end;
end; {Display}
function Ran1: real;
var
t: real;
begin
t := (a1*32749+3) mod 32749;
a1 := Trunc(t);
Ran1 := Abs(t/32749);
end; {Ran1}
function Ran2: real;
var
t: real;
begin
t := (a2*10001+3) mod 17417;
a2 := Trunc(t);
Ran2 := Abs(t/17417);
end; {Ran2}
begin
{ переключение на
графический режим, используя режим 4 CGA/EGA }
GraphDriver := CGA;
GraphMode := CGAC1;
InitGraph(GraphDriver, GraphMode, '');
SetColor(2);
SetLineStyle(SolidLn, 0, NormWidth);
OutTextXy(80, 10, 'Comparison of Random');
OutTextXy(96, 20, 'Number Generators');
{ прорисовать базовые линии }
Line(0, 180, 90, 180);
Line(110, 180, 200, 180);
Line(220, 180, 310, 180);
OutTextXy(30, 190, 'Random Ran1 Ran2');
{инициализация переменных генераторов случайных чисел }
a1:=1; a2:=203;
f := 0; f2 := 0; f3 := 0;
for x := 0 to 9 do
begin { инициализация матриц частот }
freg1[x] := 0;
freg2[x] := 0;
freg3[x] := 0;
end;
for x := 1 to COUNT do
begin
r:=Random; { взять случайное число }
f:=f+r; { прибавить для вычисления среднего }
y:=Trunc(r*10);{ преобразовать в целое число от 0 до 9 }
freg1[y]:=freg1[y]+1;{ увеличить счетчик частоты }
r2 := Ran1; { взять случайное число }
f2:=f2+r2; { прибавить для вычисления среднег }
y:=Trunc(r2*10);{ преобразовать в целое число от 0 до 9}
freg2[y]:=freg2[y]+1;{ увеличить счетчик частоты }
r3 := Ran2; { взять случайное число }
f3:=f3+r3; { прибавить для вычисления среднего }
y:=Trunc(r3*10);{ преобразовать в целое число от 0 до 9}
freg3[y]:=freg3[y]+1;{увеличить счетчик частоты }
Display; { отобразить счетчики частот }
end;
ReadLn;
RestoreCrtMode;
WriteLn('mean of Random is: ', f/COUNT);
WriteLn('mean of Ran1 is: ', f2/COUNT);
WriteLn('mean of Ran2 is: ', f3/COUNT);
end.
В данной программе каждая функция генерирует 1000 чисел и на
основе этого создаются таблицы частот. Процедура Display рисует
все три матрицы частот на экране после генерации каждого случай-
ного числа так, что вы можете наблюдать рост частот. На рис.7-2
показан вывод каждого генератора случайных чисел после генерации
1000 чисел. Средние значения равны 0,489932 у Ran1, 0,4858311 y
Ran2 и 0,494014 у Random. Это приемлемо.
------------------------------------------------------------
Сравнение генераторов случайных чисел
¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+-----------------+ +-----------------+ +-----------------+
Random Ran1 Ran2
-----------------------------------------------------------
Рис.7-2. Вывод из программы отображения работы генераторов
случайных чисел.
Для эффективного использования программы вы должны наблюдать
как за формой диаграммы, так и за динамикой роста, чтобы выявить
короткие повторяющиеся циклы. Например, Ran2 генерирует значи-
тельно меньше чисел в области от 0,9 до 0,999999, чем Random и
Ran1.
Конечно данный текст не является всеобъемлющим, но он помо-
жет вам понять способ, которым генератор порождает числа, и уско-
рит процесс анализа генераторов.
