Случайные числа – это простой элемент криптографии, о котором меньше всего говорят, но он важен не менее, чем остальные. Почти всем системам компьютерной безопасности, в которых применяется криптография, необходимы случайные числа – для ключей, уникальных чисел в протоколах и т. п. – и безопасность таких систем часто зависит от произвольности ее случайных чисел. Если генератор случайных чисел ненадежен, вся система выходит из строя.
В зависимости от того, с кем вы разговариваете, генерация случайных чисел выглядит или тривиальной, или невозможной. Теоретически это невозможно. Джон фон Нейман, отец вычислительной техники, сказал: «Любой, кто считает, что существуют арифметические методы получения случайных цифр, безусловно, грешит». Он имел в виду, что невозможно получить что-то случайное в полном смысле слова на выходе такого детерминированного зверя, как компьютер. Это правда, но, к счастью, кое-что сделать мы можем. От генератора случайных чисел нам необходимо не то, чтобы числа были действительно случайными, а чтобы их невозможно было предсказать и воспроизвести. Если у нас будут выполнены эти два условия, мы сможем достичь безопасности.
С другой стороны, если мы нарушаем эти два условия, безопасности нет. В 1994 году в казино Монреаля установили компьютерный генератор случайных чисел для лотерей. Один наблюдательный игрок, проводивший в казино очень много времени, заметил, что выигрышные номера были каждый день одни и те же. Он успешно сорвал три Джек-Пота подряд и получил 600 000 долларов. (Как следует позаламывав руки, поскрежетав зубами и расследовав все, казино заплатило выигрыш.)
Существует несколько обширных классов генераторов случайных чисел. В основе некоторых из них лежат физические процессы, которые можно считать довольно случайными. Агентство национальной безопасности любит использовать в своей аппаратуре для создания случайных чисел электрические шумы диодов. Другие возможности – счетчик Гейгера или приемники радиопомех. Одна система в Интернете использует цифровой фотоаппарат, направленный на несколько стробоскопов. В других системах применяется турбулентность воздуха в дисководах или момент поступления сетевых пакетов.
Некоторые генераторы случайных чисел отслеживают случайные движения пользователя. Программа может попросить пользователя набрать на клавиатуре большую строку произвольных символов; она может задействовать последовательность символов или даже время между нажатиями клавиш для создания случайных чисел. Другая программа запросто способна потребовать у пользователя туда-сюда подвигать мышью или похрюкать в микрофон.
Некоторые генераторы случайных чисел применяют эту введенную информацию без изменений. В других она служит затравкой (начальным числом) для математических генераторов случайных чисел. Этот прием работает лучше, если системе требуется случайных чисел больше, чем их обеспечивает ввод информации.
Какого бы происхождения ни была случайность, генератор создаст ряд случайных битов. Затем их можно использовать как криптографические ключи и для всего остального, что нужно системе.
Все явления, которые с нами происходят, бывают двух типов – случайные и закономерные. Например, у вас недоставало для покупки магнитофона немножко купюр, и вы решили купить плеер – т.е. поступок является логичным и ожидаемым. Но, идя к магазину, вы обнаруживаете нужную сумму, которая случайным образом изменила планы. Работа генератора случайных чисел полностью зависит от заданного в оператор механизма, так что все числа, которые выдаются, в текущем событии являются псевдослучайными. Операторы, возвращающие случайные числа , обращаются ко времени, а именно системному. Т.е. как в мире, так и в программировании не бывает ничего всецело абсолютного.
Функция rand
В программировании на си, для получения случайных значений изобрели встроенные операторы, которые выдают нам требуемые результаты. И так, для создания случайного числа применяется функция rand , которая Оператор rand применяется для получения случайных чисел, которые возвращают диапазон от 0, и до определенной константы. Причем данная константа объявляется в системной директиве “stdlib.h”, там и базируется эта функция rand. Синтаксис этой функции прост: int m= rand(); т.е. выдается целое число. Опробовав оператор на практике, вы увидите, что появляющиеся числа при старте приложения идентичные. Оплошность заключается в том, что оператор rand работает с одним и тем же системным временем, которое сохранилось при компиляции. Данный генератор случайных чисел завязан на алгоритме изменения программного времени, то все работает неверно.
Теперь о srand и random
Для данной проблемы, незаменима была функция, которая б обнуляла встроенное время при каждом обращении к оператору rand, и разработчики ПО сделали функцию srand . Действие позволяет функции rand каждый раз обращаться не к установленному, а к текущему встроенному таймеру, что открывает возможность работать генератору верно – выдавать случайные значения. Недавно в программирования си ++ усовершенствовался механизм выдачи случайных чисел, из-за появления микросекунд. К тому же расширился диапазон значений, и все текущие новшества трансформировались в функцию random.
Каждый человек, независимо от степени азартности и авантюризма, так или иначе, сталкивался с таким понятием, как лотерея. И лишь немногие спрашивали себя, каким образом происходит случайное распределение выигрышных комбинаций цифр. Как выпадает та или иная цифра? Что заставляет чашу весов опуститься в сторону победителя? Рассмотрим это детально.
Все мы хотя бы раз в своей жизни сталкивались с таким явлением, как лотерея. Но мало кто задумывался или представлял себе, как именно работает данная система, что такое генератор чисел для лотереи и каков его принцип действия.
Понятие генератора чисел
Генератор случайных чисел для лотереи - некое устройство или заданная программа, которая выдает номера, находящиеся на выделенном интервале, в случайном (правильнее сказать, псевдослучайном) порядке. Для определенного вида лотерей, к примеру, "Спортлото", генерируются номера, находящиеся на интервале от 1 до 49.
Выделяют генератор чисел для лотереи аппаратный и программный. В любом языке программирования присутствует функция RAND(), именно она отвечает за выдачу псевдослучайных цифр в заданном диапазоне.
Почему утверждается, что выданные результаты псевдослучайны и что генератор чисел для лотереи работает именно по такому принципу?
Функция RAND: понятие и способ использования
Функция RAND() - это программа или, к примеру, аппарат с детерминированным алгоритмом, который при одинаковых заданных условиях будет показывать постоянно одни и те же результаты. Но для того чтобы соблюдались условия истинной случайной последовательности, не должно быть никакой зависимости от начальных условий или параметров. Поэтому, чтобы избежать подобных случаев, дополнительно используется специальная процедура RANDOMIZE, которая убирает предсказуемость начальных условий, делая их случайными.
Кроме уже известного нам принципа генерации, используется еще один вид генератора лотереи. Рассмотрим его ниже.
Генератор цифр 6 из 45
Генератор чисел для лотереи 6 из 45 - программа, которая используется с целью получения счастливых чисел. При этом есть возможность задать дополнительные параметры для получения более качественного результата.
Можно указать критерии отбора, например:
- Количество выигрышных номеров, которые нужно получить в конечном результате.
- Указать диапазон номеров, в котором будет проводиться отбор.
- Сортировку цифр возможно задать как по возрастанию, так и по убыванию.
- Выбрать тип и способ разделения.
- Исключить повторы или оставить выборку неотсортированной.
- Скопировать ссылку на полученный результат и разместить её на странице в социальных сетях с целью публикации результата.
Генератор номеров: инструкция к пользованию
- По умолчанию установлен вывод пяти номеров. Поменяв настройки, можно получить до 250 случайных выигрышных комбинаций.
- Задаем диапазон, стандартно указывается от 0 до 36, вы же можете указать максимально до 9 999 999 999.
- Выбираем необходимую к нашему виду лотереи сортировку: по возрастанию, по убыванию или расположение цифр в случайном порядке.
- Следующим шагом указываем, как будут отделяться цифры друг от друга - запятой, точкой, пробелом, точкой с запятой.
- Избавляемся от случайных повторений, возникших в процессе выборки.
Таким образом, мы получаем качественно отобранные числа, которые могут быть самыми счастливыми и выигрышными.
Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рис. 22.3 . То есть в идеальном случае в каждый интервал попадает одинаковое число точек: N i = N /k , где N общее число точек, k количество интервалов, i = 1, , k .
порождаемых идеальным генератором теоретически
Следует помнить, что генерация произвольного случайного числа состоит из двух этапов:
- генерация нормализованного случайного числа (то есть равномерно распределенного от 0 до 1);
- преобразование нормализованных случайных чисел r i в случайные числа x i , которые распределены по необходимому пользователю (произвольному) закону распределения или в необходимом интервале.
Генераторы случайных чисел по способу получения чисел делятся на:
- физические;
- табличные;
- алгоритмические.
Физические ГСЧ
Примером физических ГСЧ могут служить: монета («орел» 1, «решка» 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в качестве которого используют шумящее тепловое устройство, например, транзистор (рис. 22.422.5 ).
| Задача «Генерация случайных чисел при помощи монеты» | |
|
Сгенерируйте случайное трехразрядное число, распределенное по равномерному закону в интервале от 0 до 1, с помощью монеты. Точность три знака после запятой. |
|
Первый способ решения задачи
Начертите интервал от 0 до 1. Считывая числа в последовательности слева направо, разбивайте интервал пополам и выбирайте каждый раз одну из частей очередного интервала (если выпал 0, то левую, если выпала 1, то правую). Таким образом, можно добраться до любой точки интервала, сколь угодно точно. Итак, 1 : интервал делится пополам и , выбирается правая половина, интервал сужается: . Следующее число, 0 : интервал делится пополам и , выбирается левая половина , интервал сужается: . Следующее число, 0 : интервал делится пополам и , выбирается левая половина , интервал сужается: . Следующее число, 1 : интервал делится пополам и , выбирается правая половина , интервал сужается: . По условию точности задачи решение найдено: им является любое число из интервала , например, 0.625. В принципе, если подходить строго, то деление интервалов нужно продолжить до тех пор, пока левая и правая границы найденного интервала не СОВПАДУТ между собой с точностью до третьего знака после запятой. То есть с позиций точности сгенерированное число уже не будет отличимо от любого числа из интервала, в котором оно находится.
Второй способ решения задачи
|
Табличные ГСЧ
Табличные ГСЧ в качестве источника случайных чисел используют специальным образом составленные таблицы, содержащие проверенные некоррелированные, то есть никак не зависящие друг от друга, цифры. В табл. 22.1 приведен небольшой фрагмент такой таблицы. Обходя таблицу слева направо сверху вниз, можно получать равномерно распределенные от 0 до 1 случайные числа с нужным числом знаков после запятой (в нашем примере мы используем для каждого числа по три знака). Так как цифры в таблице не зависят друг от друга, то таблицу можно обходить разными способами, например, сверху вниз, или справа налево, или, скажем, можно выбирать цифры, находящиеся на четных позициях.
| Таблица 22.1. Случайные цифры. Равномерно распределенные от 0 до 1 случайные числа |
||||||||||||||||||||||||||||||||||||||||||||
| Случайные цифры | Равномерно распределенные от 0 до 1 случайные числа |
|||||||
| 9 | 2 | 9 | 2 | 0 | 4 | 2 | 6 | 0.929 |
| 9 | 5 | 7 | 3 | 4 | 9 | 0 | 3 | 0.204 |
| 5 | 9 | 1 | 6 | 6 | 5 | 7 | 6 | 0.269 |
Достоинство данного метода в том, что он дает действительно случайные числа, так как таблица содержит проверенные некоррелированные цифры. Недостатки метода: для хранения большого количества цифр требуется много памяти; большие трудности порождения и проверки такого рода таблиц, повторы при использовании таблицы уже не гарантируют случайности числовой последовательности, а значит, и надежности результата.
Находится таблица, содержащая 500 абсолютно случайных проверенных чисел (взято из книги И. Г. Венецкого, В. И. Венецкой «Основные математико-статистические понятия и формулы в экономическом анализе»).
Алгоритмические ГСЧ
Числа, генерируемые с помощью этих ГСЧ, всегда являются псевдослучайными (или квазислучайными), то есть каждое последующее сгенерированное число зависит от предыдущего:
r i + 1 = f (r i ) .
Последовательности, составленные из таких чисел, образуют петли, то есть обязательно существует цикл, повторяющийся бесконечное число раз. Повторяющиеся циклы называются периодами .
Достоинством данных ГСЧ является быстродействие; генераторы практически не требуют ресурсов памяти, компактны. Недостатки: числа нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности квазислучайных чисел.
Рассмотрим несколько алгоритмических методов получения ГСЧ:
- метод серединных квадратов;
- метод серединных произведений;
- метод перемешивания;
- линейный конгруэнтный метод.
Метод серединных квадратов
Имеется некоторое четырехзначное число R 0 . Это число возводится в квадрат и заносится в R 1 . Далее из R 1 берется середина (четыре средних цифры) новое случайное число и записывается в R 0 . Затем процедура повторяется (см. рис. 22.6 ). Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij , а 0.ghij с приписанным слева нулем и десятичной точкой. Этот факт отражен как на рис. 22.6 , так и на последующих подобных рисунках.
 |
Недостатки метода: 1) если на некоторой итерации число R 0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R 0 ; 2) генератор будет повторять последовательность через M n шагов (в лучшем случае), где n разрядность числа R 0 , M основание системы счисления.
Для примера на рис. 22.6 : если число R 0 будет представлено в двоичной системе счисления, то последовательность псевдослучайных чисел повторится через 2 4 = 16 шагов. Заметим, что повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно.
Описанный выше способ был предложен Джоном фон Нейманом и относится к 1946 году. Поскольку этот способ оказался ненадежным, от него очень быстро отказались.
Метод серединных произведений
Число R 0 умножается на R 1 , из полученного результата R 2 извлекается середина R 2 * (это очередное случайное число) и умножается на R 1 . По этой схеме вычисляются все последующие случайные числа (см. рис. 22.7 ).
 |
