No Image

Экспоненциальное распределение случайной величины c

СОДЕРЖАНИЕ
1 просмотров
22 января 2020

Прошу прощения за доставленные неудобства.

Контент будет доступен.

Разспределения. Библиотега генерации экспоненциального закона распределения

Описание: Код для выполнения генерации распределния случайных чисел по закону экспоненциальному закону распределения.

Итак, Закон экспоненциального распределения наимболее распростран в дипломных работах по экономике для отображения теории спроса и предложения. Также, это одна из основных курсовых работ по программированию и прикладных информатиков, с целью написания алгоритма с экспоненциальным законом распределения. В данной статье рассатривается блок схема-алгоритм и исполняемый код на C#. Приступим.

Моделирование случайной величины с экспоненциальным распределением .

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

методом обратной функции.

Этот закон распределения случайных величин имеет следующие графики:

  • Для плотности распределений (рис. 1):

  • Для функции распределения (рис. 2):

Также экспоненциальное распределение имеет несколько числовых характеристик:

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

Алгоритм программы выглядит следующим образом:

Допустим, у нас есть проект в Visual Studio и мы создали класс "Exp.cs", который содержит довольно простой код (Листинг 1):

Листинг 1

Даю пояснения к листингу 1.

Здесь применяется подход из ряда статей "Распределения — (первая статья)", т.е. имеется ввиду, что мы используем некий класс входных переменных(enVal) и выводимых(ouVal). В классе "ouVal" мы используем переменную для храненя случайных велечин (СВ) с экспоненциальным законом распредления "ouVal._arX[i]", куда мы записываем новые СВ. Входной параметр "enVal._Lya" является неотъемлемой частью этого закона распределния, а папраметр "enVal._N" означает количество генерирумых СВ.

Также, если вы используете "все в одном", то можно написать примерно следующимм кодом — Листинг 2.

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

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

В универе задали написать программу по моделированию событий.

Задача не сложная, но не могу понять вот эту часть условия:
Интервал (дельта)t подчиняется экспоненциальному закону с математическим ожиданием равным 10 секундам.

Не могу понять/представить схему действий по вычислению этих интервалов.

Как вычислить этот интервал?

ПС: полное условие задачи:
На линию связи, которая состоит из 2 каналов, через случайные промежутки времени t поступают информационные посылки. При поступлении сообщения каждый из каналов може бути занят с вероятностью 0.4. Если оба канала заняты. То информация теряется. Интервал t подчиняется экспоненциальному закону с математическим ожиданием равным 10 секундам.

Определить какой процент посылок теряется в течение часа.

Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984)

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

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

Читайте также:  0X800b0109 windows 7 как исправить

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

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

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

Равномерное распределение может использоваться при генерации почти что любой случайной величины, благо имеется очень простой и универсальный метод инверсии (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) Доказательство работы алгоритма:

Воспользовавшись тем, что вероятность происхождения двух событий А и B равна

вычислим вероятность принятия случайной величины X с функцией плотности распределения g(x) и функцией распределения G(x), но уже при условии, что она меньше некого заданного параметра x:

И тогда по теореме Байеса:


Для примера сгенерируем модуль стандартной нормальной величины. В силу симметрии нормального распределения полученную величину можно умножить на случайную величину, принимающую значения +1 и -1 с равными вероятностями, и таким образом получить стандартную нормально распределенную величину X. Любая нормальная величина получается из стандартной умножением на sigma и сдвигом на mu. Функция плотности распределения |X|:

Попытаемся её приблизить функцией плотности стандартного экспоненциального распределения. Я немного забегаю вперед, так как об экспоненциальном распределении еще не говорил. Оно генерируется просто пресловутым методом инверсии — берем равномерно распределенную на [0, 1] величину U и возвращаем -ln(U).

Читайте также:  Хакерские форумы и сайты

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

    1. Случайно и равномерно выбирается прямоугольник i и генерируется равномерно распределенная величина X от 0 до xi
    2. Если X E1 2 / 2, то принимаем |X| = E1 + x1, иначе возвращаемся назад.
    3. Генерируем U. Если U Доказательство для хвоста

    Мы знаем, что случайная величина |X| > x1. Постараемся построить для нее алгоритм выборки с отклонением, используя E1+x1, где E1 — экспоненциально распределенная случайная величина с плотностью x1. Функция плотности распределения E1+x1:

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

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

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

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

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

    1. Случайно и равномерно выбирается прямоугольник i и генерируется равномерно распределенная величина X от 0 до xi.
    2. Если X Экспоненциальное распределение

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

    Нужно доказать, что при Е > 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] и W — экспоненциально распределенная случайная величина с плотностью 1 / lambda. Пусть:

    Если g(W) >= U, то W имеет гамма-распределение с параметром lambda:

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

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

    Или нет?

    Помните полярный метод Джорджа Марсальи? Он позволял в преобразовании Бокса-Мюллера быстро получать синус или косинус равномерно распределенной случайной величины. Ровно таким же образом можно получить и тангенс. Генерируем две равномерно распределенные случайные координаты x и y на квадрате [-1, 1]x[-1, 1]. Если мы попали в круг с центром в (0, 0) и единичным радиусом — возвращаем x/y, иначе — генерируем x и y еще раз. Вероятность не попасть в круг, скажем, с раза третьего уже меньше чем 0.01.

    Распределение Лапласа


    Распределение Лапласа — это то же экспоненциальное, только со случайным знаком.

    Распределение Леви

    Несмотря на то, как ужасно выглядит функция плотности распределения, сама случайная величина генерируется крайне просто и быстро:

    Распределение хи-квадрат


    Как известно, случайная величина с распределением хи-квадрат с параметром k — это сумма квадратов k стандартных нормальных случайных величин. Менее известно, что при четном k это же и удвоенная сумма k/2 экспоненциальных случайных величин (или же распределение Эрланга). Из этого соотношения и происходит вышеупомянутый алгоритм GA2:

    Этот факт легко доказать, используя характеристическую функцию — обратное преобразование Фурье функции плотности распределения:

    У этой функции есть полезное свойство для суммы двух независимых случайных величин:

    Пусть E — случайная величина с экспоненциальным распределением:

    Тогда её характеристическая функция:

    Нам нужно узнать распределение случайной величины равной удвоенной сумме стандартных экспоненциальных величин:

    Если оно совпадает с распределением хи-квадрат, то его характеристическая функция:

    Докажем это. Ранее было упомянуто также, что для экспоненциального распределения:

    Используя это свойство, получаем:

    Из этого свойства следует примечательный факт: если выбирать точку на плоскости со случайными и нормальными координатами (x, y), то расстояние от (0,0) до этой точки будет распределено экспоненциально.

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


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

    Логистическое распределение


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

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

    Комментировать
    1 просмотров
    Комментариев нет, будьте первым кто его оставит

    Это интересно
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    Adblock detector