Гсч с заданным законом распределения

| | 0 Comment

Случайные числа (квазиравномерные и псевдослучайные с равномерным законом распределения), хотя и являются равномерными лишь приближенно, могут быть использованы в качестве исходного материала для получения любых вероятностных объектов.

Такими вероятностными объектами в первую очередь являются случайные события, наступающие с заданной вероятностью, случайные величины с заданным законом распределения и некоторые виды случайных векторов и процессов.

Посмотрим, как можно моделировать с помощью случайных равномерно распределенных чисел случайные события, наступающие с заданной вероятностью. Эту процедуру называют еще «реализацией жребия». Пусть событие А наступает с вероятностью р, тогда процедура моделирования этого события с помощью равномерно распределенных в интервале (0,1) случайных чисел выглядит следующим образом:

1) выбирается очередное случайное число

2) проверкой неравенства

устанавливается принадлежность этого числа отрезку

Если число удовлетворяет неравенству (2.4), говорят, что событие А наступило, в противном случае — не наступило.

Аналогично выглядит процедура моделирования на ЭВМ дискретной случайной величины с заданным законом распределения.

Пусть случайная величина принимает возможные значения с вероятностями

Очевидно, что значение будет принято случайной величиной в том случае, когда выполняется неравенство, аналогичное неравенству (2.4)

