随机模拟

随机模拟是跟踪变量演化的模拟，这些变量可以以一定的概率随机（随机）变化。

利用随机模型，创建一个基于一组随机值的投影。记录输出，并用一组新的变量的随机值重复投影。重复这些步骤，直到收集到足够数量的数据为止。最后，输出的分布显示了关于变量或多或少可能落入的值范围的最可能的估计以及期望框架。

离散事件仿真

为了确定在一个随机模拟未来事件，计算所有模型的状态可能发生的变化概率，然后排列数组。接下来，取数组的累积和，最后的单元包含数字R，其中R是总事件概率。这种累积的阵列，现在是一个离散的累积分布，可用于下一个事件，通过随机选择一个数 z~U(0,R)，并且选择的第一个事件，使得z小于与该事件相关联的概率。

A probability distribution is used to describe the potential outcome of a random variable.

概率分布- Probability distributions：一个概率分布被用来描述一个随机变量的潜在结果。变量受到限制，变量只能接受离散值的结果。

伯努利分布-Bernoulli distribution

如果一个随机变量X服从关于p的伯努利分布，那么只有两个可能的结果，通常编码为1（成功或默认）或0（失败或存活）。

Example: Toss of coin 丢硬币游戏：

Define

X = 1 if head comes up and
X = 0 if tail comes up

每种概率都是:P (X = 1) = P (X = 0) = 1/2。当然，这两种出来的结果可能不是绝对相等的（例如医疗成功[4]）。

二项式分布-Binomial distribution

将参数n和p的二项分布，随机变量Y作为n个独立且完全相同的Bernoulli分布随机变量X1，X2，…，Xn之和。

Example: 硬币掷三次。找到得到两个正面head的概率。这个问题可以通过观察样本空间来解决。有三种方法可以得到两个正面。

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

答案是： 3/8 (= 0.375).[5]

泊松分布-Poisson distribution

泊松分布仅依赖于一个参数λ，当参数p为小数时，泊松分布可被解释为二项分布的近似。泊松分布随机变量通常用于描述在一定时间间隔内发生的事件的随机数。

典型的示例问题：如果一家公司生产的3%的电灯泡有缺陷，那么在100个灯泡的样本中，发现5个灯泡有缺陷的概率。（E-0.25＝0.7788）

方法：

直接和第一反应方法

1977年，由Dan Gillespie出版，是对累积数组的线性搜索。见Gillespie algorithm。

Gillespie的随机模拟算法（Stochastic Simulation Algorithm，SSA）本质上是一种通过考虑化学反应体系固有的随机性来精确模拟该体系时间演化的方法。

它严格基于化学主方程所依据的相同的微观物理为前提，并且比由ODE数学表示的确定性反应速率方程(RRE，reaction rate equation )更真实地表示了系统的演化。

与化学主方程一样，在大量反应物的限制下，SSA收敛到与质量作用定律相同的解。

下一步反应法 - Next reaction method

发表在2000年。这是对第一反应方法的改进，其中未使用的反应时间被重复使用。为了使反应的采样更有效，使用索引优先级队列来存储反应时间。另一方面，为了使效率的再计算更有效，使用依赖图。这种依赖关系图（ dependency graph）表明在特定的反应发生后更新反应的趋势。

优化和排序直接法 - Optimised and sorting direct methods

发表于2004和2005。这些方法对累积数组进行排序，以减少算法的平均搜索深度。前者进行预模拟以估计反应的激发频率，而后者对累积阵列进行动态排序。

对数直接法 - Logarithmic direct method

发表于2006。这是对累积数组的二值搜索，从而将反应采样的最坏情况下的时间复杂度减少到O（log m）。

偏倾向法 - Partial-propensity methods

发表于2009, 2010，2011（Ramaswamy 2009, 2010, 2011）。使用因数输出，部分反应倾向（partial reaction propensities ），以减少计算成本与网络中物种的数量成比例，而不是（更大）数量的反应。存在四种变体：

