Стохастическое моделирование — это моделирование системы , в которой переменные могут изменяться стохастически (случайным образом) с индивидуальными вероятностями. [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]
Пример: Монета подбрасывается три раза. Найдите вероятность выпадения ровно двух орлов. Эту задачу можно решить, посмотрев на выборочное пространство. Существует три способа выпадения двух орлов.
Ответ: 3/8 (= 0,375). [7]
Пуассоновский процесс — это процесс, в котором события происходят случайным образом в интервале времени или пространства. [2] [8] Распределение вероятностей для пуассоновских процессов с постоянной скоростью λ за интервал времени задается следующим уравнением. [4]
Определяя как количество событий, которые происходят в интервале времени
Можно показать, что время между прибытиями событий распределено экспоненциально с кумулятивной функцией распределения (CDF) . Обратная экспоненциальная функция CDF определяется как , где — равномерно распределенная случайная величина. [2]
Моделирование процесса Пуассона с постоянной скоростью для числа событий , происходящих в интервале, можно выполнить с помощью следующего алгоритма. [9]
Опубликован Дэном Джиллеспи в 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 распределена нормально с параметрами μ и σ , сокращенно X ∈ N ( μ , σ 2 ) , если плотность случайной величины определяется формулой [4]
Многие вещи на самом деле распределены нормально или очень близко к этому. Например, рост и интеллект распределены приблизительно нормально ; ошибки измерения также часто имеют нормальное распределение . [19]
Экспоненциальное распределение описывает время между событиями в пуассоновском процессе , то есть процессе, в котором события происходят непрерывно и независимо с постоянной средней скоростью.
Экспоненциальное распределение популярно, например, в теории очередей , когда мы хотим смоделировать время, которое нам нужно ждать, пока не произойдет определенное событие. Примерами служат время, пока следующий клиент не войдет в магазин, время, пока определенная компания не обанкротится, или время, пока какая-то машина не обнаружит дефект. [4]
Распределение Стьюдента используется в финансах как вероятностная модель доходности активов. Функция плотности распределения Стьюдента задается следующим уравнением: [4] где — число степеней свободы , а — гамма-функция .
Для больших значений n распределение Стьюдента не имеет существенных отличий от стандартного нормального распределения . Обычно для значений n > 30 распределение Стьюдента считается равным стандартному нормальному распределению .
Часто можно моделировать одну и ту же систему, используя совершенно разные взгляды на мир. Дискретно-событийное моделирование проблемы, а также непрерывно-событийное моделирование проблемы (непрерывное моделирование с дискретными событиями, которые нарушают непрерывный поток) могут в конечном итоге привести к одним и тем же ответам. Однако иногда методы могут отвечать на разные вопросы о системе. Если нам обязательно нужно ответить на все вопросы или если мы не знаем, для каких целей будет использоваться модель, удобно применять комбинированную непрерывно-дискретную методологию . [20] Подобные методы могут изменяться от дискретного, стохастического описания к детерминированному, континуальному описанию в зависимости от времени и пространства. [21] Использование этого метода позволяет улавливать шум из-за малого количества копий, при этом его моделирование выполняется намного быстрее, чем с помощью обычного алгоритма Джиллеспи. Кроме того, использование детерминированного континуального описания позволяет моделировать произвольно большие системы.
Монте-Карло — это процедура оценки. Основная идея заключается в том, что если необходимо узнать среднее значение некоторой случайной величины, а ее распределение не может быть установлено, и если возможно взять выборки из распределения, мы можем оценить его, взяв выборки независимо и усреднив их. Если выборок достаточно, то закон больших чисел гласит, что среднее значение должно быть близко к истинному значению. Центральная предельная теорема гласит, что среднее значение имеет гауссово распределение вокруг истинного значения. [22]
В качестве простого примера предположим, что нам нужно измерить площадь фигуры со сложным, нерегулярным контуром. Подход Монте-Карло заключается в том, чтобы нарисовать квадрат вокруг фигуры и измерить квадрат. Затем мы бросаем дротики в квадрат, как можно более равномерно. Доля дротиков, падающих на фигуру, дает отношение площади фигуры к площади квадрата. Фактически, можно привести к этой форме почти любую интегральную задачу или любую задачу усреднения. Необходимо иметь хороший способ определить, находитесь ли вы внутри контура, и хороший способ выяснить, сколько дротиков нужно бросить. И последнее, но не менее важное: нам нужно бросать дротики равномерно, т. е. использовать хороший генератор случайных чисел . [22]
Существуют широкие возможности использования метода Монте-Карло: [1]
Для имитационных экспериментов (включая Монте-Карло) необходимо генерировать случайные числа (как значения переменных). Проблема в том, что компьютер — это высоко детерминированная машина — по сути, за каждым процессом всегда стоит алгоритм, детерминированное вычисление, меняющее входы на выходы; поэтому нелегко генерировать равномерно распределенные случайные числа на определенном интервале или наборе. [1]
Генератор случайных чисел — это устройство, способное производить последовательность чисел, которые нельзя «легко» идентифицировать с детерминированными свойствами. Такая последовательность называется последовательностью стохастических чисел . [23]
Алгоритмы обычно полагаются на псевдослучайные числа , числа, сгенерированные компьютером имитирующие истинные случайные числа, для генерации реализации, одного из возможных результатов процесса. [24]
Методы получения случайных чисел существуют уже давно и используются во многих различных областях (например, в играх ). Однако эти числа страдают от определенной предвзятости. В настоящее время лучшими методами, которые, как ожидается, дадут действительно случайные последовательности, являются естественные методы, которые используют случайную природу квантовых явлений . [23]