Эта запись означает, что

В [40] доказана теорема о независимости случайных цифр в случай­ном числе, которая формулируется следующим образом.

Десятичные цифры h₁,h₂, …,h_k, … случайного числа x_k представ­ляют собой независимые случайные цифры. Обратно, если h₁,h₂, …, h_k, … - независимые случайных цифры, то формула (4.1) дает случайное число.

В вычислительных процессах всегда используют числа с конеч­ным количеством десятичных знаков, поэтому вместо случайных чи­сел x_i употребляют конечные десятичные дроби x_i=0, h₁,h₂, …, h_k. Принято считать, что здесь имеют место ошибки округле­ния.

Предположим, что, используя некоторый механизм (игральную кость, рулетку и т.п.), мы осуществили ряд опытов, в результате ко­торых получили N случайных цифр, h₁,h₂, …, h_N. Записав эти цифры в таблицу, получим то, что называется таблицей случай­ных цифр (приложение 2). Это есть первый способ получения первичных случайных чисел.

Способ употребления такой таблицы прост. Если в ходе реше­ния некоторой задачи нам потребуется случайная цифра h_j, то мы можем взять любую цифру h_k из этой таблицы. Если нам потребуется случайное число x_j, то мы можем по произвольному алгоритму вы­брать из таблицы n очередных цифр и считать, что

x_i = 0, h₁, …, h_n.

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

Пример 4.1. Используя таблицу (см. приложение 2) равномер­но распределенных случайных цифр, получить пять случайных цифр.

Решение 4.1.а. Выбираем наугад строку таблицы. Пусть это будет 5-я строка. Выписываем из нее 5 цифр: 1,2,8,0,7.

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

Пусть мы выбрали 9-ю строку и 10-ю колонку. Тогда получаем следующие цифры: 5, 0, 8, 4, 9.

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

Решение 4.2.а. Выбираем наугад колонку и выписываем из нее, двигаясь вниз, 12 цифр. Пусть мы выберем, первую колонку и тогда получим цифры: 1,3,0,9,1,6,3,8,6,7,9,1. Сгруппируем их в четыре группы (заметим, что это можно сделать по-разному): 130, 916, 386, 791.

Решение 4.2.б. Воспользовавшись ходом шахматного коня и начиная с первой цифры таблиц, получим следующие четыре трехзна­чных числа: 180, 276, 299, 379.

Второй способ получения первичных случайных чисел заключается в использовании технических устройств - датчиков или генераторов случайных чисел. В качестве таких могут применяться механические (рулетка, кубик, и т.п.), электронные (резисторы, ди­оды, электронные лампы и т.п.), радиоактивные и другие типы устройств. На выбор конкретного типа устройства оказывают влия­ние ряд факторов: стабильность параметров генерируемых сигналов, взаимо­за­меняемость элементов, срок их службы, условия эксплуатации, простота источника преобразований сигнала и т.п. После оп­ределе­ния типа источника требуется сконструировать пре­образователь случайного сигнала, основное назначение кото­рого состоит в преобразовании полученного первичного случайного сигнала в форму, пригодную для использования в вычислительном устройстве. Приведем пример такого генератора (рис. 4.6) – [43]. Пусть мы имеем K генераторов стандартных импульсов ГИ-j, которые воспроизводят детерминированные по свойствам импульсы. В силу того, что каждый из генераторов не явля ется идеальным устрой­ством, сигналы на их выходах C_j будут иметь случайные от­клонения от идеального. Эти отклонения не превышают допустимых. Объединяя все сигна­лы C_j элементом ИЛИ, будем получать выходной сигнал U, который по своей сути (в силу неидеальности генераторов) будет пред­став­лять собой последовательность импульсов со случайными параметра­ми, например, амплитудой.

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

Числа x₁, x₂, …, x_n, …, которые вычисляются по какой-либо формуле и могут быть использованы вместо случайных чисел при решении некоторых задач, называются псевдослучайными числа­ми.

Большинство алгоритмов, используемых на практике, представля­ют собой рекуррентные формулы следующего вида:

x _n+1=F(x _n), (4.2)

где x₀ - задано.

Часто в качестве функции F выбирают следующую функцию x _i+1=[Ax_i], где [] - знак целой части числа, а A- некоторый множитель(A>>1).

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

Вместо формулы (4.2) можно попытаться использовать для получения пос­ледо­вательностей псевдослучайных чисел более сложные рекуррент­ные формулы

x_n+1=F(x_n, x_n+1, …, x_n-r+1),

считая, что начальные значения x₀, x₁, …, x_r-1 заданы. В [40] при­ведены алгоритмы, основанные на подобных формулах.

В качестве конкретных алгоритмов вида (4.2) можно назвать ме­тоды усечения, вычетов, перемешивания и т.д.

Метод усечения. В качестве рекуррентного процесса берется произвольное число x₀, состоящее из 2n двоичных цифр. Величина x₀ возводится в квадрат (состоящий уже из 4n цифр) и выбирает число x₁ из 2n средних двоичных цифр (от n+1-й до 2n -й). В дальнейшем процесс повторяется в той же последовательности.

Такой рекуррентный процесс не дает удовлетворительной (в смысле некоррелированности) последовательности случайных разря­дов, а распределение полученных этим способом псевдослучайных чисел отклоняется от равномерного.

Пример 4.3. Пусть x₀=1011. Построить последовательность из трех псевдослучайных чисел методом усечения.

Решение 4.3. x =(1011) =01111001. Отсюда x₁=1110, x =(1110) =11000100. Отсюда x =0001, x =(0001) =00000001. Отсюда x₃=0000. Имеем последова­тель­ность: 1110, 0001, 0000.

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

Способ произведений. Значительно лучшие ре­зультаты дает следующее видоизменение метода усечений: выбирает­ся произвольная пара чисел x₀ и x₁; составляется их произведение и его средние цифры используются в качестве x₂.

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

Пример 4.4. Пусть x₀=24 и x₁=31. Построить пос­ледовательность из трех псевдослучайных чисел методом произве­дений.

Решение 4.4. x₀x₁=0744. x₂=74. x₁x₂=2294. Тогда x₃=29. x₂x₃=2146. Отсюда x₄=14. Таким образом, по­лучена последовательность: 74, 29, 14.

4.2.2.3. P-методы.

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

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

К числу точных Р-методов относятся метод обратных функций (метод Н.В.Смирнова) и специальные методы, к приближен­ным - метод Неймана и метод кусочной аппроксимации (метод Н.П. Бусленко) [12].

В дальнейшем будем использовать следующие обозначения:

h - случайное некоррелированное число, равномерно рас­пределенное в интервале [0,1];

x - случайное число с одномерным законом распределе­ния вероятностей, который требуется получить;

d - случайное число с гауссовским (нормальным) зако­ном распределения вероятностей.