• PDM，偏倾向直接法（the partial-propensity direct method）。计算成本与反应网络中不同物种的数量成线性关系，与网络的耦合类别无关(Ramaswamy 2009)。
• SPDM，排序偏倾向直接法（the sorting partial-propensity direct method）。使用动态气泡排序来减少反应速率跨越几个数量级的多尺度反应网络中计算成本的预因子(Ramaswamy 2009)。
• PSSA-CR，部分倾向SSA与成分抑制采样（the partial-propensity SSA with composition-rejection sampling）。使用合成拒绝采样(Slepoy 2008)将弱耦合网络(Ramaswamy 2010)的计算成本降低到恒定时间(即，独立于网络大小)。
• DPDM，延迟偏倾向直接法（the delay partial-propensity direct method）。通过提供延迟SSA方法的部分倾向性变体（Brasun 2005，CAI 2007），将PDM扩展到引起时间延迟的反应网络（RAMASWAMY 2011）。

部分倾向法（partial-propensity methods）的使用限于基本化学反应，即与最多两种不同反应物的反应。每一个非基本化学反应都可以等价地分解成一组基本的化学反应，但是需要牺牲一个线性（按反应级数）增加网络大小。

近似方法

随机模拟的一个普遍缺点是，对于大系统，发生太多事件，而这些事件在模拟中无法全部考虑。下面的方法可以通过一些近似来显著地提高仿真速度。

跳跃法-\tau leaping method

由于SSA方法跟踪每个转换，所以对于某些应用程序来说，由于时间复杂度很高，因此不切实际。Gillespie提出了一个近似过程，即跳跃法 tau-leaping method，它以极小的精度损失减少了计算时间。[8]跳跃法不是像SSA方法那样在时间上采取增量步骤，而是在每个时间步长上跟踪X(t)，而是从一个子区间跳跃到另一个子区间。下一步，估计在给定的子区间中需要进行多少个过渡。假设跃迁的值足够小，使得沿子区间 [t, t + τ]的转变率的值没有显著变化。这个条件被称为跳跃条件。因此，跳跃方法具有在一次跳跃中模拟许多跃迁的优点，同时不损失显著的精度，从而加快了计算时间。

条件差分法  - Conditional Difference Method

此方法仅考虑可逆过程的相反事件的净速率来近似可逆过程（包括随机游走/扩散过程）。这种方法的主要优点是可以用一个简单的if语句实现它，用新的、有效的速率替换模型的先前的转换速率。因此，具有替换的转换速率的模型可以用常规SSA来解决。

Continuous simulation-连续模拟

在离散状态空间中，可以清楚地区分连续空间中的特定状态（值），但由于一定的连续性，这是不能区分的。系统通常随时间变化，模型的变量，然后连续变化。连续模拟在给定确定状态变量变化率的微分方程，模拟系统随时间的变化。连续系统的例子是捕食者/食饵模型（ predator/prey model）或车极平衡（cart-pole balancing）

Monte Carlo simulation

Monte Carlo是一个估计过程。其主要思想是，如果需要知道某些随机变量的平均值并且其分布不能被陈述，然而如果可以从分布中取样，就可以通过独立地取样并对它们进行平均来估计它。如果有足够的样本，那么大数定律说平均值必须接近于真值。中心极限定理表示平均值在真值附近服从高斯分布。

作为一个简单的例子，假设我们需要测量具有复杂、不规则轮廓的形状区域。 Monte Carlo的方法是在形状周围画一个正方形并测量正方形。然后我们尽可能均匀地把飞镖扔进广场。飞镖落在形状上的比例给出了形状的面积与正方形面积的比值。事实上，可以将几乎任何积分问题或任何平均问题都铸造成这种形式。必须有一个很好的方法来判断你是否在轮廓内，以及一个很好的方法来计算有多少飞镖投掷。很重要的是，我们需要均匀地掷镖，也就是说，需要使用一个好的随机数发生器。

【出处： https://en.wikipedia.org/wiki/Stochastic_simulation】

下图就是Monte Carlo的方法的案例：

 【来源： https://en.wikipedia.org/wiki/Monte_Carlo_method】

应用

使用蒙特卡洛方法有广泛的应用领域：

• 利用随机变量生成的统计实验（如骰子）
• 抽样方法
• 数学（例如数值积分，多重积分）
• 可靠性工程
• 项目管理（SixSigma）
• 粒子物理学实验
• 模拟
• 风险度量/风险管理（如投资组合价值估计）
• 经济学（例如寻找最佳拟合需求曲线）
• 过程仿真
• 运筹学

