0

我正在制作一个需要生成确定性随机事件的应用程序。它们需要具有确定性，以便我可以计算应用程序关闭时发生的事件。我想找到一个函数 f(time1, time2) 告诉我在任意两个时间点之间发生了多少事件，而不生成完整的过程。也应该是 f(t1,t3) = f(t1,t2) + f(t2, t3)。

我从这个问题开始，但开始了这个新问题，所以我现在可以重写它，因为我对我正在寻找的东西有了更好的了解。

我在 Math Overflow 上提出了一个关于寻找 f 公式的问题，因为它似乎更像是一个数学问题而不是编码问题。

4

2 回答 2

0

如果我理解你的限制，你（A）不想存储你的过程，因为它很大。(B) 出于同样的原因，不想重复生成进程。但是您可以尝试混合策略。

获取任何随机数生成器 R，您可以 (A) 确定性地播种并 (B) 读取状态（请参阅下文如何伪造它）。

现在：

  • 存储R.state（或使用硬编码的东西设置它）
  • 生成N样本并使用它们来生成您的泊松过程。
  • 存储 (time, Poisson CDF, R.state)的三元组

稍后当您返回数据时，您可以找到感兴趣区间、查找R.state和 CDF 之前的最后时间，并开始重新生成您的泊松过程。您将永远不必生成N额外的样本，但您只需存储每个Nth状态。

现在如何存储随机数生成器的状态？其中一些具有用于读取其状态的 API 函数。另一个技巧是使用两个生成器R1, R2. R2然后你使用每 N 个点播种R1。的值R1就是您存储的“状态”。

于 2013-10-28T10:39:06.540 回答
0

让我们重写问题。假设你的f存在。然后，您可以使用二进制搜索找到下一个事件的时间，达到您想要的任何精度。所以f先构建。

那么我们该如何创造f呢？好吧，我们只需要计算ffrom0到任意任意t的 then f(s, t) = f(0, t) - f(0, s)。

我们甚至不需要能够直接为每个t. 如果我们可以在每个整数上计算它，并且如果我们在区间的两端都有它，如果我们可以在中点计算它，那就足够了。由于f它是非递减的并且始终是整数，因此二分算法最终将t夹在我们知道f的具有相同值的两个点之间。

现在我们有了一个方法。我们将以整数计算。然后，一旦我们t夹住，就开始平分，直到我们的下限和上限f(0,t)相同。

我们可以通过生成一个随机数来从整数到整数，然后使用泊松分布来找出发生了多少事件。如果我们知道f在一个区间的两端，我们可以用同样的技巧在中点找到它，但是这次知道在区间的前半部分发生的事件的数量是由二项分布描述的。

担心我们需要一个带有 2 个不相关的“下一步移动”选项的伪随机生成器的诀窍。其中一个用于当我们将下一个区间/土地移动到区间的上半部分时。另一个用于当我们停止移动区间/降落在区间的下半部分时。我们需要在两者之间行走的路径，而不是给出相同的答案。否则，您的随机事件将以奇怪的周期性方式分布。我建议通过使用两个使用相同范围内的种子的不同生成器来做到这一点。（如果它们很接近，但不相同，你可以重复你正在做的那个，直到种子在共同范围内结束......）你使用哪个生成器取决于最后一次翻转带你的方向。

找出正确的使用方法可能需要一些思考。但希望这比你开始的问题更容易解决！

于 2013-10-28T07:29:17.353 回答