stringtranslate.com

Стохастическое моделирование

Стохастическое моделирование — это моделирование системы , в которой есть переменные, которые могут изменяться стохастически (случайно) с отдельными вероятностями. [1]

Реализации этих случайных величин генерируются и вставляются в модель системы. Выходные данные модели записываются, а затем процесс повторяется с новым набором случайных значений. Эти шаги повторяются до тех пор, пока не будет собрано достаточное количество данных. В конце концов, распределение результатов показывает наиболее вероятные оценки, а также структуру ожиданий относительно того, в какие диапазоны значений переменные с большей или меньшей вероятностью попадут. [1]

Часто случайные величины, вставленные в модель, создаются на компьютере с помощью генератора случайных чисел (ГСЧ). Выходные данные генератора случайных чисел с равномерным распределением U(0,1) затем преобразуются в случайные величины с распределениями вероятностей, которые используются в модели системы. [2]

Этимология

Первоначально «Стохастик» означало «относящийся к предположению»; от греческого стохастикос "способный догадываться, догадываться": от стохазестаи "догадываться"; от стохос "догадка, цель, цель, отметка". Смысл «случайно определенного» впервые был зафиксирован в 1934 году в немецком журнале «Сточастик». [3]

Дискретно-событийное моделирование

Чтобы определить следующее событие в стохастическом моделировании, вычисляются скорости всех возможных изменений состояния модели, а затем упорядочиваются в массиве. Далее берется накопительная сумма массива, а в последней ячейке содержится число R, где R — общая частота событий. Этот кумулятивный массив теперь представляет собой дискретное кумулятивное распределение, и его можно использовать для выбора следующего события, выбирая случайное число z~U(0,R) и выбирая первое событие так, чтобы z было меньше частоты, связанной с этим событием. .

Распределения вероятностей

Распределение вероятностей используется для описания потенциального результата случайной величины.

Ограничивает результаты, когда переменная может принимать только дискретные значения. [4]

Распределение Бернулли

Случайная величина X является распределенной по Бернулли с параметром p, если она имеет два возможных результата, обычно кодируемых 1 (успех или дефолт) или 0 (неудача или выживание) [5] , где вероятности успеха и неудачи равны и где .

Чтобы получить случайную величину X с распределением Бернулли из равномерного распределения U (0,1), созданного генератором случайных чисел, мы определяем

[2]
Пример: подбрасывание монеты.

Определять

[6]

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

Биномиально распределенная случайная величина Y с параметрами n и p получается как сумма n независимых и одинаково распределенных по Бернулли случайных величин X 1 , X 2 , ..., X n [4]

Пример: Монету подбрасывают три раза. Найдите вероятность того, что выпадет ровно две решки. Эту проблему можно решить, посмотрев на выборочное пространство. Есть три способа получить две головы.

ХХХ, ХХТ, ХТХ, ТХХ , ТТХ, ЧТ, ХТТ, ТТТ

Ответ: 3/8 (= 0,375). [7]

распределение Пуассона

Пуассоновский процесс — это процесс, в котором события происходят случайным образом в интервале времени или пространства. [2] [8] Распределение вероятностей для пуассоновских процессов с постоянной скоростью λ за интервал времени определяется следующим уравнением. [4]

Определяя как количество событий, происходящих за интервал времени

Можно показать, что время между прибытиями событий распределяется экспоненциально с кумулятивной функцией распределения (CDF) . Обратная экспоненциальная CDF определяется выражением

[2]

Моделирование процесса Пуассона с постоянной скоростью для количества событий , происходящих в интервале, можно выполнить с помощью следующего алгоритма. [9]

  1. Начните с и
  2. Сгенерируйте случайную величину из равномерного распределения
  3. Обновите время с помощью
  4. Если , то стоп. В противном случае перейдите к шагу 5.
  5. Перейдите к шагу 2

Методы

Методы прямой и первой реакции

Опубликовано Дэном Гиллеспи в 1977 году и представляет собой линейный поиск по кумулятивному массиву. См. алгоритм Гиллеспи .

Алгоритм стохастического моделирования Гиллеспи (SSA) по сути представляет собой точную процедуру численного моделирования временной эволюции хорошо перемешиваемой химически реагирующей системы с должным учетом случайности, присущей такой системе. [10]

Оно строго основано на той же самой микрофизической предпосылке, которая лежит в основе основного химического уравнения, и дает более реалистичное представление об эволюции системы, чем детерминированное уравнение скорости реакции (RRE), математически представленное ОДУ. [10]

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

Следующий метод реакции

Опубликованный в 2000 году Гибсоном и Бруком [11] метод следующей реакции превосходит первый метод реакции за счет уменьшения количества случайных чисел, которые необходимо генерировать. Чтобы сделать выборку реакций более эффективной, для хранения времени реакции используется индексированная [очередь приоритетов]. Чтобы сделать расчет склонностей к реакции более эффективным, также используется граф зависимостей. Этот график зависимостей показывает, какие реакции склонны обновляться после запуска конкретной реакции. Хотя метод следующей реакции более эффективен, он требует более сложных структур данных, чем метод прямого моделирования или метод первой реакции.

Оптимизированные и сортируемые прямые методы

Опубликовано в 2004 г. [12] и 2005 г. Эти методы сортируют совокупный массив для уменьшения средней глубины поиска алгоритма. Первый выполняет предварительное моделирование для оценки частоты срабатывания реакций, тогда как второй сортирует совокупный массив «на лету».

Логарифмический прямой метод

Опубликовано в 2006 году. Это двоичный поиск в накопительном массиве, что позволяет снизить временную сложность выборки реакции в наихудшем случае до O (log M).

Методы частичной склонности

Опубликовано в 2009, 2010 и 2011 годах (Рамасвами 2009, 2010, 2011). Используйте исключенные частичные склонности к реакциям, чтобы уменьшить вычислительные затраты и масштабироваться в зависимости от количества видов в сети, а не (большего) количества реакций. Существует четыре варианта:

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

Приближенные методы

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

τ прыгающий метод

Поскольку метод SSA отслеживает каждый переход, его было бы непрактично реализовать для определенных приложений из-за высокой временной сложности. Гиллеспи предложил процедуру аппроксимации — метод тау-прыжка , который сокращает время вычислений с минимальной потерей точности. [13] Вместо того, чтобы делать постепенные шаги во времени, отслеживая X ( t ) на каждом временном шаге, как в методе SSA, метод тау-прыжка перескакивает от одного подинтервала к другому, аппроксимируя количество переходов, происходящих в течение заданного интервала. подинтервал. Предполагается, что значение скачка τ достаточно мало, чтобы не было существенного изменения значения скоростей перехода вдоль подинтервала [ t , t + τ ]. Это состояние известно как условие скачка. Таким образом, метод тау-прыжка имеет то преимущество, что моделирует множество переходов за один скачок, не теряя при этом значительной точности, что приводит к ускорению времени вычислений. [14]

Метод условной разницы

Этот метод аппроксимирует обратимые процессы (включая процессы случайного блуждания/диффузии), принимая во внимание только чистые скорости противоположных событий обратимого процесса. Основное преимущество этого метода заключается в том, что его можно реализовать с помощью простого оператора if, заменяющего предыдущие скорости перехода модели новыми, эффективными ставками. Таким образом, модель с замененными темпами перехода может быть решена, например, с помощью обычного SSA. [15]

Непрерывное моделирование

Если в дискретном пространстве состояний четко разграничить отдельные состояния (значения), то в непрерывном пространстве это невозможно в силу определенной непрерывности. Система обычно меняется со временем, переменные модели затем также изменяются непрерывно. Таким образом , непрерывное моделирование моделирует систему с течением времени, учитывая дифференциальные уравнения , определяющие скорость изменения переменных состояния. [16] Примером непрерывной системы является модель хищник/жертва [17] или балансировка тележки с шестом [18].

Распределения вероятностей

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

Говорят, что случайная величина X нормально распределена с параметрами µ и σ , сокращенно XN ( µ , σ 2 ) , если плотность случайной величины задается формулой [4]

Многие вещи на самом деле нормально распределены или очень близки к этому. Например, рост и интеллект распределены примерно нормально ; Ошибки измерения также часто имеют нормальное распределение . [19]

Экспоненциальное распределение

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

Экспоненциальное распределение популярно, например, в теории массового обслуживания , когда мы хотим смоделировать время ожидания, пока не произойдет определенное событие. Примеры включают время, пока в магазин не войдет следующий клиент, время, пока определенная компания не выйдет из строя, или время, пока какая-то машина не выйдет из строя. [4]

t-распределение Стьюдента

Т-распределение Стьюдента используется в финансах как вероятностные модели доходности активов. Функция плотности t-распределения определяется следующим уравнением: [4]

степеней свободыгамма-функция

Для больших значений n t -распределение существенно не отличается от стандартного нормального распределения . Обычно для значений n > 30 t-распределение считают равным стандартному нормальному распределению .

Другие дистрибутивы

Комбинированное моделирование

Зачастую одну и ту же систему можно смоделировать, используя совершенно разные взгляды на мир. Дискретное моделирование проблемы, а также ее непрерывное моделирование событий (непрерывное моделирование с дискретными событиями, которые нарушают непрерывный поток) может в конечном итоге привести к одним и тем же ответам. Однако иногда методы могут ответить на разные вопросы о системе. Если нам обязательно нужно ответить на все вопросы или мы не знаем, для каких целей будет использоваться модель, удобно применить комбинированную непрерывную/дискретную методологию . [20] Подобные методы могут перейти от дискретного стохастического описания к детерминированному континуальному описанию в зависимости от времени и пространства. [21] Использование этого метода позволяет улавливать шум из-за небольшого количества копий, при этом его моделирование происходит намного быстрее, чем традиционный алгоритм Гиллеспи. Более того, использование детерминированного описания континуума позволяет моделировать сколь угодно большие системы.

Моделирование Монте-Карло

Монте-Карло – это процедура оценки. Основная идея состоит в том, что если необходимо знать среднее значение некоторой случайной величины, а ее распределение невозможно определить, и если можно взять выборку из распределения, мы можем оценить ее, взяв выборки независимо и усреднив их. Если выборок достаточно, то закон больших чисел гласит, что среднее значение должно быть близко к истинному значению. Центральная предельная теорема гласит, что среднее значение имеет гауссово распределение вокруг истинного значения. [22]

В качестве простого примера предположим, что нам нужно измерить площадь фигуры со сложным неправильным контуром. Подход Монте-Карло заключается в том, чтобы нарисовать квадрат вокруг фигуры и измерить квадрат. Затем бросаем дротики в квадрат, как можно равномернее. Доля стрел, попадающих на фигуру, дает отношение площади фигуры к площади квадрата. Фактически, к этой форме можно привести почти любую интегральную задачу или любую задачу усреднения. Необходимо иметь хороший способ определить, находитесь ли вы внутри контура, и хороший способ определить, сколько дротиков нужно бросить. И последнее, но не менее важное: нам нужно бросать дротики равномерно, т. е. используя хороший генератор случайных чисел . [22]

Приложение

Существуют широкие возможности использования метода Монте-Карло: [1]

Генераторы случайных чисел

Для имитационных экспериментов (в том числе Монте-Карло) необходимо генерировать случайные числа (как значения переменных). Проблема в том, что компьютер является в высшей степени детерминированной машиной: по сути, за каждым процессом всегда стоит алгоритм, детерминированное вычисление, изменяющее входные данные на выходные; поэтому нелегко генерировать случайные числа с равномерным распределением в пределах определенного интервала или набора. [1]

Генератор случайных чисел — это устройство, способное генерировать последовательность чисел, которую невозможно «легко» идентифицировать по детерминированным свойствам. Эта последовательность тогда называется последовательностью стохастических чисел . [23]

Алгоритмы обычно полагаются на псевдослучайные числа , сгенерированные компьютером числа, имитирующие настоящие случайные числа, для генерации реализации, одного из возможных результатов процесса. [24]

Методы получения случайных чисел существуют уже давно и используются во многих различных областях (например, в играх ). Однако эти цифры страдают определенной предвзятостью. В настоящее время лучшими методами, которые, как ожидается, создадут действительно случайные последовательности, являются естественные методы, использующие случайную природу квантовых явлений . [23]

Смотрите также

