Генераторы случайныхчисел
Возможно использование трех способов генерации случайных чисел: - аппаратный (физический); - табличный (файловый); - алгоритмический (программный); Аппаратный способ предполагает использование случайных сигналов физического происхождения. Чаще всего в таких генераторах используются шумы в электроныых и полупроводниковых приборах, явления распада радиоактивных элементов. Один из вариантов реализации заключается в следующем. Возьмем фиксированный промежуток времени Δt. Если в его течение уровень напряжения превысит пороговое значение четное число раз – записывается ноль, нечетное – единица. Для получения m-разрядного случайного числа параллельно соединяют m – генераторов. Достоинства метода: - запас чисел не ограничен; - не занимается место в памяти ЭВМ; Недостатки: - требуется периодическая проверка и настройка; - нельзя воспроизвести последовательности; - требуется специальное устройство; Табличный способ основан на использовании специальных таблиц, в которых размещены случайные числа, распределенные по какому-либо закону. В компьютерных моделях такой способ применяется довольно редко. Достоинства метода: - требуется однократная проверка; - можно воспроизвести последовательности; Недостатки: - ограниченный запас чисел; - занимает существенное место в памяти (при обращении к внешней памяти требуется время); Алгоритмический способ основан на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. С этой точки зрения под генератором случайных чисел (или генератором псевдослучайных чисел согласно заданному распределению вероятностей и обладающий свойством видимости случайности). Достоинства: - требуется однократная проверка; - можно многократно воспроизводить последовательности чисел; - занимает мало места в памяти; - не используются внешние (аппаратные) устройства. Недостатки: - запас чисел ограничен периодом генератора; - более высокие затраты машинного времени на расчет. В качестве базового случайного процесса используется повторная выборка из генеральной совокупности значений, равномерно распределенных в интервале (0;1). Используются рекурентные формулы , где i-случайное число определяется начиная с первого случайного числа. Чаще всего используются так называемые конгруэнтные методы (наиболее распространенный – мультипликативный). В основе конгруэнтных процедур лежит понятие конгруэнтности. Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m – целое число, тогда и только тогда, когда существует такое целое число k, что a-b = km, т.е. если разность a-b делится на m и если числа a и b дают одинаковые остатки от деления на абсолютную величину m. Рекуррентное соотношение имеет вид: Xi+1 = λXi mod M, где λ,X0 – целые положительные нечетные числа; М – наиболее удобно выбирать так: M = pg; где p – основание используемой системы счисления. g – количество разрядов в получаемых случайных числах. Пример: Пусть необходимо получить случайное число , равномерно распределенное в интервале (0;1). Пусть λ (ядро) = 5167; X0 = 3729 M = 104 = 10000; Тогда λXi = 19267743 и случ. число = 0,7743 на 2-м шаге Xi = 7743 , λXi = 40008081, случ. число = 0,8081 и т.д… Количество случайных чисел, выработанных генератором до того, как они начнут повторяться, называются периодом или длинной генератора.
Метод обратной функции и его использование для гененрирования непрерывных случайных величин Предположим, нам необходимо генерировать случайную величину Х, являющуюся непрерывной и имеющую функцию распределения F – непрерывную строго возрастающую, когда 0 < F(x) < 1, из этого следует, что если x1 < x2 и 0 < F(x1) < F(x2) < 1, то F(x1) < F(x2). Примем, что F-1 – это обратная функция F. Две функции y = f(x) и y = phi(x) называются взаимно обратными, если для каждой пары значений a,b, удовлетворяющих условию b = f(a), удовлетворяется также условие a = phi(b), а для каждой пары , удовлетворяющих условию a = phi(b), удовлетворяется также условие b = f(a). Одна из двух взаимно обратных функций может быть названа прямой (безразлично какая), тогда другая функция называется обратной. Пример: y = x2 и y = +-sqrt(x) y = ex и y = ln x На первом шаге строится интегральная функция распределения F(x). Т.к. F(x) изменяется в интервале от 0 до 1, полагают F(x) = R, где R – случайная величина, равномерно распределенная в интервале (0,1). Тогда: x = F-1(R) где x – случайная величина с функцией плотности распределения f(x), F-1‑ - функция, обратная по отношению к F.
Метод обратной функции и его использование для гененрирования дискретных случайных величин Для дискретной величины X является функция распределения F(X) = P(X<=x) = ∑p(xi) (если xi<=x) где pi(x) является вероятностной мерой p(xi) = P(X = xi) Допускается, что величина X может иметь только значения x1,x2,… для которых x1<x2<… Тогда алгоритм будет иметь следующий вид: 1. Генерируем U ~ U(0,1) 2. Определяем положительное наименьшее число I, для которого U <= F(xI) и возвращаем X = xI .
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (572)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |