在C++中快速添加随机变量

Question

简短版本:如何最有效地表示和添加由其实现列表给出的两个随机变量？

版本更长: 对于工作项目,我需要添加几个随机变量,每个变量都由一个值列表给出.例如,兰德的实现.变种.A是{1,2,3},B的实现是{5,6,7}.因此,我需要的是A + B的分布,即{1 + 5,1 + 6,1 + 7,2 + 5,2 + 6,2 + 7,3 + 5,3 + 6,3 + 7 }.对于不同的随机变量(C,D,...),我需要做几次这样的添加(让我们将这个数量的加法表示为COUNT,其中COUNT可能达到720).

问题是:如果我使用这种将A的每个实现与B的每个实现相加的愚蠢算法,则复杂度在COUNT中是指数的.因此,对于每个rv由三个值给出的情况,COUNT = 720的计算量是3 ^ 720~3.36xe ^ 343,这将持续到我们计算的日期结束:)更不用说在实际中生活中,每个rv的长度将是5000+.

解决方案: 1 /第一个解决方案是使用我可以进行舍入的事实,即具有整数实现值.像这样,我可以将每个rv表示为向量,并且在对应于实现的索引处,我具有值1(当rv具有此实现一次时).因此对于rv A和从0到10索引的实现向量,表示A的向量将是[0,1,1,1,0,0,0 ...]并且B的表示将是[0, 0,0,0,0,1,1,1,0,0,10.现在我通过遍历这些向量来创建A + B,并执行与上面相同的操作(将每个A的实现与B的每个实现相加并将其编码为相同的向量结构,向量长度中的二次复杂度).这种方法的好处是复杂性受到约束.这种方法的问题在于,在实际应用中,A的实现将在区间[-50000,

2 /为了拥有更短的数组,可以使用散列映射,这很可能会减少A + B中涉及的操作(数组访问)的数量,因为假设是理论跨度的一些非平凡部分[-50K, 50K]永远不会成为现实.然而,随着越来越多的随机变量的持续求和,实现的数量呈指数增长,而跨度仅线性增加,因此跨度中的数字密度随时间增加.这会破坏hashmap的好处.

所以问题是:我怎样才能有效地解决这个问题呢？计算电力交易中的VaR需要解决方案,其中所有分布都是凭经验给出的,并且不像普通分布,因此公式是没有用的,我们只能模拟.

---

使用数学被视为我们部门的一半的第一选择.是数学家.但是,我们要添加的分布表现不佳,COUNT = 720是极端的.更有可能的是,我们将使用COUNT = 24来获得每日VaR.考虑到要添加的分布的不良行为,对于COUNT = 24,中心极限定理不会过于紧密(SUM(A1,A2,...,A24)的发音不会接近正常).在我们计算可能的风险时,我们希望尽可能精确地得到一个数字.

预期用途是:您从某些操作中获得每小时的casflow.一小时的现金流量分配是rv A.对于下一个小时,它是rv B等等.你的问题是:99%的案件中最大的损失是多少？因此,您为这24小时中的每一小时模拟现金流量,并将这些现金流量作为随机变量添加,以便在一整天内获得总流量的分布.然后你取0.01分位数.

Answer 1

基本上有两种方法。近似值和精确值...

近似方法通过大量采样对随机变量的总和进行建模。基本上，有了随机变量A，B我们从每个 rv 中随机采样 50K 次，将采样值相加（这里 SSE 可以提供很大帮助），我们就得到了 的分布A+B。这就是数学家在 Mathematica 中执行此操作的方式。

精确方法利用了 Dan Puzey 提出的方法，即仅对每个 rv 密度的一小部分进行求和。假设我们有具有以下“密度”的随机变量（为了简单起见，每个值具有相同的可能性）

A = {-5,-3,-2}
B = {+0,+1,+2}
C = {+7,+8,+9}

的总和A+B+C将为

{2,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,8,8,8,9}

如果我想精确地知道整个分布，我别无选择，只能将 A 的每个元素与 B 的每个元素相加，然后将这个和的每个元素与 C 的每个元素相加。但是，如果我只想要 99% VaR的总和，即总和的 1% 百分位，我只需对 的最小元素求和A,B,C。

更准确地说，我将从nA,nB,nC每个分布中获取最小的元素。为了确定nA,nB,nC这一点，我们首先将它们设置为 1。然后，如果（指望已排序）则加nA一。这样，我可以获得必须相加的最小元素（每个元素彼此相加），并取第 X 个最小和（其中 X 是 1% 乘以和的总组合计数，即 3*3* 3 为)。这也告诉我们何时停止增加- 当> X时停止。A[nA] = min( A[nA], B[nB], C[nC])A,B,CnA, nB, nCA,B,CA,B,CnA,nB,nCnA*nB*nC

A+B+C然而，像这样我再次做同样的冗余，即我正在计算1% 百分位数左侧的整个分布。然而，即使这也比计算整个发行版要短得多A+B+C。但我相信应该有一个简单的迭代算法来准确地告诉给定的 VaR 数，其中O(a*b)是a添加的 rv 数量，b是每个 rv 密度中的最大元素数

对于任何关于我是否正确的评论，我都会很高兴。