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

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

а) б) в)

Рис. 2. Области, из которых выбираются точки

Для получения равномерно распределенных случайных чисел из прямоугольника, стороны которого параллельны осям координат (см. рис.2, а), достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужным интервалам и использовать как координаты точки:

,

где uj - равномерно распределенное случайное число из отрезка [0, m].

Окружность можно представить одномерным множеством точек с угловой координатой ?, принимающей значения на интервале (0, 2?). Таким образом, декартовы координаты очередной точки можно вычислить следующим образом:

.

где uj - равномерно распределенное случайное число из интервала (0, m); r - радиус окружности.

В случае круга первое, что приходит в голову - воспользоваться полярной системой координат (?, ?), в которой данное множество фактически представляет собой прямоугольник (а для него способ генерации чисел известен). Однако при переходе от полярных координат к декартовым нарушается распределение случайных чисел: оно становится неравномерным; плотность распределения в центре круга выше, чем по краям.

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

Воспользуемся полярной системой координат для генерирования точек. При этом будем выбирать угол ? равномерно распределенным на интервале (0; 2?), а распределение ? построим следующим образом:

,

где x - равномерно распределенная на отрезке [0; 1] случайная величина. Можно показать, что при таком способе формирования координат случайные точки будут равномерно распределены по всей площади круга.

Помимо выбора из произвольного множества, часто требуется формировать числа с распределением, отличным от равномерного. Распределение обычно задается функцией плотности распределения f(x) либо функцией распределения F(x). Функция распределения в произвольной точке x показывает вероятность того, что случайная величина X окажется меньше данного значения x:

F(x)=P (X<x).

Функция плотности распределения представляет собой производную F(x):

.

Функция F(x) для любой случайной величины является неубывающей на всем интервале (-?; +?), стремится к 0 при x> -? и к 1 при x> +?. Для получения случайных чисел с заданным распределением F(x) необходимо найти функцию, обратную к F(x), т.е. такую функцию G, что для всех y=F(x) выполняется G(y)=x. Это можно пояснить следующим образом. Предположим, что мы многократно выбираем число y, равномерно распределенное на интервале [0; 1]; каждому y мы ставим в соответствие некоторое x=G(y). Выбору 50000 игреков соответствует выбор 50000 иксов. Таким образом, доля выбранных y, лежащих между двумя фиксированными значениями, скажем y1 и y2, в точности равна доле x, лежащих в интервале [x1; x2]. Но вероятность первого из названных событий равна | y2 - y1 |, если y распределено равномерно; следовательно, верна цепочка равенств:

доля чисел в интервале [x1; x2] = доля чисел в интервале [y1; y2] =  y2 - y1 = F(x2) - F(x1) = ,

которая и показывает, что в случае равномерного распределения игреков x имеет распределение с плотностью f(?). Сложной проблемой в этом подходе является достаточно быстрое и точное формирование обратной функции распределения G(y).

Рассмотрим в качестве примера получение случайного числа с экспоненциальным распределением. Это распределение характеризуется одним параметром ?>0 и имеет следующие функции распределения и плотности распределения:

, x?0;

.

Для этого распределения легко получить F-1 (y), т.е. разрешить уравнение F(x)=y. Решение имеет вид

.

Для получения x с искомым распределением нужно сгенерировать y, равномерно распределенное на (0,1), и применить эту формулу. Если говорить о практической стороне дела, то существуют более эффективные способы, в которых не используется медленная операция вычисления логарифма для каждого случайного числа. Данный способ продемонстрирован лишь как пример более общего подхода с использованием обратной функции распределения.

6. Тестирование ГСЧ

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

