10

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

稍微长一点的版本： 对于一个工作项目，我需要添加几个随机变量，每个变量都由一个值列表给出。例如，rand 的实现。变种。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，这将持续到我们的日子结束来计算:) 更不用说实际了生活，每辆房车的长度将是 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] 永远不会成为现实。然而，随着越来越多的随机变量的不断求和，实现的数量呈指数增长，而跨度仅线性增加，因此跨度中的数字密度随着时间的推移而增加。这会扼杀哈希图的好处。

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

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

预期用途是这样的：您从某些操作中获得每小时的现金流量。一小时的现金流分布是 rv A。下一小时，是 rv B，等等。你的问题是：在 99% 的情况下，最大的损失是什么？因此，您对这 24 小时中的每个小时的现金流进行建模，并将这些现金流作为随机变量添加，以便获得全天总现金流的分布。然后你取 0.01 分位数。

4

4 回答 4

1

尝试减少整个添加所需的通过次数，可能将每个列表（包括最后一个列表）减少到一次通过。

我认为您不能减少添加的总数。

此外，如果适用，您应该研究并行算法和多线程。

在这一点上，大多数处理器能够并行执行加法，给定适当的指令（SSE），这将使加法速度快很多倍（仍然不能解决复杂性问题）。

于 2012-10-24T08:36:08.923 回答
1

正如您在问题中所说，您将需要大量的计算才能获得确切的答案。所以这不会发生。

但是，当您处理随机值时，可以将一些数学应用于该问题。所有这些添加的结果不会导致接近正态分布的东西吗？例如，考虑掷一个骰子。每个数字都有相等的概率，因此实现不遵循正态分布（实际上，他们可能这样做，上周 BBC4 上有一个关于它的节目，它表明彩票球的外观呈正态分布）。但是，如果您掷两个骰子并将它们相加，那么实现确实遵循正态分布。因此，我认为您的计算结果将近似于正态分布，因此找到给定输入集的平均值和 sigma 值就成了问题。

我想有一个必然的问题，这就是结果的用途？了解如何使用结果将有助于决定如何创建结果。

于 2012-10-24T08:39:08.017 回答
1

忽略编程解决方案，随着数据集的增长，您可以显着减少添加的总数。

如果我们定义四个组W、和X，每个组都有三个元素，根据您自己的数学计算，这会导致大量操作：YZ

  • W + X => 9 次操作
  • (W + X) + Y => 27 次操作
  • (W + X + Y) + Z => 81 次操作
  • 总计：117 次操作

但是，如果我们假设您的“添加”操作的严格排序定义使得两个集合{a,b}并且{c,d}总是导致{a+c,a+d,b+c,b+d}那么您的操作是关联的。这意味着您可以这样做：

  • W + X => 9 次操作
  • Y + Z => 9 次操作
  • (W + X) + (Y + Z) => 81 次操作
  • 总计：99 次操作

对于一个简单的情况，这节省了 18 次操作。如果将上述扩展至 6 组，每组 3 名成员，则操作总数可以从 1089 减少到 837 - 几​​乎节省 20%。您拥有的数据越多，这种改进就越明显（更多集合或更多元素将节省更多）。

此外，这为更好的并行化打开了问题：如果您有 200 个组要处理，您可以首先并行组合 100 对，然后是 50 对或结果，然后是 25 对，等等。这将允许很大程度的并行性，应该给你更好的表现。（例如，在大约 10 个并行操作中将添加 720 个集合，因为每个并行添加将允许增加COUNT2 倍。）

我绝对不是这方面的专家，但对于使用典型 GPU 的并行处理能力来说，这似乎是一个理想的问题——我的理解是，像 CUDA 这样的东西可以让并行处理所有这些计算变得很短。

编辑：如果你真正的问题是“你最大的损失是什么”，那么这是一个更容易的问题。鉴于最终集合中的每个值都是每个“组件”集合中的一个值的总和，通常通过组合每个组件集中的最低值来找到最大的损失。找到这些较低的值（每组一个值）是一项更简单的工作，然后您只需将有限的一组值相加即可。

于 2012-10-24T09:04:33.943 回答
0

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

近似方法通过大量抽样对随机变量的总和进行建模。基本上，有了随机变量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如果A[nA] = min( A[nA], B[nB], C[nC])（计数A,B,C已排序）则加一。这样，我可以得到nA, nB, nC最小的元素A,B,C，我必须将它们相加（彼此相加）并取第 X 个最小的和（其中 X 是 1% 乘以总和的总组合数，即 3*3* 3 为A,B,C）。这也告诉何时停止增加nA,nB,nC- 当nA*nB*nC> X时停止。

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

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

于 2012-10-30T09:13:14.053 回答