Датчики случайных и псевдослучайных чисел

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

Считается, что первая попытка создать физический датчик случайных чисел относится к 3500 году до н.э. и связана с настольной игрой сенет, древнеегипетским светским развлечением. Согласно современным реконструкциям правил игры для определения набранного каждым игроком количества очков и очередности ходов в этой игре использовались четыре плоские палочки, одна сторона которых была белой, другая — черной. Палочки бросали одновременно и в зависимости от выпавшей комбинации цветов определяли дополнительные возможности игроков. В начале XX в. последовательности случайных чисел имитировались вручную — с помощью бросаний монеты или игральной кости, раскладывания игральных карт, рулетки, извлечения шаров из урны и т. д. Современные физические (аппаратные) датчики представляют собой специальные устройства, генерирующие случайные числа на основе преобразования случайных шумов естественного или искусственного происхождения (тепловой шум, дробовой эффект в электронных лампах, радиоактивный распад и т. д.). Например, машина ERNIE 4 (electronic random number indicator equipment),.

• 1 Иногда, хотя и редко, к стандартным относят распределение, задаваемое таблицей 0 1 … 8 9
• 0,1 0,1 … 0,1 0,1/ с помощью которой определяют выигравшие номера в ежемесячной Британской лотерее, в качестве источника случайных величин использует тепловой шум транзисторов. У физического способа получения последовательности случайных чисел есть особенности, которые для имитационной модели являются недостатками. К ним относятся, в первую очередь, необходимость специальных мер по обеспечению стабильности источника сигнала, преобразуемого в случайные числа, и невозможность воспроизведения полученной последовательности случайных чисел.

Таблицы случайных чисел лишены указанных недостатков. Поясним, что понимается под таблицей случайных чисел. Предположим, что мы осуществили N независимых опытов, в результате которых получили случайные цифры а, а₂, осдг. Запись этих цифр (в порядке появления и в форме прямоугольной таблицы) даст так называемую таблицу случайных цифр. Используется она следующим образом. В ходе расчетов нам может потребоваться либо случайная цифра, либо случайное число. Если потребуется случайная цифра, то мы можем взять любую цифру из этой таблицы. То же относится к случаю целого случайного числа — для каждого разряда можно выбрать любую цифру. Если нам понадобится случайное число 0 < 5 < 1, то можно взять из таблицы k очередных цифр сц, а₂, ос/, и считать, что 8 = (Хоцо^.-.о^. При этом в случае «идеальной» таблицы случайных цифр выбирать цифры из нее можно случайным образом, можно подряд, можно использовать любой алгоритм выбора, не зависящий от значений цифр таблицы, начинать с любого места таблицы, читать в любом направлении.

Первые таблицы случайных чисел были получены с помощью рулеток. Такие таблицы несколько раз издавались в виде книг. Одна из самых известных таблиц^[1], опубликованная в 1927 г., содержала свыше 40 000 случайных цифр, «произвольно взятых из отчетов о переписи».

Историческая справка Леонард Типпет (Leonard Henry Caleb Tippett, 1902—1985) — английский статистик, ученик К. Пирсона и Р. Фишера. В 1965—1966 гг. — президент Королевского статистического общества. С его именем связаны некоторые важные результаты в теории экстремальных значений, например распределение Фишера — Типпета и теорема Фишера — Типпета — Гнеденко.

Позже были сконструированы специальные устройства (машины), механически вырабатывающие случайные числа. Первую такую машину в 1939 г. использовали М. Дж. Кендалл и Б. Бэбингтон-Смит при создании таблиц, включающих 100 тыс. случайных цифр. В 1955 г. компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных цифр, полученных другой машиной такого типа. Практическое применение таблиц случайных чисел ограничивается в настоящее время, как правило, задачами, в которых используются методы случайного отбора.

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

Это интересно В России действует ГОСТ 18 321–73 (СТ СЭВ 1934—79), устанавливающий правила отбора единиц продукции в выборку при проведении статистического приемочного контроля качества, статистических методов анализа и регулирования технологических процессов для всех видов штучной продукции производственно-технического назначения и товаров народного потребления. В нем, в частности, указывается, что при отборе единиц продукции в выборку «используют таблицы случайных чисел по СТ СЭВ 546—77».

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

Алгоритмов получения последовательностей псевдослучайных чисел существует много, реализации таких алгоритмов, называемые датчиками (генераторами) псевдослучайных чисел, довольно подробно описаны в специальной литературе^[2]. Укажем несколько наиболее известных алгоритмов.

• [1] Tippett L. Random sampling numbers. London: Cambridge University Press, 1927.
• [2] См.: Кнут Д. Э. Искусство программирования. 3-е изд. М.: Вильямс, 2000. Т. 2. Гл. 3. Случайные числа.