65

我想生成一些伪随机数，到目前为止，我对 .Net 库的Random.Next(int min, int max)功能非常满意。这种类型的 PRNG应该使用均匀分布，但我非常想使用指数分布生成一些数字。

我正在使用 C# 编程，尽管我会接受伪代码或 C++、Java 等。

有什么建议/代码片段/算法/想法吗？

4

9 回答 9

112

由于您可以访问统一的随机数生成器，因此使用反演方法很容易生成与您知道其 CDF 的其他分布一起分布的随机数。

因此，生成一个统一的随机数u, in [0,1)，然后x通过以下方式计算：

x = log(1-u)/(-λ),

其中λ是指数分布的速率参数。现在，x是一个具有指数分布的随机数。请注意，log上面是ln自然对数。

于 2010-01-21T02:44:10.243 回答
16

抽样基本定理认为，如果你能对期望的分布进行归一化、积分和反转，你就可以自由自在了。

如果您有所需的分布F(x)在[a,b]. 你计算

C(y) = \int_a^y F(x) dx

反转得到C^{-1}，均匀地扔z在 [0,1) 上并找到

x_i = C^{-1}(z_i)

这将具有所需的分布。

在你的情况下：F(x) = ke^{-kx}我会假设你想要[0,infinity]. 我们得到：

C(y) = 1 - e^{-ky}

这是可逆的

x = -1/k  ln(1 - z)

对于 z 均匀地抛出[0,1)。

但是，坦率地说，使用调试良好的库会更聪明，除非您这样做是为了自己的启迪。

于 2010-01-21T02:44:58.067 回答
11

这是我在维基百科上找到的公式：

T = -Ln(u) / λ

我们在 [0,1] 中创建一个具有均匀分布 (u) 的随机数，我们得到 x：

随机 R = 新随机（）；

双 u = R. NextDouble();

双 x = -Math.Log(u)/(λ);

于 2020-12-21T14:01:52.373 回答
7

如果您想要好的随机数，请考虑链接到 gsl 例程：http ://www.gnu.org/software/gsl/ 。他们有例行公事gsl_ran_exponential。如果您想使用在 [0, 1) 上均匀分布的内置生成器生成随机数（例如 u=Random.Next(0, N-1)/N，对于一些较大的 N），那么只需使用：

-mu * log (1-u)

请参阅 gsl 源代码中的 randist/exponential.c。

编辑：只是为了与后来的一些答案进行比较——这相当于 mu = 1/lambda。这里的 mu 是分布的平均值，也称为 OP 链接到的维基百科页面上的比例参数，而 lambda 是速率参数。

于 2010-01-21T02:34:00.620 回答
4

指数分布的一个有趣特性：考虑具有指数到达间隔时间的到达过程。取任意时间段（t1，t2）和该时间段内的到达。这些到达均匀分布在 t1 和 t2 之间。（谢尔顿罗斯，随机过程）。

如果我有一个伪随机数生成器，并且由于某种原因（例如我的软件无法计算日志），您不想进行上述转换，而是想要一个平均值为 1.0 的指数 rv。

你可以 ：

1) 创建 1001 个 U(0,1) 随机变量。

2）按顺序排序

3）从第一个中减去第二个，从第二个中减去第三个，......得到1000个差异。

4) 这些差异是指数 RVs，来自均值 = 1.0 的分布。

我认为效率较低，但也是达到同一目的的一种手段。

于 2010-01-25T20:23:59.157 回答
1

Dan Dyer的开源Uncommons Math 库为 Java 提供随机数生成器、概率分布、组合和统计。

在其他有价值的课程中，ExponentialGenerator基本上实现了@Alok Singhal 解释的想法。在其教程博客中，给出了一个代码片段来模拟一些平均每分钟发生 10 次的随机事件：

final long oneMinute = 60000;
Random rng = new MersenneTwisterRNG();

// Generate events at an average rate of 10 per minute.
ExponentialGenerator gen = new ExponentialGenerator(10, rng);
boolean running = true;
while (true)
{
    long interval = Math.round(gen.nextValue() * oneMinute);
    Thread.sleep(interval);

    // Fire event here.
}

当然，如果你更喜欢时间单位per second（而不是a minute这里），你只需要设置final long oneMinute = 1000.

深入研究 的方法的源代码，你会发现Generating_exponential_variates [wiki]中描述的所谓逆变换采样：nextValue()ExponentialGenerator

public Double nextValue()
{
    double u;
    do
    {
        // Get a uniformly-distributed random double between
        // zero (inclusive) and 1 (exclusive)
        u = rng.nextDouble();
    } while (u == 0d); // Reject zero, u must be positive for this to work.
    return (-Math.log(u)) / rate.nextValue();
}

PS：最近我在使用 Uncommons Math 库。谢谢丹戴尔。

于 2014-06-26T12:12:58.250 回答
1

还有另一种生成指数（rate·）随机变量的方法，尽管它不像现在使用对数那么方便。它来自 John von Neumann (1951) 的算法，仅使用比较。

  1. 让。scale_ 1/rate设置highpart为 0。
  2. 生成一个 uniform(0, scale) 随机变量（例如NextDouble()*scale），调用它u。
  3. 设置val为u，并设置accept为 1。
  4. 生成一个 uniform(0, scale) 随机变量，调用它v。
  5. 如果u大于v，设置u为v，然后设置accept为 1 减去accept，然后转到步骤 4。
  6. 如果接受为 1，则返回val + highpart。
  7. 添加并scale转到highpart步骤 2。

参考：

  • Von Neumann, J.，“与随机数字相关的各种技术”，1951 年。
于 2020-12-21T15:20:07.990 回答
0

如果我了解您的问题，并且您可以接受有限数量的 PRNG，则可以采用以下方法：

  • 创建一个数组，其中每个元素都在您的指数分布中
  • 生成一个 PRNG，它是数组的整数索引。返回数组中该索引处的元素。
于 2010-01-21T02:30:28.890 回答
-2

这是我在遇到类似要求时使用的：

// sorry.. pseudocode, mine was in Tcl:

int weighted_random (int max) {
    float random_number = rand();
    return floor(max - ceil( max * random_number * random_number))
}

当然，这是对随机数进行平方的公式，因此您可以沿二次曲线生成随机数。

于 2010-01-21T02:31:17.210 回答