Рекомендации

  1. ^ abcd ДЛОУГЕ, М.; ФАБРИ, Ж.; КУНЦОВА, М.. Simulace pro ekonomy. Прага: ВШЭ, 2005.
  2. ^ abcd Деккинг, Фредерик Мишель (2005). Современное введение в вероятность и статистику: понимание почему и как . Спрингер. ISBN 1-85233-896-2. OCLC  783259968.
  3. ^ стохастический. (без даты). Интернет-этимологический словарь. Получено 23 января 2014 г. с веб-сайта Dictionary.com: http://dictionary.reference.com/browse/stochastic.
  4. ^ abcdef Рачев, Светлозар Т. Стоянов, Стоян В. Фабоцци, Фрэнк Дж., «Глава 1, концепции вероятности» в расширенных стохастических моделях, оценке рисков и оптимизации портфеля: идеальные показатели риска, неопределенности и производительности, Хобокен, Нью-Джерси , США: Вили, 2008.
  5. ^ Рачев, Светлозар Т.; Стоянов, Стоян В.; Фабоцци, Фрэнк Дж. (14 апреля 2011 г.). Вероятностно-метрический подход к измерению финансовых рисков . дои : 10.1002/9781444392715. ISBN 9781444392715.
  6. ^ Распределение Бернулли, Чикагский университет - Статистический факультет, [онлайн] доступно по адресу http://galton.uchicago.edu/~eichler/stat22000/Handouts/l12.pdf.
  7. ^ «Биномиальное распределение». Архивировано из оригинала 26 февраля 2014 г. Проверено 25 января 2014 г.
  8. ^ Хайт, Фрэнк А. (1967). Справочник по распределению Пуассона . Уайли. ОКЛК  422367440.
  9. ^ Сигман, Карл. «Пуассоновские процессы и сложные (периодические) пуассоновские процессы» (PDF) .
  10. ^ ab Стивен Гилмор, Введение в стохастическое моделирование - Алгоритмы стохастического моделирования, Эдинбургский университет, [онлайн] доступно по адресу http://www.doc.ic.ac.uk/~jb/conferences/pasta2006/slides/stochastic-simulation -введение.pdf
  11. ^ Майкл А. Гибсон и Иехошуа Брук, Эффективное точное стохастическое моделирование химических систем со многими видами и множеством каналов , J. Phys. хим. А, 104:1876–1899, 2000.
  12. ^ Ю. Цао, Х. Ли и Л. Петцольд. Эффективная формулировка алгоритма стохастического моделирования химически реагирующих систем , J. Chem. Физика, 121(9):4059–4067, 2004.
  13. ^ Гиллеспи, DT (1976). «Общий метод численного моделирования стохастической эволюции во времени связанных химических реакций». Журнал вычислительной физики . 22 (4): 403–434. Бибкод : 1976JCoPh..22..403G. дои : 10.1016/0021-9991(76)90041-3.
  14. ^ HT Бэнкс, Анна Бройдо, Брэнди Кантер, Кейтлин Гайверт, Шухуа Ху, Мишель Джойнер, Кэтрин Линк, Алгоритмы моделирования для моделей цепей Маркова с непрерывным временем, [онлайн] доступно по адресу http://www.ncsu.edu/crsc/reports/ ftp/pdf/crsc-tr11-17.pdf
  15. ^ Разлив, Ф; Майни, ПК; Бирн, HM (2016). «Оптимизация моделирования случайных процессов путем устранения противоположных реакций». Журнал химической физики . 144 (8): 084105. arXiv : 1602.02655 . Бибкод : 2016JChPh.144h4105S. дои : 10.1063/1.4942413. PMID  26931679. S2CID  13334842.
  16. ^ Креспо-Маркес, А., Р.Р. Усано и Р.Д. Аснар, 1993, «Непрерывное и дискретное моделирование в системе планирования производства. Сравнительное исследование»
  17. ^ Луи Дж. Бирта, Гилберт Арбез (2007). Моделирование и симуляция, с. 255. Спрингер.
  18. ^ «Учебное пособие по балансировке шестов».
  19. ^ Университет Нотр-Дам, Нормальное распределение, [онлайн] доступно по адресу http://www3.nd.edu/~rwilliam/stats1/x21.pdf.
  20. ^ Франсуа Э. Селье, Приложения, методы и инструменты комбинированного непрерывного/дискретного моделирования
  21. ^ Пролив, Ф.; и другие. (2015). «Гибридные подходы к многовидовым стохастическим моделям реакции-диффузии». Журнал вычислительной физики . 299 : 429–445. arXiv : 1507.07992 . Бибкод : 2015JCoPh.299..429S. дои : 10.1016/j.jcp.2015.07.002. ПМЦ 4554296 . ПМИД  26478601. 
  22. ^ ab Косма Рохилла Шализи, Монте-Карло и другие виды стохастического моделирования, [онлайн] доступно по адресу http://bactra.org/notebooks/monte-carlo.html.
  23. ^ ab Дональд Э. Кнут, Искусство компьютерного программирования, Том 2: Получисловые алгоритмы - глава 3: Случайные числа (Аддисон-Уэсли, Бостон, 1998).
  24. ^ Андреас Хелландер, Стохастическое моделирование и методы Монте-Карло, [онлайн] доступно по адресу http://www.it.uu.se/edu/course/homepage/bervet2/MCkompendium/mc.pdf.

Внешние ссылки

Программное обеспечение