Проверка равномерности последовательностей псевдослучайных равномерно распределенных чисел {xi} может быть выполнена по гистограмме с присваиванием косвенных признаков. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел (0, 1). Затем интервал (0, 1) разбивается на m равных частей, тогда при генерации последовательности {xi} каждое из чисел xi c вероятностью , , попадет в один из подынтервалов. Всего в каждый j_й подынтервал попадает Ni чисел последовательности {xi}, , причём . Относительная частота попадания случайных чисел из последовательности {xi} в каждый из подынтервалов будет равна Nj/N. Очевидно, что если числа xi принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис.3, а) приближается к теоретической прямой 1/m. Оценка степени приближения, т.е. равномерности последовательности {xi}, может быть проведена с использованием критериев согласия.

Рис. 3. Проверка равномерности последовательности

Существуют и другие способы проверки равномерности распределения.

Проверка стохастичности последовательности псевдослучайных чисел {xi} наиболее часто проводится методами комбинаций и серий. Сущность метода сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе Xi.

Теоретически закон появления j единиц в l разрядах двоичного числа Xi описывается, исходя из независимости отдельных разрядов, биномиальным законом распределения:

,

где P (j, l) - вероятность появления j единиц в l разрядах числа Xi;

p(1) = p(0) = 0,5 - вероятность появления единицы и нуля в любом разряде числа Xi;

.

Тогда при фиксированной точке выборки N теоретически ожидаемое число появления случайных чисел Xi с j единицами в проверяемых l разрядах будет равно .

После нахождения теоретических и экспериментальных вероятностей P (j, l) или чисел nj при различных значениях l  n гипотеза о стохастичности проверяется с использованием критериев согласия, которые подробно рассматриваются в курсе математической статистики.

При анализе стохастичности последовательности чисел {xi} методом серий последовательность разбивается на элементы первого и второго рода (a и b), т.е.

где 0 < p < 1.

Серией называется отрезок последовательности {xi}, состоящий из идущих друг за другом элементов одного и того же рода. Число элементов в отрезке (a или b) называется длиной серии.

После разбиения последовательности {xi} на серии первого и второго рода будем иметь, например, серию вида

…..aabbbbaaabbbaabbab….

Так как случайные числа a и b в данной последовательности независимы и принадлежат последовательности {xi}, равномерно распределённой на интервале (0, 1), то теоретическая вероятность появления серии длиной j в N опытах (под опытом здесь понимается генерация числа xi и проверка условия xi < p) определится формулой Бернулли:

, , .

В случае экспериментальной проверки оцениваются частоты появления серий длиной j. В результате получаются экспериментальная и теоретическая зависимости P (j, l), сходимость которых проверяется по известным критериям, причем проверку целесообразно проводить при разных значениях l и р, 0 < р < 1.

7. Генератор случайных чисел в Borland C++

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

В Borland C++ (как и во многих других реализациях C/C++) используется линейный конгруэнтный ГСЧ. Длина периода этого ГСЧ составляет 232 числа.

Для работы с ГСЧ в языке C предусмотрены следующие функции:

1) int rand()

Возвращает случайное целое число в диапазоне от 0 до RAND_MAX, где RAND_MAX - некоторая константа, зависящая от конкретной реализации ГСЧ. В Borland C++ значение RAND_MAX=32767.

2) int random (int max)

Возвращает случайное целое число в диапазоне от 0 до max_1.

3) void srand (unsigned seed)

Устанавливает новое зерно ГСЧ. Обычно используется для установки известного начального значения x0 при отладке программы.

4) void randomize()

Устанавливает начальное значение, полученное из текущего системного времени путем путем преобразования его в целое число. Обычно используется для сброса ГСЧ в начале программы с целью предотвращения генерирования одних и тех же последовательностей. Не рекомендуется использовать в процессе отладки, т. к. последовательность, выбранную вызовом randomize(), сложно воспроизвести. Кроме того, не рекомендуется вызывать слишком часто или через фиксированные промежутки времени, т. к. это снизит качество («случайность») генерируемых последовательностей.

8. Практические задания

8.1 Случайные числа в заданном диапазоне

Выдайте на экран 10 случайных равномерно распределенных чисел в диапазоне:

От 3 до 12, целые.