Метод перемешивания
В методе перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R 0 . Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R 0 * . Точно так же, циклически сдвигая содержимое ячейки R 0 вправо на 1/4 длины ячейки, получаем второе число R 0 ** . Сумма чисел R 0 * и R 0 ** дает новое случайное число R 1 . Далее R 1 заносится в R 0 , и вся последовательность операций повторяется (см. рис. 22.8 ).
 |
Обратите внимание, что число, полученное в результате суммирования R 0 * и R 0 ** , может не уместиться полностью в ячейке R 1 . В этом случае от полученного числа должны быть отброшены лишние разряды. Поясним это для рис. 22.8 , где все ячейки представлены восемью двоичными разрядами. Пусть R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , тогда R 0 * + R 0 ** = 100110010 2 = 306 10 . Как видим, число 306 занимает 9 разрядов (в двоичной системе счисления), а ячейка R 1 (как и R 0 ) может вместить в себя максимум 8 разрядов. Поэтому перед занесением значения в R 1 необходимо убрать один «лишний», крайний левый бит из числа 306, в результате чего в R 1 пойдет уже не 306, а 00110010 2 = 50 10 . Также заметим, что в таких языках, как Паскаль, «урезание» лишних битов при переполнении ячейки производится автоматически в соответствии с заданным типом переменной.
Линейный конгруэнтный метод
Линейный конгруэнтный метод является одной из простейших и наиболее употребительных в настоящее время процедур, имитирующих случайные числа. В этом методе используется операция mod(x , y ) , возвращающая остаток от деления первого аргумента на второй. Каждое последующее случайное число рассчитывается на основе предыдущего случайного числа по следующей формуле:
r i + 1 = mod(k · r i + b , M ) .
Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью . Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом , а при b ≠ 0 смешанным конгруэнтным методом .
Для качественного генератора требуется подобрать подходящие коэффициенты. Необходимо, чтобы число M было довольно большим, так как период не может иметь больше M элементов. С другой стороны, деление, использующееся в этом методе, является довольно медленной операцией, поэтому для двоичной вычислительной машины логичным будет выбор M = 2 N , поскольку в этом случае нахождение остатка от деления сводится внутри ЭВМ к двоичной логической операции «AND». Также широко распространен выбор наибольшего простого числа M , меньшего, чем 2 N : в специальной литературе доказывается, что в этом случае младшие разряды получаемого случайного числа r i + 1 ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случайных чисел в целом. В качестве примера можно привести одно из чисел Мерсенна , равное 2 31 1 , и таким образом, M = 2 31 1 .
Одним из требований к линейным конгруэнтным последовательностям является как можно большая длина периода. Длина периода зависит от значений M , k и b . Теорема, которую мы приведем ниже, позволяет определить, возможно ли достижение периода максимальной длины для конкретных значений M , k и b .
Теорема . Линейная конгруэнтная последовательность, определенная числами M , k , b и r 0 , имеет период длиной M тогда и только тогда, когда:
- числа b и M взаимно простые;
- k 1 кратно p для каждого простого p , являющегося делителем M ;
- k 1 кратно 4, если M кратно 4.
Наконец, в заключение рассмотрим пару примеров использования линейного конгруэнтного метода для генерации случайных чисел.
Было установлено, что ряд псевдослучайных чисел, генерируемых на основе данных из примера 1, будет повторяться через каждые M /4 чисел. Число q задается произвольно перед началом вычислений, однако при этом следует иметь в виду, что ряд производит впечатление случайного при больших k (а значит, и q ). Результат можно несколько улучшить, если b нечетно и k = 1 + 4 · q в этом случае ряд будет повторяться через каждые M чисел. После долгих поисков k исследователи остановились на значениях 69069 и 71365 .
Генератор случайных чисел, использующий данные из примера 2, будет выдавать случайные неповторяющиеся числа с периодом, равным 7 миллионам.
Мультипликативный метод генерации псевдослучайных чисел был предложен Д. Г. Лехмером (D. H. Lehmer) в 1949 году.
Проверка качества работы генератора
От качества работы ГСЧ зависит качество работы всей системы и точность результатов. Поэтому случайная последовательность, порождаемая ГСЧ, должна удовлетворять целому ряду критериев.
Осуществляемые проверки бывают двух типов:
- проверки на равномерность распределения;
- проверки на статистическую независимость.
Проверки на равномерность распределения
1) ГСЧ должен выдавать близкие к следующим значения статистических параметров, характерных для равномерного случайного закона:
2) Частотный тест
Частотный тест позволяет выяснить, сколько чисел попало в интервал (m r σ r ; m r + σ r ) , то есть (0.5 0.2887; 0.5 + 0.2887) или, в конечном итоге, (0.2113; 0.7887) . Так как 0.7887 0.2113 = 0.5774 , заключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел (см. рис. 22.9 ).
в случае проверки его на частотный тест
Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5) , должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1) .
3) Проверка по критерию «хи-квадрат»
Критерий «хи-квадрат» (χ 2 -критерий) это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.
Для нашего случая проверка по критерию «хи-квадрат» позволит узнать, насколько созданный нами реальный ГСЧ близок к эталону ГСЧ , то есть удовлетворяет ли он требованию равномерного распределения или нет.
Частотная диаграмма эталонного ГСЧ представлена на рис. 22.10 . Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность p i попадания чисел в i -ый интервал (всего этих интервалов k ) равна p i = 1/k . И, таким образом, в каждый из k интервалов попадет ровно по p i · N чисел (N общее количество сгенерированных чисел).
Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по n i чисел (в сумме n 1 + n 2 + + n k = N ). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n i и «эталонным» p i · N . Сложим их, и в результате получим:
χ 2 эксп. = (n 1 p 1 · N ) 2 + (n 2 p 2 · N ) 2 + + (n k p k · N ) 2 .
Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ 2 эксп. ), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.
В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i -го слагаемого, поделив его на p i · N :
Наконец, запишем полученное выражение более компактно и упростим его:
Мы получили значение критерия «хи-квадрат» для экспериментальных данных.
В табл. 22.2 приведены теоретические значения «хи-квадрат» (χ 2 теор. ), где ν = N 1 это число степеней свободы, p это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или p это вероятность того, что экспериментальное значение χ 2 эксп. будет меньше табулированного (теоретического) χ 2 теор. или равно ему .
| Таблица 22.2. Некоторые процентные точки χ 2 -распределения |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| p = 1% | p = 5% | p = 25% | p = 50% | p = 75% | p = 95% | p = 99% | |
| ν = 1 | 0.00016 | 0.00393 | 0.1015 | 0.4549 | 1.323 | 3.841 | 6.635 |
| ν = 2 | 0.02010 | 0.1026 | 0.5754 | 1.386 | 2.773 | 5.991 | 9.210 |
| ν = 3 | 0.1148 | 0.3518 | 1.213 | 2.366 | 4.108 | 7.815 | 11.34 |
| ν = 4 | 0.2971 | 0.7107 | 1.923 | 3.357 | 5.385 | 9.488 | 13.28 |
| ν = 5 | 0.5543 | 1.1455 | 2.675 | 4.351 | 6.626 | 11.07 | 15.09 |
| ν = 6 | 0.8721 | 1.635 | 3.455 | 5.348 | 7.841 | 12.59 | 16.81 |
| ν = 7 | 1.239 | 2.167 | 4.255 | 6.346 | 9.037 | 14.07 | 18.48 |
| ν = 8 | 1.646 | 2.733 | 5.071 | 7.344 | 10.22 | 15.51 | 20.09 |
| ν = 9 | 2.088 | 3.325 | 5.899 | 8.343 | 11.39 | 16.92 | 21.67 |
| ν = 10 | 2.558 | 3.940 | 6.737 | 9.342 | 12.55 | 18.31 | 23.21 |
| ν = 11 | 3.053 | 4.575 | 7.584 | 10.34 | 13.70 | 19.68 | 24.72 |
| ν = 12 | 3.571 | 5.226 | 8.438 | 11.34 | 14.85 | 21.03 | 26.22 |
| ν = 15 | 5.229 | 7.261 | 11.04 | 14.34 | 18.25 | 25.00 | 30.58 |
| ν = 20 | 8.260 | 10.85 | 15.45 | 19.34 | 23.83 | 31.41 | 37.57 |
| ν = 30 | 14.95 | 18.49 | 24.48 | 29.34 | 34.80 | 43.77 | 50.89 |
| ν = 50 | 29.71 | 34.76 | 42.94 | 49.33 | 56.33 | 67.50 | 76.15 |
| ν > 30 | ν + sqrt(2ν ) · x p + 2/3 · x 2 p 2/3 + O (1/sqrt(ν )) | ||||||
| x p = | 2.33 | 1.64 | 0.674 | 0.00 | 0.674 | 1.64 | 2.33 |
Приемлемым считают p от 10% до 90% .
Если χ 2 эксп. много больше χ 2 теор. (то есть p велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения n i слишком далеко уходят от теоретических p i · N и не могут рассматриваться как случайные. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.
Еще Д. Кнут в своей книге «Искусство программирования» заметил, что иметь χ 2 эксп. маленьким тоже, в общем-то, нехорошо, хотя это и кажется, на первый взгляд, замечательно с точки зрения равномерности. Действительно, возьмите ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, они идеальны с точки зрения равномерности, и χ 2 эксп. будет практически нулевым, но вряд ли вы их признаете случайными.
Если χ 2 эксп. много меньше χ 2 теор. (то есть p мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения n i слишком близки к теоретическим p i · N и не могут рассматриваться как случайные.
А вот если χ 2 эксп. лежит в некотором диапазоне, между двумя значениями χ 2 теор. , которые соответствуют, например, p = 25% и p = 50%, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными.
При этом дополнительно надо иметь в виду, что все значения p i · N должны быть достаточно большими, например больше 5 (выяснено эмпирическим путем). Только тогда (при достаточно большой статистической выборке) условия проведения эксперимента можно считать удовлетворительными.
Итак, процедура проверки имеет следующий вид.
Проверки на статистическую независимость
1) Проверка на частоту появления цифры в последовательности
Рассмотрим пример. Случайное число 0.2463389991 состоит из цифр 2463389991, а число 0.5467766618 состоит из цифр 5467766618. Соединяя последовательности цифр, имеем: 24633899915467766618.
Понятно, что теоретическая вероятность p i выпадения i -ой цифры (от 0 до 9) равна 0.1.
2) Проверка появления серий из одинаковых цифр
Обозначим через n L число серий одинаковых подряд цифр длины L . Проверять надо все L от 1 до m , где m это заданное пользователем число: максимально встречающееся число одинаковых цифр в серии.
В примере «24633899915467766618» обнаружены 2 серии длиной в 2 (33 и 77), то есть n 2 = 2 и 2 серии длиной в 3 (999 и 666), то есть n 3 = 2 .
Вероятность появления серии длиной в L равна: p L = 9 · 10 L (теоретическая). То есть вероятность появления серии длиной в один символ равна: p 1 = 0.9 (теоретическая). Вероятность появления серии длиной в два символа равна: p 2 = 0.09 (теоретическая). Вероятность появления серии длиной в три символа равна: p 3 = 0.009 (теоретическая).
Например, вероятность появления серии длиной в один символ равна p L = 0.9 , так как всего может встретиться один символ из 10, а всего символов 9 (ноль не считается). А вероятность того, что подряд встретится два одинаковых символа «XX» равна 0.1 · 0.1 · 9, то есть вероятность 0.1 того, что в первой позиции появится символ «X», умножается на вероятность 0.1 того, что во второй позиции появится такой же символ «X» и умножается на количество таких комбинаций 9.
Частость появления серий подсчитывается по ранее разобранной нами формуле «хи-квадрат» с использованием значений p L .
Примечание: генератор может быть проверен многократно, однако проверки не обладают свойством полноты и не гарантируют, что генератор выдает случайные числа. Например, генератор, выдающий последовательность 12345678912345 , при проверках будет считаться идеальным, что, очевидно, не совсем так.
В заключение отметим, что третья глава книги Дональда Э. Кнута «Искусство программирования» (том 2) полностью посвящена изучению случайных чисел. В ней изучаются различные методы генерирования случайных чисел, статистические критерии случайности, а также преобразование равномерно распределенных случайных чисел в другие типы случайных величин. Изложению этого материала уделено более двухсот страниц.