stringtranslate.com

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

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

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

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

Этимология

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

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

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

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

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

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

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

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

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

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

Определить Для честной монеты обе реализации равновероятны. Мы можем сгенерировать реализации этой случайной величины X из равномерного распределения, предоставленного генератором случайных чисел (ГСЧ), имея если ГСЧ выводит значение между 0 и 0,5 и если ГСЧ выводит значение между 0,5 и 1. Конечно, два результата могут быть не равновероятны (например, успех лечения). [6]

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

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

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

HHH, HHT, HTH, THH , TTH, THT, HTT, TTT

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

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

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

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

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

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

метод прыжка τ

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

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

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

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

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

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

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

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

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

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

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

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

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

Распределение Стьюдента используется в финансах как вероятностная модель доходности активов. Функция плотности распределения Стьюдента задается следующим уравнением: [4] где — число степеней свободы , а — гамма-функция .

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

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

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

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

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

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

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

Приложение

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

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

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

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

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

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

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

Ссылки

  1. ^ abcd ДЛОУГЕ, М.; ФАБРИ, Ж.; КУНЦОВА, М.. Simulace pro ekonomy. Прага: ВШЭ, 2005.
  2. ^ abcd Деккинг, Фредерик Мишель (2005). Современное введение в вероятность и статистику: понимание почему и как . Springer. ISBN 1-85233-896-2. OCLC  783259968.
  3. ^ стохастический. (nd). Онлайн-словарь этимологии. Получено 23 января 2014 г. с сайта Dictionary.com: http://dictionary.reference.com/browse/stochastic
  4. ^ abcdef Рачев, Светлозар Т. Стоянов, Стоян В. Фабоцци, Фрэнк Дж., «Глава 1. Концепции вероятности» в книге «Расширенные стохастические модели, оценка рисков и оптимизация портфеля: идеальные показатели риска, неопределенности и производительности», Хобокен, Нью-Джерси, США: Wiley, 2008
  5. ^ Рачев, Светлозар Т.; Стоянов, Стоян В.; Фабоцци, Фрэнк Дж. (2011-04-14). Подход к финансовым рискам на основе метрик вероятности . doi : 10.1002/9781444392715. ISBN 9781444392715.
  6. ^ Распределение Бернулли, Чикагский университет - Департамент статистики, [онлайн] доступно по адресу http://galton.uchicago.edu/~eichler/stat22000/Handouts/l12.pdf
  7. ^ "Биномиальное распределение". Архивировано из оригинала 2014-02-26 . Получено 2014-01-25 .
  8. ^ Хейт, Фрэнк А. (1967). Справочник по распределению Пуассона . Wiley. OCLC  422367440.
  9. ^ Сигман, Карл. «Пуассоновские процессы и составные (пакетные) пуассоновские процессы» (PDF) .
  10. ^ Стивен Гилмор, Введение в стохастическое моделирование - Алгоритмы стохастического моделирования, Эдинбургский университет, [онлайн] доступно по адресу http://www.doc.ic.ac.uk/~jb/conferences/pasta2006/slides/stochastic-simulation-introduction.pdf
  11. ^ Майкл А. Гибсон и Иегошуа Брук, Эффективное точное стохастическое моделирование химических систем со многими видами и многими каналами , J. Phys. Chem. A, 104:1876–1899, 2000.
  12. ^ Y. Cao, H. Li и L. Petzold. Эффективная формулировка алгоритма стохастического моделирования для химически реагирующих систем , J. Chem. Phys, 121(9):4059–4067, 2004.
  13. ^ Gillespie, DT (1976). "Общий метод численного моделирования стохастической временной эволюции связанных химических реакций". Журнал вычислительной физики . 22 (4): 403–434. Bibcode : 1976JCoPh..22..403G. doi : 10.1016/0021-9991(76)90041-3.
  14. ^ HT Banks, Anna Broido, Brandi Canter, Kaitlyn Gayvert, Shuhua Hu, Michele Joyner, Kathryn Link, Simulation Algorithms for Continuous Time Markov Chain Models, [онлайн] доступно по адресу http://www.ncsu.edu/crsc/reports/ftp/pdf/crsc-tr11-17.pdf
  15. ^ Спилл, Ф.; Майни, П.К.; Бирн, Х.М. (2016). «Оптимизация моделирования стохастических процессов путем удаления противоположных реакций». Журнал химической физики . 144 (8): 084105. arXiv : 1602.02655 . Bibcode : 2016JChPh.144h4105S. doi : 10.1063/1.4942413. PMID  26931679. S2CID  13334842.
  16. ^ Креспо-Маркес, А., Р. Р. Усано и Р. Д. Аснар, 1993, «Непрерывное и дискретное моделирование в системе планирования производства. Сравнительное исследование»
  17. ^ Луис Г. Бирта, Жильбер Арбез (2007). Моделирование и имитация, стр. 255. Springer.
  18. ^ «Учебник по балансировке шеста».
  19. ^ Университет Нотр-Дам, Нормальное распределение, [онлайн] доступно по адресу http://www3.nd.edu/~rwilliam/stats1/x21.pdf
  20. ^ Франсуа Э. Селье, Комбинированные приложения, методы и инструменты непрерывного/дискретного моделирования
  21. ^ Spill, F.; et al. (2015). «Гибридные подходы для многовидовых стохастических моделей реакции–диффузии». Журнал вычислительной физики . 299 : 429–445. arXiv : 1507.07992 . Bibcode : 2015JCoPh.299..429S. doi : 10.1016 /j.jcp.2015.07.002. PMC 4554296. PMID  26478601. 
  22. ^ ab Cosma Rohilla Shalizi, Monte Carlo, and Other Kinds of Stochastic Simulation, [онлайн] доступно по адресу http://bactra.org/notebooks/monte-carlo.html
  23. ^ Дональд Э. Кнут, Искусство программирования, том 2: Получисленные алгоритмы - глава 3: Случайные числа (Addison-Wesley, Бостон, 1998).
  24. ^ Андреас Хелландер, Стохастическое моделирование и методы Монте-Карло, [онлайн] доступно по адресу http://www.it.uu.se/edu/course/homepage/bervet2/MCkompendium/mc.pdf

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

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