§ 4. Статистическая проверка качества последовательности случайных чисел

Рекомендованные выше способы формирования последовательностей случайных (или псевдослучайных) чисел основываются на предположениях, которые соответствуют реализации заданного закона распределения лишь приближенно. Поэтому закон распределения фактически получаемых случайных чисел в принципе отличается от квазиравномерного. Однако практически можно с этим не считаться, если отклонения закона распределения от квазиравномерного оказываются несущественными.

В настоящем параграфе будут рассмотрены способы статистического контроля, при помощи которых можно оценить практическую пригодность вырабатываемых последовательностей случайных чисел для решения задач методом статистических испытаний.

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

Выдвигается гипотеза о том, что закон распределения случайных чисел, получаемых данным способом, является квазиравномерным. При этом предположении

вычисляются значения некоторых параметров распределения и сравниваются с оценками для этих параметров, полученными в результате обработки фактически формируемых случайных чисел.

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

Для этой цели используются методы статистической проверки гипотез, основанные на распределениях некоторых функций от выборочных характеристик (см. например, [5]).

Основным контролируемым параметром для квазиравномерного закона распределения является вероятность того, что выбранное наудачу случайное число равно

При использовании -разрядных случайных чисел мы будем иметь несовпадающих возможных значений с вероятностями

В качестве оценки для вероятности р, принимается частота

фактического появления возможного значения при испытаниях.

Известно, что величина

имеет -распределениес степенями свободы.

Задаваясь определенным уровнем значимости из таблиц -распределения можно определить — процентный предел Если вычисленное по данным выборки значение превышает будем считать, что выборочные данные не согласуются с выдвинутой гипотезой. В этом случае гипотеза о квазиравномерном

распределении исходной совокупности случайных чисел должна быть отвергнута.

Однако, как правило, одной лишь проверкой соответствия частоты вероятности ограничиться нельзя. Необходимо обратить внимание также на «случайность» следования возможных значений случайных чисел при том или другом способе их получения. Для простоты проверку случайности последовательности удобно проводить по отношению к знакам нуль и единица для каждого разряда случайного числа.

Рассмотрим последовательность, в которой имеет место случайное чередование нулей и единиц. Каждую подпоследовательность, содержащую только (следующие друг за другом) нули или только единицы, будем называть серией, а количество элементов, входящих в серию, — ее длиной.

Пусть где равно нулю или единице, — число серий из элементов длины Тогда

где — число элементов в последовательности, будет числом серий из элементов длины не менее Очевидно, что

является числом серий длины не менее общим числом серий в последовательности.

Известно, что при рассматриваемых здесь условиях величина имеет при асимптотически нормальное распределение с математическим ожиданием и дисперсиеи Этот факт можно использовать для проверки гипотезы о случайности последовательности путем сравнения выборочного значения с величиной соответствующей заданному уровню значимости.

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

При больших эта вероятность имеет вид

В ряде случаев целесообразно провести статистическую проверку гипотезы о независимости последовательностей знаков между отдельными разрядами двоичного числа. Для этого обычно используется -критерий по отношению к величине, зависящей от выборочного значения количества нулей и единиц в соответствующих разрядах (см. [5]).

Соображения о статистической проверке качества исходной совокупности случайных чисел рассматриваются также в [10].