Из множества {-3, 0, 6, 9, 12, 15}.

От 3 до 12, вещественные.

От -2,3 до 10,7 с шагом 0,1.

Из множества {-30; 10; 63; 59; 120; 175}.

Из множества {1; 0,1; 0,01; …; 10-15}.

8.2 Двумерные случайные величины

Написать функцию генерации случайной точки в двумерном круге с параметрами r, x0, y0.

8.3 Генерация одномерной случайной величины

Постройте случайную последовательность плотностью распределения которой принимает значение 1/4 на отрезке [0; 2] и 1/2 на отрезке [4; 5].

8.4 Оценить вероятность

В урне 5 белых, 10 черных и 15 красных шаров. Вынимают три шара. Оцените программным способом вероятность того, что все шары разного цвета.

8.5 Медианы треугольника

Известно, что две медианы в треугольнике пересекаются в точке, которая делит их в отношении 2:1. Используя ГСЧ и векторную алгебру, докажите этот факт.

9. Лабораторные задания

9.1 ГСЧ фон Неймана

Реализуйте программно метод средин квадратов для двоичных 8-разрядных чисел. Покажите, что ГСЧ зацикливается после прихода в ноль.

Замечания:

Квадрат числа будет занимать 16 бит, что может вызвать переполнение знакового типа int. Рекомендуется использовать типы unsigned int или long для промежуточных вычислений.

Для выделения средней части следует использовать операции сдвига и преобразования типа (либо побитового «И»).

9.2 Случайная матрица

Заполните динамическую матрицу 40?50 целыми случайными числами от -3 до 2. Найдите среднее арифметическое всех элементов этой матрицы. Зная точное значение данной величины (), вычислите ее относительную погрешность (в процентах) по формуле:

100% * (ТочноеЗначение - ПриблЗначение) / ДлинаДиапазона

Замечания:

Количество целых чисел в диапазоне от -3 до 2 равно 2 - (-3) + 1 = 6.

Чтобы напечатать символ %, используйте в функции printf спецификатор «%%».

9.3 Площадь фигуры

С помощью встроенного ГСЧ вычислите площадь фигуры, ограниченной линиями:

2 ? x ? 5,

4 ? y ? 25,

y ? x2.

Вычислите относительную погрешность (в процентах) в двух случаях, когда количество случайных точек равно 1000 и 10000.

Замечания: точное значение площади в данном примере равно

125/3 - 8/3 - 12

9.4 Случайная величина с заданными свойствами

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

Распределения, для которых требуется генерировать случайные числа:

Равномерное на отрезках [a, b] [c, d].

Треугольное с параметрами [a, b].

10. Дополнительные задания

10.1 Многомерные случайные величины

Напишите функцию генерации случайной точки в n_мерном шаре с центром в начале координат и радиусом r.

10.2 Быки и коровы

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

1. Керниган Б. Язык программирования Си: Задачи по языку Си. / Б. Керниган, Д. Ритчи, А. Фьюэр М.: Финансы и статистика, 1985. - 192 с.

2. Керниган Б., Ритчи Д. Язык программирования Си. М.: Финансы и статистика, 1992. - 272 с.

3. Подбельский В.В., Фомин С.С. Программирование на языке Си. Учеб. пособие. М.: Финансы и статистика, 2004. 600 с.

4. Форсайт Дж. Машинные методы математических вычислений / Дж. Форсайт, М. Малькольм, К. Моулер. М.: Мир, 1980. - 279 с.

5. Кнут Д. Искусство программирования, том 2. Получисленные методы / Д. Кнут. М.: Изд. дом «Вильямс», 2007. 832 с.

6. Каханер Д. Численные методы и математическое обеспечение: Пер. с англ. / Д. Каханер, К. Моулер, С. Нэш. М.: Мир, 1998. - 575 с., ил.

7. Зубинский А. В поисках случайности // А. Зубинский. Компьютерное обозрение №29, 2003.

Страницы: 1, 2