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

| | 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

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

    • Приказ обращение с отходами Обращение с опасными отходами К числу основных документов в области обращения с отходами на предприятии относятся: Инвентаризация источников образования отходов и мест накопления, размещения отходов. (Карты-схемы) Формы первичного учета отходов(Приказ МПР от 01 […]
    • Характеристика бытовая для суда Характеристика с места жительства от соседей в суд Достаточно часто характеристика с места жительства от соседей в суд оказывает существенное влияние на ход рассмотрения дела. Ведь такой документ характеризует личность участника дела и может стать доказательством по […]
    • Налог при покупке недвижимости россия Особенности уплаты налога при покупке квартиры для физических лиц в 2018 году Налог при покупке квартиры в 2018 году для физических лиц определяется действующим законодательством. С 2018 году вступают в силу изменения, которые были внесены в Налоговый кодекс РФ. Именно […]
    • Если не сдать права после суда Статьи автоюристов Не сдал права после лишения прав судом. Как это может повлиять на исчисление срока лишения прав? 01 сентября 2013 года вступили в силу изменения закона, согласно которым у нарушителей ПДД больше не забирают права. В результате даже если водителя […]
    • Закон об осаго приложение Новый закон об ОСАГО в 2018 году Готовит ли государство новый закон об ОСАГО в 2018 году? Замена выплат по ОСАГО направлением на ремонт и его оплатой за счет страховой организации уже осуществлена. Применяется такой способ компенсации причиненного транспортному средству […]
    • Единый налог третья группа 2018 Ставка единого налога - 2018 Ставка единого налога - 2018 для предпринимателей-физлиц первой и второй гpупп расcчитывается в процентах oт размера прожиточного минимума и минимальной зарплаты, установлeнных нa 01 января 2018 года (смотрите страницy Минимальная зарплата - […]
    • Уведомление о ликвидации учреждения Уведомление работника о ликвидации предприятия Увольнение работников по пункту 1 части 1 статьи 81 Трудового кодекса РФ возможно только при вручении персонально каждому лицу такого документа, как уведомление работника о ликвидации предприятия. Как и в случае с сокращением […]
    • Ф Закон о правах потребителя Приняты изменения в Закон РФ «О защите прав потребителей». С 01 июля 2014 года вступил в силу Федеральный закон от 21.12.2013 N 363-ФЗ, которым внесены дополнения в Закон РФ "О защите прав потребителей". Пункт 3 статьи 16 дополнен предложением следующего содержания: […]