Введение
В практике моделирования систем наиболее часто приходится иметь дело с объектами, которые в процессе своего функционирования содержат элементы случайности событий внешней среды. К примерам систем, характеризующихся случайными параметрами, можно отнести системы связи, у которых характеристики канала связи меняются случайным образом, а также локационные системы обнаружения отражений от целей на фоне случайных помех. Широкие возможности для моделирования с использованием современных вычислительных систем открывают датчики случайных чисел.
Датчики случайных чисел применяются для имитации реальных условий функционирования систем автоматического управления, для решения задач методом статистических испытаний, для моделирования случайных изменений параметров производства в автоматизированных системах управления и т. д. Кроме непосредственного использования в статистических моделях, равномерно распределённые случайные числа, вырабатываемые датчиком случайныхчисел, являются основой для формирования числовых последовательностей с заданным законом распределения.
Цель работы - овладение навыками алгоритмизации и программирования задач с использованием датчиков случайных чисел, способами получения случайных чисел с различными законами распределения, навыками оценки качества псевдослучайных чисел и их соответствия их выполняемым задачам.
Для чего нужны случайные числа?
Для чего нужны «случайно выбранные» числа? Они, оказывается полезны для самых различных целей. Вот некоторые примеры:
1. Моделирование. Когда с помощью вычислительной машины моделируются природные явления, случайные числа позволяют приблизить модель к реальности.
2. Выборка. Часто бывает, что проверка всех возможных вариантов практически не осуществима, тогда на некоторые вопросы позволяет получить ответы случайная выборка.
3. Численный анализ. Для решения сложных задач вычислительной математики была разработана остроумная техника, использующая случайные числа.
4. Программирование для вычислительных машин. Случайные значения служат хорошим источником данных при испытании эффективности различных алгоритмов для вычислительных машин.
5. Принятие решений.
6. Развлечения.
И все-таки, что же такое «случайность»? в некотором смысле такого объекта, как случайное число, просто нет. Скажем, двойка – это случайное число? Скорее это последовательность независимых случайных чисел с определенным законом распределения, и это означает, грубо говоря, что каждое число было получено самым произвольным образом, без всякой связи с другими членами последовательности, и что у него есть определенная вероятность оказаться в любом заданном интервале.
Равномерным называется такое распределение, при котором каждое возможное число равновероятно. Каждая из десяти цифр от 0 до 9 составляют примерно одну десятую часть всех цифр во всякой случайной (равномерной) последовательности цифр. Любая заданная пара двух соседних цифр должна составлять примерно одну сотую часть всех пар, встречающихся в последовательности и т. д. Тем не менее, если мы рассмотрим какую-нибудь конкретную случайную последовательность из миллиона цифр, в ней совсем не обязательно окажется ровно 100 000 нулей, 100 000 единиц и т. д. В действительности вероятность такого события очень мала. Закономерность же выполняется в среднем для последовательности таких последовательностей.
Любая заданная последовательность столь же вероятна, как и последовательность, состоящая из одних нулей. Более того, допустим, что мы выбираем случайным образом последовательность из миллиона цифр. Пусть оказалось, что первые 999 999 из них равны нулю. И в этом случае вероятность того, что последняя цифра будет нулем, все еще в точности равна одной десятой, если выборка действительно случайная.
Немного истории
Раньше ученые, нуждавшиеся для своей работы в случайных числах, раскладывали карты, бросали кости или вытаскивали шары из урны, которую предварительно «как следует трясли». В 1927 году Л. Типпет опубликовал таблицы, содержащие свыше 40 000 случайных цифр, «произвольно взятых из отчетов о переписи». Позже были сконструированы специальные машины, механически вырабатывающие случайные числа. Первую такую машину в 1939 году использовали М. Дж. Кендалл и Б. Бэбингтон-Смит при создании таблиц, включающих 100 тысяч случайных цифр. В 1935 году компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных цифр, полученных другой такой машиной. Известная машина ERNIE, вырабатывающая случайные числа, определяет выигравшие номера в Британской лотерее. Вскоре после создания вычислительных машин начались поиски эффективных методов получения случайных чисел, пригодных для использования в программах. В принципе можно работать и с таблицами, однако этот метод имеет ограничения, связанные с конечным объемом памяти машин и затратами времени для ввода чисел в машину в том случае, когда таблица оказывается слишком короткой. Кроме того, довольно неприятно готовить таблицы заранее, да и вообще иметь с ними дело. Можно присоединить к ЭВМ машину типа ERNIE, но и этот путь оказывается неудовлетворительным, потому что при отладке программы невозможно воспроизвести вторично вычисления, сделанные ранее.
Несовершенство всех этих методов пробудило интерес к получению случайных чисел с помощью арифметических операций вычислительной машины. Первым такой подход в 1946 году предложил Джон фон Нейман, использовавший метод «середины квадрата». Идея заключается в том, что предыдущее число возводится в квадрат, а затем из результата извлекаются средние цифры. Пусть, например, мы вырабатываем десятизначные числа и допустим, что предыдущее число было равно 5772156649; возведя его в квадрат, получим 33317792380594909201, и поэтому следующее число равно 7923805949.
Метод вызывает довольно очевидное возражение. Как может быть случайной выработанная таким способом последовательность, если каждый ее член полностью определен своим предшественником? Ответ заключается в том, что эта последовательность не случайна, но выглядит как случайная. В типичных приложениях обычно не имеет значения, как связаны друг с другом два последующих числа последовательности; таким образом, неслучайный характер последовательности не является нежелательным. Интуитивно метод середины квадрата должен довольно хорошо «перемешивать» предыдущее число.
Однако первоначальный «метод середины квадрата» фон Неймана оказался сравнительно скудным источником случайных чисел. Недостаток его заключается в том, что последовательности имеют тенденцию превращаться в короткие циклы повторяющихся элементов. Например, если какой-нибудь член последовательности окажется равным нулю, все последующие члены также будут нулями. В начале пятидесятых годов некоторые ученые проводили эксперименты с методом середины квадрата. Дж. Э. Форсайт, работавший с четырехзначными (а не с десятичными) числами, проверил 16 чисел в качестве начальных значений последовательностей. Оказалось, что 12 из них порождали последовательности, оканчивающиеся циклом 6100, 2100, 4100, 8100, 6100, …, а две последовательности выродились в нуль. Обширные эксперименты по исследованию метода середины квадрата провел Н. Метрополис, оперировавший главным образом двоичными числами. Работая с 20-разрядными числами, он показал, что существует тринадцать различных циклов, в которые могут выродиться последовательности; длина периода самого большого из них равна 142. Как только последовательность вырождается в нуль, довольно легко начать выработку случайных чисел заново. Гораздо трудней бороться с длинными циклами. Все же Р. Флойд предложил остроумный метод, позволяющий зарегистрировать возникновение цикла в последовательности.
Метод Флойда требует небольшой памяти машины, увеличивает время выработки случайного числа всего в три раза и сразу же сигнализирует, как только в последовательности появляется встречавшееся ранее число.
С другой стороны, отметим, что, работая с 38-разрядными двоичными числами, Н. Метрополис обнаружил последовательность, состоящую из 750 000 членов, отличающихся друг от друга. Статистические тесты подтвердили случайный характер полученной последовательности из 750 000 × 38 битов. Это подтверждает, что, применяя метод середины квадрата, можно получить полезные результаты.
Тем не менее без предварительных трудоемких вычислений ему не стоит излишне доверять.
Многие датчики случайных чисел, популярные сейчас, недостаточно хороши. Среди пользователей наметилась тенденция избегать их изучения. Довольно часто какой-нибудь старый сравнительно неудовлетворительный метод передается от одного программиста к другому в слепую, и сегодняшний пользователь уже ничего не знает об его недостатках.
Получения последовательности
Так как в вычислительной машине действительное число всегда представляется с ограниченной точностью, фактически мы будем генерировать целые числа Xn в интервале от 0 до некоторого m. Тогда дробь Un=Xn/m, где Un случайные действительные числа, попадает в интервал от 0 до 1. Обычно m на единицу больше максимального числа, которое можно записать в машинном слове. Поэтому Xn можно интерпретировать как целое содержимое машинного слова с десятичной запятой, расположенной справа, а Un можно считать дробью, содержащейся в том же слове, с запятой в крайней левой позиции.
Наилучшие из известных сегодня датчиков случайных чисел представляют собой частные случаи следующей схемы, предложенной Д. Х. Лемером в 1948 году. Выбираем четыре «магических числа»:
x0 - начальное значение; x0≥0;
a - множитель; a≥0;
c - приращение; c≥0;
m - модуль; m>x0, m>a, m>c.
Тогда искомая последовательность случайных чисел <Xn> получается из соотношения Xn+1=(aXn+c) modm, n≥0. Она называется линейной конгруэнтной последовательностью. Например, при Xn= a= c=7, m=10 последовательность выглядит так: 7, 6, 9, 0, 7, 6, 9, 0, … .