(наступает событие, состоящее в том, что значение когда

(наступает событие, состоящее в том, что ) значение — когда

(наступает событие, состоящее в том, что ) и т. д.

Другими словами, пусть

наступает событие, состоящее в том, что

Процедура реализации этого способа моделирования дискретной случайной величины на ЭВМ сводится к следующему. Вырабатываем случайные числа с равномерным распределением в интервале (0,1). Очередное сравниваем с если неравенство (2.5) выполнено, считаем, что в противном случае переходим к 12. Сравниваем с если неравенство (2.6) выполнено, считаем, что в противном случае переходим к и т. д. до тех пор, пока одно из неравенств вида (2.9) окажется выполненным. Эта процедура всегда рано или поздно приводит к цели, так как событие, состоящее в в том, что случайная величина принимает какое-нибудь из своих значений является достоверным.

Перейдем к рассмотрению метода моделирования непрерывных случайных величин. Пусть по-прежнему в нашем распоряжении имеются случайные числа с равномерным распределением в интервале (0,1). Требуется получить случайные числа являющиеся возможными значениями случайной величины с законом распределения, заданным функцией плотности

Можно доказать, (см., например [9]), что случайная величина являющаяся решением уравнения

имеет распределение , если случайная величина I распределена равномерно в интервале (0,1).

Соотношением (2.10) можно воспользоваться для получения случайных чисел с заданным законом распределения.

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

Пример 1. Предположим, что нам необходимо получить случайные числа с показательным распределением

Используем соотношение (2.10)

Интеграл (2.12) берется в конечном виде, поэтому

Решим уравнение (2.13) относительно

Соотношение (2.14) полностью решает поставленную задачу. Заметим, что случайное число имеет также равномерное распределение в интервале (0,1). Поэтому вместо (2.14) обычно пользуются соотношением

Подставляя в правую часть соотношения (2.15) последовательно случайные числа мы получим последовательность чисел с показательным законом распределения.

Пример 2. Случайная величина имеет функцию плотности

Располагая случайными числами имеющими равномерное распределение в интервале (0,1), требуется получить случайные числа с законом распределения, который выражается функцией плотности (2.16).

Соотношение (2.10) имеет вид:

После вычисления интеграла

Решив уравнение (2.18) относительно получим

или, с учетом замечания, относящегося к соотношению (2.14):

Можно привести и другие примеры использования соотношения (2.10). Однако приходится признать, что практически изложенная методика имеет весьма ограниченную сферу применения. Это объясняется следующими двумя обстоятельствами.

Во-первых, для многих законов распределения, встречающихся в практических задачах, интеграл (2.10) в конечном виде не берется. Например, для нормального распределения (закона Гаусса)

соотношение (2.10) приводит к интегралу

который можно вычислить только численными методами. Это приводит к недопустимо большим затратам машинных операций на преобразование случайных чисел.

Во-вторых, даже для тех случаев, когда соответствующие интегралы берутся в конечном виде, получаются формулы, например (2.15), (2.20) и др., весьма неудобные для расчета на ЭВМ. Причина в том, что вычисление логарифмов, корней и других элементарных функций на ЭВМ выполняется при помощи стандартных программ, состоящих из многих исходных операций машины (сложение, умножение и т. д.). Учитывая, что применение метода статистических испытаний требует большого количества случайных чисел, естественно, возникает опасность существенных затрат машинного

времени. Поэтому на практике обычно пользуются приближенными методами преобразования случайных чисел, обеспечивающими достаточную экономию операций ЭВМ.

edu.alnam.ru

Лекция 24.
Моделирование случайной величины
с заданным законом распределения

Большей информативностью, по сравнению с такими статистическими характеристиками как математическое ожидание, дисперсия, для инженера обладает закон распределения вероятности случайной величины X . Представим, что X принимает случайные значения из некоторого диапазона. Например, X — диаметр вытачиваемой детали. Диаметр может отклоняться от запланированного идеального значения под влиянием различных факторов, которые нельзя учесть, поэтому он является случайной слабо предсказуемой величиной. Но в результате длительного наблюдения за выпускаемыми деталями можно отметить, сколько деталей из 1000 имели диаметр X1 (обозначим NX1 ), сколько деталей имели диаметр X2 (обозначим NX2 ) и так далее. В итоге можно построить гистограмму частости диаметров, откладывая для X1 величину NX1/1000 , для X2 величину NX2/1000 и так далее. (Обратите внимание, если быть точным, NX1 — это число деталей, диаметр которых не просто равен X1 , а находится в диапазоне от X1 – Δ/2 до X1 + Δ/2 , где Δ = X1 – X2 ). Важно, что сумма всех частостей будет равна 1 (суммарная площадь гистограммы неизменна). Если X меняется непрерывно, опытов проведено очень много, то в пределе N –> ∞ гистограмма превращается в график распределения вероятности случайной величины. На рис. 24.1, а показан пример гистограммы дискретного распределения, а на рис. 24.1, б показан вариант непрерывного распределения случайной величины.

В нашем примере закон распределения вероятности случайной величины показывает насколько вероятно то или иное значение диаметра выпускаемых деталей. Случайной величиной является диаметр детали.

В производстве и технике часто такие законы распределения заданы по условию задачи. Наша задача сейчас состоит в том, чтобы научиться имитировать появление конкретных случайных событий согласно вероятностям такого распределения.

Метод ступенчатой аппроксимации

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

Обозначим: hi — высота i -го столбца, f(x) — распределение вероятности (показывает насколько вероятно некоторое событие x ). Значение hi операцией нормировки необходимо перевести в единицы вероятности появления значений x из интервала xi –1 (r) . Здесь r — число, генерируемое эталонным ГСЧ в интервале от 0 до 1, x1 — сгенерированная в итоге случайная величина. Графически суть метода изображена на рис. 24.6 .

stratum.ac.ru

ГСЧ с нормальным законом распределения — C#

Здравствуйте, нужно как то сделать ГСЧ с нормальным законом распределения (0,1), а способ построения использовать Метод отбора.

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

Добавлено через 1 час 41 минуту
если я правильно понял нужно создать равномерную последовательность случайных чисел, а из этой последовательности используя метод отбора, сделать последовательность с нормальным распределением?

Генерация случайных чисел за нормальным законом распределения
Cгенерировать случайные числа за нормальным законом распределения и по y.

Как сделать данный код нормальным?
В общем написал код . но он оказался уж очень галимым((( вот он using.

Как сгенерировать массив чисел с нормальным распределением по заданным параметрам
Как сгенерировать массив чисел с нормальным распределением по заданным.

Как построить случайные величины с нормальным (Гауссовым) распределением на основе Random
Доброго времени суток. У меня имеется задача построение броуновского движения.

Случайные числа с нормальным законом распределения
Нужно сгенерировать случайные числа нормальным законом распределения, в.

Смоделировать случайную величину с нормальным законом распределения
(Помогите,пожалуйста ,написать программу на языке си,очень нужно,если не.

www.cyberforum.ru

Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984)
Популярность стохастических алгоритмов все растет. Многие из них базируются на генерации большого количества различных случайных величин. Далеко не всегда равномерно распределенных. Здесь я попытался собрать информацию о быстрых и точных генераторах случайных величин с известными распределениями. Задачи могут быть разными, разными могут быть и критерии. Кому-то важно время генерации, кому-то — точность, кому-то — криптоустойчивость, кому-то — скорость сходимости. Лично я исходил из предположения, что мы имеем некий базовый генератор, возвращающий псевдослучайное целое число, равномерно распределенное от 0 до некого RAND_MAX

и что этот генератор достаточно быстрый. Я имею ввиду, что дешевле сгенерировать с десяток случайных чисел, нежели чем посчитать логарифм или возвести в степень одно из них. Это могут быть стандартные генераторы: std::rand(), rand в MATLAB, Java.util.Random и т.д. Но имейте ввиду, что подобные генераторы редко подходят для серьезной работы. Зачастую они проваливают разные статистические тесты. А также, помните, что вы полностью зависите от них и лучше использовать свой собственный генератор, чтобы иметь представление о его работе.

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

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

Равномерное распределение

Равномерное распределение может использоваться при генерации почти что любой случайной величины, благо имеется очень простой и универсальный метод инверсии (inverse transform sampling): генерируем случайную величину U, равномерно распределенную от 0 до 1, и возвращаем обратную функцию распределения (квантиль) с параметром U. Действительно:

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

С генератором равномерного распределения, я надеюсь, мне не нужно долго останавливаться (при большом количестве генерируемых случайных величин лучше посчитать (b — a) / RAND_MAX только один раз):

Разумеется, непрерывность — это лишь абстракция. В реальном мире и в данном случае конкретно под этим подразумевается достаточно малый шаг дискретизации. Стоит заметить важную вещь. Если вы генерируете случайное число, равномерно распределенное от 0 до 1, то 32 бит недостаточно, чтобы покрыть все значения, которые может принимать на этом диапазоне double (хотя, для float этого более чем достаточно). Для лучшего качества нужно либо генерировать 64-битные целые, либо комбинировать два 32-битных.

Нормальное распределение

Метод инверсии потребует вычисления обратной функции ошибок. Если не использовать специальные аппроксимирующие функции, сложно и невероятно долго. Для нормальной величины существует метод Бокса-Мюллера. Он довольно прост и широко распространен. Его явный недостаток — это вычисление трансцендентных функций. На Хабре уже упоминался полярный метод, помогающий избежать подсчета синуса и косинуса. Но мы все еще должны считать логарифм и корень из него. Куда быстрее работает красиво названный метод Ziggurat, придуманный Джорджем Марсалья, автором того же полярного метода.
Полярный метод — это пример выборки с отклонением (acceptance-rejection sampling). Буквально, вы генерируете величину и принимаете ее, если она подходит, иначе — отклоняете и генерируете еще раз. Основной пример: нужно сгенерировать случайную величину с плотностью f(x), однако это слишком сложно сделать простым методом инверсии. Зато, вы можете сгенерировать случайную величину с плотностью g(x), не очень сильно отличающейся от f(x). В таком случае вы берете наименьшую константу M, такую что M > 1 и почти всюду f(x) 2 ) — то |X| = E, иначе возвращаемся на первый шаг.

  • Генерируем новую U. Если U (E1 — 1) 2 / 2, то принимаем |X| = E1, иначе возвращаемся назад.
  • Генерируем U. Если U 2 / 2 будет также распределена экспоненциально и независимо от E1. Поэтому её можно запомнить и использовать в следующий раз вместо E1.

    Экспоненциальное распределение обладает свойством отсутствия памяти:

    А это означает, что функция распределения разницы:

    Общая проблема выборки с отклонением заключается в подборе такой случайной величины с плотностью распределения g(x), чтобы отклонений было как можно меньше. Для решения этой проблемы существует множество расширений. Сам же метод является основой для почти все последующих алгоритмов, включая Ziggurat. Суть последнего все та же: пытаемся покрыть функцию плотности нормального распределения похожей и более простой функцией и возвращаем величины, попавшие под кривую. Функция своеобразная и напоминает многоступенчатое сооружение, откуда, собственно, и такое название у алгоритма.


    Зиккурат сооружается следующим образом. У подножья функции f(x) выбираются точки x1 и y0 = f(x1). Площадь под прямоугольником от (0,0) до (x1, y0) + площадь под хвостом функции f(x > x1) = А. Так мы построили базовый слой. Поверх него ставится еще один прямоугольник, такой, что его ширина x1, а высота y1 = A/y0 и таким образом его площадь будет равна A. Этот прямоугольник уже включает в себя точки, которые лежат выше функции f(x), например (x1, y1). Функцию f(x) второй прямоугольник пересекает в точке (x2, y1) — это будет координата нижней правой точки третьего прямоугольника, который накладывается таким же образом как и второй, чтобы его площадь была равна А. Так продолжается до тех пор, пока мы не построим Зиккурат до вершины функции. Площадь каждой ступени будет равна А. Дальнейший алгоритм (без обработки попадания в базовый слой):

  • Случайно и равномерно выбирается прямоугольник i и генерируется равномерно распределенная величина X от 0 до xi
  • Если X E1 2 / 2, то принимаем |X| = E1 + x1, иначе возвращаемся назад.
  • Генерируем U. Если U x1. Постараемся построить для нее алгоритм выборки с отклонением, используя E1+x1, где E1 — экспоненциально распределенная случайная величина с плотностью x1. Функция плотности распределения E1+x1:

    Чтобы знать значение М, нам нужно найти максимум отношения функций:

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

    Получаем границу для равномерной случайной величины:

    И тогда условие принятия случайной величины будет:

    Тогда полностью алгоритм будет выглядеть так:

  • Случайно и равномерно выбирается прямоугольник i и генерируется равномерно распределенная величина X от 0 до xi.
  • Если X x1 функция распределения E — x1 будет также распределена экспоненциально. Это возможно благодаря ранее упомянутому отсутствию памяти у экспоненциального распределения:

    Еще пара фактов: если использовать таблицу с 255 прямоугольниками, то вероятность принятия с первого раза для экспоненциального распределения — 0.989, для нормального — 0.993. В MATLAB с 5 версии для нормального распределения используется Ziggurat (раньше использовался полярный метод). В R для нормальных величин, насколько мне известно, аппроксимируют полиномами обратную функцию ошибок и используют метод инверсии.

    Гамма-распределение

    Алгоритмы для генерации здесь уже сложнее, поэтому я не буду здесь описывать их доказательства, привожу лишь примеры. Для генерации стандартной величины (theta = 1), используются четыре алгоритма, каждый в зависимости от k.

    • Если k или 2k — целое и k 3 — GO алгоритм.

    Нестандартная случайная величина с гамма-распределением, получается из стандартной умножением на theta.

    Алгоритм GA

    Если сложить две случайные величины с гамма-распределением с параметрами k1 и k2, то получится случайная величина с гамма-распределением и с параметром k1+k2. Еще одно свойство — если theta = k = 1, то легко проверить, что распределение будет экспоненциальным. Поэтому, если k целое — то можно просто просуммировать k случайных величин со стандартным экспоненциальным распределением.

    Если k не целое, но 2k — целое, то можно вместо одной из экспоненциальных случайных величин в сумме использовать половину квадрата нормальной величины. Почему так возможно, станет ясно позднее.

    Алгоритм GS

      Генерируем стандартную экспоненциально распределенную величину Е и величину U, равномерно распределенную от 0 до 1 + k / e. Если U 1/k . Если x 1, однако среднее время его выполнения возрастает пропорционально sqrt(k), поэтому он эффективен только для k = U, то W имеет гамма-распределение с параметром lambda:

    Доказательство. Функция плотности распределения W:

    Так как U имеет равномерное распределение, то

    m.habr.com

    Гсч с заданным законом распределения

    ГПСЧ с источником энтропии или ГСЧ

    Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG). Такие генераторы чаще всего строятся из комбинации ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ). Под источником энтропии понимают некоторые устройства (счетчики) случайных событий.

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

    В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии является наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например,смарт-картах). Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движениемышии т.п.), как, например, вPGPи Yarrow, или взаимодействия междупотоками, как, например, в Java secure random.

    Пример простейшего ГСЧ с источником энтропии

    Если в качестве источника энтропии использовать текущее время, то для получения натурального числаот 0 до N достаточно вычислитьостаток от делениятекущего времени вмиллисекундахна число N+1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.

    Примеры ГСЧ и источников энтропии приведены в таблице 3.1

    studfiles.net

    Это интересно:

    • Инвалид детства пенсия россия Ежемесячные пособия и льготы по уходу за ребенком-инвалидом По российскому законодательству, родителям, опекунам или другим трудоспособным лицам, которые не работают и осуществляют уход за ребенком-инвалидом или инвалидом 1 группы с детства, назначается ежемесячная […]
    • 492 приказ мвд Приказ МВД РФ от 7 июля 2010 г. № 492 "О внесении изменения в приказ МВД России от 2 июня 2005 г. № 444" Внести прилагаемое изменение в приказ МВД России от 2 июня 2005 г. № 444 "О полномочиях должностных лиц МВД России по составлению протоколов по делам об […]
    • Судебные споры по детям Судебные споры, связанные с воспитанием детей Обязанность граждан воспитывать детей является конституционной обязанностью. Ребенок является самым беспомощным существом. Поэтому продолжительный период времени нуждается в заботе, которая осуществляется в семье прежде всего, […]
    • Правила безопасности тепловых установок Тепловые энергоустановки Правила технической эксплуатации ПРАВИЛА ТЕХНИКИ БЕЗОПАСНОСТИ ПРИ ЭКСПЛУАТАЦИИ ТЕПЛОПОТРЕБЛЯЮЩИХ УСТАНОВОК И ТЕПЛОВЫХ СЕТЕЙ ПОТРЕБИТЕЛЕЙ СОГЛАСОВАНЫ Советом Федерации независимых профсоюзов России 06.05.1992 г. письмом № 105/78 УТВЕРЖДЕНЫ […]
    • Алименты с премии к празднику Как удерживаются алименты с премии Алиментные обязательства необходимы, чтобы защитить финансовую сторону ребенка, если по стечению обстоятельств он воспитывается одним из родителей или же опекуном. Право на денежную компенсацию от одного из родителей не прекращаются даже […]
    • Образец договор на сдачу квартиры квартирантам Образец договор на сдачу квартиры квартирантам √ Скачать образец договора аренды квартир √ Данный документ заключается с собственником жилья на время аренды квартиры. В договоре указывают: срок аренды квартиры, даты посещения квартиры собственником, для контроля за ее […]
    • Срок обжалования определения об отказе в удовлетворении ходатайства Постановление Федерального арбитражного суда Восточно-Сибирского округа от 10 сентября 2013 г. N Ф02-4592/13 по делу N А19-6447/2013 (ключевые темы: отказ в удовлетворении ходатайства - право на обжалование - рассмотрение дела по существу - буквальное толкование - договор […]
    • Отчеты по налогу за воду Пример расчета водного налога (порядок исчисления, сроки) Отправить на почту Расчет водного налога - пример его приводится в данной статье - требуется делать ежеквартально при наличии у налогоплательщика объекта, облагаемого этим налогом. Рассмотрим особенности такого […]