11.6.   СЛУЧАЙНЫЕ ЧИСЛА

До сих пор мы со спокойной совестью пользовались генератором случайных чисел, предусмотренным нашим языком программирования, для получения в приложениях метода Моите-Карло требуемых «случайных» чисел. В принципе можно было бы генерировать эти числа, используя какой-нибудь случайный физический процесс, как, например, радиоактивный распад. Однако такая последовательность чисел не воспроизводима и, следовательно, не может использоваться для проверки наших программ. Поэтому иа практике пользуются цифровым компьютером, который является полностью детерминированной машиной, и получают последовательности «случайных» чисел по вполне конкретному алгоритму. Конечно, эти последовательности не являются истинно случайными, и в действительности их часто называют псевдослучайными. Тем не менее мы называем последовательности случайными, если они имеют равномерное распределение и удовлетворяют всем нашим критериям случайности. В дальнейшем мы увидим, что фактически многие из критериев случайности можно сформулировать на языке случайного блуждания.

Мы изложим кратко только некоторые свойства хорошего генератора случайных чисел. В большинстве генераторов случайных чисел получается последовательность, в которой каждое число используется для нахождения последующего по вполне определенному алгоритму. Таким образом, последовательность определяется начальным значением — первым ее числом. Все генераторы случайных чисел дают последовательность, повторяющуюся после некоторого количества членов, называемого периодом. Во всех обычных методах максимально возможный период связан с конечной длиной машинного «слова». В основе наиболее распространенного генератора случайных чисел лежит метод вычетов, или линейный конгруэнтный метод. А именно, если задано начальное число *0, то каждое число последовательности определяется «отображением»

где а, с и ш —натуральные числа. (Обозначение у = z mod m означает, что пг вычитается из z до тех пор, пока не получится 0 £ у £ т. Например, 412 mod 50 равно 12.) Отображение (11.38) характеризуется тремя параметрами: множителем а, инкрементом с и модулем т. Поскольку т является наибольшим целым числом, генерируемым с помощью (11.38), наибольший возможный период равен т. Однако в общем случае период зависит от всех трех  параметров.   Например,   если  а = 3,   с =

= 4, т = 32 и х0 - 1, то с помощью соотношения (11.38) генерируется последовательность 1, 7, 25, 15, 17, 23, 9, 31, 1, 7, 25, ... и период равен 8, а не максимально возможному значению 32. Если мы тщательно выберем а, с и т так, чтобы получался максимальный период, то в последовательности будут встречаться все целые числа от 0 до т-\. Поскольку обычно нужны случайные числа на отрезке [0,1], а ие случайные целые числа, то генераторы случайных чисел выдают, как правило, отношение *п+1/т, которое всегда меньше единицы. (Заметим, что хп = 0 появляется в последовательности один раз.)

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

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