【出处： https://en.wikipedia.org/wiki/Stochastic_simulation  】

2. 发展历史

描述

词源

随机“Stochastic ”的起初意思是“关于猜想”- "pertaining to conjecture"；‘’来自希腊的斯托克斯塔克语“能够猜测，猜测” -"able to guess, conjecturing"；来自stokhazesthai 的“猜测”；来自斯托克语“猜测，目标，标记”-"a guess, aim, target, mark".。"randomly determined" 首先记录在1934的德国SuxasTik。

1977年，第一反应方法由Dan Gillespie出版，是对累积数组的线性搜索。见Gillespie algorithm。Gillespie的随机模拟算法(Stochastic Simulation Algorithm，SSA)实质上是通过适当考虑这种系统固有的随机性来模拟数值，它可以充分搅拌的化学反应系统的时间演化的精确过程。

下一步反应法 - Next reaction method，发表在2000年。这是对第一反应方法的改进，其中未使用的反应时间被重复使用。为了使反应的采样更有效，使用索引优先级队列来存储反应时间。

优化和排序直接法 - Optimised and sorting direct methods，发表于2004和2005年。这些方法对累积数组进行排序，以减少算法的平均搜索深度。

对数直接法 - Logarithmic direct method，发表于2006年。这是对累积数组的二值搜索，从而将反应采样的最坏情况下的时间复杂度减少到O（log m）。

偏倾向法 - Partial-propensity methods，发表于2009, 2010，2011（Ramaswamy 2009, 2010, 2011）。使用因数输出，部分反应倾向（partial reaction propensities），以减少计算成本与网络中物种的数量成比例，而不是（更大）数量的反应。存在四种变体：

• PDM，偏倾向直接法（the partial-propensity direct method）。2009，Ramaswamy发表《A new class of highly efficient exact stochastic simulation algorithms for chemical reaction networks》。
• SPDM，排序偏倾向直接法（the sorting partial-propensity direct method）。2009，Ramaswamy发表《A partial-propensity variant of the composition-rejection stochastic simulation algorithm for chemical reaction networks》。
• PSSA-CR，部分倾向SSA与成分抑制采样（the partial-propensity SSA with composition-rejection sampling）。《A constant-time kinetic Monte Carlo algorithm for simulation of large biochemical reaction networks》使用合成拒绝采样(Slepoy 2008)将弱耦合网络(Ramaswamy 2010)的计算成本降低到恒定时间(即，独立于网络大小)《Fast exact stochastic simulation algorithms using partial propensities》。
• DPDM，延迟偏倾向直接法（the delay partial-propensity direct method）。通过提供延迟SSA方法的部分倾向性变体（Brasun 2005《A pooled analysis of bone marrow micrometastasis in breast cancer》，CAI 2007），将PDM扩展到引起时间延迟的反应网络（RAMASWAMY 2011）。

【出处： https://en.wikipedia.org/wiki/Stochastic_simulation   】

主要事件

3. 发展分析

瓶颈

随机模拟的一个普遍缺点是，对于大系统，发生太多事件，而这些事件在模拟中无法全部考虑。

Monte Carlo缺点：

 1.对于确定性问题需要转化成随机性问题。

2.误差是概率误差。

3.通常需要较多的计算步数N.

未来发展方向

对于模拟实验（包括蒙特卡罗模拟），需要产生随机数（作为变量值）。 问题是计算机是高度确定性的机器——基本上，在每一个进程的后面总是有一个算法，一个确定性的计算，将输入转换为输出； 因此，在定义的区间或集合上生成均匀分布的随机数并不容易。

随机数发生器是一种能够产生用确定性属性“容易”识别的数字序列的设备。 这个序列称为随机数序列。 算法通常依赖于伪随机数，计算机生成的数字来模拟真实随机数。 获得随机数的方法已经存在很长时间了，并且被用于许多不同的领域（例如游戏）。 然而，这些数字有一定的偏差。 目前，产生真正随机序列的最好方法是：利用量子现象（ quantum phenomena）的随机性的自然方法。

Contributor: Ruiying Cai